Ensemble Sampling

新分析表明线性集成采样可媲美汤普森采样

研究人员发表了对随机线性 bandits 中线性集成采样 (ES) 的新分析，证明了其在标准高斯扰动下的有效性。研究表明，ES 可以实现 \tilde O(d^{3/2}\sqrt n) 的遗憾值，集成大小为 m=\Theta(d\log n)，其性能可媲美汤普森采样，同时计算成本相当。新颖的证明技术涉及将分析简化为独立布朗运动的时间均匀超额问题，为线性 bandits 中的随机探索提供了新视角。