Bellman Optimality of Average-Reward Robust Markov Decision Processes with a Constant Gain

Shengbo Wang; Nian Si

math.OCSep 17, 2025

Bellman Optimality of Average-Reward Robust Markov Decision Processes with a Constant Gain

Authors: Shengbo Wang, Nian Si

Organizations: Daniel J. Epstein Department of Industrial and Systems Engineering, University of Southern California · Department of Industrial Engineering and Decision Analytics, Hong Kong University of Science and Technology

Abstract

Learning and optimal control under robust Markov decision processes (MDPs) have received increasing attention, yet most existing theory, algorithms, and applications focus on finite-horizon or discounted models. Long-run average-reward formulations, while natural in many operations research and management contexts, remain underexplored. This is primarily because the dynamic programming foundations are technically challenging and only partially understood, with several fundamental questions remaining open. This paper steps toward a general framework for average-reward robust MDPs by analyzing the constant-gain setting. We study the average-reward robust control problem with possible information asymmetries between the controller and an S-rectangular adversary. Our analysis centers on the constant-gain robust Bellman equation, examining both the existence of solutions and their relationship to the optimal average reward. Specifically, we identify when solutions to the robust Bellman equation characterize the optimal average reward and stationary policies, and we provide one-sided weak communication conditions ensuring solutions' existence. These findings expand the dynamic programming theory for average-reward robust MDPs and lay a foundation for robust dynamic decision making under long-run average criteria in operational environments.

Figures & tables

Panel of Figure 1 — Figure 1: The dynamics of an average-reward robust MDP instance where $\alpha^{*}\neq\alpha^{\prime}$ . The red and blue arrows represent the dynamics under actions $a_{1}$ and $a_{2}$ , respectively.

Panel of Figure 2 — Figure 2: Transition diagrams for different actions in the example of dynamic service allocation in queuing environments.

Robust Markov Decision Processes

Robust Markov decision processes optimize decisions under uncertain dynamics, seeking reliable performance against adverse transition models.

See all 26 papers

Vector Bellman Theory for Multichain Robust Average-Reward Markov Decision Processes
Sep 23, 2026Yue Wang, George AtiaRobust Markov Decision Processes Markov Decision Processes
Department of Electrical and Computer Engineering University of Central Florida
Non-Rectangular Average-Reward Robust MDPs: Optimal Policies and Their Transient Values
Mar 1, 2026Shengbo Wang, Nian SiRobust Markov Decision Processes Average-Reward RL
Daniel J. Epstein Department of Industrial and Systems Engineering, University of Southern California · Department of Industrial Engineering and Decision Analytics, Hong Kong University of Science and Technology
Distributionally Robust Markov Games with Average Reward
Aug 5, 2025Zachary Roch, Yue WangNash Equilibrium Computation Multi-Agent System Optimization
Department of Electrical and Computer Engineering, University of Central Florida, Orlando, Florida, USA. · Department of Computer Science, University of Central Florida, Orlando, Florida, USA.

Sep 23, 2026J/K move · Enter open · S save

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

Yue Wang, George Atia

Department of Electrical and Computer Engineering University of Central Florida

Robust Markov Decision Processes Markov Decision Processes Average-Reward RL Model-Based Planning Robust RL

Open paper AskPDF 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.

Abstract

Robust Markov Decision Processes

Explore similar work

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

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

Distributionally Robust Markov Games with Average Reward