Многоорукий бандит с бюджетным ограничением и переменными затратами

Мы исследуем задачи о многооруком бандите с бюджетным ограничением и переменными затратами (MAB-BV). В этой постановке выбор руки приносит случайную награду и одновременно связан со случайными затратами, а цель алгоритма состоит в выборе последовательности рук для максимизации ожидаемой суммарной награды при соблюдении бюджетного ограничения на затраты, связанные с их выбором. Эта новая постановка более точно моделирует многие интернет-приложения (например, обмен рекламой, поиск с рекламными объявлениями и облачные вычисления), чем предыдущие постановки, в которых выбор руки либо не требовал затрат, либо сопровождался фиксированными затратами. Мы предлагаем два алгоритма для этой постановки, основанных на верхних доверительных границах (UCB). Первый алгоритм требует априорного знания нижней границы ожидаемых затрат при вычислении члена исследования. Второй алгоритм устраняет эту необходимость, оценивая минимальные ожидаемые затраты по эмпирическим наблюдениям, и поэтому может применяться в более реалистичных задачах, где априорные знания недоступны. Мы доказываем, что оба алгоритма обладают хорошими способностями к обучению и имеют оценки сожаления порядка O(ln B). Кроме того, мы показываем, что применение предложенных алгоритмов к предыдущей постановке с фиксированными затратами, которую можно рассматривать как частный случай нашей постановки, позволяет улучшить ранее полученную оценку сожаления. Результаты моделирования торгов в реальном времени на рынке рекламного обмена подтверждают эффективность алгоритмов и согласуются с теоретическим анализом.