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 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.
