Multiple-play Stochastic Bandits with Prioritized Arm Capacity Sharing

2025/12/25 by Hong Xie, Xie, Hong, Haoran Gu +7
Decision Sciences · Computer Science · #Advanced Bandit Algorithms Research #Reinforcement Learning in Robotics #Stochastic Gradient Optimization Techniques

paper · doi:10.48550/arxiv.2512.21626

Abstract

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 Ω( α₁ σ√(KM T) ) and Ω(α₁ σ² \fracMΔ ln T) are proved, where α₁ is the largest priority weight and σ characterizes the reward tail. When model parameters are given, we design an algorithm named MSB-PRS-OffOpt to locate the optimal play allocation policy with a computational complexity of O(MK³). Utilizing MSB-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 α₁ K² 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.

Citations

• Adversarial Sleeping Bandit Problems with Multiple Plays: Algorithm and Ranking Application
• Competing for Shareable Arms in Multi-Player Multi-Armed Bandits
• Multi-Player Multi-Armed Bandits with Finite Shareable Resources Arms: Learning Algorithms & Applications
• Multiple-Play Bandits in the Position-Based Model
• Combinatorial Cascading Bandits
• Optimal Regret Analysis of Thompson Sampling in Stochastic Multi-armed\n Bandit Problem with Multiple Plays
• Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically\n Triggered Arms
• Matroid Bandits: Fast Combinatorial Optimization with Learning
• Cosmological parameters from large scale structure observations

Related

• Multiple-Play Stochastic Bandits with Shareable Finite-Capacity Arms
• Bandits with Dynamic Arm-acquisition Costs
• Multi-agent Multi-armed Bandits with Stochastic Sharable Arm Capacities
• Finite-Time Analysis of Round-Robin Kullback-Leibler Upper Confidence Bounds for Optimal Adaptive Allocation with Multiple Plays and Markovian Rewards
• Deterministic Sequencing of Exploration and Exploitation for Multi-Armed Bandit Problems