Fixed-Confidence Multiple Change Point Identification under Bandit Feedback¶

会议: ICML2025
arXiv: 2507.08994
代码: 无
领域: bandits
关键词: change point detection, multi-armed bandits, pure exploration, fixed-confidence, Track-and-Stop, sample complexity

一句话总结¶

提出了固定置信度下分段常数 bandit 中多变点识别问题，给出实例相关的采样复杂度下界，并设计了简单高效且渐近最优的 MCPI（Multiple Change Point Identification）算法。

研究背景与动机¶

分段常数函数在化学、制造业、通信系统、材料科学、海洋地质等领域广泛存在。实际中经常需要以高置信度快速定位这些函数的突变点位置。例如：

通信系统：确定系统过载发生的临界点
材料开发：找到新材料在不同实验条件下发生相变的位置
海洋学：探测海底悬崖的边缘

这些场景中数据采集成本高昂，且对结果的可靠性有严格要求。现有工作主要集中在：(1) 固定预算（fixed-budget）下的单变点识别；(2) 非平稳 bandit 中的时间维度变点检测。本文首次系统研究了固定置信度（fixed-confidence）下多变点识别问题，填补了理论空白。

方法详解¶

问题形式化¶

考虑 \(K\) 个臂的 multi-armed bandit，均值 \((\mu_i)_{i=1}^K\) 在动作空间 \(\mathcal{A}=[K]\) 上分段常数。变点集合 \(\underline{x}^* \subset [K-1]\)，\(|\underline{x}^*| = N\)。每轮选择动作 \(a_t \in [K]\)，观测带噪奖励：

\[y_t = \mu_{a_t} + \epsilon_t, \quad \epsilon_t \sim \mathcal{N}(0, \sigma^2)\]

第 \(j\) 个变点处的跃变幅度定义为 \(\Delta_j = |\mu_{x_j^*} - \mu_{x_j^*+1}|\)。

两种目标¶

目标	定义	适用场景
Exact-\((N,\delta)\)	返回的 \(N\) 个变点恰好等于真实变点集合	已知变点数量
Any-\((N,\delta)\)	返回的 \(N\) 个变点是真实变点集合 \(\underline{x}^*\)（可能 \(m \geq N\) 个）的子集	未知变点数量

两种情形都要求 \(\mathbb{P}(\text{正确}) > 1 - \delta\) 且有限时间停止。

实例相关下界¶

单变点下界（Corollary 4.3）：

\[\mathbb{E}[\tau] \geq \frac{8\sigma^2}{\Delta^2} \log\frac{1}{4\delta}\]

最优采样比例 \(\alpha^*\) 有显式解：只在变点两侧各采一半，其余动作不采。

多变点下界（Theorem 5.2, Exact 情形）：

\[\mathbb{E}[\tau] \geq 4\sigma^2 \log\frac{1}{4\delta} \sum_{i=1}^{N} \frac{1}{\Delta_i^2}\]

未知变点数下界（Theorem 5.5, Any 情形）：

\[\mathbb{E}[\tau] \geq 8\sigma^2 \log\frac{1}{4\delta} \sum_{i=1}^{N} \frac{1}{\Delta_{(i)}^2}\]

其中 \(\Delta_{(i)}\) 为按幅度降序排列的第 \(i\) 个变点跃变。

关键洞察¶

最优策略应将采样集中在变点两侧相邻动作上，且每个变点周围的采样量反比于跃变幅度的平方：

\[\alpha_j^* = \alpha_{j+1}^* = \frac{1/\Delta_j^2}{2 \sum_{i=1}^N 1/\Delta_i^2}\]

MCPI 算法（Algorithm 2）¶

MCPI 是 Track-and-Stop 框架的变体，包含三个组件：

1. 采样规则

强制探索：若某动作被采样次数 \(T_i(t) < \sqrt{t}\)，优先采样该动作
跟踪：估计 \(N\) 个变点位置 \(\hat{x}_1, \dots, \hat{x}_N\)，在每个估计变点两侧均匀采样，选择当前采样比例最低于目标比例的动作

变点估计器使用最大经验均值差：

\[\hat{x}_t(S) = \arg\max_{a \in S} |\hat{\mu}_a(t) - \hat{\mu}_{a+1}(t)|\]

2. 停止规则

基于 Chernoff 停止时间，对每个估计变点 \(\hat{x}_j\) 计算检验统计量：

\[Z_j(t) = \frac{T_{\hat{x}_j}(t) \cdot T_{\hat{x}_j+1}(t)}{2(T_{\hat{x}_j}(t) + T_{\hat{x}_j+1}(t))} \hat{\Delta}_{\hat{x}_j}^2\]

当所有变点的 \(Z_j(t)\) 都超过阈值 \(\beta(t, \delta/N)\) 时停止。

3. 推荐规则

返回停止时刻的变点估计 \(\hat{x}_1, \dots, \hat{x}_N\)。

渐近最优性（Theorem 5.7）¶

MCPI 在 Exact 和 Any 两种目标下均渐近最优：

\[\limsup_{\delta \to 0} \frac{\mathbb{E}[\tau_\delta]}{\log(1/\delta)} \leq 8\sigma^2 \sum_{i=1}^N \frac{1}{\Delta_i^2}\]

与下界匹配（至多常数因子 2 的差距），且不需要已知变点数 \(N\)。

理论结果总结¶

结果	复杂度/界	条件
单变点下界	\(\frac{8\sigma^2}{\Delta^2}\log\frac{1}{4\delta}\)	\(N=1\)，已知
多变点下界 (Exact)	\(4\sigma^2 \log\frac{1}{4\delta} \sum_i \Delta_i^{-2}\)	已知 \(N\)
多变点下界 (Any)	\(8\sigma^2 \log\frac{1}{4\delta} \sum_i \Delta_{(i)}^{-2}\)	未知 \(N\)，\(m \geq N\)
CPI 上界 (单变点)	\(\frac{8\sigma^2}{\Delta^2}\log\frac{1}{\delta}\)	渐近最优
MCPI 上界 (多变点)	\(8\sigma^2 \log\frac{1}{\delta} \sum_i \Delta_i^{-2}\)	渐近最优，两种目标
已知 vs 未知 \(N\) 代价	至多 \(\times 2\)	渐近意义

亮点与洞察¶

显式最优解：不同于一般 Track-and-Stop 需数值求解优化问题，本文利用分段常数结构解析求解了最优采样比例，带来计算效率和可解释性的双重优势
直觉清晰：最优策略只在变点两侧采样，小跃变分配更多样本——这与直觉完全一致
统一框架：MCPI 一个算法同时在 Exact 和 Any 两种目标下渐近最优
与经典统计的联系：停止时间的形式与离线变点分析中的 CUSUM/GLR 检验有内在关联
优于聚类 bandit：实验表明 MCPI 大幅优于将问题视为聚类 bandit（Yang et al., 2022）的方法，因为后者未利用分段常数的空间结构

局限与展望¶

高斯噪声假设：理论结果依赖已知方差的高斯噪声假设，推广到亚高斯或更一般分布仍为开放问题
一维动作空间：仅考虑了一维分段常数函数，高维变化面（change surface）的扩展未涉及
仅有合成实验：实验在人工生成环境中进行，缺乏真实世界应用验证
渐近最优性：上下界匹配是渐近的（\(\delta \to 0\)），有限样本下的性能保证可进一步加强
强制探索代价：\(\sqrt{t}\) 的强制探索虽保证了一致性，但在有限时间带来额外采样开销

评分¶

新颖性: ⭐⭐⭐⭐ — 首次系统研究固定置信度多变点 bandit 识别
理论深度: ⭐⭐⭐⭐⭐ — 上下界紧密匹配，显式解优雅
实验充分度: ⭐⭐⭐ — 仅合成实验，无真实数据
写作质量: ⭐⭐⭐⭐ — 结构清晰，动机充分
综合价值: ⭐⭐⭐⭐