首个解决连续动作空间中带利普希茨结构的对决强化学习算法
Lipschitz Dueling Bandits over Continuous Action Spaces
- 基于分轮探索与递归区域剔除，用自适应参考臂指导搜索
- 理论证明后悔上界为 $\tilde O(T^{(d_z+1)/(d_z+2)})$，优于传统方法
- 仅需对数空间复杂度，适合大规模连续决策场景
首次研究具有利普希茨结构的连续动作空间随机对决强化学习问题，反馈仅为比较结果。尽管对决强化学习和利普希茨强化学习各自已有研究，但两者的结合尚未被探索。本文提出首个针对此类问题的算法，采用分轮探索与递归区域剔除策略，并引入自适应参考臂。通过构建新的相对反馈分析工具，证明了后悔上界为 $\tilde O(T^{(d_z+1)/(d_z+2)})$，其中 $d_z$ 为近最优区域的缩放维数。此外，该算法在总时间跨度上的空间复杂度仅为对数级，是连续动作空间强化学习算法能达到的最佳水平。
原文摘要 · Abstract (English)
We study for the first time, stochastic dueling bandits over continuous action spaces with Lipschitz structure, where feedback is purely comparative. While dueling bandits and Lipschitz bandits have been studied separately, their combination has remained unexplored. We propose the first algorithm for Lipschitz dueling bandits, using round-based exploration and recursive region elimination guided by an adaptive reference arm. We develop new analytical tools for relative feedback and prove a regret bound of $\tilde O\left(T^{\frac{d_z+1}{d_z+2}}\right)$, where $d_z$ is the zooming dimension of the near-optimal region. Further, our algorithm takes only logarithmic space in terms of the total time horizon, best achievable by any bandit algorithm over a continuous action space.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。