Research map / Bandits and online learning / Online convex optimization and games
On the Optimality of Dilated Entropy and Lower Bounds for Online Learning in Extensive-Form Games
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows weight-one dilated entropy (DilEnt) is nearly optimal as a distance-generating function for first-order methods in extensive-form games, via new primal-dual treeplex norms and a matching regret lower bound.
Problem
Finding the optimal distance-generating function (regularizer) for first-order methods on sequence-form extensive-form decision spaces, measured by the diameter-to-strong-convexity ratio, and whether OMD can match KOMWU's regret without kernelization.
Approach
Introduces a pair of primal-dual treeplex norms (treeplex l1 and l_infinity) under which DilEnt is 1-strongly convex, giving diameter-to-strong-convexity ratio ln|V|; a matching regret lower bound shows this is optimal up to logarithmic factors.
Key results
- DilEnt is 1-strongly convex w.r.t. the treeplex l1 norm with diameter bounded by ln|V|, giving regret O(sqrt(ln|V| T)) matching KOMWU.
- A new regret lower bound of Omega(sqrt(||Q||_perp log|A_0|) sqrt(T)) for online learning in sequence-form strategy spaces shows DilEnt's ratio is optimal up to logarithmic factors.
- Clairvoyant OMD with DilEnt reaches an O(n log|V| log T / T) CCE rate, improving on prior O(n log|V| log^4 T / T).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use weight-one DilEnt with treeplex norms instead of prior dilated entropy analyses | DilEnt on extensive-form decision spaces · Extensive-form decision spaces | diameter-to-strong-convexity ratio: \cO(2^{D} \|\cQ\|_1^2 \log |\cA|) -> ln |\cV| | Helped |
| Use treeplex norms to analyze OMD with DilEnt | OMD in online learning · Extensive-form games, full-information | regret: \sqrt{2\ln |\cV|} \sqrt{T} | Helped |
| Equip Clairvoyant OMD with DilEnt | Clairvoyant OMD · n-player extensive-form games | CCE convergence rate: \cO(n \log |\cV| \log^4 T/T) -> \cO(n \log |\cV| \log T/T) | Helped |
| Use DilEnt with treeplex norms | Regularizers for extensive-form decision spaces · Extensive-form decision spaces | diameter-to-strong-convexity ratio: \ln |\cV|; lower bound: \Omega(\|\cQ\|_{\perp} \log |\cA_0|) | Mixed |
Limitations
- Lower bound only applies to full-information feedback, not bandit or sampling feedback.
- Optimality holds only up to a logarithmic gap in the number of sequences in general; tight constant-factor results only for a specific TFSDP family.
- Lower bound is established only in a specific family of games with a logarithmic gap for general trees.
Experimental setup
Metrics: regret diameter-to-strong-convexity ratio epsilon-CCE approximation rate
Baselines: Dilated entropy Dilated global entropy KOMWU Clairvoyant MWU
Builds on: Online mirror descent Dilated entropy regularizer Kernelized OMWU (KOMWU) Clairvoyant OMD Predictive OMD
Closest papers by meaning
- Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms (NeurIPS 2024 · similarity 0.90)
- Accelerated Regularized Learning in Finite N-Person Games (NeurIPS 2024 · similarity 0.88)
- From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applications (NeurIPS 2025 · similarity 0.88)
- Local and Adaptive Mirror Descents in Extensive-Form Games (NeurIPS 2024 · similarity 0.87)
- On the Universal Near Optimality of Hedge in Combinatorial Settings (NeurIPS 2025 · similarity 0.87)
- Extensive-Form Game Solving via Blackwell Approachability on Treeplexes (NeurIPS 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.