Carrot and Stick - Part 3 - Deep Q Learning

01 Mar 2020 in Machine Learning

When the Table Gets Too Big

In the previous post we saw that Q Learning can outperform Hill Climb when the state space is naturally discrete and the optimal policy is non-linear. But we also saw its limits: on CartPole, a continuous environment, the discretization required to build a Q-table introduced enough noise that Hill Climb won anyway.

The root problem is the Q-table itself. It stores one number per (state, action) pair. When the state space is continuous — or even just large — the table becomes impractical. CartPole has four continuous features. With 15 bins per feature, the table has 15⁴ = 50,625 possible entries. Add a fifth feature and it is 759,375. Add image pixels as input and it is infinite.

The fix is to stop storing a table and start approximating. Instead of looking up $Q(s, a)$ in a dictionary, we learn a function that takes a state and returns Q-values for all actions. That function is a neural network. This is Deep Q Learning.

From Table to Network

In tabular Q Learning, the Q-table is updated directly: $$Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha \, \delta_t$$

In Deep Q Learning, the network plays the role of the table. We define a network Q(s, a; θ) parameterized by weights θ, and instead of updating a single cell, we perform a gradient descent step to move the network’s output closer to the TD target: $$\mathcal{L}(\theta) = \left( r_t + \gamma \max_{a'} Q(s_{t+1}, a';\, \theta) - Q(s_t, a_t;\, \theta) \right)^2$$

This is the squared TD error — the same $\delta_t$ as before, now used as a loss function. Minimizing it nudges the network weights so that $Q(s_t, a_t)$ moves toward the target $r_t + \gamma \max_{a'} Q(s_{t+1}, a')$.

The structure of everything else stays the same: ε-greedy exploration, a discount factor γ, learning episode by episode. What changes is the representation of Q-values — from a lookup table to a learned function.

Two Tricks That Make It Work

Naively plugging a neural network into Q Learning is unstable. The network is both generating the targets and being trained on them — chasing a moving goal. Two practical tricks fix this.

Experience Replay

In tabular Q Learning, each transition $(s, a, r, s')$ is used once and discarded — the table is updated directly and the transition is no longer needed. With a neural network, this becomes a problem for two reasons.

First, consecutive transitions are highly correlated. Step 47 follows step 46 follows step 45 — the agent is in the same region of the state space, doing the same thing. Training on these in sequence is like studying the same page of a book over and over: the network overfits to recent experience and forgets everything it learned earlier.

Second, a single transition carries very little information. A neural network has thousands of weights; one gradient step on one transition barely moves them. You want to extract more signal from each experience before discarding it.

The fix is a replay buffer: a circular queue that stores the last N transitions. After every step, the new transition is added to the buffer. Training happens by drawing a random mini-batch from the buffer — not from the last step, but from any step stored in memory.

Random sampling solves both problems at once: it breaks the temporal correlation between consecutive updates, and it lets the network see each transition multiple times from different batch contexts, extracting more learning from each experience.

Target Network

The loss function needs a target — the value the network should move toward: $$y_t = r_t + \gamma \max_{a'} Q(s_{t+1}, a';\, \theta)$$

The problem is that $\theta$ — the network weights — appear on both sides. Every gradient step changes $\theta$, which changes the prediction and the target simultaneously. The network is chasing a goal that moves every time it takes a step toward it. In practice this causes oscillation or outright divergence.

The fix is a target network: a second copy of the network with its own weights $\theta^{-}$, held frozen for $N$ steps at a time. The target is computed using this frozen copy: $$y_t = r_t + \gamma \max_{a'} Q(s_{t+1}, a';\, \theta^{-})$$

Only the main network’s weights $\theta$ are updated by gradient descent. Every $N$ steps, the target network is refreshed by copying $\theta$ into $\theta^{-}$. This gives the main network a stable goal to train against, long enough to make consistent progress before the target shifts again.

Implementation

The Carrot and Stick framework already contains a DQNModel that implements both tricks. Here is the core of it.

The Network

A three-layer network maps the raw state features to Q-values for each action:

self.f1   = nn.Linear(number_of_features, 64)
self.f2   = nn.Linear(64, 128)
self.f3   = nn.Linear(128, number_of_actions)
self.relu = nn.ReLU()

The forward pass:

def forward(self, state):
    out = self.relu(self.f1(state))
    out = self.relu(self.f2(out))
    return self.f3(out)

No softmax — the outputs are raw Q-value estimates, not probabilities.

The Replay Buffer

class ReplayMemory:
    def __init__(self, memory_size):
        self.memory   = []
        self.position = 0
        self.memory_size = memory_size

    def push(self, transition):
        if len(self.memory) < self.memory_size:
            self.memory.append(None)
        self.memory[self.position] = transition
        self.position = (self.position + 1) % self.memory_size

    def sample(self, batch_size):
        return random.sample(self.memory, batch_size)

A circular buffer of fixed size — old transitions are overwritten once full. sample returns a random mini-batch for training.

The Training Step

def update_model(self, transition):
    self.replay_memory.push(transition)

    if len(self.replay_memory) > self.batch_size:
        state, action, reward, next_state, done = self.replay_memory.sample(self.batch_size)

        target      = reward + self.gamma * torch.max(self.q_network(next_state), dim=1)[0] * (1 - done)
        prediction  = self.q_network(state).gather(1, action.unsqueeze(1))

        loss = F.mse_loss(prediction.squeeze(), target)
        self.optimizer.zero_grad()
        loss.backward()
        self.optimizer.step()

The target is the Bellman target — the best estimate of the true Q-value, constructed from the immediate reward plus the discounted value of the next state: $y_t = r_t + \gamma \max_{a'} Q(s_{t+1}, a';\, \theta^{-})$. The same TD formula from the theory section, now computed in batch using the frozen target network weights $\theta^{-}$. The prediction is the network’s current estimate for the action that was actually taken. The loss is their squared difference.

The Agent and Game Loop

The agent is identical to QLearningAgent — reinforce is called at every step with the full transition. The game loop does not change at all:

while True:
    action               = self.agent.get_action(state)
    next_state, reward, done = self.world.interact_with_world(action)

    transition = Transition(state, action, reward, next_state, done)
    self.agent.reinforce(transition)

    state = next_state
    total_reward += reward

    if done:
        break

The only thing that changed from Q Learning to Deep Q Learning is what happens inside reinforce.

Results

On CartPole, DQN handles the continuous state space directly — no binning, no aliasing, no clipping. It takes longer to warm up than Hill Climb (the replay buffer needs to fill before training starts, and the network needs enough experience to produce useful Q-value estimates), but it converges to near-perfect performance and stays there.

Hill Climb finds a good linear policy quickly but plateaus — it cannot improve beyond what a linear function of the raw features can represent. DQN has no such ceiling.

Conclusion and Next Steps

Deep Q Learning replaces the Q-table with a neural network, unlocking environments where the state space is too large or too continuous for tabular methods. The two stabilizing tricks — experience replay and a target network — are what make the training actually converge.

The algorithm that follows from this reasoning has been used to play Atari games at superhuman level, control robotic arms, and optimize complex systems — all from raw observations, with no hand-crafted features.

What we have built here is the foundation. From this point, the extensions are: Double DQN (decouple action selection from Q-value estimation to reduce overestimation), Dueling DQN (split the network into value and advantage streams), and Prioritized Experience Replay (sample important transitions more often). Each is a targeted fix for a specific weakness of the base algorithm.

But that is a story for another post.