1Trung tâm Công nghệ Lượng tử, Đại học Quốc gia Singapore, Singapore
2Khoa Kỹ thuật Điện và Máy tính, Khoa Kỹ thuật, Đại học Quốc gia Singapore, Singapore
Tìm bài báo này thú vị hay muốn thảo luận? Scite hoặc để lại nhận xét về SciRate.
Tóm tắt
Chúng tôi bắt đầu nghiên cứu sự cân bằng giữa việc thăm dò và khai thác trong việc học trực tuyến các thuộc tính của trạng thái lượng tử. Với quyền truy cập tiên tri tuần tự vào một trạng thái lượng tử chưa biết, trong mỗi vòng, chúng tôi có nhiệm vụ chọn một hành động có thể quan sát được từ một tập hợp các hành động nhằm tối đa hóa giá trị kỳ vọng của nó đối với trạng thái (phần thưởng). Thông tin thu được về trạng thái chưa biết từ các vòng trước có thể được sử dụng để dần dần cải thiện lựa chọn hành động, do đó giảm khoảng cách giữa phần thưởng và phần thưởng tối đa có thể đạt được với bộ hành động đã cho (sự hối tiếc). Chúng tôi cung cấp các giới hạn thấp hơn về mặt lý thuyết-thông tin khác nhau dựa trên sự hối tiếc tích lũy mà một người học tối ưu phải gánh chịu, và chỉ ra rằng tỉ lệ đó ít nhất là căn bậc hai của số vòng chơi. Chúng tôi cũng điều tra sự phụ thuộc của tiếc tích lũy vào số lượng các hành động có sẵn và kích thước của không gian cơ bản. Hơn nữa, chúng tôi trưng bày các chiến lược tối ưu cho những tên cướp có số lượng vũ khí hữu hạn và trạng thái hỗn hợp nói chung.
[Nhúng nội dung]
► Dữ liệu BibTeX
► Tài liệu tham khảo
[1] T. Lattimore và C. Szepesvári. "Các thuật toán của kẻ cướp". Nhà xuất bản Đại học Cambridge. (Năm 2020).
https: / / doi.org/ 10.1017 / 9781108571401
[2] A. Slivkins. "Giới thiệu về tên cướp nhiều vũ khí". Cơ sở và Xu hướng trong Học máy 12, 1–286 (2019).
https: / / doi.org/ 10.1561 / 2200000068
[3] S. Bubeck và N. Cesa-Bianchi. “Phân tích hối tiếc về các vấn đề tên cướp nhiều nhánh ngẫu nhiên và ngẫu nhiên”. Cơ sở và Xu hướng trong Học máy 5, 1–122 (2012).
https: / / doi.org/ 10.1561 / 2200000024
[4] D. Bouneffouf, I. Rish và C. Aggarwal. “Khảo sát về các ứng dụng của kẻ cướp nhiều nhánh và theo ngữ cảnh”. Vào năm 2020, Đại hội IEEE về Tính toán Tiến hóa (CEC). Trang 1–8. (Năm 2020).
https: / / doi.org/ 10.1109 / CEC48606.2020.9185782
[5] L. Tang, R. Rosales, A. Singh và D. Agarwal. “Lựa chọn định dạng quảng cáo tự động thông qua trình chia theo ngữ cảnh”. Trong Kỷ yếu của Hội nghị Quốc tế ACM lần thứ 22 về Quản lý Thông tin và Tri thức. Trang 1587–1594. Hiệp hội Máy tính (2013).
https: / / doi.org/ 10.1145 / 2505515.2514700
[6] M. Cohen, I. Lobel và R. Paes Leme. "Định giá động dựa trên tính năng". Khoa học Quản lý 66, 4921–4943 (2020).
https: / / doi.org/ 10.1287 / mnsc.2019.3485
[7] W. Thompson. “Về khả năng một xác suất chưa biết sẽ vượt quá xác suất khác khi xem xét bằng chứng của hai mẫu”. Biometrika 25, 285–294 (1933).
https: / / doi.org/ 10.1093 / biomet / 25.3-4.285
[8] H. Robbins. “Một số khía cạnh của thiết kế tuần tự các thử nghiệm”. Bản tin của Hiệp hội Toán học Hoa Kỳ 58, 527–535 (1952).
https://doi.org/10.1090/S0002-9904-1952-09620-8
[9] TL Lai và H. Robbins. “Quy tắc phân bổ thích ứng hiệu quả tiệm cận”. Những tiến bộ trong Toán học Ứng dụng 6, 4–22 (1985).
https://doi.org/10.1016/0196-8858(85)90002-8
[10] P. Auer, N. Cesa-Bianchi và P. Fischer. “Phân tích thời gian hữu hạn của vấn đề tên cướp nhiều phần”. Mach. Học. 47, 235–256 (2002).
https: / / doi.org/ 10.1023 / A: 1013689704352
[11] B. Casalé, G. Di Molfetta, H. Kadri và L. Ralaivola. "Kẻ cướp lượng tử". Lượng tử Mach. Giới thiệu. 2 (năm 2020).
https://doi.org/10.1007/s42484-020-00024-8
[12] D. Wang, X. You, T. Li và A. Childs. “Các thuật toán thăm dò lượng tử cho kẻ cướp nhiều nhánh”. Trong Kỷ yếu của Hội nghị AAAI về Trí tuệ Nhân tạo. Tập 35, trang 10102–10110. (Năm 2021).
[13] P. Rebentrost, Y. Hamoudi, M. Ray, X. Wang, S. Yang và M. Santha. “Các thuật toán lượng tử để bảo hiểm rủi ro và việc học các mô hình ising”. Thể chất. Phiên bản A 103, 012418 (2021).
https: / / doi.org/ 10.1103 / PhysRevA.103.012418
[14] O. Shamir. “Về mức độ phức tạp của tối ưu hóa tuyến tính nhóm cướp”. Trong Kỷ yếu của Hội nghị lần thứ 28 về Lý thuyết Học tập. Tập 40 của Kỷ yếu Nghiên cứu Máy học, trang 1523–1551. PMLR (2015).
[15] P. Rusmevichientong và J. Tsitsiklis. "Kẻ cướp được tham số tuyến tính". Toán học của Nghiên cứu Hoạt động 35 (2008).
https: / / doi.org/ 10.1287 / moor.1100.0446
[16] J. Barry, DT Barry và S. Aaronson. “Các quá trình quyết định markov có thể quan sát được một phần lượng tử”. Thể chất. Phiên bản A 90, 032311 (2014).
https: / / doi.org/ 10.1103 / PhysRevA.90.032311
[17] M. Ying, Y. Feng và S. Ying. “Các chính sách tối ưu cho các quá trình quyết định markov lượng tử”. Tạp chí Quốc tế về Tự động hóa và Máy tính 18, 410–421 (2021).
https: / / doi.org/ 10.1007 / s11633-021-1278-z
[18] M. Paris và J. Rehacek. “Ước tính trạng thái lượng tử”. Springer Publishing Company, Incorporated. (2010). Phiên bản đầu tiên.
https: / / doi.org/ 10.1007 / b98673
[19] S. Aaronson. "Chụp cắt lớp bóng tối của các trạng thái lượng tử". Trong Kỷ yếu Hội thảo ACM SIGACT hàng năm lần thứ 50 về Lý thuyết Máy tính. Trang 325–338. STOC 2018. Hiệp hội Máy tính (2018).
https: / / doi.org/ 10.1145 / 3188745.3188802
[20] S. Aaronson, X. Chen, E. Hazan, S. Kale và A. Nayak. “Học trực tuyến về trạng thái lượng tử”. Tạp chí Cơ học Thống kê: Lý thuyết và Thực nghiệm 2019 (2018).
https: / / doi.org/ 10.1088 / 1742-5468 / ab3988
[21] J. Bretagnolle và C. Huber. “Ước tính 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 và M. Tomamichel. “Về Entropies lượng tử Rényi: Một sự tổng quát hóa mới và một số thuộc tính”. Tạp chí Toán học Vật lý 54, 122203 (2013).
https: / / doi.org/ 10.1063 / 1.4838856
[23] M. Wilde, A. Winter, và D. Yang. “Converse mạnh mẽ cho khả năng cổ điển của các kênh Hadamard và Entanglement-Break thông qua một Entropy tương đối Rényi được kẹp vào nhau”. Truyền thông trong Vật lý Toán học 331, 593–622 (2014).
https: / / doi.org/ 10.1007 / s00220-014-2122-x
[24] W. Hoeffding. "Bất bình đẳng xác suất cho các khoản tiền của các biến ngẫu nhiên bị chặn". Tạp chí của Hiệp hội Thống kê Hoa Kỳ 58, 13–30 (1963).
https: / / doi.org/ 10.1080 / 01621459.1963.10500830
[25] P. Auer. “Sử dụng giới hạn tin cậy để đánh đổi khai thác-thăm dò”. J. Mach. Học. Res. 3, 397–422 (2003).
https: / / doi.org/ 10.5555 / 944919.944941
[26] D. Varsha, T. Hayes và S.Kakade. “Tối ưu hóa tuyến tính ngẫu nhiên theo phản hồi của kẻ cướp.”. Trong Kỷ yếu của Hội nghị lần thứ 21 về Lý thuyết Học tập. Trang 355–366. (2008).
[27] P. Rusmevichientong và JN Tsitsiklis. "Kẻ cướp được tham số tuyến tính". Toán học của Nghiên cứu Hoạt động 35, 395–411 (2010).
https: / / doi.org/ 10.1287 / moor.1100.0446
[28] Y. Abbasi-Yadkori, D. Pál, và Cs. Szepesvári. “Các thuật toán được cải thiện cho kẻ cướp ngẫu nhiên tuyến tính”. Những tiến bộ trong hệ thống xử lý thông tin thần kinh. Tập 24. Curran Associates, Inc. (2011).
[29] TL Lai. “Phân bổ Điều trị Thích ứng và Vấn đề Kẻ cướp Nhiều vũ trang”. Biên niên sử thống kê 15, 1091 - 1114 (1987).
https: / / doi.org/ 10.1214 / aos / 1176350495
[30] M. Guţă, J. Kahn, R. Kueng và JA Tropp. “Chụp cắt lớp trạng thái nhanh với giới hạn sai số tối ưu”. Tạp chí Vật lý A: Toán học và Lý thuyết 53, 204001 (2020).
https: / / doi.org/ 10.1088 / 1751-8121 / ab8111
[31] T. Lattimore và B. Hao. “Truy xuất giai đoạn kẻ cướp”. Những tiến bộ trong hệ thống xử lý thông tin thần kinh. Tập 34, trang 18801–18811. Curran Associates, Inc. (2021).
Trích dẫn
[1] Zongqi Wan, Zhijie Zhang, Tongyang Li, Jialin Zhang và Xiaoming Sun, “Những tên cướp đa vũ trang lượng tử và những tên cướp tuyến tính Stochastic tận hưởng những điều tiếc nuối về lôgarit”, arXiv: 2205.14988.
[2] Xinyi Chen, Elad Hazan, Tongyang Li, Zhou Lu, Xinzhao Wang và Rui Yang, “Học trực tuyến thích ứng về các trạng thái lượng tử”, arXiv: 2206.00220.
Các trích dẫn trên là từ SAO / NASA ADS (cập nhật lần cuối thành công 2022 / 07-24 00:26:50). Danh sách có thể không đầy đủ vì không phải tất cả các nhà xuất bản đều cung cấp dữ liệu trích dẫn phù hợp và đầy đủ.
On Dịch vụ trích dẫn của Crossref không có dữ liệu về các công việc trích dẫn được tìm thấy (lần thử cuối cùng 2022 / 07-24 00:26:48).
Bài viết này được xuất bản trong Lượng tử dưới Creative Commons Ghi công 4.0 Quốc tế (CC BY 4.0) giấy phép. Bản quyền vẫn thuộc về chủ sở hữu bản quyền gốc như các tác giả hoặc tổ chức của họ.
