Многорукие бандиты с несколькими выборами и ограничением бюджета

Мы исследуем задачу многорукого бандита с несколькими выборами и ограничением бюджета как в стохастической, так и в состязательной постановке. На каждом раунде необходимо выбрать ровно K из N возможных рук (1 ≤ K ≤ N). Помимо наблюдения индивидуальных выигрышей каждой выбранной руки, игрок также получает вектор затрат, которые должны покрываться заранее заданным бюджетом B. Игра заканчивается, когда сумма текущих затрат, связанных с выбранными руками, превышает оставшийся бюджет. Сначала мы анализируем эту постановку в стохастическом случае, предполагая, что каждая рука имеет лежащие в основе распределения затрат и выигрышей с носителями [c_min, 1] и [0, 1] соответственно. Мы выводим алгоритм верхней доверительной границы (Upper Confidence Bound, UCB), обеспечивающий сожаление O(NK^4 log B). Затем для состязательного случая, в котором вся последовательность выигрышей и затрат фиксирована заранее, мы выводим верхнюю границу сожаления порядка O(√(NB log(N/K))), используя расширение хорошо известного алгоритма Exp3. Также приведены верхние границы, справедливые с высокой вероятностью, и нижняя граница порядка Ω((1 − K/N)^2 √(NB/K)).