Roping in Uncertainty: Robustness and Regularization in Markov Games
This work addresses robustness in multi-agent decision-making under uncertainty, providing theoretical insights and efficient solutions for specific cases, though it is incremental in extending existing regularization methods.
The paper tackles robust Markov games with s-rectangular uncertainty by showing an equivalence between computing robust Nash equilibria and regularized Nash equilibria, leading to planning algorithms and robustness guarantees, but proves PPAD-hardness for general cases and identifies a polynomial-time solvable class including L1 and L∞ ball uncertainty sets.
We study robust Markov games (RMG) with $s$-rectangular uncertainty. We show a general equivalence between computing a robust Nash equilibrium (RNE) of a $s$-rectangular RMG and computing a Nash equilibrium (NE) of an appropriately constructed regularized MG. The equivalence result yields a planning algorithm for solving $s$-rectangular RMGs, as well as provable robustness guarantees for policies computed using regularized methods. However, we show that even for just reward-uncertain two-player zero-sum matrix games, computing an RNE is PPAD-hard. Consequently, we derive a special uncertainty structure called efficient player-decomposability and show that RNE for two-player zero-sum RMG in this class can be provably solved in polynomial time. This class includes commonly used uncertainty sets such as $L_1$ and $L_\infty$ ball uncertainty sets.