# Provable Anytime Ensemble Sampling Algorithms in Nonlinear Contextual Bandits

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 40 of its 54 references that are in the map.
- First posted on arXiv 12 Oct 2025.

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

- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Deep Exploration via Bootstrapped DQN](https://mlsanity.com/paper/1602.04621/) (2016)
- [(More) Efficient Reinforcement Learning via Posterior Sampling](https://mlsanity.com/paper/1306.0940/) (2013)
- [Neural Thompson Sampling](https://mlsanity.com/paper/2010.00827/) (2020)
- [Sequential Experimental Design for Transductive Linear Bandits](https://mlsanity.com/paper/1906.08399/) (2019)
- [What Doubling Tricks Can and Can't Do for Multi-Armed Bandits](https://mlsanity.com/paper/1803.06971/) (2018)
- [Neural Contextual Bandits with Deep Representation and Shallow Exploration](https://mlsanity.com/paper/2012.01780/) (2020)
- [Randomized Exploration in Generalized Linear Bandits](https://mlsanity.com/paper/1906.08947/) (2019)
- [Ensemble Sampling](https://mlsanity.com/paper/1705.07347/) (2017)
- [Randomized Exploration for Reinforcement Learning with General Value Function Approximation](https://mlsanity.com/paper/2106.07841/) (2021)
- [EE-Net: Exploitation-Exploration Neural Networks in Contextual Bandits](https://mlsanity.com/paper/2110.03177/) (2021)
- [Generalized Self-Concordant Functions: A Recipe for Newton-Type Methods](https://mlsanity.com/paper/1703.04599/) (2017)
- [Improved Confidence Bounds for the Linear Logistic Model and Applications to Linear Bandits](https://mlsanity.com/paper/2011.11222/) (2020)
- [An Efficient Algorithm For Generalized Linear Bandit: Online Stochastic Gradient Descent and Thompson Sampling](https://mlsanity.com/paper/2006.04012/) (2020)
- [Perturbed-History Exploration in Stochastic Linear Bandits](https://mlsanity.com/paper/1903.09132/) (2019)
- [Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlo](https://mlsanity.com/paper/2305.18246/) (2023)
- [A Unified Confidence Sequence for Generalized Linear Models, with Applications to Bandits](https://mlsanity.com/paper/2407.13977/) (2024)
- [MOTS: Minimax Optimal Thompson Sampling](https://mlsanity.com/paper/2003.01803/) (2020)
- [Offline Neural Contextual Bandits: Pessimism, Optimization and Generalization](https://mlsanity.com/paper/2111.13807/) (2021)
- [An Analysis of Ensemble Sampling](https://mlsanity.com/paper/2203.01303/) (2022)
- [Langevin Monte Carlo for Contextual Bandits](https://mlsanity.com/paper/2206.11254/) (2022)
- [Generalized Linear Bandits with Limited Adaptivity](https://mlsanity.com/paper/2404.06831/) (2024)
- [Model-based Reinforcement Learning for Continuous Control with Posterior Sampling](https://mlsanity.com/paper/2012.09613/) (2020)
- [A Contextual-bandit-based Approach for Informed Decision-making in Clinical Trials](https://mlsanity.com/paper/1809.00258/) (2018)
- [Learning Neural Contextual Bandits Through Perturbed Rewards](https://mlsanity.com/paper/2201.09910/) (2022)
- [Randomized Exploration in Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2404.10728/) (2024)
- [Posterior Sampling for Deep Reinforcement Learning](https://mlsanity.com/paper/2305.00477/) (2023)
- [Combinatorial Neural Bandits](https://mlsanity.com/paper/2306.00242/) (2023)
- [Generalized Linear Bandits: Almost Optimal Regret with One-Pass Update](https://mlsanity.com/paper/2507.11847/) (2025)
- [Deep Exploration for Recommendation Systems](https://mlsanity.com/paper/2109.12509/) (2021)

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

- [Sharp analysis of linear ensemble sampling](https://mlsanity.com/paper/2602.08026/) (2026)
- [Linear Ensemble Sampling with Smaller Ensembles](https://mlsanity.com/paper/2609.13954/) (2026)

## Abstract (arXiv)

We provide a unified algorithmic framework for ensemble sampling in nonlinear contextual bandits and develop corresponding regret bounds for two most common nonlinear contextual bandit settings: Generalized Linear Model Ensemble Sampling (GLM-ES) for generalized linear contextual bandits and Neural Ensemble Sampling (Neural-ES) for neural contextual bandits. Both methods maintain multiple estimators for the reward model parameters via maximum likelihood estimation on randomly perturbed data. We prove high-probability frequentist regret bounds of widetildeO(d3/2 √T + d4) for GLM-ES and widetildeO(widetilded3/2 √T) for Neural-ES, where d is the dimension of feature vectors, widetilded is the effective dimension of a neural tangent kernel (NTK) matrix and T is the number of rounds. The regret bound of GLM-ES matches the state-of-the-art result of randomized exploration algorithms in generalized linear bandit setting. In the theoretical analysis, we introduce techniques that address challenges specific to nonlinear models. Practically, we remove fixed-time horizon assumption by developing anytime versions of our algorithms, suitable when T is unknown. Finally, we empirically evaluate GLM-ES, Neural-ES and their anytime variants, demonstrating strong performance. Overall, our results establish ensemble sampling as a provable and practical randomized exploration approach for nonlinear contextual bandits.