Research map / Bandits and online learning / Online convex optimization and games

Near-Optimal Last-Iterate Convergence for Zero-Sum Games with Bandit Feedback and Opponent Actions

NeurIPS 2026 · Bandits and online learning › Online convex optimization and games · approach: Last-iterate convergence in games · 0 citations (OpenAlex)

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 PMO-LB, a phased minimax algorithm with log-barrier regularization that exploits opponent-action feedback to achieve high-probability t^{-1/2} last-iterate duality-gap convergence in bandit zero-sum games.

Problem

Last-iterate convergence in two-player zero-sum games with bandit feedback is slow (t^{-1/4} high-probability) when players only see their own loss; it is unknown whether observing the opponent's action enables faster last-iterate convergence.

Approach

Epoch-based soft-elimination: each epoch solves for the Nash equilibrium of an estimated log-barrier-regularized game built from empirical mean estimates of the matrix, with a new multiplicative-stability proof that works for games and generalizes the FALCON analysis.

Key results

• Proves high-probability duality gap O(d^2 sqrt(log(d log t/delta)/t)) for PMO-LB, i.e., t^{-1/2} last-iterate convergence with opponent-action feedback, versus t^{-1/4} without it.
• On two GUARD security games over 10^7 rounds (10 runs each), PMO-LB consistently achieves lower duality gap than five baselines, including the naive uniform-exploration method.
• The naive uniform-exploration baseline achieves only O(d^{1/2} t^{-1/4}) high-probability duality gap.

Surprising findings

• Estimating the duality gap of a pure strategy requires playing other potentially bad strategies, so hard-elimination and low-regret-low-variance analyses fail even when a pure Nash equilibrium exists.

Limitations

• Dependence on dimension d^2 is likely suboptimal and not matched by a lower bound for last-iterate with opponent-action feedback.
• Requires observing the opponent's action; the setting does not apply when only own loss is observed.
• Hyperparameters for baselines tuned for stable performance rather than theory in experiments.

Experimental setup

Datasets: GUARD Green Security Game environment (synthetic security game matrices)

Benchmarks: GUARD security game matrices of size 61x21 and 39x35

Metrics: duality gap fitted convergence slope

Baselines: naive uniform-exploration NE estimate prior bandit last-iterate methods without opponent-action feedback (four methods

Builds on: FALCON Follow-the-Regularized-Leader with log-barrier UCB

Closest papers by meaning

• From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applications (NeurIPS 2025 · similarity 0.95)
• Last-Iterate Convergence Properties of Regret-Matching Algorithms in Games (ICLR 2025 · similarity 0.93)
• The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback (ICML 2025 · similarity 0.93)
• Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms (NeurIPS 2024 · similarity 0.92)
• Convergence of No-Swap-Regret Dynamics in Self-Play (NeurIPS 2024 · similarity 0.90)
• Best of Both Worlds: Regret Minimization versus Minimax Play (ICML 2025 · similarity 0.90)