Title: Budget-Constrained Multi-Armed Bandits with Multiple Plays,
Abstract: We study the multi-armed bandit problem with multiple plays and a budget
constraint for both the stochastic and the adversarial setting. At each round,
exactly $K$ out of $N$ possible arms have to be played (with $1\leq K \leq N$).
In addition to observing the individual rewards for each arm played, the player
also learns a vector of costs which has to be covered with an a-priori defined
budget $B$. The game ends when the sum of current costs associated with the
played arms exceeds the remaining budget.
Firstly, we analyze this setting for the stochastic case, for which we assume
each arm to have an underlying cost and reward distribution with support
$[c_{\min}, 1]$ and $[0, 1]$, respectively. We derive an Upper Confidence Bound
(UCB) algorithm which achieves $O(NK^4 \log B)$ regret.
Secondly, for the adversarial case in which the entire sequence of rewards
and costs is fixed in advance, we derive an upper bound on the regret of order
$O(\sqrt{NB\log(N/K)})$ utilizing an extension of the well-known
$\texttt{Exp3}$ algorithm. We also provide upper bounds that hold with high
probability and a lower bound of order $\Omega((1 - K/N)^2 \sqrt{NB/K})$.