Reinforcement Learning: Generalization and Policy Search

This builds on 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 $1 0^{20}$ states and chess around $1 0^{40}$ . No agent can visit each even once, let alone many times, so the table has to go.¹

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}_{θ} (s) = θ_{1} f_{1} (s) + θ_{2} f_{2} (s) + \dots + θ_{n} f_{n} (s) .

A backgammon utility that would need $1 0^{20}$ table entries might be captured by a few dozen weights $θ$ — an enormous compression. More important is generalization: adjusting $θ$ 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.¹

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.

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) = \frac{1}{2} (\hat{U}_{θ} (s) - u_{j} (s))^{2}$ , and gradient descent on it gives the Widrow–Hoff (delta) rule,

θ_{i} \leftarrow θ_{i} + α (u_{j} (s) - \hat{U}_{θ} (s)) \frac{\partial U ^ _{θ} ( s )}{\partial θ _{i}} .

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

θ_{i} \leftarrow θ_{i} + α [R (s) + γ \hat{U}_{θ} (s^{'}) - \hat{U}_{θ} (s)] \frac{\partial U ^ _{θ} ( s )}{\partial θ _{i}},

and the analogous update for $\hat{Q}_{θ} (s, a)$ using $max_{a^{'}} \hat{Q}_{θ} (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.

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 $π_{θ}$ , and adjusts $θ$ 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.²

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

Value-based learning fits

\hat{Q}_{θ}

to the target

Q^{*}

and reads a policy off it; policy search skips the value target and adjusts

θ

to raise the policy value

ρ (θ)

directly.

Representing the policy

A policy $π_{θ}$ 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}_{θ} (s, a)$ , one per action, linear in $θ$ or a neural network, with $π_{θ} (s) = ar g max_{a} \hat{Q}_{θ} (s, a)$ . It has a fatal defect for gradient methods, though. With discrete actions the $ar g max$ makes $π_{θ}$ a discontinuous function of $θ$ : at some settings an infinitesimal nudge to $θ$ flips the winning action, so the policy value jumps. A jump has no useful gradient, and gradient ascent stalls.²

The remedy is a stochastic policy. Instead of committing to one action, $π_{θ} (s, a)$ returns the probability of choosing $a$ in $s$ . The standard choice is the softmax over the parameterised scores,

π_{θ} (s, a) = \frac{e ^{\hat{Q}_{θ} (s, a)}}{\sum _{a^{'}} e ^{\hat{Q}_{θ} (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 $θ$ everywhere — a small change in $θ$ 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 $θ$ , and gradient ascent applies again.

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

ρ (θ)

is differentiable.

The objective: policy value

Let $ρ (θ)$ be the policy value — the expected reward-to-go when $π_{θ}$ is executed. Policy search is the optimisation problem

θ^{⋆} = ar g θ max ρ (θ) .

When the policy and environment are both deterministic and $ρ (θ)$ is available in closed form, this is an ordinary continuous optimisation: follow the policy gradient $\nabla_{θ} ρ (θ)$ uphill. When no closed form exists, we can still estimate $ρ (θ)$ by executing $π_{θ}$ 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.²

Stochasticity is what makes this hard. Empirical hill climbing wants to compare $ρ (θ)$ against $ρ (θ + Δ θ)$ , 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 $Δ θ$ . 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 $π_{θ} (s, a)$ there is a better route: an unbiased estimate of $\nabla_{θ} ρ (θ)$ read straight off the trials run at $θ$ , 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_{θ} ρ (θ) = \nabla_{θ} a \sum π_{θ} (s_{0}, a) R (a) = a \sum (\nabla_{θ} π_{θ} (s_{0}, a)) 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 $π_{θ}$ itself, so that it can be approximated by samples. Multiply and divide each term by $π_{θ} (s_{0}, a)$ :

\nabla_{θ} ρ (θ) = a \sum π_{θ} (s_{0}, a) \frac{( \nabla _{θ} π _{θ} ( s _{0} , a ) ) R ( a )}{π _{θ} ( s _{0} , a )} \approx \frac{1}{N} j = 1 \sum N \frac{( \nabla _{θ} π _{θ} ( s _{0} , a _{j} ) ) R ( a _{j} )}{π _{θ} ( s _{0} , a _{j} )},

where $a_{j}$ is the action taken on the $j$ th of $N$ trials. The outer factor $π_{θ} (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.

The importance-weighting trick. The intractable sum over all actions (left) is rewritten as an expectation under

π_{θ}

(right), so the observed trials

a_{1}, \dots, a_{N}

estimate the gradient with no need to enumerate unchosen actions.

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_{θ} ρ (θ) \approx \frac{1}{N} j = 1 \sum N \frac{( \nabla _{θ} π _{θ} ( s , a _{j} ) ) R _{j} ( s )}{π _{θ} ( s , a _{j} )} for each state s visited.

The resulting algorithm is REINFORCE. It is usually far more effective than hill climbing that reruns many trials at each $θ$ , because every trial contributes a gradient direction rather than a single noisy scalar — although it is still slower than one would like.³

Algorithm:

\textsc{Reinforce}

— policy-gradient search over a parameterised stochastic policy

\pi_\theta

1
input: differentiable policy $\pi_\theta(s,a)$ , step-size $\alpha$ , discount $\gamma$
2
$\theta \gets$ any point in parameter space
3
for each episode do
4
generate a trial $S_0, A_0, R_1, S_1, A_1, \ldots, S_T$ by executing $\pi_\theta$
5
for each visited state $S_t$ with action $A_t$ do
6
$G \gets$ reward-to-go $\sum_{k=t+1}^{T} \gamma^{k-t-1} R_k$
7
$g \gets \dfrac{\nabla_\theta\, \pi_\theta(S_t, A_t)}{\pi_\theta(S_t, A_t)}\, G$
one trial's gradient term
8
$\theta \gets \theta + \alpha\, g$
9
until the policy value $\rho(\theta)$ stops improving
10
return $\theta$

Two features make REINFORCE recognisable as gradient ascent on $ρ$ . The ratio $\nabla_{θ} π_{θ} / π_{θ}$ is the gradient of $log π_{θ}$ — 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.⁴

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.

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 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}_{θ}$ or $π_{θ}$ 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 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}_{θ} (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.⁵

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 + γ max_{a^{'}} \hat{Q}_{θ} (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}_{θ^{-}}$ 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.⁵ It is the tabular update of this lesson, generalized by a network and stabilized by two buffers.

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.

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.⁶ It is the optimizer behind reinforcement learning from human feedback in modern language models.

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.

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 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.⁷ 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, §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, §21.5 — Policy Search: keep adjusting the policy while its performance improves; a parameterised policy $π_{θ}$ (e.g. $π (s) = ar g max_{a} \hat{Q}_{θ} (s, a)$ ) with far fewer parameters than states; policy search finds $θ$ that performs well, not $θ$ that makes $\hat{Q}_{θ}$ resemble $Q^{*}$ (the $Q^{*} /10$ example); the discrete-action $ar g max$ makes the policy a discontinuous function of $θ$ , so methods use a differentiable stochastic policy $π_{θ} (s, a)$ , typically the softmax; the policy value $ρ (θ)$ is the expected reward-to-go, optimised by following $\nabla_{θ} ρ (θ)$ or by empirical hill climbing, which stochasticity makes noisy. ↩ ↩² ↩³
AIMA, §21.5 — the policy-gradient derivation: in a nonsequential environment $\nabla_{θ} ρ (θ) = \sum_{a} (\nabla_{θ} π_{θ} (s_{0}, a)) R (a)$ , rewritten by multiplying and dividing by $π_{θ}$ into an expectation estimated from $N$ trials, $\frac{1}{N} \sum_{j} (\nabla_{θ} π_{θ} (s_{0}, a_{j})) R (a_{j}) / π_{θ} (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, §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. ↩
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.) ↩ ↩²
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. ↩
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. ↩