Survey of Modern

Reinforcement Learning

Julia Maddalena

What to expect from this talk

Part 1 Introduce the foundations of reinforcement learning

• Definitions and basic ideas
• A couple algorithms that work in simple environments

Part 2 Review some state-of-the-art methods

• Higher level concepts, vanilla methods
• Not a complete list of cutting edge methods

Part 3 Current state of reinforcement learning

​

Part 1

Foundations of reinforcement learning

What is reinforcement learning?

A type of machine learning where an agent interacts with an environment and learns to take actions that result in greater cumulative reward.

Definitions

Reward

Motivation for the agent. Not always obvious what the reward signal should be

​

​

​

YOU WIN! +1

GAME OVER -1

Stay alive +1/second

(sort of)

Agent

The learner and decision maker

Environment

Everything external to the agent used to make decisions

Actions

The set of possible steps the agent can take depending on the state of the environment

The Problem with Rewards...

Designing reward functions is notoriously difficult

​

​

Clark, Jack. “Faulty Reward Functions in the Wild.” OpenAI, 21 Dec. 2016.

¹ Irpan, Alex. “Deep Reinforcement Learning Doesn't Work Yet.” Sorta Insightful, 14 Feb. 2018.

Possible reward structure

​

• Total points
• Time to finish
• Finishing position

Human player

“I’ve taken to imagining deep RL as a demon that’s deliberately misinterpreting your reward and actively searching for the laziest possible local optima.”

- Alex Irpan

Resulting RL Agent

More Definitions

​

Return

Long-term, discounted reward

​

�

​

​

​

​

​

​

​

Value

Expected return

​

​

​

​

value of states → V(s)

how good is it to be in state s

​

value of state-action pairs → Q(s,a)

how good is it to take action a from state s

discount factor

Policy

How the agent should act from a given state

→ π(a|s)

Markov Decision Process

Markov Process

A random process whose future behavior only depends on the current state.

​

​

Sleepy

Energetic

Hungry

70%

50%

15%

70%

50%

35%

50%

Markov Decision Process

Markov Process

Sleepy

Energetic

Hungry

nap

beg

be good

beg

be good

30%

70%

20%

60%

20%

50%

60%

40%

60%

40%

10%

40%

+ Actions

• Reward

= Markov Decision Process

To model or not to model

Model-based methods

​

Model-free methods

​

We don’t know or care about the dynamics, we just want to learn a good policy by

exploring the environment

Planning

Learning

Planning and Learning

Reinforcement Learning Methods

​

​

​

Model-based

Model-free

Transition

Model

Sample

Model

Dynamic Programming

Bellman Equations

Value of each states under optimal policy for Robodog:

​

Bellman Equation

Bellman Optimality Equation

policy

transition probabilities

value of the next state

reward

discount factor

value of the current state

Policy Iteration

Policy evaluation

Makes the value function consistent with the current policy

​

​

Policy improvement

Make the policy greedy with respect to the current value function

Converge to optimal policy and value under optimal policy

Reinforcement Learning Methods

​

​

​

Model-based

Model-free

Transition

Model

On-policy

Off-policy

Sample

Model

Value-based

Policy-based

Dynamic Programming

Sarsa

Q-Learning

Monte Carlo

Temporal Difference

When learning happens

Monte Carlo: wait until end of episode before making updates to value estimates

Update value for all states in episode

Update value for previous state

Temporal difference, TD(0): update every step using estimates of next states

bootstrapping

Update value for previous state

Update value for previous state

Update value for previous state

. . .

in this example, learning = updating value of states

Exploration vs exploitation

• Greedy policy will get stuck in local optima early on
• We need to explore to be able to learn, but we need to exploit in order to gather the most reward.
• With value-based methods, we need to determine policy from value.

​

​

​

​

𝜀-greedy policy

​

​

Sarsa

Energetic

be good

Hungry

+5

beg

S

A

R

S’

A’

Hungry

beg

Initialize Q(s,a)

For each episode:

• Start in a random state, S.

• Choose action A from S using 𝛆-greedy policy from Q(s,a).

• While S is not terminal:

1. Take action A, observe reward R and new state S’.

2. Choose action A’ from S’ using 𝛆-greedy policy from Q(s,a).

3. Update Q for state S and action A:

4. S ← S’, A ← A’

Q-Learning

3. Update Q for state S and action A:

​

​

Energetic

be good

Hungry

+5

beg

S

A

R

S’

be good

Q = -1

Q = 2

Hungry

Initialize Q(s,a)

​

For each episode:

• Start in a random state, S.

• While S is not terminal:

1. Choose action A from S using 𝛆-greedy policy from Q(s,a).
2. Take action A, observe reward R and new state S’.

4. S ← S’

beg

Part 2

State-of-the-art methods

Reinforcement Learning Methods

​

​

​

Model-based

Model-free

Transition

Model

On-policy

Off-policy

Sample

Model

Value-based

Policy-based

Dynamic Programming

Dyna-Q

Monte Carlo Tree Search

Sarsa

Q-Learning

Monte Carlo

Temporal Difference

Dyna-Q

For each episode:

• Start in a random state, S.

• While S is not terminal:

1. Choose action A from S using 𝛆-greedy policy from Q(s,a).
2. Take action A, observe reward R and new state S’.
3. Update Q for state S and action A:

​

​

​

Energetic

be good

Hungry

+5

ordinary Q-Learning

Hungry

beg

Sleepy

-6

R

R

R

⋮

5

hungry

0.5

R

R

R

⋮

Initialize Q(s,a) and Model(s,a)

4. Update Model for state S and action A:

5. “Hallucinate” n transitions and use them to update Q:

0.95

1.355

1.7195

Dyna-Q

Monte Carlo Tree Search

When brute force expansion of entire game tree (Minimax) is not feasible

​

Tic-tac-toe

Go

5,478 states

10¹⁷⁰ states

Monte Carlo Tree Search

Selection

Choose starting node

Expansion

Look at unexplored child nodes

Simulation

Simulate playing out the game under rollout policy

Update

Update stats

0/0

0/0

0/0

1/1

0/1

0/1

Monte Carlo Tree Search

Expansion

Look at unexplored child nodes

Simulation

Simulate playing out the game under rollout policy

Update

Update stats, including those of parent nodes

1/1

0/1

0/1

Selection

Choose child node to explore

(based on how good its stats are and how much it has been ignored)

0/0

0/0

0/0

1/1

0/1

1/1

2/2

2/3

3/4

Monte Carlo Tree Search

Expansion

Look at unexplored child nodes

(only applies if child node has not been expanded before)

Simulation

Simulate playing out the game under rollout policy

Update

Update stats, including those of parent nodes

3/4

0/1

0/1

Selection

Choose child node to explore

(based on how good its stats are and how much it has been ignored)

1/1

0/1

1/1

0/0

0/0

0/0

Monte Carlo Tree Search

47/65

32/37

12/33

Deep Reinforcement Learning

2

3

4

5

6

7

8

Black Box

state, s

Q(s, a)

for each action a

1

Q(s,X)

Q(s,Y)

Q(s,Z)

Reinforcement Learning Methods

​

​

​

Model-based

Model-free

Transition

Model

On-policy

Off-policy

Sample

Model

Value-based

Policy-based

Dynamic Programming

Dyna-Q

Monte Carlo Tree Search

Sarsa

Q-Learning

Deep Q Networks*

Monte Carlo Methods

Temporal Difference Methods

* Utilize deep learning

Deep Q Networks (DQN)

Black Box

X

blank

O

state, s

Q(s, a)

for each action a

how good is it to take this action from this state?

1. Initialize network.

​

1. Take one action under Q policy.

3. Add new information to training data:

4. Use stochastic gradient descent to update weights based on:

Repeat steps 2 - 4 until convergence

ŷ

y

Deep Q Networks (DQN)

1. Initialize network.
2. Take one action under Q policy.
3. Add new information to training data:

​

​

​

​

​

​

​

​

1. Use stochastic gradient descent to update weights based on:

​

​

Problem:

• Data not i.i.d.
• Data collected based on an evolving policy, not the optimal policy that we are trying to learn.

​

Solution:

Create a replay buffer of size k to take small samples from

Problem:

Instability introduced when updating Q(s, a) using Q(s’, a’)

​

​

Solution:

Have a secondary target network used to evaluate Q(s’, a’) and only sync with primary network after every n training iterations

primary network

target network

Reinforcement Learning Methods

​

​

​

Model-based

Model-free

Transition

Model

On-policy

Off-policy

Sample

Model

Value-based

Policy-based

Dynamic Programming

Dyna-Q

Monte Carlo Tree Search

Sarsa

Q-Learning

Deep Q Networks*

REINFORCE*

Monte Carlo Methods

Temporal Difference Methods

* Utilize deep learning

REINFORCE

​

Black Box

X

blank

O

state, s

𝛑(a|s)

for each action a

what is the probability of taking this action under policy 𝛑?

1. Initialize network.

​

​

​

​

r₁

r₂

r₃

r₄

r₅

r₆

r₇

r₈

2. Play out a full episode under 𝛑.

​

​

3. For every step t, calculate return from that state until the end:

4. Use stochastic gradient descent to update weights based on:

Repeat steps 2 - 4 until convergence

DQN vs REINFORCE

Reinforcement Learning Methods

​

​

​

Model-based

Model-free

Transition

Model

On-policy

Off-policy

Sample

Model

Value-based

Policy-based

Dynamic Programming

Dyna-Q

Monte Carlo Tree Search

Sarsa

Q-Learning

Deep Q Networks*

REINFORCE*

Monte Carlo Methods

Temporal Difference Methods

* Utilize deep learning

Advantage Actor-Critic*

Q Actor-Critic

Common layers

X

blank

O

state, s

Policy net

Value net

𝛑(a|s)

for each action a

Q(s,a)

for each action a

Actor

Policy-based like REINFORCE but can now use temporal difference learning

Critic

Value-based, works sort of like DQN

Quick review

Q-Learning

DQN

REINFORCE

Q Actor-Critic

A2C

Ability to generalize values in state space

Ability to control in continuous action spaces using stochastic policy

One step updates

Reduce variability in gradients

Advantage vs action value

A(S, A)

Q(S, A)

V(S)

Will lead to gradients with high variance, i.e. will take much longer to converge

Baseline = V(s)

Q(S, A)

V(S)

Will be much quicker to converge!

Advantage Actor-Critic (A2C)

Common layers

X

blank

O

state, s

Policy net

Value net

𝛑(a|s)

for each action a

V(s)

Actor

Policy-based like REINFORCE

Can now use temporal difference learning and baseline:

Critic

Value-based, now learns value of states instead of state-action pairs

Part 3

Current state of reinforcement learning

Current state of reinforcement learning

Mostly in academia or research-focused companies, e.g. DeepMind, OpenAI

• Most impressive progress has been made in games

​

​

​

¹ Irpan, Alex. “Deep Reinforcement Learning Doesn't Work Yet.” Sorta Insightful, 14 Feb. 2018.

Barriers to entry:

• Too much real-world experience required
• Simulation is often not realistic enough
• Poor convergence properties
• There has not been enough development in transfer learning for RL models
• Models do not generalize well outside of what they are trained on

Driverless car, robotics, etc. still largely not using RL.

• “The rule-of-thumb is that except in rare cases, domain-specific algorithms work faster and better than reinforcement learning.”¹

Promising applications of RL (that aren’t games)

Energy

Finance

Healthcare

Some aspects of robotics

NLP

Computer systems

Traffic light control

Assisting GANs

Neural network architecture

Computer vision

Education

Recommendation systems

Science & Math

References

Clark, Jack. “Faulty Reward Functions in the Wild.” OpenAI, 21 Dec. 2016.

​

Friedman, Lex (2015). MIT: Introduction to Deep Reinforcement Learning. https://www.youtube.com/watch?v=zR11FLZ-O9M

​

Fullstack Academy (2017). Monte Carlo Tree Search Tutorial. https://www.youtube.com/watch?v=Fbs4lnGLS8M

​

Irpan, Alex. “Deep Reinforcement Learning Doesn't Work Yet.” Sorta Insightful, 14 Feb. 2018.

​

Lapan, M. (2018). Deep reinforcement learning hands-on: Apply modern RL methods, with deep Q-networks, value iteration, policy gradients, TRPO, AlphaGo Zero and more. Birmingham, UK: Packt Publishing.

​

Silver, David (2015). University College London Reinforcement Learning Course. Lecture 7: Policy Gradient Methods

​

Towards Data Science. “Applications of Reinforcement Learning in Real World”, 1 Aug 2018.

​

Sutton, R. S., & Barto, A. G. (2018). Reinforcement learning: An introduction. Cambridge, MA: The MIT Press.

​