AFA-BANDIT：预算约束下具有理论近最优保证的在线多特征分类

arXiv:2610.07615v1 公告类型：新 摘要：主动特征获取（AFA）是一类分类问题，其中智能体在预测每个样本的标签之前，决定获取哪些高成本特征。不同于批量 AFA（后者在完整观测的数据上离线训练固定策略和分类器），在线 AFA 会随着样本的到达，根据已揭示的标签更新其预测器。现有在线方法要么使用无法提供性能保证的深度强化学习（RL），要么最大化经成本调整的奖励，而不是施加全局预算约束。我们将在线 AFA 建模为组合式带背包的多臂老虎机（BwK）问题，将特征获取与预测结合起来。不同于以往基于多臂老虎机的 AFA 和经典 BwK，我们的设定同时具有组合复杂性、不断变化的奖励、全局预算以及结构化辅助信息。在这一框架下，借助考虑基数的置信界和子集更新结构，我们获得了优于标准 BwK 界的改进遗憾上界。为避免指数级增长的动作空间，我们提出了 \emph{LP-Chain}，一种搜索成本感知特征子集链的变体，其规模随特征数量线性增长。尽管遗憾上界是针对组合式框架给出的，\emph{LP-Chain} 在实验中仍取得了相当的预测性能。在合成数据上，\emph{LP-Chain} 优于基于 HEDGE 的 BwK 和基于深度 RL 的在线 AFA 基线方法，并且能够更有利地扩展到更多特征。