Математическая теория игр и её приложения
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



МТИП:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Математическая теория игр и её приложения, 2021, том 13, выпуск 2, страницы 9–39 (Mi mgta279)  

Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)

Задача о двуруком бандите и пакетная версия алгоритма зеркального спуска

Александр В. Колногоровa, Александр В. Назинb, Дмитрий Н. Шиянa

a Новгородский государственный университет им. Ярослава Мудрого, 173003, Великий Новгород, ул. Б.С.-Петербургская, 41
b Институт проблем управления им. В.А. Трапезникова РАН, 117997, Москва, ул. Профсоюзная, 65
Список литературы:
Аннотация: Рассматривается минимаксная постановка задачи о двуруком бандите в приложении к обработке данных, если для обработки имеются два альтернативных метода с различными априори неизвестными эффективностями. Требуется определить более эффективный метод и обеспечить его преимущественное применение. Для этой цели используется алгоритм зеркального спуска (АЗС). Известно, что минимаксный риск, обеспечиваемый этим алгоритмом, имеет порядок $N^{1/2}$, где $N$ характеризует количество обрабатываемых данных, причем этот порядок неулучшаем. Нами предложена версия АЗС, позволяющая обрабатывать данные пакетами, что особенно важно, если можно обеспечить параллельную обработку данных. В этом случае полное время обработки определяется количеством обрабатываемых пакетов, а не полным числом данных. Неожиданным оказался результат, что пакетный алгоритм ведет себя не так, как обычный, даже если количество пакетов, на которые разбиты данные, велико. Более того, пакетная версия позволила значительно уменьшить величину минимаксного риска, т.е. повысить качество управления. Для объяснения этого результата мы рассмотрели еще одну пакетную версию АЗС, демонстрирующую поведение, близкое к поведению обычного алгоритма и обеспечивающую близкое значение минимаксного риска. Наши оценки используют инвариантное описание алгоритмов, основанное на гауссовских аппроксимациях доходов в пакетах в области «близких» распределений и получены с помощью моделирования методом Монте-Карло.
Ключевые слова: задача о двуруком бандите, минимаксный подход, алгоритм зеркального спуска, EXP3, пакетная обработка.
Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований 20-01-00062
Российский научный фонд 16-11-10015
Исследование выполнено при финансовой поддержке РФФИ, научный проект номер 20-01-00062. Исследование выполнено при финансовой поддержке РНФ, научный проект номер 16-11-10015.
Поступила в редакцию: 20.11.2020
Исправленный вариант: 08.12.2020
Принята в печать: 01.03.2021
Тип публикации: Статья
УДК: 519.832, 519.245
ББК: 22.18
Образец цитирования: Александр В. Колногоров, Александр В. Назин, Дмитрий Н. Шиян, “Задача о двуруком бандите и пакетная версия алгоритма зеркального спуска”, МТИП, 13:2 (2021), 9–39
Цитирование в формате AMSBIB
\RBibitem{KolNazShi21}
\by Александр~В.~Колногоров, Александр~В.~Назин, Дмитрий~Н.~Шиян
\paper Задача о двуруком бандите и пакетная версия алгоритма зеркального спуска
\jour МТИП
\yr 2021
\vol 13
\issue 2
\pages 9--39
\mathnet{http://mi.mathnet.ru/mgta279}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/mgta279
  • https://www.mathnet.ru/rus/mgta/v13/i2/p9
  • Эта публикация цитируется в следующих 2 статьяx:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Математическая теория игр и её приложения
    Статистика просмотров:
    Страница аннотации:221
    PDF полного текста:105
    Список литературы:21
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024