Deep Reinforcement Learning
Lex Fridman

Course 6.S191:
Intro to Deep Learning

Lex Fridman:
fridman@mit.edu

January
2018

Environment

Open Question:
Sensors
Sensor Data

What can be learned fromdata?

Feature Extraction
Representation
Machine Learning
Knowledge
Reasoning

Planning
ActionEffector
Course 6.S191:
Intro to Deep Learning

Lex Fridman:
fridman@mit.edu

January
2018

Environment
Sensors
Sensor Data

Feature Extraction
Representation
Machine Learning
Knowledge
Reasoning

GPS
Lidar

Camera(Visible, Infrared)

Radar

Planning
ActionEffector
References: [132]

Stereo Camera

Microphone

Networking(Wired, Wireless)Course 6.S191:
Intro to Deep Learning

IMU
Lex Fridman:
fridman@mit.edu

January
2018

Environment
Sensors
Sensor Data

Feature Extraction
Representation
Machine Learning
Knowledge
Reasoning

Planning
ActionEffector
Course 6.S191:
Intro to Deep Learning

Lex Fridman:
fridman@mit.edu

January
2018

Environment
Sensors
Sensor Data

Feature Extraction
Representation
Machine Learning
Knowledge
Reasoning

Planning
ActionEffector
Course 6.S191:
Intro to Deep Learning

Lex Fridman:
fridman@mit.edu

January
2018

Environment

Image Recognition:
If it looks like a duck

Audio Recognition:
Quacks like a duck

Sensors
Sensor Data

Feature Extraction
Representation
Machine Learning

Activity Recognition:
Swims like a duck

Knowledge
Reasoning

Planning
ActionEffector
Course 6.S191:
Intro to Deep Learning

Lex Fridman:
fridman@mit.edu

January
2018

Environment
Sensors
Sensor Data

Feature Extraction
Representation
Machine Learning
Knowledge
Reasoning

Planning
ActionEffector

Final breakthrough, 358 years after its conjecture:“It was so indescribably beautiful; it was so simple andso elegant. I couldn’t understand how I’d missed it andI just stared at it in disbelief for twenty minutes. Then
during the day I walked around the department, andI’d keep coming back to my desk looking to see if it
was still there. It was still there. I couldn’t containmyself, I was so excited. It was the most importantmoment of my working life. Nothing I ever do again
will mean as much."
Course 6.S191:
Intro to Deep Learning

Lex Fridman:
fridman@mit.edu

January
2018

Environment
Sensors
Sensor Data

Feature Extraction
Representation
Machine Learning
Knowledge
Reasoning

Planning
ActionEffector
Course 6.S191:
Intro to Deep Learning

Lex Fridman:
fridman@mit.edu

January
2018

Environment
Sensors
Sensor Data

Feature Extraction
Representation
Machine Learning
Knowledge
Reasoning

Planning
ActionEffector
References: [133]

Course 6.S191:
Intro to Deep Learning

Lex Fridman:
fridman@mit.edu

January
2018

Environment
Sensors
Sensor Data

Feature Extraction

The promise of
Deep Learning

Representation
Machine Learning
Knowledge
Reasoning

Planning

The promise of
Deep Reinforcement Learning

ActionEffector
Course 6.S191:
Intro to Deep Learning

Lex Fridman:
fridman@mit.edu

January
2018

Types of Deep Learning

Supervised
Learning

Semi-Supervised
Learning

For the full updated list of references visit:https://selfdrivingcars.mit.edu/references[81, 165]

Unsupervised
Learning

Reinforcement
Learning

Course 6.S191:
Intro to Deep Learning

Lex Fridman:
fridman@mit.edu

January
2018

Philosophical Motivation for Reinforcement Learning
Takeaway from Supervised Learning:
Neural networks are great at memorization and not (yet) great at
reasoning.
Hope for Reinforcement Learning:
Brute-force propagation of outcomes to knowledge about states
and actions. This is a kind of brute-force “reasoning”.

For the full updated list of references visit:https://selfdrivingcars.mit.edu/references

Course 6.S191:
Intro to Deep Learning

Lex Fridman:
fridman@mit.edu

January
2018

Agent and Environment• At each step the agent:• Executes action• Receives observation (new state)• Receives reward• The environment:• Receives action• Emits observation (new state)• Emits reward

For the full updated list of references visit:https://selfdrivingcars.mit.edu/references[80]

Course 6.S191:
Intro to Deep Learning

Lex Fridman:
fridman@mit.edu

January
2018

Examples of Reinforcement Learning
Reinforcement learning is a general-purpose framework for decision-making:• An agent operates in an environment: Atari Breakout• An agent has the capacity to act• Each action influences the agent’s future state• Success is measured by a reward signal• Goal is to select actions to maximize future reward

For the full updated list of references visit:https://selfdrivingcars.mit.edu/references[85]

Course 6.S191:
Intro to Deep Learning

Lex Fridman:
fridman@mit.edu

January
2018

Examples of Reinforcement Learning

Cart-Pole Balancing• Goal — Balance the pole on top of a moving cart
• State — Pole angle, angular speed. Cart position, horizontal velocity.

• Actions — horizontal force to the cart
• Reward — 1 at each time step if the pole is upright
For the full updated list of references visit:https://selfdrivingcars.mit.edu/references[166]

Course 6.S191:
Intro to Deep Learning

Lex Fridman:
fridman@mit.edu

January
2018

Examples of Reinforcement Learning

Doom• Goal — Eliminate all opponents• State — Raw game pixels of the game• Actions — Up, Down, Left, Right etc• Reward — Positive when eliminating an opponent,
negative when the agent is eliminated
For the full updated list of references visit:https://selfdrivingcars.mit.edu/references[166]

Course 6.S191:
Intro to Deep Learning

Lex Fridman:
fridman@mit.edu

January
2018

Examples of Reinforcement Learning

Bin Packing• Goal - Pick a device from a box and put it into a container• State - Raw pixels of the real world• Actions - Possible actions of the robot• Reward - Positive when placing a device successfully, negative otherwise
For the full updated list of references visit:https://selfdrivingcars.mit.edu/references[166]

Course 6.S191:
Intro to Deep Learning

Lex Fridman:
fridman@mit.edu

January
2018

Examples of Reinforcement Learning

Human Life
• Goal - Survival? Happiness?
• State - Sight. Hearing. Taste. Smell. Touch.

• Actions - Think. Move.
• Reward – Homeostasis?
For the full updated list of references visit:https://selfdrivingcars.mit.edu/references

Course 6.S191:
Intro to Deep Learning

Lex Fridman:
fridman@mit.edu

January
2018

Key Takeaways for Real-World Impact• Deep Learning:• Fun part: Good algorithms that learn from data.
• Hard part: Huge amounts of representative data.

• Deep Reinforcement Learning:• Fun part: Good algorithms that learn from data.
• Hard part: Defining a useful state space, action space, and reward.
• Hardest part: Getting meaningful data for the above formalization.

For the full updated list of references visit:https://selfdrivingcars.mit.edu/references

Course 6.S191:
Intro to Deep Learning

Lex Fridman:
fridman@mit.edu

January
2018

Markov Decision Process𝑠0, 𝑎0, 𝑟1, 𝑠1, 𝑎1, 𝑟2, … , 𝑠𝑛−1, 𝑎𝑛−1, 𝑟𝑛, 𝑠𝑛
state

Terminal state

actionrewardFor the full updated list of references visit:https://selfdrivingcars.mit.edu/references[84]

Course 6.S191:
Intro to Deep Learning

Lex Fridman:
fridman@mit.edu

January2018

Major Components of an RL AgentAn RL agent may include one or more of these components:• Policy: agent’s behavior function• Value function: how good is each state and/or action• Model: agent’s representation of the environment𝑠0, 𝑎0, 𝑟1, 𝑠1, 𝑎1, 𝑟2, … , 𝑠𝑛−1, 𝑎𝑛−1, 𝑟𝑛, 𝑠𝑛
state

Terminal state

actionrewardFor the full updated list of references visit:https://selfdrivingcars.mit.edu/references

Course 6.S191:
Intro to Deep Learning

Lex Fridman:
fridman@mit.edu

January
2018

Robot in a Room
+1
-1
START

actions: UP, DOWN, LEFT, RIGHT

When actions are stochastic:
UP
80%
10%
10%

move UP
move LEFT
move RIGHT• reward +1 at [4,3], -1 at [4,2]• reward -0.04 for each step
• what’s the strategy to achieve max reward?
• what if the actions were deterministic?
Course 6.S191:
Intro to Deep Learning

Lex Fridman:
fridman@mit.edu

January2018

Is this a solution?
+1

actions: UP, DOWN, LEFT, RIGHT

When actions are stochastic:

-1

UP
80%
10%
10%

move UP
move LEFT
move RIGHT• only if actions deterministic• not in this case (actions are stochastic)• solution/policy• mapping from each state to an action
Course 6.S191:
Intro to Deep Learning

Lex Fridman:
fridman@mit.edu

January
2018

Optimal policy+1

actions: UP, DOWN, LEFT, RIGHT

When actions are stochastic:

-1

UP
80%
10%
10%

move UP
move LEFT
move RIGHT

Course 6.S191:
Intro to Deep Learning

Lex Fridman:
fridman@mit.edu

January
2018Reward for each step -2+1-1

Course 6.S191:
Intro to Deep Learning

Lex Fridman:
fridman@mit.edu

January
2018Reward for each step: -0.1
+1
-1

Course 6.S191:
Intro to Deep Learning

Lex Fridman:
fridman@mit.edu

January
2018Reward for each step: -0.04+1-1

Course 6.S191:
Intro to Deep Learning

Lex Fridman:
fridman@mit.edu

January
2018Reward for each step: -0.01+1-1

Course 6.S191:
Intro to Deep Learning

Lex Fridman:
fridman@mit.edu

January
2018Reward for each step: +0.01+1-1

Course 6.S191:
Intro to Deep Learning

Lex Fridman:
fridman@mit.edu

January
2018

Value Function• Future reward

𝑅 = 𝑟1 + 𝑟2 + 𝑟3 + ⋯ + 𝑟𝑛
𝑅𝑡 = 𝑟𝑡 + 𝑟𝑡 +1 + 𝑟𝑡 +2 + ⋯ + 𝑟𝑛

• Discounted future reward (environment is stochastic)
𝑅𝑡 = 𝑟𝑡 + 𝛾𝑟𝑡+1 + 𝛾2𝑟𝑡+2 + ⋯ + 𝛾𝑛−𝑡𝑟𝑛= 𝑟𝑡 + 𝛾(𝑟𝑡+1 + 𝛾(𝑟𝑡+2 + ⋯ ))= 𝑟𝑡 + 𝛾𝑅𝑡+1• A good strategy for an agent would be to always choose
an action that maximizes the (discounted) future reward
References: [84]Course 6.S191:
Intro to Deep Learning

Lex Fridman:
fridman@mit.edu

January
2018

Q-Learningsa• State-action value function: Q(s,a)• Expected return when starting in s,
performing a, and following rs’• Q-Learning: Use any policy to estimate Q that maximizes future reward:• Q directly approximates Q* (Bellman optimality equation)• Independent of the policy being followed• Only requirement: keep updating each (s,a) pair
Learning Rate

New State

Old State

Discount Factor

RewardCourse 6.S191:
Intro to Deep Learning

Lex Fridman:
fridman@mit.edu

January
2018

Exploration vs Exploitation•

Deterministic/greedy policy won’t explore all actions•••

Don’t know anything about the environment at the beginning
Need to try all actions to find the optimal one

ε-greedy policy••

With probability 1-ε perform the optimal/greedy action, otherwise random action
Slowly move it towards greedy policy: ε -> 0

Course 6.S191:
Intro to Deep Learning

Lex Fridman:
fridman@mit.edu

January
2018

Q-Learning: Value Iteration

A1

A2

A3

A4

S1

+1

+2

-1

0

S2

+2

0

+1

-2

S3

-1

+1

0

-2

S4

-2

0

+1

+1

References: [84]Course 6.S191:
Intro to Deep Learning

Lex Fridman:
fridman@mit.edu

January
2018

Q-Learning: Representation Matters• In practice, Value Iteration is impractical• Very limited states/actions• Cannot generalize to unobserved states• Think about the Breakout game
• State: screen pixels• Image size: 𝟖𝟒 × 𝟖𝟒 (resized)• Consecutive 4 images• Grayscale with 256 gray levels

References: [83, 84]

𝟐𝟓𝟔𝟖𝟒×𝟖𝟒×𝟒 rows in the Q-table!

Course 6.S191:
Intro to Deep Learning

Lex Fridman:
fridman@mit.edu

January
2018

Philosophical Motivation for Deep Reinforcement Learning
Takeaway from Supervised Learning:
Neural networks are great at memorization and not (yet) great at
reasoning.
Hope for Reinforcement Learning:
Brute-force propagation of outcomes to knowledge about states
and actions. This is a kind of brute-force “reasoning”.
Hope for Deep Learning + Reinforcement Learning:
General purpose artificial intelligence through efficient
generalizable learning of the optimal thing to do given aformalized set of actions and states (possibly huge).
For the full updated list of references visit:https://selfdrivingcars.mit.edu/references

Course 6.S191:
Intro to Deep Learning

Lex Fridman:
fridman@mit.edu

January
2018

Deep Learning is Representation Learning(aka Feature Learning)

Deep
Learning

Representation
Learning
MachineLearning
Artificial
IntelligenceIntelligence: Ability to accomplish complex goals.
Understanding: Ability to turn complex information to into simple, useful information.
For the full updated list of references visit:https://selfdrivingcars.mit.edu/references[20]

Course 6.S191:
Intro to Deep Learning

Lex Fridman:
fridman@mit.edu

January
2018

DQN: Deep Q-Learning
Use a function (with parameters)
to approximate the Q-function• Linear• Non-linear: Q-Network

For the full updated list of references visit:https://selfdrivingcars.mit.edu/references[83]

Course 6.S191:
Intro to Deep Learning

Lex Fridman:
fridman@mit.edu

January
2018

Deep Q-Network (DQN): Atari

Mnih et al. "Playing atari with deep reinforcement learning." 2013.
For the full updated list of references visit:https://selfdrivingcars.mit.edu/references[83]

Course 6.S191:
Intro to Deep Learning

Lex Fridman:
fridman@mit.edu

January
2018

DQN and Double DQN (DDQN)• Loss function (squared error):targetprediction• DQN: same network for both Q• DDQN: separate network for each Q• Helps reduce bias introduced by the inaccuracies of
Q network at the beginning of training
For the full updated list of references visit:https://selfdrivingcars.mit.edu/references[83]

Course 6.S191:
Intro to Deep Learning

Lex Fridman:
fridman@mit.edu

January
2018

DQN Tricks• Experience Replay• Stores experiences (actions, state transitions, and rewards) and createsmini-batches from them for the training process• Fixed Target Network• Error calculation includes the target function depends on network
parameters and thus changes quickly. Updating it only every 1,000
steps increases stability of training process.

• Reward Clipping• To standardize rewards across games by setting all positive rewards to+1 and all negative to -1.

• Skipping Frames• Skip every 4 frames to take action
For the full updated list of references visit:https://selfdrivingcars.mit.edu/references[83, 167]

Course 6.S191:
Intro to Deep Learning

Lex Fridman:
fridman@mit.edu

January
2018

DQN Tricks• Experience Replay• Stores experiences (actions, state transitions, and rewards) and createsmini-batches from them for the training process• Fixed Target Network• Error calculation includes the target function depends on network
parameters and thus changes quickly. Updating it only every 1,000
steps increases stability of training process.

For the full updated list of references visit:https://selfdrivingcars.mit.edu/references[83, 167]

Course 6.S191:
Intro to Deep Learning

Lex Fridman:
fridman@mit.edu

January
2018

Deep Q-Learning Algorithm

For the full updated list of references visit:https://selfdrivingcars.mit.edu/references[83, 167]

Course 6.S191:
Intro to Deep Learning

Lex Fridman:
fridman@mit.edu

January
2018

Atari Breakout

After
10 Minutesof Training

For the full updated list of references visit:https://selfdrivingcars.mit.edu/references

After
120 Minutesof Training

[85]

After
240 Minutesof Training

Course 6.S191:
Intro to Deep Learning

Lex Fridman:
fridman@mit.edu

January
2018

DQN Results in Atari

For the full updated list of references visit:https://selfdrivingcars.mit.edu/references[83]

Course 6.S191:
Intro to Deep Learning

Lex Fridman:
fridman@mit.edu

January
2018

Policy Gradients (PG)
• DQN (off-policy): Approximate Q and infer optimal policy• PG (on-policy): Directly optimize policy space

Good illustrative explanation:
http://karpathy.github.io/2016/05/31/rl/“Deep Reinforcement Learning:
Pong from Pixels”

Policy Network

For the full updated list of references visit:https://selfdrivingcars.mit.edu/references[63]

Course 6.S191:
Intro to Deep Learning

Lex Fridman:
fridman@mit.edu

January
2018

Policy Gradients – Training• REINFORCE (aka Actor-Critic): Policy gradient that increases probability ofgood actions and decreases probability of bad action:• Policy network is the “actor”• Rt is the “critic”
For the full updated list of references visit:https://selfdrivingcars.mit.edu/references[63, 204]

Course 6.S191:
Intro to Deep Learning

Lex Fridman:
fridman@mit.edu

January
2018

Policy Gradients (PG)
• Pros vs DQN:
• Able to deal with more complex Q function• Faster convergence• Since Policy Gradients model probabilities of actions, it is capable oflearning stochastic policies, while DQN can’t.

• Cons:• Needs more data

For the full updated list of references visit:https://selfdrivingcars.mit.edu/references[63]

Course 6.S191:
Intro to Deep Learning

Lex Fridman:
fridman@mit.edu

January
2018

Game of Go

For the full updated list of references visit:https://selfdrivingcars.mit.edu/references[170]

Course 6.S191:
Intro to Deep Learning

Lex Fridman:
fridman@mit.edu

January2018

AlphaGo (2016) Beat Top Human at Go

For the full updated list of references visit:https://selfdrivingcars.mit.edu/references[83]

Course 6.S191:
Intro to Deep Learning

Lex Fridman:
fridman@mit.edu

January2018

AlphaGo Zero (2017): Beats AlphaGo

For the full updated list of references visit:https://selfdrivingcars.mit.edu/references[149]

Course 6.S191:
Intro to Deep Learning

Lex Fridman:
fridman@mit.edu

January2018

AlphaGo Zero Approach• Same as the best before: Monte Carlo Tree Search (MCTS)• Balance exploitation/exploration (going deep on promising positions or
exploring new underplayed positions)• Use a neural network as “intuition” for which positions to
expand as part of MCTS (same as AlphaGo)

For the full updated list of references visit:https://selfdrivingcars.mit.edu/references[170]

Course 6.S191:
Intro to Deep Learning

Lex Fridman:
fridman@mit.edu

January2018

AlphaGo Zero Approach• Same as the best before: Monte Carlo Tree Search (MCTS)• Balance exploitation/exploration (going deep on promising positions or
exploring new underplayed positions)• Use a neural network as “intuition” for which positions to
expand as part of MCTS (same as AlphaGo)• “Tricks”• Use MCTS intelligent look-ahead (instead of human games) to improvevalue estimates of play options• Multi-task learning: “two-headed” network that outputs (1) moveprobability and (2) probability of winning.
• Updated architecture: use residual networks

For the full updated list of references visit:https://selfdrivingcars.mit.edu/references[170]

Course 6.S191:
Intro to Deep Learning

Lex Fridman:
fridman@mit.edu

January
2018

DeepStack first to beat professional poker players (2017)(in heads-up poker)

For the full updated list of references visit:https://selfdrivingcars.mit.edu/references[150]

Course 6.S191:
Intro to Deep Learning

Lex Fridman:
fridman@mit.edu

January2018

To date, for most successful robots operating in the real world:

Deep RL is not involved(to the best of our knowledge)

For the full updated list of references visit:https://selfdrivingcars.mit.edu/references

Course 6.S191:
Intro to Deep Learning

Lex Fridman:
fridman@mit.edu

January2018

To date, for most successful robots operating in the real world:

Deep RL is not involved(to the best of our knowledge)

For the full updated list of references visit:https://selfdrivingcars.mit.edu/references[169]

Course 6.S191:
Intro to Deep Learning

Lex Fridman:
fridman@mit.edu

January
2018Unexpected Local Pockets of High Reward

For the full updated list of references visit:https://selfdrivingcars.mit.edu/references[63, 64]

Course 6.S191:
Intro to Deep Learning

Lex Fridman:
fridman@mit.edu

January
2018

AI Safety
Risk (and thus Human Life) Part of the Loss Function

For the full updated list of references visit:https://selfdrivingcars.mit.edu/references

Course 6.S191:
Intro to Deep Learning

Lex Fridman:
fridman@mit.edu

January
2018

DeepTraffic: Deep Reinforcement Learning Competition

https://selfdrivingcars.mit.edu/deeptraffic
For the full updated list of references visit:https://selfdrivingcars.mit.edu/references

Course 6.S191:
Intro to Deep Learning

Lex Fridman:
fridman@mit.edu

January
2018