1Centrul pentru Tehnologii Cuantice, Universitatea Națională din Singapore, Singapore
2Departamentul de Inginerie Electrică și Calculatoare, Facultatea de Inginerie, Universitatea Națională din Singapore, Singapore
Găsiți această lucrare interesant sau doriți să discutați? Scite sau lasă un comentariu la SciRate.
Abstract
Inițiem studiul compromisurilor între explorarea și exploatarea în învățarea online a proprietăților stărilor cuantice. Având în vedere accesul oracol secvenţial la o stare cuantică necunoscută, în fiecare rundă, suntem însărcinaţi să alegem un observabil dintr-un set de acţiuni care urmăresc să maximizeze valoarea aşteptărilor sale asupra stării (recompensa). Informațiile obținute despre starea necunoscută din rundele anterioare pot fi folosite pentru a îmbunătăți treptat alegerea acțiunii, reducând astfel decalajul dintre recompensă și recompensa maximă atinsă cu setul de acțiuni dat (regretul). Oferim diverse limite inferioare teoretice informaționale cu privire la regretul cumulativ pe care trebuie să-l suporte un cursant optim și arătăm că acesta crește cel puțin ca rădăcina pătrată a numărului de runde jucate. De asemenea, investigăm dependența regretului cumulat de numărul de acțiuni disponibile și dimensiunea spațiului subiacent. Mai mult, expunem strategii care sunt optime pentru bandiții cu un număr finit de arme și stări generale mixte.
[Conținutul încorporat]
► Date BibTeX
► Referințe
[1] T. Lattimore și C. Szepesvári. „Algoritmi de bandit”. Cambridge University Press. (2020).
https: / / doi.org/ 10.1017 / 9781108571401
[2] A. Slivkins. „Introducere în bandiții multi-armate”. Fundamente și tendințe în învățarea automată 12, 1–286 (2019).
https: / / doi.org/ 10.1561 / 2200000068
[3] S. Bubeck şi N. Cesa-Bianchi. „Analiza regretului a problemelor stochastice și nonstohastice ale bandiților multi-armate”. Fundamente și tendințe în învățarea automată 5, 1–122 (2012).
https: / / doi.org/ 10.1561 / 2200000024
[4] D. Bouneffouf, I. Rish și C. Aggarwal. „Sondaj asupra aplicațiilor bandiților multi-armate și contextuali”. În 2020, IEEE Congress on Evolutionary Computation (CEC). Paginile 1–8. (2020).
https:///doi.org/10.1109/CEC48606.2020.9185782
[5] L. Tang, R. Rosales, A. Singh și D. Agarwal. „Selectare automată a formatului de anunț prin bandiți contextuali”. În Proceedings of the 22th ACM International Conference on Information and Knowledge Management. Pagina 1587–1594. Asociația pentru Mașini de Calcul (2013).
https: / / doi.org/ 10.1145 / 2505515.2514700
[6] M. Cohen, I. Lobel și R. Paes Leme. „Prețuri dinamice bazate pe funcții”. Management Science 66, 4921–4943 (2020).
https:///doi.org/10.1287/mnsc.2019.3485
[7] W. Thompson. „Cu privire la probabilitatea ca o probabilitate necunoscută să o depășească pe alta, având în vedere dovezile a două eșantioane”. Biometrika 25, 285–294 (1933).
https:///doi.org/10.1093/biomet/25.3-4.285
[8] H. Robbins. „Câteva aspecte ale designului secvenţial al experimentelor”. Buletinul Societății Americane de Matematică 58, 527–535 (1952).
https://doi.org/10.1090/S0002-9904-1952-09620-8
[9] TL Lai și H. Robbins. „Reguli de alocare adaptativă eficientă asimptotic”. Advances in Applied Mathematics 6, 4–22 (1985).
https://doi.org/10.1016/0196-8858(85)90002-8
[10] P. Auer, N. Cesa-Bianchi și P. Fischer. „Analiza în timp finit a problemei bandiților multiarmate”. Mach. Învăța. 47, 235–256 (2002).
https: / / doi.org/ 10.1023 / A: 1013689704352
[11] B. Casalé, G. Di Molfetta, H. Kadri, , and L. Ralaivola. „Bandiți cuantici”. Quantum Mach. Intel. 2 (2020).
https://doi.org/10.1007/s42484-020-00024-8
[12] D. Wang, X. You, T. Li și A. Childs. „Algoritmi de explorare cuantică pentru bandiți cu mai multe arme”. În Proceedings of the AAAI Conference on Artificial Intelligence. Volumul 35, paginile 10102–10110. (2021).
[13] P. Rebentrost, Y. Hamoudi, M. Ray, X. Wang, S. Yang și M. Santha. „Algoritmi cuantici pentru acoperire și învățarea modelelor de ising”. Fiz. Rev. A 103, 012418 (2021).
https: / / doi.org/ 10.1103 / PhysRevA.103.012418
[14] O. Shamir. „Despre complexitatea optimizării liniare bandit”. În Proceedings of The 28th Conference on Learning Theory. Volumul 40 din Proceedings of Machine Learning Research, paginile 1523–1551. PMLR (2015).
[15] P. Rusmevichientong şi J. Tsitsiklis. „Bandiți parametrizați liniar”. Matematica cercetării operaționale 35 (2008).
https: / / doi.org/ 10.1287 / moor.1100.0446
[16] J. Barry, DT Barry și S. Aaronson. „Procese de decizie cuantice markov parțial observabile”. Fiz. Rev. A 90, 032311 (2014).
https: / / doi.org/ 10.1103 / PhysRevA.90.032311
[17] M. Ying, Y. Feng și S. Ying. „Politici optime pentru procesele de decizie cuantică markov”. International Journal of Automation and Computing 18, 410–421 (2021).
https: / / doi.org/ 10.1007 / s11633-021-1278-z
[18] M. Paris şi J. Rehacek. „Estimarea stării cuantice”. Springer Publishing Company, Incorporated. (2010). editia 1.
https: / / doi.org/ 10.1007 / b98673
[19] S. Aaronson. „Tomografia în umbră a stărilor cuantice”. În Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. Pagina 325–338. STOC 2018. Asociația pentru Mașini de Calcul (2018).
https: / / doi.org/ 10.1145 / 3188745.3188802
[20] S. Aaronson, X. Chen, E. Hazan, S. Kale și A. Nayak. „Învățarea online a stărilor cuantice”. Journal of Statistical Mechanics: Theory and Experiment 2019 (2018).
https: / / doi.org/ 10.1088 / 1742-5468 / ab3988
[21] J. Bretagnolle şi C. Huber. „Estimation des densités: risc 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 și M. Tomamichel. „Despre entropiile cuantice Rényi: o nouă generalizare și unele proprietăți”. Journal of Mathematical Physics 54, 122203 (2013).
https: / / doi.org/ 10.1063 / 1.4838856
[23] M. Wilde, A. Winter și D. Yang. „Conversație puternică pentru capacitatea clasică de rupere a încurcăturii și canalele Hadamard printr-o entropie relativă Sandwiched Rényi”. Communications in Mathematical Physics 331, 593–622 (2014).
https: / / doi.org/ 10.1007 / s00220-014-2122-x
[24] W. Hoeffding. „Inegalități de probabilitate pentru sumele variabilelor aleatoare mărginite”. Jurnalul Asociaţiei Americane de Statistică 58, 13–30 (1963).
https: / / doi.org/ 10.1080 / 01621459.1963.10500830
[25] P. Auer. „Folosirea limitelor de încredere pentru compromisuri exploatare-explorare”. J. Mach. Învăța. Res. 3, 397–422 (2003).
https: / / doi.org/ 10.5555 / 944919.944941
[26] D. Varsha, T. Hayes și S.Kakade. „Optimizare liniară stocastică sub feedback bandit”. În Proceedings of the 21st Conference on Learning Theory. Paginile 355–366. (2008).
[27] P. Rusmevichientong și JN Tsitsiklis. „Bandiți parametrizați liniar”. Matematica cercetării operaționale 35, 395–411 (2010).
https: / / doi.org/ 10.1287 / moor.1100.0446
[28] Y. Abbasi-Yadkori, D. Pál și Cs. Szepesvári. „Algoritmi îmbunătățiți pentru bandiții stocastici liniari”. În avansuri în sistemele de procesare a informațiilor neuronale. Volumul 24. Curran Associates, Inc. (2011).
[29] TL Lai. „Alocarea adaptivă a tratamentului și problema bandiților multi-armate”. Analele statisticii 15, 1091 – 1114 (1987).
https: / / doi.org/ 10.1214 / AOS / 1176350495
[30] M. Guţă, J. Kahn, R. Kueng şi JA Tropp. „Tomografie în stare rapidă cu limite optime de eroare”. Journal of Physics A: Mathematical and Theoretical 53, 204001 (2020).
https: / / doi.org/ 10.1088 / 1751-8121 / ab8111
[31] T. Lattimore și B. Hao. „Recuperarea fazei de bandit”. În avansuri în sistemele de procesare a informațiilor neuronale. Volumul 34, paginile 18801–18811. Curran Associates, Inc. (2021).
Citat de
[1] Zongqi Wan, Zhijie Zhang, Tongyang Li, Jialin Zhang și 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 și Rui Yang, „Adaptive Online Learning of Quantum States”, arXiv: 2206.00220.
Citatele de mai sus sunt din ADS SAO / NASA (ultima actualizare cu succes 2022-07-24 00:26:50). Lista poate fi incompletă, deoarece nu toți editorii furnizează date de citare adecvate și complete.
On Serviciul citat de Crossref nu s-au găsit date despre citarea lucrărilor (ultima încercare 2022-07-24 00:26:48).
Acest Lucru este publicat în Quantum sub Creative Commons Atribuire 4.0 internațională (CC BY 4.0) licență. Drepturile de autor rămân la deținătorii de drepturi de autor originale, precum autorii sau instituțiile lor.
