汤普森采样输给贪婪选择！高维赌博机遗憾比率竟逼近2倍
Exact Bayes Regret and Asymptotic Optimality in High-Dimensional Gaussian Bandits
📖 AI 总结
本文研究高维贝叶斯线性赌博机问题，设定参数服从各向同性高斯分布、候选臂与奖励噪声均为高斯分布，且时间跨度与维度成正比。作者发现归一化后验不确定性存在一个对所有因果策略一致成立的显式极限，并借助高斯后验恒等式确定极限参数重叠，无需假设自适应递推的封闭性。由此得到Thompson采样、后验均值贪心选择及一类缩放后验采样协方差策略的精确遗憾曲线，证明归一化累积遗憾在紧致比例时间区间上依L1范数一致收敛。策略一致下界给出了极限最优贝叶斯遗憾，并证明后验均值贪心选择可达到该下界，而Thompson采样则产生严格更大的主导遗憾，其瞬时遗憾比介于一到二之间并在长比例时间跨度下趋近于二。研究还表明瞬时遗憾收敛于非退化高斯决策损失分布而非其均值，并将策略获取信息量与决策质量加以区分。
🔑 关键词速览
| 贝叶斯线性赌博机 | 一种在线决策模型，其中奖励与特征向量线性相关，参数具有先验分布，智能体通过贝叶斯推断更新后验。 |
| 汤普森采样 | 一种概率匹配策略，通过从后验分布中采样参数并选择最优臂，以平衡探索与利用。 |
| 后验均值贪婪选择 | 一种策略，直接选择基于当前后验均值估计的最优臂，不进行额外探索。 |
| 贝叶斯遗憾 | 衡量策略性能的指标，定义为最优策略与所采用策略之间累积奖励期望的差值。 |
| 比例时间范围 | 指时间范围T与维度d成比例增长的情形，即T = c*d，用于研究高维渐近性质。 |
📱 每天一份 AI 前沿日报
关注公众号，每天 09:00 推送 · 不错过任何重磅