Reinforcement Learning and Q-Learning

Markov Decision Processes solved the planning problem: given $P(s' \mid s, a)$ and $R(s)$, value iteration returns an optimal policy. But an agent dropped into an unfamiliar environment has neither. It does not know what its actions do, or where the rewards are. It has to find out by acting.

That is the reinforcement learning problem, and it is much closer to the situation any real agent is in.

A. Learning from the difference between successive estimates

Suppose the agent is following some policy $\pi$ in Russell & Norvig's $4 \times 3$ world, where each step costs $R = -0.04$ and rewards are not discounted ($\gamma = 1$), and currently believes $U^{\pi}(1,3) = 0.84$ and $U^{\pi}(2,3) = 0.92$. It then observes a transition from $(1,3)$ to $(2,3)$. If that transition happened every time, the two utilities would have to satisfy the Bellman relation for $\pi$, $U^{\pi}(1,3) = -0.04 + 0.92 = 0.88$ - and they do not quite. The estimate at $(1,3)$ looks a little low. (With the $\gamma = 0.9$ used later in this article the target would be $0.788$, and the same estimate would look high.)

The fix is to nudge it toward consistency. On observing a transition $s \to s'$:

$$U^{\pi}(s) \leftarrow U^{\pi}(s) + \alpha\big(R(s) + \gamma\, U^{\pi}(s') - U^{\pi}(s)\big),$$

where $\alpha$ is a learning rate. This is the temporal-difference (TD) update, so called because it is driven by the difference between utility estimates at successive time steps.

The bracketed quantity is the TD error: what we just observed, $R(s) + \gamma U(s')$, minus what we previously believed, $U(s)$. Zero error means our estimates are locally consistent and nothing changes. All TD methods work this way - adjusting estimates toward the equilibrium that holds when they are correct.

Why this is remarkable. The update mentions no probabilities at all. The agent never estimates $P(s' \mid s, a)$. Yet because transitions are sampled from the true model, frequent transitions drive the update proportionally often, and the averaging happens implicitly. The model is never learned, only obeyed.

B. From utilities to action values

TD as written learns $U^{\pi}(s)$ - how good a state is. That is not directly actionable: to choose, an agent must know how good each available action is, and converting $U$ into a choice requires knowing where actions lead, which is exactly the model we do not have.

So learn action values instead. Define $Q(s, a)$ as the expected utility of taking action $a$ in state $s$. The two are related by

$$U(s) = \max_{a} Q(s, a),$$

and an agent holding $Q$ can act without any model at all: look up the row for the current state and take the largest entry.

C. The Q-learning update

$$Q(s, a) \leftarrow Q(s, a) + \alpha\Big(R(s) + \gamma \max_{a'} Q(s', a') - Q(s, a)\Big)$$

This is applied whenever action $a$ is taken in $s$ and leads to $s'$. It is the TD idea with the state utility replaced by the best action value available at the next state.

The $\max_{a'}$ is the crucial detail. The agent backs up the value of the best action at $s'$, regardless of what it actually does next. That makes Q-learning off-policy: it learns about the optimal policy while behaving according to some other, more exploratory one.

Its close relative SARSA - for state, action, reward, state, action - instead uses the action $a'$ actually taken:

$$Q(s, a) \leftarrow Q(s, a) + \alpha\big(R(s) + \gamma\, Q(s', a') - Q(s, a)\big).$$

That makes SARSA on-policy: it learns the value of the policy being followed, exploration and all. For a purely greedy agent the two coincide. When exploration is happening they differ, and the difference matters: Q-learning can learn good behaviour even while guided by a random or adversarial exploration policy, whereas SARSA is more realistic when the policy is partly out of the agent's control - for instance when other agents share the environment.

D. The mechanics, step by step

Take the world from the previous article: non-terminal states $s_1, s_2$ with $R(s) = -0.04$, terminals GOAL $(+1)$ and PIT $(-1)$, and $\gamma = 0.9$. All $Q$ values start at zero. Use $\alpha = 0.5$.

Suppose the agent goes $s_1 \to s_2 \to$ GOAL, twice.

Update 1, $(s_1, \text{Right}) \to s_2$. Every $Q(s_2, \cdot)$ is still $0$:

$$Q(s_1, \text{Right}) \leftarrow 0 + 0.5\big(-0.04 + 0.9 \times 0 - 0\big) = -0.02 .$$

Update 2, $(s_2, \text{Right}) \to$ GOAL, whose value is $+1$:

$$Q(s_2, \text{Right}) \leftarrow 0 + 0.5\big(-0.04 + 0.9 \times 1 - 0\big) = 0.5 \times 0.86 = 0.43 .$$

Update 3, $(s_1, \text{Right}) \to s_2$ again - but now $s_2$ has value:

$$Q(s_1, \text{Right}) \leftarrow -0.02 + 0.5\big(-0.04 + 0.9 \times 0.43 - (-0.02)\big) = 0.1635 .$$

Update 4, $(s_2, \text{Right}) \to$ GOAL: $0.43 + 0.5(0.86 - 0.43) = 0.645$.

Notice how value propagates backwards: nothing useful reaches $s_1$ until $s_2$ has learned something first.

This particular sequence converges to the wrong number, and that is the point. Both episodes above were hand-picked to reach GOAL. Repeating only them drives $Q(s_2, \text{Right})$ toward $-0.04 + 0.9(1) = 0.86$ - the value of a Right that always succeeds. But Right only reaches GOAL 80% of the time; the other 20% it falls into PIT. The correct value is $-0.04 + 0.9\,(0.8 \times 1 + 0.2 \times (-1)) = 0.5$. Q-learning gets there only because real experience samples both outcomes in the right proportion. A biased sample gives a biased answer.

E. Exploration versus exploitation

An agent that always takes its current best action may never discover a better one. An agent that always acts randomly learns about everything and exploits nothing. This is the exploration–exploitation tradeoff.

The simplest workable answer is $\varepsilon$-greedy: act greedily with probability $1 - \varepsilon$, act randomly with probability $\varepsilon$. Provided $\varepsilon$ decays over time, the agent explores enough early to find the good actions and exploits enough later to accumulate reward. More refined schemes use an exploration function that inflates the value of state–action pairs that have been tried rarely, which requires keeping visit counts.

The figure below runs the same update in a slightly different world, so its numbers are not the table's: two states A and B, a terminal worth $+1$ reached by going right from B, and a Right that fails 20% of the time by slipping back to A rather than into a pit. It starts with five scripted trips that all succeed, in the order B, B, A, B, A. Step through them and watch the order rather than the numbers. A sits at exactly zero for the first two trips, because neither starts from A, and its first update then finds B already holding $0.42$ to learn from. Then sample the environment the agent really faces. A diet of nothing but successful trips converges on 0.8600 for B - the value of a world where going right always works. Only slipping teaches otherwise.

F. Does it actually recover the planned optimum?

The previous article computed the exact answer by planning with full knowledge of the model: $U(s_1) = 0.3902$ and $U(s_2) = 0.5000$. A Q-learner never sees that model. Run it for 200,000 episodes with $\varepsilon = 0.2$ and a decaying learning rate:

It prints:

Taking $U(s) = \max_a Q(s,a)$ gives $0.3847$ and $0.4926$, against the planned $0.3902$ and $0.5000$ - and the greedy policy read off these values is Right in both states, exactly the policy value iteration produced. The agent recovered the optimal behaviour without ever being told what its actions do.

The small residual gap is honest sampling error, not a bug: the estimates are averages over finitely many sampled transitions, and they tighten slowly as the learning rate decays. This is the standard tradeoff - Q-learning asks far less of you than value iteration, and pays for it in sample efficiency.

G. The limits

Everything here assumes a $Q$ table with one entry per state–action pair. That is fine for four entries and hopeless for chess or for any environment with continuous state. Real problems need generalisation: approximating $Q$ with a parameterised function rather than enumerating it, which is where reinforcement learning meets the rest of machine learning.

A second limitation is that Q-learning agents cannot look ahead. Because they do not know where actions lead, they cannot plan a sequence the way a model-based agent can - they can only compare the action values they have learned. Freedom from the model is bought at the cost of foresight.

Key takeaways

• Reinforcement learning drops the MDP assumption that the model is known; the agent learns from experience instead.
• The TD update nudges estimates toward local consistency, using no probabilities - sampling supplies the averaging implicitly.
• $Q(s,a)$ makes action selection model-free, with $U(s) = \max_a Q(s,a)$.
• The Q-learning rule backs up $\max_{a'} Q(s', a')$, making it off-policy; SARSA backs up the action actually taken and is on-policy.
• Value propagates backwards from rewards, one update per step.
• A biased sample of transitions yields a biased $Q$; correctness relies on experiencing outcomes in their true proportions.
• Our learner reached $0.3847$ and $0.4926$ against the planned $0.3902$ and $0.5000$, recovering the optimal policy with no model.
• Tabular $Q$ does not scale; generalisation is the bridge to the rest of ML.

What's next

The exploration problem, the sampling error above, and the credit-assignment question all have an information-theoretic flavour. Entropy and Information makes the notion of "how much uncertainty is left" precise.