Nearly-tight Approximation Guarantees for the Improving Multi-Armed Bandits Problem

我们为改进的多臂赌博机问题提供了几乎紧密的上下界。该问题的一个实例有$k$个臂，每个臂的奖励函数是一个凹且随着该臂被拉动的次数而增加的函数。我们证明，对于任何随机在线算法，都存在一个实例，使得相对于最优奖励，它必须遭受至少$\Omega(\sqrt{k})$的近似因子损失。然后，我们提供了一个随机在线算法，如果提前告知最优臂可实现的最大奖励，则可保证$O(\sqrt{k})$的近似因子。然后，我们展示如何消除这个假设，代价是额外的$O(\log k)$近似因子，实现相对于最优的$O(\sqrt{k}\log k)$近似。

解决问题：本论文旨在解决改进多臂赌博机问题，即针对每个臂的奖励函数是次凸且随着拉动次数单调递增的多臂赌博机问题。论文证明了任何随机在线算法都存在至少一种实例，在该实例上相对于最优奖励必须遭受至少Ω(√k)的近似因子。

关键思路：论文提出了一种基于先验知识的随机在线算法，该算法可以保证在最优臂可达到的最大奖励已知的情况下，相对于最优奖励具有O(√k)的近似因子。此外，论文还提出了一种方法，可以消除这种先验知识的假设，但代价是增加O(logk)的近似因子，从而实现相对于最优的O(√k logk)的近似。

其他亮点：该论文的实验设计了两个实例来验证算法的有效性，并使用了UCI的人口普查数据集进行了实验。论文还提供了开源代码。值得深入研究的工作包括如何在没有先验知识的情况下，实现更好的近似因子。

相关研究：在这个领域的相关研究包括：1. Kalyanakrishnan等人的“Stochastic multi-armed bandits with side observations”；2. Agrawal等人的“Thompson sampling for contextual bandits with linear payoffs”；3. Neu等人的“Online learning in dynamic environments”等。