RL Theory

What RL theory asks, and what it’s actually for

This is “the only theory lecture in this course,” and Levine’s goal is not depth but flavor: what kinds of analysis can we do, and what kinds of conclusions do they support? The typical questions are sample-complexity statements. If an algorithm gets $N$ samples per iteration for $k$ iterations, how good is the result — can we show $\|\hat{Q}_k - Q^\star\| \le \epsilon$ with probability at least $1 - \delta$ whenever $N \ge f(\epsilon, \delta)$, for some well-behaved $f$? A subtly different question: how good is the policy the Q-function induces — is $\|Q^{\pi_k} - Q^\star\| \le \epsilon$, where $Q^{\pi_k}$ is the true expected reward of the greedy policy under $\hat{Q}_k$? Not the same thing: $\hat{Q}_k$ can overestimate wildly while its argmax policy is fine. A third family asks about exploration, e.g. the upper-confidence-bound regret bound $\text{Reg}(T) \le \mathcal{O}\big(\sqrt{T \cdot N \cdot \log \frac{NT}{\delta}}\big) + \delta T$.

Before any analysis, Levine is blunt about the payoff. Proving that deep RL algorithms “work perfectly every time” is off the table — with all the tricks of the trade, they aren’t even guaranteed to converge. The real purpose is to understand how error responds to problem parameters: do larger discounts make problems easier or harder? If you want half the error, do you need $2\times$ the samples, or $4\times$?

Abstracting away exploration

Effective analysis in RL is “very hard without strong assumptions,” and the trick is choosing assumptions that admit interesting conclusions without divorcing us too much from reality. The big structural choice is to separate exploration from learning. Worst-case exploration — the thing guarantees must address — is extremely pessimistic and tends to dominate any joint analysis, while typical exploration (say, with a well-shaped reward) is nowhere near that bad. Exploration analysis has its own goal: show a method finds an $\epsilon$-good policy in time polynomial in $|S|$, $|A|$, and the horizon. To study learning on its own, we delete exploration entirely:

The first algorithm analyzed is deliberately naive and tabular: estimate $\hat{P}(s' \mid s, a) = \#(s,a,s')/N$ by counting, then, given a policy $\pi$, compute $\hat{Q}^\pi$ exactly under $\hat{P}$ — exact solution of an inexact model, so all the error comes from $\hat{P} \ne P$. The questions, all in the infinity norm because it bounds the worst-case state–action pair: how close is $\hat{Q}^\pi$ to $Q^\pi$? How close is $\hat{Q}^\star$ to $Q^\star$? And how suboptimal is the resulting greedy policy — $\|Q^\star - Q^{\hat{\pi}^\star}\|_\infty$, the number that actually quantifies RL performance? The first question turns out to be the tool that answers the other two.

Concentration inequalities: the supervised-learning toolkit

Whenever we ask how close a learned quantity is to the truth as a function of sample count, the tool is a concentration inequality. The most basic is Hoeffding’s:

Hoeffding covers real-valued means, but $\hat{P}(s' \mid s,a)$ is a categorical distribution. The analogue for discrete distributions bounds the $\ell_1$ error — total variation divergence, the norm we’ll use: with $N$ i.i.d. samples of a $d$-valued variable, $\Pr\big(\|\hat{q} - q\|_1 \ge \sqrt{d}\,(1/\sqrt{N} + \epsilon)\big) \le e^{-N\epsilon^2}$. Substituting the model estimate ($d = |S|$) and absorbing constants,

$\|\hat{P}(\cdot \mid s,a) - P(\cdot \mid s,a)\|_1 \le c\,\sqrt{\frac{|S| \log 1/\delta}{N}} \quad \text{with probability } 1 - \delta.$

Same shape as Hoeffding: error falls as $1/\sqrt{N}$, grows as $\sqrt{|S|}$.

From model error to Q-function error: the simulation lemma

Now the RL-specific part: pass this supervised-learning bound through the Bellman machinery. Writing the Bellman equation in matrix form — $Q^\pi$ and $r$ as vectors of length $|S||A|$, $P$ as an $|S||A| \times |S|$ matrix, $V^\pi = \Pi Q^\pi$ with $\Pi$ the policy matrix, and $P^\pi = P\Pi$ — gives $Q^\pi = r + \gamma P^\pi Q^\pi$, and since $I - \gamma P^\pi$ is (non-trivially) always invertible,

$Q^\pi = (I - \gamma P^\pi)^{-1} r.$

Policy evaluation is a linear operation, and the same identity holds under $\hat{P}$: $\hat{Q}^\pi = (I - \gamma \hat{P}^\pi)^{-1} r$. Two lemmas do the rest.

The second lemma controls the evaluation operator: for any vector $v$, $\|(I - \gamma P^\pi)^{-1} v\|_\infty \le \|v\|_\infty / (1 - \gamma)$ — the “Q-function” of a pseudo-reward $v$ is at most $1/(1-\gamma)$ times larger. The proof sets $w = (I - \gamma P^\pi)^{-1} v$ and uses the triangle inequality plus the fact that a stochastic matrix cannot increase an infinity norm: $\|v\|_\infty \ge \|w\|_\infty - \gamma\|P^\pi w\|_\infty \ge (1-\gamma)\|w\|_\infty$. Whenever you see $1/(1-\gamma)$, think horizon: discounted sums are geometric series, $\sum_t \gamma^t c = c/(1-\gamma)$, so $1/(1-\gamma)$ is the effective horizon of an infinite-horizon problem.

Chaining the lemmas, bounding the matrix–vector product crudely by the max-row $\ell_1$ norm times $\|V^\pi\|_\infty$, using $\|V^\pi\|_\infty \le R_{\max}/(1-\gamma)$ with the standard normalization $R_{\max} = 1$, and applying the concentration bound (with a union bound over all $(s,a)$, which only changes constants):

$\|Q^\pi - \hat{Q}^\pi\|_\infty \;\le\; \frac{\gamma}{(1-\gamma)^2}\, c_2 \sqrt{\frac{|S| \log 1/\delta}{N}}$

The qualitative content: error still concentrates at the supervised rate $1/\sqrt{N}$, but it grows quadratically in the effective horizon $1/(1-\gamma)$ — each Bellman backup accumulates error over the horizon. (Not every scheme is quadratic, but this naive one is.)

Two corollaries follow almost for free. For the optimal Q-functions, use $|\sup_x f - \sup_x g| \le \sup_x |f - g|$ with $Q^\star = \sup_\pi Q^\pi$: since the per-policy bound holds for all $\pi$, $\|Q^\star - \hat{Q}^\star\|_\infty \le \epsilon$. For the policy $\hat{\pi}^\star$ greedy under $\hat{Q}^\star$, subtract and add $\hat{Q}^{\hat{\pi}^\star}$ and apply the triangle inequality: one term is the optimal-Q gap ($\le \epsilon$, noting $\hat{Q}^{\hat{\pi}^\star} = \hat{Q}^\star$), the other compares true and learned Q for the same policy ($\le \epsilon$), so $\|Q^\star - Q^{\hat{\pi}^\star}\|_\infty \le 2\epsilon$.

Analyzing fitted Q-iteration

Part two analyzes something closer to an algorithm we’d actually run — model-free fitted Q-iteration — though still idealized, since the real thing isn’t guaranteed to converge at all. Exact Q-iteration applies the Bellman optimality operator $T Q = r + \gamma P \max_a Q$ (a block-wise max over actions per state); the approximate version fits

$\hat{Q}_{k+1} \leftarrow \arg\min_{\hat{Q}} \|\hat{Q} - \hat{T}\hat{Q}_k\|$

with two error sources. First, $\hat{T} \ne T$: the approximate operator $\hat{T}Q = \hat{r} + \gamma \hat{P} \max_a Q$ uses the empirical averages $\hat{r}(s,a)$ and $\hat{P}(s' \mid s,a)$ over the data. Levine stresses these “are not models” — they’re exactly the effect of averaging together the regression targets for each state–action tuple. That mismatch is sampling error. Second, the minimization itself is inexact — function approximation never fits the targets perfectly. That’s approximation error, and since squared-error fitting breaks even convergence proofs, the analysis assumes the fit is controlled in the infinity norm: $\|\hat{Q}_{k+1} - T\hat{Q}_k\|_\infty \le \epsilon_k$ — “a strong assumption,” since real supervised learning bounds a weighted expectation, not the worst case.

Sampling error reduces to the earlier toolkit. Splitting $|\hat{T}Q(s,a) - TQ(s,a)|$ into a reward term and a next-value term, Hoeffding bounds the first by $2R_{\max}\sqrt{\log(1/\delta)/2N}$, and the categorical concentration bound handles the second, giving (after a union bound over $(s,a)$)

$\|\hat{T}Q - TQ\|_\infty \le 2R_{\max} c_1 \sqrt{\frac{\log |S||A|/\delta}{2N}} + c_2 \|Q\|_\infty \sqrt{\frac{\log |S|/\delta}{N}}.$

For approximation error, subtract and add $T\hat{Q}_{k-1}$ inside $\|\hat{Q}_k - Q^\star\|_\infty$, use $Q^\star = TQ^\star$ (the fixed point), and invoke the fact that $T$ is a $\gamma$-contraction in the infinity norm:

$\|\hat{Q}_k - Q^\star\|_\infty \le \epsilon_{k-1} + \gamma \|\hat{Q}_{k-1} - Q^\star\|_\infty.$

Unrolling the recursion gives $\sum_{i=0}^{k-1} \gamma^i \epsilon_{k-i-1} + \gamma^k \|\hat{Q}_0 - Q^\star\|_\infty$: the initialization is forgotten as $k \to \infty$, and bounding every $\epsilon_i$ by the worst one turns the sum into a geometric series:

$\lim_{k \to \infty} \|\hat{Q}_k - Q^\star\|_\infty \le \frac{1}{1-\gamma} \max_k \epsilon_k.$

Every backup incurs fresh fitting error, and you make a horizon’s worth of backups. Finally, put the two together by letting $\epsilon_k$ absorb both errors — $\|\hat{Q}_k - T\hat{Q}_{k-1}\|_\infty \le \|\hat{Q}_k - \hat{T}\hat{Q}_{k-1}\|_\infty + \|\hat{T}\hat{Q}_{k-1} - T\hat{Q}_{k-1}\|_\infty$ — and note that the sampling term carries $\|Q\|_\infty = \mathcal{O}(R_{\max}/(1-\gamma))$ inside the outer $1/(1-\gamma)$: the total error is again quadratic in the effective horizon, just as in part one. Infinity-norm assumptions aren’t realistic for practical learners; more advanced results use $p$-norms weighted by a distribution $\mu$ — at $p = 2$ that’s exactly the familiar quadratic Bellman error — but those need their own assumptions to dodge non-convergence, and the RL theory book by Agarwal, Jiang, Kakade, and Sun (the source this lecture follows) develops them properly.

Check yourself

Derivation-style exercises in the lecture’s spirit — work them on paper.

Problem 17.1 Hoeffding sample complexity

Rewards for a fixed $(s,a)$ lie in $[0, 1]$, and you estimate $r(s,a)$ by averaging $n$ samples. Using Hoeffding’s inequality, how many samples guarantee error at most $\epsilon$ with probability at least $1 - \delta$ (two-sided)? If you then decide you want half the error at the same confidence, by what factor must $n$ grow? What if you instead want failure probability $\delta/10$ at the same $\epsilon$?

Show solution

Two-sided failure probability: $\delta \le 2 e^{-2n\epsilon^2/(b_+-b_-)^2}$ with $b_+ - b_- = 1$. Solving: $\log(\delta/2) \le -2n\epsilon^2$, so $n \ge \frac{1}{2\epsilon^2} \log \frac{2}{\delta}$. Halving $\epsilon$ multiplies the $1/\epsilon^2$ factor by 4 — you need $4\times$ the samples, which answers Levine’s “if we want half the error, do we need $2\times$ or $4\times$?” question for this estimator. Dropping $\delta$ to $\delta/10$ only changes $\log(2/\delta)$ to $\log(20/\delta)$ — an additive $\log 10$ inside the logarithm — so confidence is cheap: sample cost grows logarithmically in $1/\delta$ but quadratically in $1/\epsilon$.

Problem 17.2 evaluation-operator lemma

Prove that for any vector $v \in \mathbb{R}^{|S||A|}$, $\|(I - \gamma P^\pi)^{-1} v\|_\infty \le \|v\|_\infty / (1 - \gamma)$. State exactly where you use (a) the triangle inequality and (b) the fact that $P^\pi$ is a stochastic matrix. Then explain in one sentence why this is the algebraic shadow of the geometric series $\sum_t \gamma^t c = c/(1-\gamma)$.

Show solution

Let $w = (I - \gamma P^\pi)^{-1} v$, so $v = (I - \gamma P^\pi) w$. Then $\|v\|_\infty = \|w - \gamma P^\pi w\|_\infty \ge \|w\|_\infty - \gamma \|P^\pi w\|_\infty$ — this is (a), the reverse triangle inequality $\|a - b\| \ge \|a\| - \|b\|$. Next, each entry of $P^\pi w$ is a convex combination of entries of $w$ (rows of a stochastic matrix are nonnegative and sum to 1), so $\|P^\pi w\|_\infty \le \|w\|_\infty$ — this is (b). Combining: $\|v\|_\infty \ge (1 - \gamma)\|w\|_\infty$, and dividing by $1 - \gamma$ gives the claim. The connection to the geometric series: $(I - \gamma P^\pi)^{-1}$ is the discounted sum $\sum_{t=0}^\infty (\gamma P^\pi)^t$, each term of which shrinks $v$‘s infinity norm by at most a factor $\gamma^t$; summing the worst case gives $\|v\|_\infty \sum_t \gamma^t = \|v\|_\infty/(1-\gamma)$ — the effective horizon.

Problem 17.3 from evaluation to policy suboptimality

Suppose you have already proven $\|Q^\pi - \hat{Q}^\pi\|_\infty \le \epsilon$ for every policy $\pi$. Using only the identity $|\sup_x f(x) - \sup_x g(x)| \le \sup_x |f(x) - g(x)|$ and the triangle inequality, derive (a) $\|Q^\star - \hat{Q}^\star\|_\infty \le \epsilon$ and (b) $\|Q^\star - Q^{\hat{\pi}^\star}\|_\infty \le 2\epsilon$, where $\hat{\pi}^\star$ is the greedy policy under $\hat{Q}^\star$. Identify the step where it matters that both Q-functions in one of your terms belong to the same policy.

Show solution

(a) $Q^\star = \sup_\pi Q^\pi$ and $\hat{Q}^\star = \sup_\pi \hat{Q}^\pi$, so $\|Q^\star - \hat{Q}^\star\|_\infty = \|\sup_\pi Q^\pi - \sup_\pi \hat{Q}^\pi\|_\infty \le \sup_\pi \|Q^\pi - \hat{Q}^\pi\|_\infty \le \epsilon$, since the per-policy bound holds uniformly. (b) Insert $-\hat{Q}^{\hat{\pi}^\star} + \hat{Q}^{\hat{\pi}^\star}$ and apply the triangle inequality: $\|Q^\star - Q^{\hat{\pi}^\star}\|_\infty \le \|Q^\star - \hat{Q}^{\hat{\pi}^\star}\|_\infty + \|\hat{Q}^{\hat{\pi}^\star} - Q^{\hat{\pi}^\star}\|_\infty$. For the first term, note $\hat{Q}^{\hat{\pi}^\star} = \hat{Q}^\star$ because $\hat{\pi}^\star$ is optimal in the learned MDP; by (a) this term is $\le \epsilon$. The second term compares the learned and true Q-functions of the same policy $\hat{\pi}^\star$ — this is exactly where the same-policy structure matters, because only then does the part-one evaluation bound apply directly, giving $\le \epsilon$. Total: $2\epsilon$. The greedy policy’s true return is within $2\epsilon$ of optimal.

Problem 17.4 horizon scaling

The main model-based bound is $\|Q^\pi - \hat{Q}^\pi\|_\infty \le \frac{\gamma}{(1-\gamma)^2} c_2 \sqrt{|S| \log(1/\delta) / N}$. (a) Trace where each of the two factors of $1/(1-\gamma)$ enters the derivation. (b) You move from $\gamma = 0.99$ to $\gamma = 0.995$, doubling the effective horizon. By what factor must $N$ grow to keep the bound unchanged? (c) Why does the bound carry a factor $\sqrt{|S|}$ but only $\sqrt{\log(1/\delta)}$?

Show solution

(a) One factor comes from the evaluation operator: the simulation lemma passes $(P - \hat{P})V^\pi$ through $(I - \gamma\hat{P}^\pi)^{-1}$, which inflates the infinity norm by at most $1/(1-\gamma)$. The second comes from bounding $\|V^\pi\|_\infty$ itself: values are discounted reward sums, so with $R_{\max} = 1$, $\|V^\pi\|_\infty \le 1/(1-\gamma)$. Model error weighted by values, then backed up over a horizon — error per backup, accumulated over a horizon’s worth of backups. (b) Doubling $1/(1-\gamma)$ multiplies the bound by 4 through the quadratic term. To cancel a factor of 4 you need $\sqrt{N}$ to grow by 4, i.e. $N$ must grow by $16\times$. Long horizons are punishingly expensive under this scheme. (c) The $\sqrt{|S|}$ enters through the categorical concentration inequality — estimating an $|S|$-outcome distribution in total variation costs $\sqrt{d}$ with $d = |S|$ — while $\delta$ enters through the exponential tail $e^{-N\epsilon^2}$, so solving for $\epsilon$ pulls it inside a logarithm: confidence is exponentially cheap, state-space coverage is polynomially expensive.