Adaptive Exploration-Exploitation Tradeoff for Opportunistic Bandits
Adaptive Exploration-Exploitation Tradeoff for Opportunistic Bandits
复制标题
DOI：
--
复制
发表时间：
2017-09
期刊：
影响因子：
--
通讯作者：
Huasen Wu;Xueying Guo;Xin Liu
中科院分区：
文献类型：
--
作者：
Huasen Wu;Xueying Guo;Xin Liu
在本文中，我们提出并研究了机会主义强盗-一个新的变种强盗拉一个次优的手臂在不同的环境条件下，如网络负载或产品价格变化的遗憾。当负载/价格低时，拉动次优臂的成本/遗憾也低（例如，尝试次优网络配置）。因此，直观地说，我们可以在负载/价格较低时进行更多探索，而在负载/价格较高时进行更多开发。受这种直觉的启发，我们提出了一个自适应置信上限（AdaUCB）算法，以适应性地平衡机会主义强盗的探索-利用权衡。我们证明了AdaUCB实现$O（\log T）$遗憾与一个更小的系数比传统的UCB算法。此外，当负载水平低于某个阈值时，如果探索成本为零，则AdaUCB相对于$T$实现$O（1）$遗憾。最后，基于模拟数据和真实数据的实验结果表明，AdaUCB算法在较大的负载/价格波动下，性能明显优于UCB和TS（Thompson Sampling）等其他Bandit算法。
In this paper, we propose and study opportunistic bandits - a new variant of bandits where the regret of pulling a suboptimal arm varies under different environmental conditions, such as network load or produce price. When the load/price is low, so is the cost/regret of pulling a suboptimal arm (e.g., trying a suboptimal network configuration). Therefore, intuitively, we could explore more when the load/price is low and exploit more when the load/price is high. Inspired by this intuition, we propose an Adaptive Upper-Confidence-Bound (AdaUCB) algorithm to adaptively balance the exploration-exploitation tradeoff for opportunistic bandits. We prove that AdaUCB achieves $O(\log T)$ regret with a smaller coefficient than the traditional UCB algorithm. Furthermore, AdaUCB achieves $O(1)$ regret with respect to $T$ if the exploration cost is zero when the load level is below a certain threshold. Last, based on both synthetic data and real-world traces, experimental results show that AdaUCB significantly outperforms other bandit algorithms, such as UCB and TS (Thompson Sampling), under large load/price fluctuations.