Skip to yearly menu bar Skip to main content


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

Abstract: We propose the first online quantum algorithm for zero-sum games with O~(1) regret under the game setting. Moreover, our quantum algorithm computes an ε-approximate Nash equilibrium of an m×n matrix zero-sum game in quantum time O~(m+n/ε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.

Chat is not available.