GP-UCB遗憾界首次逼近最优！数据稀疏化让置信区间更紧，效果碾压非自适应方法
Near-Optimal Regret Bounds for UCB-Style Gaussian Process Bandits via Data Thinning
📖 AI 总结
该论文研究高斯过程赌博机中GP-UCB算法的遗憾界问题。已有研究表明GP-UCB的遗憾上界并非最优，而现有改进方法多依赖不确定性采样等非自适应策略，实际效果有限。作者提出在高斯噪声假设下，借助数据稀疏化（data thinning）这一能从单一数据集生成相互独立数据集的统计技术，使UCB类算法达到近最优遗憾界。具体而言，论文首先证明数据稀疏化可在赌博机场景中给出更紧的置信区间，直接扩展的GP-UCB由此获得近最优的简单遗憾上界；进一步结合更紧置信区间与分阶段消除算法，得到近最优的累积遗憾上界。数值实验验证了引入数据稀疏化的UCB类算法的有效性。该工作为自适应UCB类方法实现近最优遗憾界提供了新途径。
🔑 关键词速览
| GP-UCB | 高斯过程上置信界算法，一种用于贝叶斯优化和赌博机问题的经典方法。 |
| 数据稀疏化 | 一种统计技术，通过将单个数据集划分为多个独立子集来生成独立数据集。 |
| 遗憾上界 | 衡量在线学习算法性能的理论指标，表示算法累积损失与最优策略累积损失之差的上限。 |
| 简单遗憾 | 在赌博机问题中，指算法在单次决策中相对于最优动作的损失。 |
| 分阶段消除算法 | 一种通过逐步淘汰表现不佳的动作来优化决策的算法框架。 |
📱 每天一份 AI 前沿日报
关注公众号，每天 09:00 推送 · 不错过任何重磅