1Center for Quantum Technologies, National University of Singapore, Singapore
2Dipartimento di Ingegneria Elettrica e Informatica, Facoltà di Ingegneria, Università Nazionale di Singapore, Singapore
Trovi questo documento interessante o vuoi discuterne? Scrivi o lascia un commento su SciRate.
Astratto
Iniziamo lo studio dei compromessi tra esplorazione e sfruttamento nell'apprendimento online delle proprietà degli stati quantistici. Dato l'accesso sequenziale dell'oracolo a uno stato quantistico sconosciuto, in ogni round, ci viene chiesto di scegliere un osservabile da un insieme di azioni che mirano a massimizzare il suo valore atteso sullo stato (la ricompensa). Le informazioni acquisite sullo stato sconosciuto dai round precedenti possono essere utilizzate per migliorare gradualmente la scelta dell'azione, riducendo così il divario tra la ricompensa e la ricompensa massima ottenibile con la serie di azioni data (il rimpianto). Forniamo vari limiti inferiori di teoria dell'informazione sul rimpianto cumulativo che deve incorrere in uno studente ottimale e mostriamo che scala almeno come radice quadrata del numero di round giocati. Indaghiamo anche la dipendenza del rimpianto cumulativo dal numero di azioni disponibili e dalla dimensione dello spazio sottostante. Inoltre, mostriamo strategie ottimali per i banditi con un numero finito di armi e stati misti generali.
[Contenuto incorporato]
► dati BibTeX
► Riferimenti
, T. Lattimore e C. Szepesvári. "Algoritmi dei banditi". Cambridge University Press. (2020).
https: / / doi.org/ 10.1017 / 9781108571401 mila
, A. Slivkins. "Introduzione ai banditi multi-armati". Fondamenti e tendenze nell'apprendimento automatico 12, 1–286 (2019).
https: / / doi.org/ 10.1561 / 2200000068 mila
, S. Bubeck e N. Cesa-Bianchi. "Analisi del rimpianto dei problemi stocastici e non stocastici dei banditi multi-armati". Fondamenti e tendenze nell'apprendimento automatico 5, 1–122 (2012).
https: / / doi.org/ 10.1561 / 2200000024 mila
, D. Bouneffouf, I. Rish e C. Aggarwal. “Indagine sulle applicazioni dei banditi multi-armati e contestuali”. Nel 2020 IEEE Congress on Evolutionary Computation (CEC). Pagine 1–8. (2020).
https:///doi.org/10.1109/CEC48606.2020.9185782
, L. Tang, R. Rosales, A. Singh e D. Agarwal. "Selezione automatica del formato dell'annuncio tramite banditi contestuali". In Atti della 22a Conferenza Internazionale ACM sull'Informazione e la Gestione della Conoscenza. Pagina 1587–1594. Associazione per le macchine informatiche (2013).
https: / / doi.org/ 10.1145 / 2505515.2514700 mila
, M. Cohen, I. Lobel e R. Paes Leme. "Prezzi dinamici basati sulle funzionalità". Scienze gestionali 66, 4921–4943 (2020).
https: / / doi.org/ 10.1287 / mnsc.2019.3485
, W. Thompson. “Sulla probabilità che una probabilità sconosciuta superi un'altra data l'evidenza di due campioni”. Biometrika 25, 285–294 (1933).
https:///doi.org/10.1093/biomet/25.3-4.285
, H. Robbins. "Alcuni aspetti della progettazione sequenziale degli esperimenti". Bollettino dell'American Mathematical Society 58, 527–535 (1952).
https://doi.org/10.1090/S0002-9904-1952-09620-8
, TL Lai e H. Robbins. "Regole di allocazione adattiva asintoticamente efficienti". Progressi nella matematica applicata 6, 4–22 (1985).
https://doi.org/10.1016/0196-8858(85)90002-8
, P. Auer, N. Cesa-Bianchi e P. Fischer. “Analisi a tempo finito del problema dei banditi multiarmati”. Mach. Imparare. 47, 235–256 (2002).
https: / / doi.org/ 10.1023 / A: 1013689704352 millions
, B. Casalé, G. Di Molfetta, H. Kadri, , e L. Ralaivola. "Banditi quantistici". Quantum Mach. Intel. 2 (2020).
https://doi.org/10.1007/s42484-020-00024-8
, D. Wang, X. You, T. Li e A. Childs. "Algoritmi di esplorazione quantistica per banditi multi-armati". In Atti del Convegno AAAI sull'Intelligenza Artificiale. Volume 35, pagine 10102–10110. (2021).
, P. Rebentrost, Y. Hamoudi, M. Ray, X. Wang, S. Yang e M. Santha. “Algoritmi quantistici per la copertura e l'apprendimento di modelli di ising”. Phys. Rev. A 103, 012418 (2021).
https: / / doi.org/ 10.1103 / PhysRevA.103.012418
, O. Shamir. "Sulla complessità dell'ottimizzazione lineare dei banditi". In Atti della 28a conferenza sulla teoria dell'apprendimento. Volume 40 di Atti della ricerca sull'apprendimento automatico, pagine 1523–1551. PMLR (2015).
, P. Rusmevichientong e J. Tsitsiklis. "Banditi parametrizzati linearmente". Matematica della ricerca operativa 35 (2008).
https: / / doi.org/ 10.1287 / moor.1100.0446
, J. Barry, DT Barry e S. Aaronson. "Processi decisionali markov parzialmente osservabili quantistici". Phys. Rev. A 90, 032311 (2014).
https: / / doi.org/ 10.1103 / PhysRevA.90.032311
, M. Ying, Y. Feng e S. Ying. "Politiche ottimali per i processi decisionali di markov quantistico". International Journal of Automation and Computing 18, 410–421 (2021).
https: / / doi.org/ 10.1007 / s11633-021-1278-z
, M. Paris e J. Rehacek. "Stima quantistica dello stato". Springer Publishing Company, Incorporated. (2010). 1a edizione.
https: / / doi.org/ 10.1007 / b98673
, S. Aaronson. "Tomografia ombra degli stati quantistici". In Atti del 50° Simposio annuale ACM SIGACT sulla teoria dell'informatica. Pagina 325–338. STOC 2018. Associazione per le macchine informatiche (2018).
https: / / doi.org/ 10.1145 / 3188745.3188802 mila
, S. Aaronson, X. Chen, E. Hazan, S. Kale e A. Nayak. "Apprendimento online degli stati quantistici". Journal of Statistical Mechanics: Theory and Experiment 2019 (2018).
https: / / doi.org/ 10.1088 / 1742-5468 / ab3988
, J. Bretagnolle e C. Huber. "Estimation des densités: osé minimax". Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete 47, 119–137 (1979).
https: / / doi.org/ 10.1007 / BF00535278
, M. Müller-Lennert, F. Dupuis, O. Szehr, S. Fehr e M. Tomamichel. "Sulle entropie quantistiche di Rényi: una nuova generalizzazione e alcune proprietà". Giornale di fisica matematica 54, 122203 (2013).
https: / / doi.org/ 10.1063 / 1.4838856 mila
, M. Wilde, A. Winter e D. Yang. "Converse forti per la capacità classica di rompere l'entanglement e i canali Hadamard tramite un'entropia relativa di Rényi sandwich". Comunicazioni in fisica matematica 331, 593–622 (2014).
https: / / doi.org/ 10.1007 / s00220-014-2122-x
, W. Hoeffding. "Disequazioni di probabilità per somme di variabili aleatorie limitate". Journal of American Statistical Association 58, 13–30 (1963).
https: / / doi.org/ 10.1080 / 01621459.1963.10500830 mila
, P. Auer. "Utilizzare i limiti di fiducia per i compromessi sfruttamento-esplorazione". J. Mach. Imparare. ris. 3, 397–422 (2003).
https: / / doi.org/ 10.5555 / 944919.944941 mila
, D. Varsha, T. Hayes e S. Kakade. "Ottimizzazione lineare stocastica sotto feedback bandito.". In Atti del 21° Convegno sulla Teoria dell'Apprendimento. Pagine 355–366. (2008).
, P. Rusmevichientong e JN Tsitsiklis. "Banditi parametrizzati linearmente". Matematica della ricerca operativa 35, 395–411 (2010).
https: / / doi.org/ 10.1287 / moor.1100.0446
, Y. Abbasi-Yadkori, D. Pál e Cs. Szepesvari. "Algoritmi migliorati per banditi stocastici lineari". In progressi nei sistemi di elaborazione delle informazioni neurali. Volume 24. Curran Associates, Inc. (2011).
, TL Lai. "Assegnazione del trattamento adattivo e problema del bandito multi-armato". Gli annali della statistica 15, 1091-1114 (1987).
https: / / doi.org/ 10.1214 / AOS / 1176350495 mila
, M. Guţă, J. Kahn, R. Kueng e JA Tropp. "Tomografia a stato veloce con limiti di errore ottimali". Journal of Physics A: Mathematical and Theoretical 53, 204001 (2020).
https: / / doi.org/ 10.1088 / 1751-8121 / ab8111
, T. Lattimore e B. Hao. "Recupero della fase dei banditi". In progressi nei sistemi di elaborazione delle informazioni neurali. Volume 34, pagine 18801–18811. Curran Associates, Inc. (2021).
Citato da
[1] Zongqi Wan, Zhijie Zhang, Tongyang Li, Jialin Zhang e Xiaoming Sun, "I banditi quantistici multi-armati e i banditi lineari stocastici godono di rimpianti logaritmici", arXiv: 2205.14988.
[2] Xinyi Chen, Elad Hazan, Tongyang Li, Zhou Lu, Xinzhao Wang e Rui Yang, "Apprendimento adattivo online degli stati quantistici", arXiv: 2206.00220.
Le citazioni sopra sono di ANNUNCI SAO / NASA (ultimo aggiornamento riuscito 2022-07-24 00:26:50). L'elenco potrebbe essere incompleto poiché non tutti gli editori forniscono dati di citazione adeguati e completi.
On Il servizio citato da Crossref non sono stati trovati dati su citazioni (ultimo tentativo 2022-07-24 00:26:48).
Questo documento è pubblicato in Quantum sotto il Creative Commons Attribuzione 4.0 Internazionale (CC BY 4.0) licenza. Il copyright rimane dei detentori del copyright originali come gli autori o le loro istituzioni.
