Independent Reading · 2024
Global Rewards in Restless Multi-Armed Bandits
Naveen Raman, Zheyuan Ryan Shi, and Fei Fang · arXiv preprint
Restless BanditsResource AllocationGlobal Rewards
Full text
Read the Paper
Use View PDF or Download PDF to read the full paper on this device.
Paper Information
- Authors
- Naveen Raman, Zheyuan Ryan Shi, and Fei Fang
- Venue
- arXiv preprint · 2024
Summary
This paper extends restless multi-armed bandits to objectives with global, non-separable rewards across selected arms.
Core Idea
Resource-allocation rewards may depend on the joint set of activated arms, so per-arm Whittle indices require new global approximations.
Method
The authors develop Linear- and Shapley-Whittle indices plus adaptive greedy and Monte Carlo tree-search policies, with theory and experiments.
Key Takeaways
- Reward separability can be unrealistic in social-impact allocation problems.
- Index approximations work best for near-linear global rewards.
- Adaptive search improves decisions when reward interactions are highly nonlinear.
Questions
- How can global-reward policies remain efficient with very large arm populations?
- Can uncertainty in transition models be integrated into the adaptive policies?