Reinforcement learning foundations: MDPs, value iteration, and regret

Why this subject matters now

Five years ago a practitioner could treat reinforcement learning as a bag of recipes, DQN for Atari-shaped problems, PPO for everything else, tune until it works. That is no longer enough, for two reasons. First, RL moved to the center of the most consequential training pipelines in the field. RLHF and its successors fine-tune every major language model, and the interesting failure modes there, reward hacking, distribution shift between the policy that generated the data and the policy being improved, over-optimization against a learned reward, are exactly the phenomena this page's theory names and bounds. Second, the theory itself matured. Between 2017 and 2022 the community settled questions that had been open for decades, among them minimax-optimal regret for tabular exploration (Azar et al., then a line of refinements), global convergence of policy gradient methods on softmax policies (Agarwal, Kakade, Lee, and Mahajan, and Mei et al.), and a clean account of why offline RL is hard and what pessimism buys (Jin et al. and Rashidinejad et al.). An interview at a serious lab now assumes fluency in this material. The question is no longer "what is Q-learning" but "why does Q-learning overestimate, by how much, and what is the fix", not "explore with epsilon-greedy" but "state the regret of epsilon-greedy versus UCB and say where the log factor comes from". The recipes change every eighteen months. The Bellman operator, the contraction argument, and the optimism-versus-pessimism duality have not changed since they were written down, and they are what transfers.

The MDP formalism

States, actions, transitions, rewards

A Markov decision process is the tuple \( (\mathcal{S}, \mathcal{A}, P, r, \gamma) \), a state space \( \mathcal{S} \), an action space \( \mathcal{A} \), a transition kernel \( P(s' \mid s, a) \) giving the probability of landing in \( s' \) after taking action \( a \) in state \( s \), a reward function \( r(s, a) \) (sometimes \( r(s,a,s') \), the difference is bookkeeping), and a discount factor \( \gamma \in [0, 1) \). This page works mostly with finite \( \mathcal{S} \) and \( \mathcal{A} \), where the theory is complete. The function-approximation section is about what survives when finiteness is dropped. The agent interacts in rounds. It observes \( s_t \), chooses \( a_t \), receives \( r_t = r(s_t, a_t) \), and transitions to \( s_{t+1} \sim P(\cdot \mid s_t, a_t) \).

The load-bearing assumption is the Markov property, that the distribution of \( s_{t+1} \) depends on the history \( s_0, a_0, \ldots, s_t, a_t \) only through \( (s_t, a_t) \). Everything on this page, every Bellman equation, every convergence proof, is downstream of this one conditional-independence statement, because it is what lets a value be attached to a state rather than to a full history. When the property fails, as it does whenever the observation is not the full state (a camera image of a robot does not contain velocities, and a dialogue prefix does not contain the user's intent), the problem becomes a partially observed MDP, and the honest fixes are to enlarge the state (stack frames, add recurrence) until Markov approximately holds, or to move to belief states, which are distributions over hidden state and are themselves Markov. Practitioners mostly do the former and accept the approximation error.

Discounting, and why the sum converges

The object the agent maximizes is the return. In the continuing (infinite-horizon) setting, the discounted return from time \( t \) is

This infinite sum must be shown to exist before anything can be proved about it. Assume rewards are bounded, \( |r(s,a)| \le R_{\max} \) for all \( s, a \), which is true in every finite MDP and arranged by clipping in practice. Then the partial sums are absolutely convergent by comparison with a geometric series, since

where the last equality is the geometric sum \( \sum_k \gamma^k = 1/(1-\gamma) \), valid exactly because \( \gamma < 1 \). At \( \gamma = 1 \) the series can diverge (a reward of \(+1\) per step forever), and the entire apparatus of this page, bounded value functions, the contraction property, the fixed-point theorem, collapses. So \( \gamma < 1 \) is not a modeling nicety. It is the analytic device that makes value functions well-defined real numbers and, as proved below, makes the Bellman operator a contraction with modulus exactly \( \gamma \).

Two readings of \( \gamma \) coexist. In the economic reading, reward tomorrow is worth \( \gamma \) of reward today, and \( 1/(1-\gamma) \) is the effective horizon, the timescale over which the agent meaningfully plans. At \( \gamma = 0.99 \) the effective horizon is 100 steps, and rewards 460 steps away are discounted below \( e^{-4.6} \approx 0.01 \) and barely register. In the probabilistic reading, a discounted problem is equivalent to an undiscounted one in which the episode terminates at each step with probability \( 1 - \gamma \), since the probability of surviving \( k \) steps is \( \gamma^k \), exactly the weight on \( r_{t+k} \). Both readings matter in practice, and the practice section returns to the uncomfortable fact that \( \gamma \) is usually tuned as a variance-control knob rather than chosen to represent anything.

Episodic versus continuing, finite versus infinite horizon

An episodic task ends, meaning there is a set of terminal states, and the return is a finite sum up to the terminal time \( T \), which may be random. Episodic tasks fold into the infinite-horizon formalism by making terminal states absorbing with reward zero, after which all the infinite-horizon theory applies verbatim, and \( \gamma = 1 \) becomes tolerable when every policy reaches a terminal state with probability one (a proper policy, in Bertsekas's terminology for stochastic shortest path problems). The gridworld worked below uses exactly this device. A continuing task never ends, and there \( \gamma < 1 \) or the average-reward formulation (last section) is mandatory.

The finite-horizon problem, maximize \( \E[\sum_{t=0}^{H-1} r_t] \) over exactly \( H \) steps, is genuinely different in one respect. The optimal policy is generally nonstationary. With three steps left the right action can differ from the right action with one step left, even in the same state, so the optimal object is a sequence of policies \( \pi_0, \ldots, \pi_{H-1} \), computed by backward induction from the horizon. In the infinite-horizon discounted problem the future looks identical from every point in time, and one of the cleanest results of the theory (next section) is that a single stationary, deterministic policy attains the optimum. Modern theory papers, Azar et al.'s minimax bounds among them, are often stated in the episodic finite-horizon model with horizon \( H \) precisely because the nonstationarity makes the analysis cleaner. Translating between \( H \) and \( 1/(1-\gamma) \) is routine and the results correspond.

Policies and value functions

The Bellman expectation equations, derived

A policy \( \pi(a \mid s) \) is a distribution over actions in each state. A deterministic policy is the special case putting mass one on a single action. Fix \( \pi \) and define the state value and action value

where \( \E_\pi \) means actions are drawn from \( \pi \) and states from \( P \). Both are bounded by \( R_{\max}/(1-\gamma) \) by the convergence argument above, so they are well-defined. The Bellman expectation equation follows from one algebraic fact about the return, \( G_t = r_t + \gamma G_{t+1} \), plus the Markov property. The derivation is one chain of equalities.

The step that uses Markov is the third line. Conditioned on \( s_{t+1} = s' \), the distribution of \( G_{t+1} \) does not depend on \( (s_t, a_t) \), so the inner expectation collapses to \( V^\pi(s') \). The same computation one action earlier gives the action-value form and the two cross-relations.

In matrix form, stacking \( V^\pi \) into a vector in \( \R^{|\mathcal{S}|} \) and writing \( r^\pi \) and \( P^\pi \) for the policy-averaged reward vector and transition matrix, the equation reads \( V^\pi = r^\pi + \gamma P^\pi V^\pi \), one linear system, \( |\mathcal{S}| \) equations in \( |\mathcal{S}| \) unknowns. Since \( P^\pi \) is row-stochastic its spectral radius is 1, so every eigenvalue of \( \gamma P^\pi \) has modulus at most \( \gamma < 1 \), the matrix \( I - \gamma P^\pi \) is invertible, and

exists and is unique. Policy evaluation is, exactly, solving this system. The dynamic programming section does it both directly and iteratively.

The Bellman optimality equations

Define the optimal value function \( V^*(s) = \sup_\pi V^\pi(s) \), the best achievable value from each state, and \( Q^*(s,a) = \sup_\pi Q^\pi(s,a) \). The Bellman optimality equation replaces the policy average with a maximum.

The intuition is a one-step decomposition of optimal behavior. Act optimally now, then behave optimally afterward, and no policy can do better than the best first action followed by the best continuation. Turning that intuition into a theorem requires knowing that a solution exists and is unique, which is precisely what the contraction argument in the next section delivers. The right-hand side defines an operator on value functions, that operator is a \( \gamma \)-contraction, and Banach's fixed-point theorem hands us existence, uniqueness, and an algorithm in one stroke. Note the equation is nonlinear in \( V^* \) because of the max, so unlike policy evaluation it cannot be solved as a linear system. It can be solved as a linear program (minimize \( \sum_s V(s) \) subject to \( V \ge \) the right-hand side, componentwise), which is the third classical solution method after value and policy iteration and the basis of much of the approximation-theory literature.

Existence of a deterministic optimal policy

The claim is that in a finite discounted MDP there exists a single stationary deterministic policy \( \pi^* \) with \( V^{\pi^*}(s) = V^*(s) \) for every state simultaneously. The argument runs in three steps, given that \( V^* \) exists as the unique fixed point of the optimality operator (proved in the next section).

Step 1. Define \( \pi^* \) greedily as \( \pi^*(s) \in \argmax_a \big( r(s,a) + \gamma \sum_{s'} P(s' \mid s,a) V^*(s') \big) \). The argmax is over a finite set, so it is attained. This is where finiteness of \( \mathcal{A} \) is used, and in continuous-action MDPs one needs compactness and continuity assumptions in its place.

Step 2. By construction, applying the policy-specific Bellman operator of \( \pi^* \) to \( V^* \) gives back the max, which equals \( V^* \) by the optimality equation, \( T^{\pi^*} V^* = T V^* = V^* \). So \( V^* \) is a fixed point of \( T^{\pi^*} \).

Step 3. But \( T^{\pi^*} \) is itself a \( \gamma \)-contraction whose unique fixed point is \( V^{\pi^*} \) (the policy evaluation equation). Uniqueness forces \( V^{\pi^*} = V^* \), so the greedy policy achieves the optimal value. Since every policy's value is at most \( V^* \) pointwise by definition of the supremum, \( \pi^* \) is optimal, and it is stationary and deterministic.

Two consequences are worth internalizing. Randomization buys nothing in a fully observed MDP. Stochastic policies matter for exploration during learning, for partially observed problems, and for the smoothness that policy-gradient methods need, but not for the optimum itself. And the greedy map from value functions to policies is the hinge of every algorithm that follows. Value iteration, policy iteration, SARSA, and Q-learning are all different schedules for interleaving "improve the value estimate" with "act greedily against it".

Dynamic programming

Policy evaluation: a linear system, or an iteration

The evaluation equation \( V^\pi = r^\pi + \gamma P^\pi V^\pi \) can be solved directly, \( V^\pi = (I - \gamma P^\pi)^{-1} r^\pi \), at \( O(|\mathcal{S}|^3) \) cost for the solve. For the state spaces where tabular methods apply this is often the right choice, and the implementation section does exactly this inside policy iteration. The alternative is fixed-point iteration. Define the Bellman expectation operator

and iterate \( V_{k+1} = T^\pi V_k \) from any starting \( V_0 \). Whether and how fast this converges is settled by one property, proved next, which is the most important calculation in reinforcement learning theory.

The Bellman operator is a γ-contraction

Equip \( \R^{|\mathcal{S}|} \) with the sup norm \( \|V\|_\infty = \max_s |V(s)| \). The claim is that for any two value functions \( U, V \),

and the same for the optimality operator \( (TV)(s) = \max_a \big( r(s,a) + \gamma \sum_{s'} P(s' \mid s,a) V(s') \big) \). For \( T^\pi \) the computation is direct. Fix a state \( s \).

because the reward terms cancel, the probabilities are nonnegative and sum to one, and an average can never exceed the max. Taking the max over \( s \) gives the claim. For the optimality operator one extra lemma is needed, because the max does not cancel as neatly. The lemma says \( \big| \max_a f(a) - \max_a g(a) \big| \le \max_a |f(a) - g(a)| \). To prove it, let \( a^\dagger \) attain \( \max_a f(a) \). Then \( \max_a f - \max_a g \le f(a^\dagger) - g(a^\dagger) \le \max_a |f - g| \), and by symmetry the same bounds the other direction. Applying the lemma pointwise in \( s \), with \( f(a) \) and \( g(a) \) the bracketed one-step expressions under \( U \) and \( V \), reduces the optimality case to the expectation case, and the same \( \gamma \) factor comes out.

Now invoke Banach's fixed-point theorem. A contraction on a complete metric space has exactly one fixed point, and iterating the map from any starting point converges to it geometrically. \( (\R^{|\mathcal{S}|}, \|\cdot\|_\infty) \) is complete, so the theorem applies to both operators, and everything claimed earlier lands at once. \( V^\pi \) exists and is the unique fixed point of \( T^\pi \), \( V^* \) exists and is the unique solution of the Bellman optimality equation, and the iterates obey

The error shrinks by at least the factor \( \gamma \) every sweep, so reaching accuracy \( \epsilon \) takes at most \( \log(\|V_0 - V^*\|_\infty / \epsilon) / \log(1/\gamma) \) iterations, each costing \( O(|\mathcal{S}|^2 |\mathcal{A}|) \) for the expectation. The bound is worst-case. On the stochastic gridworld below, with \( \gamma = 0.9 \), the measured per-sweep error ratio \( \|V_{k+1} - V^*\| / \|V_k - V^*\| \) averaged 0.585 with a maximum of 0.763 across sweeps, comfortably inside the guaranteed 0.9, because short paths to the absorbing states contract faster than the worst case. The theorem gives the ceiling. The structure of the particular MDP decides how far below it you run.

A gridworld evaluated by hand

The classic evaluation example comes from Sutton and Barto, chapter 4. Take a 4×4 grid, terminal states in the top-left and bottom-right corners, four actions that move one cell (bumping a wall leaves the state unchanged), reward \( -1 \) on every step, and \( \gamma = 1 \) (legitimate here because every policy reaches a terminal corner with probability one). The policy to evaluate is uniform random over the four actions. \( V^\pi(s) \) is then \( -1 \) times the expected number of steps a random walk takes to reach a corner. Iterating \( V_{k+1} = T^\pi V_k \) from \( V_0 = 0 \) produces the value tables below, taken from the run stored in classes/data/rl-theory.json.

  0.0   0.0   0.0   0.0
  0.0   0.0   0.0   0.0
  0.0   0.0   0.0   0.0
  0.0   0.0   0.0   0.0

  0.0  -1.0  -1.0  -1.0
 -1.0  -1.0  -1.0  -1.0
 -1.0  -1.0  -1.0  -1.0
 -1.0  -1.0  -1.0   0.0

  0.0  -1.8  -2.0  -2.0
 -1.8  -2.0  -2.0  -2.0
 -2.0  -2.0  -2.0  -1.8
 -2.0  -2.0  -1.8   0.0

  0.0  -2.4  -2.9  -3.0
 -2.4  -2.9  -3.0  -2.9
 -2.9  -3.0  -2.9  -2.4
 -3.0  -2.9  -2.4   0.0

  0.0  -6.1  -8.4  -9.0
 -6.1  -7.7  -8.4  -8.4
 -8.4  -8.4  -7.7  -6.1
 -9.0  -8.4  -6.1   0.0

  0.0 -14.0 -20.0 -22.0
-14.0 -18.0 -20.0 -20.0
-20.0 -20.0 -18.0 -14.0
-22.0 -20.0 -14.0   0.0

The \( k = 2 \) entry adjacent to a corner is worth verifying by hand, because it exercises the operator exactly once. Take the state just right of the top-left terminal. Its four moves under the random policy lead to the terminal (value 0), the state two to the right (\( V_1 = -1 \)), the state below (\( V_1 = -1 \)), and itself via the wall bump (\( V_1 = -1 \)). So \( V_2 = \tfrac14 \sum ( -1 + V_1(s') ) = -1 + \tfrac14 (0 - 1 - 1 - 1) = -1.75 \), which rounds to the \( -1.8 \) in the table. The converged values say a random walk started next to a corner takes 14 expected steps to terminate, and one started in the far corner takes 22. Convergence here is slow (426 sweeps) precisely because \( \gamma = 1 \) removes the geometric contraction and leaves only the absorbing-state mixing to do the work. The discounted problems below converge in a few dozen sweeps.

The policy improvement theorem, proved

Evaluation alone does not improve behavior. The improvement step rests on one theorem. Let \( \pi \) and \( \pi' \) be policies with

Then \( V^{\pi'}(s) \ge V^\pi(s) \) for all \( s \), and if the hypothesis is strict anywhere, the conclusion is strict there. In words, if in every state taking \( \pi' \)'s action once and then reverting to \( \pi \) is at least as good as following \( \pi \), then switching to \( \pi' \) forever is at least as good everywhere. The proof unrolls the hypothesis one step at a time.

Each inequality applies the hypothesis at the next state and each equality is the Bellman expansion. The residual term \( \gamma^k V^\pi(s_{t+k}) \) is bounded by \( \gamma^k R_{\max}/(1-\gamma) \to 0 \), which is what justifies passing to the limit, and is again where \( \gamma < 1 \) earns its keep. The greedy policy \( \pi'(s) = \argmax_a Q^\pi(s,a) \) satisfies the hypothesis by construction, since a max is at least the \( \pi \)-average, so greedy improvement never hurts and strictly helps wherever the greedy action beats the current policy's mixture.

Policy iteration and its finite convergence

Policy iteration alternates exact evaluation and greedy improvement. Evaluate \( V^{\pi_k} \) by the linear solve, set \( \pi_{k+1} \) greedy with respect to it, and stop when the policy is unchanged. Convergence in finitely many rounds is immediate from two facts. First, by the improvement theorem the sequence \( V^{\pi_0} \le V^{\pi_1} \le \cdots \) is pointwise monotone, and strictly increases somewhere unless \( \pi_{k+1} = \pi_k \) is already greedy against its own value function, in which case \( V^{\pi_k} \) satisfies the Bellman optimality equation and \( \pi_k \) is optimal. Second, there are only \( |\mathcal{A}|^{|\mathcal{S}|} \) deterministic policies, and monotonicity means none can repeat. So the algorithm terminates at an optimal policy in at most \( |\mathcal{A}|^{|\mathcal{S}|} \) rounds. That worst case is far too pessimistic. On the stochastic gridworld below (16 states, 4 actions, so \( 4^{16} \approx 4.3 \) billion policies), measured policy iteration converged in 3 rounds, and the modern theory explains why, with results showing policy iteration behaves like Newton's method on the Bellman equation and, more recently, strongly polynomial bounds for fixed \( \gamma \) (a line of work due to Ye and successors). The trade against value iteration is per-round cost. Each policy iteration round pays an \( O(|\mathcal{S}|^3) \) solve to remove far more error than one \( O(|\mathcal{S}|^2 |\mathcal{A}|) \) value-iteration sweep does.

Value iteration and the 2γε/(1−γ) bound

Value iteration iterates the optimality operator, \( V_{k+1} = T V_k \), and extracts a greedy policy at the end. Two questions need answers, when to stop and what the extracted policy is worth. Both are answered by the stopping-rule bound. Suppose a sweep produces a small change, \( \| V_{k+1} - V_k \|_\infty \le \epsilon \). First bound the distance to \( V^* \), using the triangle inequality and the contraction,

and solving for the left side gives \( \| V_{k+1} - V^* \|_\infty \le \gamma \epsilon / (1 - \gamma) \). Now let \( \pi_g \) be greedy with respect to \( V_{k+1} \), so that \( T^{\pi_g} V_{k+1} = T V_{k+1} \), and bound how far \( \pi_g \)'s actual value sits from \( V_{k+1} \).

so \( \| V^{\pi_g} - V_{k+1} \|_\infty \le \gamma \epsilon / (1-\gamma) \) as well (the middle step used \( T V_{k+1} = T^{\pi_g} V_{k+1} \) and \( V_{k+1} = T V_k \)). Adding the two pieces gives

This is the operational guarantee of value iteration. Stop when a sweep moves no value by more than \( \epsilon \), act greedily on what you have, and the resulting policy loses at most \( 2\gamma\epsilon/(1-\gamma) \) value in any state. The \( 1/(1-\gamma) \) amplification is characteristic and shows up throughout RL theory. Small Bellman errors can cost a full effective horizon's worth of return. On the measured gridworld run, stopping at \( \epsilon = 10^{-4} \) with \( \gamma = 0.9 \) gives a guaranteed policy loss of at most \( 2 \times 0.9 \times 10^{-4} / 0.1 = 1.8 \times 10^{-3} \). The measured loss was 0.0, because the greedy policy had already locked onto the exact optimum long before the values finished converging. That gap, policies converging before values, is typical and is the observation that motivates policy iteration in the first place.

The gridworld solved: value iteration, policy iteration, and the tables

The running control example for the rest of the page is a 4×4 gridworld with stochastic dynamics, chosen small enough to print and interesting enough to have a nontrivial optimal policy.

+------+------+------+------+
| S0   | S1   | S2   | GOAL |   goal: terminal, reward +1 on entry
+------+------+------+------+
| S4   | S5   | S6   | PIT  |   pit:  terminal, reward -1 on entry
+------+------+------+------+
| S8   | S9   | S10  | S11  |   all other rewards 0, gamma = 0.9
+------+------+------+------+   actions U/D/L/R; intended direction
| S12  | S13  | S14  | S15  |   w.p. 0.8, each perpendicular w.p. 0.1;
+------+------+------+------+   bumping a wall stays in place

Value iteration from \( V_0 = 0 \) reached a sup-norm change below \( 10^{-10} \) in 46 sweeps. Policy iteration from the all-U policy converged in 3 evaluation-improvement rounds to the same answer, agreeing with the value-iteration solution to \( 10^{-9} \). The tables show the converged optimal values and policy.

0.707  0.815  0.943  GOAL
0.629  0.701  0.642  PIT
0.557  0.605  0.551  0.386
0.493  0.523  0.482  0.419

  →      →      →    GOAL
  ↑      ↑      ↑    PIT
  ↑      ↑      ↑     ↓
  ↑      ↑      ↑     ←

The tables repay a minute of reading. Values decay roughly geometrically with distance from the goal, as \( \gamma^d \) predicts. The column next to the pit is depressed. S6 sits at 0.642 against its left neighbor's 0.701, because moving up from S6 slips right into the pit with probability 0.1 and the value function prices that risk. And the policy at S11, directly below the pit, is Down. The agent takes the long way around the bottom rather than walk the pit-adjacent column, which is not a choice anyone hand-coded. It falls out of the max in the Bellman equation. This MDP, with these exact numbers, is re-solved by Q-learning from samples alone in the control section.

Asynchronous dynamic programming and prioritized sweeping

Nothing in the contraction argument requires full sweeps. Updating states one at a time, in place, using the freshest values of the others (Gauss–Seidel style) still converges to \( V^* \) provided every state continues to be updated infinitely often. The proof extends the contraction argument to asynchronous updates and is classical (Bertsekas covers it in depth). This matters for two reasons. Practically, in-place sweeps propagate information faster than Jacobi-style simultaneous sweeps, often by a constant factor worth having. Conceptually, it licenses updating states in any order, including the order in which a simulated or real trajectory happens to visit them, which is precisely what the sample-based methods later on this page do. TD learning is asynchronous DP with expectations replaced by samples. Prioritized sweeping (Moore and Atkeson, 1993) chooses the order greedily. Keep a priority queue keyed by each state's Bellman error, pop the largest, update it, then push its predecessors, whose errors just changed. On problems where reward is sparse, a goal state's value change propagates backward through exactly the states that need revisiting instead of through full sweeps, and the speedups over blind iteration are routinely one to two orders of magnitude in update count. The same idea reappears in deep RL as prioritized experience replay, with TD error standing in for Bellman error.

Monte Carlo methods

Learning from complete returns

Dynamic programming needs \( P \) and \( r \). When only sampled experience is available, the most direct estimator comes from the definition itself. \( V^\pi(s) \) is an expectation of the return, so run episodes under \( \pi \), record the return observed after each visit to \( s \), and average. First-visit Monte Carlo averages only the return following the first visit to \( s \) in each episode. Every-visit Monte Carlo averages the returns following all visits. The distinction sounds pedantic and is not. First-visit returns are independent across episodes and each is an unbiased draw of the quantity being estimated, so the estimator is unbiased with variance \( \sigma^2_s / n \) after \( n \) first visits, and ordinary i.i.d. theory (laws of large numbers, CLT confidence intervals) applies off the shelf. Every-visit returns from the same episode overlap, the later ones are statistically entangled with the earlier ones through shared future rewards, and the estimator is biased at any finite \( n \). It remains consistent, its bias falls as \( O(1/n) \), and its mean squared error is often lower than first-visit's because it uses more data. Singh and Sutton (1996) work out both sets of properties. In practice the choice rarely decides success, but knowing which estimator has which property is exactly the kind of question that separates reading about RL from knowing it.

Monte Carlo's defining trade is that the target \( G_t \) is an unbiased sample of \( V^\pi(s_t) \), while its variance accumulates the randomness of every action, transition, and reward until the end of the episode. In long episodes that variance is the binding constraint, and reducing it is the entire reason temporal-difference methods exist. Monte Carlo also only produces a target when an episode finishes, so it does not apply to continuing tasks at all without truncation, and it cannot update mid-episode.

Off-policy evaluation by importance sampling

Suppose episodes are generated by a behavior policy \( b \) but the quantity wanted is \( V^\pi \) for a different target policy \( \pi \), the fundamental setup of off-policy evaluation. Importance sampling reweights each trajectory by the ratio of its probability under the two policies. For a trajectory segment \( a_t, s_{t+1}, a_{t+1}, \ldots, s_T \), the transition probabilities cancel between numerator and denominator (they do not depend on the policy), leaving

provided \( b \) has coverage, meaning \( b(a \mid s) > 0 \) wherever \( \pi(a \mid s) > 0 \). The ordinary importance sampling estimator averages \( \rho \, G \) over episodes and is unbiased. The weighted estimator normalizes by the sum of the ratios instead of the count, \( \hat V = \sum_i \rho_i G_i / \sum_i \rho_i \). It is biased at finite \( n \) (its first sample gives \( G_1 \) exactly, regardless of \( \rho_1 \)), consistent, and its variance stays bounded because the weights are self-normalized into a convex combination. The standard practical verdict, ordinary IS for unbiasedness in analysis, weighted IS for anything that must actually work, comes from the variance analysis in the next problem, which shows the ordinary estimator's variance growing exponentially with horizon. Per-decision importance sampling (Precup, Sutton, and Singh, 2000) improves both by weighting each reward only by the ratios up to its own timestep, since later actions cannot influence earlier rewards.

The exploring-starts problem

Using Monte Carlo for control, not just evaluation, needs \( Q^\pi \) rather than \( V^\pi \), because improving a policy without a model requires comparing actions, and that exposes a structural problem. A deterministic policy generates data about only one action per state, leaving the other \( |\mathcal{A}| - 1 \) entries of \( Q \) unestimated, and the greedy improvement step then maximizes over garbage. The classical patch is exploring starts. Assume every state-action pair has positive probability of beginning an episode, so every pair keeps being sampled no matter what the current policy does. Monte Carlo with exploring starts (Monte Carlo ES) alternates episode generation, Q-estimation, and greedy improvement, and empirically converges. Proving that it converges was open for decades, far longer than the algorithm's simplicity suggests it should have been, with proofs available only under additional conditions (Tsitsiklis's 2002 analysis of optimistic policy iteration is the closest classical treatment). The assumption itself is the real objection. Real environments do not let you teleport into arbitrary state-action pairs. The practical alternatives are soft policies (\( \epsilon \)-greedy, which keeps every action's probability at least \( \epsilon / |\mathcal{A}| \) and converges to the best \( \epsilon \)-soft policy) or off-policy learning with a separate behavior policy, which is the road that leads to Q-learning. The exploration sections later on this page replace all of these heuristics with methods that carry actual guarantees.

Temporal-difference learning

TD(0) as stochastic approximation

The Bellman expectation equation says \( V^\pi(s) = \E[\, r_t + \gamma V^\pi(s_{t+1}) \mid s_t = s \,] \). Monte Carlo ignores this structure and regresses on raw returns, while dynamic programming uses it with known expectations. TD(0) uses the structure with sampled expectations. On observing \( (s_t, r_t, s_{t+1}) \), move the estimate toward a sampled version of the right-hand side,

This is a Robbins–Monro stochastic approximation scheme for solving \( \E[\delta_t \mid s_t = s] = 0 \), which is exactly the Bellman equation at \( s \). The target \( r_t + \gamma V(s_{t+1}) \) is an unbiased sample of \( (T^\pi V)(s_t) \) for the current \( V \), so on average the update moves \( V \) toward \( T^\pi V \), and the contraction property pulls the whole process toward \( V^\pi \). The classical convergence theorem (Jaakkola, Jordan, and Singh, 1994, and independently Tsitsiklis, 1994, both reducing TD to stochastic approximation) states that tabular TD(0) converges to \( V^\pi \) with probability 1 provided every state is visited infinitely often and the step sizes satisfy the Robbins–Monro conditions

for example \( \alpha_t = 1/t \) or \( 1/t^{0.7} \). The first condition ensures the steps can travel arbitrarily far, so a bad initialization cannot trap the estimate. The second ensures the accumulated noise has finite variance, so the estimate settles rather than jittering forever. A constant step size, which is what practice almost always uses, violates the second condition and yields convergence in distribution to a ball around \( V^\pi \) whose radius scales with \( \alpha \). This is the perpetual tracking regime, often what you want in nonstationary problems, and it is why the violation is tolerated.

TD versus Monte Carlo: the bias-variance trade

The two methods bracket a spectrum. The Monte Carlo target \( G_t \) is unbiased for \( V^\pi(s_t) \) and has the variance of an entire episode. The TD target \( r_t + \gamma V(s_{t+1}) \) contains one step of environment randomness plus a bootstrap from the current estimate \( V(s_{t+1}) \), which is wrong during learning, so the target is biased. In exchange its variance is one step's worth. Neither dominates universally, but TD has a structural advantage that the batch analysis makes precise (Sutton and Barto, section 6.3). Given a fixed batch of episodes, batch TD(0) converges to the value function of the maximum-likelihood MDP fitted to the data, the certainty-equivalence solution, while batch Monte Carlo converges to the least-squares fit of observed returns. The certainty-equivalence solution generalizes across states through the estimated transition structure. The Monte Carlo solution treats each state's returns in isolation. On the standard 5-state random-walk testbed (states with true values \( 1/6, \ldots, 5/6 \), measured numbers in classes/data/rl-theory.json), after 100 episodes averaged over 200 runs, TD(0) with \( \alpha = 0.1 \) reached RMS error 0.055 while the Monte-Carlo-equivalent \( \lambda = 1 \) run at its best-of-tested step size reached 0.087, a gap entirely attributable to target variance.

n-step returns and TD(λ)'s forward view

Between the one-step target and the full return sit the n-step returns,

which take \( n \) steps of real reward before bootstrapping. Here \( n = 1 \) is TD(0) and \( n \to \infty \) (episodic) is Monte Carlo. Rather than pick one \( n \), TD(λ) averages all of them with geometrically decaying weights. The \( \lambda \)-return is

where the \( (1-\lambda) \) prefactor makes the weights sum to one (for an episode ending at \( T \), the tail weight \( \lambda^{T-t-1} \) collapses onto the full return \( G_t \)). At \( \lambda = 0 \) only \( G^{(1)} \) survives. At \( \lambda = 1 \) the weights concentrate on the full return and the method is Monte Carlo. This is the forward view, a well-defined compound target for each state, unusable online as stated because \( G_t^\lambda \) depends on the entire future of the episode.

The backward view, eligibility traces, and the equivalence theorem

The backward view makes the same computation causal. Maintain an eligibility trace \( z \), one entry per state, decayed and bumped each step, and broadcast the current TD error to every state in proportion to its trace.

A state visited \( k \) steps ago has trace \( (\gamma\lambda)^k \) and receives that fraction of today's TD error. The equivalence theorem says this is not an approximation of the forward view but the same algorithm. For a fixed value function, the identity

expresses the forward-view error at \( t \) as a discounted sum of future one-step TD errors. The derivation for \( \lambda = 1 \) shows the mechanism, a pure telescope.

adding and subtracting \( \gamma V(s_{t+1}) \) at each level and recursing. The general-\( \lambda \) identity is the same algebra with \( \gamma\lambda \) as the decay, using the recursion \( G_t^\lambda = r_t + \gamma\big( (1-\lambda) V(s_{t+1}) + \lambda G_{t+1}^\lambda \big) \). Summing the per-visit forward updates over an episode and exchanging the order of the double sum reproduces exactly the trace-weighted backward updates. Offline (updates applied at episode end), the two views produce identical total updates. Online, with \( V \) changing mid-episode, they differ at \( O(\alpha^2) \). The true-online TD(λ) of van Seijen and Sutton (2014) modifies the trace (a "dutch trace") to make the online equivalence exact. The trace parameter is a bias-variance dial with a credit-assignment reading. \( \lambda \) controls how far back along the trajectory each surprise propagates in a single update, which is why intermediate \( \lambda \) often trains fastest even though \( \lambda = 0 \) has the lowest target variance. The same \( (\gamma\lambda) \)-weighted sum of TD errors, rediscovered as generalized advantage estimation, is the variance-reduction backbone of modern policy-gradient implementations, covered on the policy gradients page.

Control: SARSA, Q-learning, and maximization bias

On-policy control: SARSA

Moving from prediction to control replaces \( V \) with \( Q \) and interleaves improvement. SARSA applies the TD(0) idea to the action-value Bellman expectation equation, updating from the quintuple \( (s_t, a_t, r_t, s_{t+1}, a_{t+1}) \) that names it,

where \( a_{t+1} \) is the action the agent actually takes, drawn from its current (typically \( \epsilon \)-greedy) policy. SARSA is on-policy. It estimates \( Q^\pi \) for the policy being followed, exploration included, and improves that policy as it goes. The tabular convergence result (Singh, Jaakkola, Littman, and Szepesvári, 2000) requires the by-now-familiar conditions, every pair visited infinitely often and Robbins–Monro step sizes, plus a condition on the policy schedule called GLIE, greedy in the limit with infinite exploration, for instance \( \epsilon_t \to 0 \) slowly enough that exploration never fully stops early. Under GLIE, SARSA converges to \( Q^* \) and its policy to an optimal policy.

Off-policy control: Q-learning

Q-learning (Watkins, 1989) makes one substitution that changes the estimand entirely. It bootstraps from the best next action rather than the taken one,

The target is now a sampled version of the Bellman optimality operator applied to \( Q \), so the fixed point being tracked is \( Q^* \) regardless of what policy generated the data. That is the precise meaning of off-policy. The estimated quantity is decoupled from the behavior. What it buys is substantial. Exploration policy design is unconstrained (no GLIE schedule is needed for the values to converge, only coverage), data from old policies, other agents, or logs remains usable, and one stream of behavior can in principle feed many value functions. The convergence theorem (Watkins and Dayan, 1992, with the modern proof route again going through Jaakkola, Jordan, and Singh's stochastic-approximation lemma) needs only infinitely-often visitation of all pairs and Robbins–Monro steps. Tabular Q-learning converges to \( Q^* \) with probability 1.

What off-policy costs shows up twice on this page. Here, in the tabular setting, the cost is behavioral. Q-learning's values reflect the greedy policy while its behavior includes exploration, so during learning it walks cliff edges that SARSA, which prices its own exploration into \( Q \), learns to avoid (in the cliff-walking example in Sutton and Barto, SARSA takes the safe path and earns more during training, while Q-learning learns the optimal path and falls off it while exploring). Later, in the function-approximation section, the cost becomes existential. Off-policy bootstrapping with function approximation is one leg of the deadly triad and can diverge outright. Expected SARSA sits between the two methods, replacing the sampled next action with its expectation under the target policy, \( r_t + \gamma \sum_{a'} \pi(a' \mid s_{t+1}) Q(s_{t+1}, a') \), removing the variance of the next-action draw at the price of a sum over actions. With a greedy target policy it is Q-learning, and with the behavior policy as target it is a lower-variance SARSA (van Seijen et al., 2009, analyze exactly when it dominates).

Q-learning re-solves the gridworld from samples

On the slip-gridworld solved exactly by dynamic programming above, tabular Q-learning was run for 400,000 environment steps (56,248 episodes) with \( \epsilon = 0.1 \) exploration, random restart states, and per-pair step sizes \( \alpha = 1/n(s,a)^{0.7} \) satisfying Robbins–Monro. The measured outcome, against the exact \( Q^* \) from value iteration, was a maximum absolute Q error of 0.119 (on values spanning \( \pm 0.94 \)), a greedy policy agreeing with \( \pi^* \) in 13 of 14 non-terminal states, and, the number that actually matters, a policy value loss \( \|V^{\pi_{\text{greedy}}} - V^*\|_\infty = 0.0030 \). The one disagreeing state is S6, where the exact gap between the best action (Up, \( Q^* = 0.6418 \)) and the runner-up (Left, \( Q^* = 0.6394 \)) is 0.0024, smaller than the residual noise in the estimates, so the sampled max lands on either action. This is worth internalizing as a general lesson about evaluating RL. Policy identification fails precisely where the action gap is small, and where the action gap is small, misidentification is cheap. Judging an agent by percent-of-actions-matched overstates the problem. Judging by value loss is the honest metric, and theory bounds are stated in value loss for this reason.

Maximization bias, worked numerically

The max in Q-learning's target is also a statistical trap. For any random estimates \( \hat Q(a) \) of true values \( q(a) \), Jensen's inequality applied to the convex max function gives

with strict inequality whenever the estimates are noisy and competing. The max operator selects favorable noise, then uses the same inflated value as the estimate. Q-learning commits this sin at every bootstrap, so its targets carry systematic upward bias wherever several actions have similar values and noisy estimates, and the bias compounds through the bootstrap chain. Double learning (van Hasselt, 2010) breaks the correlation with two tables. One selects the argmax and the other evaluates it,

with the tables' roles swapped on alternate updates. Since \( Q_2 \)'s noise is independent of the selection made with \( Q_1 \), the evaluation is unbiased given the selection, and the systematic inflation disappears (a mild downward bias can replace it, which is usually harmless). The deep version, Double DQN, is a two-line change that measurably improved Atari scores. Details are on the Q-learning page.

What the tabular guarantees actually say

It is worth collecting the exact shape of the classical guarantees, because every one of them is conditional and the conditions are routinely violated in practice. Tabular TD(0), SARSA (with GLIE), Q-learning, and double Q-learning all converge with probability 1 under (i) a finite MDP, (ii) every relevant state or state-action pair visited infinitely often, (iii) Robbins–Monro step sizes, and for SARSA (iv) a GLIE policy schedule. None of these theorems says anything about rate. The asymptotic guarantee is compatible with arbitrarily slow learning, and the exploration section is precisely the study of what it costs to make condition (ii) happen efficiently rather than by luck. And all of them are statements about tables, one cell per state-action pair, no generalization. The next section is about what breaks when the table is replaced by a function approximator, which is the single largest gap between this theory and the deep RL built on top of it.

Function approximation and the deadly triad

The projected Bellman equation

When \( |\mathcal{S}| \) is astronomical the table is replaced by a parameterized family. The cleanest analyzable case is linear, \( V_\theta = \Phi \theta \) with \( \Phi \in \R^{|\mathcal{S}| \times d} \) a feature matrix and \( \theta \in \R^d \), \( d \ll |\mathcal{S}| \). Immediately a structural problem appears. The Bellman backup \( T^\pi V_\theta \) generally leaves the representable subspace \( \{\Phi\theta\} \), so the fixed-point equation \( V = T^\pi V \) has no solution inside the family. The standard resolution is to compose the backup with a projection back onto the subspace. Weight states by the stationary distribution \( d^\pi \) of the policy being evaluated, let \( D = \diag(d^\pi) \), define the weighted norm \( \|V\|_D^2 = \sum_s d^\pi(s) V(s)^2 \), and let \( \Pi = \Phi (\Phi\T D \Phi)^{-1} \Phi\T D \) be the orthogonal projection in that geometry. The object TD methods actually solve is the projected Bellman equation.

Existence and uniqueness again come from a contraction argument, but a more delicate one, and the delicacy is exactly where the deadly triad lives. Two facts combine. First, \( \Pi \) is a nonexpansion in \( \|\cdot\|_D \), as orthogonal projections always are in their own inner product. Second, \( P^\pi \) is a nonexpansion in \( \|\cdot\|_D \) provided \( d^\pi \) is the stationary distribution of \( P^\pi \). By Jensen, \( \|P^\pi V\|_D^2 = \sum_s d^\pi(s) \big( \sum_{s'} P^\pi(s' \mid s) V(s') \big)^2 \le \sum_s d^\pi(s) \sum_{s'} P^\pi(s' \mid s) V(s')^2 = \sum_{s'} d^\pi(s') V(s')^2 = \|V\|_D^2 \), where the last equality is precisely stationarity, \( \sum_s d^\pi(s) P^\pi(s' \mid s) = d^\pi(s') \). Hence \( \Pi T^\pi \) is a \( \gamma \)-contraction in \( \|\cdot\|_D \), it has a unique fixed point \( \Phi\theta^* \) (the TD fixed point), and linear TD(0) with on-policy sampling converges to it with probability 1. This is the theorem of Tsitsiklis and Van Roy (1997), and the stationarity step is the exact point where off-policy sampling breaks the proof. Sample states from any distribution other than \( d^\pi \) and \( P^\pi \) can expand the norm, the composed operator can cease to be a contraction, and divergence becomes possible rather than merely unproven.

How good is the TD fixed point?

The TD fixed point is not the best approximation of \( V^\pi \) in the family. That would be \( \Pi V^\pi \). The gap is bounded, with a proof short enough to give in full. Using the Pythagorean identity in \( \|\cdot\|_D \) (the error decomposes orthogonally through the projection) and then the contraction,

where the middle line used \( \Phi\theta^* = \Pi T^\pi \Phi\theta^* \) and \( V^\pi = T^\pi V^\pi \) (so \( \Pi T^\pi V^\pi = \Pi V^\pi \)). Rearranging gives

TD's answer is at most \( 1/\sqrt{1-\gamma^2} \) times worse than the best the features could ever do. At \( \gamma = 0.9 \) the factor is 2.29, and at \( \gamma = 0.99 \) it is 7.09. The bound is tight in the worst case, and the blow-up as \( \gamma \to 1 \) is real. With long-horizon bootstrapping, mediocre features do not just cap quality, they get amplified. When the features can represent \( V^\pi \) exactly the right side is zero and TD finds it, so the tabular results are the special case \( \Phi = I \).

The deadly triad, stated precisely

Three ingredients, each individually safe.

1. Function approximation. The value estimate lives in a restricted family, so updates to one state move others. 2. Bootstrapping. Targets contain the current estimate (TD, Q-learning, DP), so errors feed back. 3. Off-policy training. The updating distribution differs from the target policy's stationary distribution, so the norm-nonexpansion argument above fails. Any two can be combined with guarantees. Tabular off-policy bootstrapping is Q-learning, which converges. On-policy bootstrapping with linear approximation is Tsitsiklis and Van Roy's theorem. Off-policy function approximation without bootstrapping is ordinary supervised regression on Monte Carlo targets, convergent by SGD theory. All three together admit divergence, not slow learning, not convergence to a poor answer, but parameters escaping to infinity on a problem where the exact value function is representable. The name "deadly triad" is Sutton and Barto's. van Hasselt et al. (2018) study empirically how much of the danger survives in deep Q-learning, finding that divergence is real but rarer than the theory's worst case, and that target networks and replay mitigate it, which is part of why DQN works at all.

Baird's counterexample (1995) is the canonical demonstration. It has seven states arranged as a star and two actions, among them a dash action that always jumps to the hub state, with a uniform action distribution as behavior, all rewards zero, so \( V^\pi = 0 \) for every policy, and a linear parameterization with eight features for seven states that can represent the zero function exactly (set all \( \theta = 0 \)). Train semi-gradient TD(0) off-policy, with the behavior policy visiting all states uniformly while the target policy always dashes to the hub. The expected update matrix has an eigenvalue with positive real part under this distribution mismatch, and \( \theta \) spirals to infinity. The values it implies grow without bound even though the perfect answer is sitting at the origin. The mechanism, in words, is that the hub state's feature weight is shared with the spoke states' features, the behavior distribution updates the spokes far more often than the target-policy dynamics would, and each spoke update pushes the shared weight in a direction the hub's own (rare) updates cannot correct fast enough. The distribution mismatch converts a stable feedback loop into an unstable one, exactly the instability that the stationarity step in the convergence proof was excluding.

Gradient TD and the semi-gradient distinction

The standard TD update with function approximation, \( \theta \leftarrow \theta + \alpha \, \delta_t \, \nabla_\theta V_\theta(s_t) \), is called a semi-gradient because it treats the target \( r + \gamma V_\theta(s') \) as a constant, differentiating only through the prediction. It is not the gradient of any fixed objective function, which is precisely why divergence is possible and why the convergence proofs go through fixed-point arguments instead of optimization arguments. Gradient-TD methods repair this by choosing an explicit objective, the mean-squared projected Bellman error \( \mathrm{MSPBE}(\theta) = \| \Phi\theta - \Pi T^\pi \Phi\theta \|_D^2 \), and performing true stochastic gradient descent on it. The gradient contains a product of expectations, which a single sample cannot estimate without bias, so GTD2 and TDC (Sutton, Maei, Precup, Bhatnagar, Silver, Szepesvári, and Wiewiora, 2009) carry a second parameter vector estimating one factor and update the two on different timescales. Convergence then holds under off-policy sampling with linear approximation, at \( O(d) \) per step. Emphatic TD (Sutton, Mahmood, and White, 2016) achieves off-policy stability differently, reweighting updates by a followon trace so the effective distribution restores the contraction. The honest summary of a decade of experience is that these methods fix the counterexamples, cost roughly double per step, are more sensitive to their extra step size, and have seen limited production adoption. Deep RL mostly ships the unsound semi-gradient with stabilizers (target networks, replay, clipping) and accepts the residual risk.

Control with function approximation

For control the situation is genuinely worse. The policy improvement theorem, the engine of every convergence argument in the tabular control section, has no exact analog. Improving against an approximate \( \hat Q \) can degrade the true policy value, and the greedy step is no longer monotone. What survives is an error-propagation bound for approximate policy iteration (Bertsekas and Tsitsiklis, 1996). If each evaluation is off by at most \( \epsilon \) in sup norm and each improvement step is exact, then

a \( 1/(1-\gamma)^2 \) amplification against value iteration's \( 1/(1-\gamma) \), and the sequence of policies need not converge at all. It can cycle among several policies whose values all sit within the bound (Bertsekas calls this chattering). Sharper statements replace the sup norm with distribution-weighted norms and concentrability coefficients, foreshadowing the offline-RL section. The practical consequence is visible across deep RL. Value-based control with approximation oscillates, is seed-sensitive, and needs its stabilizers, not because implementations are sloppy but because the underlying operator lost its monotonicity, and the theory says exactly which property went missing.

Exploration with theory: bandits, regret, and optimism

The multi-armed bandit and the definition of regret

Strip the MDP of states and dynamics and one hard problem remains. There are \( K \) actions ("arms"), each paying i.i.d. rewards from an unknown distribution with mean \( \mu_a \), one pull per round, and the tension between pulling the arm that looks best and pulling others to find out whether looks deceive. Let \( \mu^* = \max_a \mu_a \) and \( \Delta_a = \mu^* - \mu_a \) the suboptimality gap of arm \( a \). The (expected, pseudo-) regret after \( T \) rounds is the price of not having known the best arm from the start,

where \( N_a(T) \) counts pulls of arm \( a \). The second equality, the regret decomposition, follows by writing the sum over rounds as a sum over arms of (pulls of \( a \)) times (per-pull loss \( \Delta_a \)). It reduces every regret proof to one question, how many times the algorithm pulls each suboptimal arm. Two baselines calibrate expectations. Pure greedy after a finite trial phase suffers linear regret \( \Omega(T) \) with constant probability, because a finite sample can rank the arms wrongly forever after. \( \epsilon \)-greedy with constant \( \epsilon \) also pays linear regret \( \epsilon \bar\Delta T \) forever, by construction. Sublinear regret, meaning \( R_T / T \to 0 \), requires exploration that decays at the right rate, and the theory pins down that rate exactly.

The Lai–Robbins lower bound

Lai and Robbins (1985) proved that logarithmic regret is not just achievable but the floor. For any algorithm that is uniformly good (its regret is \( o(T^\alpha) \) for every \( \alpha > 0 \) on every bandit instance, ruling out algorithms that gamble on one instance at the expense of others), and reward distributions in a smooth parametric family, every suboptimal arm must be pulled at least

times, where \( \KL(\mu_a \| \mu^*) \) is the KL divergence between the reward distribution of arm \( a \) and one with the optimal mean. The information-theoretic reading is that to be sure arm \( a \) is not secretly the best, the algorithm needs enough samples of it to statistically distinguish its distribution from an optimal one. Distinguishing costs \( \ln T / \KL \) samples against a confidence level that must tighten as \( 1/T \), and pulling the arm that often costs \( \Delta_a \) each time. Consequently \( R_T \ge \big( \sum_{a: \Delta_a > 0} \Delta_a / \KL(\mu_a \| \mu^*) \big) \ln T \, (1 - o(1)) \). The constant in front of \( \ln T \) is instance-specific and no algorithm beats it asymptotically. For the 5-arm Bernoulli instance measured below, this constant evaluates to 12.28, giving an asymptote of 141.4 at \( T = 10^5 \). The measured algorithms are compared against it in the table.

UCB from Hoeffding's inequality

The upper confidence bound algorithm turns a concentration inequality into a policy. Hoeffding's inequality for \( n \) i.i.d. samples in \( [0,1] \) reads \( \P(\hat\mu - \mu \ge u) \le e^{-2nu^2} \), and symmetrically for the lower tail. Choose the deviation \( u \) so that the failure probability is \( t^{-4} \). Setting \( e^{-2nu^2} = t^{-4} \) gives \( u = \sqrt{2 \ln t / n} \). UCB1 (Auer, Cesa-Bianchi, and Fischer, 2002) plays each arm once, then at round \( t \) plays the arm maximizing the optimistic index

The regret proof is short enough to sketch honestly. Suppose a suboptimal arm \( a \) is played at round \( t \), so \( \mathrm{UCB}_a(t) \ge \mathrm{UCB}_{*}(t) \). Then at least one of three events must hold, because if all three fail the chain \( \hat\mu_a + c_a < \mu_a + 2c_a \le \mu_a + \Delta_a = \mu^* \le \hat\mu_* + c_* \) (writing \( c_a \) for the bonus) contradicts the assumption.

(i) The best arm's index dips below its true mean, \( \hat\mu_* + c_* \le \mu^* \), with probability at most \( t^{-4} \) by Hoeffding's lower tail. (ii) Arm \( a \)'s mean is overestimated by more than its bonus, \( \hat\mu_a \ge \mu_a + c_a \), with probability at most \( t^{-4} \). (iii) Arm \( a \) is undersampled, with \( 2 c_a > \Delta_a \), i.e. \( N_a(t) < 8 \ln t / \Delta_a^2 \). Event (iii) can occur at most \( 8 \ln T / \Delta_a^2 \) times over the horizon, because each occurrence while playing \( a \) increments \( N_a \). Events (i) and (ii) are rare uniformly. Union-bounding over the possible values of the sample counts contributes \( \sum_t 2 t \cdot t^{-4} \le 2\sum_t t^{-3} \), a convergent series, adding the constant \( 1 + \pi^2/3 \) to the pull count. Altogether

This is logarithmic regret with the right shape. Harder-to-distinguish arms (small \( \Delta_a \)) are pulled more, exactly as Lai–Robbins requires, though UCB1's constant \( 8/\Delta_a \) exceeds the optimal \( \Delta_a/\KL \) constant (for Bernoulli arms, KL-UCB and Thompson sampling close that gap). Note what optimism did in the proof. The algorithm never needed to decide between exploring and exploiting. It always exploited an upper bound, and the concentration inequality guaranteed that persistent over-optimism about a bad arm is self-correcting, since every pull shrinks the bonus.

Thompson sampling and posterior matching

Thompson sampling (1933, the oldest algorithm on this page) maintains a posterior over each arm's mean, samples one draw per arm each round, and plays the argmax of the samples. For Bernoulli rewards with a \( \mathrm{Beta}(1,1) \) prior, the posterior after \( s \) successes in \( n \) pulls is \( \mathrm{Beta}(1+s, 1+n-s) \), so the whole algorithm is "sample \( \theta_a \sim \mathrm{Beta}(1+s_a, 1+f_a) \), play \( \argmax_a \theta_a \), update one counter". The randomization implements probability matching. Each arm is played with exactly the posterior probability that it is the best arm. Its modern analysis came in two waves. Agrawal and Goyal (2012) and Kaufmann, Korda, and Munos (2012) proved frequentist logarithmic regret, the latter with the exact Lai–Robbins constant, making Thompson sampling asymptotically optimal for Bernoulli bandits. Russo and Van Roy (2014) gave the general Bayesian account. In expectation over the prior, posterior sampling inherits the regret bound of any UCB-style algorithm one can construct for the problem class, because the sampled model plays the role of the optimistic model, yielding Bayesian regret \( O(\sqrt{KT \log T}) \) for \( K \)-armed bandits and clean extensions to structured problems. The practical reputation, that Thompson sampling matches or beats tuned UCB variants with no tuning at all, is borne out in the measured numbers below.

Measured regret against the theoretical curves

The measured experiment, with full data in classes/data/rl-theory.json, is a 5-arm Bernoulli bandit with means \( (0.60, 0.50, 0.45, 0.40, 0.30) \), so gaps \( (0.10, 0.15, 0.20, 0.30) \) for the suboptimal arms. UCB1 and Beta-Bernoulli Thompson sampling run to \( T = 10^5 \), averaged over 400 independent runs (standard errors of the means at the final checkpoint are 2.6 and 1.1 respectively).

Three things to read off. First, the bound holds with room to spare, as an honest worst-case bound should. Measured UCB1 regret at \( T = 10^5 \) is 461 against a guarantee of 2,306. Second, the shape is right, which is the real test of a logarithmic theory. Between \( t = 10^4 \) and \( t = 10^5 \), UCB1's regret grew by 197.6 over an \( \ln t \) increase of 2.303, a measured local slope of 85.8 per unit \( \ln t \), sitting below the theorem's asymptotic coefficient \( \sum 8/\Delta_a = 200 \) and above the Lai–Robbins coefficient 12.28. Regret against \( \ln t \) is close to a straight line exactly as the theory draws it. Third, Thompson sampling's measured slope over the same decade is 10.0 per unit \( \ln t \), consistent with the Kaufmann–Korda–Munos result that it attains the Lai–Robbins constant (12.28 here) asymptotically, and it beats UCB1 by 5.9× in final regret. Untuned, with a two-line implementation. This is why Thompson sampling is the default in industrial A/B and recommendation systems.

Contextual bandits and LinUCB

Between bandits and MDPs sit contextual bandits. Each round reveals a context \( x_t \), the algorithm picks an arm, and only the picked arm's reward is observed. There are no dynamics, so today's choice does not change tomorrow's context. Under a linear payoff model \( \E[r_{t,a}] = x_{t,a}\T \theta^* \), LinUCB (Li, Chu, Langford, and Schapire, 2010, built for news recommendation) maintains the ridge-regression estimate \( \hat\theta = A^{-1} b \) with \( A = \lambda I + \sum x x\T \) and \( b = \sum x r \), and plays the arm maximizing \( x\T \hat\theta + \alpha \sqrt{x\T A^{-1} x} \), predicted reward plus an exploration bonus that is exactly the confidence width of the prediction in the direction \( x \). The rigorous confidence set is the ellipsoid of Abbasi-Yadkori, Pál, and Szepesvári (2011), whose self-normalized martingale bound gives regret \( \tilde O(d \sqrt{T}) \). Dimension replaces arm count, so structure converts an intractable arm space into a learnable one. Contextual bandits are the exploration workhorse of industry (recommendation, ad allocation, A/B at scale) because they capture the observation-action-feedback loop without the credit-assignment problems of full RL.

Exploration in MDPs: R-max, UCRL2, and minimax regret

In an MDP, exploration must be planned. Reaching an unknown state may require a long deliberate detour, so per-step randomization is not enough, and the bandit machinery has to be lifted to sequential structure. R-max (Brafman and Tennenholtz, 2002) does it with a blunt form of optimism. Mark every state-action pair "unknown" until it has been visited \( m \) times. In the internal model, unknown pairs teleport to a fictional state paying the maximum reward \( R_{\max} \) forever. Plan optimally in this model and act. The optimism makes unknown regions look maximally rewarding, so the planner steers into them until they become known, and once all reachable pairs are known the model is accurate and the policy near-optimal. The guarantee is the PAC-MDP form (formalized in Kakade's 2003 thesis). With probability \( 1 - \delta \), the number of timesteps at which R-max's policy is more than \( \epsilon \) worse than optimal is polynomial in \( |\mathcal{S}|, |\mathcal{A}|, 1/\epsilon, 1/\delta, 1/(1-\gamma) \). Polynomial, not logarithmic. PAC-MDP counts mistakes, regret counts cumulative loss, and the two frameworks are related but not interchangeable.

UCRL2 (Jaksch, Ortner, and Auer, 2010) is the regret-side refinement. Maintain confidence sets around the empirical transition probabilities and rewards (\( L^1 \) balls from concentration bounds), and at the start of each episode compute the policy that is optimal for the best MDP in the confidence set, via extended value iteration. This is optimism over models rather than over values. Its regret in a communicating MDP with diameter \( D \) (the worst-case expected time to travel between any two states under the best policy for doing so) is \( \tilde O(D |\mathcal{S}| \sqrt{|\mathcal{A}| T}) \), against a lower bound of \( \Omega(\sqrt{D |\mathcal{S}| |\mathcal{A}| T}) \), leaving a \( \sqrt{D|\mathcal{S}|} \) gap that took years to close. Azar, Osband, and Munos (2017) closed the analogous gap in the episodic setting. Their UCBVI puts Bernstein-style bonuses directly on the value estimates rather than building model confidence sets, achieving regret \( \tilde O(\sqrt{H |\mathcal{S}| |\mathcal{A}| T}) \) for horizon \( H \), matching the lower bound up to log factors once \( T \) is large. That result is the tabular endpoint. Exploration in finite MDPs is, in the minimax sense, solved.

The unifying principle across every algorithm in this section is optimism in the face of uncertainty. Act greedily with respect to the most favorable hypothesis consistent with the data. The two-sided argument for why it works is always the same. If the optimistic hypothesis is approximately correct, greedy behavior against it is approximately optimal, and little regret accrues. If it is badly wrong, then acting on it drives the agent into the region of state or arm space where the hypothesis and reality disagree, the data collected there shrinks exactly the uncertainty that produced the error, and the mistake is self-limiting. Pessimism, by contrast, is self-sealing. An agent that underestimates an unknown option never touches it and never learns better. That asymmetry is the deepest single idea in exploration theory, and its mirror image, pessimism as the right principle when no new data can be collected, organizes the offline RL section below.

Policy gradient theory

The policy gradient theorem, proved

Value-based methods derive a policy from a value function. Policy methods parameterize the policy directly, \( \pi_\theta(a \mid s) \), and ascend \( J(\theta) = V^{\pi_\theta}(s_0) \) (or its average over a start distribution). The obstacle is that \( \theta \) affects \( J \) through two routes, the action probabilities and the distribution of states visited, and the second route looks hopeless to differentiate because the visitation distribution depends on \( P \), which is unknown. The policy gradient theorem (Sutton, McAllester, Singh, and Mansour, 2000) shows the state-distribution route contributes nothing extra. Start from the Bellman expansion of \( V \) and differentiate the product,

and since \( Q^\pi(s,a) = r(s,a) + \gamma \sum_{s'} P(s' \mid s,a) V^\pi(s') \) with \( r \) and \( P \) independent of \( \theta \), \( \nabla Q^\pi(s,a) = \gamma \sum_{s'} P(s' \mid s,a) \nabla V^\pi(s') \). Substituting gives a recursion for \( \nabla V^\pi \). Its value at \( s \) equals a local term \( g(s) = \sum_a \nabla\pi(a \mid s) Q^\pi(s,a) \) plus the \( \gamma \)-discounted expectation of itself one step ahead. Unrolling the recursion along the Markov chain gives

where \( d^\pi(s) = \sum_t \gamma^t \P(s_t = s) \) is the discounted state-visitation measure. No \( \nabla P \) and no \( \nabla d^\pi \) appear. The environment's dynamics enter only through quantities that sampling can estimate. Multiplying and dividing by \( \pi_\theta \) puts it in the sampled (likelihood-ratio) form used by every implementation,

and since \( \E[\nabla\log\pi] = 0 \), any action-independent baseline \( b(s) \) can be subtracted from \( Q^\pi \) without bias, which is where advantage functions and the variance-reduction industry begin. The derivation, REINFORCE, baselines, and actor-critic construction are treated at implementation depth on the policy gradients page. Here the point is the theorem and what has been proved around it.

Compatible function approximation

Replacing \( Q^\pi \) in the theorem with a learned critic \( f_w \) generally biases the gradient. Sutton et al.'s second contribution in the same paper is the compatibility condition under which it does not. If

(the critic is linear in the policy's own score features) and \( w \) is chosen to minimize the mean-squared error \( \E_{d^\pi, \pi}[(Q^\pi(s,a) - f_w(s,a))^2] \), then at the minimizer the error is orthogonal to the score features, \( \E[(Q^\pi - f_w)\nabla\log\pi] = 0 \), which is precisely the statement that swapping \( f_w \) for \( Q^\pi \) inside the policy gradient changes nothing. A critic can be wrong everywhere yet, if it is wrong in directions the score features cannot see, the gradient it produces is exact. In practice critics are not compatible (they are neural networks trained by TD, inheriting all of the bias discussed above), and the condition's real legacy is theoretical. It is the hinge of the natural-gradient connection next.

Natural gradients and the Fisher metric

Vanilla gradient ascent moves \( \theta \) a fixed Euclidean distance, but Euclidean distance in parameter space is meaningless for a distribution. The same step can barely perturb \( \pi \) in one region and destroy it in another. The natural gradient (Amari's information geometry, brought to RL by Kakade, 2001) measures steps by the KL divergence they induce on the policy, whose local quadratic form is the Fisher information matrix \( F(\theta) = \E_{d^\pi, \pi}[\nabla\log\pi \, \nabla\log\pi\T] \), and ascends \( \tilde\nabla J = F^{-1} \nabla J \). This is invariant to reparameterization of the policy family, and it composes cleanly with compatibility. If \( f_w \) is the compatible critic at its least-squares solution, the normal equations read \( \E[\nabla\log\pi \, \nabla\log\pi\T] w = \E[\nabla\log\pi \, Q^\pi] \), i.e. \( F w = \nabla J \), so the natural gradient is the compatible critic's weights, \( \tilde\nabla J = w \). Trust region and proximal methods (TRPO, PPO) are engineering descendants of this idea, constraining KL movement per update. Their derivations live on the PPO page.

Global convergence for softmax policies

\( J(\theta) \) is non-concave even for tabular softmax policies, so for twenty years the honest statement was "policy gradient converges to a stationary point". The recent theory sharpened this considerably. For the tabular softmax parameterization \( \pi_\theta(a \mid s) \propto e^{\theta_{s,a}} \) with exact gradients and a start distribution \( \mu \) giving positive weight to all states, Agarwal, Kakade, Lee, and Mahajan (JMLR 2021) proved that gradient ascent converges to a globally optimal policy. Despite non-concavity, the landscape's stationary points that are not global optima are avoided from generic initializations, and with relative-entropy regularization they give polynomial rates. Their rates carry a distribution-mismatch coefficient \( \| d^{\pi^*}_\mu / \mu \|_\infty \), quantifying how well the start distribution covers where the optimal policy goes, an early-warning echo of the concentrability constants below. Mei, Xiao, Szepesvári, and Schuurmans (2020) pinned the rates. Unregularized softmax gradient ascent converges at \( O(1/t) \) and entropy-regularized at a linear (geometric) rate, via non-uniform Łojasiewicz inequalities, and natural policy gradient enjoys an \( O(1/t) \) rate with no dependence on state-space size (Agarwal et al.), the cleanest theoretical separation between vanilla and natural gradients known. The mechanism behind the slow unregularized rate is visible in the two-action problem below. As the softmax saturates, the score \( \nabla\log\pi \) collapses and gradients vanish precisely when the policy is nearly right. These results assume exact gradients and tabular policies. With sampling and neural policies the guarantees weaken to the local statements deep RL actually lives with.

Offline and batch RL: pessimism and its limits

The distribution-shift problem, stated formally

Offline (batch) RL learns from a fixed dataset \( \D = \{(s_i, a_i, r_i, s_i')\} \) collected by some behavior policy \( \mu \), with no further interaction. Every difficulty in the field is one problem wearing different costumes. The quantity to be optimized is an expectation under the visitation distribution \( d^\pi \) of the policy \( \pi \) being considered, but the data estimates expectations under \( d^\mu \). Bellman backups query \( \max_{a'} Q(s', a') \) at actions the dataset may never take in \( s' \). A function approximator extrapolates there, the max selects the most flattering extrapolation (maximization bias again, now with no corrective data ever arriving), and the fictitious values propagate backward through bootstrapping. Run vanilla Q-learning on a fixed dataset and the value estimates routinely climb without bound while the actual policy quality collapses. Levine, Kumar, Tucker, and Fu's 2020 tutorial documents this failure mode as the field's starting point.

The classical theory quantifies shift with concentrability coefficients. The all-policy version (from Munos's error-propagation analyses of fitted value and policy iteration in the 2000s) assumes \( d^\pi(s,a) / d^\mu(s,a) \le C \) for all policies \( \pi \), and yields bounds for fitted Q-iteration of the shape \( \|V^* - V^{\hat\pi}\| \lesssim \frac{\sqrt{C}}{(1-\gamma)^2} \, \epsilon \), where \( \epsilon \) is the per-iteration regression error. This is the same \( 1/(1-\gamma)^2 \) amplification as approximate policy iteration, now multiplied by how far the data's coverage can be stretched. All-policy concentrability is a very strong assumption. It demands the dataset cover everywhere any policy could go. The modern refinement asks only for single-policy concentrability, \( C^* = \max_{s,a} \, d^{\pi^*}(s,a) / d^\mu(s,a) \), coverage of one good policy's footprint, and this is where pessimism enters.

Pessimism as the mirror of optimism

Online, optimism is correct because acting on an inflated estimate generates exactly the data that deflates it. Offline, that feedback loop is severed, so optimism's errors are permanent, and the correct principle inverts. Pessimistic value iteration subtracts an uncertainty bonus instead of adding one,

with \( b(s,a) \) sized (by concentration inequalities, as in UCB but negated) to make \( \hat Q \) a high-probability lower bound on the truth. The policy then optimizes a floor, since anything it expects, the data supports. Jin, Yang, and Wang (2021) proved this is provably efficient in linear MDPs. Rashidinejad, Zhu, Ma, Jiao, and Russell (2021) gave the clean tabular statement, that pessimistic value iteration finds a policy with suboptimality \( \tilde O\big( \sqrt{C^* |\mathcal{S}| / ((1-\gamma)^3 n)} \big) \) from \( n \) samples, requiring coverage only of the optimal policy (\( C^* \)), and matching an information-theoretic lower bound up to logarithmic factors. The conceptual symmetry is exact. Optimism guarantees you eventually do as well as the best discoverable policy. Pessimism guarantees you immediately do as well as the best covered policy.

The fundamental limits of a fixed dataset

The limits are equally sharp. If \( C^* = \infty \), meaning the optimal policy visits state-actions the behavior policy never touches, no algorithm can find it. The needed information is simply absent from the data-generating distribution, and lower bounds formalize that even nearness to optimality is unattainable in the worst case. Worse, coverage plus expressive function approximation is still not enough. Zanette (2021) and related lower bounds show offline RL with linear realizability can require exponentially many samples where online RL needs polynomially many, an exponential online-offline separation. Batch data cannot ask the follow-up questions that online interaction answers for free. The practical translation for the RLHF era is direct. A reward model or value function trained on a fixed preference dataset is trustworthy only on the data distribution's support, optimizing hard against it walks the policy straight off that support, and the KL penalties in RLHF pipelines are doing exactly the job the theory prescribes, keeping \( d^\pi / d^\mu \) bounded. Algorithms (CQL, IQL, model-based variants) and their empirical behavior are covered in the RL section. The theory above is what all of them are approximating.

Average-reward MDPs, briefly

For continuing tasks with no natural discounting, the average-reward criterion optimizes the gain \( \rho^\pi = \lim_{T\to\infty} \tfrac{1}{T} \E_\pi[\sum_{t=0}^{T-1} r_t] \), which under an ergodicity (unichain) assumption is a single number independent of the start state. In the long run only the stationary distribution matters. States still differ transiently, and the differential (bias) value function measures exactly that transient,

the cumulative excess over the long-run average, convergent because the summand decays as the chain mixes. The Bellman equations acquire \( \rho \) in place of \( \gamma \). Evaluation is \( \rho^\pi + h^\pi(s) = \sum_a \pi(a|s) [ r(s,a) + \sum_{s'} P(s'|s,a) h^\pi(s') ] \), optimality replaces the average with a max, and \( h \) is determined only up to an additive constant (adding \( c \) to every \( h(s) \) preserves the equation), so algorithms pin one reference state or subtract an estimate of \( \rho \), as R-learning and differential TD do. The connection to discounting is the Laurent expansion \( V_\gamma(s) = \rho/(1-\gamma) + h(s) + O(1-\gamma) \). As \( \gamma \to 1 \), the discounted value is a large state-independent term plus the differential value, which explains both why large-\( \gamma \) discounted methods approximate average-reward behavior and why they become ill-conditioned doing it (the interesting signal \( h \) rides on a \( 1/(1-\gamma) \) pedestal). Puterman's chapters 8 and 9 are the definitive treatment. A line of work from Sutton's group (Wan, Naik, and Sutton, 2021) has recently revived the criterion for continuing-task deep RL.

Worked problems

Six problems are distributed through the sections above (linear-system evaluation, iteration counts from the contraction rate, importance-sampling variance, maximization bias, the UCB constants, and the softmax gradient). Two more here, chosen because each one is a small computation that makes a big theorem concrete.

Implementation

Everything below was actually run. The measured numbers quoted throughout the page, and the tables at the end of this section, are the output, stored in classes/data/rl-theory.json. The first block builds the slip-gridworld's transition tensor and solves it with both value iteration and exact policy iteration. The representation to internalize is the transition tensor \( P \in \R^{S \times A \times S} \). With it, a full Bellman sweep is one contraction of the tensor against the value vector, and the whole of dynamic programming is ten lines of array code.

import numpy as np

# 4x4 slip gridworld. goal=state 3 (+1 on entry), pit=state 7 (-1),
# gamma=0.9, intended move w.p. 0.8, each perpendicular w.p. 0.1.
S, A, GAMMA = 16, 4, 0.9
TERM = (3, 7)
PERP = {0: (2, 3), 1: (2, 3), 2: (0, 1), 3: (0, 1)}  # U,D -> L,R etc.

def move(s, a):
    r, c = divmod(s, 4)
    if a == 0: r = max(r - 1, 0)      # up
    elif a == 1: r = min(r + 1, 3)    # down
    elif a == 2: c = max(c - 1, 0)    # left
    else:        c = min(c + 1, 3)    # right
    return 4 * r + c

def build():
    P = np.zeros((S, A, S))           # P[s, a, s']
    R = np.zeros((S, A))              # expected one-step reward
    for s in range(S):
        for a in range(A):
            if s in TERM:
                P[s, a, s] = 1.0      # absorbing, reward 0
                continue
            for aa, p in ((a, .8), (PERP[a][0], .1), (PERP[a][1], .1)):
                s2 = move(s, aa)
                P[s, a, s2] += p
                R[s, a] += p * (1.0 if s2 == 3 else -1.0 if s2 == 7 else 0.0)
    return P, R

P, R = build()

def value_iteration(tol=1e-10):
    V, k = np.zeros(S), 0
    while True:
        Q = R + GAMMA * (P @ V)       # (S,A): one full Bellman sweep
        V_new = Q.max(axis=1)
        V_new[list(TERM)] = 0.0
        k += 1
        if np.abs(V_new - V).max() < tol:
            return V_new, Q.argmax(axis=1), k
        V = V_new

def eval_policy(pi):                  # exact: solve (I - g P_pi) V = R_pi
    Ppi = P[np.arange(S), pi].copy()  # (S, S')
    Rpi = R[np.arange(S), pi].copy()
    for t in TERM:
        Ppi[t] = 0.0; Ppi[t, t] = 1.0; Rpi[t] = 0.0
    return np.linalg.solve(np.eye(S) - GAMMA * Ppi, Rpi)

def policy_iteration():
    pi, rounds = np.zeros(S, dtype=int), 0
    while True:
        V = eval_policy(pi)                      # evaluation (linear solve)
        pi_new = (R + GAMMA * (P @ V)).argmax(1) # greedy improvement
        rounds += 1
        if (pi_new == pi).all():
            return pi, V, rounds
        pi = pi_new

V_star, pi_star, iters = value_iteration()   # iters == 46
pi_pi, V_pi, rounds = policy_iteration()     # rounds == 3
assert np.abs(V_pi - V_star).max() < 1e-9    # same fixed point

import torch

# Same MDP; P and R built once as tensors. build() as in the NumPy tab.
P_np, R_np = build()
P = torch.tensor(P_np)                 # (S, A, S')
R = torch.tensor(R_np)                 # (S, A)
term = torch.zeros(S, dtype=torch.bool)
term[list(TERM)] = True

def value_iteration(tol=1e-10):
    V, k = torch.zeros(S, dtype=torch.float64), 0
    while True:
        Q = R + GAMMA * torch.einsum('san,n->sa', P, V)  # (S, A)
        V_new = torch.where(term, torch.zeros(()), Q.max(dim=1).values)
        k += 1
        if (V_new - V).abs().max() < tol:
            return V_new, Q.argmax(dim=1), k
        V = V_new

def eval_policy(pi):                   # pi: (S,) long
    idx = torch.arange(S)
    Ppi, Rpi = P[idx, pi].clone(), R[idx, pi].clone()
    Ppi[term] = 0.0
    Ppi[term, term.nonzero().squeeze(1)] = 1.0
    Rpi[term] = 0.0
    A_mat = torch.eye(S, dtype=torch.float64) - GAMMA * Ppi
    return torch.linalg.solve(A_mat, Rpi)

def policy_iteration():
    pi, rounds = torch.zeros(S, dtype=torch.long), 0
    while True:
        V = eval_policy(pi)
        Q = R + GAMMA * torch.einsum('san,n->sa', P, V)
        pi_new = Q.argmax(dim=1)
        rounds += 1
        if torch.equal(pi_new, pi):
            return pi, V, rounds
        pi = pi_new

V_star, pi_star, iters = value_iteration()   # iters == 46
_, V_pi, rounds = policy_iteration()         # rounds == 3
assert (V_pi - V_star).abs().max() < 1e-9

import jax
import jax.numpy as jnp

# Same MDP; build() as in the NumPy tab produces the arrays once.
P_np, R_np = build()
P, R = jnp.asarray(P_np), jnp.asarray(R_np)       # (S,A,S'), (S,A)
term = jnp.zeros(S, bool).at[jnp.array(TERM)].set(True)

@jax.jit
def sweep(V):                                     # one Bellman sweep
    Q = R + GAMMA * jnp.einsum('san,n->sa', P, V)
    return jnp.where(term, 0.0, Q.max(axis=1))

def value_iteration(tol=1e-10):
    def cond(carry):
        V, V_new, k = carry
        return jnp.abs(V_new - V).max() >= tol
    def body(carry):
        _, V, k = carry
        return V, sweep(V), k + 1
    V0 = jnp.zeros(S)
    _, V, k = jax.lax.while_loop(cond, body, (V0, sweep(V0), 1))
    Q = R + GAMMA * jnp.einsum('san,n->sa', P, V)
    return V, Q.argmax(axis=1), k

def eval_policy(pi):                              # exact linear solve
    idx = jnp.arange(S)
    Ppi = P[idx, pi]
    Ppi = jnp.where(term[:, None], jnp.eye(S), Ppi)
    Rpi = jnp.where(term, 0.0, R[idx, pi])
    return jnp.linalg.solve(jnp.eye(S) - GAMMA * Ppi, Rpi)

def policy_iteration():
    pi, rounds = jnp.zeros(S, jnp.int32), 0
    while True:                                   # tiny loop; python is fine
        V = eval_policy(pi)
        Q = R + GAMMA * jnp.einsum('san,n->sa', P, V)
        pi_new = Q.argmax(axis=1).astype(jnp.int32)
        rounds += 1
        if bool((pi_new == pi).all()):
            return pi, V, rounds
        pi = pi_new

V_star, pi_star, iters = value_iteration()   # iters == 46
_, V_pi, rounds = policy_iteration()         # rounds == 3
assert jnp.abs(V_pi - V_star).max() < 1e-9

TD(λ) with accumulating eligibility traces, evaluating the uniform-random policy on the 5-state random walk whose true values are \( 1/6, \ldots, 5/6 \). The NumPy tab is the algorithm exactly as derived (backward view). The JAX tab shows the idiomatic functional restructuring, a lax.scan over the steps of a pre-generated episode, which is how libraries like rlax organize the same arithmetic.

import numpy as np

# 5 interior states 0..4, terminals to the left (r=0) and right (r=+1).
# gamma = 1 (episodic), start in the center, uniform random policy.
TRUE_V = np.arange(1, 6) / 6.0

def td_lambda(lam, alpha, episodes, seed):
    rng = np.random.default_rng(seed)
    V = np.full(5, 0.5)                       # initial guess
    for _ in range(episodes):
        z = np.zeros(5)                       # eligibility trace
        s = 2
        while True:
            s2 = s + (1 if rng.random() < 0.5 else -1)
            if s2 == 5:   r, v2, done = 1.0, 0.0, True
            elif s2 == -1: r, v2, done = 0.0, 0.0, True
            else:          r, v2, done = 0.0, V[s2], False
            delta = r + v2 - V[s]             # TD error (gamma=1)
            z *= lam                          # decay all traces
            z[s] += 1.0                       # accumulate current state
            V += alpha * delta * z            # broadcast delta backward
            if done: break
            s = s2
    return V

V = td_lambda(lam=0.8, alpha=0.05, episodes=100, seed=0)
rms = np.sqrt(np.mean((V - TRUE_V) ** 2))
# measured over 200 runs: lambda=0 rms 0.055, lambda=0.8 rms 0.064,
# lambda=1 (Monte Carlo) rms 0.087 -- see rl-theory.json

import torch

TRUE_V = torch.arange(1, 6, dtype=torch.float64) / 6.0

def td_lambda(lam, alpha, episodes, seed):
    g = torch.Generator().manual_seed(seed)
    V = torch.full((5,), 0.5, dtype=torch.float64)
    for _ in range(episodes):
        z = torch.zeros(5, dtype=torch.float64)   # eligibility trace
        s = 2
        while True:
            step = 1 if torch.rand((), generator=g) < 0.5 else -1
            s2 = s + step
            if s2 == 5:    r, v2, done = 1.0, 0.0, True
            elif s2 == -1: r, v2, done = 0.0, 0.0, True
            else:          r, v2, done = 0.0, V[s2].item(), False
            delta = r + v2 - V[s].item()          # TD error (gamma=1)
            z *= lam
            z[s] += 1.0
            V += alpha * delta * z                # trace-weighted update
            if done: break
            s = s2
    return V

V = td_lambda(lam=0.8, alpha=0.05, episodes=100, seed=0)
rms = torch.sqrt(torch.mean((V - TRUE_V) ** 2))

import jax
import jax.numpy as jnp
import numpy as np

# Generate an episode's (state, reward, v_next_is_terminal) with numpy,
# then run the trace updates as a lax.scan: the rlax-style structure.
def gen_episode(rng):
    s, states, rews, terms = 2, [], [], []
    while True:
        s2 = s + (1 if rng.random() < 0.5 else -1)
        states.append(s)
        rews.append(1.0 if s2 == 5 else 0.0)
        terms.append(s2 in (-1, 5))
        if terms[-1]: break
        s = s2
    nxt = states[1:] + [0]                      # next-state indices
    return (jnp.array(states), jnp.array(nxt),
            jnp.array(rews), jnp.array(terms))

@jax.jit
def td_lambda_episode(V, ep, lam=0.8, alpha=0.05):
    states, nxt, rews, terms = ep
    def step(carry, t):
        V, z = carry
        s, s2, r, done = states[t], nxt[t], rews[t], terms[t]
        v2 = jnp.where(done, 0.0, V[s2])
        delta = r + v2 - V[s]                   # TD error (gamma=1)
        z = (lam * z).at[s].add(1.0)            # accumulating trace
        return (V + alpha * delta * z, z), delta
    (V, _), _ = jax.lax.scan(step, (V, jnp.zeros(5)),
                             jnp.arange(states.shape[0]))
    return V

rng = np.random.default_rng(0)
V = jnp.full(5, 0.5)
for _ in range(100):
    V = td_lambda_episode(V, gen_episode(rng))

Tabular Q-learning on the slip-gridworld, with Robbins–Monro step sizes \( \alpha = 1/n(s,a)^{0.7} \) and \( \epsilon \)-greedy behavior. The JAX tab is fully functional, environment included. The dynamics become lookup tables and the whole training loop is one fori_loop, which is the pattern that scales to vectorized thousands-of-environments training.

STARTS = [s for s in range(S) if s not in TERM]

def env_step(s, a, rng):              # sample from the slip dynamics
    u = rng.random()
    aa = a if u < 0.8 else (PERP[a][0] if u < 0.9 else PERP[a][1])
    s2 = move(s, aa)
    r = 1.0 if s2 == 3 else (-1.0 if s2 == 7 else 0.0)
    return s2, r, s2 in TERM

def q_learning(steps, eps, seed):
    rng = np.random.default_rng(seed)
    Q = np.zeros((S, A))
    N = np.zeros((S, A))              # visit counts for step sizes
    s = int(rng.choice(STARTS))
    for _ in range(steps):
        greedy = int(Q[s].argmax())
        a = rng.integers(A) if rng.random() < eps else greedy
        s2, r, done = env_step(s, a, rng)
        N[s, a] += 1
        alpha = 1.0 / N[s, a] ** 0.7  # Robbins-Monro compliant
        target = r if done else r + GAMMA * Q[s2].max()
        Q[s, a] += alpha * (target - Q[s, a])
        s = int(rng.choice(STARTS)) if done else s2
    return Q

Q = q_learning(steps=400_000, eps=0.1, seed=1)
# measured: max|Q - Q*| = 0.119, policy value loss 0.0030,
# 13/14 states match pi*; the one miss has a Q* action gap of 0.0024

import torch

def q_learning(steps, eps, seed):
    g = torch.Generator().manual_seed(seed)
    Q = torch.zeros(S, A, dtype=torch.float64)
    N = torch.zeros(S, A)
    starts = torch.tensor(STARTS)
    s = int(starts[torch.randint(len(starts), (1,), generator=g)])
    for _ in range(steps):
        if torch.rand((), generator=g) < eps:
            a = int(torch.randint(A, (1,), generator=g))
        else:
            a = int(Q[s].argmax())
        # sample slip dynamics
        u = torch.rand((), generator=g).item()
        aa = a if u < 0.8 else (PERP[a][0] if u < 0.9 else PERP[a][1])
        s2 = move(s, aa)
        r = 1.0 if s2 == 3 else (-1.0 if s2 == 7 else 0.0)
        done = s2 in TERM
        N[s, a] += 1
        alpha = 1.0 / N[s, a].item() ** 0.7
        target = r if done else r + GAMMA * Q[s2].max().item()
        Q[s, a] += alpha * (target - Q[s, a])
        if done:
            s = int(starts[torch.randint(len(starts), (1,), generator=g)])
        else:
            s = s2
    return Q

Q = q_learning(steps=400_000, eps=0.1, seed=1)

import jax
import jax.numpy as jnp
import numpy as np

# Dynamics as lookup tables so the env itself is jittable.
MOVE = jnp.array([[move(s, a) for a in range(A)] for s in range(S)])
PERP_T = jnp.array([[2, 3], [2, 3], [0, 1], [0, 1]])
REW = jnp.array([1.0 if s == 3 else -1.0 if s == 7 else 0.0
                 for s in range(S)])          # reward on *entering* s
IS_TERM = jnp.zeros(S, bool).at[jnp.array(TERM)].set(True)
STARTS_J = jnp.array(STARTS)

@jax.jit
def train(key, steps=400_000, eps=0.1):
    def body(_, carry):
        Q, N, s, key = carry
        key, k1, k2, k3, k4 = jax.random.split(key, 5)
        a = jnp.where(jax.random.uniform(k1) < eps,
                      jax.random.randint(k2, (), 0, A),
                      Q[s].argmax())
        u = jax.random.uniform(k3)            # slip: 0.8 / 0.1 / 0.1
        aa = jnp.where(u < 0.8, a,
             jnp.where(u < 0.9, PERP_T[a, 0], PERP_T[a, 1]))
        s2 = MOVE[s, aa]
        r, done = REW[s2], IS_TERM[s2]
        N = N.at[s, a].add(1.0)
        alpha = 1.0 / N[s, a] ** 0.7
        target = r + GAMMA * jnp.where(done, 0.0, Q[s2].max())
        Q = Q.at[s, a].add(alpha * (target - Q[s, a]))
        restart = STARTS_J[jax.random.randint(k4, (), 0, len(STARTS))]
        return Q, N, jnp.where(done, restart, s2), key
    Q, _, _, _ = jax.lax.fori_loop(
        0, steps, body,
        (jnp.zeros((S, A)), jnp.zeros((S, A)),
         STARTS_J[0], key))
    return Q

Q = train(jax.random.PRNGKey(1))

The bandit pair is UCB1 and Beta-Bernoulli Thompson sampling on the 5-arm instance, the code that produced the regret table in the exploration section. Note how little there is to either algorithm. The entire intellectual content is in the index formula and the posterior update.

import numpy as np

MEANS = np.array([0.60, 0.50, 0.45, 0.40, 0.30])
K = len(MEANS)
GAPS = MEANS.max() - MEANS

def ucb1(T, seed):
    rng = np.random.default_rng(seed)
    n = np.zeros(K); s = np.zeros(K)
    regret = 0.0
    for t in range(1, T + 1):
        if t <= K:
            a = t - 1                      # play each arm once
        else:
            idx = s / n + np.sqrt(2.0 * np.log(t) / n)
            a = int(idx.argmax())          # optimism
        x = float(rng.random() < MEANS[a]) # Bernoulli pull
        n[a] += 1; s[a] += x
        regret += GAPS[a]
    return regret

def thompson(T, seed):
    rng = np.random.default_rng(seed)
    alpha = np.ones(K); beta = np.ones(K)  # Beta(1,1) priors
    regret = 0.0
    for t in range(T):
        theta = rng.beta(alpha, beta)      # one posterior draw per arm
        a = int(theta.argmax())            # probability matching
        x = float(rng.random() < MEANS[a])
        alpha[a] += x; beta[a] += 1.0 - x
        regret += GAPS[a]
    return regret

# measured over 400 runs at T=1e5: UCB1 461.2 +/- 2.6,
# Thompson 78.3 +/- 1.1, UCB1 Theorem-1 bound 2305.8

import torch

MEANS = torch.tensor([0.60, 0.50, 0.45, 0.40, 0.30])
K = MEANS.numel()
GAPS = MEANS.max() - MEANS

def ucb1(T, seed):
    g = torch.Generator().manual_seed(seed)
    n = torch.zeros(K); s = torch.zeros(K)
    regret = 0.0
    for t in range(1, T + 1):
        if t <= K:
            a = t - 1
        else:
            idx = s / n + torch.sqrt(2.0 * torch.log(torch.tensor(float(t))) / n)
            a = int(idx.argmax())
        x = float(torch.rand((), generator=g) < MEANS[a])
        n[a] += 1; s[a] += x
        regret += float(GAPS[a])
    return regret

def thompson(T, seed):
    g = torch.Generator().manual_seed(seed)
    alpha = torch.ones(K); beta = torch.ones(K)
    regret = 0.0
    for t in range(T):
        theta = torch.distributions.Beta(alpha, beta).sample()
        a = int(theta.argmax())
        x = float(torch.rand((), generator=g) < MEANS[a])
        alpha[a] += x; beta[a] += 1.0 - x
        regret += float(GAPS[a])
    return regret

import jax
import jax.numpy as jnp

MEANS = jnp.array([0.60, 0.50, 0.45, 0.40, 0.30])
K = MEANS.shape[0]
GAPS = MEANS.max() - MEANS

@jax.jit
def ucb1(key, T=100_000):
    def body(t, carry):
        n, s, regret, key = carry
        key, k1 = jax.random.split(key)
        idx = jnp.where(n > 0,
                        s / jnp.maximum(n, 1)
                        + jnp.sqrt(2.0 * jnp.log(t + 1.0)
                                   / jnp.maximum(n, 1)),
                        jnp.inf)               # unplayed arms first
        a = idx.argmax()
        x = (jax.random.uniform(k1) < MEANS[a]).astype(jnp.float32)
        return (n.at[a].add(1.0), s.at[a].add(x),
                regret + GAPS[a], key)
    n, s, regret, _ = jax.lax.fori_loop(
        0, T, body, (jnp.zeros(K), jnp.zeros(K), 0.0, key))
    return regret

@jax.jit
def thompson(key, T=100_000):
    def body(t, carry):
        alpha, beta, regret, key = carry
        key, k1, k2 = jax.random.split(key, 3)
        theta = jax.random.beta(k1, alpha, beta)  # posterior draws
        a = theta.argmax()
        x = (jax.random.uniform(k2) < MEANS[a]).astype(jnp.float32)
        return (alpha.at[a].add(x), beta.at[a].add(1.0 - x),
                regret + GAPS[a], key)
    _, _, regret, _ = jax.lax.fori_loop(
        0, T, body, (jnp.ones(K), jnp.ones(K), 0.0, key))
    return regret

print(ucb1(jax.random.PRNGKey(0)), thompson(jax.random.PRNGKey(1)))

What the runs measured

Collected results from classes/data/rl-theory.json, all quoted earlier in context, gathered here for reference.

How it is done in practice: where the theory binds

Sample complexity in real problems

The minimax theory says tabular exploration costs \( \tilde O(\sqrt{H S A T}) \) regret, which sounds encouraging until the sizes are plugged in. State spaces in real problems are not enumerable, so the tabular bounds are vacuous verbatim, and the function-approximation bounds depend on structural assumptions (linear MDPs, low Bellman rank) that real environments are not known to satisfy. The theory still binds, just indirectly. It says what the price is paid for. Every factor in the bounds corresponds to a mechanism, horizon compounds errors (\( H \) or \( 1/(1-\gamma) \) factors), coverage must be bought (the \( S A \) factor is the cost of touching everything), and noise must be averaged away (the \( \sqrt{T} \)). Deep RL's empirical sample complexities, millions of frames for Atari, billions of environment steps for competitive Dota or StarCraft agents, tens of thousands of expensive rollouts for RLHF, are these mechanisms operating through a function approximator's generalization rather than a table. The practical craft, reward shaping, curricula, demonstrations, resets to interesting states, is a menu of ways to smuggle in coverage so the \( S A \)-shaped cost does not have to be paid by undirected exploration.

Reward design and reward hacking

The formalism treats \( r \) as given. Practice has to write it, and the optimality machinery on this page is exactly as good at maximizing the written reward's defects as its intent. Problem 8's episodic constant is the toy version. The production versions are boat-racing agents circling reward pickups instead of finishing, groundedness rewards gamed by verbose hedging, and RLHF policies drifting into the reward model's off-distribution blind spots and scoring arbitrarily well there, the offline-RL failure mode operating on the reward model instead of the value function. The theory offers two disciplined tools, potential-based shaping for adding guidance without changing the optimum, and distribution-shift penalties (KL terms against a reference policy) for staying where the learned reward is trustworthy, both of which are standard in modern RLHF pipelines. What it cannot offer is a guarantee that the written reward means what its author intended. That failure mode, specification gaming, has a growing empirical literature and is a core safety concern rather than an engineering nuisance.

The discount factor as a hyperparameter

In the formalism, \( \gamma \) defines the objective. In practice almost no one chooses it that way. It is tuned, typically in \( \{0.99, 0.995, 0.999\} \), because it controls a bias-variance trade the theory makes precise. Smaller \( \gamma \) shortens the effective horizon, shrinks return variance, tightens every \( 1/(1-\gamma) \)-dependent bound, and speeds contraction. It also biases the agent against genuinely long-term consequences, solving a deliberately myopic proxy of the task. Blackwell optimality gives the clean theoretical statement (there exists \( \gamma_0 < 1 \) such that a single policy is optimal for all \( \gamma \in (\gamma_0, 1) \), so pushing \( \gamma \) high enough recovers the far-sighted optimum), and analyses of the discount as an explicit regularizer (Jiang, Kulesza, Singh, and Lewis, 2015) show a lower-than-"true" \( \gamma \) provably helps when the model or value function is estimated from limited data. Myopia is a form of regularization. Reading \( \gamma \) as a hyperparameter with a bias-variance dial, rather than a fact about the world, is the correct modern posture, and GAE's \( \lambda \) plays the same role one level up.

The gap between tabular guarantees and deep RL

It is worth being blunt about what is and is not proved for the systems that make headlines. DQN, PPO on neural policies, actor-critic systems, and RLHF fine-tuning carry no convergence guarantees. They inherit the deadly triad, non-compatible critics, and non-concave objectives, and their reliability is an empirical achievement built from stabilizers (target networks, replay, trust regions, advantage normalization, KL penalties) each of which maps onto a specific theoretical failure mode discussed above. That mapping is the practical value of this page's theory. When a deep RL run diverges, oscillates, overestimates values, or hacks its reward, the tabular theory names the mechanism and points at which stabilizer addresses it. The per-algorithm engineering, and what actually happens at scale, is the subject of the RL section's pages on Q-learning/DQN, policy gradients, PPO, and GRPO/RLHF.

The current research frontier

A general theory of when RL is statistically possible. The tabular question is closed (minimax regret settled by Azar et al. 2017 and successors), so the frontier moved to function approximation, asking which structural properties make exploration tractable. Three competing frameworks aim to be the final answer, the Bellman-Eluder dimension (Jin, Liu, and Miryoosefi, Princeton), bilinear classes (Du, Kakade, Lee, Lovett, Mahajan, Sun, and Wang, spanning Washington, Harvard, and Cornell), and the decision-estimation coefficient of Foster, Kakade, Golowich, and Rakhlin (Microsoft Research and MIT), the last giving matching upper and lower bounds for general interactive decision making and currently the closest thing to a complexity theory of RL. These lines subsume linear MDPs, low-rank MDPs, and most earlier conditions.

Offline RL theory maturing into practice. After the pessimism results (Jin et al., Rashidinejad et al., and related lower bounds from Wang, Foster, and Kakade showing offline linear RL can be exponentially hard), current work refines what coverage really costs, single-policy concentrability as the right quantity, hybrid settings that mix offline data with limited online interaction, and the statistics of learned reward models. This literature is the theoretical backbone of the empirical offline-RL and RLHF-adjacent work at Berkeley (Levine's group) and the direct-alignment line (DPO and successors) covered on the DPO page.

Policy optimization theory. The global convergence program continues past the softmax results, with sharper rates via non-uniform Łojasiewicz analysis (Mei et al., Alberta and Google), mirror-descent views of policy optimization unifying NPG, TRPO, and regularized methods, and convergence theory for actor-critic with two-timescale analysis. The uncomfortable open middle is that almost nothing global is known once the policy class is a neural network, and the honest theoretical frontier is narrowing that gap rather than pretending it is closed.

Exploration at scale and RL for reasoning. Practical exploration research runs through targeted probes like DeepMind's bsuite and continues in the intrinsic-motivation and ensemble-posterior lines (randomized value functions and bootstrapped DQN, Osband et al., a direct descendant of Thompson sampling). Meanwhile the most visible application of the old theory is new. RL with verifiable rewards for LLM reasoning (DeepSeek's R1 and the broader RLVR wave) is textbook policy optimization against a programmatic reward, where the binding constraints are exactly this page's, reward hacking, distribution shift, and credit assignment over long horizons, now at hundreds of billions of parameters. Average-reward and discount-free formulations are also being revisited for continuing agentic tasks (Alberta's line from Wan, Naik, and Sutton). The theory did not change. The stakes did.

Open source to read

Repositories chosen for readability of exactly the algorithms on this page, with the first file worth opening in each.

Farama-Foundation/Gymnasium is the maintained successor of OpenAI Gym and the de facto MDP interface, and every agent-environment loop in the field is shaped by its API. Open gymnasium/core.py first. The Env.step/reset contract is the MDP formalism of this page rendered as a Python protocol, terminal-versus-truncated distinction included.

google-deepmind/rlax offers RL primitives as pure JAX functions, the closest code gets to the equations. Open rlax/_src/value_learning.py to find TD errors, Q-learning, double Q-learning, and expected SARSA as five-line functions with the same names used here.

google-deepmind/bsuite is DeepMind's behavioral test suite isolating core capabilities (exploration, credit assignment, memory) in minimal environments. Open bsuite/environments/deep_sea.py, the canonical needle-in-a-haystack exploration probe on which epsilon-greedy provably needs exponentially many episodes and optimism does not.

vwxyzjn/cleanrl has single-file, hackable implementations of the deep descendants of this page's algorithms. Open cleanrl/dqn.py for Q-learning plus function approximation plus the stabilizers, in ~300 lines you can hold in your head, with the deadly-triad countermeasures (replay buffer, target network) plainly visible.

DLR-RM/stable-baselines3 is the production-grade PyTorch baseline library. Open stable_baselines3/dqn/dqn.py and read train(), the semi-gradient TD update with Polyak-averaged targets, i.e. exactly the compromise with the deadly triad discussed above, written carefully.

openai/spinningup is OpenAI's pedagogical RL codebase, still the best bridge from this page's theory to policy-gradient practice. Open spinup/algos/pytorch/vpg/vpg.py to see the policy gradient theorem as runnable code, with GAE as the \( (\gamma\lambda) \)-weighted TD-error sum derived in the TD(λ) section.

tensorflow/agents is TF-Agents, Google's production library, worth reading precisely because it is engineered rather than pedagogical. Open tf_agents/agents/dqn/dqn_agent.py to see what a deployment-grade version of the same update adds, n-step targets, importance-weighted replay, and both Huber and squared TD losses behind flags.

thu-ml/tianshou is Tsinghua's modular RL platform with unusually clean separation between algorithm and data collection. Open tianshou/policy/modelfree/dqn.py for the n-step Q-learning target assembled explicitly, a direct implementation of the n-step returns section.

Common misconceptions

"Q-learning converges, so DQN converges." The Watkins guarantee is tabular. Add function approximation and off-policy replay and you are running the deadly triad. Baird's counterexample shows divergence is possible with even linear approximation, and DQN's target network and replay buffer are mitigations, not proofs. Nothing about DQN is guaranteed, which is worth saying plainly because the two algorithms share a name.

"The discount factor is part of the problem, so it should be set from the task's true horizon." In practice \( \gamma \) is a regularizer trading bias against variance and conditioning, tuned like any hyperparameter. Lower-than-true discounting provably helps under model error (Jiang et al., 2015), and Blackwell optimality says pushing it high recovers the far-sighted optimum only in the exact setting. Treating \( \gamma \) as sacred rather than tunable leaves performance on the table.

"Epsilon-greedy explores, and the rest is fine-tuning." Constant-\( \epsilon \) exploration pays linear regret forever, by construction, and on structured problems (deep_sea, chain MDPs) undirected dithering needs exponentially many episodes where optimism needs polynomially many. The gap between \( \Omega(T) \) and \( O(\ln T) \) is measured above, 461 versus a Lai–Robbins-shaped 78 at \( T = 10^5 \), and epsilon-greedy would sit at \( \epsilon \bar\Delta T \approx 1{,}500 \) and climbing linearly.

"Off-policy means any data works." Off-policy methods need coverage of the target policy's choices (the importance ratio must be finite, the visitation condition must hold), and correcting a large policy mismatch costs variance that grows exponentially with horizon in the worst case (Problem 3's \( 2^{20} \)). Offline, without new interaction, the requirement sharpens into concentrability, and violating it is not inefficient, it is impossible.

"Monte Carlo is the biased method because it is noisy." This is backwards. First-visit Monte Carlo is exactly unbiased and merely high-variance, while TD is biased during learning because it bootstraps from wrong estimates. The reason TD usually wins anyway is the variance side of the trade plus the certainty-equivalence property of its batch solution, not unbiasedness.

"An optimal policy may need to randomize." In a fully observed finite MDP a deterministic stationary optimal policy always exists (proved above). Randomness earns its place only for exploration during learning, in partially observed problems, and in game-theoretic settings with an adversary, and conflating those cases with the MDP optimum muddles both theory and practice.

"Value iteration converged because the values stopped changing, so they are correct." Small sweep-to-sweep change bounds distance to \( V^* \) only through the \( \gamma\epsilon/(1-\gamma) \) factor. At \( \gamma = 0.99 \), a sweep change of \( 10^{-3} \) still permits value error of 0.099 and greedy policy loss of about 0.2. The stopping rule must be chosen from the bound, not from aesthetics, and the closer \( \gamma \) is to 1 the more misleading "it stopped moving" becomes.

"Offline RL fails for lack of data, so collect more and it works." Dataset size fixes the statistical term. It does nothing to coverage. If the behavior policy never takes near-optimal actions, infinite data from it still contains no information about them (\( C^* = \infty \)), and the lower bounds are indifferent to \( n \). More data of the same distribution sharpens the floor pessimism can guarantee. It does not raise it.

Self-check

References

1. Sutton, R. S., and Barto, A. G. Reinforcement Learning: An Introduction, 2nd ed., MIT Press, 2018. incompleteideas.net/book/the-book-2nd.html
2. Puterman, M. L. Markov Decision Processes: Discrete Stochastic Dynamic Programming, Wiley, 1994. doi:10.1002/9780470316887
3. Bertsekas, D. P. Dynamic Programming and Optimal Control, Vols. I-II, 4th ed., Athena Scientific, 2012/2017. athenasc.com/dpbook.html
4. Bertsekas, D. P. Reinforcement Learning and Optimal Control, Athena Scientific, 2019. athenasc.com/rlbook_athena.html
5. Bertsekas, D. P., and Tsitsiklis, J. N. Neuro-Dynamic Programming, Athena Scientific, 1996. athenasc.com/ndpbook.html
6. Szepesvári, C. Algorithms for Reinforcement Learning, Morgan & Claypool, 2010. sites.ualberta.ca/~szepesva
7. Lattimore, T., and Szepesvári, C. Bandit Algorithms, Cambridge University Press, 2020. doi:10.1017/9781108571401
8. Agarwal, A., Jiang, N., Kakade, S. M., and Sun, W. Reinforcement Learning: Theory and Algorithms, book manuscript. rltheorybook.github.io
9. Thompson, W. R. "On the likelihood that one unknown probability exceeds another in view of the evidence of two samples", Biometrika 25, 1933. doi:10.1093/biomet/25.3-4.285
10. Lai, T. L., and Robbins, H. "Asymptotically efficient adaptive allocation rules", Advances in Applied Mathematics 6, 1985. doi:10.1016/0196-8858(85)90002-8
11. Watkins, C. J. C. H., and Dayan, P. "Q-learning", Machine Learning 8, 1992. doi:10.1007/BF00992698
12. Jaakkola, T., Jordan, M. I., and Singh, S. P. "On the convergence of stochastic iterative dynamic programming algorithms", Neural Computation 6, 1994. doi:10.1162/neco.1994.6.6.1185
13. Baird, L. "Residual algorithms: reinforcement learning with function approximation", ICML, 1995. doi:10.1016/B978-1-55860-377-6.50013-X
14. Tsitsiklis, J. N., and Van Roy, B. "An analysis of temporal-difference learning with function approximation", IEEE Transactions on Automatic Control 42(5), 1997. doi:10.1109/9.580874
15. Sutton, R. S., McAllester, D., Singh, S., and Mansour, Y. "Policy gradient methods for reinforcement learning with function approximation", NeurIPS, 2000. papers.nips.cc/paper/1713
16. Brafman, R. I., and Tennenholtz, M. "R-max: a general polynomial time algorithm for near-optimal reinforcement learning", JMLR 3, 2002. jmlr.org/papers/v3/brafman02a
17. Auer, P., Cesa-Bianchi, N., and Fischer, P. "Finite-time analysis of the multiarmed bandit problem", Machine Learning 47, 2002. doi:10.1023/A:1013689704352
18. Sutton, R. S., Maei, H. R., Precup, D., Bhatnagar, S., Silver, D., Szepesvári, C., and Wiewiora, E. "Fast gradient-descent methods for temporal-difference learning with linear function approximation", ICML, 2009. doi:10.1145/1553374.1553501
19. van Hasselt, H. "Double Q-learning", NeurIPS, 2010. papers.nips.cc/paper/3964
20. Jaksch, T., Ortner, R., and Auer, P. "Near-optimal regret bounds for reinforcement learning", JMLR 11, 2010. jmlr.org/papers/v11/jaksch10a
21. Russo, D., and Van Roy, B. "Learning to optimize via posterior sampling", Mathematics of Operations Research 39(4), 2014. arXiv:1301.2609
22. Azar, M. G., Osband, I., and Munos, R. "Minimax regret bounds for reinforcement learning", ICML, 2017. arXiv:1703.05449
23. Levine, S., Kumar, A., Tucker, G., and Fu, J. "Offline reinforcement learning: tutorial, review, and perspectives on open problems", 2020. arXiv:2005.01643
24. Agarwal, A., Kakade, S. M., Lee, J. D., and Mahajan, G. "On the theory of policy gradient methods: optimality, approximation, and distribution shift", JMLR 22, 2021. arXiv:1908.00261
25. Jin, Y., Yang, Z., and Wang, Z. "Is pessimism provably efficient for offline RL?", ICML, 2021. arXiv:2012.15085
26. Rashidinejad, P., Zhu, B., Ma, C., Jiao, J., and Russell, S. "Bridging offline reinforcement learning and imitation learning: a tale of pessimism", NeurIPS, 2021. arXiv:2103.12021