Nearly Optimal Fixed-Confidence Best-Arm Identification with 1-Bit Feedback¶

会议: NeurIPS 2026
arXiv: 2610.02771
论文: https://arxiv.org/abs/2610.02771
领域: 其他
关键词: 最佳臂识别, 1比特反馈, 尾部积分恒等式, 时间一致置信序列, 自适应分阶段截断

一句话总结¶

针对有限方差分布无关设定下仅能获取单比特集合查询反馈的最佳臂识别难题，本文基于截断尾部积分恒等式与随机化阈值查询构建了时间一致均值估计原语，提出定截断与自适应分阶段截断算法，并给出匹配的信息论下界证明对数惩罚的不可避免性。

研究背景与动机¶

固定置信度最佳臂识别（Fixed-Confidence Best-Arm Identification, BAI）是纯探索多臂老虎机中的经典核心课题，其目标是在保证输出臂高概率达到 $\varepsilon$-最优的前提下，尽可能减少与环境交互采样的总轮数。在经典文献设定中，算法拉动任意臂后均能直接观测到实值奖励样本，从而可以通过直接构建经验均值与经验方差来维持置信区间或运行逐次淘汰机制。然而在物联网上行受限感知（如传感器仅能发送标量是否超过本地阈值的单比特标志）以及出价机制（如仅能观测买家是否接受某一口价的成交指示位）等现实场景中，中央决策者在每一轮只能向环境提交查询集合并接收 1 比特的二值反馈。

这种严苛的信息瓶颈使得经典算法完全失效，其核心矛盾在于：在仅有有限二阶矩假设（未假设有界支撑集或次高斯尾部）的分布无关环境下，算法必须通过截断（Clipping）来控制方差与估计范围，但这不可避免地引入了截断偏差（Bias）；更为棘手的是，多臂老虎机中每个臂的分配拉动次数与停止时间具有强烈的数据依赖性与适应性（Adaptivity），无法直接套用样本量固定的点估计器，必须在整个采样时间轴上维持时间一致（Time-Uniform）的置信有效性。

为了打破有限方差与 1 比特交互下的偏差-方差困境，本文从一维实变量积分几何出发，重构了单比特均值估计与自适应臂淘汰流水线。核心 idea：利用截断尾部积分恒等式将均值重写为阈值超越概率差分积分，通过随机化阈值查询构造单样本无偏估计量并推导时间一致置信序列，再将截断级别与消除统计分辨率动态对齐，以近乎最优的样本复杂度达成固定置信度最佳臂识别。

方法详解¶

整体框架¶

算法的整体 pipeline 围绕“局部化锚点初始化 $\to$ 单比特尾部积分查询 $\to$ 时间一致置信区间维持 $\to$ 候选者-挑战者淘汰与停止”展开。系统首先通过中位数估计子程序（MedianEst）在粗糙网格上为每个臂确定距离真值均值不超过常数倍标准差 $\sigma$ 的局部化锚点 $c_k$；在后续的主识别阶段，算法分别采用两套架构：一套是基于全局固定截断参数 $L_\varepsilon$ 的随时可用（Anytime）算法 FixedClip-1BitBAI；另一套则是从粗到细调度分辨率梯度的分阶段自适应算法 RestartPhasedClip-1BitBAI。

在分阶段自适应框架中，算法按几何级数缩减统计分辨率 $\rho_j = 2^{-j}\sigma$，将每一阶段的截断级别严格对齐为 $L_j = 32\sigma^2/\rho_j$。在阶段 $j$ 内部，系统交替选取置信下界最高的候选臂 $h$ 与其余臂中置信上界最高的挑战者臂 $\ell$，优先拉动置信半径较大的臂并执行随机化单比特查询，直至满足 $\varepsilon$-最优停止条件或将当前所有活跃臂的置信半径压缩至目标尺度 $r_j = \rho_j/16$；阶段末尾则依据置信界安全剔除次优臂并步入更精细阶段。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入：K个臂分布族<br/>方差代理σ与精度ε, 置信度δ"] --> B["中位数锚点定位<br/>MedianEst获取初始锚点ck"]
    B --> C["分阶段分辨率调度<br/>设定分辨率ρj与对齐截断级别Lj"]
    C --> D["尾部积分单比特查询<br/>随机化采样S与T并观测指示位Y"]
    D --> E["时间一致置信序列构建<br/>拼接伯恩斯坦边界形成LCB与UCB"]
    E --> F{"候选者-挑战者对比<br/>判定Gap与统计半径"}
    F -->|达到ε最优或单臂存活| G["输出ε最优推荐臂并停止"]
    F -->|半径缩小至rj且未收敛| H["安全淘汰次优臂<br/>晋级下一精细阶段j+1"]
    H --> C
    F -->|当前阶段未完成收敛| D

关键设计¶

1. 截断尾部积分恒等式与随机化阈值查询：将单比特比较转化为均值无偏估计

针对无法直接观测实值奖励导致的均值估计障碍，本文基于实变量截断算子 $[w]_L = \max\{-L, \min\{w, L\}\}$ 建立了恒等式 $[w]_L = \int_{0}^L (\mathbf{1}\{w \geq t\} - \mathbf{1}\{w \leq -t\}) dt$。对于以已知锚点 $c_k$ 为中心化的变量 $W = X - c_k$，其截断均值可表示为上下尾部超越概率之差的定积分。为使用单比特观测无偏估计此积分，算法构造了分布密度 $g_L(t) = 1/[\alpha_L \max\{\sigma, t\}]$（其中 $\alpha_L = 1 + \log(L/\sigma)$），在每一轮独立均匀抽取符号 $S \in \{+1, -1\}$ 与连续阈值 $T \sim g_L$，向环境提交查询集合并在观测到单比特反馈 $Y = \mathbf{1}\{S(X-c_k) \geq T\}$ 后构造统计量： $$Z := \frac{2S}{g_L(T)} Y$$ 该设计极其精妙地实现了 $\mathbb{E}[Z \mid W] = [W]_L$ 以及无偏性 $\mathbb{E}[Z] = \mathbb{E}[[W]_L]$，且将方差严格控制在 $\mathrm{Var}(Z) \leq 3\alpha_L\sigma^2$，绝对上界满足 $|Z| \leq 2\alpha_L L$。由方差有界性可知其截断偏差满足 $|\mathbb{E}[W] - \mathbb{E}[[W]_L]| \leq \frac{\sigma^2}{2L}$，从而将实数估计完全转化为带对数方差惩罚的受控二值推断问题。

2. 时间一致置信序列构建：适应自适应臂选择与随机停止时间

多臂纯探索算法的臂拉动次数 $N_k(t)$ 与终止轮数 $\tau$ 本质上是数据依赖的停时，传统固定样本量的集中不等式直接应用会导致显著的置信泄露。本文利用 Ville 极大值鞅不等式与二进划分拼接技术（Stitching Method），为上述 1 比特统计量构建了全时间轴一致成立的置信半径 $\beta(n, \gamma, L)$。在任意给定的阶段截断级别 $L$ 与置信预算 $\gamma$ 下，真值均值 $\mu_k$ 以至少 $1-\gamma$ 的概率对所有正整数 $n \geq 1$ 满足 $|\hat{\mu}_{k,n} - \mu_k| \leq \beta(n, \gamma, L)$： $$\beta(n, \gamma, L) = \frac{\sigma^2}{2L} + 2\sqrt{\frac{3\alpha_L\sigma^2 x_n(\gamma)}{n}} + \frac{\alpha_L L x_n(\gamma)}{n}$$ 其中拼接惩罚项定义为 $x_n(\gamma) := \log(\pi^2(1+\lfloor\log_2 n\rfloor)^2 / (3\gamma))$，其渐近尺度为 $\mathcal{O}(\log(1/\gamma) + \log\log n)$。该置信序列将确定性截断偏差项、随机游动波动项（$\mathcal{O}(n^{-1/2})$）与伯恩斯坦极差修正项（$\mathcal{O}(n^{-1})$）深度融合，为候选臂与挑战者臂之间的停时判定提供了坚实的数学防线。

3. 自适应分阶段截断调度：根据臂区分尺度消除固定截断混合惩罚

在固定截断算法 FixedClip-1BitBAI 中，为了保证全局最差截断偏差不超过 $\varepsilon/4$，必须将截断参数全局固定为 $L_\varepsilon = 2\sigma^2/\varepsilon$；这导致即使一个臂具有极大的次优差距 $\Delta_k \gg \varepsilon$，其伯恩斯坦范围修正项仍必须承担 $\frac{\sigma^2}{\varepsilon \widetilde{\Delta}_k}$ 的混合复杂度开销。分阶段算法 RestartPhasedClip-1BitBAI 引入分辨率梯度，设定 $\rho_j = 2^{-j}\sigma$，并将对应截断设为 $L_j = 32\sigma^2/\rho_j$、置信目标半径设为 $r_j = \rho_j/16$。在粗分辨率阶段，次优差距满足 $\Delta_k > \varepsilon + \rho_j/4$ 的较差臂在极小的样本开销下即可被 UCB-LCB 规则安全淘汰，绝不会存活进入细分辨阶段；唯有真正具有竞争力的候选臂才会进入更深阶段。该机制消除了固定截断的混合项，使得各臂仅根据自身有效差距 $\overline{\Delta}_k = \min\{\max\{\Delta_k, \varepsilon\}, \sigma\}$ 贡献对数惩罚样本量。

一个完整示例¶

考虑一个 $K=3$ 的多臂老虎机，已知全局方差代理 $\sigma=1.0$，目标精度 $\varepsilon=0.05$。各臂真实均值分别为 $\mu_1 = 0.5$（最优臂 $k^\star=1$），$\mu_2 = 0.3$（差距 $\Delta_2=0.2$），$\mu_3 = 0.1$（差距 $\Delta_3=0.4$）。初始锚点由中位数估计器确定为 $c_1=c_2=c_3=0$。算法执行自适应分阶段调度： - 阶段 0 ($\rho_0=1.0$)：设置截断界 $L_0=32$，目标半径 $r_0=0.0625$。所有活跃臂采样至置信半径收敛到 $r_0$ 附近，此时 $\Delta_3=0.4 > 0.05 + 1.0/4 = 0.30$，3 号臂的 UCB 显著落后于当前最优 LCB，被直接淘汰。 - 阶段 1 ($\rho_1=0.5$)：剩余活跃臂集为 $\{1, 2\}$，截断界精细化提升至 $L_1=64$，目标半径缩小至 $r_1=0.03125$。继续对比 1 号臂与 2 号臂，当置信区间收缩至 $r_1$ 时，$\Delta_2=0.2 > 0.05 + 0.5/4 = 0.175$，2 号臂被成功识别并淘汰。 - 阶段 2 及终止：活跃集仅剩 1 号臂（$|A|=1$），算法安全停止并推荐臂 1 为最优臂。整个流程中，大差距臂 3 在粗糙分辨率下仅耗费少量查询即被舍弃，避免了在细分辨率下承受过大范围惩罚。

实验关键数据¶

主实验¶

论文在单比特均值估计与多臂最佳臂识别两个维度上进行了系统性的对比验证。在均值估计主实验中，固定真值 $\mu=1$、方差代理 $\sigma=1$、锚点 $c=0$，在名义截断偏差目标 $b=0.1$（对应 $L=t=5$）下，对比本文尾部积分估计器（Ours）与 Lau-Scarlett [20] 分区估计器在不同分布下的真实偏差及经验离散度（$1000$ 次独立重复）。

分布环境	样本量 $n$	本文标准差 (Ours)	Lau-Scarlett [20] 标准差	离散度比例 (LS / Ours)
高斯分布 (Normal)	$10^4$	0.02515	0.04917	1.955
高斯分布 (Normal)	$10^6$	0.002472	0.005166	2.090
Student-t(5) 重尾	$10^4$	0.02532	0.04995	1.973
Student-t(5) 重尾	$10^6$	0.002452	0.005002	2.040
偏置指数分布 (Exponential)	$10^4$	0.02469	0.04917	1.992
偏置指数分布 (Exponential)	$10^6$	0.002413	0.004916	2.037

消融实验¶

在多臂老虎机最佳臂识别实验中（$K=5$, $\sigma=0.5$, $\varepsilon=0.05$），对比固定截断（FixedClip）、分阶段重启（RestartPhase）、分阶段样本复用（ReusePhase）以及具有完整实值反馈的 UGapE 基线在不同奖励分布与差距结构下的平均停止轮数（5000 次独立运行）。

算法配置	伯努利分布 (等差距 $\Delta_k=0.1$, $\delta=0.05$)	高斯分布 (异质差距线性衰减, $\delta=0.05$)	Student-t(3) (重尾异质差距, $\delta=0.05$)	说明
UGapE (实值连续反馈基线)	~1,200	~2,100	~2,400	拥有完整标量反馈的理想基准
FixedClip-1BitBAI (定截断)	~7,800	~14,200	~15,100	全程采用最细截断 $L_\varepsilon$，异质差距下开销大
RestartPhase-1BitBAI (分阶段重启)	~7,900	~9,800	~10,300	粗分辨率早淘汰大差距臂，查询数降低 ~31%
ReusePhase-1BitBAI (分阶段样本复用)	~7,600	~9,100	~9,500	跨阶段复用已有阈值切片，性能略优于重启版本

关键发现¶

在单比特均值估计中，本文提出的随机化平滑采样机制相比于分块阶梯基线具有显著更小的真实截断偏差（如高斯分布下本文偏差为 $7.15 \times 10^{-6}$，基线为 $1.66 \times 10^{-4}$；重尾 Student-t 下本文为 $1.56 \times 10^{-3}$，基线为 $9.06 \times 10^{-3}$）。在经验标准差上，基线各配置下的离散度恒为本文的 1.924 至 2.090 倍（相当于方差增大 3.7 至 4.4 倍），因而本文估计器拥有显著更优的预渐近 MAE 衰减速度。
在多臂最佳臂识别任务中，臂间差距的几何结构对截断策略有着决定性影响：在伯努利等差距环境下，所有次优臂差距相同，无法在粗分辨率下提前剔除，固定截断与分阶段自适应算法表现接近；而在高斯与重尾分布等异质差距环境下，分阶段自适应截断通过及早过滤大差距臂，大幅减少了在高截断级别下的低效采样，总停止轮数显著优于固定截断。

亮点与洞察¶

巧妙衔接几何恒等式与 1 比特感知：将截断变量的几何积分定义与连续密度阈值抛币结合，仅用单比特集合查询便实现了对截断均值的精确无偏估计，避免了启发式区间搜索带来的信息丢失。
严密的时间一致自适应置信界构建：将经典鞅不等式与子指数极差控制扩展至 1 比特反馈，成功解决了多臂老虎机适应性停时中的置信有效性问题，填补了 1 比特均值估计向序列决策迁移的理论鸿沟。
匹配的信息论下界揭示对数惩罚本质：通过构造多尺度扰动困难实例并结合自适应停时测度变换，严格证明了在有限二阶矩下 1 比特最佳臂识别必承受 $\Omega((K-1)\frac{\sigma^2}{\Delta^2} \log\frac{\sigma}{\Delta} \log\frac{1}{\delta})$ 的样本量，证明了本文分阶段算法在 worst-case 意义下的渐近最优性。

局限与展望¶

依赖初步局部化锚点先验：算法理论分析预先假定了每个臂已知满足 $|\mu_k - c_k| \le \sigma$ 的锚点；尽管可通过中位数预估计子程序（MedianEst）在紧凑区间 $[-\lambda, \lambda]$ 上初始化，但这额外引入了依赖于全局动态范围 $\lambda$ 的前期采样开销。
实例依赖最优性（Instance-Optimality）仍未封闭：下界构造主要针对 worst-case 等差距困难实例，在具有极端非均匀差距与非对称分布的任意实例上，严格渐近匹配的高阶常数与最优分配策略仍属于开放问题。
未来方向：可进一步将时间一致单比特尾部估计原语推广至通信受限下的纯探索强化学习、带约束的线性/组合老虎机以及联邦分布式臂选择场景中。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次系统性解决有限方差下 1 比特反馈的最佳臂识别问题，理论设计完备且兼具下界匹配。
实验充分度: ⭐⭐⭐⭐ 涵盖标量估计与多臂决策，跨高斯、重尾与有界分布，对比详尽但受限于算力规模仅验证了 5 臂场景。
写作质量: ⭐⭐⭐⭐⭐ 数学推导严密精炼，从恒等式引申至置信界与分阶段调度的逻辑链条极其顺畅明晰。
价值: ⭐⭐⭐⭐⭐ 为通信约束、硬件量化感知与出价机制下的序列决策提供了扎实的基础理论支撑与算法模板。

分布环境	样本量 \(n\)	本文标准差 (Ours)	Lau-Scarlett [20] 标准差	离散度比例 (LS / Ours)
高斯分布 (Normal)	\(10^4\)	0.02515	0.04917	1.955
高斯分布 (Normal)	\(10^6\)	0.002472	0.005166	2.090
Student-t(5) 重尾	\(10^4\)	0.02532	0.04995	1.973
Student-t(5) 重尾	\(10^6\)	0.002452	0.005002	2.040
偏置指数分布 (Exponential)	\(10^4\)	0.02469	0.04917	1.992
偏置指数分布 (Exponential)	\(10^6\)	0.002413	0.004916	2.037