  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.

Machine Learning