提出低复杂度公平学习算法，解决组合多臂老虎机的计算瓶颈。
On the Low-Complexity of Fair Learning for Combinatorial Multi-Armed Bandit
- 通过随机选取固定数量超臂进行比较，降低计算开销。
- 理论证明复杂度下降仅轻微影响公平性和累积损失。
- 适合大规模无线网络等超臂数量指数增长的场景。
带有公平性约束的组合多臂老虎机框架中，多个臂组成超臂，在每轮中于不确定性下选择以最大化累计奖励，并确保每个臂的最低平均回报。现有悲观乐观算法将虚拟队列长度（追踪公平性违规）与置信上界估计线性结合作为各臂权重，选择总权重最大的超臂。但在许多场景中，超臂数量可能随臂数呈指数增长，例如无线网络中的干扰约束会导致超臂数量指数级增加。评估所有可行超臂以寻找最大总权重超臂会带来极高的计算复杂度。为避免此问题，我们基于‘选中并比较’方法设计了一种低复杂度公平学习算法，随机选取M个可行超臂进行评估。将M设为常数后，悲观乐观算法中的比较步骤数可降至常数，从而显著降低计算复杂度。理论证明表明，该低复杂度设计仅带来轻微的公平性与累积遗憾性能损失。最后，通过大量仿真验证了理论结果。
原文摘要 · Abstract (English)
Combinatorial Multi-Armed Bandit with fairness constraints is a framework where multiple arms form a super arm and can be pulled in each round under uncertainty to maximize cumulative rewards while ensuring the minimum average reward required by each arm. The existing pessimistic-optimistic algorithm linearly combines virtual queue-lengths (tracking the fairness violations) and Upper Confidence Bound estimates as a weight for each arm and selects a super arm with the maximum total weight. The number of super arms could be exponential to the number of arms in many scenarios. In wireless networks, interference constraints can cause the number of super arms to grow exponentially with the number of arms. Evaluating all the feasible super arms to find the one with the maximum total weight can incur extremely high computational complexity in the pessimistic-optimistic algorithm. To avoid this, we develop a low-complexity fair learning algorithm based on the so-called pick-and-compare approach that involves randomly picking $M$ feasible super arms to evaluate. By setting $M$ to a constant, the number of comparison steps in the pessimistic-optimistic algorithm can be reduced to a constant, thereby significantly reducing the computational complexity. Our theoretical proof shows this low-complexity design incurs only a slight sacrifice in fairness and regret performance. Finally, we validate the theoretical result by extensive simulations.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。