mlsanityData to 14 Oct 2026

Sparse Nonparametric Contextual Bandits

arXiv 2503.16382 ↗First posted 20 Mar 2025stat.ML cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

We study the benefits of sparsity in nonparametric contextual bandit problems, in which the set of candidate features is countably or uncountably infinite. Our contribution is two-fold. First, using a novel reduction to sequences of multi-armed bandit problems, 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 enables better regret bounds whenever the horizon is large enough relative to the sparsity and the number of actions.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 38 of its 109 references that are in the map. First posted on arXiv 20 Mar 2025.

Builds on

38 of 109 references.

References · 38

  1. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,621
  2. 2018On Lazy Training in Differentiable Programmingcited by 675
  3. 2014Breaking the Curse of Dimensionality with Convex Neural Networkscited by 331
  4. 2020Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oraclescited by 197
  5. 2013Bayesian Optimization in a Billion Dimensions via Random Embeddingscited by 182
  6. 2013Finite-Time Analysis of Kernelised Contextual Banditscited by 177
  7. 2020On Information Gain and Regret Bounds in Gaussian Process Banditscited by 158
  8. 2015High Dimensional Bayesian Optimisation and Bandits via Additive Modelscited by 139
  9. 2020Neural Thompson Samplingcited by 128
  10. 2016Corralling a Band of Bandit Algorithmscited by 100
  11. 2018Practical Contextual Bandits with Regression Oraclescited by 93
  12. 2017Mostly Exploration-Free Algorithms for Contextual Banditscited by 85
26 more
  1. 2021Adapting to Misspecification in Contextual Banditscited by 81
  2. 2021Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learningcited by 66
  3. 2020High-Dimensional Sparse Linear Banditscited by 61
  4. 2018High-Dimensional Bayesian Optimization via Additive Models with Overlapping Groupscited by 59
  5. 2021Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discriminationcited by 53
  6. 2019Doubly-Robust Lasso Banditcited by 49
  7. 2020Sparsity-Agnostic Lasso Banditcited by 44
  8. 2019Adaptive Exploration in Linear Contextual Banditcited by 43
  9. 2021Neural Contextual Bandits without Regretcited by 40
  10. 2018Approximation beats concentration? An approximation view on inference with smooth radial kernelscited by 33
  11. 2021Leveraging Good Representations in Linear Contextual Banditscited by 29
  12. 2013Exact Support Recovery for Sparse Spikes Deconvolutioncited by 22
  13. 2022Lifting the Information Ratio: An Information-Theoretic Analysis of Thompson Sampling for Contextual Banditscited by 19
  14. 2022PopArt: Efficient Sparse Regression and Experimental Design for Optimal Sparse Linear Banditscited by 17
  15. 2020Stochastic Linear Contextual Bandits with Diverse Contextscited by 16
  16. 2020Thresholded Lasso Banditcited by 16
  17. 2022Thompson Sampling for High-Dimensional Sparse Linear Contextual Banditscited by 16
  18. 2020On Frequentist Regret of Linear Thompson Samplingcited by 14
  19. 2020Continuum-Armed Bandits: A Function Space Perspectivecited by 8
  20. 2021Regret Lower Bound and Optimal Algorithm for High-Dimensional Contextual Linear Banditcited by 8
  21. 2024Local Anti-Concentration Class: Logarithmic Regret for Greedy Linear Contextual Banditcited by 8
  22. 2024Optimistic Information Directed Samplingcited by 7
  23. 2022Scalable Representation Learning in Linear Contextual Bandits with Constant Regret Guaranteescited by 5
  24. 2020Dimension Reduction in Contextual Online Learning via Nonparametric Variable Selectioncited by 3
  25. 2025Spike-and-Slab Posterior Sampling in High Dimensionscited by 3
  26. 2024Sparsity-Agnostic Linear Bandits with Adaptive Adversariescited by 2

Built on by

Not cited yet.