Research map / Reinforcement learning / MDPs and planning
A Reduction Framework for Distributionally Robust Reinforcement Learning under Average Reward
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.
Reduces distributionally robust average-reward MDPs to robust discounted MDPs via a specific discount factor γ = 1 − ε/H, yielding a model-based algorithm with near-optimal sample complexity and a scalable linear-FA robust natural actor-critic.
Problem
Robust reinforcement learning under the average reward criterion with (s,a)-rectangular uncertainty sets is understudied, with no finite-sample guarantees and difficulty scaling to function approximation.
Approach
Shows that a robust discounted MDP with discount factor 1 − ε/H (H = robust optimal bias span) yields an O(ε)-optimal policy for the robust average-reward problem, so any robust discounted algorithm (model-based or function-approximation based) can be reused for average reward.
Key results
- Sample complexity of Algorithm 1 is roughly Õ(SAH²/ε²) for TV and χ² uncertainty sets, near-optimal in S, A, ε.
- Reduction with γ = 1 − ε/H gives robust average reward within the prescribed ε-accuracy on the Garnet problem.
- Robust NAC with linear function approximation achieves Õ(H²ε⁻³) total sample complexity, with convergence shown on Walker2d-v3 and Hopper-v3.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the reduction discount factor γ := 1−ϵ/H to optimize the robust discounted problem | Robust AMDPs · Robust average reward | policy optimality: gπ∗P − gˆπγP ≤ (8 + 5ϵγ/H)ϵ | Helped |
| Use the model-based reduction algorithm with TV uncertainty | Robust AMDPs · Total variation uncertainty | sample complexity: ˜O\left(\frac{SAH^2}{ϵ^2}\right) | Helped |
| Use the model-based reduction algorithm with χ2 divergence uncertainty | Robust AMDPs · χ2 divergence uncertainty | sample complexity: ˜O\left(\frac{SAH^2}{ϵ^2}\right) | Helped |
| Use the reduction framework with linear function approximation | Robust Natural Actor-Critic · Robust average reward | sample complexity: ˜O(H^2ϵ^{-3}) | Helped |
| Increase the reduction discount factor | Reduction framework · Walker2d-v3 and Hopper-v3 | average reward | Helped |
| Increase the dataset size | Model-based reduction algorithm · Garnet | robust average reward | Helped |
| Use the reduction method instead of robust value iteration or robust relative value iteration | Robust AMDP optimization · Garnet | robust average reward | Helped |
Limitations
- TV/CS sample complexity is worse than the optimal lower bound by a dependence on H; the paper attributes this to loose robust discounted bounds.
- H is assumed known; practical MuJoCo experiments use a diameter-based upper bound instead.
- Analysis is in the generative model setting; offline and online settings are not analyzed directly.
Experimental setup
Datasets: Garnet MDP (synthetic, 20 states, 8 actions) MuJoCo Walker2d-v3 MuJoCo Hopper-v3
Benchmarks: Garnet problem Walker2d-v3 (perturbed) Hopper-v3 (perturbed)
Metrics: robust average reward sample efficiency vs dataset size
Baselines: Robust value iteration (RVI) Robust relative value iteration (RRVI) Grand-Clément & Petrik 2024 Blackwell discount reduction
Builds on: robust MDP (Iyengar 2005) Wang et al. 2023 robust average reward value iteration Shi et al. 2023 robust discounted sample complexity Zhou et al. 2024 robust natural actor-critic Grand-Clément & Petrik 2024 Blackwell discount bound
Closest papers by meaning
- Sample Complexity of Distributionally Robust Average-Reward Reinforcement Learning (NeurIPS 2025 · similarity 0.91)
- Minimax Optimal and Computationally Efficient Algorithms for Distributionally Robust Offline Reinforcement Learning (NeurIPS 2024 · similarity 0.90)
- Robust Reinforcement Learning with General Utility (NeurIPS 2024 · similarity 0.90)
- Finite-Sample Analysis of Policy Evaluation for Robust Average Reward Reinforcement Learning (NeurIPS 2025 · similarity 0.90)
- Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithms (NeurIPS 2024 · similarity 0.89)
- Robust Offline Reinforcement Learning with Linearly Structured $f$-Divergence Regularization (ICML 2025 · similarity 0.88)
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.