1 Tom Mitchell, April 2011 Machine Learning 10-701 Tom M. Mitchell Machine Learning Department Carnegie Mellon University April 26, 2011 Today: • Learning of control policies • Markov Decision Processes • Temporal difference learning • Q learning Readings: • Mitchell, chapter 13 • Kaelbling, et al., Reinforcement Learning: A Survey Thanks to Aarti Singh for several slides Tom Mitchell, April 2011 Reinforcement Learning [Sutton and Barto 1981; Samuel 1957; ...]2 Tom Mitchell, April 2011 Reinforcement Learning: Backgammon [Tessauro, 1995] Learning task: • chose move at arbitrary board states Training signal: • final win or loss Training: • played 300,000 games against itself Algorithm: • reinforcement learning + neural network Result: • World-class Backgammon player Tom Mitchell, April 2011 Outline • Learning control strategies – Credit assignment and delayed reward – Discounted rewards • Markov Decision Processes – Solving a known MDP • Online learning of control strategies – When next-state function is known: value function V*(s) – When next-state function unknown: learning Q*(s,a) • Role in modeling reward learning in animals3 Tom Mitchell, April 2011 Tom Mitchell, April 2011 • Set of states S • Set of actions A • At each time, agent observes state st ∈ S, then chooses action at ∈ A • Then receives reward rt , and state changes to st+1 • Markov assumption: P(st+1 | st, at, st-1, at-1, ...) = P(st+1 | st, at) • Also assume reward Markov: P(rt | st, at, st-1, at-1,...) = P(rt | st, at) • The task: learn a policy π: S A for choosing actions that maximizes for every possible starting state s0 Markov Decision Process = Reinforcement Learning Setting4 Tom Mitchell, April 2011 HMM, Markov Process, Markov Decision Process Tom Mitchell, April 2011 HMM, Markov Process, Markov Decision Process5 Tom Mitchell, April 2011 Reinforcement Learning Task for Autonomous Agent Execute actions in environment, observe results, and • Learn control policy π: SA that maximizes from every state s ∈ S Example: Robot grid world, deterministic reward r(s,a) Tom Mitchell, April 2011 Reinforcement Learning Task for Autonomous Agent Execute actions in environment, observe results, and • Learn control policy π: SA that maximizes from every state s ∈ S Yikes!! • Function to be learned is π: SA • But training examples are not of the form <s, a> • They are instead of the form < <s,a>, r >6 Tom Mitchell, April 2011 Value Function for each Policy • Given a policy π : S A, define • Then we want the optimal policy π* where • For any MDP, such a policy exists! • We’ll abbreviate Vπ *(s) as V*(s) • Note if we have V*(s) and P(st+1|st,a), we can compute π*(s) assuming action sequence chosen according to π, starting at state s#Tom Mitchell, April 2011 Value Function – what are the Vπ(s) values?7 Tom Mitchell, April 2011 Value Function – what are the V*(s) values? Tom Mitchell, April 2011 Immediate rewards r(s,a) State values V*(s)8 Tom Mitchell, April 2011 Recursive definition for V*(S) assuming actions are chosen according to the optimal policy, π*#Tom Mitchell, April 2011 Value Iteration for learning V* : assumes P(St+1|St, A) known Initialize V(s) arbitrarily Loop until policy good enough Loop for s in S Loop for a in A • End loop End loop V(s) converges to V*(s) Dynamic programming9 Tom Mitchell, April 2011 Value Iteration Interestingly, value iteration works even if we randomly traverse the environment instead of looping through each state and action methodically • but we must still visit each state infinitely often on an infinite run • For details: [Bertsekas 1989] • Implications: online learning as agent randomly roams If max (over states) difference between two successive value function estimates is less than ε, then the value of the greedy policy differs from the optimal policy by no more than Tom Mitchell, April 2011 So far: learning optimal policy when we know P(st | st-1, at-1) What if we don’t?10 Tom Mitchell, April 2011 Q learning Define new function, closely related to V* If agent knows Q(s,a), it can choose optimal action without knowing P(st+1|st,a) ! And, it can learn Q without knowing P(st+1|st,a) Tom Mitchell, April 2011 Immediate rewards r(s,a) State values V*(s) State-action values Q*(s,a) Bellman equation. Consider first the case where P(s’| s,a) is deterministic11 Tom Mitchell, April 2011 Tom Mitchell, April 201112 Tom Mitchell, April 2011 Tom Mitchell, April 2011 Use general fact:13 Tom Mitchell, April 2011 Tom Mitchell, April 201114 Tom Mitchell, April 2011 Tom Mitchell, April 2011 • Learning to choose optimal actions A • From delayed reward • By learning evaluation functions like V(S), Q(S,A) Key ideas: • If next state function St x At St+1 is known – can use dynamic programming to learn V(S) – once learned, choose action At that maximizes V(St+1) • If next state function St x At St+1 unknown – learn Q(St,At) = E[V(St+1)] – to learn, sample St x At St+1 in actual world – once learned, choose action At that maximizes Q(St,At) MDP’s and RL: What You Should Know15 Tom Mitchell, April 2011 MDPs and Reinforcement Learning: Further Issues • What strategy for choosing actions will optimize – learning rate? (explore uninvestigated states) – obtained reward? (exploit what you know so far) • Partially observable Markov Decision Processes – state is not fully observable – maintain probability distribution over possible states you’re in • Convergence guarantee with function approximators? – our proof assumed a tabular representation for Q, V – some types of function approximators still converge (e.g., nearest neighbor) [Gordon, 1999] • Correspondence to human
View Full Document
Unlocking...