在噪声环境下快速定位分段常数函数的突变点，提升检测效率。
Fixed-Confidence Multiple Change Point Identification under Bandit Feedback
- 基于追踪停止思想设计高效采样策略，聚焦突变点附近区域。
- 理论证明最优采样量与突变幅度成反比，显著减少总查询次数。
- 适用于需要高置信度快速识别异常点的工业监控场景。
分段常数函数描述了从化学到制造等多个领域的实际现象。实践中，需以高置信度尽快识别这些函数中突变的位置。为此，我们提出固定置信度下的分段常数贝叶斯问题。在此设定下，按序查询域内点并接收带噪声的函数评估值，仅获得带限制反馈。我们给出了该问题中突变点识别复杂度的实例相关下界。这些下界表明，最优方法应将采样重点放在每个突变点附近，且每个突变点附近的采样次数应与其变化幅度成反比。基于此，我们设计了一种简单且计算高效的追踪停止变体，并证明其在多个情形下为渐近最优。我们在合成环境中的实验结果验证了该方法的高效性。
原文摘要 · Abstract (English)
Piecewise constant functions describe a variety of real-world phenomena in domains ranging from chemistry to manufacturing. In practice, it is often required to confidently identify the locations of the abrupt changes in these functions as quickly as possible. For this, we introduce a fixed-confidence piecewise constant bandit problem. Here, we sequentially query points in the domain and receive noisy evaluations of the function under bandit feedback. We provide instance-dependent lower bounds for the complexity of change point identification in this problem. These lower bounds illustrate that an optimal method should focus its sampling efforts adjacent to each of the change points, and the number of samples around each change point should be inversely proportional to the magnitude of the change. Building on this, we devise a simple and computationally efficient variant of Track-and-Stop and prove that it is asymptotically optimal in many regimes. We support our theoretical findings with experimental results in synthetic environments demonstrating the efficiency of our method.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。