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

arXiv: https://arxiv.org/abs/2605.09363 · HTML: https://mlsanity.com/paper/2605.09363/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Placed in Reward modeling and RLHF, one of 10 directions in LLM alignment / RLHF / preference optimisation.
- Builds on 32 of its 40 references that are in the map.
- First posted on arXiv 10 May 2026.

## Placed in

- LLM alignment / RLHF / preference optimisation / [Reward modeling and RLHF](https://mlsanity.com/alignment/reward-modeling-and-rlhf/)

## Builds on (most cited first, 30 of 32)

- [Nash Learning from Human Feedback](https://mlsanity.com/paper/2312.00886/) (2023)
- [Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits](https://mlsanity.com/paper/1402.0555/) (2014)
- [Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles](https://mlsanity.com/paper/2002.04926/) (2020)
- [A Minimaximalist Approach to Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2401.04056/) (2024)
- [Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits](https://mlsanity.com/paper/1807.07623/) (2018)
- [Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizability](https://mlsanity.com/paper/2003.12699/) (2020)
- [More Adaptive Algorithms for Adversarial Bandits](https://mlsanity.com/paper/1801.03265/) (2018)
- [Provable Self-Play Algorithms for Competitive Reinforcement Learning](https://mlsanity.com/paper/2002.04017/) (2020)
- [Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium](https://mlsanity.com/paper/2002.07066/) (2020)
- [Adapting to Misspecification in Contextual Bandits](https://mlsanity.com/paper/2107.05745/) (2021)
- [Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with O(1/k2) Rate on Squared Gradient Norm](https://mlsanity.com/paper/2102.07922/) (2021)
- [Halpern Iteration for Near-Optimal and Parameter-Free Monotone Inclusion and Strong Solutions to Variational Inequalities](https://mlsanity.com/paper/2002.08872/) (2020)
- [Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability](https://mlsanity.com/paper/2111.12306/) (2021)
- [Accelerated Single-Call Methods for Constrained Min-Max Optimization](https://mlsanity.com/paper/2210.03096/) (2022)
- [Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedback](https://mlsanity.com/paper/2303.02738/) (2023)
- [Accelerated Algorithms for Constrained Nonconvex-Nonconcave Min-Max Optimization and Comonotone Inclusion](https://mlsanity.com/paper/2206.05248/) (2022)
- [No-Regret Learning in Unknown Games with Correlated Payoffs](https://mlsanity.com/paper/1909.08540/) (2019)
- [Matrix games with bandit feedback](https://mlsanity.com/paper/2006.05145/) (2020)
- [A Finite-Sample Analysis of Payoff-Based Independent Learning in Zero-Sum Stochastic Games](https://mlsanity.com/paper/2303.03100/) (2023)
- [Doubly Optimal No-Regret Learning in Monotone Games](https://mlsanity.com/paper/2301.13120/) (2023)
- [Instance-Dependent Regret Bounds for Learning Two-Player Zero-Sum Games with Bandit Feedback](https://mlsanity.com/paper/2502.17625/) (2025)
- [On the Limitations and Possibilities of Nash Regret Minimization in Zero-Sum Matrix Games under Noisy Feedback](https://mlsanity.com/paper/2306.13233/) (2023)
- [From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applications](https://mlsanity.com/paper/2506.03464/) (2025)
- [Decentralized Best-Response-Based Learning in Two-Player Zero-Sum Stochastic Games: A Finite-Sample Analysis](https://mlsanity.com/paper/2409.01447/) (2024)
- [Uniform Last-Iterate Guarantee for Bandits and Reinforcement Learning](https://mlsanity.com/paper/2402.12711/) (2024)
- [Optimal last-iterate convergence in matrix games with bandit feedback using the log-barrier](https://mlsanity.com/paper/2604.15242/) (2026)
- [The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback](https://mlsanity.com/paper/2604.16087/) (2026)
- [Competing Against Equilibria in Zero-Sum Games with Evolving Payoffs](https://mlsanity.com/paper/1907.07723/) (2019)
- [Contextual Multinomial Logit Bandits with General Value Functions](https://mlsanity.com/paper/2402.08126/) (2024)
- [Adversarial Learning in Games with Bandit Feedback: Logarithmic Pure-Strategy Maximin Regret](https://mlsanity.com/paper/2602.06348/) (2026)

## Built on by (most cited first, 4 of 4)

- [Minimax Last-Iterate Convergence in Matrix Games with Observed Actions](https://mlsanity.com/paper/2609.34656/) (2026)
- [Polylogarithmic Nash Regret in Matrix Games with Bandit Feedback](https://mlsanity.com/paper/2609.34812/) (2026)
- [Fast Last-Iterate Convergence in Zero-Sum Markov Games with Bandit Feedback](https://mlsanity.com/paper/2610.05968/) (2026)
- [Thompson Sampling for Learning in Zero-Sum Games](https://mlsanity.com/paper/2610.18899/) (2026)

## Abstract (arXiv)

Last-iterate convergence of learning dynamics in games has attracted significant recent attention. In two-player zero-sum games with bandit feedback, where only the loss of the selected action pair is observed, Fiegel et al. (2025) show a separation between average-iterate and last-iterate convergence in duality gap: while the optimal t^(-1/2) rate after t rounds is achievable for the former via standard no-regret algorithms, the latter cannot converge faster than t^(-1/3) in expectation or t^(-1/4) with high probability. However, in many practical settings, such as preference learning, the players observe not only their loss but also the opponent's action. This raises a natural question: can such additional information enable faster last-iterate convergence? We answer this question affirmatively, showing that t^(-1/2) last-iterate convergence is achievable with high probability in this setting, via an efficient algorithm that updates its strategy infrequently by solving an estimated log-barrier-regularized game. We identify fundamental obstacles preventing standard analysis for multi-armed bandits, the single-player case, from generalizing to games, and develop a novel analysis to overcome them. Experiments confirm that our algorithm indeed converges faster than naive baselines and prior methods that do not exploit opponent-action feedback. Finally, we note that our results also improve those for dueling bandits, a special case with skew-symmetric game matrices.