Markov Decision Processes MDPs Machine Learning 10701 15781 Carlos Guestrin Carnegie Mellon University December 2nd 2009 2005 2009 Carlos Guestrin 1 Markov Decision Process MDP Representation State space Action space Joint state x of entire system Joint action a a1 an for all agents Reward function Total reward R x a sometimes reward can depend on action Transition model Dynamics of the entire system P x x a 2005 2009 Carlos Guestrin 2 1 Discount Factors People in economics and probabilistic decision making do this all the time The Discounted sum of future rewards using discount factor is reward now reward in 1 time step 2 reward in 2 time steps 3 reward in 3 time steps infinite sum 3 2005 2009 Carlos Guestrin The Academic Life 0 6 0 6 0 2 B Assoc Prof 60 A Assistant Prof 20 0 2 S On the Street 10 0 2 0 2 0 7 T Tenured Prof 400 D Dead 0 0 3 Define 0 7 0 3 VA Expected discounted future rewards starting in state A VB Expected discounted future rewards starting in state B VT T S VS VD D How do we compute VA VB VT VS VD 2005 2009 Carlos Guestrin 4 2 Policy At state x action a for all agents Policy x a x0 x0 both peasants get wood x1 x1 one peasant builds barrack other gets gold x2 x2 peasants get gold footmen attack 5 2005 2009 Carlos Guestrin Value of Policy Expected longterm reward starting from x Value V x V x0 E R x0 R x1 2 R x2 3 R x3 4 R x4 Start from x0 x0 x0 x1 R x0 R x1 x1 Future rewards discounted by 2 0 1 x1 x1 x2 x2 R x2 x3 R x1 x1 R x1 2005 2009 Carlos Guestrin x1 x3 x4 R x3 6 R x4 3 Computing the value of a policy V x0 E R x0 R x1 2 R x2 3 R x3 4 R x4 Discounted value of a state value of starting from x0 and continuing with policy from then on A recursion 2005 2009 Carlos Guestrin 7 Simple approach for computing the value of a policy Iteratively Can solve using a simple convergent iterative approach a k a dynamic programming Start with some guess V0 Iteratively say Stop when Vt 1 Vt means that V Vt 1 1 2005 2009 Carlos Guestrin 8 4 But we want to learn a Policy So far told you how good a policy is But how can we choose the best policy At state x action a for all agents Policy x a x0 x0 both peasants get wood x1 Suppose there was only one time step x1 one peasant builds barrack other gets gold x2 x2 peasants get gold footmen attack world is about to end select action that maximizes reward 2005 2009 Carlos Guestrin 9 Unrolling the recursion Choose actions that lead to best value in the long run Optimal value policy achieves optimal value V 2005 2009 Carlos Guestrin 10 5 Bellman equation Evaluating policy Computing the optimal value V Bellman equation V x max R x a P x x a V x a x 11 2005 2009 Carlos Guestrin Optimal Long term Plan Optimal value function V x Optimal Policy x Optimal policy x argmax R x a P x x a V x a 2005 2009 Carlos Guestrin x 12 6 Interesting fact Unique value V x max R x a P x x a V x a Slightly surprising fact There is only one V that solves Bellman equation x there may be many optimal policies that achieve V Surprising fact optimal policies are good everywhere 13 2005 2009 Carlos Guestrin Solving an MDP Solve Bellman equation Optimal value V x Optimal policy x V x max R x a P x x a V x a x Bellman equation is non linear Many algorithms solve the Bellman equations 2005 2009 Carlos Guestrin Policy iteration Howard 60 Bellman 57 Value iteration Bellman 57 Linear programming Manne 60 14 7 Value iteration a k a dynamic programming the simplest of all Start with some guess V0 Iteratively say Stop when Vt 1 Vt means that V Vt 1 1 15 2005 2009 Carlos Guestrin A simple example 0 9 1 You run a startup company In every state you must choose between Saving money or Advertising 2005 2009 Carlos Guestrin S 1 Poor Unknown 0 Poor Famous 0 1 2 A 1 2 1 2 1 2 1 2 S 1 2 1 2 1 2 Rich Unknown 10 1 2 S 1 2 A 1 Rich Famous 10 16 8 Let s compute Vt x for our example 0 9 1 S Poor Unknown 0 1 Poor Famous 0 1 2 A 1 2 1 2 1 2 1 Rich Unknown 10 S 1 2 1 2 Vt PU Vt PF Vt RU Vt RF 2 3 1 2 1 2 t 1 S 1 2 1 2 A Rich Famous 10 4 5 6 Vt 1 x max R x a P x x a Vt x a x 17 2005 2009 Carlos Guestrin Let s compute Vt x for our example 0 9 1 S Poor Unknown 0 1 Poor Famous 0 1 2 A 1 2 1 2 1 2 1 2 A S 1 2 1 1 2 1 2 Rich Unknown 10 S 1 2 1 2 Rich Famous 10 t Vt PU Vt PF Vt RU Vt RF 1 2 3 4 5 6 0 0 2 03 3 852 7 22 10 03 0 4 5 6 53 12 20 15 07 17 65 10 14 5 25 08 29 63 32 00 33 58 10 19 18 55 19 26 20 40 22 43 Vt 1 x max R x a P x x a Vt x a 2005 2009 Carlos Guestrin x 18 9 What you need to know What s a Markov decision process state actions transitions rewards a policy value function for a policy computing V Optimal value function and optimal policy Bellman equation Solving Bellman equation with value iteration policy iteration and linear programming 2005 2009 Carlos Guestrin 19 Acknowledgment This lecture contains some material from Andrew Moore s excellent collection of ML tutorials http www cs cmu edu awm tutorials 2005 2009 Carlos Guestrin 20 10 Reinforcement Learning Machine Learning 10701 15781 Carlos Guestrin Carnegie Mellon University November 29th 2007 2005 2009 Carlos Guestrin 21 The Reinforcement Learning task World You are in state 34 Your immediate reward is 3 You have possible 3 actions Robot World I ll take action 2 You are in state 77 Your immediate reward is 7 You have possible 2 actions Robot World I ll take action 1 You re in state 34 again Your immediate reward is 3 You have possible 3 actions 2005 2009 Carlos Guestrin 22 11 Formalizing the online reinforcement learning problem Given a set of states X and actions A in some versions of the problem size of X and A unknown Interact with world at each …
View Full Document
Unlocking...