Research map / Optimization / Nonconvex and smooth optimization
Adaptively Perturbed Mirror Descent for Learning in 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.
Proposes Adaptively Perturbed Mirror Descent (APMD), which keeps the payoff-perturbation strength fixed but periodically resets the slingshot (anchor) strategy to the current strategy, giving non-asymptotic last-iterate gap rates in full and noisy feedback for monotone games.
Problem
Last-iterate convergence to Nash equilibrium in smooth monotone games when gradient feedback is noisy; existing payoff-perturbation methods need carefully decayed perturbation strengths and give only asymptotic guarantees.
Approach
Keep the perturbation strength mu constant and perturb payoffs by a divergence G from a slingshot strategy that is re-initialized to the current strategy every T_sigma iterations, so the perturbation magnitude adapts automatically; this yields non-asymptotic rates O(ln T/sqrt T) (full feedback) and O(ln T / T^{1/10}) (noisy feedback).
Key results
- APMD achieves last-iterate gap rate O(ln T/sqrt T) under full feedback with constant learning rate and T_sigma = Theta(ln T).
- Under noisy feedback APMD achieves E[GAP] = O(ln T / T^{1/10}) with T_sigma = Theta(T^{4/5}).
- In zero-sum polymatrix games APMD converges faster than MWU and OMWU under both full and noisy feedback (averaged over 100 seeds).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Apply adaptive slingshot payoff perturbation using squared L2 distance | Mirror Descent in zero-sum polymatrix games · 3BRPS and random payoff games with 10 and 50 actions, full feedback | gap function | Helped |
| Apply adaptive slingshot payoff perturbation | Mirror Descent in zero-sum polymatrix games · 3BRPS and random payoff games with 10 and 50 actions, noisy feedback | gap function | Helped |
| Use squared L2 distance rather than the tested KL-based divergences | APMD · 3BRPS and random payoff games with 10 and 50 actions, full feedback | gap function | Helped |
| Use squared L2 distance rather than the tested KL-based divergences | APMD · 3BRPS and random payoff games with 10 and 50 actions, noisy feedback | gap function | Mixed |
Surprising findings
- OMWU fails to converge under noisy feedback and orbits the equilibrium, per the reported experiments.
- The noisy-feedback rate is O(ln T / T^{1/10}) with T_sigma = Theta(T^{4/5}), much slower than the full-feedback rate.
Limitations
- The noisy-feedback rate O(ln T / T^{1/10}) is much slower than the full-feedback rate and may not be tight.
- Main theory is for squared l2 distances with bounded gradients; general divergences only have asymptotic convergence results.
- Experiments are limited to two small zero-sum polymatrix games.
Experimental setup
Datasets: random payoff games (synthetic) three-player biased rock-paper-scissors
Benchmarks: three-player biased rock-paper-scissors three-player random payoff games (10 and 50 actions)
Metrics: gap function
Baselines: MWU OMWU
Builds on: mirror descent optimistic mirror descent mutant FTRL multiplicative weights update
Closest papers by meaning
- Boosting Perturbed Gradient Ascent for Last-Iterate Convergence in Games (ICLR 2025 · similarity 0.93)
- Local and Adaptive Mirror Descents in Extensive-Form Games (NeurIPS 2024 · similarity 0.90)
- Optimistic Mirror Descent Either Converges to Nash or to Strong Coarse Correlated Equilibria in Bimatrix Games (NeurIPS 2022 · similarity 0.89)
- Stochastic No-regret Learning for General Games with Variance Reduction (ICLR 2023 · similarity 0.88)
- Learning to Steer Learners in Games (ICML 2025 · similarity 0.87)
- Uncoupled and Convergent Learning in Monotone Games under Bandit Feedback (NeurIPS 2025 · similarity 0.87)
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.