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 regret under the game setting. Moreover, our quantum algorithm computes an -approximate Nash equilibrium of an matrix zero-sum game in quantum time . 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.