Quantum Non-Linear Bandit Optimization

• URL: http://arxiv.org/abs/2503.03023v1
• Date: Tue, 04 Mar 2025 21:53:33 GMT
• Title: Quantum Non-Linear Bandit Optimization
• Authors: Zakaria Shams Siam, Chaowen Guan, Chong Liu,
• Abstract summary: We study non-linear bandit optimization where the learner maximizes a black-box function with zeroth order function oracle.<n>We propose the new Q-NLB-UCB algorithm which uses the novel parametric function approximation technique.<n>We prove that the regret bound of Q-NLB-UCB is not only $O(mathrmpolylog T)$ but also input dimension-free.
• Score: 2.7718037613443127
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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 hyperparameter tuning. Existing works have showed that with the aid of quantum computing, it is possible to break the $\Omega(\sqrt{T})$ regret lower bound in classical settings and achieve the new $O(\mathrm{poly}\log 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 uses the novel parametric function approximation technique and enjoys performance improvement due to quantum fast-forward and quantum Monte Carlo mean estimation. We prove that the regret bound of Q-NLB-UCB is not only $O(\mathrm{poly}\log T)$ but also input dimension-free, making it applicable for high-dimensional tasks. At the heart of our analyses are a new quantum regression oracle and a careful construction of parameter uncertainty region. Our algorithm is also validated for its efficiency on both synthetic and real-world tasks.

Related papers

• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• Quantum Bayesian Optimization [64.58749619145908]
  We introduce the quantum-Gaussian process-upper confidence bound (Q-GP-UCB) algorithm. It is the first BO algorithm able to achieve a regret upper bound of O(polylog T), which is significantly smaller than its regret lower bound of Omega(sqrt(T)) in the classical setting. Thanks to our novel analysis of the confidence ellipsoid, our Q-GP-UCB with the linear kernel achieves a smaller regret than the quantum linear UCB algorithm.
  arXiv  Detail & Related papers  (2023-10-09T03:10:42Z)
• Quantum Computing Provides Exponential Regret Improvement in Episodic Reinforcement Learning [35.11103784048256]
  We propose an textitUpper Confidence Bound (UCB) based quantum algorithmic framework to facilitate learning of a finite-horizon MDP. Our quantum algorithm achieves an exponential improvement in regret as compared to the classical counterparts.
  arXiv  Detail & Related papers  (2023-02-16T23:01:27Z)
• Global Optimization with Parametric Function Approximation [19.699902334787325]
  We consider the problem of global optimization with noisy zeroth order oracles. We propose a new algorithm GO-UCB that leverages a parametric family of functions instead. We show that GO-UCB achieves a cumulative regret of O$(sqrtT)$ where $T$ is the time horizon.
  arXiv  Detail & Related papers  (2022-11-16T18:35:42Z)
• Sample-Then-Optimize Batch Neural Thompson Sampling [50.800944138278474]
  We introduce two algorithms for black-box optimization based on the Thompson sampling (TS) policy. To choose an input query, we only need to train an NN and then choose the query by maximizing the trained NN. Our algorithms sidestep the need to invert the large parameter matrix yet still preserve the validity of the TS policy.
  arXiv  Detail & Related papers  (2022-10-13T09:01:58Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
  arXiv  Detail & Related papers  (2022-06-30T03:15:23Z)
• Avoiding Barren Plateaus with Classical Deep Neural Networks [0.0]
  Vari quantum algorithms (VQAs) are among the most promising algorithms in the era of Noisy Intermediate Scale Quantum Devices. VQAs are applied to a variety of tasks, such as in chemistry simulations, optimization problems, and quantum neural networks. We report on how the use of a classical neural networks in the VQAs input parameters can alleviate the Barren Plateaus phenomenon.
  arXiv  Detail & Related papers  (2022-05-26T15:14:01Z)
• Misspecified Gaussian Process Bandit Optimization [59.30399661155574]
  Kernelized bandit algorithms have shown strong empirical and theoretical performance for this problem. We introduce a emphmisspecified kernelized bandit setting where the unknown function can be $epsilon$--uniformly approximated by a function with a bounded norm in some Reproducing Kernel Hilbert Space (RKHS) We show that our algorithm achieves optimal dependence on $epsilon$ with no prior knowledge of misspecification.
  arXiv  Detail & Related papers  (2021-11-09T09:00:02Z)
• Bayesian Optimistic Optimisation with Exponentially Decaying Regret [58.02542541410322]
  The current practical BO algorithms have regret bounds ranging from $mathcalO(fraclogNsqrtN)$ to $mathcal O(e-sqrtN)$, where $N$ is the number of evaluations. This paper explores the possibility of improving the regret bound in the noiseless setting by intertwining concepts from BO and tree-based optimistic optimisation. We propose the BOO algorithm, a first practical approach which can achieve an exponential regret bound with order $mathcal O(N-sqrt
  arXiv  Detail & Related papers  (2021-05-10T13:07:44Z)
• Quantum Algorithm for Online Convex Optimization [4.702729080310267]
  We explore whether quantum advantages can be found for the zeroth-order online convex optimization problem. In this paper, we present quantum algorithms for the problem and show for the first time that potential quantum advantages are possible.
  arXiv  Detail & Related papers  (2020-07-29T18:34:05Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.