DeepMind x UCL RL Lecture Series - Approximate Dynamic Programming [10/13]

Key Takeaways

hi everyone and welcome back to our 10th lecture on reinforcement learning today we're going to be talking a lot more about approximate dynamic programming and the frame the algorithm that you've seen in the last few lectures especially in model 3 reinforcement learning in terms of this paradigm so let's dig in so last lectures you've already seen mdps dynamic programming we touched a bit about uh approximate dynamic programming mostly as a framework to to guide you through the model 3 and model model-free prediction and model-free control we've also seen a bit far back belmont equations and their corresponding operators we're going to be reusing these concepts today and we touched upon with hado on reinforcement learning under function approximation and we'll see a bit more of that in the next lectures with mateo on a particular deep reinforcement learning now this lecture we're going to be revisiting the proxima dynamic programming and under these two sources of error estimation so uh not having access to the true model and being being forced in a sense to sample from from the model through experience paired with function approximation which means that we are not in a tabular setting anymore we can't represent the value functions exactly for all states in action but we would use a function approximator to to do that okay and as i um already mentioned in the next lectures you're going to see more of these paradigms and most of the state-of-the-art research kind of falls within this paradigm and in in particular removing the perfect uh knowledge of the environment assumption and going more towards a popular version of function approximation which is deep neural networks a couple of preliminaries this have been introduced before but just to to recap and be on the same side uh we've introduced previously the belmont optimality operator this was derived from the bellman optimality equation and the definition is in in equation 1 here to note that this bellman operator has a unique fixed point which is exactly the value function that we are looking for that's why iterating this operator will eventually get us to the optimal value function this is under you know no approximation condition with perfect knowledge of the the model so this is just pure dynamic programming okay and then we had the the belmont expectation uh operator which has similar uh properties it's a contraction it has one unique fixed point but the unique fixed point of this operator is the um evaluation of the policy pi uh for for which this operator is defined okay good and uh just uh another reminder dynamic programming through the lens of these operators uh the two popular algorithms there that we've seen are value iteration and policy iteration and you've seen approximate versions of this for instance q learning being an approximate version of a value iteration so these both of these say value iteration is just applying multiple times the belmont optimality operator and again under perfect conditions no approximation this is guaranteed to converge to the fixed point of this this operator t star which is the optimal batman operator which is the optimal value function and policy iteration was this procedure of starting with a particular policy doing policy evaluation which can be done iteratively via the the bellman expectation operator or can be done in any other way especially if uh we can solve the the true system of equations and then on top of these uh this evaluation we're going to do an improvement step usually greedy improvement step and if we've seen in previous lectures that that is guaranteed to give us a better policy than the one we've just evaluated and we just iterated this process by improving greedily on these uh this evaluation and at least in finite cases this will will eventually because we're improving the the policy at the age point in time this will eventually get us to the optimal policy good okay so uh now approximate dynamic programming as you've seen before uh removes a couple of the the assumption of the of the true and of knowing the underlying mdp and being able to to represent exactly the value function so moving away from tabular and moving away from the the assumption that we can uh actually evaluate perfectly the expectations needed in these in these updates okay and by doing so in one of the cases where we don't know the underlying mdp we're going to be introducing some sampling or estimation error because we're trying to estimate an expectation via samples and in the other uh case we're going to be introducing some kind of approximation error because we're not we might not be able to represent exactly in the parametric function class we've we've chosen the true value functions that that we want to estimate at each point of this process all of these procedures are kind of iterative procedures so we'll have a lot of value functions uh in between value functions that we would need to estimate so whenever neither of like any of these functions cannot fully be approximated by the approximation uh by the parametric class we've chosen then we incur some error at that iteration so it's not only that the true solution can't be represented it might be that the true solution is representable but the intermediate uh steps in the the intermediate value functions that that we're trying to approximate are not representable under the parametric class then we'll still going to incur some approximation error okay and of course as as always the even under these conditions the the objective of of rl is to come up with a policy that is hopefully close to optimal behavior okay so let's uh let's look more in depth at the approximate value function uh value iteration uh paradigm so this is this is close to what you've seen for instance in in q learning so again as a reminder just this is this is value iteration through the lens of the belmont optimality operator so we started with the value and at each iteration k we update uh vk plus 1 towards or in in the exact case with the one step application of the belmont optimality operator applied to the value function at the previous iteration okay and iterating this as k tends to infinity this the sequence of value function eventually converges under the infinity norm to v star if this is still not uh clear to you i would urge you to to go back to our second lecture on dynamic programming and uh see the arguments there okay now the approximate version of this is basically we're gonna do this this iterative step at each iteration k approximately so that's that's what this a stands for and again this approximation can be based on the function approximation or based on the fact that we we actually don't have access to a t star and we'll we'll have to sample to approximate it and the same as as before we're gonna do a greedy improve one step uh on the one whatever uh value function we approximated here okay now the the question that the rises of course is if we iterate this process would we converge to the optimal value function we converge at all um and in general that's that's that's a no it highly depends on what the approximation here is okay um the nice things that that we kind of hinted last time is that even if we don't converge all the way to the optimal value function we are actually interested only in the uh quality of the policy this derived greedy policy with respect to the estimate at one point in this iteration we're never gonna do this iteration forever um and we're we're trying to understand how good that that policy is okay um and just uh just to be clear usually we would be using something like the q version of uh approximate value iteration where we do exactly the same process but not for v but for q again start with uh with an arbitrary value function q zero update uh towards the uh one step bellman operator with respect to uh qk at iteration k plus one and then return as a control policy the greedy with respect to to that estimate this is this is what we use usually in practice especially if we don't have a model because remember that to derive this greedy policy we actually need the action value function uh to just basically pick the the the arc max of the q value function if we don't and we have only v then we would have to have at least a one-step model in order to to derive the greedy policy so usually we're just gonna uh go for approximating the the q value okay and as i hinted uh before we really want to be able to say something about the quality of this greedy policy derived after n steps of uh iterating this approximate value iteration process and this is what the the following theorem is saying this is um an old result from 96 but still a very important result in the in the field that basically does this for us so we're going to bound under the infinity norm the performance of the policy uh at the end iteration of this value iteration procedure with respect to the optimal value function so that's what this uh first term says and this is gonna be uh bounded by two factors first the initial error this is uh uh basically defined in the in the second line here is how far is my um initial initialization with respect to the optimal value function with respect to the l infinity norm so this is this is the second term in the bound okay and the the first term here is the approximation error that i'm gonna incur at iteration k okay so usually at the iteration k plus one i'm gonna try to estimate i'm gonna try to uh back up d star q uh okay but because i'm in a an approximate setting what i'm actually gonna be uh my my next q k plus 1 would actually be a uh t star qk so this is this accounts for how much error am i incurring by introducing this a in my backups in the in the value iteration okay so this this should be kind of intuitive outside the you know the the terms uh in front that uh our performance of the policy after and and iterations of this value iteration is bounded by um both where we started so our initial error and the the approximate error that we're gonna be incurring at each iteration cool so um next we're gonna move into the the proof of the statement okay let's start by first denoting the maximum error that we can incur up to iteration n so for any iteration a k in between that and n we are maximizing over the approximation error this is again for usually for dynamic programming this would be um qk plus one but in approximate dynamic programming we're introducing approximation so this instead this term will be our value function at the iteration k plus 1. so discrepancy between um this k plus 1 and this k plus 1 is what the approximation error introduces okay so we're gonna now maximize over all of these errors and denote that by uh epsilon okay next the the first thing we're going to do is try to relate the value function at iteration k plus 1 and in particular at iteration n with respects to the optimal value function note that this is not exactly what we want uh the statement of the the theorem is actually saying something stronger in terms of the performance of the policy derived based on the estimate um at the iteration n so if we have q n then this induces uh via greedy this policy q n it's greedy with respect to the estimate that we had at iteration n and we're interested really in the in the value of that policy okay but we'll we'll see that this is really um simple based on the result that we've had um in the last lecture on dynamic programming where uh we we have a result that relates the performance of greedy policy uh with respect to the value function that induces that that policy we're going to just revise that that result in the in the next slide but first um let's let's look at this this equation okay and uh we're going gonna break it down into a couple of terms so first we um add and subtract the same term and due to the triangle inequality we can we can split these apart this is an upper bound to the left hand side okay and then note that this term is exactly the approximation error at iteration k which is upper bounded by definition by this epsilon which maximizes over all the iteration up to n okay so that's that's why we get uh this term being less than equal then epsilon and then on the the first term there we are using uh that the amount operator has a unique fixed point which is q star so uh just as a reminder that means that this holds um again because q star is the unique fixed point of this operator and then we're going to be using the fact that this operator q star is a contraction contraction actually it's a gamma contraction which means that less than equal then gamma so the um so this term now is less than equal than this term okay and now what we've actually achieved is a recurrence relationship between uh how far the value function at iteration k plus 1 is related to how far it was at the previous iteration qk okay and what we're gonna do um now is basically unfold the data that equation so this is the equation that that we're gonna like the inequality that we're gonna be using and we're gonna apply it uh at previous iterations so uh first for k and we're going to relate it to k minus 1 then k minus 1 to k minus 2 and so on so forth and what we get is we can relate this to the initial error at iteration k equals zero um and this term which is the discounted errors it's an upper bound actually of the discounted errors that we've encountered at each iteration and this is of course uh also less than equal then if this would have been uh you know k equals capital k actually goes to infinity so this now is upper bounded by um the mistake or the um how good our initialization was and this uh this term accounting for the errors that we've uh we've seen it's actually an upper bound on the errors that we've seen throughout this approximation at every iteration k okay now uh i'm just restating this here it's the same equation as as here and now the the last step is to relate apologies for the buzzer there but as as i was saying we're gonna now relate to this result to the performance of the policy induced by the estimate at iteration k or iteration n so just as a reminder the policy that we're deriving is greedy with respect to that estimate and we are interested in evaluating the that policy at iteration n and for that we're going to be using the result we had in our um last lecture on dynamic programming which was the performance of the greedy policy based on an arbitrary value function qk and that if you remember this was the performance of the derived policy q pi k can be bounded in terms of the performance of uh how far this estimate on which we're basing the greedy on is with respect to the optimal value function okay and note that we already have this term upper bounded here and just by plugging in 10 into equation 11 you get exactly the statement of the theory okay now that we've proven the statement of the theorem let's look at some of the implications that this has and first we're going to look at the last term there so some of the implications are as n tends to infinity this term in red tends to zero as um this uh gamma to the n decays exponentially passed so what that means is that although uh at each iteration n this this term appears and is is bounding our performance with respect to the the initial point our initialization of this this process as n tends to infinity basically this term will disappear which is good news which means that um in the limit we will have no um dependence on the initialization point okay um another question uh here just as maybe as a sanity check um is what if we do initialize you know by chance at exactly the uh optimal point at q star well let's say what the the bound says so obviously this uh the second term goes away because the norm there uh of the initial error is zero but uh you can see that we are left with uh another term here which is still the maximization of all the approximation error that we would encounter uh in in each iteration okay um [Music] now the question becomes would that be would that be zero in general let's uh let's consider just one iteration of this process so let's say at we start at q star as our first iteration of this process so q zero is q star and our first iteration of this approximate value iteration process gets us q1 which is the approximate version of the one step application of the belmont operator to q0 because q0 is q star then the application of the belmont operator 2 q star is q star so um q1 is actually the approximation operator applied to q star now in general this might not be zero so for instance if a is um an approximate of a hypothesis space let's say that is not within our class of approximations then this um this error at the first iteration might not be by might not be zero so even initializing at the um right solution in the sense by approximation we might move away from from this solution that being said if uh if this initial point has to be in the uh function of approximations then uh this has to be zero because the the projection here just just in in terms of coming back into the the class of functions uh this would be like not lossy so the the projection of q star under the function approximation um would just give you back the q star because that's the closest point in the function approximation uh again if if a is something like an estimation error where instead of having the true belmont operator we have a sampled version of this again this error add the first iteration might be non-zero probably will be non-zero which means that even um if we initialize at the right solution we might move away and once we move away from the the solution we can further move away and so on so forth so this this result is very general but it does a state that even if we are close enough to the solution it highly depends on what the approximation errors incurred that if each iteration will do and how much we could in principle lose based on that okay now uh let's focus a bit on the the other term we've seen already that as n tends to infinity the second term goes to zero which means we wash out the initial approximation error now let's um consider a hypothesis space uh f so this this is where um let's say our approximation comes from and uh let's now have uh a be exactly the projection uh with respect to the l infinity norm okay so this is uh the definition of this projection is uh uh is now in the uh in the equation below so we're just looking for um for the projection of g a function or vector uh under the l infinity is trying to find in the space of value function f the closest point to g under the l infinity north okay now if we do that then the approximate value iteration algorithm uh at each iteration k plus 1 tries to will uh take the form of uh applying the the bellman operator to optimality operator to the previous value function and then projecting it via this this operator now the the thing to note here is that this combine operator uh the approximation just via the projection we're still doing full dynamic programming in terms of uh using the the expectation using the true model here so this combined operator is is indeed a contraction operator in l infinity because basically t star is a contraction with respect to l infinity and the projection with respect to that norm is a non-expansional mapping so the full thing is a contraction with the same gamma parameter because this whole operator is a contraction this algorithm does converge is guaranteed to converge to a fixed point actually because it's a contraction from uh from previous the banana fix point theorem it has one unique fixed point it says a fixed point uh and this is unique that has this uh this equation and as before if q star the thing that we're looking is uh indeed in f is under our functional class then uh the above algorithm this this uh this iteration in uh in red actually converges to the to the true value function and this is this is uh easy to to see if we again remember that uh this algorithm has one unique fixed point and you can you can plug in in this equation if f equals uh the projection uh via the l infinity norm uh t star f and see that q star actually satisfies this this equation so now we've got at least on the function approximator still full full model of the mdp a converging algorithm that at least if you know the the true value function the one that we're looking for the optimal value function is representable in our functional class then we are guaranteed to to converge there even if it's not in our if q star is not in that function across this algorithm still converges it just might not be to to q star because you know as as we've established q star is not representable enough so we we can't hope to recover something uh we can't recover q star via this parameterization okay let's look now at some concrete instances of this paradigm and um uh although i have just proposed a convergent algorithm we'll see that this algorithm is somewhat impractical and we're gonna try to fix that and we'll see that uh trying to fix that actually gives us some of the popular algorithms that that you've seen before and that are now used in the in the literature okay so um let's first have a you know um clear instantiation of the algorithm that we've just proposed so at each iteration k we're trying to uh approximate uh the the one step bellman operator by projecting back with respect to the an infinity norm under some hypothesis class f now for uh concreteness we're gonna consider uh f to be the the space of all um linear functions with respect to some feature space phi so all of the the functions all of the q k in all of these iterations will have to be represented or approximated in this in this functional class okay and then uh doing that we obtain this simplify the algorithm at iteration k plus 1 we're looking in the space of linear value functions of the point that best approximates under the l infinity norm t star q k and because we have only you know one set of parameters which is w the weight of this feature vector the equation 12 can be reinterpreted as just finding at each duration k or k plus one a weight vector k plus 1 that that minimizes this this equation now um how would you solve this this equation how how tractable is this even under a very you know one of the simplest hypothesis classes uh out there now here are um a couple of potential problems but before before i flash that uh just just try to take a moment here and try to think how you would find this vector um wk plus one at each duration and how how hard or how easy would uh that update look like or what's the complexity of that that update how would you do it for you know a linear class or something like a neural network or any kind of other function approximator class there okay hopefully you've uh you've at least tried this mental exercise and see that this is not trivial um and there are basically two problems there one is that the l infinity minimization is typically hard to be carried out usually we are using different norms more prominently something like l2 that is very well behaved and easy to to optimize in the linear case this has a you know um closed form solution uh l infinity is is is usually a much harder optimization problem and as you've seen in the the previous lectures and this is the general assumption i guess in reinforcement learning is that t-star is typically unknown and has to be approximated somehow usually from samples so um here are some proposals of easing these problems so first i just hinted at this that instead of fel infinity we're just gonna replace that with something like l2 that is much easier to uh to optimize so instead of having now the l infinity optimization there we're gonna do the same thing but find in um find the point in f that is closest to um t star q uh k with respect to an l to norm or an l to norm with respect to some probability uh distribution mu okay and hopefully you you know how to solve this um any any kind of like um squared regression kind of thing will tackle that so uh in most cases this will have both uh at least for the linear case a fixed like tractable form and if not in most of the other cases we can do something like back prop and just take gradients with respect to this this loss and you've already seen you know in the lectures in model free control and variants of that that in order to approximate the star we're just gonna sample and uh usually we have this tuples of s a our next state that we're going to sample with respect to this distribution with respect to that norm and our transition model and we're going to approximate this term t t star q q k by this y t target for each sample and this is just again the true uh operator the true uh q uh d star would be just expectation of uh yt for all the the samples um sd 80 uh rt plus one st plus one okay so now uh what we get is that at each iteration we're gonna find in our um hypothesis space f q uh w this these are the parameters of the our function approximator we're still we're still using a linear function class that minimizes the square loss and this is now a sample square loss rather than the the true expectation loss okay so this is just re uh stating what the what the last equation was and um just uh uh reinterpreting yt as an approximate approximation an approximate application of the belmont optimality operator to the previous uh value function at the iteration key and this actually is a very general recipe for coming up with a fitted q iteration kind of algorithms or just simple cube based uh q learning based uh algorithms uh and there are a couple of dimensions there that we can vary one i've um really never used that we're using here linear parametrization so this can be done with any kind of functional class f that can be parameterized by as we did here with uh linear uh function classes with neural networks kernels whatever your you know parametrization of your regressor is anything can can go in there so these these are the you know the parametric class that we're gonna be approximating the intermediate value functions with now um there's there's a couple of other dimensions that we can vary the other one is again we're gonna be uh approximating uh t star the the application of this operator and in order to do that we're gonna have to sample somehow and this can be done online can be done from a fixed predefined or pre um you know a given kind of data set uh someone you know gets you some data um some previous intervention protocols some previous behaviors of policies that have been used in uh regulating the power plant or something like that and those are like you know just a fixed data set um you can also have a replay kind of uh model or a replay memory or a generative model where you can sample from this model to generate those uh those samples so all of these are you know a way of approximating that operator via samples but how you generate the samples and where they come from it's um you know it's a free dimension in a sense and the the last dimension there that is free also uh has to do with uh how we approximate the um this one step bellman operator and the the the simplest one is the one we've used before this is basically q learning uh the the other instantiation the second instantiation there is in instead of this uh um this the the application to the previous estimate we uh we have something like a target network that that we keep fixed it's almost like saying um we at one point uh decide that iteration k is uh the target network that we saved and we're gonna keep that for a while and make estimates uh and updates and when we change the target network again we're gonna call that iteration k plus one and there are multiple other versions of this this target that can be done via off policy learning and multi-step operators where we can get not a one-step estimate of this operator but maybe multiple steps uh estimate to um to speed up the credit assignment and you're gonna see that in the next lecture with the with hana both of these uh both of these variants but again this is a very general recipe and there are as i said like these these three dimensions you can pretty much mix and match so let's look at one particular instantiation of this recipe which is dqn i'm sure you've seen this before or at least you've looked at the paper and the dqn is one of these algorithms that that does follow this to this recipe and in particular for the approximation class we chose neural networks uh the samples are sampled from a replay and the um the target here in the regression is based on a target network okay now um here's another instantiation of this which is bachara where um we can't interact necessarily with the environment is the um examples i mentioned before that maybe someone hands you in some data that has been collected under some policies or under human interventions or any any kind of other uh data set and you wanna still make use of that so the function approximator there can be whatever is appropriate for the size of data or the you know the the problem specification the observation um set and then we are working with the fixed data set and let's say a a option here for instantiation is uh is just the one step uh approximation of the belmont operator via one sample which is uh which is what uh the first line here uh says this is probably the the first thing that that i would try but of course like uh you can have something like just more generally off policy updates um because the data set is uh is fixed and you didn't have necessarily access to the policy that generated that data set this might be hard so q learning so the the first version there this one is uh probably the easiest uh if you do have access basically to the collection policy then you can do something more fancy in terms of policy updates but again in both of these examples i'm kind of assuming that the data set that you are given is not the current policy that you're trying to evaluate so this will be off policy most of time if not all of the time i mean for the control problem we will always be off policy because the data set was collected under a particular policy versus now at each iteration we're changing the policy okay and another example here is what you've seen in the last lecture which is something like dinah again we can choose whatever approximation family we choose to and this is um okay this is a mistake it should be samples are both online and from a replay model and the the simplest instantiation of dyna will choose to do something like q learning which is the one sample instantiation of this this operator okay that's it for uh approximate value iteration next we're gonna be looking at approximate policy iteration the other uh algorithm for for using for doing control this is a much um less studied i guess or less popular paradigm but it's uh it's good to uh to go through it because there are many algorithms these days that do follow that but most of the algorithms that will you will encounter in control especially for off policy uh actually followed the the this this kind of uh recipe a fitted queue iteration with one of these dimensions varying or an instantiation of one of these dimensions we start with a reminder of the policy iteration paradigm this again is the iterative procedure where we start with the policy at um at the initialization and we iterate this process of policy evaluation and uh policy improvement in our case greeting improvement so at each point in time we are evaluating the the policy derived at the previous step and we make a gratification step with respect to that and we know that at least in finite cases this will converge to the optimal policy now the approximate setting uh actually the approximation incurs in this policy evaluation step only and now the value we derived at or our approximation at iteration i is the one that will provide uh the argument for the gratification so instead of doing a gratification with respect to the actual evaluation of our previous policy we're going to do a gratification with respect to the approximation to that evaluation problem as hinted before this usually does not converge to the optimal value function but um nevertheless what what we're really interested in is the quality of the policy that we're gonna get after let's say iteration k in this particular notation iteration i so in general we're interested in the quality of the policy pi i uh as determined by q pi i uh with respect to let's say the the optimal value function so how how good is that the policy after um i iterations of this this procedure and this is exactly what the the next result uh we're gonna look at um quantifies so considering an mdp and the cube um qk and pi k are the um value function uh at iteration k and the the gratification uh at iteration k minus one then we we have the following statement so we can bound the quality of the policy at time at the iteration k by the approximations errors that we've incurred uh up to that up to that point uh actually it's a it's a much stronger statement than this is saying the the in the limit the limb sup of this error so your error with respect to the value function is upper bounded by the the last errors like the convergence of this approximation errors as you approach uh convergence okay um we're gonna try to prove this uh but first some notation um i think first of all this should be a uh somewhat intuitive statement uh the same as before we're gonna the quality of the policy that you're gonna get after k iteration is uh bounded by the the errors we're making in this approximation but this is actually a stronger result as i said as these things uh the approximation errors might still converge uh in the limit or at least they are bounded which means that this um this term is also bounded and will converge at least in within that bound so it might oscillate around a fixed point but it is it is bounded by the um by how much the approximation errors vary in the limit okay so a bit of notation before we jump into the proof um you've seen these uh notations before just uh as a reminder so we're gonna note uh denote um via p the the matrix corresponding to the transition curl and this is uh the entries of these p are um sa and the s s prime which uh the the entry s a uh s prime denotes the probability of transitioning to s prime considering we started in s and took action a this is just the transition kernel and then p pi is the transition probability corresponding to policy pi this is a number of actions a number of states by number of actions number of states so this is basically a probability transition between sa and sa a prime under policy pi okay uh and just a reminder under this notation the the bellman equation can be written in matrix form as we've seen before in policy evaluation okay so having this in mind um let's uh let's start the proof um first thing we're going to do is look at this quantity that we call gain which is the performance of policy um at iteration k plus one versus the policy at iteration k so between two uh consecutive iterations of uh approximate policy iteration where uh where we have two policies at these um at this iterations and we're saying like how much better is policy at k plus one with respect to uh the policy at um iteration k okay and first we're gonna um try to say something about this quantity and then we're gonna relate this quantity with the the thing that we're actually interested in which is the the performance with respect to the optimal policy okay so the the gain as defined uh here is just the difference between these uh consecutive evaluation of two consecutive uh iterations of policy uh approximate policy iteration and this is just um rewriting the the above equation just using that the fixed point of operators pi k and pi k plus 1 are the value function corresponding to these evaluations okay and then we're gonna do um we're gonna add and subtract a couple of terms there okay this might sound a bit um or might look a bit scary at this point but it's it's just adding up subtraction um and it does have a um it does make sense in in terms of we always do this this kind of procedure just varying one term at the time uh so if you look at the the first equation here um 17 we are uh keeping the operator fix but we're uh varying the argument uh in the next equation again we're keeping the operator fixed but we're changing the argument uh now um in the in the next equation we are changing the operator but keeping the argument fixed and then the last one we're keeping the operator fixed between these two and changing the the argument so usually that's the kind of um relationships that that we're gonna have because we're gonna exploit the the properties of these operators okay so i've just written uh exactly what we had in the previous slide and we're gonna unpack this terms okay let's look at the first term here this this is going to be r we're just uh unpacking the definition of these bellman operators plus gamma and sorry two plus one minus r plus gamma pi plus one at okay and uh we can see that the r there goes uh goes away and what we're left with is gamma pi k plus 1 and the difference between these policies and this is what we called gain okay and similarly we can do the same trick for this this equation and this would be now the r's again simplify and we have p pi k plus 1 and the difference between this which we called um ek which is the uh approximation error at iteration k uh we're gonna skip this next turn because this one has a very similar um expression as the ones which you we've just seen because the operator is the same again things simplify and we get the gamma p pi k and difference between these two and again these are as before in the notation it's minus um the approximation error that we incurred at the iteration um k uh just just a bit of uh notation e k we've denoted this um the difference between uh the evaluation uh of the policy pi k and the estimate uh qk but not the norm of that this this has a sign kind of thing okay the last term that that we have here is this one and this one where um we're actually not gonna do anything but say that this is greater or equal than zero and this is because um this policy pi k plus 1 is the greedy with respect to uh this uh um q uh qk which means that the uh evaluation operator there is actually the optimality the one um application of the belmont optimality operator and this is less greater than equal than any application of any other policy okay hopefully you are able to to follow that if not uh just stop the video and go over it but these are um exactly the same equations but repeat it in the in the slide okay and again this this particular inequality you can unpack it explicitly if you want to convince yourself of that but the argument we we've just done is uh is sufficient okay so um we the only thing that we're gonna do now is uh basically upper bound this by this um so because we're gonna replace this term with zero um this is an upper bound and we're just going to plug in the the terms that the simplification of the terms that we just had here okay this is just rewriting okay and uh rewriting a bit by noticing that the gain k appears both on the right hand side and the left hand side and collecting those terms we reach this final expression um by bounding the the gain at iteration k okay so um this is the statement that we've just proven uh let's see a couple of implications so this gain is really how much your policy the quality of the policy that you derive has improved from one iteration to to the other so the first thing to notice is that if e k which is the approximation error is by definition uh here is um the gap between the actual evaluation of policy pi k and our approximation of that so if that is zero which means you have perfect evaluation at policy k that thing is zero so uh what we're getting is that the gain at iteration k is greater or equal than zero which means that the pulse the quality of the policy at the iteration k plus one is greater or equal than the uh policy uh the quality of the policy at iteration um k which is exactly what we've proven before in terms of the greedy improvement step being um an actual improvement step guaranteed improvement step over the the whole state space now um if this term is different than 0 either larger or smaller than zero this is a vector so uh some of the entries might be uh positive some of them might be negative um depending on your approximation so can this gain uh be zero be zero or uh negative which would mean that the at least in some states the policy at um iteration k plus one actually is worse than the policy at iteration k so fortunately under under approximation that's that can happen um and this is a very simple example just to give you an intuition where things can go wrong so this is a simple mdp three states we have uh plus one rewards every time we transition at the end of this uh chain uh the action space is left and right the fully deterministic uh and where uh let's say at iteration um k the policy that we're uh evaluating is uh always going right okay so if we if you if we evaluate this policy the the value function um q pi k associated with that is is as follows so um you can you can convince yourself that um at least in the terminal state if if we're in state uh s1 s2 and taking action 1 which is exiting to this plus 1 reward then we get the the reward the plus one if not if you're in a state as zero um and you're taking action um one which is going to s2 you uh basically have a zero reward plus gamma is 0.9 here so 0 plus 0.9 and the value at this state which is 0.9 uh the same for s1 we're taking one step with reward zero but then we're discounting by 0.9 this already discounted value of 0.9 now for action 2 this is a bit more complicated we start with s1 so if you're in s1 and take action a2 you're gonna transition to this terminal status and uh get uh reward one now if you are in uh state s0 and take action uh a2 you're going to transition to s1 and then you're still going to follow this is evaluating this deterministic policy of always going right so we make one transition according to a a2 we transition to s1 and then from s1 we continue according to policy pi k and the according to policy pi k we're just gonna go right uh which means that we're we're making a step we we transition to to s1 and then uh basically we're just discounting this value again because in s1 we're not actually transitioning to the the end state there we're not actually exiting because we are executing a policy that will get us in the opposite direction okay hopefully that's clear now consider um instead of having this full evaluation of policy pi k consider an approximation um for different reasons you might have either a functional class or um based on samples you get this this approximation and i've just made up some values that are you know fairly close to what the the evaluation would be and uh it's it it also maintains the you know um the relationship between the uh the action values at least within within the same action okay so it it's a reasonable approximation now if you take the greedy with respect to this approximation to this evaluation then you get a policy pi k plus 1 which is this so this is just reading out from our approximation what what am i going to do in s1 well i look at the value of these two actions uh obviously uh a2 is better i'm going to take that one uh the same in s 0 um i look at the the the values of these actions the one corresponding to a1 is better so i'm gonna take that one and in um s2 i'm gonna i'm looking again at the approximate values uh here and i see that a2 in this case is better than uh than a1 so the the induced policy is uh um is the one depicted here okay so let's now see uh this this new policy at iteration k plus one if we if i were to actually evaluate how good that policy is what what would that evaluation be and this is the evaluation for the the policy that we've just computed as greedy with respect to the approximation that that we had and this one um because of the cycle there going back and forth between those uh those states actually has this value function which you can see that if you compare the the value of a policy at uh policy pi k and the the one at uh policy at the k plus one you can see that even state by state these things are either equal or the policy at the iteration k plus 1 is actually worse uh in this state um in this state in this state so actually this is an extreme example of uh of what i wanted to illustrate in the game being the negative that in all of the k in all of the states um and actions uh the the gain is act uh either zero or negative in most situation you would have a mix of these where in some cases it will be an improvement but in some states and actions it it can actually be negative so it's not it's not under approximation it's not necessarily a strict improvement over the policy we had at the previous iteration and there is where the the problems with the uh with convergence and with you know the the monotonic improvement of these is this policies uh occurs okay okay um this was a bit of a detour but i think it was it's it's good to to have an intuition of what happens from one iteration to to the other and why this fails under um potentially fails under uh approximation so let's go back to the proof and actually go for the term that we are actually interested in in bounding which is the quality of the policy after k iteration with respect to the optimal value function okay uh we're gonna denote by lk exactly the difference between the optimal value function and the quality of the policy at the iteration k note that this thing is always positive uh because the by definition the the value of the optimal policy is um greater than the value of any other policy and this is this is not an approximation this is an actual evaluation of the policy at the iteration k okay so we're gonna start with just the definition uh we're gonna do a similar thing that we did before introducing the the bellman operators and um using the fact that um both of these value functions are um fixed points of the expectation operator of pi k plus 1 and the fixed point of the evaluation the expectation evaluator with respect to the optimal policy okay and then we're gonna do exactly what we did before which is uh introdu like uh introduce a couple of uh of terms so adding and subtracting a few of these terms so just just convince yourself that this thing and this thing goes um simplify the same this one and this one this one and this one this one and this one and again the same recipe uh as before we're just changing one thing at a time so the the the operator state is the same the argument is different again the operator stays the same argument is different the the operator changes here uh and so on so forth okay and we're gonna do very similar thing that we did before and basically bound uh all the terms that that we've uh all these um differences um we're gonna uh either spell them out or uh bound them uh in this case by zero okay the the argument goes exactly as we did before they are uh uh they're just uh rewriting what these differences are okay so by collecting uh the terms here and again this uh this particular inequality is a follows the same argument as we had before because um this operator is uh the greedy with respect to uh q k so pi k plus 1 is by definition the greedy with respect to the approximation q k so that means this operator is actually the one step optimality operator applied to qk okay so this one is always better or it's always greater than any kind of policy there so any any other evaluation operator applied to qk can't be better okay so we're just uh we're just gonna rewrite uh or all of the terms that we in group all of the terms that we had uh here um and uh we're gonna now uh expand we had the term here in terms of the the gain at the iteration k and we've previously upper bounded this by this expression so from 27 to 28 we're just plugging in the bound that we've previously proven uh for gk and we're just bringing the terms together and rewriting a couple of uh stuff and a couple of things simplify from 29 to 30. okay and uh um now sorry um as uh as k tends to infinity um then we can uh we can introduce the limb soup of this quantity so we have uh lk and lk plus one uh in in one side of the equation and the the other side of the equation uh in asymptotic regime as uh as k tends to infinity this will uh become just this term and then um basically by rewriting we we have this expression so this term all of this term here appears in the limb soup here and the last thing that that we're going to do is we're gonna take the l infinity norm with respect to this equation this is just rewriting uh what was on the on the other slide okay and when you when we take that we have a couple of terms there that that will simplify um so in particular if you look at this term uh this um fairly ugly term in uh in equation 37 this actually simplifies to being upper bounded by um one plus gamma over one minus gamma plus one this is using the fact that uh all of these matrixes uh p a pi uh for pi equals uh pi k plus one or pi k or the the optimal policy all of them are stochastic uh matrixes where the l infinity norm of all of these is one okay and that is uh that is it for the for the proof if you uh rewrite basically this uh this term you get exactly what the statement of the the theorem uh says so this is uh ek was exactly uh the the approximation error that we incur at the iteration k and this term just simplifies to this okay last thing we're going to do here is look at the concrete instance of of this algorithm and we're gonna actually look at an algorithm that you've seen before uh namely td lambda with uh a linear under linear approximation important to note at this point that this algorithm at least in the form that i describe it here will just implement the policy valuation step in an approximate policy iteration loop so it's it's just one of the steps that you have to do at each iteration k in this approximate policy iteration it's a policy evaluation this is mainly to show how one could reason under function approximator about the errors you incur at this evaluation step because we've seen from the the previous result that the quality at least in the limit of the policy that you're gonna get at iteration k as k tends to infinity as compared to the optimal uh value function is bounded by how the errors at the at each iteration as case goes to uh to infinity uh behave so keeping those errors as small as possible in the policy uh evaluation uh case will mean that that bound is tighter and tighter which means that with respect to the optimal uh value function you're losing less and less so uh in in the best case scenario if that if those error are zero then you will converge to the optimal value function so this is just a an attempt at uh saying under you know the normal scenario where we're using function approximator and we're using something like td learning how can we reason about the errors that we incur in this procedure okay so uh we start with the linear functional space and remember that the tdr under this approximation is defined as in equation 37 and then the parameter update w at each step after each tdr uh is updated with the magnitude of the tdr in the direction of phi s t a t uh previously i think you've seen this update for just the value function not the um state action value function and this phi would be um just a function of the state and i think you've denoted it as xd okay well under this um under this paradigm um this this algorithm actually has nice properties so under the normal conditions on uh of the learning rate here uh satisfying these conditions the the sum of them being infinite and the the square of them being finite then this procedure converges to um its limit um denoted here by uh w star which is not approximating the optimal value function it's just the annotation for the fixed point and uh all all of this procedure is trying to approximate uh the value of some policy pi the one we are computing the td errors with respect to and uh furthermore it has been shown in the same paper the sickness and panroi that the the approximation error that we're gonna be incurring by using td in this uh uh in in this formulation is bounded by one minus gamma lambda over one minus gamma and this term is basically the best that you can do in this functional space with respect to to this norm so this is the uh the point in f that is the closest to the value function you're trying to approximate the closest to the approximation so this is uh really saying that if i were to know this evaluation in advance then if i were to just represent it in this functional uh functional space f this is the the closest that i can get in terms of approximation and the whole expression is just saying that if i am doing this um temporal difference learning under mild conditions i'm going to be bounded by basically the best way of representing the the value function that i'm interested in this this might not be exactly uh the this this point the best approximator to uh q pi but is very close to it okay um just a couple of um you know breaking down uh the the statement as as we usually do um one is uh you can lambda is a parameter in td lambda so um uh one thing that we can ask is for which lambda is this upper bound the tightest which means that we lose we are guaranteed to lose the least and it turns out if you're eyeballing that or maximizing over that is that for lambda equals 1 which corresponds to the monte carlo estimate this this band is tighter and i'll let you reason why that would be the case okay uh the the other question that might come to mind is what if the um the value that we're trying to uh to evaluate the the value of the policy that we're trying to evaluate this q pi is actually representable in our um space of uh hypothesis class well then the this part of the equation actually is zero which means that uh q um w star which is the the point of convergence of the the the previous algorithm is actually two pi so this is nice because we're saying that if my um the the function that i'm trying to represent is part of my uh my functional class then i'm guaranteed with this algorithm to converge to that okay um now the question becomes if this is not the case if q pi is not representable in uh our hypothesis space then in general um well we won't recover q pi but more more general than that the the fixed point we converge to this um uh q uh w uh star is generally not the best approximation that we can get uh in this function of class which is exactly what this this term says okay okay that is uh it uh for today i'm gonna just do a quick summary uh now of the the two paradigms in approximate dynamic programming that with that we've uh we've seen today first let's start with the approximate value uh iteration so uh we've proven this result where as a reminder um pi n is the the policy that we're getting at iteration n of this procedure now some lessons that we've learned uh in general uh the conversion is not guaranteed depends highly on the approximation but in practice a lot of the algorithm that we've seen and we use in practice look at all the instantiations that we had at the at the end of this section um seems to point that in practice this is generally well behaved how how do we control uh how good the the policy that we're getting is well the the way to control uh this is to control the approximate uh the approximation error and there are two sources of error the estimation by a sampling so we don't have access to the true belmont operator and then there's the approximation coming from the the function class that you we are using we saw that although all of these results are in terms of the l infinity norm and if we were to optimize with respect to that we would get the safe algorithm in the sense of this being a full contraction operator and having a unique fixed point for more efficient optimization we usually substitute this l infinity norm with something like an l2 with respect to some distribution usually that will be the stationary distribution with respect to the policy that that we're following okay um note that the convergence point is not always q star especially if q star is not representable in the function class and even if that is the case if q star is representable in the functional class that is not enough uh just remind yourself of the the example that we had where really the the inside there is that all of the intermediate errors kind of have to be zero in order for that to happen it's it's not it's not exactly necessary it's the better way of saying it is that um there might be uh errors at different points in that the iteration um process that can introduce errors that cannot be cannot be washed away or at least we can't say anything um because this is kind of the worst case scenario we're maximizing over all these errors it might still be possible to uh to converge to a q star it's just um at least based on this bound we're not guaranteed to to do that if we are incurring uh any kind of error at any of the intermediate iterations okay and then what we've just seen is approximate policy iteration and we've proven this result um uh a couple of lessons again in general convergences uh is not guaranteed but again in practice this seems to be well behaved its popularity is not as great as the other paradigm just because it does have uh this inner loop this uh procedure of policy evaluation which is in itself is a is a problem of its uh its own you you've seen the i guess the the first lecture on uh model three prediction that that alone can be an iterative procedure itself so it's not it's it's not easy to usually it's not easy to evaluate a policy so this being just this side inside step of another interactive procedure means that in practice it's not it's not used as often okay um again the the statement really the only thing that says is that if we can control this errors e ek actually the the um l infinity norm of these these errors then uh we are able to control the the quality of the end result and at the same as before there are two sources of error sampling and functional crass approximation for we haven't gone uh really that much into this uh example but uh uh for efficient uh optimization again we do the same thing of uh trading in the l infinity norm to a much more behave well behave the approximation uh prob optimization problem in the l2 uh norm and this is usually now with respect to the stationary distribution of the policy that we're trying to evaluate right now a different way of saying is this is that we are safe on policy um this is just the distribution of states uh that acting in the environment with respect to the policy that we're trying to evaluate pi i in this case will will induce okay and again depending on the the function class and the couple of mild condition we can obtain convergence but the convergence point is not always um q q q star or even q pi in the policy evaluation case and moreover we haven't touched upon this but it is known that the convergent point for approximate policy iteration may not be unique in the sense of this uh this expression actually can have the behavior of um stabilizing uh like going down in terms of the the error and stabilizing around the band uh around the around the point it's still bounded by this term but it might oscillate back and forth around that uh that point okay that is it for today any questions that you might have please post on moodle or come to the q a session thank you for your time