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

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