Poster

Logarithmic-Regret Quantum Learning Algorithms for Zero-Sum Games

Minbo Gao · Zhengfeng Ji · Tongyang Li · Qisheng Wang

Great Hall & Hall B1+B2 (level 1) #1713
[ ]
Tue 12 Dec 8:45 a.m. PST — 10:45 a.m. PST

Abstract: We propose the first online quantum algorithm for zero-sum games with $\widetilde O(1)$ regret under the game setting. Moreover, our quantum algorithm computes an $\varepsilon$-approximate Nash equilibrium of an $m \times n$ matrix zero-sum game in quantum time $\widetilde O(\sqrt{m+n}/\varepsilon^{2.5})$. Our algorithm uses standard quantum inputs and generates classical outputs with succinct descriptions, facilitating end-to-end applications. As an application, we obtain a fast quantum linear programming solver. 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.

Chat is not available.