Research map / Bandits and online learning / Online convex optimization and games
Polynomial-Time Linear-Swap Regret Minimization in Imperfect-Information Sequential Games
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Characterize all linear transformations of the sequence-form strategy polytope with polynomially many constraints, then use projected gradient descent and fixed-point computation | No-linear-swap-regret learning in extensive-form games · Perfect-recall imperfect-information extensive-form games | linear-swap regret: O(|\Seqs|^2 \sqrt{T}) | Helped |
| Use a polynomial characterization of the transformation set to enable polynomial-time projection and fixed-point computation | No-linear-swap-regret algorithm · Perfect-recall imperfect-information extensive-form games | iteration time: O(\poly(|\Seqs|) \log^2{t}) | Helped |
| Use no-linear-swap-regret dynamics instead of no-trigger-regret dynamics | Learning dynamics in extensive-form games · Experimental comparison; game not identified in the provided text | linear-swap regret | Helped |
| Use either no-linear-swap-regret or no-trigger-regret dynamics | Learning dynamics in extensive-form games · Experimental comparison; game not identified in the provided text | trigger regret | No clear effect |
Closest papers by meaning
- Mediator Interpretation and Faster Learning Algorithms for Linear Correlated Equilibria in General Sequential Games (ICLR 2024 · similarity 0.94)
- Convergence of No-Swap-Regret Dynamics in Self-Play (NeurIPS 2024 · similarity 0.91)
- Efficient $\Phi$-Regret Minimization with Low-Degree Swap Deviations in Extensive-Form Games (NeurIPS 2024 · similarity 0.90)
- Optimism Without Regularization: Constant Regret in Zero-Sum Games (NeurIPS 2025 · similarity 0.90)
- No Coin Left Behind: Maximizing Strategic Surplus Against No-Regret Dynamics (NeurIPS 2026 · similarity 0.89)
- No-regret Learning in Harmonic Games: Extrapolation in the Face of Conflicting Interests (NeurIPS 2024 · similarity 0.89)
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.