Optimistic matrix mirror-prox (OMMP) computes ε-approximate Nash equilibria in quantum zero-sum games with an O(1/ε) average-iterate guarantee [arXiv:2311.10859]. We investigate whether this dependence on accuracy is tight and whether geometric last-iterate convergence can be guaranteed. We study these questions through explicit games with one qubit per player. First, we prove an Ω(1/ε) lower bound for the uniform-average output that includes the maximally mixed initial state, independently of the regularizer and step size. Second, we construct a fixed game on which optimistic gradient descent-ascent (OGDA), initialized at the maximally mixed state, has last-iterate Frobenius distance to equilibrium Θ(1/t) and duality gap Θ(1/t3) for every sufficiently small fixed step size. A separate fixed game exhibits arbitrarily long delays in reducing the initial error by a constant factor across a family of initial states. Finally, we give a fixed game with a unique, strictly complementary equilibrium on which optimistic matrix multiplicative weights updates (OMMWU) converge only polynomially from the maximally mixed state for every fixed positive step size. The last-iterate Frobenius distance and quantum relative entropy from the equilibrium to the iterates decay as Θ(1/t), while the duality gap decays as Θ(1/t2).
Figures & tables
Figure 1: One Alice projection for OGDA in the (u,w) cross-section of the Bloch sphere. The pure input satisfies u2+w2=1 . Subtracting hQ , where h≥0 , shifts the Bloch vector from (u,w) to (u,w+h) along the orange arrow. The blue arrow is the radial projection onto the unit circle, giving (u′,w′)=(u/N,(w+h)/N) with N=1+2hw+h2 . Writing c=u/2 and c′=u′/2 for the input and output coherences, we have c′=c/N≥c/(1+h) . Thus a small shift changes the coherence only slightly.
Figure 2: OMMWU in the (x,z) cross-section of the Bloch ball. Alice’s state αt has Bloch radius tanhRt and lies on the radius through the pure state Pt+ associated with the leading eigenvector of Ht . The orange segment represents the radial concentration 1−tanhRt=O(e−2κt) . The angle between this radius and the equilibrium direction satisfies θt∼p∞/(κt) . Thus Alice’s state approaches the moving pure state Pt+ exponentially fast, while its direction approaches P at rate 1/t . The radial separation is enlarged to distinguish the two errors.
Figure 3: OGDA on UG=Q⊗Q from (ρr,P) with η=1/8 . Top: gap and distance versus iteration. Bottom: errors normalized by their initial values versus tηr . Open circles mark Tr ; dotted lines mark the normalized thresholds 1/2 and 1/2 from ( 4.15 ). The top panels use logarithmic vertical axes and symlog horizontal axes to include t=0 .
Figure 4: Initialization control for OGDA on UG=Q⊗Q with η=1/8 . Normalized gap (left) and distance (right) from the maximally mixed state (black) and coherent starts (colored). Open circles mark the mixed run’s first zero at t=13 and the coherent horizon T10−1=12 ; the other horizons exceed the displayed window.
Figure 5: OGDA from (I/2,I/2) on UGmix with η=1/8 . Played-iterate distance (left) and gap (right) on logarithmic axes, with dashed asymptotes 32/t and 2048/t3 from Theorem 4.9 . Annotated slopes are fitted over 104≤t≤105 . Open circles mark the final recorded iterate.
Figure 6: OMMWU from (I/2,I/2) on UM with η=1/8 . Solid curves show the played-iterate errors on logarithmic axes; dashed curves show the asymptotes from Theorem 5.2 . Annotated slopes are fitted over 104≤t≤105 .
This paper studies the convergence of the Optimistic Multiplicative Weights Update algorithm (OMWU) in two player zero-sum games. Recent works have identified instances on which the last-iterate of OMWU can converge arbitrarily slowly, but understanding when and why this slow convergence occurs has remained open. In this work, we develop a new analysis framework that gives sharp, quantitative explanations for this behavior. Our analysis is based on viewing the algorithm's dual iterates as an optimistic skew-gradient descent with respect to an energy function. We prove over the dual iterates that energy is dissipative, and by establishing tight bounds on the magnitude of dissipation, our analysis quantifies the geometric bottlenecks that arise when the corresponding primal iterates are close to the simplex boundary. This further translates into a new linear last-iterate convergence rate in KL divergence on games with a unique and interior Nash equilibrium. Compared to prior work, this new rate contains a much sharper dependence on game-specific constants, and we prove this dependence is optimal. Moreover, these geometric insights further translate into new separations on uniform convergence rates for OMWU. On the one hand, we prove constant lower bounds on the uniform best-iterate convergence rate in KL divergence and total variation distance from Nash. On the other hand, we establish for the 2×2 setting a new O(T−1/2) best-iterate rate in duality gap, improving substantially over prior work. Together, this shows in general that uniform convergence rate guarantees do not transfer across different measures of distance to Nash.
John Lazarsfeld, Anas Barakat, Georgios Piliouras +2
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
ENSAE Paris – CREST, France · ENS Lyon, France · Isara Labs +2
We study bimatrix two-player games and investigate the last-iterate convergence and stability of equilibria for the iterates generated by the optimistic exponential weights method. In contrast to prior work, we allow the step sizes ηx and ηy to differ. Our first main result establishes, under the assumption that the set of fixed points is finite, a sufficient condition for global last-iterate convergence in the special case of zero-sum games, which constrains only the product ηxηy of the step sizes. This condition is practically relevant and partially explains empirically observed behavior. Our second main result provides an almost-tight threshold for asymptotic stability and instability, again in terms of products of the step sizes, for general bimatrix games. This result is primarily of theoretical interest. We derive several known results and practically relevant step size bounds for special cases and illustrate our results by experiments.
Hédi Hadiji, Sarah Sachs
Laboratoire des Signaux et Systèmes, CentraleSupélec, Paris, France · School of Mathematics, University of Bristol, Bristol, United Kingdom