# Average-and Last-Iterate Lower Bounds for Optimistic Matrix Mirror-Prox in Quantum Zero-Sum Games

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 3 of its 9 references that are in the map.
- First posted on arXiv 30 Sep 2026.

## Builds on (most cited first, 3 of 3)

- [Optimization, Learning, and Games with Predictable Sequences](https://mlsanity.com/paper/1311.1869/) (2013)
- [Learning in quantum games](https://mlsanity.com/paper/2302.02333/) (2023)
- [A Quadratic Speedup in Finding Nash Equilibria of Quantum Zero-Sum Games](https://mlsanity.com/paper/2311.10859/) (2023)

## Abstract (arXiv)

Optimistic matrix mirror-prox (OMMP) computes ε-approximate Nash equilibria in quantum zero-sum games with an O(1/varepsilon) 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 Omega(1/varepsilon) 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 Theta(1/t) and duality gap Theta(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 Theta(1/t), while the duality gap decays as Theta(1/t2).