Vector Bellman Theory for Multichain Robust Average-Reward Markov Decision Processes
Not on the map. Why?
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.
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
21 of 87 references.
References · 21
- 2022Robust Reinforcement Learning using Offline Datacited by 96
- 2022Distributionally Robust Model-Based Offline Reinforcement Learning with Near-Optimal Sample Complexitycited by 87
- 2023The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Modelcited by 52
- 2023Sample Complexity of Variance-reduced Distributionally Robust Q-learningcited by 29
- 2024Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithmscited by 26
- 2021Average-Reward Reinforcement Learning with Trust Region Methodscited by 19
- 2024Minimax Optimal and Computationally Efficient Algorithms for Distributionally Robust Offline Reinforcement Learningcited by 18
- 2023Single-Trajectory Distributionally Robust Reinforcement Learningcited by 16
- 2024Sample Complexity of Offline Distributionally Robust Linear Markov Decision Processescited by 14
- 2023Beyond discounted returns: Robust Markov decision processes with average and Blackwell optimalitycited by 13
- 2024On Convergence of Average-Reward Q-Learning in Weakly Communicating Markov Decision Processescited by 9
- 2023Bring Your Own (Non-Robust) Algorithm to Solve Robust MDPs by Estimating The Worst Kernelcited by 8
9 more
- 2025Finite-Sample Analysis of Policy Evaluation for Robust Average Reward Reinforcement Learningcited by 7
- 2022On Convergence of Average-Reward Off-Policy Control Algorithms in Weakly Communicating MDPscited by 6
- 2023An Efficient Solution to s-Rectangular Robust Markov Decision Processescited by 6
- 2025Bellman Optimality of Average-Reward Robust Markov Decision Processes with a Constant Gaincited by 5
- 2024Model-Free Robust φ-Divergence Reinforcement Learning Using Both Offline and Online Datacited by 4
- 2025Efficient Q-Learning and Actor-Critic Methods for Robust Average-Reward Reinforcement Learningcited by 4
- 2026Non-Rectangular Average-Reward Robust MDPs: Optimal Policies and Their Transient Valuescited by 2
- 2026Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductionscited by 2
- 2013Projection: A Unified Approach to Semi-Infinite Linear Programs and Duality in Convex Programmingcited by 1
Built on by
Not cited yet.