mlsanityData to 14 Oct 2026

Finite-Sample Analysis of Policy Evaluation for Robust Average Reward Reinforcement Learning

arXiv 2502.16816 ↗First posted 24 Feb 2025stat.ML cs.LGcited by 7

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

Abstract (arXiv)

We present the first finite-sample analysis of policy evaluation in robust average-reward Markov Decision Processes (MDPs). Prior work in this setting have established only asymptotic convergence guarantees, leaving open the question of sample complexity. In this work, we address this gap by showing that the robust Bellman operator is a contraction under a carefully constructed semi-norm, and developing a stochastic approximation framework with controlled bias. Our approach builds upon Multi-Level Monte Carlo (MLMC) techniques to estimate the robust Bellman operator efficiently. To overcome the infinite expected sample complexity inherent in standard MLMC, we introduce a truncation mechanism based on a geometric distribution, ensuring a finite expected sample complexity while maintaining a small bias that decays exponentially with the truncation level. Our method achieves the order-optimal sample complexity of tildeO(ε-2) for robust policy evaluation and robust average reward estimation, marking a significant advancement in robust reinforcement learning theory.

Key facts. Cited by 7 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 24 of its 52 references that are in the map. First posted on arXiv 24 Feb 2025.

Builds on

24 of 52 references.

Closest ancestors · 3

Same direction, newest first

  1. 2024A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approach26 Jul
  2. 2024Model-Free Robust Reinforcement Learning with Sample Complexity Analysis24 Jun
  3. 2024Order-Optimal Regret with Novel Policy Gradient Approaches in Infinite-Horizon Average Reward MDPs2 Apr

Other references · 21

  1. 2019Reinforcement Learning in Healthcare: A Surveycited by 310
  2. 2016Distributionally Robust Stochastic Optimization with Wasserstein Distancecited by 185
  3. 2024Deep Reinforcement Learning for Robotics: A Survey of Real-World Successescited by 176
  4. 2021Recent Advances in Reinforcement Learning in Financecited by 110
  5. 2018The Limits and Potentials of Deep Learning for Roboticscited by 104
  6. 2019Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processescited by 82
  7. 2022Policy Gradient Method For Robust Reinforcement Learningcited by 69
  8. 2019DeepPool: Distributed Model-free Algorithm for Ride-sharing using Deep Reinforcement Learningcited by 54
  9. 2020Partial Policy Iteration for L1-Robust Markov Decision Processescited by 50
  10. 2023Natural Actor-Critic for Robust Reinforcement Learning with Function Approximationcited by 36
  11. 2022First-order Policy Optimization for Robust Markov Decision Processcited by 32
  12. 2023Policy Gradient for Rectangular Robust Markov Decision Processescited by 31
9 more
  1. 2022Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDPcited by 29
  2. 2023Regret Analysis of Policy Gradient Algorithm for Infinite Horizon Average Reward Markov Decision Processescited by 26
  3. 2023Robust Average-Reward Markov Decision Processescited by 22
  4. 2023Model-Free Robust Average-Reward Reinforcement Learningcited by 20
  5. 2019Unbiased Multilevel Monte Carlo: Stochastic Optimization, Steady-state Simulation, Quantiles, and Other Applicationscited by 18
  6. 2021Learning Robust Policy against Disturbance in Transition Dynamics via State-Conservative Policy Optimizationcited by 18
  7. 2020First-Order Methods for Wasserstein Distributionally Robust MDPcited by 17
  8. 2025A Non-Asymptotic Theory of Seminorm Lyapunov Stability: From Deterministic to Stochastic Iterative Algorithmscited by 10
  9. 2025Accelerating Quantum Reinforcement Learning with a Quantum Natural Policy Gradient Based Approachcited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 4; 2026: 3.

7 papers.

  1. 2025Efficient Q-Learning and Actor-Critic Methods for Robust Average-Reward Reinforcement Learningcited by 4
  2. 2025Model-Free Robust Average-Reward Reinforcement Learning with Sample Complexity Analysiscited by 3
  3. 2025Primal-Only Actor Critic Algorithm for Robust Constrained Average Cost MDPscited by 1
  4. 2026Persistent-Transient Policy Evaluation for Markov Chains via Minimal Peripheral Quotientscited by 1
  5. 2026Non-Asymptotic Convergence of Stochastic Iterative Algorithms: A Lyapunov Frameworkcited by 1
  6. 2025Finite-Time Convergence of Single-Trajectory Chi-Square Robust Q-Learning With Linear Function Approximationcited by 0
  7. 2026Vector Bellman Theory for Multichain Robust Average-Reward Markov Decision Processescited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025Sample Complexity of Distributionally Robust Average-Reward Reinforcement Learning
  2. 2025Provably Efficient Sample Complexity for Robust CMDP
  3. 2026Distributionally Robust Average-Reward Reinforcement Learning: Finite-Sample Guarantees under Weak Communication
  4. 2024Sample Complexity of Offline Distributionally Robust Linear Markov Decision Processes
  5. 2026Non-Rectangular Average-Reward Robust MDPs: Optimal Policies and Their Transient Values
  6. 2021Robust Entropy-regularized Markov Decision Processes
  7. 2026Sample Complexity of Average-Reward Q-Learning: From Single-agent to Federated Reinforcement Learning
  8. 2026Mathematical methods of reinforcement learning