  Restless multi-armed bandits (RMAB) is a framework for allocating limited
resources under uncertainty. It is an extremely useful model for monitoring
beneficiaries and executing timely interventions to ensure maximum benefit in
public health settings (e.g., ensuring patients take medicines in tuberculosis
settings, ensuring pregnant mothers listen to automated calls about good
pregnancy practices). Due to the limited resources, typically certain
communities or regions are starved of interventions that can have follow-on
effects. To avoid starvation in the executed interventions across
individuals/regions/communities, we first provide a soft fairness constraint
and then provide an approach to enforce the soft fairness constraint in RMABs.
The soft fairness constraint requires that an algorithm never probabilistically
favor one arm over another if the long-term cumulative reward of choosing the
latter arm is higher. Our approach incorporates softmax based value iteration
method in the RMAB setting to design selection algorithms that manage to
satisfy the proposed fairness constraint. Our method, referred to as SoftFair,
also provides theoretical performance guarantees and is asymptotically optimal.
Finally, we demonstrate the utility of our approaches on simulated benchmarks
and show that the soft fairness constraint can be handled without a significant
sacrifice on value.
