
YZ
Yuheng Zhang
· 1 min read
ResearcharXiv cs.LG
Minimax Last-Iterate Convergence in Matrix Games with Observed Actions
arXiv:2609.34656v1 Announce Type: new
Abstract: We study last-iterate convergence in unknown two-player zero-sum matrix games with bandit payoff feedback and observed opponent actions. For games with $d$ actions per player, we develop an algorithm achieving a duality gap of $\widetilde{\mathcal{O}}(\sqrt{d/t})$ with high probability, simultaneously at every round $t$. This improves the dimension dependence of the best previously known guarantee by a factor of $d^{3/2}$. The rate matches a standard bandit lower bound, establishing minimax optimality in both the number of actions and the number of rounds, up to logarithmic factors. The algorithm is computationally efficient, requiring only $\mathcal{O}(d)$ time and memory per round. Our technical contribution is a joint design of adaptive averaging and corrected exponential weights that absorbs estimation variance, together with a potential argument that bounds phase durations.
Original source
This story was published by arXiv cs.LG and written by Yuheng Zhang. SyncAI.news shows a preview; the complete article is on the publisher's site.
Read the full story on arxiv.org


