# Non-Rectangular Average-Reward Robust MDPs: Optimal Policies and Their Transient Values

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 31 references that are in the map.
- First posted on arXiv 1 Mar 2026.

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

- [Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processes](https://mlsanity.com/paper/1910.07072/) (2019)
- [Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learning](https://mlsanity.com/paper/1802.04020/) (2018)
- [Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processes](https://mlsanity.com/paper/2306.16394/) (2023)
- [Robust Average-Reward Markov Decision Processes](https://mlsanity.com/paper/2301.00858/) (2023)
- [On the Foundation of Distributionally Robust Reinforcement Learning](https://mlsanity.com/paper/2311.09018/) (2023)
- [Policy Gradient Algorithms for Robust MDPs with Non-Rectangular Uncertainty Sets](https://mlsanity.com/paper/2305.19004/) (2023)
- [Beyond discounted returns: Robust Markov decision processes with average and Blackwell optimality](https://mlsanity.com/paper/2312.03618/) (2023)
- [Bounded regret in stochastic multi-armed bandits](https://mlsanity.com/paper/1302.1611/) (2013)
- [Solving Non-Rectangular Reward-Robust MDPs via Frequency Regularization](https://mlsanity.com/paper/2309.01107/) (2023)
- [Bellman Optimality of Average-Reward Robust Markov Decision Processes with a Constant Gain](https://mlsanity.com/paper/2509.14203/) (2025)
- [Dual Formulation for Non-Rectangular Lp Robust Markov Decision Processes](https://mlsanity.com/paper/2502.09432/) (2025)
- [Tractable and Near-Optimal Adversarial Algorithms for Robust Estimation in Contaminated Gaussian Models](https://mlsanity.com/paper/2112.12919/) (2021)
- [Dynamic Programming-Compatible Uncertainty Sets in Robust Markov Decision Processes](https://mlsanity.com/paper/2411.08435/) (2024)
- [Playing against a stationary opponent](https://mlsanity.com/paper/2503.15346/) (2025)
- [Provably Efficient Algorithms for S- and Non-Rectangular Robust MDPs with General Parameterization](https://mlsanity.com/paper/2602.11387/) (2026)

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

- [Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions](https://mlsanity.com/paper/2608.06545/) (2026)
- [Vector Bellman Theory for Multichain Robust Average-Reward Markov Decision Processes](https://mlsanity.com/paper/2609.28792/) (2026)

## Abstract (arXiv)

We study non-rectangular robust Markov decision processes under the average-reward criterion, where the ambiguity set couples transition probabilities across states and the adversary commits to a stationary kernel for the entire horizon. We show that any history-dependent policy achieving sublinear expected regret uniformly over the ambiguity set is robust-optimal, and that the robust value admits a minimax representation as the infimum over the ambiguity set of the classical optimal gains, without requiring any form of rectangularity or robust dynamic programming principle. Under the weak communication assumption, we establish the existence of such policies by converting high-probability regret bounds from the average-reward reinforcement learning literature into the expected-regret criterion. We then introduce a transient-value framework to evaluate finite-time performance of robust optimal policies, proving that average-reward optimality alone can mask arbitrarily poor transients and deriving regret-based lower bounds on transient values. Finally, we construct an epoch-based policy that combines an optimal stationary policy for the worst-case model with an anytime-valid sequential test and an online learning fallback, achieving a constant-order transient value.