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

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