Navigating Sparsities in High-Dimensional Linear Contextual Bandits
This work addresses the challenge of sparsity in high-dimensional bandits for machine learning practitioners, offering a more flexible and generalizable method compared to existing approaches.
The paper tackles high-dimensional linear contextual bandit problems by introducing a pointwise estimator that adaptively handles sparsity in model parameters and context covariance matrices, leading to improved regret bounds and efficient performance in heterogeneous settings.
High-dimensional linear contextual bandit problems remain a significant challenge due to the curse of dimensionality. Existing methods typically consider either the model parameters to be sparse or the eigenvalues of context covariance matrices to be (approximately) sparse, lacking general applicability due to the rigidity of conventional reward estimators. To overcome this limitation, a powerful pointwise estimator is introduced in this work that adaptively navigates both kinds of sparsity. Based on this pointwise estimator, a novel algorithm, termed HOPE, is proposed. Theoretical analyses demonstrate that HOPE not only achieves improved regret bounds in previously discussed homogeneous settings (i.e., considering only one type of sparsity) but also, for the first time, efficiently handles two new challenging heterogeneous settings (i.e., considering a mixture of two types of sparsity), highlighting its flexibility and generality. Experiments corroborate the superiority of HOPE over existing methods across various scenarios.