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

Joshua Steier

cs.LGMar 1, 2026

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

Authors: Joshua Steier

Abstract

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.

Figures & tables

Panel of Figure 1 — Figure 1: Survey roadmap. The CSO framework (§2) organizes all results. Preliminaries (§3) introduce formal tools. Three pillars (tabular §4, structural measures §5, function approximation §6) feed into applications (§7–§9). The practical toolkit (§14) synthesizes. Reading paths: Practitioners start at §2 and §14, then read domain sections; theorists start at §3, then §4–§6.

	Szepesvári (2010)	Strehl et al. (2009)	This survey (2018–2025)
Venue/Type	Monograph (Morgan & Claypool)	JMLR survey article	TMLR survey (2025)
Scope	Algorithms for RL; primarily tabular and basic function approximation	PAC-MDP framework; finite MDPs; sample complexity	Uniform-PAC across tabular, structural measures, FA, RFE, offline, POMDP
Time window	Pre-2010	Pre-2009	2018–2025
Primary axis	Algorithms and theory	PAC-MDP sample complexity	CSO: Coverage $\times$ Structure $\times$ Objective
Guarantee types	PAC/Regret (primarily tabular)	PAC-MDP bounds for finite state-action spaces	Uniform-PAC, instance-dependent, offline/pessimism, PAC-Bayes
Practitioner tools	Conceptual algorithms	Theoretical foundations	Decision tree; coverage gates; certificates; rate tables

Table 1: Comparison with foundational surveys. We build on Szepesvári’s algorithmic treatment and Strehl et al.’s PAC-MDP framework, adding 2018–2025 results under a unified CSO lens with deployment-oriented tools.

Setting	$\mathsf{Cov}$	$\mathsf{Comp}$	$\mathrm{poly}(H)$	Rate	Section
Tabular online	$1$	$SA$	$H^{3}$	$\tilde{\Theta}(SAH^{3}/\varepsilon^{2})$	§ 4
Tabular BPI	$1$	$\sum\frac{q_{h}}{\Delta^{2}}$	varies	instance-dep.	§ 4
Linear MDP	$1$	$d^{3}$	$H^{4}$	$\tilde{\mathcal{O}}(d^{3}H^{4}/\varepsilon^{2})$	§ 6
Kernel/RKHS	$1$	$d_{\mathrm{eff}}(\lambda)$	$H^{4}$ – $H^{6}$	$\tilde{\mathcal{O}}(d_{\mathrm{eff}}\cdot\mathrm{poly}(H)/\varepsilon^{2})$	§ 6
Low-rank MDP	$1$	$\mathrm{poly}(r)$	varies	$\tilde{\mathcal{O}}(\mathrm{poly}(r,H)/\varepsilon^{2})$	§ 7
Block MDP	$1$	$\mathrm{poly}(m)\cdot A$	varies	$\tilde{\mathcal{O}}(\mathrm{poly}(m)AH^{\cdot}/\varepsilon^{2})$	§ 7

Table 2: CSO coordinates of major results. Each row decomposes a PAC bound into Coverage (

\mathsf{Cov}

), Structure (

\mathsf{Comp}

), and horizon scaling. “Varies” indicates setting-dependent exponents stated in the referenced section. All rates suppress

\log(1/\delta)

and polylogarithmic factors.

Panel of Figure 2 — Figure 2: The CSO space. Every PAC guarantee occupies a point in Coverage $\times$ Structure $\times$ Objective space. Moving along an axis changes one factor in the sample complexity decomposition ( 1 ). Two example results are marked.

Panel of Figure 3 — Figure 3: Structural complexity hierarchy. Each inclusion is strict: moving right trades tighter constants for broader applicability. The capacity parameter replacing $SA$ is shown below each class name.

Measure	Type	Tabular value	Key assumption	Reference
Bellman rank $B$	Value-based	$S$	Realizability	Jiang et al. [19]
Witness rank $W$	Model-based	$S$	Realizable model class	Sun et al. [37]
Bilinear rank $r$	Unified	$S$	Rank- $r$ factorization	Du et al. [9]
BE dimension $d_{\mathrm{BE}}$	Information-theoretic	$SA$	Finite BE dimension	Jin et al. [21]

Table 3: Structural complexity measures compared. All reduce to

S

SA

in the tabular case. The BE dimension is the most general: finite

B

W

, or bilinear rank each imply finite

d_{\mathrm{BE}}

, but not conversely.

Function Approximation in RL

See all 20 papers

May 20, 2026

On the Sample Complexity of Discounted Reinforcement Learning with Optimized Certainty Equivalents

We study risk-sensitive reinforcement learning in finite discounted MDPs, where a generative model of the MDP is assumed to be available. We consider a family or risk measures called the optimized certainty equivalent (OCE), which includes important risk measures such as entropic risk, CVaR, and mean-variance. Our focus is on the sample complexities of learning the optimal state-action value function (value learning) and an optimal policy (policy learning) under recursive OCE. We provide an exact characterization of utility functions

u

for which the corresponding OCE defines an objective that is PAC-learnable. We analyze a simple model-based approach and derive PAC sample complexity bounds. We establish that whenever

u

does not have full domain

\text{dom}(u)\neq \mathbb{R}

, the corresponding problem is not PAC-learnable. Finally, we establish corresponding lower bounds for both value and policy learning, demonstrating tightness in the size

SA

of state-action space, and for a more restricted class of utilities, we derive lower bounds that makes the dependence on the effective horizon

\frac{1}{1-γ}

explicit. Specifically, for

\text{CVaR}_τ

we show that the correct dependence on

τ

\frac{1}{τ^2}

, thus improving by a factor of

\frac{1}τ

over state-of-the-art although our bound has a suboptimal dependence on

\frac{1}{1-γ}

Oliver Mortensen, Mohammad Sadegh Talebi

Department of Computer Science, University of Copenhagen.

Reinforcement Learning Risk-Sensitive RL Sample-Efficient RL Conditional Value-at-Risk

Ask PDF

May 23, 2026

Reinforcement Learning for Reachability: Guaranteeing Asymptotic Optimality

Reinforcement learning (RL) for reachability specifications is fundamental in sequential decision-making, yet theoretical guarantees remain less explored. A recent work achieves asymptotic convergence to optimal policies. However, this approach provides limited insight into convergence dynamics. In this work, we present an alternative approach that provides deeper theoretical insights into convergence. Our approach builds on PAC learning with assumptions. PAC learning guarantees near-optimal policies with high confidence in finite time but requires knowing internal MDP parameters like minimum transition probability. We argue that while these parameters are unknown in RL, they can be iteratively refined and estimated with increasing accuracy. By iteratively satisfying PAC conditions, we show that exact optimality can be achieved in the limit. Empirical evaluations on standard benchmarks validate our theoretical insights into convergence dynamics.

Amogh Palasamudram, Jakub Svoboda, Suguman Bansal +1

Georgia Institute of Technology, USA · Institute of Science and Technology, Austria · Dartmouth College, USA

Markov Decision Processes Reinforcement Learning

Ask PDF

Jun 12, 2026

Lyapunov-Based Sample Complexity Analysis for Weakly-Coupled MDPs

We study the sample complexity of learning in average-reward weakly-coupled Markov decision processes (WCMDPs) and Restless Bandits (RBs) under a generative model. Naive reduction to a tabular MDP leads to high complexity bounds as the state-action space is exponentially large in the number of arms

N

. By exploiting the weakly coupled structure, we show that near-optimal policies can be learned with sample and computational complexities that are polynomial in

N

. Specifically, we analyze the plug-in approach, which applies an efficient planning algorithm to an empirical model estimated from data. For fully heterogeneous WCMDPs, we establish the first finite-sample PAC guarantee with polynomial complexity and an

O(1/\sqrt{N})

optimality gap. For homogeneous RBs, we further prove that a smaller optimality gap is achievable under mild structural assumptions. A primary technical contribution of our work is a novel Lyapunov-based analysis framework. Unlike classical approaches that rely on the difficult-to-control bias function, our framework uses an explicitly constructed Lyapunov function along with a drift transfer technique between the true and empirical models. A key step of independent interest in our framework is a fine-grained perturbation analysis for the underlying linear programming (LP) relaxation, which provides a general tool for analyzing LP-based policies and weakly-coupled systems.

Tianhao Wu, Matthew Zurek, Weina Wang +1

Department of Industrial and Systems Engineering, University of Wisconsin-Madison · Department of Computer Sciences, University of Wisconsin-Madison · Computer Science Department, Carnegie Mellon University

Multi-Armed Bandits Robust Markov Decision Processes Markov Decision Processes Reinforcement Learning Average-Reward RL Markov Models+2

Ask PDF

Abstract

Function Approximation in RL

Explore similar work

On the Sample Complexity of Discounted Reinforcement Learning with Optimized Certainty Equivalents

Reinforcement Learning for Reachability: Guaranteeing Asymptotic Optimality

Lyapunov-Based Sample Complexity Analysis for Weakly-Coupled MDPs