






















Abstract: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.
| Subjects: | Machine Learning (cs.LG) |
| Cite as: | arXiv:2604.15242 [cs.LG] |
| (or arXiv:2604.15242v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2604.15242 arXiv-issued DOI via DataCite (pending registration) |
From: Michal Valko [view email]
[v1]
Thu, 16 Apr 2026 17:17:42 UTC (40 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。