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.

For complex, interactive systems such as algorithmic trading in financial markets, warehouse robots, or a fleet of self-driving cars, multiple independent players must repeatedly make decisions that lead to sustained, positive performance for their respective objectives. But how many independent decision makers all operate in the same unpredictable environment, and how do their interactions affect each other? While artificial intelligence can learn effective strategies in isolated, simulated environments, deploying multiple players or "agents" on real-world problems often leads to a severe degradation in performance. This phenomenon can stem from many different causes, but at it's core, this discrepancy in performance is due to the sheer complexity encountered by the unpredictability of dynamic real-world situations when compared to the training environment. When multiple agents are involved, even a small modeling error can result in a severe performance drop as this error is aggressively compounded by the many agents all reacting to each other and the constraints set forth by their environment over a sustained period of time (e.g., a fleet of fully-autonomous cars in heavy traffic might overreact to a simple lane change by a single vehicle by slamming on their breaks, causing an unnecessary back-up of traffic or collision). To mitigate this problem and ensure the reliability of the many independent players, we must design strategies that are robust to this mismatch between the simulator and target environment. This means that a baseline level (or average) of performance must be guaranteed, even when the real-world environment deviates significantly from the training environment. However, finding a stable, long-term compromise (optimal joint strategy) amongst an arbitrary number of agents is notoriously difficult to prove mathematically for long time-horizons. The goal here is to find an optimal joint arrangement among all players so that there is not an incentive for any single player to act alone. However, the current models used to plan such strategies never match reality, so plans that look good on paper can fail when conditions shift. Our work solves this problem by formally proving that such a robust, long-term agreement among all players always exists given certain conditions. These strategies stay reliable even under the worst plausible version of the environment, favoring the optimization of long-run average performance rather than chasing quick payoffs. To facilitate these theoretical findings into application, we design practical algorithms that find this optimal strategy without requiring unrealistic constraints or assumptions about the environment. Finally, we provide a bridge showing that we can approximate this optimal agreement among players by employing simpler, well-understood methods. Ultimately, this work provides a comprehensive foundation for safely deploying competitive multi-player AI in highly uncertain and long-running real-world scenarios.