# AFA-BANDIT: Provably Near-Optimal Online Multi-Feature Classification Under Budget Constraints

arXiv: https://arxiv.org/abs/2610.07615 · HTML: https://mlsanity.com/paper/2610.07615/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Deep RL algorithms and representations, one of 15 directions in Deep reinforcement learning methods.
- Builds on 7 of its 32 references that are in the map.
- First posted on arXiv 6 Oct 2026.

## Placed in

- Deep reinforcement learning methods / [Deep RL algorithms and representations](https://mlsanity.com/deeprl/deep-rl-algorithms-and-representations/)

## Builds on (most cited first, 7 of 7)

- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Opportunistic Learning: Budgeted Cost-Sensitive Learning from Data Streams](https://mlsanity.com/paper/1901.00243/) (2019)
- [Acquisition Conditioned Oracle for Nongreedy Active Feature Acquisition](https://mlsanity.com/paper/2302.13960/) (2023)
- [AFABench: A Generic Framework for Benchmarking Active Feature Acquisition](https://mlsanity.com/paper/2508.14734/) (2025)
- [Towards Robust Active Feature Acquisition](https://mlsanity.com/paper/2107.04163/) (2021)
- [Cost-Efficient Online Decision Making: A Combinatorial Multi-Armed Bandit Approach](https://mlsanity.com/paper/2308.10699/) (2023)

## Abstract (arXiv)

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 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, LP-Chain empirically achieves comparable predictive performance. On synthetic data, LP-Chain outperforms HEDGE-based BwK and deep RL-based online AFA baselines and scales favorably to more features.