赌博机遗憾界从T的2/3次方直降到平方根，自适应块乐观策略首次实现！
Block Optimism for Nonstationary Bandits with Latent Linear Dynamics
📖 AI 总结
本文研究一类具有潜在线性动态的内生非平稳随机赌博机问题，其中动作既影响即时奖励，也影响不可观测潜在状态的未来演化，奖励为动作与潜在状态的双线性函数，导致奖励依赖历史并带来长时程规划难题。已有的“先探索后承诺”方法通过均匀探索估计潜在动态，再固定开环动作序列，仅能达到 Õ(T^{2/3}) 的遗憾界。作者提出基于自适应块级乐观策略的改进算法，核心是循环近似：在稳定动态下将无限记忆的奖励过程截断，用有限记忆的块级代理优化开环基准，并据此设计基于UCB的块算法，对截断动态参数维护置信集并乐观选择动作块。理论证明该算法达到 Õ(√T) 的遗憾界，显著优于此前同模型下的 Õ(T^{2/3}) 结果。这是首个在双线性奖励观测与开环动作序列基准下，针对潜在线性动态赌博机取得 Õ(√T) 遗憾保证的工作，对非平稳决策与动态规划问题具有理论意义。
🔑 关键词速览
| 非平稳随机赌博机 | 一种奖励分布随时间变化的序贯决策问题，玩家需在探索与利用间权衡。 |
| 潜在线性动态 | 未观测状态按线性规则演化，且动作会影响该状态的转移。 |
| 双线性奖励 | 奖励函数是动作向量与潜在状态向量的内积，即对两者均为线性。 |
| 块级乐观 | 将时间划分为块，在块级别使用置信上界进行乐观决策以平衡探索与利用。 |
| 遗憾界 | 衡量算法累积奖励与最优策略累积奖励之间差距的理论上界。 |
📱 每天一份 AI 前沿日报
关注公众号，每天 09:00 推送 · 不错过任何重磅