Публикации
Д.Н. Шиян.
Алгоритм зеркального спуска в задаче об одноруком бандите
// Математическая Теория Игр и ее Приложения, т. 15, в. 3. 2023. C. 88-106
Ключевые слова: задача о двуруком бандите, задача об одноруком бандите, минимаксный подход, алгоритм зеркального спуска, EXP3, пакетная обработка
Рассматривается применение алгоритма зеркального спуска (АЗС) в задаче об одноруком бандите в минимаксной постановке применительно к обработке данных. Данная задача известна также как игра с природой, в которой платежной функцией игрока является математическое ожидание полного дохода. Игроку необходимо в процессе управления определить наиболее эффективный метод из двух доступных и обеспечить его преимущественное применение. При этом априорная эффективность одного из методов известна. В данной статье рассмотрена модификация АЗС, позволяющая улучшить эффективность управления за счет использования дополнительной информации. Предложенная стратегия сохраняет характерное свойство стратегий для одноруких бандитов - если известное действие будет однажды применено, то оно будет применяться до конца управления. Рассмотрены модификации для алгоритма для одиночной обработки и для его пакетной версии. Пакетная обработка интересна тем, что полное время обработки определяется количеством пакетов, а не исходным количеством данных, при возможности обеспечить параллельную обработку данных в пакетах. Для предложенных алгоритмов с помощью моделирования методом Монте-Карло были вычислены оптимальные значения настраиваемых параметров и получены оценки минимаксного риска.
Индексируется в РИНЦ, РИНЦ (WS)
Алгоритм зеркального спуска в задаче об одноруком бандите (747 Kb, скачиваний: 68)
Последние изменения: 23 октября 2023