|
Математическая теория игр и её приложения, 2021, том 13, выпуск 2, страницы 9–39
(Mi mgta279)
|
|
|
|
Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)
Задача о двуруком бандите и пакетная версия алгоритма зеркального спуска
Александр В. Колногоровa, Александр В. Назинb, Дмитрий Н. Шиянa a Новгородский государственный университет им. Ярослава Мудрого, 173003, Великий Новгород, ул. Б.С.-Петербургская, 41
b Институт проблем управления им. В.А. Трапезникова РАН, 117997, Москва, ул. Профсоюзная, 65
Аннотация:
Рассматривается минимаксная постановка задачи о двуруком бандите в приложении к обработке данных, если для обработки имеются два альтернативных метода с различными априори неизвестными эффективностями. Требуется определить более эффективный метод и обеспечить его преимущественное применение. Для этой цели используется алгоритм зеркального спуска (АЗС). Известно, что минимаксный риск, обеспечиваемый этим алгоритмом, имеет порядок $N^{1/2}$, где $N$ характеризует количество обрабатываемых данных, причем этот порядок неулучшаем. Нами предложена версия АЗС, позволяющая обрабатывать данные пакетами, что особенно важно, если можно обеспечить параллельную обработку данных. В этом случае полное время обработки определяется количеством обрабатываемых пакетов, а не полным числом данных. Неожиданным оказался результат, что пакетный алгоритм ведет себя не так, как обычный, даже если количество пакетов, на которые разбиты данные, велико. Более того, пакетная версия позволила значительно уменьшить величину минимаксного риска, т.е. повысить качество управления. Для объяснения этого результата мы рассмотрели еще одну пакетную версию АЗС, демонстрирующую поведение, близкое к поведению обычного алгоритма и обеспечивающую близкое значение минимаксного риска. Наши оценки используют инвариантное описание алгоритмов, основанное на гауссовских аппроксимациях доходов в пакетах в области «близких» распределений и получены с помощью моделирования методом Монте-Карло.
Ключевые слова:
задача о двуруком бандите, минимаксный подход, алгоритм зеркального спуска, EXP3, пакетная обработка.
Поступила в редакцию: 20.11.2020 Исправленный вариант: 08.12.2020 Принята в печать: 01.03.2021
Образец цитирования:
Александр В. Колногоров, Александр В. Назин, Дмитрий Н. Шиян, “Задача о двуруком бандите и пакетная версия алгоритма зеркального спуска”, МТИП, 13:2 (2021), 9–39
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/mgta279 https://www.mathnet.ru/rus/mgta/v13/i2/p9
|
Статистика просмотров: |
Страница аннотации: | 221 | PDF полного текста: | 105 | Список литературы: | 21 |
|