Combinatorial Sleeping Bandits with Fairness Constraints and Long-Term Non-Availability of Arms

摘要

In this paper, the situation of long term non-availability of arms in combinatorial sleeping bandits problem is analyzed. The multi-arm sleeping bandit’s model along with fairness constraint is very widely used to model real world examples like a network switch. One common occurrence in such a scenario is long term non-availability. In such cases the queue length (in the Queuing techniques) grows rapidly causing system instability. The algorithm proposed in this paper deals with this problem and still maintain the regret bounds along with the queue fairness constraints. A better way of estimating the fairness that takes into account the long term non-availability of arms is also proposed. Extension of the UCB algorithm is used to deal with the exploration versus exploitation dilemma. Mathematical proofs for arriving at the regret bounds and feasibility optimality is given in the end.