1Szingapúri Nemzeti Egyetem Quantum Technologies Központja, Szingapúr
2Villamos- és Számítástechnikai Tanszék, Műszaki Kar, Szingapúri Nemzeti Egyetem, Szingapúr
Érdekesnek találja ezt a cikket, vagy szeretne megvitatni? Scite vagy hagyjon megjegyzést a SciRate-en.
Absztrakt
Kezdeményezzük a feltárás és a kiaknázás közötti kompromisszumok tanulmányozását a kvantumállapotok tulajdonságainak online tanulásában. Tekintettel arra, hogy az orákulum szekvenciálisan hozzáfér egy ismeretlen kvantumállapothoz, minden körben az a feladatunk, hogy válasszunk egy megfigyelhetőt a cselekvések halmazából, hogy maximalizáljuk az állapotra vonatkozó elvárási értékét (a jutalmat). A korábbi körök ismeretlen állapotáról szerzett információk segítségével fokozatosan javítható a cselekvés kiválasztása, így csökkenthető a jutalom és az adott akciókészlettel elérhető maximális jutalom (a megbánás) közötti különbség. Különböző információelméleti alsó határokat adunk meg a halmozott sajnálatnak, amelyet egy optimális tanulónak el kell viselnie, és megmutatjuk, hogy ez legalább a lejátszott fordulók számának négyzetgyökével skálázódik. Megvizsgáljuk továbbá a halmozott megbánás függését a rendelkezésre álló cselekvések számától és a mögöttes tér dimenziójától. Ezenkívül olyan stratégiákat mutatunk be, amelyek optimálisak a véges számú karral és általános vegyes állapotú banditák számára.
[Beágyazott tartalmat]
► BibTeX adatok
► Referenciák
[1] T. Lattimore és C. Szepesvári. „Bandita algoritmusok”. Cambridge University Press. (2020).
https:///doi.org/10.1017/9781108571401
[2] A. Slivkins. „Bevezetés a többkarú banditákba”. Foundations and Trends in Machine Learning 12, 1–286 (2019).
https:///doi.org/10.1561/2200000068
[3] S. Bubeck és N. Cesa-Bianchi. „Sztochasztikus és nem sztochasztikus többkarú rablóproblémák sajnálatos elemzése”. Foundations and Trends in Machine Learning 5, 1–122 (2012).
https:///doi.org/10.1561/2200000024
[4] D. Bouneffouf, I. Rish és C. Aggarwal. „Felmérés a többkarú és kontextuális banditák alkalmazásairól”. 2020-ban az IEEE Congress on Evolutionary Computation (CEC). 1–8. oldal. (2020).
https:///doi.org/10.1109/CEC48606.2020.9185782
[5] L. Tang, R. Rosales, A. Singh és D. Agarwal. „Automatikus hirdetésformátum-választás kontextuális banditák segítségével”. In Proceedings of the 22nd ACM International Conference on Information and Knowledge Management. 1587–1594. oldal. Számítógépek Szövetsége (2013).
https:///doi.org/10.1145/2505515.2514700
[6] M. Cohen, I. Lobel és R. Paes Leme. „Funkcióalapú dinamikus árképzés”. Management Science 66, 4921–4943 (2020).
https:///doi.org/10.1287/mnsc.2019.3485
[7] W. Thompson. „Annak valószínűségéről, hogy az egyik ismeretlen valószínűség meghaladja a másikat, tekintettel két minta bizonyítékaira”. Biometrika 25, 285–294 (1933).
https:///doi.org/10.1093/biomet/25.3-4.285
[8] H. Robbins. „A kísérletek szekvenciális tervezésének néhány szempontja”. Bulletin of the American Mathematical Society 58, 527–535 (1952).
https://doi.org/10.1090/S0002-9904-1952-09620-8
[9] TL Lai és H. Robbins. „Aszimptotikusan hatékony adaptív allokációs szabályok”. Advances in Applied Mathematics 6, 4–22 (1985).
https://doi.org/10.1016/0196-8858(85)90002-8
[10] P. Auer, N. Cesa-Bianchi és P. Fischer. „A többkarú rablóprobléma véges idejű elemzése”. Mach. Tanul. 47, 235–256 (2002).
https:///doi.org/10.1023/A:1013689704352
[11] B. Casalé, G. Di Molfetta, H. Kadri, és L. Ralaivola. „Kvantumbanditák”. Quantum Mach. Intell. 2 (2020).
https://doi.org/10.1007/s42484-020-00024-8
[12] D. Wang, X. You, T. Li és A. Childs. „Kvantumfeltáró algoritmusok többkarú banditák számára”. In Proceedings of the AAAI Conference on Artificial Intelligence. 35. kötet, 10102–10110. (2021).
[13] P. Rebentrost, Y. Hamoudi, M. Ray, X. Wang, S. Yang és M. Santha. „Kvantumalgoritmusok a fedezeti ügyletekhez és a modellezési modellek tanulásához”. Phys. Rev. A 103, 012418 (2021).
https:///doi.org/10.1103/PhysRevA.103.012418
[14] O. Shamir. „A bandita lineáris optimalizálás bonyolultságáról”. In Proceedings of The 28th Conference on Learning Theory. Proceedings of Machine Learning Research 40. kötete, 1523–1551. PMLR (2015).
[15] P. Rusmevichientong és J. Tsitsiklis. „Lineárisan paraméterezett banditák”. Operációkutatás matematikája 35 (2008).
https:///doi.org/10.1287/moor.1100.0446
[16] J. Barry, DT Barry és S. Aaronson. „Kvantumban részben megfigyelhető Markov döntési folyamatok”. Phys. Rev. A 90, 032311 (2014).
https:///doi.org/10.1103/PhysRevA.90.032311
[17] M. Ying, Y. Feng és S. Ying. „Optimális irányelvek a kvantummarkov döntési folyamatokhoz”. International Journal of Automation and Computing 18, 410–421 (2021).
https:///doi.org/10.1007/s11633-021-1278-z
[18] M. Paris és J. Rehacek. „Kvantumállapot-becslés”. Springer Publishing Company, Incorporated. (2010). 1. kiadás.
https:///doi.org/10.1007/b98673
[19] S. Aaronson. „A kvantumállapotok árnyéktomográfiája”. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. 325–338. oldal. STOC 2018. Association for Computing Machinery (2018).
https:///doi.org/10.1145/3188745.3188802
[20] S. Aaronson, X. Chen, E. Hazan, S. Kale és A. Nayak. „A kvantumállapotok online tanulása”. Journal of Statistical Mechanics: Theory and Experiment 2019 (2018).
https:///doi.org/10.1088/1742-5468/ab3988
[21] J. Bretagnolle és C. Huber. „Estimation des densité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 és M. Tomamichel. „A kvantumrényi entrópiákról: új általánosítás és néhány tulajdonság”. Journal of Mathematical Physics 54, 122203 (2013).
https:///doi.org/10.1063/1.4838856
[23] M. Wilde, A. Winter és D. Yang. „Erős társalgás az összefonódás-megszakítás és a Hadamard-csatornák klasszikus képességéhez egy szendvics-rényi relatív entrópián keresztül”. Communications in Mathematical Physics 331, 593–622 (2014).
https:///doi.org/10.1007/s00220-014-2122-x
[24] W. Hoeffding. „Valószínűségi egyenlőtlenségek korlátos valószínűségi változók összegére”. Journal of the American Statistical Association 58, 13–30 (1963).
https:///doi.org/10.1080/01621459.1963.10500830
[25] P. Auer. „A bizalmi korlátok használata a kiaknázás és a feltárás közötti kompromisszumokhoz”. J. Mach. Tanul. Res. 3, 397–422 (2003).
https:///doi.org/10.5555/944919.944941
[26] D. Varsha, T. Hayes és S. Kakade. "Sztochasztikus lineáris optimalizálás bandita visszacsatolás alatt." In Proceedings of the 21. Conference on Learning Theory. 355–366. oldal. (2008).
[27] P. Rusmevichientong és JN Tsitsiklis. „Lineárisan paraméterezett banditák”. Mathematics of Operations Research 35, 395–411 (2010).
https:///doi.org/10.1287/moor.1100.0446
[28] Y. Abbasi-Yadkori, D. Pál, és Cs. Szepesvári. „Továbbfejlesztett algoritmusok lineáris sztochasztikus banditákhoz”. In Advances in Neural Information Processing Systems. 24. kötet Curran Associates, Inc. (2011).
[29] TL Lai. „Adaptív kezelések elosztása és a többkarú bandita probléma”. The Annals of Statistics 15, 1091–1114 (1987).
https:///doi.org/10.1214/aos/1176350495
[30] M. Guţă, J. Kahn, R. Kueng és JA Tropp. „Gyors állapotú tomográfia optimális hibahatárokkal”. Journal of Physics A: Mathematical and Theoretical 53, 204001 (2020).
https:///doi.org/10.1088/1751-8121/ab8111
[31] T. Lattimore és B. Hao. „Bandita fázis visszakeresés”. In Advances in Neural Information Processing Systems. 34. kötet, 18801–18811. Curran Associates, Inc. (2021).
Idézi
[1] Zongqi Wan, Zhijie Zhang, Tongyang Li, Jialin Zhang és Xiaoming Sun, „Kvantum többkarú banditák és sztochasztikus lineáris banditák élvezik a logaritmikus sajnálkozást”, arXiv: 2205.14988.
[2] Xinyi Chen, Elad Hazan, Tongyang Li, Zhou Lu, Xinzhao Wang és Rui Yang, „Adaptive Online Learning of Quantum States”, arXiv: 2206.00220.
A fenti idézetek innen származnak SAO/NASA HIRDETÉSEK (utolsó sikeres frissítés: 2022-07-24 00:26:50). Előfordulhat, hogy a lista hiányos, mivel nem minden kiadó ad megfelelő és teljes hivatkozási adatokat.
On Crossref által idézett szolgáltatás művekre hivatkozó adat nem található (utolsó próbálkozás 2022-07-24 00:26:48).
Ez a tanulmány a Quantumban jelent meg Creative Commons Nevezd meg 4.0 International (CC BY 4.0) engedély. A szerzői jog az eredeti szerzői jog tulajdonosainál marad, például a szerzőknél vagy intézményeiknél.
