Model selection for contextual bandits

Dylan J. Foster, Akshay Krishnamurthy, Haipeng Luo

Abstract

We introduce the problem of model selection for contextual bandits, where a learner must adapt to the complexity of the optimal policy while balancing exploration and exploitation. Our main result is a new model selection guarantee for linear contextual bandits. We work in the stochastic realizable setting with a sequence of nested linear policy classes of dimension $d_1 < d_2 < \dots$, where the $m^\star$-th class contains the optimal policy, and we design an algorithm that achieves $\tilde{O}(T^{2/3}d^{1/3}_{m^\star})$ regret with no prior knowledge of the optimal dimension $d_{m^\star}$. The algorithm also achieves regret $\tilde{O}(T^{3/4} + \sqrt{Td_{m^\star}})$, which is optimal for $d_{m^{\star}}\geq{}\sqrt{T}$. This is the first model selection result for contextual bandits with non-vacuous regret for all values of $d_{m^\star}$, and to the best of our knowledge is the first positive result of this type for any online learning setting with partial information. The core of the algorithm is a new estimator for the gap in the best loss achievable by two linear policy classes, which we show admits a convergence rate faster than the rate required to learn the parameters for either class.

1. Introduction

In machine learning, model selection involves choosing a hypothesis class that balances bias and variance. In the contextual bandit setting—where a learner selects actions based on contexts to maximize rewards—this tradeoff is particularly acute. A class that is too restrictive (low dimension) suffers from high bias, while a class that is too expressive (high dimension) requires extensive exploration, leading to high estimation error.

Ideally, a learner should achieve low regret if the true optimal policy is simple, even if the learner considers a much larger ambient hypothesis space. However, prior to this work, it was unclear if such adaptation was possible without prior knowledge of the optimal model's complexity. This paper introduces ModCB, the first algorithm for linear contextual bandits that automatically adapts to the complexity of the optimal policy.

2. Problem Setting

We consider the stochastic realizable linear setting. The learner is presented with a sequence of nested linear policy classes $\mathcal{F}_1 \subset \mathcal{F}_2 \subset \dots \subset \mathcal{F}_M$ with dimensions $d_1 < d_2 < \dots < d_M$. There exists an unknown "true" class $m^*$ such that the optimal policy resides in $\mathcal{F}_{m^*}$. The goal is to minimize regret relative to the optimal policy in $\mathcal{F}_{m^*}$ without knowing $m^*$ or $d_{m^*}$ beforehand.

3. The ModCB Algorithm

The proposed algorithm, ModCB (Model Selection for Contextual Bandits), employs a hierarchical approach to model complexity.

3.1 Agnostic Base Learning

ModCB begins by acting as if the simplest class, $\mathcal{F}_1$, is correct. It utilizes a modified version of the Exp4-IX algorithm as its base learner. Unlike standard linear bandit algorithms such as LinUCB, which assume the current model class is perfectly specified, this agnostic learner can handle the bias inherent in smaller, potentially misspecified classes.

3.2 Statistical Gap Estimation

The primary innovation of ModCB is a statistical test called EstimateResidual. Periodically, the algorithm uses a small amount of data collected via uniform exploration to test whether a more complex class $\mathcal{F}_i$ would offer a significant performance improvement over the current class.

Crucially, the authors demonstrate that the improvement (the gap in square loss) between two classes of dimension $d$ can be estimated using only $O(\sqrt{d})$ samples. This is a significant improvement over standard regression, which requires $O(d)$ samples to learn the model parameters themselves. This "sublinear" estimation allows the learner to decide when to transition to a more complex model without incurring the prohibitive regret associated with high-dimensional exploration.

4. Theoretical Results

ModCB provides the first non-vacuous regret guarantees for model selection in this setting:

  • Regret Bound: The algorithm achieves a regret of $\tilde{O}(T^{2/3} d_{m^*}^{1/3})$. Notably, this bound is independent of the maximum dimension $d_M$ of the largest class in the hierarchy.
  • Oracle Parity: For regimes where $d_{m^*} \geq \sqrt{T}$, the algorithm achieves a regret of $\tilde{O}(T^{3/4} + \sqrt{T} d_{m^*})$, matching the optimal rate achievable by an "Oracle" that knows $d_{m^*}$ in advance.

5. Empirical Validation

The authors validated ModCB using a synthetic environment with $K=2$ actions and an ambient dimension of $d=1000$. The ground truth was constructed such that only the first $d_{m^*} = 10$ coordinates were relevant to the optimal policy.

In simulations, ModCB significantly outperformed LinUCB (which operated on the full 1000 dimensions). Interestingly, ModCB occasionally outperformed the Oracle learner. This occurs because ModCB starts in a lower-dimensional space, allowing it to converge to a "good enough" policy faster than an Oracle attempting to learn the exact parameters of the 10-dimensional space from the outset.

6. Discussion and Future Work

A key insight of this work is that the presence of contexts makes model selection possible in bandits, a task previously thought to be impossible in the non-contextual multi-armed bandit setting. The ability to estimate the "gap" between models more efficiently than the models themselves is the cornerstone of this result.

However, several challenges remain. The current analysis requires a lower bound on the minimum eigenvalue of the feature covariance matrix, a condition that may not hold in settings with redundant features. Additionally, the computational complexity of the base learner and the sequential testing process is higher than that of simple greedy methods. Future research may focus on relaxing the eigenvalue condition, closing the gap between the $T^{2/3}$ and $T^{1/2}$ regret rates, and extending these sublinear gap tests to non-linear model classes such as neural networks.

Summary updated

Abstract

We introduce the problem of model selection for contextual bandits, where a learner must adapt to the complexity of the optimal policy while balancing exploration and exploitation. Our main result is a new model selection guarantee for linear contextual bandits. We work in the stochastic realizable setting with a sequence of nested linear policy classes of dimension $d_1 < d_2 < \ldots$, where the $m^\star$-th class contains the optimal policy, and we design an algorithm that achieves $\tilde{O}(T^{2/3}d^{1/3}_{m^\star})$ regret with no prior knowledge of the optimal dimension $d_{m^\star}$. The algorithm also achieves regret $\tilde{O}(T^{3/4} + \sqrt{Td_{m^\star}})$, which is optimal for $d_{m^{\star}}\geq{}\sqrt{T}$. This is the first model selection result for contextual bandits with non-vacuous regret for all values of $d_{m^\star}$, and to the best of our knowledge is the first positive result of this type for any online learning setting with partial information. The core of the algorithm is a new estimator for the gap in the best loss achievable by two linear policy classes, which we show admits a convergence rate faster than the rate required to learn the parameters for either class.
BibTeX
@inproceedings{foster2019model,
  author = {Dylan J. Foster and Akshay Krishnamurthy and Haipeng Luo},
  title = {{Model selection for contextual bandits}},
  booktitle = {NeurIPS},
  year = {2019},
  url = {https://openreview.net/forum?id=BPoee5TnUmk},
}
Figure