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

Рассматривается применение алгоритма зеркального спуска (АЗС) в задаче об одноруком бандите в минимаксной постановке применительно к обработке данных. Данная задача известна также как игра с природой, в которой платежной функцией игрока является математическое ожидание полного дохода. Игроку необходимо в процессе управления определить наиболее эффективный метод из двух доступных и обеспечить его преимущественное применение. При этом априорная эффективность одного из методов известна. В данной статье рассмотрена модификация АЗС, позволяющая улучшить эффективность управления за счет использования дополнительной информации. Предложенная стратегия сохраняет характерное свойство стратегий для одноруких бандитов – если известное действие будет однажды применено, то оно будет применяться до конца управления. Рассмотрены модификации для алгоритма для одиночной обработки и для его пакетной версии. Пакетная обработка интересна тем, что полное время обработки определяется количеством пакетов, а не исходным количеством данных, при возможности обеспечить параллельную обработку данных в пакетах. Для предложенных алгоритмов с помощью моделирования методом Монте-Карло были вычислены оптимальные значения настраиваемых параметров и получены оценки минимаксного риска.