1Center for Quantum Technologies, National University of Singapore, Singapore
2Institut for Elektro- og Computerteknik, Det Tekniske Fakultet, National University of Singapore, Singapore
Finder du denne artikel interessant eller vil du diskutere? Scite eller efterlade en kommentar på SciRate.
Abstrakt
Vi starter studiet af afvejninger mellem udforskning og udnyttelse i online læring af egenskaber ved kvantetilstande. Givet sekventiel orakeladgang til en ukendt kvantetilstand, har vi i hver runde til opgave at vælge en observerbar fra et sæt af handlinger, der sigter mod at maksimere dens forventningsværdi for staten (belønningen). Information opnået om den ukendte tilstand fra tidligere runder kan bruges til gradvist at forbedre valget af handling, og dermed reducere afstanden mellem belønningen og den maksimale belønning, der kan opnås med det givne handlingssæt (beklagelsen). Vi giver forskellige informationsteoretiske nedre grænser for den kumulative fortrydelse, som en optimal elev skal pådrage sig, og viser, at den skalerer mindst som kvadratroden af antallet af spillet runder. Vi undersøger også afhængigheden af den kumulative beklagelse af antallet af tilgængelige handlinger og dimensionen af det underliggende rum. Desuden udviser vi strategier, der er optimale for banditter med et begrænset antal arme og generelle blandede tilstande.
[Indlejret indhold]
► BibTeX-data
► Referencer
[1] T. Lattimore og C. Szepesvári. "Banditalgoritmer". Cambridge University Press. (2020).
https:///doi.org/10.1017/9781108571401
[2] A. Slivkins. "Introduktion til flerarmede banditter". Fundamenter og tendenser i maskinlæring 12, 1-286 (2019).
https:///doi.org/10.1561/2200000068
[3] S. Bubeck og N. Cesa-Bianchi. "Beklager analyse af stokastiske og ikke-stokastiske flerarmede banditproblemer". Fundamenter og tendenser i maskinlæring 5, 1-122 (2012).
https:///doi.org/10.1561/2200000024
[4] D. Bouneffouf, I. Rish og C. Aggarwal. "Undersøgelse om anvendelser af 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 af annonceformat via kontekstuelle banditter". I Proceedings of the 22nd ACM International Conference on Information and Knowledge Management. Side 1587–1594. Foreningen for Computermaskiner (2013).
https:///doi.org/10.1145/2505515.2514700
[6] M. Cohen, I. Lobel og R. Paes Leme. "Funktionsbaseret dynamisk prissætning". Management Science 66, 4921–4943 (2020).
https:///doi.org/10.1287/mnsc.2019.3485
[7] W. Thompson. "På sandsynligheden for, at en ukendt sandsynlighed overstiger en anden i lyset af beviserne fra to prøver". Biometrika 25, 285-294 (1933).
https:///doi.org/10.1093/biomet/25.3-4.285
[8] H. Robbins. "Nogle aspekter af det sekventielle design af 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 af det flerarmede banditproblem". 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. "Kvanteudforskningsalgoritmer 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 til afdækning og indlæring af ising-modeller". Phys. Rev. A 103, 012418 (2021).
https:///doi.org/10.1103/PhysRevA.103.012418
[14] O. Shamir. "Om kompleksiteten af bandit lineær optimering". I Proceedings of The 28th Conference on Learning Theory. Bind 40 af Proceedings of Machine Learning Research, side 1523-1551. PMLR (2015).
[15] P. Rusmevichientong og J. Tsitsiklis. "Lineært parameteriserede banditter". Mathematics of Operations Research 35 (2008).
https:///doi.org/10.1287/moor.1100.0446
[16] J. Barry, DT Barry og S. Aaronson. "Kvante delvist observerbare markov-beslutningsprocesser". Phys. Rev. A 90, 032311 (2014).
https:///doi.org/10.1103/PhysRevA.90.032311
[17] M. Ying, Y. Feng og S. Ying. "Optimale politikker for kvantemarkov-beslutningsprocesser". 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. udgave.
https://doi.org/10.1007/b98673
[19] S. Aaronson. "Skyggetomografi af kvantetilstande". I Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. Side 325–338. STOC 2018. Foreningen for Computing Machinery (2018).
https:///doi.org/10.1145/3188745.3188802
[20] S. Aaronson, X. Chen, E. Hazan, S. Kale og A. Nayak. "Online læring af kvantetilstande". 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 Entropies: En ny generalisering og nogle egenskaber". Journal of Mathematical Physics 54, 122203 (2013).
https:///doi.org/10.1063/1.4838856
[23] M. Wilde, A. Winter og D. Yang. "Stærk samtale om den klassiske kapacitet af sammenfiltringsbrydende og Hadamard-kanaler via en indlejret Rényi-relativ entropi". Communications in Mathematical Physics 331, 593–622 (2014).
https:///doi.org/10.1007/s00220-014-2122-x
[24] W. Hoeffding. "Sandsynlighedsuligheder for summer af afgrænsede stokastiske variable". Journal of the American Statistical Association 58, 13–30 (1963).
https:///doi.org/10.1080/01621459.1963.10500830
[25] P. Auer. "Brug af tillid grænser til afvejninger mellem udnyttelse og udforskning". 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 optimering under banditfeedback." I Proceedings of the 21st Conference on Learning Theory. Side 355-366. (2008).
[27] P. Rusmevichientong og JN Tsitsiklis. "Lineært parameteriserede 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 til lineære stokastiske banditter". Fremskridt inden for neurale informationsbehandlingssystemer. Bind 24. Curran Associates, Inc. (2011).
[29] TL Lai. "Adaptiv behandlingstildeling og det flerarmede banditproblem". 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. "Hurtig tilstandstomografi med optimale fejlgrænser". Journal of Physics A: Mathematical and Theoretical 53, 204001 (2020).
https:///doi.org/10.1088/1751-8121/ab8111
[31] T. Lattimore og B. Hao. "Bandit fase hentning". Fremskridt inden for neurale informationsbehandlingssystemer. Bind 34, sider 18801–18811. Curran Associates, Inc. (2021).
Citeret af
[1] Zongqi Wan, Zhijie Zhang, Tongyang Li, Jialin Zhang og 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 og Rui Yang, "Adaptive Online Learning of Quantum States", arXiv: 2206.00220.
Ovenstående citater er fra SAO/NASA ADS (sidst opdateret 2022-07-24 00:26:50). Listen kan være ufuldstændig, da ikke alle udgivere leverer passende og fuldstændige citatdata.
On Crossrefs citeret af tjeneste ingen data om at citere værker blev fundet (sidste forsøg 2022-07-24 00:26:48).
Dette papir er udgivet i Quantum under Creative Commons Attribution 4.0 International (CC BY 4.0) licens. Ophavsretten forbliver hos de originale copyright-indehavere, såsom forfatterne eller deres institutioner.
