Optimal Resource Allocation with Semi-Bandit Feedback

Tor Lattimore, Koby Crammer, Csaba Szepesvari
Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence, PMLR R12:126-135, 2014.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR12-lattimore14a, title = {Optimal Resource Allocation with Semi-Bandit Feedback}, author = {Lattimore, Tor and Crammer, Koby and Szepesvari, Csaba}, booktitle = {Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence}, pages = {126--135}, year = {2014}, editor = {Zhang, Nevin L. and Tian, Jin}, volume = {R12}, series = {Proceedings of Machine Learning Research}, month = {23--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r12/main/assets/lattimore14a/lattimore14a.pdf}, url = {https://proceedings.mlr.press/r12/lattimore14a.html}, abstract = {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.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Optimal Resource Allocation with Semi-Bandit Feedback %A Tor Lattimore %A Koby Crammer %A Csaba Szepesvari %B Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2014 %E Nevin L. Zhang %E Jin Tian %F pmlr-vR12-lattimore14a %I PMLR %P 126--135 %U https://proceedings.mlr.press/r12/lattimore14a.html %V R12 %X 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. %Z Reissued by PMLR on 04 October 2026.
APA
Lattimore, T., Crammer, K. & Szepesvari, C.. (2014). Optimal Resource Allocation with Semi-Bandit Feedback. Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R12:126-135 Available from https://proceedings.mlr.press/r12/lattimore14a.html. Reissued by PMLR on 04 October 2026.

Related Material