Human-level control through deep reinforcement learning

Gianluca Peri, PhD Student Unifi

​

mainly from Google DeepMind - Nature - 2015

Chapter I - Introduction

R. Sutton & A.Barto, Reinforcement Learning: An Introduction, 2018.

​

C. Watkins & P. Dayan, Q-learning, 1992

​

V. Mnih et al, Playing Atari with Deep Reinforcement Learning, 2013

​

​

Reinforcement

Learning

Learning paradigm useful in contexts interpretable as agent-environment

Formally:

​

• The loss is not well defined for each sample

​

• Different performances lead to different samples

​

​

​

​

​

Note: agents, states, actions, and policies

Agent

Equipped with policy

​

Environment

Defines all possible states

1 Game ≡ 1 Episode

We want to find the best policy!

Of course there is no best policy a priori, instead it depends on the reward signal.

We must specify what we want from the agent: to do this any state of the environment can be associated with a reward signal R(s). We can think of states without reward as ones with reward set to zero.

​

The best policy will be the one maximizing the expected cumulative reward!

​

​

Finding the best policy is easy!

(on paper)

We define the state-action value function q(s,a): it is defined as the expected cumulative reward of being in the state s and performing the action a.

​

Once we have q(s,a) the best policy π(a|s) is simply the one assigning probability 1 to:

But the problem now is how to find q(s,a)

A priori we don’t know the probabilities needed to compute the expectation value, and even if we knew them the state-action space is almost always too big to compute the expectation value anyway!

Q-learning

Id est: a smart method for approximating the value of the state-action value function

When the spaces of states and actions are discrete and finite the Q-function becomes a Q-table (initialized at random!).

From the Q-table we can extract a (training) policy by normalizing the rows of the Q-table. We choose to do it via epsilon greedy policy implementation:

Q-learning

Id est: a smart method for approximating the value of the state-action value function

The elements of the Q-table are updated, at every move, via the Q-learning algorithm:

But what if the spaces are not discrete? Or simply too big to handle with a table?

The use of this algorithm is motivated by the Q-learning convergence theorem (Watkins and Dayan, 1992), that proves the convergence of this algorithm to the optimal policy in the limit of infinite exploration.

Deep Q-learning

A good idea to handle continuous (or simply too big) state spaces.

The idea is simply get the state-action value function through a neural network instead of relying on a lookup table.

In practice it generates one row of the new infinite Q-table. Notice that the action space is still assumed finite.

But the problem becomes how to adapt the Q-learning update rule to this new context!

Chapter II - The paper

How to train a deep Q-network (without instability issues)

The Experience Replay Trick

A trick to turn our RL problem into a regression one.

1. Start with a random Q-network

​

• Play for a bit, recording s, a, r , ŷ(a|s), ŷ(a’|s’) for each game state.

​

• Once we have enough memory build a regression batch with the function characteristic of Q-learning optimization

​

​

​

​

​

​

• Train the Q-network with a MSE loss on this batch (shuffled)

​

• Repeat from 2.

But this is not all!

Stop moving the target! (for a bit)

The second key idea needed to avoid instabilities during training.

We must also fix the network that builds the regression target, and update it only every C steps, with C a not too small number.

Final version of the algorithm’s loss:

• MSE loss
• Training step on minibatch U(D) made with experience replay
• 𝜶 set to 1
• The network under training has parameters 𝜃, while network used for target building has the old parameters 𝜃^—

That’s it! End of the theory! Let’s see the results.

Note: details of DQN implementation

Performance of DQN on Atari Games

100% represents the performance of a professional human game tester. 75% is chosen to represent the mean performance of a non professional human player.

Thanks for the

attention!