Reading Kaelbling et al 1996 see class website Reinforcement Learning Machine Learning 10701 15781 Carlos Guestrin Carnegie Mellon University May 3rd 2006 1 Announcements Project Poster session Friday May 5th 2 5pm NSH Atrium please arrive a little early to set up posterboards easels and pins provided class divided into two shift so you can see other posters FCEs Please please please please please please give us your feedback it helps us improve the class http www cmu edu fce 2 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 3 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 4 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 5 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 6 Brafman Tennenholtz 2002 see class website Rmax A modelbased approach 7 Given a dataset learn model Given data learn MDP Representation Dataset Learn reward function R x a Learn transition model P x x a 8 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 9 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 10 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 11 Understanding Rmax With Rmax you either explore visit a state action pair you don t know much about because it seems to have lots of potential exploit spend all your time on known states even if unknown states were amazingly good it s not worth it Note you never know if you are exploring or exploiting 12 Implicit Exploration Exploitation Lemma Lemma every T time steps either Exploits achieves near optimal reward for these T steps or Explores with high probability the agent visits an unknown state action pair learns a little about an unknown state T is related to mixing time of Markov chain defined by MDP time it takes to approximately forget where you started 13 The Rmax algorithm Initialization Add state x0 to MDP R x a Rmax x a P x0 x a 1 x a all states except for x0 are unknown Repeat obtain policy for current MDP and Execute policy for any visited state action pair set reward function to appropriate value if visited some state action pair x a enough times to estimate P x x a update transition probs P x x a for x a using MLE recompute policy 14 Visit enough times to estimate P x x a How many times are enough use Chernoff Bound Chernoff Bound X1 Xn are i i d Bernoulli trials with prob P 1 n i Xi exp 2n 2 15 Putting it all together Theorem With prob at least 1 Rmax will reach a optimal policy in time polynomial in num states num actions T 1 1 Every T steps achieve near optimal reward great or visit an unknown state action pair num states and actions is finite so can t take too long before all states are known 16 Problems with model based approach If state space is large transition matrix is very large requires many visits to declare a state as know Hard to do approximate learning with large state spaces some options exist though 17 TD Learning and Q learning Modelfree approaches 18 Value of Policy Expected longterm reward starting from x Value V x Start from x0 x0 R x0 V x0 E R x0 R x1 2 R x2 3 R x3 4 R x4 L x0 x1 x1 R x1 x1 R x1 x1 x1 x1 R x1 Future rewards discounted by 0 1 x2 R x2 x2 x3 R x3 x3 x4 R x4 19 A simple monte carlo policy evaluation Estimate V x start several trajectories from x V x is average reward from these trajectories Hoeffding s inequality tells you how many you need discounted reward don t have to run each trajectory forever to get reward estimate 20 Problems with monte carlo approach Resets assumes you can restart process from same state many times Wasteful same trajectory can be used to estimate many states 21 Reusing trajectories Value determination Expressed as an expectation over next states Initialize value function zeros at random Idea 1 Observe a transition xt xt 1 rt 1 approximate expec with single sample unbiased but a very bad estimate 22 Simple fix Temporal Difference TD Learning Sutton 84 Idea 2 Observe a transition xt xt 1 rt 1 approximate expectation by mixture of new sample with old estimate 0 is learning rate 23 …
View Full Document
Unlocking...