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

Shengbo Wang, Nian Si

Abstract

This paper establishes the first comprehensive theoretical foundation for average-reward robust Markov Decision Processes (RMDPs). By introducing the concept of "one-sided weak communication," the authors identify the conditions under which a robust Bellman equation possesses a solution. These solutions are shown to successfully characterize optimal long-term strategies in environments characterized by model uncertainty and adversarial dynamics.

Introduction

In standard reinforcement learning, Markov Decision Processes (MDPs) serve as the primary framework for modeling sequential decision-making. However, these models often suffer from model misspecification, where the transition dynamics used for training do not perfectly match the real-world environment. Robust MDPs (RMDPs) address this by assuming an adversary selects the worst-case transition dynamics from a predefined uncertainty set, ensuring that the resulting policy remains effective even under unfavorable conditions.

While the theory of RMDPs is well-developed for discounted rewards—where immediate gains are prioritized over future ones—many critical systems, such as supply chain management and network routing, are better modeled by the long-run average reward. This setting is mathematically complex because the "gain" (average reward) can vary based on the starting state, and standard dynamic programming tools often fail to converge. This paper bridges this gap by identifying the specific conditions under which a stable, "constant-gain" solution exists for robust average-reward problems.

Methodology

One-Sided Weak Communication

The authors generalize the classical MDP concept of "weak communication" to the robust setting. This condition assumes that either the controller or the adversary possesses sufficient influence to prevent the system from becoming trapped in isolated states, regardless of the other player's actions. This structural assumption is vital for ensuring that the optimal average reward eventually becomes independent of the initial state.

The Vanishing Discount Approach

To prove the existence of a solution to the average-reward equation, the authors utilize a vanishing discount approach. They demonstrate that if the "span"—the difference between the maximum and minimum values—of the discounted-reward version of the problem remains bounded as the discount factor approaches 1, a solution to the average-reward Bellman equation must exist. This provides a mathematical bridge between the well-understood discounted setting and the more elusive average-reward setting.

Information Asymmetry and Policy Complexity

A significant portion of the analysis focuses on information asymmetry. The authors explore scenarios where the controller can utilize "history-dependent" policies (incorporating past observations), while the adversary is restricted to "stationary" policies (relying only on the current state). This distinction is crucial, as robust MDPs often require the controller to use randomized strategies to mitigate exploitation by an adversary who might otherwise predict and counter deterministic behavior.

Key Theoretical Insights

The Constant-Gain Bridge

The paper identifies that under weak communication conditions, the optimal average reward is independent of the starting state. This allows for the formulation of a "constant-gain" Bellman equation. Such an equation is considered the "Holy Grail" for designing efficient algorithms, as it simplifies the optimization objective across the entire state space.

S-Rectangularity

The proofs rely heavily on "S-rectangular" ambiguity sets. This assumption implies that the adversary's choices at one state do not restrict their choices at another. While this preserves the mathematical tractability of the model, it also ensures that the robust optimization problem remains solvable through dynamic programming.

Learning the Adversary

In Section 6, the authors present a compelling insight: if a controller is history-dependent and the adversary is stationary, the controller can essentially "learn" the adversary's strategy over time. This creates an information advantage where the controller can achieve a higher reward than the standard Bellman equation would otherwise predict. This is illustrated through a variant of the "Big Match" game, a 3-state counter-example demonstrating that stationary policies can fail to be optimal under asymmetric information.

Principal Results

  1. Existence Theorems: The paper provides definitive sufficient conditions (Theorems 5 and 6) for the existence of a solution to the robust average-reward Bellman equation based on the communication structure of the environment.
  2. Optimality Certification: Theorem 3 proves that any stationary policy derived from the robust Bellman equation is $\epsilon$-optimal for the long-run average reward.
  3. Duality and Nash Equilibrium: The authors establish conditions under which "strong duality" holds. This means the order of play (whether the controller or adversary moves first) does not change the optimal value, leading to a stable Nash Equilibrium.

Conclusion and Future Directions

This work provides the necessary theoretical scaffolding for average-reward RMDPs, yet several avenues for future research remain. Currently, the theory is limited to finite state and action spaces; extending these results to continuous spaces, such as those found in robotics, would involve significant measure-theoretic challenges. Additionally, while S-rectangular sets are tractable, they can be overly conservative. Exploring non-rectangular sets remains an open problem. Finally, while this paper establishes that solutions exist, the development of specific, high-efficiency algorithms (such as Robust Value Iteration) for large-scale applications is the next logical step in this research trajectory.

Summary updated

BibTeX
@inproceedings{wang2025bellman,
  author = {Shengbo Wang and Nian Si},
  title = {{Bellman Optimality of Average-Reward Robust Markov Decision Processes with a Constant Gain}},
  booktitle = {MLxOR @ NeurIPS},
  year = {2025},
  url = {https://openreview.net/forum?id=D8TYyKjCnK},
}
Figure