Global Rewards in Restless Multi-Armed Bandits
This addresses a key deficiency in RMABs for applications like resource allocation, though it is an incremental extension of existing methods.
The paper tackles the limitation of separable rewards in restless multi-armed bandits by proposing RMAB-G with global non-separable rewards, developing Linear- and Shapley-Whittle indices and adaptive policies that outperform baselines in synthetic and real-world food rescue data.
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.