64806

Автор(ы): 

Автор(ов): 

3

Параметры публикации

Тип публикации: 

Статья в журнале/сборнике

Название: 

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

ISBN/ISSN: 

ISSN 2074-9872

Наименование источника: 

  • Математическая теория игр и ее приложения

Обозначение и номер тома: 

Т. 13, вып. 2

Город: 

  • Петрозаводск

Издательство: 

  • Изд-во ФИЦ "Карельский научный центр РАН"

Год издания: 

2021

Страницы: 

9-39
Аннотация
Рассматривается минимаксная постановка задачи о двуруком бандите в приложении к обработке данных, если для обработки имеются два альтернативных метода с различными априори неизвестными эффективностями. Требуется определить более эффективный метод и обеспечить его преимущественное применение. Для этой цели используется алгоритм зеркального спуска (АЗС). Известно, что минимаксный риск, обеспечиваемый этим алгоритмом, имеет порядок N^{1/2}, где N характеризует количество обрабатываемых данных, причем этот порядок неулучшаем. Нами предложена версия АЗС, позволяющая обрабатывать данные пакетами, что особенно важно, если можно обеспечить параллельную обработку данных. В этом случае полное время обработки определяется количеством обрабатываемых пакетов, а не полным числом данных. Неожиданным оказался результат, что пакетный алгоритм ведет себя не так, как обычный, даже если количество пакетов, на которые разбиты данные, велико. Более того, пакетная версия позволила значительно уменьшить величину минимаксного риска, т.е. повысить качество управления. Для объяснения этого результата мы рассмотрели еще одну пакетную версию АЗС, демонстрирующую поведение, близкое к поведению обычного алгоритма и обеспечивающую близкое значение минимаксного риска. Наши оценки используют инвариантное описание алгоритмов, основанное на гауссовских аппроксимациях доходов в пакетах в области «близких» распределений и получены с помощью моделирования методом Монте-Карло.

Библиографическая ссылка: 

Колногоров А.В., Назин А.В., Шиян Д.Н. Задача о двуруком бандите и пакетная версия алгоритма зеркального спуска / Математическая теория игр и ее приложения. Петрозаводск: Изд-во ФИЦ "Карельский научный центр РАН", 2021. Т. 13, вып. 2 . С. 9-39.