Quantum Non-Linear Bandit Optimization
Not on the map. Why?
Abstract (arXiv)
We study non-linear bandit optimization where the learner maximizes a black-box function with zeroth order function oracle, which has been successfully applied in many critical applications such as drug discovery and materials design. Existing works have showed that with the aid of quantum computing, it is possible to break the classical Omega(√T) regret lower bound and achieve the new O(polylog T) upper bound. However, they usually assume that the objective function sits within the reproducing kernel Hilbert space and their algorithms suffer from the curse of dimensionality. In this paper, we propose the new Q-NLB-UCB algorithm which enjoys an input dimension-free O(polylog T) upper bound, making it applicable for high-dimensional tasks. At the heart of our algorithm design are quantum Monte Carlo mean estimator, parametric function approximation technique, and a new quantum non-linear regression oracle, which can be of independent interests in more quantum machine learning problems. Our algorithm is also validated for its efficiency compared with other quantum algorithms on both high-dimensional synthetic and real-world tasks.
Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 49 of its 79 references that are in the map. First posted on arXiv 4 Mar 2025.
Builds on
49 of 79 references.
References · 49
- 2018A Tutorial on Bayesian Optimizationcited by 734
- 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
- 2017A Tutorial on Thompson Samplingcited by 420
- 2017On Kernelized Multi-armed Banditscited by 348
- 2015Scalable Bayesian Optimization Using Deep Neural Networkscited by 284
- 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 283
- 2020Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oraclescited by 195
- 2018Neural Architecture Search with Bayesian Optimisation and Optimal Transportcited by 192
- 2019BANANAS: Bayesian Optimization with Neural Architectures for Neural Architecture Searchcited by 175
- 2016Katyusha: The First Direct Acceleration of Stochastic Gradient Methodscited by 134
- 2020Neural Thompson Samplingcited by 127
- 2022Offline Reinforcement Learning with Realizability and Single-policy Concentrabilitycited by 122
37 more
- 2020Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizabilitycited by 114
- 2019Practical Multi-fidelity Bayesian Optimization for Hyperparameter Tuningcited by 91
- 2015Bayesian optimization for materials designcited by 78
- 2017Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimizationcited by 77
- 2019ChemBO: Bayesian Optimization of Small Organic Molecules with Synthesizable Recommendationscited by 77
- 2019Bayesian Optimization for Materials Design with Mixed Quantitative and Qualitative Variablescited by 64
- 2017Sub-sampled Cubic Regularization for Non-convex Optimizationcited by 63
- 2021Misspecified Gaussian Process Bandit Optimizationcited by 52
- 2019Learning search spaces for Bayesian optimization: Another view of hyperparameter transfer learningcited by 50
- 2023Convex and Non-convex Optimization Under Generalized Smoothnesscited by 44
- 2021Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvaturecited by 32
- 2017Quantum SDP-Solvers: Better upper and lower boundscited by 27
- 2022Sample-Then-Optimize Batch Neural Thompson Samplingcited by 25
- 2018Convex optimization using quantum oraclescited by 19
- 2022Quantum Multi-Armed Bandits and Stochastic Linear Bandits Enjoy Logarithmic Regretscited by 19
- 2018A Quantum Interior Point Method for LPs and SDPscited by 17
- 2022When is Realizability Sufficient for Off-Policy Reinforcement Learning?cited by 17
- 2018Quantum algorithms and lower bounds for convex optimizationcited by 15
- 2018Optimization of Smooth Functions with Noisy Observations: Local Minimax Ratescited by 14
- 2023Quantum speedups for stochastic optimizationcited by 12
- 2023Quantum Bayesian Optimizationcited by 12
- 2022Quantum Speedups of Optimizing Approximately Convex Functions with Applications to Logarithmic Regret Stochastic Convex Banditscited by 11
- 2020Quantum algorithms for escaping from saddle pointscited by 10
- 2022On Quantum Speedups for Nonconvex Optimization via Quantum Tunneling Walkscited by 9
- 2022Quantum simulation of real-space dynamicscited by 8
- 2022Global Optimization with Parametric Function Approximationcited by 7
- 2023Quantum Heavy-tailed Banditscited by 7
- 2023Quantum Hamiltonian Descentcited by 7
- 2023Quantum Langevin Dynamics for Optimizationcited by 7
- 2020No quantum speedup over gradient descent for non-smooth convex optimizationcited by 6
- 2021Near-Optimal Lower Bounds For Convex Optimization For All Orders of Smoothnesscited by 6
- 2022Quantum Lower Bounds for Finding Stationary Points of Nonconvex Functionscited by 4
- 2024Quantum Algorithms and Lower Bounds for Finite-Sum Optimizationcited by 3
- 2022Robustness of Quantum Algorithms for Nonconvex Optimizationcited by 2
- 2023No-Regret Linear Bandits beyond Realizabilitycited by 2
- 2024Quantum Algorithms for Non-smooth Non-convex Optimizationcited by 2
- 2019Quadratic speedup for finding marked vertices by quantum walkscited by 1
Built on by
Citing papers per year: 2026: 2.
2 papers.