all right in the next portion of this lecture i'm going to introduce and introduce the notion of value functions which are a very useful mathematical object both for designing reinforcement learning algorithms and for conceptually thinking about the reinforcement learning objective so as i mentioned earlier the reinforcement objective can be defined as an expectation it's an expectation of a sum of rewards with respect to the trajectory distribution or equivalently a sum over time of the expected reward for every state action marginal now one of the things we could do with this expectation is we can actually
write it out recursively so you know how we can apply the chain rule of probability to factorize the trajectory distribution as a product of many distributions in the same way we can apply the chain rule and write out an expected value with respect to that distribution as a series of nested expectations so the outermost expectation here would be over p of s1 inside of it we have an expected value with respect to a1 distributed according to pi of a1 given s1 and now since we have an expectation for both s1 and a1 we can put
in the first reward r of s1 comma a1 and notice that this inner expectation the one over a1 is conditioned on s1 i have a bunch of blank space here because i'm going to need to put in all the other rewards but we already have r of s1a1 now we add to that all the other rewards but those require putting in another expectation now over s2 distributed query to p of s2 given s1 a1 so this expectation is conditioned on s1 and a1 and inside of that we have another expectation over a2 distribute according to
pi of a2 given s2 and now since we have both s2 and a2 we can put in r of s2 a2 and then we add to that the expected value over s3 inside of which is the expected value over a3 inside of it is r of s3 a3 and so on and so on and we have this these nested expectations now at first it kind of seems like we just wrote a very concise expected value of trajectories as a really really messy set of nested expectations but one thing that we could think about is well
what if we had some some function that told us the uh the stuff that goes inside of the x of the second expectation what if we had some function that tells us r of s1 plus comma a1 plus the expected value over s2 plus etc etc etc so what if we we knew this part so let's uh define a a symbol for this let's say that q of s1 comma a1 is equal to r of s1 comma a1 plus the expectation over s2 of the expectation over a2 of r of s28 to etcetera so basically
just this middle part the part that goes inside the second set of square brackets i'm just going to call that q of s1 comma a1 then we can write our original rl objective as simply the expected value over s1 of the expected value over a1 of q of s1 comma a1 so it's just a little bit of symbolic manipulation a little bit of definition but the important point about this definition is that if you knew q of s1 comma a1 then optimizing the policy at the first time step would be very easy so if you
had access to a queue of s1 comma a1 and you needed to select the policy pi of a1 given s1 you would just select the policy for which this expected value is largest you could simply test every action and just assign 100 probability to the best one one with the largest value for q so this basic idea can be extended uh to a more general concept uh so this is this is the simple rule that i said you know a simple way to get pi here is just assign a probability of one to the arc
max so the the more general principle is what we're going to call the q function so the q function can be defined at other time steps not just time step one and the definition is this q pi of st comma a t and i say q pi because it depends on pi q pi of st comma 80 is equal to the sum over all time steps from t until the end capital t of the expected value of the reward at that future time step condition on starting an st comma 18. so what that means is
basically if you start an sd common a t and then f and then roll out your policy for the rest of time will be the expected sum of rewards a closely related quantity that we can also define is something called the value function the value function is defined in much the same way only it's conditioned only a state rather than a state in action so the value function says if you start in state st and then roll out your policy what will be your expected total value and the value function can also be written as
the expected value over actions of the q function right because if the q function tells you they expect the total reward if you start an st comma a t then taking the expectation of that with respect to a t will give you the expected total reward if you start an st so now one observation we could make is the expectation of the value function at state s1 is the entirety of the reinforcement learning objective for the same reason that the expected value with respect to s 1 a a1 of qs1a1 was the rl objective on
the previous slide okay so at this point i would like everyone to pause for a minute and think about these definitions of q functions and value functions you might want to flip back to the previous slide if something here is unclear take a moment to think about that and if something about these definitions is unclear please make sure to write a question in the comments all right let's continue so what are q functions and value functions good for well i provided some intuition for this a couple slides ago when i talked about how once you
have a q function for at least the first time step you can recover a better policy for the first time step so one idea is that if we have a policy pi and if we can figure out its full q function q pi s comma a then we can improve pi for example we can pick a new policy pi prime that assigns a probability of 1 to a given action if that action is the r max of q pi s a and we can do this on not just the first time step but on all
of the time steps and in fact we can show that this policy is at least as good as pi and probably better don't worry if this is not if it's not obvious to you right now why this is true we'll cover this in much more detail later but this is the basis of a class of methods called policy iteration algorithms which themselves can be used to derive q-learning algorithms and crucially it doesn't matter what pi is you can always improve it in this way another idea which we will use in the next lecture when we
talk about policy gradients is you can use this to compute a gradient to increase the probability of a good action a so the intuition is that if q pi s a is larger than v of s then a is better than average because remember that the v pi of s is just the expected value of q pi s a under pi of a given s by this definition v pi of s is how you will do on average when you use your policy from state s so if you can do better than average if you
can choose an action a so that q pi s a is larger than v pi of s then you will do better you'll do better than average under your old policy so one thing you could do is you could modify pi of a given s to increase the probability of actions whose value under the q function is larger than the value at that state and you can actually use this to get a gradient based update rule on pi these ideas are very important in rl and we'll revisit them again and again in the next few
lectures when we talk about model free reinforcement learning algorithms all right so in the anatomy of the reinforcement learning algorithm the green box is typically where you would use uh or where you would learn q functions or value functions so q functions and value functions fundamentally are objects that evaluate how good your policy currently is so you would typically fit them or learn them in the green box and then use them in the blue box to improve the policy
