[LG]《A Reduction Algorithm for Markovian Contextual Linear Bandits》K Buyukkalayci, O Hanna, C Fragouli [University of California, Los Angeles & Meta] (2026)

在序贯决策领域，当动作集随时间变化时，标准线性赌博机理论要求上下文独立同分布，而现实中机器人位置、用户偏好等往往呈马尔可夫相关性。已有的 i.i.d. 归约框架在时序依赖出现时彻底失效，根本原因是非平稳条件分布向线性赌博机引入了无法控制的偏差。

本文的核心洞见是：把马尔可夫上下文的时序相关性重新看作一个可被"等待"消除的偏差。由此，延迟反馈这一关键操作使问题得以解开——给马尔可夫链足够时间混合后，条件分布与平稳分布之间的差距以多项式速率收缩，使标准线性赌博机算法在无感知偏差的环境下正常运行。

这项工作真正留下的遗产是：遍历性可以扮演独立性的角色，时序依赖不必然提高学习难度。它为后来者打开的新门是将此归约思路推广至更广泛的遍历过程与对抗性奖励设定；但尚未跨过的门槛是：混合时间未知时存在额外的 $(1-\beta)^{-1/2}$ 代价，且当混合极慢时遗憾界可能显著劣化。

arxiv.org/abs/2603.12530

机器学习 人工智能 论文 AI创造营