Research map / Bandits and online learning / Online convex optimization and games
Let’s be Honest: An Optimal No-Regret Framework for 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 |
|---|---|---|---|
| Play averaged rather than auxiliary OMD iterates | OMD in honest zero-sum games · Two-player zero-sum games, honest | honest regret: O(\log T) | Helped |
| Use horizon-independent mixing steps in ROMD | Optimistic mirror descent against arbitrary play · Arbitrary sequence of convex functions | adversarial regret: O(\sqrt{T}) | Helped |
| Bridge OMD and ROMD with synchronized signaling | Decentralized zero-sum game learning · Two-player zero-sum games | game value error: O\l( \frac{1}{T}\r) | Helped |
| Use LbH instead of modified OMD | Decentralized zero-sum game learning · Two-player zero-sum games, adversarial | adversarial regret: O(\sqrt{T}\log T) -> O(\sqrt{T}) | Helped |
| Use LbH instead of modified OMD | Decentralized zero-sum game learning · Two-player zero-sum games | game value error: O\l(T^{-1}{\log T}\r) -> O\l(T^{-1}\r) | Helped |
| Use LbH instead of the prior complicated method | Decentralized zero-sum game learning · Two-player zero-sum games | game value error: O(T^{-1}{\log^{\frac{3}{2}} T}) -> O\l(T^{-1}\r) | Helped |
| Replace doubling b with b \leftarrow (1+\epsilon)b (ablation) | Let's Be Honest (LbH) OMD · Two-player zero-sum games | convergence rates | No clear effect |
| Play b^2-1 rather than b^4-1 ROMD rounds (ablation) | Let's Be Honest (LbH) OMD · Two-player zero-sum games | convergence rates | No clear effect |
| Use LbH instead of m-OMD | Decentralized zero-sum game learning · Adversarial setting, random payoff matrices | regret | Mixed |
| Use LbH instead of horizon-tuned m-OMD | Decentralized zero-sum game learning · Honest setting, random payoff matrices | game value error | Helped |
Closest papers by meaning
- Optimistic Mirror Descent Either Converges to Nash or to Strong Coarse Correlated Equilibria in Bimatrix Games (NeurIPS 2022 · similarity 0.92)
- Optimism Without Regularization: Constant Regret in Zero-Sum Games (NeurIPS 2025 · similarity 0.91)
- Convergence of No-Swap-Regret Dynamics in Self-Play (NeurIPS 2024 · similarity 0.89)
- Best of Both Worlds: Regret Minimization versus Minimax Play (ICML 2025 · similarity 0.89)
- Uncoupled and Convergent Learning in Monotone Games under Bandit Feedback (NeurIPS 2025 · similarity 0.89)
- Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms (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.