# Collapsing Bandits and Their Application to Public Health Interventions

arXiv: https://arxiv.org/abs/2007.04432 · HTML: https://mlsanity.com/paper/2007.04432/

## Key facts

- Cited by 47 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Jul 2020.

## Built on by (most cited first, 30 of 47)

- [Field Study in Deploying Restless Multi-Armed Bandits: Assisting Non-Profits in Improving Maternal and Child Health](https://mlsanity.com/paper/2109.08075/) (2021)
- [Learn to Intervene: An Adaptive Learning Policy for Restless Bandits in Application to Preventive Healthcare](https://mlsanity.com/paper/2105.07965/) (2021)
- [On the Sublinear Regret of GP-UCB](https://mlsanity.com/paper/2307.07539/) (2023)
- [Q-Learning Lagrange Policies for Multi-Action Restless Bandits](https://mlsanity.com/paper/2106.12024/) (2021)
- [Finite-Time Analysis of Whittle Index based Q-Learning for Restless Multi-Armed Bandits with Neural Network Function Approximation](https://mlsanity.com/paper/2310.02147/) (2023)
- [Planning to Fairly Allocate: Probabilistic Fairness in the Restless Bandit Setting](https://mlsanity.com/paper/2106.07677/) (2021)
- [Scalable Decision-Focused Learning in Restless Multi-Armed Bandits with Application to Maternal and Child Health](https://mlsanity.com/paper/2202.00916/) (2022)
- [Efficient Resource Allocation with Fairness Constraints in Restless Multi-Armed Bandits](https://mlsanity.com/paper/2206.03883/) (2022)
- [Non-Stationary Bandits with Auto-Regressive Temporal Dependency](https://mlsanity.com/paper/2210.16386/) (2022)
- [Indexability is Not Enough for Whittle: Improved, Near-Optimal Algorithms for Restless Bandits](https://mlsanity.com/paper/2211.00112/) (2022)
- [Act-Then-Measure: Reinforcement Learning for Partially Observable Environments with Active Measuring](https://mlsanity.com/paper/2303.08271/) (2023)
- [Policy Optimization for Personalized Interventions in Behavioral Health](https://mlsanity.com/paper/2303.12206/) (2023)
- [Selective Intervention Planning using Restless Multi-Armed Bandits to Improve Maternal and Child Health Outcomes](https://mlsanity.com/paper/2103.09052/) (2021)
- [Restless and Uncertain: Robust Policies for Restless Bandits via Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2107.01689/) (2021)
- [Networked Restless Multi-Armed Bandits for Mobile Interventions](https://mlsanity.com/paper/2201.12408/) (2022)
- [Efficient Algorithms for Finite Horizon and Streaming Restless Multi-Armed Bandit Problems](https://mlsanity.com/paper/2103.04730/) (2021)
- [Context in Public Health for Underserved Communities: A Bayesian Approach to Online Restless Bandits](https://mlsanity.com/paper/2402.04933/) (2024)
- [Global Rewards in Restless Multi-Armed Bandits](https://mlsanity.com/paper/2406.00738/) (2024)
- [Towards Soft Fairness in Restless Multi-Armed Bandits](https://mlsanity.com/paper/2207.13343/) (2022)
- [Networked Restless Bandits with Positive Externalities](https://mlsanity.com/paper/2212.05144/) (2022)
- [Evaluating the Effectiveness of Index-Based Treatment Allocation](https://mlsanity.com/paper/2402.11771/) (2024)
- [Improved Policy Evaluation for Randomized Trials of Algorithmic Resource Allocation](https://mlsanity.com/paper/2302.02570/) (2023)
- [Learning MDPs from Features: Predict-Then-Optimize for Sequential Decision Problems by Reinforcement Learning](https://mlsanity.com/paper/2106.03279/) (2021)
- [Fairness for Workers Who Pull the Arms: An Index Based Policy for Allocation of Restless Bandit Tasks](https://mlsanity.com/paper/2303.00799/) (2023)
- [Planning a Community Approach to Diabetes Care in Low- and Middle-Income Countries Using Optimization](https://mlsanity.com/paper/2305.06426/) (2023)
- [Preliminary Study of the Impact of AI-Based Interventions on Health and Behavioral Outcomes in Maternal Health Programs](https://mlsanity.com/paper/2407.11973/) (2024)
- [Improving Health Information Access in the World's Largest Maternal Mobile Health Program via Bandit Algorithms](https://mlsanity.com/paper/2407.12131/) (2024)
- [Deep Index Policy for Multi-Resource Restless Matching Bandit and Its Application in Multi-Channel Scheduling](https://mlsanity.com/paper/2408.07205/) (2024)
- [DOPL: Direct Online Preference Learning for Restless Bandits with Preference Feedback](https://mlsanity.com/paper/2410.05527/) (2024)
- [Decision-Focused Evaluation: Analyzing Performance of Deployed Restless Multi-Arm Bandits](https://mlsanity.com/paper/2301.07835/) (2023)

## Abstract (arXiv)

We propose and study Collpasing Bandits, a new restless multi-armed bandit (RMAB) setting in which each arm follows a binary-state Markovian process with a special structure: when an arm is played, the state is fully observed, thus "collapsing" any uncertainty, but when an arm is passive, no observation is made, thus allowing uncertainty to evolve. The goal is to keep as many arms in the "good" state as possible by planning a limited budget of actions per round. Such Collapsing Bandits are natural models for many healthcare domains in which workers must simultaneously monitor patients and deliver interventions in a way that maximizes the health of their patient cohort. Our main contributions are as follows: (i) Building on the Whittle index technique for RMABs, we derive conditions under which the Collapsing Bandits problem is indexable. Our derivation hinges on novel conditions that characterize when the optimal policies may take the form of either "forward" or "reverse" threshold policies. (ii) We exploit the optimality of threshold policies to build fast algorithms for computing the Whittle index, including a closed-form. (iii) We evaluate our algorithm on several data distributions including data from a real-world healthcare task in which a worker must monitor and deliver interventions to maximize their patients' adherence to tuberculosis medication. Our algorithm achieves a 3-order-of-magnitude speedup compared to state-of-the-art RMAB techniques while achieving similar performance.