Markov Decision Process - Reinforcement Learning Chapter 3

Key Takeaways

[Music] thanks for watching Henry AI Labs this video will cover finite Markov decision processes in the context of our book introduction to reinforce and learning by Richard Sutton and Andrew Bartow this is chapter three of that book and this is a part of a video series going chapter by chapter through this book explaining some of the key concepts and ideas a link to a free pdf version of this book is in the description as well as a print version available for purchase the key concepts of this chapter are seeing how reinforcement learning problems fit into this Markov decision process framework pictured here and understanding the Markov property how we have these well-defined transition probabilities in our MDP the idea of discounting future rewards how you would manage an episode ik task compared to a continuing task and then this idea of solving for the optimal policies you know the optimal decision making framework and the optimal value functions using these bellman optimality equations so this is the Markov decision process given here as a recycling robot so we've seen this diagram of the aging environment interface where the agent sends an action to the environment and gets back a state in a reward well in this case compared to the chapter 2 where we looked at contextual bandits and K armed bandits with no context we're now looking to see how the state transitions as a function of the action we take so in the recycling robot example the robot has two states high battery charge and low battery charge and they can make these decisions to either wait where it won't deplete his battery or it can go search for garbage where it runs this risk with the transition probability 1 minus alpha of going from the state high battery to low battery and if it chooses to search with low battery it has this probability transition probability of 1 minus beta of depleting the battery all the way and going to having a reward of minus 3 for doing that one of the key components to this Markov decision process is the markov property so what the Markov property is is it basically says the all the information that you need to predict the future is contained in the current state representation so using conditional probabilities shown here we can summarize the Markov property is saying that the probability of the reward given the state at this time step say T is equal to the probability of the reward given the current state the previous state and then all the previous states that have ever existed in time so basically does just summarize it the Markov property says that all the information you need is given in the car so in the example of our recycling robot it doesn't matter when the robot is in the high battery charge state it doesn't matter whether it just came from high or if it just just came from low and has just recharged or if it has just come from waiting all the matters is the current state to predict the future another key of Markov decision processes are this is this dynamics function P so the dynamics function is basically telling you how the environment is transitioning with respect to the different actions you take as well as the rewards you can expect to get as it's transitioning from state to state with respect to the action taken so from the for argument dynamics function which is get the next state and the reward given the current state in the action taken you can also derive other things you might want to know about the Markov decision process such as the next state probability given the state action pair the reward for a state in action and the reward for a state action next state to ball the dynamics function of a Markov decision process is probably better explained to the use of a concrete example like the recycling robot so in this case we're looking at a table of state action and next States and the probability of going into this next state given a state action pair and the reward achieved by this state action next state tuple so the first entry of being in the current state hi and taking the action search corresponds to this path on the Markov decision process illustration so we're in the current state of having a high battery charge and we just decided to go search for trash so if we find the trash we received this reward our search in both cases but we also have this probability of transitioning from the high battery charge to the low battery charge with this 1 minus alpha parameter or essentially staying in the next state of high with this alpha parameter now that we have an understanding of the transition probabilities of going from one state to the next with respect to the actions we take in the state we're currently in now we'll formally define our idea of expected reward or return denoted G sub T so as we've seen in many of the reinforce and learning cases we constantly receive a reward from the environment at every time step so the return of the expected reward in total is the summation of these rewards we achieved at each time step so in this case if we have an episode with T time steps it's just a summation of all the rewards up to time step T so there are two different kinds of tasks that we're going to formally define an distinguish from each other and that's episode ik and doing tasks and we'll use the carpool balancing example to show how you might structure carpool balancing is an episode task or a continuing task so if you've messed around at the open AI gym this is an episode ik implementation of the carpool balancing problem basically you get a +1 reward for every time step the pole is balanced and when the pole tips over the episode is ended and then it just restarts back to the middle and this is how the open a IDM allows you to interface with carpool balancing but another way of doing it might be to have a continuing task where the reward is zero all the time and then minus one when it tips over so we'll use this idea of discounting in order to reward the agent for keeping the the pole balanced for many time steps so this is done with this gamma discount factor so we've seen this idea of return G sub T as being the summation of rewards over a series of time steps so now we're going to trade off immediate and future reward through the use of this gamma parameter so basically if you imagine the game parameter is closer to 1 like 0.9 then a 0.9 squared is 0.8 1 I think it's not so discounted but say the gamma is 0.5 then gamma squared is already 0.25 so you see how gamma gets closer to 0 the future rewards matter less and less to the overall return of the agent so then one key idea with this new notation of introducing discounting is that we can factor out the gamma from a sequence of rewards at different time steps using this notation to have our return is equal to the reward at the next time step plus the discount factor times the expected return at that next time step and this consistency condition of G sub T equals R sub T plus 1 plus gamma times G sub T plus 1 is the key idea to the bellman equations which are one of the hugest most important ideas in this chapter in addition to discounting rewards we can unify episodic and continuing tasks by using an absorbing state in our Markov decision process so with this gray box represents is converting an episodic task into a continuing task by just having the end of the episode loop in Italy and receive zero rewarded every time stuff so now that we have this idea of our discount of return and our transition probabilities we can solve for the optimal value functions and policies using this idea of the bellman optimality equations so the bellman equations are basically this idea of breaking our current expected reward G sub T into the reward at the next time step plus the discount factor times the expected return from that state so this is probably the key idea here to development equations is basically you're computing the expected value of this state as a function of all the next states that it can transition into so it's an idea derived from dynamic programming of you know shortcutting the equations needed by just using this one step look-ahead so that's why we see things like the back-up diagram for the value function of this policy PI at state s is just given based on the next states it might achieve with respect to the different actions that can take so all these details of the equation show is just the policy meaning the action it takes given the state and the summation of the next states basically the probability distribution over the next states and rewards given this state action pair and then we have our reward of that step plus the discount factor times the expectation of our future rewards from this new state s Prime now we'll look at a concrete example to show how the bellman equations can be used to find the value of every state given a certain policy so in this case our policy or our mapping from States to actions is random meaning that we're choosing up right down left all with the same probability of 0.25 shown here in the calculation so what the bellman equation will do is will solve for the expected return of a state in this case we're gonna look at how it derives 2.3 for this state as a function of the reward for that state plus the discount factor times the expected return of all these subsequent states that it might go to and then the probabilities of it going to that state so when we're in this middle state we received zero reward we only receive reward when we're on a transitioning into a prime or B transitioning into B prime or if we fall off of the map we receive a negative reward so from here we look ahead to our subsequent states we can either go here here here or here so from these different states all with the same probability 0.25 of transitioning into this probability we have this summation which is our G sub T plus 1 and then we multiply it by a 0.9 gamma discount factor and then we add it to the reward at this state and this gives us our estimate of 2.3 of for this state or the value of this state using the bellman equations looking ahead one step to these subsequent states and using those to evaluate the state at the current step in the grid world example we're looking at the estimating the values of each state and then with respect to these different actions of moving up right down or left but it's also helpful to have an understanding of the difference between value functions and then state action functions so in the example of the golf problem we have the value function if all the action we take is two-putt we have this kind of contour map of our expected rewards at each location of the map compared to if we have this action of using the driver we see a different kind of contour map where in this case it's better to use the putter but we're still using the driver compared to the putter so this golf example is really just good to get a concrete example of difference between value functions and then how adding different actions can change this with the state action functions or the cue functions so we've seen how the bellman equation can be used to compute the values of states as a function of the successor States but now we're gonna look at the bellman optimality equation which is a way of solving for the optimal values of the of the states in the in the environment and this is denoted V sub star as city bus 1 or V sub star of s so basically what this is is taking the max a or meaning taking the action which is the you know has the best reward at each of the states in order to maximize our reward so from the state where we have a high battery charge we either take the actions of waiting or searching and that's given right here in the V star of H or the optimal value function estimate of H as the maximum reward with the actions that it can take so the way this top line of the argument is defined is this is the reward given by searching plus the gamma times the discount factor times the expect reward for the next state might be so for example we have the alpha probability of returning back to this high state so then we're back in the same H state and we have our value estimate of that state but then we also have the 1 minus alpha probability of going into this low battery charge state so we have our value estimate of that state and then Contra Darrell e we have the weight decision or the action where we receive this reward our subway and then we have plus the gamma times the expected return for the new state that we're in which in this case is always going to be returning us to the state of high battery using the bellman optimality equations leaves us with this system of equations that we can use to solve for the optimal values at each state so once we have this table of the optimal values at each state it's easy to construct a policy an optimal policy which is basically just taking the greedy decision to move into the state with the highest value so for example if you're in this state you 19.8 of the value estimate you would move either upper left to the higher value state at 22.0 so with nearly all interesting problems it's actually computationally intractable to explicitly solve the system of equations like this so in our recycling robot case we only have two states so we can and only get three actions in low battery state and then two actions in the high battery state so it's not that complex to construct this system of equations for the bellmen optimality equations but if we have games like backgammon with 10 to the 20 states we can't just explicitly solve for the optimal values to take in every state thanks for watching this explanation of finite Markov decision processes chapter 3 in our book an introduction reinforced learning by Richard Sutton and Andrew Bartow please subscribe to stay tuned to the series as we follow along with chapters 4 through 17 and please subscribe to Henry AI labs for more deep learning and artificial intelligence videos