mlsanityData to 7 Oct 2026

Decentralized Optimistic Hyperpolicy Mirror Descent: Provably No-Regret Learning in Markov Games

arXiv 2206.01588 ↗First posted 3 Jun 2022cs.LG stat.MLcited by 11

Not on the map. Why?

Abstract (arXiv)

We study decentralized policy learning in Markov games where we control a single agent to play with nonstationary and possibly adversarial opponents. Our goal is to develop a no-regret online learning algorithm that (i) takes actions based on the local information observed by the agent and (ii) is able to find the best policy in hindsight. For such a problem, the nonstationary state transitions due to the varying opponent pose a significant challenge. In light of a recent hardness result citepliu2022learning, we focus on the setting where the opponent's previous policies are revealed to the agent for decision making. With such an information structure, we propose a new algorithm, underlineDecentralized underlineOptimistic hypeunderlineRpolicy munderlineIrror deunderlineScent (DORIS), which achieves √K-regret in the context of general function approximation, where K is the number of episodes. Moreover, when all the agents adopt DORIS, we prove that their mixture policy constitutes an approximate coarse correlated equilibrium. In particular, DORIS maintains a textithyperpolicy which is a distribution over the policy space. The hyperpolicy is updated via mirror descent, where the update direction is obtained by an optimistic variant of least-squares policy evaluation. Furthermore, to illustrate the power of our method, we apply DORIS to constrained and vector-valued MDPs, which can be formulated as zero-sum Markov games with a fictitious opponent.

Key facts. Cited by 11 papers in the map (data through 7 Oct 2026). Builds on 36 of its 59 references that are in the map. First posted on arXiv 3 Jun 2022.

Builds on

36 of 59 references.

References · 36

  1. 2013Playing Atari with Deep Reinforcement Learningcited by 3,211
  2. 2019Dota 2 with Large Scale Deep Reinforcement Learningcited by 1,084
  3. 2019Introduction to Online Convex Optimizationcited by 793
  4. 2018QMIX: Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learningcited by 697
  5. 2019Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithmscited by 555
  6. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  7. 2016Safe, Multi-Agent, Reinforcement Learning for Autonomous Drivingcited by 301
  8. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  9. 2021Bellman-consistent Pessimism for Offline Reinforcement Learningcited by 267
  10. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
  11. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 176
  12. 2018A Survey and Critique of Multiagent Deep Reinforcement Learningcited by 173
24 more
  1. 2020Exploration-Exploitation in Constrained MDPscited by 146
  2. 2019Constrained Reinforcement Learning Has Zero Duality Gapcited by 144
  3. 2020Provably Efficient Safe Exploration via Primal-Dual Policy Optimizationcited by 131
  4. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  5. 2020Provable Self-Play Algorithms for Competitive Reinforcement Learningcited by 112
  6. 2019Optimism in Reinforcement Learning with Generalized Linear Function Approximationcited by 111
  7. 2021V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RLcited by 111
  8. 2020Near-Optimal Reinforcement Learning with Self-Playcited by 108
  9. 2020Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibriumcited by 100
  10. 2021Independent Policy Gradient Methods for Competitive Reinforcement Learningcited by 97
  11. 2021Global Convergence of Multi-Agent Policy Gradient in Markov Potential Gamescited by 89
  12. 2021Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPscited by 78
  13. 2017Online Reinforcement Learning in Stochastic Gamescited by 67
  14. 2021Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Gamescited by 66
  15. 2019Reinforcement Learning with Convex Constraintscited by 57
  16. 2022Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergencecited by 54
  17. 2021Decentralized Q-Learning in Zero-sum Markov Gamescited by 53
  18. 2021The Power of Exploiter: Provable Multi-Agent RL in Large State Spacescited by 48
  19. 2021Towards General Function Approximation in Zero-Sum Markov Gamescited by 42
  20. 2021On Improving Model-Free Algorithms for Decentralized Multi-Agent Reinforcement Learningcited by 35
  21. 2021A Simple Reward-free Approach to Constrained Reinforcement Learningcited by 28
  22. 2021Provably Efficient Algorithms for Multi-Objective Competitive RLcited by 20
  23. 2021A Provably-Efficient Model-Free Algorithm for Constrained Markov Decision Processescited by 17
  24. 2022Learning Markov Games with Adversarial Opponents: Efficient Algorithms and Fundamental Limitscited by 17

Built on by

Cited by year (2026 to 7 Oct)

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

11 papers.

  1. 2023Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximationcited by 29
  2. 2022Regret Minimization and Convergence to Equilibria in General-sum Markov Gamescited by 22
  3. 2022Strategic Decision-Making in the Presence of Information Asymmetry: Provably Efficient RL with Algorithmic Instrumentscited by 9
  4. 2023Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Gamescited by 9
  5. 2025Multi-Objective Reinforcement Learning with Max-Min Criterion: A Game-Theoretic Approachcited by 5
  6. 2024Refined Sample Complexity for Markov Games with Independent Linear Function Approximationcited by 3
  7. 2023Posterior Sampling for Competitive RL: Function Approximation and Partial Observationcited by 2
  8. 2023Sample-Efficient Multi-Agent RL: An Optimization Perspectivecited by 1
  9. 2023Improving Sample Efficiency of Model-Free Algorithms for Zero-Sum Markov Gamescited by 0
  10. 2026Cooperative Multi-agent RL with Communication Constraintscited by 0
  11. 2026Taming the Curses of Multiagency in Robust Markov Games with Large State Space through Linear Function Approximationcited by 0