Comparison of Convergence Guarantees and Requirements

Summary of Convergence by Method Family

Below a summary of the convergence behavior of the major algorithms classes described in Sutton & Barto, Reinforcement Learning: An Introduction, 2nd ed. “Converges” is used in the theoretical sense—typically under tabular representation, sufficient exploration, and appropriate step-size assumptions.

Algorithm class	Typical convergence story
Tabular DP	Strongest guarantees: convergence to one of $v_\pi, v_*, \pi_*$.
Tabular MC	Converges with infinite sampling; control requires sufficient exploration.
Tabular TD	Strong convergence guarantees with infinite visits and Robbins–Monro step sizes.
Tabular off-policy TD control	Q-learning still converges under standard assumptions.
Linear, on-policy approximation	Usually well behaved; TD converges to a projected fixed point.
Nonlinear approximation	General convergence guarantees largely disappear.
Off-policy + approximation + bootstrapping	Can diverge—the deadly triad.
Gradient-TD methods	Restore convergence guarantees for important linear off-policy cases.
Policy-gradient methods	Gradient-based convergence generally means reaching a stationary/local optimum, not necessarily the globally optimal policy.

An important distinction is that “convergence” does not always mean convergence to the optimal value function. For example, on-policy linear TD prediction converges, but generally to the projected Bellman fixed point, while REINFORCE may converge to a local stationary point, and constant-step-size methods often intentionally never converge because they are designed to keep tracking a changing problem.

Convergence by Algorithm

Below is a chapter-organized summary of the convergence behavior of the major algorithms in Sutton & Barto, Reinforcement Learning: An Introduction, 2nd ed. Typical general assumptions are under tabular representation, sufficient exploration, and appropriate step-size assumptions.

Ch.	Algorithm / Method	Convergence behavior	Main assumptions / qualifications
3: Finite MDPs	Bellman expectation equation	Has a unique solution $v_\pi$ for discounted continuing tasks	Finite MDP and $\gamma<1$; suitable episodic formulations also yield well-defined values.
	Bellman optimality equation	Has a unique optimal value function $v_*$	Finite discounted MDP; Bellman optimality operator is a contraction for $\gamma<1$.
4: Dynamic Programming	Iterative Policy Evaluation	Converges to $v_\pi$	Complete model known; repeated Bellman expectation backups; $\gamma<1$, or suitable episodic setting.
	Policy Iteration	Converges to an optimal policy and $v_*$	Finite MDP; exact policy evaluation and greedy policy improvement. Terminates after finitely many policy improvements.
	Value Iteration	Converges to $v_*$	Finite discounted MDP; Bellman optimality operator is a contraction.
	Asynchronous DP	Converges to $v_*$	Every state must continue to be updated; usual finite-MDP assumptions.
	Generalized Policy Iteration	Evaluation and improvement processes can converge jointly to optimality	Depends on the particular algorithms used; competing processes stabilize when policy is greedy with respect to its own value function.
5: Monte Carlo Methods	First-visit MC prediction	Converges to $v_\pi$	Episodes terminate; every relevant state visited infinitely often; sample averages or suitable stochastic approximation.
	MC Exploring Starts control	Converges to an optimal policy/action-value function in the tabular case	Exploring starts assumption guarantees every state-action pair receives sufficient sampling.
	On-policy $\epsilon$-soft MC control	Converges toward an optimal $\epsilon$-soft policy	Every state-action pair continues to be visited; policy improvement and evaluation continue indefinitely.
	On-policy $\epsilon$-soft MC control + GLIE	Converges to an optimal deterministic policy	Greedy in the limit with infinite exploration: all $(s,a)$ pairs visited infinitely often while exploration probability tends to zero.
	Ordinary importance-sampling MC	Consistent but potentially extremely high variance	Off-policy coverage required: behavior policy must assign nonzero probability to actions that target policy may choose.
	Weighted importance-sampling MC	Converges asymptotically, usually with lower variance	Biased at finite sample sizes but consistent under coverage; denominator must receive adequate samples.
6: Temporal-Difference Learning	TD(0) prediction	Converges to $v_\pi$ with probability 1	Tabular representation; Markov environment; sufficient visits; diminishing step sizes satisfying $\sum_t \alpha_t=\infty,\ \sum_t\alpha_t^2<\infty$.
	Sarsa	Converges to $q_*$	Tabular case; GLIE policy; every state-action pair visited infinitely often; Robbins–Monro step sizes.
	Q-learning	Converges to $q_*$ with probability 1	Finite tabular MDP; every state-action pair updated infinitely often; appropriate diminishing step sizes. Behavior policy may be off-policy.
	Expected Sarsa	Can converge to $q_*$ under appropriate control/exploration conditions	Tabular case; often lower variance than Sarsa; depends on policy becoming suitably greedy.
	Double Q-learning	Converges to $q_*$ under conditions analogous to Q-learning	Tabular finite MDP; sufficient exploration and suitable step sizes. Reduces maximization bias.
7: (n)-step Bootstrapping	(n)-step TD prediction	Converges to $v_\pi$ under standard stochastic-approximation conditions	Tabular representation, sufficient sampling, appropriate step sizes. Intermediate between MC and one-step TD.
	(n)-step Sarsa	Can converge to optimal action values/policy	Tabular setting, sufficient exploration, appropriate step-size and policy conditions.
	Off-policy (n)-step methods	Convergence is more delicate	Importance sampling or related corrections needed; variance can become very large as (n) increases.
8: Planning and Learning with Tabular Methods	Dyna-Q	Can converge to $q_*$	If real/planning updates continue to cover state-action pairs and model becomes accurate; essentially repeated Q-learning updates.
	Prioritized Sweeping	Same fixed point as value iteration / Q-learning	Scheduling changes speed rather than the desired solution; convergence requires continued relevant backups.
	Trajectory Sampling	Can converge to optimal values	Requires sufficient coverage of relevant states/actions.
9: On-policy Prediction with Approximation	Gradient Monte Carlo with linear approximation	Converges to a global minimum of the mean squared value error	Linear function approximation; on-policy sampling; suitable diminishing step sizes. Objective is projection error, not necessarily exact $v_\pi$.
	Semi-gradient TD(0), linear/on-policy	Converges to a unique TD fixed point	Linear approximation; on-policy sampling; suitable step sizes; fixed point minimizes a projected Bellman error rather than ordinary squared value error.
	Semi-gradient TD with nonlinear approximation	No general convergence guarantee	May converge to local solutions, oscillate, or diverge.
10: On-policy Control with Approximation	Episodic semi-gradient Sarsa	Often converges empirically, but no broad global optimality guarantee	Function approximation couples state-action values; nonlinear approximators make guarantees especially weak.
	Differential semi-gradient Sarsa	Similar: useful convergence behavior under restricted assumptions	Continuing average-reward setting; linear approximation is better understood theoretically than nonlinear approximation.
	Tile coding + linear Sarsa	Generally stable under on-policy learning	Linear approximation avoids many instabilities of nonlinear networks, but does not imply convergence to globally optimal policy.
11: Off-policy Methods with Approximation	Off-policy semi-gradient TD	Can diverge	Even with linear function approximation. This is one manifestation of the deadly triad: function approximation + bootstrapping + off-policy learning.
	Semi-gradient Q-learning with function approximation	Can diverge	No general convergence theorem analogous to tabular Q-learning.
	Gradient-TD / TDC / GTD2	Converges under linear function approximation	Designed as true stochastic-gradient methods for well-defined objectives; suitable step sizes and coverage required.
12: Eligibility Traces	TD($\lambda$) prediction, tabular/on-policy	Converges to $v_\pi$	Standard tabular stochastic-approximation assumptions; $0\le\lambda\le1$.
	True Online TD($\lambda$)	Exactly matches the online forward view	Linear function approximation; typically exhibits stable on-policy behavior.
	Sarsa($\lambda$)	Can converge in tabular control with GLIE-style assumptions	Every state-action pair needs sufficient visitation; policy becomes greedy in the limit.
	Off-policy TD($\lambda$)	May diverge with function approximation	Same deadly-triad issue as one-step off-policy TD.
13: Policy Gradient Methods	REINFORCE	Stochastic gradient ascent on expected return; converges to a stationary/local optimum under standard assumptions	On-policy; unbiased gradient estimate; diminishing step sizes usually needed for formal stochastic-approximation convergence. No guarantee of global optimum.
	REINFORCE with baseline	Same expected gradient and asymptotic solution as REINFORCE	Baseline reduces variance without introducing bias if it does not depend on action inappropriately.
	Actor-Critic	May converge to a local stationary point under restrictive assumptions	Critic must track the value function sufficiently accurately; typically uses two-time-scale stochastic approximation in theory.