Merit-based Fair Combinatorial Semi-Bandit with Unrestricted Feedback Delays
This addresses fairness and delay challenges in applications like crowdsourcing and online advertising, representing an incremental improvement by extending existing bandit frameworks with new constraints.
The paper tackles the stochastic combinatorial semi-bandit problem with unrestricted feedback delays under merit-based fairness constraints, proposing algorithms that achieve sublinear expected reward and fairness regret with dependence on delay distribution quantiles, as validated by experiments on synthetic and real-world data.
We study the stochastic combinatorial semi-bandit problem with unrestricted feedback delays under merit-based fairness constraints. This is motivated by applications such as crowdsourcing, and online advertising, where immediate feedback is not immediately available and fairness among different choices (or arms) is crucial. We consider two types of unrestricted feedback delays: reward-independent delays where the feedback delays are independent of the rewards, and reward-dependent delays where the feedback delays are correlated with the rewards. Furthermore, we introduce merit-based fairness constraints to ensure a fair selection of the arms. We define the reward regret and the fairness regret and present new bandit algorithms to select arms under unrestricted feedback delays based on their merits. We prove that our algorithms all achieve sublinear expected reward regret and expected fairness regret, with a dependence on the quantiles of the delay distribution. We also conduct extensive experiments using synthetic and real-world data and show that our algorithms can fairly select arms with different feedback delays.