Logarithmic-Regret Quantum Learning Algorithms for Zero-Sum Games
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916415007621120 |
|---|---|
| author | Gao, Minbo Ji, Zhengfeng Li, Tongyang Wang, Qisheng |
| author_facet | Gao, Minbo Ji, Zhengfeng Li, Tongyang Wang, Qisheng |
| contents | We propose the first online quantum algorithm for solving 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2304_14197 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Logarithmic-Regret Quantum Learning Algorithms for Zero-Sum Games Gao, Minbo Ji, Zhengfeng Li, Tongyang Wang, Qisheng Quantum Physics Machine Learning Optimization and Control We propose the first online quantum algorithm for solving 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. |
| title | Logarithmic-Regret Quantum Learning Algorithms for Zero-Sum Games |
| topic | Quantum Physics Machine Learning Optimization and Control |
| url | https://arxiv.org/abs/2304.14197 |