Combinatorial Sleeping Bandits with Fairness Constraints The multiarmed bandit (MAB) model has been widely adopted for studying many practical optimization problems (network resource allocation, ad placement, crowdsourcing, etc.) with unknown parameters. The goal of the player here is to maximize the cumulative reward in the face of uncertainty. However, the basic MAB model neglects several important factors of the system in many realworld applications, where multiple arms can be simultaneously played and an arm could sometimes be sleeping. Besides, ensuring fairness is also a key design concern in practice. To that end, we propose a new Combinatorial Sleeping MAB model with Fairness constraints, called CSMABF, aiming to address the aforementioned crucial modeling issues. The objective is now to maximize the reward while satisfying the fairness requirement of a minimum selection fraction for each individual arm. To tackle this new problem, we extend an online learning algorithm, UCB, to deal with a critical tradeoff between exploitation and exploration and employ the virtual queue technique to properly handle the fairness constraints. By carefully integrating these two techniques, we develop a new algorithm, called Learning with Fairness Guarantee (LFG), for the CSMABF problem. Further, we rigorously prove that not only LFG is feasibilityoptimal, but it also has a timeaverage regret upper bounded by fracN2etafracbeta_1sqrtmNTlogTbeta_2 NT, where N is the total number of arms, m is the maximum number of arms that can be simultaneously played, T is the time horizon, beta_1 and beta_2 are constants, and eta is a design parameter that we can tune. Finally, we perform extensive simulations to corroborate the effectiveness of the proposed algorithm. Interestingly, the simulation results reveal an important tradeoff between the regret and the speed of convergence to a point satisfying the fairness constraints.

An ArmWise Randomization Approach to Combinatorial Linear SemiBandits Combinatorial linear semibandits (CLS) are widely applicable frameworks of sequential decisionmaking, in which a learner chooses a subset of arms from a given set of arms associated with feature vectors. Existing algorithms work poorly for the clustered case, in which the feature vectors form several large clusters. This shortcoming is critical in practice because it can be found in many applications, including recommender systems. In this paper, we clarify why such a shortcoming occurs, and we introduce a key technique of armwise randomization to overcome it. We propose two algorithms with this technique: the perturbed C2 UCB (PC2 UCB) and the Thompson sampling (TS). Our empirical evaluation with artificial and realworld datasets demonstrates that the proposed algorithms with the armwise randomization technique outperform the existing algorithms without this technique, especially for the clustered case. Our contributions also include theoretical analyses that provide high probability asymptotic regret bounds for our algorithms.