提出首个多项式后悔的组合强化学习算法，揭示先验知识反而可能有害。
Thompson Sampling For Combinatorial Bandits: Polynomial Regret and Mismatched Sampling Paradox
- 设计新型泰勒采样算法，避免维度指数级增长的后悔。
- 理论证明：已知分布却正确采样的性能反而比盲目采样更差。
- 适合研究贝叶斯优化与在线学习中不确定性建模的学者。
我们研究线性组合半强化学习问题下的泰勒采样（Thompson Sampling, TS）与次高斯奖励。首次提出一种有限时间后悔不随问题维度指数增长的TS算法。进一步揭示了“采样错配悖论”：已知奖励分布并从正确后验采样的学习者，其表现可能远劣于不了解分布而使用精心选择的高斯后验进行采样的学习者。实验代码已开源：https://github.com/RaymZhang/CTS-Mismatched-Paradox。
原文摘要 · Abstract (English)
We consider Thompson Sampling (TS) for linear combinatorial semi-bandits and subgaussian rewards. We propose the first known TS whose finite-time regret does not scale exponentially with the dimension of the problem. We further show the "mismatched sampling paradox": A learner who knows the rewards distributions and samples from the correct posterior distribution can perform exponentially worse than a learner who does not know the rewards and simply samples from a well-chosen Gaussian posterior. The code used to generate the experiments is available at https://github.com/RaymZhang/CTS-Mismatched-Paradox
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。