AdaLinUCB: Opportunistic Learning for Contextual Bandits

Xueying Guo, Xiaoxiao Wang, Xin Liu

Introduction

In contextual bandit problems, an agent selects actions (arms) based on observed information (context) to maximize cumulative rewards. This necessitates balancing exploration (gathering new information) and exploitation (leveraging known high-reward actions). Traditional algorithms like LinUCB often assume a constant cost for exploration. However, in many real-world applications—such as network configuration or e-commerce—the "cost of a mistake" varies significantly over time. AdaLinUCB introduces "opportunistic learning" to exploit these fluctuations, exploring more when costs are low and exploiting when stakes are high.

The Cost of Exploration

Standard contextual bandit models treat every time step as equally critical. In reality, environmental conditions often dictate the risk associated with exploration. For instance, testing a new network configuration during low-traffic hours is far less risky than doing so during peak demand. AdaLinUCB formalizes this by introducing a variation factor ($L_t$), revealed to the agent before each decision, representing the current exploration cost.

The AdaLinUCB Algorithm

AdaLinUCB (Adaptive Linear Upper Confidence Bound) modifies the standard UCB decision rule. While traditional methods use a fixed exploration parameter $\alpha$, AdaLinUCB dynamically adjusts the weight of the uncertainty term based on the variation factor:

$$\text{Score} = \text{Estimated Reward} + \alpha(1 - \tilde{L}_t) \cdot \text{Uncertainty}$$

Here, $\tilde{L}_t$ is a normalized variation factor. When the cost is low ($\tilde{L}_t \approx 0$), the algorithm explores aggressively like standard LinUCB. When the cost is high ($\tilde{L}_t \approx 1$), the uncertainty term is suppressed, forcing the algorithm to exploit its current best knowledge and avoid costly errors.

Experimental Evaluation

The authors evaluated AdaLinUCB using both synthetic and real-world datasets:

  1. Synthetic Scenarios: 20 arms and 6-dimensional context vectors were tested under binary (high/low) and continuous (Beta-distributed) cost fluctuations.
  2. Yahoo! Today Module: A dataset of 4 million user visits was combined with real-world sales data from the Rossman Store Sales dataset to simulate time-varying exploration costs.
Regret comparison for AdaLinUCB against baselines in synthetic environments with binary (a) and beta (b) distributed variation factors.

Key Results

In synthetic tests, AdaLinUCB demonstrated significant efficiency, reducing regret to as little as 10.3% of that incurred by standard LinUCB variants. The algorithm's theoretical regret bound of $O(\log T)^2$ is mathematically tighter than traditional methods under varying cost conditions.

On the real-world Yahoo! dataset, AdaLinUCB outperformed existing policies by strategically timing its exploration. It achieved a 17.0% increase in total reward compared to LinUCBExtracted and a 40.8% increase over a random policy.

Cumulative reward performance on the Yahoo! Today Module dataset, demonstrating AdaLinUCB's superior performance in real-world scenarios.

Conclusion

AdaLinUCB provides a robust framework for opportunistic learning in contextual bandits. By recognizing that exploration costs are not uniform, it achieves higher rewards and lower regret than static exploration strategies. While the current model assumes a linear relationship between context and reward and i.i.d. variation factors, its practical performance suggests strong potential for high-stakes, real-world applications where the cost of failure is dynamic.

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