Research map / Bandits and online learning / RL theory and MDPs
Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPs
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.
Shows span-based minimax-optimal sample complexity SA·H/ε² for weakly communicating average-reward MDPs and SA·(B+H)/ε² for general multichain MDPs via an improved average-to-discounted reduction under a generative model.
Problem
Sample complexity of learning an ε-optimal policy for average-reward MDPs under a generative model, previously unresolved in terms of the bias span H, and unstudied for general (multichain) MDPs.
Approach
Reduce the average-reward MDP to a discounted MDP with discount chosen from H (or B+H), and sharpen discounted-MDP analysis via a multistep variance Bellman equation that bounds variance by H/(1-γ) instead of 1/(1-γ)², yielding quadratic rather than cubic effective-horizon dependence; introduces a transient time parameter B for multichain MDPs.
Key results
- Weakly communicating average-reward MDPs: Õ(SA·H/ε²) samples suffice via the reduction, matching the minimax lower bound up to log factors.
- General multichain average-reward MDPs: Õ(SA·(B+H)/ε²) samples suffice, with a matching minimax lower bound Ω̃(SA·(B+H)/ε²) up to log factors.
- Discounted MDP sample complexity improved to Õ(SA·H/((1-γ)²ε²)) for weakly communicating MDPs, circumventing the 1/(1-γ)³ lower bound for fixed instances.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the span-based average-to-discounted reduction and variance analysis | Weakly communicating average-reward MDPs · Weakly communicating average-reward MDPs | sample complexity: \widetilde{O}\left(SA\frac{\mathsf{H}}{\varepsilon^3} \right) -> \widetilde{O} \left( \frac{\mathsf{H} SA}{\varepsilon^2 | Helped |
| Include transient time bound \mathsf{B} alongside bias span \mathsf{H} in the reduction | General average-reward MDPs · General average-reward MDPs | sample complexity: span \mathsf{H} alone cannot characterize the sample complexity; \widetilde{O}\left( SA\frac{\mathsf{B} + \mathsf{H}}{\v | Helped |
| Use span-dependent variance bounds for fixed weakly communicating instances | Discounted MDPs · Weakly communicating discounted MDPs | sample complexity: \widetilde{O}\bigl(\frac{SA}{(1-\gamma)^3 \varepsilon^2} \bigr) -> \widetilde{O} \big(\frac{\mathsf{H} SA}{(1-\gamma)^2\ | Helped |
| Account for transient time \mathsf{B} as well as span \mathsf{H} in discounted-MDP analysis | General discounted MDPs · General discounted MDPs | sample complexity: \widetilde{O}\cigl( SA\frac{1}{(1-\gamma)^3\varepsilon^2} \cigr) -> \widetilde{O}\cigl(SA\frac{\mathsf{B} + \mathsf{H}}{ | Helped |
| Set the discounted reduction horizon using only the bias span, omitting transient time | General average-reward MDPs · General average-reward MDPs | sample complexity characterization: null | Hurt |
Surprising findings
- The span H alone cannot characterize sample complexity for general MDPs; a transient time parameter B is necessary.
- Two MDPs with bias span 1 and span T can be indistinguishable with n samples, so H cannot be estimated from samples without knowing it.
Limitations
- Average-to-discounted reduction requires prior knowledge of H (or B+H) for optimal complexity.
- Results are under a generative model, not the online setting.
- Knowledge of the span is necessary in the sense that span-only sample complexity cannot be achieved without an upper bound.
Experimental setup
Metrics: sample complexity span-based minimax optimality gain suboptimality
Baselines: Primal-Dual SMD Policy Mirror Descent Refined Q-Learning Reduction to DMDP with uniform mixing
Builds on: Perturbed empirical model-based planning for discounted MDPs (Li et al. 2020) Average-to-discounted reduction (Wang et al. 2023) Law of total variance for MDPs
Closest papers by meaning
- Near-Optimal Sample Complexity for MDPs via Anchoring (ICML 2025 · similarity 0.94)
- Optimal Sample Complexity for Average Reward Markov Decision Processes (ICLR 2024 · similarity 0.92)
- Optimal Single-Policy Sample Complexity and Transient Coverage for Average-Reward Offline RL (NeurIPS 2025 · similarity 0.91)
- Finding good policies in average-reward Markov Decision Processes without prior knowledge (NeurIPS 2024 · similarity 0.91)
- Optimal Non-Asymptotic Rates of Value Iteration for Average-Reward Markov Decision Processes (ICLR 2025 · similarity 0.90)
- Finite-Time Bounds for Average-Reward Fitted Q-Iteration (NeurIPS 2025 · 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.