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, such as personalized recommendation and clinical trials. While popular approaches like LinUCB and Thompson Sampling are practical, they often lack asymptotic optimality. Conversely, existing asymptotically optimal algorithms frequently suffer from poor short-term performance. This paper introduces the Optimal Allocation Matching (OAM) algorithm, which bridges this gap by tracking an optimal allocation of actions. OAM achieves instance-dependent asymptotic optimality while maintaining strong empirical performance in finite-time horizons.

Introduction: The Exploration-Exploitation Gap

In linear contextual bandits, an agent observes a context, chooses an action, and receives a reward that is a linear function of the context-action features. The primary challenge is balancing exploration (learning the reward function) with exploitation (choosing the best action).

Standard algorithms like LinUCB rely on the "optimism in the face of uncertainty" principle. While effective in practice, they are known to be suboptimal in the long run. On the other hand, theoretically "perfect" algorithms often require excessive initial exploration, making them impractical for real-world applications where short-term performance is critical. The goal of this work is to develop an algorithm that is both asymptotically optimal and empirically efficient.

The Optimal Allocation Matching (OAM) Algorithm

The proposed OAM algorithm moves beyond simple optimism by solving a convex optimization problem to determine the "ideal" distribution of pulls across actions for any given context. This distribution is designed to minimize regret while ensuring enough information is gathered to distinguish the optimal action from suboptimal ones.

Key Algorithmic Components

  1. Adaptive Switching: In each round, OAM evaluates whether the current data is sufficient to identify the optimal action. If a specific criterion is met, the algorithm exploits the greedy choice; otherwise, it enters an exploration phase.
  2. Three-Tiered Exploration: When exploration is necessary, OAM chooses between:
  3. Forced Exploration: Ensures the covariance matrix remains invertible.
  4. Unwasted Exploration: Follows the calculated optimal allocation.
  5. Optimistic Fallback: Uses a LinUCB-style choice if the optimal allocation is not yet well-defined.
  6. Computational Efficiency: To avoid the overhead of solving optimization problems every round, OAM employs "lazy updates," re-calculating the allocation only when the volume of information (the determinant of the covariance matrix) increases significantly.
Regret comparison between OAM and LinUCB in fixed action set scenarios with varying gap parameters (u).

Key Insights: Rich Contexts and Bounded Regret

A significant theoretical contribution of this paper is the identification of the "Rich Context" phenomenon. If the distribution of contexts is sufficiently diverse—meaning the optimal actions for different contexts span the entire feature space—the environment naturally provides enough information for exploration.

In such "rich" settings, OAM (and even LinUCB, to an extent) can achieve bounded regret, where the total regret stops growing after a finite number of rounds. This happens because the variety of contexts allows the agent to learn the global reward parameters even while acting greedily on most individual contexts.

Empirical Results

The authors evaluated OAM against several baselines, including LinUCB, OSSB, and LinTS, across various synthetic scenarios.

  • Fixed Action Sets: OAM significantly outperforms LinUCB in scenarios with small gaps between the best and second-best actions, as shown in Figure 1.
  • Large Action Spaces: Unlike structured bandit solvers like OSSB, which can struggle as the number of actions ($K$) grows, OAM remains stable and efficient by fully leveraging the linear structure of the problem.
  • Bounded Regret Verification: Simulations confirmed that in rich-context environments, OAM's regret curve flattens, demonstrating the practical realization of bounded regret.
Demonstrations of bounded regret (left) and performance in large action spaces (K=100) against multiple baselines (right).

Conclusion

OAM represents a significant step toward unifying asymptotic theory and finite-time practice in contextual bandits. By matching optimal allocations and adaptively switching between exploration and exploitation, it provides a robust framework for sequential decision-making. Future work includes extending these guarantees to continuous context spaces and further reducing the computational overhead of the optimization step.

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 and Thompson sampl...
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