# Censored Semi-Bandits for Resource Allocation

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 48 references that are in the map.
- First posted on arXiv 12 Apr 2021.

## Builds on (most cited first, 18 of 18)

- [Bandits with Knapsacks](https://mlsanity.com/paper/1305.2545/) (2013)
- [Thompson Sampling for Combinatorial Semi-Bandits](https://mlsanity.com/paper/1803.04623/) (2018)
- [Combinatorial Multi-Armed Bandit with General Reward Functions](https://mlsanity.com/paper/1610.06603/) (2016)
- [Online learning in repeated auctions](https://mlsanity.com/paper/1511.05720/) (2015)
- [Optimal Regret Analysis of Thompson Sampling in Stochastic Multi-armed Bandit Problem with Multiple Plays](https://mlsanity.com/paper/1506.00779/) (2015)
- [Statistical Efficiency of Thompson Sampling for Combinatorial Semi-Bandits](https://mlsanity.com/paper/2006.06613/) (2020)
- [Learning Theory and Algorithms for Revenue Optimization in Second-Price Auctions with Reserve](https://mlsanity.com/paper/1310.5665/) (2013)
- [Censored Semi-Bandits: A Framework for Resource Allocation with Censored Feedback](https://mlsanity.com/paper/1909.01504/) (2019)
- [An adaptive stochastic optimization algorithm for resource allocation](https://mlsanity.com/paper/1902.04376/) (2019)
- [Online Algorithm for Unsupervised Sensor Selection](https://mlsanity.com/paper/1901.04676/) (2019)
- [Online Algorithm for Unsupervised Sequential Selection with Contextual Information](https://mlsanity.com/paper/2010.12353/) (2020)
- [Optimal Resource Allocation with Semi-Bandit Feedback](https://mlsanity.com/paper/1406.3840/) (2014)
- [A Better Resource Allocation Algorithm with Semi-Bandit Feedback](https://mlsanity.com/paper/1803.10415/) (2018)
- [Stochastic Network Utility Maximization with Unknown Utilities: Multi-Armed Bandits Approach](https://mlsanity.com/paper/2006.09997/) (2020)
- [Online Learning of Optimal Bidding Strategy in Repeated Multi-Commodity Auctions](https://mlsanity.com/paper/1703.02567/) (2017)
- [Thompson Sampling for Unsupervised Sequential Selection](https://mlsanity.com/paper/2009.07554/) (2020)
- [Multi-Armed Bandits with Censored Consumption of Resources](https://mlsanity.com/paper/2011.00813/) (2020)
- [Network Utility Maximization with Heterogeneous Traffic Flows](https://mlsanity.com/paper/1803.00081/) (2018)

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

- [The Relative Value of Prediction in Algorithmic Decision Making](https://mlsanity.com/paper/2312.08511/) (2023)
- [Bayesian Optimization under Stochastic Delayed Feedback](https://mlsanity.com/paper/2206.09341/) (2022)
- [Sequential Decision Problems with Weak Feedback](https://mlsanity.com/paper/2212.11603/) (2022)
- [Learning to Allocate Resources with Censored Feedback](https://mlsanity.com/paper/2602.06565/) (2026)

## Abstract (arXiv)

We consider the problem of sequentially allocating resources in a censored semi-bandits setup, where the learner allocates resources at each step to the arms and observes loss. The loss depends on two hidden parameters, one specific to the arm but independent of the resource allocation, and the other depends on the allocated resource. More specifically, the loss equals zero for an arm if the resource allocated to it exceeds a constant (but unknown) arm dependent threshold. The goal is to learn a resource allocation that minimizes the expected loss. The problem is challenging because the loss distribution and threshold value of each arm are unknown. We study this setting by establishing its `equivalence' to Multiple-Play Multi-Armed Bandits (MP-MAB) and Combinatorial Semi-Bandits. Exploiting these equivalences, we derive optimal algorithms for our problem setting using known algorithms for MP-MAB and Combinatorial Semi-Bandits. The experiments on synthetically generated data validate the performance guarantees of the proposed algorithms.