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

Aug 10, 2026

Tracking the Best Strategy in an Extensive-Form Game

We consider the extensive-form bandit problem where on each trial the learner plays an extensive-form game against an oblivious adversary. We focus on the notion of switching regret, which measures the expected performance of the learner against that of any switching sequence of mixed strategies in retrospect. Our algorithm takes a parameter ρ>0ρ>0 and achieves a switching regret of O~((1/ρ+ρK)HAT)\tilde{\mathcal{O}}((1/ρ+ρK)\sqrt{H A T}) where KK is the number of switches in the comparator sequence, HH is the maximum number of the learner's information sets that can be traversed during a play of the game and AA is the number of actions that the learner can possibly take. Our algorithm is extremely efficient, taking a per trial time of only O(HB)\mathcal{O}(H B) where BB is the maximum number of actions available to the learner at any of its information sets.
Aug 31, 2026

Constant Individual Regret in General Games

Uncoupled no-regret dynamics provide a decentralized route to equilibrium, but prior guarantees for individual regret retain a polylogarithmic dependence on the horizon. We remove this dependence for every finite NN-player normal-form game under full-information feedback. We introduce ECHO-OFTRL: optimistic follow-the-regularized-leader (OFTRL) equipped with an EMA cascade for high-order optimism (ECHO), where EMA denotes exponential moving average. The algorithm is deterministic and fully uncoupled. If mmax⁡m_{\max} denotes the largest action-set size, then, simultaneously for every horizon T≥1T\geq1, it guarantees that each of the NN players in the game incurs regret upper bounded by O(poly(N,log⁡mmax⁡))O(\textrm{poly}(N, \log m_{\max})). Our algorithm leverages a new form of optimism inspired by modern filter design.
Sep 3, 2026

Constant regret in general games via higher-order optimism

We introduce an uncoupled learning algorithm which, when employed by all players of an arbitrary NN-player normal form game with up to KK actions per player, guarantees O(N3log⁡2K)O(N^3\log^2 K) individual regret, uniformly over the horizon of play. The proposed algorithm - which we call higher-order optimism with discounting (HOOD) is a variant of optimistic follow-the-regularized-leader (OptFTRL) that combines a discounted (N+1)(N+1)-th order predictor with entropic regularization over a suitable "lifting" of the game's strategy space. This combination of ingredients is purposefully designed to dampen large oscillations of the induced sequence of play in a controlled manner, removing in this way a key stumbling block of previous attempts to achieve constant regret in general games. Our approach bears several striking similarities to the concurrent - and completely independent - work of Liu, Farina, and Ozdaglar (arXiv:2608.31166), who very recently derived an O(N21log⁡4K)O(N^{21}\log^{4} K) regret bound through the use of higher-order optimism and an exponential moving average estimator.