Deep Q-Learning

Motivation

What is deep Q-learning, and why do we want to use it?

Brief History

Deep Q-learning was introduced in 2015 by Google's DeepMind in a Nature article called Human-level control through deep reinforcement learning. DeepMind used Q-learning 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 Q-table, deep Q-learning approximates a Q-function. Unlike the rows of a table, a function is continuous, so even if we predict for a value we have never seen before in the state space, the Q-function will provide an informed estimate, while the Q-table would have no information. There is no need to discretize our data into arbitrary, independent buckets.

Can handle high-dimensional data. Deep networks can use convolutional layers and other trickery to extract features from high-dimensional data. Table-based Q-learning would fail miserably at this task, as the curse of dimensionality leaves us with gigantic state space to explore.

Stock prediction

How might we use deep Q-learning 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 Q-learning is a much more natural fit to the trading problem than the Q-table 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 Q-learning, it is imperative you first have an understanding of normal, table-based Q-learning. And even if you do, read over this recipe so that you will understand what changes when I reference it later:

Table-based Q-learning

Initialization step

1. Define a table Q with a row for each state and a column for each action. We can index into Q with Q(s,a). The value at each index will be the expected utility of being in state s and taking action a. Initialize this table with small, random values.
2. Define exploration probability 0 < p <= 1

Training step

1. Be in state s
2. With probability p, take action a = argmax_a(Q(s,a)). Otherwise, take a random action from the action space.
3. Take action a and witness the reward r and the new state you are in s'.
4. This unit of training has yielding 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*Q(s',a))
5. Multiply p by some discount factor (perhaps .999).

Repeat the above steps until the reward achieved by the agent converges and no longer improves.