Revision
Algorithm catalogue & comparisons
Every algorithm from Chapters 2–9 in one place: what it estimates, its update target, whether it needs a model, bootstraps, or learns off-policy — and how it differs from its neighbours.
The catalogue
Filter by property (filters combine). Click a name to jump to its chapter section.
All
Prediction
Control
Model-free
Needs model
Bootstraps
Off-policy
Function approx.
Algorithm Ch Estimates Update target / rule Model Boot-straps Policy Key hyperparameters
The dimensions that classify methods
Dimension Options What it means Prediction vs control estimate $v_\pi$/$q_\pi$ · find $\pi_*$ Control is GPI: prediction + improvement. Model full distribution (DP) · sample model (MC simulation) · none DP needs $p(s',r|s,a)$; MC/TD learn from experience. Update width expected (all successors) · sample (one successor) Expected updates need a model; sample updates add variance. Update depth 1 step (TD) · n steps · whole episode (MC) Bootstrapping depth: bias ↔ variance trade-off. On- vs off-policy learn about the behaviour policy · about a different target policy Off-policy needs coverage, and IS or max/expectation targets. Representation tabular · linear · nonlinear Function approximation generalises; changes convergence guarantees.
Head-to-head comparisons
DP vs MC vs TD
DP Monte Carlo TD Target $\E_\pi[R+\gamma V(S')]$ (model) $G_t$ $R+\gamma V(S')$ (sample) Needs model yes no no Bootstraps yes no yes Bias / variance of target no sampling noise unbiased, high variance biased, low variance Online, continuing tasks — no (episodic, end of episode) yes Batch solution — min. training MSE certainty equivalence (ML model) Non-Markov robustness low higher lower
Policy iteration vs value iteration
Policy iteration Value iteration Sweep update Bellman expectation (evaluate π fully) Bellman optimality (max) — one sweep of evaluation + improvement Iterations Few, finite (strict improvement) Many cheap sweeps; converges in the limit Policy during run explicit implicit; extract at end
Sarsa vs Q-learning vs Expected Sarsa vs Double Q-learning
Sarsa Q-learning Expected Sarsa Double Q Target $R+\gamma Q(S',A')$ $R+\gamma\max_aQ(S',a)$ $R+\gamma\sum_a\pi(a|S')Q(S',a)$ $R+\gamma Q_2(S',\argmax_aQ_1(S',a))$ Policy on off on or off off Learns $q$ of ε-greedy π $q_*$ $q_\pi$ (greedy π ⇒ $q_*$) $q_*$ Cliff walking safe path, better online reward optimal edge path, falls off like Sarsa, better; α = 1 ok — Variance from $A'$ yes no no no Maximization bias some (ε-greedy max) yes some removed Cost low low sum over actions 2× memory
First-visit vs every-visit MC · ordinary vs weighted IS
First-visit Every-visit Uses first visit per episode all visits Bias unbiased biased (→ 0) Best for theory FA, eligibility traces
Ordinary IS Weighted IS Estimate $\sum\rho G/|\mathcal T|$ $\sum\rho G/\sum\rho$ Bias unbiased biased (→ 0) Variance can be infinite bounded
Exploration mechanisms
Mechanism Where How Drawback ε-greedy / ε-soft Ch 2, 5, 6 random action with prob. ε indiscriminate; caps performance Optimistic initial values Ch 2 disappointment drives trying everything temporary; stationary only UCB Ch 2 uncertainty bonus $c\sqrt{\ln t/N}$ hard beyond bandits Soft-max (gradient bandit) Ch 2 sample from $\pi\propto e^H$ α-sensitive; needs baseline Exploring starts Ch 5 random start (s, a) unrealistic in real interaction Off-policy behaviour policy Ch 5–7 explore with b, learn greedy π variance (IS) / slow tails
Multi-step off-policy options (Ch 7)
Approach Mechanism Pro Con n-step with IS multiply update by $\rho$ simple, sound high variance Control variates per-decision ρ + $(1-\rho)V$ term same expectation, less variance more complex Tree backup weight branches by π; no ρ no IS at all short effective span if π ≠ b Q(σ) mix sampling (σ=1) and expectation (σ=0) unifies all choose σ
Gradient MC vs semi-gradient TD vs LSTD (Ch 9)
Gradient MC Semi-gradient TD(0) LSTD True gradient? yes no (ignores target's dependence on w) closed form Linear convergence global optimum of VE TD fixed point; $\overline{\mathrm{VE}}\le\frac{1}{1-\gamma}\min$ TD fixed point directly Cost per step $O(d)$ $O(d)$ $O(d^2)$ Speed / data efficiency slow (variance) fast most data-efficient Step size α α none (ε regulariser), never forgets
Which algorithm when?
Situation Reasonable choice Why Full, accurate model; small state space Policy / value iteration Exact, polynomial-time Model but huge state space Asynchronous DP on visited states No full sweeps No model, episodic, need values of a few states Monte Carlo Independent of other states, no bootstrapping Simulator easy but distributions hard (blackjack) MC (ES or ε-soft) Only needs sample episodes Continuing task or very long episodes TD (Sarsa / Q-learning / Expected Sarsa) Online, step-by-step Exploration is costly (online performance matters) Sarsa / Expected Sarsa Accounts for its own exploration Want the optimal greedy policy while exploring Q-learning (Double Q if noisy rewards) Off-policy max target Learning from another agent's / logged data Off-policy MC with weighted IS, tree backup Separate behaviour and target Sparse delayed reward, slow credit propagation n-step methods (intermediate n) Propagates credit n steps per update Large/continuous state Semi-gradient TD with tile coding or Fourier features; LSTD if d small Generalisation with linear guarantees