Sample Complexity Of Distributionally Robust Average-reward Reinforcement Learning

Abstract

Motivated by practical applications where stable long-term performance is critical-such as robotics, operations research, and healthcare-we study the problem of distributionally robust (DR) average-reward reinforcement learning. We propose two algorithms that achieve near-optimal sample complexity. The first reduces the problem to a DR discounted Markov decision process (MDP), while the second, Anchored DR Average-Reward MDP, introduces an anchoring state to stabilize the controlled transition kernels within the uncertainty set. Assuming the nominal MDP is uniformly ergodic, we prove that both algorithms attain a sample complexity of \(\widetilde\{O\}\left(|\mathbf\{S\}||\mathbf\{A\}| t_\{\mathrm\{mix\}\}^2\epsilon^\{-2\}\right)\) for estimating the optimal policy as well as the robust average reward under KL and \(f_k\)-divergence-based uncertainty sets, provided the uncertainty radius is sufficiently small. Here, \(\epsilon\) is the target accuracy, \(|\mathbf\{S\}|\) and \(|\mathbf\

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keychen2025sample

Related papers

• Near-optimal Sample Complexities Of Divergence-based S-rectangular Distributionally Robust Reinforcement Learning (2026)0.00
• Optimal Sample Complexity For Average Reward Markov Decision Processes (2023)0.00
• Sample Complexity Of Offline Distributionally Robust Linear Markov Decision Processes (2024)0.00
• The Curious Price Of Distributional Robustness In Reinforcement Learning With A Generative Model (2023)0.00
• Sample Complexity Of Average-reward Q-learning: From Single-agent To Federated Reinforcement Learning (2026)0.00
• Sample Complexity Of Variance-reduced Distributionally Robust Q-learning (2023)0.00
• Sample Complexity Of Robust Reinforcement Learning With A Generative Model (2021)0.00
• Optimal Single-policy Sample Complexity And Transient Coverage For Average-reward Offline RL (2025)0.00