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.)

2 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: 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.

3 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+.

4 =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+.

5 =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)!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)

6 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)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)

7 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)!

8 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)

9 / model-based (learn model, plan on it)Recap: 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 t