Research map / Bandits and online learning / Online convex optimization and games
Efficient $\Phi$-Regret Minimization with Low-Degree Swap Deviations 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.
Gives parameterized no-regret algorithms for Phi-regret over k-mediator and degree-k polynomial swap deviations in extensive-form games, plus a relaxed "fixed point in expectation" template that avoids PPAD-hard fixed-point computation.
Problem
Minimizing swap-type Phi-regret in extensive-form games efficiently: full swap regret takes N^{~O(1/eps)} rounds and linear-swap regret only covers a weak deviation class, so intermediate deviation classes need efficient algorithms.
Approach
Introduce k-mediator deviations (degree-k polynomial deviations) and minimize regret over them via tree-form/DAG-form decision problems of size N^{O(k)}; replace exact fixed points in the Gordon-Greenwald-Marks template with distributions satisfying E[phi(x)-x] ≈ 0, which are efficiently computable via a telescoping iteration.
Key results
- Regret minimization over k-mediator deviations in N^{O(k)}/eps^2 rounds, and over degree-k polynomial deviations in N^{O(kd)^3}/eps^2 rounds.
- Computing a fixed point in expectation is efficient, whereas computing an actual approximate fixed point of a multilinear deviation under behavioral strategies is PPAD-hard.
- Yields an eps-correlated equilibrium algorithm in normal-form games running in O(A log A/eps^2 (EO + nA^2/eps)) time, improving on prior moderate-precision bounds.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use depth-k decision-tree deviations instead of unrestricted swap deviations | Online regret minimization on the hypercube · Hypercube {0,1}^N | rounds to ε-regret: N^{O(k)}/ε^2 | Helped |
| Use degree-k polynomial deviations | Online regret minimization on the hypercube · Hypercube {0,1}^N | rounds to ε-regret: N^{O(k^3)}/ε^2 | Helped |
| Allow k mediators | Online regret minimization in extensive-form games · Extensive-form games | rounds to ε-regret: N^{O(k)}/ε^2 | Helped |
| Use degree-k polynomial deviations | Online regret minimization in extensive-form games · Extensive-form games | rounds to ε-regret: N^{O(kd)^3}/ε^2 | Helped |
| Use distributions over pure strategies rather than behavioral strategies | Low-degree Φ-regret minimization · Behavioral strategies [0,1]^N | computational tractability | Helped |
| Replace actual fixed-point computation with an approximate fixed point in expectation | The Φ-regret minimization framework · Extensive-form games | computational tractability: O(1/L) | Helped |
| Use expected fixed points to replace the fixed-point oracle | Φ-regret minimization with external regret on Φ · General strategy sets | per-iteration runtime: O(R_1 + R_2/ε) | Helped |
| Use mixed strategies instead of points in the convex hull | Low-degree regret minimization · Behavioral strategies [0,1]^N | computational tractability | Helped |
| Use the expected-fixed-point framework for correlated-equilibrium computation | Normal-form games · Normal-form games | time to compute ε-correlated equilibrium: O \left( \frac{A \log A }{\epsilon^2} \left( \mathsf{EO}(n, A) + n \frac{A^2}{\epsilon} \right) \right) | Helped |
Surprising findings
- Behavioral-strategy regret minimization over multilinear deviations is PPAD-hard even for degree 2, while mixed-strategy learners avoid this.
Limitations
- Degree-k polynomial bound depends exponentially on game depth d (N^{O(kd)^3}).
- Only quasipolynomial for balanced trees with polylog depth; polynomial only for Bayesian games at fixed k.
Experimental setup
Metrics: Phi-regret bound iteration complexity
Baselines: Dagan et al. 2023 swap regret algorithm Peng and Rubinstein 2023 Farina and Pipis 2023 linear-swap regret
Builds on: Gordon-Greenwald-Marks template Dagan et al. 2023 swap regret reduction Farina and Pipis linear-swap regret Zhang, Farina, Sandholm untimed communication deviations
Closest papers by meaning
- Optimistic Regret Minimization for Extensive-Form Games via Dilated Distance-Generating Functions (NeurIPS 2019 · similarity 0.91)
- Near-Optimal $\Phi$-Regret Learning in Extensive-Form Games (ICML 2023 · similarity 0.90)
- Mediator Interpretation and Faster Learning Algorithms for Linear Correlated Equilibria in General Sequential Games (ICLR 2024 · similarity 0.90)
- Comparator-Adaptive $\Phi$-Regret: Improved Bounds, Simpler Algorithms, and Applications to Games (NeurIPS 2025 · similarity 0.90)
- Last-Iterate Convergence Properties of Regret-Matching Algorithms in Games (ICLR 2025 · similarity 0.89)
- Optimism Without Regularization: Constant Regret in Zero-Sum Games (NeurIPS 2025 · 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.