mlsanityData to 7 Oct 2026

Provably and Practically Efficient Neural Contextual Bandits

arXiv 2206.00099 ↗First posted 31 May 2022stat.ML cs.LGcited by 6

Not on the map. Why?

Abstract (arXiv)

We consider the neural contextual bandit problem. In contrast to the existing work which primarily focuses on ReLU neural nets, we consider a general set of smooth activation functions. Under this more general setting, (i) we derive non-asymptotic error bounds on the difference between an overparameterized neural net and its corresponding neural tangent kernel, (ii) we propose an algorithm with a provably sublinear regret bound that is also efficient in the finite regime as demonstrated by empirical studies. The non-asymptotic error bounds may be of broader interest as a tool to establish the relation between the smoothness of the activation functions in neural contextual bandits and the smoothness of the kernels in kernel bandits.

Key facts. Cited by 6 papers in the map (data through 7 Oct 2026). Builds on 24 of its 45 references that are in the map. First posted on arXiv 31 May 2022.

Builds on

24 of 45 references.

References · 24

  1. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  2. 2020Implicit Neural Representations with Periodic Activation Functionscited by 2,214
  3. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 784
  4. 2018Gradient Descent Finds Global Minima of Deep Neural Networkscited by 572
  5. 2019On Exact Computation with an Infinitely Wide Neural Netcited by 572
  6. 2017On Kernelized Multi-armed Banditscited by 348
  7. 2019Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networkscited by 221
  8. 2013Finite-Time Analysis of Kernelised Contextual Banditscited by 177
  9. 2018Deep Bayesian Bandits Showdown: An Empirical Comparison of Bayesian Deep Networks for Thompson Samplingcited by 166
  10. 2016Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivitycited by 138
  11. 2020On the linearity of large non-linear models: when and why the tangent kernel is constantcited by 129
  12. 2020Neural Thompson Samplingcited by 127
12 more
  1. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  2. 2019Generalization Error Bounds of Gradient Descent for Learning Over-parameterized Deep ReLU Networkscited by 60
  3. 2021Gaussian Process Bandit Optimization with Few Batchescited by 57
  4. 2021High-Dimensional Experimental Design and Kernel Banditscited by 55
  5. 2019Nearly Minimax-Optimal Regret for Linearly Parameterized Banditscited by 54
  6. 2021Optimal Order Simple Regret for Gaussian Process Banditscited by 52
  7. 2019A Survey on Practical Applications of Multi-Armed and Contextual Banditscited by 44
  8. 2021Neural Contextual Bandits without Regretcited by 40
  9. 2020A Domain-Shrinking based Bayesian Optimization Algorithm with Order-Optimal Regret Performancecited by 38
  10. 2021Batched Neural Banditscited by 22
  11. 2021Uniform Generalization Bounds for Overparameterized Neural Networkscited by 21
  12. 2021Open Problem: Tight Online Confidence Intervals for RKHS Elementscited by 13

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 1; 2024: 1; 2025: 3; 2026: 1.

6 papers.

  1. 2026Tighter Regret Lower Bound for Gaussian Process Bandits with Squared Exponential Kernel in Hyperspherecited by 4
  2. 2024Stochastic Bandits with ReLU Neural Networkscited by 2
  3. 2025Online Clustering of Dueling Banditscited by 2
  4. 2025Provable Anytime Ensemble Sampling Algorithms in Nonlinear Contextual Banditscited by 2
  5. 2023Non-Stationary Contextual Bandit Learning via Neural Predictive Ensemble Samplingcited by 1
  6. 2025Neural Contextual Bandits Under Delayed Feedback Constraintscited by 0