Roping in Uncertainty: Robustness and Regularization in Markov Games

2024-06-13 · Jeremy McMahan, Giovanni Artiglio, Qiaomin Xie

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.

📄 PDF Abstract BibTeX arXiv:2406.08847

Code (0)

등록된 구현이 없습니다.

Achieving Logarithmic Regret in KL-Regularized Zero-Sum Markov Games

2025-10-15 · Anupam Nayak, Tong Yang, Osman Yagan, Gauri Joshi 외 arxiv

Reverse Kullback-Leibler (KL) divergence-based regularization with respect to a fixed reference policy is widely used in modern reinforcement learning to preserve the desired traits of the reference policy and sometimes …

Reinforcement Learning

Taming the Curses of Multiagency in Robust Markov Games with Large State Space through Linear Function Approximation

2026-05-04 · Jingchu Gai, Laixi Shi arxiv

Multi-agent reinforcement learning (MARL) holds great potential but faces robustness challenges due to environmental uncertainty. To address this, distributionally robust Markov games (RMGs) optimize worst-case performan…

Multi-agent Reinforcement Learning

Distributional Robustness and Regularization in Reinforcement Learning

2020-03-05 · Esther Derman, Shie Mannor

Distributionally Robust Optimization (DRO) has enabled to prove the equivalence between robustness and regularization in classification and regression, thus providing an analytical reason why regularization generalizes w…

Decision Making reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)+1

Formalizing the Problem of Side Effect Regularization

2022-06-23 · Alexander Matt Turner, Aseem Saxena, Prasad Tadepalli

AI objectives are often hard to specify properly. Some approaches tackle this problem by regularizing the AI's side effects: Agents must weigh off "how much of a mess they make" with an imperfectly specified proxy object…

Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedback

2023-03-05 · NeurIPS 2023 11

We revisit the problem of learning in two-player zero-sum Markov games, focusing on developing an algorithm that is uncoupled, convergent, and rational, with non-asymptotic convergence rates. We start from the case of st…