10.6 State-action value function | State-action value function definition -[ML| Andrew Ng]
 When we start to develop reinforcement learning arrows later this week, you see that there's a key quantity that reinforcement learning arrows will try to compute, and that's called the state action value function. Let's take a look at what this function is. The state action value function is a function typically denoted by the letter uppercase Q and is a function of a state you might be in, as well as the action you might choose to take in that state. Q of s, a will give a number that equals the return. If you start in that state s and take the action a just once, and after taking action a once, you then behave optimally after that. After that, you take whatever actions will result in the highest possible return. Now, you might be thinking, there's something a little bit strange about this definition, because how do we know what is the optimal behavior? If we knew what's the optimal behavior, if we already knew what's the best action to take in every state, why do we still need to compute Q of s, a because we already have the optimal policy? I do want to acknowledge that there's something a little bit strange about this definition. There's almost something a little bit circular about this definition. But rest assured, when we look at specific reinforcement learning arrows later, we'll resolve this slightly circular definition, and we'll come up with a way to compute the Q function. Even before, we've come up with the optimal policy, but you see that in the later video, so don't worry about this for now. Let's look at an example. We saw previously that this is a pretty good policy. Go left from states 2, 3, and 4, and go right from state 5. It turns out that this is actually the optimal policy for the Mars Rover application when the discount factor gamma is 0.5. So Q of s, a will be equal to the total return. If you start from state s, take the action a, and then behave optimally after that, meaning take actions according to this policy shown over here. Let's figure out what Q of s, a is for a few different states. Let's look at say Q of state 2, and what if we take the action to go right? Well, if you're in state 2 and you go right, then you end up at state 3, and then after that, if you behave optimally, you're going to go left from state 3, and then go left from state 2, and then eventually you get the reward of a 100. In this case, the rewards you get would be 0 from state 2, 0 when you get to state 3, 0 when you get back to state 2, and then 100 when you finally get to the terminal state 1. So the return will be 0 plus 0.5 times that, plus 0.5 squared times that plus 0.5 cubed times 100, and this turns out to be 12.5. So Q of state 2 of going right is equal to 12.5. Note that this passes no judgment on whether going right is a good idea or not. It's actually not that good an idea from state 2 to go right, but it just faithfully reports out the return if you take action A and then behave optimally afterward. Here's another example. If you're in state 2 and you were to go left, then the sequence of rewards you get will be 0 when you're in state 2, followed by 100, and so the return is 0 plus 0.5 times 100, and that's equal to 50. In order to write down the values of QsA in this diagram, I'm going to write 12.5 here on the right to denote that this is Q of state 2 going to the right, and then when I write a little 50 here on the left, to denote that this is Q of state 2 and going to the left. Just to take one more example, what if we're in state 4 and we decide to go left? Well, if you're in state 4 and you go left, you get reward 0 and then you take action left here. So 0 again, take action left here, 0 and then 100. So Q of 4 left results in rewards 0, because the first action is left and then because we follow the optimal policy afterwards, you get rewards 0, 0, 100, and so the return is 0 plus 0.5 times that plus 0.5 squared times that, plus 0.5 cubed times that, which is therefore equal to 12.5. So Q of 4 left is 12.5, I'm going to write this here as 12.5. It turns out if you were to carry out this exercise for all of the other states and all of the other actions, you end up with this being the Q of SA for different states and different actions. Then finally, at the terminal state, well, it doesn't matter what you do, you just get that terminal reward 100 or 40. So I'm just write down those terminal rewards over here. So this is Q of SA for every state, state 1 through 6, and for the two actions, action left and action right. Because the state action value function is almost always denoted by the letter Q, this is also often called the Q function. So the terms Q function and state action value function are used interchangeably, and it tells you what are your returns or really what is the value, how good is it to take action A and state S, and then behave optimally after that. Now, it turns out that once you can compute the Q function, this would give you a way to pick actions as well. Here's the policy and return, and here are the values Q of SA from the previous slide. You notice one interesting thing when you look at the different states, which is that if you take state 2, taking the action left results in a Q value or state action value of 50, which is actually the best possible return you can get from that state. In state 3, Q of SA for the action left also gives you that higher return. In state 4, the action left gives you the return you want, and in state 5, is actually the action going to the right that gives you that higher return of 20. It turns out that the best possible return from any state S is the largest value of Q of SA maximizing over A. Just to make sure this is clear, what I'm saying is that in state 4, there is Q of state 4 left, which is 12.5, and Q of state 4 right, which turns out to be 10, and the larger of these two values, which is 12.5, is the best possible return from that state 4. In other words, the highest return you can hope to get from state 4 is 12.5, and it's actually the larger of these two numbers, 12.5 and 10. Moreover, if you want your Mars rover to enjoy a return of 12.5 rather than say 10, then the action you should take is the action A that gives you the larger value of Q of SA. The best possible action in state S is the action A that actually maximizes Q of SA. This might give you a hint for why computing Q of SA is an important part of the reinforcement learning algorithm that we'll build later. Namely, if you have a way of computing Q of SA for every state and for every action, then when you're in some state S, all you have to do is look at the different actions A, and pick the action A that maximizes Q of SA. So pi of S can just pick the action A that gives the largest value of Q of SA, and that will turn out to be a good action. In fact, it will turn out to be the optimal action. Another intuition about why this makes sense is Q of SA is returned if you start in state S and take the action A and then behave optimally after that. So in order to earn the biggest possible return, what you really want is to take the action A that results in the biggest total return. That's why if only we have a way of computing Q of SA for every state, taking the action A that maximizes return under these circumstances seems like it's the best action to take in that state. Although this isn't something you need to know for this course, I want to mention also that if you look online or look at the reinforcement learning literature, sometimes you also see this Q function written as Q star instead of Q, and this Q function is sometimes also called the optimal Q function. These terms just refer to the Q function exactly as we've defined it. So if you look at the reinforcement learning literature and read about Q star or the optimal Q function, that just means the state action value function that we've been talking about. But for the purposes of this course, you don't need to worry about this. So to summarize, if you can compute Q of SA for every state and every action, then that gives us a good way to compute the optimal policy pi of S. So that's the state action value function or the Q function. We'll talk later about how to come up with an algorithm to compute them, despite the slightly circular aspect of the definition of the Q function. But first, let's take a look at the next video as some specific examples of what these values QSA actually look like.
[{"start": 0.0, "end": 5.72, "text": " When we start to develop reinforcement learning arrows later this week,"}, {"start": 5.72, "end": 8.34, "text": " you see that there's a key quantity that"}, {"start": 8.34, "end": 10.74, "text": " reinforcement learning arrows will try to compute,"}, {"start": 10.74, "end": 13.9, "text": " and that's called the state action value function."}, {"start": 13.9, "end": 16.38, "text": " Let's take a look at what this function is."}, {"start": 16.38, "end": 21.32, "text": " The state action value function is a function typically denoted by"}, {"start": 21.32, "end": 28.080000000000002, "text": " the letter uppercase Q and is a function of a state you might be in,"}, {"start": 28.08, "end": 32.76, "text": " as well as the action you might choose to take in that state."}, {"start": 32.76, "end": 39.08, "text": " Q of s, a will give a number that equals the return."}, {"start": 39.08, "end": 44.959999999999994, "text": " If you start in that state s and take the action a just once,"}, {"start": 44.959999999999994, "end": 47.519999999999996, "text": " and after taking action a once,"}, {"start": 47.519999999999996, "end": 51.08, "text": " you then behave optimally after that."}, {"start": 51.08, "end": 56.019999999999996, "text": " After that, you take whatever actions will result in the highest possible return."}, {"start": 56.02, "end": 59.760000000000005, "text": " Now, you might be thinking, there's something a little bit strange about this definition,"}, {"start": 59.760000000000005, "end": 63.2, "text": " because how do we know what is the optimal behavior?"}, {"start": 63.2, "end": 65.48, "text": " If we knew what's the optimal behavior,"}, {"start": 65.48, "end": 68.92, "text": " if we already knew what's the best action to take in every state,"}, {"start": 68.92, "end": 71.12, "text": " why do we still need to compute Q of s,"}, {"start": 71.12, "end": 73.92, "text": " a because we already have the optimal policy?"}, {"start": 73.92, "end": 78.16, "text": " I do want to acknowledge that there's something a little bit strange about this definition."}, {"start": 78.16, "end": 80.98, "text": " There's almost something a little bit circular about this definition."}, {"start": 80.98, "end": 85.72, "text": " But rest assured, when we look at specific reinforcement learning arrows later,"}, {"start": 85.72, "end": 89.76, "text": " we'll resolve this slightly circular definition,"}, {"start": 89.76, "end": 92.6, "text": " and we'll come up with a way to compute the Q function."}, {"start": 92.6, "end": 95.48, "text": " Even before, we've come up with the optimal policy,"}, {"start": 95.48, "end": 97.2, "text": " but you see that in the later video,"}, {"start": 97.2, "end": 99.2, "text": " so don't worry about this for now."}, {"start": 99.2, "end": 101.28, "text": " Let's look at an example."}, {"start": 101.28, "end": 106.08, "text": " We saw previously that this is a pretty good policy."}, {"start": 106.08, "end": 108.44, "text": " Go left from states 2, 3,"}, {"start": 108.44, "end": 110.82, "text": " and 4, and go right from state 5."}, {"start": 110.82, "end": 114.08, "text": " It turns out that this is actually the optimal policy for"}, {"start": 114.08, "end": 119.6, "text": " the Mars Rover application when the discount factor gamma is 0.5."}, {"start": 119.6, "end": 125.34, "text": " So Q of s, a will be equal to the total return."}, {"start": 125.34, "end": 127.08, "text": " If you start from state s,"}, {"start": 127.08, "end": 128.8, "text": " take the action a,"}, {"start": 128.8, "end": 132.32, "text": " and then behave optimally after that,"}, {"start": 132.32, "end": 136.82, "text": " meaning take actions according to this policy shown over here."}, {"start": 136.82, "end": 138.56, "text": " Let's figure out what Q of s,"}, {"start": 138.56, "end": 141.36, "text": " a is for a few different states."}, {"start": 141.36, "end": 146.16000000000003, "text": " Let's look at say Q of state 2,"}, {"start": 146.16000000000003, "end": 150.08, "text": " and what if we take the action to go right?"}, {"start": 150.08, "end": 153.12, "text": " Well, if you're in state 2 and you go right,"}, {"start": 153.12, "end": 156.32000000000002, "text": " then you end up at state 3,"}, {"start": 156.32000000000002, "end": 157.88000000000002, "text": " and then after that,"}, {"start": 157.88000000000002, "end": 159.34, "text": " if you behave optimally,"}, {"start": 159.34, "end": 161.56, "text": " you're going to go left from state 3,"}, {"start": 161.56, "end": 162.96, "text": " and then go left from state 2,"}, {"start": 162.96, "end": 165.76000000000002, "text": " and then eventually you get the reward of a 100."}, {"start": 165.76000000000002, "end": 170.48000000000002, "text": " In this case, the rewards you get would be 0 from state 2,"}, {"start": 170.48, "end": 172.88, "text": " 0 when you get to state 3,"}, {"start": 172.88, "end": 175.29999999999998, "text": " 0 when you get back to state 2,"}, {"start": 175.29999999999998, "end": 180.39999999999998, "text": " and then 100 when you finally get to the terminal state 1."}, {"start": 180.39999999999998, "end": 185.92, "text": " So the return will be 0 plus 0.5 times that,"}, {"start": 185.92, "end": 190.72, "text": " plus 0.5 squared times that plus 0.5 cubed times 100,"}, {"start": 190.72, "end": 194.51999999999998, "text": " and this turns out to be 12.5."}, {"start": 194.51999999999998, "end": 199.6, "text": " So Q of state 2 of going right is equal to 12.5."}, {"start": 199.6, "end": 202.23999999999998, "text": " Note that this passes no judgment on"}, {"start": 202.23999999999998, "end": 204.44, "text": " whether going right is a good idea or not."}, {"start": 204.44, "end": 207.68, "text": " It's actually not that good an idea from state 2 to go right,"}, {"start": 207.68, "end": 211.92, "text": " but it just faithfully reports out the return if you"}, {"start": 211.92, "end": 214.92, "text": " take action A and then behave optimally afterward."}, {"start": 214.92, "end": 216.64, "text": " Here's another example."}, {"start": 216.64, "end": 221.24, "text": " If you're in state 2 and you were to go left,"}, {"start": 221.24, "end": 226.12, "text": " then the sequence of rewards you get will be 0 when you're in state 2,"}, {"start": 226.12, "end": 227.95999999999998, "text": " followed by 100,"}, {"start": 227.96, "end": 232.48000000000002, "text": " and so the return is 0 plus 0.5 times 100,"}, {"start": 232.48000000000002, "end": 234.52, "text": " and that's equal to 50."}, {"start": 234.52, "end": 241.28, "text": " In order to write down the values of QsA in this diagram,"}, {"start": 241.28, "end": 245.56, "text": " I'm going to write 12.5 here on the right to"}, {"start": 245.56, "end": 250.16, "text": " denote that this is Q of state 2 going to the right,"}, {"start": 250.16, "end": 253.12, "text": " and then when I write a little 50 here on the left,"}, {"start": 253.12, "end": 258.12, "text": " to denote that this is Q of state 2 and going to the left."}, {"start": 258.12, "end": 260.56, "text": " Just to take one more example,"}, {"start": 260.56, "end": 264.44, "text": " what if we're in state 4 and we decide to go left?"}, {"start": 264.44, "end": 267.12, "text": " Well, if you're in state 4 and you go left,"}, {"start": 267.12, "end": 271.4, "text": " you get reward 0 and then you take action left here."}, {"start": 271.4, "end": 276.08, "text": " So 0 again, take action left here, 0 and then 100."}, {"start": 276.08, "end": 282.4, "text": " So Q of 4 left results in rewards 0,"}, {"start": 282.4, "end": 285.52, "text": " because the first action is left and then because we"}, {"start": 285.52, "end": 288.23999999999995, "text": " follow the optimal policy afterwards,"}, {"start": 288.23999999999995, "end": 292.03999999999996, "text": " you get rewards 0, 0, 100,"}, {"start": 292.03999999999996, "end": 297.47999999999996, "text": " and so the return is 0 plus 0.5 times that plus 0.5 squared times that,"}, {"start": 297.47999999999996, "end": 299.59999999999997, "text": " plus 0.5 cubed times that,"}, {"start": 299.59999999999997, "end": 303.59999999999997, "text": " which is therefore equal to 12.5."}, {"start": 303.59999999999997, "end": 306.52, "text": " So Q of 4 left is 12.5,"}, {"start": 306.52, "end": 310.44, "text": " I'm going to write this here as 12.5."}, {"start": 310.44, "end": 314.8, "text": " It turns out if you were to carry out this exercise for all of"}, {"start": 314.8, "end": 316.8, "text": " the other states and all of the other actions,"}, {"start": 316.8, "end": 320.44, "text": " you end up with this being the Q of"}, {"start": 320.44, "end": 324.68, "text": " SA for different states and different actions."}, {"start": 324.68, "end": 326.8, "text": " Then finally, at the terminal state,"}, {"start": 326.8, "end": 328.68, "text": " well, it doesn't matter what you do,"}, {"start": 328.68, "end": 332.56, "text": " you just get that terminal reward 100 or 40."}, {"start": 332.56, "end": 335.56, "text": " So I'm just write down those terminal rewards over here."}, {"start": 335.56, "end": 340.76, "text": " So this is Q of SA for every state, state 1 through 6,"}, {"start": 340.76, "end": 342.28000000000003, "text": " and for the two actions,"}, {"start": 342.28000000000003, "end": 344.8, "text": " action left and action right."}, {"start": 344.8, "end": 351.72, "text": " Because the state action value function is almost always denoted by the letter Q,"}, {"start": 351.72, "end": 355.88, "text": " this is also often called the Q function."}, {"start": 355.88, "end": 361.2, "text": " So the terms Q function and state action value function are used interchangeably,"}, {"start": 361.2, "end": 365.28, "text": " and it tells you what are your returns or really what is the value,"}, {"start": 365.28, "end": 369.03999999999996, "text": " how good is it to take action A and state S,"}, {"start": 369.03999999999996, "end": 371.47999999999996, "text": " and then behave optimally after that."}, {"start": 371.47999999999996, "end": 376.52, "text": " Now, it turns out that once you can compute the Q function,"}, {"start": 376.52, "end": 379.4, "text": " this would give you a way to pick actions as well."}, {"start": 379.4, "end": 382.08, "text": " Here's the policy and return,"}, {"start": 382.08, "end": 386.44, "text": " and here are the values Q of SA from the previous slide."}, {"start": 386.44, "end": 391.15999999999997, "text": " You notice one interesting thing when you look at the different states,"}, {"start": 391.15999999999997, "end": 393.91999999999996, "text": " which is that if you take state 2,"}, {"start": 393.92, "end": 400.44, "text": " taking the action left results in a Q value or state action value of 50,"}, {"start": 400.44, "end": 403.56, "text": " which is actually the best possible return you can get from that state."}, {"start": 403.56, "end": 410.12, "text": " In state 3, Q of SA for the action left also gives you that higher return."}, {"start": 410.12, "end": 415.16, "text": " In state 4, the action left gives you the return you want,"}, {"start": 415.16, "end": 417.20000000000005, "text": " and in state 5,"}, {"start": 417.20000000000005, "end": 423.08000000000004, "text": " is actually the action going to the right that gives you that higher return of 20."}, {"start": 423.08, "end": 429.24, "text": " It turns out that the best possible return from any state S is"}, {"start": 429.24, "end": 433.84, "text": " the largest value of Q of SA maximizing over A."}, {"start": 433.84, "end": 435.44, "text": " Just to make sure this is clear,"}, {"start": 435.44, "end": 438.88, "text": " what I'm saying is that in state 4,"}, {"start": 438.88, "end": 441.91999999999996, "text": " there is Q of state 4 left,"}, {"start": 441.91999999999996, "end": 443.88, "text": " which is 12.5,"}, {"start": 443.88, "end": 447.28, "text": " and Q of state 4 right,"}, {"start": 447.28, "end": 449.24, "text": " which turns out to be 10,"}, {"start": 449.24, "end": 452.71999999999997, "text": " and the larger of these two values,"}, {"start": 452.72, "end": 457.8, "text": " which is 12.5, is the best possible return from that state 4."}, {"start": 457.8, "end": 462.04, "text": " In other words, the highest return you can hope to get from state 4 is 12.5,"}, {"start": 462.04, "end": 466.12, "text": " and it's actually the larger of these two numbers, 12.5 and 10."}, {"start": 466.12, "end": 474.0, "text": " Moreover, if you want your Mars rover to enjoy a return of 12.5 rather than say 10,"}, {"start": 474.0, "end": 482.04, "text": " then the action you should take is the action A that gives you the larger value of Q of SA."}, {"start": 482.04, "end": 490.52000000000004, "text": " The best possible action in state S is the action A that actually maximizes Q of SA."}, {"start": 490.52000000000004, "end": 497.16, "text": " This might give you a hint for why computing Q of SA is"}, {"start": 497.16, "end": 501.88, "text": " an important part of the reinforcement learning algorithm that we'll build later."}, {"start": 501.88, "end": 508.12, "text": " Namely, if you have a way of computing Q of SA for every state and for every action,"}, {"start": 508.12, "end": 514.76, "text": " then when you're in some state S, all you have to do is look at the different actions A,"}, {"start": 514.76, "end": 518.76, "text": " and pick the action A that maximizes Q of SA."}, {"start": 518.76, "end": 524.92, "text": " So pi of S can just pick the action A that gives the largest value of Q of SA,"}, {"start": 524.92, "end": 527.92, "text": " and that will turn out to be a good action."}, {"start": 527.92, "end": 530.44, "text": " In fact, it will turn out to be the optimal action."}, {"start": 530.44, "end": 535.84, "text": " Another intuition about why this makes sense is Q of SA is returned if you"}, {"start": 535.84, "end": 540.6800000000001, "text": " start in state S and take the action A and then behave optimally after that."}, {"start": 540.6800000000001, "end": 544.5600000000001, "text": " So in order to earn the biggest possible return,"}, {"start": 544.5600000000001, "end": 552.6, "text": " what you really want is to take the action A that results in the biggest total return."}, {"start": 552.6, "end": 557.48, "text": " That's why if only we have a way of computing Q of SA for every state,"}, {"start": 557.48, "end": 560.72, "text": " taking the action A that maximizes return under"}, {"start": 560.72, "end": 565.0400000000001, "text": " these circumstances seems like it's the best action to take in that state."}, {"start": 565.04, "end": 568.28, "text": " Although this isn't something you need to know for this course,"}, {"start": 568.28, "end": 574.8399999999999, "text": " I want to mention also that if you look online or look at the reinforcement learning literature,"}, {"start": 574.8399999999999, "end": 580.64, "text": " sometimes you also see this Q function written as Q star instead of Q,"}, {"start": 580.64, "end": 585.7199999999999, "text": " and this Q function is sometimes also called the optimal Q function."}, {"start": 585.7199999999999, "end": 590.0799999999999, "text": " These terms just refer to the Q function exactly as we've defined it."}, {"start": 590.0799999999999, "end": 594.04, "text": " So if you look at the reinforcement learning literature and read about Q star or"}, {"start": 594.04, "end": 599.12, "text": " the optimal Q function, that just means the state action value function that we've been talking about."}, {"start": 599.12, "end": 602.48, "text": " But for the purposes of this course, you don't need to worry about this."}, {"start": 602.48, "end": 605.0799999999999, "text": " So to summarize,"}, {"start": 605.0799999999999, "end": 609.7199999999999, "text": " if you can compute Q of SA for every state and every action,"}, {"start": 609.7199999999999, "end": 615.28, "text": " then that gives us a good way to compute the optimal policy pi of S."}, {"start": 615.28, "end": 620.68, "text": " So that's the state action value function or the Q function."}, {"start": 620.68, "end": 624.68, "text": " We'll talk later about how to come up with an algorithm to compute them,"}, {"start": 624.68, "end": 628.88, "text": " despite the slightly circular aspect of the definition of the Q function."}, {"start": 628.88, "end": 651.28, "text": " But first, let's take a look at the next video as some specific examples of what these values QSA actually look like."}]