Source-linked AI summary
Optimal last-iterate convergence in matrix games with bandit feedback using the log-barrier
Come Fiegel, Pierre Menard, Tadashi Kozuno, Michal Valko, Vianney Perchet
TL;DR
For uncoupled players unable to communicate, prior methods did not achieve the O(t^-1/4) rate in the desired setting: one coupled players, while the other lacked full last-iterate guarantees. The approach combines mirror descent, varying log-barrier regularization, and analysis focused on the dual norm of the regularized operator. O-tilde(t^-1/4) anytime last-iterate convergence is obtained with high probability for bandit matrix games, and the approach is extended to extensive-form games.
Problem
For uncoupled players unable to communicate, prior methods did not achieve the O(t^-1/4) rate in the desired setting: one coupled players, while the other lacked full last-iterate guarantees.
Source: §1 · p. 2Method
Results
O-tilde(t^-1/4) anytime last-iterate convergence is obtained with high probability for bandit matrix games, and the approach is extended to extensive-form games.
Source: §1 · p. 2, §8 · p. 10Takeaways & Limitations
The conclusion states that the algorithms achieve high-probability last-iterate convergence without prior knowledge of the horizon.
Source: §8 · p. 10Algorithm 2 updates the whole tree each iteration, implying time complexity of at least Ω(K) per iteration.
Source: §8 · p. 10
Abstract
from arXiv · showhide
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.
1 Introduction
The introduction frames last-iterate convergence under bandit feedback as a harder problem than regret-based convergence. It presents a log-barrier and dual-focused approach aimed at the uncoupled players’ O(t^-1/4) limit.
1 Introduction
- Zero-sum matrix games seek minimax policies that are optimal against worst-case opponents.One player maximizes the shared reward while the other minimizes it.Source: §1 · p. 1
- With full-information feedback, regret methods achieve O(t^-1/2), improvable to O(t^-1) with optimism; bandit regret methods achieve O(t^-1/2).For bandit last-iterate convergence, Cai et al. (2023) report O(t^-1/8) with high probability and O(t^-1/6) in expectation.Source: §1 · pp. 1–2
- Regret-based methods generally guarantee ergodic convergence—the average of played policies—whereas last-iterate convergence concerns the policies played directly.Problem-independent O(t^-1) and problem-dependent linear rates are reported for last-iterate convergence in the cited full-information literature.Source: §1 · pp. 1–2
- Fiegel et al. (2025) show that uncoupled players cannot guarantee a rate better than O(t^-1/4), while prior methods at that rate rely on coupling or only guarantee convergence near a chosen horizon.The setting disallows communication about players’ actions.Source: §1 · p. 2
- The proposed log-barrier mirror-descent method uses dual-focused analysis to obtain anytime O-tilde(t^-1/4) last-iterate convergence with bandit feedback.The paper also extends the approach to extensive-form games using a dilation of the same regularizer.Source: §1 · p. 2
2 Problem formulation
The problem is to find minimax policies in an unknown zero-sum game from repeated bandit play. The exploitability gap measures how far a policy profile is from minimax, and uncoupled players face an O(t^-1/4) lower bound.
2 Problem formulation
- A minimax profile is the target, and its existence is guaranteed by von Neumann’s result.The players may choose stochastic mixed policies.Source: §2 · p. 2
- The exploitability gap is zero if and only if the profile is minimax, giving it strategic meaning beyond distributional distance.The passage contrasts it with total variation, which has no strategic interpretation.Source: §2 · p. 2
- At each iteration, both players sample actions from their mixed policies and observe the loss associated with those moves.The game has two players choosing actions from their respective action sets; the min-player minimizes loss and the max-player maximizes it.Source: §2 · p. 2
- In the unknown-game setting without communication between players, convergence of the exploitability gap cannot be guaranteed faster than O(t^-1/4).This is the lower bound established by Fiegel et al. (2025).Source: §2 · p. 3
3 Characterization as a variational inequality problem
The paper recasts minimax learning as a variational inequality and uses importance-sampling estimates because the operator is not directly observed under bandit feedback. Those estimates are unbiased but can have unbounded variance.
3 Characterization as a variational inequality problem
- The variational inequality generalizes the minimax-profile problem, and convex-concavity of the loss supports this characterization.The loss is linear in each player’s policy in this setting.Source: §3 · p. 3
- Because the bandit setting does not reveal the operator directly, the method uses importance-sampling estimates of player losses and the operator.The estimates use the sampled actions and observed loss at each iteration.Source: §3 · p. 3
- The importance-sampling estimator is unbiased but unbounded, and its variance can grow arbitrarily large as the probability of an action with nonzero loss approaches zero.The cited passage states that the relevant quantity diverges as such action probabilities go to zero.Source: §3 · pp. 3–4
4 Intuition of the approach
Regularizing the operator can support last-iterate convergence, but the paper shifts from tracking the regularized solution to bounding the dual norm of the regularized operator. The Euclidean illustration relies on a second-order assumption that does not hold for the bandit estimator in that norm.
4 Intuition of the approach
- The zero-sum operator is monotone, which explains solvability, but last-iterate convergence remains difficult, especially under bandit feedback.Regularization is introduced as a previously studied route to last-iterate convergence.Source: §4 · p. 4
- A strongly convex regularizer makes the regularized operator strongly monotone, and prior mirror-descent analysis obtains primal convergence to its regularized solution with an additional dependence on the regularization strength.The cited regularizer is 1-strongly convex with respect to the L1 norm.Source: §4 · p. 4
- The proposed analysis bounds the dual norm of the regularized operator on the iterates instead of tracking convergence to a regularized solution.The paper presents the Euclidean norm as an illustrative case before giving a more formal log-barrier result.Source: §4 · p. 4
- The Euclidean illustration assumes a bounded second-order moment for the unbiased estimate, but that assumption is not realistic for the bandit estimator.The paper says the earlier result cannot be applied in this setting because the assumption fails at least with the Euclidean norm.Source: §4 · pp. 4–5
5 Main algorithm
The algorithm combines mirror descent with a varying log-barrier regularization and a dual-focused analysis. Under parameter assumptions, it provides high-probability convergence at every iteration.
5 Main algorithm
- Algorithm 1 uses mirror descent with the log-barrier regularizer and takes regularized importance-sampling estimates as its steps.Its inputs include a learning rate, regularization strength, starting iteration, and confidence level.Source: §5 · p. 6
- Under Assumption 5.1, Algorithm 1 has high-probability near-optimal convergence guarantees at every iteration.The theorem states the guarantee for any confidence δ > 0.Source: §5 · p. 6
- Tracking the dual norm of F_τt(w_t), rather than convergence to a regularized solution, permits varying τ_t and true last-iterate guarantees without a fixed known horizon.The method uses regularized importance-sampling estimates as mirror-descent steps.Source: §5 · p. 6
- The log-barrier bounds primal-iterate variation almost surely at every iteration, whereas Shannon entropy gives this bound only in expectation.The paper identifies this stability difference as part of why its guarantees hold with high probability.Source: §5 · p. 6
6 Analysis of the Algorithm
The analysis controls a regularizer-linked distance recursively despite changing local norms and simplex constraints. A high-probability bound on this quantity yields an exploitability-gap bound across iterations.
6 Analysis of the Algorithm
- Locally defined norms linked to the regularizer play the role of the Section 4 norm and satisfy the required second-order-moment assumption.The analysis also establishes Lipschitz properties with respect to these local norms.Source: §6 · p. 7
- The constrained analysis uses a more precise quantity than the norm of F_τ(w), and that quantity bounds exploitability at every iteration.Without constraints, the quantities are equivalent because the normal cone reduces to {0}.Source: §6 · p. 7
- The recursion must account for second-order update approximations, changing local norms, and constraints keeping w in the product of simplices.These additional terms make the proof complex.Source: §6 · pp. 7–8
- A high-probability recursive bound on d_τt(w_t) holds across iterations and yields a bound on the exploitability gap.The iteration indices are offset by T_0 to ensure initial conditions, and the proof uses a variation of Azuma–Hoeffding.Source: §6 · p. 8
7 Extension to extensive-form games
The paper extends its approach to extensive-form games with perfect recall by working with sequence-form policies and corresponding importance-sampling estimates. The resulting algorithm has the same kind of guarantees as the matrix-game algorithm.
7 Extension to extensive-form games
- The extension considers sequential-action games with perfect recall, where each player remembers past observations and actions and each information set has a unique path.The game is described using a state tree, player information sets and action sets, transitions, and bounded losses.Source: §7 · pp. 8–9
- Although losses are not linear in each player's policy, they are linear in the corresponding sequence-form policies, which define the profile used to express expected loss and the operator F.The max-player's sequence-form policy is defined similarly.Source: §7 · p. 9
- The extensive-form importance-sampling estimate is unbiased when w_t(x,a) > 0 for all states and actions.The estimate is used for the operator F, and the algorithm applies the same importance-sampling approach in this setting.Source: §7 · p. 9
- Algorithm 2 has the same kind of guarantees as Algorithm 1, with a high-probability guarantee at every iteration under Assumption 5.1.The proof follows Theorem 5.2 using the properties established for the extensive-form operator and estimate.Source: §7 · p. 10
8 Conclusion
The conclusion presents Algorithms 1 and 2 as addressing earlier approaches’ main issue through horizon-independent, high-probability last-iterate convergence and dual-space analysis. It also identifies open questions about proof length, regularization, optimistic updates, and the cost of extensive-form updates.
8 Conclusion
- Algorithms 1 and 2 use log-barrier regularization and dual-space analysis to obtain high-probability last-iterate convergence without prior horizon knowledge.The conclusion describes this as solving the main issue behind earlier approaches.Source: §8 · p. 10
- Whether log-barrier regularization is necessary for horizon adaptivity, and whether optimistic mirror descent could work more efficiently, remain open questions.The conclusion also asks whether other regularizers might adapt to the horizon, potentially without high-probability guarantees.Source: §8 · p. 10
- Algorithm 2 has time complexity of at least Ω(K) per iteration because it updates the whole tree; trajectory-only updates are raised as a possible efficiency direction.The conclusion also asks whether the proof can be simplified, noting its length.Source: §8 · p. 10
A Proof - Main lemmas
The main-lemmas proof develops operator and estimator properties, then uses a stopping-time argument to control an event across iterations.
A Proof - Main lemmas
- The proof uses Ville’s inequality to bound the probability of a stopping-time event through a stopped process.The displayed derivation concludes with a probability bound of at most δ.Source: A Proof - Main lemmas · pp. 12–14
- The proof invokes an importance-sampling estimator and identifies its estimate as unbiased.The passage introduces the estimator and refers to its unbiased estimate.Source: A Proof - Main lemmas · p. 15
- The operator is described as linear and monotone, with a K-Lipschitz property stated for two norms.K is defined as the total number of actions across both trees.Source: A Proof - Main lemmas · pp. 14–15
B Proof - Technical lemmas
These technical proofs establish divergence properties, approximate mirror-step relations, and recursive bounds used in the convergence argument.
B Proof - Technical lemmas
- The Itakura-Saito divergence component is nonnegative, and a value at most 1/6 implies its argument lies between 1/2 and 2.The proof also introduces an unrestricted mirror step and applies Bregman-divergence properties.Source: B Proof - Technical lemmas · pp. 16–17
C Proof - First order approximations of the next iterate
- The first-order analysis treats the inverse Hessian times the estimated or expected operator as approximating the corresponding next-iterate change.An assumption makes the learning rate small enough for second-order terms to be negligible relative to first-order terms.Source: C Proof - First order approximations… · p. 18
D Proof - Recursive bound
- The proof obtains a result from Proposition C.3 and Proposition C.5.Source: D Proof - Recursive bound · p. 24
E Proof - Final bound
The final proof applies its lemmas under parameter conditions to state high-probability guarantees for both algorithms at every iteration. It also notes that a suitable starting parameter T0 exists once η and τ are fixed.
E Proof - Final bound
- For fixed η and τ, the proof says some T0 satisfying the third parameter assumption is always guaranteed to exist.The third assumption also provides the starting condition used in the stopping-time lemma.Source: E Proof - Final bound · p. 25
- With parameters satisfying Assumption 5.1, Theorem 5.2 states a probability-at-least-1−δ guarantee for Algorithm 1 that holds at every iteration t.The theorem’s displayed bound is not specified in these passages.Source: E Proof - Final bound · p. 26
- Theorem 7.4 states the corresponding probability-at-least-1−δ guarantee for Algorithm 2 at every iteration t under Assumption 5.1.The proof says this follows by the same proof as above.Source: E Proof - Final bound · p. 27