Anytime Fairness Guarantees in Stochastic Combinatorial MABs: A Novel Learning Framework

This paper proposes a novel framework for incorporating anytime fairness guarantees in a general Stochastic Combinatorial Multi-Armed Bandit (CMAB) problem when the time horizon is unknown. Our framework does not make any assumptions about the reward feedback or structure and provides fairness guarantees as long as a sublinear regret algorithm exists to solve the same problem. The framework essentially operates in the episodes of length 𝐻 , which is a user-defined parameter. The framework divides each episode of length 𝐻 into fairness rounds and learning rounds. Motivated by preemptive scheduling on uniform machines, we propose Fair-CMAB which prioritizes fairness rounds upfront and uses any existing CMAB algorithm for learning rounds. This helps in generalizing the framework significantly. Theoretically, we prove that for a sufficiently large value of 𝐻 , Fair-CMAB achieves anytime fairness guarantees after some initial number of rounds and achieves the regret guarantees of the same order as the learning algorithm.