arXiv preprint ·
AFA-BANDIT: Provably Near-Optimal Online Multi-Feature Classification Under Budget Constraints
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Machine Learning
SkillFormer: Skill-Decomposed Adaptation for Audio Language Models
The Winner's Curse in LLM Self-Improvement Loops: Selection Noise, Lock-in, and Acceptance Rules
Preserving Unstable Modes Through Inverse Dynamics in JEPA World Models
Beyond Nominal Equilibria: Risk-Averse Multi-Population Mean-Field Games
Foundation Model-Aided Multi-Agent Reinforcement Learning for Wireless Random Access Network Optimization
Get the few papers worth your time in Machine Learning every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.