Mitme relvaga kvantbandiidid: uurimine versus ekspluateerimine kvantolekute omaduste õppimisel

Taasavaldanud Platon

järgijaid: 0

Josep Lumbreras¹, Erkka Haapasalo¹ja Marco Tomamichel^1,2

¹Singapuri riikliku ülikooli kvanttehnoloogia keskus
²Singapuri riikliku ülikooli inseneriteaduskonna elektri- ja arvutitehnika osakond

Kas see artikkel on huvitav või soovite arutada? Scite või jätke SciRate'i kommentaar.

Abstraktne

Algatame kvantolekute omaduste online-õppes uurimise ja kasutamise vaheliste kompromisside uurimist. Arvestades järjestikust oraakli juurdepääsu tundmatule kvantolekule, on meil igas voorus ülesanne valida toimingute hulgast vaadeldav, mille eesmärk on maksimeerida selle eeldatavat väärtust olekule (tasu). Eelmistes voorudes tundmatu oleku kohta kogutud teavet saab kasutada tegevuse valiku järkjärguliseks parandamiseks, vähendades seeläbi lõhet tasu ja antud tegevuskomplektiga saavutatava maksimaalse tasu (kahetsuse) vahel. Pakume erinevaid teabeteoreetilisi alumisi piire kumulatiivsele kahetsusele, mida optimaalne õppija peab kogema, ja näitame, et see ulatub vähemalt mängitud voorude arvu ruutjuureni. Samuti uurime kumulatiivse kahetsuse sõltuvust saadaolevate toimingute arvust ja aluseks oleva ruumi mõõtmest. Veelgi enam, me eksponeerime strateegiaid, mis on optimaalsed piiratud arvu relvade ja üldiste segaseisunditega bandiitide jaoks.

[Varjatud sisu]

► BibTeX-i andmed

@article{Lumbreras2022multiarmedquantum, doi = {10.22331/q-2022-06-29-749}, url = {https://doi.org/10.22331/q-2022-06-29-749}, title = {Mitmekäelised kvantbaniidid: {E}uurimine versus ekspluateerimine kvantolekute omaduste õppimisel}, autor = {Lumbreras, Josep ja Haapasalo, Erkka ja Tomamichel, Marco}, ajakiri = {{Kvant}}, issn = {2521-327X}, väljaandja = {{Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, helitugevus = {6}, lehekülge = {749}, kuu = juuni, aasta = {2022} }

► Viited

[1] T. Lattimore ja C. Szepesvári. "Bandiidi algoritmid". Cambridge University Press. (2020).
https:///doi.org/10.1017/9781108571401

[2] A. Slivkins. "Sissejuhatus mitmekäeliste bandiitidega". Masinõppe alused ja suundumused 12, 1–286 (2019).
https:///doi.org/10.1561/2200000068

[3] S. Bubeck ja N. Cesa-Bianchi. "Stohhastiliste ja mittestohhastiliste mitmekäeliste bandiitide probleemide kahetsusanalüüs". Masinõppe alused ja suundumused 5, 1–122 (2012).
https:///doi.org/10.1561/2200000024

[4] D. Bouneffouf, I. Rish ja C. Aggarwal. "Uuring mitme relvaga ja kontekstuaalsete bandiitide rakenduste kohta". 2020. aastal toimub IEEE evolutsioonilise arvutuse kongress (CEC). Lk 1–8. (2020).
https:///doi.org/10.1109/CEC48606.2020.9185782

[5] L. Tang, R. Rosales, A. Singh ja D. Agarwal. "Reklaamivormingu automaatne valimine kontekstuaalsete bandiitide kaudu". 22. ACM rahvusvahelise teabe- ja teadmusjuhtimise konverentsi toimetistes. Lk 1587–1594. Arvutusmasinate Liit (2013).
https:///doi.org/10.1145/2505515.2514700

[6] M. Cohen, I. Lobel ja R. Paes Leme. "Funktsioonipõhine dünaamiline hinnakujundus". Juhtimisteadus 66, 4921–4943 (2020).
https:///doi.org/10.1287/mnsc.2019.3485

[7] W. Thompson. "Tõenäosuse kohta, et üks tundmatu tõenäosus ületab teise, võttes arvesse kahe valimi tõendeid." Biometrika 25, 285–294 (1933).
https:///doi.org/10.1093/biomet/25.3-4.285

[8] H. Robbins. "Mõned katsete järjestikuse kavandamise aspektid". Bulletin of the American Mathematical Society, lk 58, 527–535 (1952).
https://doi.org/10.1090/S0002-9904-1952-09620-8

[9] TL Lai ja H. Robbins. "Asümptootiliselt tõhusad adaptiivsed jaotamise reeglid". Advances in Applied Mathematics 6, 4–22 (1985).
https://doi.org/10.1016/0196-8858(85)90002-8

[10] P. Auer, N. Cesa-Bianchi ja P. Fischer. "Mitmerelvaliste bandiitide probleemi piiratud aja analüüs". Mach. Õppige. 47, 235–256 (2002).
https:///doi.org/10.1023/A:1013689704352

[11] B. Casalé, G. Di Molfetta, H. Kadri, ja L. Ralaivola. "Kvantbandiidid". Quantum Mach. Intell. 2 (2020).
https://doi.org/10.1007/s42484-020-00024-8

[12] D. Wang, X. Sina, T. Li ja A. Childs. "Mitmekäeliste bandiitide kvantuuringute algoritmid". AAAI tehisintellekti konverentsi toimetistes. 35. köide, lk 10102–10110. (2021).

[13] P. Rebentrost, Y. Hamoudi, M. Ray, X. Wang, S. Yang ja M. Santha. "Kvantalgoritmid riskimaandamiseks ja mudelite õppimiseks". Phys. Rev. A 103, 012418 (2021).
https:///doi.org/10.1103/PhysRevA.103.012418

[14] O. Šamir. "Bandiidi lineaarse optimeerimise keerukusest". In Proceedings of The 28th Conference on Learning Theory. Proceedings of Machine Learning Research, 40. köide, lk 1523–1551. PMLR (2015).

[15] P. Rusmevichientong ja J. Tsitsiklis. "Lineaarselt parameetritega bandiidid". Operatsiooniuuringute matemaatika 35 (2008).
https:///doi.org/10.1287/moor.1100.0446

[16] J. Barry, DT Barry ja S. Aaronson. "Kvant-osaliselt jälgitavad Markovi otsustusprotsessid". Phys. Rev. A 90, 032311 (2014).
https:///doi.org/10.1103/PhysRevA.90.032311

[17] M. Ying, Y. Feng ja S. Ying. "Optimaalne poliitika kvantmarkovi otsustusprotsesside jaoks". International Journal of Automation and Computing 18, 410–421 (2021).
https:///doi.org/10.1007/s11633-021-1278-z

[18] M. Paris ja J. Rehacek. "Kvantseisundi hindamine". Springer Publishing Company, asutatud. (2010). 1. väljaanne.
https:///doi.org/10.1007/b98673

[19] S. Aaronson. "Kvantseisundite varitomograafia". In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. Lk 325–338. STOC 2018. Arvutusmasinate Liit (2018).
https:///doi.org/10.1145/3188745.3188802

[20] S. Aaronson, X. Chen, E. Hazan, S. Kale ja A. Nayak. "Kvantolekute veebiõpe". Journal of Statistical Mechanics: Theory and Experiment 2019 (2018).
https:///doi.org/10.1088/1742-5468/ab3988

[21] J. Bretagnolle ja C. Huber. “Estimation 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 ja M. Tomamichel. “Kvantrényi entroopiate kohta: uus üldistus ja mõned omadused”. Journal of Mathematical Physics 54, 122203 (2013).
https:///doi.org/10.1063/1.4838856

[23] M. Wilde, A. Winter ja D. Yang. "Tugev vestlus klassikalise põimumise katkestamise ja Hadamardi kanalite võime jaoks vahekihiga Rényi suhtelise entroopia kaudu". Kommunikatsioonid matemaatilises füüsikas 331, 593–622 (2014).
https:///doi.org/10.1007/s00220-014-2122-x

[24] W. Hoeffding. "Piiratud juhuslike muutujate summade tõenäosuse ebavõrdsused". Journal of the American Statistical Association, 58, 13–30 (1963).
https:///doi.org/10.1080/01621459.1963.10500830

[25] P. Auer. "Usalduspiiride kasutamine ekspluateerimise ja uurimise kompromissideks". J. Mach. Õppige. Res. 3, 397–422 (2003).
https:///doi.org/10.5555/944919.944941

[26] D. Varsha, T. Hayes ja S. Kakade. "Stohhastiline lineaarne optimeerimine bandiidi tagasiside all." 21. õpiteooria konverentsi toimetistes. Lk 355–366. (2008).

[27] P. Rusmevichientong ja JN Tsitsiklis. "Lineaarselt parameetritega bandiidid". Operatsiooniuuringute matemaatika 35, 395–411 (2010).
https:///doi.org/10.1287/moor.1100.0446

[28] Y. Abbasi-Yadkori, D. Pál ja Cs. Szepesvári. "Täiustatud algoritmid lineaarsete stohhastiliste bandiitide jaoks". Neuraalsete teabetöötlussüsteemide edusammudes. 24. köide. Curran Associates, Inc. (2011).

[29] TL Lai. "Adaptiivne ravi määramine ja mitme relvaga bandiidi probleem". The Annals of Statistics 15, 1091–1114 (1987).
https:///doi.org/10.1214/aos/1176350495

[30] M. Guţă, J. Kahn, R. Kueng ja JA Tropp. "Kiire olekuga tomograafia optimaalsete veapiiridega". Journal of Physics A: Mathematical and Theoretical 53, 204001 (2020).
https:///doi.org/10.1088/1751-8121/ab8111

[31] T. Lattimore ja B. Hao. "Bandiidi faasi otsimine". Neuraalsete teabetöötlussüsteemide edusammudes. 34. köide, lk 18801–18811. Curran Associates, Inc. (2021).

Viidatud

[1] Zongqi Wan, Zhijie Zhang, Tongyang Li, Jialin Zhang ja Xiaoming Sun, “Kvant-mitmerelvalised bandiidid ja stohhastilised lineaarsed bandiidid naudivad logaritmilist kahetsust”, arXiv: 2205.14988.

[2] Xinyi Chen, Elad Hazan, Tongyang Li, Zhou Lu, Xinzhao Wang ja Rui Yang, „Adaptive Online Learning of Quantum States” arXiv: 2206.00220.

Ülaltoodud tsitaadid on pärit SAO/NASA KUULUTUSED (viimati edukalt värskendatud 2022-07-24 00:26:50). Loend võib olla puudulik, kuna mitte kõik väljaandjad ei esita sobivaid ja täielikke viiteandmeid.

On Crossrefi viidatud teenus teoste viitamise andmeid ei leitud (viimane katse 2022-07-24 00:26:48).

See raamat on avaldatud Quantum all Creative Commons Attribution 4.0 International (CC BY 4.0) litsents. Autoriõigus jääb algsetele autoriõiguste valdajatele, näiteks autoritele või nende institutsioonidele.