Optimal Resource Allocation with Semi-Bandit Feedback
This work addresses resource allocation for recurring jobs with semi-bandit feedback, which is incremental as it builds on existing bandit literature but introduces a new model and algorithm.
The paper tackles a sequential resource allocation problem with unknown job difficulties, aiming to maximize completed jobs using a linear probability model with a cutoff. It presents the first algorithm for this problem, proving upper and lower regret bounds and showing that an optimistic algorithm can significantly improve learning speed in resource-laden scenarios.
We study a sequential resource allocation problem involving a fixed number of recurring jobs. At each time-step the manager should distribute available resources among the jobs in order to maximise the expected number of completed jobs. Allocating more resources to a given job increases the probability that it completes, but with a cut-off. Specifically, we assume a linear model where the probability increases linearly until it equals one, after which allocating additional resources is wasteful. We assume the difficulty of each job is unknown and present the first algorithm for this problem and prove upper and lower bounds on its regret. Despite its apparent simplicity, the problem has a rich structure: we show that an appropriate optimistic algorithm can improve its learning speed dramatically beyond the results one normally expects for similar problems as the problem becomes resource-laden.