When Does Synergy Help Active Feature Acquisition? A PID-Based Study

Jie Li; Maruf A. Dhali; Hjalmar R. Bouma

cs.LGSep 26, 2026

When Does Synergy Help Active Feature Acquisition? A PID-Based Study

Authors: Jie Li, Maruf A. Dhali, Hjalmar R. Bouma

Organizations: Acutelines Data Science Group University Medical Center Groningen University of Groningen Groningen, The Netherlands · Department of Artificial Intelligence University of Groningen Groningen, The Netherlands

Abstract

Active feature acquisition (AFA) sequentially selects informative features under budget constraints. However, existing policies rarely distinguish whether information contributed by interacting features is redundant, unique, or synergistic. We introduce SynAFA, a state-dependent AFA policy that combines pairwise joint information and conditional information, with Partial Information Decomposition (PID) characterizing its information structure. Across five tabular datasets and MNIST-loop, performance is heterogeneous. SynAFA shows its strongest gains at low budgets on PhysioNet, where synergistic and redundant feature pairs are supported by permutation tests, but its advantage diminishes as budgets increase and does not depend on pair proposals. SynAFA performs significantly worse than nearly all baselines on MiniBooNE, and than CAE on MNIST-loop. Controlled synthetic experiments further show that, within budget, SynAFA's advantage rises as joint information becomes more synergy-dominated, including when total joint information is held approximately constant. Further analyses show that the budget-dependent erosion is not resolved by non-greedy local search, which improves a diagnostic set-level objective but leaves predictive performance no better, often significantly worse, and that improvements in this objective are weakly aligned with the fixed classifier's predictive utility. These findings characterize when pairwise synergy can benefit AFA while exposing a persistent challenge in translating local information into effective acquisition objectives.

Figures & tables

	Budgets	vs. AACO		vs. CAE
Dataset	low/high	Low	High	Low	High
CKD	2/7	$-0.050^{*}$	$+0.000$	$+0.038$	$+0.025$
ACTG175	3/10	$-0.023$	$-0.009$	$+0.016$	$+0.009$
BankMarketing	2/7	$+0.034^{*}$	$-0.068^{*}$	$+0.000$	$-0.045^{*}$
PhysioNet	5/15	$+0.011$	$-0.038^{*}$	$+0.037^{*}$	$-0.005$
MiniBooNE	5/15	$-0.034^{*}$	$-0.033^{*}$	$-0.025^{*}$	$-0.044^{*}$

Table 1: Results of the tabular benchmark: accuracy differences at the lowest and highest tested budgets, against the adaptive AACO and static CAE. Positive values favor SynAFA.

{}^{*}p<0.05

without multiplicity correction. Endpoints summarize scope, not monotonicity, and all intermediate budgets are in Table A2 . CKD (

n=80

) stars are bootstrap-based and are not significant under an exact sign test (Table A13 ). Small CKD and ACTG175 test sets (

n=80

and

429

) limit precision, non-significant differences thus do not establish equivalence.

Budget	Mean $\Delta\mathrm{Acc}$	Wins	Ties	Losses
5	$+0.026$	6	2	0
10	$+0.005$	2	5	1
15	$-0.011$	1	5	2

Table 2: PhysioNet: mean accuracy difference against eight baselines and counts of significant wins/ties/losses at each budget (

n=2{,}400

). Ties denote non-significant differences, not equivalence. Tests are unadjusted across comparisons. Full effects are in Table A3 .

Figure 2: Controlled synergy sweeps. (a) Mean SynAFA advantage by budget (five dataset instances; band: $\pm 1$ SD across instances); the designated pair costs 6, exceeding budgets 3 and 5 but fitting budget 8. (b) Individual baseline comparisons at budget 8, pooled over instances (95% paired-bootstrap intervals). (c) Fixed- $V$ control: advantage versus realized synergy fraction with joint information approximately constant. Full results and calibration are in Appendix A.7 .

Budget	Deployed	Feasibility-masked
3	$-0.051$	$+0.064$
5	$-0.057$	$+0.063$
8	$+0.077$	$+0.077$

Table 3: Feasibility diagnostic at pure XOR (

\alpha=1

): mean accuracy advantage over AACO, CAE, and permutation, averaged over five dataset instances. Masking restores positive relative performance when the pair is unaffordable (budgets 3 and 5: the mean advantage is negative before and positive after masking in all five dataset instances). Budget 8 is unchanged.

Baseline	Budget 5	Budget 10	Budget 20
AACO	$+0.127^{*}$	$+0.149^{*}$	$+0.070^{*}$
CAE	$-0.023^{*}$	$-0.034^{*}$	$-0.070^{*}$
Permutation	$+0.020^{*}$	$+0.001$	$-0.018^{*}$

Table 4: MNIST-loop: accuracy(SynAFA v2)

-

accuracy(baseline), evaluated with the shared classifier (

n=12{,}000

). ∗ denotes an unadjusted paired-bootstrap

p<0.05

Dataset	Budget	$\Delta\mathrm{Acc}$	Mean $\Delta U$	$\rho(\Delta T,\Delta U)$
MNIST-loop	5	$-0.0025$	$+0.0014$	$+0.073$
MNIST-loop	10	$-0.0213^{*}$	$+0.0007$	$+0.107$
MNIST-loop	20	$-0.0322^{*}$	$-0.0024$	$+0.044$
PhysioNet	5	$-0.0371^{*}$	$-0.0116$	$-0.010$
PhysioNet	10	$-0.0150^{*}$	$-0.0022$	$-0.068$
PhysioNet	15	$-0.0042$	$+0.0004$	$-0.048$

Table 5: Non-greedy revision under the diagnostic objective, full test sets. Accuracy changes compare revised and original sets; mean utility changes and correlations use accepted swaps. These point estimates summarize Tables A20 and A21 ; ∗ denotes unadjusted

p<0.05

for accuracy.

Appendix figures & tables30 assets

Supplementary material from the paper’s appendix.

Appendix

Figure A1: Real examples from the MNIST-loop binary relabeling used for $D=784$ experiments.

Figure A2: (a) Schematic: two features $X_{a},X_{b}$ jointly informing target $Y$ , decomposed into redundant ( $R$ ), unique ( $U_{a}$ , $U_{b}$ ), and synergistic ( $\mathrm{Syn}$ ) information. (b) The decomposition applied to a real PhysioNet pair, PaO 2 /FiO 2 : this particular pair happens to have $R\approx U_{b}\approx 0$ (PaO 2 dominates FiO 2 ’s unique contribution almost entirely), with a non-zero synergistic component in addition to the dominant unique contribution from PaO 2 .

Figure A3: A recurring budget-dependent erosion pattern across two benchmark settings (§ 6.1 ): SynAFA’s relative performance is strongest at low budgets and diminishes as budget grows. Greedy, one-step-ahead construction is a natural candidate explanation for this pattern, tested directly in § 6.2 . (a) PhysioNet, SynAFA vs. each of 8 baselines (gray) and the mean $\pm$ SEM (red). (b) MNIST-loop, SynAFA v2’s accuracy gap to CAE before and after the precomputation sampling correction (§ 6 ).

DATASET	DOMAIN	TASK (TARGET $Y$ )	$D$	$n$	MAJORITY
CKD	clinical (nephrology)	chronic kidney disease present vs. absent	24	80	0.600
ACTG175	clinical (HIV/AIDS trial)	treatment-failure / disease-progression indicator	23	429	0.730
BankMarketing	marketing / finance	client subscribed to a term deposit vs. not, following a phone campaign	16	9,043	0.884
PhysioNet	clinical (ICU / critical care)	in-hospital mortality of ICU patients ( Silva et al., 2012 )	41	2,400	0.862
MiniBooNE	particle physics	electron-neutrino signal vs. muon-neutrino background event	50	26,014	0.717
MNIST-loop	vision (relabeled MNIST)	digit contains a topological loop (0,6,8,9) vs. not (1,2,3,4,5,7) ( LeCun et al., 1998 )	784	12,000	0.604

Appendix

Table A1: Datasets and hard-budget test-set sizes. CKD, ACTG175, BankMarketing and MiniBooNE use the UCI dataset variants described by the benchmark. MNIST-loop is a binary relabeling. The purpose-built synthetic dataset is described in § 5.2 . The last column is the share of the more frequent class in the test set. The external classifier is trained with class-weighted cross-entropy (Appendix A.9 ) and predicts from partially observed features, so reported accuracies can lie below this rate: they do for every evaluated method at every tested hard budget on PhysioNet and BankMarketing, which is why only paired differences between policies are interpreted.

DATASET	BUDGET	VS. AACO	VS. CAE
CKD	2	$-0.050^{*}$	$+0.038$ (n.s.)
CKD	4	$+0.000$ (n.s.)	$+0.075^{*}$
CKD	7	$+0.000$ (n.s.)	$+0.025$ (n.s.)
ACTG175	3	$-0.023$ (n.s.)	$+0.016$ (n.s.)
ACTG175	5	$-0.021$ (n.s.)	$-0.005$ (n.s.)
ACTG175	10	$-0.009$ (n.s.)	$+0.009$ (n.s.)

Appendix

Table A2: SynAFA versus AACO and CAE: accuracy differences under the shared classifier and matched hard budgets.

{}^{*}p<0.05

; unmarked values are not significant. Additional reported comparisons follow below. CKD (

n=80

) stars are bootstrap-based and are not significant under an exact sign test (Table A13 ).

BASELINE	BUDGET 5	BUDGET 10	BUDGET 15
AACO	$+0.011$	$-0.034^{*}$	$-0.038^{*}$
Permutation	$+0.042^{*}$	$+0.007$	$-0.014$
CAE	$+0.037^{*}$	$-0.009$	$-0.005$
GDFS	$+0.025^{*}$	$+0.014$	$-0.051^{*}$
DIME	$+0.017^{*}$	$+0.007$	$-0.000$
JAFA	$+0.010$	$+0.007$	$+0.018^{*}$

Appendix

Table A3: PhysioNet accuracy(SynAFA)

-

accuracy(baseline),

n=2{,}400

, matched hard budgets and the shared classifier.

{}^{*}p<0.05

, unadjusted.

$\alpha$	BUDGET 3	BUDGET 5	BUDGET 8
0.00	$+0.060$ (0.036)	$+0.027$ (0.011)	$+0.007$ (0.006)
0.25	$+0.038$ (0.024)	$+0.010$ (0.010)	$+0.030$ (0.006)
0.50	$+0.014$ (0.017)	$-0.000$ (0.018)	$+0.028$ (0.012)
0.75	$-0.045$ (0.020)	$-0.059$ (0.011)	$+0.045$ (0.006)
1.00	$-0.051$ (0.022)	$-0.057$ (0.011)	$+0.077$ (0.016)
$\mathrm{corr}(\alpha,\ \mathrm{mean}\ \Delta)$	$-0.974$	$-0.945$	$+0.946$

Appendix

Table A4: Deployed synthetic sweep: mean accuracy advantage over CAE, AACO and permutation, averaged over five dataset instances (standard deviation across instances in parentheses;

D=24

n=6{,}000

test instances per instance). The designated pair costs 6, exceeding budgets 3 and 5. At budget 8, it is affordable in isolation; this does not guarantee completion along a trajectory. The last row correlates

\alpha

with the five-instance mean; per-instance correlations range over budget 3:

[-0.99,-0.77]

; budget 5:

[-0.99,-0.87]

; budget 8:

[+0.79,+0.97]

. Full effects appear in Table A8 .

	BUDGET 3		BUDGET 5
$\alpha$	DEPLOYED	MASKED	DEPLOYED	MASKED
0.00	$+0.060$	$+0.058$	$+0.027$	$+0.027$
0.25	$+0.038$	$+0.033$	$+0.010$	$+0.010$
0.50	$+0.014$	$+0.048$	$-0.000$	$+0.040$
0.75	$-0.045$	$+0.065$	$-0.059$	$+0.058$
1.00	$-0.051$	$+0.064$	$-0.057$	$+0.063$

Appendix

Table A5: Feasibility diagnostic: mean advantage (five dataset instances) under deployed and masked pair proposals. Masking recovers positive mean effects at high

\alpha

; it does not make advantage monotonic in

\alpha

. Budget 8 is essentially unchanged (identical in 22 of 25 instance-by-

\alpha

cells) and is omitted. This variant is used only for the mechanism diagnostic.

$\alpha$	$R$	$\mathrm{Syn}$	$V=R+U_{a}+U_{b}+\mathrm{Syn}$	$\mathrm{Syn}/V$
0.00	$0.0471$	$0.0505$	$0.0976$	$0.518$
0.25	$0.0275$	$0.0414$	$0.0689$	$0.601$
0.50	$0.0117$	$0.0637$	$0.0754$	$0.845$
0.75	$0.0025$	$0.1174$	$0.1199$	$0.979$
1.00	$0.0000$	$0.1951$	$0.1951$	$1.000$

Appendix

Table A6: Population-level PID of S1/S2, computed by marginalizing the

2^{22}

background configurations. Symmetry gives equal source-specific information and hence

U_{a}=U_{b}=0

under

I_{\min}

. Additive outcome logits at

\alpha=0

do not imply zero PID synergy. The synergy fraction increases even though absolute synergy and joint information are non-monotonic.

$\alpha$	BUDGET	$P(S1)$	$P(S2)$	$P(\text{BOTH})$
0.00	3	100.0%	0.0%	0.0%
0.00	5	100.0%	0.0%	0.0%
0.00	8	100.0%	29.9%	29.9%
0.25	3	100.0%	0.0%	0.0%
0.25	5	100.0%	0.0%	0.0%
0.25	8	100.0%	50.3%	50.3%

Appendix

Table A7: Acquisition rates for S1/S2, mean over five dataset instances (

n=6{,}000

per instance and row).

P(\mathrm{both})

is 100% in every dataset instance at budget 8 for

\alpha\geq 0.75

but instance-dependent at

\alpha=0

(

0\%

50\%

100\%

0\%

0\%

). At budget 3 and

\alpha=1

, S1 is abandoned in four of five instances; at budget 5 and

\alpha=1

, S2 alone consumes the entire budget in four of five.

$\alpha$	BASELINE	BUDGET 3	BUDGET 5	BUDGET 8
0.00	CAE	$+0.0273^{*}$	$+0.0102^{*}$	$-0.0011$
	AACO	$+0.0534^{*}$	$+0.0322^{*}$	$+0.0194^{*}$
	Permutation	$+0.1000^{*}$	$+0.0391^{*}$	$+0.0041$
0.25	CAE	$+0.0182^{*}$	$-0.0038$	$+0.0234^{*}$
	AACO	$+0.0054$	$-0.0054$	$+0.0429^{*}$
	Permutation	$+0.0903^{*}$	$+0.0392^{*}$	$+0.0231^{*}$

Appendix

Table A8: Deployed synthetic sweep: full accuracy differences against the three baselines, pooled over five dataset instances (30,000 paired test comparisons per cell; 10,000 bootstrap resamples).

{}^{*}p<0.05

(pooled, test-level; not a between-instance test).

$\alpha$	BASELINE	BUDGET 3 (MASKED)	BUDGET 5 (MASKED)
0.00	CAE	$+0.0254^{*}$	$+0.0096^{*}$
	AACO	$+0.0515^{*}$	$+0.0316^{*}$
	Permutation	$+0.0981^{*}$	$+0.0386^{*}$
0.25	CAE	$+0.0133^{*}$	$-0.0039$
	AACO	$+0.0005$	$-0.0054$
	Permutation	$+0.0854^{*}$	$+0.0392^{*}$

Appendix

Table A9: Masked synthetic sweep: accuracy differences with pair proposals restricted to those affordable within the remaining budget, pooled over five dataset instances (30,000 paired comparisons per cell; 10,000 bootstrap resamples).

{}^{*}p<0.05

(pooled, test-level).

TARGET $\mathrm{Syn}/V$	$w_{1}{=}w_{2}$	$w_{\mathrm{xor}}$	REALIZED $V$	REALIZED $\mathrm{Syn}/V$
0.52	0.70875	0.0629	0.1032	0.512
0.65	0.61239	0.5283	0.1003	0.644
0.78	0.49142	0.73411	0.1003	0.776
0.90	0.33509	0.87496	0.1011	0.896
1.00	0.00000	0.97202	0.1017	1.000

Appendix

Table A10: Fixed-

V

calibration. Population calibration uses a

6\times 10^{6}

-sample background draw with target

V=0.10

bits. Realized quantities are recomputed from generated training data pooled over five dataset instances (

n=90{,}000

each). Population symmetry implies

U_{a}=U_{b}=0

; finite-sample empirical estimates need not satisfy this exactly. Numerical small-effect checks approach

\mathrm{Syn}/V=0.5

; no general lower-bound theorem is asserted here.

Per-dataset correlation (synergy fraction vs. mean advantage): $0.51,\ 0.89,\ 0.78,\ 0.85,\ 0.93$
TARGET $\mathrm{Syn}/V$	VS. AACO	VS. CAE	VS. PERMUTATION	MEAN
0.52	$+0.0207^{*}$	$+0.0058^{*}$	$+0.0030$	$+0.0098$
0.65	$+0.0169^{*}$	$+0.0310^{*}$	$+0.0084^{*}$	$+0.0188$
0.78	$+0.0410^{*}$	$+0.0399^{*}$	$+0.0081^{*}$	$+0.0297$
0.90	$+0.0416^{*}$	$+0.0406^{*}$	$+0.0035^{*}$	$+0.0286$
1.00	$+0.0431^{*}$	$+0.0406^{*}$	$+0.0000$	$+0.0279$

Appendix

Table A11: Fixed-

V

control at budget 8: accuracy differences pooled over five independently generated dataset instances, each with its own trained policies and a classifier shared across instances (trained once, on instance 0) (

n=30{,}000

paired test comparisons per row; 10,000 bootstrap resamples).

{}^{*}p<0.05

describes pooled test-level uncertainty, not between-repetition significance. Instance-level trend correlations are 0.51, 0.89, 0.78, 0.85, and 0.93; all five endpoint changes are positive.

BASELINE	BUDGET 5	BUDGET 10	BUDGET 15
AACO	$-0.034^{*}$	$-0.053^{*}$	$-0.033^{*}$
Permutation	$-0.038^{*}$	$-0.047^{*}$	$-0.049^{*}$
CAE	$-0.025^{*}$	$-0.051^{*}$	$-0.044^{*}$
GDFS	$-0.032^{*}$	$-0.040^{*}$	$-0.038^{*}$
DIME	$-0.032^{*}$	$-0.038^{*}$	$-0.046^{*}$
JAFA	$-0.028^{*}$	$-0.038^{*}$	$-0.025^{*}$

Appendix

Table A12: MiniBooNE: accuracy differences (

n=26{,}014

). There are 22 significant losses, one significant win, and one non-significant comparison;

{}^{*}p<0.05

. OL-with-mask at budget 5 has

p=0.13

DATASET	BASELINE	BUDGET (LOW)	BUDGET (MID)	BUDGET (HIGH)
CKD (n=80)	AACO	$-0.050^{*}$	tie	tie
CKD	CAE	tie	$+0.075^{*}$	tie
CKD	Permutation	$+0.075^{*}$	tie	tie
CKD	EDDI	tie	tie	tie
CKD	ODIN	tie	tie	tie
ACTG175 (n=429)	AACO	tie	tie	tie

Appendix

Table A13: Reported CKD/ACTG175 summaries (

n=80

and 429). Low/mid/high budgets are 2/4/7 for CKD and 3/5/10 for ACTG175. “Tie” denotes a non-significant reported comparison; it does not imply zero effect or equivalence. This is a partial summary, not a complete eight-baseline matrix.

{}^{*}p<0.05

. For CKD (

n=80

), the three starred cells (AACO at budget 2, CAE at budget 4, permutation at budget 2) have bootstrap

p\approx 0.03

but rest on only 4, 8 and 8 discordant test instances (0 vs. 4 against SynAFA, 7 vs. 1 and 7 vs. 1 in its favor); an exact sign test on these pairs gives

p=0.125

0.070

and

0.070

, so these three stars should be read as suggestive only. All starred ACTG175 cells remain significant under the exact test (

p\leq 0.009

for DIME and JAFA,

p=0.0003

for ODIN). EDDI denotes the external-classifier variant and ODIN the model-based variant; the built-in-classifier EDDI and model-free ODIN variants, run in the same pipeline, are significantly worse than SynAFA on ACTG175 (EDDI built-in at all three budgets, ODIN model-free at budget 10) and are omitted here.

BASELINE	BUDGET 2	BUDGET 4	BUDGET 7
AACO	$+0.034^{*}$	$-0.017^{*}$	$-0.068^{*}$
CAE	tie	$+0.015^{*}$	$-0.045^{*}$
Permutation	tie	$+0.047^{*}$	$-0.046^{*}$

Appendix

Table A14: Reported BankMarketing comparisons (

n=9{,}043

). At budget 2, SynAFA, CAE and permutation select the same two features for all instances. “Tie” denotes the reported tie;

{}^{*}p<0.05

Hypothesis	Reported diagnostic
Higher-order interaction	MiniBooNE’s absolute three-way synergy (“Synergy3”) is second highest of five datasets (mean 0.014 bits; CKD 0.027) and mid-range relative to joint information; CKD is higher without significant losses ( $n=80$ , low power). This does not test all higher orders.
Binarization loss	The reported retained-information fraction is 59.5% (second lowest of five datasets), versus 40.7% for PhysioNet, which performs better.
Training sample size	The AACO–SynAFA gap (budget 10) does not shrink as the training set grows in a subsampling sweep from $n=300$ (0.067) to 78,038 (0.044).

Appendix

Table A15: MiniBooNE alternative explanations. These diagnostics do not support the tested hypotheses as sufficient explanations; they do not rule out every higher-order or preprocessing effect.

BASELINE	BUDGET	ORIGINAL	POLICY-ALIGNED	CLOSED
AACO	5	$-0.0343^{*}$	$-0.0007$ (n.s.)	98%
CAE	5	$-0.0252^{*}$	$-0.0176^{*}$	30%
Permutation	5	$-0.0381^{*}$	$-0.0200^{*}$	47%
AACO	10	$-0.0525^{*}$	$-0.0222^{*}$	58%
CAE	10	$-0.0506^{*}$	$-0.0296^{*}$	41%
Permutation	10	$-0.0469^{*}$	$-0.0305^{*}$	35%

Appendix

Table A16: MiniBooNE classifier realignment: acquisition trajectories are fixed while the external classifier is retrained using 96,000 policy masks from training-split rollouts. Entries are SynAFA minus baseline accuracy (

n=26{,}014

). Closed is the percentage reduction in absolute gap, averaged over the nine rows for the final mean.

{}^{*}p<0.05

CONFIGURATION	ACCURACY	GAP TO EXACT	FIT TIME
Exact pairwise information	0.7632	–	–
Amortized, k_infer=150 (original)	0.7505	$+0.0128^{*}$ ( $p=0.02$ )	25.6s
Amortized, k_infer=1000	0.7538	$+0.0095$ ( $p=0.08$ )	24.3s
Amortized, k_infer=36,000 (full)	0.7628	$+0.0005$ ( $p=0.91$ )	24.8s

Appendix

Table A17: Reduced

D=90

control, adaptive acquisition without local search (

n=4{,}000

). Gaps reproduce the reported exact-minus-amortized differences and may differ from subtraction of rounded accuracies. Fit times do not establish total end-to-end precomputation cost.

p

-values come from a paired bootstrap over test instances with 5,000 resamples.

CONFIGURATION	BUDGET 5	BUDGET 10	BUDGET 20
Original (k_infer=150)	0.695	0.786	0.814
k_infer=36,000, with-replacement sampling	0.719	0.770	0.811
k_infer=36,000, seed=1 (variance check)	0.752	0.754	0.800
k_infer=36,000, extended training $k$ -range (rejected)	0.735	0.765	0.790
k_infer=36,000, sampling corrected	0.748	0.776	0.805

Appendix

Table A18: MNIST-loop accuracy on the full 12,000-instance test set across amortized configurations. Increasing the precompute sample and correcting replacement sampling are separate changes.

	ADAPTIVE ACC.	REVISED ACC.	% CAE GAP CLOSED
Corrected search, $n=1000$ subsample	0.836	0.806	$-$ 73.2% (reversed)
Corrected search, full test set ( $n=12{,}000$ )	0.805	0.773	$-$ 46.3% (reversed)

Appendix

Table A19: MNIST-loop local-search diagnostic at

D=784

, budget 20, on the sampling-corrected amortized table ( k_infer =36,000). The first row uses a random subsample of

n=1000

test instances (the setting of the original diagnostic); the second uses the full 12,000-instance test set, whose adaptive accuracy matches Table A18 . Mean

T(S)

before/after search:

2.60\to 3.77

(

n=1000

) and

2.56\to 3.74

(full).

SETTING	BUDGET	$n$	$\Delta$ ACC.	95% CI	$p$
MNIST-loop (amortized, sampling-corrected)	5	12,000	$-0.0025$	[ $-0.0106$ , $+0.0054$ ]	0.547
MNIST-loop (amortized, sampling-corrected)	10	12,000	$-0.0213^{*}$	[ $-0.0288$ , $-0.0138$ ]	$<0.0001^{*}$
MNIST-loop (amortized, sampling-corrected)	20	12,000	$-0.0322^{*}$	[ $-0.0400$ , $-0.0244$ ]	$<0.0001^{*}$
PhysioNet (exact)	5	2,400	$-0.0371^{*}$	[ $-0.0512$ , $-0.0221$ ]	$<0.0001^{*}$
PhysioNet (exact)	10	2,400	$-0.0150^{*}$	[ $-0.0275$ , $-0.0025$ ]	$0.019^{*}$
PhysioNet (exact)	15	2,400	$-0.0042$	[ $-0.0158$ , $+0.0079$ ]	0.514

Appendix

Table A20: Single-swap revision (corrected local search under the diagnostic

T(S)

objective): revised minus adaptive accuracy, evaluated on the full test set of each dataset (MNIST-loop

n=12{,}000

, PhysioNet

n=2{,}400

, MiniBooNE

n=26{,}014

) with the shared external classifier;

\lambda

is each trained bundle’s own value (

0.001

for MNIST-loop,

0.01

otherwise) and every instance converged within 200 rounds. 95% CI and

p

come from a paired bootstrap over test instances (10,000 resamples;

p<0.0001

means no resample crossed zero). None of the nine settings shows a gain, and seven show significant losses; ∗ :

p<0.05

. Below the line, the reduced-dimensional exact control (exact PID on the 90 highest-variance pixels,

\lambda=0.001

, same test set and bootstrap) improves accuracy at budgets 5 and 20 but reduces it at budget 10.

Figure A4: A diagnostic test for whether amortized estimation error contributes to the reversal in this specific comparison (§ 6 ): the same single-swap local-search procedure, run against an amortized table ( $D=784$ , left/blue) vs. an exact-information table ( $D=90$ , right/red). Both conditions use the full 12,000-instance test set at budget 20. Dimensionality and estimator type change together between these two conditions, so this is diagnostic evidence for estimation error’s role, not a controlled isolation of it. (a) Accuracy before/after search. (b) In this comparison the search reverses direction depending on whether the underlying scores are exact or learned (budget 20 shown; with exact scoring the search also improves accuracy at budget 5, $+0.0767$ , but reduces it at budget 10, $-0.0125$ ), though § 6.3 ’s broader, nine-setting test finds that changes in the pairwise aggregation objective are weakly aligned with changes in predictive utility even under exact scoring, so this $D=90$ result should not be interpreted as evidence that the scoring framework is generally effective.

SETTING	BUDGET	$n$	#SWAPS	MEAN $\Delta U$	$P(\Delta U>0)$	$P(\Delta U_{\rm rand}>0)$	$\rho(\Delta T,\Delta U)$ [95% CI]
MNIST-loop	5	12,000	45,189	$+0.0014$	0.506	0.400	$+0.073$ [ $+0.063$ , $+0.082$ ]
MNIST-loop	10	12,000	79,544	$+0.0007$	0.520	0.426	$+0.107$ [ $+0.099$ , $+0.114$ ]
MNIST-loop	20	12,000	131,317	$-0.0024$	0.485	0.418	$+0.044$ [ $+0.038$ , $+0.050$ ]
PhysioNet	5	2,400	4,225	$-0.0116$	0.450	0.422	$-0.010$ [ $-0.040$ , $+0.019$ ]
PhysioNet	10	2,400	5,386	$-0.0022$	0.482	0.464	$-0.068$ [ $-0.094$ , $-0.042$ ]
PhysioNet	15	2,400	8,903	$+0.0004$	0.533	0.535	$-0.048$ [ $-0.072$ , $-0.024$ ]

Appendix

Table A21: Alignment between the diagnostic set-level objective

T(S)

and predictive utility, from the same full-test-set runs as Table A20 . Every accepted swap increases

T(S)

by construction.

\Delta U

is the change in the external classifier’s true-class probability for the swap chosen by

T(S)

; the random control keeps the same removal and draws a uniformly random replacement. #Swaps is the number of accepted swaps.

\rho

is Pearson’s correlation of

\Delta T

and

\Delta U

over accepted swaps, with 95% CIs from an instance-level cluster bootstrap (10,000 resamples; swaps from one instance are dependent).

|\rho|\leq 0.11

in the nine main settings; the last rows show the exact-scoring

D{=}90

control, whose correlation is largest (

+0.17

) at budget 5, where revision helps.

$\alpha$	Budget 3		Budget 5		Budget 8		Branch effect (B8)
	Deployed	Off	Deployed	Off	Deployed	Off	(Dep. $-$ Off acc.)
0.00	+0.060	+0.058	+0.027	+0.026	+0.007	+0.006	$+0.001$
0.25	+0.038	+0.033	+0.010	+0.005	+0.030	+0.030	$-0.000$
0.50	+0.014	+0.048	-0.000	+0.040	+0.028	+0.001	$+0.027^{*}$
0.75	-0.045	+0.065	-0.059	+0.058	+0.045	-0.005	$+0.051^{*}$
1.00	-0.051	+0.064	-0.057	+0.063	+0.077	-0.043	$+0.120^{*}$

Appendix

Table A22: Pair-branch ablation on the synthetic

\alpha

-sweep: mean accuracy advantage over CAE, AACO and permutation (five dataset instances) for the deployed policy and with the pair branch removed (Off). The last column is the paired accuracy difference Deployed

-

Off at budget 8, pooled over the 30,000 test comparisons (

{}^{*}p<0.05

, test-level, not a between-instance test). The last row is the correlation with

\alpha

Realized Syn/ $V$	Deployed	Off	Branch effect (Dep. $-$ Off acc.)
0.512	+0.0098	+0.0100	$-0.0002$
0.644	+0.0188	+0.0328	$-0.0140^{*}$
0.776	+0.0297	+0.0419	$-0.0122^{*}$
0.896	+0.0286	-0.0087	$+0.0373^{*}$
1.000	+0.0279	+0.0032	$+0.0246^{*}$
corr. with Syn/ $V$	+0.874	-0.395

Appendix

Table A23: Pair-branch ablation on the fixed-

V

sweep (budget 8, five dataset instances pooled): mean advantage over CAE, AACO and permutation, deployed versus pair branch removed, and the pooled paired accuracy difference (

{}^{*}p<0.05

, test-level).

Dataset	Budget	Acc. deployed	Acc. off	Dep. $-$ Off	W/T/L deployed	W/T/L off
CKD	2	0.9375	0.9875	$-0.0500$	2/5/1	4/4/0
	4	0.9875	0.9750	$+0.0125$	2/6/0	1/7/0
	7	0.9750	0.9750	$+0.0000$	0/8/0	0/8/0
ACTG175	3	0.8159	0.8159	$+0.0000$	0/7/1	0/7/1
	5	0.8205	0.8205	$+0.0000$	0/6/2	0/6/2
	10	0.8392	0.8392	$+0.0000$	0/8/0	0/8/0

Appendix

Table A24: Pair-branch ablation on the real datasets: test accuracy of deployed SynAFA and with the pair branch removed, their paired difference (

{}^{*}p<0.05

, unadjusted), and significant wins/ties/losses against the eight shared baselines (unadjusted

p<0.05

$\lambda$	BUDGET	SYNAFA ACC.	VS. CAE	VS. AACO	VS. PERMUTATION
0.001	5	$0.7477$	$-0.0235^{*}$	$+0.1273^{*}$	$+0.0202^{*}$
	10	$0.7762$	$-0.0344^{*}$	$+0.1491^{*}$	$+0.0007$
	20	$0.8047$	$-0.0695^{*}$	$+0.0704^{*}$	$-0.0182^{*}$
0.003	5	$0.7318$	$-0.0394^{*}$	$+0.1113^{*}$	$+0.0043$
	10	$0.7655$	$-0.0451^{*}$	$+0.1384^{*}$	$-0.0100^{*}$
	20	$0.8002$	$-0.0740^{*}$	$+0.0659^{*}$	$-0.0227^{*}$

Appendix

Table A25: MNIST-loop (SynAFA v2) sensitivity to the cost weight

\lambda

: same trained table, only

\lambda

changed; full 12,000-instance test set, shared external classifier, hard budgets 5/10/20. Accuracy of SynAFA and its difference to each baseline (accuracy(SynAFA)

-

accuracy(baseline)); ∗ : unadjusted paired-bootstrap

p<0.05

(10,000 resamples).

\lambda=0.001

is the value used in the main text and reproduces that run exactly.

Figure A5: The acquisition-cost weight $\lambda$ gates how much room PID-atom reweighting has to affect decisions (Appendix A.15 ). (a) Fraction of acquisition steps decided by the pairwise branch of the deployed decision rule (the only branch any reweighting of pair_value, including $Q_{\mathrm{PID}}$ , can affect), as a function of $\lambda$ ; each point is the mean over 3 hard budgets. (b) Mean $|\Delta\mathrm{acc}|$ between $Q_{\mathrm{PID}}$ and the original joint-MI table $V$ , over the same 3 presets and budgets. PhysioNet’s pair-value branch, and with it $Q_{\mathrm{PID}}$ ’s effect, is suppressed at a smaller $\lambda$ than MiniBooNE’s (usage reaches zero at $\lambda=0.03$ versus $0.1$ on this grid); both go to exactly zero once $\lambda$ is large enough that the pair-value branch never wins.

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 15, 2026

The Lagrangian Structure of Cost-Penalized Active Feature Acquisition

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.

Joseph Bingham

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

Active Feature Acquisition Constrained Optimization Cost-Sensitive Learning

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

Abstract

Active Feature Acquisition

Explore similar work

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

The Lagrangian Structure of Cost-Penalized Active Feature Acquisition

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