Adaptive Exploration in Linear Contextual Bandit

Botao Hao, Tor Lattimore, Csaba Szepesvári

Abstract

Contextual bandits serve as a fundamental model for many sequential decision making tasks. The most popular theoretically justified approaches are based on the optimism principle. While these algorithms can be practical, they are known to be suboptimal asymptotically. On the other hand, existing asymptotically optimal algorithms for this problem do not exploit the linear structure in an optimal way and suffer from lower-order terms that dominate the regret in all practically interesting regimes. We start to bridge the gap by designing an algorithm that is asymptotically optimal and has good finite-time empirical performance. At the same time, we make connections to the recent literature on when exploration-free methods are effective. Indeed, if the distribution of contexts is well behaved, then our algorithm acts mostly greedily and enjoys sub-logarithmic regret. Furthermore, our approach is adaptive in the sense that it automatically detects the nice case. Numerical results demonstrate significant regret reductions by our method relative to several baselines.

Introduction

The linear contextual bandit is a cornerstone of modern recommendation systems and personalized services. For years, practitioners have relied on algorithms like LinUCB, which follow the "Optimism in the Face of Uncertainty" (OFU) principle. While robust, these methods are asymptotically suboptimal, often exploring more than necessary in the long run. Conversely, theoretically "perfect" asymptotically optimal algorithms often fail in practice due to high computational costs or large lower-order regret terms.

This paper introduces Optimal Allocation Matching (OAM), an algorithm designed to bridge this gap. OAM achieves asymptotic optimality while maintaining strong finite-time performance and computational efficiency.

The OAM Algorithm

OAM operates by solving an optimization problem to determine the "optimal allocation"—the precise number of times each arm should be pulled for a given context to distinguish the best arm with minimal effort.

The algorithm consists of three main components:

  1. Estimation: Using least-squares to maintain an estimate of the unknown parameter $\theta$.
  2. Allocation Tracking: Solving a convex optimization problem to find the ideal pull-counts ($T^*$) for each arm, leveraging the linear structure of the features.
  3. Adaptive Switching: OAM dynamically chooses between acting greedily (exploitation), catching up to the optimal allocation (exploration), or falling back to a standard optimistic approach (LinUCB) if progress stalls.

Key Results and Insights

A major contribution of this work is the identification of "natural exploration." If context distributions are sufficiently diverse, the algorithm can learn the optimal parameter $\theta$ while acting greedily most of the time. OAM automatically detects these "rich" context scenarios, leading to bounded or sub-logarithmic regret.

Regret comparison between OAM and LinUCB in fixed action set scenarios.

In empirical evaluations, OAM consistently outperforms LinUCB, especially in scenarios with geometrically close arms where LinUCB's regret continues to grow while OAM's levels off. This demonstrates OAM's ability to stop exploring once it has gathered sufficient information, unlike optimistic methods that may over-explore.

Scalability and Bounded Regret

Unlike previous asymptotically optimal algorithms like OSSB, which scale poorly with the number of actions ($K$), OAM's reliance on the linear structure allows it to remain efficient even as the action space grows.

OAM performance in bounded regret scenarios (left) and large action spaces (right).

As shown in the experiments, OAM maintains competitive performance in large action spaces ($K=100$) where other structured bandit algorithms like OSSB become unstable or suffer from significantly higher regret. Furthermore, the "bounded regret" property is empirically verified in settings with rich context distributions, where regret eventually plateaus, confirming that the algorithm can effectively transition to a greedy strategy.

Conclusion

OAM represents a significant step forward in contextual bandit research, providing a theoretically grounded algorithm that performs exceptionally well in practice. By adaptively switching between greedy behavior and structured exploration, it offers a robust solution for real-world sequential decision-making tasks, finally bridging the gap between asymptotic theory and finite-time practice.

Summary updated

Abstract

Contextual bandits serve as a fundamental model for many sequential decision making tasks. The most popular theoretically justified approaches are based on the optimism principle. While these algorithms can be practical, they are known to be suboptimal asymptotically. On the other hand, existing asymptotically optimal algorithms for this problem do not exploit the linear structure in an optimal way and suffer from lower-order terms that dominate the regret in all practically interesting regimes. We start to bridge the gap by designing an algorithm that is asymptotically optimal and has good finite-time empirical performance. At the same time, we make connections to the recent literature on when exploration-free methods are effective. Indeed, if the distribution of contexts is well behaved, then our algorithm acts mostly greedily and enjoys sub-logarithmic regret. Furthermore, our approach is adaptive in the sense that it automatically detects the nice case. Numerical results demonstrate significant regret reductions by our method relative to several baselines.
BibTeX
@inproceedings{hao2020adaptive,
  author = {Botao Hao and Tor Lattimore and Csaba Szepesvári},
  title = {{Adaptive Exploration in Linear Contextual Bandit}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2020},
  url = {https://openreview.net/forum?id=6G35IBSFVI},
}
Figure