ИСТИНА

Ряд опубликованных в последнее время работ посвящен задаче о многоруком бандите. В докладе будет обсуждаться одна из версий этой задачи. Мы будем рассматривать простое семейство марковских игровых автоматов, предполагая, что отсутствует дисконтирование и присутствуют штрафы за переход от одного игрового автомата к другому. Также будем предполагать, что марковские цепи, задающие эволюцию игровых автоматов, имеют конечное пространство состояний. Оптимальной считается стратегия, имеющая наибольшую среднюю прибыль за единицу времени на бесконечном временном отрезке. Основным результатом доклада является теорема о том, что в данной задаче оптимальная стратегия может быть задана с помощью индекса Гиттинса в случае естественного предположения о неотрицательности штрафов.