1新加坡国立大学量子技术中心，新加坡
2新加坡国立大学工程学院电气与计算机工程系，新加坡
觉得本文有趣或想讨论？ 在SciRate上发表评论或发表评论.
抽象
我们开始研究量子态属性在线学习中探索和利用之间的权衡。 给定对未知量子状态的顺序预言机访问，在每一轮中，我们的任务是从一组旨在最大化其对状态的期望值（奖励）的动作中选择一个可观察的。 从前几轮中获得的关于未知状态的信息可用于逐步改进动作选择，从而减少奖励与给定动作集可达到的最大奖励（遗憾）之间的差距。 我们提供了最佳学习者必须产生的累积遗憾的各种信息论下限，并表明它至少与所玩轮数的平方根成比例。 我们还研究了累积后悔对可用操作数量和潜在空间维度的依赖性。 此外，我们展示了最适合具有有限数量的臂和一般混合状态的老虎机的策略。
[嵌入的内容]
►BibTeX数据
►参考
[1] T. Lattimore 和 C. Szepesvári。 “强盗算法”。 剑桥大学出版社。 （2020 年）。
https：/ / doi.org/10.1017/ 9781108571401
[2] A.斯利夫金斯。 “介绍多臂土匪”。 机器学习的基础和趋势 12, 1–286 (2019)。
https：/ / doi.org/10.1561/ 2200000068
[3] S. Bubeck 和 N. Cesa-Bianchi。 “对随机和非随机多臂老虎机问题的遗憾分析”。 机器学习的基础和趋势 5, 1–122 (2012)。
https：/ / doi.org/10.1561/ 2200000024
[4] D. Bouneffouf、I. Rish 和 C. Aggarwal。 “多臂和上下文强盗的应用调查”。 2020 年 IEEE 进化计算大会 (CEC)。 第 1-8 页。 （2020 年）。
https:///doi.org/10.1109/CEC48606.2020.9185782
[5] L. Tang、R. Rosales、A. Singh 和 D. Agarwal。 “通过上下文强盗自动选择广告格式”。 在第 22 届 ACM 信息与知识管理国际会议论文集上。 第 1587-1594 页。 计算机协会（2013 年）。
https：/ / doi.org/10.1145/ 2505515.2514700
[6] M. Cohen、I. Lobel 和 R. Paes Leme。 “基于特征的动态定价”。 管理科学 66, 4921–4943 (2020)。
https：/ / doi.org/ 10.1287 / mnsc.2019.3485
[7] W.汤普森。 “鉴于两个样本的证据，一个未知概率超过另一个的可能性”。 Biometrika 25, 285–294 (1933)。
https:///doi.org/10.1093/biomet/25.3-4.285
[8] H.罗宾斯。 “实验顺序设计的一些方面”。 美国数学学会公报 58, 527–535 (1952)。
https://doi.org/10.1090/S0002-9904-1952-09620-8
[9] TL Lai 和 H. Robbins。 “渐近有效的自适应分配规则”。 应用数学进展 6, 4-22 (1985)。
https://doi.org/10.1016/0196-8858(85)90002-8
[10] P. Auer、N. Cesa-Bianchi 和 P. Fischer。 “多臂老虎机问题的有限时间分析”。 马赫学。 47, 235–256 (2002)。
https：/ / doi.org/ 10.1023 / A：1013689704352
[11] B. Casalé、G. Di Molfetta、H. Kadri 和 L. Ralaivola。 “量子强盗”。 量子马赫英特尔。 2（2020）。
https://doi.org/10.1007/s42484-020-00024-8
[12] D. Wang、X. You、T. Li 和 A. Childs。 “多臂老虎机的量子探索算法”。 在 AAAI 人工智能会议论文集中。 第 35 卷，第 10102-10110 页。 （2021 年）。
[13] P. Rebentrost、Y. Hamoudi、M. Ray、X. Wang、S. Yang 和 M. Santha。 “用于对冲和 ising 模型学习的量子算法”。 物理。 修订版 A 103, 012418 (2021)。
https：/ / doi.org/ 10.1103 / PhysRevA.103.012418
[14] O.沙米尔。 “论强盗线性优化的复杂性”。 在第 28 届学习理论会议论文集上。 机器学习研究论文集第 40 卷，第 1523-1551 页。 PMLR（2015 年）。
[15] P. Rusmevichientong 和 J. Tsitsiklis。 “线性参数化老虎机”。 运筹学数学 35 (2008)。
https：/ / doi.org/ 10.1287 / moor.1100.0446
[16] J. Barry、DT Barry 和 S. Aaronson。 “量子部分可观察马尔可夫决策过程”。 物理。 修订版 A 90, 032311 (2014)。
https：/ / doi.org/ 10.1103 / PhysRevA.90.032311
[17] M. Ying、Y. Feng 和 S. Ying。 “量子马尔可夫决策过程的最优策略”。 国际自动化与计算杂志 18, 410–421 (2021)。
https：/ / doi.org/ 10.1007 / s11633-021-1278-z
[18] M. Paris 和 J. Rehacek。 “量子态估计”。 施普林格出版公司，股份有限公司。 （2010）。 第 1 版。
https：///doi.org/10.1007/b98673
[19] S.亚伦森。 “量子态的阴影断层扫描”。 在第 50 届 ACM SIGACT 计算理论研讨会论文集上。 第 325-338 页。 STOC 2018。计算机协会（2018 年）。
https：/ / doi.org/10.1145/ 3188745.3188802
[20] S. Aaronson、X. Chen、E. Hazan、S. Kale 和 A. Nayak。 “量子态的在线学习”。 统计力学杂志：理论与实验 2019（2018）。
https：/ / doi.org/ 10.1088 / 1742-5468 / ab3988
[21] J. Bretagnolle 和 C. Huber。 “Estimation des densités: risque minimax”。 Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete 47, 119–137 (1979)。
https：/ / doi.org/ 10.1007 / BF00535278
[22] M. Müller-Lennert、F. Dupuis、O. Szehr、S. Fehr 和 M. Tomamichel。 “论量子仁义熵：一种新的概括和一些性质”。 数学物理杂志 54, 122203 (2013)。
https：/ / doi.org/10.1063/ 1.4838856
[23] M. Wilde、A. Winter 和 D. Yang。 “通过夹层 Rényi 相对熵对纠缠破坏和 Hadamard 通道的经典容量的强逆”。 数学物理通讯 331, 593–622 (2014)。
https：///doi.org/10.1007/s00220-014-2122-x
[24] W. 霍夫丁。 “有界随机变量和的概率不等式”。 美国统计协会杂志 58, 13–30 (1963)。
https：/ / doi.org/10.1080/ 01621459.1963.10500830
[25] P.奥尔。 “使用置信区间进行开发-探索权衡”。 J.马赫。 学。 水库。 3, 397–422 (2003)。
https：/ / doi.org/10.5555/ 944919.944941
[26] D. Varsha、T. Hayes 和 S.Kakade。 “强盗反馈下的随机线性优化。”。 在第 21 届学习理论会议论文集上。 第 355-366 页。 （2008 年）。
[27] P. Rusmevichientong 和 JN Tsitsiklis。 “线性参数化老虎机”。 运筹学数学 35, 395–411 (2010)。
https：/ / doi.org/ 10.1287 / moor.1100.0446
[28] Y. Abbasi-Yadkori、D. Pál 和 Cs。 塞佩斯瓦里。 “线性随机老虎机的改进算法”。 在神经信息处理系统的进展。 第 24 卷。Curran Associates, Inc. (2011)。
[29] TL赖。 “自适应治疗分配和多臂强盗问题”。 统计年鉴 15, 1091 – 1114 (1987)。
https：///doi.org/10.1214/aos/1176350495
[30] M. Guţă、J. Kahn、R. Kueng 和 JA Tropp。 “具有最佳误差范围的快速状态断层扫描”。 物理学杂志 A：数学与理论 53, 204001 (2020)。
https：/ / doi.org/ 10.1088 / 1751-8121 / ab8111
[31] T. Lattimore 和 B. Hao。 “强盗阶段检索”。 在神经信息处理系统的进展。 第 34 卷，第 18801-18811 页。 Curran Associates, Inc. (2021)。
被引用
[1] 万宗奇、张志杰、李同阳、张家林、孙晓明，“量子多臂强盗和随机线性强盗享受对数遗憾”， 的arXiv：2205.14988.
[2] Xinyi Chen, Elad Hazan, Tongyang Li, Zhou Lu, Xinzhao Wang, and Rui Yang，“量子态的自适应在线学习”， 的arXiv：2206.00220.
以上引用来自 SAO / NASA广告 （最近成功更新为2022-07-24 00:26:50）。 该列表可能不完整，因为并非所有发布者都提供合适且完整的引用数据。
On Crossref的引用服务 找不到有关引用作品的数据（上一次尝试2022-07-24 00:26:48）。
该论文发表在《量子》杂志上 国际知识共享署名署名4.0（CC BY 4.0） 执照。 版权归原始版权持有者所有，例如作者或其所在机构。
