mlsanityData to 14 Oct 2026

Model-Free Robust Average-Reward Reinforcement Learning with Sample Complexity Analysis

arXiv 2505.12462 ↗First posted 18 May 2025cs.LG stat.MLcited by 3

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

Robust reinforcement learning (RL) under the average-reward criterion is essential for long-term decision-making, particularly when the environment may differ from its training dynamics. However, most existing studies focus on model-based settings and provide only asymptotic guarantees, hindering their principled understanding and practical deployment, especially in data-limited scenarios. We aim to close this gap by proposing a model-free algorithm, Robust Halpern Iteration (RHI). We first design our algorithm based on a black-box sampling oracle, which can estimate the worst-case performance accurately. We then derive the finite sample complexity of RHI under the generative model setting, assuming the sampling oracle. To concretely design such an oracle, we propose a K-order multi-level Monte-Carlo estimator, which is shown to have a lower bias compared to prior methods. We further instantiate our design for multiple uncertainty models, including KL and chi2 divergence sets, and show that our RHI algorithm achieves an varepsilon-optimal robust policy with a sample complexity of tildeOleft( fracSAH2varepsilon(2+o(1))right), where S,A are the number of states and actions, and H is the robust optimal span. Our result asymptotically matches the best complexity in robust average reward RL.

Key facts. Cited by 3 papers in the map (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 51 of its 98 references that are in the map. First posted on arXiv 18 May 2025.

Builds on

51 of 98 references.

Closest ancestors · 4

Same direction, newest first

  1. 2025Sample Complexity of Distributionally Robust Average-Reward Reinforcement Learning15 May
  2. 2025Finite-Sample Analysis of Policy Evaluation for Robust Average Reward Reinforcement Learning24 Feb
  3. 2024Model-Free Robust Reinforcement Learning with Sample Complexity Analysis24 Jun
  4. 2024Sample Complexity of Offline Distributionally Robust Linear Markov Decision Processes19 Mar

Other references · 47

  1. 2017Domain Randomization for Transferring Deep Neural Networks from Simulation to the Real Worldcited by 1,498
  2. 2017Deep Reinforcement Learning that Matterscited by 754
  3. 2017Sim-to-Real Transfer of Robotic Control with Dynamics Randomizationcited by 672
  4. 2017Robust Adversarial Reinforcement Learningcited by 451
  5. 2020Sim-to-Real Transfer in Deep Reinforcement Learning for Robotics: a Surveycited by 413
  6. 2018A Study on Overfitting in Deep Reinforcement Learningcited by 174
  7. 2016EPOpt: Learning Robust Neural Network Policies Using Model Ensemblescited by 138
  8. 2020Off-Dynamics Reinforcement Learning: Training for Transfer with Domain Classifierscited by 97
  9. 2021Online Robust Reinforcement Learning with Model Uncertaintycited by 96
  10. 2021Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysiscited by 92
  11. 2022Distributionally Robust Model-Based Offline Reinforcement Learning with Near-Optimal Sample Complexitycited by 87
  12. 2021Sample Complexity of Robust Reinforcement Learning with a Generative Modelcited by 83
35 more
  1. 2018What Doubling Tricks Can and Can't Do for Multi-Armed Banditscited by 71
  2. 2017A First Order Method for Solving Convex Bi-Level Optimization Problemscited by 67
  3. 2020Reinforcement Learning in Economics and Financecited by 58
  4. 2020Learning and Planning in Average-Reward Markov Decision Processescited by 54
  5. 2023The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Modelcited by 52
  6. 2021Twice regularized MDPs and the equivalence between robustness and regularizationcited by 47
  7. 2023Improved Sample Complexity Bounds for Distributionally Robust Reinforcement Learningcited by 44
  8. 2023A Finite Sample Complexity Bound for Distributionally Robust Q-learningcited by 36
  9. 2021Towards Tight Bounds on the Sample Complexity of Average-reward MDPscited by 33
  10. 2022Stochastic first-order methods for average-reward Markov decision processescited by 32
  11. 2022Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDPcited by 29
  12. 2023Sample Complexity of Variance-reduced Distributionally Robust Q-learningcited by 29
  13. 2023Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processescited by 29
  14. 2022Honor of Kings Arena: an Environment for Generalization in Competitive Reinforcement Learningcited by 28
  15. 2022Exact Optimal Accelerated Complexity for Fixed-Point Iterationscited by 25
  16. 2020Average-reward model-free reinforcement learning: a systematic review and literature mappingcited by 22
  17. 2023Robust Average-Reward Markov Decision Processescited by 22
  18. 2023Model-Free Robust Average-Reward Reinforcement Learningcited by 20
  19. 2024Minimax Optimal and Computationally Efficient Algorithms for Distributionally Robust Offline Reinforcement Learningcited by 18
  20. 2023Single-Trajectory Distributionally Robust Reinforcement Learningcited by 16
  21. 2023Optimal Sample Complexity for Average Reward Markov Decision Processescited by 15
  22. 2022On Efficient Reinforcement Learning for Full-length Game of StarCraft IIcited by 14
  23. 2025Near-Optimal Sample Complexity for MDPs via Anchoringcited by 14
  24. 2023Reducing Blackwell and Average Optimality to Discounted MDPs via the Blackwell Discount Factorcited by 13
  25. 2023Beyond discounted returns: Robust Markov decision processes with average and Blackwell optimalitycited by 13
  26. 2024Finding good policies in average-reward Markov Decision Processes without prior knowledgecited by 13
  27. 2021Optimal error bounds for nonexpansive fixed-point iterations in normed spacescited by 12
  28. 2024Solving Robust Markov Decision Processes: Generic, Reliable, Efficientcited by 11
  29. 2023Solving Long-run Average Reward Robust MDPs via Stochastic Gamescited by 10
  30. 2024The Plug-in Approach for Average-Reward and Discounted MDPs: Optimal Sample Complexity Analysiscited by 9
  31. 2022On Convergence of Average-Reward Off-Policy Control Algorithms in Weakly Communicating MDPscited by 6
  32. 2023An Efficient Solution to s-Rectangular Robust Markov Decision Processescited by 6
  33. 2023Optimal Sample Complexity of Stable Discounted Markov Decision Processescited by 6
  34. 2025Optimal Non-Asymptotic Rates of Value Iteration for Average-Reward Markov Decision Processescited by 6
  35. 2023Span-Based Optimal Sample Complexity for Average Reward MDPscited by 5

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 1; 2026: 2.

3 papers.

  1. 2026Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductionscited by 2
  2. 2026Persistent-Transient Policy Evaluation for Markov Chains via Minimal Peripheral Quotientscited by 1
  3. 2025Finite-Time Convergence of Single-Trajectory Chi-Square Robust Q-Learning With Linear Function Approximationcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026Distributionally Robust Average-Reward Reinforcement Learning: Finite-Sample Guarantees under Weak Communication
  2. 2025Online Robust Reinforcement Learning with General Function Approximation
  3. 2024Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithms
  4. 2025Efficient Q-Learning and Actor-Critic Methods for Robust Average-Reward Reinforcement Learning
  5. 2024Model-Free Robust φ-Divergence Reinforcement Learning Using Both Offline and Online Data
  6. 2025Near-Optimal Sample Complexities of Divergence-based S-rectangular Distributionally Robust Reinforcement Learning
  7. 2024Sample-Efficient Robust Multi-Agent Reinforcement Learning in the Face of Environmental Uncertainty
  8. 2024Robust Offline Reinforcement Learning with Linearly Structured f-Divergence Regularization