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

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