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

Рассматриваются две стохастические задачи о многоруком бандите. Одна «классическая», с конечным числом действий и со случайными потерями (в частном случае, бинарными, принимающими значения 0 или 1). Другая задача, как обобщение предыдущей, содержит потери, зависящие еще и от состояния наблюдаемой стационарной конечной марковской цепи. На основе оптимизационного подхода получены рекуррентные алгоритмы зеркального спуска. Доказаны верхние границы превышения средних потерь над их минимальным значением. Обсуждаются также и нижние границы для этих задач. Доказывается, что верхние и нижние границы совпадают с точностью до логарифмического множителя.