# A Better Resource Allocation Algorithm with Semi-Bandit Feedback

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Mar 2018.

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

- [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)
- [Learning to Allocate Resources with Censored Feedback](https://mlsanity.com/paper/2602.06565/) (2026)

## Abstract (arXiv)

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 cut-off. We follow Lattimore et al. (2014) and assume that the probability increases linearly until it equals one, after which allocating more of the resource is wasteful. These cut-off 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(log2 n). Lower bounds we prove show that our upper bound is tight. Simulations demonstrate the superiority of our algorithm.