1Center for Quantum Technologies, National University of Singapore, Singapore
2Institutt for elektro- og datateknikk, Fakultet for ingeniørvitenskap, National University of Singapore, Singapore
Finn dette papiret interessant eller vil diskutere? Scite eller legg igjen en kommentar på SciRate.
Abstrakt
Vi starter studiet av avveininger mellom utforskning og utnyttelse i nettbasert læring av egenskaper ved kvantetilstander. Gitt sekvensiell orakeltilgang til en ukjent kvantetilstand, får vi i hver runde i oppgave å velge en observerbar fra et sett med handlinger som tar sikte på å maksimere dens forventningsverdi på staten (belønningen). Informasjon innhentet om den ukjente tilstanden fra tidligere runder kan brukes til å gradvis forbedre valg av handling, og dermed redusere gapet mellom belønningen og den maksimale belønningen som kan oppnås med det gitte handlingssettet (angringen). Vi gir ulike informasjonsteoretiske nedre grenser for den kumulative beklagelsen som en optimal elev må pådra seg, og viser at den skalerer minst som kvadratroten av antall spilte runder. Vi undersøker også avhengigheten av den kumulative beklagelsen av antall tilgjengelige handlinger og dimensjonen til det underliggende rommet. Dessuten viser vi strategier som er optimale for banditter med et begrenset antall armer og generelle blandede tilstander.
[Innebygd innhold]
► BibTeX-data
► Referanser
[1] T. Lattimore og C. Szepesvári. "Banditalgoritmer". Cambridge University Press. (2020).
https: / / doi.org/ 10.1017 / 9781108571401
[2] A. Slivkins. "Introduksjon til flerarmede banditter". Fundamenter og trender i maskinlæring 12, 1–286 (2019).
https: / / doi.org/ 10.1561 / 2200000068
[3] S. Bubeck og N. Cesa-Bianchi. "Beklager analyse av stokastiske og ikke-stokastiske flerarmede bandittproblemer". Fundamenter og trender i maskinlæring 5, 1–122 (2012).
https: / / doi.org/ 10.1561 / 2200000024
[4] D. Bouneffouf, I. Rish og C. Aggarwal. "Undersøkelse om anvendelser av flerarmede og kontekstuelle banditter". I 2020 IEEE Congress on Evolutionary Computation (CEC). Side 1–8. (2020).
https:///doi.org/10.1109/CEC48606.2020.9185782
[5] L. Tang, R. Rosales, A. Singh og D. Agarwal. "Automatisk valg av annonseformat via kontekstuelle banditter". I Proceedings of the 22nd ACM International Conference on Information and Knowledge Management. Side 1587–1594. Foreningen for datamaskiner (2013).
https: / / doi.org/ 10.1145 / 2505515.2514700
[6] M. Cohen, I. Lobel og R. Paes Leme. "Funksjonsbasert dynamisk prissetting". Management Science 66, 4921–4943 (2020).
https: / / doi.org/ 10.1287 / mnsc.2019.3485
[7] W. Thompson. "På sannsynligheten for at en ukjent sannsynlighet overstiger en annen i lys av bevisene fra to prøver." Biometrika 25, 285–294 (1933).
https:///doi.org/10.1093/biomet/25.3-4.285
[8] H. Robbins. "Noen aspekter ved den sekvensielle utformingen av eksperimenter". Bulletin of the American Mathematical Society 58, 527–535 (1952).
https://doi.org/10.1090/S0002-9904-1952-09620-8
[9] TL Lai og H. Robbins. "Asymptotisk effektive adaptive 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 og P. Fischer. "Endetidsanalyse av det flerarmede bandittproblemet". Mach. Lære. 47, 235–256 (2002).
https: / / doi.org/ 10.1023 / A: 1013689704352
[11] B. Casalé, G. Di Molfetta, H. Kadri, og L. Ralaivola. "Kvantebanditter". Quantum Mach. Intell. 2 (2020).
https://doi.org/10.1007/s42484-020-00024-8
[12] D. Wang, X. You, T. Li og A. Childs. "Kvanteutforskningsalgoritmer for flerarmede banditter". I Proceedings of the AAAI Conference on Artificial Intelligence. Bind 35, side 10102–10110. (2021).
[13] P. Rebentrost, Y. Hamoudi, M. Ray, X. Wang, S. Yang og M. Santha. "Kvantealgoritmer for sikring og læring av ising-modeller". Phys. Rev. A 103, 012418 (2021).
https: / / doi.org/ 10.1103 / PhysRevA.103.012418
[14] O. Shamir. "Om kompleksiteten til lineær optimalisering av banditt". I Proceedings of The 28th Conference on Learning Theory. Bind 40 av Proceedings of Machine Learning Research, side 1523–1551. PMLR (2015).
[15] P. Rusmevichientong og J. Tsitsiklis. "Lineært parameteriserte banditter". Mathematics of Operations Research 35 (2008).
https: / / doi.org/ 10.1287 / moor.1100.0446
[16] J. Barry, DT Barry og S. Aaronson. "Kvante delvis observerbare markov-beslutningsprosesser". Phys. Rev. A 90, 032311 (2014).
https: / / doi.org/ 10.1103 / PhysRevA.90.032311
[17] M. Ying, Y. Feng og S. Ying. "Optimal policy for kvantemarkov-beslutningsprosesser". International Journal of Automation and Computing 18, 410–421 (2021).
https: / / doi.org/ 10.1007 / s11633-021-1278-z
[18] M. Paris og J. Rehacek. "Kvantetilstandsestimat". Springer Publishing Company, Incorporated. (2010). 1. utgave.
https: / / doi.org/ 10.1007 / b98673
[19] S. Aaronson. "Skyggetomografi av kvantetilstander". I Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. Side 325–338. STOC 2018. Foreningen for datamaskiner (2018).
https: / / doi.org/ 10.1145 / 3188745.3188802
[20] S. Aaronson, X. Chen, E. Hazan, S. Kale og A. Nayak. "Online læring av kvantetilstander". Journal of Statistical Mechanics: Theory and Experiment 2019 (2018).
https: / / doi.org/ 10.1088 / 1742-5468 / ab3988
[21] J. Bretagnolle og C. Huber. "Estimat desité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 og M. Tomamichel. "Om Quantum Rényi-entropier: En ny generalisering og noen egenskaper". Journal of Mathematical Physics 54, 122203 (2013).
https: / / doi.org/ 10.1063 / 1.4838856
[23] M. Wilde, A. Winter og D. Yang. "Sterk samtale for den klassiske kapasiteten til sammenfiltringsbrytende og Hadamard-kanaler via en sammensatt Rényi relativ entropi". Communications in Mathematical Physics 331, 593–622 (2014).
https: / / doi.org/ 10.1007 / s00220-014-2122-x
[24] W. Hoeffding. "Sannsynlighetsulikheter for summer av avgrensede tilfeldige variabler". Journal of the American Statistical Association 58, 13–30 (1963).
https: / / doi.org/ 10.1080 / 01621459.1963.10500830
[25] P. Auer. "Å bruke tillit setter grenser for avveininger mellom utnyttelse og leting". J. Mach. Lære. Res. 3, 397–422 (2003).
https: / / doi.org/ 10.5555 / 944919.944941
[26] D. Varsha, T. Hayes og S.Kakade. "Stokastisk lineær optimalisering under banditt-feedback." I Proceedings of the 21st Conference on Learning Theory. Side 355–366. (2008).
[27] P. Rusmevichientong og JN Tsitsiklis. "Lineært parameteriserte banditter". Mathematics of Operations Research 35, 395–411 (2010).
https: / / doi.org/ 10.1287 / moor.1100.0446
[28] Y. Abbasi-Yadkori, D. Pál og Cs. Szepesvári. "Forbedrede algoritmer for lineære stokastiske banditter". I fremskritt innen nevrale informasjonsbehandlingssystemer. Bind 24. Curran Associates, Inc. (2011).
[29] TL Lai. "Adaptiv behandlingstildeling og det flerarmede bandittproblemet". The Annals of Statistics 15, 1091 – 1114 (1987).
https: / / doi.org/ 10.1214 / AOS / 1176350495
[30] M. Guţă, J. Kahn, R. Kueng og JA Tropp. "Rask tilstandstomografi med optimale feilgrenser". Journal of Physics A: Mathematical and Theoretical 53, 204001 (2020).
https: / / doi.org/ 10.1088 / 1751-8121 / ab8111
[31] T. Lattimore og B. Hao. "Bandittfasehenting". I fremskritt innen nevrale informasjonsbehandlingssystemer. Bind 34, side 18801–18811. Curran Associates, Inc. (2021).
Sitert av
[1] Zongqi Wan, Zhijie Zhang, Tongyang Li, Jialin Zhang og Xiaoming Sun, "Quantum Multi-Armed Bandits and Stokastic Linear Bandits Enjoy Logariithmic Regrets", arxiv: 2205.14988.
[2] Xinyi Chen, Elad Hazan, Tongyang Li, Zhou Lu, Xinzhao Wang og Rui Yang, "Adaptive Online Learning of Quantum States", arxiv: 2206.00220.
Sitatene ovenfor er fra SAO / NASA ADS (sist oppdatert vellykket 2022-07-24 00:26:50). Listen kan være ufullstendig fordi ikke alle utgivere gir passende og fullstendige sitasjonsdata.
On Crossrefs siterte tjeneste ingen data om sitering av verk ble funnet (siste forsøk 2022-07-24 00:26:48).
Denne artikkelen er utgitt i Quantum under Creative Commons Attribution 4.0 International (CC BY 4.0) tillatelse. Opphavsrett forblir hos de opprinnelige rettighetshaverne som forfatterne eller institusjonene deres.
