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.
The Challenge of Model Selection in Bandits
In traditional supervised learning, model selection is a well-understood process. Practitioners often use techniques like cross-validation to find the "sweet spot" between underfitting (using a model too simple to capture the data) and overfitting (using a model so complex it captures noise). However, in the realm of contextual bandits, model selection introduces a unique and difficult "Catch-22."
In a contextual bandit setting, a learner chooses actions based on observed contexts and only receives feedback (rewards) for the specific actions taken. This creates a fundamental tension:
- Exploration Cost: To determine if a complex model (e.g., a high-dimensional linear class) is superior to a simpler one, the learner must explore a wider variety of actions.
- The Regret Penalty: If the simpler model was actually sufficient, the extra exploration required by the complex model leads to significant "regret"—the cumulative loss of potential rewards.
- The Risk of Underfitting: Conversely, if the learner fails to explore enough to justify a complex model, they may remain stuck with a simple model that can never represent the optimal strategy.
Prior to this work, no algorithms could provide "luckiness" guarantees—regret bounds that scale with the complexity of the best model class in a sequence rather than the largest possible one—without prior knowledge of that complexity.
The ModCB Algorithm
This paper introduces ModCB (Model Selection for Contextual Bandits), the first algorithm designed to automatically adapt to the complexity of the optimal policy. ModCB operates on a sequence of nested linear policy classes ($\mathcal{F}_1 \subset \mathcal{F}_2 \subset \dots \subset \mathcal{F}_M$) where the dimension $d$ increases at each step.
Innovation: Faster Gap Estimation
The core innovation of ModCB is a subroutine called EstimateResidual. In a standard approach, comparing two models requires training both, which typically necessitates $O(d)$ samples. ModCB bypasses this requirement by using a novel statistical estimator for the "square loss gap" between two classes.
Drawing inspiration from U-statistics and variance estimation, the authors demonstrate that the improvement offered by a larger model can be estimated using only $O(\sqrt{d})$ samples. Because this gap can be detected faster than the model parameters themselves can be learned, the algorithm can test whether a higher-dimensional class is necessary without over-exploring. If the test indicates a significant potential for improvement, the algorithm "promotes" itself to the larger class and re-initializes its base learner.
Key Results and Theoretical Impact
ModCB provides the first positive result for model selection in an online learning setting with partial information that yields non-vacuous regret across all values of the optimal dimension.
- Sublinear Regret: The algorithm achieves a regret bound of $\tilde{O}(T^{2/3}d_{m^*}^{1/3})$, where $d_{m^*}$ is the dimension of the smallest class containing the optimal policy.
- Near-Optimality: For high-dimensional problems where $d_{m^*} \geq \sqrt{T}$, ModCB achieves a rate of $\tilde{O}(T^{3/4} + \sqrt{Td_{m^*}})$. This matches the "oracle" rate—the performance one would expect if they knew the correct dimension from the start—aside from a small penalty term.
- Validation: While primarily theoretical, the authors validated the algorithm using simulated data (detailed in Appendix A), showing that ModCB performs favorably against standard benchmarks like LinUCB in controlled environments.
Limitations and Future Directions
While ModCB represents a significant milestone, several challenges remain for future research:
- Realizability: The current proofs assume "realizability," meaning the optimal policy is strictly contained within one of the provided linear classes.
- Computational Overhead: The algorithm utilizes Exp4-IX as a base learner. While theoretically sound, this can be computationally expensive when dealing with very large policy classes.
- Environmental Assumptions: The proof currently requires a lower bound on the eigenvalues of the context distribution, ensuring the environment provides a sufficiently diverse set of contexts.
- The Oracle Gap: A theoretical gap still exists between ModCB's performance and a true Oracle across all ranges of $T$. Closing this gap remains an open question in the field of contextual bandits.
Summary updated