1Zentrum für Quantentechnologien, National University of Singapore, Singapur
2Fakultät für Elektrotechnik und Informationstechnik, Fakultät für Ingenieurwissenschaften, National University of Singapore, Singapur
Findest du dieses Paper interessant oder möchtest du darüber diskutieren? Scite oder hinterlasse einen Kommentar zu SciRate.
Abstrakt
Wir initiieren die Untersuchung der Kompromisse zwischen Erforschung und Nutzung beim Online-Lernen von Eigenschaften von Quantenzuständen. Wenn wir sequenziellen Oracle-Zugriff auf einen unbekannten Quantenzustand haben, müssen wir in jeder Runde aus einer Reihe von Aktionen ein Observables auswählen, das darauf abzielt, seinen Erwartungswert für den Zustand (die Belohnung) zu maximieren. Informationen über den unbekannten Zustand aus früheren Runden können verwendet werden, um die Wahl der Aktion schrittweise zu verbessern und so die Lücke zwischen der Belohnung und der mit dem gegebenen Aktionssatz maximal erreichbaren Belohnung (dem Bedauern) zu verringern. Wir liefern verschiedene informationstheoretische Untergrenzen für das kumulative Bedauern, das ein optimaler Lernender auf sich nehmen muss, und zeigen, dass es mindestens als Quadratwurzel der Anzahl der gespielten Runden skaliert. Wir untersuchen auch die Abhängigkeit des kumulativen Bedauerns von der Anzahl der verfügbaren Aktionen und der Dimension des zugrunde liegenden Raums. Darüber hinaus zeigen wir Strategien, die für Banditen mit einer endlichen Anzahl von Waffen und allgemeinen gemischten Zuständen optimal sind.
[Eingebetteten Inhalt]
► BibTeX-Daten
► Referenzen
[1] T. Lattimore und C. Szepesvári. „Bandit-Algorithmen“. Cambridge University Press. (2020).
https: / / doi.org/ 10.1017 / 9781108571401
[2] A. Slivkins. „Einführung in mehrarmige Banditen“. Grundlagen und Trends im maschinellen Lernen 12, 1–286 (2019).
https: / / doi.org/ 10.1561 / 2200000068
[3] S. Bubeck und N. Cesa-Bianchi. „Bedauernsanalyse stochastischer und nichtstochastischer mehrarmiger Banditenprobleme“. Grundlagen und Trends im maschinellen Lernen 5, 1–122 (2012).
https: / / doi.org/ 10.1561 / 2200000024
[4] D. Bouneffouf, I. Rish und C. Aggarwal. „Umfrage zu Einsatzmöglichkeiten mehrarmiger und kontextueller Banditen“. Im Jahr 2020 IEEE Congress on Evolutionary Computation (CEC). Seiten 1–8. (2020).
https:///doi.org/10.1109/CEC48606.2020.9185782
[5] L. Tang, R. Rosales, A. Singh und D. Agarwal. „Automatische Auswahl des Anzeigenformats über kontextbezogene Banditen“. In Proceedings der 22. ACM International Conference on Information and Knowledge Management. Seite 1587–1594. Verband für Computermaschinen (2013).
https: / / doi.org/ 10.1145 / 2505515.2514700
[6] M. Cohen, I. Lobel und R. Paes Leme. „Funktionsbasierte dynamische Preisgestaltung“. Management Science 66, 4921–4943 (2020).
https: / / doi.org/ 10.1287 / mnsc.2019.3485
[7] W. Thompson. „Über die Wahrscheinlichkeit, dass eine unbekannte Wahrscheinlichkeit angesichts der Evidenz von zwei Proben eine andere übertrifft.“ Biometrie 25, 285–294 (1933).
https:///doi.org/10.1093/biomet/25.3-4.285
[8] H. Robbins. „Einige Aspekte der sequentiellen Versuchsplanung“. Bulletin der American Mathematical Society 58, 527–535 (1952).
https://doi.org/10.1090/S0002-9904-1952-09620-8
[9] TL Lai und H. Robbins. „Asymptotisch effiziente adaptive Allokationsregeln“. Fortschritte in der angewandten Mathematik 6, 4–22 (1985).
https://doi.org/10.1016/0196-8858(85)90002-8
[10] P. Auer, N. Cesa-Bianchi und P. Fischer. „Finite-Time-Analyse des Problems der mehrarmigen Banditen“. Mach. Lernen. 47, 235–256 (2002).
https: / / doi.org/ 10.1023 / A: 1013689704352
[11] B. Casalé, G. Di Molfetta, H. Kadri und L. Ralaivola. „Quantenbanditen“. Quantenmach. Intel. 2 (2020).
https://doi.org/10.1007/s42484-020-00024-8
[12] D. Wang, X. You, T. Li und A. Childs. „Quantenexplorationsalgorithmen für mehrarmige Banditen“. In Proceedings of the AAAI Conference on Artificial Intelligence. Band 35, Seiten 10102–10110. (2021).
[13] P. Rebentrost, Y. Hamoudi, M. Ray, X. Wang, S. Yang und M. Santha. „Quantenalgorithmen für die Absicherung und das Lernen von Ising-Modellen“. Physik. Rev. A 103, 012418 (2021).
https: / / doi.org/ 10.1103 / PhysRevA.103.012418
[14] O. Shamir. „Zur Komplexität der Bandit-Linearoptimierung“. In Proceedings der 28. Konferenz zur Lerntheorie. Band 40 der Proceedings of Machine Learning Research, Seiten 1523–1551. PMLR (2015).
[15] P. Rusmevichientong und J. Tsitsiklis. „Linear parametrisierte Banditen“. Mathematik des Operations Research 35 (2008).
https: / / doi.org/ 10.1287 / moor.1100.0446
[16] J. Barry, DT Barry und S. Aaronson. „Quantenteilweise beobachtbare Markov-Entscheidungsprozesse“. Physik. Rev. A 90, 032311 (2014).
https: / / doi.org/ 10.1103 / PhysRevA.90.032311
[17] M. Ying, Y. Feng und S. Ying. „Optimale Richtlinien für Quanten-Markov-Entscheidungsprozesse“. International Journal of Automation and Computing 18, 410–421 (2021).
https: / / doi.org/ 10.1007 / s11633-021-1278-z
[18] M. Paris und J. Rehacek. „Quantenzustandsschätzung“. Springer Publishing Company, Incorporated. (2010). 1. Auflage.
https: / / doi.org/ 10.1007 / b98673
[19] S. Aaronson. „Schattentomographie von Quantenzuständen“. In Proceedings des 50. jährlichen ACM SIGACT-Symposiums zur Computertheorie. Seite 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 und A. Nayak. „Online-Lernen von Quantenzuständen“. Journal of Statistical Mechanics: Theorie und Experiment 2019 (2018).
https: / / doi.org/ 10.1088 / 1742-5468 / ab3988
[21] J. Bretagnolle und C. Huber. „Schätzung der Dichte: riskantes 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 und M. Tomamichel. „Über Quanten-Rényi-Entropien: Eine neue Verallgemeinerung und einige Eigenschaften“. Journal of Mathematical Physics 54, 122203 (2013).
https: / / doi.org/ 10.1063 / 1.4838856
[23] M. Wilde, A. Winter und D. Yang. „Starkes Gegenteil für die klassische Kapazität von Verschränkungsbrechungs- und Hadamard-Kanälen über eine relative Rényi-Sandwich-Entropie“. Communications in Mathematical Physics 331, 593–622 (2014).
https: / / doi.org/ 10.1007 / s00220-014-2122-x
[24] W. Hoeffding. „Wahrscheinlichkeitsungleichungen für Summen beschränkter Zufallsvariablen“. Journal of the American Statistical Association 58, 13–30 (1963).
https: / / doi.org/ 10.1080 / 01621459.1963.10500830
[25] P. Auer. „Verwendung von Vertrauensgrenzen für Ausbeutungs-Explorations-Kompromisse“. J. Mach. Lernen. Res. 3, 397–422 (2003).
https: / / doi.org/ 10.5555 / 944919.944941
[26] D. Varsha, T. Hayes und S. Kakade. „Stochastische lineare Optimierung unter Banditen-Feedback“. In Proceedings der 21. Konferenz zur Lerntheorie. Seiten 355–366. (2008).
[27] P. Rusmevichientong und JN Tsitsiklis. „Linear parametrisierte Banditen“. Mathematik des Operations Research 35, 395–411 (2010).
https: / / doi.org/ 10.1287 / moor.1100.0446
[28] Y. Abbasi-Yadkori, D. Pál und Cs. Szepesvari. „Verbesserte Algorithmen für lineare stochastische Banditen“. In Fortschritte in neuronalen Informationsverarbeitungssystemen. Band 24. Curran Associates, Inc. (2011).
[29] TL Lai. „Adaptive Behandlungszuteilung und das Problem der mehrarmigen Banditen“. The Annals of Statistics 15, 1091 – 1114 (1987).
https: / / doi.org/ 10.1214 / aos / 1176350495
[30] M. Guţă, J. Kahn, R. Kueng und JA Tropp. „Schnelle Zustandstomographie mit optimalen Fehlergrenzen“. Zeitschrift für Physik A: Mathematisch und Theoretisch 53, 204001 (2020).
https: / / doi.org/ 10.1088 / 1751-8121 / ab8111
[31] T. Lattimore und B. Hao. „Rückgewinnung der Banditenphase“. In Fortschritte in neuronalen Informationsverarbeitungssystemen. Band 34, Seiten 18801–18811. Curran Associates, Inc. (2021).
Zitiert von
[1] Zongqi Wan, Zhijie Zhang, Tongyang Li, Jialin Zhang und Xiaoming Sun, „Quantum Multi-Armed Bandits and Stochastic Linear Bandits Enjoy Logarithmic Regrets“, arXiv: 2205.14988.
[2] Xinyi Chen, Elad Hazan, Tongyang Li, Zhou Lu, Xinzhao Wang und Rui Yang, „Adaptive Online Learning of Quantum States“, arXiv: 2206.00220.
Die obigen Zitate stammen von SAO / NASA ADS (Zuletzt erfolgreich aktualisiert am 2022, 07:24:00 Uhr). Die Liste ist möglicherweise unvollständig, da nicht alle Verlage geeignete und vollständige Zitationsdaten bereitstellen.
On Der von Crossref zitierte Dienst Es wurden keine Daten zum Zitieren von Werken gefunden (letzter Versuch 2022-07-24 00:26:48).
Dieses Papier ist in Quantum unter dem veröffentlicht Creative Commons Namensnennung 4.0 International (CC BY 4.0) Lizenz. Das Copyright verbleibt bei den ursprünglichen Copyright-Inhabern wie den Autoren oder deren Institutionen.
