精确滑动窗口约束下的线性赌博机

arXiv:2610.08745v1 公告类型：新增 摘要：我们研究精确滑动窗口约束下的线性赌博机问题，其中每个连续的动作块都必须属于预先规定的可行集合。在离线设置中，即奖励函数已知时，我们证明了当 $w\mid T$ 时，凸性与循环移位不变性使平稳解达到最优；否则，该解与最优解之间的差距为加性 $O(w)$。在在线设置中，我们证明仅凭几何结构不足以实现学习，次线性遗憾可能无法实现。我们引入转移直径 $\tau$ 来量化可行可达性，并设计了一种少切换的 OFUL 算法；相对于离线最优可行轨迹，其遗憾为 $\widetilde{O}(d\sqrt{T}+\tau d+w)$。最后，我们去除循环不变性，研究一般的滑动窗口约束，此时最优行为可能是非平稳的。我们将近期动作历史表示为有限记忆控制问题的状态，并引入历史状态直径 $D$，用于衡量可行历史之间的连通性。通过结合乐观的剩余时域规划与罕见的策略更新，我们获得了 $\widetilde{O}(d\sqrt{T}+dD+w)$ 的遗憾界。我们在真实世界和合成基准上评估了该方法，结果表明，该方法在保持严格可行性的同时，能够以显著更少的策略更新次数，达到与基线相当的奖励和遗憾表现。