1Kuantum Teknolojileri Merkezi, Singapur Ulusal Üniversitesi, Singapur
2Elektrik ve Bilgisayar Mühendisliği Bölümü, Mühendislik Fakültesi, Singapur Ulusal Üniversitesi, Singapur
Bu makaleyi ilginç mi buldunuz yoksa tartışmak mı istiyorsunuz? SciRate'e çığlık at veya yorum bırak.
Özet
Kuantum durumlarının özelliklerinin çevrimiçi olarak öğrenilmesinde keşif ve sömürü arasındaki dengeleri incelemeye başlıyoruz. Bilinmeyen bir kuantum durumuna sıralı kahin erişimi verildiğinde, her turda, durum (ödül) üzerindeki beklenti değerini en üst düzeye çıkarmayı amaçlayan bir dizi eylemden bir gözlemlenebilir olanı seçmekle görevlendirildik. Önceki turlardan bilinmeyen durum hakkında elde edilen bilgiler, eylem seçimini kademeli olarak iyileştirmek için kullanılabilir, böylece ödül ile verilen eylem seti ile elde edilebilecek maksimum ödül (pişmanlık) arasındaki boşluğu azaltır. Optimal bir öğrencinin maruz kalması gereken kümülatif pişmanlık üzerine çeşitli bilgi-teorik alt sınırlar sağlıyoruz ve bunun en azından oynanan tur sayısının karekökü kadar ölçeklendiğini gösteriyoruz. Ayrıca kümülatif pişmanlığın mevcut eylemlerin sayısına ve altta yatan alanın boyutuna bağımlılığını da araştırıyoruz. Ayrıca, sınırlı sayıda silahlı ve genel karışık durumdaki haydutlar için en uygun stratejiler sergiliyoruz.
[Gömülü içerik]
► BibTeX verileri
► Referanslar
[1] T. Lattimore ve C. Szepesvári. “Haydut algoritmaları”. Cambridge Üniversitesi Yayınları. (2020).
https: / / doi.org/ 10.1017 / 9781108571401
[2] A. Slivkins. “Çok kollu haydutlara giriş”. Makine Öğreniminde Temeller ve Eğilimler 12, 1–286 (2019).
https: / / doi.org/ 10.1561 / 2200000068
[3] S. Bubeck ve N. Cesa-Bianchi. "Stokastik ve stokastik olmayan çok kollu eşkıya problemlerinin pişmanlık analizi". Makine Öğrenimindeki Temeller ve Eğilimler 5, 1–122 (2012).
https: / / doi.org/ 10.1561 / 2200000024
[4] D. Bouneffouf, I. Rish ve C. Aggarwal. “Çok silahlı ve bağlamsal eşkıyaların uygulamaları üzerine bir araştırma”. 2020'de IEEE Evrimsel Hesaplama Kongresi (CEC). Sayfa 1-8. (2020).
https:///doi.org/10.1109/CEC48606.2020.9185782
[5] L. Tang, R. Rosales, A. Singh ve D. Agarwal. "Bağlamsal haydutlar aracılığıyla otomatik reklam formatı seçimi". 22. ACM Uluslararası Bilgi ve Bilgi Yönetimi Konferansı Bildirileri içinde. Sayfa 1587–1594. Bilgisayar Makineleri Derneği (2013).
https: / / doi.org/ 10.1145 / 2505515.2514700
[6] M. Cohen, I. Lobel ve R. Paes Leme. “Özelliğe dayalı dinamik fiyatlandırma”. Yönetim Bilimi 66, 4921–4943 (2020).
https:///doi.org/10.1287/mnsc.2019.3485
[7] W. Thompson. "İki örneğin kanıtları ışığında bilinmeyen bir olasılığın diğerini aşma olasılığı üzerine". Biometrika 25, 285–294 (1933).
https:///doi.org/10.1093/biomet/25.3-4.285
[8] H. Robbins. “Sıralı Deney Tasarımının Bazı Yönleri”. Amerikan Matematik Derneği Bülteni 58, 527–535 (1952).
https://doi.org/10.1090/S0002-9904-1952-09620-8
[9] TL Lai ve H. Robbins. "Asimptotik olarak verimli uyarlanabilir tahsis kuralları". Uygulamalı Matematikteki Gelişmeler 6, 4–22 (1985).
https://doi.org/10.1016/0196-8858(85)90002-8
[10] P. Auer, N. Cesa-Bianchi ve P. Fischer. "Çok kollu eşkıya probleminin sonlu zaman analizi". Mach. Öğrenmek. 47, 235–256 (2002).
https: / / doi.org/ 10.1023 / A: 1013689704352
[11] B. Casalé, G. Di Molfetta, H. Kadri, ve L. Ralaivola. “Kuantum haydutları”. Kuantum Mak. Intel. 2 (2020).
https://doi.org/10.1007/s42484-020-00024-8
[12] D. Wang, X. You, T. Li ve A. Childs. “Çok kollu haydutlar için kuantum keşif algoritmaları”. AAAI Yapay Zeka Konferansı Bildirileri'nde. Cilt 35, sayfalar 10102–10110. (2021).
[13] P. Rebentrost, Y. Hamoudi, M. Ray, X. Wang, S. Yang ve M. Santha. “Korunma için kuantum algoritmaları ve yaşam modellerinin öğrenilmesi”. Fizik. Rev. A 103, 012418 (2021).
https: / / doi.org/ 10.1103 / PhysRevA.103.012418
[14] O. Shamir. "Haydut doğrusal optimizasyonunun karmaşıklığı üzerine". 28. Öğrenme Teorisi Konferansı Bildiri Kitaplarında. Makine Öğrenimi Araştırması Bildirileri Cilt 40, sayfalar 1523–1551. PMLR (2015).
[15] P. Rusmevichientong ve J. Tsitsiklis. “Doğrusal parametreli haydutlar”. Yöneylem Araştırması Matematiği 35 (2008).
https: / / doi.org/ 10.1287 / moor.1100.0446
[16] J. Barry, DT Barry ve S. Aaronson. “Kuantum kısmen gözlemlenebilir Markov karar süreçleri”. Fizik. Rev. A 90, 032311 (2014).
https: / / doi.org/ 10.1103 / PhysRevA.90.032311
[17] M. Ying, Y. Feng ve S. Ying. "Kuantum Markov karar süreçleri için optimal politikalar". Uluslararası Otomasyon ve Bilgisayar Dergisi 18, 410–421 (2021).
HTTPS: / / doi.org/ 10.1007 / s11633-021-1278-z
[18] M. Paris ve J. Rehacek. “Kuantum durum tahmini”. Springer Yayıncılık Şirketi, Anonim Şirketi. (2010). 1. baskı.
https: / / doi.org/ 10.1007 / b98673
[19] S. Aaronson. “Kuantum durumlarının gölge tomografisi”. 50. Yıllık ACM SIGACT Hesaplama Teorisi Sempozyumu Bildiri Kitaplarında. Sayfa 325–338. STOC 2018. Bilgisayar Makineleri Birliği (2018).
https: / / doi.org/ 10.1145 / 3188745.3188802
[20] S. Aaronson, X. Chen, E. Hazan, S. Kale ve A. Nayak. “Kuantum durumlarının çevrimiçi öğrenimi”. İstatistiksel Mekanik Dergisi: Teori ve Deney 2019 (2018).
https: / / doi.org/ 10.1088 / 1742-5468 / ab3988
[21] J. Bretagnolle ve C. Huber. "Estimation des densités: riskli minimummaks". 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 ve M. Tomamichel. “Kuantum Rényi Entropileri Üzerine: Yeni Bir Genelleme ve Bazı Özellikler”. Matematiksel Fizik Dergisi 54, 122203 (2013).
https: / / doi.org/ 10.1063 / 1.4838856
[23] M. Wilde, A. Winter ve D. Yang. "Sandviçlenmiş Rényi Göreli Entropisi Yoluyla Dolaşma-Kırılma ve Hadamard Kanallarının Klasik Kapasitesi için Güçlü Converse". Matematiksel Fizikte İletişim 331, 593–622 (2014).
https: / / doi.org/ 10.1007 / s00220-014-2122-x
[24] W. Hoeffding. "Sınırlı rastgele değişkenlerin toplamları için olasılık eşitsizlikleri". Amerikan İstatistik Birliği Dergisi 58, 13–30 (1963).
https: / / doi.org/ 10.1080 / 01621459.1963.10500830
[25] P. Auer. “Kullanım-keşif dengeleri için güven sınırlarının kullanılması”. J. Mach. Öğrenmek. Res. 3, 397–422 (2003).
https: / / doi.org/ 10.5555 / 944919.944941
[26] D. Varsha, T. Hayes ve S.Kakade. "Haydut geribildirimi altında stokastik doğrusal optimizasyon.". 21. Öğrenme Teorisi Konferansı Bildirileri içinde. Sayfalar 355–366. (2008).
[27] P. Rusmevichientong ve JN Tsitsiklis. “Doğrusal parametreli haydutlar”. Yöneylem Araştırması Matematiği 35, 395–411 (2010).
https: / / doi.org/ 10.1287 / moor.1100.0446
[28] Y. Abbasi-Yadkori, D. Pál ve Cs. Szepesvári. “Doğrusal stokastik haydutlar için geliştirilmiş algoritmalar”. Sinirsel Bilgi İşleme Sistemlerindeki Gelişmeler. Cilt 24. Curran Associates, Inc. (2011).
[29] TL Lai. “Uyarlanabilir Tedavi Tahsisi ve Çok Silahlı Eşkıya Sorunu”. İstatistik Yıllıkları 15, 1091 – 1114 (1987).
https: / / doi.org/ 10.1214 / aos / 1176350495
[30] M. Guţă, J. Kahn, R. Kueng ve JA Tropp. "Optimal hata sınırlarına sahip hızlı durum tomografisi". Fizik Dergisi A: Matematiksel ve Teorik 53, 204001 (2020).
https: / / doi.org/ 10.1088 / 1751-8121 / ab8111
[31] T. Lattimore ve B. Hao. "Haydut aşamasının geri alınması". Sinirsel Bilgi İşleme Sistemlerindeki Gelişmeler. Cilt 34, sayfalar 18801–18811. Curran Associates, Inc. (2021).
Alıntılama
[1] Zongqi Wan, Zhijie Zhang, Tongyang Li, Jialin Zhang ve Xiaoming Sun, "Kuantum Çok Silahlı Haydutlar ve Stokastik Doğrusal Haydutlar Logaritmik Pişmanlıkların Keyfini Çıkarıyor", arXiv: 2205.14988.
[2] Xinyi Chen, Elad Hazan, Tongyang Li, Zhou Lu, Xinzhao Wang ve Rui Yang, “Kuantum Durumlarının Uyarlanabilir Çevrimiçi Öğrenmesi”, arXiv: 2206.00220.
Yukarıdaki alıntılar SAO / NASA REKLAMLARI (son başarıyla 2022-07-24 00:26:50) güncellendi. Tüm yayıncılar uygun ve eksiksiz alıntı verisi sağlamadığından liste eksik olabilir.
On Crossref'in alıntı yaptığı hizmet alıntı yapma çalışmaları ile ilgili veri bulunamadı (son deneme 2022-07-24 00:26:48).
Bu Makale, Quantum'da Creative Commons Atıf 4.0 Uluslararası (CC BY 4.0) lisans. Telif hakkı, yazarlar veya kurumları gibi orijinal telif hakkı sahiplerine aittir.
