分析无限动作空间下汤普森采样的贝叶斯后悔，给出可衡量复杂度的上界。
An Information-Theoretic Analysis of Thompson Sampling with Infinite Action Spaces
- 基于信息论框架，将汤普森采样分析扩展至连续动作空间。
- 在奖励函数为利普希茨连续时，得到依赖动作空间复杂度的后悔上界。
- 适用于高维或连续决策场景，适合对理论性能有要求的研究者。
本文研究了贝叶斯框架下汤普森采样算法在广义置信区间问题中的贝叶斯后悔，沿用Russo和Van Roy（2015）提出的信息论框架。具体而言，它拓展了Dong和Van Roy（2018）针对线性带域问题的率失真分析，该分析已提供近最优的后悔界。然而这些结果受限于有限动作空间的假设。本文突破此限制，将分析推广至具有无限甚至连续动作空间的设定。此外，针对期望奖励关于动作空间满足利普希茨连续性的带域问题，导出了显式考虑动作空间复杂度的后悔上界。
原文摘要 · Abstract (English)
This paper studies the Bayesian regret of the Thompson Sampling algorithm for bandit problems, building on the information-theoretic framework introduced by Russo and Van Roy (2015). Specifically, it extends the rate-distortion analysis of Dong and Van Roy (2018), which provides near-optimal bounds for linear bandits. A limitation of these results is the assumption of a finite action space. We address this by extending the analysis to settings with infinite and continuous action spaces. Additionally, we specialize our results to bandit problems with expected rewards that are Lipschitz continuous with respect to the action space, deriving a regret bound that explicitly accounts for the complexity of the action space.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。