Markov Decision Processes MDPs Machine Learning 10701 15781 Carlos Guestrin Carnegie Mellon University May 2nd 2007 2005 2007 Carlos Guestrin 1 Joint Decision Space 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 2 2005 2007 Carlos Guestrin 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 3 2005 2007 Carlos Guestrin Computing the value of a policy V x0 E R x0 R x1 2 R x2 3 R x3 4 R x4 L Discounted value of a state value of starting from x0 and continuing with policy from then on A recursion 4 2005 2007 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 Policy iteration Howard 60 Bellman 57 Value iteration Bellman 57 Linear programming Manne 60 2005 2007 Carlos Guestrin 5 Value iteration a k a dynamic programming the simplest of all V x max R x a P x x a V x a x Start with some guess V0 Iteratively say Vt 1 x max R x a P x x a Vt x a x Stop when Vt 1 Vt 1 means that V Vt 1 1 1 6 2005 2007 Carlos Guestrin Policy iteration Another approach for computing Start with some guess for a policy 0 Iteratively say evaluate policy Vt x R x a t x P x x a t x Vt x x improve policy t 1 x max R x a P x x a Vt x a x Stop when policy stops changing usually happens in about 10 iterations or Vt 1 Vt 1 means that V Vt 1 1 1 7 2005 2007 Carlos Guestrin Policy Iteration Value Iteration Which is best It depends Lots of actions Choose Policy Iteration Already got a fair policy Policy Iteration Few actions acyclic Value Iteration Best of Both Worlds Modified Policy Iteration Puterman a simple mix of value iteration and policy iteration 3rd Approach Linear Programming 8 2005 2007 Carlos Guestrin LP Solution to MDP Manne 60 Value computed by linear programming minimize V x x V x R x a P x x a V x subject to x x a One variable V x for each state One constraint for each state x and action a Polynomial time solution 9 2005 2007 Carlos Guestrin 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 10 2005 2007 Carlos Guestrin Reinforcement Learning Machine Learning 10701 15781 Carlos Guestrin Carnegie Mellon University May 2nd 2007 2005 2007 Carlos Guestrin 11 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 12 2005 2007 Carlos Guestrin 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 time step t world gives state xt and reward rt you give next action at Goal quickly learn policy that approximately maximizes long term expected discounted reward 13 2005 2007 Carlos Guestrin The Credit Assignment Problem I m in state 43 reward 0 action 2 39 0 4 22 0 1 21 0 1 21 0 1 13 0 2 54 0 2 26 100 Yippee I got to a state with a big reward But which of my actions along the way actually helped me get there This is the Credit Assignment problem 14 2005 2007 Carlos Guestrin Exploration Exploitation tradeoff You have visited part of the state space and found a reward of 100 is this the best I can hope for Exploitation should I stick with what I know and find a good policy w r t this knowledge at the risk of missing out on some large reward somewhere Exploration should I look for a region with more reward at the risk of wasting my time or collecting a lot of negative reward 2005 2007 Carlos Guestrin 15 Two main reinforcement learning approaches Model based approaches explore environment learn model P x x a and R x a almost everywhere use model to plan policy MDP style approach leads to strongest theoretical results works quite well in practice when state space is manageable Model free approach don t learn a model learn value function or policy directly leads to weaker theoretical results often works well when state space is large 16 2005 2007 Carlos Guestrin Rmax A modelbased approach 2005 2007 Carlos Guestrin 17 Given a dataset learn model Given data learn MDP Representation Dataset Learn reward function R x a Learn transition model P x x a 18 2005 2007 Carlos Guestrin Some challenges in model based RL 1 Planning with insufficient information Model based approach estimate R x a P x x a obtain policy by value or policy iteration or linear programming No credit assignment problem learning model planning algorithm takes care of assigning credit What do you plug in when you don t have enough information about a state don t reward at a particular state plug in smallest reward Rmin plug in largest reward Rmax don t know a particular transition probability 19 2005 2007 Carlos Guestrin Some challenges in model based RL 2 Exploration Exploitation tradeoff A state may be very hard to reach waste a lot of time trying to learn rewards and transitions for this state after a much effort state may be useless A strong advantage of a model based approach you know which states estimate for rewards and transitions are bad can try to plan to reach these states have a good estimate of how long it takes to get there 20 2005 2007 Carlos Guestrin A surprisingly simple approach for model based RL The Rmax algorithm Brafman Tennenholtz Optimism in the face of uncertainty heuristic shown to be useful long before theory was done e g Kaelbling 90 If you don t know reward for a particular state action pair set it to Rmax If you don t know the transition probabilities P x x a from some some state action pair x a assume you go to a magic fairytale new state x0 R x0 a Rmax P x0 x0 a 1 21 2005 …
View Full Document
Unlocking...