mlsanityData to 7 Oct 2026

Neural Contextual Bandits without Regret

arXiv 2107.03144 ↗First posted 7 Jul 2021stat.ML cs.AI cs.LGcited by 40

Not on the map. Why?

Abstract (arXiv)

Contextual bandits are a rich model for sequential decision making given side information, with important applications, e.g., in recommender systems. We propose novel algorithms for contextual bandits harnessing neural networks to approximate the unknown reward function. We resolve the open problem of proving sublinear regret bounds in this setting for general context sequences, considering both fully-connected and convolutional networks. To this end, we first analyze NTK-UCB, a kernelized bandit optimization algorithm employing the Neural Tangent Kernel (NTK), and bound its regret in terms of the NTK maximum information gain γT, a complexity parameter capturing the difficulty of learning. Our bounds on γT for the NTK may be of independent interest. We then introduce our neural network based algorithm NN-UCB, and show that its regret closely tracks that of NTK-UCB. Under broad non-parametric assumptions about the reward function, our approach converges to the optimal policy at a tildeO(T-1/2d) rate, where d is the dimension of the context.

Key facts. Cited by 40 papers in the map (data through 7 Oct 2026). Builds on 34 of its 64 references that are in the map. First posted on arXiv 7 Jul 2021.

Builds on

34 of 64 references.

References · 34

  1. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,160
  2. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  3. 2018Gradient Descent Finds Global Minima of Deep Neural Networkscited by 572
  4. 2019On Exact Computation with an Infinitely Wide Neural Netcited by 572
  5. 2017On Kernelized Multi-armed Banditscited by 348
  6. 2019Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networkscited by 221
  7. 2014An Information-Theoretic Analysis of Thompson Samplingcited by 178
  8. 2013Finite-Time Analysis of Kernelised Contextual Banditscited by 177
  9. 2019Towards Understanding the Spectral Bias of Deep Learningcited by 173
  10. 2018Deep Bayesian Bandits Showdown: An Empirical Comparison of Bayesian Deep Networks for Thompson Samplingcited by 166
  11. 2020On Information Gain and Regret Bounds in Gaussian Process Banditscited by 156
  12. 2019Neural Tangents: Fast and Easy Infinite Neural Networks in Pythoncited by 149
22 more
  1. 2016Bayesian Optimization with Safety Constraints: Safe and Automatic Parameter Tuning in Roboticscited by 134
  2. 2020Neural Thompson Samplingcited by 127
  3. 2021Learning with invariances in random features and kernel modelscited by 89
  4. 2020Deep Equals Shallow for ReLU Networks in Kernel Regimescited by 83
  5. 2018Stagewise Safe Bayesian Optimization with Gaussian Processescited by 79
  6. 2017Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimizationcited by 77
  7. 2020Deep Neural Tangent Kernel and Laplace Kernel Have the Same RKHScited by 74
  8. 2020High-Dimensional Sparse Linear Banditscited by 61
  9. 2020Distributionally Robust Bayesian Optimizationcited by 60
  10. 2019Doubly-Robust Lasso Banditcited by 49
  11. 2020Bandit optimisation of functions in the Mat'ern kernel RKHScited by 40
  12. 2020Corruption-Tolerant Gaussian Process Bandit Optimizationcited by 34
  13. 2018Approximation beats concentration? An approximation view on inference with smooth radial kernelscited by 33
  14. 2016Multi-fidelity Gaussian Process Bandit Optimisationcited by 31
  15. 2021Approximation and Learning with Deep Convolutional Models: a Kernel Perspectivecited by 31
  16. 2021Batched Neural Banditscited by 22
  17. 2017Gaussian Process bandits with adaptive discretizationcited by 20
  18. 2018Tight Regret Bounds for Bayesian Optimization in One Dimensioncited by 20
  19. 2020On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spacescited by 19
  20. 2019Stochastic Bandits with Context Distributionscited by 18
  21. 2019No-Regret Learning in Unknown Games with Correlated Payoffscited by 18
  22. 2021Online Limited Memory Neural-Linear Bandits with Likelihood Matchingcited by 14

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 8; 2023: 10; 2024: 7; 2025: 10; 2026: 5.

40 papers.

Sort:

By area:

  1. 2022Contextual Bandits with Large Action Spaces: Made Practicalcited by 32
  2. 2022Sample-Then-Optimize Batch Neural Thompson Samplingcited by 25
  3. 2023Kernelized Reinforcement Learning with Order Optimal Regret Boundscited by 20
  4. 2022Federated Neural Banditscited by 17
  5. 2022An Optimization-based Algorithm for Non-stationary Kernel Bandits without Prior Knowledgecited by 17
  6. 2025Improved Regret Bounds for Gaussian Process Upper Confidence Bound in Bayesian Optimizationcited by 13
  7. 2022Graph Neural Network Banditscited by 10
  8. 2023Neural Contextual Bandits for Personalized Recommendationcited by 10
  9. 2025Gaussian Process Upper Confidence Bound Achieves Nearly-Optimal Regret in Noise-Free Gaussian Process Banditscited by 9
  10. 2023LLMs-augmented Contextual Banditcited by 8
  11. 2023Neural Exploitation and Exploration of Contextual Banditscited by 7
  12. 2024Neural Dueling Bandits: Preference-Based Optimization with Human Feedbackcited by 7
28 more
  1. 2024Meta Clustering of Neural Banditscited by 7
  2. 2022Provably and Practically Efficient Neural Contextual Banditscited by 6
  3. 2023On the Disconnect Between Theory and Practice of Neural Networks: Limits of the NTK Perspectivecited by 6
  4. 2023Adaptation to Misspecified Kernel Regularity in Kernelised Banditscited by 5
  5. 2023Training-Free Neural Active Learning with Initialization-Robustness Guaranteescited by 5
  6. 2025Neural Logistic Banditscited by 5
  7. 2023Representation-Driven Reinforcement Learningcited by 4
  8. 2024Sample-efficient Bayesian Optimisation Using Known Invariancescited by 4
  9. 2026Tighter Regret Lower Bound for Gaussian Process Bandits with Squared Exponential Kernel in Hyperspherecited by 4
  10. 2022Reward-Biased Maximum Likelihood Estimation for Neural Contextual Banditscited by 2
  11. 2023Neural-BO: A Black-box Optimization Algorithm using Deep Neural Networkscited by 2
  12. 2024Active Few-Shot Fine-Tuningcited by 2
  13. 2024Stochastic Bandits with ReLU Neural Networkscited by 2
  14. 2025Online Clustering of Dueling Banditscited by 2
  15. 2022Maximum entropy exploration in contextual bandits with neural networks and energy based modelscited by 1
  16. 2023Non-Stationary Contextual Bandit Learning via Neural Predictive Ensemble Samplingcited by 1
  17. 2024Graph Neural Thompson Samplingcited by 1
  18. 2025LNUCB-TA: Linear-nonlinear Hybrid Bandit Learning with Temporal Attentioncited by 1
  19. 2025Exploiting Concavity Information in Gaussian Process Contextual Bandit Optimizationcited by 1
  20. 2025Revisiting Clustering of Neural Bandits: Selective Reinitialization for Mitigating Loss of Plasticitycited by 1
  21. 2024OptEx: Expediting First-Order Optimization with Approximately Parallelized Iterationscited by 0
  22. 2025FRAUD-RLA: A new reinforcement learning adversarial attack against credit card fraud detectioncited by 0
  23. 2025Sparse Nonparametric Contextual Banditscited by 0
  24. 2025Neural Contextual Bandits Under Delayed Feedback Constraintscited by 0
  25. 2026Tractable Multinomial Logit Contextual Bandits with Non-Linear Utilitiescited by 0
  26. 2026Learning to Attack: A Bandit Approach to Adversarial Context Poisoningcited by 0
  27. 2026Logistic Bandits with tildeO(√dT) Regret without Context Diversity Assumptionscited by 0
  28. 2026Transferring Information Across Interventions in Causal Bayesian Optimizationcited by 0