1Центр квантових технологій Національного університету Сінгапуру, Сінгапур
2Кафедра електротехніки та комп’ютерної інженерії, Інженерний факультет, Національний університет Сінгапуру, Сінгапур
Вам цей документ цікавий чи ви хочете обговорити? Скайте або залиште коментар на SciRate.
абстрактний
Ми розпочинаємо дослідження компромісів між дослідженням та експлуатацією в онлайн-вивченні властивостей квантових станів. Маючи послідовний доступ оракула до невідомого квантового стану, у кожному раунді нам доручають вибрати спостережувану величину з набору дій, спрямованих на максимізацію її очікуваного значення для стану (винагороди). Інформацію, отриману про невідомий стан із попередніх раундів, можна використовувати для поступового покращення вибору дії, таким чином зменшуючи розрив між винагородою та максимальною винагородою, яку можна отримати за допомогою даного набору дій (жалю). Ми надаємо різні інформаційно-теоретичні нижні межі кумулятивного жалю, який повинен зазнати оптимальний учень, і показуємо, що воно масштабується принаймні як квадратний корінь із кількості зіграних раундів. Ми також досліджуємо залежність кумулятивного жалю від кількості доступних дій і розміру основного простору. Крім того, ми демонструємо стратегії, які є оптимальними для бандитів із кінцевою кількістю озброєнь і загальних змішаних станів.
[Вбудоване вміст]
► Дані BibTeX
► Список літератури
[1] Т. Латтімор і К. Шепешварі. «Бандитські алгоритми». Cambridge University Press. (2020).
https: / / doi.org/ 10.1017 / 9781108571401
[2] А. Сливкінс. «Знайомство з багаторукими бандитами». Основи та тенденції машинного навчання 12, 1–286 (2019).
https: / / doi.org/ 10.1561 / 2200000068
[3] С. Бубек і Н. Чеза-Біанкі. «Аналіз жалю стохастичних і нестохастичних проблем багаторуких бандитів». Основи та тенденції машинного навчання 5, 1–122 (2012).
https: / / doi.org/ 10.1561 / 2200000024
[4] Д. Бунеффуф, І. Ріш і К. Аггарвал. «Опитування щодо заявок багаторуких та контекстних бандитів». У 2020 році на Конгресі IEEE з еволюційних обчислень (CEC). Сторінки 1–8. (2020).
https:///doi.org/10.1109/CEC48606.2020.9185782
[5] Л. Танг, Р. Розалес, А. Сінгх і Д. Агарвал. «Автоматичний вибір формату реклами за допомогою контекстних бандитів». У матеріалах 22-ї міжнародної конференції ACM з управління інформацією та знаннями. Сторінки 1587–1594. Асоціація обчислювальної техніки (2013).
https: / / doi.org/ 10.1145 / 2505515.2514700
[6] М. Коен, І. Лобель, Р. Паес Леме. «Динамічне ціноутворення на основі функцій». Наука управління 66, 4921–4943 (2020).
https:///doi.org/10.1287/mnsc.2019.3485
[7] В. Томпсон. «Про ймовірність того, що одна невідома ймовірність перевищує іншу з огляду на докази двох зразків». Біометрика 25, 285–294 (1933).
https:///doi.org/10.1093/biomet/25.3-4.285
[8] Х. Роббінс. «Деякі аспекти послідовного планування експериментів». Бюлетень Американського математичного товариства 58, 527–535 (1952).
https://doi.org/10.1090/S0002-9904-1952-09620-8
[9] Т. Л. Лай і Х. Роббінс. “Асимптотично ефективні адаптивні правила розподілу”. Досягнення прикладної математики 6, 4–22 (1985).
https://doi.org/10.1016/0196-8858(85)90002-8
[10] П. Ауер, Н. Чеза-Біанкі, П. Фішер. “Аналіз проблеми багаторукого бандита в кінцевому часі”. мах. вчитися. 47, 235–256 (2002).
https:///doi.org/10.1023/A:1013689704352
[11] B. Casalé, G. Di Molfetta, H. Kadri, , and L. Ralaivola. «Квантові бандити». Квант Маха. Intell. 2 (2020).
https://doi.org/10.1007/s42484-020-00024-8
[12] Д. Ван, X. Ю, Т. Лі та А. Чайлдс. «Алгоритми квантового дослідження багаторуких бандитів». У матеріалах конференції AAAI зі штучного інтелекту. Том 35, сторінки 10102–10110. (2021).
[13] П. Ребентрост, Ю. Хамуді, М. Рей, X. Ван, С. Янг і М. Санта. «Квантові алгоритми для хеджування та вивчення моделей Ізінга». фіз. Rev. A 103, 012418 (2021).
https: / / doi.org/ 10.1103 / PhysRevA.103.012418
[14] О. Шамір. “Про складність бандитної лінійної оптимізації”. У матеріалах 28-ї конференції з теорії навчання. Том 40 Proceedings of Machine Learning Research, сторінки 1523–1551. PMLR (2015).
[15] П. Русмевичентонг і Я. Ціцикліс. «Лінійно параметризовані бандити». Математика дослідження операцій 35 (2008).
https:///doi.org/10.1287/moor.1100.0446
[16] Дж. Баррі, Д. Т. Баррі та С. Ааронсон. “Квантові частково спостережувані марковські процеси прийняття рішень”. фіз. Rev. A 90, 032311 (2014).
https: / / doi.org/ 10.1103 / PhysRevA.90.032311
[17] М. Ін, Ю. Фенг і С. Ін. “Оптимальна політика для квантових марковських процесів прийняття рішень”. Міжнародний журнал автоматизації та обчислювальної техніки 18, 410–421 (2021).
https: / / doi.org/ 10.1007 / s11633-021-1278-z
[18] М. Паріс і Я. Рехачек. “Оцінка квантового стану”. Springer Publishing Company, Incorporated. (2010). 1-е видання.
https:///doi.org/10.1007/b98673
[19] С. Ааронсон. “Тіньова томографія квантових станів”. У матеріалах 50-го щорічного симпозіуму ACM SIGACT з теорії обчислень. Сторінки 325–338. STOC 2018. Асоціація обчислювальної техніки (2018).
https: / / doi.org/ 10.1145 / 3188745.3188802
[20] С. Ааронсон, X. Чен, Е. Хазан, С. Кале та А. Наяк. «Онлайн навчання квантовим станам». Журнал статистичної механіки: Теорія та експеримент 2019 (2018).
https:///doi.org/10.1088/1742-5468/ab3988
[21] Ж. Бретаньолле і К. Губер. «Оцінка щільності: ризикований мінімакс». Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete 47, 119–137 (1979).
https: / / doi.org/ 10.1007 / BF00535278
[22] М. Мюллер-Леннерт, Ф. Дюпюї, О. Зер, С. Фер, М. Томаміхель. “Про квантові ентропії Реньї: нове узагальнення та деякі властивості”. Журнал математичної фізики 54, 122203 (2013).
https: / / doi.org/ 10.1063 / 1.4838856
[23] М. Уайльд, А. Вінтер, Д. Янг. «Сильна протилежність для класичної здатності розриву заплутаності та каналів Адамара через сендвічну відносну ентропію Реньї». Повідомлення в математичній фізиці 331, 593–622 (2014).
https: / / doi.org/ 10.1007 / s00220-014-2122-x
[24] В. Хьофдінг. “Імовірнісні нерівності для сум обмежених випадкових величин”. Журнал Американської статистичної асоціації 58, 13–30 (1963).
https: / / doi.org/ 10.1080 / 01621459.1963.10500830
[25] П. Ауер. «Використання довірчих меж для компромісів між експлуатацією та розвідкою». Й. Мах. вчитися. рез. 3, 397–422 (2003).
https: / / doi.org/ 10.5555 / 944919.944941
[26] Д. Варша, Т. Хейс, С. Какаде. «Стохастична лінійна оптимізація за умов бандитного зворотного зв’язку». У матеріалах 21-ї конференції з теорії навчання. Сторінки 355–366. (2008).
[27] П. Русмевичентонг і Ю. Н. Ціцикліс. «Лінійно параметризовані бандити». Математика дослідження операцій 35, 395–411 (2010).
https:///doi.org/10.1287/moor.1100.0446
[28] Y. Abbasi-Yadkori, D. Pál, and Cs. Szepesvári. «Покращені алгоритми для лінійних стохастичних бандитів». Досягнення нейронних систем обробки інформації. Том 24. Curran Associates, Inc. (2011).
[29] Т. Л. Лай. «Адаптивний розподіл лікування та проблема багаторукого бандита». Аннали статистики 15, 1091 – 1114 (1987).
https:///doi.org/10.1214/aos/1176350495
[30] М. Гуце, Дж. Кан, Р. Куенг і Дж. А. Тропп. “Швидка томографія стану з оптимальними межами помилки”. Journal of Physics A: Mathematical and Theoretical 53, 204001 (2020).
https:///doi.org/10.1088/1751-8121/ab8111
[31] Т. Латтімор і Б. Хао. «Вилучення фази бандита». Удосконалення нейронних систем обробки інформації. Том 34, сторінки 18801–18811. Curran Associates, Inc. (2021).
Цитується
[1] Zongqi Wan, Zhijie Zhang, Tongyang Li, Jialin Zhang, and Xiaoming Sun, “Quantum Multi-Armed Bandits and Stochastic Linear Bandits Enjoy Logarithmic Regrets”, arXiv: 2205.14988.
[2] Сіньї Чен, Елад Хазан, Тонг’ян Лі, Чжоу Лу, Сіньчжао Ван і Руй Ян, «Адаптивне онлайн-навчання квантових станів», 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 International (CC на 4.0) ліцензія. Авторське право залишається за оригінальними власниками авторських прав, такими як автори або їх установи.
