线性集合采样在随机线性博弈中表现接近贝叶斯采样，计算开销却更低。
Sharp analysis of linear ensemble sampling
- 用布朗运动建模多个独立采样路径，将离散过程转为连续时间问题。
- 当集合大小 m=Θ(d log n) 时，高概率后悔上界为 Õ(d^{3/2}√n)。
- 适合关注高效探索策略与理论分析的强化学习研究者。
我们分析了在随机线性博弈中使用标准高斯扰动的线性集合采样（ES）。研究表明，当集合规模 m=Θ(d log n) 时，ES 可实现高概率后悔上界 Õ(d^{3/2}√n)，逼近汤普森采样基准，同时保持相近的计算复杂度。证明的核心在于将随机探索分析转化为 m 个独立布朗运动的时间一致超出问题。这种连续时间视角在此尤为自然：它能精确表示相关离散过程，且我们尚不知晓其他可导出严格 ES 边界的途径。
原文摘要 · Abstract (English)
We analyse linear ensemble sampling (ES) with standard Gaussian perturbations in stochastic linear bandits. We show that for ensemble size $m=Θ(d\log n)$, ES attains $\tilde O(d^{3/2}\sqrt n)$ high-probability regret, closing the gap to the Thompson sampling benchmark while keeping computation comparable. The proof brings a new perspective on randomized exploration in linear bandits by reducing the analysis to a time-uniform exceedance problem for $m$ independent Brownian motions. This continuous-time lens appears particularly natural here: it yields an exact representation of the relevant discrete-time processes, and we do not know another route to a sharp ES bound.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。