在固定预算下定位奖励突变点，提出高效算法并证明其最优性。
Fixed-Budget Change Point Identification in Piecewise Constant Bandits
- 基于固定探索预算，设计可定位奖励突变点的策略。
- 小预算与大预算下均实现近似最优的错误概率上界。
- 算法自适应不同预算规模，适合在线学习与资源受限场景。
我们研究了分段常数老虎机问题，其中期望奖励是定义在动作空间 [0,1] 上的分段常数函数，仅有一个变化点（不连续点），学习者的任务是定位该变化点。在固定探索预算的假设下，首次对旨在识别均值奖励函数中突变的策略进行了非渐近分析。我们研究了大预算和小预算两种情形，并在两种设定下建立了误差概率的下界，同时提出了具有近似匹配上界的算法。有趣的是，我们的结果揭示了两种情形在复杂度上的分离。随后，我们提出一种可自适应不同预算区间的算法，该算法在小预算和大预算下均接近最优。我们通过模拟环境中的实验结果补充了理论分析，验证了结论的合理性。
原文摘要 · Abstract (English)
We study the piecewise constant bandit problem where the expected reward is a piecewise constant function with one change point (discontinuity) across the action space $[0,1]$ and the learner's aim is to locate the change point. Under the assumption of a fixed exploration budget, we provide the first non-asymptotic analysis of policies designed to locate abrupt changes in the mean reward function under bandit feedback. We study the problem under a large and small budget regime, and for both settings establish lower bounds on the error probability and provide algorithms with near matching upper bounds. Interestingly, our results show a separation in the complexity of the two regimes. We then propose a regime adaptive algorithm which is near optimal for both small and large budgets simultaneously. We complement our theoretical analysis with experimental results in simulated environments to support our findings.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。