1Κέντρο Κβαντικών Τεχνολογιών, Εθνικό Πανεπιστήμιο της Σιγκαπούρης, Σιγκαπούρη
2Τμήμα Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, Σχολή Μηχανικών, Εθνικό Πανεπιστήμιο της Σιγκαπούρης, Σιγκαπούρη
Βρείτε αυτό το άρθρο ενδιαφέρουσα ή θέλετε να συζητήσετε; Scite ή αφήστε ένα σχόλιο για το SciRate.
Περίληψη
Ξεκινάμε τη μελέτη των ανταλλαγών μεταξύ εξερεύνησης και εκμετάλλευσης στη διαδικτυακή εκμάθηση ιδιοτήτων κβαντικών καταστάσεων. Δεδομένης της διαδοχικής πρόσβασης του μαντείου σε μια άγνωστη κβαντική κατάσταση, σε κάθε γύρο, έχουμε την αποστολή να επιλέξουμε ένα παρατηρήσιμο από ένα σύνολο ενεργειών με στόχο να μεγιστοποιήσουμε την προσδοκώμενη αξία του στην κατάσταση (την ανταμοιβή). Οι πληροφορίες που αποκτήθηκαν για την άγνωστη κατάσταση από προηγούμενους γύρους μπορούν να χρησιμοποιηθούν για τη σταδιακή βελτίωση της επιλογής της δράσης, μειώνοντας έτσι το χάσμα μεταξύ της ανταμοιβής και της μέγιστης ανταμοιβής που μπορεί να επιτευχθεί με το δεδομένο σύνολο ενεργειών (τη λύπη). Παρέχουμε διάφορα κατώτερα όρια θεωρητικών πληροφοριών σχετικά με τη σωρευτική λύπη που πρέπει να έχει ένας βέλτιστος μαθητής και δείχνουμε ότι κλιμακώνεται τουλάχιστον ως η τετραγωνική ρίζα του αριθμού των γύρων που παίχτηκαν. Διερευνούμε επίσης την εξάρτηση της σωρευτικής λύπης από τον αριθμό των διαθέσιμων ενεργειών και τη διάσταση του υποκείμενου χώρου. Επιπλέον, παρουσιάζουμε στρατηγικές που είναι βέλτιστες για ληστές με πεπερασμένο αριθμό βραχιόνων και γενικά μικτές καταστάσεις.
[Ενσωματωμένο περιεχόμενο]
► Δεδομένα BibTeX
► Αναφορές
[1] T. Lattimore και C. Szepesvári. «Ληστικοί αλγόριθμοι». Cambridge University Press. (2020).
https: / / doi.org/ 10.1017 / 9781108571401
[2] Α. Σλίβκινς. «Εισαγωγή στους πολυοπλισμένους ληστές». Θεμέλια και Τάσεις στη Μηχανική Μάθηση 12, 1–286 (2019).
https: / / doi.org/ 10.1561 / 2200000068
[3] S. Bubeck και N. Cesa-Bianchi. «Ανάλυση λύπης στοχαστικών και μη στοχαστικών πολυοπλισμένων προβλημάτων ληστών». Θεμέλια και Τάσεις στη Μηχανική Μάθηση 5, 1–122 (2012).
https: / / doi.org/ 10.1561 / 2200000024
[4] D. Bouneffouf, I. Rish και C. Aggarwal. «Έρευνα σχετικά με τις εφαρμογές πολυοπλισμένων και συμφραζομένων ληστών». Το 2020 IEEE Congress on Evolutionary Computation (CEC). Σελίδες 1–8. (2020).
https://doi.org/10.1109/CEC48606.2020.9185782
[5] L. Tang, R. Rosales, A. Singh, and D. Agarwal. "Αυτόματη επιλογή μορφής διαφήμισης μέσω ληστών με βάση τα συμφραζόμενα". Στα Πρακτικά του 22ου Διεθνούς Συνεδρίου ACM για τη Διαχείριση Πληροφοριών και Γνώσης. Σελίδα 1587–1594. Association for Computing Machinery (2013).
https: / / doi.org/ 10.1145 / 2505515.2514700
[6] M. Cohen, I. Lobel, and R. Paes Leme. «Δυναμική τιμολόγηση βασισμένη σε χαρακτηριστικά». Management Science 66, 4921–4943 (2020).
https://doi.org/ 10.1287/mnsc.2019.3485
[7] W. Thompson. «Στην πιθανότητα μια άγνωστη πιθανότητα να υπερβαίνει την άλλη εν όψει της απόδειξης δύο δειγμάτων». Biometrika 25, 285–294 (1933).
https://doi.org/10.1093/biomet/25.3-4.285
[8] Χ. Ρόμπινς. «Μερικές πτυχές του διαδοχικού σχεδιασμού των πειραμάτων». Bulletin of the American Mathematical Society 58, 527–535 (1952).
https://doi.org/10.1090/S0002-9904-1952-09620-8
[9] TL Lai και H. Robbins. «Ασυμπτωτικά αποτελεσματικοί προσαρμοστικοί κανόνες κατανομής». Advances in Applied Mathematics 6, 4–22 (1985).
https://doi.org/10.1016/0196-8858(85)90002-8
[10] P. Auer, N. Cesa-Bianchi και P. Fischer. «Ανάλυση πεπερασμένου χρόνου του προβλήματος των πολυοπλισμένων ληστών». Mach. Μαθαίνω. 47, 235–256 (2002).
https: / / doi.org/ 10.1023 / Α: 1013689704352
[11] B. Casalé, G. Di Molfetta, H. Kadri, και L. Ralaivola. «Κβαντικοί ληστές». Κβαντικό Μαχ. Intell. 2 (2020).
https://doi.org/10.1007/s42484-020-00024-8
[12] D. Wang, X. You, T. Li και A. Childs. «Κβαντικοί αλγόριθμοι εξερεύνησης για ληστές πολλαπλών όπλων». Στα Πρακτικά του Συνεδρίου AAAI για την Τεχνητή Νοημοσύνη. Τόμος 35, σελίδες 10102–10110. (2021).
[13] P. Rebentrost, Y. Hamoudi, M. Ray, X. Wang, S. Yang, and M. Santha. «Κβαντικοί αλγόριθμοι για αντιστάθμιση και εκμάθηση μοντέλων». Phys. Αναθ. Α 103, 012418 (2021).
https: / / doi.org/ 10.1103 / PhysRevA.103.012418
[14] Ο. Σαμίρ. «Σχετικά με την πολυπλοκότητα της ληστρικής γραμμικής βελτιστοποίησης». Στα Πρακτικά του 28ου Συνεδρίου για τη Θεωρία της Μάθησης. Τόμος 40 του Proceedings of Machine Learning Research, σελίδες 1523–1551. PMLR (2015).
[15] P. Rusmevichientong και Ι. Τσιτσικλής. «Γραμμικά παραμετροποιημένοι ληστές». Μαθηματικά Επιχειρησιακής Έρευνας 35 (2008).
https: / / doi.org/ 10.1287 / moor.1100.0446
[16] J. Barry, DT Barry και S. Aaronson. «Κβαντικές μερικώς παρατηρήσιμες διαδικασίες απόφασης Markov». Phys. Α' 90, 032311 (2014).
https: / / doi.org/ 10.1103 / PhysRevA.90.032311
[17] M. Ying, Y. Feng και S. Ying. «Βέλτιστες πολιτικές για διαδικασίες κβαντικών μαρκοβικών αποφάσεων». International Journal of Automation and Computing 18, 410–421 (2021).
https: / / doi.org/ 10.1007 / s11633-021-1278-z
[18] M. Paris και J. Rehacek. «Εκτίμηση κβαντικής κατάστασης». Springer Publishing Company, Incorporated. (2010). 1η έκδοση.
https: / / doi.org/ 10.1007 / b98673
[19] S. Aaronson. «Σιιακή τομογραφία κβαντικών καταστάσεων». In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. Σελίδα 325–338. STOC 2018. Association for Computing Machinery (2018).
https: / / doi.org/ 10.1145 / 3188745.3188802
[20] S. Aaronson, X. Chen, E. Hazan, S. Kale και Α. Nayak. «Διαδικτυακή εκμάθηση κβαντικών καταστάσεων». Journal of Statistical Mechanics: Theory and Experiment 2019 (2018).
https: / / doi.org/ 10.1088 / 1742-5468 / ab3988
[21] J. Bretagnolle και 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, and M. Tomamichel. «Στις κβαντικές εντροπίες Rényi: Μια νέα γενίκευση και μερικές ιδιότητες». Journal of Mathematical Physics 54, 122203 (2013).
https: / / doi.org/ 10.1063 / 1.4838856
[23] M. Wilde, A. Winter και D. Yang. «Ισχυρή συνομιλία για την κλασική ικανότητα των καναλιών διαπλοκής και Hadamard μέσω μιας σχετικής εντροπίας Rényi Sandwiched». Communications in Mathematical Physics 331, 593–622 (2014).
https: / / doi.org/ 10.1007 / s00220-014-2122-x
[24] W. Hoeffding. «Ανισώσεις πιθανοτήτων για αθροίσματα περιορισμένων τυχαίων μεταβλητών». Journal of the American Statistical Association 58, 13–30 (1963).
https: / / doi.org/ 10.1080 / 01621459.1963.10500830
[25] P. Auer. «Χρήση ορίων εμπιστοσύνης για συμβιβασμούς εκμετάλλευσης-εξερεύνησης». J. Mach. Μαθαίνω. Res. 3, 397–422 (2003).
https: / / doi.org/ 10.5555 / 944919.944941
[26] D. Varsha, T. Hayes και S.Kakade. "Στοχαστική γραμμική βελτιστοποίηση υπό ληστική ανάδραση." Στα Πρακτικά του 21ου Συνεδρίου Θεωρίας Μάθησης. Σελίδες 355–366. (2008).
[27] P. Rusmevichientong και Ι. Ν. Τσιτσικλής. «Γραμμικά παραμετροποιημένοι ληστές». Mathematics of Operations Research 35, 395–411 (2010).
https: / / doi.org/ 10.1287 / moor.1100.0446
[28] Y. Abbasi-Yadkori, D. Pál και Cs. Szepesvári. «Βελτιωμένοι αλγόριθμοι για γραμμικούς στοχαστικούς ληστές». In Advances in Neural Information Processing Systems. Τόμος 24. Curran Associates, Inc. (2011).
[29] TL Lai. «Προσαρμοστική κατανομή θεραπείας και πρόβλημα ληστών πολλαπλών όπλων». The Annals of Statistics 15, 1091 – 1114 (1987).
https://doi.org/10.1214/aos/1176350495
[30] M. Guţă, J. Kahn, R. Kueng και JA Tropp. «Ταμογραφία γρήγορης κατάστασης με βέλτιστα όρια σφάλματος». Journal of Physics A: Mathematical and Theoretical 53, 204001 (2020).
https: / / doi.org/ 10.1088 / 1751-8121 / ab8111
[31] T. Lattimore και B. Hao. «Ανάκτηση φάσης ληστών». In Advances in Neural Information Processing Systems. Τόμος 34, σελίδες 18801–18811. Curran Associates, Inc. (2021).
Αναφέρεται από
[1] Zongqi Wan, Zhijie Zhang, Tongyang Li, Jialin Zhang και 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 και Rui Yang, "Adaptive Online Learning of Quantum State", arXiv: 2206.00220.
Οι παραπάνω αναφορές είναι από SAO / NASA ADS (τελευταία ενημέρωση επιτυχώς 2022-07-24 00:26:50). Η λίστα μπορεί να είναι ελλιπής, καθώς δεν παρέχουν όλοι οι εκδότες τα κατάλληλα και πλήρη στοιχεία αναφοράς.
On Η υπηρεσία παραπομπής του Crossref δεν βρέθηκαν δεδομένα σχετικά με την αναφορά έργων (τελευταία προσπάθεια 2022-07-24 00:26:48).
Αυτό το Βιβλίο δημοσιεύεται στο Quantum στο πλαίσιο του Creative Commons Attribution 4.0 Διεθνής (CC BY 4.0) άδεια. Τα πνευματικά δικαιώματα παραμένουν στους κατόχους των πρωτότυπων δικαιωμάτων πνευματικής ιδιοκτησίας όπως οι δημιουργοί ή τα ιδρύματά τους
