1Center for Quantum Technologies, National University of Singapore, Singapore
2Institutionen för elektro- och datateknik, fakulteten för teknik, National University of Singapore, Singapore
Hitta det här uppsatsen intressant eller vill diskutera? Scite eller lämna en kommentar på SciRate.
Abstrakt
Vi initierar studiet av avvägningar mellan utforskning och exploatering vid onlineinlärning av egenskaper hos kvanttillstånd. Givet sekventiell orakelåtkomst till ett okänt kvanttillstånd, i varje omgång, har vi i uppdrag att välja en observerbar från en uppsättning åtgärder som syftar till att maximera dess förväntade värde på tillståndet (belöningen). Information som erhållits om det okända tillståndet från tidigare omgångar kan användas för att gradvis förbättra valet av åtgärd, och på så sätt minska klyftan mellan belöningen och den maximala belöningen som kan uppnås med den givna åtgärdsuppsättningen (ångern). Vi ger olika informationsteoretiska nedre gränser för den kumulativa ångern som en optimal elev måste ådra sig, och visar att den skalar åtminstone som kvadratroten av antalet spelade rundor. Vi undersöker också beroendet av den kumulativa ångern av antalet tillgängliga åtgärder och dimensionen av det underliggande utrymmet. Dessutom visar vi strategier som är optimala för banditer med ett begränsat antal armar och generella blandade tillstånd.
[Inbäddat innehåll]
► BibTeX-data
► Referenser
[1] T. Lattimore och C. Szepesvári. "Banditalgoritmer". Cambridge University Press. (2020).
https: / / doi.org/ 10.1017 / 9781108571401
[2] A. Slivkins. "Introduktion till flerarmade banditer". Grunder och trender inom maskininlärning 12, 1–286 (2019).
https: / / doi.org/ 10.1561 / 2200000068
[3] S. Bubeck och N. Cesa-Bianchi. "Ångeranalys av stokastiska och icke-stokastiska flerarmade banditproblem". Grunder och trender inom maskininlärning 5, 1–122 (2012).
https: / / doi.org/ 10.1561 / 2200000024
[4] D. Bouneffouf, I. Rish och C. Aggarwal. "Enkät om tillämpningar av flerarmade och kontextuella banditer". 2020 IEEE Congress on Evolutionary Computation (CEC). Sidorna 1–8. (2020).
https:///doi.org/10.1109/CEC48606.2020.9185782
[5] L. Tang, R. Rosales, A. Singh och D. Agarwal. "Automatiskt val av annonsformat via kontextuella banditer". I samband med den 22:a ACM International Conference on Information and Knowledge Management. Sida 1587–1594. Association for Computing Machinery (2013).
https: / / doi.org/ 10.1145 / 2505515.2514700
[6] M. Cohen, I. Lobel och R. Paes Leme. "Funktionsbaserad dynamisk prissättning". Management Science 66, 4921–4943 (2020).
https: / / doi.org/ 10.1287 / mnsc.2019.3485
[7] W. Thompson. "På sannolikheten att en okänd sannolikhet överstiger en annan med tanke på bevisen från två prover". Biometrika 25, 285–294 (1933).
https:///doi.org/10.1093/biomet/25.3-4.285
[8] H. Robbins. "Några aspekter av den sekventiella designen av experiment". Bulletin of the American Mathematical Society 58, 527–535 (1952).
https://doi.org/10.1090/S0002-9904-1952-09620-8
[9] TL Lai och H. Robbins. "Asymptotiskt effektiva adaptiva allokeringsregler". Advances in Applied Mathematics 6, 4–22 (1985).
https://doi.org/10.1016/0196-8858(85)90002-8
[10] P. Auer, N. Cesa-Bianchi och P. Fischer. "Ändtidsanalys av det flerarmade banditproblemet". Mach. Lära sig. 47, 235–256 (2002).
https: / / doi.org/ 10.1023 / A: 1013689704352
[11] B. Casalé, G. Di Molfetta, H. Kadri, och L. Ralaivola. "Quantum banditer". Quantum Mach. Intell. 2 (2020).
https://doi.org/10.1007/s42484-020-00024-8
[12] D. Wang, X. You, T. Li och A. Childs. "Quantum prospekteringsalgoritmer för flerarmade banditer". I handlingar från AAAI-konferensen om artificiell intelligens. Volym 35, sid 10102–10110. (2021).
[13] P. Rebentrost, Y. Hamoudi, M. Ray, X. Wang, S. Yang och M. Santha. "Kvantalgoritmer för säkring och inlärning av isingmodeller". Phys. Rev. A 103, 012418 (2021).
https: / / doi.org/ 10.1103 / PhysRevA.103.012418
[14] O. Shamir. "Om komplexiteten i linjär optimering av bandit". I Proceedings of the 28th Conference on Learning Theory. Volym 40 av Proceedings of Machine Learning Research, sidorna 1523–1551. PMLR (2015).
[15] P. Rusmevichientong och J. Tsitsiklis. "Linjärt parametriserade banditer". Mathematics of Operations Research 35 (2008).
https: / ⠀ </ ⠀ <doi.org/†<10.1287 / ⠀ <moor.1100.0446
[16] J. Barry, DT Barry och S. Aaronson. "Quantum delvis observerbara markov beslutsprocesser". Phys. Rev. A 90, 032311 (2014).
https: / / doi.org/ 10.1103 / PhysRevA.90.032311
[17] M. Ying, Y. Feng och S. Ying. "Optimala policyer för beslutsprocesser för kvantmarkov". International Journal of Automation and Computing 18, 410–421 (2021).
https: / / doi.org/ 10.1007 / s11633-021-1278-z
[18] M. Paris och J. Rehacek. "Kvanttillståndsuppskattning". Springer Publishing Company, Incorporated. (2010). 1:a upplagan.
https: / / doi.org/ 10.1007 / b98673
[19] S. Aaronson. "Skuggtomografi av kvanttillstånd". I samband med det 50:e årliga ACM SIGACT-symposiet om datorteori. Sida 325–338. STOC 2018. Association for Computing Machinery (2018).
https: / / doi.org/ 10.1145 / 3188745.3188802
[20] S. Aaronson, X. Chen, E. Hazan, S. Kale och A. Nayak. "Online-inlärning av kvanttillstånd". Journal of Statistical Mechanics: Theory and Experiment 2019 (2018).
https: / / doi.org/ 10.1088 / 1742-5468 / ab3988
[21] J. Bretagnolle och C. Huber. "Estimat des densités: risk 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 och M. Tomamichel. "Om Quantum Rényi Entropies: En ny generalisering och några egenskaper". Journal of Mathematical Physics 54, 122203 (2013).
https: / / doi.org/ 10.1063 / 1.4838856
[23] M. Wilde, A. Winter och D. Yang. "Stark konversation för den klassiska kapaciteten av intrasslingsbrytande och Hadamard-kanaler via en sammanfogad Rényi relativ entropi". Communications in Mathematical Physics 331, 593–622 (2014).
https: / / doi.org/ 10.1007 / s00220-014-2122-x
[24] W. Hoeffding. "Sannolikhetsolikheter för summor av gränsade stokastiska variabler". Journal of the American Statistical Association 58, 13–30 (1963).
https: / / doi.org/ 10.1080 / 01621459.1963.10500830
[25] P. Auer. "Att använda förtroende för avvägningar mellan exploatering och utforskning". J. Mach. Lära sig. Res. 3, 397–422 (2003).
https: / / doi.org/ 10.5555 / 944919.944941
[26] D. Varsha, T. Hayes och S. Kakade. "Stokastisk linjär optimering under banditåterkoppling." I Proceedings of the 21st Conference on Learning Theory. Sidorna 355–366. (2008).
[27] P. Rusmevichientong och JN Tsitsiklis. "Linjärt parametriserade banditer". Mathematics of Operations Research 35, 395–411 (2010).
https: / ⠀ </ ⠀ <doi.org/†<10.1287 / ⠀ <moor.1100.0446
[28] Y. Abbasi-Yadkori, D. Pál och Cs. Szepesvári. "Förbättrade algoritmer för linjära stokastiska banditer". Framsteg inom neurala informationsbehandlingssystem. Volym 24. Curran Associates, Inc. (2011).
[29] TL Lai. "Adaptiv behandlingstilldelning och det flerarmade banditproblemet". The Annals of Statistics 15, 1091 – 1114 (1987).
https: / / doi.org/ 10.1214 / AOS / 1176350495
[30] M. Guţă, J. Kahn, R. Kueng och JA Tropp. "Snabb tillståndstomografi med optimala felgränser". Journal of Physics A: Mathematical and Theoretical 53, 204001 (2020).
https: / / doi.org/ 10.1088 / 1751-8121 / ab8111
[31] T. Lattimore och B. Hao. "Hämtning av banditfas". Framsteg inom neurala informationsbehandlingssystem. Volym 34, sidorna 18801–18811. Curran Associates, Inc. (2021).
Citerad av
[1] Zongqi Wan, Zhijie Zhang, Tongyang Li, Jialin Zhang och Xiaoming Sun, "Quantum Multi-Armed Bandits and Stokastical Linear Bandits Enjoy Logaritmic Regrets", arXiv: 2205.14988.
[2] Xinyi Chen, Elad Hazan, Tongyang Li, Zhou Lu, Xinzhao Wang och Rui Yang, "Adaptive Online Learning of Quantum States", arXiv: 2206.00220.
Ovanstående citat är från SAO / NASA ADS (senast uppdaterad framgångsrikt 2022-07-24 00:26:50). Listan kan vara ofullständig eftersom inte alla utgivare tillhandahåller lämpliga och fullständiga citatdata.
On Crossrefs citerade service Inga uppgifter om citerande verk hittades (sista försök 2022-07-24 00:26:48).
Detta papper publiceras i Quantum under Creative Commons Attribution 4.0 International (CC BY 4.0) licens. Upphovsrätten kvarstår med de ursprungliga upphovsrättsinnehavarna som författarna eller deras institutioner.
