Research map / Reinforcement learning / MDPs and planning
Sample Complexity of Distributionally Robust Average-Reward Reinforcement Learning
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.
Proposes two generative-model algorithms (reduction to DR discounted MDP with calibrated discount, and anchored DR average-reward MDP) for distributionally robust average-reward RL, achieving O~(|S||A| t_mix^2 eps^-2) sample complexity under KL and f_k uncertainty sets with small radius.
Problem
Finite-sample sample complexity of distributionally robust average-reward reinforcement learning in the tabular setting, where the nominal MDP is uniformly ergodic and the uncertainty set is defined by KL or f_k divergence.
Approach
Reduce DR average-reward MDP learning to a DR discounted MDP with discount gamma = 1 - n^{-1/2}, or anchor the uncertainty set by mixing each kernel with a fixed anchoring state (weight xi = 1/sqrt(n)), so that all kernels in the uncertainty set remain uniformly ergodic and the bias-variance trade-off yields near-optimal rates without knowing the mixing time.
Key results
- Both algorithms achieve sample complexity O~(|S||A| t_mix^2 eps^-2) for the optimal robust average reward and policy under KL and f_k uncertainty sets with small radius.
- Reduction-based DR-DMDP achieves (1-gamma)^-2 dependence on effective horizon, improving on prior (1-gamma)^-4 DR-DMDP bounds.
- Numerical experiments on a hard MDP instance show empirical error decaying at rate n^{-1/2} for both algorithms under KL and chi-square uncertainty.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Reduce DR-AMDP to DR-DMDP using calibrated discount γ = 1-1/√n | DR-AMDP learning · DR-AMDP, KL and f_k uncertainty | sample complexity: \widetilde O ( |\mathbf{S}||\mathbf{A}|\tmin^2\mathfrak{p}_\wedge^{-1}\varepsilon^{-2}) | Helped |
| Use the anchoring state with strength ξ = 1/√n instead of the reduction approach | DR-AMDP learning · DR-AMDP, KL and f_k uncertainty | sample complexity: \widetilde O ( |\mathbf{S}||\mathbf{A}|\tmin^2\mathfrak{p}_\wedge^{-1}\varepsilon^{-2}) | No clear effect |
| Use the proposed reduction algorithm | DR-AMDP learning on the Hard MDP · Hard MDP, KL and χ² uncertainty | convergence rate: -1/2 | Helped |
| Use the proposed anchored algorithm | DR-AMDP learning on the Hard MDP · Hard MDP, KL and χ² uncertainty | convergence rate: -1/2 | Helped |
Limitations
- Results require uniform ergodicity of the nominal MDP and a small uncertainty radius delta bounded by minimum support and m_vee.
- Analysis restricted to generative model and SA-rectangular KL and f_k uncertainty sets.
- Extension to weakly communicating or multichain MDPs and other uncertainty sets (l_p, Wasserstein) left open.
Experimental setup
Datasets: synthetic hard MDP instance
Benchmarks: Hard MDP family (two-state instance)
Metrics: l-infinity error of average-reward estimate log-log regression slope
Baselines: Hard MDP lower bound instance
Builds on: robust MDP framework DR-DMDP sample complexity analysis anchored value iteration for MDPs
Closest papers by meaning
- Finite-Sample Analysis of Policy Evaluation for Robust Average Reward Reinforcement Learning (NeurIPS 2025 · similarity 0.93)
- Near-Optimal Distributionally Robust Reinforcement Learning with General $L_p$ Norms (NeurIPS 2024 · similarity 0.93)
- Optimal Sample Complexity for Average Reward Markov Decision Processes (ICLR 2024 · similarity 0.91)
- A Reduction Framework for Distributionally Robust Reinforcement Learning under Average Reward (ICML 2025 · similarity 0.91)
- Optimal Single-Policy Sample Complexity and Transient Coverage for Average-Reward Offline RL (NeurIPS 2025 · similarity 0.91)
- Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithms (NeurIPS 2024 · similarity 0.91)
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.