Transcription of Bonus Lecture: Introduction to Reinforcement Learning
1 Bonus lecture : Introduction to Reinforcement Learning Garima Lalwani, Karan Ganju and Unnat Jain Credits: These slides and images are borrowed from slides by David Silver and Peter Abbeel Outline 1 RL Problem Formulation 2 Model-based Prediction and Control 3 Model-free Prediction 4 Model-free Control 5 Summary Part 1: RL Problem Formulation Characteristics of Reinforcement Learning What makes Reinforcement Learning different from other machine Learning paradigms? There is no supervisor, only a reward signal Feedback is delayed, not instantaneous Time really matters (correlated, non data). Agent's actions affect the subsequent data it receives Agent and Environment Agent Observed state action St At reward Rt Environment Rewards A reward Rt is a scalar feedback signal Indicates how well agent is doing at step t The agent's job is to maximise cumulative reward Rod Balancing Demo Learn to swing up and balance a real pole based on raw visual input data, ICNIP 2012 RL based visual control End-to-end training of deep visuomotor policies, JMLR 2016 RL based visual control Link: Source.
2 Examples of Rewards Fly stunt manoeuvres in a helicopter +ve reward for following desired trajectory ve reward for crashing Stanford autonomous helicopter Abbeel et. Al. Play many Atari games better than humans +/ ve reward for increasing/decreasing score Defeat the world champion at Go +/ ve reward for winning/losing a game Sample model of RL problem Pubbing R = -1. Project Murphy's Complete Submit Leave Pubbing project R=0 R = -1 R=0. Submit project Study Study R = +10. Group Arun's Home R = -2 Disc. R = -2 OH. Take Arun's Quiz R = +1. States Pubbing R = -1. Project Murphy's Complete Submit Leave Pubbing project R=0 R = -1 R=0.
3 Submit project Study Study R = +10. Group Arun's Home R = -2 Disc. R = -2 OH. Take Arun's Quiz R = +1. Actions Pubbing R = -1. Project Murphy's Complete Submit Leave Pubbing project R=0 R = -1 R=0. Submit project Study Study R = +10. Group Arun's Home R = -2 Disc. R = -2 OH. Take Arun's Quiz R = +1. Rewards Pubbing R = -1. Project Murphy's Complete Submit Leave Pubbing project R=0 R = -1 R=0. Submit project Study Study R = +10. Group Arun's Home R = -2 Disc. R = -2 OH. Take Arun's Quiz R = +1. Transition probabilities Pubbing R = -1. Project Murphy's Complete Submit Leave Pubbing project R=0 R = -1 R=0.
4 Submit project Study Study R = +10. Group Arun's Home R = -2 Disc. R = -2 OH. Take Arun's Quiz R = +1. Markov Decision Process A Markov decision process (MDP) is an environment in which all states are Markov. P [St+1 | St , At = a ] = P [St+1 | S1, .., S t , At = a ]. MDP. A Markov Decision Process has the following h S, A, P, R, i S is a finite set of states A is a finite set of actions P is a state transition probability matrix, a = P [S 0. Pss 0 t+1 = s | St = s, At = a]. R is a reward function, Ras = E [Rt+1 | St = s, At = a]. Major Components of an RL Agent An RL agent may include one or more of these components: Policy: agent's behaviour function Model: agent's representation of the environment Value function: how good is each state and/or action Policy A policy is the agent's behaviour It is a map from state to action, Deterministic policy: (s) = 1 for At= a Stochastic policy: (a|s) = P[At = a|St = s].
5 Actions Pubbing R = -1. Project Murphy's Complete Submit Leave Pubbing project R=0 R = -1 R=0. Submit project Study Study R = +10. Group Arun's Home R = -2 Disc. R = -2 OH. Take Arun's Quiz R = +1. Model A model predicts what the environment will do next P : Transition probabilities R : Expected rewards a 0. Pss 0 = P[St+1 = s | St = s, At = a]. Ras = E [Rt+1 | St = s, At = a]. Beyond Rewards Pubbing R = -1. Project Murphy's Complete Submit Leave Pubbing project R=0 R = -1 R=0. Submit project Study Group Study Arun's R = +10. Home R = -2 Disc. R = -2 OH. Take Arun's Quiz R = +1. Value function - Concept of Return Return Gt The return Gt is cumulative discounted reward from time-step t.
6 X. Gt = Rt+1 + Rt+2 + .. = k Rt+k+1. k=0. The discount [0, 1] is the present value of future rewards This values immediate reward above delayed reward. Avoids in nite returns in cyclic Markov processes Value Function State Value Function v (s). v (s) = E [Gt | St = s]. v (s) of an MDP is the expected return starting from state s, and then following policy . Action Value Function q (s,a). q (s, a) = E [Gt | St = s, At = a]. q (s, a) is the expected return starting from state s, taking action a, and then following policy . Subproblems in RL. Model based Model free Prediction: evaluate the future Given a policy Control: optimise the future Find the best policy Part 2: Model-based Prediction and Control Connecting v(s) and q(s,a): Bellman equations v (s) !
7 7 s v in terms of q : X. (a|s)q (s, a) v (s) = (a|s)q (s, a). a A. q (s, a) !7 a (a1|s )q (s , a) (an|s )q (s , a). q (s, a) !7 s, a q in terms of v : a 0 a 0. X. r P ss0 v (s ) q (s, a) = Ras + Pss0 v (s ). s 0 S. v (s0 ) !7 s0. Connecting v(s) and q(s,a): Bellman equations (2). v (s) !7 s v in terms of other v : ! X X a 0. a v (s) = (a|s) Rsa+ Pss0 v (s ). r a A s0 S. v (s0 ) !7 s0. q (s, a) !7 s, a q in terms of other q : r X X. s 0 q (s, a) = Ras + a Pss 0 (a0|s 0)q (s 0, a0). s 0 S a0 A. q (s0 , a0 ) !7 a0. Example: v (s). Pubbing R = -1. 0. Submit Leave Pubbing project R=0 R = -1 R=0. Submit project Study Study R = +10.
8 Group Disc. R = -2 R = -2. Take Arun's Quiz R = +1. Example: v (s). v (s) for (a|s)= , =1. Pubbing R = -1. v (GD) = * (R+v (Submitted) ) + *(R+v (Arun's OH)). v (GD) = *(0+0) + *(-2 + ). 0. Submit Leave Pubbing project R=0 R = -1 R=0. Submit project Study Study R = +10. Group Disc. R = -2 R = -2. Take Arun's Quiz R = +1. Example: v (s). v (s) for (a|s)= , =1. Pubbing R = -1. v (GD) = * (R+v (Submitted) ) + *(R+v (Arun's OH)). v (GD) = *(0+0) + *(-2 + ). 0. Submit Leave Pubbing project R=0 R = -1 R=0. Submit project Study Study R = +10. R = -2 R = -2. Take Arun's Quiz R = +1. Example: q (s,a). q (s,a) for (a|s)= , =1.
9 R = -1. q = - q = q=0. R=0 R = -1 R=0. q = q = 10. q = q = R = +10. R = -2 R = -2. q = R = +1. Example: q (s,a). q (s,a) for (a|s)= , =1. R = -1. q = - q = q=0. R=0 R = -1 R=0. q = q = 10. q = q = R = +10. R = -2 R = -2. q = R = +1. Example: Policy improvement R = -1. q = - q = q=0. R=0 R = -1 R=0. q = q = 10. q = q = R = +10. R = -2 R = -2. q = R = +1. Example: Policy improvement - Greedy (. 1 if a = argmax qold(s, a). R = -1 new(a|s) = a A. q = - 0 otherwise q = q=0. R=0 R = -1 R=0. q = q = 10. q = q = R = +10. R = -2 R = -2. q = R = +1. Policy Iteration Policy evaluation Estimate v . Iterative policy evaluation Policy improvement Generate 0.)
10 Greedy policy improvement Iterative Policy Evaluation in Small Gridworld vVkk for the Greedy Policy update States: 14 cells + 2 terminal cells Random Policy vkk V Actions: 4 directions Rewards: -1 for time step random k=0 policy k=1. k=2. Iterative k = 2 Policy Evaluation in Small Gridworld (2). k=3. Saturated k = 10 policy -14. -20. -22. -14. -18. -20. -20. k = . -20. -20. -18. -14. -22. -20. -14. Policy Iteration Policy evaluation Estimate v . Iterative policy evaluation Policy improvement Generate 0 . Greedy policy improvement Modified Policy Iteration - Value Iteration Policy converges faster than value function In t he small gridworld k =3 was sufficient t o achieve optimal policy Why not update policy every iteration?
