cs.LGMay 10, 2026

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

Authors: Soumita Hait, Ping Li, Haipeng Luo, Mengxiao Zhang

Organizations: University of Southern California · Shanghai University of Finance and Economics · University of Iowa

Abstract

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.

Explore similar work

CardsList
Apr 17, 2026cs.LG

The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback

We study the problem of learning in zero-sum matrix games with repeated play and bandit feedback. Specifically, we focus on developing uncoupled algorithms that guarantee, without communication between players, the convergence of the last-iterate to a Nash equilibrium. Although the non-bandit case has been studied extensively, this setting has only been explored recently, with a bound of O(T−1/8)\mathcal{O}(T^{-1/8}) on the exploitability gap. We show that, for uncoupled algorithms, guaranteeing convergence of the policy profiles to a Nash equilibrium is detrimental to the performance, with the best attainable rate being Ω(T−1/4)Ω(T^{-1/4}) in contrast to the usual Ω(T−1/2)Ω(T^{-1/2}) rate for convergence of the average iterates. We then propose two algorithms that achieve this optimal rate up to constant and logarithmic factors. The first algorithm leverages a straightforward trade-off between exploration and exploitation, while the second employs a regularization technique based on a two-step mirror descent approach.
Côme Fiegel, Pierre Ménard, Tadashi Kozuno +2
Imperfect-Information GamesMirror DescentBanditsExploitationHard
AskPDF
Apr 16, 2026cs.LG

Optimal last-iterate convergence in matrix games with bandit feedback using the log-barrier

We study the problem of learning minimax policies in zero-sum matrix games. Fiegel et al. (2025) recently showed that achieving last-iterate convergence in this setting is harder when the players are uncoupled, by proving a lower bound on the exploitability gap of Omega(t^{-1/4}). Some online mirror descent algorithms were proposed in the literature for this problem, but none have truly attained this rate yet. We show that the use of a log-barrier regularization, along with a dual-focused analysis, allows this O-tilde(t^{-1/4}) convergence with high-probability. We additionally extend our idea to the setting of extensive-form games, proving a bound with the same rate.
Come Fiegel, Pierre Menard, Tadashi Kozuno +2
Imperfect-Information GamesMirror DescentMinimaxBanditsConvergenceExploitation
AskPDF
May 31, 2026cs.LG

Fairness in two-player zero-sum games with bandit feedback

We study two-player zero-sum games (TPZSGs) with bandit feedback under fairness constraints requiring every action to be played with probability at least α/mα/m. Existing instance-dependent results target pure\textit{pure} Nash equilibria, while fairness generically produces mixed\textit{mixed} equilibria, a harder learning target. Our key technical tool is a reparametrization: every fair strategy decomposes as p=(α/m)1+(1−α)p~p = (α/m)\mathbf{1} + (1-α)\widetilde{p} with p~∈Δm\widetilde{p} \in Δ_m, and substituting into the payoff form yields p⊤Aq=p~⊤A~qp^{\top}Aq = \widetilde{p}^{\top}\widetilde{A} q for a fair payoff matrix A~:=(1−α)A+α1c⊤\widetilde{A} := (1-α)A + α\mathbf{1} c^{\top}, where cj=1m∑iA(i,j)c_j = \tfrac{1}{m}\sum_i A(i,j) is the column-mean vector. The fair game on AA is then equivalent to a standard zero-sum game on A~\widetilde{A}, so equilibrium existence, KKT structure, and LP basis stability reduce to classical results applied to A~\widetilde{A}. We derive the fair minimax value, fair Nash equilibrium, fair regret, and a clean dual representation showing the price of fairness is at most α(1−1/m)α(1-1/m) and vanishes whenever the unconstrained equilibrium already has full support. Our main result is an O~(T2/3)\widetilde{O}(T^{2/3}) regret bound for an Explore-Then-Commit algorithm, Fair-ETC-TPZSG\texttt{Fair-ETC-TPZSG}, applicable to general mixed fair equilibria, together with a discussion of why naive action elimination does not readily improve it. When the fair equilibrium has a single dominant action, equivalently when p~⋆\widetilde{p}^{\star} is a vertex of ΔmΔ_m, the bound sharpens to instance-dependent O~(1/Δ~(α)2)\widetilde{O}(1/\widetildeΔ(α)^{2}), where Δ~(α)\widetildeΔ(α) is the LP-margin gap.
S Akash, Pratik Gajane
BanditsEquilibriumFeedback Learning
AskPDF