Roping in Uncertainty: Robustness and Regularization in Markov Games

Jeremy Mcmahan, Giovanni Artiglio, Qiaomin Xie
Proceedings of the 41st International Conference on Machine Learning, PMLR 235:35267-35295, 2024.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v235-mcmahan24a, title = {Roping in Uncertainty: Robustness and Regularization in {M}arkov Games}, author = {Mcmahan, Jeremy and Artiglio, Giovanni and Xie, Qiaomin}, booktitle = {Proceedings of the 41st International Conference on Machine Learning}, pages = {35267--35295}, year = {2024}, editor = {Salakhutdinov, Ruslan and Kolter, Zico and Heller, Katherine and Weller, Adrian and Oliver, Nuria and Scarlett, Jonathan and Berkenkamp, Felix}, volume = {235}, series = {Proceedings of Machine Learning Research}, month = {21--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v235/main/assets/mcmahan24a/mcmahan24a.pdf}, url = {https://proceedings.mlr.press/v235/mcmahan24a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Roping in Uncertainty: Robustness and Regularization in Markov Games %A Jeremy Mcmahan %A Giovanni Artiglio %A Qiaomin Xie %B Proceedings of the 41st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2024 %E Ruslan Salakhutdinov %E Zico Kolter %E Katherine Heller %E Adrian Weller %E Nuria Oliver %E Jonathan Scarlett %E Felix Berkenkamp %F pmlr-v235-mcmahan24a %I PMLR %P 35267--35295 %U https://proceedings.mlr.press/v235/mcmahan24a.html %V 235 %X 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.
APA
Mcmahan, J., Artiglio, G. & Xie, Q.. (2024). Roping in Uncertainty: Robustness and Regularization in Markov Games. Proceedings of the 41st International Conference on Machine Learning, in Proceedings of Machine Learning Research 235:35267-35295 Available from https://proceedings.mlr.press/v235/mcmahan24a.html.

Related Material