10.8 State-action value function | Bellman Equations -[Machine Learning|Andrew Ng]
 Let me summarize where we are. If you can compute the state action value function q of s, a, then it gives you a way to pick a good action from every state. Just pick the action a that gives you the largest value of q of s, a. So the question is, how do you compute these values q of s, a? In reinforcement learning, there's a key equation called the Bellman equation that will help us to compute the state action value function. Let's take a look at what is this equation. As a reminder, this is the definition of q of s, a. It is returned if you start in state s, take the action a once, and then behave optimally after that. In order to describe the Bellman equation, I'm going to use the following notation. I'm going to use s to denote the current state. Next, I'm going to use r of s to denote the reward of the current state. So for our little MDP example, we would have that r of 1, state 1 is 100, the reward of state 2 is 0, and so on, and the reward of state 6 is 40. I'm going to use the alphabet a to denote the current action. So the action that you take in the state s, after you take the action a, you get to some new state. For example, if you're in state 4 and you take the action left, then you get to state 3. And so I'm going to use s prime to denote the state you get to after taking that action a from the current state s. I'm also going to use a prime to denote the action that you might take in state s prime, the new state that you got to. The notation convention, by the way, is that s a correspond to the current state and action, and when we add the prime, that's the next state and the next action. The Bellman equation is the following. It says that q of s a, that is, the return under this set of assumptions, that's equal to r of s, so the reward you get for being in that state, plus the discount factor gamma times max over all possible actions a prime of q of s prime, the new state you just got to, and then of a prime. There's a lot going on in this equation, so let's first take a look at some examples that will come back to see why this equation might make sense. Let's look at an example. Let's look at q of state 2 and action right and apply Bellman equation to this to see what value it gives us. So if the current state is state 2 and the action is to go right, then the next state you get to after going right, s prime, will be the state 3. So the Bellman equation says q of 2 right is r of s, so this r of state 2, which is just a reward 0, plus the discount factor gamma, which we've set to 0.5 in this example, times max of the q values in state s prime, in state 3. So this is going to be the max of 25 and 6.25, since this is max over a prime of q of s prime comma a prime, and this is taking the larger of 25 or 6.25, because those are the two choices for state 3. And this turns out to be equal to 0 plus 0.5 times 25, which is equal to 12.5, which fortunately is q of 2 and then the action right. Let's look at just one more example. Let me pick state 4 and see what is q of state 4 if you decide to go left. In this case, the current state is 4, current action is to go left, and so the next state, if you start from 4 and go left, you end up also at state 3. So s prime is 3 again. The equation will say this is equal to r of s, so r of state 4, which is 0 plus 0.5 to discount factor gamma of max over a prime of q of s prime, that is to say 3 again, comma a prime. So once again, the q values for state 3 are 25 and 6.25, and the larger of these is 25. And so this works out to be r of 4 is 0 plus 0.5 times 25, which is again equal to 12.5. So that's why q of 4 with the action left is also equal to 12.5. Just one note, if you're in a terminal state, then Bellman equation simplifies to q of sA equals to r of s because there's no state s prime, and so that second term would go away, which is why q of sA in the terminal states is just 100, 100, or 40, 40. If you wish, feel free to pause the video and apply the Bellman equation to any other state action in this NDP and check for yourself if this math works out. Just to recap, this is how we had defined q of sA, and we saw earlier that the best possible return from any state s is max over a q of sA. In fact, just to rename s and a, it turns out that the best possible return from a state s prime is max over s prime of a prime, right? I didn't really do anything other than rename s to s prime and a to a prime, but this will make some of the intuitions a little bit easier later. But for any state s prime, like state 3, the best possible return from, say, state 3 is the max of all possible actions of q of s prime a prime. So here again is the Bellman equation, and the intuition that this captures is if you're starting from state s and you're going to take action a and then act optimally after that, then you're going to see some sequence of rewards over time. In particular, the return will be computed from the reward at the first step plus gamma times the reward at the second step plus gamma squared times the reward at the third step and so on, plus dot dot dot until you get the terminal state. So what Bellman equation says is this sequence of rewards with the discount factors can be broken down into two components. First, this R of s, that's the reward you get right away. In the reinforcement learning literature, this is sometimes also called the immediate reward, but that's what R1 is, is the reward you get for starting out in some state s. The second term then is the following. After you start in state s and take action a, you get to some new state s prime. The definition of q of s a assumes we're going to behave optimally after that. So after we get to s prime, we're going to behave optimally and get the best possible return from the state s prime. And so what this is, max over a prime of q of s prime a prime, this is the return from behaving optimally starting from the state s prime. That's exactly what we had written up here, is the best possible return for when you start from state s prime. Another way of phrasing this is, this total return down here is also equal to R1 plus, and then I'm going to factor out gamma in the math, is gamma times R2 plus, and then instead of gamma squared, it's just gamma times R3 plus gamma squared times R4 plus dot dot dot. Notice that if you were starting from state s prime, the sequence of rewards you get will be R2, then R3, then R4, and so on. And that's why this expression here, that's the total return if you were to start from state s prime. And if you were to behave optimally, then this expression should be the best possible return for starting from state s prime, which is why this sequence of this counter was equals that max of a prime of q of s prime a prime, and there were also leftover with this extra discount factor gamma there, which is why q of s a is also equal to this expression over here. In case you think this is quite complicated and you aren't following all the details, don't worry about it. So long as you apply this equation, you will manage to get the right results. But the high level intuition I hope you take away is that the total return you get in the reinforcement learning problem has two parts. The first part is this reward that you get right away. And then the second part is gamma times the return you get starting from the next state s prime. And as these two components together, R of s plus gamma times return from the next state that is equal to the total return from the current state s. That is the essence of development equation. So just to relate this back to our earlier example, q of four left, that's the total return for starting state four and going left. So if you were to go left in state four, the rewards you get are zero in state four, zero in state three, zero in state two, and then 100, which is why the total return is this 0.5 squared plus 0.5 cubed, which was 12.5. And what Bellman equation is saying is that we can break this up into two pieces. There is this zero, which is R of the state four, and then plus 0.5 times this other sequence, zero plus 0.5, zero plus 0.5 squared times 100. But if you look at what this sequence is, this is really the optimal return from the next state s prime that you got to after taking the action left from state four. So that's why this is equal to the reward four plus 0.5 times the optimal return from state three, because if you were to start from state three, the rewards you get would be zero followed by zero followed by 100. So this is optimal return from state three. And that's why this is just R of four plus 0.5 max over a prime q of state three, a prime. I know the Bellman equation is a somewhat complicated equation, breaking down your total returns into the reward you get right away, the immediate reward plus gamma times the returns from the next state s prime. If it kind of makes sense to you, but not fully, it's okay. Don't worry about it. You can still apply Bellman's equations to get a reinforcement learning algorithm to work correctly. But I hope that at least a high level intuition of why breaking down the rewards into what you get right away plus what you get in the future. I hope that makes sense. Before moving on to develop a reinforcement learning algorithm, we have coming up next an optional video on stochastic Markov decision processes or on reinforcement learning applications where the actions that you take can have a slightly random effect. Take a look at the optional video if you wish. And then after that, we'll start to develop a reinforcement learning algorithm.
[{"start": 0.0, "end": 4.44, "text": " Let me summarize where we are."}, {"start": 4.44, "end": 8.4, "text": " If you can compute the state action value function q of s,"}, {"start": 8.4, "end": 13.0, "text": " a, then it gives you a way to pick a good action from every state."}, {"start": 13.0, "end": 17.0, "text": " Just pick the action a that gives you the largest value of q of s,"}, {"start": 17.0, "end": 18.0, "text": " a."}, {"start": 18.0, "end": 21.44, "text": " So the question is, how do you compute these values q of s,"}, {"start": 21.44, "end": 22.44, "text": " a?"}, {"start": 22.44, "end": 27.12, "text": " In reinforcement learning, there's a key equation called the Bellman equation that will help"}, {"start": 27.12, "end": 30.560000000000002, "text": " us to compute the state action value function."}, {"start": 30.560000000000002, "end": 33.760000000000005, "text": " Let's take a look at what is this equation."}, {"start": 33.760000000000005, "end": 38.08, "text": " As a reminder, this is the definition of q of s, a."}, {"start": 38.08, "end": 42.120000000000005, "text": " It is returned if you start in state s, take the action a once, and then behave optimally"}, {"start": 42.120000000000005, "end": 43.82, "text": " after that."}, {"start": 43.82, "end": 48.64, "text": " In order to describe the Bellman equation, I'm going to use the following notation."}, {"start": 48.64, "end": 52.120000000000005, "text": " I'm going to use s to denote the current state."}, {"start": 52.12, "end": 59.08, "text": " Next, I'm going to use r of s to denote the reward of the current state."}, {"start": 59.08, "end": 66.8, "text": " So for our little MDP example, we would have that r of 1, state 1 is 100, the reward of"}, {"start": 66.8, "end": 73.32, "text": " state 2 is 0, and so on, and the reward of state 6 is 40."}, {"start": 73.32, "end": 78.38, "text": " I'm going to use the alphabet a to denote the current action."}, {"start": 78.38, "end": 84.92, "text": " So the action that you take in the state s, after you take the action a, you get to some"}, {"start": 84.92, "end": 85.92, "text": " new state."}, {"start": 85.92, "end": 91.03999999999999, "text": " For example, if you're in state 4 and you take the action left, then you get to state"}, {"start": 91.03999999999999, "end": 92.36, "text": " 3."}, {"start": 92.36, "end": 98.16, "text": " And so I'm going to use s prime to denote the state you get to after taking that action"}, {"start": 98.16, "end": 100.82, "text": " a from the current state s."}, {"start": 100.82, "end": 108.38, "text": " I'm also going to use a prime to denote the action that you might take in state s prime,"}, {"start": 108.38, "end": 110.11999999999999, "text": " the new state that you got to."}, {"start": 110.11999999999999, "end": 115.94, "text": " The notation convention, by the way, is that s a correspond to the current state and action,"}, {"start": 115.94, "end": 120.39999999999999, "text": " and when we add the prime, that's the next state and the next action."}, {"start": 120.39999999999999, "end": 123.44, "text": " The Bellman equation is the following."}, {"start": 123.44, "end": 132.28, "text": " It says that q of s a, that is, the return under this set of assumptions, that's equal"}, {"start": 132.28, "end": 142.24, "text": " to r of s, so the reward you get for being in that state, plus the discount factor gamma"}, {"start": 142.24, "end": 150.72, "text": " times max over all possible actions a prime of q of s prime, the new state you just got"}, {"start": 150.72, "end": 154.92, "text": " to, and then of a prime."}, {"start": 154.92, "end": 159.48, "text": " There's a lot going on in this equation, so let's first take a look at some examples that"}, {"start": 159.48, "end": 163.24, "text": " will come back to see why this equation might make sense."}, {"start": 163.24, "end": 164.66, "text": " Let's look at an example."}, {"start": 164.66, "end": 172.64, "text": " Let's look at q of state 2 and action right and apply Bellman equation to this to see"}, {"start": 172.64, "end": 175.26, "text": " what value it gives us."}, {"start": 175.26, "end": 183.22, "text": " So if the current state is state 2 and the action is to go right, then the next state"}, {"start": 183.22, "end": 187.94, "text": " you get to after going right, s prime, will be the state 3."}, {"start": 187.94, "end": 198.0, "text": " So the Bellman equation says q of 2 right is r of s, so this r of state 2, which is"}, {"start": 198.0, "end": 206.64, "text": " just a reward 0, plus the discount factor gamma, which we've set to 0.5 in this example,"}, {"start": 206.64, "end": 214.62, "text": " times max of the q values in state s prime, in state 3."}, {"start": 214.62, "end": 224.4, "text": " So this is going to be the max of 25 and 6.25, since this is max over a prime of q of s prime"}, {"start": 224.4, "end": 233.72, "text": " comma a prime, and this is taking the larger of 25 or 6.25, because those are the two choices"}, {"start": 233.72, "end": 235.34, "text": " for state 3."}, {"start": 235.34, "end": 246.5, "text": " And this turns out to be equal to 0 plus 0.5 times 25, which is equal to 12.5, which fortunately"}, {"start": 246.5, "end": 250.28, "text": " is q of 2 and then the action right."}, {"start": 250.28, "end": 251.86, "text": " Let's look at just one more example."}, {"start": 251.86, "end": 259.78000000000003, "text": " Let me pick state 4 and see what is q of state 4 if you decide to go left."}, {"start": 259.78000000000003, "end": 265.62, "text": " In this case, the current state is 4, current action is to go left, and so the next state,"}, {"start": 265.62, "end": 270.24, "text": " if you start from 4 and go left, you end up also at state 3."}, {"start": 270.24, "end": 272.5, "text": " So s prime is 3 again."}, {"start": 272.5, "end": 282.26, "text": " The equation will say this is equal to r of s, so r of state 4, which is 0 plus 0.5 to"}, {"start": 282.26, "end": 290.56, "text": " discount factor gamma of max over a prime of q of s prime, that is to say 3 again, comma"}, {"start": 290.56, "end": 292.12, "text": " a prime."}, {"start": 292.12, "end": 300.12, "text": " So once again, the q values for state 3 are 25 and 6.25, and the larger of these is 25."}, {"start": 300.12, "end": 310.88, "text": " And so this works out to be r of 4 is 0 plus 0.5 times 25, which is again equal to 12.5."}, {"start": 310.88, "end": 317.48, "text": " So that's why q of 4 with the action left is also equal to 12.5."}, {"start": 317.48, "end": 324.64, "text": " Just one note, if you're in a terminal state, then Bellman equation simplifies to q of sA"}, {"start": 324.64, "end": 330.4, "text": " equals to r of s because there's no state s prime, and so that second term would go"}, {"start": 330.4, "end": 337.53999999999996, "text": " away, which is why q of sA in the terminal states is just 100, 100, or 40, 40."}, {"start": 337.53999999999996, "end": 341.82, "text": " If you wish, feel free to pause the video and apply the Bellman equation to any other"}, {"start": 341.82, "end": 348.65999999999997, "text": " state action in this NDP and check for yourself if this math works out."}, {"start": 348.66, "end": 356.20000000000005, "text": " Just to recap, this is how we had defined q of sA, and we saw earlier that the best"}, {"start": 356.20000000000005, "end": 362.28000000000003, "text": " possible return from any state s is max over a q of sA."}, {"start": 362.28000000000003, "end": 368.20000000000005, "text": " In fact, just to rename s and a, it turns out that the best possible return from a state"}, {"start": 368.20000000000005, "end": 374.04, "text": " s prime is max over s prime of a prime, right?"}, {"start": 374.04, "end": 379.28000000000003, "text": " I didn't really do anything other than rename s to s prime and a to a prime, but this will"}, {"start": 379.28000000000003, "end": 382.64000000000004, "text": " make some of the intuitions a little bit easier later."}, {"start": 382.64000000000004, "end": 388.16, "text": " But for any state s prime, like state 3, the best possible return from, say, state 3 is"}, {"start": 388.16, "end": 392.88, "text": " the max of all possible actions of q of s prime a prime."}, {"start": 392.88, "end": 400.32000000000005, "text": " So here again is the Bellman equation, and the intuition that this captures is if you're"}, {"start": 400.32, "end": 406.24, "text": " starting from state s and you're going to take action a and then act optimally after"}, {"start": 406.24, "end": 411.56, "text": " that, then you're going to see some sequence of rewards over time."}, {"start": 411.56, "end": 419.34, "text": " In particular, the return will be computed from the reward at the first step plus gamma"}, {"start": 419.34, "end": 424.98, "text": " times the reward at the second step plus gamma squared times the reward at the third step"}, {"start": 424.98, "end": 429.0, "text": " and so on, plus dot dot dot until you get the terminal state."}, {"start": 429.0, "end": 436.6, "text": " So what Bellman equation says is this sequence of rewards with the discount factors can be"}, {"start": 436.6, "end": 438.88, "text": " broken down into two components."}, {"start": 438.88, "end": 445.72, "text": " First, this R of s, that's the reward you get right away."}, {"start": 445.72, "end": 450.04, "text": " In the reinforcement learning literature, this is sometimes also called the immediate"}, {"start": 450.04, "end": 457.12, "text": " reward, but that's what R1 is, is the reward you get for starting out in some state s."}, {"start": 457.12, "end": 460.52, "text": " The second term then is the following."}, {"start": 460.52, "end": 467.52, "text": " After you start in state s and take action a, you get to some new state s prime."}, {"start": 467.52, "end": 472.8, "text": " The definition of q of s a assumes we're going to behave optimally after that."}, {"start": 472.8, "end": 477.72, "text": " So after we get to s prime, we're going to behave optimally and get the best possible"}, {"start": 477.72, "end": 480.68, "text": " return from the state s prime."}, {"start": 480.68, "end": 488.28000000000003, "text": " And so what this is, max over a prime of q of s prime a prime, this is the return from"}, {"start": 488.28000000000003, "end": 493.98, "text": " behaving optimally starting from the state s prime."}, {"start": 493.98, "end": 500.2, "text": " That's exactly what we had written up here, is the best possible return for when you start"}, {"start": 500.2, "end": 502.4, "text": " from state s prime."}, {"start": 502.4, "end": 511.35999999999996, "text": " Another way of phrasing this is, this total return down here is also equal to R1 plus,"}, {"start": 511.35999999999996, "end": 516.92, "text": " and then I'm going to factor out gamma in the math, is gamma times R2 plus, and then"}, {"start": 516.92, "end": 524.16, "text": " instead of gamma squared, it's just gamma times R3 plus gamma squared times R4 plus"}, {"start": 524.16, "end": 525.8, "text": " dot dot dot."}, {"start": 525.8, "end": 531.4399999999999, "text": " Notice that if you were starting from state s prime, the sequence of rewards you get will"}, {"start": 531.44, "end": 537.12, "text": " be R2, then R3, then R4, and so on."}, {"start": 537.12, "end": 545.08, "text": " And that's why this expression here, that's the total return if you were to start from"}, {"start": 545.08, "end": 547.36, "text": " state s prime."}, {"start": 547.36, "end": 552.5, "text": " And if you were to behave optimally, then this expression should be the best possible"}, {"start": 552.5, "end": 561.2, "text": " return for starting from state s prime, which is why this sequence of this counter was equals"}, {"start": 561.2, "end": 567.5200000000001, "text": " that max of a prime of q of s prime a prime, and there were also leftover with this extra"}, {"start": 567.5200000000001, "end": 574.32, "text": " discount factor gamma there, which is why q of s a is also equal to this expression"}, {"start": 574.32, "end": 576.48, "text": " over here."}, {"start": 576.48, "end": 580.6, "text": " In case you think this is quite complicated and you aren't following all the details,"}, {"start": 580.6, "end": 582.1, "text": " don't worry about it."}, {"start": 582.1, "end": 587.0, "text": " So long as you apply this equation, you will manage to get the right results."}, {"start": 587.0, "end": 593.44, "text": " But the high level intuition I hope you take away is that the total return you get in the"}, {"start": 593.44, "end": 596.88, "text": " reinforcement learning problem has two parts."}, {"start": 596.88, "end": 601.76, "text": " The first part is this reward that you get right away."}, {"start": 601.76, "end": 608.44, "text": " And then the second part is gamma times the return you get starting from the next state"}, {"start": 608.44, "end": 609.9, "text": " s prime."}, {"start": 609.9, "end": 616.6, "text": " And as these two components together, R of s plus gamma times return from the next state"}, {"start": 616.6, "end": 621.4, "text": " that is equal to the total return from the current state s."}, {"start": 621.4, "end": 624.72, "text": " That is the essence of development equation."}, {"start": 624.72, "end": 631.2, "text": " So just to relate this back to our earlier example, q of four left, that's the total"}, {"start": 631.2, "end": 635.0400000000001, "text": " return for starting state four and going left."}, {"start": 635.0400000000001, "end": 641.76, "text": " So if you were to go left in state four, the rewards you get are zero in state four, zero"}, {"start": 641.76, "end": 647.36, "text": " in state three, zero in state two, and then 100, which is why the total return is this"}, {"start": 647.36, "end": 652.64, "text": " 0.5 squared plus 0.5 cubed, which was 12.5."}, {"start": 652.64, "end": 657.0, "text": " And what Bellman equation is saying is that we can break this up into two pieces."}, {"start": 657.0, "end": 667.52, "text": " There is this zero, which is R of the state four, and then plus 0.5 times this other sequence,"}, {"start": 667.52, "end": 675.0, "text": " zero plus 0.5, zero plus 0.5 squared times 100."}, {"start": 675.0, "end": 679.92, "text": " But if you look at what this sequence is, this is really the optimal return from the"}, {"start": 679.92, "end": 685.76, "text": " next state s prime that you got to after taking the action left from state four."}, {"start": 685.76, "end": 694.0799999999999, "text": " So that's why this is equal to the reward four plus 0.5 times the optimal return from"}, {"start": 694.08, "end": 698.1600000000001, "text": " state three, because if you were to start from state three, the rewards you get would"}, {"start": 698.1600000000001, "end": 702.1600000000001, "text": " be zero followed by zero followed by 100."}, {"start": 702.1600000000001, "end": 706.6800000000001, "text": " So this is optimal return from state three."}, {"start": 706.6800000000001, "end": 715.94, "text": " And that's why this is just R of four plus 0.5 max over a prime q of state three, a prime."}, {"start": 715.94, "end": 720.4000000000001, "text": " I know the Bellman equation is a somewhat complicated equation, breaking down your total"}, {"start": 720.4, "end": 726.12, "text": " returns into the reward you get right away, the immediate reward plus gamma times the"}, {"start": 726.12, "end": 729.24, "text": " returns from the next state s prime."}, {"start": 729.24, "end": 732.36, "text": " If it kind of makes sense to you, but not fully, it's okay."}, {"start": 732.36, "end": 733.36, "text": " Don't worry about it."}, {"start": 733.36, "end": 737.72, "text": " You can still apply Bellman's equations to get a reinforcement learning algorithm to"}, {"start": 737.72, "end": 738.72, "text": " work correctly."}, {"start": 738.72, "end": 744.52, "text": " But I hope that at least a high level intuition of why breaking down the rewards into what"}, {"start": 744.52, "end": 747.4399999999999, "text": " you get right away plus what you get in the future."}, {"start": 747.4399999999999, "end": 750.16, "text": " I hope that makes sense."}, {"start": 750.16, "end": 754.92, "text": " Before moving on to develop a reinforcement learning algorithm, we have coming up next"}, {"start": 754.92, "end": 761.68, "text": " an optional video on stochastic Markov decision processes or on reinforcement learning applications"}, {"start": 761.68, "end": 767.0, "text": " where the actions that you take can have a slightly random effect."}, {"start": 767.0, "end": 768.8399999999999, "text": " Take a look at the optional video if you wish."}, {"start": 768.84, "end": 780.48, "text": " And then after that, we'll start to develop a reinforcement learning algorithm."}]