Logarithmic-Regret Quantum Learning Algorithms for Zero-Sum Games
Authors: Minbo Gao, Zhengfeng Ji, Tongyang Li, Qisheng Wang
NeurIPS 2023 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We propose the first online quantum algorithm for solving zero-sum games with e 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 e O( m + n/ε2.5). |
| Researcher Affiliation | Academia | Minbo Gao State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing, China and University of Chinese Academy of Sciences, Beijing, China EMAIL Zhengfeng Ji Department of Computer Science and Technology, Tsinghua University, Beijing, China EMAIL Tongyang Li Center on Frontiers of Computing Studies, and School of Computer Science, Peking University, Beijing, China EMAIL Qisheng Wang Graduate School of Mathematics, Nagoya University, Nagoya, Japan Qisheng EMAIL |
| Pseudocode | Yes | Algorithm 1 Sample-Based Optimistic Multiplicative Weight Update for Matrix Games; Algorithm 2 Quantum Multi-Gibbs Sampling OGibbs u (k, ϵG) |
| Open Source Code | No | The paper presents theoretical algorithms and their complexity analysis. There is no explicit statement or link indicating that the source code for the described methodology is publicly available. |
| Open Datasets | No | The paper is theoretical and focuses on algorithm design and complexity analysis for zero-sum games represented by a matrix A Rm n. It does not mention the use of any specific datasets for training or evaluation, nor does it provide any links or citations to publicly available datasets. |
| Dataset Splits | No | This is a theoretical paper that proposes and analyzes algorithms without empirical evaluation on datasets. Therefore, it does not provide details on training/test/validation dataset splits. |
| Hardware Specification | No | This is a theoretical research paper focusing on algorithm development and complexity analysis. It does not describe any experimental setups or specify hardware used for running experiments. |
| Software Dependencies | No | The paper is theoretical, presenting algorithms and their complexity. It does not describe an implementation or experiments that would require specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and focuses on developing and analyzing a quantum algorithm. It does not describe an experimental setup with specific details such as hyperparameters or system-level training settings. |