RL Course by David Silver - Lecture 4: Model-Free Prediction

Key Takeaways

let's get going so today uh we're going to start to talk about model free prediction um so what that means is taking something like a an environment that could be represented by a mark of decision process but no one gives us the mdp and we still want to solve it and so I think up to this point you should be wondering you know correctly well you know this is all very well but what if I don't know the U exact equations governing the way in which my factory operates what if no one tells me you know how the U the pollution level which comes out of the Smoke Stack really depends on the U the torque which I put into the engine and so forth you know what do you do in those situations and and the answer will be started we'll start to understand that in this class where we'll talk about model free prediction so methods for for which no one tells us the the environment and and the agent still has to try and figure out the optimal way to behave so we're just going to start by introducing the basic ideas um and then there's going to be two major classes to model free U prediction that we're going to talk about um first of all Carlo learning uh which in a nutshell we use to mean um methods which go all the way to the end of a trajectory and estimate the value by just looking at sample returns um and then we'll talk about another family of methods which also is model-free um and can be significantly more efficient in practice which are Temple difference learning methods um and these are methods which just look one step ahead and then estimate the return um after one step and then what we'll see towards the end of the class is that we can actually unify these approaches and there's a whole spectrum of methods known as TD Lambda where we can unify and kind of go any number of steps along the trajectory to come up with a a viable estimate of what this uh of what the value function is for our for our problem so that's the goal um I anticipate that we will probably get um to here but there's some details um which are sort of deferred to an appendix again um which basically give the sort of formal proofs of um the equivalence between montio learning and TD learning um so that might be left until after to this lecture you can look at in your own time okay so let's start with the introduction so let's kind of just take stock of where we're up to so far so last lecture um we we saw in the previous lectures what the definition of a reinforcement learning problem is and we formalized these environments a large class of environments by using a mark of decision process and then last lecture we saw how to solve a markup decision process and by solve we meant find the optimal behavior in that mdp that maximizes the amount of reward that the agent can expect to get from any state in that in that environment any state in that mvp um but this was all for a known mdp so someone had to plug in the Dynamics of that mdp and the reward function for that mdp and then you could use dynamic programming to turn the handle um apply these iterative equations using the Bellman equations back up those bman equations again and again and again and we could solve it we could output the optimal value function and hence the optimal policy um for that um MVP and what we did last lecture was we broke it down into two pieces we started off by first of all using dynamic programming to evaluate a policy and then in the second part of the lecture we saw how to use that as an inner loop so once we knew how to evaluate a policy we could find the optimal policy um and what we're going to do with model free methods is we're going to do something similar when now we're going to give up on this major assumption which is that someone tells us how the environment Works which in is is really unrealistic for most interesting problems um and what we're going to talk about instead is these model methods which go directly from the experience the interactions of the agent with its environment directly from those interactions to um a value function and hence a a policy but what we're going to do is just like in the dynamic programming case we're going to break it down into two pieces we're going to break it down into policy evaluation and then we're going to use our methods for policy evaluation to help us do control and so what we're going to do is this lecture we're going to focus just on the policy evaluation case we're just going to look at prediction we're just going to ask the question if someone gives us a policy how much reward will we get for that policy and we're going to try and figure out how we can do that entirely model free without anyone telling us the um the Dynamics or the reward function of the environment so now you can just you know run your factory and see how much reward you get and estimate the value function directly from just trying things and seeing what happens um and next lecture we'll use these core ideas to actually do control and find the optimal value function and hence the optimal U policy for the mdp okay so there's two two distinctions we're talking about here distinction between um planning which we did in the last lecture with a known model um and this and next lecture we're doing model three full reinforcement learning problem model three no one tells us the environment um and the second distinction is between prediction and control whether we're just evaluating a given policy or whether we're trying to optimize for the best policy and that's this lecture and the next lecture okay so this lecture model fre prediction how to figure out the value function for an unknown mdp when someone gives us the policy okay so now let's talk about our major methods for doing this um you should be thinking well you know how can I do this how can I figure out the value function when no one even tells me how the world Works um but we'll see it's actually straightforward um and our first method is Monte Carlo learning um it's not necessarily the most efficient method but it's extremely effective and actually very widely used in practice um and the idea is just to learn directly from episodes of experience so we don't need knowledge of the mdp Transitions and rewards so this is model free um and what we're going to do is look at complete episode so this is really suitable for episodic tasks where where you start it's like a game or something you start at the beginning of your game and and you play for some number of steps and then the episode always finishes always terminates um and what we're going to do is we're going to go all the way through our episodes and we're going to use um the simplest possible idea to estimate the value function which is just to take sample returns so we're going to look at you know one episode I got um a return of five the next episode I got a return of seven so we can already estimate the value function from our start State as being six you know the average of five and seven so we're going to use the simplest possible idea which is just to look at sample returns and average over them um and that's Monte Carlo U reinforcement maning now there's a major caveat here which is that this only works for episodic mdps you have to terminate to be able to form this mean um and we'll see some other issues with Monte Carlo learning but nevertheless it's it's such a core idea I think we should begin there it helps us to understand the key intuitions and once you can do Monti Caro learning you really you can you can build up um a value function you can solve for that value function you can do all of reinforcement learning with this very simple idea um so so let's see how this actually works a little bit more by going slightly more into detail so so what's our goal first of all so we're going to try and learn this this value function the expected teacher return from any state what we're going to do is just observe some episodes of experience under the policy that we're interested in evaluating so if we want to know what happens following the random policy just going to have our robots going to wander around randomly for a while um that's one episode we're going to do another episode and going to wander over here and then we're going to look at those episodes of experience we're going to look at the stream of States actions rewards States actions rewards that that we sampled from our policy and from the environment um and what we're going to look at is the the total discounted reward that we got from each time step onwards okay so that's this GT this was the that was the return the return was just the the reward from that time step onwards until the end of the episode with some discount Factor um so this is going to be different for every time step in the episode like you know the the return that I see from the beginning of the episode includes everything all the way along this trajectory um whereas the return from halfway through only includes the rewards from halfway Until the End okay and what we're going to do now is we're going to estimate the value function by basically just taking this expectation here so the value function is the expected return um from time T onwards if we were to kind of set our state to that particular point so if I was to set my state to here and look at the expected return from this point onwards that's the definition of the value function um so all we do in Monte Carlo policy evaluation this simplest idea of Monte Carlo learning is we use the empirical mean return in place of this expected return so we're just going to replace this expectation with an empirical mean and we're going to collect as many samples as we can from each of these states of of what happens from that point onwards and then the only issue is how do we do this when we kind of don't get to reset our state back to that exact point repeatedly and we want to kind of figure this out for for all states in our environment how do we get the the mean for all states just from trajectories um and there are two different ways we can do this um and they both work and they're both effective um but there's a sort of subtle difference between them um so the first approach is what's called first visit Monte Carlo policy evaluation um so so to understand this imagine that you've got some Loop in your mdp where you come back to the same state repeatedly um but to evaluate a state what we're going to consider is the the very first time we visit that state we're going to basically say the first time I get to this state here in some trajectory even if I come back to that state later and then go off and get some reward afterwards which going to look at the first time I arrived at that State um and when I reach that state for the first time I'm going to increment a counter to say how many times I visited that state and I'm going to add up the total return and now I could just get the the mean return from that state onwards so consider you know in each episode we're going to look at the first time I visited that state we're going to measure the total return we got from that and we're going to take the mean over those total returns from that point onwards um and all we're going to use is a you know a very simple mathematical result which is the law of large numbers which basically says that you know when you take a mean of um a bunch of um ID random variables that that the mean of those random variables actually does approach approach the true expectation so that tells us that if we see enough episodes if we just randomly sample enough episodes this very simple idea of Monte Carlo learning really will converge on the True Value function for our policy as we get more and more samples um and the only requirement is that we somehow visit all of these states um and and we do that by just sampling along our policy itself so we generate trajectories along our policy we do that again and again and again and we just look at the returns that we get from the first time you visit a state onwards and we average over those returns okay people understanding questions on that good yeah I'm slightly confused because every time we enter the step we increment the count right or because the first time we visit always no no because we we the counter persists over multiple episodes so what we're trying to do is get an average over multiple episodes so this is counting how many times over a set of episodes okay how many times have we visited that particular State for the first time and this is telling us the total return over many episodes um we're adding on the complete return for each episode here so it's just this is just um you know very simple way to say we just take the mean of all of those returns okay yeah number runon no um well so so first of all we can ask how quickly do do does the so the law of large numbers basically if you want to know how quickly does it approach the mean that's the central limit theorem so we basically know that you normally get some U normal distribution and the the rate at which the uh the rate at which the error reduces roughly sort of a with a variance of one over n okay so the number of uh the number of episodes you need to reduce the variance so the number of visits you need to any individual state is kind of um uh you know the the error you get is has a variance which reduces with one over n um which is completely independent of the size of the state space so you just need to see that returns from that state um that number of times and that very quickly will reduce your variance um and the size of the state space um again the only thing which matters is that we see these states enough times so each time we're going to see a trajectory and we basically want to make sure that that every state in that trajectory um we we're maintaining this mean for um so again um as long as your trajectory visits the states that you're interested in um you it basically depends on the frequency with which you visit those States so you have to see those States some number of times and and so it depends on how frequently your policy visits the states that you care about seeing the value function for but again that's actually independent of the size of the state space so that's one of the nice things about these model three methods actually is they they don't have unlike dynamic programming where we're doing full sweeps we just sampling here and sampling actually kind of breaks this dependence on the size of the of the problem okay so that's first visit Monte Carlo let's look at a very subtly different version um sorry quick question I don't understand how how can you make you visit states okay um we'll talk about that more next class so going to defer that question mostly to next class for now we're just doing policy evaluation so all we care about is how good are the states that we visit under policy pi and the way that we make sure that we that we see all the states that we care about under policy Pi is by following policy Pi so so just by following the policy that I'm trying to evaluate we guarantee that we see all of the states that that are reachable under that policy and so we will see all of those States um and and that idea is is sufficient for now to make sure that we see enough um visits to all of those States in subsequent lectures your your question's really actually a very uh interesting one which is how do you make sure that you cover the whole state space when you're trying to find the best policy um and that's a whole issue of exploration that comes up in reinforcement it's one of the fundamental questions of of reinforcement Le it but here we're just trying to evaluate this policy so it's enough to just run episodes with that policy you know if I want to know what happens if I follow a straight line for the wall um all I need to do is just keep following that policy of running a straight line towards the wall and I'll see all of the states which are of interest and I can evaluate those States because I've I've run that policy already okay second idea very closely related is every visit Monte Carlo policy evaluation um so now to evaluate a a single state s um if we've got this loop again the only difference is now that we're going to consider every visit to that state instead of just the first one um so we're basically going to come around um and if I could do my Loop I'm going to come back to it again and I'm going to include both my original estimate of the return including the loop and also my my second estimate from that state the second time I visited to it so basically you know in in one episode you can increment the counter multiple times for this state each time you visit it you'll increment the counter and you'll add on a different value of the return based on the point which you were up to at that time step t for for each of those visits apart from that the algorithms identical we still um use the law of large numbers this thing still finds the the True Value function everything's good so both of these are valid estimators of the mean of the expectation by just taking samples of the mean in different ways yeah which one is better which case which should um so so it sort of depends on the setting actually when we talk about TD lambra I'll come back to that question that there's different types of traces you can use and they correspond to every visit and first visit traces um and there's some evidence in favor of both depending on the domain actually okay so let's let's make an example so I just want to talk about this it's a little bit related to the assignment so um so the idea is um we're going to consider you know how can you guys how can I train you up to go and break the casino um like after after this class um so um don't hold me to that I don't want to be responsible for anyone losing money casinos actually don't follow exactly this is a simplified version of blackjack so you won't be able to use this and and really win money um but we're going to consider the game of blackjack sometimes called 21 or Pon two and things like that and it's a very game where where the dealer basically um you get you get um dealt um you start off with two cards and the idea is to get as close as possible to 21 in the summer those two cards without going over 21 so you just add up the face values of all of your cards and if if you ever get Delta card that such that the sum of your cards goes over 21 you're bust and you lose um but the closer you get to 21 the more likely you are to be beat the dealer who also has two cards um and it's going to play the game the same way and if your total beats the dealer then you you win the game and you win some money okay so that's the game with Blackjack um and how many people know the game by the way just to go yeah okay so so the way we're going to represent this we're going to represent it as an mdp um and we're going to treat the state um as having basically three different variables um in the state space first variable is the current sum of our cards so if we've got three cards and the sum of those cards is 17 we're going to say we're in a state with a sum of 17 um and note that we're not going to consider um sums below um 11 because for those States we're just going to automatically ask for another card because for free you can ask for another card and you're it's not an interesting decision at that point if you have less than 12 um there's no interesting decision to make because you'll always ask for another card okay so we're only going to consider the states where we actually have an interesting decision to make where some of our cards is between 12 and 21 um and we're going to look at what the dealer is showing so when you're playing your game you see one card of the dealers and that gets you can use that to decide whether they should ask for another card or or not and your goal is to without having seen the Dealer's next card how can you decide on this decision of whether to ask for another card and possibly go bust um or to stick with what you have so you've got those two actions to stop stick or to twist um and if you do stick um then the dealer plays out the game you just think of that as the turn of the environment the dealer plays out the game um all the way to the end that's like one step of the environment and and then you get plus one reward if if your sum's greater than the dealer sum zero if it matches and and minus one if you're if you've got less um and if you twist then um you get minus one if you go over 21 because you go fast and zero otherwise and for the transition structure of this mdp the only thing we're going to add to it is this idea that if you've got less than 12 we're going to automatically twist so we're not going to that's just part of the mdp then so you and actually make actions where there's an interesting action to make and there's this sort of Auto twist as part of the environment if you if you have less than 12 okay um so so let's apply Monte Carlo policy evaluation to this problem um and and so next class we'll actually see how to really uh find the optimal policy for now we're just doing policy evaluation um and what we're going to do is we're going to choose a really naive policy and we're going to see what happens with that naive policy and so the policy is going to be we're going to stick if the sum of our cards is 20 or 21 um and otherwise we're always going to twist so even if we've got 19 or 18 we're just going to twist and we want to know well how how good or bad is this um and we're going to consider oh sorry I forgot to mention one more State variable so we had three state VAR the third state variable is whether we have a um an ace in our hand which is usable that means it can either take the value of one or or 11 um and so it's good to have mace in in your hand um and and basically what we see is that this is basically using uh I think every visit Monte Carlo learning and and what what was done here was basically to just roll out 10,000 episodes of blackjack so to literally play out this game with 10,000 hands and then 500,000 hands and apply exactly the procedure we've just seen so for these 10,000 hands every time we came across one of those States every time we had a sum of of 13 and we had a usable Ace um and the dealer was showing a a five or whatever we would find the appropriate Point here um in the value function space and we would update that estimate of the value function a little bit towards the mean of so for for each point here we're keeping a separate estimate of the mean for that State uh and so for all of these states we update the mean from these episodes and if you run enough episodes you start to get the shape of the value function and what you should immediately see here this is really to give you a flavor of of um what happens with these algorithms you see that even after 10,000 episodes you still have a you get a pretty decent estimate of the um case where well you don't have an ace but the estimate where you do have an ace is much noisier and that's because these are rarer these states are rarer so 10,000 episodes you don't actually see enough cases where you've got an ace to really figure out all of these means correctly so it's still quite noisy um and you need something like half a million episodes to really get the correct shape of this value function and this shape is telling you something quite interesting which is you know as you'd expect if the Dealer's um showing something towards an ace uh so the better the dealer has the the worse of your your value is um unless he's got an ace that's even worse there um and and that this is your sum so if you've got 20 or 21 you do quite well in this game but for anything below that you do really badly because you've got this very naive polic you're just going to keep um twisting and probably go Bast um so we see that emerging nicely from the structure of this value function just by sampling so no one told us the Dynamics of the game no one told us the probabilities uh that govern the game of of blackjack no one told us the structure of the pack the deck of cards um this was just by running episodes trial and error learning and figuring out the value function directly from experience okay can you just clarify the the dealer aises it does it go Ace 2 three four yes yeah okay okay so Jack um Queen so picture cards are just treated as tens in this in this game so in Black Jack all picture cards have value of 10 Yeah question is the expected reward given you're atate you follow the policy the expected um return which is yeah the expected return which is the value function so if you were to follow this policy each point on this diagram that the height of this point on that diagram is showing you your estimated value function your estimate of how well you will do whether you'll win or lose this game um if you're in a situation where you say where the dealer is showing an ace um and you've got a player sum of say 19 um this value here tells you how well you think you will do in that game um and so it's the shape of this value function is is exactly the information we're after right once we have this um we can do all kinds of things like the the key quantity we're after is this picture once you you have this picture you can evaluate your decisions and and pick the best decision and make better policies because you can look at the shape of this surface for all different policies and find the best one okay good um and so the assignment is to work on a similar game something called easy21 which um um I think you'll have fun just playing around with and trying to understand and you can run all kinds of reinforcement learning algorithms to to figure out not just policy evaluation but to find the optimal policy for for that game that turn off slightly with the 10 compared to the n on the bottom right hand side there um yes it might just be noise in the um evaluation I the 10 would be a better estimate right just because you have more T if you if you bundle up together all the JS and queens and kings maybe not better but uh different but if the Dealer's got a 10 it's a better hand the dealer right that's why you get no because you're on 19 um when you're on 19 you don't want to get a 10 that's why it's improving slightly all the way up because you don't want large cars so you're happy when the got large cars well it's a little bit unclear right so it depends on the strategy the dealer is using to um to twist actually like so so I think it depends so so it might be that the dealer has the same um strategy as us in which case um having something like a seven or eight is actually a bad situation for the dealer because um they will um they'll probably twist and most likely get a 10 again and then they'll most likely Twist Again and um you know and there's a higher probability of going bust here than if they've already got a 10 in which case they're likely to get another 10 because there's more of them um and then they'll stick so I think it depends on the dealer strategy to program actually had to program the de strategy as well which we don't know you do know for the assignment okay so let's move on um but I think that illustrates that you know that the value function depends depends on all kinds of factors like you don't the actual value function does depend on on every aspect of the environment it depends on how the dealer acts it depends on the deck of the card the randomness how many tens there are compared to nines and eights all these things um affect the value function and yet we don't need to tell our agent any of those things just by sampling the returns we're able to go directly to the the right thing which is the value function and and hence the optimal behavior in the next lecture without needing to explain it anything about the Dynamics and that's the power of model free reinforcement learning you can go directly to the result without going through these intermediate steps okay so so far we've talked about this sort of um explicit computation of the mean um so what we're going to see is that this can be done um incrementally we're going to start to move towards online algorithms which um step by step update the mean um so this slide is really it's probably a well-known result sorry if you guys are aware of this but it's just to show that the mean can be computed incrementally you don't have to first of all um make the sum of everything and then divide the sum by your count um you can do it incrementally and so very briefly if the the mean of K elements is just one over K of the sum of those U those elements um what we can do is we can split this sum out into a sum up to Kus one so the previous Kus one elements plus the K element um and then what we can do is just observe that that this sum here is K minus one time the mean um up to K minus one so that's this sum here is just um you can take your previous mean multiply it by K minus one and then add on your new element and divide by K again that gives you your new mean um and then if we just rearrange these terms uh we see that if we collect together our xks um then we've got one over K of them here um and our mu we can basically pull out here um and we can subtract off the the one over k um UK that we have here um and this is the K * 1 K of new K that we pull out here and what we see is that you can basically the the new mean is the old mean plus some step size 1 overk a little increment towards the difference between um your new element and what you thought the mean was so we're going to see a lot of algorithms which take this form there's an error turn here so think of this error term as this being your estimate of what the value is going to be before before you actually see this new element you've got some estimate of what you think that that value is going to be which is your previous mean so you think that your elements are going to have this value on average then you see your new element here and there's some kind of error between what you thought was going to happen and what actually happened so that's your error term here um and now what we basically do is we update our mean a little bit in the direction of that error we're going to see a lot of algorithms which take that form where where you sort of correct um you have like a prediction and you correct that prediction in the direction of the error so basically if you if you are estimating your mean too too low and you see something higher then you need to increase the value of your of your mean in the direction of the error between what you thought the mean was and what you actually observed so that's the idea of these incremental mean computations um and we'll pretty much see that every algorithm in the remainder of this lecture takes takes this form um and so let's first of all do this with incremental Monte Carlo updates so we can take our Monte Carlo algorithm and we're just going to make it an incremental update so we're going to do it episode by episode now without keeping track of these sums in these in these visit counts oh you still need the visit count but without keeping track of the sum um what we're going to do um so we're going to take the same algorithm so for each state with some return that we've seen um so for now we'll just keep the visit count um and what we'll do is we'll update every time we see that state we're going to measure the return from that state onwards um we're going to look at the error between the value function that's what we thought the um the return was going to be um and the return we actually observed we're going to generate some error we're going to update our mean estimate for that state a little bit in the direction of that return okay and so this is exactly the same we've just transformed our computation of the mean in this way yeah question no no so so we're not Computing intermediate returns that's the next part of the class actually so I'm glad you said that so so what we're doing is we're still getting the complete return but it's only incremental in the sense that every episode we're going to update our mean and just it's this it's it's a trivial rewrite of how we compute the mean um and the reason we're doing it this way is we're we're showing how this is going to develop towards other algorithms so we're going to replace this one over n by by other quantities and we're going replace the target we move by other quantities um but all of it's just to show that so we're doing exactly the same computation as before nothing has changed it's just an incremental mean update just to put things in the form that we're going to use later um so we're we're doing things Episode by episode we're incrementally updating our estimate of the the mean for that yeah but we add this um these values under and after after we finish the episode right because then we know the value function yes so this is all forward looking everything with Monte Carlo so far you have to wait until the end of the episode to see the the return that you got and then you have to go back to the state um that you want to update and say okay well from that state I ended up getting 100 points um of reward and now you update your your estimate from at the end of the episode so this is one disadvantage of Monti Carlo that we'll address shortly okay so so really what we're going to move towards then is is we want to move towards um algorithms that that don't have to maintain these statistics and just incrementally update themselves and one way in which this can be done is actually um by forgetting old episodes so you don't necessarily want to take a complete mean um sometimes you actually want to forget the stuff that that came a long time ago and one way you can do that is just by having a constant step size here and this gives you like an exponential forgetting rate when you're Computing your mean it gives you a exponential moving average of all of the returns you've seen so far um so it's another way to compute a different type of mean now where we've replaced our one over n by by this fixed depth size Alpha but the the concept is still the same that we we had some estimate of what we thought the mean value was going to be um then we saw some return from that state onwards that gives us an error term and now we just move our value function a little bit in the direction of that error except now we don't move all the way to correct this exactly to the to the overall mean um we we maybe um under or over correct depending on what the value of alha is but the only thing which you've got here is like we don't have to store one integer right which is so the question was is there an advantage to this Beyond not having store n so maybe I wasn't clear so so so first advantage of this approach is is that um this applies to non-stationary setups where where things can be drifting around so in the real world well stuff is changing you don't want to remember everything um all the way into the past because stuff that came 100 years ago you kind of want to forget about and including that in your mean is just going to slow you down and sort of give you baggage that you you actually want to to let go of and we'll actually see as the um lectures develop that that we're always in that case in reinforcement learning we're always in the case where things are nonstationary because um although in this lecture we're evaluating a fixed policy in general we'll start to improve the policy and so the thing which we're evaluating is getting better and better and better and so that's why we prefer these um non-stationary um estimators um rather than taking the true mean um in addition um it's something where we can have memoryless algorithms where where each a new Step comes in and we just look at that step and we can do an update without having to track these statistics about what's come up on I think that's a less important detail um so we're just in this setup where we're looking at algorithms where we move a little bit towards the the sample that we've seen okay so so that's Monte Carlo learning so very simple idea you you run out episodes you look at those complete returns that you've seen and you update your estimate of the mean value towards your um sample return for each state that you visit okay now we're going to move on to a different class of methods which really do now break up the U the episode and use incomplete returns so so let's think about this what do we mean by Temple difference learning so again like Monte Carlo learning these methods TD methods we call all them they learn directly from um actual experience from interaction with the environment um says episodes here actually TD applies to the non-episodic case as well continu case TD again is is model free so again we don't need to know how the environment works the transition structure the reward structure you know again we don't need to know how the dealer works or the deck of the cards um or any of those details um but one difference from Monte Carlo is that now we're going to learn from incomplete episodes so we don't have to go all the way until I hit the wall and see how much reward I got from that complete trajectory I can basically take a partial trajectory um and now use an estimate of how much reward I think I'll get from here up until the wall um in place of the actual return so this idea is called bootstrapping this idea of substituting the remainder of the trajectory with our estimate of what will happen from that point onwards that's called bootstrapping we basically update our guess of the value function so I'm going to start off guessing how much how long it's going to take me to get to the wall I'm going to walk some number of steps I'm going to make another guess of how long it's going to take me to get to the wall and I'm going to update my original guess towards my subsequent guess that that idea is called bootstrapping and that's the fundamental idea behind TD learning okay so let's make that more concrete so again the goal is the same as we had before we're trying to learn our value function V Pi we're just doing policy evaluation in this class next class we'll turn this into a control method um and we're just going to look at our interactions under some policy so if I follow my random walk around um you know how well will I do how much reward will I get and I want to estimate this efficiently um and now we're going to try and do this online we're going to try and just look every step I'm going to make a new estimate adjust my estimate of the of the valy function without waiting until the end um so so let's think about what we've done so far so in Monte Carlo what did we do well we basically we were in some State we had an estimate of value function um this was our previous estimate the value function we got our return we looked at the error term between our estimated value and the return and we updated our value function a little bit in the direction of that error so what we're going to do now is we're going to use temporal difference learning let's consider the simplest version td0 and we'll understand later what that zero means but what this means is now we're going to update our value function towards the estimated return after one step and I'm going to estimate how much um the return is going to be and our estimate basically consists of two parts just like in the bman equation so the estimate consists of two parts which are the immediate reward so I think the total reward is going to be the immediate reward plus the discounted value of The Next Step so it's just like the Bellman equations we saw in the previous um in the previous lectures and now what we're going to do is we're going to substitute this estimated return and we're going to use that instead of the real return so we're basically going to take the exactly the same algorithm we had before pull out the real return we're going to replace it with an estimate of the return which consists of these two pieces the immediate reward plus our estimated reward over the rest of the trajectory um so we're coming up with a an estimated biased um algorithm um and we'll see the consequences of that bias shortly okay so this term here this red term here is what we call the TD Target this is the thing which we're now moving towards it's like a a random Target it depends on exactly what happens over for this next time step um but we get some immediate reward and some value at wherever we happen to end up and we're going to move towards that thing um and that thing's called the TD Target and this whole error term here the difference between what we thought we had um and the difference between our TD Target and our our estimated value before we saw this this St is called the TD error the difference between our estimate before and our estimate after taking a step that's the TD error um so why is this a good idea I mean I think the simplest example would be imagine you're driving along um you're driving in your car um and if you're doing Monte Carlo learning um you have to basically you know when would you update your your value function well imagine that you you drive along and consider the following scenario where you're driving um you see suddenly a car um that comes hurtling towards you um and you think you're going to crash but then you don't actually crash at the the last second the car swerves out of the way um and and you don't actually crash so in Monte Carlo you wouldn't get this negative reward you wouldn't have a crash you wouldn't be able to update your value to say that you almost um died but in TD learning you're in this situation where you think everything's fine then you um you drive along and you're now in a situation where you think you're going to die think this car crash is going to happen and so you can immediately update the value he had before to say oh that was actually worse than I thought maybe I should have slowed down the car and anticipated this potential near-death experience and you can do that immediately you don't need to wait until you die to update your value function um so there's a great Slide by U someone I know in reinforcement he he puts up these backup diagrams that we saw in the last class and with this big skull and crossb and saying you can't back up death anyway so let's do another driving example um so this example is from sattin andto so you can look at this in your own time um but the idea was basically that you know I'm driving along I'm on my way to work let's imagine I didn't actually do my usual horrible commute on the train and was actually in a car um so um I start off by making some prediction of how long it's going to take me and so these these rows basically show how how much time has passed so far um how much time I think it's going to take from this point onwards and the total of um these two columns here time so far plus predicted time to go okay I start off thinking it's going to take me half an hour to get to work but you know maybe then I I leave the office and I reach the car and I see that it's raining and I'm like oh I'll have to drive a bit slower I'll probably be more traffic um took me five minutes um and now okay maybe I haven't really adjusted my I now think it's raining so it's going to take me slightly longer um so I think it's going to take 35 minutes to get to the office now giving a total of 40 um Next Step um I get off the motorway Highway um and that's taking me 20 minutes um and now I think okay that went a bit smoother than I expected so now I think there's only 15 minutes to go um giving a total of 35 um then I get stuck behind a truck and think oh actually it's going to take me a bit longer than I thought so now I kind of increase this I think oh there's actually 10 minutes to go now it's going to take me 40 minutes um and then I get on the home street and I've only got you know things are going okay but it took a little longer than they thought I think they're still minutes to go and then eventually I get there and it actually took in total 43 minutes um I realized there's no more time to go and so the total everything lines up at the end um and we think that um there's nothing left and it took us 43 minutes in total so now how do we actually update our value function based on this trajectory of experience um so this these figures really show the difference between Monte Carlo and TD in practice and in Monte Carlo learning if we look at each point along that trajectory um this shows basically um how much um like the total predicted Journey time so basically what we thought so it actually took 43 minutes along here um but at every moment I had some prediction of what that total time would be um so you know here I thought it was going to take 30 minutes it actually took 43 um then it sort of I reached the car and at that point I thought uh oh it's going to take 40 minutes and then things were going better so I thought it's going to take 35 minutes and so forth and each step along this um using Monte Carlo learning you update towards the actual outcome you have to wait until you finally get there see that it actually took 43 minutes and then update each of your value estimates along the way towards that 43 minutes okay whereas with TD learning it's quite different now every step is like you started off thinking it was going to take you um 30 minutes um after one step you thought it was going to take you 40 minutes so you can immediately update there already you don't need to wait until anything else happens can say oh I was in a situation where I thought it was going to take 30 minutes but then I saw it was raining so probably my 30 minute was too optimistic let's adjust that a little bit towards 40 minutes um at the next step you know I started off think it was 40 minutes but then things went quite smoothly on the highway so I can immediately pull this guy down and say well maybe I was a bit pessimistic and I should move this towards this guy um and then you know you have to realize that you might get stuck behind a truck so that might pull you back up again um and so you should move this towards your subsequent estimate and eventually you get grounded by the actual outcome so you're always updating the guess towards a guess but eventually you get grounded by this actual outcome where you really get there and that's the end of your episode um and you get your your real reward and having a day at work um in in this example what are the what what is the goal and what are the actions um so so first of all okay um the goal um is to so the reward function is the time that it takes you um so think of that as the reward function the reward function is time um you could think of this as the goal is to get to work and you get minus one per step so if you made all of these negative you could think of that as a goal and that would be a well formulated um markup decision process that such that the optimum corresponds to getting to work as quickly as possible the actions are um there are no actions here think if this is a markof reward process we're just trying to do policy estimation the policy could be anything we want the policy is just driving your car and the action SPAC is it could be anything um and the reason it doesn't matter is we're just trying to evaluate whatever that policy is and whatever that space is for now we're just looking at how to how to evaluate how much reward I got from this particular trajectory remember you can flatten any mdp into a markup reward process given a fixed policy so that's kind of what we're doing we're just evaluating this thing we're just trying to understand how much reward you get um independent of the action space next class it will matter much more what the action space is because we're going to pick actions so as to optimize our our decisions okay so is this a good or a bad bad idea so well there's several ways in which it's a good idea um so the one we've just seen really and focused on is that TD can learn before you see this final outcome so you don't need to wait until you crash and die you can already start learning after just one step um whereas Monte Carlo has to wait always until the end of the episode before you actually see the return and then it backs it up retrospectively um and one advantage of this is that TD can learn in situations where you never see the final outcome so this BAS basically means you know what if you get incomplete sequences what if you're learning from in some situation where you just don't get to observe the um the return at the end of the episode we'll see this later when we do off policy learning this really happens a lot in many cases um or what happens if you want to deal with continuing environments that just go on and on forever and you never get to the end well Monte Carlo just doesn't apply there I mean you can go to some arbitary Horizon in the future and just back up from there but there's always some error introduced where TD really works it really works in all of these cases even if the environment just goes on and on and on you just update now from what happens at the next step and if your steps go on forever that's okay everything still works you'll find a True Value function regardless okay does it learn the same behavior so if you have a car and the car almost crashes but it doesn't and the reason that it doesn't is because other people invid a lunatic so when you're learning step by step um you're going to learn a behavior that you're you're scared of crashing but if you only learn from the very end you would never learn something which encourag you to be to to avoid your own manic behavior Because by the time you get to the end you don't suffer