PAC Guarantees for Reinforcement Learning: Sample Complexity, Coverage, and Structure

This paper surveys recent advances in PAC guarantees for reinforcement learning (2018–2025) by introducing the Coverage-Structure-Objective (CSO) framework to unify sample complexity results across diverse settings, while offering practical tools and cataloging open problems to bridge theoretical bounds with real-world deployment.

The Gist

Imagine you are teaching a robot to navigate a maze. In the world of Reinforcement Learning (RL), the robot learns by trying things, making mistakes, and getting rewards.

Usually, scientists measure how well the robot learns by looking at its average performance over a long time. They say, "After 10,000 tries, the robot is pretty good on average."

But what if you can't afford 10,000 mistakes?

• In a hospital: You can't let a robot doctor try a dangerous treatment on 100 patients just to see if it works.
• In a self-driving car: You can't wait for the car to crash a few times to learn how to stop at a red light.

You need a guarantee. You need to know: "If I run this algorithm for 500 tries, I can be 99% sure the robot will be safe and effective immediately."

This paper is a massive guidebook for that kind of guarantee. It covers the years 2018 to 2025, a time when researchers made huge leaps in figuring out exactly how to give these guarantees.

Here is the paper explained through a simple story and some analogies.

---

The Big Idea: The "CSO" Framework

The authors realized that every guarantee in this field boils down to three things. They call this the CSO Framework (Coverage, Structure, Objective). Think of it like buying a house:

1. Coverage (The Neighborhood):

   • What it is: How much of the "map" does your data cover?
   • The Analogy: Imagine you are trying to learn the layout of a city.
     • Online Learning: You have a car and can drive anywhere. You create your own map as you go. (Great coverage).
     • Offline Learning: You are stuck with a single, old map drawn by someone else. If that map only shows the downtown area, but you need to drive to the suburbs, you are in trouble. The "old map" has poor coverage.
   • The Lesson: If your data doesn't cover the important parts of the problem, no amount of smart math will save you.

2. Structure (The Complexity of the Puzzle):

   • What it is: How hard is the actual problem? Is it a simple grid or a chaotic jungle?
   • The Analogy:
     • Tabular (Simple): The maze is a small grid. You can just memorize every square. Easy.
     • Function Approximation (Complex): The maze is infinite. You can't memorize it. You need a "rule" or a "pattern" (like "always turn left at the red wall") to generalize.
   • The Lesson: If the problem is too complex for your "rule" (your math model), the guarantee fails.

3. Objective (The Goal):

   • What it is: What exactly are you trying to achieve?
   • The Analogy:
     • Control: "Find the perfect path to the exit." (Hard).
     • Evaluation: "Just tell me how long the path would take if I went this way." (Easier).
   • The Lesson: Asking for the perfect path requires more data than just estimating a path.

The Paper's Magic: The authors show that you can predict how much data you need by multiplying these three factors together. If your Coverage is bad, you need infinite data. If your Structure is too complex, you need infinite data. If your Objective is too hard, you need infinite data.

---

Key Concepts Made Simple

1. The "Pessimist" vs. The "Optimist"

• The Optimist (Online Learning): When the robot is learning live, it says, "I'm not sure what's behind that door, but maybe there's a treasure! Let's go check!" It tries new things to learn.
• The Pessimist (Offline Learning): When the robot is learning from old data, it says, "I've never seen this door in the old maps. I'm going to assume it leads to a pit of lava."
  • Why? Because if it guesses wrong and the door is actually safe, it might miss a great opportunity. But if it guesses wrong and the door is a pit, it's a disaster. So, the "Pessimist" only trusts what it has seen clearly.

2. The "Reward-Free" Explorer

Imagine you are training a robot arm to do any task you might ask it later. You don't know yet if you'll need it to stack blocks, paint a wall, or cook an egg.

• The Strategy: The robot spends time exploring the whole room without any specific goal. It builds a super-detailed 3D map of everything.
• The Payoff: Later, when you say "Paint the wall," the robot doesn't need to explore again. It already has the map. It just needs to pick the right brush.
• The Paper's Insight: This costs more data upfront (exploring the whole room), but it saves you time and money if you have many different tasks later.

3. The "Certificate" (The Safety Badge)

In the past, you had to wait until the robot finished training to see if it was good.

• The New Tool: The paper suggests giving the robot a Certificate after every single try.
• The Analogy: It's like a teacher grading a student's homework as they do it. "Okay, you've done 10 problems. Based on these, I can guarantee you are 95% ready for the test."
• Why it matters: If the certificate says "Not ready yet," you stop. You don't deploy the robot. You collect more data. It prevents you from launching a bad policy.

---

The "Gotchas" (Where things go wrong)

The paper warns practitioners about three traps:

1. The "Garbage In, Garbage Out" Trap: You can have the smartest math in the world, but if your data (the old map) doesn't cover the area you care about, the robot will fail. The paper gives tools to check if your data is "good enough" before you start.
2. The "Wrong Map" Trap: You might think the world is a simple grid (Linear), but it's actually a chaotic jungle (Non-linear). If you use a simple map for a complex world, the robot will be confidently wrong. The paper suggests tests to check if your "map" fits the "territory."
3. The "Hidden Bias" Trap: If your data comes from a specific type of doctor or driver, the robot might learn their bad habits. The paper discusses how to spot these hidden biases.

---

The Takeaway for Everyone

This paper is a manual for safety.

It tells us that in high-stakes fields (medicine, driving, finance), we can't just say "it works on average." We need to say, "We are 99% sure this works right now."

To do that, you need to check three boxes:

1. Do you have enough data covering the right places? (Coverage)
2. Is your math model simple enough to be true, but complex enough to be useful? (Structure)
3. Are you asking for the right thing? (Objective)

If you check these boxes, you get a guarantee. If you don't, the paper gives you a checklist of tools (like "coverage gates" and "residual tests") to tell you when to stop and collect more data, rather than risking a failure.

In short: It turns Reinforcement Learning from a "black box" of trial-and-error into a transparent, auditable process where you know exactly how safe your robot is before you let it loose.

Technical Summary

1. Problem Statement

Reinforcement Learning (RL) research has traditionally relied on regret (average-case performance over time) as the primary metric. However, in high-stakes domains (e.g., healthcare, autonomous driving, industrial control), average-case metrics are insufficient. Practitioners require fixed-confidence guarantees: assurances that with probability at least $1-\delta$, a learned policy is $\epsilon$-close to optimal after a specific number of episodes $N$.

The challenge lies in the vast diversity of RL settings (tabular vs. continuous, online vs. offline, reward-free vs. standard) and the lack of a unified framework to compare sample complexity bounds across them. Existing literature often uses incompatible notation and assumptions, making it difficult to determine which theoretical guarantees apply to a specific practical problem.

2. Methodology: The CSO Framework

The core methodological contribution of this survey is the introduction of the Coverage-Structure-Objective (CSO) framework. This is not a new theorem but an interpretive template that decomposes nearly every PAC sample complexity bound in the literature (2018–2025) into three multiplicative factors:

$$N(\epsilon, \delta) \approx \underbrace{\text{Cov}}_{\text{Coverage}} \times \underbrace{\text{Comp}}_{\text{Structure}} \times \underbrace{\text{poly}(H) \cdot \epsilon^{-2} \cdot \log(1/\delta)}_{\text{Objective/Stats}}$$

• Coverage (Cov): Reflects how data is obtained.
  • Online/Generative: $Cov = 1$ (agent creates its own coverage).
  • Offline: $Cov = \text{poly}(C^*)$, where $C^*$ is the concentrability coefficient (mismatch between behavior and optimal policies).
  • Reward-Free: $Cov = S$ (or similar), representing an upfront investment to cover all possible future rewards.
• Structure (Comp): Measures the intrinsic complexity of the MDP or function class.
  • Tabular: $Comp = SA$ (number of state-action pairs).
  • Linear/Kernel/Low-Rank: $Comp = \text{poly}(d)$, $d_{eff}(\lambda)$, or $r$ (feature dimension, effective dimension, or rank).
  • Complexity Measures: Includes Bellman Rank, Witness Rank, and Bellman-Eluder (BE) dimension.
• Objective (Obj): Specifies the learning goal.
  • Standard $(\epsilon, \delta)$-PAC control.
  • Uniform-PAC (guarantees hold for all $\epsilon$ simultaneously, implying regret bounds).
  • Instance-dependent identification (gap-weighted rates).
  • Off-policy evaluation (OPE).

The survey uses this framework to organize results, identify bottlenecks (e.g., when coverage dominates structure in offline RL), and provide a "lookup table" for practitioners.

3. Key Contributions

A. Unified Technical Synthesis

The paper synthesizes results from 2018–2025 across disparate settings:

• Tabular Baselines: Confirms the minimax rate of $\tilde{\Theta}(SAH^3/\epsilon^2)$ and the bridge between Uniform-PAC and regret.
• Structural Complexity: Systematically compares Bellman Rank, Witness Rank, and Bellman-Eluder dimension, establishing a strict hierarchy where BE dimension is the most general but least precise.
• Function Approximation: Analyzes Linear MDPs, Kernel/RKHS models, and Neural Tangent Kernel (NTK) regimes, highlighting how estimation errors compound across the horizon (e.g., $H^4$ for linear vs. $H^3$ for tabular).
• Reward-Free Exploration (RFE): Formalizes the trade-off where an upfront exploration cost (factor of $S$) amortizes across multiple downstream tasks.
• Offline RL: Demonstrates that coverage ($C^*$) is often the binding constraint, rendering structural simplicity irrelevant if data support is poor.

B. Practical Toolkit

The survey moves beyond theory to provide actionable tools for applied researchers:

• Bellman Residual Diagnostics (Algorithm 1): A procedure to test for realizability and Bellman completeness before invoking theoretical bounds. It involves fitting value functions via ridge regression and checking if residuals grow with the horizon.
• Coverage Estimation & Deployment Gates (Algorithm 2): Methods to estimate the concentrability coefficient $C^*$ using density ratios and ridge leverage scores. It defines thresholds (e.g., Effective Sample Size > 200) to decide whether to deploy an offline policy.
• Policy Certificates: Data-dependent, per-episode bounds on suboptimality that allow for real-time monitoring and safe deployment.

C. Open Problems Catalog

The paper categorizes open problems into "near-term" (solvable with current tools) and "frontier" (requiring new ideas):

• Near-term: Verifiable Uniform-PAC for kernel classes, instance-dependent identification with function approximation, and scalable coverage estimation.
• Frontier: Agnostic low-rank learning (handling misspecification), offline RL under simultaneous misspecification and poor coverage, and information-theoretic lower bounds for kernel RL.

4. Key Results and Findings

• The Hierarchy of Complexity: The paper establishes that while Tabular $\subset$ Linear $\subset$ Low-Rank $\subset$ Bilinear $\subset$ Finite BE Dimension, moving up this hierarchy trades tighter constants for broader applicability.
• The Horizon Exponent Problem: In function approximation, the sample complexity horizon exponent often increases (e.g., from $H^3$ in tabular to $H^4$ in linear MDPs) due to correlated estimation errors across features. The optimal exponent for kernel/NTK settings remains an open question ($H^4$ to $H^6$).
• Coverage is King in Offline RL: The survey emphasizes that in offline settings, no amount of structural simplicity (small $d$) can compensate for poor coverage (large $C^*$). If $C^*$ is large, guarantees become vacuous regardless of the algorithm.
• Uniform-PAC Bridge: The paper reinforces that Uniform-PAC is a stronger condition than single-$\epsilon$ PAC and serves as a direct translation device to derive high-probability regret bounds.
• Misspecification Risks: Theoretical bounds for linear/kernel methods are only valid if the function class is realizable and Bellman-complete. The paper provides diagnostics to detect when these assumptions fail, preventing the deployment of confidently wrong policies.

5. Significance

This survey is significant for several reasons:

1. Bridging Theory and Practice: It directly addresses the "theory-practice gap" by providing decision trees, diagnostic algorithms, and deployment gates, making abstract PAC bounds actionable for engineers.
2. Standardization: By introducing the CSO framework, it creates a common language for comparing results across different RL subfields (e.g., comparing offline linear RL with reward-free tabular RL).
3. Safety-Critical Focus: It shifts the focus from average-case regret to fixed-confidence guarantees, which is essential for safety-critical applications where occasional failures are unacceptable.
4. Roadmap for Future Research: By clearly delineating what is "settled" (tabular, linear online) versus what is "frontier" (agnostic low-rank, kernel lower bounds), it guides the research community toward the most impactful open problems.

In summary, Steier's paper serves as both a comprehensive technical reference for the state of PAC RL theory (2018–2025) and a practical manual for applying these guarantees safely and effectively in real-world systems.