Combinatorial Sleeping Bandits With Fairness Constraints
Combinatorial Sleeping Bandits With Fairness Constraints
复制标题
DOI：
10.1109/tnse.2019.2954310
复制
发表时间：
2020-07
影响因子：
6.6
通讯作者：
Fengjiao Li;Jia Liu;Bo Ji
中科院分区：
文献类型：
--
作者：
Fengjiao Li;Jia Liu;Bo Ji
多臂老虎机（MAB）模型已被广泛用于研究许多具有未知参数的实际优化问题（网络资源分配、广告投放、众包等）。在此，参与者（即决策者）的目标是在不确定性面前最大化累积奖励。然而，在许多实际应用中，基本的MAB模型忽略了系统的几个重要因素，其中多个臂（即动作）可能会同时被操作，并且一个臂有时可能会“休眠”（即不可用）。除了奖励最大化，确保公平性在实践中也是一个关键的设计关注点。为此，我们提出了一种具有公平性约束的新型组合睡眠多臂老虎机模型，称为CSMAB - F，旨在解决上述关键的建模问题。现在的目标是在满足每个单独臂的最小选择比例的公平性要求的同时最大化奖励。为了解决这个新问题，我们扩展了一种在线学习算法，称为上置信界（UCB），以处理利用和探索之间的关键权衡，并采用虚拟队列技术来妥善处理公平性约束。通过仔细整合这两种技术，我们为CSMAB - F问题开发了一种新算法，称为具有公平性保证的学习（LFG）。此外，我们严格证明了LFG不仅是可行性最优的，而且其时间平均遗憾上界为$\frac{N}{2\eta} + \frac{\beta_1\sqrt{mNT\log{T}} + \beta_2N}{T}$，其中$N$是臂的总数，$m$是可同时操作的臂的最大数量，$T$是时间范围，$\beta_1$和$\beta_2$是常数，$\eta$是我们可以调整的设计参数。最后，我们进行了大量的模拟以证实所提出算法的有效性。有趣的是，模拟结果揭示了遗憾与收敛到满足公平性约束的点的速度之间的一个重要权衡。
The multi-armed 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 (i.e., the decision maker) 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 real-world applications, where multiple arms (i.e., actions) can be simultaneously played and an arm could sometimes be “sleeping” (i.e., unavailable). Besides reward maximization, 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 CSMAB-F, 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, called Upper Confidence Bound (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 CSMAB-F problem. Further, we rigorously prove that not only LFG is feasibility-optimal, but it also has a time-average regret upper bounded by $\frac{N}{2 \eta } + \frac{\beta _1 \sqrt{m N T \log {T}}+ \beta _2~N}{T}$, 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.