Adaptive Exploration-Exploitation Tradeoff for Opportunistic Bandits

Abstract

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.

In Proceedings of the 35th International Conference on Machine Learning (ICML), 2018, pp. 5306-5314, Stockholmsmässan, Stockholm Sweden, ICML 2018. (PMLR 80:5306-5314)

Cited by in corpus (5)

• Computation Offloading in Heterogeneous Vehicular Edge Networks: On-line and Off-policy Bandit Solutions
• Adaptive Learning-Based Task Offloading for Vehicular Edge Computing Systems
• Bandit Policies for Reliable Cellular Network Handovers in Extreme Mobility
• AdaLinUCB: Opportunistic Learning for Contextual Bandits
• An Opportunistic Bandit Approach for User Interface Experimentation