量子算法解决连续动作空间的非线性奖励问题，显著降低累积后悔值。
Quantum Lipschitz Bandits
- 基于量子消除与量子缩放框架，设计新算法提升搜索效率。
- 理论后悔界达$ ilde O(T^{d_z/(d_z+1)})$，优于经典方法的$ ilde O(T^{(d_z+1)/(d_z+2)})$。
- 适合对量子优化和自适应决策感兴趣的科研人员。
Lipschitz 调色盘是随机调色盘问题的重要变种，其期望奖励函数在动作度量空间上满足Lipschitz条件。尽管已有多种算法实现累计后悔下界$ ilde O(T^{(d_z+1)/(d_z+2)})$，但面对连续动作空间和非线性奖励函数仍具挑战。受量子计算进展及量子蒙特卡洛在简单调色盘中的成功启发，本文首次提出量子Lipschitz调色盘算法。首先，基于消除框架设计高效量子算法Q-LAE；其次，对经典缩放算法进行创新改进，得到简洁的量子方法Q-Zooming。两者均利用量子计算优势，将后悔界提升至$ ilde O(T^{d_z/(d_z+1)})$。大量实验验证了理论结果，显示其在性能上显著优于现有方法。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。