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

В задачах многорукого бандита (MAB) с ограниченным бюджетом действия обучающегося являются затратными и ограничены фиксированным бюджетом. Поэтому оптимальная политика эксплуатации может заключаться не в многократном выборе оптимального рычага, как в других вариантах задач MAB, а в выборе последовательности различных рычагов, максимизирующей суммарное вознаграждение агента в пределах бюджета. Это отличие от существующих моделей MAB означает необходимость новых подходов к максимизации суммарного вознаграждения. В связи с этим мы разрабатываем две политики выбора рычагов: (i) KUBE и (ii) дробную KUBE. В то время как первая в наших экспериментальных условиях обеспечивает производительность до 40% выше, вторая требует меньших вычислительных затрат. Мы также доказываем логарифмические верхние границы для сожаления обеих политик и показываем, что эти границы асимптотически оптимальны (то есть отличаются от наилучшего возможного сожаления лишь на постоянный множитель).