2024/06/02 by Naveen Raman, Raman, Naveen, Ryan Shi +3 · 3 citations
Computer Science · Decision Sciences · Engineering · #Advanced Bandit Algorithms Research #Artificial Intelligence (cs.AI) #Cognitive Radio Networks and Spectrum Sensing #Computers and Society (cs.CY) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Smart Grid Energy Management
paper · pdf · doi:10.48550/arxiv.2406.00738
openalex publication_date 2024/06/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Restless multi-armed bandits (RMAB) extend multi-armed bandits so pulling an arm impacts future states. Despite the success of RMABs, a key limiting assumption is the separability of rewards into a sum across arms. We address this deficiency by proposing restless-multi-armed bandit with global rewards (RMAB-G), a generalization of RMABs to global non-separable rewards. To solve RMAB-G, we develop the Linear- and Shapley-Whittle indices, which extend Whittle indices from RMABs to RMAB-Gs. We prove approximation bounds but also point out how these indices could fail when reward functions are highly non-linear. To overcome this, we propose two sets of adaptive policies: the first computes indices iteratively, and the second combines indices with Monte-Carlo Tree Search (MCTS). Empirically, we demonstrate that our proposed policies outperform baselines and index-based policies with synthetic data and real-world data from food rescue.