cs.LGNov 9, 2026

Tropical Gaussian Anticoncentration: Optimal Instance-Dependent Bounds for Online Learning in Extensive-Form Games

Authors: Ashkan Soleymani, Zhiyuan Fan, Lillian J. Ratliff, Patrick Jaillet, Gabriele Farina

Organizations: MIT · University of Washington

Abstract

We study the minimax regret of full-information online decision making in extensive-form games. For prediction with expert advice, the optimal regret is Θ(Tlog⁡K)Θ(\sqrt{T\log K}), where KK is the number of experts, or equivalently, the number of normal-form actions. For treeplex strategy spaces, existing efficient algorithms, including KOMWU and online mirror descent with the weight-one dilated entropy regularizer, achieve regret O(Tlog⁡∣V∣)\mathcal{O}(\sqrt{T\log|\mathcal{V}|}), where V\mathcal{V} is the set of reduced normal-form strategies. We prove that this logarithmic dependence is minimax optimal in the worst-case full-information reward model. The main difficulty is that pure plans in a treeplex are not independent experts: their rewards are correlated through the recursive structure of decisions and observations. To capture this correlation, we introduce tropical Gaussian formulae, recursive Gaussian expressions built from maxima and normalized sums which preserve the variance. The index count of such a formula matches the number of reduced normal-form continuation plans in the corresponding subtree. Our main analytic result shows that every log-balanced tropical Gaussian formula with index count NN has Gaussian width Ω(log⁡N)Ω(\sqrt{\log N}). While a direct approach struggles to recover this lower bound, our proof uses a spherical entropy profile to measure scale-dependent separation among the Gaussian directions, and then applies Turán's theorem and Sudakov minoration to obtain the width lower bound. Applying this result to treeplexes gives an oblivious hard distribution with valid transition outcome and Rademacher terminal rewards, establishing a regret lower bound of Ω(Tlog⁡∣V∣)Ω(\sqrt{T\log|\mathcal{V}|}). This matches known upper bounds up to universal constants and shows that the DilEnt/KOMWU dependence on the reduced normal-form complexity is unavoidable.

Figures & tables

Explore similar work

CardsList
  1. Tracking the Best Strategy in an Extensive-Form Game

    Aug 10, 2026Stephen Pasteris, Rahul Savani, Theodore TurocyImperfect-Information GamesRegret Minimization

  2. Constant Individual Regret in General Games

    Aug 31, 2026Mingyang Liu, Gabriele Farina, Asuman OzdaglarGame TheoryFollow-the-Regularized-Leader

  3. Constant regret in general games via higher-order optimism

    Sep 3, 2026Omar Abbadi, Rida Laraki, Panayotis MertikopoulosFollow-the-Regularized-LeaderRegret Minimization