AFA-BANDIT: Provably Near-Optimal Online Multi-Feature Classification Under Budget Constraints
作者: AbdAlRahman Odeh, Teng-Hui Huang, Hesham El Gamal
分类: cs.LG
发布日期: 2026-10-06
备注: 10 pages, 3 figures
💡 一句话要点
提出AFA-BANDIT以解决预算约束下的在线多特征分类问题
🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)
关键词: 主动特征获取 在线学习 组合优化 带背包问题 深度强化学习 特征选择 动态奖励 预算约束
📋 核心要点
- 现有在线AFA方法缺乏性能保证，且未能有效处理全局预算约束。
- 论文提出将在线AFA形式化为组合带背包问题，结合特征获取与预测，提供了理论保证。
- 实验结果表明，LP-Chain在合成数据上优于HEDGE基线和深度RL基线，并且在特征数量增加时表现良好。
📝 摘要（中文）
主动特征获取（AFA）是一种分类问题，代理在预测每个样本标签之前决定获取哪些昂贵特征。与批量AFA不同，在线AFA根据到达的样本标签更新预测器。现有在线方法要么使用深度强化学习（RL）而没有性能保证，要么最大化成本调整奖励而不是强制执行全局预算。我们将在线AFA形式化为一个组合带背包（BwK）问题，结合了特征获取和预测。与之前的基于带的AFA和经典BwK不同，我们的设置具有组合复杂性、动态奖励、全局预算和结构化侧信息。我们在此框架下获得了比标准BwK界限更好的遗憾上界，利用了基于基数的置信界和子集更新结构。为了避免指数级大的动作空间，我们提出了LP-Chain，一种搜索特征子集的成本感知链的变体，其大小随特征数量线性增长。尽管遗憾上界特定于组合框架，LP-Chain在经验上实现了可比的预测性能。
🔬 方法详解
问题定义：论文要解决的具体问题是在线特征获取中的预算约束与动态奖励问题。现有方法往往无法在保证性能的同时有效管理特征获取的成本。
核心思路：论文的核心解决思路是将在线AFA问题建模为组合带背包问题，通过结合特征获取和预测来优化决策过程。这样的设计使得在动态环境中能够有效利用已知信息。
技术框架：整体架构包括特征获取模块和预测模块，特征获取模块负责选择特征，而预测模块则基于获取的特征进行分类。通过引入基数感知的置信界和子集更新结构，提升了决策的准确性和效率。
关键创新：最重要的技术创新点在于提出了LP-Chain方法，能够在特征数量增加时有效搜索特征子集，避免了指数级的动作空间，从而提高了计算效率。
关键设计：在设计中，采用了基于成本的链式搜索策略，确保特征子集的选择能够在预算限制内进行，同时保持较高的预测性能。
🖼️ 关键图片
📊 实验亮点
实验结果显示，LP-Chain在合成数据集上相较于HEDGE基线和深度RL基线具有显著的性能提升，具体表现为在特征数量增加时，模型的预测准确率保持稳定，且计算效率显著提高。
🎯 应用场景
该研究的潜在应用领域包括医疗诊断、金融风险评估和智能制造等场景，能够在特征获取成本高昂的情况下，优化分类决策过程，提升系统的整体效率和准确性。未来可能对实时数据分析和决策支持系统产生深远影响。
📄 摘要（原文）
Active Feature Acquisition (AFA) is a classification problem in which an agent decides which costly features to acquire before predicting each sample's label. Unlike batch AFA, which trains a fixed policy and classifier offline on fully observed data, online AFA updates its predictor from revealed labels as samples arrive. Existing online methods either use deep reinforcement learning (RL) without performance guarantees or maximize cost-adjusted reward rather than enforce a global budget. We formulate online AFA as a combinatorial Bandits with Knapsacks (BwK) problem that couples acquisition and prediction. Unlike prior bandit-based AFA and classical BwK, our setting has combinatorial complexity, evolving rewards, a global budget, and structured side information. We obtain an improved regret upper bound over standard BwK bounds in this framework, leveraging a cardinality-aware confidence bound and the subset update structure. To avoid an exponentially large action space, we propose \emph{LP-Chain}, a variant that searches a cost-aware chain of feature subsets with a size that grows linearly with the number of features. While the regret upper bound is specific to the combinatorial framework, \emph{LP-Chain} empirically achieves comparable predictive performance. On synthetic data, \emph{LP-Chain} outperforms HEDGE-based BwK and deep RL-based online AFA baselines and scales favorably to more features.