  Restless multi-armed bandits (RMAB) have been widely used to model sequential
decision making problems with constraints. The decision maker (DM) aims to
maximize the expected total reward over an infinite horizon under an
"instantaneous activation constraint" that at most B arms can be activated at
any decision epoch, where the state of each arm evolves stochastically
according to a Markov decision process (MDP). However, this basic model fails
to provide any fairness guarantee among arms. In this paper, we introduce
RMAB-F, a new RMAB model with "long-term fairness constraints", where the
objective now is to maximize the long term reward while a minimum long-term
activation fraction for each arm must be satisfied. For the online RMAB-F
setting (i.e., the underlying MDPs associated with each arm are unknown to the
DM), we develop a novel reinforcement learning (RL) algorithm named Fair-UCRL.
We prove that Fair-UCRL ensures probabilistic sublinear bounds on both the
reward regret and the fairness violation regret. Compared with off-the-shelf RL
methods, our Fair-UCRL is much more computationally efficient since it contains
a novel exploitation that leverages a low-complexity index policy for making
decisions. Experimental results further demonstrate the effectiveness of our
Fair-UCRL.
