mlsanityData to 7 Oct 2026

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

arXiv 2603.01309 ↗First posted 1 Mar 2026cs.LG stat.MLcited by 0

Not on the map. Why?

Abstract (arXiv)

When data is scarce or mistakes are costly, average-case metrics fall short. What a practitioner needs is a guarantee: with probability at least 1-δ, the learned policy is varepsilon-close to optimal after N episodes. This is the PAC promise, and between 2018 and 2025 the RL theory community made striking progress on when such promises can be kept. We survey that progress. Our organizing tool is the Coverage-Structure-Objective (CSO) framework, proposed here, which decomposes nearly every PAC sample complexity result into three factors: coverage (how data were obtained), structure (intrinsic MDP or function-class complexity), and objective (what the learner must deliver). CSO is not a theorem but an interpretive template that identifies bottlenecks and makes cross-setting comparison immediate. The technical core covers tight tabular baselines and the uniform-PAC bridge to regret; structural complexity measures (Bellman rank, witness rank, Bellman-Eluder dimension) governing learnability with function approximation; results for linear, kernel/NTK, and low-rank models; reward-free exploration as upfront coverage investment; and pessimistic offline RL where inherited coverage is the binding constraint. We provide practitioner tools: rate lookup tables indexed by CSO coordinates, Bellman residual diagnostics, coverage estimation with deployment gates, and per-episode policy certificates. A final section catalogs open problems, separating near-term targets from frontier questions where coverage, structure, and computation tangle in ways current theory cannot resolve.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 21 of its 41 references that are in the map. First posted on arXiv 1 Mar 2026.

Builds on

21 of 41 references.

References · 21

  1. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  2. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  3. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  4. 2020Is Pessimism Provably Efficient for Offline RL?cited by 362
  5. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  6. 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 232
  7. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
  8. 2020Reward-Free Exploration for Reinforcement Learningcited by 177
  9. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 176
  10. 2019Provably efficient RL with Rich Observations via Latent State Decodingcited by 169
  11. 2020Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisitedcited by 104
  12. 2018Policy Certificates: Towards Accountable Reinforcement Learningcited by 81
9 more
  1. 2020Adaptive Reward-Free Explorationcited by 77
  2. 2018On Oracle-Efficient PAC RL with Rich Observationscited by 71
  3. 2020PAC-Bayes Analysis Beyond the Usual Boundscited by 63
  4. 2021Causal Inference Under Unmeasured Confounding With Negative Controls: A Minimax Learning Approachcited by 43
  5. 2021Beyond No Regret: Instance-Dependent PAC Reinforcement Learningcited by 41
  6. 2023Reinforcement Learning in Low-Rank MDPs with Density Featurescited by 17
  7. 2021Agnostic Reinforcement Learning with Low-Rank MDPs and Rich Observationscited by 13
  8. 2022PAC-Bayes Bounds for Bandit Problems: A Survey and Experimental Comparisoncited by 7
  9. 2024Deep Exploration with PAC-Bayescited by 4

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2022The Role of Coverage in Online Reinforcement Learning
  2. 2025Optimal Single-Policy Sample Complexity and Transient Coverage for Average-Reward Offline RL
  3. 2024On Sample-Efficient Offline Reinforcement Learning: Data Diversity, Posterior Sampling, and Beyond
  4. 2023Offline Reinforcement Learning with Additional Covering Distributions
  5. 2021Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximation
  6. 2023What can online reinforcement learning with function approximation benefit from general coverage conditions?
  7. 2023Achieving the Asymptotically Optimal Sample Complexity of Offline Reinforcement Learning: A DRO-Based Approach
  8. 2022Settling the Sample Complexity of Model-Based Offline Reinforcement Learning