证明随机探索在光滑凸动作空间中可实现最优维度依赖的后悔界。
When and why randomised exploration works (in linear bandits)
- 不依赖乐观或后验膨胀，分析泰普森采样等随机探索算法。
- 在d维线性贝尔特问题中，n步后悔界为O(d√n log n)。
- 首次展示泰普森采样在非平凡线性带宽设置下可达到最优维度依赖。
我们提出一种分析随机探索算法（如泰普森采样）的新方法，无需依赖强制乐观或后验膨胀。在此基础上，我们证明在d维线性带宽设置中，当动作空间光滑且强凸时，随机探索算法的n步后悔界为O(d√n log n)。值得注意的是，这首次表明存在非平凡的线性带宽场景，使得泰普森采样能够实现后悔项中最优的维度依赖关系。
原文摘要 · Abstract (English)
We provide an approach for the analysis of randomised exploration algorithms like Thompson sampling that does not rely on forced optimism or posterior inflation. With this, we demonstrate that in the $d$-dimensional linear bandit setting, when the action space is smooth and strongly convex, randomised exploration algorithms enjoy an $n$-step regret bound of the order $O(d\sqrt{n} \log(n))$. Notably, this shows for the first time that there exist non-trivial linear bandit settings where Thompson sampling can achieve optimal dimension dependence in the regret.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。