Roping in Uncertainty: Robustness and Regularization in Markov Games

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₁ and L_∞ ball uncertainty sets.