mlsanityData to 14 Oct 2026

Learning Markov Games with Adversarial Opponents: Efficient Algorithms and Fundamental Limits

arXiv 2203.06803 ↗First posted 14 Mar 2022cs.LG cs.AI stat.MLcited by 17

Not on the map. Why?

Abstract (arXiv)

An ideal strategy in zero-sum games should not only grant the player an average reward no less than the value of Nash equilibrium, but also exploit the (adaptive) opponents when they are suboptimal. While most existing works in Markov games focus exclusively on the former objective, it remains open whether we can achieve both objectives simultaneously. To address this problem, this work studies no-regret learning in Markov games with adversarial opponents when competing against the best fixed policy in hindsight. Along this direction, we present a new complete set of positive and negative results: When the policies of the opponents are revealed at the end of each episode, we propose new efficient algorithms achieving √K-regret bounds when either (1) the baseline policy class is small or (2) the opponent's policy class is small. This is complemented with an exponential lower bound when neither conditions are true. When the policies of the opponents are not revealed, we prove a statistical hardness result even in the most favorable scenario when both above conditions are true. Our hardness result is much stronger than the existing hardness results which either only involve computational hardness, or require further restrictions on the algorithms.

Key facts. Cited by 17 papers in the map (data through 14 Oct 2026). Builds on 19 of its 42 references that are in the map. First posted on arXiv 14 Mar 2022.

Builds on

19 of 42 references.

References · 19

  1. 2019Emergent Tool Use From Multi-Agent Autocurriculacited by 313
  2. 2016Safe, Multi-Agent, Reinforcement Learning for Autonomous Drivingcited by 311
  3. 2020Provable Self-Play Algorithms for Competitive Reinforcement Learningcited by 113
  4. 2020Near-Optimal Reinforcement Learning with Self-Playcited by 109
  5. 2020A Sharp Analysis of Model-based Reinforcement Learning with Self-Playcited by 105
  6. 2020Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibriumcited by 100
  7. 2019Learning Adversarial MDPs with Bandit Feedback and Unknown Transitioncited by 85
  8. 2019Online Convex Optimization in Adversarial Markov Decision Processescited by 79
  9. 2020Optimistic Policy Optimization with Bandit Feedbackcited by 79
  10. 2021RL for Latent MDPs: Regret Guarantees and a Lower Boundcited by 70
  11. 2017Online Reinforcement Learning in Stochastic Gamescited by 67
  12. 2020Sample-Efficient Reinforcement Learning of Undercomplete POMDPscited by 66
7 more
  1. 2020Faster Game Solving via Predictive Blackwell Approachability: Connecting Regret Matching and Mirror Descentcited by 57
  2. 2016Reinforcement Learning of POMDPs using Spectral Methodscited by 52
  3. 2021The Power of Exploiter: Provable Multi-Agent RL in Large State Spacescited by 48
  4. 2021Model-Free Learning for Two-Player Zero-Sum Partially Observable Markov Games with Perfect Recallcited by 21
  5. 2013Online Learning in Markov Decision Processes with Adversarially Chosen Transition Probability Distributionscited by 18
  6. 2021Model-Free Online Learning in Unknown Sequential Decision Making Problems and Gamescited by 12
  7. 2020Linear Last-iterate Convergence in Constrained Saddle-point Optimizationcited by 5

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 7; 2023: 5; 2024: 1; 2025: 1; 2026: 3.

17 papers.

Sort:

By area:

  1. 2022On the Complexity of Adversarial Decision Makingcited by 33
  2. 2023Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximationcited by 30
  3. 2022Sample-Efficient Reinforcement Learning of Partially Observable Markov Gamescited by 27
  4. 2022Regret Minimization and Convergence to Equilibria in General-sum Markov Gamescited by 24
  5. 2022Policy Optimization for Markov Games: Unified Framework and Faster Convergencecited by 16
  6. 2022Decentralized Optimistic Hyperpolicy Mirror Descent: Provably No-Regret Learning in Markov Gamescited by 12
  7. 2023Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Gamescited by 10
  8. 2022Strategic Decision-Making in the Presence of Information Asymmetry: Provably Efficient RL with Algorithmic Instrumentscited by 9
  9. 2022A Survey of Decision Making in Adversarial Gamescited by 3
  10. 2023Posterior Sampling for Competitive RL: Function Approximation and Partial Observationcited by 3
  11. 2024Learning in Markov Games with Adaptive Adversaries: Policy Regret, Fundamental Barriers, and Efficient Algorithmscited by 3
  12. 2023Learning in Zero-Sum Markov Games: Relaxing Strong Reachability and Mixing Time Assumptionscited by 2
5 more
  1. 2026Online Learning for Uninformed Markov Games: Empirical Nash-Value Regret and Non-Stationarity Adaptationcited by 1
  2. 2023Decentralized model-free reinforcement learning in stochastic games with average-reward objectivecited by 0
  3. 2025Playing Markov Games Without Observing Payoffscited by 0
  4. 2026Minimax-Optimal Policy Regret in Partially Observable Markov Gamescited by 0
  5. 2026Online Security Learning in Cooperative Multi-Agent Systems under Hidden Byzantine Attackscited by 0