Carrot and Stick - Part 3 - Deep Q 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:
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:
This is the squared TD error — the same δ 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 + γ max 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. With a neural network, highly correlated consecutive transitions cause the weights to overfit to recent experience and forget the rest.
The fix is a replay buffer: a queue of recent transitions. After every step, the transition is stored in the buffer. Training happens by sampling a random mini-batch from the buffer, not by using the latest transition directly.
Random sampling breaks the correlation between consecutive updates and reuses each transition multiple times, making training far more stable.
Target Network
The loss function above uses the same network to compute both the prediction Q(s_t, a_t; θ) and the target max Q(s{t+1}, a’; θ)_. Every gradient step shifts the network weights, which immediately shifts the target — like trying to hit a target that moves every time you fire.
The fix is a target network: a second copy of the network whose weights are updated less frequently (every N steps, not every step). The target is computed using this frozen copy, so it stays stable long enough for the main network to converge toward it.
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 same TD formula as before, now computed in batch. 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.