Research map / Optimization / Nonconvex and smooth optimization
Local and Adaptive Mirror Descents 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.
Proposes LocalOMD, a fixed-sampling OMD method for zero-sum imperfect-information extensive-form games with trajectory feedback that runs local OMD per information set with adaptive learning rates and a regularized loss, plus a generalized dual-stabilized OMD with time-varying regularization.
Problem
Learning epsilon-optimal strategies in zero-sum imperfect information extensive-form games from trajectory feedback only, where importance sampling over action sequences yields high-variance loss estimates.
Approach
Use a fixed sampling policy for observations and decouple observation from interaction policies; apply OMD locally per information set with dilated entropy, importance weighting only the current action (regularized loss), and time-varying regularization with convex increments (generalized dual stabilization).
Key results
- LocalOMD achieves regret/sample complexity Õ(H^3(X+Y)/ε^2) with the balanced sampling policy, and an Õ(H^{3/2}sqrt(X T)) regret bound with high probability, matching near-optimal rates up to H.
- With any positive fixed sampling policy LocalOMD achieves Õ(1/ε^2) sample complexity ignoring game-dependent parameters.
- In tabular experiments LocalOMD (both learning-rate variants) consistently beats BalancedCFR and is comparable to BalancedFTRL, with fewer policy updates.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use LocalOMD instead of BalancedCFR | LocalOMD vs. BalancedCFR · Kuhn poker, Leduc poker, and liars dice | performance | Helped |
| Use LocalOMD instead of BalancedFTRL | LocalOMD vs. BalancedFTRL · Liars dice | performance | Hurt |
| Use LocalOMD instead of BalancedFTRL | LocalOMD vs. BalancedFTRL · Leduc poker | performance | Helped |
| Use the parameter setting of Theorem [ref] rather than Theorem [ref] | LocalOMD · Kuhn poker, Leduc poker, and liars dice | performance | No clear effect |
Surprising findings
- BalancedFTRL performs better than LocalOMD on liar's dice but worse on Leduc poker, so the advantage is not uniform across games.
Limitations
- Balanced sampling policy is hard to compute for large games needing function approximation.
- Results and guarantees are for tabular settings only; no function approximation experiments.
- Guarantees rely on policy averaging rather than last-iterate convergence.
Experimental setup
Datasets: Kuhn poker Leduc poker Liar's dice
Benchmarks: Kuhn poker Leduc poker Liar's dice
Metrics: exploitability vs number of episodes
Baselines: BalancedCFR BalancedFTRL
Builds on: Online Mirror Descent dilated entropy outcome-sampling MCCFR BalancedCFR dual-stabilized OMD
Closest papers by meaning
- Learning Imperfect Information Extensive-form Games with Last-iterate Convergence under Bandit Feedback (ICML 2025 · similarity 0.91)
- Adaptively Perturbed Mirror Descent for Learning in Games (ICML 2024 · similarity 0.90)
- A Policy-Gradient Approach to Solving Imperfect-Information Games with Best-Iterate Convergence (ICLR 2025 · similarity 0.89)
- Uncoupled and Convergent Learning in Monotone Games under Bandit Feedback (NeurIPS 2025 · similarity 0.89)
- The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback (ICML 2025 · similarity 0.88)
- The Update-Equivalence Framework for Decision-Time Planning (ICLR 2024 · similarity 0.88)
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.