1Centre for Quantum Technologies, Université nationale de Singapour, Singapour
2Département de génie électrique et informatique, Faculté de génie, Université nationale de Singapour, Singapour
Vous trouvez cet article intéressant ou souhaitez en discuter? Scite ou laisse un commentaire sur SciRate.
Abstract
Nous initions l'étude des compromis entre exploration et exploitation dans l'apprentissage en ligne des propriétés des états quantiques. Étant donné l'accès oracle séquentiel à un état quantique inconnu, à chaque tour, nous sommes chargés de choisir un observable parmi un ensemble d'actions visant à maximiser sa valeur d'espérance sur l'état (la récompense). Les informations obtenues sur l'état inconnu des tours précédents peuvent être utilisées pour améliorer progressivement le choix d'action, réduisant ainsi l'écart entre la récompense et la récompense maximale pouvant être atteinte avec l'ensemble d'actions donné (le regret). Nous fournissons diverses bornes inférieures théoriques de l'information sur le regret cumulatif qu'un apprenant optimal doit encourir, et montrons qu'il évolue au moins comme la racine carrée du nombre de tours joués. Nous étudions également la dépendance du regret cumulatif sur le nombre d'actions disponibles et la dimension de l'espace sous-jacent. De plus, nous exposons des stratégies optimales pour les bandits avec un nombre fini d'armes et des états mixtes généraux.
[Contenu intégré]
► Données BibTeX
► Références
T. Lattimore et C. Szepesvári. "Algorithmes bandits". La presse de l'Universite de Cambridge. (2020).
https: / / doi.org/ 10.1017 / 9781108571401
A.Slivkins. "Introduction aux bandits multi-armés". Fondements et tendances de l'apprentissage automatique 12, 1–286 (2019).
https: / / doi.org/ 10.1561 / 2200000068
S. Bubeck et N. Cesa-Bianchi. "Analyse des regrets des problèmes de bandits multi-armés stochastiques et non stochastiques". Fondements et tendances de l'apprentissage automatique 5, 1–122 (2012).
https: / / doi.org/ 10.1561 / 2200000024
D. Bouneffouf, I. Rish et C. Aggarwal. « Enquête sur les applications des bandits multi-armés et contextuels ». En 2020 Congrès IEEE sur le calcul évolutif (CEC). Pages 1 à 8. (2020).
https:///doi.org/10.1109/CEC48606.2020.9185782
L. Tang, R. Rosales, A. Singh et D. Agarwal. "Sélection automatique du format d'annonce via des bandits contextuels". Dans Actes de la 22e Conférence internationale de l'ACM sur la gestion de l'information et des connaissances. Pages 1587–1594. Association pour les machines informatiques (2013).
https: / / doi.org/ 10.1145 / 2505515.2514700
M. Cohen, I. Lobel et R. Paes Leme. "Tarification dynamique basée sur les fonctionnalités". Sciences de gestion 66, 4921–4943 (2020).
https: / / doi.org/ 10.1287 / mnsc.2019.3485
W.Thompson. "Sur la probabilité qu'une probabilité inconnue dépasse une autre compte tenu de la preuve de deux échantillons". Biometrika 25, 285–294 (1933).
https:///doi.org/10.1093/biomet/25.3-4.285
H. Robbins. "Certains aspects de la conception séquentielle d'expériences". Bulletin de l'American Mathematical Society 58, 527–535 (1952).
https://doi.org/10.1090/S0002-9904-1952-09620-8
TL Lai et H. Robbins. "Règles d'allocation adaptative asymptotiquement efficaces". Avancées en mathématiques appliquées 6, 4–22 (1985).
https://doi.org/10.1016/0196-8858(85)90002-8
P. Auer, N. Cesa-Bianchi et P. Fischer. "Analyse en temps fini du problème du bandit multi-armé". Mach. Apprendre. 47, 235-256 (2002).
https: / / doi.org/ 10.1023 / A: 1013689704352
B. Casalé, G. Di Molfetta, H. Kadri, , and L. Ralaivola. "Bandits quantiques". Mach quantique. Renseignement. 2 (2020).
https://doi.org/10.1007/s42484-020-00024-8
D. Wang, X. You, T. Li et A. Childs. "Algorithmes d'exploration quantique pour bandits multi-armés". Dans Actes de la conférence AAAI sur l'intelligence artificielle. Tome 35, pages 10102–10110. (2021).
P. Rebentrost, Y. Hamoudi, M. Ray, X. Wang, S. Yang et M. Santha. « Algorithmes quantiques pour le hedging et l'apprentissage des modèles d'ising ». Phys. Rév. A 103, 012418 (2021).
https: / / doi.org/ 10.1103 / PhysRevA.103.012418
O.Shamir. "Sur la complexité de l'optimisation linéaire des bandits". Dans Actes de la 28e Conférence sur la théorie de l'apprentissage. Volume 40 des Actes de recherche sur l'apprentissage automatique, pages 1523–1551. PMLR (2015).
P. Rusmevichientong et J. Tsitsiklis. "Bandits linéairement paramétrés". Mathématiques de la recherche opérationnelle 35 (2008).
https: / / doi.org/ 10.1287 / moor.1100.0446
J. Barry, DT Barry et S. Aaronson. "Processus décisionnels de Markov quantiques partiellement observables". Phys. Rév. A 90, 032311 (2014).
https: / / doi.org/ 10.1103 / PhysRevA.90.032311
M. Ying, Y. Feng et S. Ying. "Politiques optimales pour les processus de décision de markov quantique". Journal international d'automatisation et d'informatique 18, 410–421 (2021).
https: / / doi.org/ 10.1007 / s11633-021-1278-z
M. Paris et J. Rehacek. "Estimation de l'état quantique". Société d'édition Springer, incorporée. (2010). 1ère édition.
https: / / doi.org/ 10.1007 / b98673
S. Aaronson. "Tomographie d'ombre des états quantiques". Dans Actes du 50e symposium annuel ACM SIGACT sur la théorie de l'informatique. Pages 325–338. STOC 2018. Association pour les machines informatiques (2018).
https: / / doi.org/ 10.1145 / 3188745.3188802
S. Aaronson, X. Chen, E. Hazan, S. Kale et A. Nayak. "Apprentissage en ligne des états quantiques". Journal of Statistical Mechanics: Théorie et expérience 2019 (2018).
https: / / doi.org/ 10.1088 / 1742-5468 / ab3988
J. Bretagnolle et 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
M. Müller-Lennert, F. Dupuis, O. Szehr, S. Fehr et M. Tomamichel. « Sur les entropies quantiques de Rényi : une nouvelle généralisation et quelques propriétés ». Journal de physique mathématique 54, 122203 (2013).
https: / / doi.org/ 10.1063 / 1.4838856
M. Wilde, A. Winter et D. Yang. "Converse forte pour la capacité classique de rupture d'enchevêtrement et de canaux Hadamard via une entropie relative de Rényi en sandwich". Communications en physique mathématique 331, 593–622 (2014).
https: / / doi.org/ 10.1007 / s00220-014-2122-x
W. Hoeffding. « Inégalités de probabilité pour des sommes de variables aléatoires bornées ». Journal de l'Association statistique américaine 58, 13–30 (1963).
https: / / doi.org/ 10.1080 / 01621459.1963.10500830
P.Auer. "Utiliser des limites de confiance pour les compromis exploitation-exploration". J.Mach. Apprendre. Rés. 3, 397–422 (2003).
https: / / doi.org/ 10.5555 / 944919.944941
D. Varsha, T. Hayes et S.Kakade. "Optimisation linéaire stochastique sous rétroaction de bandit.". Dans Actes de la 21e Conférence sur la théorie de l'apprentissage. Pages 355–366. (2008).
P. Rusmevichientong et JN Tsitsiklis. "Bandits linéairement paramétrés". Mathématiques de la recherche opérationnelle 35, 395–411 (2010).
https: / / doi.org/ 10.1287 / moor.1100.0446
Y. Abbasi-Yadkori, D. Pál et Cs. Szepesvari. "Algorithmes améliorés pour les bandits stochastiques linéaires". Dans les progrès des systèmes de traitement de l'information neuronale. Volume 24. Curran Associates, Inc. (2011).
TL Lai. "Allocation de traitement adaptative et problème de bandit multi-armé". Les Annals of Statistics 15, 1091 - 1114 (1987).
https: / / doi.org/ 10.1214 / aos / 1176350495
M. Guţă, J. Kahn, R. Kueng et JA Tropp. "Tomographie d'état rapide avec des limites d'erreur optimales". Journal of Physics A: Mathematical and Theoretical 53, 204001 (2020).
https: / / doi.org/ 10.1088 / 1751-8121 / ab8111
T. Lattimore et B. Hao. "Récupération de phase de bandit". Dans les progrès des systèmes de traitement de l'information neuronale. Tome 34, pages 18801–18811. Curran Associates, Inc. (2021).
Cité par
[1] Zongqi Wan, Zhijie Zhang, Tongyang Li, Jialin Zhang et 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 et Rui Yang, "Apprentissage en ligne adaptatif des états quantiques", arXiv: 2206.00220.
Les citations ci-dessus proviennent de SAO / NASA ADS (dernière mise à jour réussie 2022-07-24 00:26:50). La liste peut être incomplète car tous les éditeurs ne fournissent pas de données de citation appropriées et complètes.
On Le service cité par Crossref aucune donnée sur la citation des œuvres n'a été trouvée (dernière tentative 2022-07-24 00:26:48).
Cet article est publié dans Quantum sous le Creative Commons Attribution 4.0 International (CC BY 4.0) Licence. Le droit d'auteur reste la propriété des détenteurs d'origine tels que les auteurs ou leurs institutions.
