A Better Resource Allocation Algorithm with Semi-Bandit Feedback
This work addresses resource allocation in multi-armed bandit settings, providing a more efficient algorithm for applications like online advertising or network routing, but it is incremental as it builds on existing models and improves bounds.
The paper tackles the sequential resource allocation problem with semi-bandit feedback, where allocating more resource to an arm increases its success probability linearly up to a cut-off, and presents an algorithm that achieves a regret upper bound of O(log n), improving over the previous best of O(log^2 n), with simulations showing its superiority.
We study a sequential resource allocation problem between a fixed number of arms. On each iteration the algorithm distributes a resource among the arms in order to maximize the expected success rate. Allocating more of the resource to a given arm increases the probability that it succeeds, yet with a cut-off. We follow Lattimore et al. (2014) and assume that the probability increases linearly until it equals one, after which allocating more of the resource is wasteful. These cut-off values are fixed and unknown to the learner. We present an algorithm for this problem and prove a regret upper bound of $O(\log n)$ improving over the best known bound of $O(\log^2 n)$. Lower bounds we prove show that our upper bound is tight. Simulations demonstrate the superiority of our algorithm.