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

Yue Wang; George Atia

cs.LGSep 23, 2026

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

Authors: Yue Wang, George Atia

Abstract

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.

Explore similar work

Aug 6, 2026cs.LG

Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions

Distributionally robust Markov decision processes provide a principled framework for sequential decision making under model uncertainty. We study how many samples are necessary and sufficient to learn an

\varepsilon

-optimal robust policy under the average-reward criterion. A generative model provides samples from the nominal transition kernel, whereas policy performance is evaluated over

(s,a)

-rectangular total-variation uncertainty sets of radius at most

σ

. Let

H_0

and

H_σ

denote the nominal and robust optimal bias spans, respectively. We identify

σH_0

as the perturbation scale separating high- and low-tolerance regimes. Our matching upper and lower bounds show that, up to logarithmic factors, the minimax total sample complexity is

NSA \asymp \frac{SA}{\varepsilon^2}\begin{cases} \min\{H_0,H_σ\}, & \varepsilon\gtrsimσH_0,\\ \min\{H_0,H_σ\}+σH_σ^2, & \varepsilon\lesssimσH_0. \end{cases}

Here

S

and

A

are the numbers of states and actions, and

N

is the number of samples per state-action pair. The sample complexity consists of a linear-span term that resembles the nominal AMDP results and a robustness-specific term that appears only in the low-tolerance regime. We attain these rates using reduction-based plug-in procedures that select the reduction---nominal or robust---and its discount factor: a span-informed procedure that makes these choices using known span parameters, and a span-agnostic procedure that calibrates both choices from data.

Yuepeng Yang, Yuxin Chen, Yuejie Chi

Markov Decision Processes Optimal Policies Sample Complexity Decisions

Ask PDF

Aug 5, 2025cs.MA

Distributionally Robust Markov Games with Average Reward

We propose and study distributionally robust Markov games (DR-MGs) with the average-reward criterion as a crucial framework for multi-agent decision-making under model mismatches and over extended horizons. Under a standard irreducible assumption, we first derive a correspondence between the optimal policies and the solutions of the robust Bellman equation, based on which we further show the existence of a stationary Nash Equilibrium (NE) of the game. We further study DR-MGs under a more general weakly communicating setting. We construct a set-valued map based on the constant-gain optimal robust Bellman operator and show that its value is a subset of the best-response policies. We further prove that this map admits a fixed point, which implies the existence of NE. We then design two algorithms, Robust Nash-Iteration and robust TD Descent, with provably convergent guarantees. Finally, we show that the NE under average-reward can be approximated by the ones for the discounted DR-MGs as the discount factor approaches one. Our studies provide a comprehensive theoretical and algorithmic foundation for decision-making in complex, uncertain, and long-running multi-player environments.

Zachary Roch, Yue Wang

Zero--Sum Differential Game Markov Decision Processes Multi-Agent Reinforcement Learning Nash Equilibrium Bellman Equation Multi-Agent Systems

Ask PDF

Jun 8, 2025cs.LG

Efficient Q-Learning and Actor-Critic Methods for Robust Average-Reward Reinforcement Learning

We study model-free methods for distributionally robust infinite-horizon average-reward Markov decision processes (MDPs). We present non-asymptotic convergence analyses of Q-learning and actor-critic algorithms for robust average-reward MDPs under contamination, total-variation distance, and Wasserstein uncertainty sets. A key ingredient of our analysis is showing that the optimal robust Bellman operator is a strict contraction with respect to a carefully designed semi-norm. This property enables a stochastic approximation update that learns the optimal robust

Q

-function with

\tilde{\mathcal{O}}(ε^{-2})

dependence on the target accuracy. We also establish robust TD convergence bounds whose constants are uniform over all stationary policies, yielding an efficient data-driven routine for robust critic estimation. Building on this, we introduce an actor-critic algorithm that learns an

ε

-optimal robust policy with

\tilde{\mathcal{O}}(ε^{-2})

dependence on the target accuracy. We provide numerical simulations to illustrate the qualitative behavior of the proposed algorithms. Our results contribute to the theoretical foundations of robust planning under model misspecification and to model-free approaches for building robust long-run policies directly from simulation data.

Yang Xu, Swetha Ganesh, Vaneet Aggarwal

Q-Learning Soft Actor-Critic Bellman Equation Critic-Free Reinforcement Learning Classical Planning

Ask PDF