10.3 Reinforcement Learning formalism | The Return in reinforcement learning -[ML |Andrew Ng]
 You saw in the last video what are the states of a reinforcement learning application, as well as how depending on the actions you take, you go through different states and also get to enjoy different rewards. But how do you know if a particular set of rewards is better or worse than a different set of rewards? The return in reinforcement learning, which we'll define in this video, allows us to capture that. So if you go through this, one analogy that you might find helpful is if you imagine you have a $5 bill at your feet, you can reach down and pick up, or half an hour across town, you can walk half an hour and pick up a $10 bill. Which one would you rather go after? $10 is much better than $5, but if you need to walk for half an hour to go and get that $10 bill, then maybe it'd be more convenient to just pick up the $5 bill instead. So the concept of a return captures that rewards you can get quicker are maybe more attractive than rewards that take you a long time to get to. Let's take a look at exactly how that works. Here's our Mars rover example. If starting from state four, you go to the left, we saw that the rewards you get would be zero on the first step from state four, zero from state three, zero from state two, and then 100 at state one, the terminal state. And so the return is defined as the sum of these rewards, but weighted by one additional factor, which is called the discount factor. So the discount factor is a number a little bit less than one. So let me pick 0.9 as the discount factor. I'm going to weight the reward on the first step is just zero. The reward on the second step is a discount factor, 0.9 times that reward, and then plus the discount factor squared times that reward, and then plus the discount factor cubed times that reward. And if you calculate this out, this turns out to be 0.729 times 100, which is 72.9. The more general formula for the return is that if your robot goes through some sequence of states and gets reward R1 on the first step and R2 on the second step and R3 on the third step and so on, then the return is R1 plus the discount factor gamma, that's Greek alphabet gamma, which I've set to 0.9 as this example, the gamma times R2 plus gamma squared times R3 plus gamma cubed times R4 and so on until you get to the terminal state. What the discount factor gamma does is it has the effect of making the reinforcement learning algorithm a little bit impatient because the return gives full credit to the first reward is 100%, is 1 times R1, but then it gives a little bit less credit to the reward you get at the second step, that's multiplied by 0.9, and then even less credit to the reward you get at the next time step R3 and so on. And so getting rewards sooner results in a higher value for the total return. In many reinforcement learning algorithms, a common choice for the discount factor would be a number pretty close to 1, like 0.9 or 0.99 or even 0.999. But for illustrative purposes, in the running example I'm going to use, I'm actually going to use a discount factor of 0.5. So this very heavily down weights or very heavily we say discounts rewards in the future, because with every additional passing time step, you get only half as much credit as rewards that you would have gotten one step earlier. And so if gamma were equal to 0.5, the return under the example above would have been 0.9, 0 plus 0.5 times 0, replacing this equation on top, plus 0.5 squared, 0 plus 0.5 cubed times 100. That's the last reward because state 1 is a terminal state, and this turns out to be a return of 12.5. In financial applications, the discount factor also has a very natural interpretation as the interest rate or the time value of money. So if you can have a dollar today, that may be worth a little bit more than if you could only get a dollar in the future, because even a dollar today, you can put in the bank, earn some interest and end up with a little bit more money a year from now. So for financial applications, often that discount factor represents how much less is a dollar in the future worth compared to a dollar today. Let's look at some concrete examples of returns. The return you get depends on the rewards, and the rewards depends on the actions you take. And so the return depends on the actions you take. Let's use our usual example and say for this example, I'm going to always go to the left. And so we already saw previously that if the robot were to start off in state 4, the return is 12.5. As we worked out on the previous slide, it turns out that if it were to start off in state 3, the return would be 25 because it gets to the 100 reward one step sooner. And so it's discounted less. If it were to start off in state 2, the return would be 50. And if it were to just start off in state 1, well, it gets the reward of 100 right away. So it's not discounted at all. And so the return, if it were to start off in state 1, would be 100. And then the return in these two states are 6.25. It turns out if you start off in state 6, which is terminal state, you just get the reward and thus the return of 40. Now if you were to take a different set of actions, the returns would actually be different. For example, if we were to always go to the right, if those were our actions, then if you were to start in state 4, get a reward of 0, then you get to state 5, get a reward of 0, and then get to state 6, and get a reward of 40. In this case, the return would be 0 plus 0.5, the discount factor, times 0 plus 0.5 squared times 40. And that turns out to be equal to 0.5 squared is one quarter. So one quarter of 40 is 10. And so the return from this state, from state 4, is 10. If you were to take actions, always go to the right. And through similar reasoning, the return from this state is 20, the return from this state is 5, the return from this state is 2.5, and then the return at the terminal state is 140. By the way, if these numbers don't fully make sense, feel free to pause the video and double check the math and see if you can convince yourself that these are the appropriate values for the return, for if you start from different states and if you were to always go to the right. And so we see that if we were to always go to the right, the return you expect to get is lower from most states. So maybe always going to the right isn't as good an idea as always going to the left. But it turns out that we don't have to always go to the left or always go to the right. We could also decide if you're in state 2, go left. If you're in state 3, go left. If you're in state 4, go left. But if you're in state 5, then you're so close to this reward, let's go right. So this would be a different way of choosing actions to take based on what state you're in. And it turns out that the return you get from the different states will be 100, 50, 25, 12.5, 20, and 40. Just to illustrate one case, if you were to start off in state 5, here you would go to the right and so the rewards you get would be 0 first in state 5 and then 40. And so the return is 0, the first reward, plus the discount factor 0.5 times 40, which is 20, which is why the return from this state is 20 if you take actions shown here. So to summarize, the return in reinforcement learning is the sum of the rewards that the system gets, but weighted by the discount factor, where rewards in the far future are weighted by the discount factor raised to a higher power. Now this actually has an interesting effect when you have systems with negative rewards. In the example we went through, all the rewards were 0 or positive, but if there are any rewards are negative, then the discount factor actually incentivizes the system to push out the negative rewards as far into the future as possible. Taking a financial example, if you had to pay someone $10, maybe that's a negative reward of minus 10, but if you could postpone payment by a few years, then you're actually better off because $10 a few years from now, because of the interest rate, is actually worth less than $10 that you had to pay today. So for systems with negative rewards, it causes the algorithm to try to push out the negative rewards as far into the future as possible. And for financial applications and for other applications, that actually turns out to be the right thing for the system to do. You now know what is the return in reinforcement learning. Let's go on to the next video to formalize the goal of reinforcement learning algorithm.
[{"start": 0.0, "end": 6.76, "text": " You saw in the last video what are the states of a reinforcement learning application, as"}, {"start": 6.76, "end": 12.120000000000001, "text": " well as how depending on the actions you take, you go through different states and also get"}, {"start": 12.120000000000001, "end": 14.76, "text": " to enjoy different rewards."}, {"start": 14.76, "end": 19.64, "text": " But how do you know if a particular set of rewards is better or worse than a different"}, {"start": 19.64, "end": 21.16, "text": " set of rewards?"}, {"start": 21.16, "end": 26.04, "text": " The return in reinforcement learning, which we'll define in this video, allows us to capture"}, {"start": 26.04, "end": 27.04, "text": " that."}, {"start": 27.04, "end": 31.96, "text": " So if you go through this, one analogy that you might find helpful is if you imagine you"}, {"start": 31.96, "end": 37.96, "text": " have a $5 bill at your feet, you can reach down and pick up, or half an hour across town,"}, {"start": 37.96, "end": 41.44, "text": " you can walk half an hour and pick up a $10 bill."}, {"start": 41.44, "end": 43.879999999999995, "text": " Which one would you rather go after?"}, {"start": 43.879999999999995, "end": 49.96, "text": " $10 is much better than $5, but if you need to walk for half an hour to go and get that"}, {"start": 49.96, "end": 54.92, "text": " $10 bill, then maybe it'd be more convenient to just pick up the $5 bill instead."}, {"start": 54.92, "end": 60.64, "text": " So the concept of a return captures that rewards you can get quicker are maybe more attractive"}, {"start": 60.64, "end": 63.6, "text": " than rewards that take you a long time to get to."}, {"start": 63.6, "end": 66.2, "text": " Let's take a look at exactly how that works."}, {"start": 66.2, "end": 68.36, "text": " Here's our Mars rover example."}, {"start": 68.36, "end": 74.04, "text": " If starting from state four, you go to the left, we saw that the rewards you get would"}, {"start": 74.04, "end": 80.04, "text": " be zero on the first step from state four, zero from state three, zero from state two,"}, {"start": 80.04, "end": 83.88, "text": " and then 100 at state one, the terminal state."}, {"start": 83.88, "end": 91.75999999999999, "text": " And so the return is defined as the sum of these rewards, but weighted by one additional"}, {"start": 91.75999999999999, "end": 95.25999999999999, "text": " factor, which is called the discount factor."}, {"start": 95.25999999999999, "end": 99.44, "text": " So the discount factor is a number a little bit less than one."}, {"start": 99.44, "end": 102.28, "text": " So let me pick 0.9 as the discount factor."}, {"start": 102.28, "end": 105.52, "text": " I'm going to weight the reward on the first step is just zero."}, {"start": 105.52, "end": 112.32, "text": " The reward on the second step is a discount factor, 0.9 times that reward, and then plus"}, {"start": 112.32, "end": 118.39999999999999, "text": " the discount factor squared times that reward, and then plus the discount factor cubed times"}, {"start": 118.39999999999999, "end": 119.6, "text": " that reward."}, {"start": 119.6, "end": 129.44, "text": " And if you calculate this out, this turns out to be 0.729 times 100, which is 72.9."}, {"start": 129.44, "end": 135.56, "text": " The more general formula for the return is that if your robot goes through some sequence"}, {"start": 135.56, "end": 143.04, "text": " of states and gets reward R1 on the first step and R2 on the second step and R3 on the"}, {"start": 143.04, "end": 152.4, "text": " third step and so on, then the return is R1 plus the discount factor gamma, that's Greek"}, {"start": 152.4, "end": 160.32, "text": " alphabet gamma, which I've set to 0.9 as this example, the gamma times R2 plus gamma squared"}, {"start": 160.32, "end": 168.72, "text": " times R3 plus gamma cubed times R4 and so on until you get to the terminal state."}, {"start": 168.72, "end": 176.07999999999998, "text": " What the discount factor gamma does is it has the effect of making the reinforcement"}, {"start": 176.07999999999998, "end": 181.79999999999998, "text": " learning algorithm a little bit impatient because the return gives full credit to the"}, {"start": 181.79999999999998, "end": 188.64, "text": " first reward is 100%, is 1 times R1, but then it gives a little bit less credit to the reward"}, {"start": 188.64, "end": 193.48, "text": " you get at the second step, that's multiplied by 0.9, and then even less credit to the reward"}, {"start": 193.48, "end": 197.29999999999998, "text": " you get at the next time step R3 and so on."}, {"start": 197.29999999999998, "end": 203.07999999999998, "text": " And so getting rewards sooner results in a higher value for the total return."}, {"start": 203.07999999999998, "end": 207.79999999999998, "text": " In many reinforcement learning algorithms, a common choice for the discount factor would"}, {"start": 207.79999999999998, "end": 215.23999999999998, "text": " be a number pretty close to 1, like 0.9 or 0.99 or even 0.999."}, {"start": 215.24, "end": 219.76000000000002, "text": " But for illustrative purposes, in the running example I'm going to use, I'm actually going"}, {"start": 219.76000000000002, "end": 224.0, "text": " to use a discount factor of 0.5."}, {"start": 224.0, "end": 230.88, "text": " So this very heavily down weights or very heavily we say discounts rewards in the future,"}, {"start": 230.88, "end": 235.8, "text": " because with every additional passing time step, you get only half as much credit as"}, {"start": 235.8, "end": 239.66000000000003, "text": " rewards that you would have gotten one step earlier."}, {"start": 239.66000000000003, "end": 245.20000000000002, "text": " And so if gamma were equal to 0.5, the return under the example above would have been 0.9,"}, {"start": 245.2, "end": 256.52, "text": " 0 plus 0.5 times 0, replacing this equation on top, plus 0.5 squared, 0 plus 0.5 cubed"}, {"start": 256.52, "end": 258.52, "text": " times 100."}, {"start": 258.52, "end": 263.28, "text": " That's the last reward because state 1 is a terminal state, and this turns out to be"}, {"start": 263.28, "end": 266.88, "text": " a return of 12.5."}, {"start": 266.88, "end": 272.2, "text": " In financial applications, the discount factor also has a very natural interpretation as"}, {"start": 272.2, "end": 275.44, "text": " the interest rate or the time value of money."}, {"start": 275.44, "end": 281.64, "text": " So if you can have a dollar today, that may be worth a little bit more than if you could"}, {"start": 281.64, "end": 286.52, "text": " only get a dollar in the future, because even a dollar today, you can put in the bank, earn"}, {"start": 286.52, "end": 290.41999999999996, "text": " some interest and end up with a little bit more money a year from now."}, {"start": 290.41999999999996, "end": 295.59999999999997, "text": " So for financial applications, often that discount factor represents how much less is"}, {"start": 295.59999999999997, "end": 299.4, "text": " a dollar in the future worth compared to a dollar today."}, {"start": 299.4, "end": 303.15999999999997, "text": " Let's look at some concrete examples of returns."}, {"start": 303.15999999999997, "end": 308.4, "text": " The return you get depends on the rewards, and the rewards depends on the actions you"}, {"start": 308.4, "end": 309.4, "text": " take."}, {"start": 309.4, "end": 313.35999999999996, "text": " And so the return depends on the actions you take."}, {"start": 313.35999999999996, "end": 321.59999999999997, "text": " Let's use our usual example and say for this example, I'm going to always go to the left."}, {"start": 321.59999999999997, "end": 328.79999999999995, "text": " And so we already saw previously that if the robot were to start off in state 4, the return"}, {"start": 328.8, "end": 329.8, "text": " is 12.5."}, {"start": 329.8, "end": 336.12, "text": " As we worked out on the previous slide, it turns out that if it were to start off in"}, {"start": 336.12, "end": 344.74, "text": " state 3, the return would be 25 because it gets to the 100 reward one step sooner."}, {"start": 344.74, "end": 347.62, "text": " And so it's discounted less."}, {"start": 347.62, "end": 351.6, "text": " If it were to start off in state 2, the return would be 50."}, {"start": 351.6, "end": 356.62, "text": " And if it were to just start off in state 1, well, it gets the reward of 100 right away."}, {"start": 356.62, "end": 358.0, "text": " So it's not discounted at all."}, {"start": 358.0, "end": 362.02, "text": " And so the return, if it were to start off in state 1, would be 100."}, {"start": 362.02, "end": 365.88, "text": " And then the return in these two states are 6.25."}, {"start": 365.88, "end": 370.52, "text": " It turns out if you start off in state 6, which is terminal state, you just get the"}, {"start": 370.52, "end": 374.56, "text": " reward and thus the return of 40."}, {"start": 374.56, "end": 380.82, "text": " Now if you were to take a different set of actions, the returns would actually be different."}, {"start": 380.82, "end": 387.72, "text": " For example, if we were to always go to the right, if those were our actions, then if"}, {"start": 387.72, "end": 394.16, "text": " you were to start in state 4, get a reward of 0, then you get to state 5, get a reward"}, {"start": 394.16, "end": 398.82000000000005, "text": " of 0, and then get to state 6, and get a reward of 40."}, {"start": 398.82000000000005, "end": 407.84000000000003, "text": " In this case, the return would be 0 plus 0.5, the discount factor, times 0 plus 0.5 squared"}, {"start": 407.84000000000003, "end": 409.56, "text": " times 40."}, {"start": 409.56, "end": 413.8, "text": " And that turns out to be equal to 0.5 squared is one quarter."}, {"start": 413.8, "end": 416.18, "text": " So one quarter of 40 is 10."}, {"start": 416.18, "end": 420.36, "text": " And so the return from this state, from state 4, is 10."}, {"start": 420.36, "end": 423.72, "text": " If you were to take actions, always go to the right."}, {"start": 423.72, "end": 428.24, "text": " And through similar reasoning, the return from this state is 20, the return from this"}, {"start": 428.24, "end": 434.68, "text": " state is 5, the return from this state is 2.5, and then the return at the terminal state"}, {"start": 434.68, "end": 437.68, "text": " is 140."}, {"start": 437.68, "end": 441.96000000000004, "text": " By the way, if these numbers don't fully make sense, feel free to pause the video and double"}, {"start": 441.96, "end": 446.79999999999995, "text": " check the math and see if you can convince yourself that these are the appropriate values"}, {"start": 446.79999999999995, "end": 452.59999999999997, "text": " for the return, for if you start from different states and if you were to always go to the"}, {"start": 452.59999999999997, "end": 454.15999999999997, "text": " right."}, {"start": 454.15999999999997, "end": 459.91999999999996, "text": " And so we see that if we were to always go to the right, the return you expect to get"}, {"start": 459.91999999999996, "end": 462.71999999999997, "text": " is lower from most states."}, {"start": 462.71999999999997, "end": 469.35999999999996, "text": " So maybe always going to the right isn't as good an idea as always going to the left."}, {"start": 469.36, "end": 473.72, "text": " But it turns out that we don't have to always go to the left or always go to the right."}, {"start": 473.72, "end": 478.1, "text": " We could also decide if you're in state 2, go left."}, {"start": 478.1, "end": 480.04, "text": " If you're in state 3, go left."}, {"start": 480.04, "end": 481.76, "text": " If you're in state 4, go left."}, {"start": 481.76, "end": 488.08000000000004, "text": " But if you're in state 5, then you're so close to this reward, let's go right."}, {"start": 488.08000000000004, "end": 493.6, "text": " So this would be a different way of choosing actions to take based on what state you're"}, {"start": 493.6, "end": 494.6, "text": " in."}, {"start": 494.6, "end": 504.6, "text": " And it turns out that the return you get from the different states will be 100, 50, 25,"}, {"start": 504.6, "end": 509.28000000000003, "text": " 12.5, 20, and 40."}, {"start": 509.28000000000003, "end": 515.44, "text": " Just to illustrate one case, if you were to start off in state 5, here you would go to"}, {"start": 515.44, "end": 522.36, "text": " the right and so the rewards you get would be 0 first in state 5 and then 40."}, {"start": 522.36, "end": 528.8000000000001, "text": " And so the return is 0, the first reward, plus the discount factor 0.5 times 40, which"}, {"start": 528.8000000000001, "end": 535.3000000000001, "text": " is 20, which is why the return from this state is 20 if you take actions shown here."}, {"start": 535.3000000000001, "end": 540.6, "text": " So to summarize, the return in reinforcement learning is the sum of the rewards that the"}, {"start": 540.6, "end": 546.08, "text": " system gets, but weighted by the discount factor, where rewards in the far future are"}, {"start": 546.08, "end": 550.84, "text": " weighted by the discount factor raised to a higher power."}, {"start": 550.84, "end": 556.5600000000001, "text": " Now this actually has an interesting effect when you have systems with negative rewards."}, {"start": 556.5600000000001, "end": 562.64, "text": " In the example we went through, all the rewards were 0 or positive, but if there are any rewards"}, {"start": 562.64, "end": 569.24, "text": " are negative, then the discount factor actually incentivizes the system to push out the negative"}, {"start": 569.24, "end": 572.64, "text": " rewards as far into the future as possible."}, {"start": 572.64, "end": 578.0400000000001, "text": " Taking a financial example, if you had to pay someone $10, maybe that's a negative reward"}, {"start": 578.04, "end": 584.5999999999999, "text": " of minus 10, but if you could postpone payment by a few years, then you're actually better"}, {"start": 584.5999999999999, "end": 590.88, "text": " off because $10 a few years from now, because of the interest rate, is actually worth less"}, {"start": 590.88, "end": 594.74, "text": " than $10 that you had to pay today."}, {"start": 594.74, "end": 600.92, "text": " So for systems with negative rewards, it causes the algorithm to try to push out the negative"}, {"start": 600.92, "end": 603.88, "text": " rewards as far into the future as possible."}, {"start": 603.88, "end": 608.0, "text": " And for financial applications and for other applications, that actually turns out to be"}, {"start": 608.0, "end": 611.0, "text": " the right thing for the system to do."}, {"start": 611.0, "end": 614.2, "text": " You now know what is the return in reinforcement learning."}, {"start": 614.2, "end": 634.6, "text": " Let's go on to the next video to formalize the goal of reinforcement learning algorithm."}]