High-dimensional Contextual Bandit Problem without Sparsity
This work addresses the high-dimensional contextual bandit problem for machine learning practitioners, offering a novel approach without sparsity assumptions, though it appears incremental as it builds on existing overparameterized model findings.
The paper tackles the high-dimensional linear contextual bandit problem without assuming sparsity in regression coefficients, using overparameterized models and minimum-norm interpolating estimators to analyze performance under small effective ranks; it proposes explore-then-commit algorithms, derives optimal rates in terms of budget T, and validates them through simulations.
In this research, we investigate the high-dimensional linear contextual bandit problem where the number of features $p$ is greater than the budget $T$, or it may even be infinite. Differing from the majority of previous works in this field, we do not impose sparsity on the regression coefficients. Instead, we rely on recent findings on overparameterized models, which enables us to analyze the performance of the minimum-norm interpolating estimator when data distributions have small effective ranks. We propose an explore-then-commit (EtC) algorithm to address this problem and examine its performance. Through our analysis, we derive the optimal rate of the ETC algorithm in terms of $T$ and show that this rate can be achieved by balancing exploration and exploitation. Moreover, we introduce an adaptive explore-then-commit (AEtC) algorithm that adaptively finds the optimal balance. We assess the performance of the proposed algorithms through a series of simulations.