Research map / Learning theory and algorithms / Sample complexity
Optimal Sample Complexity for Average Reward Markov Decision Processes
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 that reduction to a perturbed discounted MDP with a generative model achieves the optimal Õ(|S||A| t_mix ε^-2) sample complexity for uniformly ergodic average-reward MDPs, matching the known lower bound.
Problem
Sample complexity of learning an ε-optimal policy for average reward MDPs under a generative model, where the known upper bound Õ(|S||A|t_mix^2 ε^-2) and lower bound Ω(|S||A|t_mix ε^-2) had a gap of t_mix.
Approach
Reduce the average-reward problem to a discounted MDP with discount 1-γ=Θ(ε/t_mix), and analyze the reward-perturbed model-based planning algorithm with a refined Bernstein/decoupling analysis that yields (1-γ)^-2 dependence and a minimum sample size of only Õ(|S||A|(1-γ)^-1).
Key results
- Algorithm achieves Õ(|S||A| t_mix ε^-2) sample complexity for uniformly ergodic AMDPs, matching the Ω(|S||A| t_mix ε^-2) lower bound up to log factors.
- Discounted-MDP analysis improves the dependence on (1-γ)^-1 from ε^-3 (prior reduction methods) to ε^-2 and needs only Õ(|S||A|(1-γ)^-1) minimum samples.
- Numerical experiments show error slope near -1/2 in n (matching ε^-2) and near 0 slope in t_mix, versus about -1/3 for the prior algorithm.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the improved perturbed model-based planning analysis for the discounted MDP reduction | Average-reward policy learning · Uniformly ergodic AMDP, generative model | sample complexity: |S||A|\tmix\epsilon^{-3} -> |S||A|\tmix \epsilon^{-2} | Helped |
| Use the paper's analysis of perturbed model-based planning under uniform ergodicity | Uniformly ergodic DMDP policy learning · Uniformly ergodic DMDP | sample complexity upper bound: |S||A|(1-\gamma)^{-3}\epsilon^{-2} -> |S||A|\tmix(1-\gamma)^{-2}\epsilon^{-2} | Helped |
| Use the paper's implementation and analysis instead of the prior algorithm | Average-reward policy learning on the hard MDP instance · Hard AMDP instance from [cite] | convergence-rate exponent: near -1/3 -> close to -1/2 | Helped |
| Set sample size proportional to minorization time | Proposed algorithm · Hard AMDP instances with t_minorize in [10,1000] | regression-line slope of average error: near 0 | No clear effect |
Limitations
- Requires a priori knowledge of an upper bound on the uniform mixing time to set the discount factor.
- Relies on uniform ergodicity, which can give conservative bounds when suboptimal policies mix slowly.
- Analysis restricted to finite state and action spaces.
Experimental setup
Datasets: synthetic hard MDP instances from prior work (generative-model samples)
Benchmarks: hard MDP instance family from prior work (numerical experiments)
Metrics: estimation error of average reward log-log slope vs ε^-1 and t_mix
Baselines: Primal-dual π learning Primal-dual SMD Reduction to DMDP (ε^-3 algorithms) Refined Q-learning
Builds on: perturbed model-based planning reduction from average reward to discounted MDP Li et al. variance-reduced/refined analysis of discounted MDPs
Closest papers by meaning
- Finding good policies in average-reward Markov Decision Processes without prior knowledge (NeurIPS 2024 · similarity 0.93)
- Near-Optimal Sample Complexity for MDPs via Anchoring (ICML 2025 · similarity 0.92)
- Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPs (NeurIPS 2024 · similarity 0.92)
- Sample Complexity of Distributionally Robust Average-Reward Reinforcement Learning (NeurIPS 2025 · similarity 0.91)
- Achieving $\tilde{O}(1/\epsilon)$ Sample Complexity for Constrained Markov Decision Process (NeurIPS 2024 · similarity 0.90)
- Optimal Single-Policy Sample Complexity and Transient Coverage for Average-Reward Offline RL (NeurIPS 2025 · similarity 0.89)
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.