💻 computer science

Distributionally Robust Markov Games with Average Reward

This paper establishes the theoretical existence of stationary Nash equilibria for distributionally robust Markov games under both irreducible and weakly communicating settings with average-reward criteria, while proposing convergent algorithms and demonstrating their approximation via discounted counterparts.

Original authors: Zachary Roch, Yue Wang

Published 2026-06-23

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Zachary Roch, Yue Wang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a group of friends trying to navigate a maze together. In a perfect world, they know exactly where every wall is and where every door leads. But in the real world, the map they have might be slightly wrong. Maybe a wall moved, or a door is jammed. This is the problem of model mismatch: the plan they made doesn't match the reality they are actually in.

This paper introduces a new way for these friends to make decisions that works even when their map is wrong, and when they are playing for a very long time (not just a quick race).

Here is the breakdown of their solution using simple analogies:

1. The Problem: "What If the Map is Wrong?"

Usually, when people teach computers to play games or make decisions (like robots in a warehouse or cars on a highway), they assume the rules are fixed. But in reality, things change.

The Old Way: Most previous methods focused on short-term goals (like "get to the exit in 10 steps") or used a "discount" (valuing a reward today more than a reward tomorrow). This is like a runner sprinting for a short race; they don't care about the long-term wear and tear on their shoes.
The New Challenge: The authors wanted to solve the Average Reward problem. This is like a marathon runner who needs to maintain a steady, sustainable pace forever. They care about the average speed over the whole race, not just the first mile.
The Twist: They also wanted to be Distributionally Robust. This means the players assume the "worst-case scenario" for the map. They don't just hope the map is right; they plan as if a mischievous "gremlin" is constantly trying to change the walls to make their life as hard as possible.

2. The Big Hurdle: "The Maze is Too Complicated"

The authors explain that mixing "long-term average goals" with "worst-case planning" is incredibly hard.

The Analogy: Imagine trying to find the best path in a maze where the walls move every time you take a step, and you have to keep walking forever. In simpler games (short races), you can work backward from the finish line. But in an endless marathon, there is no finish line to work backward from.
The Discovery: They proved that without certain rules (like the maze being "connected" so you can get from any room to any other room), a perfect, stable strategy might not even exist. It's like trying to find a single "best move" in a game where the rules change so wildly that no move is ever truly safe.

3. The Solution: Finding a "Stable Agreement"

The paper proves that if the environment is "well-connected" (you can eventually get anywhere), there does exist a Nash Equilibrium.

What is a Nash Equilibrium? Think of it as a "stable truce." It's a set of strategies where no single player can improve their average score by changing their own plan, assuming everyone else sticks to theirs. Even with the worst-case map changes, everyone agrees on a strategy that is the best they can do given the chaos.
The Breakthrough: The authors showed how to mathematically prove this agreement exists, even when the "gremlin" is trying to break the game. They did this by creating a special equation (a "Bellman equation") that balances the immediate reward against the long-term average, accounting for the worst-case map changes.

4. The Tools: Two New Algorithms

To actually find this "stable truce," the authors built two new tools (algorithms):

Tool A: Robust Nash-Iteration (The "Iterative Negotiation")
- How it works: Imagine the players sitting around a table. They take turns saying, "If you all stick to your current plan, here is the best move for me." They keep updating their plans based on what the others are doing.
- The Catch: This method works perfectly but requires a "super-computer" to solve a complex math puzzle at every single step. It's like needing a genius mathematician to solve a Sudoku puzzle every time you take a step in the maze.
Tool B: Robust TD Descent (The "Smoothed Climb")
- How it works: This is a smarter, more practical method. Instead of solving a hard puzzle every time, the players take small steps downhill on a "happiness hill." They measure how "wrong" their current plan is (the error) and gently nudge their strategy to reduce that error.
- The Trick: Because the math is jagged and bumpy (due to the worst-case planning), they "smoothed out" the hill first, like sanding down a rough piece of wood. This allows them to slide down to the best solution without getting stuck on a bump. This method is much faster and doesn't need a super-computer.

5. The Bridge: Connecting Short and Long

Finally, the authors showed a clever shortcut.

The Analogy: They proved that if you play the game with a "discount" (valuing the present slightly more than the future) but make that discount factor extremely close to 1 (meaning you care almost exactly as much about the future as the present), you get almost the same result as the perfect long-term average plan.
Why it matters: This means we can use existing, well-understood tools designed for short-term games to approximate the solution for these complex, long-term, worst-case scenarios. It's like using a standard compass to navigate a marathon if you just adjust the needle slightly.

Summary

In short, this paper provides a mathematical guarantee and a practical toolkit for groups of agents (like robots or AI) to cooperate or compete effectively over the long haul, even when they don't know the exact rules of the game and expect the environment to try to trick them. They proved a stable solution exists and gave two ways to find it: one precise but heavy, and one practical and smooth.

Technical Summary: Distributionally Robust Markov Games with Average Reward

Problem Formulation

This paper addresses the challenge of multi-agent decision-making in environments characterized by model uncertainty and extended operational horizons. While Markov Games (MGs) provide a framework for competitive multi-agent systems, standard formulations often fail to account for the "Sim-to-Real" gap, where the assumed transition model diverges from the true environment due to non-stationarity, modeling errors, or adversarial disturbances.

To mitigate this, the authors study Distributionally Robust Markov Games (DR-MGs), where agents optimize for the worst-case performance over a predefined uncertainty set of transition kernels. Crucially, this work focuses on the average-reward criterion rather than the more commonly studied finite-horizon or discounted-reward settings. The average-reward criterion is essential for systems operating over indefinite time horizons (e.g., warehouse robotics, communication networks), yet it presents significant theoretical hurdles:

Failure of Min-Max Duality: In robust settings, the worst-case transition kernel for one agent may differ from that of another, breaking the saddle-point structure even in zero-sum games.
Structural Complexity: Unlike discounted settings, the correspondence between stationary policies and state-action frequencies breaks down in average-reward settings without restrictive structural assumptions.
Lack of Existing Solutions: Prior methods for discounted DR-MGs or non-robust average-reward MGs cannot be directly extended to the robust average-reward setting due to the non-contraction of Bellman operators and the non-uniqueness of solutions.

The paper demonstrates that without structural assumptions, average-reward DR-MGs may not admit a stationary Nash Equilibrium (NE), as shown by a constructed counterexample of a two-player zero-sum game.

Methodology

1. Theoretical Foundations: Existence of Equilibrium

The authors establish the existence of a stationary robust Nash Equilibrium under two distinct structural assumptions:

Irreducible Setting: Assuming that for any stationary joint policy and any admissible kernel, the induced Markov chain is irreducible (all states belong to a single recurrent class).
- The authors derive a correspondence between optimal policies and the solutions of the robust Bellman equation.
- They prove that the robust Bellman equation admits a unique solution (up to a constant vector) for the gain and bias.
- Using these results, they show that the best-response mapping is non-empty, convex, and upper semi-continuous. By applying the Kakutani fixed-point theorem, they prove the existence of a stationary robust NE.
Weakly Communicating Setting: A more general setting where the state space can be decomposed into transient states and a union of recurrent classes.
- In this setting, the direct correspondence between policies and Bellman solutions fails.
- The authors construct a proxy set-valued map based on the constant-gain optimal robust Bellman operator.
- They prove this proxy map is a subset of the true best-response mapping and satisfies the conditions for the Kakutani fixed-point theorem, thereby establishing the existence of a stationary robust NE even in this broader context.

2. Algorithmic Solutions

The paper proposes two algorithms to compute the robust NE:

Robust Nash-Iteration: An extension of standard Nash value iteration. It maintains bias estimates and solves for a Nash Equilibrium of a stage game defined by robust Q-values at each step.
- Convergence: Proven to converge to a robust NE under the irreducible assumption and an additional assumption regarding the selection of stage-game equilibria (e.g., global optimality or saddle-point selection).
- Limitation: Requires an oracle to compute the NE of the stage game, which is PPAD-complete in general-sum settings.
Robust TD Descent: A two-time-scale actor-critic algorithm designed to bypass the need for an NE oracle.
- Mechanism: It characterizes the robust NE via the minimization of a global robust Temporal Difference (TD) gap. The algorithm minimizes a smoothed version of this gap (using a Moreau envelope) to handle non-smoothness.
- Convergence: The algorithm is proven to weakly converge to a stationary point of the smoothed objective. While it does not guarantee convergence to the exact NE without further assumptions (like local gradient domination), it provides the first provably convergent method for average-reward DR-MGs that does not rely on an NE oracle.

3. Connection to Discounted Equilibria

The authors establish a theoretical bridge between average-reward and discounted DR-MGs. They prove that as the discount factor $\gamma \to 1$ , the robust NE of the discounted game converges to the robust NE of the average-reward game. This allows for the approximation of the challenging average-reward problem using the more tractable discounted formulations.

Key Results

Existence of NE: The paper proves the existence of a stationary robust Nash Equilibrium for average-reward DR-MGs under both irreducible and weakly communicating assumptions, addressing a fundamental solvability question left open in prior literature.
Solvability of Robust Bellman Equations: The authors provide foundational results on the solvability and uniqueness (up to constants) of the robust Bellman equation for average-reward MDPs, correcting previous gaps in the literature.
Convergent Algorithms: Two algorithms are introduced. The Robust Nash-Iteration offers convergence under specific structural assumptions, while the Robust TD Descent offers a practical, oracle-free approach with provable convergence to stationary points.
Approximation via Discounting: The paper validates that average-reward equilibria can be effectively approximated by discounted equilibria with sufficiently large discount factors, offering a practical computational pathway.

Significance and Claims

The paper claims to provide a comprehensive theoretical and algorithmic foundation for decision-making in complex, uncertain, and long-running multi-player environments. Specifically:

It resolves the fundamental question of whether robust equilibria exist in average-reward multi-agent settings, a problem where standard techniques fail.
It introduces the first algorithms with provable convergence guarantees for solving average-reward DR-MGs, moving beyond the limitations of discounted or finite-horizon approximations.
It highlights the necessity of structural assumptions (irreducibility or weak communication) for the existence of stationary equilibria, demonstrating through counterexamples that such assumptions are not merely technical but essential.

The authors note that while their framework provides a strong foundation, finding exact equilibria in general-sum games remains challenging, and their TD-based algorithm converges to stationary points which serve as a necessary first step toward finding exact robust NEs. Future work is suggested to explore local gradient domination for stronger convergence guarantees and to extend the framework beyond $(s, a)$ -rectangular uncertainty sets.