Deep QLearning
Contents
Motivation
What is deep Qlearning, and why do we want to use it?
Brief History
Deep Qlearning was introduced in 2015 by Google's DeepMind in a Nature article called Humanlevel control through deep reinforcement learning. DeepMind used Qlearning backed by a deep neural network to train an agent to play Atari games from raw pixel data  often outperforming humans. Previous attempts to combine reinforcement learning with neural networks had largely failed due to unstable learning. To address these instabilities, DeepMind introduced a mechanism by which the algorithm stores all of the agent's experiences and then randomly samples and replays these experiences to provide diverse and decorrelated training data.
Advantages
Continuous state space. Instead of building a Qtable, we use a neural network as part of deep Qlearning to approximate a Qfunction. There is no need to discretize our data into arbitrary, independent buckets. Unlike the rows of a table, a function is continuous  so we predict Qvalues for states that we have never seen before.
Can handle highdimensional data. Deep networks can use convolutional layers and other trickery to extract features from highdimensional data. Tablebased Qlearning would fail miserably at this task, as the curse of dimensionality would leave us with gigantic state space to explore.
Stock prediction
How might we use deep Qlearning to predict stocks? Our actions would be BUY, HOLD, or SELL, and our state space might just be one feature, RETURNS, a continuous value. Deep Qlearning is a much more natural fit to the trading problem than the Qtable implementation we did in class, where we had to discretize our technical indicator values. In theory, technical indicators derived from price are superfluous if we provide our network with raw price data  deep learning should extract these features, and perhaps better ones, on its own.
Intro
To understand deep Qlearning, it is imperative you first have an understanding of normal, tablebased Qlearning. And even if you do, read over this recipe because it will be used as reference later.
Tablebased Qlearning
A Qvalue is the expected future reward of taking an action in a certain state. Qlearning is model free, and so we do not try to learn the transition or immediate reward functions; we are just trying to construct a model of future reward. In this case, that model is a Qtable, which is a simple matrix.
Initialization step (happens only once)
 Define a table
Q
with a row for each state and a column for each action. We will be able to index intoQ
withQ(s,a)
to get the expected utility of being in states
and taking actiona
. Alternatively, you can get an entire row containing Qvalues for each action withQ(s) = [q_{1}, q_{2}, ..., q_{n}]
. Initialize this table with small, random values.  Define exploration probability
0 <= p <= 1
Training step
 Be in state
s
 With probability
p
, choose a random actiona
from the action space (explore). Otherwise, choose actiona = argmax_{a}(Q(s,a))
(exploit).  Take action
a
and witness the rewardr
and the new state you are ins'
.  This unit of training has yielded an experience tuple 
<s, a, s', r>
. Using this experience tuple, perform value iteration with Bellman's equation.
Legend: gamma = discount rate, alpha = learning rate.
Q(s,a) = (1  alpha)Q(s,a) + (alpha)(r + gamma*max(Q(s')))

Multiply
p
by some discount factor (perhaps .999).
Loop the above training steps until your epoch completes. Keep doing more epochs (reset to initial state) until the reward achieved by your agent converges and no longer improves. Note that the Qtable persists between epochs.
Deep QLearning Algorithm
Now that we have established the vanilla, tablebased way of doing things, here is the shiny new deep Qlearning algorithm. Differences from the tablebased algorithm are highlighted in blue.
The main differences are the presence of a neural network backing the Qfunction, and the experience replay bucket. Experience replay works very much like dynaq learning. We store experience tuples and later randomly sample from our bucket and train off those examples. This enables us to train off of I.I.D. experience tuples rather than just training off of sequential data, which is highly correlated.
Initialization step (happens only once)
 Define a neural network
Q
with an input node for each feature and an output node for each action. The hidden layers are defined however you like. Ultimately, providing this network with current states = [feature_{1}, feature_{2}, ..., feature_{n}]
as input should generate the Qvalues of each action[q_{1}, q_{2}, ..., q_{n}]
as output  in other words,Q(s) = [q_{1}, q_{2}, ..., q_{n}]
. Just as before,Q(s,a)
is the Qvalue of taking actiona
in states
. Initialize this table with small, random values. Picking the right activation functions is critical to success  the output should be a linear activation function (outputs need to be continuous and unbounded), and the hidden layer activations should perhaps be ReLu. The loss function is also an important hyperparameter, try meansquared error to start.  Define exploration probability
0 <= p <= 1
 Define a deque of some size. This will henceforth be referred to as
the bucket
. The bucket will hold our historical data for experience replay.
Training step
 Be in state
s
 With probability
p
, choose a random actiona
from the action space (explore). Otherwise, choose actiona = argmax_{a}(Q(s,a))
(exploit).  Take action
a
and witness the rewardr
and the new state you are ins'
.  This unit of training has yielded an experience tuple 
<s, a, s', r>
. Add this experience tuple to the bucket. If your bucket overflows its size, remove the oldest entry.  Experience replay step. If you have more than
BATCH_SIZE
(usually 32) entries in the bucket, sampleBATCH_SIZE
experience tuples from the bucket without replacement. For each sampled tuple<s, a, s', r>
, generate a new training instance with xvalues
. The yvalue of each instance is where things get a little complicated, so pay attention. Let the variableP = Q(s)
, all current Qvalue predictions for all actions. If thea
from our experience tuple is the i^{th} action in the neural net, then we update only the Qvalue corresponding toa
withP[i] = r + gamma*max(Q(s'))
. The yvalue of each sample is set to its respectiveP
, and the model is updated with a training session on just these samples.
Loop the above training steps until your epoch completes. Keep doing more epochs (reset to initial state) until the reward achieved by your agent converges and no longer improves. Note that the neural network weights persist between epochs.
Advanced Deep QLearning
DQNs tend not to be stable. Because the loss is calculated from the same network that weights are applied to, you tend to see oscillations in policies. Think of this like a cat chasing its own tail. There are a few tricks you can use to mitigate these problems.
 Target network. Instead of calculating targets with
P[i] = r + gamma*max(Q(s'))
, we have a separate target networkQ~
that we will use inP[i] = r + gamma*max(Q~(s'))
.Q~
has a structure identical toQ
. Every 1000 or so training iterations, we updateQ~
's weight to be the same asQ
's weights. In this way, there will be reduced correlation betweenQ~
andQ
, mitigating the aforementioned catchasingtail scenario.  Double Qlearning. One problem in the DQN algorithm is that the agent tends to overestimate the Qfunction value, due to the max in the formula used to set targets:
P[i] = r + gamma*max(Q(s'))
. The solution is to use two Qfunctions, Q_{1} and Q_{2}, which are independently learned. One function is then used to determine the maximizing action and second to estimate its value. For our purposes, the target networkQ~
is relatively independent ofQ
, so we can useQ
andQ~
as our networks for double Qlearning. So our update now becomesP[i] = r + gamma*Q~(s',argmax_{a}(Q(s',a))
.
Notes
Hyperparameters:
 Network architecture
 Weight initilizations (glorot, he...)
 Network architecture
 Optimizer
 Learning rate
 Bucket size
 Sample training batch size
 Gamma
 Explore starting probability
 Explore ending probability
 Explore probability decay rate
 Target network update interval
Resources
Cartpole DQN implementation
https://gist.github.com/tsunera/edd306ddeefebe4afb1efceefbc3f953
Another explanation + algorithm for deep Qlearning
http://neuro.cs.ut.ee/demystifyingdeepreinforcementlearning/
A full tutorial on how to build a DQN from scratch with keras + gym:
https://jaromiru.com/2016/09/27/letsmakeadqntheory/