---
title: Reinforcement Learning
module: Learning
moduleNumber: 5
lessonNumber: 5
order: 505
summary: >
  Reinforcement learning is an MDP with the model unknown: the agent knows
  neither how its actions move the world nor which states are rewarded, and
  must recover good behaviour from experienced transitions and rewards alone.
  This first part
  builds the classical tabular theory — passive learning (fix a policy, learn its
  value, by direct estimation, adaptive dynamic programming, and temporal
  differences) and active learning (choose actions, trade exploration against
  exploitation, and learn control with Q-learning and SARSA). A second part lifts
  it off the lookup table with function approximation and policy search.
topics: [Learning]
sources:
  - book: AIMA
    ref: "Ch. 21 — Reinforcement Learning; §21.1 Introduction; §21.2 Passive Reinforcement Learning"
  - book: AIMA
    ref: "§21.3 Active Reinforcement Learning"
---

The [decision-theory lesson](/artificial-intelligence/uncertainty/making-decisions)
handed the agent a finished Markov decision process: it knew the transition model
$P(s' \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.[^aima-intro]

> **Definition (Reinforcement learning).** The problem of learning to act well in
> an **unknown** MDP. The agent does not know the transition model $P(s' \mid s, a)$
> or the reward function $R(s)$; it observes a sequence of transitions and rewards
> as it acts, and must recover an optimal (or near-optimal) policy from that
> experience alone.

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.[^aima-intro] 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:

| Design | What it learns | Uses it how |
| --- | --- | --- |
| Utility-based (model-based) | a model $P$, $R$, and utilities $U(s)$ | one-step look-ahead through $P$ to pick actions |
| Q-learning (model-free) | an action-utility function $Q(s,a)$ | picks $\arg\max_a Q(s,a)$, no model needed |
| Reflex | a policy $\pi$ mapping states to actions directly | executes $\pi(s)$ |

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$.[^aima-passive] The utility is the expected
discounted return obtained by following $\pi$ from $s$:

$$
U^\pi(s) \;=\; \mathbb{E}\left[\, \sum_{t=0}^{\infty} \gamma^t\, R(S_t) \;\Bigm|\; S_0 = s,\; \pi \,\right],
$$

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

$$
(1,1)_{-.04} \rightsquigarrow (1,2)_{-.04} \rightsquigarrow (1,3)_{-.04} \rightsquigarrow (2,3)_{-.04} \rightsquigarrow (3,3)_{-.04} \rightsquigarrow (4,3)_{+1},
$$

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)$.[^aima-direct]

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:

$$
U^\pi(s) \;=\; R(s) + \gamma \sum_{s'} P\!\big(s' \mid s, \pi(s)\big)\, U^\pi(s').
$$

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'$ example, and the
agent estimates $P(s' \mid s, a)$ by the frequency with which $s'$ 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.[^aima-adp]

$$
% caption: The ADP loop: observed transitions feed a maximum-likelihood model $\hat P$
% and reward table $\hat R$; solving the fixed-policy Bellman equations on that model
% yields the utilities $U^\pi$.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  box/.style={draw, minimum width=26mm, minimum height=12mm, align=center}]
  \definecolor{acc}{HTML}{2348F2}
  \node[box] (exp)   at (0,0)    {experience\\(s, a, r, s-prime)};
  \node[box] (model) at (4.4,0)  {estimated model\\P-hat, R-hat};
  \node[box, draw=acc, text=acc, thick] (util) at (9.0,0) {utilities\\U-pi(s)};
  \draw[->, acc, thick] (exp) -- (model) node[midway, above, font=\scriptsize] {count};
  \draw[->, acc, thick] (model) -- (util) node[midway, above, font=\scriptsize] {solve Bellman};
  \draw[->, black, thick] (util.south) .. controls (9.0,-1.5) and (0,-1.5) .. (exp.south)
    node[midway, below, font=\scriptsize] {act under f\/ixed policy, observe more};
\end{tikzpicture}
$$

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.[^aima-td] Suppose the agent is in $s$ with current estimate $U^\pi(s)$, acts,
and lands in $s'$. If the estimates were exactly consistent they would satisfy the
local relation $U^\pi(s) = R(s) + \gamma\, U^\pi(s')$. They usually don't, and the
gap between the two sides is the **temporal-difference error**. TD nudges $U^\pi(s)$
to shrink it:

$$
U^\pi(s) \;\gets\; U^\pi(s) \;+\; \alpha\,\big[\,\underbrace{R(s) + \gamma\, U^\pi(s') - U^\pi(s)}_{\text{TD error }\delta}\,\big].
$$

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'$ 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.

$$
% caption: The TD update. The observed successor s-prime yields a target
% $R(s) + \gamma U(s')$; the agent moves its estimate $U(s)$ a fraction $\alpha$ of
% the way toward that target, closing the temporal-difference error $\delta$.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % number line
  \draw[black, thick] (0,0) -- (11,0);
  \foreach \x in {0,1,...,11} \draw[black] (\x,-0.07) -- (\x,0.07);
  % old estimate
  \fill[black] (2.6,0) circle (2.6pt);
  \node[anchor=south] at (2.6,0.15) {old U(s)};
  % target
  \fill[red] (8.4,0) circle (2.6pt);
  \node[red, anchor=south] at (8.4,0.15) {target R(s) + g U(s-prime)};
  % new estimate (a fraction alpha toward the target)
  \fill[acc] (4.35,0) circle (2.6pt);
  \node[acc, anchor=north] at (4.35,-0.18) {new U(s)};
  % the TD error span
  \draw[<->, black] (2.6,-0.95) -- (8.4,-0.95) node[midway, below, black] {TD error d};
  % the step actually taken
  \draw[->, acc, very thick] (2.6,0.62) -- (4.35,0.62) node[midway, above, acc, font=\scriptsize] {step a . d};
\end{tikzpicture}
$$

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.[^aima-td]

```algorithm
caption: $\textsc{Passive-TD}$ — learn $U^\pi$ for a fixed policy $\pi$, model-free
input: policy $\pi$, step-size schedule $\alpha(\cdot)$, discount $\gamma$
$U(s) \gets 0$ for all $s$; visit counts $N(s) \gets 0$
for each episode do
  observe start state $S$
  repeat
    take action $\pi(S)$, observe reward $R$ and next state $S'$
    $N(S) \gets N(S) + 1$
    $U(S) \gets U(S) + \alpha(N(S))\,[R + \gamma\, U(S') - U(S)]$
    $S \gets S'$
  until $S$ is terminal
return $U$
```

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

| Method | Uses Bellman link? | Needs a model? | Cost per step | Data efficiency |
| --- | --- | --- | --- | --- |
| Direct estimation | no | no | tiny | poor (slow) |
| ADP | yes (fully) | yes (learns it) | solves the MDP | best |
| Temporal difference | yes (one successor) | no | tiny | between the two |

## 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:

$$
U(s) \;=\; R(s) + \gamma \max_a \sum_{s'} P(s' \mid s, a)\, U(s').
$$

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.[^aima-explore]

$$
% caption: The exploration-exploitation tradeoff. Pure exploitation gets stuck on
% the first workable route; pure exploration never cashes in what it learns; good
% agents explore early and exploit late.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  box/.style={draw, minimum width=30mm, minimum height=13mm, align=center}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \node[box, draw=red, text=red] (exploit) at (0,0)   {exploit\\act on best estimate};
  \node[box, draw=acc, text=acc] (explore) at (6.5,0) {explore\\try unfamiliar actions};
  \draw[<->, black, thick] (exploit) -- (explore)
    node[midway, above, font=\scriptsize] {tradeo\/f\/f}
    node[midway, below, font=\scriptsize] {balance shifts over time};
  \node[red, anchor=north, font=\scriptsize, align=center] at (0,-1.15) {risk: stuck in a rut};
  \node[acc, anchor=north, font=\scriptsize, align=center] at (6.5,-1.15) {risk: never cash in};
\end{tikzpicture}
$$

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.

> **Definition (GLIE).** A scheme is **greedy in the limit of infinite exploration**
> if it tries every action in every state an unbounded number of times (so it never
> misses the optimal action through an unlucky streak) yet becomes greedy in the
> limit (so its behaviour eventually converges to optimal for the true model). Any
> GLIE scheme learns optimal behaviour; the crudest one takes a random action with
> probability $1/t$ and acts greedily otherwise.

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

$$
U^+(s) \;\gets\; R(s) + \gamma \max_a f\!\left(\sum_{s'} P(s' \mid s, a)\, U^+(s'),\; N(s,a)\right).
$$

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.[^explore-rules] Let $\bar Q(a)$
be the current estimate of action $a$'s value and $N(a)$ the number of times $a$ has
been tried.

> **Definition ($\varepsilon$-greedy).** With probability $1 - \varepsilon$ take the
> greedy action $\arg\max_a \bar Q(a)$; with probability $\varepsilon$ take an action
> uniformly at random. A fixed $\varepsilon$ never stops exploring, so it is not
> GLIE; **decaying** $\varepsilon$ toward $0$ makes it GLIE and lets behaviour
> converge to greedy. A common schedule is $\varepsilon_t = \varepsilon_0 / t$ or a
> geometric decay $\varepsilon_t = \varepsilon_0\, d^{\,t}$ with $0 < d < 1$; the
> $1/t$ random-action rule above is exactly $\varepsilon_t = 1/t$.

$\varepsilon$-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.

> **Definition (UCB).** Pick the action maximising an upper confidence bound on its
> value,
> $$
> a_t \;=\; \arg\max_a \left[\, \bar Q(a) \;+\; c\,\sqrt{\frac{\ln t}{N(a)}} \,\right],
> $$
> where $t$ is the total number of pulls so far, $N(a)$ the pulls of $a$, and $c > 0$
> tunes the exploration weight. The bonus $c\sqrt{\ln t / N(a)}$ is large for rarely
> tried actions (small $N(a)$) and decays as $N(a)$ grows, so a genuinely good action
> is quickly confirmed and a genuinely bad one is dropped after few trials —
> "optimism in the face of uncertainty." For stochastic bandits UCB's regret grows
> only as $O(\ln t)$, which is optimal in order.

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: $\varepsilon$-greedy explores
blindly, the $R^+/N_e$ function explores until a visit count is met, and UCB
explores in proportion to statistical uncertainty.

$$
% caption: Three exploration rules on a five-arm bandit, ranked by how they spend
% exploration. epsilon-greedy pulls a uniform random arm on an epsilon fraction of
% steps (wasting some on known-bad arms); the R-plus/Ne function forces each arm to
% Ne pulls then trusts the value; UCB adds a bonus c sqrt(ln t / N(a)) that steers
% exploration toward high-uncertainty arms. Bar height is how often each arm is
% chosen; the true-best arm is marked.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % three mini bar-charts side by side
  % --- epsilon-greedy ---
  \begin{scope}[xshift=0cm]
    \node[font=\scriptsize, anchor=south] at (1.5,2.6) {epsilon-greedy};
    \draw[black] (0,0) -- (3.0,0);
    \foreach \x/\h in {0.3/0.35, 0.9/0.35, 1.5/2.0, 2.1/0.35, 2.7/0.35}
      \fill[acc!70] (\x-0.18,0) rectangle (\x+0.18,\h);
    \node[red, font=\scriptsize] at (1.5,2.15) {best};
    \node[font=\scriptsize, text=black, anchor=north] at (1.5,-0.1) {uniform when exploring};
  \end{scope}
  % --- R+/Ne ---
  \begin{scope}[xshift=4.4cm]
    \node[font=\scriptsize, anchor=south] at (1.5,2.6) {R-plus / Ne};
    \draw[black] (0,0) -- (3.0,0);
    \foreach \x/\h in {0.3/0.7, 0.9/0.7, 1.5/1.6, 2.1/0.7, 2.7/0.7}
      \fill[acc!70] (\x-0.18,0) rectangle (\x+0.18,\h);
    \node[red, font=\scriptsize] at (1.5,1.75) {best};
    \node[font=\scriptsize, text=black, anchor=north] at (1.5,-0.1) {each arm to Ne, then trust};
  \end{scope}
  % --- UCB ---
  \begin{scope}[xshift=8.8cm]
    \node[font=\scriptsize, anchor=south] at (1.5,2.6) {UCB};
    \draw[black] (0,0) -- (3.0,0);
    \foreach \x/\h in {0.3/0.5, 0.9/0.75, 1.5/2.0, 2.1/0.6, 2.7/0.45}
      \fill[acc!70] (\x-0.18,0) rectangle (\x+0.18,\h);
    \node[red, font=\scriptsize] at (1.5,2.15) {best};
    \node[font=\scriptsize, text=black, anchor=north] at (1.5,-0.1) {by uncertainty};
  \end{scope}
\end{tikzpicture}
$$

### 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)$.[^aima-qlearn]
At equilibrium the Q-values satisfy their own Bellman constraint,

$$
Q(s,a) \;=\; R(s) + \gamma \sum_{s'} P(s' \mid s, a) \max_{a'} Q(s', a'),
$$

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

$$
Q(s,a) \;\gets\; Q(s,a) \;+\; \alpha\,\big[\,R(s) + \gamma \max_{a'} Q(s', a') - Q(s,a)\,\big].
$$

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.

> **Definition (Model-free learning).** A method that learns to act **without ever
> estimating** the transition model $P(s' \mid s, a)$, using only observed rewards
> and successor states. Q-learning is model-free: because $Q(s,a)$ can be updated
> from the neighbours' Q-values alone, the agent needs no model for either learning
> or action selection.

$$
% caption: The Q-learning backup. The agent takes a in s, lands in s-prime, and
% backs up the best next value $\max_{a'} Q(s', a')$ into $Q(s,a)$ — a model-free
% update indexed by action.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  node distance=6mm,
  st/.style={circle, draw, minimum size=10mm, inner sep=0pt},
  ac/.style={circle, draw, fill=black, minimum size=3pt, inner sep=0pt}]
  \definecolor{acc}{HTML}{2348F2}
  % current state
  \node[st] (s) at (0,0) {s};
  % action node
  \node[ac] (a) at (2.4,0) {};
  \node[anchor=south, font=\scriptsize] at (2.4,0.28) {a};
  % successor state
  \node[st] (sp) at (4.8,0) {s-prime};
  % the two best-next actions branching from s-prime
  \node[ac] (a1) at (7.2,0.9) {};
  \node[ac] (a2) at (7.2,-0.9) {};
  \node[anchor=west, font=\scriptsize] at (7.4,0.9) {a-prime 1};
  \node[anchor=west, font=\scriptsize] at (7.4,-0.9) {a-prime 2};
  % edges
  \draw[->, acc, thick] (s) -- (a) node[midway, below, font=\scriptsize] {take a};
  \draw[->, acc, thick] (a) -- (sp) node[midway, below, font=\scriptsize] {observe R, s-prime};
  \draw[->, black] (sp) -- (a1);
  \draw[->, black] (sp) -- (a2);
  % the max backup, drawn returning
  \draw[->, acc, very thick] (5.9,-1.6) .. controls (3.5,-2.1) and (0.5,-1.5) .. (s.south)
    node[midway, below, font=\scriptsize, acc] {back up  R + g . max Q(s-prime, a-prime)};
\end{tikzpicture}
$$

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 $\varepsilon$-greedy rule defined above.

```algorithm
caption: $\textsc{Q-Learning}$ — model-free off-policy TD control, estimate $Q \approx Q^\ast$
input: step-size schedule $\alpha(\cdot)$, discount $\gamma$, exploration function $f$
$Q(s,a) \gets 0$ for all $s, a$; visit counts $N(s,a) \gets 0$
for each episode do
  observe start state $S$
  repeat
    choose $A$ from $S$ using $f$ over $Q(S, \cdot)$ and $N(S, \cdot)$
    take action $A$, observe reward $R$ and next state $S'$
    $N(S,A) \gets N(S,A) + 1$
    $Q(S,A) \gets Q(S,A) + \alpha(N(S,A))\,[R + \gamma \max_{a'} Q(S', a') - Q(S,A)]$
    $S \gets S'$
  until $S$ is terminal
return $Q$
```

#### 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 $\mathit{right}$ (toward $s_3$) or $\mathit{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 $\mathit{right}$, lands in the terminal $s_3$
with reward $10$.** The successor is terminal, so $\max_{a'} Q(s_3, a') = 0$. The
update is

$$
Q(s_2, R) \gets 0 + 0.5\big[\,10 + 0.9(0) - 0\,\big] = 0.5 \cdot 10 = 5.0.
$$

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 $\mathit{right}$, lands in
$s_2$ with reward $0$.** Now the successor $s_2$ is _not_ terminal, and its best
action value is $\max_{a'} Q(s_2, a') = Q(s_2, R) = 5.0$ from step 1. So

$$
Q(s_1, R) \gets 0 + 0.5\big[\,0 + 0.9(5.0) - 0\,\big] = 0.5 \cdot 4.5 = 2.25.
$$

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 $\mathit{right}$ into $s_3$, reward
$10$.** The same target as step 1, but $Q(s_2, R)$ is no longer $0$:

$$
Q(s_2, R) \gets 5.0 + 0.5\big[\,10 + 0.9(0) - 5.0\,\big] = 5.0 + 0.5(5.0) = 7.5.
$$

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.

$$
% caption: A Q-learning trace on a three-state corridor (reward +10 on entering the
% terminal s3, discount 0.9, learning rate 0.5). Q(s2, right) climbs 0, 5.0, 7.5,
% 8.75 toward its true value 10 as the goal reward is bootstrapped backward; Q(s1,
% right) reaches 2.25 after one visit even with zero immediate reward.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \draw[->, black] (0,0) -- (0,3.4) node[above, black, font=\scriptsize] {Q(s2, right)};
  \draw[->, black] (0,0) -- (6.6,0) node[right, black, font=\scriptsize] {visits to s2};
  % target line at 10 -> height 3.0
  \draw[red, dashed] (0,3.0) -- (6.2,3.0);
  \node[red, anchor=east, font=\scriptsize] at (-0.08,3.0) {10 (true)};
  % points: 0, 5.0(1.5), 7.5(2.25), 8.75(2.625)
  \node[anchor=north east, black, font=\scriptsize] at (-0.05,0) {0};
  \fill[acc] (0.0,0.0) circle (1.8pt);
  \fill[acc] (1.6,1.5) circle (1.8pt);
  \fill[acc] (3.2,2.25) circle (1.8pt);
  \fill[acc] (4.8,2.625) circle (1.8pt);
  \draw[acc, thick] (0.0,0.0) -- (1.6,1.5) -- (3.2,2.25) -- (4.8,2.625);
  \node[acc, anchor=west, font=\scriptsize] at (1.65,1.4) {5.0};
  \node[acc, anchor=west, font=\scriptsize] at (3.25,2.15) {7.5};
  \node[acc, anchor=west, font=\scriptsize] at (4.85,2.5) {8.75};
  \foreach \x/\n in {0/0,1.6/1,3.2/2,4.8/3} \node[anchor=north, font=\scriptsize] at (\x,-0.05) {\n};
\end{tikzpicture}
$$

### 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'$, rather than the best available:

$$
Q(s,a) \;\gets\; Q(s,a) \;+\; \alpha\,\big[\,R(s) + \gamma\, Q(s', a') - Q(s,a)\,\big].
$$

The rule fires on the full quintuple $(s, a, r, s', a')$ — 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**.[^aima-qlearn] 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'$, 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'$'s actions,
ignoring which one the agent will really pick; SARSA takes the single action $a'$
its own policy actually samples next.

$$
% caption: SARSA versus Q-learning backups, side by side. Both take a in s and land
% in s-prime. Q-learning (left) backs up the MAX over s-prime's action values,
% max Q(s-prime, a-prime), so it learns the greedy policy no matter how it behaves
% (off-policy). SARSA (right) backs up the value of the single action a-prime its
% own policy actually samples next (solid arrow; the unchosen action is dashed), so
% it learns the value of the policy it follows (on-policy). The one-symbol
% difference, max versus sample, is the whole on/off-policy distinction.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  st/.style={circle, draw, minimum size=9mm, inner sep=0pt, font=\scriptsize},
  ac/.style={circle, draw, fill=black, minimum size=3pt, inner sep=0pt}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % ===== left: Q-learning =====
  \begin{scope}
    \node[font=\scriptsize, anchor=south] at (2.4,2.5) {Q-learning (of\/f-policy)};
    \node[st] (s) at (0,0.7) {s};
    \node[ac] (a) at (1.4,0.7) {};
    \node[anchor=south, font=\scriptsize] at (1.4,0.9) {a};
    \node[st] (sp) at (2.8,0.7) {s'};
    \node[ac] (a1) at (4.3,1.5) {};
    \node[ac] (a2) at (4.3,-0.1) {};
    \draw[->, acc, thick] (s) -- (a);
    \draw[->, acc, thick] (a) -- (sp);
    \draw[->, black] (sp) -- (a1);
    \draw[->, black] (sp) -- (a2);
    \node[anchor=west, font=\scriptsize, acc] at (4.5,1.5) {max};
    \node[anchor=west, font=\scriptsize, black] at (4.5,-0.1) {other};
    \node[font=\scriptsize, text=acc, anchor=north, align=center] at (2.4,-0.9) {back up max Q(s', a')};
  \end{scope}
  % ===== right: SARSA =====
  \begin{scope}[xshift=7.6cm]
    \node[font=\scriptsize, anchor=south] at (2.4,2.5) {SARSA (on-policy)};
    \node[st] (s2) at (0,0.7) {s};
    \node[ac] (b) at (1.4,0.7) {};
    \node[anchor=south, font=\scriptsize] at (1.4,0.9) {a};
    \node[st] (sp2) at (2.8,0.7) {s'};
    \node[ac] (b1) at (4.3,1.5) {};
    \node[ac] (b2) at (4.3,-0.1) {};
    \draw[->, acc, thick] (s2) -- (b);
    \draw[->, acc, thick] (b) -- (sp2);
    \draw[->, red, thick] (sp2) -- (b1);
    \draw[->, black, dashed] (sp2) -- (b2);
    \node[anchor=west, font=\scriptsize, red] at (4.5,1.5) {sampled a'};
    \node[anchor=west, font=\scriptsize, black] at (4.5,-0.1) {not taken};
    \node[font=\scriptsize, text=acc, anchor=north, align=center] at (2.4,-0.9) {back up Q(s', a')};
  \end{scope}
\end{tikzpicture}
$$

| | Q-learning | SARSA |
| --- | --- | --- |
| Target action | $\arg\max_{a'} Q(s', a')$ (best) | $a'$ actually taken next |
| Policy learned | greedy (off-policy) | the behaviour policy (on-policy) |
| Under exploration | learns $Q^\ast$ regardless of behaviour | learns value of what it really does |
| Model required | none | none |

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](/artificial-intelligence/learning/generalization-and-policy-search).

[^aima-intro]: **AIMA**, §21.1 — Introduction: reinforcement learning as the task of using observed rewards to learn an optimal policy in an environment where the agent knows neither the transition model nor the reward function in advance; the reward is part of the percept, and games like chess deliver it only at the end.
[^aima-passive]: **AIMA**, §21.2 — Passive Reinforcement Learning: with a fixed policy $\pi$, the agent learns $U^\pi(s)$ (the policy-evaluation task) from trials in the environment, without knowing $P$ or $R$.
[^aima-direct]: **AIMA**, §21.2.1 — Direct utility estimation: the utility of a state is the expected reward-to-go; averaging the sampled reward-to-go per state reduces RL to supervised learning but ignores the Bellman links between states, so it converges slowly.
[^aima-adp]: **AIMA**, §21.2.2 — Adaptive dynamic programming: learn the transition model by frequency counting, then solve the fixed-policy Bellman equations; modified policy iteration and prioritized sweeping keep it tractable, but the exact method does not scale to large state spaces.
[^aima-td]: **AIMA**, §21.2.3 — Temporal-difference learning: the update $U^\pi(s) \gets U^\pi(s) + \alpha(R(s) + \gamma U^\pi(s') - U^\pi(s))$ adjusts a state toward its observed successor, needs no transition model, and converges when $\alpha$ decays with visit count; TD is a model-free approximation to ADP.
[^aima-explore]: **AIMA**, §21.3.1 — Exploration: the greedy agent that acts optimally for its learned model rarely converges to the optimal policy; a GLIE scheme (greedy in the limit of infinite exploration) and an exploration function $f(u,n)$ with an optimistic $U^+$ trade exploitation against exploration; the $1/t$ random-action rule is the simplest GLIE scheme, and the bandit sidebar (§21.3.1) frames exploration as an $n$-armed bandit problem with the Gittins index as its exact-but-intractable solution.
[^explore-rules]: The two rules are standard in the bandit literature rather than derived in AIMA. **$\varepsilon$-greedy** with a decaying schedule appears throughout **Sutton & Barto**, _Reinforcement Learning: An Introduction_ (2nd ed., 2018), §2.2–2.3. **UCB1** and its $O(\ln t)$ regret bound are from **Auer, Cesa-Bianchi, and Fischer** (2002), "Finite-time analysis of the multiarmed bandit problem", _Machine Learning_ 47, building on **Lai and Robbins** (1985). UCB is the selection rule inside the UCT tree search of **Kocsis and Szepesvári** (2006), "Bandit based Monte-Carlo planning", _ECML_ — the algorithm AIMA cites for game-tree search and the basis of AlphaGo's Monte-Carlo tree search.
[^aima-qlearn]: **AIMA**, §21.3.2 — Learning an action-utility function: Q-learning's model-free TD update $Q(s,a) \gets Q(s,a) + \alpha(R(s) + \gamma \max_{a'} Q(s',a') - Q(s,a))$ and its on-policy relative SARSA, which backs up the action actually taken; Q-learning is off-policy, SARSA on-policy.