Reinforcement Learning 7: Planning and Models

Key Takeaways

today I wanted to talk models but in the context of learning maybe I should have put it in the title but just this quickly to recap what we've been doing last lecture we learned policies directly from experience using policy gradients methods and such before that we talked a lot about learning value function and in each of these cases I said I'll not talk so much about models in this lecture deliberately because this is like a whole rich field you know in and of itself and in addition these things can look at in isolation so then it's good to separate them and to look at the components to try to understand each of the components separately before going all the way into the complete breadth of what you could imagine so in this lecture will basically revisit models and specifically we will talk about basically two again kind of separable things one is where you don't have a model you have to learn this you have to use this somehow and the other one is where you want to plan with the model and these are related but there are difference in the sense that you could also imagine just having a model and in fact when you have a model you want to do plan and we've already seen in the case of that in the dynamic programming lecture where we were doing dynamic programming as a way to do planning given a model and that's a valid way to do planning of course other ways to do planning and we'll discuss some today I will not be able to cover the full width of the field of planning because it's a very rich field one thing to keep in mind though is that a lot of the classic planning algorithms they have basically been built for the assumption that you have true model and if you don't then these algorithms might not be the right choice and I'll discuss why that's the case this is just refreshing the terminology so we've talked a lot about mobile free reinforcement learning this covers both the value-based reinforce building and the direct policy search reinforcement learning and the extra critical gur if we do where the idea is to learn a value function or repose from experience directly and the contrast with that what is sometimes called model-based reinforcement learning is the setting where you you don't have a model again but you're going to learn it from experience or you're given a model and then you plan a value function or a policy from that model now the terminology is a little bit there's a little bit of a gray zone in the literature if you search for say model-based reinforcement learning and you look at the papers that you find some papers will strictly look at basically the first case there where there's no model but you have to learn it and they'll say this is model-based reinforcement learning by definition this is motivation reinforced learning whereas other papers might allow there to be a model maybe even a true model or an approximate model so the terminology is a little bit ambiguous in that sense but it's still useful distinction to have a short shorthand that you can refer to whether or not you're building an explicit model and this is again recapping what we've seen so far but it's useful to have this picture in mind so yes very good question so yeah when I say here you learn a model or you're given a model I essentially mean or the best way to think about it for now is that you're given an MDP that you can Fuli inspect so you can look at the state transition probabilities you can look at the rewards that's the simplest thing to keep in mind although in on later slides you'll see exceptions to that for instance you might not be able to inspect the MVP you might just be able to sample from it in that case it's more like a black box that you can query but you can't actually see the actual probabilities it just gives you a random sample we would still in some cases call it a model in other cases we would just call it a simulator and in yet other cases we would just call that the environment depending on whether you care about that thing or whether you care about something else that that thing is trying to mimic so the word model is a bit overloaded it's actually very overloaded we're planning as well but unless I say otherwise when I say model you could think of some MVP which is trying to model the problem that you're actually interested in it's a good question thanks yeah so yeah so the question is if you would have a through simulator inside say you're doing Atari but you have the Atari simulator inside the agents then that would constitute in the sense of which we're talking about here that would constitute a model in that case it would even be a true model it would map exactly to the thing that you're trying to solve in which case you never have to collect real experience again you can just do all the thinking in your head do the panning if you will and this again shows that there's a little bit of a gray area here because then what is the distinction well it depends what you use for planning you could just query the simulator inside your head and you could still use a model free algorithm to learn from that which means we're using for instance Q learning to plan which is a valid thing to do is that that model based model free it kind of depends where you draw the boundary between the agent and the environment so some of these things are definitely ambiguous and that's okay right but it's good to keep in mind that they might be so did this thinking sort or aren't or was that clear it's somewhat clearer when you think about the case where there's an external environment that you really don't know and you're going to construct a model inside and you're basically going to accept that this thing is going to be approximate it's going to be not the true MVP but then you're going to try to use this somehow so now there's an explicit representation of the the outside world of the the environment that you're trying to solve and you're trying to use that in some way to come up with a good policy okay so just this is just a general overview of or at least one way to look at reinforcement learning as a whole so more or less where we started all the way at the beginning was at the top left corner where we talked about dynamic programming as a way to solve Markov decision processes and specifically we talked about these one-step updates where you basically Pam one step into the future and if you do this for the true value if you just write down the true value of the states as a function of the one step in your model in the true MVP in that case into the value at the next states then this constitutes the bellman equation so that's just the definition of what the value is and then we talked about that it's also possible that to define the optimal value in that way and then we talked about using that equation the bellman equations to basically define updates where are you instead of plugging in the true value function which you don't know you plug in an estimate and n turns out if you keep on doing these one-step rollouts and using your estimate you'll converge to the true values that was dynamic programming then we talked about basically the bottom left corridor temporal difference learning which is basically a sample based version of dynamic programming we sample a one step and then turns out if you do that sufficiently often you can still get the same answers that dynamic programming programming gives you but you don't need a model we also talked about Monte Carlo learning on the bottom writes where you do something very similar you sample but instead of using the estimate the state value at the next state you're going to sample a whole trajectory say for instance for a given policy and you use that to approximate your value what we didn't talk about that much is exhaustive search because it basically is too big so that will be the version where you use your true model to basically plan through the whole tree but you go all the way to the end so you're not using any value estimates along the way but of course you go don't have to go all the way to the end and this is a little bit of a maybe a strawman and a lot of classical planning algorithms actually work a little bit closer to that space where we are constructing at least part of the tree maybe not just a single step and we might go a couple of steps deep and then we still might use a value function somewhere along the way which means we're maybe somewhere along the center of this thing especially if you also roll in sampling and I'll talk about how to roll in sampling when do that so you could imagine combining a model and a sampling based approach and this can be actually very useful so just to remind ourselves the difference between top and bottom here is whether you use the model or whether you sample and one thing that I'm saying is you can go in between you can use your model a little bit a little bit and then still sample the other dimension is whether you use a one-step look-ahead or whether you use full look ahead and we actually talked about this quite a bit when I said you could do multi-step updates where you do a few steps and then you bootstrap and you could even have mixtures I didn't talk about that that much but there's this lab the parameter for their bottom which basically says you might bootstrap a little bit you might look a little bit at the e value evaluates vation at the certain states but you might also still roll forward from the state and then mix the sample based value from the learned value at that state so this is the full space and now we're going to try to go a little bit a summary within that space to find algorithms that might usefully combine properties of these extremes and so first to remind ourselves this was the classic example that I've shown many many times the agent takes the action the environment sends back to the observation there's a reward somewhere which you could think of as coming from the environment if you please so the difference now is that we're going to basically inject a model in there so you're still going to act but the experience now goes into the model rather than into the agent directly and then we use the model to inform our value or a policy so there's this indirection now you could still have the direct loop so basically this loop here on the top rat right it's basically the same loop as you've seen before but now there's this additional loop which basically sits inside the agents if you want where you build an additional representation of the world out there and you use that to additionally augment your your value or your policy now intuitively this already sounds like it could be a good idea because by trying to learn to model the outside world we might just be learning more about what's happening there if for instance you're if your values are fairly non informative about everything that might be happening you might be learning specific values but it might be hard to generalize when you go to a new situation and you don't understand the rules so to give give you a somewhat abstract example you could imagine if you go through a completely new situation where your vision is difference your value function might be completely wrong but if you know the laws of physics you might still be able to figure out that if you toss a ball in the air it will drop down even if you've never seen a ball of that color of the error of that size and so on so it does make intuitive sense that you sometimes want to learn a little bit more than just the policy or just a value function and maybe that more is then is then or could then be a policy sorry a model okay so that's the high level now I wanted to make it more concrete and will just be very explicit about what a model is model is in this case a Markov decision process it doesn't have to be but this is how we're going to define it for now and to keep things simple I'm going to keep the state space in the action space the same so the states and the actions are the same as those from the environments that's not necessarily the case but it's just for the simplicity of the exposition here that I'm going to stick to that case which means that the model is not fully characterized by the transition function and the rewards and these is that's what we're going to learn this little P you can see it in equation there this is the same equation we've had before when we were just talking about Markov decision processes in general except that there's now a little hats on the P and there's this ETA subscript the each are the parameters of your model because we're going to typically consider parametric models it doesn't have to be could also be a non parametric model in a sense in which case maybe the ETA is replaced by data instead of parameters you have data that you're that you're using but we have some approximate model and the idea is that this model somehow approximates the true model I'm already going to call out here that this is only one thing you could do you could imagine that the true model is too complex and sometimes it might be useful to consider that's not actually the true model but something that is still useful but I won't go into too much depth in that but that's an interesting research direction so we're going to assume that the states and axis are the same which means that we can basically just learn these things and we could also think about learning them separately which might be simpler in some cases where you basically try to learn for each state action what is the expected reward and for similarly for each state in action what is the next state yeah so in a great world what will be the approximation so yes we don't know the probabilities so the question is how do you then maybe maybe there's multiple questions one is how do you learn this and it's good to have a concrete example so we could say for instance in a great world what would what would what would be the goal of this learning this model let's take the simplest example at a great world it's completely deterministic which means that when you for instance press up in a certain cell in your great worlds you'll deterministic we go to the cell above it then what you're trying to learn here is that the next States for any state where you press up is the state above it and maybe additionally you want to learn that whenever you try to do that when you're just below a wall then it's actually the same state again you could imagine learning this quite simply in a simple small great world of course if it's very complex domain you want to generalize somehow so maybe this this model is then something that generalized as well so choose two deep neural network so that you could also query it for States and axis that you've never actually seen and you hope to still get a relatively reliably right reliable answer through generalization and actually here I'm going to make it a little more concrete so we're just going to collect some experience this could be from multiple episodes so I'm not making distinctions here between where the episodes at end or in not end of course you need to be careful about that if you want to implement something yes and then we're just going to note that this experience can basically be transformed into a dataset where you have a state and an action as an input and as the output you have the reward in the next say that you've actually seen in that situation on that time step and one thing that you can do is then to learn a function that basically tells you what the expected reward and the expected next state is for a given state in action now you can pick a loss function maybe you could have separate loss functions for the reward or the state or you could merge these somehow you could also have separate functions for the reward in the states each of which has their own loss function and for instance maybe you have something like a mean squared error whether that makes sense depends a lot on the specifics of the of the domain for instance if you think of about the Atari games you can question whether it makes a lot of sense to put a loss on the pixels of one frame versus the pixels of another frame whether you want to do this pixel by pixel or whether it makes more sense to maybe try to find some features of the screen and then try to define a loss in that space that's non-trivial in general and I won't go into much detail on how you should pick that loss because it really does depend but it's something to keep in mind when you when you want to construct something like this but whatever loss function you pick for this model you then minimize the parameters of the model so that you you map you you find this function that map's these inputs input States and actions to these outputs so in this case if you do it like that where for instance you pick a mean square error then the output would be an expectation model that's fine in a sense but there might be certain things that are that are limitations of this before I go there let me just quickly stop here to see if everybody's on board if you have any questions please PLEASE interrupt okay otherwise I'll continue to the expectation models because they might have certain disadvantages and one way to see that intuitively is you could imagine that there's an action and it randomly transitions to one of two states in one state you went to the left of a wall and the other you went to the right of a wall so note I'm not talking about the action going left or going right there's this one action that you do you you you give a certain decision to say or your motors and it just so happens to me the case and then fifty percent of the time you end up to the left if fifty percent of the time you end up to a right of a wall maybe because there's additional safety controllers or whatnot that basically prevent you from going into the wall that you don't have control over that are basically as far as the learning algorithm is concerned they're part of the environment but they are there and they do do result in you're not hitting the wall so you can imagine then if you're depending on the loss you have in your next state that the expected next state might be exactly in the wall or against the wall which is a state you might not actually end up in so if you think about the great world maybe that's an easier example to think of if your expectation if you have random transitions on these grid on these grids and let's say that if you press up you don't actually go up ever but you go diagonally left up or you go to Angley right up you could imagine that the dynamics work like that and let's say that you're just below a grid which in which there's a there's a hole then pressing up would mean in all cases you would never end up in the hole but if your loss is such that you try to interpolate between your position you would end up exactly in the hole which is a state that you never actually end up in and the reason is that we're discussing expectation models here and the expected state might not actually be a state that you could that would ever happen in reality now so this might seem that this is a problem for expectation models and it could be but for linear models and values this turns out not to be so much of a problem and you could take this in two ways one you could take this as as meaning that we should be doing linear values and models where maybe the features are themselves nonlinear functions of say your observations but then you have a linear model on top of that linear value or you could still take this to be just a limitation of the expected models and it really depends on what you want to do in terms of creet algorithms but just to show you that in a linear case is okay so what I've done here is I've basically replaced the states with features so we assume for now we have some fixed feature function that takes a state as input and in turns that into a vector Phi we've done that before as well so there's a search and here's where we're a 5 subscript T means this is your features at States s T and then of course 5 T plus 1 is the features at States T plus 1 now if we would build an expectation model on these features where again the interpolation may or may not make sense in terms of the actual features you might see then we might note if we have a linear model that this is basically just a matrix multiplication we take the features Phi T we multiply a matrix P that we're going to learn potentially and the output of this to semantical said is that this is an approximation to the expectation of the features at the next state for now we can even assume that this is exact you've learned it's modeler their orders model is given to you you have this linear model and it actually gives you the expected next features just for simplicity and let's assume that we also have a linear value function which is parametrized with some parameter vector theta which we might be learning which means that the value at s T is the dot product of this vector theta with the features at SS T so features subscript T then we can just write it out and we could talk about what is then the expectation of the value of the state after a couple of steps or even after one step but I did it here for after n steps and we can just write that out because we know going n steps into the future with our model would mean we just apply this matrix P multiple times but you can go through these steps yourself one by one if you once but the main point that we're using here is that the expectation commutes with the linear operation of the matrix so what essentially happens all the way at the bottom is that we're able to push the expectation all the way through inside and in stead of talking about the expected value of some states in the future we can talk about the value of the expected state in a sense so that's what we've done here actually the notation there at the end is a little bit that should have been expected states not the expected feature now because I I gave States this input to the value so for linear values and linear models because the expectation commutes with linear operations basically expectation models are fine but it's might not hold in general when say the value function is nonlinear you cannot push this expectation through through the value in which case these things are not necessarily the same and typically we are interested in the expectation of the value of a state after multiple steps but we don't have it because the only thing their model can compute is the expected state and then applying the value to the expected state is no longer necessarily the same as the expectation of the value at that state so is there an alternative yes first question sorry so concrete example so that's a little bit harder - harder to do on the fly I mean the examples that I gave don't all go through because in that case you actually want to have something that's nonlinear I brother had just think about that a little bit and then give an answer later for a concrete example first let's discuss the alternative so what what else could you do we might not want to assume that everything is linear and in that case the expectation model might not be sufficient because it gives you expected States that might not actually be real states and then it might not make sense to for instance feed those expected states back into your model which expects real states to iterate on and it might not make sense to feed is expected States into a value function which also might be trained only to give you valid answers for real States so what else can we then do well one potential possibility is to build in a stochastic model something that is trying to basically output rewards and next states that are valid reward the next states in a sense but it's not committing to exactly giving you just one it's it basically gives you the whole distribution and one way to do that is to use a stochastic model or a generative model lists are also called and how I noted that here is that there's this predicted next reward and next states which are our samples and the input to the model is Omega which is a noise term which means that if you would query this model again you would resample the noise term and you might get a different sample for the reward in the next state now these this reward in this next state they will have variance right because you'll Sam if you'll sample them again you might get different answers but the idea is that each of these next days are actually valid next states that you could put into your model again and thereby you could create a whole trajectory which is basically very similar now to a Monte Carlo rollout in the real environment but instead of using the real environment and carrying that to give you random States you're carrying your stochastic model yes in this case yes so P hats now here is a function this is that's a there's a good question and it's can be a function doesn't have to be a probability distribution because I have this noise term that I also explicitly give as an input and therefore the output of the function can still be noisy it's not it's not a yeah it's not a sample from its an equals but I shoot probably subscripts Omega also with some index because you're going to re sample that thing every time you query this not necessarily once for every time step you could imagine querying it multiple times at the same time step but you might put in different or you would put in different noise terms for every time you sample it typically when you actually implement this on a computer typically you would just put uniform noise in there and somehow internally this gets transformed to the right noise that you need to have your generative model yes so what this could just be equivalent to the linear model so this is already in some sense even the types don't really match because this one does take this noise term and depends on the noise term where the linear model just gives you one answer every time you query it gives you the same answer so in that sense it's already not the same there of course edge cases in which you can make these things to be basically equivalent one version would be where you basically don't you just ignore the noise term and maybe your loss function still makes it so that then the output will be the expected state and if your model itself is linear then as well then you just have your linear model back so definitely in some case you could say that linear expectation model is a special case of this one but this one's more general because it can use the noise to basically try to match the whole distribution of next States rather than just trying to output one specific next state the example I already mentioned just was just sort of reiterate that sorry the advantage is this is that you can chain these the outputs sampled States is a valid input for your model again so you could create a whole trajectory instead of just having this single single output to expect it next say that you don't then cannot really put into your model again except if it's linear however there is noise introduced which might be a downside in some cases because it might mean that your samples have have more variants so one consequence of this is if this is a fairly expensive function your your outputs might have high variance if it's a cheap function you might be able to mitigate that by you're sampling multiple times and then you create maybe a whole tree of outputs yeah so the noise term there's a good question so where does it come from how is it used so this is basically just a way to turn something that you want to be stochastic into a proper function it's it's just now a function of its inputs it has nothing to do with expiration or anything else it is just trying to match the dynamics but it's trying to match the dynamics in terms of the full distribution rather than just trying to match the expectation of the next next state so if you would sample this yeah so this map this this thing does model indeed a probability distribution yes and the idea would that meet it if you sample this thing over and over again and this is how also how you would typically then construct your loss to for train to train this thing if you would sample it over and over you would like the the outputs the rewards and the next states that the outputs outputs to match the distribution of rewards the next states that you would get from that state in action so the simplest example is perhaps when you stayed in the action are fixed let's just take a very simple example where you're basically in a one-armed bandit where there's only one state one action and there is no next state so we're just looking at the reward now this is maybe the simplest example you could think of the reward itself might still be noisy and now you could learn an expectation model which would be the expected reward but you could also try to learn it my friends would be a Bernoulli distributed as a reward the other thing you might do is instead learn a function that actually randomly samples that Bernoulli with this same probability as the actual reward get sample in that case it might not be particularly useful some actual the the complete distribution compared to the expected reward but especially if you want to apply this is a sequential case where you want to sample these next states then it might become more useful because then you can sample trajectories that are plausible which were which is not necessarily the case if you have these expected states in the middle because these expected states might not actually be they might not correspond to any real states that you might encounter yeah so the question is whether the noise term makes it easier to learn function I would say we can that's a separable question in a sense here I just wrote it down with the noise term because then you can write it down as an explicit function if you have a different way to build a function that maps or something that maps through this distribution so from a state and action maps to a probability distribution and then maybe you have a separate process that that samples from a distribution that's also fine and in fact these things might be depending on how you look at it might be equivalents depending on how you draw the box which is then labeled the P hat so this thing now captures both the mapping a to distribution and the sampling where the sampling is regulated by this Omega term but you could of course separate these you could have a separate component which tries just to Maps map to the distribution and it doesn't have any sampling it just tells you the complete distribution maybe some statistics of a parametric distribution like a Gaussian or something like that and then you could separately sample from that in fact if you had a work in the software typically is that the sampling itself then still generates this Omega and thereby constructs the actual sample that you get there subdued a random number generator and somewhere in there which generates this Omega but here I just made it explicit in the year inputs okay now there is a third alternative which is related to the previous one but it's a little bit more explicit in the sense that we're going to learn the full transition dynamics including so casa City this is different from the previous one because in the previous one we basically said we have this box which takes a state and an action and implicitly or explicitly takes a noise term and it gives you a sample in this case we're not going to take that next take that second step of sampling we're just going to stop basically at the point where we have the probability distribution so for any state in action you need to supply an additional argument which is the next state and then it will tell you how likely let next stasis or alternatively maybe it could just give you the full distribution like I said in some parametric way but in any case we'll have something which which you can write down as in this top equation as the P hats it is a function in the sense of the state action and next States and it this chute map to a a probability and in addition this should sum to one over the next state it should be valid probability distribution of course if you have an approximate model anyway maybe that's actually something that you could violate it's unclear whether you'd want to but it's maybe something to keep in mind but if you have that so in this case I split the probability of the next state from the reward model you don't have to do that you could also try to learn the joint model in one go but if you have those you could basically plan all the way ahead one way to do that is to do something like dynamic programming which is more akin to the first equation here or if you want to know the value of a state many steps in the future you can actually unroll this thing again and again and again which effectively builds a big tree where the branching factor of the tree depends on how many actions you have but also how many next states you have to consider so this could be a very big tree so it can be hard to iterate this explicitly but they can still be useful and indeed if your number of states and action isn't too big you could at least do something like dynamic programming where maybe you each time you just take one step in the tree and then you back up using your approximate model so what I'm saying is actually something that it's maybe quite obvious in hindsight what we've done here is we've basically just approximated the transition probabilities for the states and the rewards and now here we're just assuming that these are the true MVP and then we use them with our standard dynamic programming methods for instance to approximate values so we had these three let me just stop on this light we had these three ways to do models now we could do the expectation model we could do the the the sampling model stochastic model or also called generative model or we could try to learn foam well fool model and all of these cases are valid cases in some sense and some in some cases one might be more appropriate than the other one might be easier to learn than the other but then we still of course need to use them somehow to plan yeah yeah you do fool models for continuous state spaces it's the question yeah you could but of course these sums who turn into turn into integrals so then you bump into the issue of having to evaluate these integrals there's ways to do that like MCMC or other methods you do have to keep in mind then that these are going to be approximations to the full integral in general of course in certain specific cases you might actually be able to analytically evaluate the integral which might be better but even if you do that you should keep in mind that you're still analytically and therefore precisely evaluating something that depends on an approximation so whether that's then so much better is unclear so then there's an alternative which is quite obvious maybe in hindsight which is okay you could just sample this thing which is actually what MCMC does to evaluate the integral and in some sense then we're back to the stochastic models again so we have this probability distribution but then in order to use it we're going to sample from it which is a need a valid thing to do and this means that we've basically went back and we learned the full model internally but we did go back and do the stochastic model where we've sampling from this model and then sometimes it's actually easier to sidestep this this intermediate step of trying to learn full model and just try to learn a generative model immediately with just having a loss on the samples rather than having an internal explicit representation of the probability distribution depends similarly by the way you can extend all of this to continues actions in a similar way where you could imagine that there's a continuous action space but there might still be a probability distribution that might be relatively straightforward to learn for instance there might be a gaussian that you can put around maybe your policies a gaussian which case you only need a few parameters to approximate this thing and that's of course if your action is very high-dimensional but that's that that's typically just a hard problem in any case okay now I want to talk a little bit more more about how you can then represent these well I've mentioned a few of these already but let's look a little bit more detail in in for instance whether you use a table lookup which is of course only useful or possible in small problems where they use linear models or whether you use deep neural network and specifically just to be also very concrete about what we're doing let's look at the table table lookup case so in this case the model is an explicit finite Markov decision process and one thing that you can very easily do is to estimate these transition probabilities and these rewards by just tallying the actual transitions that you've made so in this case there's an indicator function here which means that this is 1 whenever the arguments are all true and it's 0 otherwise so the first equation here basically says for each time you've been in this specific state in action you're going to add all all the times you were in the next States s Prime on the left which is bound on the right and you're going to divide that by the number of times you were in this state in action in total so this will be a number that is between zero and one if you're always in the same next date is this s Prime mr. state you always end up in then this will become one if you're never there and this thing will be zero you're dividing by something which is nonzero you're dividing by the number of times you were in the state in action but you never went to this specific X Prime so then this probability will be zero and in general it will be between zero and one and in addition if you sum over all the possible S Prime's all the possible next States this will sum to one so it's a valid probability distribution and here we separated out the the reward from the transition again and then the rewards could be similarly estimated where in this case there should have been an expectation here route over the reward because of course could be random on a sorry we're doing the sampling version here so we basically is just looking at the reward and whenever you were in that state in action and you got a certain reward you're going to average exactly those so in this case we're doing an expected reward but we're learning the stochastic transition probabilities and this is typically a relatively good idea in the sense that you don't necessarily have to keep the distribution of the rewards around because we're not iterating on that we don't need to sample the rewards necessarily in our model in fact you often get lower variance if you can just plug in the expected reward for each set in action in general the next states and the reward might be there might be a joint distribution and it might be better to model that one but this is a this is one way to construct the tabular model alternatively one thing that you could also do is to use a nonparametric model as a stochastic model which is something that is very easy and intuitive I guess in the in the tabular case so what we're going to do then is keep around all of our past data in the simplest case and whenever you want to sample from your model first state in action you're just going to look into your ask saison actions and you're going to pick one that matches that stays in action for simplicity let's just now assume that you've done all actions in all states at least once but you may have them you may visit the certain states multiple times and taking the same action there so there might be multiple copies of the same States in action in your replay but if there's at least one that you can do this you could take you could query your replay buffer you could look at the states in action that you're in right now say and you might just look at your replay buffer for every time you were in let's say you took that action you could look at the reward and the next day that occurred there now you could do two things you could look at all the cases that this happened and an average over them say in which case you're doing expectation model or you could just take the first one that you find maybe randomly and then in that case you would have a stochastic model so this shows that there's a some some link between experience replay and model-based reinforcement learning where you can think of the experience replay buffer as basically being a nonparametric model that stores experience samples rather than some explicit parametric representation of course as you may have realized when I was saying this when I was explaining how this works it does come with a limitation because if a state and action pair is not in your replay then you cannot really sample meaningfully from it you cannot say what the next reward the next state would be which is of course very common let's say you're playing Atari and you have these pixel based states it might not be that likely depending on the game that you're playing it might not be that likely that you see the same frame very often or that you see is that you've seen certain frames sufficiently often that they will be in your experience replay buffer and in fact because we want to explore we would also be tempted to actually pick new states and states the new axis e states that we've seen before which means that there should be a lot of diversity in your replay but you can still think of the replay even in that case as a nonparametric model that we're using somehow and I'll get back to that in a moment this is just an example this is one we've seen before when we're talking about the difference between temporal difference learning in Monte Carlo it's the same experience that we had in that case we've been in States a once and when we were in state a we saw a reward of zero we transition to state B and then we sell another reward of zero then we had a bunch of episodes that all started in state B and in six of these seven episodes we saw a reward one and then one we saw a reward of zero now if you would apply these equations on the previous slide we will build a model that basically look look looks like this we're in a hundred percent of the cases we went from say A to B and then it's 75 percent of the cases we transitions with a reward of 1 and terminated and in fact 25% of the cases we transitions with the reward of zero and we terminate it note that all the episodes ended with state B so in this case from state B you always terminate this might will be the real MVP but it's the MVP that is consistent with the data any questions about this okay okay so now we've talked about what type of mobile you might learn how you might represent that model and of course we still want to use that model so now for now we're going to assume that this P hats ETA it's it's it's built up from somewhere you have it and one thing that you could do is just sample from it and then use model bit model free reinforcement learning might be a little bit surprising because we're going to do model-based stuff we're going to plan but this is a form of planning you're you're trying to build let me say it differently one definition that you could of what you could call planning is you take a model and you output a policy you output a plan if you will you could call that planning if that is planning then applying something like Q learning to a model is a form of planning because when you apply it you will come up with a new policy or a new plan if you so you could call that planning the only reason it's now called planning rather than learning is because we're doing it on the model rather not only in on the real environments which of course is a little bit of a subtle distinction so let's assume a generative model for now we're going to sample experience from the model and then we're just going to apply any model free RL algorithm that we've discussed previously and going back to the example that we just had this could look like this where we've constructed this this model and note that we can do this in basically two ways here one is we can construct a parametric model using those equations that I had where you basically just average the experience that you've had so far which you end up with something that looks a lot like the thing here in the middle looks exactly like the thing here in the middle alternatively we could just keep the experience around and we could call it a nonparametric model which in this case would be equivalent and then we could sample from that and the sampled experience might look like what you see here on the right which is basically in this case just something that's fairly similar to a permutation of the experience we already sell on the left there's a small distinction see if you can find the difference but if you would iterate on this long enough and we just use some model free reinforce learning algorithm you would come up with the exact answer exact same answer this is related to what we talked about before we were looking at this example I'll remind you what we were doing there what we were discussing there we were discussing the difference between temporal difference learning and Montecarlo learning and we were specifically discussing it in the context of batch learning where you collect a certain amount of experience and then you iterate over and over again on that experience until convergence and then we were talking about that the the answers found by Monte Carlo differ from the answers found by temporal difference learning which is still the case by the way but what we skimmed over in that case was that using the batch in full is basically a way to use a nonparametric model essentially we've collected the experience and we were using that we were thinking about the experience more and more without collecting new experience and so this is what people then often call planning yes what yes now you touch upon something this is very good you know so what we're not modeling explicitly what we should be modeling explicitly and what would be models implicitly when we just use the the experience is the start state distribution so that's the need something to keep in mind and it is something that you should be modeling if you just use the experience it's there right you you it's in your experience so it's already there if you construct an explicit model you should also basically construct that and I skimmed over that I basically just didn't talk about it but it is something that's part of your model not just the transitions but also where do you start when an episode ends so there's a great question yeah yes so how is batch learning equal to planning in a sense it's a good question so the way to think about it is is this so the batch learning as we talked about this is a specific type of batch learning where we were just constructed sorry we're collecting some data and then we would learn over and over on that batch of data so we're not talking about say mini batches or something like that we're talking about using the full batch of data and learning over and over on it and what I'm saying here is that you can say you could look at the batch of data you could call that a long parametric model it's not going to be exact but it's it is what you've seen so far and then the going over and over on it you could call that planning because you're not collecting any new data so what we're making we're making maybe a somewhat arbitrary distinction here between learning and planning where we can we call it learning whenever recollecting new experience and learning from that and we call the planning whenever it just happens in the agents head innocence and if you're not collecting you experience but you're just reusing the old experience you're just in your head in a sense so then we might call that planning if you're using model free reinforcement learning algorithms to do the planning they might not be aware of this right the algorithm might not know and might not care whether the data is real data or generated by a model okay so traditionally reinforced learning algorithms do not store their experiences the classic view is that some experience piece of experience comes in you somehow use that and then it's discarded and then it becomes maybe easier to talk about model free versus model-based because some of the experience is used for certain purposes say to learn a value function or a policy but you might not have an explicit dynamics model but if you do use it to construct an explicit dynamics model then we might call it model-based so this is again going back to that terminology but as I've mentioned a couple of times already it's actually a little bit more gray than that and maybe it's not so useful to make this sharp distinction anymore so so for the tabular case I've already mentioned how Batchelor learning is equal to say nonparametric model based learning and there's other equivalences i also mentioned the second point here that basically a replay buffer is a nonparametric model it's a stochastic nonparametric model if you just sample a certain state action and and then you look at what the reward and next state were in that case this will be a sample so it's a it's a generative nonparametric model if you want to call it that and more generally you could think about using your experience in a variety of ways one is you could take a sample you could put it somewhere in a model maybe maybe your model is a nonparametric experience buffer type model mayb