Hello everyone, this is Alice Gao.
In this video, I'm going to talk about adaptive dynamic programming, which is one type of
passive reinforcement learning algorithm.
Adaptive dynamic programming is trying to improve on direct utility estimation by taking
advantage of the relationships between the utility values of different states, right.
As I mentioned in the previous video, direct utility estimation is really easy to do and
it's simple but it misses a lot of learning opportunities because it assumes that the
utility of different states are independent.
They are in fact now not independent and they are related to each other via the bellman
equations.
If we already have a fixed policy, then the relationships between the utility values can
be written down as the system of equations we have for policy evaluation.
Let's recall this system of equations we saw for the policy iteration algorithm.
For policy evaluation, we have that the v values are just the solutions of the simplified
bellman equations, which are these equations given below.
Remember that these equations are simpler than the bellman equations because we don't
have the maximization in it, right.
We already have a fixed policy so this policy tells us which action to perform, so we don't
have to take the maximum over all possible actions.
Now if we want to get estimates of the utility values, well we can just write down this system
of equations and then solve for the v values then we're done.
This is exactly what we did for policy evaluation, except now we have some difficulties than
before.
Recall that for the policy duration algorithm, we assume that we have two more pieces of
information.
We have the reward function and we also have the transition probabilities.
But unfortunately for the reinforcement learning setting, we have neither of these, right.
So, how do we figure out the reward function and how do we figure out the transition probabilities?
If we had these two pieces of information, then we can directly we can solve this system
of equations like we did before for policy evaluation.
Well, getting the reward function is relatively simple.
We are going to perform trials in the environment as I explained before.
So, for each trial, when we visit a particular state, we are going to observe how much immediate
reward we get in that state, right.
So, for the reward function, we can directly use the observed rewards.
Now for learning the transition probabilities, it's a little more complicated but not much
more.
So, what are really the transition probabilities?
The transition probability says if I'm in a particular state, if I take a particular
action, then how likely is it that I'm going to transition into this other particular state?
So, we don't have this information directly because every time we perform we take an action,
we're going to get into one deterministic state, right.
So, we're going to only observe the realizations of these probabilities.
We don't have the probabilities directly, but that's okay.
We can directly use these realizations to calculate the probabilities.
This is basically a maximum likelihood approach if you have heard of this terminology before.
You can think about this as a supervised learning problem.
As for conducting trials, the trials provide us with pairs of state and actions, right.
So, in the particular state, if we take a particular action, then we're going to end
up in a resulting state.
So, the input information are the state action pairs and the output information is a resulting
state.
So given these input and output value pairs, we can estimate these probabilities directly.
Here's a numeric example.
Suppose we have during the trials we have performed, we started from s11 three times,
all three times we took the action down and twice we ended up in s12, and one time we
end up back in s11.
So given this data, then we can estimate that the probability of reaching s12 starting from
s11 and taking the action down is two-third.
Basically, we're counting the frequency of reaching a particular state given a state
and action pair.
Given this, we have all the information we need to perform adaptive dynamic programming.
So, let me recap the high level ideas.
We want to solve for the utility value estimates using this system of equations I'm showing
you on the slide.
This is exactly what we do with policy evaluation but we have two pieces of missing information.
One is the reward function, one is the transition probabilities.
For the reward function, we can directly use the observed rewards as estimates for the
reward function.
For the transition probabilities, we can use a supervised learning approach by estimating
each transition probability directly to be the frequency of reaching a particular state
starting from a state and action pair.
So given these two pieces of information, we can solve this system of equations in two
ways as I explained when I talked about policy iteration.
So, we can solve it exactly in cubic time or we can solve it approximately using an
iterative approach.
The iterative approach is basically the same idea as what we did for the value iteration
algorithm.
This is everything I want to talk about for adaptive dynamic programming.
Thank you very much for watching.
I will see you in the next video.
Bye for now.