A Better Resource Allocation Algorithm with SemiBandit Feedback
[edit]
Proceedings of Algorithmic Learning Theory, PMLR 83:268320, 2018.
Abstract
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 cutoff. We follow
\cite{LCS} and assume that the probability increases
linearly until it equals one, after which allocating more of the
resource is wasteful. These cutoff 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.
Related Material


