Quantum Lipschitz Bandits
This work addresses the challenge of efficient decision-making in complex bandit settings for researchers and practitioners in machine learning and quantum computing, representing a novel application rather than an incremental improvement.
The paper tackles the Lipschitz bandit problem in continuous action spaces with non-linear reward functions by introducing the first quantum algorithms, Q-LAE and Q-Zooming, which achieve an improved regret bound of ˜O(T^{d_z/(d_z+1)}) and demonstrate superior empirical performance over existing methods.
The Lipschitz bandit is a key variant of stochastic bandit problems where the expected reward function satisfies a Lipschitz condition with respect to an arm metric space. With its wide-ranging practical applications, various Lipschitz bandit algorithms have been developed, achieving the cumulative regret lower bound of order $\tilde O(T^{(d_z+1)/(d_z+2)})$ over time horizon $T$. Motivated by recent advancements in quantum computing and the demonstrated success of quantum Monte Carlo in simpler bandit settings, we introduce the first quantum Lipschitz bandit algorithms to address the challenges of continuous action spaces and non-linear reward functions. Specifically, we first leverage the elimination-based framework to propose an efficient quantum Lipschitz bandit algorithm named Q-LAE. Next, we present novel modifications to the classical Zooming algorithm, which results in a simple quantum Lipschitz bandit method, Q-Zooming. Both algorithms exploit the computational power of quantum methods to achieve an improved regret bound of $\tilde O(T^{d_z/(d_z+1)})$. Comprehensive experiments further validate our improved theoretical findings, demonstrating superior empirical performance compared to existing Lipschitz bandit methods.