# Distributionally Robust Average-Reward Reinforcement Learning: Finite-Sample Guarantees under Weak Communication

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 4 of its 50 references that are in the map.
- First posted on arXiv 26 Sep 2026.

## 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, 4 of 4)

- [On Convergence of Average-Reward Q-Learning in Weakly Communicating Markov Decision Processes](https://mlsanity.com/paper/2408.16262/) (2024)
- [Bellman Optimality of Average-Reward Robust Markov Decision Processes with a Constant Gain](https://mlsanity.com/paper/2509.14203/) (2025)
- [Learning Policy from a Single Trajectory in Average-Reward Markov Decision Process](https://mlsanity.com/paper/2606.16729/) (2026)
- [Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions](https://mlsanity.com/paper/2608.06545/) (2026)

## Abstract (arXiv)

We study distributionally robust reinforcement learning (DR-RL) in the average-reward setting under weak communication. Our main result provides finite-sample guarantees for estimating the robust optimal average reward and learning a near-optimal policy, covering both SA-rectangular and S-rectangular structures with divergence-based and distance-based uncertainty sets. Specifically, for Kullback--Leibler and fk-divergence balls, we establish explicit radius conditions under which the robust average-reward Bellman equation admits a constant-gain solution, while for total variation and Wasserstein balls, any positive radius suffices without requiring the nominal MDP to be weakly communicating. Our algorithm is prior-knowledge-free and achieves sample complexities of widetilde O(|S||A|pwedge-1operatornameSpan2(uδast)ε-2) for estimating the robust optimal average reward and widetilde O(|S||A|pwedge-2operatornameSpan2(uδast)ε-2) for learning an ε-optimal policy. Here, pwedge is the smallest positive nominal transition probability and uδast is a robust optimal bias function. We further provide an almost-tight explicit upper bound on operatornameSpan(uδast). Finally, we validate the predicted n-1/2 convergence rate through numerical experiments.