AFA-Bandit 将在线主动特征获取建模为组合式背包老虎机，LP-Chain 在合成数据上以线性规模链式搜索超越 HEDGE 与深度强化学习基线
核心概要
该工作把在线主动特征获取（AFA）建模为预测器耦合的组合式背包老虎机问题，在全局预算下同时决定特征获取与标签预测，并利用基数感知置信界与子集反馈结构得到比经典 BwK 更紧的遗憾上界；为规避指数级动作空间，作者提出 LP-Chain，用随特征数线性增长的代价感知链搜索候选子集，在合成高斯混合数据上其预测误差低于 HEDGE 式 BwK 与深度强化学习在线 AFA 基线。
Figure 1: Average prediction error versus budget fraction q q on synthetic data. OL: Opportunistic Learning [ 15 ] ; HEDGE (BwK): HEDGE-based BwK policy [ 6 ] ; LP-Chain (ours): the proposed method; Lower Bound: prediction error of the full-action oracle OPT LP \mathrm{OPT}_{\mathrm{LP}} . Lower is better.
arXiv深度剖析
将在线 AFA 形式化为预测器耦合的组合式 BwK 问题，其中每个可行特征子集是一个带代价的臂，奖励随预测器更新而演化，并受全局获取预算约束。 既有基于老虎机的 AFA 工作要么把获取代价从奖励中扣除而不施加全局预算，要么只关注最小化获取代价；经典 BwK 则不含组合结构、演化奖励与结构化反馈。该形式化把获取与预测耦合进同一预算约束框架。 问题定义与线性规划松弛基准（式 5）在正文第 2 节给出，并说明该松弛是动态 oracle 的可解上界，从而把遗憾界定为相对 LP 松弛的遗憾。
在该组合框架下给出比直接套用经典 BwK 界更紧的遗憾上界，改进因子为阶数级别，来源是基数感知置信界与子集更新结构。 证明利用被获取集合的所有子集都可被评估这一额外反馈，把误差项归结为反向分级偏序集的最大独立集规模，并用 Sperner 定理与 Stirling 近似得到约二项式系数量级，再经 Cauchy-Schwarz 引入类别数因子。 定理 1 及其证明梗概在正文第 4 节，完整推导在附录 B；分析基于 Assumption A（观测、奖励、代价有界，期望奖励对参数为 Lipschitz 光滑）。作者明确该上界仅适用于组合式设定，不适用于 LP-Chain。
提出 LP-Chain：每轮用乐观奖励贪心构造一条每次增加一个特征的代价感知特征链，再在剩余预算的每轮配额下求解候选动作上的线性规划并采样，链规模随特征数线性增长。 直接在全幂集上优化随特征数指数增长；LP-Chain 只考虑嵌套动作，并用每轮配额直接强制预算，而非依赖 OMD 对偶更新。 方法见第 3.2.2 节（式 15–19）；消融表 1 显示链式限制与全子集搜索的平均误差差异随特征数增长但保持很小（MSE 从 0.00005 到 0.00318），且在特征数为 20 时 LP-Chain 训练时间约 2,461.93 秒、组合式约 5,397.70 秒。
在合成高斯混合数据上，LP-Chain 在每个预算比例下平均预测误差均低于 HEDGE 式 BwK 与深度强化学习在线 AFA 基线 OL，且随预算增大与下界的差距收窄。 此前在线 AFA 方法或缺乏性能保证，或未在全局预算下与 BwK 式策略直接比较；该实验在同一全局获取预算下比较了链式选择、全动作资源加权选择与神经网络获取-预测方法。 第 5 节报告合成数据结果，样本以单一在线流到达，结果在 50 次独立试验上平均；附录 A.4 在 CKD、BankMarketing、PhysioNet、MNIST、FashionMNIST 上 LP-Chain 达到最高或近似最高表现，Diabetes 上 OL 在线训练准确率更高，且作者说明这些曲线是在线训练表现，不确立留出测试集上的相同排序。
启示与展望
该结果面向在线多分类设定：每轮从参数化混合分布抽取样本，特征代价已知，存在一组无代价特征，获取受全局预算约束，且预测后真实标签被揭示。在此设定下，组合式算法获得相对 LP 松弛的遗憾上界，LP-Chain 提供线性规模的实用替代，适用于需要在流式数据上按预算权衡获取与预测的读者，例如代价可量化的表格或图像特征分类任务。作者指出未来将扩展到 bandit 标签设定，即只返回正确/错误结果而非真实标签，并计划用弱监督学习中的无偏风险估计更新预测参数。
遗憾上界仅针对组合式设定，LP-Chain 的遗憾分析被作者留作未来工作，因此其实用变体目前只有经验证据。真实数据结果报告的是在线训练表现，作者明确这些曲线不确立留出测试集上的相同排序；Diabetes 上 OL 在线训练准确率更高，作者将其部分归因于类别平衡流与回放式更新，并说明 LP-Chain 未使用相同流、面向不平衡数据的适配留待未来。此外，合成实验使用高斯混合生成数据，作者强调该高斯模型仅用于生成数据，不被形式化、方法或分析所假设。