Stochastic Linear Contextual Bandits with Diverse Contexts
This work addresses bandit learning efficiency for scenarios with diverse contexts, offering a theoretical improvement over prior methods.
The paper tackles the problem of stochastic linear contextual bandits by showing that diverse contexts can reduce regret, and it achieves a constant cumulative expected regret bound with the proposed LinUCB-d algorithm.
In this paper, we investigate the impact of context diversity on stochastic linear contextual bandits. As opposed to the previous view that contexts lead to more difficult bandit learning, we show that when the contexts are sufficiently diverse, the learner is able to utilize the information obtained during exploitation to shorten the exploration process, thus achieving reduced regret. We design the LinUCB-d algorithm, and propose a novel approach to analyze its regret performance. The main theoretical result is that under the diverse context assumption, the cumulative expected regret of LinUCB-d is bounded by a constant. As a by-product, our results improve the previous understanding of LinUCB and strengthen its performance guarantee.