اللصوص الكمومية متعددة الأسلحة: الاستكشاف مقابل الاستغلال عند تعلم خصائص الحالات الكمية

عقدة المصدر: 1590105

جوزيب لومبريراس1، إركا هاباسالو1، وماركو توماميشل1,2

1مركز تقنيات الكم ، جامعة سنغافورة الوطنية ، سنغافورة
2قسم الهندسة الكهربائية وهندسة الحاسبات ، كلية الهندسة ، جامعة سنغافورة الوطنية ، سنغافورة

تجد هذه الورقة مثيرة للاهتمام أو ترغب في مناقشة؟ Scite أو ترك تعليق على SciRate.

ملخص

بدأنا دراسة المفاضلات بين الاستكشاف والاستغلال في التعلم عبر الإنترنت لخصائص الحالات الكمية. بالنظر إلى الوصول المتسلسل أوراكل إلى حالة كمومية غير معروفة ، في كل جولة ، تم تكليفنا باختيار ما يمكن ملاحظته من مجموعة من الإجراءات التي تهدف إلى تعظيم قيمة توقعها على الحالة (المكافأة). يمكن استخدام المعلومات المكتسبة حول الحالة غير المعروفة من الجولات السابقة لتحسين اختيار الإجراء تدريجيًا ، وبالتالي تقليل الفجوة بين المكافأة والمكافأة القصوى التي يمكن تحقيقها مع مجموعة الإجراءات المحددة (الندم). نحن نقدم العديد من الحدود السفلية النظرية للمعلومات حول الأسف التراكمي الذي يجب أن يتحمله المتعلم الأمثل ، ونوضح أنه يتساوى على الأقل مع الجذر التربيعي لعدد الجولات التي تم لعبها. نحن نحقق أيضًا في اعتماد الأسف التراكمي على عدد الإجراءات المتاحة وأبعاد المساحة الأساسية. علاوة على ذلك ، فإننا نعرض استراتيجيات مثالية لقطاع الطرق الذين لديهم عدد محدود من الأسلحة والحالات المختلطة العامة.

[المحتوى جزءا لا يتجزأ]

► بيانات BibTeX

ferences المراجع

[1] T. Lattimore و C. Szepesvári. "خوارزميات اللصوص". صحافة جامعة كامبرج. (2020).
الشبكي: / / doi.org/ 10.1017 / 9781108571401

[2] أ. سليفكينز. "مقدمة في ماكينات الألعاب المتعددة". أسس واتجاهات في التعلم الآلي 12 ، 1-286 (2019).
الشبكي: / / doi.org/ 10.1561 / 2200000068

[3] S. Bubeck و N. Cesa-Bianchi. "تحليل الأسف لمشاكل ماكينات الألعاب المتعددة العشوائية وغير العشوائية". أسس واتجاهات في التعلم الآلي 5 ، 1-122 (2012).
الشبكي: / / doi.org/ 10.1561 / 2200000024

[4] بنيفوف وإي. ريش وسي. أجروال. "دراسة استقصائية عن تطبيقات ماكينات الألعاب متعددة الأغراض والسياقية". في عام 2020 مؤتمر IEEE حول الحساب التطوري (CEC). الصفحات 1-8. (2020).
https: / / doi.org/ 10.1109 / CEC48606.2020.9185782

تانغ ، ر. روساليس ، أ. سينغ ، ود. أغاروال. "التحديد التلقائي لشكل الإعلان عبر قطاع الطرق السياقية". في وقائع المؤتمر الدولي الثاني والعشرين للـ ACM حول إدارة المعلومات والمعرفة. صفحة 22-1587. جمعية ماكينات الحوسبة (1594).
الشبكي: / / doi.org/ 10.1145 / 2505515.2514700

[6] إم كوهين وإي لوبيل ور. بايس ليم. "التسعير الديناميكي القائم على الميزات". علم الإدارة 66 ، 4921-4943 (2020).
https: / / doi.org/ 10.1287 / mnsc.2019.3485

[7] دبليو طومسون. "عن احتمال تجاوز احتمال غير معروف آخر في ضوء دليل عينتين". Biometrika 25 ، 285-294 (1933).
https: / / doi.org/10.1093 / biomet / 25.3-4.285

[8] H. روبنز. "بعض جوانب التصميم المتسلسل للتجارب". نشرة الجمعية الرياضية الأمريكية 58 ، 527-535 (1952).
https:/​/​doi.org/​10.1090/​S0002-9904-1952-09620-8

[9] TL Lai و H. Robbins. "قواعد تخصيص تكيفية ذات كفاءة مقاربة". التقدم في الرياضيات التطبيقية 6 ، 4-22 (1985).
https:/​/​doi.org/​10.1016/​0196-8858(85)90002-8

[10] بي أوير ، ن. سيسا بيانكي ، وبي. فيشر. "تحليل الوقت المحدود لمشكلة ماكينات الألعاب المتعددة". ماخ. يتعلم. 47 ، 235-256 (2002).
الشبكي: / / doi.org/ 10.1023 / A: 1013689704352

[11] B. Casalé ، و G. Di Molfetta ، و H. Kadri ، و L. Ralaivola. "قطاع الطرق الكم". ماخ الكم. انتل. 2 (2020).
https:/​/​doi.org/​10.1007/​s42484-020-00024-8

[12] وانغ ، إكس. أنت ، ت. لي ، وأ. تشايلدز. "خوارزميات استكشاف الكم لقطاع الطرق متعددة الأسلحة". في وقائع مؤتمر AAAI حول الذكاء الاصطناعي. المجلد 35 ، الصفحات 10102-10110. (2021).

[13] ريبنتروست ، واي.حمودي ، إم. راي ، إكس وانج ، إس يانج ، إم سانثا. "خوارزميات الكم للتحوط وتعلم نماذج ising". فيز. القس أ 103 ، 012418 (2021).
الشبكي: / / doi.org/ 10.1103 / PhysRevA.103.012418

[14] يا شامير. "على تعقيد التحسين الخطي ماكينات القطع". في وقائع المؤتمر الثامن والعشرين حول نظرية التعلم. المجلد 28 من وقائع بحث التعلم الآلي ، الصفحات 40-1523. PMLR (1551).

[15] P. Rusmevichientong و J. Tsitsiklis. "قطاع الطرق الخطي المعلمات". رياضيات بحوث العمليات 35 (2008).
الشبكي: / / doi.org/ 10.1287 / moor.1100.0446

[16] جي باري ودي تي باري وس. آرونسون. "عمليات قرار ماركوف الكمية التي يمكن ملاحظتها جزئيًا". فيز. القس أ 90 ، 032311 (2014).
الشبكي: / / doi.org/ 10.1103 / PhysRevA.90.032311

[17] إم يينغ ، واي. فنغ ، وس. ينج. "السياسات المثلى لعمليات اتخاذ القرار علامة الكم". المجلة الدولية للأتمتة والحوسبة 18 ، 410-421 (2021).
الشبكي: / / doi.org/ 10.1007 / s11633-021-1278 زي

[18] م.باريس وج. ريهاشك. "تقدير الحالة الكمومية". شركة Springer للنشر ، إنكوربوريتد. (2010). الطبعة الأولى.
الشبكي: / / doi.org/ 10.1007 / b98673

[19] إس آرونسون. "تصوير الظل المقطعي للحالات الكمومية". في وقائع الندوة السنوية الخمسين لـ ACM SIGACT حول نظرية الحوسبة. صفحة 50–325. STOC 338. Association for Computing Machinery (2018).
الشبكي: / / doi.org/ 10.1145 / 3188745.3188802

[20] إس آرونسون ، إكس تشين ، إي هازان ، س. كالي ، وأ. ناياك. "التعلم عبر الإنترنت للحالات الكمومية". مجلة الميكانيكا الإحصائية: النظرية والتجربة 2019 (2018).
الشبكي: / / doi.org/ 10.1088 / 1742-5468 / ab3988

[21] J. Bretagnolle و C. Huber. "تقدير الكثافة: الحد الأدنى الصاعد". Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete 47، 119–137 (1979).
الشبكي: / / doi.org/ 10.1007 / BF00535278

[22] م. مولر-لينرت ، إف. دوبوي ، أو.زيهر ، س. فيهر ، إم توماميشيل. "في الانتروبيا الكمومية: تعميم جديد وبعض الخصائص". مجلة الفيزياء الرياضية 54 ، 122203 (2013).
الشبكي: / / doi.org/ 10.1063 / 1.4838856

[23] إم وايلد ، أ. وينتر ، ودي يانج. "حديث قوي عن القدرة الكلاسيكية لقنوات كسر التشابك و Hadamard عبر الانتروبيا النسبية المحصورة من Rényi". الاتصالات في الفيزياء الرياضية 331 ، 593-622 (2014).
الشبكي: / / doi.org/ 10.1007 / s00220-014-2122-X

[24] دبليو هوفدينغ. "عدم المساواة احتمال لقاء مبالغ من المتغيرات العشوائية يحدها". مجلة الجمعية الإحصائية الأمريكية 58 ، 13-30 (1963).
الشبكي: / / doi.org/ 10.1080 / 01621459.1963.10500830

[25] P. أوير. "استخدام حدود الثقة لمقايضات الاستغلال والاستكشاف". J. ماخ. يتعلم. الدقة. 3 ، 397-422 (2003).
الشبكي: / / doi.org/ 10.5555 / 944919.944941

[26] فارشا ، ت. هايز ، إس كاكادي. "التحسين الخطي العشوائي في ظل ردود فعل قطاع الطرق.". في وقائع المؤتمر الحادي والعشرين حول نظرية التعلم. الصفحات من 21 إلى 355. (366).

[27] P. Rusmevichientong و JN Tsitsiklis. "قطاع الطرق الخطي المعلمات". رياضيات بحوث العمليات 35 ، 395-411 (2010).
الشبكي: / / doi.org/ 10.1287 / moor.1100.0446

[28] ي. عباسي يادكوري ، د. بال ، وسي. Szepesvári. "خوارزميات محسنة للقطاع العشوائي الخطي". في التقدم في أنظمة معالجة المعلومات العصبية. المجلد 24. Curran Associates، Inc. (2011).

[29] TL لاي. "تخصيص العلاج التكيفي ومشكلة قطاع الطرق متعددة الأسلحة". سجلات الإحصاء 15 ، 1091-1114 (1987).
https: / / doi.org/ 10.1214 / aos / 1176350495

[30] M. Guţă و J. Kahn و R. Kueng و JA Tropp. "التصوير المقطعي السريع مع حدود الخطأ المثلى". مجلة الفيزياء أ: الرياضيات والنظرية 53 ، 204001 (2020).
الشبكي: / / doi.org/ 10.1088 / 1751-8121 / ab8111

[31] T. Lattimore و B. Hao. "استرجاع طور قطاع الطرق". في التقدم في أنظمة معالجة المعلومات العصبية. المجلد 34 ، الصفحات 18801–18811. كوران أسوشيتس ، إنك (2021).

دليلنا يستخدم من قبل

[1] Zongqi Wan ، و Zhijie Zhang ، و Tongyang Li ، و Jialin Zhang ، و Xiaoming Sun ، "اللصوص متعددو الأذرع واللصوص الخطيون العشوائي يتمتعون بالندم اللوغاريتمي" ، أرخايف: 2205.14988.

[2] Xinyi Chen و Elad Hazan و Tongyang Li و Zhou Lu و Xinzhao Wang و Rui Yang ، "التعلم التكيفي عبر الإنترنت للدول الكمية" ، أرخايف: 2206.00220.

الاستشهادات المذكورة أعلاه من إعلانات ساو / ناسا (تم آخر تحديث بنجاح 2022-07-24 00:26:50). قد تكون القائمة غير كاملة نظرًا لأن جميع الناشرين لا يقدمون بيانات اقتباس مناسبة وكاملة.

On خدمة Crossref's cited-by service لم يتم العثور على بيانات حول الاستشهاد بالأعمال (المحاولة الأخيرة 2022-07-24 00:26:48).

الطابع الزمني:

اكثر من مجلة الكم