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

Мы исследуем интересный вариант задачи стохастического многорукого бандита, называемый задачей Fair-SMAB, в котором требуется выбирать каждую ручку не менее заданной доли от общего числа доступных раундов. Мы изучаем взаимосвязь между обучением и справедливостью через заранее заданный вектор, определяющий доли гарантированных выборов каждой ручки. Мы вводим регрет с учетом справедливости, называемый r-регретом, который учитывает указанные ограничения справедливости и естественным образом расширяет традиционное понятие регрета. Наш основной результат заключается в характеристике класса алгоритмов Fair-SMAB двумя параметрами: допустимым уровнем несправедливости и алгоритмом обучения, используемым как алгоритм-черный ящик. Для этого класса мы устанавливаем гарантию справедливости, выполняющуюся равномерно по времени независимо от выбора алгоритма обучения. В частности, если в качестве алгоритма обучения используется UCB1, мы показываем, что предложенный алгоритм достигает r-регрета порядка O(ln T). Наконец, мы оцениваем стоимость справедливости с точки зрения традиционного понятия регрета.