1Центр квантовых технологий, Национальный университет Сингапура, Сингапур
2Кафедра электротехники и вычислительной техники, инженерный факультет, Национальный университет Сингапура, Сингапур
Находите эту статью интересной или хотите обсудить? Scite или оставить комментарий на SciRate.
Абстрактные
Мы инициируем изучение компромиссов между исследованием и эксплуатацией в онлайн-изучении свойств квантовых состояний. Учитывая последовательный доступ оракула к неизвестному квантовому состоянию, в каждом раунде перед нами ставится задача выбрать наблюдаемую из набора действий, направленных на максимизацию ее ожидаемого значения в состоянии (вознаграждение). Информация, полученная о неизвестном состоянии из предыдущих раундов, может использоваться для постепенного улучшения выбора действия, тем самым уменьшая разрыв между вознаграждением и максимальным вознаграждением, достижимым с данным набором действий (сожаление). Мы приводим различные теоретико-информационные нижние границы кумулятивного сожаления, которое должен испытать оптимальный ученик, и показываем, что оно масштабируется как минимум как квадратный корень из числа сыгранных раундов. Мы также исследуем зависимость кумулятивного сожаления от количества доступных действий и размерности лежащего в их основе пространства. Более того, мы показываем стратегии, оптимальные для бандитов с конечным числом рук и общими смешанными состояниями.
[Встраиваемое содержимое]
► Данные BibTeX
► Рекомендации
[1] Т. Латтимор и К. Сепешвари. «Бандитские алгоритмы». Издательство Кембриджского университета. (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] Б. Казале, Г. Ди Мольфетта, Х. Кадри и Л. Ралайвола. «Квантовые бандиты». Квантовая мах. Интел. 2 (2020).
https://doi.org/10.1007/s42484-020-00024-8
[12] Д. Ван, X. Ю, Т. Ли и А. Чайлдс. «Алгоритмы квантовой разведки для многоруких бандитов». В материалах конференции AAAI по искусственному интеллекту. Том 35, страницы 10102–10110. (2021).
[13] П. Ребентрост, Ю. Хамуди, М. Рэй, X. Ван, С. Ян и М. Санта. «Квантовые алгоритмы хеджирования и изучения моделей Изинга». физ. Ред. А 103, 012418 (2021 г.).
https: / / doi.org/ 10.1103 / PhysRevA.103.012418
[14] О. Шамир. «О сложности бандитской линейной оптимизации». В материалах 28-й конференции по теории обучения. Том 40 журнала Proceedings of Machine Learning Research, страницы 1523–1551. ПМЛР (2015).
[15] П. Русмевичиентонг и Дж. Цициклис. «Линейно параметризованные бандиты». Математика исследования операций 35 (2008).
https: / / doi.org/ 10.1287 / moor.1100.0446
[16] Дж. Барри, Д.Т. Барри и С. Ааронсон. «Квантовые частично наблюдаемые марковские процессы принятия решений». физ. Ред. А 90, 032311 (2014).
https: / / doi.org/ 10.1103 / PhysRevA.90.032311
[17] М. Ин, Ю. Фэн и С. Ин. «Оптимальные политики для квантовых марковских процессов принятия решений». Международный журнал автоматизации и вычислений 18, 410–421 (2021).
HTTPS: / / doi.org/ 10.1007 / s11633-021-1278-г
[18] М. Пэрис и Дж. Рехачек. «Квантовая оценка состояния». Издательская компания Спрингер, Инкорпорейтед. (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-х
[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] Ю. Аббаси-Ядкори, Д. Пал и Кс. Сепешвари. «Улучшенные алгоритмы для линейных стохастических бандитов». Достижения в области нейронных систем обработки информации. Том 24. Curran Associates, Inc. (2011).
[29] ТЛ Лай. «Адаптивное распределение лечения и проблема многорукого бандита». Статистические анналы 15, 1091–1114 (1987).
https: / / doi.org/ 10.1214 / AOS / 1176350495
[30] М. Гуцэ, Дж. Кан, Р. Куенг и Дж. А. Тропп. «Томография быстрого состояния с оптимальными границами ошибки». Журнал физики A: Mathematical and Theoretical 53, 204001 (2020).
https: / / doi.org/ 10.1088 / 1751-8121 / ab8111
[31] Т. Латтимор и Б. Хао. «Поиск бандитской фазы». Достижения в области нейронных систем обработки информации. Том 34, страницы 18801–18811. Карран Ассошиэйтс, Инк. (2021).
Цитируется
[1] Zongqi Wan, Zhijie Zhang, Tongyang Li, Jialin Zhang и Xiaoming Sun, «Квантовые многорукие бандиты и стохастические линейные бандиты наслаждаются логарифмическими сожалениями», Arxiv: 2205.14988.
[2] Xinyi Chen, Elad Hazan, Tongyang Li, Zhou Lu, Xinzhao Wang и Rui Yang, «Адаптивное онлайн-обучение квантовым состояниям», Arxiv: 2206.00220.
Приведенные цитаты из САО / НАСА ADS (последнее обновление успешно 2022-07-24 00:26:50). Список может быть неполным, поскольку не все издатели предоставляют подходящие и полные данные о цитировании.
On Цитируемый сервис Crossref Данные о цитировании работ не найдены (последняя попытка 2022-07-24 00:26:48).
Эта статья опубликована в Quantum под Creative Commons Attribution 4.0 International (CC BY 4.0) лицензия. Авторское право остается за первоначальными правообладателями, такими как авторы или их учреждения.
