AdaLinUCB: Opportunistic Learning for Contextual Bandits

Xueying Guo, Xiaoxiao Wang, Xin Liu

Abstract

In this paper, we propose and study opportunistic contextual bandits - a special case of contextual bandits where the exploration cost varies under different environmental conditions, such as network load or return variation in recommendations. When the exploration cost is low, so is the actual regret of pulling a sub-optimal arm. Therefore, intuitively, we could explore more when the exploration cost is relatively low and exploit more when the exploration cost is relatively high. Inspired by this intuition, for opportunistic contextual bandits with Linear payoffs, we propose an Adaptive Upper-Confidence-Bound algorithm (AdaLinUCB) to adaptively balance the exploration-exploitation trade-off for opportunistic learning. We prove that AdaLinUCB achieves $O((\log T)^2)$ problem-dependent regret upper bound, which has a smaller coefficient than that of the traditional LinUCB algorithm. Moreover, based on both synthetic and real-world dataset, we show that AdaLinUCB significantly outperforms other contextual bandit algorithms, under large exploration cost fluctuations.

Introduction

In sequential decision-making, the contextual bandit framework is widely used for applications like news recommendations and clinical trials. A fundamental challenge in this framework is the exploration-exploitation trade-off: deciding whether to pull the arm that has historically performed best (exploit) or try a new arm to gain more information (explore).

Traditional algorithms typically assume a constant cost for exploration mistakes. However, in many real-world scenarios, these costs are time-varying. For instance, in recommendation systems, testing a sub-optimal product on a casual browser during off-peak hours is significantly less costly than doing so for a high-value customer during a major sale. Similarly, in network configuration, exploring new settings during low-traffic periods is "cheaper" than during peak hours. This paper introduces a formal framework for opportunistic learning, where an algorithm adaptively leverages these low-cost windows to accelerate learning without incurring high cumulative regret.

Methods

The proposed algorithm, AdaLinUCB (Adaptive Linear Upper Confidence Bound), modifies the standard LinUCB approach to incorporate a variation factor ($L_t$). This factor, observed before each decision, represents the current cost of regret.

AdaLinUCB utilizes a normalized version of this factor, $\tilde{L}_t$, to scale its exploration term. When $\tilde{L}_t$ is low, the algorithm expands its confidence intervals to encourage exploration. Conversely, when $\tilde{L}_t$ is high, the exploration term is reduced, prioritizing exploitation of the best-known arm. The authors also introduce E-AdaLinUCB, an extension that learns the distribution of these costs online, eliminating the need for prior knowledge of cost thresholds.

Results and Discussion

The researchers evaluated AdaLinUCB through both synthetic simulations and real-world datasets. Synthetic tests involved 20 arms and 6-dimensional context vectors under binary and Beta-distributed cost fluctuations.

Regret performance under binary-valued (a) and Beta distributed (b) variation factors.

As shown in Figure 2, AdaLinUCB consistently achieves lower regret than standard baselines. In scenarios with binary costs, AdaLinUCB’s regret was only 10.3% of that incurred by a standard "multiply" approach and 17.6% of a standard LinUCB implementation.

For real-world validation, the team used the Yahoo! Today Module dataset (4 million visits) paired with the Rossman store dataset to simulate time-varying exploration costs.

Total reward comparison on the Yahoo! dataset.

In these experiments (Figure 4), AdaLinUCB demonstrated a 17.0% increase in total reward compared to LinUCB and a 40.8% increase over a random policy. Notably, AdaLinUCB maintains the computational efficiency of linear methods, making it more scalable than non-linear alternatives like KernelUCB for high-frequency systems.

Conclusion

AdaLinUCB demonstrates that timing is a critical dimension of the exploration-exploitation trade-off. By shifting exploration to low-cost periods, the algorithm significantly reduces actual regret. While current results rely on a linearity assumption and pre-revealed costs, future work could extend this opportunistic approach to non-linear reward structures and non-stationary environments where the underlying distributions evolve over time.

Summary updated

Abstract

In this paper, we propose and study opportunistic contextual bandits - a special case of contextual bandits where the exploration cost varies under different environmental conditions, such as network load or return variation in recommendations. When the exploration cost is low, so is the actual regret of pulling a sub-optimal arm (e.g., trying a suboptimal recommendation). Therefore, intuitively, we could explore more when the exploration cost is relatively low and exploit more when the exploration cost is relatively high. Inspired by this intuition, for opportunistic contextual bandits with Linear payoffs, we propose an Adaptive Upper-Confidence-Bound algorithm (AdaLinUCB) to adaptively balance the exploration-exploitation trade-off for opportunistic learning. We prove that AdaLinUCB achieves O((log T)^2) problem-dependent regret upper bound, which has a smaller coefficient than that of the traditional LinUCB algorithm. Moreover, based on both synthetic and real-world dataset, we show that AdaLinUCB significantly outperforms other contextual bandit algorithms, under large exploration cost fluctuations.
BibTeX
@inproceedings{guo2019adalinucb,
  author = {Xueying Guo and Xiaoxiao Wang and Xin Liu},
  title = {{AdaLinUCB: Opportunistic Learning for Contextual Bandits}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/336},
}
Figure