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

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 60 references that are in the map.
- First posted on arXiv 14 Jun 2021.

## Builds on (most cited first, 8 of 8)

- [Fairness in Learning: Classic and Contextual Bandits](https://mlsanity.com/paper/1605.07139/) (2016)
- [A Case for Humans-in-the-Loop: Decisions in the Presence of Erroneous Algorithmic Scores](https://mlsanity.com/paper/2002.08035/) (2020)
- [Combinatorial Sleeping Bandits with Fairness Constraints](https://mlsanity.com/paper/1901.04891/) (2019)
- [Collapsing Bandits and Their Application to Public Health Interventions](https://mlsanity.com/paper/2007.04432/) (2020)
- [Fair Contextual Multi-Armed Bandits: Theory and Experiments](https://mlsanity.com/paper/1912.08055/) (2019)
- [Regret Bounds for Thompson Sampling in Episodic Restless Bandit Problems](https://mlsanity.com/paper/1905.12673/) (2019)
- [Thompson Sampling in Non-Episodic Restless Bandits](https://mlsanity.com/paper/1910.05654/) (2019)
- [A verification theorem for threshold-indexability of real-state discounted restless bandits](https://mlsanity.com/paper/1902.09318/) (2019)

## Built on by (most cited first, 12 of 12)

- [Online Restless Multi-Armed Bandits with Long-Term Fairness Constraints](https://mlsanity.com/paper/2312.10303/) (2023)
- [Equitable Restless Multi-Armed Bandits: A General Framework Inspired By Digital Health](https://mlsanity.com/paper/2308.09726/) (2023)
- [Towards Soft Fairness in Restless Multi-Armed Bandits](https://mlsanity.com/paper/2207.13343/) (2022)
- [Ranked Prioritization of Groups in Combinatorial Bandit Allocation](https://mlsanity.com/paper/2205.05659/) (2022)
- [Fairness for Workers Who Pull the Arms: An Index Based Policy for Allocation of Restless Bandit Tasks](https://mlsanity.com/paper/2303.00799/) (2023)
- [DOPL: Direct Online Preference Learning for Restless Bandits with Preference Feedback](https://mlsanity.com/paper/2410.05527/) (2024)
- [Fairness of Exposure in Online Restless Multi-armed Bandits](https://mlsanity.com/paper/2402.06348/) (2024)
- [Provably Efficient Reinforcement Learning for Adversarial Restless Multi-Armed Bandits with Unknown Transitions and Bandit Feedback](https://mlsanity.com/paper/2405.00950/) (2024)
- [Finite-Horizon Single-Pull Restless Bandits: An Efficient Index Policy For Scarce Resource Allocation](https://mlsanity.com/paper/2501.06103/) (2025)
- [A resource-constrained stochastic scheduling algorithm for homeless street outreach and gleaning edible food](https://mlsanity.com/paper/2403.10638/) (2024)
- [Fair Resource Allocation in Weakly Coupled Markov Decision Processes](https://mlsanity.com/paper/2411.09804/) (2024)
- [Restless Bandits with Individual Penalty Constraints: Near-Optimal Indices and Deep Reinforcement Learning](https://mlsanity.com/paper/2604.04101/) (2026)

## Abstract (arXiv)

Restless and collapsing bandits are often used to model budget-constrained resource allocation in settings where arms have action-dependent transition probabilities, such as the allocation of health interventions among patients. However, state-of-the-art Whittle-index-based approaches to this planning problem either do not consider fairness among arms, or incentivize fairness without guaranteeing it. We thus introduce ProbFair, a probabilistically fair policy that maximizes total expected reward and satisfies the budget constraint while ensuring a strictly positive lower bound 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. We find that ProbFair preserves utility while providing fairness guarantees.