Политики «сначала ε» для многоруких бандитов с ограниченным бюджетом

Мы вводим модель многорукого бандита (MAB) с ограниченным бюджетом, описывающую ситуации, в которых действия обучающегося являются затратными и ограничены фиксированным бюджетом, несоизмеримым с вознаграждениями, получаемыми от бандитного автомата, а также описываем первый алгоритм решения этой задачи. Поскольку обучающийся располагает ограниченным бюджетом, продолжительность задачи конечна. Следовательно, оптимальная политика эксплуатации заключается не в многократном выборе оптимального рычага, а в выборе комбинации рычагов, максимизирующей суммарное вознаграждение агента в пределах бюджета. Поэтому необходимо оценивать вознаграждения всех рычагов, поскольку любой из них может входить в оптимальную комбинацию. Это отличие от существующих моделей многорукого бандита означает необходимость новых подходов к максимизации суммарного вознаграждения. Для этого мы предлагаем алгоритм «сначала ε», в котором первая ε-доля бюджета используется исключительно для оценки вознаграждений рычагов (исследование), а оставшаяся доля 1 − ε — для максимизации получаемого вознаграждения на основе этих оценок (эксплуатация). Мы выводим границы потерь алгоритма для общих и равномерных методов исследования и сравниваем его эффективность с традиционными алгоритмами многорукого бандита при различных распределениях вознаграждений и затрат, показывая, что он превосходит остальные методы на величину до 50%.