Logarithmic-Regret Quantum Learning Algorithms for Zero-Sum Games

Abstract

We propose the first online quantum algorithm for solving zero-sum games with $\tilde{O}(1)$ regret under the game setting. Moreover, our quantum algorithm computes an $\epsilon$-approximate Nash equilibrium of an $m\times n$ matrix zero-sum game in quantum time $\tilde{O}(\sqrt{m+n}/{\epsilon }^{2.5})$. Our algorithm uses standard quantum inputs and generates classical outputs with succinct descriptions, facilitating end-to-end applications. Technically, our online quantum algorithm "quantizes" classical algorithms based on the optimistic multiplicative weight update method. At the heart of our algorithm is a fast quantum multi-sampling procedure for the Gibbs sampling problem, which may be of independent interest.

35 pages, 1 table, 4 algorithms. Close to the conference version. Corrected the contraints of the norm of A in Theorem 1.1 due to an error found in [v1, Theorem B.8]