# Optimal Resource Allocation with Semi-Bandit Feedback

arXiv: https://arxiv.org/abs/1406.3840 · HTML: https://mlsanity.com/paper/1406.3840/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Jun 2014.

## Built on by (most cited first, 6 of 6)

- [Artificial Replay: A Meta-Algorithm for Harnessing Historical Data in Bandits](https://mlsanity.com/paper/2210.00025/) (2022)
- [Censored Semi-Bandits for Resource Allocation](https://mlsanity.com/paper/2104.05781/) (2021)
- [BORA: Bayesian Optimization for Resource Allocation](https://mlsanity.com/paper/2210.05977/) (2022)
- [Allocating Divisible Resources on Arms with Unknown and Random Rewards](https://mlsanity.com/paper/2306.16578/) (2023)
- [Online Budget Allocation with Censored Semi-Bandit Feedback](https://mlsanity.com/paper/2508.05844/) (2025)
- [Learning to Allocate Resources with Censored Feedback](https://mlsanity.com/paper/2602.06565/) (2026)

## Abstract (arXiv)

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.