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
Open official paper

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?