The Lagrangian Structure of Cost-Penalized Active Feature Acquisition

Joseph Bingham

cs.LGOct 15, 2026

The Lagrangian Structure of Cost-Penalized Active Feature Acquisition

Authors: Joseph Bingham

Organizations: Faculty of Computer Science Faculty of Biology Technion – Israel Institute of Technology Haifa 3200003, Israel

Abstract

Active Feature Acquisition (AFA) sequentially selects features to maximize predictive accuracy under an acquisition budget. A natural heuristic greedily maximizes Expected Information Gain minus a cost penalty, EIG(j|x_S)-lamc_j (EIG-Cost), but its theoretical guarantees are unclear. We provide an a-posteriori certificate decomposing the gap to the optimal hard-budget policy into a budget-slack term and a greedy-suboptimality term Del_lam. The certificate is computable when the penalized optimum is tractable; on small heterogeneous-cost instances, we verify it exactly, finding Del_lam near zero across 4,000 solved cases. On the large clinical task, Del_lam is not computable, so the decomposition is diagnostic rather than a numerical guarantee. Our analysis identifies EIG-Cost as one-step greedy optimization of the Lagrangian relaxation of expected-cost AFA, with lam as its dual multiplier. For equal costs, we prove Del_lam <= exp(-gamI(Y;X_[d])), where gam is the submodularity ratio, yielding a structural guarantee in the near-submodular regime. Supporting results establish an adaptive chain-rule identity showing that cumulative stepwise EIG optimizes transcript information, and prove that A -> I(Y;X_A) need not be submodular, even for jointly Gaussian variables. This rules out a direct Nemhauser-Wolsey-Fisher bound; naive Bayes restores submodularity. We also bound the randomization gap between hard-budget and expected-cost optima, analyze sensitivity to dual-multiplier error under local smoothness, and derive a conditional CVAE generator-shift bound given a bound on forward predictive KL. We treat this KL as a diagnostic quantity, not as a transform of training loss. Experiments cover synthetic Gaussian settings, AFA benchmarks, and clinical differential diagnosis on MIMIC-IV. On MIMIC-IV, EIG-Cost achieves macro-F1 0.180 +/- 0.012 at a $30 budget, using 6.6% of full-panel cost.

Figures & tables

Figure 1: EIG-Cost pipeline. Partial observations

(x_{\mathcal{S}},m_{\mathcal{S}})

are fed simultaneously to the MaskableClassifier

f_{\theta}

(computing the posterior

P(Y\mid x_{\mathcal{S}})

) and to the TabularMAE CVAE

g_{\psi}

(generating

K

Monte Carlo completions

\{\hat{x}^{(k)}\}

). The EIG Computation block evaluates Eq. ( 2 ); the CPT cost

c_{j}

is subtracted (scaled by

\lambda

) to yield the acquisition score. The highest-scoring panel is acquired and the loop repeats until budget exhaustion.

$\sigma$ (noise)	$k=1$	$k=3$	$k=5$
$0.1$ (high synergy)	$1.000$	$0.212$	$0.179$
$0.5$	$1.000$	$0.430$	$0.347$
$1.0$	$1.000$	$0.623$	$0.509$
$2.0$	$1.000$	$0.826$	$0.726$
$5.0$ (low synergy)	$1.000$	$0.963$	$0.930$

Table 1: Empirical submodularity ratio

\gamma_{f,k}

for the additive Gaussian model (

d=8

). Rows: noise level

\sigma

(small = high feature synergy). Columns: parameter

k

in Definition 15 . The

k{=}1

column is trivially

1.0

for any set function (numerator and denominator coincide when

|\mathcal{R}|=1

); the informative columns are

k{=}3

and

k{=}5

Figure 2: Empirical approximation ratio vs. theoretical bound (Corollary 31 ). Each point corresponds to one noise level

\sigma

(and hence one value of

\gamma

). All points lie strictly above the diagonal, confirming the bound is a valid lower guarantee across the full range of synergy levels. In every one of the twelve sweep points, the greedy policy matched the exhaustive-search optimum (

V/V^{*}=1.0

): an empirical observation specific to the additive Gaussian model with independent features and unit costs, where the closed-form conditional Gaussian distributions allow each greedy step to correctly account for feature complementarity. We make no claim that this holds for general distributions. The x-axis spread (bound ranging from

0.02

at high synergy to

0.63

at near-submodularity) shows the bound responds correctly to the distribution’s structure.

Figure 3:

\lambda

-calibration curve (

\rho=0.7

B=5

, unit costs). Greedy policy value

V(\pi^{\lambda})

(blue) as a function of cost penalty

\lambda

, with the optimal dual multiplier

\lambda^{*}

(gray dotted) and

V^{\mathrm{hard}}_{B}

(horizontal line). The value is a step function because the policy is discrete: it holds at

V^{\mathrm{hard}}_{B}

across a plateau of penalties, then drops as increasing

\lambda

prunes successively more panels. The plateau (value within

2\%

V^{\mathrm{hard}}_{B}

) spans

\lambda\in[0,0.157]

and contains

\lambda^{*}=0.147

, a half-width of

\approx 50\%

\lambda^{*}

, the empirical signature of dual sensitivity (Proposition 29 ): the dual certificate degrades quadratically in

\lambda-\lambda^{*}

and the greedy value, which the dual bounds via Remark 30 , is correspondingly flat near

\lambda^{*}

Figure 4: MC EIG estimation error vs.

K

(Proposition 36 ). Empirical

\varepsilon_{\mathrm{MC}}

(blue, mean

\pm

SD across 5 seeds, 500 patients) and the Hoeffding bound

O(1/\sqrt{K})

(orange dashed). All points lie below the bound, validating Proposition 36 . At

K=50

the empirical error is

0.017\pm 0.001

nats , negligible relative to typical EIG values of

0.1

–

0.5

nats in clinical AFA. The bound is conservative by approximately

40\times

(expected, as Hoeffding bounds worst-case variance). This experiment isolates

\varepsilon_{\mathrm{MC}}

; the total estimation error additionally includes

\varepsilon_{\mathrm{gen}}

from CVAE model bias (Proposition 37 ).

Figure 5: Penalized greedy gap

\Delta_{\lambda}

on heterogeneous-cost instances (

n=600

, costs up to

20\times

, exact

L(\lambda)

by exhaustive search). Empirical CDF of

\Delta_{\lambda}

for the difference-form rule

\mathrm{EIG}-\lambda c

(EIG-Cost) and the density form

\mathrm{EIG}/c

. The gap is exactly zero on

97.3\%

of instances and small on the remainder (median

0

99

th percentile

0.088

nats, maximum

0.160

nats); the two curves coincide.

Panel of Figure 6 — Figure 6: Certificate calibration on tractable instances. Left: actual hard-budget gap vs. the two-term certificate over $4{,}000$ instances; all points lie below the diagonal (validity), coloured by submodularity ratio $\gamma$ . Right: the certificate’s two components as a function of $\lambda$ on one instance. The greedy gap $\Delta_{\lambda}$ (red) stays near zero greedy is essentially penalized-optimal, so the certificate’s looseness is entirely the budget-slack term $\lambda(B-B^{\lambda})$ (blue), which grows as larger $\lambda$ makes the policy stop further below the budget. The certificate is tightest near budget matching (small $\lambda$ ), where slack vanishes.

Dataset	Budget	Method	Macro-F1 [95% CI]	Accuracy	Spend ($)
CKD (max $25)	$5	EIG-Cost	$\mathbf{0.903\,[0.865,\,0.941]}$	$0.905$	$3.17$
		Greedy-EIG	$0.903\,[0.871,\,0.935]$	$0.905$	$3.20$
		Random	$0.688\,[0.601,\,0.775]$	$0.728$	$4.00$
	$10	EIG-Cost	$\mathbf{0.961\,[0.950,\,0.972]}$	$0.963$	$8.65$
		Greedy-EIG	$0.961\,[0.944,\,0.978]$	$0.963$	$9.28$
		Random	$0.863\,[0.825,\,0.901]$	$0.868$	$9.19$

Table 2: Benchmark results: macro-F1 at selected budgets (5 seeds, mean with 95%

t

-confidence interval). “Spend” is the mean actual cost (EIG-Cost stops voluntarily when all remaining panels satisfy

\mathrm{EIG}(j)\leq\lambda c_{j}

). Uncertainty is reported as

95\%

t

-confidence intervals over five seeds; with only five seeds we rely on interval overlap rather than significance tests, since the smallest attainable two-sided Wilcoxon signed-rank

p

-value at

n=5

0.0625

. Best per dataset–budget in bold .

Figure 7: Accuracy–cost frontier on benchmark datasets (5 seeds, mean

\pm

SD). Left (CKD): EIG-Cost (red) and Greedy-EIG (blue) achieve near-identical accuracy at every cost point and lie above Random (gray) at low-to-moderate cost, where guidance matters most. Both curves plateau at

\approx\!0.965

around

10 actual spend and remain flat thereafter, while Random continues rising and closes much of the gap by the full

25 budget. The leftward shift of EIG-Cost relative to Greedy-EIG at the plateau confirms cost savings from voluntary stopping (

12.4 vs.

18.9 at budget

25). Right (PhysioNet): EIG-Cost’s curve rises steeply and saturates around

20 actual spend; Greedy-EIG reaches the same accuracy level at

\approx\!\

, a

75%

higher spend. Random rises slowly but, because it keeps spending to the full

74 budget while EIG-Cost has stopped, it overtakes EIG-Cost at the largest budgets (

0.671

vs.

0.625

F1 at

74; Table 2 ); the EIG-Cost advantage is a cost-efficiency one at low to moderate budget, not a dominance across the whole frontier. In both panels, the EIG-Cost saturation point corresponds to the voluntary-stopping condition of Proposition 39 (

\mathrm{EIG}(j)\leq\lambda c_{j}

for all remaining panels), and the plateau is consistent with the dual-sensitivity result (Proposition 29 ): the policy operates in the near-optimal flat region around

\lambda^{*}$ .

Figure 8: Performance on the 21-condition cohort. Macro-F1 (left) and top-1 accuracy (right) vs. cost budget. Shaded regions: mean

\pm

1 SD across five seeds. Methods with voluntary stop rates

>87\%

are excluded (see Figure 10 ).

\dagger

CAE and Permutation at $10 omitted due to evaluation-set mismatch.

Family	Method	Macro-F1	Accuracy	Cost ($)	Acq.	Vol. Stop
Ours	EIG-Cost	$\mathbf{0.180\pm 0.012}$	$\mathbf{0.265\pm 0.010}$	$27.07$	$8.4$	$0.00\%$
RL	AACO-NN	$0.169\pm 0.011$	$0.244\pm 0.009$	$24.28$	$7.8$	$0.00\%$
	AACO	$0.162\pm 0.009$	$0.233\pm 0.008$	$23.48$	$6.3$	$0.00\%$
	JAFA	$0.011\pm 0.001$	$0.079\pm 0.001$	$7.89$	$0.03$	$99.2\pm 0.6\%$
Info.- theoretic	CAE	$0.145\pm 0.005$	$0.231\pm 0.004$	$23.31$	$7.7$	$0.00\%$
	DIME	$0.027\pm 0.002$	$0.103\pm 0.002$	$0.89$	$0.44$	$96.9\pm 0.9\%$

Table 3: Results on the 21-condition MIMIC-IV full-availability cohort (

202{,}971

admissions) at budget

30. Mean

\pm

SD across 5 seeds. Best per metric in bold . Vol. stop: voluntary stop rate. This is the paper’s primary (oracle-availability) cohort; for the separate deployment-faithful

12$ -hour cohort see Table 6 .

Figure 9: Performance on the five-condition subset. Macro-F1 (left) and accuracy (right) vs. cost budget. Dotted horizontal line: 20% random baseline.

Family	Method	Macro-F1	Accuracy	Cost ($)	Acq.	Vol. Stop
Ours	EIG-Cost	$\mathbf{0.417\pm 0.018}$	$\mathbf{0.446\pm 0.014}$	$26.65$	$11.5$	$0.00\%$
RL	AACO	$0.386\pm 0.015$	$0.428\pm 0.013$	$23.71$	$10.0$	$0.00\%$
RL	AACO-NN	$0.368\pm 0.016$	$0.416\pm 0.013$	$23.93$	$10.5$	$0.00\%$
Info.- theoretic	CAE	$0.357\pm 0.012$	$0.410\pm 0.010$	$23.31$	$9.0$	$0.00\%$
Info.- theoretic	DIME	$0.067\pm 0.003$	$0.148\pm 0.003$	$0.90$	$0.4$	$96.9\pm 0.8\%$
Static	Permutation	$0.344\pm 0.013$	$0.391\pm 0.011$	$24.69$	$3.0$	$0.00\%$

Table 4: Results on the five-condition subset at budget

30. Mean

\pm$ SD across 5 seeds. Best per metric in bold .

Figure 10: Voluntary stop rates at budget

30 (21-condition cohort). Methods in the shaded region exhibit stop rates

>87.5%

, they predict using class priors without acquiring diagnostic information (baseline collapse; Corollary 41 ). The

87.5%

boundary is not a derived constant: it is the observed stop rate of the least-collapsed method in the collapsed group (ma2018), and simply separates the two clearly-separated clusters of methods. Error bars:

\pm 1$ SD across five seeds.

Figure 11: Cost–accuracy tradeoff at budget $30. Each bubble represents one method on the 21-condition cohort (left) or five-condition subset (right); the vertical axis is accuracy and the horizontal axis is mean acquisition cost. Bubble area is proportional to macro-F1. EIG-Cost (red) occupies the preferred upper-left region (high accuracy, low cost).

$k$	Mean $\gamma$	SD	Min $\gamma$	$n$ pairs
$1$	$1.001$	$0.008$	$0.971$	$200$
$3$	$0.995$	$0.043$	$0.705$	$200$
$5$	$0.984$	$0.067$	$0.662$	$200$
$10$	$0.969$	$0.081$	$0.676$	$200$

Table 5: Empirical submodularity ratio

\gamma_{f,k}

on MIMIC-IV test set (300 patients, 200 sampled

(L,R)

panel pairs,

K{=}50

MC samples per EIG estimate). The

k{=}1

column is trivially

1.0

for any set function by definition; the reported

1.001\pm 0.008

is the Monte Carlo estimate, whose small excess over

1.0

is estimation noise from the finite CVAE sample (

K{=}50

) used to compute each EIG, and confirms the estimator is approximately unbiased. Mean

\pm

SD over sampled pairs. “Min

\gamma

” is the smallest ratio among the sampled pairs ; because the true

\gamma_{f,k}

is a minimum over all admissible pairs, this sampled minimum is an upper bound on

\gamma_{f,k}

, not a certificate, the true worst case can only be smaller. We therefore read the table as an empirical distribution of local submodularity ratios, not as a global bound.

Method	Macro-F1 [95% CI]	Mean cost ($)
EIG-Cost	$\mathbf{0.188}\,[0.185,\,0.191]$	$17.28$
ma2018	$0.170\,[0.167,\,0.174]$	$22.12$
CAE	$0.151\,[0.148,\,0.154]$	$24.40$
DIME	$0.102\,[0.099,\,0.104]$	$25.73$

Table 6: Deployment-faithful

12

-hour cohort ( separate availability-constrained cohort of Bingham and Arussy (2026) :

64{,}766

admissions,

39{,}884

patients,

12

-hour decision cutoff, per-patient availability mask; budget

30, panel costing, 5 seeds, bootstrap

95%

CIs). This cohort is distinct from the paper’s primary

202{,}971$ -admission full-availability cohort (Table 3 ); the two sets of numbers are not comparable and are reported separately. Best macro-F1 in bold .

$\lambda$	Macro-F1	Accuracy	Cost ($)
$0$ (unconstrained EIG)	$0.183\pm 0.013$	$0.268\pm 0.010$	$30.00$
$0.005$ (EIG-Cost)	$0.180\pm 0.012$	$0.265\pm 0.010$	$27.07$

Table 7: Cost-penalty ablation on the 21-condition cohort at budget

30. Mean

\pm$ SD across 5 seeds.

$\lambda$	Macro-F1	Accuracy	Cost ($)	Mean #panels
$0$	$0.193\pm 0.003$	$0.211$	$28.48$	$3.7$
$0.001$	$0.195\pm 0.006$	$0.213$	$27.77$	$3.7$
$0.0025$	$0.189\pm 0.005$	$0.207$	$25.81$	$3.4$
$0.005$	$0.176\pm 0.004$	$0.196$	$20.32$	$2.6$
$0.01$	$0.128\pm 0.006$	$0.156$	$9.38$	$1.1$
$0.02$	$0.089\pm 0.004$	$0.122$	$2.85$	$0.3$

Table 8: Cost–accuracy frontier vs.

\lambda

(

2{,}000

-patient subsample, budget

30, 5 seeds, mean

\pm

SD). This subsample traces the frontier shape; absolute values are not comparable to the full-cohort Table 7 . At

\lambda\geq 0.05

the policy acquires nothing and returns the class-prior baseline (macro-F1

\approx 0.06$ ).

Policy	Macro-F1	Accuracy	Cost ($)
greedy-EIG (order only)	$0.194\pm 0.005$	$0.212\pm 0.005$	$29.05$
EIG-Cost (forced, no stop)	$0.190\pm 0.002$	$0.211\pm 0.004$	$28.52$
EIG-Cost (entropy stop)	$0.189\pm 0.005$	$0.210\pm 0.004$	$28.53$
EIG-Cost (score stop)	$0.176\pm 0.005$	$0.196\pm 0.007$	$20.31$
$\lambda{=}0$ (order only)	$0.196\pm 0.006$	$0.212\pm 0.005$	$28.48$

Table 9: Mechanism decomposition on a

2{,}000

-patient subsample (budget

30, 5 seeds, mean

\pm$ SD). All arms share panel ordering, patients, and seeds; absolute values are not comparable to Table 3 (subsample).

Figure 12: Mechanism decomposition in cost–accuracy space (same

2{,}000

-patient subsample, budget

30, 5 seeds; error bars

\pm 1

SD). The four full-budget policies cluster at high cost (

28–29); only the score-floor stopping rule moves the policy to low cost (

20.3), and it does so at a small macro-F1 cost. The dashed arrow marks the deployed entropy-floor vs. theoretically-characterized score-floor operating points:

8.2 more spend for

+0.011

macro-F1. Absolute values are subsample figures used only for the within-panel contrasts.

$K$	Macro-F1	Accuracy	Time/patient (s)
$5$	$0.180\pm 0.007$	$0.219\pm 0.003$	$2.95$
$10$	$0.165\pm 0.008$	$0.208\pm 0.009$	$2.99$
$25$	$0.180\pm 0.001$	$0.223\pm 0.003$	$2.54$
$50$	$0.177\pm 0.002$	$0.220\pm 0.003$	$2.45$

Table 10: MC samples ablation (

K

) on the 21-condition MIMIC-IV cohort at budget

30 (300-patient subsample, 5 seeds, mean

\pm

SD). Absolute accuracy here (

\approx 0.22

) is lower than the full-test-set result of Table 3 (

0.265

) because this ablation is computed on a 300-patient subsample chosen to keep the

-sweep tractable; the subsample is fixed across

so that relative comparison across

is valid even though absolute values are not directly comparable to the main table. Macro-F1 is flat across

: the

K=25

and

K=50

values (

0.180

and

0.177

) are within one standard deviation, and the

K=10

dip (

0.165

) is sampling noise within the inter-seed spread (see main text). We adopt

K=50

as a conservative default; it carries no measured time penalty at this scale (wall-clock is dominated by TensorFlow graph warm-up rather than by

), and

K=25$ would serve equally well if MC cost dominated.

Metric	Value
Macro-F1	$0.175\pm 0.005$
Accuracy	$0.195\pm 0.006$
Log-loss (nats)	$2.60\pm 0.02$
Brier score	$0.896\pm 0.003$
Expected calibration error	$0.026\pm 0.004$
Mean posterior entropy (nats)	$2.65\pm 0.004$

Table 11: Information and calibration metrics for EIG-Cost at budget

30 (21-condition full test set, 5 seeds, mean

\pm

SD). Log-loss and Brier are proper scoring rules; ECE is expected calibration error (15 bins). Empirical information gain is

H(Y)-\mathbb{E}[H(Y\mid x_{\mathcal{S}})]

with prior entropy

H(Y)=2.85$ nats.

Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

Problem setup
Symbol	Meaning
$Y\in\mathcal{Y}$	target label ( $21$ diagnostic conditions on MIMIC-IV)
$X=(X_{1},\dots,X_{d})$	candidate features
$G_{1},\dots,G_{m}$	acquisition panels (disjoint feature groups)
$c_{j}\geq 0$	cost of panel/feature $j$ (2026 Medicare CPT)
$B$	acquisition budget

Appendix

Table 12: Summary of notation.

Condition
Acute Kidney Injury	Endocarditis	Pneumonia
Anemia	GI Bleed	Pulmonary Embolism
Atrial Fibrillation	Heart Failure	Respiratory Failure
Cirrhosis	Hyponatremia	Rhabdomyolysis
COPD Exacerbation	Liver Failure	Sepsis
Diabetic Emergency	Meningitis	Stroke

Appendix

Table 13: 21 acute diagnostic conditions in the MIMIC-IV cohort.

Panel	Features (#)	Cost ($)
Vital Signs (pre-acquired)	5	0.00
Basic Metabolic Panel	7	3.17
Complete Blood Count (+ diff.)	8	6.51
Prothrombin Time / INR	2	7.77
Lactate	1	8.46
Troponin-I	1	10.30

Appendix

Table 14: Selected test panels with 2026 Medicare CPT costs (representative subset; full panel list in Appendix C ).

Family	Method	Min	Max	Mean $\pm$ SD
Ours	EIG-Cost	0.169	0.191	$0.180\pm 0.012$
RL	AACO-NN	0.158	0.179	$0.169\pm 0.011$
	AACO	0.153	0.171	$0.162\pm 0.009$
	JAFA	0.010	0.012	$0.011\pm 0.001$
Info.- theoretic	CAE	0.140	0.149	$0.145\pm 0.005$
	DIME	0.025	0.029	$0.027\pm 0.002$

Appendix

Table 15: Macro-F1 at budget

30 on the 21-condition cohort, summarised over 5 seeds (mean

\pm$ SD, with min and max across seeds). Collapsed methods show negligible inter-seed variance.

Active Feature Acquisition

Active Feature Acquisition studies how models can selectively obtain costly or missing inputs to improve predictions within limited budgets.

See all 19 papers

Aug 3, 2026

BRiG-AFA: Bellman Risk-to-Go Learning for Non-Myopic Active Feature Acquisition

Active feature acquisition (AFA) asks which unobserved feature to measure next for each test instance under a budget. Greedy rules are easy to train but can overlook context features whose value is realized only through later acquisitions, while reinforcement-learning and generative approaches introduce difficult optimization or conditional-density estimation. We introduce \method, a deployable, supervised alternative that learns a separate candidate-conditioned risk-to-go function for every remaining budget. Starting from the one-step terminal classification risk, the functions are fitted backward with Bellman targets; inference greedily minimizes the learned terminal risk using only observed values, the mask, candidate identity, and remaining budget. A controlled non-myopic benchmark shows the expected mechanism: at budgets two and three, \method improves accuracy over its one-step ablation by

4.84\pm2.17

and

4.39\pm1.10

percentage points (mean

\pm

standard error over five seeds). On Fashion-MNIST with 20 candidate pixels, it improves accuracy at every nontrivial reported budget on average, including

10.20\pm0.74

points at four acquisitions; its mean paired gain across budgets

\{2,4,8,12,16\}

3.50\pm0.37

points. A three-seed MiniBooNE study is mixed at small budgets but positive at 8 and 16 acquisitions, identifying a current boundary rather than supporting a universal claim. These results establish a reproducible mechanism-level case for direct Bellman risk regression and delimit the experiments still needed for state-of-the-art comparison.

Jiaorong Feng, Qian Li, Ying Li

Curtin Business School, Curtin University, Perth, Western Australia, Australia · †Present affiliation: Independent Researcher. · School of Electrical Engineering, Computing and Mathematical Sciences, Curtin University, Perth, Western Australia, Australia

Cost-Aware Inference Active Learning Active Feature Acquisition Classification

Ask PDF

Oct 6, 2026

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

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.

AbdAlRahman Odeh, Teng-Hui Huang, Hesham El Gamal

The University of Sydney School of Electrical and Computer Engineering Sydney 2006, NSW, Australia · The University of Sydney Faculty of Engineering Sydney 2006, NSW, Australia

Active Learning Active Feature Acquisition Combinatorial Multi-Armed Bandits

Ask PDF

Sep 26, 2026

Active Feature Acquisition With Incomplete Training Data

In many prediction tasks, acquiring all features can be a prohibitively expensive or outright impossible task. Further, in many cases a static subset of features may not be enough to solve the problem sufficiently across various instances. Active Feature Acquisition (AFA) addresses these problems by formalizing the trade-off between feature cost and predictive performance during sequential feature selection. However, prior AFA work largely assumes access to complete training data, an assumption that is often violated in practice. Here we study AFA with Incomplete Training Data (AFA-ITD), showing that under missing completely at random (MCAR) data, one-step acquisition values remain unchanged, whereas multi-step values can decrease. We analyze three approaches to learning from incomplete data: aliasing, filtering, and generative restoration. We show that filtering can require a number of training instances scaling exponentially with the dimension, whereas generative restoration scales exponentially with the acquisition budget. We empirically test our theory on a controlled experiment and across common AFA datasets and find that missingness mainly damages methods that exploit multi-step acquisitions and that generative restoration is able to recover lost performance in many experiments. Code is available at https://github.com/Linusaronsson/AFA-Benchmark/tree/missing-data.

Reza Rezvan, Valter Schütz, Han Wu +2

Department of Computer Science and Engineering Chalmers University of Technology & University of Gothenburg

Active Feature Acquisition Learning with Missing Data

Ask PDF

Abstract

Active Feature Acquisition

Explore similar work

BRiG-AFA: Bellman Risk-to-Go Learning for Non-Myopic Active Feature Acquisition

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

Active Feature Acquisition With Incomplete Training Data