# Combinatorial Multi-armed Bandits for Resource Allocation

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 11 references that are in the map.
- First posted on arXiv 10 May 2021.

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

- [Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically Triggered Arms](https://mlsanity.com/paper/1407.8339/) (2014)
- [Bandits and Experts in Metric Spaces](https://mlsanity.com/paper/1312.1277/) (2013)
- [Improving Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms and Its Applications](https://mlsanity.com/paper/1703.01610/) (2017)
- [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)

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

- [Artificial Replay: A Meta-Algorithm for Harnessing Historical Data in Bandits](https://mlsanity.com/paper/2210.00025/) (2022)
- [Combinatorial Multivariant Multi-Armed Bandits with Applications to Episodic Reinforcement Learning and Beyond](https://mlsanity.com/paper/2406.01386/) (2024)
- [Offline Learning for Combinatorial Multi-armed Bandits](https://mlsanity.com/paper/2501.19300/) (2025)
- [On Bits and Bandits: Quantifying the Regret-Information Trade-off](https://mlsanity.com/paper/2405.16581/) (2024)
- [Multi-Task Combinatorial Bandits for Budget Allocation](https://mlsanity.com/paper/2409.00561/) (2024)
- [Strategic Multi-Armed Bandit Problems Under Debt-Free Reporting](https://mlsanity.com/paper/2501.16018/) (2025)
- [Simultaneously Achieving Group Exposure Fairness and Within-Group Meritocracy in Stochastic Bandits](https://mlsanity.com/paper/2402.05575/) (2024)
- [Q-Learning with Shift-Aware Upper Confidence Bound in Non-Stationary Reinforcement Learning](https://mlsanity.com/paper/2510.03181/) (2025)
- [Constant or logarithmic regret in asynchronous multiplayer bandits](https://mlsanity.com/paper/2305.19691/) (2023)
- [Learning to Allocate Resources with Censored Feedback](https://mlsanity.com/paper/2602.06565/) (2026)

## Abstract (arXiv)

We study the sequential resource allocation problem where a decision maker repeatedly allocates budgets between resources. Motivating examples include allocating limited computing time or wireless spectrum bands to multiple users (i.e., resources). At each timestep, the decision maker should distribute its available budgets among different resources to maximize the expected reward, or equivalently to minimize the cumulative regret. In doing so, the decision maker should learn the value of the resources allocated for each user from feedback on each user's received reward. For example, users may send messages of different urgency over wireless spectrum bands; the reward generated by allocating spectrum to a user then depends on the message's urgency. We assume each user's reward follows a random process that is initially unknown. We design combinatorial multi-armed bandit algorithms to solve this problem with discrete or continuous budgets. We prove the proposed algorithms achieve logarithmic regrets under semi-bandit feedback.