改进线性集成采样理论，实现最优后悔界。
Improved Regret of Linear Ensemble Sampling
- 提出通用分析框架，实现对线性带域算法的统一建模。
- 仅需对数规模集成大小即可达$ ilde{O}(d^{3/2} oot{2}{T})$后悔界。
- 揭示林普赫与集成采样的关系，适用于任意臂数场景。
本文通过提供线性集成采样的改进后悔界，弥合了理论与实践之间的根本差距。我们证明：当集成规模为$T$的对数级时，线性集成采样可实现频率论后悔界$ ilde{O}(d^{3/2} oot{2}{T})$，与最先进的随机线性带域算法结果一致，其中$d$为参数维度，$T$为时间范围。本方法引入一个通用的线性带域算法后悔分析框架。此外，我们揭示了线性集成采样与线性扰动历史探索（LinPHE）之间的显著关系——当集成大小等于$T$时，LinPHE是线性集成采样的特例。这一洞察使我们的分析框架能够独立于臂的数量，推导出针对LinPHE的$ ilde{O}(d^{3/2} oot{2}{T})$后悔界。技术进展强化了集成采样的理论基础，使其后悔界与其它随机探索算法的最佳已知界限齐平。
原文摘要 · Abstract (English)
In this work, we close the fundamental gap of theory and practice by providing an improved regret bound for linear ensemble sampling. We prove that with an ensemble size logarithmic in $T$, linear ensemble sampling can achieve a frequentist regret bound of $\tilde{O}(d^{3/2}\sqrt{T})$, matching state-of-the-art results for randomized linear bandit algorithms, where $d$ and $T$ are the dimension of the parameter and the time horizon respectively. Our approach introduces a general regret analysis framework for linear bandit algorithms. Additionally, we reveal a significant relationship between linear ensemble sampling and Linear Perturbed-History Exploration (LinPHE), showing that LinPHE is a special case of linear ensemble sampling when the ensemble size equals $T$. This insight allows our analysis framework to derive a regret bound of $\tilde{O}(d^{3/2}\sqrt{T})$ for LinPHE, independent of the number of arms. Our techniques advance the theoretical foundation of ensemble sampling, bringing its regret bounds in line with the best known bounds for other randomized exploration algorithms.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。