# Sample Complexity of Distributionally Robust Average-Reward Reinforcement Learning

arXiv: https://arxiv.org/abs/2505.10007 · HTML: https://mlsanity.com/paper/2505.10007/

## 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 1 of its 1 references that are in the map.
- First posted on arXiv 15 May 2025.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 1 of 1)

- [An Efficient High-Dimensional Gradient Estimator for Stochastic Differential Equations](https://mlsanity.com/paper/2407.10065/) (2024)

## Built on by (most cited first, 7 of 7)

- [Efficient Q-Learning and Actor-Critic Methods for Robust Average-Reward Reinforcement Learning](https://mlsanity.com/paper/2506.07040/) (2025)
- [Model-Free Robust Average-Reward Reinforcement Learning with Sample Complexity Analysis](https://mlsanity.com/paper/2505.12462/) (2025)
- [Primal-Only Actor Critic Algorithm for Robust Constrained Average Cost MDPs](https://mlsanity.com/paper/2511.05758/) (2025)
- [Provably Efficient Algorithms for S- and Non-Rectangular Robust MDPs with General Parameterization](https://mlsanity.com/paper/2602.11387/) (2026)
- [Finite-Time Convergence of Single-Trajectory Chi-Square Robust Q-Learning With Linear Function Approximation](https://mlsanity.com/paper/2510.01721/) (2025)
- [Central Limit Theorem for Two-Time-Scale Approximate Distributionally Robust RL](https://mlsanity.com/paper/2605.08417/) (2026)
- [Stationary Robust Mean-Field Games under Model Mismatches](https://mlsanity.com/paper/2606.22579/) (2026)

## Abstract (arXiv)

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 widetildeOleft(|S||A| tmix2varepsilon-2right) for estimating the optimal policy as well as the robust average reward under KL and fk-divergence-based uncertainty sets, provided the uncertainty radius is sufficiently small. Here, varepsilon is the target accuracy, |S| and |A| denote the sizes of the state and action spaces, and tmix 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.