Optimal last-iterate convergence in matrix games with bandit feedback using the log-barrier
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908970693689344 |
|---|---|
| author | Fiegel, Come Menard, Pierre Kozuno, Tadashi Valko, Michal Perchet, Vianney |
| author_facet | Fiegel, Come Menard, Pierre Kozuno, Tadashi Valko, Michal Perchet, Vianney |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_15242 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Optimal last-iterate convergence in matrix games with bandit feedback using the log-barrier Fiegel, Come Menard, Pierre Kozuno, Tadashi Valko, Michal Perchet, Vianney Machine Learning 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. |
| title | Optimal last-iterate convergence in matrix games with bandit feedback using the log-barrier |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2604.15242 |