Carrot and Stick - Part 2 - Q Learning
From Theory to Practice
In the previous post we introduced the Carrot and Stick framework and walked through the Hill Climb algorithm on the CartPole environment. Hill Climb is simple and surprisingly effective, but it has a fundamental limitation: it treats the entire episode as a single experience. It only asks “did this episode go well?” and updates accordingly — it never asks “which specific decisions in the episode were good, and which were bad?”.
Q Learning takes a different approach. Instead of waiting until the end of an episode to learn, it learns at every single step. It keeps a running estimate of how valuable each action is in each state, and updates that estimate the moment new information arrives.
In this post we will go into depth on how Q Learning works, how to implement it with Carrot and Stick, and compare it to the Hill Climb algorithm.
Q Learning in Theory
The Q-Value
The central idea of Q Learning is the Q-value — a number that estimates the total future reward you can expect if you take action a in state s and then follow the optimal policy from that point onwards.
We write it as Q(s, a).
Think of it as a lookup table — rows are states, columns are actions, and each cell holds the agent’s current best estimate of how good that (state, action) pair is. At the start, all values are zero. After many episodes, the table fills in with meaningful estimates, and the agent can simply look up the best action for any state it finds itself in.
Temporal Difference
Hill Climb learns at the end of each episode — it uses the total cumulative reward as its signal. This is called a Monte Carlo approach, and it has a drawback: you have to wait until the episode ends to learn anything, and the signal you get is blurry — the total reward does not tell you which of the hundreds of steps along the way was responsible for the outcome.
Q Learning uses Temporal Difference (TD) learning instead. It updates after every single step, using the reward just received plus its own current estimate of the next state’s value. It does not wait for the episode to end — it bootstraps from what it already knows.
The key insight is the TD error — the difference between what you expected and what you got:
Where:
- r_t is the reward received at step t
- γ (gamma) is the discount factor — how much future rewards are worth relative to immediate ones (between 0 and 1)
- max Q(s’, a’) is the best Q-value available in the next state
- Q(s, a) is the current estimate for the action taken
If the TD error is positive, the outcome was better than expected — increase Q(s, a). If it is negative, the outcome was worse — decrease it.
The Update Rule
Since δ_t is already defined, the update rule is simply:
Scale the error by a learning rate α and nudge the current estimate in that direction. Expanding δ_t gives the full form:
This is applied after every step in every episode. Over time, the Q-values converge to their true values and the agent learns the optimal policy.
Exploration
A greedy agent — one that always picks the action with the highest Q-value — stops exploring too early. Early in training, Q-values are poor estimates. If the agent commits to them too soon it may never discover better actions.
The standard solution is ε-greedy: with probability ε, take a random action; otherwise take the greedy action. ε starts high (explore a lot) and decays over episodes as the Q-values become more reliable.
Implementation
Now let’s put this into the Carrot and Stick framework.
The CartPole state space is continuous — four real-valued features (cart position, cart velocity, pole angle, pole angular velocity). A Q-table requires a finite number of states, so we discretize each feature into bins before storing or looking up Q-values.
The Decision Model
The decision model holds the Q-table and implements get_action (ε-greedy), get_random_action (pure exploration), and update_model (TD update).
class QLearningDecisionModel:
def __init__(self, number_of_actions, number_of_bins=10,
alpha=0.1, gamma=0.99, epsilon=1.0, epsilon_decay=0.995):
self.number_of_actions = number_of_actions
self.number_of_bins = number_of_bins
self.alpha = alpha
self.gamma = gamma
self.epsilon = epsilon
self.epsilon_decay = epsilon_decay
self.epsilon_min = 0.01
self.q_table = dict()
def _discretize(self, state):
# Bin each continuous feature into one of number_of_bins buckets
bins = np.linspace(-3, 3, self.number_of_bins)
return tuple(np.digitize(s, bins) for s in state)
def _get_q_values(self, state):
key = self._discretize(state)
if key not in self.q_table:
self.q_table[key] = np.zeros(self.number_of_actions)
return self.q_table[key]
def get_action(self, state):
if np.random.rand() < self.epsilon:
return self.get_random_action()
return int(np.argmax(self._get_q_values(state)))
def get_random_action(self):
return np.random.randint(self.number_of_actions)
def update_model(self, transition: Transition):
state, action, reward, next_state, done = transition
q_values = self._get_q_values(state)
next_q_values = self._get_q_values(next_state) if not done else np.zeros(self.number_of_actions)
td_target = reward + self.gamma * np.max(next_q_values)
td_error = td_target - q_values[action]
q_values[action] += self.alpha * td_error
# Decay epsilon
self.epsilon = max(self.epsilon * self.epsilon_decay, self.epsilon_min)
A few things to note. The Q-table is a dictionary keyed by the discretized state tuple — this is more memory-efficient than a full multi-dimensional array when the state space is large and most states are never visited. Epsilon decays multiplicatively after every update so the agent gradually shifts from exploration to exploitation as it gains experience.
The Agent
The agent is straightforward — it delegates to the decision model and packages the transition for it. The key difference from Hill Climb is that reinforce is called at every step, not just at episode end.
class QLearningAgent:
def __init__(self, decision_model):
self.decision_model = decision_model
def get_action(self, state):
return self.decision_model.get_action(state)
def reinforce(self, transition: Transition):
self.decision_model.update_model(transition)
Running the Game
The game loop is similar to Hill Climb, with one important change: we now pass the full transition — current state, action, reward, next state, and done signal — to reinforce at every step, not just at episode end.
def run(self):
rewards = dict()
for episode in range(1, self.episodes + 1):
total_reward = 0
state = self.world.reset()
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:
rewards[episode] = total_reward
self.best_total_reward = max(total_reward, self.best_total_reward)
print('Episode {0} done. Total: {1}, Best: {2}'.format(
episode, total_reward, self.best_total_reward))
break
score_interval = 50
print('Average reward of last {0} runs: {1}'.format(
score_interval,
sum(list(rewards.values())[-score_interval:]) / score_interval))
return rewards
Results
The objective is to balance the pole for as long as possible. A perfect episode in CartPole scores 200 — the pole stays upright for 200 steps.
Hill Climb starts with a random policy and gradually improves by randomly perturbing the weight matrix each episode. It can reach good performance quickly but plateaus — once it finds a decent policy it tends to stay close to it.
Q Learning starts knowing nothing and explores heavily — with ε near 1.0, the agent takes mostly random actions. As episodes accumulate and ε decays, the Q-table fills in with meaningful estimates, and performance improves. On CartPole, however, it never catches Hill Climb. The reason is the discretization: to use a Q-table, we must divide each continuous feature into discrete bins. Two states that are physically different but fall into the same bin look identical to the agent — this is aliasing. And when a feature value exceeds the bin range, it gets mapped to the boundary bin regardless of how extreme it is — this is clipping. Both artefacts blur the agent’s view of the world and prevent the Q-table from representing the policy precisely enough to match Hill Climb’s linear approximation.
On CartPole, Hill Climb wins on both counts — it converges faster and reaches a higher final reward. This is not because Q Learning is a worse algorithm, but because the problem is a poor fit for a discretized Q-table.
The chart below shows this directly — 50 independent runs of each algorithm, 300 episodes each, with the shaded bands showing the spread across runs:
Does the Algorithm Matter?
CartPole is a specific kind of problem: the state is continuous, and the right action at any point depends on a smooth combination of four real-valued features. The optimal policy is nearly linear — push right when the pole leans right, push left when it leans left. Hill Climb searches directly in the space of linear weight matrices, so it is accidentally solving exactly the right kind of problem.
Q Learning’s tabular approach forces a discretization of the continuous state space into bins. That introduces aliasing — states that are physically different but land in the same bin look identical to the agent — and clipping, where extreme feature values all map to the same boundary bin. These artefacts hurt Q Learning on CartPole specifically.
To see how the algorithms behave when the problem structure changes, consider two other environments.
Simple GridWorld is a 5×5 grid. The agent starts in the top-left corner and must reach the bottom-right. There are no holes — every cell is safe. The state is a single integer (the grid position), which is naturally discrete, so there is no binning artefact. The optimal policy is mostly directional — move right or down — which is simple enough that Hill Climb can learn something useful, but Q Learning’s state-level precision gives it a clear edge in final reward.
Putting both together:
| Environment | State space | Optimal policy shape | Winner |
|---|---|---|---|
| CartPole | Continuous | Linear | Hill Climb |
| Simple GridWorld | Discrete | Mostly directional | Both, Q Learning more efficient |
The pattern is not that one algorithm is better. It is that each algorithm has a structural match to a class of problems. Hill Climb works when a linear function of the state is enough to make good decisions. Q Learning works when the state space is naturally discrete and the policy is too irregular for a linear function to approximate.
Neither works well when the state space is large and continuous and the policy is complex. CartPole is manageable with bins, but scaling to environments with dozens of features or image inputs makes the Q-table grow exponentially and the aliasing problem unsolvable by adding more bins.
Conclusion and Next Steps
In this post we covered Q Learning from the ground up — the Q-value, Temporal Difference learning, the update rule, ε-greedy exploration, and a full implementation inside the Carrot and Stick framework. We also saw that Q Learning is not universally better than Hill Climb — the right algorithm depends on the structure of the problem.
The limitation that remains is scale. Both tabular Q Learning and Hill Climb break down when the state space is large and continuous and the policy is genuinely complex. The answer to this is to replace the Q-table with a neural network that approximates Q-values directly from raw state features — no binning, no aliasing, no table explosion. This is Deep Q Learning, and it is what allows reinforcement learning to scale to environments like Atari games, robotic control, and beyond. That is where we are headed next.