Deep Reinforcement Learning
MIT 6.S191

Alexander Amini
January 30, 2019

AlphaGo video

6.S191 Introduction to Deep Learning
introtodeeplearning.com

1/30/19

Classes of Learning Problems
Supervised Learning
Data: (", $)" is data, $ is label
Goal: Learn function to map"→$Apple example:

This thing is an apple.
6.S191 Introduction to Deep Learning
introtodeeplearning.com

1/30/19

Classes of Learning Problems
Supervised Learning

Unsupervised Learning

Data: (", $)" is data, $ is label

Data: "" is data, no labels!

Goal: Learn function to map"→$

Goal: Learn underlying
structure

Apple example:

Apple example:

This thing is an apple.

This thing is likethe other thing.
6.S191 Introduction to Deep Learning
introtodeeplearning.com

1/30/19

Classes of Learning Problems
Supervised Learning

Unsupervised Learning

Reinforcement Learning

Data: (", $)" is data, $ is label

Data: "" is data, no labels!

Data: state-action pairs

Goal: Learn function to map"→$Goal: Learn underlying
structure

Goal: Maximize future rewards
over many time steps

Apple example:

Apple example:

Apple example:

This thing is an apple.

This thing is likethe other thing.
6.S191 Introduction to Deep Learning
introtodeeplearning.com

Eat this thing because it
will keep you alive.
1/30/19

Classes of Learning Problems
Supervised Learning

Unsupervised Learning

Reinforcement Learning

Data: (", $)" is data, $ is label

Data: "" is data, no labels!

Data: state-action pairs

RL: our focus
today.
Goal: Learn
underlying

Goal: Learn function to map"→$structure

Goal: Maximize future rewards
over many time steps

Apple example:

Apple example:

Apple example:

This is an apple.

This thing is likethe other thing.
6.S191 Introduction to Deep Learning
introtodeeplearning.com

Eat this thing because it
will keep you alive.
1/30/19

Reinforcement Learning (RL): Key Concepts

AGENT

Agent: takes actions.

6.S191 Introduction to Deep Learning
introtodeeplearning.com

1/30/19

Reinforcement Learning (RL): Key Concepts

AGENT

ENVIRONMENT

Environment: the world in which the agent exists and operates.

6.S191 Introduction to Deep Learning
introtodeeplearning.com

1/30/19

Reinforcement Learning (RL): Key Concepts

AGENT

Action: !"ENVIRONMENTACTIONS
Action: a move the agent can make in the environment.

6.S191 Introduction to Deep Learning
introtodeeplearning.com

1/30/19

Reinforcement Learning (RL): Key Concepts
OBSERVATIONSAGENTAction: !"ENVIRONMENTACTIONS
Observations: of the environment after taking actions.

6.S191 Introduction to Deep Learning
introtodeeplearning.com

1/30/19

Reinforcement Learning (RL): Key Concepts
OBSERVATIONSState changes: !"#$AGENT

Action: %"ENVIRONMENTACTIONSState: a situation which the agent perceives.

6.S191 Introduction to Deep Learning
introtodeeplearning.com

1/30/19

Reinforcement Learning (RL): Key Concepts
OBSERVATIONSState changes: !"#$
Reward: %"AGENTAction: &"ENVIRONMENTACTIONS
Reward: feedback that measures the success or failure of the agent’s action.

6.S191 Introduction to Deep Learning
introtodeeplearning.com

1/30/19

Reinforcement Learning (RL): Key Concepts
OBSERVATIONSState changes: !"#$
Reward: %"Action: &"AGENTENVIRONMENTACTIONS
Total Reward,'" = ) %**+"
6.S191 Introduction to Deep Learning
introtodeeplearning.com

1/30/19

Reinforcement Learning (RL): Key Concepts
OBSERVATIONSState changes: !"#$
Reward: %"Action: &"AGENTENVIRONMENTACTIONS
Total Reward,'" = ) %* = %" + %"#$ … + %"#/ + ⋯*+"
6.S191 Introduction to Deep Learning
introtodeeplearning.com

1/30/19

Reinforcement Learning (RL): Key Concepts
OBSERVATIONSState changes: !"#$
Reward: %"Action: &"AGENTENVIRONMENTACTIONS
Discounted
Total Reward,'" = ) - * %**+"6.S191 Introduction to Deep Learning
introtodeeplearning.com

1/30/19

Reinforcement Learning (RL): Key Concepts
OBSERVATIONSState changes: !"#$
Reward: %"Action: &"AGENTENVIRONMENTACTIONS
Discounted
Total Reward': discount factor.

)" = + ' , %, = ' " %" + ' "#$ %"#$ … + ' "#1 %"#1 + ⋯,-"
6.S191 Introduction to Deep Learning
introtodeeplearning.com

1/30/19

Defining the Q-function!" = $" + &$"'( +& ) $"') + ⋯Total reward, !" , is the discounted sum of all rewards obtained from time 0+ ,, . = / !"The Q-function captures the expected total future reward an
agent in state, ,, can receive by executing a certain action, .
6.S191 Introduction to Deep Learning
introtodeeplearning.com

1/30/19

How to take actions given a Q-function?
! ", $ = & '((state, action)
Ultimately, the agent needs a policy ) * , to infer the best action to take at its state, sStrategy: the policy should choose an action that maximizes future reward+ ∗ " = argmax !(", $)2

6.S191 Introduction to Deep Learning
introtodeeplearning.com

1/30/19

Deep Reinforcement Learning Algorithms
Value Learning

Policy Learning

Find % ", #Find ! "# = argmax %(", #)Sample # ~ ! "-Deep Reinforcement Learning Algorithms
Value Learning

Policy LearningFind % ", #Find ! "# = argmax %(", #)Sample # ~ ! "-Digging deeper into the Q-function
Example: Atari Breakout

It can be very difficult for humans toaccurately estimate Q-values
AB

Which (s, a) pair has ahigher Q-value?
6.S191 Introduction to Deep Learning
introtodeeplearning.com

1/30/19

Digging deeper into the Q-function
Example: Atari Breakout

It can be very difficult for humans toaccurately estimate Q-values
AB

Which (s, a) pair has ahigher Q-value?
6.S191 Introduction to Deep Learningintrotodeeplearning.com

1/30/19

Digging deeper into the Q-function
Example: Atari Breakout - Middle

It can be very difficult for humans toaccurately estimate Q-values
AB

Which (s, a) pair has ahigher Q-value?
6.S191 Introduction to Deep Learning
introtodeeplearning.com

1/30/19

Digging deeper into the Q-function
Example: Atari Breakout - Side

It can be very difficult for humans toaccurately estimate Q-values
AB

Which (s, a) pair has ahigher Q-value?
6.S191 Introduction to Deep Learning
introtodeeplearning.com

1/30/19

Deep Q Networks (DQN)
How can we use deep neural networks to model Q-functions?

state, "Deep
NN! ", $“moveright”

action, $6.S191 Introduction to Deep Learning
introtodeeplearning.com

1/30/19

Deep Q Networks (DQN)
How can we use deep neural networks to model Q-functions?

! ", $%
state, "DeepNN

DeepNN! ", $“moveright”

state, "! ", $&! ", $'action, $6.S191 Introduction to Deep Learning
introtodeeplearning.com

1/30/19

Deep Q Networks (DQN): Training
How can we use deep neural networks to model Q-functions?

! ", $%state, "Deep
NNDeepNN! ", $“moveright”! ", $&! ", $'state, "action, $ℒ=*+ + - max !(" 2 , $2 )12− ! ", $6.S191 Introduction to Deep Learning
introtodeeplearning.com&1/30/19

Deep Q Networks (DQN): Training
How can we use deep neural networks to model Q-functions?

! ", $%
state, "

Deep
NN

Deep
NN! ", $“moveright”! ", $&! ", $'state, "action, $targetℒ=*+ + - max !(" 2 , $2 )12predicted− ! ", $6.S191 Introduction to Deep Learning
introtodeeplearning.com&

1/30/19

Deep Q Networks (DQN): Training
How can we use deep neural networks to model Q-functions?

! ", $%
state, "DeepNNDeep
NN! ", $“moveright”! ", $&! ", $'state, "action, $targetℒ=*+ + - max !(" 2 , $2 )12predicted− ! ", $6.S191 Introduction to Deep Learning
introtodeeplearning.com&

1/30/19

DQN Atari Results

6.S191 Introduction to Deep Learning
introtodeeplearning.com

1/30/19

DQN Atari Results
Surpass
human-level

Belowhuman-level

6.S191 Introduction to Deep Learning
introtodeeplearning.com

1/30/19

Downsides of Q-learning
Complexity:• Can model scenarios where the action space is discrete and small• Cannot handle continuous action spaces
IMPORTANT:

Imagine you want to predict
steering wheel angle of a car!

Flexibility:• Cannot learn stochastic policies since policy is deterministically computedfrom the Q function

To overcome, consider a new class of RL training algorithms:
Policy gradient methods
6.S191 Introduction to Deep Learning
introtodeeplearning.com

1/30/19

Policy Gradient (PG) : Key Idea
DQN (before): Approximating Q and inferring the optimal policy,! ", $%Deep
NN! ", $&! ", $'state, "6.S191 Introduction to Deep Learning
introtodeeplearning.com

1/30/19

Policy Gradient (PG): Key Idea
DQN (before): Approximating Q and inferring the optimal policy,
Policy Gradient: Directly optimize the policy!

! "# |%

Deep
NN! "& |%! "' |%

state, %6.S191 Introduction to Deep Learning
introtodeeplearning.com

1/30/19

Policy Gradient (PG): Key Idea
DQN (before): Approximating Q and inferring the optimal policy,
Policy Gradient: Directly optimize the policy!

! "# |%

DeepNN! "& |%( ! "- |% = 1)* ∈,! "' |%state, %6.S191 Introduction to Deep Learning
introtodeeplearning.com

1/30/19

Policy Gradient (PG): Key Idea
DQN (before): Approximating Q and inferring the optimal policy,Policy Gradient: Directly optimize the policy!

! "# |%

DeepNN! "& |%( ! "- |% = 1)* ∈,! "|% = 0("23456|%3"37)! "' |%

state, %6.S191 Introduction to Deep Learning
introtodeeplearning.com

1/30/19

Policy Gradient (PG): Key Idea
DQN (before): Approximating Q and inferring the optimal policy,Policy Gradient: Directly optimize the policy!

! "# |%

DeepNN! "& |%( ! "- |% = 1)* ∈,! "|% = 0("23456|%3"37)! "' |%

state, %6.S191 Introduction to Deep Learning
introtodeeplearning.com

1/30/19

Policy Gradient (PG): Training

1. Run a policy for a while
2. Increase probability of actions that lead to highrewards
3. Decrease probability of actions that lead tolow/no rewards
6.S191 Introduction to Deep Learning
introtodeeplearning.com

function REINFORCE
Initialize !
for "#$%&'" ~ )*{%, , ., , /, }342
,12 ← "#$%&'"
for t = 1 to T-1∇ ← ∇* log )* .: |%: <:! ← ! + >∇return !

1/30/19

Policy Gradient (PG): Training

1. Run a policy for a while
2. Increase probability of actions that lead to highrewards
3. Decrease probability of actions that lead tolow/no rewards
6.S191 Introduction to Deep Learning
introtodeeplearning.com

function REINFORCE
Initialize !
for "#$%&'" ~ )*{%, , ., , /, }342
,12 ← "#$%&'"
for t = 1 to T-1∇ ← ∇789: ;7 <= |?= @=! ← ! + B∇
return !

1/30/19

Policy Gradient (PG): Training

1. Run a policy for a while
2. Increase probability of actions that lead to highrewards
3. Decrease probability of actions that lead to
low/no rewards
6.S191 Introduction to Deep Learning
introtodeeplearning.com

function REINFORCE
Initialize !
for "#$%&'" ~ )*{%, , ., , /, }342
,12 ← "#$%&'"
for t = 1 to T-1∇ ← ∇789: ;7 <= |?= @=! ← ! + B∇
return !
log-likelihood of action∇* log )* .F |%F GF
reward
1/30/19

The Game of Go
Aim: Get more board territory than your opponent.
Board Size
nxn

Positions 3$%% LegalLegal Positions

1×1

3

33.33%

12×2

81

70.37%

57

3×3

19,68364.40%

12,6754×4

43,046,721

56.49%

24,318,165

5×5

847,288,609,443

48.90%

414,295,148,741

9×94.434264882×1038

23.44%

1.03919148791×1038

13×134.300233593×1080

8.66%

3.72497923077×1079

19×191.740896506×10172

1.20%

2.08168199382×10170

Greater number of legal board positions than atoms in the universe.
Source: Wikipedia.
6.S191 Introduction to Deep Learning
introtodeeplearning.com

1/30/19

AlphaGo Beats Top Human Player at Go (2016)

Silver et al., Nature 2016.
6.S191 Introduction to Deep Learning
introtodeeplearning.com

1/30/19

AlphaGo Beats Top Human Player at Go (2016)

1) Initial training: human data

Silver et al., Nature 2016.
6.S191 Introduction to Deep Learning
introtodeeplearning.com

1/30/19

AlphaGo Beats Top Human Player at Go (2016)

1) Initial training: human data
2) Self-play and reinforcement learningà super-human performance

Silver et al., Nature 2016.
6.S191 Introduction to Deep Learning
introtodeeplearning.com

1/30/19

AlphaGo Beats Top Human Player at Go (2016)

1) Initial training: human data
2) Self-play and reinforcement learningà super-human performance3) “Intuition” about board state

Silver et al., Nature 2016.
6.S191 Introduction to Deep Learning
introtodeeplearning.com

1/30/19

AlphaGo Beats Top Human Player at Go (2016)

1) Initial training: human data
2) Self-play and reinforcement learningà super-human performance3) “Intuition” about board state

Silver et al., Nature 2016.
6.S191 Introduction to Deep Learning
introtodeeplearning.com

1/30/19

AlphaZero: RL from Self-Play (2018)

Silver et al., Science 2018.
6.S191 Introduction to Deep Learning
introtodeeplearning.com

1/30/19

Questions?