{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,24]],"date-time":"2025-08-24T01:39:52Z","timestamp":1755999592708,"version":"3.41.0"},"reference-count":13,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2023,9,28]],"date-time":"2023-09-28T00:00:00Z","timestamp":1695859200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGMETRICS Perform. Eval. Rev."],"published-print":{"date-parts":[[2023,9,28]]},"abstract":"<jats:p>Recent progress on building quantum computers [1] envisages wide applications of quantum algorithms in the near future. With the advantage of quantum computer, one can speed up not only fundamental algorithms, e.g., unstructured search [6] and factoring [11], but recent machine learning algorithms [3] as well. In this paper, we study the quantum speedup on a canonical task of reinforcement learning-best arm identification in multi-armed bandits.<\/jats:p>","DOI":"10.1145\/3626570.3626596","type":"journal-article","created":{"date-parts":[[2023,10,2]],"date-time":"2023-10-02T22:16:57Z","timestamp":1696285017000},"page":"72-74","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Quantum Best Arm Identification"],"prefix":"10.1145","volume":"51","author":[{"given":"Xuchuang","family":"Wang","sequence":"first","affiliation":[{"name":"The Chinese University of Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yu-Zhen","family":"Janice Chen","sequence":"additional","affiliation":[{"name":"University of Massachusetts Amherst"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matheus Guedes","family":"de Andrade","sequence":"additional","affiliation":[{"name":"University of Massachusetts Amherst"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mohammad","family":"Hajiesmaili","sequence":"additional","affiliation":[{"name":"University of Massachusetts Amherst"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"John C.S.","family":"Lui","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Don","family":"Towsley","sequence":"additional","affiliation":[{"name":"University of Massachusetts Amherst"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,10,2]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41586-019-1666-5"},{"key":"e_1_2_1_2_1","volume-title":"International Conference on Algorithmic Learning Theory. PMLR","author":"Barrier A.","year":"2023","unstructured":"A. Barrier, A. Garivier, and G. Stoltz. On best-arm identification with a fixed budget in non-parametric multi-armed bandits. In International Conference on Algorithmic Learning Theory. PMLR, 2023."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature23474"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s42484-020-00024-8"},{"key":"e_1_2_1_5_1","volume-title":"Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. Journal of machine learning research, 7(6)","author":"Even-Dar E.","year":"2006","unstructured":"E. Even-Dar, S. Mannor, Y. Mansour, and S. Mahadevan. Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. Journal of machine learning research, 7(6), 2006."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237866"},{"key":"e_1_2_1_7_1","first-page":"1238","volume-title":"International Conference on Machine Learning","author":"Karnin Z.","year":"2013","unstructured":"Z. Karnin, T. Koren, and O. Somekh. Almost optimal exploration in multi-armed bandits. In International Conference on Machine Learning, pages 1238--1246. PMLR, 2013."},{"key":"e_1_2_1_8_1","volume-title":"Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1):4--22","author":"Lai T. L.","year":"1985","unstructured":"T. L. Lai, H. Robbins, et al. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1):4--22, 1985."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1017\/9781108571401"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.2015.0301"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365700"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v37i8.26202"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v35i11.17212"}],"container-title":["ACM SIGMETRICS Performance Evaluation Review"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3626570.3626596","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3626570.3626596","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:36:45Z","timestamp":1750178205000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3626570.3626596"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,9,28]]},"references-count":13,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,9,28]]}},"alternative-id":["10.1145\/3626570.3626596"],"URL":"https:\/\/doi.org\/10.1145\/3626570.3626596","relation":{},"ISSN":["0163-5999"],"issn-type":[{"type":"print","value":"0163-5999"}],"subject":[],"published":{"date-parts":[[2023,9,28]]},"assertion":[{"value":"2023-10-02","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}