Sparse Nonparametric Contextual Bandits
This work addresses feature selection and regret minimization in contextual bandits, offering theoretical insights and algorithms for sparse settings, but it is incremental as it builds on existing bandit frameworks with specific sparsity assumptions.
The paper tackles the problem of learning relevant features and minimizing regret in contextual bandits by introducing sparse nonparametric contextual bandits, where the reward function is a linear combination of a small unknown set of features from a known infinite set. It provides lower bounds showing polynomial dependence on actions is unavoidable and demonstrates that a variant of Feel-Good Thompson Sampling achieves regret bounds matching these lower bounds up to logarithmic factors, with sparsity enabling better bounds in kernelized and neural contexts for large horizons.
This paper studies the problem of simultaneously learning relevant features and minimising regret in contextual bandit problems. We introduce and analyse a new class of contextual bandit problems, called sparse nonparametric contextual bandits, in which the expected reward function lies in the linear span of a small unknown set of features that belongs to a known infinite set of candidate features. We consider two notions of sparsity, for which the set of candidate features is either countable or uncountable. Our contribution is two-fold. First, we provide lower bounds on the minimax regret, which show that polynomial dependence on the number of actions is generally unavoidable in this setting. Second, we show that a variant of the Feel-Good Thompson Sampling algorithm enjoys regret bounds that match our lower bounds up to logarithmic factors of the horizon, and have logarithmic dependence on the effective number of candidate features. When we apply our results to kernelised and neural contextual bandits, we find that sparsity always enables better regret bounds, as long as the horizon is large enough relative to the sparsity and the number of actions.