Research map / Bandits and online learning / Online convex optimization and games
Uncoupled and Convergent Learning in Monotone Games under Bandit Feedback
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 a mirror-descent algorithm with a self-concordant barrier and a second regularizer, using an ellipsoidal bandit gradient estimator, that achieves last-iterate O(T^-1/4) convergence in monotone games (O(T^-1/2) for strongly monotone) under bandit feedback and strongly uncoupled dynamics, extended to time-varying games.
Problem
Last-iterate convergence to Nash equilibrium of no-regret learning in general monotone and smooth games under bandit feedback with strongly uncoupled dynamics, including time-varying games.
Approach
Combine a self-concordant barrier regularizer (for an ellipsoidal bandit gradient estimator) with a second regularizer p that makes the game's cost function less curved than c_i, and analyze the fixed point of the regularized dynamics; tune the smoothing radius delta_t to control bias for merely convex p.
Key results
- Last-iterate convergence rate O(T^-1/4) in monotone games under bandit feedback, with individual regret O(T^1/4).
- Strongly monotone games achieve O(T^-1/2) last-iterate convergence, also with high probability.
- Time-varying monotone games: equilibrium-tracking bound max{T^(2phi/3-2/3), T^((4phi+5)^2/72-9/8)}, improving on prior T^(phi/5-1/5) and T^(phi/3-2/3) for strongly monotone games.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed algorithm instead of prior bandit methods for general monotone games | Monotone games · Monotone games, bandit feedback | last-iterate convergence rate: asymptotic -> O(T^{-1/4}) | Helped |
| Apply the proposed algorithm to strongly monotone games | Strongly monotone games · Strongly monotone games, bandit feedback | last-iterate convergence rate: O(T^{-1/3}) -> O(T^{-1/2}) | Helped |
| Apply the algorithm to games that converge to a static game | Proposed mirror-descent algorithm · Converging monotone games | last-iterate convergence rate: asymptotic -> O(T^{-1/4 + \alpha}) | Helped |
| Use the proposed method for equilibrium tracking | Monotone games · Equilibrium tracking games | average gap convergence rate: T^{\varphi/5-1/5 } -> O \left(\max\{T^{2\varphi/3-2/3 }, T^{(4\varphi + 5)^2/72-9/8}\}\right); T^{\varphi/3-2/3} -> O \l | Helped |
| Use the proposed algorithm instead of online mirror descent or gradient descent with full information | Three static games · Cournot competition, zero-sum matrix game, and monotone zero-sum matrix game | performance | No clear effect |
| Use gradient descent with the ellipsoidal estimated gradient rather than the proposed algorithm | Three static games · Cournot competition and monotone zero-sum matrix game | performance | Hurt |
Limitations
- Rate O(T^-1/4) for general monotone games is slower than O(T^-1/2) achieved only under strong monotonicity.
- Linear costs yield only O(T^-1/6), with the authors noting open questions on improvement.
- Experiments are small-scale (5-player Cournot, 2x2 matrix games) with an unspecified-in-detail tuning of learning rates.
Experimental setup
Benchmarks: Cournot competition zero-sum matrix game monotone zero-sum matrix game
Metrics: convergence to Nash equilibrium regret
Baselines: online mirror descent with full information gradient descent with exact gradient gradient descent with estimated gradient
Builds on: online mirror descent ellipsoidal gradient estimator (bandit convex optimization) self-concordant barrier
Closest papers by meaning
- The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback (ICML 2025 · similarity 0.91)
- No-regret Learning in Harmonic Games: Extrapolation in the Face of Conflicting Interests (NeurIPS 2024 · similarity 0.90)
- Local and Adaptive Mirror Descents in Extensive-Form Games (NeurIPS 2024 · similarity 0.89)
- Convergence of No-Swap-Regret Dynamics in Self-Play (NeurIPS 2024 · similarity 0.89)
- Near-Optimal Last-Iterate Convergence for Zero-Sum Games with Bandit Feedback and Opponent Actions (NeurIPS 2026 · similarity 0.89)
- From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applications (NeurIPS 2025 · 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.