Quantum Exploration Algorithms for Multi-Armed Bandits
Authors: Daochen Wang, Xuchen You, Tongyang Li, Andrew M. Childs10102-10110
AAAI 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study a quantum computational version of this problem with coherent oracle access to states encoding the reward probabilities of each arm as quantum amplitudes. Specifically, we provide an algorithm to find the best arm with fixed confidence based on variable-time amplitude amplification and estimation. This algorithm gives a quadratic speedup compared to the best possible classical result in terms of query complexity. We also prove a matching quantum lower bound (up to poly-logarithmic factors). This work is purely theoretical. Researchers working on theoretical aspects of bandits and quantum computing may immediately benefit from our results. |
| Researcher Affiliation | Academia | Daochen Wang, 1,2 Xuchen You, 1,3 Tongyang Li, 1,3,4 Andrew M. Childs1,3 1Joint Center for Quantum Information and Computer Science, University of Maryland 2Department of Mathematics, University of Maryland 3Department of Computer Science and Institute for Advanced Computer Studies, University of Maryland 4Center for Theoretical Physics, Massachusetts Institute of Technology {daochen,xyou,amchilds}@umd.edu, tongyang@mit.edu |
| Pseudocode | Yes | Algorithm 1: A(O, l2, l1, α) Algorithm 2: Locate(O, δ) Algorithm 3: Shrink(O, k, I, δ) Algorithm 4: Best Arm(O, δ) |
| Open Source Code | No | The paper does not provide explicit statements about releasing source code for its methodology or links to a code repository. It mentions a link to the full version of the paper on arXiv, but this is not a code repository. |
| Open Datasets | No | This work is purely theoretical and does not involve empirical training on a dataset, as indicated by the statement: "This work is purely theoretical." |
| Dataset Splits | No | This work is purely theoretical and does not involve empirical validation on data splits, as indicated by the statement: "This work is purely theoretical." |
| Hardware Specification | No | This work is purely theoretical and does not discuss hardware specifications for experiments, as indicated by the statement: "This work is purely theoretical." |
| Software Dependencies | No | This work is purely theoretical and does not list any specific software dependencies with version numbers. |
| Experiment Setup | No | This work is purely theoretical and does not describe any experimental setup or hyperparameters, as indicated by the statement: "This work is purely theoretical." |