# On the Optimality of Dilated Entropy and Lower Bounds for Online Learning in Extensive-Form Games

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 44 references that are in the map.
- First posted on arXiv 30 Oct 2024.

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

- [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)
- [Near-Optimal No-Regret Learning in General Games](https://mlsanity.com/paper/2108.06924/) (2021)
- [Solving Imperfect-Information Games via Discounted Regret Minimization](https://mlsanity.com/paper/1809.04040/) (2018)
- [Hedging in games: Faster convergence of external and swap regrets](https://mlsanity.com/paper/2006.04953/) (2020)
- [Faster Game Solving via Predictive Blackwell Approachability: Connecting Regret Matching and Mirror Descent](https://mlsanity.com/paper/2007.14358/) (2020)
- [Last-iterate Convergence in Extensive-Form Games](https://mlsanity.com/paper/2106.14326/) (2021)
- [Near-Optimal Learning of Extensive-Form Games with Imperfect Information](https://mlsanity.com/paper/2202.01752/) (2022)
- [Near-Optimal No-Regret Learning Dynamics for General Convex Games](https://mlsanity.com/paper/2206.08742/) (2022)
- [Online Convex Optimization for Sequential Decision Processes and Extensive-Form Games](https://mlsanity.com/paper/1809.03075/) (2018)
- [Stable-Predictive Optimistic Counterfactual Regret Minimization](https://mlsanity.com/paper/1902.04982/) (2019)
- [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)
- [Solving Large Sequential Games with the Excessive Gap Technique](https://mlsanity.com/paper/1810.03063/) (2018)
- [Efficient Phi-Regret Minimization in Extensive-Form Games via Online Mirror Descent](https://mlsanity.com/paper/2205.15294/) (2022)
- [Better Regularization for Sequential Decision Spaces: Fast Convergence Rates for Nash, Correlated, and Team Equilibria](https://mlsanity.com/paper/2105.12954/) (2021)
- [Adapting to game trees in zero-sum imperfect information games](https://mlsanity.com/paper/2212.12567/) (2022)
- [A Policy-Gradient Approach to Solving Imperfect-Information Games with Best-Iterate Convergence](https://mlsanity.com/paper/2408.00751/) (2024)
- [Clairvoyant Regret Minimization: Equivalence with Nemirovski's Conceptual Prox Method and Extension to General Convex Games](https://mlsanity.com/paper/2208.14891/) (2022)
- [On the Complexity of Computing Sparse Equilibria and Lower Bounds for No-Regret Learning in Games](https://mlsanity.com/paper/2311.14869/) (2023)

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

- [Best of Both Worlds: Regret Minimization versus Minimax Play](https://mlsanity.com/paper/2502.11673/) (2025)
- [On the Universal Near Optimality of Hedge in Combinatorial Settings](https://mlsanity.com/paper/2510.17099/) (2025)

## Abstract (arXiv)

First-order methods (FOMs) are arguably the most scalable algorithms for equilibrium computation in large extensive-form games. To operationalize these methods, a distance-generating function, acting as a regularizer for the strategy space, must be chosen. The ratio between the strong convexity modulus and the diameter of the regularizer is a key parameter in the analysis of FOMs. A natural question is then: what is the optimal distance-generating function for extensive-form decision spaces? In this paper, we make a number of contributions, ultimately establishing that the weight-one dilated entropy (DilEnt) distance-generating function is optimal up to logarithmic factors. The DilEnt regularizer is notable due to its iterate-equivalence with Kernelized OMWU (KOMWU) -- the algorithm with state-of-the-art dependence on the game tree size in extensive-form games -- when used in conjunction with the online mirror descent (OMD) algorithm. However, the standard analysis for OMD is unable to establish such a result; the only current analysis is by appealing to the iterate equivalence to KOMWU. We close this gap by introducing a pair of primal-dual treeplex norms, which we contend form the natural analytic viewpoint for studying the strong convexity of DilEnt. Using these norm pairs, we recover the diameter-to-strong-convexity ratio that predicts the same performance as KOMWU. Along with a new regret lower bound for online learning in sequence-form strategy spaces, we show that this ratio is nearly optimal. Finally, we showcase our analytic techniques by refining the analysis of Clairvoyant OMD when paired with DilEnt, establishing an O(n log |V| log T/T) approximation rate to coarse correlated equilibrium in n-player games, where |V| is the number of reduced normal-form strategies of the players, establishing the new state of the art.