Online Restless Multi-Armed Bandits with Long-Term Fairness Constraints
This work addresses fairness constraints in sequential decision-making for applications like resource allocation, though it is incremental as it builds on existing RMAB frameworks.
The paper tackles the problem of ensuring long-term fairness in online restless multi-armed bandits (RMABs) where the underlying Markov decision processes are unknown, by introducing the RMAB-F model and developing the Fair-UCRL algorithm, which achieves probabilistic sublinear bounds on reward and fairness violation regret and demonstrates computational efficiency in experiments.
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.