mlsanityData to 14 Oct 2026

High-dimensional Nonparametric Contextual Bandit Problem

arXiv 2505.14102 ↗First posted 20 May 2025stat.ML cs.LG stat.MEcited by 1

Not on the map. Why?

Abstract (arXiv)

We consider the kernelized contextual bandit problem with a large feature space. This problem involves K arms, and the goal of the forecaster is to maximize the cumulative rewards through learning the relationship between the contexts and the rewards. It serves as a general framework for various decision-making scenarios, such as personalized online advertising and recommendation systems. Kernelized contextual bandits generalize the linear contextual bandit problem and offers a greater modeling flexibility. Existing methods, when applied to Gaussian kernels, yield a trivial bound of O(T) when we consider Omega(log T) feature dimensions. To address this, we introduce stochastic assumptions on the context distribution and show that no-regret learning is achievable even when the number of dimensions grows up to the number of samples. Furthermore, we analyze lenient regret, which allows a per-round regret of at most Delta > 0. We derive the rate of lenient regret in terms of Delta.

Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 28 of its 51 references that are in the map. First posted on arXiv 20 May 2025.

Builds on

28 of 51 references.

References · 28

  1. 2019Benign Overfitting in Linear Regressioncited by 549
  2. 2019Scalable Global Optimization via Local Bayesian Optimizationcited by 374
  3. 2017On Kernelized Multi-armed Banditscited by 352
  4. 2018Just Interpolate: Kernel "Ridgeless" Regression Can Generalizecited by 190
  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. 2020Benign overfitting in ridge regressioncited by 153
  9. 2021High-Dimensional Bayesian Optimization with Sparse Axis-Aligned Subspacescited by 141
  10. 2015High Dimensional Bayesian Optimisation and Bandits via Additive Modelscited by 139
  11. 2020Neural Thompson Samplingcited by 128
  12. 2020Re-Examining Linear Embeddings for High-Dimensional Bayesian Optimizationcited by 92
16 more
  1. 2020High-Dimensional Sparse Linear Banditscited by 61
  2. 2020Open Benchmarking for Click-Through Rate Predictioncited by 53
  3. 2019No-Regret Bayesian Optimization with Unknown Hyperparameterscited by 51
  4. 2019Doubly-Robust Lasso Banditcited by 49
  5. 2020Sparsity-Agnostic Lasso Banditcited by 44
  6. 2019Adaptive Exploration in Linear Contextual Banditcited by 43
  7. 2020Kernel regression in high dimensions: Refined analysis beyond double descentcited by 39
  8. 2018Balanced Linear Contextual Banditscited by 30
  9. 2020Algorithms for Non-Stationary Generalized Linear Banditscited by 24
  10. 2021A Simple Unified Framework for High Dimensional Bandit Problemscited by 21
  11. 2022PopArt: Efficient Sparse Regression and Experimental Design for Optimal Sparse Linear Banditscited by 17
  12. 2021Lenient Regret and Good-Action Identification in Gaussian Process Banditscited by 12
  13. 2020Delay-Adaptive Learning in Generalized Linear Contextual Banditscited by 8
  14. 2020Lenient Regret for Multi-Armed Banditscited by 8
  15. 2023Adversarial Contextual Bandits Go Kernelizedcited by 6
  16. 2023High-dimensional Contextual Bandit Problem without Sparsitycited by 5

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Tighter Regret Lower Bound for Gaussian Process Bandits with Squared Exponential Kernel in Hyperspherecited by 4