Optimal last-iterate convergence in matrix games with bandit feedback using the log-barrier

Côme Fiegel, Pierre Ménard, Tadashi Kozuno, Michal Valko, Vianney Perchet

Preprint

Abstract

We address the problem of minimax policy learning in zero-sum matrix games with bandit feedback. We demonstrate that employing log-barrier regularization with a dual-focused analysis achieves a convergence rate of $\tilde{O}(t^{-1/4})$ on the exploitability gap, matching the previously established lower bound. Our method extends to extensive-form games with equivalent performance guarantees.

PDF · arXiv preprint · bibtex · DOI