A Brief Introduction to Reinforcement Learning

1 A Brief Introduction to Reinforcement LearningJingwei Zhang Characteristics of Reinforcement Learning (RL) Components of RL (MDP, value, policy, Bellman) Planning (policy iteration, value iteration) Model-free Prediction (MC, TD) Model-free Control (Q- Learning ) Deep Reinforcement Learning (DQN)2 Outline Characteristics of Reinforcement Learning (RL) The RL Problem (MDP, value, policy, Bellman) Planning (policy iteration, value iteration) Model-free Prediction (MC, TD) Model-free Control (Q- Learning ) Deep Reinforcement Learning (DQN)4 Characteristics of RL SL VS RL Supervised Learning data direct and strong supervision (label: what is the right thing to do) instantaneous feedback Reinforcement Learning sequential data, no supervisor, only a reward signal (rule: what you did is good or bad) delayed feedback5 Characteristics of RL SL VS RL Supervised Learning data direct and strong supervision (label: what is the right thing to do) instantaneous feedback Reinforcement Learning sequential data, no supervisor, only a reward signal (rule: what you did is good or bad) delayed feedback6 Characteristics of RL SL VS RL Supervised Learning data direct and strong supervision (label: what is the right thing to do) instantaneous feedback Reinforcement Learning sequential data, no supervisor, only a reward signal (rule: what you did is good or bad) delayed feedback7 Characteristics of RL SL VS RL Supervised Learning data direct and strong supervision (label.)

2 What is the right thing to do) instantaneous feedback Reinforcement Learning sequential data, no supervisor, only a reward signal (rule: what you did is good or bad) delayed feedback8 Outline Characteristics of Reinforcement Learning (RL) Components of RL (MDP, value, policy, Bellman) Planning (policy iteration, value iteration) Model-free Prediction (MC, TD) Model-free Control (Q- Learning ) Deep Reinforcement Learning (DQN)10 Components of RL MDP A general framework for sequential decision making A MDP is a tuple: Markov property: The future is independent of the past given the present 11hS,A,P,R, iS:statesA:actionsP:transition probability,Pass0=P[St+1=s0|St=s,At=a]R: reward function,Ras=E[Rt+1|St=s,At=a] :discount factor, 2[0,1]Components of RL MDP A general framework for sequential decision making A MDP is a tuple: Markov property: The future is independent of the past given the present 12hS,A,P,R, iS:statesA:actionsP:transition probability,Pass0=P[St+1=s0|St=s,At=a]R: reward function,Ras=E[Rt+1|St=s,At=a] :discount factor, 2[0,1]Components of RL MDP A general framework for sequential decision making A MDP is a tuple: Markov property: The future is independent of the past given the present 13hS,A,P,R, iS:statesA:actionsP:transition probability,Pass0=P[St+1=s0|St=s,At=a]R: reward function,Ras=E[Rt+1|St=s,At=a] :discount factor, 2[0,1] Policy: Return: State-value function: Action-value function: Components of RL Policy & Return & Value14Gt=Rt+1+ Rt+2+.

3 =1Xk=0 kRt+k+1 (a|s)=P[At=a|St=s]v (s)=E [Gt|St=s]q (s,a)=E [Gt|St=s,At=a] Policy: Return: State-value function: Action-value function: Components of RL Policy & Return & Value15Gt=Rt+1+ Rt+2+..=1Xk=0 kRt+k+1 (a|s)=P[At=a|St=s]v (s)=E [Gt|St=s]q (s,a)=E [Gt|St=s,At=a] Policy: Return: State-value function: Action-value function: Components of RL Policy & Return & Value16Gt=Rt+1+ Rt+2+..=1Xk=0 kRt+k+1 (a|s)=P[At=a|St=s]v (s)=E [Gt|St=s]q (s,a)=E [Gt|St=s,At=a] Policy: Return: State-value function: Action-value function: Components of RL Policy & Return & Value17Gt=Rt+1+ Rt+2+..=1Xk=0 kRt+k+1 (a|s)=P[At=a|St=s]v (s)=E [Gt|St=s]q (s,a)=E [Gt|St=s,At=a]Components of RL Bellman Equations Bellman Expectation Equation 18v (s)=E [Rt+1+ v (St+1)|St=s]v (s)=Xa2A (a|s) Ras+ Xs02 SPass0v (s0)! Bellman Optimality Equation Components of RL Bellman Equations19v (s)=maxa Ras+ Xs02 SPass0v (s0)!

4 Components of RL Prediction VS Control Prediction given a policy, evaluate how much reward you can get by following that policy Control find an optimal policy that maximizes the cumulative future reward20 Components of RL Prediction VS Control Prediction given a policy, evaluate how much reward you can get by following that policy Control find an optimal policy that maximizes the cumulative future reward21 Components of RL Planning VS Learning Planning the underlying MDP is known agent only needs to perform computations on the given model dynamic programming (policy iteration, value iteration) Learning the underlying MDP is initially unknown agent needs to interact with the environment model-free (learn value / policy) / model-based (learn model, plan on it)22 Components of RL Planning VS Learning Planning the underlying MDP is known agent only needs to perform computations on the given model dynamic programming (policy iteration, value iteration) Learning the underlying MDP is initially unknown agent needs to interact with the environment model-free (learn value / policy) / model-based (learn model, plan on it)23 Components of RL Planning VS Learning Planning the underlying MDP is known agent only needs to perform computations on the given model dynamic programming (policy iteration, value iteration) Learning the underlying MDP is initially unknown agent needs to interact with the environment model-free (learn value / policy) / model-based (learn model, plan on it)

5 24 Components of RL Planning VS Learning Planning the underlying MDP is known agent only needs to perform computations on the given model dynamic programming (policy iteration, value iteration) Learning the underlying MDP is initially unknown agent needs to interact with the environment model-free (learn value / policy) / model-based (learn model, plan on it)25 Outline Characteristics of Reinforcement Learning (RL) The RL Problem (MDP, value, policy, Bellman) Planning (policy iteration, value iteration) Model-free Prediction (MC, TD) Model-free Control (Q- Learning ) Deep Reinforcement Learning (DQN)27 Planning Dynamic Programming Applied when optimal solutions can be decomposed into subproblems For prediction: Input: Output: For control: Input: Output:28<S,A,R,S, >, <S,A,R,S, >v v , Planning Dynamic Programming Applied when optimal solutions can be decomposed into subproblems For prediction: (iterative policy evaluation) Input: Output: For control: (policy iteration, value iteration) Input: Output:29<S,A,R,S, >, <S,A,R,S, >v v , Planning Dynamic Programming Applied when optimal solutions can be decomposed into subproblems For prediction: (iterative policy evaluation) Input: Output: For control: (policy iteration, value iteration) Input: Output:30<S,A,R,S, >, <S,A,R,S, >v v , Iterative application of Bellman Expectation backup Planning Iterative Policy Evaluation31vk+1(s)=Xa2A (a|s) Ras+ Xs02 SPass0vk(s0)!

6 V1!v2!..!v Evaluate the given policy and get: Get an improved policy by acting greedily: Planning Policy Iteration32 0=greedy(v )v Iterative application of Bellman Optimality backup v1!v2!..!v Planning Value Iteration33vk+1(s)=maxa2A Ras+ Xs02 SPass0vk(s0)!Planning Synchronous DP Algorithms34 Outline Characteristics of Reinforcement Learning (RL) The RL Problem (MDP, value, policy, Bellman) Planning (policy iteration, value iteration) Model-free Prediction (MC, TD) Model-free Control (Q- Learning ) Deep Reinforcement Learning (DQN)36 Planning the underlying MDP is known agent only needs to perform computations on the given model dynamic programming (policy iteration, value iteration) Learning the underlying MDP is initially unknown agent needs to interact with the environment model-free (learn value / policy) / model-based (learn model, plan on it)Recap.

7 Components of RL Planning VS Learning37 Monte Carlo Learning learns from complete trajectories, no bootstrapping estimates values by looking at sample returns, empirical mean return Temporal Difference Learning learns from incomplete episodes, by bootstrapping, substituting the remainder of the trajectory with our estimate updates a guess towards a guessModel-free Prediction MC VS TD38 Monte Carlo Learning learns from complete trajectories, no bootstrapping estimates values by looking at sample returns, empirical mean return Temporal Difference Learning learns from incomplete episodes, by bootstrapping, substituting the remainder of the trajectory with our estimate updates a guess towards a guessModel-free Prediction MC VS TD39 Monte Carlo Learning learns from complete trajectories, no bootstrapping estimates values by looking at sample returns, empirical mean return Temporal Difference Learning learns from incomplete episodes, by bootstrapping, substituting the remainder of the trajectory with our estimate updates a guess towards a guessModel-free Prediction MC VS TD40 Goal: Recall: Return is the total discounted reward: Recall: Value function is the expected return: MC policy evaluation (every visit MC): uses empirical mean return instead of expected returnModel-free Prediction MC41learnv from episodes of experience under policy v (s)=E [Gt|St=s]Gt=Rt+1+ Rt+2+.

8 =1Xk=0 kRt+k+1 Goal: Recall: Return is the total discounted reward: Recall: Value function is the expected return: MC policy evaluation (every visit MC): uses empirical mean return instead of expected returnModel-free Prediction MC42learnv from episodes of experience under policy v (s)=E [Gt|St=s]Gt=Rt+1+ Rt+2+..=1Xk=0 kRt+k+1 Goal: Recall: Return is the total discounted reward: Recall: Value function is the expected return: MC policy evaluation (every visit MC): uses empirical mean return instead of expected returnModel-free Prediction MC43learnv from episodes of experience under policy v (s)=E [Gt|St=s]Gt=Rt+1+ Rt+2+..=1Xk=0 kRt+k+1 Goal: Recall: Return is the total discounted reward: Recall: Value function is the expected return: MC policy evaluation (every visit MC): uses empirical mean return instead of expected returnModel-free Prediction MC44learnv from episodes of experience under policy v (s)=E [Gt|St=s]Gt=Rt+1+ Rt+2+.

9 =1Xk=0 kRt+k+1 Goal: MC: TD: Model-free Prediction MC -> TD45learnv from episodes of experience under policy V(St) V(St)+ (Gt V(St))V(St) V(St)+ (Rt+1+ V(St+1) V(St))updatesV(St)towardsactualreturn:Gt updatesV(St) towards estimated return:Rt+1+ V(St+1)Model-free Prediction MC VS TD: Driving Home46 Model-free Prediction MC Backup47 Model-free Prediction TD Backup48 Model-free Prediction DP Backup49 Model-free Prediction Unified View50 Outline Characteristics of Reinforcement Learning (RL) The RL Problem (MDP, value, policy, Bellman) Planning (policy iteration, value iteration) Model-free Prediction (MC, TD) Model-free Control (Q- Learning ) Deep Reinforcement Learning (DQN)52 MDP is unknown: but experience can be sampled MDP is known: but too big to use except to sample from it Model-free Control Why model-free?

10 53 Evaluate the given policy and get: Get an improved policy by acting greedily: Recap: Planning Policy Iteration54 0=greedy(v )v Evaluate the given policy and get: Get an improved policy by acting greedily: Model-free Control Generalized Policy Iteration55 0=greedy(v )v Greedy policy improvement over V(s) requires model of MDP Greedy policy improvement over Q(s,a) is model-free Model-free Control V -> Q56 0(s)=argmaxa2A(Ras+Pass0V(s0)) 0(s)=argmaxa2AQ(s,a)Model-free Control SARSA57Q(S,A) Q(S,A)+ (R+ Q(S0,A0) Q(S,A))Model-free Control Q-Learning58Q(S,A) Q(S,A)+ R+ maxa0Q(S0,a0) Q(S,A) Model-free Control SARSA VS Q-Learning59 Model-free Control DP VS TD60 Model-free Control DP VS TD61 Outline Characteristics of Reinforcement Learning (RL) The RL Problem (MDP, value, policy, Bellman) Planning (policy iteration, value iteration) Model-free Prediction (MC, TD) Model-free Control (Q- Learning ) Deep Reinforcement Learning (DQN)63 Deep Reinforcement Learning Why?