Andrea Zanette · Statistical Foundations of RL

Why deep RL needs a theory at all

Andrea Zanette opens with a lecture of “a different flavor”: instead of new algorithms, the theoretical foundations of the ones you’ve already seen. Step back and the obstacles to deploying RL in the real world are consistent — stability (tricks and hyperparameter tuning to make training converge at all), data efficiency (RL is “extremely data hungry” next to supervised learning), generalization across tasks, and raw compute. In the real world these stop being annoyances: samples are interactions, interactions are expensive, and you want predictability before you let an algorithm act.

Why expect theory to help? The basic protocols of the field — value iteration, policy iteration, upper-confidence-bound exploration, REINFORCE and policy gradients — are all theory-motivated and come with guarantees in their simplest forms. There are genuine success stories of theory becoming practice: randomized least-squares value iteration “which you might know as bootstrapped DQN”. And theory uncovers fundamental limits — things no algorithm can do — one of which is the centerpiece of this lecture.

The questions you’d like answered about any algorithm: does it converge, how should the hyperparameters be chosen, how many interactions does it need for a given performance, and what does it cost to run. The honest status report is sobering — for most deep methods you can’t even prove convergence, because TD with experience replay and target networks “are not always guaranteed to converge”, and “there is kind of a huge gap right now” between the practical algorithms in this course and what theory can certify. Zanette therefore narrows to the statistical question — how many samples? — in three parts: which problems are easy, what function approximation does to learnability, and what guarantees offline RL admits.

Regret, and adapting to easy problems

The first setting is online exploration: an agent starts with an empty dataset, interacts for $H$ steps per episode over many episodes, and should play better and better policies.

For tabular problems — small, explicitly enumerated state and action spaces — a decade of work (from roughly 2010–2011 on) drove regret bounds, functions of the state and action cardinalities, horizon, and number of episodes, down to an algorithm that is minimax optimal: its worst-case guarantee matches the known lower bound, so it is unimprovable across all MDPs. But worst-case is exactly the limitation. In practice the same algorithm performs wildly differently on different problems, and some problem classes are visibly easier than the lower-bound construction: problems with weak memory, where past actions barely affect the future state — a recommender system is the running example, where a bad recommendation loses you one Amazon customer but “won’t affect the next customer that you see” (contextual bandits); deterministic problems, which are essentially search; and problems where you can only move locally, like mountain car, where mistakes are recoverable.

Zanette’s contribution: a problem-dependent complexity measure — the variance of the next-state optimal value function, $\mathrm{Var}_{s' \sim p(\cdot \mid s, a)}[V^*(s')]$ (a supremum over state–actions in the paper, relaxable to an expectation over trajectories) — and an algorithm whose regret scales with it. The measure captures long-term consequences: in a bandit-like problem, transitions may be highly stochastic, but the value of where you land barely varies, so the quantity is small — “you only lose with the current customer… you don’t mess up the entire long-term plan.”

The mechanism is the exploration bonus. Provably efficient algorithms add a bonus to the reward; the basic choice, from Hoeffding’s inequality, scales like the inverse square root of the visit count — problem-independent, so exploration looks the same on every MDP. The ideal choice is a Bernstein-style bonus containing precisely the next-state value variance — but it needs $Q^*$ and the dynamics, which you don’t have. The fix is to plug in empirical estimates plus correction terms for being wrong; the technical crux is that those corrections decay at a faster rate, and bounding them requires tracking how estimation error propagates through the MDP from states you’ve barely visited.

Function approximation: linear RL is exponentially hard

Real problems have enormous state spaces where most states are never visited, and function approximation is supposed to fix that — ideally with sample cost on the order of the number of parameters, as in supervised learning. The folklore observation is that RL with function approximation still needs far more samples than supervised learning. Is RL fundamentally harder?

The setting resembles offline RL: collect a dataset with a static distribution (chosen intelligently, so a poor dataset can’t be blamed), then predict the value of a different policy or find a good one. Suppose the value function is linearly realizable — a known feature extractor, and a promise that the target value is exactly linear in it. By analogy with linear regression this should be easy: “you can open a textbook in statistics” and one-step prediction of a linear reward is solved, fast, by the most basic algorithm in machine learning. Yet classical TD and fitted Q-iteration have documented divergence examples on linearly realizable problems, and every positive analysis assumes conditions much stronger than realizability.

The construction, sketched in response to a student question: a reward function as complex as a ReLU network, nonzero only in a hidden region of an exponentially large space, with dynamics engineered so that Bellman backups linearize it — the $Q$-function looks simple, but learning it means locating the hidden reward. It works only in high dimension, where random vectors are nearly orthogonal: “you can sort of hide information in very high dimension.” The takeaway is a strict separation — “linear regression is easy in stats, but the equivalent in reinforcement learning from a model-free point of view is already out of reach” — so polynomial-sample RL requires additional special structure beyond a simple function class. What kind? Statistical complexity of the class (Rademacher complexity, covering numbers) suffices for regression but not for RL: TD takes a function, forms its Bellman backup, and fits the same class to it, so what matters is the interplay between the Bellman operator and the function class — the object behind the many learnability conditions proposed since.

Offline RL: coverage, and beating behavior cloning

Offline RL asks: given a historical dataset of states, actions, rewards, and successor states, find the policy with the highest value — but the dataset may contain no information about the optimal policy, so the best you can do is a best effort. The obstacle is distribution shift under partial coverage: real datasets are narrowly concentrated trajectories, rich in information about some policies and silent about others. The two escapes are the ones from the offline lectures: stay close to the behavior policy, or estimate the uncertainty of your predictions and act pessimistically.

For a concrete instantiation — softmax policies from natural policy gradient, linear action-value functions — $C_\pi$ has an analytical form: the expected feature vector under the target policy, measured in the norm of the inverse empirical covariance matrix of the data. The covariance matrix, the familiar object from linear regression, encodes what the dataset knows; the norm measures how far the target policy’s features stick out of it. Notably there is no ratio of visitation distributions over states and actions, as in older concentrability analyses — everything is “projected down to a lower-dimensional feature space”, where coverage can be far better (an identity covariance makes $C_\pi$ small for every policy). The algorithmic side pairs natural policy gradient with a pessimistic variant of TD with target networks, computing confidence intervals in parameter space.

Beyond the linear case there is, again, a huge gap: the deep offline algorithms from class may not converge, so guarantees are proved for “conceptual versions” that aren’t clearly implementable. Zanette’s closing assessment: most RL problems are not worst-case; function approximation makes RL genuinely harder than supervised learning; and theory won’t tune your hyperparameters, but working at the theory–practice intersection — accepting compromises, not topping benchmarks — is how RL becomes something you’d confidently deploy, “backed by some form of guarantees that apply even in a restricted set.”

Check yourself

Three exercises in the lecture’s spirit — reason about the bounds rather than run anything.

Problem G.1 problem-dependent complexity

Zanette’s complexity measure is the variance of the next-state optimal value, $\mathrm{Var}_{s' \sim p(\cdot \mid s,a)}[V^*(s')]$. (a) Show that it is exactly zero for any deterministic MDP. (b) Explain why it is small for a contextual bandit (recommender system) even though the transitions there are highly stochastic. What does each case predict about learning speed?

Show solution

(a) In a deterministic MDP, $s'$ is a fixed function of $(s, a)$: the next-state distribution is a point mass, so $V^*(s')$ is a constant given $(s,a)$ and its variance is zero for every state–action pair. The problem-dependent term in the regret bound vanishes, matching the lecture’s claim that deterministic problems are “essentially a search problem” — the difficulty of estimating stochastic transitions disappears. (b) In a contextual bandit, the next context is drawn independently of your action — transitions are highly stochastic. But the measure is the variance of the next state’s optimal value, not of the next state itself: because your action has no effect on the future (“you only lose with the current customer”), the value of where you land does not vary meaningfully with what you did, so the quantity is small. In both cases the adaptive algorithm’s regret shrinks toward the specialized rate (search-like behavior, or UCB-on-bandits performance) even though the algorithm never computes the measure — it is small analytically on these classes and, evaluated numerically on standard benchmark MDPs, much smaller than the worst-case value prior bounds assumed.

Problem G.2 Hoeffding vs Bernstein bonus

An exploration bonus at a state–action visited $n = 400$ times, in an MDP with horizon $H = 100$ where next-state optimal values range over $[0, H]$ but have variance $\mathrm{Var}[V^*(s')] = 1$. Compare the size of (a) a Hoeffding-style bonus, which must scale with the range, roughly $H \sqrt{1/n}$, against (b) a Bernstein-style bonus, roughly $\sqrt{\mathrm{Var}[V^*(s')]/n} + H/n$. Then explain why the Bernstein bonus cannot be used directly, and what replaces it.

Show solution

(a) Hoeffding: $H\sqrt{1/n} = 100 \cdot \tfrac{1}{20} = 5$. (b) Bernstein: $\sqrt{1/400} + 100/400 = 0.05 + 0.25 = 0.3$ — roughly $17\times$ smaller, and the gap widens with $n$ since the range-dependent part decays as $1/n$ rather than $1/\sqrt{n}$. Smaller bonuses mean less forced exploration on easy problems, which is where the problem-dependent regret bound comes from; the Hoeffding bonus, depending only on the count, explores identically on every MDP and can never yield problem-dependent guarantees. The Bernstein bonus is unusable as written because it contains the variance of $V^*$ under the true dynamics — both unknown, and early in learning you have “essentially no way to guess” them; guessing wrong risks an insufficiently optimistic algorithm that stops exploring and never finds a good policy. The fix: substitute the empirical dynamics and an empirical value estimate, and add correction terms for the estimation error. These corrections decay at a faster rate than the main bonus, so asymptotically the agent behaves as if it had used the true Bernstein bonus; the technical difficulty is bounding them, which requires controlling how error propagates through the MDP from poorly visited states.

Problem G.3 offline coverage coefficient

Offline RL with linear $Q$-functions and 2-dimensional features. After $n$ episodes the empirical feature covariance is $\Sigma = \mathrm{diag}(n, 1)$ — the behavior policy explored almost entirely along the first feature direction. Target policy $A$ has expected feature $\mathbb{E}_A[\phi] = (1, 0)^\top$; target policy $B$ has $\mathbb{E}_B[\phi] = (0, 1)^\top$. Using the coverage measure $C_\pi = \lVert \mathbb{E}_\pi[\phi] \rVert_{\Sigma^{-1}}$, compute both coefficients, say which policy’s value the dataset can certify, and connect the result to the better-than-behavior-cloning guarantee.

Show solution

$\Sigma^{-1} = \mathrm{diag}(1/n, 1)$, and $\lVert v \rVert_{\Sigma^{-1}} = \sqrt{v^\top \Sigma^{-1} v}$. For $A$: $C_A = \sqrt{(1,0)\,\Sigma^{-1}(1,0)^\top} = \sqrt{1/n}$, which shrinks to zero as data accumulates — the confidence interval on $V^A$ tightens and the dataset certifies $A$‘s value. For $B$: $C_B = \sqrt{(0,1)\,\Sigma^{-1}(0,1)^\top} = 1$, independent of $n$ — collecting more data along direction one teaches you nothing about direction two, so the uncertainty about $V^B$ never shrinks. A pessimistic algorithm maximizing the lower bound $V^\pi - C_\pi/\sqrt{n}$ will therefore return $B$ only if its certified value beats $A$‘s, and otherwise correctly refuses $B$ even if a naive fitted-Q estimate makes it look good: “you have to take into account that you’re extremely uncertain about this value.” Note the coefficient involves no state–action visitation ratio — coverage is measured entirely in feature space, which is why a well-conditioned covariance (near identity) gives small $C_\pi$ for every policy. Finally, the behavior policy itself has expected features lying along the data, so its coefficient behaves like $C_A$: its lower bound is tight, and the guarantee $V^{\hat{\pi}} \ge V^{\text{behavior}} - O(1/\sqrt{n})$ follows — the algorithm can only improve on behavior cloning, which is the minimum you should demand of an offline method.