Reinforcement Learning Theory

A Guarantee Is Assumptions Plus a Conclusion

Reinforcement-learning theory asks several questions that empirical performance can blur together.

Convergence asks whether an iterate approaches a fixed point:

Sample complexity asks how much data give a finite-accuracy guarantee:

Regret measures reward lost while learning:

PAC analysis counts how often behavior is more than $\epsilon$ suboptimal. Approximation analysis separates errors from finite data, restricted function classes, imperfect optimization, and repeated Bellman backups.

These conclusions are not interchangeable. In particular,

measures value-estimation error, while

measures the performance of the policy induced by that estimate.

Every theorem should therefore be read as

A tabular theorem may rely on independently stored values for all $S A$ state-action pairs. A generative-model theorem may assume that we can request independent samples from any chosen pair:

That assumption supplies coverage and removes exploration. A function-approximation theorem may instead require realizability, Bellman closure, distributional coverage, and exact optimization. Quoting the rate while dropping these conditions changes the claim.

Bellman Operators Contract Error

For a fixed policy $\pi$, define

The policy-evaluation operator is

Its fixed point is the policy value:

In matrix form,

The inverse expands as

Since a stochastic matrix is nonexpansive in the supremum norm,

This is the first appearance of the effective-horizon factor $1/(1-\gamma)$.

The Bellman optimality operator is

It is a $\gamma$-contraction:

Contraction also proves uniqueness. If $V_1=TV_1$ and $V_2=TV_2$, then

Since $\gamma<1$, this requires $V_1=V_2$.

Value Iteration Converges Geometrically

Value iteration repeatedly applies

Because $TV^*=V^*$, contraction gives

Unrolling,

If $V_0=0$ and rewards lie in $[0,R_{\max}]$, then

so

To make the error at most $\epsilon$, it is sufficient that

When $\gamma$ is close to one,

so the iteration count scales like

Bellman residuals provide a stopping rule

For any candidate value $V$,

For value iteration, $TV_k=V_{k+1}$. Therefore

is sufficient for value error at most $\epsilon$.

Geometric convergence is an optimization statement with a known model. It does not yet say how accurately the model can be estimated from finite data.

Concentration Controls Model Estimation

Assume a generative model supplies $N$ independent next-state samples for every $(s,a)$:

The empirical transition is

For independent $X_i\in[b_-,b_+]$, Hoeffding's inequality implies

Equivalently, with probability at least $1-\delta$,

The characteristic statistical rate is $N^{-1/2}$.

For an $S$-outcome transition distribution, a standard categorical concentration bound has the form

To make this hold for all $S A$ pairs, apply a union bound with failure probability $\delta/(SA)$ per pair:

Uniform control costs only a logarithmic factor in the number of simultaneous events, but estimating each categorical distribution introduces the state-dimension factor.

Simulation Lemmas Propagate Model Error

Consider two MDPs with the same discount and policy $\pi$. Suppose, uniformly over $(s,a)$,

If $\|V_i^\pi\|_\infty\le V_{\max}$, then

For rewards bounded by $R_{\max}$,

Reward error is summed across the effective horizon. Transition error changes which future value is reached, and that future value already contains an effective-horizon sum, producing $1/(1-\gamma)^2$.

Model accuracy implies policy accuracy

Suppose every policy has uniformly accurate empirical values:

Let $\pi^*$ be optimal in the true MDP and $\widehat\pi^*$ optimal in the empirical MDP. Then

The factor two pays once for evaluating the true optimum in the empirical model and once for deploying the empirical optimum in the true model.

A Finite-Sample Bound

Combine uniform transition concentration,

with the transition-only simulation lemma:

With probability at least $1-\delta$,

Solving for value error at most $\epsilon$ gives

This is the number of independent samples per state-action pair. Across all pairs,

The qualitative dependencies matter:

This bound assumes tabularity, independent oracle sampling, bounded rewards, and uniform error. It does not count the online cost of reaching each pair or describe neural-network optimization.

Fitted Q-Iteration Adds Projection Error

Fitted Q-iteration alternates Bellman targets with regression into a function class $\mathcal F$:

Its one-step error has two sources:

Assume the total one-step deviation is bounded by

Then the error recursion is

A persistent local regression error creates a global error floor amplified by the horizon:

Exact Bellman closure means

Approximate closure requires

Without closure, every Bellman step can introduce fresh projection error. Practical $L_2$ regression adds another issue: low average error under a sampling distribution need not control the rare states selected by a new policy.

Regret and PAC Measure Learning Behavior

Convergence and sample complexity can assume coverage. Online learning must pay for exploration.

For a bandit, define

Regret decomposes as

A no-regret algorithm satisfies

Problem-independent bounds may scale like $\widetilde O(\sqrt{AT})$. Problem-dependent bounds exploit the gaps:

PAC analysis instead counts substantially bad decisions. In a discounted MDP, a typical statement says that, with probability at least $1-\delta$,

on all but a number of steps polynomial in

If $N_\epsilon(T)$ counts decisions with loss greater than $\epsilon$, then

Every $\epsilon$-bad decision contributes more than $\epsilon$ regret. Regret retains the magnitude of every loss; PAC primarily tracks how many large losses occur.

Frequentist regret conditions on one fixed unknown environment. Bayesian regret additionally averages over a prior:

Optimism Converts Uncertainty into Exploration

MBIE-EB maintains empirical rewards, transitions, and counts, then solves an optimistic Bellman equation:

The acting policy is greedy with respect to $\widetilde Q$.

The bonus mirrors concentration:

On a high-probability confidence event, it makes the estimated value optimistic:

The PAC argument has four steps:

1. Concentration gives simultaneous confidence intervals.
2. Bonuses make the empirical solution optimistic.
3. Frequently sampled pairs become accurate by the simulation lemma.
4. Each pair can be insufficiently sampled only a bounded number of times.

The agent therefore either acts nearly optimally at a known pair or visits an unknown pair and reduces uncertainty. This turns exploration into a countable resource.

In large spaces, literal counts fail. Bonuses must generalize through features, density models, or uncertainty estimates, weakening the clean tabular guarantee. The companion note on exploration develops these mechanisms and posterior sampling in detail.

Posterior Sampling Randomizes the Optimistic Model

Bayesian methods maintain

instead of a deterministic confidence set. Posterior Sampling for Reinforcement Learning draws

solves the sampled MDP, and follows its optimal policy for an episode:

The induced action distribution is probability matching:

Optimism acts as if a favorable plausible model were true. Posterior sampling draws one plausible model according to posterior mass. Holding that model for an episode produces a temporally coherent experiment.

The guarantee now depends on whether the prior and posterior model the environment meaningfully, and on whether planning in each sample is computationally feasible.

Function Approximation Replaces Counts with Structure

Tabular complexity depends directly on $S A$. A linear value model uses

so one observation can constrain many state-action pairs.

Under a representative linear-MDP assumption,

Complexity can then depend on feature dimension $d$ instead of raw state count. This gain requires the known features to align with rewards and transitions.

Modern theories use structural quantities such as:

• Bellman rank, which captures low-dimensional factorization of Bellman errors;
• eluder dimension, which counts how long sequentially selected inputs can remain informationally independent;
• concentrability coefficients, which connect regression distributions to occupancies of evaluated policies.

These quantities are not interchangeable and are not merely parameter counts. Each theorem defines its own function classes, data distributions, realizability conditions, and optimization assumptions.

Function approximation creates a coupled tradeoff:

Overgeneralization erases meaningful uncertainty. Undergeneralization degenerates toward tabular learning. There is no universal theory in which arbitrary deep networks automatically provide correct values and calibrated exploration.

Reading a Theory Claim

Before using a bound, identify:

• whether the MDP is tabular, linear, or represented by a general function class;
• whether samples are independent oracle queries or one correlated trajectory;
• whether rewards are bounded and the task is discounted or finite horizon;
• whether coverage, realizability, or Bellman completeness is assumed;
• whether optimization is exact;
• whether the metric is convergence, value error, policy loss, regret, Bayesian regret, or a PAC count;
• whether the norm is uniform or averaged under a particular distribution;
• whether exploration cost is included.

Horizon factors deserve special attention:

A bound can be polynomial yet enormous when $\gamma$ is close to one.

The proof pipeline in this note is

For approximate value learning, insert fitting and closure errors before Bellman propagation. For online RL, insert an exploration argument before concentration.

Theory is most useful when it exposes which difficulty a result has controlled and which difficulty it has assumed away.