mlsanityData to 7 Oct 2026

Local and adaptive mirror descents in extensive-form games

arXiv 2309.00656 ↗First posted 1 Sep 2023cs.GT cs.LG stat.MLcited by 2

Not on the map. Why?

Abstract (arXiv)

We study how to learn ε-optimal strategies in zero-sum imperfect information games (IIG) with trajectory feedback. In this setting, players update their policies sequentially based on their observations over a fixed number of episodes, denoted by T. Existing procedures suffer from high variance due to the use of importance sampling over sequences of actions (Steinberger et al., 2020; McAleer et al., 2022). To reduce this variance, we consider a fixed sampling approach, where players still update their policies over time, but with observations obtained through a given fixed sampling policy. Our approach is based on an adaptive Online Mirror Descent (OMD) algorithm that applies OMD locally to each information set, using individually decreasing learning rates and a regularized loss. We show that this approach guarantees a convergence rate of tildeO(T-1/2) with high probability and has a near-optimal dependence on the game parameters when applied with the best theoretical choices of learning rates and sampling policies. To achieve these results, we generalize the notion of OMD stabilization, allowing for time-varying regularization with convex increments.

Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 30 of its 69 references that are in the map. First posted on arXiv 1 Sep 2023.

Builds on

30 of 69 references.

References · 30

  1. 2017Training GANs with Optimismcited by 217
  2. 2019OpenSpiel: A Framework for Reinforcement Learning in Gamescited by 180
  3. 2020Near-Optimal Reinforcement Learning with Self-Playcited by 108
  4. 2020A Sharp Analysis of Model-based Reinforcement Learning with Self-Playcited by 104
  5. 2020Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibriumcited by 100
  6. 2021Independent Policy Gradient Methods for Competitive Reinforcement Learningcited by 97
  7. 2020Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexitycited by 91
  8. 2016Scale-Free Online Learningcited by 83
  9. 2014Solving Large Imperfect Information Games Using CFR+cited by 78
  10. 2017Online Reinforcement Learning in Stochastic Gamescited by 67
  11. 2021Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Gamescited by 66
  12. 2020Faster Game Solving via Predictive Blackwell Approachability: Connecting Regret Matching and Mirror Descentcited by 56
18 more
  1. 2019Solving Discounted Stochastic Two-Player Games with Near-Optimal Time and Sample Complexitycited by 41
  2. 2020DREAM: Deep Regret minimization with Advantage baselines and Model-free learningcited by 36
  3. 2021Last-iterate Convergence in Extensive-Form Gamescited by 27
  4. 2022Near-Optimal Learning of Extensive-Form Games with Imperfect Informationcited by 26
  5. 2019Optimistic Regret Minimization for Extensive-Form Games via Dilated Distance-Generating Functionscited by 25
  6. 2018Variance Reduction in Monte Carlo Counterfactual Regret Minimization (VR-MCCFR) for Extensive Form Games using Baselinescited by 24
  7. 2022ESCHER: Eschewing Importance Sampling in Games by Computing a History Value Function to Estimate Regretcited by 24
  8. 2017A Modular Analysis of Adaptive (Non-)Convex Optimization: Optimism, Composite Objectives, and Variational Boundscited by 23
  9. 2016Highly-Smooth Zero-th Order Online Optimization Vianney Perchetcited by 22
  10. 2020Online mirror descent and dual averaging: keeping pace in the dynamic casecited by 21
  11. 2018Revisiting CFR+ and Alternating Updatescited by 19
  12. 2020Stochastic Regret Minimization in Extensive-Form Gamescited by 17
  13. 2018Solving Large Sequential Games with the Excessive Gap Techniquecited by 16
  14. 2021Bandit Linear Optimization for Sequential Decision Making and Extensive-Form Gamescited by 15
  15. 2022Adapting to game trees in zero-sum imperfect information gamescited by 11
  16. 2014A Unified View of Large-scale Zero-sum Equilibrium Computationcited by 7
  17. 2014Computing Approximate Nash Equilibria and Robust Best-Responses Using Samplingcited by 6
  18. 2020Finding and Certifying (Near-)Optimal Strategies in Black-Box Extensive-Form Gamescited by 6

Built on by

Cited by year

Citing papers per year: 2024: 1; 2025: 1.

2 papers.

  1. 2024A Policy-Gradient Approach to Solving Imperfect-Information Games with Best-Iterate Convergencecited by 5
  2. 2025Best of Both Worlds: Regret Minimization versus Minimax Playcited by 1