AFA-BANDIT: Provably Near-Optimal Online Multi-Feature Classification Under Budget Constraints
The authors reformulate online Active Feature Acquisition (AFA) as a combinatorial Bandits with Knapsacks (BwK) problem to find a better regret bound than standard BwK methods. They propose LP-Chain, a cost-aware chain of feature subsets that achieves similar performance while drastically reducing the exponential complexity of finding the optimal subset selection.