提出睡眠竞争老虎机模型，实现最优长期收益。
Regret Analysis of Sleeping Competing Bandits
- 设计新算法处理玩家与武器随时间变化的可用性。
- 理论证明算法渐近后悔上界为O(NK log T_i / Δ²)。
- 适用于资源动态变化的在线匹配场景，如任务分配。
竞争老虎机框架是在线学习中多臂赌博机与博弈论中稳定匹配相结合的新兴领域。传统模型假设所有玩家和武器始终可用，但在现实问题中，其可用性可能随时间任意变化。本文将此设定建模为‘睡眠竞争老虎机’。我们自然扩展了现有竞争老虎机中的后悔定义，并推导出该模型的后悔界。提出一种算法，在合理假设下可同时达到渐近后悔上界为$\mathrm{O}(NK\log T_{i}/Δ^2)$，其中$N$为玩家数，$K$为武器数，$T_{i}$为每个玩家$p_i$的轮次数，$Δ$为最小奖励差距。同时在相同假设下给出了$\mathrm{Ω}(N(K-N+1)\log T_{i}/Δ^2)$的后悔下界。这表明当武器数$K$相对大于玩家数$N$时，所提算法渐近最优。
原文摘要 · Abstract (English)
The Competing Bandits framework is a recently emerging area that integrates multi-armed bandits in online learning with stable matching in game theory. While conventional models assume that all players and arms are constantly available, in real-world problems, their availability can vary arbitrarily over time. In this paper, we formulate this setting as Sleeping Competing Bandits. To analyze this problem, we naturally extend the regret definition used in existing competing bandits and derive regret bounds for the proposed model. We propose an algorithm that simultaneously achieves an asymptotic regret bound of $\mathrm{O}\left(NK\log T_{i}/Δ^2\right)$ under reasonable assumptions, where $N$ is the number of players, $K$ is the number of arms, $T_{i}$ is the number of rounds of each player $p_i$, and $Δ$ is the minimum reward gap. We also provide a regret lower bound of $\mathrmΩ\left( N(K-N+1)\log T_{i}/Δ^2 \right)$ under the same assumptions. This implies that our algorithm is asymptotically optimal in the regime where the number of arms $K$ is relatively larger than the number of players $N$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。