# Multiple-play Stochastic Bandits with Prioritized Arm Capacity Sharing

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 32 references that are in the map.
- First posted on arXiv 25 Dec 2025.

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

- [Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically Triggered Arms](https://mlsanity.com/paper/1407.8339/) (2014)
- [Combinatorial Cascading Bandits](https://mlsanity.com/paper/1507.04208/) (2015)
- [Optimal Regret Analysis of Thompson Sampling in Stochastic Multi-armed Bandit Problem with Multiple Plays](https://mlsanity.com/paper/1506.00779/) (2015)
- [Matroid Bandits: Fast Combinatorial Optimization with Learning](https://mlsanity.com/paper/1403.5045/) (2014)
- [Multiple-Play Bandits in the Position-Based Model](https://mlsanity.com/paper/1606.02448/) (2016)
- [Multi-Player Multi-Armed Bandits with Finite Shareable Resources Arms: Learning Algorithms & Applications](https://mlsanity.com/paper/2204.13502/) (2022)
- [Competing for Shareable Arms in Multi-Player Multi-Armed Bandits](https://mlsanity.com/paper/2305.19158/) (2023)
- [Adversarial Sleeping Bandit Problems with Multiple Plays: Algorithm and Ranking Application](https://mlsanity.com/paper/2307.14549/) (2023)

## Abstract (arXiv)

This paper proposes a variant of multiple-play stochastic bandits tailored to resource allocation problems arising from LLM applications, edge intelligence, etc. The model is composed of M arms and K plays. Each arm has a stochastic number of capacities, and each unit of capacity is associated with a reward function. Each play is associated with a priority weight. When multiple plays compete for the arm capacity, the arm capacity is allocated in a larger priority weight first manner. Instance independent and instance dependent regret lower bounds of Omega( α1 σ √KM T ) and Omega(α1 σ2 fracMDelta ln T) are proved, where α1 is the largest priority weight and σ characterizes the reward tail. When model parameters are given, we design an algorithm named textttMSB-PRS-OffOpt to locate the optimal play allocation policy with a computational complexity of O(MK3). Utilizing textttMSB-PRS-OffOpt as a subroutine, an approximate upper confidence bound (UCB) based algorithm is designed, which has instance independent and instance dependent regret upper bounds matching the corresponding lower bound up to factors of  √K ln KT  and α1 K2 respectively. To this end, we address nontrivial technical challenges arising from optimizing and learning under a special nonlinear combinatorial utility function induced by the prioritized resource sharing mechanism.