# Neural Contextual Bandits without Regret

arXiv: https://arxiv.org/abs/2107.03144 · HTML: https://mlsanity.com/paper/2107.03144/

## Key facts

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

## Builds on (most cited first, 30 of 34)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Gradient Descent Finds Global Minima of Deep Neural Networks](https://mlsanity.com/paper/1811.03804/) (2018)
- [On Exact Computation with an Infinitely Wide Neural Net](https://mlsanity.com/paper/1904.11955/) (2019)
- [On Kernelized Multi-armed Bandits](https://mlsanity.com/paper/1704.00445/) (2017)
- [Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks](https://mlsanity.com/paper/1905.13210/) (2019)
- [An Information-Theoretic Analysis of Thompson Sampling](https://mlsanity.com/paper/1403.5341/) (2014)
- [Finite-Time Analysis of Kernelised Contextual Bandits](https://mlsanity.com/paper/1309.6869/) (2013)
- [Towards Understanding the Spectral Bias of Deep Learning](https://mlsanity.com/paper/1912.01198/) (2019)
- [Deep Bayesian Bandits Showdown: An Empirical Comparison of Bayesian Deep Networks for Thompson Sampling](https://mlsanity.com/paper/1802.09127/) (2018)
- [On Information Gain and Regret Bounds in Gaussian Process Bandits](https://mlsanity.com/paper/2009.06966/) (2020)
- [Neural Tangents: Fast and Easy Infinite Neural Networks in Python](https://mlsanity.com/paper/1912.02803/) (2019)
- [Bayesian Optimization with Safety Constraints: Safe and Automatic Parameter Tuning in Robotics](https://mlsanity.com/paper/1602.04450/) (2016)
- [Neural Thompson Sampling](https://mlsanity.com/paper/2010.00827/) (2020)
- [Learning with invariances in random features and kernel models](https://mlsanity.com/paper/2102.13219/) (2021)
- [Deep Equals Shallow for ReLU Networks in Kernel Regimes](https://mlsanity.com/paper/2009.14397/) (2020)
- [Stagewise Safe Bayesian Optimization with Gaussian Processes](https://mlsanity.com/paper/1806.07555/) (2018)
- [Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization](https://mlsanity.com/paper/1706.00090/) (2017)
- [Deep Neural Tangent Kernel and Laplace Kernel Have the Same RKHS](https://mlsanity.com/paper/2009.10683/) (2020)
- [Distributionally Robust Bayesian Optimization](https://mlsanity.com/paper/2002.09038/) (2020)
- [High-Dimensional Sparse Linear Bandits](https://mlsanity.com/paper/2011.04020/) (2020)
- [Doubly-Robust Lasso Bandit](https://mlsanity.com/paper/1907.11362/) (2019)
- [Bandit optimisation of functions in the Mat'ern kernel RKHS](https://mlsanity.com/paper/2001.10396/) (2020)
- [Corruption-Tolerant Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2003.01971/) (2020)
- [Approximation beats concentration? An approximation view on inference with smooth radial kernels](https://mlsanity.com/paper/1801.03437/) (2018)
- [Multi-fidelity Gaussian Process Bandit Optimisation](https://mlsanity.com/paper/1603.06288/) (2016)
- [Approximation and Learning with Deep Convolutional Models: a Kernel Perspective](https://mlsanity.com/paper/2102.10032/) (2021)
- [Batched Neural Bandits](https://mlsanity.com/paper/2102.13028/) (2021)
- [Gaussian Process bandits with adaptive discretization](https://mlsanity.com/paper/1712.01447/) (2017)
- [Tight Regret Bounds for Bayesian Optimization in One Dimension](https://mlsanity.com/paper/1805.11792/) (2018)

## Built on by (most cited first, 30 of 40)

- [Contextual Bandits with Large Action Spaces: Made Practical](https://mlsanity.com/paper/2207.05836/) (2022)
- [Sample-Then-Optimize Batch Neural Thompson Sampling](https://mlsanity.com/paper/2210.06850/) (2022)
- [Kernelized Reinforcement Learning with Order Optimal Regret Bounds](https://mlsanity.com/paper/2306.07745/) (2023)
- [Federated Neural Bandits](https://mlsanity.com/paper/2205.14309/) (2022)
- [An Optimization-based Algorithm for Non-stationary Kernel Bandits without Prior Knowledge](https://mlsanity.com/paper/2205.14775/) (2022)
- [Improved Regret Bounds for Gaussian Process Upper Confidence Bound in Bayesian Optimization](https://mlsanity.com/paper/2506.01393/) (2025)
- [Graph Neural Network Bandits](https://mlsanity.com/paper/2207.06456/) (2022)
- [Neural Contextual Bandits for Personalized Recommendation](https://mlsanity.com/paper/2312.14037/) (2023)
- [Gaussian Process Upper Confidence Bound Achieves Nearly-Optimal Regret in Noise-Free Gaussian Process Bandits](https://mlsanity.com/paper/2502.19006/) (2025)
- [LLMs-augmented Contextual Bandit](https://mlsanity.com/paper/2311.02268/) (2023)
- [Neural Exploitation and Exploration of Contextual Bandits](https://mlsanity.com/paper/2305.03784/) (2023)
- [Neural Dueling Bandits: Preference-Based Optimization with Human Feedback](https://mlsanity.com/paper/2407.17112/) (2024)
- [Meta Clustering of Neural Bandits](https://mlsanity.com/paper/2408.05586/) (2024)
- [Provably and Practically Efficient Neural Contextual Bandits](https://mlsanity.com/paper/2206.00099/) (2022)
- [On the Disconnect Between Theory and Practice of Neural Networks: Limits of the NTK Perspective](https://mlsanity.com/paper/2310.00137/) (2023)
- [Neural Logistic Bandits](https://mlsanity.com/paper/2505.02069/) (2025)
- [Adaptation to Misspecified Kernel Regularity in Kernelised Bandits](https://mlsanity.com/paper/2304.13830/) (2023)
- [Training-Free Neural Active Learning with Initialization-Robustness Guarantees](https://mlsanity.com/paper/2306.04454/) (2023)
- [Representation-Driven Reinforcement Learning](https://mlsanity.com/paper/2305.19922/) (2023)
- [Sample-efficient Bayesian Optimisation Using Known Invariances](https://mlsanity.com/paper/2410.16972/) (2024)
- [Tighter Regret Lower Bound for Gaussian Process Bandits with Squared Exponential Kernel in Hypersphere](https://mlsanity.com/paper/2602.17940/) (2026)
- [Online Clustering of Dueling Bandits](https://mlsanity.com/paper/2502.02079/) (2025)
- [Reward-Biased Maximum Likelihood Estimation for Neural Contextual Bandits](https://mlsanity.com/paper/2203.04192/) (2022)
- [Neural-BO: A Black-box Optimization Algorithm using Deep Neural Networks](https://mlsanity.com/paper/2303.01682/) (2023)
- [Active Few-Shot Fine-Tuning](https://mlsanity.com/paper/2402.15441/) (2024)
- [Stochastic Bandits with ReLU Neural Networks](https://mlsanity.com/paper/2405.07331/) (2024)
- [Maximum entropy exploration in contextual bandits with neural networks and energy based models](https://mlsanity.com/paper/2210.06302/) (2022)
- [Non-Stationary Contextual Bandit Learning via Neural Predictive Ensemble Sampling](https://mlsanity.com/paper/2310.07786/) (2023)
- [Graph Neural Thompson Sampling](https://mlsanity.com/paper/2406.10686/) (2024)
- [LNUCB-TA: Linear-nonlinear Hybrid Bandit Learning with Temporal Attention](https://mlsanity.com/paper/2503.00387/) (2025)

## 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.