1Center for Quantum Technologies, National University of Singapore, Singapur
2Department of Electrical and Computer Engineering, Faculty of Engineering, National University of Singapore, Singapur
Czy ten artykuł jest interesujący czy chcesz dyskutować? Napisz lub zostaw komentarz do SciRate.
Abstrakcyjny
Inicjujemy badanie kompromisów między eksploracją a eksploatacją w uczeniu online właściwości stanów kwantowych. Mając sekwencyjny dostęp wyroczni do nieznanego stanu kwantowego, w każdej rundzie mamy za zadanie wybrać obserwowalny z zestawu działań mających na celu zmaksymalizowanie jego wartości oczekiwanej względem stanu (nagrody). Informacje uzyskane o nieznanym stanie z poprzednich rund można wykorzystać do stopniowego ulepszania wyboru akcji, zmniejszając w ten sposób różnicę między nagrodą a maksymalną nagrodą możliwą do osiągnięcia przy danym zestawie akcji (żal). Podajemy różne dolne granice informacyjne teoretyczne dotyczące skumulowanego żalu, jaki musi ponieść optymalny uczeń, i pokazujemy, że skaluje się on co najmniej jako pierwiastek kwadratowy z liczby rozegranych rund. Badamy również zależność skumulowanego żalu od liczby dostępnych działań i wymiaru przestrzeni leżącej u ich podstaw. Ponadto przedstawiamy strategie, które są optymalne dla bandytów ze skończoną liczbą broni i ogólnych stanów mieszanych.
[Osadzone treści]
► Dane BibTeX
► Referencje
[1] T. Lattimore i C. Szepesvári. „Algorytmy bandytów”. Wydawnictwo Uniwersytetu Cambridge. (2020).
https: / / doi.org/ 10.1017 / 9781108571401
[2] A. Slivkinsa. „Wprowadzenie do wielorękich bandytów”. Podstawy i trendy w uczeniu maszynowym 12, 1–286 (2019).
https: / / doi.org/ 10.1561 / 2200000068
[3] S. Bubeck i N. Cesa-Bianchi. „Analiza żalu stochastycznych i niestochastycznych problemów wielorękich bandytów”. Podstawy i trendy w uczeniu maszynowym 5, 1–122 (2012).
https: / / doi.org/ 10.1561 / 2200000024
[4] D. Bouneffouf, I. Rish i C. Aggarwal. „Ankieta dotycząca zastosowań wielorękich i kontekstowych bandytów”. W 2020 roku IEEE Congress on Evolutionary Computation (CEC). Strony 1–8. (2020).
https:///doi.org/10.1109/CEC48606.2020.9185782
[5] L. Tang, R. Rosales, A. Singh i D. Agarwal. „Automatyczny wybór formatu reklamy przez kontekstowych bandytów”. W materiałach XXII Międzynarodowej Konferencji ACM nt. Zarządzania Informacją i Wiedzą. Strona 22–1587. Stowarzyszenie Maszyn Komputerowych (1594).
https: / / doi.org/ 10.1145 / 2505515.2514700
[6] M. Cohen, I. Lobel i R. Paes Leme. „Dynamiczna wycena oparta na funkcjach”. Nauka o zarządzaniu 66, 4921-4943 (2020).
https:///doi.org/10.1287/mnsc.2019.3485
[7] W. Thompsona. „O prawdopodobieństwie, że jedno nieznane prawdopodobieństwo przewyższa inne w świetle dowodów dwóch próbek”. Biometrika 25, 285–294 (1933).
https:///doi.org/10.1093/biomet/25.3-4.285
[8] H. Robbinsa. „Niektóre aspekty sekwencyjnego projektowania eksperymentów”. Biuletyn Amerykańskiego Towarzystwa Matematycznego 58, 527-535 (1952).
https://doi.org/10.1090/S0002-9904-1952-09620-8
[9] TL Lai i H. Robbins. „Asymptotycznie skuteczne adaptacyjne zasady alokacji”. Postępy w matematyce stosowanej 6, 4-22 (1985).
https://doi.org/10.1016/0196-8858(85)90002-8
[10] P. Auer, N. Cesa-Bianchi i P. Fischer. „Analiza skończona problemu wielorękiego bandyty”. Macha Uczyć się. 47, 235-256 (2002).
https: / / doi.org/ 10.1023 / A: 1013689704352
[11] B. Casalé, G. Di Molfetta, H. Kadri i L. Ralaivola. „Bandyci kwantowi”. Macha kwantowa. Intel. 2 (2020).
https://doi.org/10.1007/s42484-020-00024-8
[12] D. Wang, X. You, T. Li i A. Childs. „Algorytmy eksploracji kwantowej dla wielorękich bandytów”. W materiałach z konferencji AAAI na temat sztucznej inteligencji. Tom 35, strony 10102–10110. (2021).
[13] P. Rebentrost, Y. Hamoudi, M. Ray, X. Wang, S. Yang i M. Santha. „Algorytmy kwantowe do zabezpieczania i uczenia modeli isingu”. Fiz. Rev. A 103, 012418 (2021).
https: / / doi.org/ 10.1103 / PhysRevA.103.012418
[14] O. Szamir. „O złożoności liniowej optymalizacji bandytów”. W materiałach z 28. Konferencji Teorii Uczenia się. Tom 40 Proceedings of Machine Learning Research, strony 1523-1551. PMLR (2015).
[15] P. Rusmevichientong i J. Tsitsiklis. „Liniowa parametryzacja bandytów”. Matematyka badań operacyjnych 35 (2008).
https: / / doi.org/ 10.1287 / moor.1100.0446
[16] J. Barry, DT Barry i S. Aaronson. „Kwantowe częściowo obserwowalne procesy decyzyjne Markowa”. Fiz. Rev. A 90, 032311 (2014).
https: / / doi.org/ 10.1103 / PhysRevA.90.032311
[17] M. Ying, Y. Feng i S. Ying. „Optymalna polityka dla procesów decyzyjnych związanych z markowa kwantową”. 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. „Estymacja stanu kwantowego”. Springer Publishing Company, Incorporated. (2010). Wydanie I.
https: / / doi.org/ 10.1007 / b98673
[19] S. Aaronsona. „Tomografia cieni stanów kwantowych”. W materiałach z 50. dorocznego sympozjum ACM SIGACT na temat teorii informatyki. Strona 325–338. STOC 2018. Stowarzyszenie Maszyn Komputerowych (2018).
https: / / doi.org/ 10.1145 / 3188745.3188802
[20] S. Aaronson, X. Chen, E. Hazan, S. Kale i A. Nayak. „Nauka online stanów kwantowych”. Journal of Statistical Mechanics: Theory and Experiment 2019 (2018).
https: / / doi.org/ 10.1088 / 1742-5468 / ab3988
[21] J. Bretagnolle i C. Huber. „Oszacowanie gęstości: ryzykowny minimaks”. 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. „O entropiach kwantowych Rényi: nowe uogólnienie i niektóre właściwości”. Journal of Mathematical Physics 54, 122203 (2013).
https: / / doi.org/ 10.1063 / 1.4838856
[23] M. Wilde, A. Winter i D. Yang. „Mocne conversy dla klasycznej zdolności do łamania splątania i kanałów Hadamarda poprzez wielowarstwową entropię względną Rényi”. Komunikacja w fizyce matematycznej 331, 593-622 (2014).
https: / / doi.org/ 10.1007 / s00220-014-2122-x
[24] W. Hoeffdinga. „Nierówności prawdopodobieństwa dla sum ograniczonych zmiennych losowych”. Journal of the American Statistical Association 58, 13-30 (1963).
https: / / doi.org/ 10.1080 / 01621459.1963.10500830
[25] P. Auera. „Wykorzystywanie granic zaufania do kompromisów między eksploatacją a eksploracją”. J.Mach. Uczyć się. Res. 3, 397–422 (2003).
https: / / doi.org/ 10.5555 / 944919.944941
[26] D. Varsha, T. Hayes i S. Kakade. „Stochastyczna optymalizacja liniowa w warunkach sprzężenia zwrotnego bandytów”. W materiałach XXI Konferencji Teorii Uczenia się. Strony 21–355. (366).
[27] P. Rusmevichientong i JN Tsitsiklis. „Liniowa parametryzacja bandytów”. Matematyka badań operacyjnych 35, 395-411 (2010).
https: / / doi.org/ 10.1287 / moor.1100.0446
[28] Y. Abbasi-Yadkori, D. Pál i Cs. Szepesvári. „Poprawione algorytmy dla liniowych bandytów stochastycznych”. W postępach w neuronowych systemach przetwarzania informacji. Tom 24. Curran Associates, Inc. (2011).
[29] TL Lai. „Adaptacyjna alokacja leczenia i problem wielorękiego bandyty”. Roczniki statystyczne 15, 1091 – 1114 (1987).
https:///doi.org/10.1214/aos/1176350495
[30] M. Guţă, J. Kahn, R. Kueng i JA Tropp. „Tomografia w szybkim stanie z optymalnymi granicami błędów”. Journal of Physics A: Matematyczne i teoretyczne 53, 204001 (2020).
https: / / doi.org/ 10.1088 / 1751-8121 / ab8111
[31] T. Lattimore i B. Hao. „Odzyskiwanie fazy bandytów”. W postępach w neuronowych systemach przetwarzania informacji. Tom 34, strony 18801–18811. Curran Associates, Inc. (2021).
Cytowany przez
[1] Zongqi Wan, Zhijie Zhang, Tongyang Li, Jialin Zhang i Xiaoming Sun, „Kwantowi wieloręcy bandyci i stochastyczni bandyci liniowi cieszą się logarytmicznym żalem”, arXiv: 2205.14988.
[2] Xinyi Chen, Elad Hazan, Tongyang Li, Zhou Lu, Xinzhao Wang i Rui Yang, „Adaptacyjne uczenie się online stanów kwantowych”, arXiv: 2206.00220.
Powyższe cytaty pochodzą z Reklamy SAO / NASA (ostatnia aktualizacja pomyślnie 2022-07-24 00:26:50). Lista może być niekompletna, ponieważ nie wszyscy wydawcy podają odpowiednie i pełne dane cytowania.
On Serwis cytowany przez Crossref nie znaleziono danych na temat cytowania prac (ostatnia próba 2022-07-24 00:26:48).
Niniejszy artykuł opublikowano w Quantum pod Creative Commons Uznanie autorstwa 4.0 Międzynarodowe (CC BY 4.0) licencja. Prawa autorskie należą do pierwotnych właścicieli praw autorskich, takich jak autorzy lub ich instytucje.
