# Optimistic Regret Minimization for Extensive-Form Games via Dilated Distance-Generating Functions

arXiv: https://arxiv.org/abs/1910.10906 · HTML: https://mlsanity.com/paper/1910.10906/

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Oct 2019.

## Built on by (most cited first, 26 of 26)

- [Nash Learning from Human Feedback](https://mlsanity.com/paper/2312.00886/) (2023)
- [Suspicion-Agent: Playing Imperfect Information Games with Theory of Mind Aware GPT-4](https://mlsanity.com/paper/2309.17277/) (2023)
- [Fast swap regret minimization and applications to approximate correlated equilibria](https://mlsanity.com/paper/2310.19647/) (2023)
- [Last-iterate Convergence in Extensive-Form Games](https://mlsanity.com/paper/2106.14326/) (2021)
- [Model-Free Learning for Two-Player Zero-Sum Partially Observable Markov Games with Perfect Recall](https://mlsanity.com/paper/2106.06279/) (2021)
- [The Power of Regularization in Solving Extensive-Form Games](https://mlsanity.com/paper/2206.09495/) (2022)
- [Beyond Time-Average Convergence: Near-Optimal Uncoupled Online Learning via Clairvoyant Multiplicative Weights Update](https://mlsanity.com/paper/2111.14737/) (2021)
- [Kernelized Multiplicative Weights for 0/1-Polyhedral Games: Bridging the Gap Between Learning in Extensive-Form and Normal-Form Games](https://mlsanity.com/paper/2202.00237/) (2022)
- [Fast Rates for Nonparametric Online Learning: From Realizability to Learning in Games](https://mlsanity.com/paper/2111.08911/) (2021)
- [Policy Space Diversity for Non-Transitive Games](https://mlsanity.com/paper/2306.16884/) (2023)
- [Regret Matching+: (In)Stability and Fast Convergence in Games](https://mlsanity.com/paper/2305.14709/) (2023)
- [Better Regularization for Sequential Decision Spaces: Fast Convergence Rates for Nash, Correlated, and Team Equilibria](https://mlsanity.com/paper/2105.12954/) (2021)
- [Mastering Strategy Card Game (Legends of Code and Magic) via End-to-End Policy and Optimistic Smooth Fictitious Play](https://mlsanity.com/paper/2303.04096/) (2023)
- [Search in Imperfect Information Games](https://mlsanity.com/paper/2111.05884/) (2021)
- [Equivalence Analysis between Counterfactual Regret Minimization and Online Mirror Descent](https://mlsanity.com/paper/2110.04961/) (2021)
- [Conic Blackwell Algorithm: Parameter-Free Convex-Concave Saddle-Point Solving](https://mlsanity.com/paper/2105.13203/) (2021)
- [A Policy-Gradient Approach to Solving Imperfect-Information Games with Best-Iterate Convergence](https://mlsanity.com/paper/2408.00751/) (2024)
- [Solving optimization problems with Blackwell approachability](https://mlsanity.com/paper/2202.12277/) (2022)
- [Fast Convergence of Optimistic Gradient Ascent in Network Zero-Sum Extensive Form Games](https://mlsanity.com/paper/2207.08426/) (2022)
- [The complexity of approximate (coarse) correlated equilibrium for incomplete information games](https://mlsanity.com/paper/2406.02357/) (2024)
- [Optimistic and Adaptive Lagrangian Hedging](https://mlsanity.com/paper/2101.09603/) (2021)
- [Local and adaptive mirror descents in extensive-form games](https://mlsanity.com/paper/2309.00656/) (2023)
- [Generalized Bandit Regret Minimizer Framework in Imperfect Information Extensive-Form Game](https://mlsanity.com/paper/2203.05920/) (2022)
- [DecisionHoldem: Safe Depth-Limited Solving With Diverse Opponents for Imperfect-Information Games](https://mlsanity.com/paper/2201.11580/) (2022)
- [GPU-CFR: 80x Faster Counterfactual Regret Minimization by Compiling the Game to Static Dataflow and CUDA Graph Replay](https://mlsanity.com/paper/2609.11923/) (2026)
- [A Geometric Perspective on Reward Function Updates in Inverse Reinforcement Learning](https://mlsanity.com/paper/2610.14041/) (2026)

## Abstract (arXiv)

We study the performance of optimistic regret-minimization algorithms for both minimizing regret in, and computing Nash equilibria of, zero-sum extensive-form games. In order to apply these algorithms to extensive-form games, a distance-generating function is needed. We study the use of the dilated entropy and dilated Euclidean distance functions. For the dilated Euclidean distance function we prove the first explicit bounds on the strong-convexity parameter for general treeplexes. Furthermore, we show that the use of dilated distance-generating functions enable us to decompose the mirror descent algorithm, and its optimistic variant, into local mirror descent algorithms at each information set. This decomposition mirrors the structure of the counterfactual regret minimization framework, and enables important techniques in practice, such as distributed updates and pruning of cold parts of the game tree. Our algorithms provably converge at a rate of T-1, which is superior to prior counterfactual regret minimization algorithms. We experimentally compare to the popular algorithm CFR+, which has a theoretical convergence rate of T-0.5 in theory, but is known to often converge at a rate of T-1, or better, in practice. We give an example matrix game where CFR+ experimentally converges at a relatively slow rate of T-0.74, whereas our optimistic methods converge faster than T-1. We go on to show that our fast rate also holds in the Kuhn poker game, which is an extensive-form game. For games with deeper game trees however, we find that CFR+ is still faster. Finally we show that when the goal is minimizing regret, rather than computing a Nash equilibrium, our optimistic methods can outperform CFR+, even in deep game trees.