Research map / Learning theory and algorithms / Submodular and game algorithms
Roping in Uncertainty: Robustness and Regularization in Markov Games
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that computing a robust Nash equilibrium of s-rectangular robust Markov games is equivalent to computing a Nash equilibrium of a regularized Markov game, proves PPAD-hardness for general zero-sum robust matrix games, and identifies an efficiently player-decomposable class solvable in polynomial time.
Problem
Computing robust Nash equilibria (MPRNE) of robust Markov games with s-rectangular uncertainty, and understanding when regularization yields robustness in multi-agent settings.
Approach
The robust value under s-rectangular reward or transition uncertainty equals the value of a regularized MG whose regularizer is the support function of the uncertainty set; hence RNE equals NE of that regularized game. Zero-sum robust games are polynomial-time solvable when the support function splits into separate per-player terms (efficient player-decomposability).
Key results
- Theorem: an MPRNE of an s-rectangular RMG is exactly an MPNE of an appropriately constructed regularized MG, for reward and transition uncertainty.
- Computing an RNE of a two-player zero-sum robust matrix game with (s,a)-rectangular reward uncertainty is PPAD-hard even for H=S=1.
- Two-player zero-sum RMGs with efficiently player-decomposable reward uncertainty (including L1 and L_infinity balls) can be solved in polynomial time.
Surprising findings
- Even two-player zero-sum robust matrix games with (s,a)-rectangular reward uncertainty are PPAD-hard, unlike classical zero-sum games solvable by LP.
- Transition uncertainty with (s,a)-rectangularity and H=2 is also PPAD-hard for zero-sum RMGs.
Limitations
- General zero-sum robust games are PPAD-hard; efficient solvability requires the player-decomposability assumption.
- Purely theoretical; no experiments reported in the excerpt.
Experimental setup
Builds on: robust MDP s-rectangularity Fenchel-Rockafellar duality Kakutani fixed point theorem
Closest papers by meaning
- Robust Equilibria in Continuous Games: From Strategic to Dynamic Robustness (NeurIPS 2025 · similarity 0.90)
- Robust PAC Learning of Concurrent Stochastic Games (NeurIPS 2026 · similarity 0.88)
- Playing Markov Games Without Observing Payoffs (NeurIPS 2026 · similarity 0.88)
- Breaking the Curse of Multiagency in Robust Multi-Agent Reinforcement Learning (ICML 2025 · similarity 0.88)
- Solving Robust Markov Decision Processes: Generic, Reliable, Efficient (AAAI 2025 · similarity 0.88)
- Solving Zero-Sum Convex Markov Games (ICML 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.