Guest Lecture: Andrea Zanette on Statistical Foundations of RL

What this lecture covers

This guest lecture steps back from the practical algorithms covered throughout the course to ask what theory can say about reinforcement learning: whether algorithms converge, how many samples they need, and what is fundamentally impossible. It is organized around three questions: which RL problems are statistically easy versus hard, why adding function approximation makes RL provably harder than supervised learning even in simple linear cases, and what performance guarantees look like for offline RL.

After watching, you can explain what regret measures and why some tabular RL problems are easier than the worst case, describe the exponential sample complexity lower bound for linear function approximation in RL, and explain how offline RL guarantees trade off estimated policy value against a data-coverage-based uncertainty penalty.

Key ideas

• Practical obstacles to real-world RL: stability, data efficiency, generalization across tasks, and computational cost all limit how much theory covers what practitioners actually run, since basic deep RL schemes like TD learning with experience replay and target networks are not generally guaranteed to converge.
• Regret: the standard measure of learning speed is the cumulative gap between the optimal policy's value and the value of the policies an agent actually plays over training, and good algorithms minimize this regret.
• Problem-dependent complexity: rather than only proving worst-case regret bounds for all tabular MDPs, it's possible to define a complexity measure based on the variance of the next-state optimal value function, so that easier problem instances (such as bandits with weak memory, deterministic problems, or locally-moving state spaces) provably admit faster learning.
• Bernstein-style exploration bonuses: achieving problem-dependent bounds in practice requires exploration bonuses that approximate the ideal Bernstein-based bonus using empirical dynamics and value estimates, with correction terms that decay quickly to account for early inaccuracy.
• Function approximation makes RL provably hard: even when the action-value function has an exact linear representation (a setting where supervised linear regression would be easy), the worst-case number of samples needed to learn or find a good policy can be exponential in the feature dimension, a limitation that holds for any algorithm.
• RL vs. supervised learning: the core difference is that supervised learning predicts one step ahead, while RL must predict value over many time steps; this compounding is what creates the exponential separation, even under an identical linear realizability assumption.
• Offline RL guarantees as a value-uncertainty tradeoff: a good offline RL algorithm should return the policy with the best lower bound on value, balancing estimated value against an uncertainty term shaped by a coverage (concentrability) coefficient that reflects how well the data set's policy distribution covers the target policy.
• Guarantee sanity check: a correctly designed offline algorithm should provably do at least as well as behavioral cloning of the data-generating policy, since that policy's coverage coefficient is small by construction.

Walkthrough

Motivating a theory of RL (0:00)

The lecture opens by listing the practical barriers to deploying RL in the real world, stability, data efficiency, generalization, and computational cost, and argues that many foundational algorithms taught in the course (value iteration, policy iteration, UCB exploration, REINFORCE) originated from theoretical guarantees. It frames the talk's goal as understanding what guarantees are achievable: convergence, sample complexity, and computational complexity, while acknowledging that most deep RL algorithms currently lack such guarantees.

Easy and hard exploration problems (6:03)

Focusing on tabular (small state-action space) problems, the lecture defines regret as the area under the curve of suboptimality gaps over episodes, and reviews the history of worst-case regret bounds for finite MDPs. It then introduces a problem-dependent complexity measure, based on the variance of the next-state optimal value function, that is small for problems with weak memory (like contextual bandits used in recommendation), deterministic dynamics, or locally constrained movement (like Mountain Car). An algorithm built around this measure matches the best worst-case (minimax) performance while automatically achieving much better performance on these easier problem subclasses, without needing to know in advance which subclass it faces. Achieving this in practice requires approximating an ideal Bernstein-style exploration bonus with empirical estimates and fast-decaying correction terms.

Why function approximation makes RL fundamentally harder (22:21)

Moving beyond tabular problems to function approximation, the settings used throughout the rest of the course, the lecture asks whether RL is fundamentally harder than supervised learning. Using an offline RL setup, it shows that even when the action-value function has an exact linear representation with a known feature extractor, a case where linear regression would solve an equivalent one-step prediction problem in polynomial samples, any algorithm can require a number of samples exponential in the feature dimension to find a good policy. The key distinction is that supervised learning predicts one step ahead, while RL must predict value across many time steps, and this multi-step compounding is what creates the hardness, backed by a hard example where dynamics are engineered to linearize an otherwise very complex, sparse reward function in high dimensions. This hardness is information-theoretic: it applies to every possible algorithm, not just current practical methods.

Guarantees for offline reinforcement learning (37:45)

The lecture turns to the offline RL setting covered earlier in the course: given a fixed historical data set, find the best possible policy without further data collection. The central challenge is distribution shift, since a data set generated by a narrow policy may say little about very different candidate policies. A good offline algorithm's guarantee takes the form of maximizing a high-probability lower bound that trades off a policy's estimated value against a coverage (concentrability) coefficient reflecting how well the data covers that policy, expressed through covariance-matrix-style quantities analogous to linear regression rather than raw state-action visitation ratios. As a sanity check, this guarantee implies the algorithm should do at least as well as simply cloning the data-generating policy, since that policy always has a small coverage coefficient. The lecture notes this style of guarantee currently only holds for linear function approximation; extending it to the richer function classes used in practice remains an open problem, since practical algorithms in that setting often lack convergence guarantees altogether.

Before you watch

• Review the exploration algorithms (UCB-style bonuses, tabular value iteration) and offline RL algorithms (CQL and similar) covered earlier in the course, since this lecture builds directly on both.
• Basic familiarity with linear regression and covariance matrices from statistics will help with the function approximation and offline RL sections.

Check your understanding

1. What does regret measure, and why is a problem-dependent complexity bound more informative than a single worst-case bound?
2. Why does weak memory (as in contextual bandits) make a reinforcement learning problem easier to explore?
3. Why can a reinforcement learning problem with an exactly linear action-value function still require exponentially many samples, unlike the equivalent one-step linear regression problem?
4. What tradeoff does an offline RL guarantee balance, and why should a well-designed offline algorithm never do worse than behavioral cloning of the data-collecting policy?