Sample Complexity of Distributionally Robust Average-Reward Reinforcement Learning

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 O(|S||A| tₘᵢₓ²ε⁻²) for estimating the optimal policy as well as the robust average reward under KL and fₖ-divergence-based uncertainty sets, provided the uncertainty radius is sufficiently small. Here, ε is the target accuracy, |S| and |A| denote the sizes of the state and action spaces, and tₘᵢₓ is the mixing time of the nominal MDP. This represents the first finite-sample convergence guarantee for DR average-reward reinforcement learning. We further validate the convergence rates of our algorithms through numerical experiments.