Logarithmic-Regret Quantum Learning Algorithms for Zero-Sum Games
Authors: Minbo Gao, Zhengfeng Ji, Tongyang Li, Qisheng Wang
NeurIPS 2023 | Conference 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 gmb17@tsinghua.org.cn Zhengfeng Ji Department of Computer Science and Technology, Tsinghua University, Beijing, China jizhengfeng@tsinghua.edu.cn Tongyang Li Center on Frontiers of Computing Studies, and School of Computer Science, Peking University, Beijing, China tongyangli@pku.edu.cn Qisheng Wang Graduate School of Mathematics, Nagoya University, Nagoya, Japan Qisheng Wang1994@gmail.com |
| 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. |