Skip to main content
Loading Explore guides…
Value Functions & Q-Learning · Acedra
Home
Explore
Computer Science
Value Functions & Q-Learning
Sign in to save
Chat
If YouTube asks you to sign in, open the video on YouTube.
Watch on YouTube
Reload player
Transcript
114 segments
Copy
Hide video
0:05
So as a recap for the last couple lectures, uh we talked a lot about value functions and Q functions. Uh we'll talk about them more today. Uh and as a reminder, value functions entry functions are representing her sum of future expected rewards uh starting at sub and value function will teach rewards partically
0:39
with respect to future rewards. uh and you've seen these uh diagrams a couple times where you can think about uh value as a reward uh state as function as
0:56
uh we've talked about a couple methods so far. Uh the first method that we talked about was policy where we alternate between collecting data and improving our policy. Uh we can think of it as trying to sample for our policy and increasing the log likelihood of actions that have a higher reward in the future. Uh where we subtract the baseline in order to encourage the policy to do more of the above average things than it did before and less of the below average things.
1:27
We then started to talk about active criticisms. uh and in this part we introduce an additional step of this loop where we are first going to estimate uh the expected future reward for our policy and use that to improve the policy. So we have this revised form for our gradient for our policy where we are still taking samples but increasing the likelihood on actions that we think are good and decreasing the likelihood on actions that we think are bad. So these are the methods that we've
2:00
talked about so far. Um we last semester focused a lot on how to do this actor critic algorithm in an off policy way. So instead of only using the data from the last from the current iteration trying to be able to use all of the past data from all past iterations. Uh and do that we needed to be able to estimate a Q function from past policy data. And do that we can use a neural network half of input a state and action and output the value. uh and we derived this equation
2:33
um that's defining the Q function recursively or we can think of the sum of future rewards as the reward at the first time step plus the Q function uh starting at the next state and action. uh we found that this equation holds for any state in action and that means that we can use uh previous state action and next state pairs uh in order to try to learn a key function and specifically the way that we did that is we would sample a state action next state from
3:04
our our buffer of previous data. Uh then we'll sample a next action from the current policy rather than from the past policy. And then we will try to do supervised learning on these targets where the targets are using our estimate our current estimate of the two function for our policy. Um and we pass the input the state the action the next state and the next another sample. So once we formulate this objective using bootstrap values then we can uh do supervised learning to try to not face.
3:43
uh we also talk about for these y eyes to be accurate uh you need to have sufficient coverage in your data set to cover actions that your newest policy. So today we're going to be covering uh valuebased RL method and specifically we'll be talking about uh what I think arguably was the very first deep reinforcement learning method uh and it was based on the Q-learning algorithm uh and so we'll be talking about Q-learning and then we'll also be talking about how
4:09
to implement Q-learning in practice how to make it stable and the goal for today is to think about how Q functions relate to policies how to do RL without learning an explicit policy uh and how to stabilize e-learning if your activity
4:26
Cool. Um, so we're going to start out with a thought exercise uh and a question uh for all of you to think about. So um the say you have some policy uh and for your policy you have a pretty good estimate of the Q functions uh and as a reminder the well I'll put the definition of of Q values up here where the future rewards for a state in action and an object that we're going to be thinking about a lot today is uh if you have some estimate of the Q function um for uh in this case for a policy.
5:05
Then one thing you could do is you could try to uh instead of following some policy that you've uh that you've already learned, you could potentially uh formulate a policy by choosing the action that maximizes your bunch of different candidate actions. uh at a given state instead of following your policy, you could pick the candidate action that has the highest speed up. Um so to continue on this product side, we'll define a policy that does exactly that. Uh that policy has a probability
5:44
of one for taking the action that maximizes the p value and has a probability of zero otherwise. So this is a deterministic policy that always follows what the p value is telling you is the best. Um and then we'll look at this in in the context of an example. So say that we have some 2D navigation problems. Um we're going to be starting somewhere in this blue box and our goal is to reach to the star. You can uh move like we can move in 2D. Um the reward is one at the
6:16
star and zero elsewhere. So very simple. Uh and let's say that our current policy always goes to the right. Um and as one additional point of detail, uh it takes if you're going to move up, it takes one time step to move about this distance and it takes about two time steps to move this distance. Um so my question for you uh is if you define this new policy uh you have this current policy that always goes right, you have an accurate estimate of the Q values for that policy. Um, if you
6:49
define this new policy, is that better than the the current policy? Is it worse than the current policy? Is it the same as the current policy? Um, is it the optimal policy? Uh, and why or why not? Um, so I'll give you well, first any questions about this example.
7:08
Okay. So, I'll give you a few minutes to um talk to your neighbor about these questions. Uh, and then we'll come back and talk through uh the answer.
7:22
It seems like people are talking a little bit less. So maybe you can come back. Uh who wants to share their thoughts? Yeah. Um so let's summarize that and then we'll talk about whether it's the optimal policy. So um summarize the old policy is going right. Uh and so uh that is not optimal because if you're starting here then you're not actually going to hit the star. uh and the that and if you think about what qpi is for the old policy kind of everything in this region right here has is going to
7:55
have a qi equal to one for all of these uh for all of these state uh and actions. Uh also the um yeah and then if you start to think about what uh what 2 pi looks like right here um this is actually where it will well actually sorry take that back. Um v pi is equal to one for everything in this row. It actually depends a little bit on the action what the key function actually is. uh if the for this row if the action is the same as the policy that should move right then if value is
8:33
one if it actually does something else if it goes like up for example then it might actually miss the star if it follows the policy after that uh after taking that action. Now if you look at this row uh for this row two pi of all the states in this row for the action of going right is going to be zero. uh but then if you look at the Q pi for all the states here for the action of going up uh what is the Q value for that but it's one cool and so that's because if you follow up and then follow the
9:11
policy we'll have a word of one and then lastly if we go to this row uh if we have uh s and then going up what is the key value zero our school. Um, and so what this means is that we're going to get uh the new policy. What it's going to do is it's going to be uh going right here. Uh, and then for everything in this row, it will be going up because it's going to be choosing the action that has the maximum value of 2 pi. Uh, but then for this row, all of the Q values are zero
9:45
because uh because all of the key values for the next one are also zero. And so um the uh if you default to the previous behavior it'll stay going to the right. And does anyone want uh to talk discuss the second question like is is this the optimal policy? Yeah. So this policy, the new policy is better than the old one, but it's not the optimal policy because uh in these states the optimal like the best policy should be the one that also is going up uh in order to get this. Yeah. So the
10:26
question was if we iterate this and do it a couple times um this will become the optimal policy, right? And yeah, you're a couple slides ahead, but we'll talk about doing this iteratively. Yeah. So we can get a reward of one. The question was why is this not the optimal policy? So we'll get a reward of one tier which is great but if we're starting at this initial state we actually will just keep on going right we won't go up after defining this new policy and so uh therefore it's not
10:53
going to get a reward of one from all states. >> Yeah. So the question is is there a sense of like if you're getting closer to the star the key would be higher versus not. Um I actually didn't explicitly define this but uh if you have a discount factor that is below one then it will get higher as you get closer. Um everything I've shown here is with a discount factor of one for simplicity. But if you use a discount factor of like 0.9 for example then the Q value here would be one. Then it would
11:23
be 0.9 here. Then 08 here 7 here and so forth. And then it would be um it would still be like zero for this entire row. um just because uh the um uh because you're not you're kind of still somewhat of a function. The other thing potentially to note here is that if your reward was denser as like the reward function instead of being one at the star and zero elsewhere if it was for example the negative distance to the star then you would actually um I won't go through that uh I
11:56
won't go through that on the board but if you go through that example you'll actually see that even in a single step um starting from this policy you would actually get a policy that goes to the star uh from policy. The question is um if I wanted to get the optical policy, I would need to iteratively do this and reconsider um the two pie for the latest policy every time. So yeah, that's true. >> Yeah. So in this example, the question is is it always better? Um in this
12:25
example, the new policy was better than the current policy and um this is actually always going to be the case. So it's always going to be at least as good as the previous policy. Um, and it's never going to well assuming that QPI is accurate, it's always going to be as it's never going to be. Um, and now if the optional policy, then it will be the same. This is starting to think about like can we actually start omitting policies? Uh, so the expected reward um when we do
12:54
this arg we're going to be taking the best action um from state s if you then follow the policy afterwards. And this is going to be at least as good as any action that the policy would have taken. And uh regardless of what the policy is, this is going to be yeah at least as good as uh what that policy. And you can see that because it's taking the the action that has uh the maximum expressive reward. Um so potentially we could actually just forget using policies and just do this
13:30
uh rather than actually explicitly learning a neural network for the policy. Um and so what this looks like as an iterative algorithm is we would run our policy to collect data. Then we would fit a model to estimate qi according to uh that latest batch of data. You could also do this in an off policy way like we talked about in the last lecture. Uh and then to improve your policy, you can just define the policy uh to be the policy that maximizes your Q. Uh and then once you define that new
14:05
policy, you can collect some new data and then estimate again QI but this case QI for your new policy and not your old policy. The policy pi is equal to this. And so we're not learning a neural network for the policy pie. uh we're not explicitly representing it as a model but we um it's helpful to have some notation to refer to the system. The only thing that's the only neural network here the only model here is the two. >> Yeah. So the question is how do we
14:34
generalize this to continuous actions or more expressive action spaces. So um this is generally going to be easiest when you have uh kind of a discrete set of actions that you might take like going up going to the right. uh if you have continuous actions, you actually can still use this algorithm. Uh the although you need to figure out how to perform that max operation, uh there's a couple ways that you could conceivably run this operation right here. Um in
15:03
principle, you could use something like gradient defense, although uh that turns out not to work very well. Um you can potentially there's a variety of reasons why it cannot work very well. And if your actions are not very high dimensional then you can um it might actually be better just to simply try to sample a bunch of different actions and pick the one that has the highest p value. Uh you can also there's other um kind of sampling based optimization algorithms where you can inter sample uh
15:30
and refine your estimates from there. The um yeah so there's a couple things you can do there. uh if you have a discrete action space that that's like like text for example in principle you could um do uh some sort of like dispute for over things where uh the Q value is your um is what you're trying to to maximize in that system. >> Yeah. How does this work in cases where the rewards are very sparse? So we saw it one example where the rewards are sparse and the um it can still work in
16:02
this scenario. Uh the thing that you need to be aware of when the rewards are sparse is that you may need to do this loop of resetting the policy potentially a large number of times because uh each time you do this, you're actually like the first time we only got a good policy here. Um and now if this environment was much bigger, that means that you need to kind of keep on doing it um as you go down. and what is often referred to as a backup. You're sort of backing up the
16:31
reward from here to the other state. And you'll need to do those backups um for as long as the essentially full for as long as the horizon of the problem is. Um so you just need to make sure that you're doing many uh iterations.
16:48
Okay. Um cool. So let's see. We can write this down as an algorithm. Um and so we can take our off policy actor critic algorithm that is fitting pock and uh then instead of using this policy gradient update simply define a new policy that um that's taking actions according to you can think of this as really having two key steps like what we talked about one is estimating pi uh this is often refer to as policy evaluations because you're learning how to what the values are for a policy.
17:32
Uh and note that you can you can do multiple gradient steps here. Uh because uh this is um this isn't like on policy. Uh we're just trying to fit our target. Uh and then the second step is improving our policy. So it's we refer to it as policy improvement. Uh and this sort of two-step iterative procedure is often called policy iteration. uh it's kind of uh on the way to an algorithm like this. Cool. So on the to write this out on the board, what this looks like is
18:10
having a first step where you collect data. Um often times you might collect data from pi. Uh it might also be it could actually potentially be from some other policy. Then you have a next step where you're going to try to fit your estimated function for that policy. Uh and next we can use the um the targets that we defined in the last of R of SA plus gamma 10 where these are from the buffer and this is sampled from our policy. And then lastly, we'll improve our policies by defining
19:04
the new policy
19:10
as being one if X is max value and zero.
19:30
The question is, is this policy deterministic? Uh, yes, this policy is deterministic. Um, the this is actually one reason why you might not want to collect data from this policy because, uh, it's you're not going to have that many data favors in your opinions. Uh, and we'll talk in a couple slides about what policy you might want to collect data from. Yeah. So the question is um when we're fitting these targets why are we sampling from a prime and ra why not do a maximum over axis
20:01
or an average? So um the so you there's a couple things here. So first you can you can uh you can do an average uh and sample multiple times uh and that can give you a better estimate of the target value. Um the second thing is that the um you can actually instead of sampling this from pi you can actually do this improvement step in the q functions target itself. Um so you can actually um instead of defining yi this way, you could consider a target for your tube function to be
20:42
the reward plus gamma times the max over a prime of 2 s. And what this looks like uh is something like this. Uh, and this actually is what gets us to. And one way to think about this, there's a couple ways to think about this. The first is that these targets are actually your Q values for your new policy. Um, so you're actually um you're already putting the the improvement steps in your Q function update and you're actually learning the Q values associated with the new policy that
21:25
you're going to be defining. Um and there's actually another way to look at this as well. Uh so we previously defined this equation um that's true for all states in action. So we defined that the Q function is equal to the reward plus the function at the next state. Uh this is true for all states and actions and it's actually um also is true for any pulse. uh including the optimal policy and you can actually write down another equation that is specifically for the
22:04
optimal policy. Uh and in particular we know that the optimal policy is always going to be taking the actions that maximize our future rewards. The optimal policy is always going to be um the action that it picks is always going to be the one that maximizes the key value. And so we can write down an equation that holds just for the optimal policy which is the same equation as the one there except instead of an expectation over the next action it's a maximization over the next.
22:40
Uh so what that looks like is we're defining the t function as the reward at the current time step plus the sum of future rewards. And for that sum of future rewards, we have some expectation over the next state that will happen. And then because we know that the optimal policy or the best policy is going to be taking the action that is maximizing the t value then we can write this as the max of
23:20
at the next state. Yeah. So the question is why do we why are we talking all about Q and why not V? Um so you can actually also write down these equations for V uh in the same in like a a very similar way. We um the thing that's very nice about Q is that um we can actually get a policy out of Q. So we uh we can if we know what Q is then we can do this argmax over action to get a policy that's better than our previous policy. Whereas with the value function, if we only know V of
23:56
S, then we don't know which action will uh lead to higher. Uh in principle with the value function, you could try to do some sort of look ahead. Like if you have a sense for what the dynamics are, you could try to then um you could try to predict what S prime is and pick actions that are um are maximizing that. Uh the And so what that would look like is um trying to like pick actions that lead to um an expectation uh a like a higher value. Um so you could in principle do
24:42
something like this uh with with V. But uh we don't know what these dynamics are and we can't necessarily predict what the next state will be as a consequence of an action. Uh and so in general it's a lot harder to get a policy out of a value function than is to and to improve our policy ultimately um with a value function than it is with a function.
25:09
So now going back to this equation um this is true for the optimal policy and write Q for the optimal policy here where I'm writing pi star as the optimal policy and if you look at our update right here um we're trying to fit a Q function that is uh that's predicting this and essentially with this equation. You can think about it as this update as we trying to make this equation true. So we're trying to make the left side of the equation equal to the right side of
25:45
the equation. And with when the equation is true, that means our policy is the optical. So essentially one way to think about Q-learning is that when we're optimizing step three, we're trying to find a Q function such that it satisfies this equation, which is only true for the optimal Yeah, sorry. the this is like it's an if and only if so this only holds for the optimal policy and if you have the optimal policy then this >> yeah great question um so the question
26:19
is if we have really good estimates of Q um will this converge we'll talk about this in one minute um so let's first just talk about some terminology really quick um reinforcement learning has a ton of terminology uh it's useful to know some of it so that if someone's talking to you about reinforcement learning or you're reading a paper, you know what they're talking about it. Um, this first equation is often referred to as the Bellman equation. Uh, very useful
26:45
object. Uh, and it's what we were using to try to do policy evaluations for a policy. And the second equation, it's called the Belman optimality equation. Um, because it's specifically for optimal policy. Uh, sometimes people also like informally might call the second one a bellman equation as well. Um but yeah officially uh the first one is solving equation. Second one is solvality equation. Uh you can derive ones that are equations like this that are also for the value function B
27:15
instead of the Q function and people often refer also refer to those as like sol equation and sol. Okay. Um so getting back to the question if we do this iteratively will we convert to um the optional policy uh there's good news and bad news here. Um the good news is that if you're in a very simple setting uh where you can actually store all of your key values in a table for every single state and action. Uh this would be like for a very small discrete state and action space.
27:49
uh and if you have sufficient exploration then this algorithm will converge. Uh so that's the good news. Uh the bad news is that uh basically in any other scenario it is not guaranteed to converge. Uh and you can construct scenarios when it diverges even with just linear functions. Uh which is kind of sad. Uh I guess the the flip side of that is it even though it it can diverge in scenarios uh it can be made to work very well uh and we'll see some examples of
28:22
it working very well at the end of the lecture. >> Yeah. So the question is like what is this this if if mean like what does this statement mean? Uh and it is a bit vague. So um specifically the it doesn't necessarily have to do with the accuracy of your t values because you're actually going to be fitting um fitting your t values like through this process. It's more a statement of the size of your state and action space and if it's small enough that you can maintain this table.
28:50
Uh and there's also a condition on exploration uh where you actually need to have full coverage of the state and actions in your data set. um then it will complete. Okay. Um so one note about this is Q-learning is off policy uh and in particular this equation holds for all state masses and it means that we don't have to have the actions coming from our current policy. Uh and in particular it might actually make a lot of sense for it to be broader than our current policy. Uh because we're going
29:25
to be doing this maximization over our p values. So this when we do this maximization, we're going to be considering a lot of different possible actions. And we uh if we have a discrete action space, we might actually just consider all of the possible actions. And when we do that, we would want our t values to be accurate when we're considering all of them. And if there's one action that we haven't collected data for that we're going to be considering in this optimization, it
29:47
might be erroneously high because we didn't collect any data for it. and then you'll get an inaccurate um target value when you are fitting or and so instead of taking collecting data from our current policy, it'd be useful to collect data from some exploration policy and specifically a policy that's collecting a broader set of actions than our deterministic policy. Um so we want covered for a lot of different actions specifically for this term. Um and there's a couple choices here.
30:20
Uh one choice is to mostly follow our policy like to follow our policy most of the time but with some small probability take a completely random action. Uh, and so what that would look like is a policy that um with some probability I say maybe you can write it as like take a random action with probability at points and follow maybe we can call this pi exploration and uh follow the action. follow your current policy uh with probability 1 -
31:13
uh and the you can write that out slightly more formally up here. Uh and this can be a good choice because it means that you're when you take a un action uniformly at random it means that you'll get very good coverage of the actions that you consider. Uh and oftentimes during like as you proceed through training you might start with a larger epsilon uh so that you have more exploration at the beginning of training and then as your policy is getting better and as you're getting a better
31:43
estimate of your Q function you can then make this smaller and explore less as you go through things. Um so this is called epsilon greedy uh because you are being greedy uh some of the time and epsilon probability of the time you're not being greedy and just taking a risk.
32:06
Okay. Um and then another choice uh that's also somewhat reasonable um although a little bit more complicated is to take actions with probability that is proportional to the key values. And so if you have actions that have a higher t value then take those actions more frequently. And if you act have actions with lower probability then take those actions less frequently. Um one way to uh write this is you could exponentiate your t values so that they're all positive uh and then
32:35
normalize in order to get a distribution over a probability distribution over. Um sometimes this is called uh Boltzman exploration um named after the Bolton distribution where you exponentiate. >> Yeah. So the question is how do you um if you have it's straightforward to do this with discrete actions. How do you do these kinds of approaches when you have continuous actions? Uh the first one is indeed a lot more common with discrete actions. uh the you can still
33:05
do something like this with continuous actions but you would need to define some uh some uniformish distribution over your continuous actions. Um and for that you would need some sort of range or something. Uh instead you could also use like a Gaussian distribution with a wide standard deviation in principle where you sample from that. Uh I think in continuous action faces this second option is a bit more um a bit more common. uh in terms of sampling from it um the
33:34
off top of my head I actually can't can't remember the details of how you would um sample from this but we can uh post on edge after it's possible that the way that you do it is actually just to try to fit a policy um but yeah we can talk about it after okay so putting the pieces together uh what a full key learning algorithm looks like is we'll collect data using some policy We'll add that data to our replay buffer. Then we will sample a batch of data from our replay buffer uh uh uniformly. And
34:07
this is it's useful to sample a batch kind of separately from what we just collected uh so that we are decorrelating um and sampling iid from our replay buffer. And then we will update our Q function by taking the gradient of the uh L2 loss with the target. And so if you write that out, you'll get a gradient that looks like this where um yeah, if you're taking the L2 loss then the um on the inside this is just the inside of the L2 loss and then you use the same rule to get the second term
34:43
right here that's back propagating into your par. Um you can repeat these multiple times. Um so you can actually kind of take multiple gradient steps after collecting a batch of data. Uh in practice it's actually pretty common to set K equals to one. Uh but you can it's more efficient. You're going to be more data efficient if you have a larger K to take more gradient steps for a given box of data. Uh and then you also iterate this process um after you're done taking
35:14
these K gradient steps then you can collect some more data uh and repeat. Yeah. Yeah. So the question was if you're collecting data from any policy, wouldn't that be less optimal than um than like using a good policy or at least using your current policy? Yeah. So the um the reason why you might use a different policy is uh the reason why you might use a different policy is specifically to learn a more accurate Q function. And so it's actually going to help you learn a more
35:47
optimal policy later. And essentially there's this trade-off between collecting less optimal data at the beginning to help you be better later on. And one way to think about this is if you are um say your reinforcement learning agent is trying to help you pick a restaurant, uh if you haven't really explored that many restaurants to know what is a good restaurant, then uh at the beginning probably you want to explore and actually try things even even restaurants that might be
36:11
suboptimal um in order to get a good estimate of like what good restaurants are for a particular person. And then later on um you once you have a good cube function once you have a good estimate for what good uh restaurants are then you might want to then explore less. Um so kind of visually what this looks like is you have some environment you'll initialize your replay buffer as empty. And then at this first step you'll run your policy uh like the F1 3D policy uh
36:40
that's exploring in the environment. You'll then get some transitions that you put into your replay buffer. Uh and then for this part, you'll then use your replay buffer to update your tree function on the data that you see with the goal of trying to get uh something that is not saying the key function of the off. Um so the question is when we combine this with one like can we still call this um off policy because we are collecting data from potentially from a policy that's very similar to our
37:11
current policy. Um because we're using a replay buffer of essentially all of our past experience um when we do these updates it's referred to as off policy. That doesn't mean that like none of the data is from our current policy. So some of the data in the replay buffer will be from the current policy. Uh but essentially what off policy means is that you're not only using that data, you're also using data from other policies. Um in practice what is the sum policy?
37:40
Yeah, so in practice it's exactly what we talked about on the last slide. So um the it would either be uh something like epsilon and greedy uh where with some small probability you're taking a random action and otherwise calling the policy uh or something where you're taking uh actions in proportion to And you might this might actually as we talked about it might actually change during training. Uh you might actually change epsilon during training so that you're more explor you're doing more
38:08
exploration at the beginning and less exploration. >> Yeah. So the question is are we resetting our learning speed iteration? Um oftentimes you will you'll keep your old speed parameters around um kind of warm start them and keep on training on top of them. one important thing. So the result of this algorithm is Q. uh and then to extract a policy out of that. The final policy that you would then deploy is a policy that um is acting according to essentially just the acting pre-release
38:43
where it's taking the actions that maximize your key. Oh, so if the size of the replay buffer is one then like like yeah one like one data point uh then that would be on. So if it's like if it's tiny uh then that's fully on policy. In practice it's replay buffer is a lot larger. Oh. Oh. Oh sorry. Right. Um if the replay buffer size is one if this policy is not the same as as this then that's still off policy because the policy is different. Yeah. A good point. Uh so
39:18
yeah this policy might be different from the one that like directly. Yeah. So how do we manage our replay buffer? make sure that we're not oversampling states and so forth. Um this is generally uh is actually an important consideration with learning algorithms and usually you will discard old data. So you'll have like a first in first out principle where uh this buffer is not infinitely large. Uh oftentimes with learning it is pretty large but you will um you can just pick a fixed size
39:47
uh and then once you have filled it to that size start discarding data and discard the oldest data first. The um one other consideration is that at the very beginning of training the replay buffer might be very small. Uh sometimes to handle that you might uh try to collect more data the very first iteration to pre-populate it. Um there are also algorithms that we won't quite cover that do asynchronous data collection and updates because data collection takes time. updating a neural
40:18
network takes time. And so you could actually have some threads that are actually adding to the replay buffer and other threads that are running updates on your Q function. Um, with those asynchronous algorithms, it's actually especially important uh to think about how this replay buffer is managed so that you're not running like um like a thousand gradient steps on one data point and one gradient step on another.
40:42
Cool. Um let's learn uh let's talk a little bit about what happens in practice when you use these methods. So um we talked about how Q-learning can diverge and uh in general when you run Q-learning with neural networks it can be unstable and one of the reasons for that is uh you have this moving target this max is of two and it seems that our optimization process is very non-stationary uh especially if K is one and one trick is to try to slow down how often you change the target uh the
41:26
target. So um instead of having these targets changed every single time you change your parameters um one idea is you could freeze the parameters of your target network and only update them kind of periodically only update them once um every 100 gradient steps or something like that. So um what this looks like is we can save a separate neural network uh another copy of our two function parameters. We'll call this five star or five prime. And when we save this out, then when we
42:08
for just for this target right here, we can use these new parameters U5 prime uh in our target. These parameters will be frozen. Uh and so it means that uh inside this inner loop, the labels will not change. Uh and so this inner loop is essentially going to be doing supervised learning with with some data being added to the replay buffer. So this should be a lot more stable. Supervised learning is a lot more stable generally. Uh and then uh only periodically then update our target
42:45
network parameters to be the same as our latest uh function. Um so once you use a target network uh this is referred to as the GQM algorithm. Uh it was introduced in 2013 was the basically the like the first DRL method uh at least in in my opinion. Uh and uh they found that you could actually train neural networks to play a variety of different Atari games. Uh and it was yeah one of the first examples of using reinforcement learning to train neural networks to do a pretty
43:19
complicated task. uh and they were actually training it directly from like the the pixel observation uh from the game and prior to that a lot of the reinforcement learning examples were on like like very toy settings or very low dimensional settings or something like that. If you save two values of two two tables of two values will that be the same as it? Yeah. So um that's actually not quite the case because you will actually be collecting new data in this
43:48
loop and so you can't just store all the key values. you actually do have to store the parameters uh so that you can then compute the key values for the new data that you the target key values in the new data. So you can't just store these uh value.
44:08
Cool. Um and so this is one of the algorithms that you'll implement in homeless. Um okay, so that's the first trick is use a target network that you only periodically update. Um there's two more things that make you learning work a lot better. Um and the first one is actually looking at the accuracy of the key values. So if you um if you look at if you plot the reward over training um the reward goes up. That's good. This is a reward on the game of Breakout uh
44:41
and the game of Tucka. And if you also plot the key values over the course of trading, they're also going up. Uh and so that is definitely what you expect because the key values is representing your average reward. So that's good. Um, one other thing to note actually as like a practical tip is, uh, when you're looking at the loss function on your t values during training, uh, when you train with, the loss values will actually often go up through training. Uh, this is sometimes a little bit
45:12
alarming because you're used to loss values going down. Uh, but the reason for that is you're collecting new data and that new data has higher t values and so the scaling of your loss function is increasing uh, throughout training. And at the very beginning, if you're getting one year of reward everywhere, it might be very easy to get a loss function. Um, so yeah, don't be alarmed if your loss function is going up. Uh, sometimes that means that it the the algorith or the policy is starting to.
45:39
Um, so cool. This looks pretty good as the predicted Q increases. So does the return. Um you can also look at uh the the value over training and you see that right in the first case the values right here are fairly uniform but once you're in a state where you like really have to go up then the key value for the action of up is higher than going down or a no up. Um likewise right here it's really important to go up and so the key value is higher for going up then the actions
46:08
of going down or no up. In the right case, it doesn't really matter because the ball is on the other side on the opponent's side and so the P value is more uniform. So when you visualize the P values, they look pretty reasonable, which is good. Um but then if you actually plot like what the true returns are, um the true returns are um are shown in in red here on this red horizontal line. And the estimate of the values according to the two networks are shown as this upper line. And you
46:44
actually see this very huge gap between the estimate where the estimate is always a lot higher than the true value. Uh and so it seems like we're seeing a lot of what's called overestimation where function is overestimating how good our policy is. Uh and then there's this algorithm that was introduced called double DQN that's able to get a much more accurate uh function and it's able to overestimate far far less than DQ. Let's talk a little bit about uh double D. So and and overestimations in
47:21
general. So our target value is um let's see we're taking a max over action right here. And when we take this max, we're choosing an action that maximizes this p value. And you can another way to write this is you can think of it as um right. You can think about this quantity as Q of I of X um evaluated at the action that is maximizing our uh p5
48:15
and so we're both using an action that has um that has a high key value and evaluating the key value of that action using the same key function. uh and this means that if there is noise in our C function then it's very easy this this noise uh it's very easy to basically pick actions that are using that noise to get a higher t value and so this last term right here is what's causing overestimation um it's not perfect has some noise in it uh as neural networks generally do and
48:53
the Um because the action selected according to the Q is the same as what's being evaluated then you can really exploit that noise and use actions that are have higher value than they actually do because of the noise. Now if you instead used a different Q function for picking an action and evaluating it then you can decorrelate the noise. If you had three different key functions, um they would have naturally different uh different noise and different errors if uh and so if we have a way to use
49:37
different key values, we can actually then eliminate this problem of overestimation by essentially deorrelating the noise by putting uh by using a different Q function to estimate the key axis here as to evaluate uh the axis. And so the key idea behind double Q learning is to have is use two different networks. one network, network A for um for picking the actions and network B for evaluating
50:16
and then if they're noisy in different ways, then we're not going to then be kind of exploiting noise in our values and then as a result not overestimating our val. The question is, can you guarantee that they don't have the same noise? um the I guess it's like you definitely can't guarantee it and there might be some noise that's a result of like the architecture of the network. Um but in practice uh this ends up making a really like if you are using different
50:46
neural networks for this uh it generally does a very good job. there's still some uh some overestimation and if we looked at the at these values like here in this game the key values are still an overestimate still an over here um and also here as well but it helped uh substantially compared to uh not so it's not perfect uh but it helps quite a bit uh the question is what if you did like triple DQN or or quadruple DQN like use even more network um it's a good question I see that like gap
51:22
perhaps that if that um if the noise correlation if you're able to get like even more samples of noise that could help um the it could be interesting to try that in practice. If the noise is coming from is instead coming from a source that's like kept constant like like the architecture of the neural network or something like that then it might not help um until you start to introduce those uh and then in practice uh using more than two neural networks uh is very impactful.
51:55
How do you ensure that they don't diverge? So let's actually talk about what we what we actually do. So um we're actually already learn using two neural networks. We're using we have the current neural network and the target neural network that was just periodically frozen. And so what we can actually do is um when we do our Q update, we can use the target network uh Q5 prime for evaluating and the current neural network for picking the app uh and the um and yeah, so that's essentially
52:34
what double Q looks like where instead of using the target network for both of these, we're going to use the current network to take the action to pick the S action and then the turn. Yeah. So you're always your previous is always going to be your previous Q and so you can't. Yeah. So this is why does this help? Um especially if the previous Q is the same noise. So um the previous Q will be outdated and the new Q will have gotten a lot of gradient updates since then.
53:02
And so um and I've seen like new data points recently. Uh and so um oftentimes the noise isn't just about YP initialization but it also has to do with what what up creating updates were applied. Um and so yeah okay the last trick we'll talk about uh which we've already talked about in actritic methods is mstep return. So our Qarning target looks like this we have the reward plus the max of Q. If your Q values are good, then this term is actually going to be really
53:35
really important and playing like most of the roles in the Q-learning update. Um, but if your T function is bad, uh, like at the beginning of training, then these are really the only values that are going to matter and these are the values that are going to be giving your learning algorithms. And if you just have a single reward function here, then that might be a bit troublesome because uh just a single reward function might not tell you that much about how good your key value is.
54:04
Um so if you remember when we talked about active critic methods, we talked about um using nstep return. So we use this bonner, we would use the sum of words. If we use bootstropping, we just do R + B like the R at the current time step plus the V at the next time step. And instead, we talked about this thing that we could do in the middle where we sum the rewards over the next end time step and then use the value at the time step after that. We talked about how
54:32
this has less variance and lower bias. And lower bias in the sense that if your targets are bad, um the reward function is going to be more accurate. So can we do this for p values? Uh and what this would look like for t values is um instead of having something like this uh say this is the target for um you're trying to get the target for sat then you would define uh yi to be uh r at the current time step plus r at the next time step up until are at t + n minus one time step and then
55:24
at the time step after that use the max of q of s t + n uh where this maximization is over a sub. Um this is what ends up returns uh could look like for learning. Um does anyone like see any pos potential issue with using this target? Yeah. So if you're doing this off policy these Rs will be coming from whatever policy you used in the replay buffer rather than um the pol rather than like the optimal policy what you're trying to estimate. So there's kind of pros and cons here.
56:11
One is that it's a lot more biased, a lot faster to learn on, especially early on. Uh but the downside is that these rewards are for the policy that collected the data, not for the optional policies. And we're trying to estimate the key function for the optional policy. Um so this is a a kind of a downside uh when using n returns risk learning. Now um and this is not an issue with uh n equals 1 uh because there the reward will just be a function of s and a and we're
56:45
estimating the q value of f of a. Um now what do we do about this? Maybe the unsatisfying answer is that uh most commonly just ignore this uh pretend it isn't true and still use an any n greater than one. Uh and ends up returns truly are often like really like very often improve the performance of the algorithm despite being incorrect. That said, there are other things you can do. Uh you can dynamically choose n and only use data that follows the current policy. basically looking at
57:19
what actions were taken and seeing if those actions actually agree with the maximum key value. Uh you could also in principle dynamically choose n and have n be smaller later in training where your q values are likely to be more accurate. Now for this particular choosing of n, you really would want to do this uh only if the action space is small and the data is mostly on policy. Um and you can also do important sampling uh as well and weight this uh weight these rewards by uh some important.
57:56
>> Great. So those were the the kind of three strikes for learning in practice. Um there's a couple examples of learning that have been very successful that I put on this slide. Uh I think there's other examples too but um one of the most prominent examples was for playing uh games and if you want to train an agent to play a game either uh for either just for uh the sake of seeing how well you can do um or to play against a human uh it learning was able to outperform most people on Atari
58:30
games. Uh so this bar right here is like everything above this bar are the games that it is at human level or above human level performance and everything below is worse than human level performance. Uh and then it also was used to train a uh robot grasping system. So this is actually a case of continuous action. Uh and the uh the robot on the right is a um is using a Q function that was training learning. uh and then it is doing a kind of continuous optimization
59:02
over action that will try to uh yeah find a good uh a good way to grasp the uh and we talked a bit last time about how with RL you can get much higher success rate and more reliable policies and we see that here too where uh this system was able to get like a 96% success rate so quite high uh at being able to drop um The other thing that's nice about using RL for this application is um the you end up um if you if in order to graph you need to uh not just like go
59:41
down and pick something up, but you actually need to like move around the object. uh it's also able to learn how to do that using um using the reinforcement because it's treating it as as
59:58
cool. Um I think one of the last things I figured I would cover is some of my advice on when to use one online RL algorithm versus another since this is the last online RL method that we'll talk about. Uh so you talked a bit about PTO um SAT and DQM. Those are like some of the three main tactile algorithms he talked about. Um so PTO uh this is great when you care about stability and ease of use. Uh generally doesn't require too much tuning. Uh but it's very data
1:00:25
inefficient and so it's great to use when you care about stability and ease of use and you don't really care about data efficiency. Uh DQN works quite well uh when you have discrete actions or lowdimensional system actions. Uh and so in those cases it can be a great choice. It can be fairly data efficient uh depending on some of the details of how officially you make it. And then um soft critic and and variants of it uh are great when you care most about data efficiency um but
1:00:54
require a bit more tuning and are a bit less stable than u than something like
1:01:03
so the what we talked about is Qing also learning in practice the three tricks for target network double DQN and separate terms we defined like the Bellman equation and the Bellman optimality equation um yeah and that was like essentially overview of how to do RL without learning in explicit policy. Um we're done with online reinforcement learning algorithms for now. Uh and yeah, we covered a lot of the basics of different online reinforcement learning algorithms.
Here to help you learn
Sign in to keep a private conversation with your course tutor.
Ask me anything about the material…
Sign in to chat