1Pusat Teknologi Kuantum, Universitas Nasional Singapura, Singapura
2Jurusan Teknik Elektro dan Komputer, Fakultas Teknik, National University of Singapore, Singapura
Apakah makalah ini menarik atau ingin dibahas? Scite atau tinggalkan komentar di SciRate.
Abstrak
Kami memulai studi pertukaran antara eksplorasi dan eksploitasi dalam pembelajaran online tentang properti keadaan kuantum. Diberi akses oracle berurutan ke keadaan kuantum yang tidak diketahui, di setiap putaran, kami ditugaskan untuk memilih yang dapat diamati dari serangkaian tindakan yang bertujuan untuk memaksimalkan nilai harapannya pada keadaan (hadiah). Informasi yang diperoleh tentang keadaan yang tidak diketahui dari putaran sebelumnya dapat digunakan untuk meningkatkan pilihan tindakan secara bertahap, sehingga mengurangi kesenjangan antara hadiah dan hadiah maksimal yang dapat dicapai dengan rangkaian tindakan yang diberikan (penyesalan). Kami memberikan berbagai informasi-teoretis batas bawah pada penyesalan kumulatif yang harus dikeluarkan oleh pembelajar yang optimal, dan menunjukkan bahwa itu berskala setidaknya sebagai akar kuadrat dari jumlah putaran yang dimainkan. Kami juga menyelidiki ketergantungan penyesalan kumulatif pada jumlah tindakan yang tersedia dan dimensi ruang yang mendasarinya. Selain itu, kami menunjukkan strategi yang optimal untuk bandit dengan jumlah senjata terbatas dan keadaan campuran umum.
[Embedded content]
โบ data BibTeX
โบ Referensi
[1] T. Lattimore dan C. Szepesvรกri. "Algoritma bandit". Pers Universitas Cambridge. (2020).
https: / / doi.org/ 10.1017 / 9781108571401
[2] A.Slivkins. "Pengantar bandit multi-bersenjata". Dasar dan Tren dalam Pembelajaran Mesin 12, 1โ286 (2019).
https: / / doi.org/ 10.1561 / 2200000068
[3] S. Bubeck dan N. Cesa-Bianchi. "Analisis penyesalan masalah bandit multi-bersenjata stokastik dan nonstokastik". Dasar dan Tren dalam Pembelajaran Mesin 5, 1โ122 (2012).
https: / / doi.org/ 10.1561 / 2200000024
[4] D. Bouneffouf, I. Rish, dan C. Aggarwal. "Survei tentang aplikasi bandit multi-bersenjata dan kontekstual". Pada Kongres IEEE 2020 tentang Komputasi Evolusioner (CEC). Halaman 1โ8. (2020).
https://โ/โdoi.org/โ10.1109/โCEC48606.2020.9185782
[5] L. Tang, R. Rosales, A. Singh, dan D. Agarwal. โPemilihan format iklan otomatis melalui bandit kontekstualโ. Dalam Prosiding Konferensi Internasional ACM ke-22 tentang Manajemen Informasi dan Pengetahuan. Halaman 1587โ1594. Asosiasi Mesin Komputasi (2013).
https: / / doi.org/ 10.1145 / 2505515.2514700
[6] M. Cohen, I. Lobel, dan R. Paes Leme. โHarga dinamis berbasis fiturโ. Ilmu Manajemen 66, 4921โ4943 (2020).
https: / / doi.org/ 10.1287 / mnsc.2019.3485
[7] W. Thompson. "Pada kemungkinan bahwa satu probabilitas yang tidak diketahui melebihi yang lain mengingat bukti dari dua sampel". Biometrika 25, 285โ294 (1933).
https://โ/โdoi.org/โ10.1093/โbiomet/โ25.3-4.285
[8] H. Robbins. "Beberapa Aspek Desain Eksperimen Berurutan". Buletin Masyarakat Matematika Amerika 58, 527โ535 (1952).
https:/โ/โdoi.org/โ10.1090/โS0002-9904-1952-09620-8
[9] TL Lai dan H. Robbins. "Aturan alokasi adaptif yang efisien secara asimptotik". Kemajuan dalam Matematika Terapan 6, 4โ22 (1985).
https:/โ/โdoi.org/โ10.1016/โ0196-8858(85)90002-8
[10] P. Auer, N. Cesa-Bianchi, dan P. Fischer. "Analisis waktu terbatas dari masalah multiarmed bandit". Mesin Mempelajari. 47, 235โ256 (2002).
https: / / doi.org/ 10.1023 / A: 1013689704352
[11] B. Casalรฉ, G. Di Molfetta, H. Kadri, , and L. Ralaivola. "Bandit kuantum". mesin kuantum Intell. 2 (2020).
https:/โ/โdoi.org/โ10.1007/โs42484-020-00024-8
[12] D. Wang, X. You, T. Li, and A. Childs. "Algoritma eksplorasi kuantum untuk bandit multi-bersenjata". Dalam Prosiding Konferensi AAAI tentang Kecerdasan Buatan. Volume 35, halaman 10102โ10110. (2021).
[13] P. Rebentrost, Y. Hamoudi, M. Ray, X. Wang, S. Yang, dan M. Santha. "Algoritme kuantum untuk lindung nilai dan pembelajaran model ising". Fisika. Pdt. A 103, 012418 (2021).
https: / / doi.org/ 10.1103 / PhysRevA.103.012418
[14] O. Shamir. "Tentang kompleksitas pengoptimalan linier bandit". Dalam Prosiding Konferensi ke-28 tentang Teori Pembelajaran. Volume 40 Prosiding Penelitian Pembelajaran Mesin, halaman 1523โ1551. PMLR (2015).
[15] P. Rusmevichientong dan J. Tsitsiklis. "Bandit berparameter linier". Matematika Riset Operasi 35 (2008).
https: / / doi.org/ 10.1287 / moor.1100.0446
[16] J. Barry, DT Barry, dan S. Aaronson. "Proses keputusan markov kuantum yang dapat diamati sebagian". Fisika. Pdt. A 90, 032311 (2014).
https: / / doi.org/ 10.1103 / PhysRevA.90.032311
[17] M. Ying, Y. Feng, and S. Ying. "Kebijakan optimal untuk proses keputusan markov kuantum". Jurnal Internasional Otomasi dan Komputasi 18, 410โ421 (2021).
https: / / doi.org/ 10.1007 / s11633-021-1278-z
[18] M.Paris dan J.Rehacek. "Estimasi keadaan kuantum". Perusahaan Penerbitan Springer, Dimasukkan. (2010). edisi pertama.
https: / / doi.org/ 10.1007 / b98673
[19] S. Aaronson. "Tomografi bayangan keadaan kuantum". Dalam Prosiding Simposium SIGACT ACM Tahunan ke-50 tentang Teori Komputasi. Halaman 325โ338. STOC 2018. Asosiasi Mesin Komputasi (2018).
https: / / doi.org/ 10.1145 / 3188745.3188802
[20] S. Aaronson, X. Chen, E. Hazan, S. Kale, and A. Nayak. "Pembelajaran online tentang keadaan kuantum". Jurnal Mekanika Statistik: Teori dan Eksperimen 2019 (2018).
https: / / doi.org/ 10.1088 / 1742-5468 / ab3988
[21] J. Bretagnolle dan C. Huber. "Estimasi kepadatan: minimax yang bersifat cabul". 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, dan M. Tomamichel. "Pada Entropi Quantum Rรฉnyi: Generalisasi Baru dan Beberapa Properti". Jurnal Fisika Matematika 54, 122203 (2013).
https: / / doi.org/ 10.1063 / 1.4838856
[23] M. Wilde, A. Musim Dingin, dan D. Yang. "Kebalikan Kuat untuk Kapasitas Klasik Pemutus Keterikatan dan Saluran Hadamard melalui Entropi Relatif Rรฉnyi Terjepit". Komunikasi dalam Fisika Matematika 331, 593โ622 (2014).
https: / / doi.org/ 10.1007 / s00220-014-2122-x
[24] W. Hoeffding. "Pertidaksamaan probabilitas untuk jumlah variabel acak terikat". Jurnal Asosiasi Statistik Amerika 58, 13โ30 (1963).
https: / / doi.org/ 10.1080 / 01621459.1963.10500830
[25] P.Auer. โMenggunakan batas kepercayaan untuk pertukaran eksploitasi-eksplorasiโ. J.Mach. Mempelajari. Res. 3, 397โ422 (2003).
https: / / doi.org/ 10.5555 / 944919.944941
[26] D. Varsha, T. Hayes, dan S.Kakade. "Optimasi linier stokastik di bawah umpan balik bandit.". Dalam Prosiding Konferensi ke-21 tentang Teori Pembelajaran. Halaman 355โ366. (2008).
[27] P. Rusmevichientong dan JN Tsitsiklis. "Bandit berparameter linier". Matematika Riset Operasi 35, 395โ411 (2010).
https: / / doi.org/ 10.1287 / moor.1100.0446
[28] Y. Abbasi-Yadkori, D. Pรกl, dan Cs. Szepesvรกri. "Algoritme yang ditingkatkan untuk bandit stokastik linier". Dalam Kemajuan dalam Sistem Pemrosesan Informasi Neural. Volume 24. Curran Associates, Inc. (2011).
[29] TL Lai. "Alokasi Perawatan Adaptif dan Masalah Multi-Armed Bandit". Sejarah Statistik 15, 1091 โ 1114 (1987).
https: / / doi.org/ 10.1214 / aos / 1176350495
[30] M. Guลฃฤ, J. Kahn, R. Kueng, dan JA Tropp. "Tomografi keadaan cepat dengan batas kesalahan optimal". Jurnal Fisika A: Matematika dan Teoritis 53, 204001 (2020).
https: / / doi.org/ 10.1088 / 1751-8121 / ab8111
[31] T. Lattimore dan B. Hao. "Pengambilan fase bandit". Dalam Kemajuan dalam Sistem Pemrosesan Informasi Neural. Volume 34, halaman 18801โ18811. Curran Associates, Inc. (2021).
Dikutip oleh
[1] Zongqi Wan, Zhijie Zhang, Tongyang Li, Jialin Zhang, dan Xiaoming Sun, โBandit Multi-Bersenjata Kuantum dan Bandit Linear Stokastik Menikmati Penyesalan Logaritmikโ, arXiv: 2205.14988.
[2] Xinyi Chen, Elad Hazan, Tongyang Li, Zhou Lu, Xinzhao Wang, dan Rui Yang, โPembelajaran Online Adaptif Negara Kuantumโ, arXiv: 2206.00220.
Kutipan di atas berasal dari SAO / NASA ADS (terakhir berhasil diperbarui, 2022-07-24 00:26:50). Daftar ini mungkin tidak lengkap karena tidak semua penerbit menyediakan data kutipan yang cocok dan lengkap.
On Layanan dikutip-oleh Crossref tidak ada data tentang karya mengutip ditemukan (upaya terakhir 2022-07-24 00:26:48).
Makalah ini diterbitkan dalam Quantum di bawah Creative Commons Attribution 4.0 Internasional (CC BY 4.0) lisensi. Hak cipta tetap berada pada pemegang hak cipta asli seperti penulis atau lembaganya.
