mlsanityData to 7 Oct 2026

Sample-Then-Optimize Batch Neural Thompson Sampling

arXiv 2210.06850 ↗First posted 13 Oct 2022cs.LG cs.AIcited by 25

Not on the map. Why?

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.

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

Builds on

49 of 75 references.

References · 49

  1. 2016XGBoost: A Scalable Tree Boosting Systemcited by 5,120
  2. 2016Simple and Scalable Predictive Uncertainty Estimation using Deep Ensemblescited by 3,888
  3. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  4. 2016OpenAI Gymcited by 1,684
  5. 2018A Tutorial on Bayesian Optimizationcited by 734
  6. 2019Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descentcited by 732
  7. 2019On Exact Computation with an Infinitely Wide Neural Netcited by 572
  8. 2019Scalable Global Optimization via Local Bayesian Optimizationcited by 359
  9. 2017On Kernelized Multi-armed Banditscited by 348
  10. 2019Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networkscited by 221
  11. 2015High Dimensional Bayesian Optimisation and Bandits via Additive Modelscited by 137
  12. 2020Neural Thompson Samplingcited by 127
37 more
  1. 2017Multi-fidelity Bayesian Optimisation with Continuous Approximationscited by 120
  2. 2017Batched Large-scale Bayesian Optimization in High-dimensional Spacescited by 116
  3. 2019What Can ResNet Learn Efficiently, Going Beyond Kernels?cited by 91
  4. 2020Bayesian Deep Ensembles via the Neural Tangent Kernelcited by 90
  5. 2019ChemBO: Bayesian Optimization of Small Organic Molecules with Synthesizable Recommendationscited by 77
  6. 2020Federated Bayesian Optimization via Thompson Samplingcited by 77
  7. 2017Parallel and Distributed Thompson Sampling for Large-scale Accelerated Exploration of Chemical Spacecited by 76
  8. 2020Neural Contextual Bandits with Deep Representation and Shallow Explorationcited by 71
  9. 2021Gaussian Process Bandit Optimization with Few Batchescited by 57
  10. 2021Fault-Tolerant Federated Reinforcement Learning with Theoretical Guaranteecited by 52
  11. 2013Parallel Gaussian Process Optimization with Upper Confidence Bound and Pure Explorationcited by 50
  12. 2019Understanding Architectures Learnt by Cell-based Neural Architecture Searchcited by 48
  13. 2017Convolutional Gaussian Processescited by 44
  14. 2021Neural Contextual Bandits without Regretcited by 40
  15. 2016Batched Gaussian Process Bandit Optimization via Determinantal Point Processescited by 33
  16. 2021Differentially Private Federated Bayesian Optimization with Distributed Explorationcited by 32
  17. 2019Mixed-Variable Bayesian Optimizationcited by 29
  18. 2021NASI: Label- and Data-agnostic Neural Architecture Search at Initializationcited by 28
  19. 2017Decentralized High-Dimensional Bayesian Optimization with Factor Graphscited by 23
  20. 2021Bayesian Optimization over Hybrid Spacescited by 23
  21. 2021Diversified Sampling for Batched Bayesian Optimization with Determinantal Point Processescited by 23
  22. 2021Batched Neural Banditscited by 22
  23. 2021Neural Active Learning with Performance Guaranteescited by 22
  24. 2020Top-k Ranking Bayesian Optimizationcited by 21
  25. 2021Value-at-Risk Optimization with Gaussian Processescited by 19
  26. 2022Unifying and Boosting Gradient-Based Training-Free Neural Architecture Searchcited by 17
  27. 2020Efficient Exploration of Reward Functions in Inverse Reinforcement Learning via Bayesian Optimizationcited by 16
  28. 2015Gaussian Process Planning with Lipschitz Continuous Reward Functions: Towards Unifying Bayesian Optimization, Active Learning, and Beyondcited by 15
  29. 2019Bayesian Optimization with Binary Auxiliary Informationcited by 15
  30. 2020Private Outsourced Bayesian Optimizationcited by 15
  31. 2021Online Limited Memory Neural-Linear Bandits with Likelihood Matchingcited by 14
  32. 2020R2-B2: Recursive Reasoning-Based Bayesian Optimization for No-Regret Learning in Gamescited by 11
  33. 2022Bayesian Optimization under Stochastic Delayed Feedbackcited by 10
  34. 2020Nonmyopic Gaussian Process Optimization with Macro-Actionscited by 8
  35. 2021Trusted-Maximizers Entropy Search for Efficient Bayesian Optimizationcited by 8
  36. 2022On Provably Robust Meta-Bayesian Optimizationcited by 8
  37. 2021Neural Ensemble Search via Bayesian Samplingcited by 7

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 1; 2023: 6; 2024: 8; 2025: 8; 2026: 2.

25 papers.

Sort:

By area:

  1. 2024Large Language Models to Enhance Bayesian Optimizationcited by 127
  2. 2023Approximate Thompson Sampling via Epistemic Neural Networkscited by 31
  3. 2024PINNACLE: PINN Adaptive ColLocation and Experimental points selectioncited by 31
  4. 2023Use Your INSTINCT: INSTruction optimization for LLMs usIng Neural bandits Coupled with Transformerscited by 29
  5. 2023Quantum Bayesian Optimizationcited by 12
  6. 2023Federated Zeroth-Order Optimization using Trajectory-Informed Surrogate Gradientscited by 8
  7. 2022Global Optimization with Parametric Function Approximationcited by 7
  8. 2023Batch Bayesian Optimization for Replicable Experimental Designcited by 7
  9. 2023Training-Free Neural Active Learning with Initialization-Robustness Guaranteescited by 5
  10. 2024Robustifying and Boosting Training-Free Neural Architecture Searchcited by 4
  11. 2025Bayesian Optimization with Inexact Acquisition: Is Random Grid Search Sufficient?cited by 4
  12. 2024Multi-Task Combinatorial Bandits for Budget Allocationcited by 2
13 more
  1. 2024Batched Bayesian optimization by maximizing the probability of including the optimumcited by 2
  2. 2024High-Dimensional Bayesian Optimization via Random Projection of Manifold Subspacescited by 2
  3. 2025Online Clustering of Dueling Banditscited by 2
  4. 2025Quantum Non-Linear Bandit Optimizationcited by 2
  5. 2025Generative Bayesian Optimization: Generative Models as Acquisition Functionscited by 2
  6. 2024Graph Neural Thompson Samplingcited by 1
  7. 2025Thompson Sampling in Function Spaces via Neural Operatorscited by 1
  8. 2026Kernel-based guarantees for nonlinear parametric models in Bayesian optimizationcited by 1
  9. 2024OptEx: Expediting First-Order Optimization with Approximately Parallelized Iterationscited by 0
  10. 2025Causal Predictive Optimization and Generation for Business AIcited by 0
  11. 2025Uncovering Scaling Laws for Large Language Models via Inverse Problemscited by 0
  12. 2025Discovering strategies for coastal resilience with AI-based prediction and optimizationcited by 0
  13. 2026Linear and Neural Dueling Bandits with Delayed Feedbackcited by 0