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

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