arXiv:2410.07638v1 类型: cross 摘要: 我们提出了一种新颖的分段平稳线性bandit (PSLB) 模型，其中环境在每个变更点随机从未知概率分布中抽取一个上下文，并通过其在所有上下文上的回报平均值来衡量臂的质量。环境及其分布，以及变更点都对代理未知。我们设计了一个名为分段平稳ε-最优臂识别+ (PSεBAI+) 的算法，该算法可以以概率≥1-δ的方式识别出一个ε-最优臂，并且使用最少的样本数量。PSεBAI+ 由两个子模块 PSεBAI 和 Naïve ε-BAI (NεBAI) 组成，它们并行执行。PSεBAI 主动检测变更点并对齐上下文，以促进臂的识别过程。当智能并行使用 PSεBAI 和 NεBAI 时，PSεBAI+ 被证明具有有限的期望样本复杂度。通过证明下界，我们显示 PSεBAI+ 的期望样本复杂度在对数因子内达到了最优。我们使用数值实验将 PSεBAI+ 与基线算法进行比较，这些实验表明它具有高效性。我们的理论和数值结果都证实，PSεBAI+ 的有效性归因于 PSεBAI 中嵌入的精细变更检测和上下文对齐过程。