mlsanityData to 7 Oct 2026

Roping in Uncertainty: Robustness and Regularization in Markov Games

arXiv 2406.08847 ↗First posted 13 Jun 2024cs.GT cs.DS cs.LGcited by 5

Not on the map. Why?

Abstract (arXiv)

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

Key facts. Cited by 5 papers in the map (data through 7 Oct 2026). Builds on 22 of its 51 references that are in the map. First posted on arXiv 13 Jun 2024.

Builds on

22 of 51 references.

References · 22

  1. 2017Proximal Policy Optimization Algorithmscited by 14,441
  2. 2017Robust Adversarial Reinforcement Learningcited by 439
  3. 2019A Theory of Regularized Markov Decision Processescited by 279
  4. 2021Maximum Entropy RL (Provably) Solves Some Robust RL Problemscited by 169
  5. 2021Online Robust Reinforcement Learning with Model Uncertaintycited by 95
  6. 2020Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexitycited by 91
  7. 2022Distributionally Robust Model-Based Offline Reinforcement Learning with Near-Optimal Sample Complexitycited by 85
  8. 2021Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergencecited by 83
  9. 2021Sample Complexity of Robust Reinforcement Learning with a Generative Modelcited by 82
  10. 2022Policy Gradient Method For Robust Reinforcement Learningcited by 67
  11. 2021Fast Policy Extragradient Methods for Competitive Games with Entropy Regularizationcited by 61
  12. 2023Double Pessimism is Provably Efficient for Distributionally Robust Offline Reinforcement Learning: Generic Algorithm and Robust Partial Coveragecited by 51
10 more
  1. 2023The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Modelcited by 50
  2. 2020Partial Policy Iteration for L1-Robust Markov Decision Processescited by 49
  3. 2021Twice regularized MDPs and the equivalence between robustness and regularizationcited by 46
  4. 2017Sparse Markov Decision Processes with Causal Sparse Tsallis Entropy Regularization for Reinforcement Learningcited by 36
  5. 2022Policy Gradient in Robust MDPs with Global Convergence Guaranteecited by 35
  6. 2021Regularized Policies are Reward Robustcited by 32
  7. 2022Distributionally Robust Offline Reinforcement Learning with Linear Function Approximationcited by 31
  8. 2022Your Policy Regularizer is Secretly an Adversarycited by 21
  9. 2022Efficient Policy Iteration for Robust Markov Decision Processes via Regularizationcited by 19
  10. 2016The role of convexity on saddle-point dynamics: Lyapunov function and robustnesscited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 1; 2025: 0; 2026: 4.

5 papers.

  1. 2024Tractable Equilibrium Computation in Markov Games through Risk Aversioncited by 3
  2. 2026Strategically Robust Multi-Agent Reinforcement Learning with Linear Function Approximationcited by 0
  3. 2026Online Security Learning in Cooperative Multi-Agent Systems under Hidden Byzantine Attackscited by 0
  4. 2026Social Laws for Multi-agent Coordination in Stochastic Environmentscited by 0
  5. 2026Robust Nash Alignment under Preference Uncertaintycited by 0