# Vector Bellman Theory for Multichain Robust Average-Reward Markov Decision Processes

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 21 of its 87 references that are in the map.
- First posted on arXiv 23 Sep 2026.

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

- [Robust Reinforcement Learning using Offline Data](https://mlsanity.com/paper/2208.05129/) (2022)
- [Distributionally Robust Model-Based Offline Reinforcement Learning with Near-Optimal Sample Complexity](https://mlsanity.com/paper/2208.05767/) (2022)
- [The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2305.16589/) (2023)
- [Sample Complexity of Variance-reduced Distributionally Robust Q-learning](https://mlsanity.com/paper/2305.18420/) (2023)
- [Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithms](https://mlsanity.com/paper/2404.03578/) (2024)
- [Average-Reward Reinforcement Learning with Trust Region Methods](https://mlsanity.com/paper/2106.03442/) (2021)
- [Minimax Optimal and Computationally Efficient Algorithms for Distributionally Robust Offline Reinforcement Learning](https://mlsanity.com/paper/2403.09621/) (2024)
- [Single-Trajectory Distributionally Robust Reinforcement Learning](https://mlsanity.com/paper/2301.11721/) (2023)
- [Sample Complexity of Offline Distributionally Robust Linear Markov Decision Processes](https://mlsanity.com/paper/2403.12946/) (2024)
- [Beyond discounted returns: Robust Markov decision processes with average and Blackwell optimality](https://mlsanity.com/paper/2312.03618/) (2023)
- [On Convergence of Average-Reward Q-Learning in Weakly Communicating Markov Decision Processes](https://mlsanity.com/paper/2408.16262/) (2024)
- [Bring Your Own (Non-Robust) Algorithm to Solve Robust MDPs by Estimating The Worst Kernel](https://mlsanity.com/paper/2306.05859/) (2023)
- [Finite-Sample Analysis of Policy Evaluation for Robust Average Reward Reinforcement Learning](https://mlsanity.com/paper/2502.16816/) (2025)
- [On Convergence of Average-Reward Off-Policy Control Algorithms in Weakly Communicating MDPs](https://mlsanity.com/paper/2209.15141/) (2022)
- [An Efficient Solution to s-Rectangular Robust Markov Decision Processes](https://mlsanity.com/paper/2301.13642/) (2023)
- [Bellman Optimality of Average-Reward Robust Markov Decision Processes with a Constant Gain](https://mlsanity.com/paper/2509.14203/) (2025)
- [Model-Free Robust φ-Divergence Reinforcement Learning Using Both Offline and Online Data](https://mlsanity.com/paper/2405.05468/) (2024)
- [Efficient Q-Learning and Actor-Critic Methods for Robust Average-Reward Reinforcement Learning](https://mlsanity.com/paper/2506.07040/) (2025)
- [Non-Rectangular Average-Reward Robust MDPs: Optimal Policies and Their Transient Values](https://mlsanity.com/paper/2603.00945/) (2026)
- [Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions](https://mlsanity.com/paper/2608.06545/) (2026)
- [Projection: A Unified Approach to Semi-Infinite Linear Programs and Duality in Convex Programming](https://mlsanity.com/paper/1304.3030/) (2013)

## Abstract (arXiv)

Robust average-reward Markov decision processes provide a fundamental framework for long-term performance optimization under uncertainty, and can have optimal long-run rewards that depend on the initial state. This state dependence requires a vector Bellman theory that accounts for both recurrent-class rewards and transition uncertainty. We develop such a theory for finite models with compact, post-action (s,a)-rectangular ambiguity. A gain-first, bias-second optimization principle yields a coupled vector gain-bias system, and every finite solution identifies the optimal robust gain and supplies stationary saddle strategies against history-dependent opponents, simultaneously from all initial states. We further characterize solvability through stationary gain conditions and a uniform bound on canonical transient corrections, and give sufficient conditions that permit distinct recurrent-class gains. The certificates also yield asymptotically affine trajectories of the robust Bellman operator, based on which we design a robust approximately shifted Halpern planning algorithm. Under finite Bellman solvability, the gain estimates and Bellman displacements converge to the optimal gain vector, and every extracted greedy controller is average-optimal after a finite, instance-dependent budget. These results thus connect finite Bellman certificates to undiscounted planning for state-dependent robust average rewards, providing theoretical understandings.