Machine Learning 10 601 Fall 2013 Reinforcement Learning Eric Xing Lecture 24 December 2 2013 3 1 2 1 1 start 1 2 3 4 Reading See class webpage Eric Xing CMU 2013 1 What is Learning Learning takes place as a result of interaction between an agent and the world the idea behind learning is that Percepts received by an agent should be used not only for understanding interpreting prediction as in the machine learning tasks we have addressed so far but also for acting and further more for improving the agent s ability to behave optimally in the future to achieve the goal Eric Xing CMU 2013 2 Types of Learning Supervised Learning A situation in which sample input output pairs of the function to be learned can be perceived or are given You can think it as if there is a kind teacher Training data X Y features label Predict Y minimizing some loss Regression Classification Unsupervised Learning Training data X features only Find similar points in high dim X space Clustering Eric Xing CMU 2013 3 Example of Supervised Learning Predict the price of a stock in 6 months from now based on economic data Regression Predict whether a patient hospitalized due to a heart attack will have a second heart attack The prediction is to be based on demographic diet and clinical measurements for that patient Logistic Regression Identify the numbers in a handwritten ZIP code from a digitized image pixels Classification Eric Xing CMU 2013 4 Example of Unsupervised Learning From the DNA micro array data determine which genes are most similar in terms of their expression profiles Clustering Eric Xing CMU 2013 5 Types of Learning Cont d Reinforcement Learning in the case of the agent acts on its environment it receives some evaluation of its action reinforcement but is not told of which action is the correct one to achieve its goal Imagine learning to go back to GHC from this room Training data S A R State Action Reward Develop an optimal policy sequence of decision rules for the learner so as to maximize its long term reward Robotics Board game playing programs Eric Xing CMU 2013 6 RL is learning from interaction Eric Xing CMU 2013 7 How to train this pilot Eric Xing CMU 2013 8 Examples of Reinforcement Learning How should a robot behave so as to optimize its performance Robotics How to automate the motion of a helicopter Control Theory How to make a good chess playing program Artificial Intelligence Eric Xing CMU 2013 9 Pole Balancing Task Move car left right to keep the pole balanced State representation Position and velocity of the car Angle and angular velocity of the pole Eric Xing CMU 2013 10 Robot in a room what s the strategy to achieve max reward what if the actions were NOT deterministic Eric Xing CMU 2013 11 History of Reinforcement Learning Roots in the psychology of animal learning Thorndike 1911 Another independent thread was the problem of optimal control and its solution using dynamic programming Bellman 1957 Idea of temporal difference learning on line method e g playing board games Samuel 1959 A major breakthrough was the discovery of Q learning Watkins 1989 Eric Xing CMU 2013 12 What is special about RL RL is learning how to map states to actions so as to maximize a numerical reward over time Unlike other forms of learning it is a multistage decisionmaking process often Markovian An RL agent must learn by trial and error Not entirely supervised but interactive Actions may affect not only the immediate reward but also subsequent rewards Delayed effect Eric Xing CMU 2013 13 Elements of RL A policy A map from state space to action space May be stochastic A reward function It maps each state or state action pair to a real number called reward A value function Value of a state or state action pair is the total expected reward starting from that state or state action pair Eric Xing CMU 2013 14 Policy Eric Xing CMU 2013 15 Reward for each step 2 Eric Xing CMU 2013 16 Reward for each step 0 1 Eric Xing CMU 2013 17 Reward for each step 0 04 Eric Xing CMU 2013 18 The Precise Goal To find a policy that maximizes the Value function transitions and rewards usually not available There are different approaches to achieve this goal in various situations Value iteration and Policy iteration are two more classic approaches to this problem But essentially both are dynamic programming Q learning is a more recent approaches to this problem Essentially it is a temporal difference method Eric Xing CMU 2013 19 Markov Decision Processes A Markov decision process is a tuple Eric Xing CMU 2013 where 20 The dynamics of an MDP We start in some state s0 and get to choose some action a0 A As a result of our choice the state of the MDP randomly transitions to some successor state s1 drawn according to s1 Ps0a0 Then we get to pick another action a1 Eric Xing CMU 2013 21 The dynamics of an MDP Cont d Upon visiting the sequence of states s0 s1 with actions a0 a1 our total payoff is given by Or when we are writing rewards as a function of the states only this becomes For most of our development we will use the simpler state rewards R s though the generalization to state action rewards R s a offers no special diffculties Our goal in reinforcement learning is to choose actions over time so as to maximize the expected value of the total payoff Eric Xing CMU 2013 22 Policy A policy is any function to the actions We say that we are executing some policy if whenever we are in state s we take action a s mapping from the states We also define the value function for a policy according to V s is simply the expected sum of discounted rewards upon starting in state s and taking actions according to Eric Xing CMU 2013 23 Value Function Given a fixed policy its value function V satisfies the Bellman equations Immediate reward expected sum of future discounted rewards Bellman s equations can be used to efficiently solve for V see later Eric Xing CMU 2013 24 The Grid world M 0 8 in direction you want to go 0 1 left 0 2 in perpendicular 0 1 right Policy mapping from states to actions An optimal policy for the stochastic environmen t utilities of states 3 1 3 0 812 2 1 2 0 762 1 0 705 1 1 1 Environment 2 3 4 0 868 0 912 1 0 660 1 0 655 0 611 0 388 2 3 4 Observable accessible percept identifies the state Partially observable Markov property Transition probabilities depend on state only not on the path to the state Markov decision problem MDP Partially observable MDP POMDP percepts does not have enough info to identify transition probabilities