AFA-Bandit casts online active feature acquisition as a combinatorial bandits-with-knapsacks problem, and LP-Chain beats HEDGE-based BwK and a deep RL baseline on synthetic data with linear-size chain search

Online AFA is formulated as a predictor-coupled combinatorial BwK problem in which each feasible feature subset is an arm with a cost, rewards evolve as the predictor updates, and acquisitions are subject to a global budget. Prior bandit-based AFA either subtracts acquisition cost from reward without enforcing a global budget or focuses on minimizing acquisition cost, while classical BwK lacks combinatorial structure, evolving rewards, and structured feedback. This formulation couples acquisition and prediction within one budget-constrained framework. The problem definition and the linear-program relaxation benchmark (Eq. 5) appear in Section 2, where the relaxation is described as a tractable upper bound on the dynamic oracle, so regret is bounded against the LP relaxation.

Within this combinatorial framework, the authors establish a regret upper bound tighter than a direct application of the classical BwK bound, with an improvement factor of order, arising from the cardinality-aware confidence bound and the subset update structure. The proof uses the extra feedback that every subset of the acquired set can be evaluated, reducing the error term to the maximum independent set size of a reversed graded partially ordered set, bounded via Sperner's theorem and Stirling's approximation, with a class-count factor from Cauchy-Schwarz. Theorem 1 and its proof sketch are in Section 4, with full derivation in Appendix B; the analysis rests on Assumption A (bounded observations, reward, and costs; expected reward Lipschitz smooth in the parameter). The authors state the bound applies only to the combinatorial setting, not to LP-Chain.

LP-Chain is proposed: each round greedily builds a cost-aware feature chain that adds one feature per step using optimistic rewards, then solves a linear program over candidate actions under the per-round allowance of the remaining budget and samples from it, with chain size growing linearly in the number of features. Direct optimization over the full power set scales exponentially with the number of features; LP-Chain considers only nested actions and enforces the budget directly through the per-round allowance rather than via OMD dual updates. The method is given in Section 3.2.2 (Eqs. 15-19); the ablation in Table 1 shows the prediction-error discrepancy between the chain restriction and full subset search grows with the number of features but remains small (MSE from 0.00005 to 0.00318), and at 20 features LP-Chain takes about 2,461.93 s versus about 5,397.70 s for the combinatorial version.

On synthetic Gaussian-mixture data, LP-Chain attains lower average prediction error than both the HEDGE-based BwK policy and the deep RL online AFA baseline OL at every budget fraction, and its gap to the lower bound narrows as the budget increases. Prior online AFA methods either lack performance guarantees or were not directly compared against a BwK-style policy under a global budget; this experiment compares chain-based selection, full-action resource-weighted selection, and a neural acquisition-prediction method under the same global acquisition budget. Section 5 reports synthetic results with samples arriving as a single online stream and results averaged over 50 independent trials; Appendix A.4 reports that LP-Chain achieves the highest or approximately equal performance on CKD, BankMarketing, PhysioNet, MNIST, and FashionMNIST, while OL has higher online training accuracy on Diabetes, and the authors note these curves report online training performance and do not establish the same ordering on held-out test data.

The result targets an online multiclass setting: each round draws a sample from a parametric mixture distribution, feature costs are known, a set of features is available at no cost, acquisitions are subject to a global budget, and the true label is revealed after prediction. In this setting the combinatorial algorithm obtains a regret bound against the LP relaxation, and LP-Chain offers a linear-size practical alternative, suited to readers who must trade acquisition against prediction on streaming data, for example tabular or image feature classification tasks with quantifiable costs. The authors state they will extend the method to bandit-label settings, where only a correct/incorrect outcome is returned instead of the true label, using unbiased risk estimators from weakly supervised learning to update prediction parameters.

The regret upper bound applies only to the combinatorial setting, and the regret analysis for LP-Chain is left by the authors for future work, so the practical variant currently rests on empirical evidence. The real-data results report online training performance, and the authors state these curves do not establish the same ordering on held-out test data; on Diabetes, OL achieves higher online training accuracy, which the authors partly attribute to its class-balanced stream and replay-based updates, noting LP-Chain does not use the same stream and that adapting to imbalanced data is left for future work. In addition, the synthetic experiments use Gaussian-mixture generated data, and the authors emphasize the Gaussian model only generates the data and is not assumed by the formulation, method, or analysis.