Research map / Optimization / Nonconvex and smooth optimization
On Last-Iterate Convergence Beyond Zero-Sum 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 |
|---|---|---|---|
| Apply OMD with an RVU regret bound in games with nonnegative sum of regrets | Constant-sum polymatrix and strategically zero-sum games · Constant-sum polymatrix and strategically zero-sum games | iterations to an approximate Nash equilibrium: O(1/epsilon^2) | Helped |
| Apply OMD with an RVU bound and bounded second-order path length | Constant-sum polymatrix and strategically zero-sum games · Constant-sum polymatrix and strategically zero-sum games | individual regret: O(1) | Helped |
| Allow different smooth regularizers for players | OMD in games with nonnegative sum of regrets · Games with nonnegative sum of regrets | iterations to an approximate Nash equilibrium: O(1/epsilon^2) | Helped |
| Use advanced prediction mechanisms, including recency-biased predictions | Optimistic learning dynamics · Games with nonnegative sum of regrets | bounded second-order path length | Helped |
| Use MD with a suitable regularizer in potential games | Potential games · Potential games | iterations to an approximate Nash equilibrium: O(1/epsilon^2) | Helped |
| Use OMWU with a sufficiently small learning rate | Potential games · Potential games | individual regret: O(1) | Helped |
| Require the potential to be concave | MD in potential games · Potential games with concave potential | potential suboptimality: O(1/T) | Helped |
| Extend the potential argument to games within delta of a potential game | MD in near-potential games · Near-potential games | equilibrium approximation: O(sqrt(delta))-Nash equilibrium | Helped |
| Use OGD when A^T B has strictly negative real eigenvalues | OGD in two-player continuous games · Two-player continuous games | convergence rate: linearly | Helped |
| Apply OGD beyond zero-sum games, including games with a coordination aspect | OGD in continuous games · General-sum continuous games | social welfare: 0; 2R^2 | Hurt |
| Perturb a zero-sum game by an arbitrarily small amount | OGD in two-player continuous games · Games arbitrarily close to zero-sum | convergence: ||A + B||_F <= epsilon | Hurt |
| Use OMD with Euclidean regularization in Kuhn and Leduc poker | OMD · Kuhn poker and Leduc poker | saddle-point gap | Helped |
Closest papers by meaning
- Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms (NeurIPS 2024 · similarity 0.94)
- Near-Optimal Last-Iterate Convergence for Zero-Sum Games with Bandit Feedback and Opponent Actions (NeurIPS 2026 · similarity 0.92)
- From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applications (NeurIPS 2025 · similarity 0.92)
- The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback (ICML 2025 · similarity 0.92)
- Last-Iterate Convergence Properties of Regret-Matching Algorithms in Games (ICLR 2025 · similarity 0.91)
- No-regret Learning in Harmonic Games: Extrapolation in the Face of Conflicting Interests (NeurIPS 2024 · similarity 0.91)
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.