# Sample-Then-Optimize Batch Neural Thompson Sampling

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

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- Builds on 49 of its 75 references that are in the map.
- First posted on arXiv 13 Oct 2022.

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

- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [Simple and Scalable Predictive Uncertainty Estimation using Deep Ensembles](https://mlsanity.com/paper/1612.01474/) (2016)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [OpenAI Gym](https://mlsanity.com/paper/1606.01540/) (2016)
- [A Tutorial on Bayesian Optimization](https://mlsanity.com/paper/1807.02811/) (2018)
- [Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descent](https://mlsanity.com/paper/1902.06720/) (2019)
- [On Exact Computation with an Infinitely Wide Neural Net](https://mlsanity.com/paper/1904.11955/) (2019)
- [Scalable Global Optimization via Local Bayesian Optimization](https://mlsanity.com/paper/1910.01739/) (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)
- [High Dimensional Bayesian Optimisation and Bandits via Additive Models](https://mlsanity.com/paper/1503.01673/) (2015)
- [Neural Thompson Sampling](https://mlsanity.com/paper/2010.00827/) (2020)
- [Multi-fidelity Bayesian Optimisation with Continuous Approximations](https://mlsanity.com/paper/1703.06240/) (2017)
- [Batched Large-scale Bayesian Optimization in High-dimensional Spaces](https://mlsanity.com/paper/1706.01445/) (2017)
- [What Can ResNet Learn Efficiently, Going Beyond Kernels?](https://mlsanity.com/paper/1905.10337/) (2019)
- [Bayesian Deep Ensembles via the Neural Tangent Kernel](https://mlsanity.com/paper/2007.05864/) (2020)
- [ChemBO: Bayesian Optimization of Small Organic Molecules with Synthesizable Recommendations](https://mlsanity.com/paper/1908.01425/) (2019)
- [Federated Bayesian Optimization via Thompson Sampling](https://mlsanity.com/paper/2010.10154/) (2020)
- [Parallel and Distributed Thompson Sampling for Large-scale Accelerated Exploration of Chemical Space](https://mlsanity.com/paper/1706.01825/) (2017)
- [Neural Contextual Bandits with Deep Representation and Shallow Exploration](https://mlsanity.com/paper/2012.01780/) (2020)
- [Gaussian Process Bandit Optimization with Few Batches](https://mlsanity.com/paper/2110.07788/) (2021)
- [Fault-Tolerant Federated Reinforcement Learning with Theoretical Guarantee](https://mlsanity.com/paper/2110.14074/) (2021)
- [Parallel Gaussian Process Optimization with Upper Confidence Bound and Pure Exploration](https://mlsanity.com/paper/1304.5350/) (2013)
- [Understanding Architectures Learnt by Cell-based Neural Architecture Search](https://mlsanity.com/paper/1909.09569/) (2019)
- [Convolutional Gaussian Processes](https://mlsanity.com/paper/1709.01894/) (2017)
- [Neural Contextual Bandits without Regret](https://mlsanity.com/paper/2107.03144/) (2021)
- [Batched Gaussian Process Bandit Optimization via Determinantal Point Processes](https://mlsanity.com/paper/1611.04088/) (2016)
- [Differentially Private Federated Bayesian Optimization with Distributed Exploration](https://mlsanity.com/paper/2110.14153/) (2021)
- [Mixed-Variable Bayesian Optimization](https://mlsanity.com/paper/1907.01329/) (2019)
- [NASI: Label- and Data-agnostic Neural Architecture Search at Initialization](https://mlsanity.com/paper/2109.00817/) (2021)

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

- [Large Language Models to Enhance Bayesian Optimization](https://mlsanity.com/paper/2402.03921/) (2024)
- [PINNACLE: PINN Adaptive ColLocation and Experimental points selection](https://mlsanity.com/paper/2404.07662/) (2024)
- [Approximate Thompson Sampling via Epistemic Neural Networks](https://mlsanity.com/paper/2302.09205/) (2023)
- [Use Your INSTINCT: INSTruction optimization for LLMs usIng Neural bandits Coupled with Transformers](https://mlsanity.com/paper/2310.02905/) (2023)
- [Quantum Bayesian Optimization](https://mlsanity.com/paper/2310.05373/) (2023)
- [Federated Zeroth-Order Optimization using Trajectory-Informed Surrogate Gradients](https://mlsanity.com/paper/2308.04077/) (2023)
- [Batch Bayesian Optimization for Replicable Experimental Design](https://mlsanity.com/paper/2311.01195/) (2023)
- [Global Optimization with Parametric Function Approximation](https://mlsanity.com/paper/2211.09100/) (2022)
- [Training-Free Neural Active Learning with Initialization-Robustness Guarantees](https://mlsanity.com/paper/2306.04454/) (2023)
- [Bayesian Optimization with Inexact Acquisition: Is Random Grid Search Sufficient?](https://mlsanity.com/paper/2506.11831/) (2025)
- [Robustifying and Boosting Training-Free Neural Architecture Search](https://mlsanity.com/paper/2403.07591/) (2024)
- [Online Clustering of Dueling Bandits](https://mlsanity.com/paper/2502.02079/) (2025)
- [Generative Bayesian Optimization: Generative Models as Acquisition Functions](https://mlsanity.com/paper/2510.25240/) (2025)
- [Multi-Task Combinatorial Bandits for Budget Allocation](https://mlsanity.com/paper/2409.00561/) (2024)
- [Batched Bayesian optimization by maximizing the probability of including the optimum](https://mlsanity.com/paper/2410.06333/) (2024)
- [High-Dimensional Bayesian Optimization via Random Projection of Manifold Subspaces](https://mlsanity.com/paper/2412.16554/) (2024)
- [Quantum Non-Linear Bandit Optimization](https://mlsanity.com/paper/2503.03023/) (2025)
- [Graph Neural Thompson Sampling](https://mlsanity.com/paper/2406.10686/) (2024)
- [Thompson Sampling in Function Spaces via Neural Operators](https://mlsanity.com/paper/2506.21894/) (2025)
- [Kernel-based guarantees for nonlinear parametric models in Bayesian optimization](https://mlsanity.com/paper/2605.13160/) (2026)
- [OptEx: Expediting First-Order Optimization with Approximately Parallelized Iterations](https://mlsanity.com/paper/2402.11427/) (2024)
- [Causal Predictive Optimization and Generation for Business AI](https://mlsanity.com/paper/2505.09847/) (2025)
- [Uncovering Scaling Laws for Large Language Models via Inverse Problems](https://mlsanity.com/paper/2509.07909/) (2025)
- [Discovering strategies for coastal resilience with AI-based prediction and optimization](https://mlsanity.com/paper/2509.19263/) (2025)
- [Linear and Neural Dueling Bandits with Delayed Feedback](https://mlsanity.com/paper/2605.26554/) (2026)

## Abstract (arXiv)

Bayesian optimization (BO), which uses a Gaussian process (GP) as a surrogate to model its objective function, is popular for black-box optimization. However, due to the limitations of GPs, BO underperforms in some problems such as those with categorical, high-dimensional or image inputs. To this end, recent works have used the highly expressive neural networks (NNs) as the surrogate model and derived theoretical guarantees using the theory of neural tangent kernel (NTK). However, these works suffer from the limitations of the requirement to invert an extremely large parameter matrix and the restriction to the sequential (rather than batch) setting. To overcome these limitations, we introduce two algorithms based on the Thompson sampling (TS) policy named Sample-Then-Optimize Batch Neural TS (STO-BNTS) and STO-BNTS-Linear. To choose an input query, we only need to train an NN (resp. a linear model) and then choose the query by maximizing the trained NN (resp. linear model), which is equivalently sampled from the GP posterior with the NTK as the kernel function. As a result, our algorithms sidestep the need to invert the large parameter matrix yet still preserve the validity of the TS policy. Next, we derive regret upper bounds for our algorithms with batch evaluations, and use insights from batch BO and NTK to show that they are asymptotically no-regret under certain conditions. Finally, we verify their empirical effectiveness using practical AutoML and reinforcement learning experiments.