Logarithmic-Regret Quantum Learning Algorithms for Zero-Sum Games
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. 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.
Cite
Text
Gao et al. "Logarithmic-Regret Quantum Learning Algorithms for Zero-Sum Games." Neural Information Processing Systems, 2023.Markdown
[Gao et al. "Logarithmic-Regret Quantum Learning Algorithms for Zero-Sum Games." Neural Information Processing Systems, 2023.](https://mlanthology.org/neurips/2023/gao2023neurips-logarithmicregret/)BibTeX
@inproceedings{gao2023neurips-logarithmicregret,
title = {{Logarithmic-Regret Quantum Learning Algorithms for Zero-Sum Games}},
author = {Gao, Minbo and Ji, Zhengfeng and Li, Tongyang and Wang, Qisheng},
booktitle = {Neural Information Processing Systems},
year = {2023},
url = {https://mlanthology.org/neurips/2023/gao2023neurips-logarithmicregret/}
}