A Better Resource Allocation Algorithm with Semi-Bandit Feedback

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(log2 n). Lower bounds we prove show that our upper bound is tight. Simulations demonstrate the superiority of our algorithm.