Reinforcement Learning

The decision-theory lesson handed the agent a finished Markov decision process: it knew the transition model $P(s^{\prime }\mid s,a)$, it knew the reward $R(s)$, and its only job was to compute an optimal policy by value or policy iteration. That is planning. Reinforcement learning removes the one thing planning takes for granted. The agent still lives in an MDP — states, actions, transitions, rewards, a discount, an optimal policy — but it is told none of the dynamics and none of the rewards in advance. It learns to act well from the only thing it actually receives: a stream of states, the actions it took, and the scalar rewards that followed.¹

Consider a game whose rules nobody explained. The agent plays a hundred moves and learns only at the end that it lost. No teacher labelled a single move good or bad; the only signal was a delayed verdict. Learning to play well anyway — assigning credit backward through a long chain of actions to the ones that actually mattered — is the reinforcement learning problem.¹ The reward is treated as part of the percept, and the agent is hardwired only to recognise which part of its input is the reward. Everything else it must infer.

Three agent designs recur, distinguished by what they choose to learn:

The utility-based agent can only choose actions if it also has a model, because knowing that a state is worth $0.9$ tells you nothing about which action reaches it. A Q-learning agent sidesteps this: $Q(s,a)$ scores the action itself, so the agent compares its options without ever predicting their outcomes — but for the same reason it cannot look ahead. Which representation is best is one of the oldest open questions in AI, and we return to it. The chapter splits along a second axis: passive learning, where the policy is fixed and the task is to evaluate it, and active learning, where the agent must also decide what to do.

Passive reinforcement learning

Start with the easier half. In passive learning the agent's policy $\pi$ is fixed — in state $s$ it always executes $\pi (s)$ — and the only goal is to learn how good that policy is, its utility function $U^{\pi }(s)$. This is the policy evaluation step of policy iteration, except the agent cannot compute it in closed form: it does not know $P$ or $R$.² The utility is the expected discounted return obtained by following $\pi$ from $s$:

where $S_t$ is the (random) state reached at time $t$. The agent runs a set of trials: from a start state it acts under $\pi$ until it hits a terminal state, observing the state and reward at each step, then repeats. A trial in the standard $4\times 3$ grid world might read

each state subscripted with the reward received there. Three methods turn these trials into estimates of $U^{\pi }$.

Direct utility estimation

The simplest idea reduces RL to something already understood. The utility of a state is the expected total reward from that state onward — the reward-to-go — and each trial supplies a sample of that quantity for every state it passes through. Average the samples per state, keep a running mean, and in the limit of infinitely many trials the average converges to the true $U^{\pi }(s)$.³

This is nothing but supervised learning: the input is a state, the output is the observed reward-to-go, and any regression method fits it. But direct estimation throws away the single most useful fact about an MDP — that the utilities of neighbouring states are not independent. They obey the Bellman equation for the fixed policy:

By ignoring the link between a state and its successor, direct estimation searches a hypothesis space far larger than it needs — one full of utility functions that violate Bellman's constraint — so it converges very slowly. If a trial reaches a brand-new state whose successor is already known to be excellent, direct estimation learns nothing about the new state until the trial ends; the Bellman equation would have told it immediately.

Adaptive dynamic programming

The fix is to put the Bellman constraint back. An adaptive dynamic programming (ADP) agent learns the model from experience and then solves the resulting MDP. Because the environment is fully observable, learning the model is itself a supervised problem: each observed transition is an $(s,a)\to s^{\prime }$ example, and the agent estimates $P(s^{\prime }\mid s,a)$ by the frequency with which $s^{\prime }$ follows $a$ in $s$. Plug those estimates and the observed rewards into the fixed-policy Bellman equations and solve — they are linear, so no maximisation is needed — to get the utilities.⁴

ADP makes optimal use of the constraints between states, so it learns as fast as the model itself improves; it is the yardstick against which other passive methods are measured. Its weakness is scale. Solving the Bellman equations means working with a value per state, which is hopeless for large spaces — backgammon would need on the order of $10^{50}$ equations in $10^{50}$ unknowns. Two escapes exist: modified policy iteration re-uses the previous utilities as a warm start after each small model change so a few sweeps suffice, and prioritized sweeping updates only the states whose successors just changed a lot. But the exact method does not scale, which motivates temporal-difference learning.

Temporal-difference learning

ADP solves the whole MDP after every observation. Temporal-difference (TD) learning does the opposite: it adjusts one state's utility, a little, toward the value implied by the single transition just observed — and it never builds a model at all.⁵ Suppose the agent is in $s$ with current estimate $U^{\pi }(s)$, acts, and lands in $s^{\prime }$. If the estimates were exactly consistent they would satisfy the local relation $U^{\pi }(s)=R(s)+\gamma U^{\pi }(s^{\prime })$. They usually don't, and the gap between the two sides is the temporal-difference error. TD nudges $U^{\pi }(s)$ to shrink it:

Here $\alpha$ is a learning rate. The bracketed quantity is the difference between the estimate the agent held and the (bootstrapped) estimate the observed successor now suggests — hence temporal difference. The update looks only at the successor $s^{\prime }$ that actually happened, not at all possible successors weighted by their probabilities as the true Bellman equation would. That is why it needs no model: the environment supplies the connection between neighbouring states in the form of observed transitions, and TD simply reads it off.

TD and ADP are two views of the same goal — make each state's estimate agree with its successors — differing only in bookkeeping. ADP adjusts a state to agree with all its successors weighted by probability and does as many updates as it takes to restore consistency; TD makes one adjustment per observed transition, toward the one successor it saw. The difference vanishes in the average, because over many transitions the observed successors appear in proportion to their true probabilities. TD is noisier and slower per unit of data, but it costs almost nothing per step and needs no model at all. If $\alpha$ is decayed as a state is visited more often, $U^{\pi }(s)$ converges to the correct value.⁵

The three passive methods differ in how much of the MDP structure each exploits, and at what cost.

Active reinforcement learning

A passive agent is handed its policy. An active agent must decide what to do. It can no longer settle for $U^{\pi }$ under a fixed $\pi$; it must learn the utilities of the optimal policy, which obey the full Bellman equation with a maximisation over actions:

An active ADP agent can learn the complete model and solve these equations, then extract an action by one-step look-ahead. The subtle question is what to do with the policy it has learned. Just follow it?

Exploration versus exploitation

No. An agent that always executes the optimal action for its current learned model — a greedy agent — reliably fails. It finds one workable route to the reward, sticks to it, and never discovers a better one, because it never tries the actions that would reveal the better route. What the greedy agent overlooks is that actions do two things at once: they collect reward now, and they gather information that improves the model and so raises future reward. It must trade exploitation — maximising reward under current estimates — against exploration — trying unfamiliar actions to improve those estimates.⁶

Finding the optimal exploration policy is the province of bandit problems and is generally intractable. But a merely reasonable scheme is easy, and one property makes precise what reasonable must mean.

The $1/t$ scheme works but is glacially slow. A better idea is to make untried actions look attractive. Let $U^{+}(s)$ be an optimistic utility estimate and $N(s,a)$ the number of times action $a$ has been tried in $s$, and replace the Bellman update with

The exploration function $f(u,n)$ trades greed (preference for high value $u$) against curiosity (preference for rarely-tried actions, low $n$): it should increase in $u$ and decrease in $n$. A simple choice returns an optimistic constant $R^{+}$ whenever $n<N_e$ and the plain value $u$ otherwise, which forces the agent to try each action at least $N_e$ times before trusting its estimate. Because $U^{+}$ (not the pessimistic $U$) appears on the right-hand side, the optimism propagates backward: states that merely lead toward unexplored regions become attractive too, so the agent is drawn toward the frontier rather than only to actions that are themselves novel. This converges to near-optimal behaviour far faster than $1/t$ — often after a handful of trials.

Two rules everyone actually uses

The $R^{+}/N_e$ exploration function is the principled route, but two simpler rules dominate practice, both borrowed straight from the bandit setting named above: strip the sequential MDP down to one state with several arms, and exploration is the whole problem. AIMA's $1/t$ scheme is the crude ancestor of the first; the second imports the upper-confidence-bound rule from the bandit literature.⁷ Let $\bar{Q}(a)$ be the current estimate of action $a$'s value and $N(a)$ the number of times $a$ has been tried.

$\epsilon$-greedy is blunt: when it explores, it picks any action with equal probability, wasting pulls on arms already known to be bad. UCB — upper confidence bound — spends its exploration where it can do the most good, on actions whose value is uncertain, not merely unfamiliar. It adds an optimism bonus that grows with how little an action has been tried and shrinks as evidence accumulates.

The bonus is not arbitrary. If the rewards for $a$ are bounded, a Hoeffding concentration bound says the true mean lies below $\bar{Q}(a)+\sqrt{\ln t/N(a)}$ with high probability, and that probability tightens as $t$ grows — so the bracket is a genuine high-confidence ceiling on each action's value, and taking the $\arg \max$ over ceilings enacts the optimism. UCB is the exploration rule inside the UCT tree-search that powers modern game-playing (Kocsis and Szepesvári, 2006). The three schemes differ in how they target exploration: $\epsilon$-greedy explores blindly, the $R^{+}/N_e$ function explores until a visit count is met, and UCB explores in proportion to statistical uncertainty.

Q-learning

The active ADP agent still learns a model. Q-learning does away with it. Instead of a utility per state it learns an action-utility function $Q(s,a)$ — the value of doing $a$ in $s$ — related to utilities by $U(s)={\max }_{a}Q(s,a)$.⁸ At equilibrium the Q-values satisfy their own Bellman constraint,

but the temporal-difference version never touches $P$. When action $a$ in $s$ leads to $s^{\prime }$ with reward $R(s)$, Q-learning applies

This is the passive TD update with two changes: it stores values indexed by action, and its target maxes over the successor's actions. That $\max$ lets a state be evaluated purely from the Q-values of its neighbours, with no model of where actions lead.

A full active Q-learner combines this update with an exploration function (the same $f$ as the ADP agent, hence the need to keep visit counts), or more simply with the decaying $\epsilon$-greedy rule defined above.

A worked Q-learning trace

A short numeric trace shows the update at work. Take a corridor of three states, $s_1\to s_2\to s_3$, with $s_3$ terminal. From each non-terminal state the agent can go $right$ (toward $s_3$) or $left$ (back). The reward is $0$ everywhere except on entering $s_3$, which pays $+10$. Use discount $\gamma =0.9$ and learning rate $\alpha =0.5$, and start every Q-value at $0$. The value of reaching the goal propagates backward, one transition per visit.

Step 1 — the agent is in $s_2$, takes $right$, lands in the terminal $s_3$ with reward $10$. The successor is terminal, so ${\max }_{a^{\prime }}Q(s_3,a^{\prime })=0$. The update is

Only this one entry changes; every other Q-value is still $0$. The goal reward has reached $s_2$ but no further.

Step 2 — a new episode: the agent is in $s_1$, takes $right$, lands in $s_2$ with reward $0$. Now the successor $s_2$ is not terminal, and its best action value is ${\max }_{a^{\prime }}Q(s_2,a^{\prime })=Q(s_2,R)=5.0$ from step 1. So

The bootstrap did the work: even though the agent received zero reward on this transition, it raised $Q(s_1,R)$ to $2.25$, because $s_2$ was already known to be worth $5.0$. This propagation is precisely what direct estimation could not do.

Step 3 — the agent visits $s_2$ again, takes $right$ into $s_3$, reward $10$. The same target as step 1, but $Q(s_2,R)$ is no longer $0$:

Each visit moves $Q(s_2,R)$ halfway from its current value toward the target $10$: $0\to 5.0\to 7.5\to 8.75\to \cdots$, converging on the true value $Q^{\ast }(s_2,R)=10$ (reward $10$, then a terminal state worth $0$). The corridor's optimal values are $Q^{\ast }(s_2,R)=10$ and $Q^{\ast }(s_1,R)=0+0.9\cdot 10=9$; the trace is crawling toward them, and it never once used a transition model.

SARSA

Q-learning has a close relative, SARSA (for State-Action-Reward-State-Action). Its update looks almost identical but backs up the value of the action actually taken next, $a^{\prime }$, rather than the best available:

The rule fires on the full quintuple $(s,a,r,s^{\prime },a^{\prime })$ — hence the name. The difference from Q-learning is small but real. Q-learning backs up the best next Q-value regardless of what the agent will actually do, so it pays no attention to the exploration policy: it is off-policy, learning about the greedy policy while behaving by some other (perhaps random) rule. SARSA backs up the value of the action its own policy will really take, so it learns about the policy it is following: it is on-policy.⁸ For a purely greedy agent the two coincide. Under exploration they diverge — Q-learning is more flexible (it can learn good behaviour even under an adversarial exploration policy), while SARSA is more realistic when the policy is partly out of the agent's hands, as when other agents share control.

The entire difference is one symbol in the backup target — a $\max$ versus a sample. The twin backup diagram makes it visible. Both updates take action $a$ in $s$, land in $s^{\prime }$, and back a value into $Q(s,a)$; they part only in which successor Q-value they use. Q-learning takes the maximum over $s^{\prime }$'s actions, ignoring which one the agent will really pick; SARSA takes the single action $a^{\prime }$ its own policy actually samples next.

Both Q-learning and SARSA find the optimal policy for the $4\times 3$ world, but more slowly than active ADP, because their purely local updates do not enforce consistency across states through a model. This reopens the model-based versus model-free question: as environments grow more complex, the knowledge a model carries tends to pay off, which is why the strongest game-playing systems have usually learned an evaluation function rather than raw Q-values.

Q-learning and SARSA close the tabular story, but they share the limitation that has run through this whole part: they store one number per state or per state-action pair. That is fine for a grid and hopeless for backgammon or chess. Lifting RL off the lookup table with function approximation, and learning a policy directly rather than reading it off a value, continue in Reinforcement Learning: Generalization and Policy Search.