Research map / Bandits and online learning / Multi-armed bandits
Global Rewards in Restless Multi-Armed Bandits
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Generalizes restless multi-armed bandits to non-separable global rewards (RMAB-G) and proposes Linear-/Shapley-Whittle indices plus iterative and MCTS-based adaptive policies, evaluated on synthetic and food rescue data.
Problem
Standard restless multi-armed bandits assume rewards are separable across arms, which fails for real objectives like food rescue trip completion where only one volunteer needs to accept a trip.
Approach
Introduce RMAB-G with a submodular global reward added to per-arm rewards; extend Whittle indices via linear (marginal) and Shapley-value linearizations, then make policies adaptive via iterative index recomputation and MCTS with Whittle-index rollouts.
Key results
- Iterative and MCTS Shapley-Whittle policies are best on synthetic rewards, outperforming Linear-Whittle by 56% on non-linear rewards.
- Best policy is within 3% of optimal for N=4 across all rewards.
- On food rescue notifications (N=100, K=50), Linear Whittle reaches 1.932 normalized reward vs 0.975 for vanilla Whittle; all proposed policies beat baselines by at least 5%.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Iterative or MCTS Shapley-Whittle instead of baseline policies | RMAB-G food rescue policies · Food rescue Notifications and Phone Calls | normalized reward: All of our policies outperform all baselines by at least 5%. | Helped |
| Use Iterative Shapley-Whittle instead of other policies | RMAB-G food rescue policies · Food rescue Phone Calls | normalized reward: 1.294 $\pm$ 0.009 | Helped |
| Reduce Shapley estimation samples from 1000 to 100, 10, or 1 (ablation) | Iterative Shapley-Whittle · Synthetic data | normalized reward | No clear effect |
| Reduce MCTS iterations from 400 to 40 or 4 (ablation) | MCTS Shapley-Whittle · Synthetic data | normalized reward | Mixed |
| Increase vanilla MCTS search depth from 1K to 2K or 4K (ablation) | Vanilla MCTS · Synthetic Max reward (N=10, K=5) | normalized reward | Hurt |
| Increase vanilla MCTS iterations from 50, 100, or 200 to 400 (ablation) | Vanilla MCTS · Synthetic Max reward (N=10, K=5) | normalized reward | Helped |
| Increase DQN training epochs from 50 to 100, 200, or 400 (ablation) | DQN · Synthetic data | normalized reward | No clear effect |
| Vary transition parameter q across 0, 0.25, 0.5, 0.75, and 1.0 (ablation) | RMAB-G policies · Synthetic Max reward | normalized reward | No clear effect |
| Use adaptive policies rather than Linear-Whittle for highly non-linear rewards | RMAB-G policies · Synthetic Subset reward, N=10 | normalized reward: 56% | Helped |
| Vary the global-versus-individual reward weight alpha across 0, 0.25, 0.5, 0.75, and 1.0 (ablation) | RMAB-G policies · Synthetic Max reward | normalized reward | No clear effect |
| Increase budget K from 2 to 5 or 8 (ablation) | Iterative Shapley-Whittle versus Iterative Linear-Whittle · Synthetic Max reward, N=10 | normalized reward | Mixed |
| Use MCTS Shapley-Whittle instead of Linear-Whittle | RMAB-G policies · Synthetic rewards, N=25 and N=100 | normalized reward | Helped |
Surprising findings
- Vanilla Whittle index performs close to random on food rescue notifications (0.975 normalized), showing separable indices ignore the global reward.
- Increasing MCTS depth lowers performance, attributed to stochasticity in rewards and large state space.
Limitations
- Adaptive policies (iterative, MCTS) lack theoretical guarantees.
- Empirical evaluation limited to one real-world dataset (food rescue).
- Analysis assumes global rewards are monotonic and submodular.
Experimental setup
Datasets: synthetic RMAB-G instances (Linear, Probability, Max, Subset rewards) partner food rescue organization volunteer trip data
Benchmarks: synthetic RMAB-G instances food rescue notifications and phone calls scenarios
Metrics: normalized discounted reward (relative to random policy)
Baselines: Random Vanilla Whittle Greedy MCTS DQN DQN Greedy Optimal
Builds on: Whittle index UCT (Monte Carlo Tree Search) DQN
Closest papers by meaning
- Online Restless Multi-Armed Bandits with Long-Term Fairness Constraints (AAAI 2024 · similarity 0.89)
- Achieving $\tilde{\mathcal{O}}(1/N)$ Optimality Gap in Restless Bandits through Gaussian Approximation (NeurIPS 2025 · similarity 0.88)
- Provably Efficient Reinforcement Learning for Adversarial Restless Multi-Armed Bandits with Unknown Transitions and Bandit Feedback (ICML 2024 · similarity 0.87)
- DOPL: Direct Online Preference Learning for Restless Bandits with Preference Feedback (ICLR 2025 · similarity 0.87)
- Combinatorial Multivariant Multi-Armed Bandits with Applications to Episodic Reinforcement Learning and Beyond (ICML 2024 · similarity 0.86)
- The Bandit Whisperer: Communication Learning for Restless Bandits (AAAI 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.