Research map / Reinforcement learning / MDPs and planning
Optimal Single-Policy Sample Complexity and Transient Coverage for Average-Reward Offline RL
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Develops a pessimistic discounted value iteration with quantile clipping and an empirical-span penalty to obtain the first fully single-policy sample complexity bound (bias span and policy hitting radius) for average-reward offline RL on weakly communicating MDPs, with matching lower bounds.
Problem
Offline average-reward RL in tabular MDPs under single-policy coverage: existing guarantees depend on uniform complexity measures (uniform mixing time, uniform span) and require prior parameter knowledge, and do not handle general weakly communicating MDPs.
Approach
Pessimistic discounted value iteration with a very large discount factor (effective horizon equal to dataset size), a Bernstein-style penalty using the empirical variance and span, and quantile clipping that makes the span-based penalty monotone and contractive, so that guarantees depend only on the target policy's bias span and a new policy hitting radius.
Key results
- Main theorem: with probability at least 1-5δ, the output policy satisfies ρ* − ρ^π̂ ≤ sqrt(C1 S (span(h*)+1) α / m) under n(s,π*(s)) ≥ m μ*(s) + α(C2 D)^2 + 4 coverage.
- Lower bound: any algorithm suffers gain suboptimality c3 sqrt(TS/m) on hard instances, matching the m-dependence of the upper bound up to log factors.
- Hard instance shows coverage of only the target stationary distribution is insufficient: suboptimality above 1/2 with constant probability even with arbitrarily large m.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add quantile clipping to the empirical-span-based penalty | Pessimistic value iteration · Average-reward offline RL | suboptimality guarantee | Helped |
| replace the horizon-dependent penalty term with a span-based term and add quantile clipping | Pessimistic value iteration · Average-reward offline RL | constant-shift property | Helped |
| use a span-based penalty without quantile clipping | Pessimistic value iteration · Average-reward offline RL | monotonicity | Hurt |
| add coverage for target-policy state-action pairs at transient states | Offline average-reward RL with single-policy complexity guarantees · Average-reward offline RL | suboptimality | Helped |
| restrict coverage to the target policy's stationary distribution | Offline average-reward RL with single-policy complexity guarantees · Average-reward offline RL | suboptimality | Hurt |
Surprising findings
- Learning a near-optimal policy is impossible with coverage of only the target policy's stationary distribution, even with arbitrarily large data.
- Only a bounded amount of data from transient state-action pairs of the target policy suffices for vanishing suboptimality.
Limitations
- Tabular setting only; dependence on S is not avoided and function approximation is left open.
- Requires transient-state coverage of about Õ(D^2) samples per target-policy state-action pair.
- Requires the target policy to be unichain (mild assumption).
Experimental setup
Metrics: gain suboptimality sample complexity bound
Baselines: uniform-mixing-time offline average-reward LP methods (unichain tabular) constant-gain offline average-reward methods linear MDP primal-dual offline average-reward methods
Builds on: pessimistic value iteration empirical Bernstein inequality discounted reduction
Closest papers by meaning
- A Primal-Dual Algorithm for Offline Constrained Reinforcement Learning with Linear MDPs (ICML 2024 · similarity 0.92)
- Worst-Case Offline Reinforcement Learning with Arbitrary Data Support (NeurIPS 2024 · similarity 0.91)
- Sample Complexity of Distributionally Robust Average-Reward Reinforcement Learning (NeurIPS 2025 · similarity 0.91)
- Offline-Online Reinforcement Learning for Linear Mixture MDPs (NeurIPS 2026 · similarity 0.91)
- Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPs (NeurIPS 2024 · similarity 0.91)
- On the Complexity of Offline Reinforcement Learning with Q*-Approximation and Partial Coverage (NeurIPS 2026 · similarity 0.90)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.