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

Problem Statement

The paper addresses the problem of learning in two-player zero-sum games under bandit feedback, where players only observe the noisy loss/reward of the specific action pair played in each round, rather than the full gradient of their mixed strategy. A critical distinction in this work is the assumption that players also observe the opponent's action in addition to their own loss.

The primary goal is to achieve last-iterate convergence to a Nash equilibrium, measured by the duality gap $DGap(x_t, y_t) \to 0$ as rounds $t \to \infty$. This is distinct from and stronger than average-iterate convergence (convergence of the time-averaged strategies) or random-iterate convergence.

Prior work established a strict separation between average-iterate and last-iterate convergence in the absence of opponent-action feedback:

• Average-iterate: Optimal rate of $O(t^{-1/2})$.
• Last-iterate (no opponent actions): Optimal rates are limited to $O(t^{-1/3})$ in expectation and $O(t^{-1/4})$ with high probability.

The central question posed is whether the additional information of observing the opponent's action allows for faster last-iterate convergence, specifically bridging the gap to the optimal $O(t^{-1/2})$ rate.

Methodology

The Algorithm: PMO-LB

The authors propose Phased Minimax Optimization with Log-Barrier Regularization (PMO-LB). The algorithm operates in epochs of doubling length ($2^{s-1}$ to $2^s - 1$).

1. Estimation: Within each epoch $s$, players collect data to compute an empirical estimator $\hat{A}_s$ of the game matrix $A$.
2. Strategy Update: At the start of each epoch, players compute a new mixed strategy pair $(x_s, y_s)$ by solving an estimated log-barrier-regularized game. The payoff function is defined as:
   $$\Phi_s(x, y) \triangleq x^\top \hat{A}_s y + \gamma_s \sum_{i=1}^d \log \frac{1}{x_i} - \gamma_s \sum_{j=1}^d \log \frac{1}{y_j}$$
   where $\gamma_s$ is a learning rate decaying with the epoch.
3. Execution: Players sample actions from $(x_s, y_s)$ for the duration of the epoch.
4. Independence: Despite the coupled nature of the game, the algorithm is uncoupled; each player can compute their strategy independently using only the observed opponent actions and their own losses.

Analytical Approach

The paper argues that standard techniques from the bandit literature (both hard-elimination and soft-elimination) fail to generalize to games even with opponent-action feedback.

• Hard-Elimination: Fails because estimating the duality gap of a pure strategy pair $(e_i, e_j)$ requires playing other potentially "bad" strategies to find best responses, which contradicts the goal of maintaining low regret in every round.
• Standard Soft-Elimination (FALCON-style): Existing analyses rely on a "low-regret-low-variance" property where the variance of an action's estimate is controlled by its regret. The authors show this property is insufficient for games because estimating the duality gap of a strategy pair requires playing strategies that may have high duality gaps themselves.

To overcome this, the authors develop a novel analysis based on multiplicative stability.

• They prove that consecutive strategies $x_s$ and $x_{s-1}$ (and similarly for $y$) are multiplicatively close ($x_{s,i} \leq \alpha x_{s-1,i}$) with high probability.
• This stability is enabled by the log-barrier regularizer, which prevents the probability mass from concentrating too quickly on a subset of actions, thereby controlling the variance of the loss estimators.
• The analysis establishes a "low-duality-gap-low-variance" property that, combined with multiplicative stability, allows bounding the true duality gap without requiring the algorithm to play bad strategies explicitly.

Key Contributions

1. Optimal Last-Iterate Convergence: The paper demonstrates that with opponent-action feedback, it is possible to achieve $O(t^{-1/2})$ last-iterate convergence with high probability. This matches the optimal rate for average-iterate convergence, effectively closing the gap between the two notions in this setting.
2. Algorithmic Efficiency: The proposed algorithm is computationally efficient, requiring only $\log t$ updates (solving a saddle-point optimization problem) after $t$ rounds.
3. Theoretical Novelty: The work identifies fundamental obstacles in generalizing single-player bandit analyses to multi-player games. It introduces a new analytical framework relying on multiplicative stability between consecutive strategies, which is distinct from previous regret-based analyses.
4. Dueling Bandits Improvement: As a special case where the game matrix is skew-symmetric (dueling bandits), the results provide the first last-iterate convergence guarantees for this setting, improving upon prior work that only offered regret bounds.

Results

Theoretical Guarantees

Theorem 4.1: For any fixed $\delta \in (0, 1)$, Algorithm 2 with a specific learning rate schedule guarantees that with probability at least $1-\delta$:
$$DGap(x_t, y_t) = O\left( \frac{d^2 \sqrt{\log(d \log t / \delta)}}{\sqrt{t}} \right)$$
for all $t \geq 1$. This represents a $t^{-1/2}$ convergence rate.

Experimental Validation

The authors evaluated PMO-LB on security game benchmarks (sizes $61 \times 21$ and $39 \times 35$) against five baselines:

• Prior methods without opponent-action feedback (Cai et al. [2023, 2025], Fiegel et al. [2025, 2026]).
• A naive baseline that utilizes opponent actions but mixes the empirical best strategy with uniform exploration (Algorithm 3).

Findings:

• PMO-LB consistently outperformed all baselines.
• Empirical convergence slopes matched theoretical predictions:
  • PMO-LB: $\approx -0.5$ (matching $t^{-1/2}$).
  • Naive Baseline: $\approx -0.25$ (matching $t^{-1/4}$).
  • Prior methods (no opponent actions): Slopes ranged from $-0.175$ to $-0.301$ (matching $t^{-1/8}$ to $t^{-1/3}$).

Significance and Claims

The paper claims to resolve a long-standing open question regarding the impact of opponent-action information on last-iterate convergence. By showing that $t^{-1/2}$ convergence is achievable, the work demonstrates that the "harder path" of last-iterate convergence in bandit feedback settings is not inherently slower than average-iterate convergence, provided the opponent's actions are observable.

The authors emphasize that their contribution is primarily theoretical and algorithmic. They note that while the $d^2$ dependence in the bound might be suboptimal, the $t^{-1/2}$ rate is optimal up to dimension factors. The work also highlights that their analysis techniques (multiplicative stability via log-barrier regularization) may be of independent interest for single-player bandit problems, offering an alternative to existing regret-based analyses.

The paper concludes that observing opponent actions fundamentally mitigates the exploration-exploitation tension required for last-iterate convergence, allowing algorithms to avoid the slow rates previously thought to be unavoidable in bandit feedback settings.