用绝对值扰动改进贝叶斯探索，让线性老虎机算法既快又好。
Randomized Exploration for Linear Bandits via Absolute Perturbations
- 用绝对值替代符号扰动，保持计算高效同时保证期望乐观
- 理论证明其后悔率达 $\tilde{O}(d^{3/2}\sqrt{K})$，与最优一致
- 多扰动集成版本可逼近确定性乐观算法，适合追求稳定性能者
在随机线性老虎机问题中，经典的上置信界（UCB）算法虽易于分析但计算成本高，而贝叶斯采样（TS）虽计算高效却因非乐观性质难分析。本文提出绝对贝叶斯采样（ATS），通过将带符号的探索噪声替换为绝对值，确保期望层面的乐观性。该方法保留了TS的计算效率，避免了传统TS分析中复杂的反集中论证，实现类似UCB的简洁后悔分析。我们证明ATS达到 $\tilde{O}(d^{3/2}\sqrt{K})$ 的后悔率，与现有线性老虎机下界一致。进一步提出集成绝对贝叶斯采样（EATS），对多个绝对扰动取最大值并按集成规模归一化。随着集成规模增大，EATS渐进趋近于UCB目标，极限下恢复UCB行为。实验表明，适度集成规模即能取得优异性能。结果揭示了随机探索与确定性乐观之间理论与实践的桥梁。
原文摘要 · Abstract (English)
In stochastic linear bandits, the canonical Upper Confidence Bound (UCB) algorithm admits a simple frequentist regret analysis but can be computationally demanding, while Thompson Sampling (TS) is computationally attractive yet typically harder to analyze due to its non-optimistic nature. We propose Absolute Thompson Sampling (ATS), a simple modification of TS that ensures optimism in expectation by replacing the signed exploration noise with its absolute value. This preserves the computational efficiency of TS while avoiding the technically involved anti-concentration arguments common in TS analyses, enabling a simple UCB-style regret analysis. We show that ATS achieves $\tilde{O}(d^{3/2}\sqrt{K})$ regret, matching existing bounds for TS in linear bandits. We further introduce Ensemble Absolute Thompson Sampling (EATS), which takes the maximum over multiple absolute perturbations with normalization by the ensemble size. As the ensemble size grows, EATS converges to the UCB objective, recovering UCB behavior in the limit. Experiments show that moderate ensemble sizes already yield strong performance. Our results point to a bridge between randomized exploration and deterministic optimism both in theory and practice.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。