Balancing Expressivity and Learnability in Quantum Kernel Bandit Optimization

Yuqi Huang, Vincent Y. F. Tan, Sharu Theresa Jose
Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, PMLR 337:2274-2313, 2026.

Abstract

We investigate {Gaussian} Process (GP) bandit optimization utilizing quantum kernels. While quantum kernels enable embedding data into high-dimensional {Hilbert} spaces—potentially offering enhanced expressivity or a "quantum advantage"—this property can pose challenges in bandit learning. Specifically, employing full quantum kernels naïvely may lead to increased model complexity and, consequently, higher cumulative regret impacting the learnability. To address this, we explore the use of projected quantum kernels and classical kernel approximation techniques, which effectively reduce feature dimensionality while preserving essential quantum properties. We demonstrate that these approaches can yield improved regret bounds by strategically balancing approximation error and information gain. Empirical results show that they significantly outperform models based on full quantum kernels in bandit optimization tasks. Additionally, we analyze how to select the optimal model complexity to achieve a favorable trade-off between expressivity and learnability. Our methods also substantially reduce computational costs by simplifying kernel-based inference to linear models, since only a finite set of reduced features is required.

Cite this Paper

BibTeX
@InProceedings{pmlr-v337-huang26c, title = {Balancing Expressivity and Learnability in Quantum Kernel Bandit Optimization}, author = {Huang, Yuqi and Tan, Vincent Y. F. and Jose, Sharu Theresa}, booktitle = {Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence}, pages = {2274--2313}, year = {2026}, editor = {Perković, Emilija and Malinsky, Daniel}, volume = {337}, series = {Proceedings of Machine Learning Research}, month = {17--21 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v337/main/assets/huang26c/huang26c.pdf}, url = {https://proceedings.mlr.press/v337/huang26c.html}, abstract = {We investigate {Gaussian} Process (GP) bandit optimization utilizing quantum kernels. While quantum kernels enable embedding data into high-dimensional {Hilbert} spaces—potentially offering enhanced expressivity or a "quantum advantage"—this property can pose challenges in bandit learning. Specifically, employing full quantum kernels naïvely may lead to increased model complexity and, consequently, higher cumulative regret impacting the learnability. To address this, we explore the use of projected quantum kernels and classical kernel approximation techniques, which effectively reduce feature dimensionality while preserving essential quantum properties. We demonstrate that these approaches can yield improved regret bounds by strategically balancing approximation error and information gain. Empirical results show that they significantly outperform models based on full quantum kernels in bandit optimization tasks. Additionally, we analyze how to select the optimal model complexity to achieve a favorable trade-off between expressivity and learnability. Our methods also substantially reduce computational costs by simplifying kernel-based inference to linear models, since only a finite set of reduced features is required.} }
Endnote
%0 Conference Paper %T Balancing Expressivity and Learnability in Quantum Kernel Bandit Optimization %A Yuqi Huang %A Vincent Y. F. Tan %A Sharu Theresa Jose %B Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2026 %E Emilija Perković %E Daniel Malinsky %F pmlr-v337-huang26c %I PMLR %P 2274--2313 %U https://proceedings.mlr.press/v337/huang26c.html %V 337 %X We investigate {Gaussian} Process (GP) bandit optimization utilizing quantum kernels. While quantum kernels enable embedding data into high-dimensional {Hilbert} spaces—potentially offering enhanced expressivity or a "quantum advantage"—this property can pose challenges in bandit learning. Specifically, employing full quantum kernels naïvely may lead to increased model complexity and, consequently, higher cumulative regret impacting the learnability. To address this, we explore the use of projected quantum kernels and classical kernel approximation techniques, which effectively reduce feature dimensionality while preserving essential quantum properties. We demonstrate that these approaches can yield improved regret bounds by strategically balancing approximation error and information gain. Empirical results show that they significantly outperform models based on full quantum kernels in bandit optimization tasks. Additionally, we analyze how to select the optimal model complexity to achieve a favorable trade-off between expressivity and learnability. Our methods also substantially reduce computational costs by simplifying kernel-based inference to linear models, since only a finite set of reduced features is required.
APA
Huang, Y., Tan, V.Y.F. & Jose, S.T.. (2026). Balancing Expressivity and Learnability in Quantum Kernel Bandit Optimization. Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 337:2274-2313 Available from https://proceedings.mlr.press/v337/huang26c.html.

Related Material