Бандиты с ограниченным бюджетом при общих распределениях затрат и вознаграждений

Мы рассматриваем задачу о бандитах с ограниченным бюджетом, в которой каждое извлечение руки связано со случайными затратами и приносит случайное вознаграждение. Цель состоит в максимизации суммарного ожидаемого вознаграждения при ограничении на бюджет суммарных затрат. Модель является общей, поскольку допускает коррелированные и потенциально имеющие тяжёлые хвосты пары «затраты–вознаграждение», которые могут принимать отрицательные значения, что необходимо во многих приложениях. Мы показываем, что если для всех пар «затраты–вознаграждение» существуют моменты порядка (2+γ) при некотором γ>0, то для бюджета B>0 достижимо сожаление порядка O(log B). Для получения точных оценок сожаления мы предлагаем алгоритмы, использующие корреляцию между затратами и вознаграждением каждой руки посредством извлечения общей информации с помощью линейной оценки методом наименьших среднеквадратичных ошибок. Мы доказываем нижнюю границу для сожаления в данной задаче и показываем, что предложенные алгоритмы достигают точных зависящих от задачи оценок сожаления, которые оптимальны с точностью до универсального постоянного множителя в случае совместно гауссовских пар затрат и вознаграждений.