# Budget-Constrained Multi-Armed Bandits with Multiple Plays

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Nov 2017.

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

- [Bandit Algorithms for Precision Medicine](https://mlsanity.com/paper/2108.04782/) (2021)
- [Online Experimental Design With Estimation-Regret Trade-off Under Network Interference](https://mlsanity.com/paper/2412.03727/) (2024)
- [Budgeted Combinatorial Multi-Armed Bandits](https://mlsanity.com/paper/2202.03704/) (2022)
- [Versatile Dueling Bandits: Best-of-both-World Analyses for Online Learning from Preferences](https://mlsanity.com/paper/2202.06694/) (2022)
- [Fast rates for prediction with limited expert advice](https://mlsanity.com/paper/2110.14485/) (2021)
- [The Survival Bandit Problem](https://mlsanity.com/paper/2206.03019/) (2022)
- [Constant regret for sequence prediction with limited advice](https://mlsanity.com/paper/2210.02256/) (2022)
- [Diversity-Based Recruitment in Crowdsensing By Combinatorial Multi-Armed Bandits](https://mlsanity.com/paper/2312.15729/) (2023)
- [Design-Based Bandits Under Network Interference: Trade-Off Between Regret and Statistical Inference](https://mlsanity.com/paper/2510.07646/) (2025)
- [TSEC: a framework for online experimentation under experimental constraints](https://mlsanity.com/paper/2101.06592/) (2021)
- [Asymptotically Optimal Bandits under Weighted Information](https://mlsanity.com/paper/2105.14114/) (2021)
- [MADDM: Multi-Advisor Dynamic Binary Decision-Making by Maximizing the Utility](https://mlsanity.com/paper/2305.08664/) (2023)
- [Online Learning with Probing for Sequential User-Centric Selection](https://mlsanity.com/paper/2507.20112/) (2025)

## Abstract (arXiv)

We study the multi-armed bandit problem with multiple plays and a budget constraint for both the stochastic and the adversarial setting. At each round, exactly K out of N possible arms have to be played (with 1≤ K ≤ N). In addition to observing the individual rewards for each arm played, the player also learns a vector of costs which has to be covered with an a-priori defined budget B. The game ends when the sum of current costs associated with the played arms exceeds the remaining budget. Firstly, we analyze this setting for the stochastic case, for which we assume each arm to have an underlying cost and reward distribution with support [cmin, 1] and [0, 1], respectively. We derive an Upper Confidence Bound (UCB) algorithm which achieves O(NK4 log B) regret. Secondly, for the adversarial case in which the entire sequence of rewards and costs is fixed in advance, we derive an upper bound on the regret of order O(√NBlog(N/K)) utilizing an extension of the well-known textttExp3 algorithm. We also provide upper bounds that hold with high probability and a lower bound of order Omega((1 - K/N)2 √NB/K).