Planning to Fairly Allocate: Probabilistic Fairness in the Restless Bandit Setting

Restless and collapsing bandits are often used to model budget-constrained resource allocation in settings where receiving the resource increases the probability that an arm will transition to, or remain in, a desirable state. However, SOTA Whittle-index-based approaches to this planning problem either do not consider fairness among arms, or incentivize fairness without guaranteeing it. We introduce ProbFair, an algorithm which finds the best (reward-maximizing) policy that: (a) satisfies the budget constraint; and (b) enforces bounds $[\ell, u]$ on the probability of being pulled at each timestep. We evaluate our algorithm on a real-world application, where interventions support continuous positive airway pressure (CPAP) therapy adherence among patients, as well as on a broader class of synthetic transition matrices. ProbFair preserves utility while providing fairness guarantees.