---
title: "Reinforcement Learning: Generalization and Policy Search"
module: Learning
moduleNumber: 5
lessonNumber: 6
order: 506
summary: >
  Tabular reinforcement learning stores one number per state, which is hopeless for
  backgammon or chess. This part lifts RL off the lookup table with function
  approximation, so that updating one state generalizes to related ones, then turns
  to policy search — representing and optimizing the policy directly, up to the
  REINFORCE policy gradient and correlated sampling. It closes with the bridge to
  deep reinforcement learning (deep Q-networks, actor-critic, PPO), the classic
  applications, and the hand-off to the dedicated RL subject.
topics: [Learning]
sources:
  - book: AIMA
    ref: "§21.4 Generalization in Reinforcement Learning; §21.5 Policy Search; §21.6 Applications"
---

This builds on [Reinforcement Learning](/artificial-intelligence/learning/reinforcement-learning),
which set up learning in an unknown MDP and developed the tabular methods — passive
evaluation by direct estimation, adaptive dynamic programming, and temporal
differences, then active control by Q-learning and SARSA. All of those store a value
per state in a table. Here we remove that restriction, first by approximating the
value function and then by searching over policies directly.

## Generalization in reinforcement learning

First, the scale of the problem. The tabular methods store one entry
per state (or per state-action pair): fine for a grid, but backgammon has around
$10^{20}$ states and chess around $10^{40}$. No agent can visit each even once, let
alone many times, so the table has to go.[^aima-generalize]

The replacement is **function approximation**: represent $U$ or $Q$ by any compact
parameterised form instead of a lookup table. The classic choice is a weighted linear
combination of **features** (basis functions) $f_1, \dots, f_n$ of the state:

$$
\hat U_\theta(s) \;=\; \theta_1 f_1(s) + \theta_2 f_2(s) + \cdots + \theta_n f_n(s).
$$

A backgammon utility that would need $10^{20}$ table entries might be captured by a
few dozen weights $\theta$ — an enormous compression. More important is
**generalization**: adjusting $\theta$ in response to one visited
state changes the estimate at _every_ state that shares features, so the agent
extrapolates from states it has seen to states it never will. By examining a
vanishing fraction of backgammon positions, a program can learn a utility that plays
at human level.[^aima-generalize]

$$
% caption: A lookup table stores one value per state and generalizes nowhere; a
% feature-based approximator maps each state through shared features to a few
% weights, so updating one state moves the estimate at related states too.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  box/.style={draw, minimum width=20mm, minimum height=9mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  % --- left: lookup table ---
  \node[font=\footnotesize, anchor=south] at (1.4,2.5) {lookup table};
  \foreach \i/\y in {1/1.8, 2/0.9, 3/0.0} {
    \node[box] (t\i) at (0,\y) {state \i};
    \node[box] (v\i) at (2.8,\y) {value \i};
    \draw[->, black] (t\i) -- (v\i);
  }
  \node[anchor=north, font=\scriptsize, align=center] at (1.4,-0.7) {one entry per state,\\no sharing};
  % --- right: feature approximator ---
  \begin{scope}[xshift=7.2cm]
    \node[font=\footnotesize, anchor=south] at (1.6,2.5) {feature approximator};
    \foreach \i/\y in {1/1.8, 2/0.9, 3/0.0} \node[box] (s\i) at (0,\y) {state \i};
    \node[box, align=center] (feat) at (2.9,0.9) {features\\f(s), weights th};
    \node[box, draw=acc, text=acc] (out) at (5.7,0.9) {U-hat(s)};
    \foreach \i in {1,2,3} \draw[->, black] (s\i) -- (feat);
    \draw[->, acc, thick] (feat) -- (out);
    \node[anchor=north, font=\scriptsize, align=center] at (2.8,-0.7) {shared weights,\\updates generalize};
  \end{scope}
\end{tikzpicture}
$$

Learning the weights is online supervised regression. If $u_j(s)$ is the observed
reward-to-go from $s$ in the $j$th trial, the squared error is
$E_j(s) = \tfrac12 (\hat U_\theta(s) - u_j(s))^2$, and gradient descent on it gives
the **Widrow–Hoff** (delta) rule,

$$
\theta_i \;\gets\; \theta_i + \alpha\,\big(u_j(s) - \hat U_\theta(s)\big)\,\frac{\partial \hat U_\theta(s)}{\partial \theta_i}.
$$

The temporal-difference and Q-learning targets slot straight in — replace the
observed return with the bootstrapped TD target:

$$
\theta_i \;\gets\; \theta_i + \alpha\,\big[\,R(s) + \gamma\, \hat U_\theta(s') - \hat U_\theta(s)\,\big]\,\frac{\partial \hat U_\theta(s)}{\partial \theta_i},
$$

and the analogous update for $\hat Q_\theta(s,a)$ using $\max_{a'} \hat Q_\theta(s', a')$.
This is the tabular update with the single value replaced by the whole parameter
vector: one observed transition now edits every weight, and so shifts the estimate at
every related state. For passive TD with a _linear_ approximator, the parameters
provably converge to the best representable fit. What matters is linearity in the
_parameters_ — the features $f_i$ themselves may be arbitrarily nonlinear functions
of the state (a distance-to-goal term, a piece-count, a board pattern). With
_nonlinear_ approximators and active learning the guarantees disappear; the
parameters can even diverge, and RL with general function approximators remains
difficult to stabilize.

> **Note (Deep reinforcement learning).** Take the nonlinear approximator to its
> conclusion and let a deep neural network play the role of $\hat Q_\theta$ or a
> parameterised policy. This is **deep RL**, the basis of agents that learn
> Atari from pixels, master Go, and control robots. It is effective and notoriously
> unstable, which is why the dedicated
> [RL subject](/reinforcement-learning/deep-rl/deep-q-networks) devotes whole
> modules to the techniques — experience replay, target networks, policy gradients —
> that make it converge.

## Policy search and policy gradients

Every method so far learns a _value_ — a utility $U$, an action-utility $Q$ — and
then reads a policy off it, greedily. **Policy search** turns that around. It
represents the policy directly, as a parameterised function $\pi_\theta$, and
adjusts $\theta$ to raise the policy's performance. The idea is the simplest in the
whole chapter: keep twiddling the policy as long as its performance improves, then
stop.[^aima-policy]

The distinction from value-based learning is substantive. Suppose we still
represent the policy through Q-functions, taking the highest-scoring action,
$\pi(s) = \arg\max_a \hat Q_\theta(s,a)$. Q-learning with function approximation
tunes $\theta$ so that $\hat Q_\theta$ lands _close_ to $Q^\ast$; policy search tunes
$\theta$ so that the resulting behaviour is _good_, and the two targets can be far
apart. The approximate function $\hat Q_\theta(s,a) = Q^\ast(s,a)/10$ gives exactly
optimal behaviour — the same $\arg\max$ in every state — yet is nowhere near $Q^\ast$
as a function. Policy search ignores the gap; only the
ranking of actions the parameters induce matters.

$$
% caption: Value-based learning fits $\hat Q_\theta$ to the target $Q^*$ and reads a
% policy off it; policy search skips the value target and adjusts $\theta$ to raise
% the policy value $\rho(\theta)$ directly.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  box/.style={draw, minimum width=27mm, minimum height=12mm, align=center}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % value-based row
  \node[box] (qfit) at (0,1.6) {f\/it Q-hat to Q-star};
  \node[box] (pol1) at (4.6,1.6) {read of\/f arg-max};
  \node[box] (perf1) at (9.2,1.6) {behaviour};
  \draw[->, black, thick] (qfit) -- (pol1);
  \draw[->, black, thick] (pol1) -- (perf1);
  \node[anchor=west, font=\scriptsize] at (-1.9,1.6) {};
  \node[font=\scriptsize, anchor=south] at (2.3,2.35) {value-based};
  % policy-search row
  \node[box] (pol2) at (0,-0.6) {policy pi-theta};
  \node[box] (perf2) at (4.6,-0.6) {policy value rho};
  \node[box] (upd) at (9.2,-0.6) {adjust theta up};
  \draw[->, black, thick] (pol2) -- (perf2) node[midway, above, font=\scriptsize] {execute};
  \draw[->, black, thick] (perf2) -- (upd) node[midway, above, font=\scriptsize] {gradient};
  \draw[->, acc, thick] (upd.south) .. controls (9.2,-1.9) and (0,-1.9) .. (pol2.south);
  \node[font=\scriptsize, text=acc, anchor=north] at (2.3,-1.35) {policy search};
\end{tikzpicture}
$$

### Representing the policy

A policy $\pi_\theta$ maps states to actions, and — as with value approximation —
we want far fewer parameters than there are states. The Q-function form above is
one option: a bank of parameterised $\hat Q_\theta(s,a)$, one per action, linear in
$\theta$ or a neural network, with $\pi_\theta(s) = \arg\max_a \hat Q_\theta(s,a)$.
It has a fatal defect for gradient methods, though. With **discrete** actions the
$\arg\max$ makes $\pi_\theta$ a _discontinuous_ function of $\theta$: at some
settings an infinitesimal nudge to $\theta$ flips the winning action, so the policy
value jumps. A jump has no useful gradient, and gradient ascent stalls.[^aima-policy]

The remedy is a **stochastic policy**. Instead of committing to one action,
$\pi_\theta(s,a)$ returns the _probability_ of choosing $a$ in $s$. The standard
choice is the **softmax** over the parameterised scores,

$$
\pi_\theta(s, a) \;=\; \frac{e^{\hat Q_\theta(s,a)}}{\sum_{a'} e^{\hat Q_\theta(s,a')}},
$$

the multi-action generalisation of the logistic function. Softmax is nearly
deterministic when one action's score dominates, recovering the greedy policy in
the limit, but it is **differentiable** in $\theta$ everywhere — a small change in
$\theta$ shifts the probabilities smoothly rather than snapping the choice from one
action to another. Because the policy value depends continuously on those
probabilities, it too becomes a differentiable function of $\theta$, and gradient
ascent applies again.

$$
% caption: A hard arg-max policy (red) is a step function of a score parameter: the
% chosen action jumps discontinuously, so the policy value has no gradient. The
% softmax policy (blue) varies its action probabilities smoothly, so $\rho(\theta)$
% is differentiable.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \draw[->, black] (0,0) -- (6.4,0) node[right, font=\scriptsize, black] {score di\/f\/ference};
  \draw[->, black] (0,0) -- (0,3.2) node[above, font=\scriptsize, black] {P(action a)};
  \node[font=\scriptsize, anchor=east] at (-0.05,2.7) {1};
  \node[font=\scriptsize, anchor=east] at (-0.05,1.35) {0.5};
  % hard step
  \draw[red, very thick] (0.2,0.15) -- (3.1,0.15);
  \draw[red, very thick, dashed] (3.1,0.15) -- (3.1,2.7);
  \draw[red, very thick] (3.1,2.7) -- (6.1,2.7);
  \node[red, anchor=south west, font=\scriptsize] at (4.4,2.7) {arg-max (hard)};
  % softmax sigmoid
  \draw[acc, very thick] (0.2,0.28)
    .. controls (1.8,0.5) and (2.6,1.0) .. (3.1,1.35)
    .. controls (3.6,1.7) and (4.4,2.2) .. (6.1,2.55);
  \node[acc, anchor=north west, font=\scriptsize] at (3.6,1.15) {softmax (smooth)};
\end{tikzpicture}
$$

### The objective: policy value

Let $\rho(\theta)$ be the **policy value** — the expected reward-to-go when
$\pi_\theta$ is executed. Policy search is the optimisation problem

$$
\theta^\star \;=\; \arg\max_\theta\, \rho(\theta).
$$

When the policy and environment are both deterministic and $\rho(\theta)$ is
available in closed form, this is an ordinary continuous optimisation: follow the
**policy gradient** $\nabla_\theta \rho(\theta)$ uphill. When no closed form exists,
we can still estimate $\rho(\theta)$ by executing $\pi_\theta$ and averaging the
return, then climb the _empirical_ gradient — perturb each parameter a little, see
how the measured value moves, and step in the improving direction. With the usual
caveats this hill-climbing converges to a local optimum in policy space.[^aima-policy]

Stochasticity is what makes this hard. Empirical hill climbing wants to compare
$\rho(\theta)$ against $\rho(\theta + \Delta\theta)$, but in a stochastic
environment the return on any single trial swings wildly — a run of good luck or bad
cards drowns the small signal from $\Delta\theta$. Comparing two noisy averages is
noisier still. One can beat the noise down by running many trials and using the
sample variance to judge when enough have accumulated, but for problems where each
trial is slow, costly, or dangerous, that is not an option.

### The policy gradient

For a **stochastic** policy $\pi_\theta(s,a)$ there is a better route: an unbiased
estimate of $\nabla_\theta \rho(\theta)$ read straight off the trials run _at_
$\theta$, with no perturbation and no second policy. Derive it first for a
nonsequential environment, where doing action $a$ in the start state $s_0$ yields
reward $R(a)$ immediately. The policy value is just the expected reward, so

$$
\nabla_\theta \rho(\theta) \;=\; \nabla_\theta \sum_a \pi_\theta(s_0, a)\, R(a)
\;=\; \sum_a \big(\nabla_\theta \pi_\theta(s_0, a)\big)\, R(a).
$$

This is a sum over _all_ actions, which the agent cannot compute — it only ever
observes the actions it actually took. The trick is to turn the sum into an
_expectation_ under $\pi_\theta$ itself, so that it can be approximated by samples.
Multiply and divide each term by $\pi_\theta(s_0, a)$:

$$
\nabla_\theta \rho(\theta)
\;=\; \sum_a \pi_\theta(s_0, a)\, \frac{\big(\nabla_\theta \pi_\theta(s_0, a)\big)\, R(a)}{\pi_\theta(s_0, a)}
\;\approx\; \frac{1}{N} \sum_{j=1}^{N} \frac{\big(\nabla_\theta \pi_\theta(s_0, a_j)\big)\, R(a_j)}{\pi_\theta(s_0, a_j)},
$$

where $a_j$ is the action taken on the $j$th of $N$ trials. The outer factor
$\pi_\theta(s_0, a)$ is the very probability with which each action is sampled, so
the weighted sum collapses to a plain average over the sampled trials. The true gradient
is thus approximated by a sum of terms, one per trial, each the gradient of the
action-selection probability scaled by the reward that action earned and normalised
by how likely it was.

$$
% caption: The importance-weighting trick. The intractable sum over all actions
% (left) is rewritten as an expectation under $\pi_\theta$ (right), so the observed
% trials $a_1, \ldots, a_N$ estimate the gradient with no need to enumerate unchosen
% actions.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  box/.style={draw, minimum width=34mm, minimum height=13mm, align=center}]
  \definecolor{acc}{HTML}{2348F2}
  \node[box, draw=black] (all) at (0,0) {sum over ALL actions\\(cannot evaluate)};
  \node[box, draw=acc, text=acc] (exp) at (5.4,0) {expectation under pi\\(sample it)};
  \node[box] (est) at (10.8,0) {average over trials\\a-1 ... a-N};
  \draw[->, acc, thick] (all) -- (exp) node[midway, above, font=\scriptsize] {times pi / pi};
  \draw[->, acc, thick] (exp) -- (est) node[midway, above, font=\scriptsize] {draw N samples};
\end{tikzpicture}
$$

For a **sequential** environment the same reasoning applies at every state the
agent visits. Writing $R_j(s)$ for the total reward received from state $s$ onward on
the $j$th trial and $a_j$ for the action taken in $s$ on that trial,

$$
\nabla_\theta \rho(\theta) \;\approx\; \frac{1}{N} \sum_{j=1}^{N} \frac{\big(\nabla_\theta \pi_\theta(s, a_j)\big)\, R_j(s)}{\pi_\theta(s, a_j)}
\qquad \text{for each state } s \text{ visited.}
$$

The resulting algorithm is **REINFORCE**. It is usually far more effective than
hill climbing that reruns many trials at each $\theta$, because every trial
contributes a gradient direction rather than a single noisy scalar — although it is
still slower than one would like.[^aima-reinforce]

```algorithm
caption: $\textsc{Reinforce}$ — policy-gradient search over a parameterised stochastic policy $\pi_\theta$
input: differentiable policy $\pi_\theta(s,a)$, step-size $\alpha$, discount $\gamma$
$\theta \gets$ any point in parameter space
for each episode do
  generate a trial $S_0, A_0, R_1, S_1, A_1, \ldots, S_T$ by executing $\pi_\theta$
  for each visited state $S_t$ with action $A_t$ do
    $G \gets$ reward-to-go $\sum_{k=t+1}^{T} \gamma^{k-t-1} R_k$
    $g \gets \dfrac{\nabla_\theta\, \pi_\theta(S_t, A_t)}{\pi_\theta(S_t, A_t)}\, G$ // one trial's gradient term
    $\theta \gets \theta + \alpha\, g$
until the policy value $\rho(\theta)$ stops improving
return $\theta$
```

Two features make REINFORCE recognisable as gradient ascent on $\rho$. The ratio
$\nabla_\theta \pi_\theta / \pi_\theta$ is the gradient of $\log \pi_\theta$ — the
direction in parameter space that makes the taken action _more probable_ — and it is
scaled by the return $G$. So the rule pushes the policy to repeat actions that were
followed by high reward and to avoid those followed by low reward, with the strength
of the push set by how good the outcome was. Nothing in it requires a model or a
value estimate; the observed return alone drives the update.

### Correlated sampling and PEGASUS

The variance that plagues policy search has a clean partial fix when a **simulator**
is available. Consider comparing two blackjack programs: play each against the dealer
for many hands and compare winnings. The winnings swing with the luck of the cards,
so the comparison is noisy. But if both programs play the _same_ pre-generated deals,
the card-luck cancels out of the difference, and a far smaller sample settles which
program is better. This is **correlated sampling**: fix the random outcomes in
advance and evaluate every candidate policy against the identical draws.[^aima-pegasus]

$$
% caption: Correlated sampling. Evaluating two policies on independent random draws
% (left) leaves the comparison swamped by luck; evaluating both on the SAME fixed
% draws (right) cancels the shared randomness so their difference is clean.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  box/.style={draw, minimum width=15mm, minimum height=8mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % --- left: independent ---
  \node[font=\scriptsize, anchor=south] at (1.4,2.7) {independent draws};
  \node[box] (r1) at (0,1.8) {draws A};
  \node[box] (r2) at (0,0.4) {draws B};
  \node[box] (pa) at (2.8,1.8) {policy 1};
  \node[box] (pb) at (2.8,0.4) {policy 2};
  \draw[->, black] (r1) -- (pa);
  \draw[->, black] (r2) -- (pb);
  \node[font=\scriptsize, anchor=north, align=center] at (1.4,-0.4) {noisy comparison};
  % --- right: correlated ---
  \begin{scope}[xshift=7.6cm]
    \node[font=\scriptsize, anchor=south] at (1.6,2.7) {same f\/ixed draws};
    \node[box, draw=acc, text=acc] (r) at (0,1.1) {draws A};
    \node[box] (qa) at (3.0,1.8) {policy 1};
    \node[box] (qb) at (3.0,0.4) {policy 2};
    \draw[->, acc, thick] (r) -- (qa);
    \draw[->, acc, thick] (r) -- (qb);
    \node[acc, font=\scriptsize, anchor=north, align=center] at (1.5,-0.4) {clean comparison};
  \end{scope}
\end{tikzpicture}
$$

This idea underlies **PEGASUS**, a policy-search algorithm for domains with a
simulator whose "random" outcomes can be replayed. It generates $N$ random-number
sequences in advance and scores every candidate policy on that same set of
sequences. A strong guarantee follows: the number of sequences needed so that
_every_ policy's value is estimated well depends only on the complexity of the
policy space, not on the complexity of the domain. Policy search by correlated
sampling is how reinforcement learning has flown autonomous helicopters
through manoeuvres beyond expert human pilots, over a simulator learned from
observed flight.

Policy search rounds out the chapter's third design. The utility-based agent learns
a model; Q-learning and SARSA learn a value; policy search learns behaviour itself,
and its gradient form — REINFORCE — is the direct ancestor of the policy-gradient
methods the dedicated
[RL subject](/reinforcement-learning/approximation/policy-gradient-methods)
takes to full depth.

## Deep reinforcement learning

AIMA's chapter ends where the modern field begins. It has the linear function
approximator and warns that nonlinear ones lose the convergence guarantees; what it
predates is the discovery of _how_ to make a deep neural network stand in for
$\hat Q_\theta$ or $\pi_\theta$ and still learn stably. That is **deep reinforcement
learning**, and the two results that opened it are worth stating precisely, because
each is a direct engineering answer to an instability this lesson already named. The
[dedicated RL subject](/reinforcement-learning/foundations/what-is-reinforcement-learning)
develops both in full; this section gives the outline.

### Deep Q-networks

Take the tabular Q-learning of this lesson and replace the table with a convolutional
network $\hat Q_\theta(s, a)$ that reads raw pixels. Trained naively, it diverges —
the deadly combination the lesson flagged: nonlinear approximation, bootstrapping, and
off-policy updates. Mnih and colleagues at DeepMind made it work with two additions,
and the fix maps one-to-one onto the two things that break.[^drl-dqn]

- **Experience replay.** Store each transition $(s, a, r, s')$ in a buffer and train on
  random minibatches drawn from it, rather than on consecutive transitions. Consecutive
  samples are heavily correlated — successive frames of one game — and correlated
  gradients destabilize the network; replay breaks the correlation and reuses each
  transition many times.
- **A target network.** The Q-learning target $r + \gamma \max_{a'} \hat Q_\theta(s', a')$
  uses the very weights being updated, so the target chases the estimate and can spiral.
  DQN computes the target from a _frozen_ copy $\hat Q_{\theta^-}$ whose weights are held
  fixed for many steps and only periodically synchronized, giving the update a stationary
  target to descend toward.

The published result was one network, one set of hyperparameters, learning to play 49
Atari games from pixels and score at or above a human tester on about half of
them.[^drl-dqn] It is the tabular update of this lesson, generalized by a network and
stabilized by two buffers.

$$
% caption: Deep Q-network training. Transitions go into a replay buffer; minibatches
% are sampled from it to decorrelate updates. The TD target uses a frozen target
% network (periodically synced) so the objective does not chase the online weights.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  box/.style={draw, minimum width=24mm, minimum height=11mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \node[box] (env) at (0,1.4) {environment\\(s, a, r, s-prime)};
  \node[box] (buf) at (3.6,1.4) {replay buf\/fer};
  \node[box, draw=acc, text=acc] (online) at (7.4,1.4) {online net\\Q-theta};
  \node[box, draw=red, text=red] (target) at (7.4,-0.9) {target net\\Q-theta-minus};
  \draw[->, thick] (env) -- (buf) node[midway, above, font=\scriptsize] {store};
  \draw[->, acc, thick] (buf) -- (online) node[midway, above, font=\scriptsize] {minibatch};
  \draw[->, red, thick] (target) -- (online) node[midway, right, font=\scriptsize, align=left] {TD\\target};
  \draw[->, black, thick] (online.south) .. controls (9.4,0.25) .. (target.east)
    node[midway, right, font=\scriptsize, align=left] {sync\\slowly};
\end{tikzpicture}
$$

### Policy-gradient methods at scale

REINFORCE, derived above, is the seed of the second branch. Its estimator is unbiased
but high-variance, and two developments tamed it into the algorithms that train
today's continuous-control and language agents.

- **Actor-critic** methods pair the REINFORCE policy (the _actor_) with a learned value
  estimate (the _critic_) that supplies a low-variance baseline, so the gradient is
  scaled by an _advantage_ — how much better an action did than the critic expected —
  rather than the raw, noisy return.
- **Proximal policy optimization (PPO)**, from Schulman and colleagues, addresses a
  different failure: a policy-gradient step large enough to learn quickly can also
  collapse the policy. PPO clips the update so the new policy cannot move too far from
  the old one in a single step, trading a little theoretical purity for the stability
  and simplicity that made it a default for large-scale RL.[^drl-ppo] It is the
  optimizer behind reinforcement learning from human feedback in modern language
  models.

$$
% caption: From REINFORCE to modern policy gradients. The high-variance REINFORCE
% estimator gains a learned critic (actor-critic) to reduce variance, then a clipped
% update (PPO) to bound each step; these are the algorithms behind continuous control
% and RLHF.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  box/.style={draw, minimum width=27mm, minimum height=12mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[box] (rf) at (0,0) {REINFORCE\\unbiased, high variance};
  \node[box] (ac) at (4.6,0) {actor-critic\\critic baseline};
  \node[box] (ppo) at (9.4,0) {PPO\\clipped step};
  \draw[->, thick] (rf) -- (ac) node[midway, above, font=\scriptsize] {cut variance};
  \draw[->, thick] (ac) -- (ppo) node[midway, above, font=\scriptsize] {bound step};
\end{tikzpicture}
$$

The through-line is that none of this abandons the lesson's Bellman-and-gradient core;
it engineers around the instabilities that appear when the lookup table becomes a deep
network. The [modern deep-RL modules](/reinforcement-learning/deep-rl/deep-q-networks)
of the sibling subject cover DQN, actor-critic, PPO, and the systems built on
them — AlphaGo and its successors — at the depth this single AIMA lesson cannot.

## Applications

The first significant learning program of any
kind was Samuel's checkers player (1959), which learned a weighted linear evaluation
function by a form of the TD update. Tesauro's TD-Gammon learned backgammon to
world-champion level from self-play alone, its only reward the win/loss at the end of
each game, a neural-network evaluation function trained by the TD rule on raw board
positions.[^aima-apps] In control, the cart-pole (inverted-pendulum) balancing
problem — jerk a cart left or right to keep a pole upright — became the standard RL
benchmark, and reinforcement learning has since flown autonomous helicopters through
manoeuvres beyond expert human pilots, using policy search over a simulator learned
from observed flight.

[^aima-generalize]: **AIMA**, §21.4 — Generalization in Reinforcement Learning: function approximation replaces the lookup table with a parameterised form (e.g. a linear combination of features), enabling generalization to unvisited states; the Widrow–Hoff/delta rule and the TD/Q-learning gradient updates fit the weights, with convergence guaranteed for linear passive TD but not for nonlinear active learning.
[^aima-policy]: **AIMA**, §21.5 — Policy Search: keep adjusting the policy while its performance improves; a parameterised policy $\pi_\theta$ (e.g. $\pi(s) = \arg\max_a \hat Q_\theta(s,a)$) with far fewer parameters than states; policy search finds $\theta$ that performs well, not $\theta$ that makes $\hat Q_\theta$ resemble $Q^\ast$ (the $Q^\ast/10$ example); the discrete-action $\arg\max$ makes the policy a discontinuous function of $\theta$, so methods use a differentiable stochastic policy $\pi_\theta(s,a)$, typically the softmax; the policy value $\rho(\theta)$ is the expected reward-to-go, optimised by following $\nabla_\theta \rho(\theta)$ or by empirical hill climbing, which stochasticity makes noisy.
[^aima-reinforce]: **AIMA**, §21.5 — the policy-gradient derivation: in a nonsequential environment $\nabla_\theta \rho(\theta) = \sum_a (\nabla_\theta \pi_\theta(s_0,a)) R(a)$, rewritten by multiplying and dividing by $\pi_\theta$ into an expectation estimated from $N$ trials, $\tfrac1N \sum_j (\nabla_\theta \pi_\theta(s_0,a_j)) R(a_j)/\pi_\theta(s_0,a_j)$; the sequential generalisation uses the reward-to-go $R_j(s)$; the algorithm is REINFORCE (Williams, 1992), more effective than repeated hill climbing but still slow.
[^aima-pegasus]: **AIMA**, §21.5 — correlated sampling: pre-generate the random outcomes and evaluate every candidate policy on the same draws to cancel the shared randomness (the blackjack example); this underlies PEGASUS (Ng and Jordan, 2000) for simulator domains, whose sample requirement depends only on the complexity of the policy space, not of the domain; used for autonomous-helicopter control.
[^aima-apps]: **AIMA**, §21.6 — Applications: Samuel's checkers program, Tesauro's TD-Gammon backgammon player learned from self-play, the cart-pole balancing benchmark, and autonomous-helicopter control by policy search over a learned simulator.
[^drl-dqn]: **Mnih, Kavukcuoglu, Silver, et al.** (2015), "Human-level control through deep reinforcement learning", _Nature_ 518 — the deep Q-network: a convolutional network trained by Q-learning from raw Atari pixels, stabilized by experience replay and a periodically-updated target network, reaching human-level play across 49 games with a single architecture and hyperparameter set. (Conference precursor: Mnih et al., NeurIPS Deep Learning Workshop, 2013.)
[^drl-ppo]: **Schulman, Wolski, Dhariwal, Radford, and Klimov** (2017), "Proximal policy optimization algorithms", arXiv:1707.06347 — PPO, which bounds each policy-gradient step with a clipped surrogate objective for stability and simplicity; it builds on trust-region policy optimization (Schulman et al., 2015). Actor-critic and advantage estimation are treated in Sutton & Barto, _Reinforcement Learning: An Introduction_ (2nd ed., 2018), Ch. 13.