# Contextual Bandits with Online Neural Regression

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Dec 2023.

## Built on by (most cited first, 7 of 7)

- [PageRank Bandits for Link Prediction](https://mlsanity.com/paper/2411.01410/) (2024)
- [Neural Contextual Bandits for Personalized Recommendation](https://mlsanity.com/paper/2312.14037/) (2023)
- [Meta Clustering of Neural Bandits](https://mlsanity.com/paper/2408.05586/) (2024)
- [Active Human Feedback Collection via Neural Contextual Dueling Bandits](https://mlsanity.com/paper/2504.12016/) (2025)
- [Neural Variance-aware Dueling Bandits with Deep Representation and Shallow Exploration](https://mlsanity.com/paper/2506.01250/) (2025)
- [Learning to Attack: A Bandit Approach to Adversarial Context Poisoning](https://mlsanity.com/paper/2603.00567/) (2026)
- [Replicable Bandits with UCB based Exploration](https://mlsanity.com/paper/2604.20024/) (2026)

## Abstract (arXiv)

Recent works have shown a reduction from contextual bandits to online regression under a realizability assumption [Foster and Rakhlin, 2020, Foster and Krishnamurthy, 2021]. In this work, we investigate the use of neural networks for such online regression and associated Neural Contextual Bandits (NeuCBs). Using existing results for wide networks, one can readily show a O(√T) regret for online regression with square loss, which via the reduction implies a O(√K T3/4) regret for NeuCBs. Departing from this standard approach, we first show a O(log T) regret for online regression with almost convex losses that satisfy QG (Quadratic Growth) condition, a generalization of the PL (Polyak-L ojasiewicz) condition, and that have a unique minima. Although not directly applicable to wide networks since they do not have unique minima, we show that adding a suitable small random perturbation to the network predictions surprisingly makes the loss satisfy QG with unique minima. Based on such a perturbed prediction, we show a O(log T) regret for online regression with both squared loss and KL loss, and subsequently convert these respectively to tildeO(√KT) and tildeO(√KL^* + K) regret for NeuCB, where L^* is the loss of the best policy. Separately, we also show that existing regret bounds for NeuCBs are Omega(T) or assume i.i.d. contexts, unlike this work. Finally, our experimental results on various datasets demonstrate that our algorithms, especially the one based on KL loss, persistently outperform existing algorithms.