当前效应推断代价多大？K臂老虎机新算法TRACE实现极小极大最优遗憾！
The Price of Current-Effect Inference in Nonstationary Multi-Armed Bandits
📖 AI 总结
该研究探讨非平稳多臂老虎机中“当前效应推断”与“奖励最大化”之间的内在冲突：前者要求持续探索可能次优的干预以跟踪时变效应，后者则倾向选择更优干预。作者针对均值奖励满足Hölder光滑性（指数β、常数L）的K臂情形，在要求所有当前效应同时获得宽度不超过w的高概率置信区间条件下，建立了期望动态遗憾的匹配极小极大界（至对数因子）。所提TRACE算法达到的遗憾由三部分构成：基础学习项、刷新当前效应估计的额外代价项，以及精度项；其中精度代价即使在某一臂始终最优时也无法避免，从而量化了推断精度对遗憾的“价格”。作者进一步给出基于经验Bernstein e-过程的扩展，使探索自适应于实际预测误差并保持最坏情形保证；并证明当块内漂移相对抽样误差可忽略时，奖励学习观测可复用于渐近正态的逐点推断，更强的局部平稳性还可带来局部渐近有效性。研究还表明遗憾约束可能阻碍对未知光滑性的诚实自适应，并用大量数值实验验证了理论。
🔑 关键词速览
| 多臂老虎机 (Multi-Armed Bandits) | 一种序贯决策框架，智能体在探索与利用之间权衡，以最大化累积奖励。 |
| 动态遗憾 (Dynamic Regret) | 衡量算法累积奖励与随时间变化的最优策略累积奖励之间差距的指标。 |
| 当前效应推断 (Current-Effect Inference) | 对当前时刻干预组与参考臂平均奖励差异的统计推断，而非历史平均。 |
| Hölder 光滑性 (Hölder Smoothness) | 描述奖励函数变化平滑程度的条件，由指数 β 和常数 L 刻画。 |
| 经验伯恩斯坦 e-过程 (Empirical-Bernstein e-process) | 一种基于经验伯恩斯坦不等式的序贯检验过程，用于自适应探索并保持最坏情况保证。 |
📱 每天一份 AI 前沿日报
关注公众号，每天 09:00 推送 · 不错过任何重磅