Bandit 反馈下多变点识别的样本复杂度研究

针对在 Bandit 反馈下定位分段常数函数多个变点的任务，研究者提出了一种先检测变点候选区间再逐步精细化定位至目标精度 $\eta$ 的自适应算法。该研究建立了非渐近样本预算的理论上下界，打破了以往认为渐近复杂度仅由跳跃幅度决定的认知，理论与实证均表明在一般置信度 $1-\delta$ 与精度 $\eta$ 下，样本复杂度由跳跃幅度与变点相对位置共同决定。