1Centrum voor Quantum Technologies, National University of Singapore, Singapore
2Afdeling Electrical and Computer Engineering, Faculteit Ingenieurswetenschappen, National University of Singapore, Singapore
Vind je dit artikel interessant of wil je het bespreken? Scite of laat een reactie achter op SciRate.
Abstract
We initiëren de studie van afwegingen tussen exploratie en exploitatie bij online leren van eigenschappen van kwantumtoestanden. Gegeven sequentiële orakeltoegang tot een onbekende kwantumtoestand, krijgen we in elke ronde de taak om een waarneembaar object te kiezen uit een reeks acties die erop gericht zijn de verwachtingswaarde voor de toestand (de beloning) te maximaliseren. Informatie verkregen over de onbekende toestand uit vorige ronden kan worden gebruikt om de actiekeuze geleidelijk te verbeteren, waardoor de kloof tussen de beloning en de maximale beloning die haalbaar is met de gegeven actieset (de spijt) wordt verkleind. We geven verschillende informatietheoretische ondergrenzen voor de cumulatieve spijt die een optimale leerling moet oplopen, en laten zien dat deze minstens gelijk is aan de vierkantswortel van het aantal gespeelde ronden. We onderzoeken ook de afhankelijkheid van de cumulatieve spijt van het aantal beschikbare acties en de dimensie van de achterliggende ruimte. Bovendien vertonen we strategieën die optimaal zijn voor bandieten met een eindig aantal wapens en algemene gemengde toestanden.
[Ingesloten inhoud]
► BibTeX-gegevens
► Referenties
[1] T. Lattimore en C. Szepesvári. "Bandit-algoritmen". Cambridge University Press. (2020).
https: / / doi.org/ 10.1017 / 9781108571401
[2] A. Slivkins. "Inleiding tot meerarmige bandieten". Grondslagen en trends in machine learning 12, 1–286 (2019).
https: / / doi.org/ 10.1561 / 2200000068
[3] S. Bubeck en N. Cesa-Bianchi. "Spijtanalyse van stochastische en niet-stochastische meerarmige bandietenproblemen". Grondslagen en trends in machine learning 5, 1–122 (2012).
https: / / doi.org/ 10.1561 / 2200000024
[4] D. Bouneffouf, I. Rish en C. Aggarwal. "Enquête over toepassingen van meerarmige en contextuele bandieten". In 2020 IEEE Congress on Evolutionary Computation (CEC). Pagina's 1-8. (2020).
https:///doi.org/10.1109/CEC48606.2020.9185782
[5] L. Tang, R. Rosales, A. Singh en D. Agarwal. "Automatische selectie van advertentie-indelingen via contextuele bandieten". In Proceedings of the 22nd ACM International Conference on Information and Knowledge Management. Pagina 1587-1594. Vereniging voor computermachines (2013).
https: / / doi.org/ 10.1145 / 2505515.2514700
[6] M. Cohen, I. Lobel en R. Paes Leme. "Op functies gebaseerde dynamische prijzen". Managementwetenschap 66, 4921-4943 (2020).
https: / / doi.org/ 10.1287 / mnsc.2019.3485
[7] W Thompson. "Over de waarschijnlijkheid dat de ene onbekende waarschijnlijkheid de andere overtreft gezien het bewijs van twee steekproeven". Biometrie 25, 285-294 (1933).
https:///doi.org/10.1093/biomet/25.3-4.285
[8] H Robbins. "Enkele aspecten van het sequentiële ontwerp van experimenten". Bulletin van de American Mathematical Society 58, 527-535 (1952).
https://doi.org/10.1090/S0002-9904-1952-09620-8
[9] TL Lai en H. Robbins. "Asymptotisch efficiënte adaptieve toewijzingsregels". Vooruitgang in toegepaste wiskunde 6, 4–22 (1985).
https://doi.org/10.1016/0196-8858(85)90002-8
[10] P. Auer, N. Cesa-Bianchi en P. Fischer. "Eindetijdanalyse van het meerarmige bandietenprobleem". Mach. Leren. 47, 235-256 (2002).
https: / / doi.org/ 10.1023 / A: 1013689704352
[11] B. Casalé, G. Di Molfetta, H. Kadri, , en L. Ralaivola. "Kwantumbandieten". Kwantum Mach. Intel. 2 (2020).
https://doi.org/10.1007/s42484-020-00024-8
[12] D. Wang, X. Jij, T. Li en A. Childs. "Quantum-verkenningsalgoritmen voor meerarmige bandieten". In Proceedings of the AAAI Conference on Artificial Intelligence. Deel 35, pagina's 10102-10110. (2021).
[13] P. Rebentrost, Y. Hamoudi, M. Ray, X. Wang, S. Yang en M. Santha. "Kwantumalgoritmen voor hedging en het leren van isingsmodellen". Fysiek. Rev. A 103, 012418 (2021).
https: / / doi.org/ 10.1103 / PhysRevA.103.012418
[14] O. Shamir. "Over de complexiteit van lineaire optimalisatie van bandieten". In Proceedings van de 28e conferentie over leertheorie. Deel 40 van Proceedings of Machine Learning Research, pagina's 1523-1551. PMLR (2015).
[15] P. Rusmevichientong en J. Tsitsiklis. "Lineair geparametriseerde bandieten". Wiskunde van Operations Research 35 (2008).
https: / / doi.org/ 10.1287 / moor.1100.0446
[16] J. Barry, DT Barry en S. Aaronson. "Quantum gedeeltelijk waarneembare markov-beslissingsprocessen". Fysiek. Rev A 90, 032311 (2014).
https: / / doi.org/ 10.1103 / PhysRevA.90.032311
[17] M. Ying, Y. Feng en S. Ying. "Optimaal beleid voor quantum markov-beslissingsprocessen". International Journal of Automation and Computing 18, 410–421 (2021).
https: / / doi.org/ 10.1007 / s11633-021-1278-z
[18] M. Parijs en J. Rehacek. "Kwantumtoestandsschatting". Uitgeverij Springer, Incorporated. (2010). 1e editie.
https: / / doi.org/ 10.1007 / b98673
[19] S Aaronson. "Schaduwtomografie van kwantumtoestanden". In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. Pagina 325-338. STOC 2018. Vereniging voor Computermachines (2018).
https: / / doi.org/ 10.1145 / 3188745.3188802
[20] S. Aaronson, X. Chen, E. Hazan, S. Boerenkool en A. Nayak. "Online leren van kwantumtoestanden". Journal of Statistical Mechanics: theorie en experiment 2019 (2018).
https: / / doi.org/ 10.1088 / 1742-5468 / ab3988
[21] J. Bretagnolle en C. Huber. "Schatting van de dichtheid: riskante 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 en M. Tomamichel. "Over Quantum Rényi Entropies: een nieuwe generalisatie en enkele eigenschappen". Journal of Mathematical Physics 54, 122203 (2013).
https: / / doi.org/ 10.1063 / 1.4838856
[23] M. Wilde, A. Winter en D. Yang. "Sterk Converse voor de klassieke capaciteit van verstrengelingsbrekende en Hadamard-kanalen via een ingeklemde Rényi relatieve entropie". Communicatie in wiskundige natuurkunde 331, 593-622 (2014).
https: / / doi.org/ 10.1007 / s00220-014-2122-x
[24] W. Hoefding. "Kansongelijkheden voor sommen van begrensde willekeurige variabelen". Publicatieblad van de American Statistical Association 58, 13-30 (1963).
https: / / doi.org/ 10.1080 / 01621459.1963.10500830
[25] P Auer. "Betrouwbaarheidsgrenzen gebruiken voor compromissen tussen exploitatie en exploratie". J Mach. Leren. Res. 3, 397-422 (2003).
https: / / doi.org/ 10.5555 / 944919.944941
[26] D. Varsha, T. Hayes en S.Kakade. "Stochastische lineaire optimalisatie onder bandietfeedback.". In Proceedings of the 21st Conference on Learning Theory. Pagina's 355-366. (2008).
[27] P. Rusmevichientong en JN Tsitsiklis. "Lineair geparametriseerde bandieten". Wiskunde van Operations Research 35, 395-411 (2010).
https: / / doi.org/ 10.1287 / moor.1100.0446
[28] Y. Abbasi-Yadkori, D. Pál en Cs. Szepesvari. "Verbeterde algoritmen voor lineaire stochastische bandieten". In vooruitgang in neurale informatieverwerkingssystemen. Deel 24. Curran Associates, Inc. (2011).
[29] TL Lai. "Adaptieve behandelingstoewijzing en het meerarmige bandietenprobleem". De Annals of Statistics 15, 1091 - 1114 (1987).
https: / / doi.org/ 10.1214 / aos / 1176350495
[30] M. Guţă, J. Kahn, R. Kueng en JA Tropp. "Fast state tomografie met optimale foutgrenzen". Journal of Physics A: Wiskundig en theoretisch 53, 204001 (2020).
https: / / doi.org/ 10.1088 / 1751-8121 / ab8111
[31] T. Lattimore en B. Hao. "Bandit-fase ophalen". In vooruitgang in neurale informatieverwerkingssystemen. Deel 34, pagina's 18801-18811. Curran Associates, Inc. (2021).
Geciteerd door
[1] Zongqi Wan, Zhijie Zhang, Tongyang Li, Jialin Zhang en Xiaoming Sun, "Quantum meerarmige bandieten en stochastische lineaire bandieten genieten van logaritmische spijt", arXiv: 2205.14988.
[2] Xinyi Chen, Elad Hazan, Tongyang Li, Zhou Lu, Xinzhao Wang en Rui Yang, "Adaptive Online Learning of Quantum States", arXiv: 2206.00220.
Bovenstaande citaten zijn afkomstig van SAO / NASA ADS (laatst bijgewerkt met succes 2022-07-24 00:26:50). De lijst is mogelijk onvolledig omdat niet alle uitgevers geschikte en volledige citatiegegevens verstrekken.
On De door Crossref geciteerde service er zijn geen gegevens gevonden over het citeren van werken (laatste poging 2022-07-24 00:26:48).
Dit artikel is gepubliceerd in Quantum onder de Creative Commons Naamsvermelding 4.0 Internationaal (CC BY 4.0) licentie. Het auteursrecht blijft berusten bij de oorspronkelijke houders van auteursrechten, zoals de auteurs of hun instellingen.
