Research map / Optimization / Nonconvex and smooth optimization
Efficient Learning in Polyhedral Games via Best-Response Oracles
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 Approximate Reflected OMD with away-step Frank-Wolfe as the proximal oracle, enabling game learning with only O(log t) best-response oracle calls per iteration, with O(log N / N) Nash convergence in zero-sum games and last-iterate linear convergence.
Problem
Learning and equilibrium computation in polyhedral games (normal-form and extensive-form) when the learner can only access a best-response / linear minimization oracle, where prior methods needed O(T) oracle calls per iteration or converged only at O(1/sqrt(N)).
Approach
Use reflected online mirror descent with Euclidean regularizer, implementing approximate proximal steps via away-step Frank-Wolfe, which converges linearly over polytopes; the RVU analysis still holds with approximate prox steps. New facial distance lower bounds for sequence-form, flow, and matching polytopes make the linear rate scale well.
Key results
- Achieves O(log N / N) convergence to Nash equilibrium in two-player zero-sum games in terms of best-response oracle calls, improving on prior O(1/sqrt(N)).
- Uses only O(log t) best-response queries per iteration with constant social regret in zero-sum self-play and O(T^{1/4}) per-player regret in general-sum games.
- Proves linear last-iterate convergence in zero-sum games (with condition-number dependence) and O(1/sqrt(T)) best-iterate convergence without it; empirically the method outperforms other projection-free algorithms on EFG benchmarks for Nash computation.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use FW-ROMD instead of the compared existing algorithms | two-player zero-sum equilibrium computation · Two-player Kuhn poker, two-player Leduc poker, and two-player Liar's Dice | Nash gap | Helped |
| use FW-OMD instead of the compared algorithms | multiplayer CCE computation · Three-player Kuhn poker, three-player Liar's Dice, and three-player Goofspiel (3 ranks) | maximum individual average regret | Helped |
| add optimism | the compared learning algorithms · Experimental games | equilibrium error or average regret | Helped |
| add optimism to FW-OMD | FW-OMD in multiplayer CCE computation · Three-player games | maximum individual average regret | Hurt |
| use warmstarting and a fixed number of LMO calls per iteration (ablation) | FW-ROMD · Two-player Leduc poker and two-player Liar's Dice | Nash gap | Helped |
| use warmstarting and a fixed number of LMO calls per iteration (ablation) | FW-OMD · Three-player Liar's Dice and three-player Goofspiel (3 ranks) | maximum individual average regret | Helped |
| use warmstarting and a fixed number of LMO calls per iteration (ablation) | FW-ROMD or FW-OMD · Two-player and three-player Kuhn poker | equilibrium error or average regret | No clear effect |
Surprising findings
- The non-optimistic variant FWOMD performs best for computing coarse correlated equilibria, and optimism hurts it in that setting.
Limitations
- Last-iterate linear convergence depends on a game-dependent condition number (nu) that is generally hard to evaluate.
- General-sum guarantees are weaker, O(T^{1/4}) regret, and the non-optimistic variant has worse theoretical guarantees than existing methods.
Experimental setup
Datasets: Kuhn poker Leduc poker Liar's Dice Goofspiel
Benchmarks: Kuhn poker Leduc poker Liar's Dice Goofspiel (3 ranks)
Metrics: Nash gap average regret duality gap
Baselines: FTPL OFTPL fictitious play optimistic fictitious play best-response dynamics OFW FWOMD
Builds on: Frank-Wolfe away-step Frank-Wolfe optimistic FTPL RVU bounds reflected OMD
Closest papers by meaning
- Extensive-Form Game Solving via Blackwell Approachability on Treeplexes (NeurIPS 2024 · similarity 0.90)
- From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applications (NeurIPS 2025 · similarity 0.89)
- Optimism Without Regularization: Constant Regret in Zero-Sum Games (NeurIPS 2025 · similarity 0.89)
- Efficient Kernelized Learning in Polyhedral Games beyond Full Information: From Colonel Blotto to Congestion Games (NeurIPS 2025 · similarity 0.89)
- Last-Iterate Convergence Properties of Regret-Matching Algorithms in Games (ICLR 2025 · similarity 0.88)
- Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms (NeurIPS 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.