Best-Arm Identification with Generative Proxy
作者: Tianyi Ma, Hanzhang Qin, Ruihao Zhu, Jierui Zuo
分类: cs.LG, stat.ML
发布日期: 2026-07-08
💡 一句话要点
提出PROBE算法以解决最佳臂识别中的样本效率问题
🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)
关键词: 最佳臂识别 样本效率 控制变量 异方差识别 普通最小二乘法 机器学习 在线学习
📋 核心要点
- 现有的最佳臂识别方法在面对昂贵的奖励观察时，样本效率较低，难以有效利用廉价的代理评分。
- 论文提出的PROBE算法通过控制变量调整，将问题转化为异方差识别，利用普通最小二乘法维护残差方差的上界。
- 实验表明，PROBE在合成实例和实际应用中表现出显著的样本节省，验证了理论的有效性和实用性。
📝 摘要（中文）
最佳臂识别是数据驱动决策中的经典模型，但在许多应用中，每次奖励观察的成本较高。本文研究了一种固定置信度的最佳臂识别方法，其中每次昂贵的奖励拉取都与一个廉价但相关的代理评分配对。通过控制变量调整，将该模型转化为异方差识别问题，提出了PROBE算法，该算法通过普通最小二乘法直接维护残差方差的上界，确保了在未知相关性的情况下证书的有效性。实验结果表明，PROBE的样本节省与奖励-代理相关性的强度成正比，验证了理论预测的准确性。
🔬 方法详解
问题定义：本文旨在解决最佳臂识别中的样本效率问题，现有方法在使用昂贵的奖励观察时，无法有效利用廉价的代理评分，导致样本浪费。
核心思路：论文的核心思路是通过控制变量调整，将最佳臂识别转化为异方差识别问题，并提出PROBE算法，利用普通最小二乘法直接维护残差方差的上界，从而提高样本效率。
技术框架：整体架构包括两个主要阶段：第一阶段是离线估计代理的边际均值，第二阶段是在线学习奖励与代理之间的相关性。PROBE算法在在线学习过程中，动态调整残差方差的上界。
关键创新：最重要的技术创新在于将控制变量调整引入异方差识别问题，并通过普通最小二乘法确保证书的有效性，这与现有方法在处理未知相关性时的保守性形成鲜明对比。
关键设计：在算法设计中，关键参数包括代理评分的边际均值和残差方差的上界，损失函数采用普通最小二乘法的形式，确保在未知相关性下仍能保持算法的有效性。算法还在$(ε,δ)$-PAC设置下进行了扩展。
🖼️ 关键图片
📊 实验亮点
实验结果显示，PROBE算法在合成数据和实际的汽车贷款定价重放中，样本节省与奖励-代理相关性的强度成正比，验证了理论预测的准确性。具体而言，PROBE在样本复杂度上相较于基线方法有显著提升，达到了已知相关性下的最优样本复杂度。
🎯 应用场景
该研究的潜在应用领域包括在线广告投放、推荐系统和金融决策等场景，能够有效降低决策成本，提高样本利用效率。随着机器学习和大语言模型的普及，PROBE算法在实际应用中具有重要的价值，能够帮助决策者在高成本环境中做出更优选择。
📄 摘要（原文）
Best-arm identification is a canonical model for data-driven decision-making, but in many applications each reward observation is costly. Motivated by the growing availability of cheap predictions from machine learning and large language models, we study fixed-confidence best-arm identification in which each costly reward pull is paired with a cheap but correlated proxy score. The marginal mean of the proxy can be estimated offline and is treated as known, whereas its correlation $ρ$ with the reward, which governs how much the proxy helps, is unknown and must be learned online in pair with real rewards. We show that a control-variate adjustment turns this model into a heteroscedastic identification problem whose oracle sample complexity improves by residual variance $1-ρ^2$. The central difficulty is that the correlation must be learned from the same costly samples that identification consumes online, and that a plug-in estimate of the residual variance is anti-conservative and can compromise correctness. We propose PROBE (PRoxy OLS for Best-arm Exploration), a phase-elimination algorithm that directly maintains an upper certificate on the residual variance with an ordinary least squares fit, whose exact chi-square law keeps the certificate valid regardless of the unknown correlation. We prove that PROBE is $δ$-PAC and attains the known-correlation oracle sample complexity up to a constant multiplicative factor and a constant additive calibration cost. The guarantee extends to the $(ε,δ)$-PAC setting under minimal changes to the algorithm. Numerical experiments on synthetic instances and on an auto-loan pricing replay with large language model and tabular proxies confirm that the sample savings of PROBE scale with the strength of the reward-proxy correlation, exactly as the theory predicts.