Budget-Constrained Bandits over General Cost and Reward Distributions
This addresses resource allocation in applications like online advertising or healthcare, offering a general model with tight regret bounds, though it builds incrementally on existing bandit frameworks.
The paper tackles the budget-constrained bandit problem with correlated and heavy-tailed cost-reward pairs, achieving O(log B) regret for a budget B by exploiting correlation via linear estimation.
We consider a budget-constrained bandit problem where each arm pull incurs a random cost, and yields a random reward in return. The objective is to maximize the total expected reward under a budget constraint on the total cost. The model is general in the sense that it allows correlated and potentially heavy-tailed cost-reward pairs that can take on negative values as required by many applications. We show that if moments of order $(2+γ)$ for some $γ> 0$ exist for all cost-reward pairs, $O(\log B)$ regret is achievable for a budget $B>0$. In order to achieve tight regret bounds, we propose algorithms that exploit the correlation between the cost and reward of each arm by extracting the common information via linear minimum mean-square error estimation. We prove a regret lower bound for this problem, and show that the proposed algorithms achieve tight problem-dependent regret bounds, which are optimal up to a universal constant factor in the case of jointly Gaussian cost and reward pairs.