Roping in Uncertainty: Robustness and Regularization in Markov Games
<|reference_start|>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_1$ and $L_\infty$ ball uncertainty sets.<|reference_end|>
@article{mcmahan2024roping,
    title={Roping in Uncertainty: Robustness and Regularization in Markov Games},
    author={Jeremy McMahan, Giovanni Artiglio, Qiaomin Xie},
    journal={arXiv preprint arXiv:2406.08847},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.08847},
    primaryClass={cs.GT cs.DS cs.LG}
}