首次高概率遗憾界！FGTS性能直逼最优算法，代价仅对数项！
High-Probability Regret Bounds for Feel-Good Thompson Sampling
📖 AI 总结
本文研究“感觉良好汤普森采样”（FGTS）算法在上下文赌博机中的遗憾界问题。FGTS 通过在朴素汤普森采样的后验中引入探索项，偏好预测最优值较高的奖励函数，此前已被证明在线性上下文赌博机中达到极小极大最优遗憾（至多对数因子），但现有对两种标准变体（累积式与当前步式）的分析仅给出期望意义下的保证。本文首次在一般可实现函数逼近的上下文赌博机中，为这两种变体推导出高概率遗憾界，其界依赖于相应的解耦系数以及真实奖励函数附近的先验质量。在 d 维线性设定下，两种变体均以至少 1−δ 的概率满足遗憾为 O(d√T log(2T)+√T log(1/δ))，与基于上置信界的算法在维度和时间跨度上的依赖相匹配（至多对数因子）。相比期望遗憾保证，高概率控制带来的额外代价仅限于对 log(1/δ) 至多线性依赖的加性项。
🔑 关键词速览
| Feel-good Thompson sampling (FGTS) | 一种增强的汤普森采样算法，通过在后验中加入探索项来偏好高预测最优值的奖励函数。 |
| Regret | 遗憾，衡量在线学习算法性能的指标，表示算法累积奖励与最优策略累积奖励之间的差距。 |
| Contextual bandits | 上下文赌博机，一种在线学习框架，智能体在每轮根据上下文选择动作并获得奖励，目标是最大化累积奖励。 |
| High-probability regret bounds | 高概率遗憾界，指算法遗憾以至少1-δ的概率不超过某个界限，提供了比期望遗憾更强的保证。 |
| Decoupling coefficients | 解耦系数，用于衡量函数逼近中不同样本之间依赖性的量，出现在遗憾界中。 |
📱 每天一份 AI 前沿日报
关注公众号，每天 09:00 推送 · 不错过任何重磅