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

2025/05/18 by Zachary Roch, George Atia, Roch, Zachary +4 · 3 citations
Computer Science · Engineering · #Adaptive Dynamic Programming Control #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Reinforcement Learning in Robotics #Traffic control and management

paper · pdf · doi:10.48550/arxiv.2505.12462

openalex publication_date 2025/05/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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 χ² divergence sets, and show that our RHI algorithm achieves an ε-optimal robust policy with a sample complexity of O( \fracSAH²ε^(2+o(1))), 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.

Cited by

• RobustVLA: Robustness-Aware Reinforcement Post-Training for Vision-Language-Action Models
• Primal-Only Actor Critic Algorithm for Robust Constrained Average Cost MDPs
• Distributionally Robust Markov Games with Average Reward

Related

• Finite-Sample Analysis of Policy Evaluation for Robust Average Reward Reinforcement Learning
• Sample Complexity of Distributionally Robust Average-Reward Reinforcement Learning
• Model-Free Robust Average-Reward Reinforcement Learning
• Efficient Q-Learning and Actor-Critic Methods for Robust Average Reward Reinforcement Learning
• Sample Complexity of Robust Reinforcement Learning with a Generative\n Model