# Better Regularization for Sequential Decision Spaces: Fast Convergence Rates for Nash, Correlated, and Team Equilibria

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 71 references that are in the map.
- First posted on arXiv 27 May 2021.

## Builds on (most cited first, 19 of 19)

- [DeepStack: Expert-Level Artificial Intelligence in No-Limit Poker](https://mlsanity.com/paper/1701.01724/) (2017)
- [Fast Convergence of Regularized Learning in Games](https://mlsanity.com/paper/1507.00407/) (2015)
- [Solving Imperfect-Information Games via Discounted Regret Minimization](https://mlsanity.com/paper/1809.04040/) (2018)
- [Faster Game Solving via Predictive Blackwell Approachability: Connecting Regret Matching and Mirror Descent](https://mlsanity.com/paper/2007.14358/) (2020)
- [Optimistic Regret Minimization for Extensive-Form Games via Dilated Distance-Generating Functions](https://mlsanity.com/paper/1910.10906/) (2019)
- [Variance Reduction in Monte Carlo Counterfactual Regret Minimization (VR-MCCFR) for Extensive Form Games using Baselines](https://mlsanity.com/paper/1809.03057/) (2018)
- [Correlation in Extensive-Form Games: Saddle-Point Formulation and Benchmarks](https://mlsanity.com/paper/1905.12564/) (2019)
- [Online Convex Optimization for Sequential Decision Processes and Extensive-Form Games](https://mlsanity.com/paper/1809.03075/) (2018)
- [Computational Results for Extensive-Form Adversarial Team Games](https://mlsanity.com/paper/1711.06930/) (2017)
- [Coarse Correlation in Extensive-Form Games](https://mlsanity.com/paper/1908.09893/) (2019)
- [Stochastic Regret Minimization in Extensive-Form Games](https://mlsanity.com/paper/2002.08493/) (2020)
- [Solving Large Sequential Games with the Excessive Gap Technique](https://mlsanity.com/paper/1810.03063/) (2018)
- [Bandit Linear Optimization for Sequential Decision Making and Extensive-Form Games](https://mlsanity.com/paper/2103.04546/) (2021)
- [Robust Stackelberg Equilibria in Extensive-Form Games and Extension to Limited Lookahead](https://mlsanity.com/paper/1711.08080/) (2017)
- [Efficient Regret Minimization Algorithm for Extensive-Form Correlated Equilibrium](https://mlsanity.com/paper/1910.12450/) (2019)
- [Theoretical and Practical Advances on Smoothing for Extensive-Form Games](https://mlsanity.com/paper/1702.04849/) (2017)
- [Sparsified Linear Programming for Zero-Sum Equilibrium Finding](https://mlsanity.com/paper/2006.03451/) (2020)
- [Polynomial-Time Computation of Optimal Correlated Equilibria in Two-Player Extensive-Form Games with Public Chance Moves and Beyond](https://mlsanity.com/paper/2009.04336/) (2020)
- [Faster Algorithms for Optimal Ex-Ante Coordinated Collusive Strategies in Extensive-Form Zero-Sum Games](https://mlsanity.com/paper/2009.10061/) (2020)

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

- [Last-iterate Convergence in Extensive-Form Games](https://mlsanity.com/paper/2106.14326/) (2021)
- [The Power of Regularization in Solving Extensive-Form Games](https://mlsanity.com/paper/2206.09495/) (2022)
- [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)
- [Best of Many Worlds Guarantees for Online Learning with Knapsacks](https://mlsanity.com/paper/2202.13710/) (2022)
- [A Survey of Decision Making in Adversarial Games](https://mlsanity.com/paper/2207.07971/) (2022)
- [Scale-Invariant Regret Matching and Online Learning with Optimal Convergence: Bridging Theory and Practice in Zero-Sum Games](https://mlsanity.com/paper/2510.04407/) (2025)
- [On the Optimality of Dilated Entropy and Lower Bounds for Online Learning in Extensive-Form Games](https://mlsanity.com/paper/2410.23398/) (2024)
- [On the Universal Near Optimality of Hedge in Combinatorial Settings](https://mlsanity.com/paper/2510.17099/) (2025)
- [Generalized Bandit Regret Minimizer Framework in Imperfect Information Extensive-Form Game](https://mlsanity.com/paper/2203.05920/) (2022)
- [Differential Privacy in the Extensive-Form Bandit Problem](https://mlsanity.com/paper/2605.05266/) (2026)
- [Convergence analysis and acceleration of the smoothing methods for solving extensive-form games](https://mlsanity.com/paper/2303.11046/) (2023)
- [Efficient Last-Iterate Convergence in Regret Minimization via Adaptive Reward Transformation](https://mlsanity.com/paper/2509.13653/) (2025)
- [Tracking the Best Strategy in an Extensive-Form Game](https://mlsanity.com/paper/2608.09501/) (2026)

## Abstract (arXiv)

We study the application of iterative first-order methods to the problem of computing equilibria of large-scale two-player extensive-form games. First-order methods must typically be instantiated with a regularizer that serves as a distance-generating function for the decision sets of the players. For the case of two-player zero-sum games, the state-of-the-art theoretical convergence rate for Nash equilibrium is achieved by using the dilated entropy function. In this paper, we introduce a new entropy-based distance-generating function for two-player zero-sum games, and show that this function achieves significantly better strong convexity properties than the dilated entropy, while maintaining the same easily-implemented closed-form proximal mapping. Extensive numerical simulations show that these superior theoretical properties translate into better numerical performance as well. We then generalize our new entropy distance function, as well as general dilated distance functions, to the scaled extension operator. The scaled extension operator is a way to recursively construct convex sets, which generalizes the decision polytope of extensive-form games, as well as the convex polytopes corresponding to correlated and team equilibria. By instantiating first-order methods with our regularizers, we develop the first accelerated first-order methods for computing correlated equilibra and ex-ante coordinated team equilibria. Our methods have a guaranteed 1/T rate of convergence, along with linear-time proximal updates.