Active Feature Acquisition With Incomplete Training Data

1 INTRODUCTION

• The paper formalizes AFA-ITD and characterizes the difference between its training and evaluation MDPs.AFA-ITD addresses the mismatch between incomplete training data and feature acquisition at evaluation.Source: §1 · pp. 1–2
• Under MCAR, incomplete training data can lower non-myopic action values even when one-step values remain unchanged.The paper characterizes this difference through the Bellman recursions.Source: §1 · p. 2
• The paper distinguishes aliasing, filtering, and generative restoration as approaches to learning from incomplete training data, and characterizes their data requirements.Source: §1 · p. 2
• Across a controlled study and eight AFA datasets, missingness mainly damages methods that exploit multi-step acquisitions, while generative restoration often recovers lost performance.The experiments compare six AFA baselines.Source: §1 · p. 2

Active Feature Acquisition

• AFA methods vary in planning horizon and in whether they model acquisition dynamics, with hybrid methods combining models and experience.Myopic methods plan one step ahead; non-myopic methods consider potential multi-step effects.Source: §2 · p. 2

AFA from Incomplete Training Data

• Prior AFA-ITD studies include restricted training actions, identifiability of a greedy objective, policy evaluation, and miss-MDPs, but the cited work had not formalized AFA-ITD and its Bellman effects.Source: §2 · p. 2

Generative Models in AFA

• Prior AFA work used generative models for conditional estimation, synthetic trajectories, and learning support; this paper frames generative modeling as a solution to incomplete training data.The passage notes that the benefit of generative modeling remained unclear in the literature.Source: §2 · p. 2

3.1 ACTIVE FEATURE ACQUISITION (AFA)

• AFA is framed as optimizing the trade-off between acquisition cost and expected predictive performance, using a hard-budget classification objective.Source: §3.1 · p. 3
• A policy maps the observed features and acquired-feature set to an unacquired feature, while a predictor maps the final observation to a label.The accumulated acquisition cost is the sum of the costs of acquired features.Source: §3.1 · p. 3
• The formulation assumes access to a well-trained predictor because learning the predictor is not the work’s objective.Source: §3.1 · p. 3

3.2 AFA AS A (PARTIALLY OBSERVABLE) MARKOV DECISION PROCESS

• AFA can be represented as a POMDP with latent instance and label, then reduced to an MDP on the acquired features and their indices.The transition describes the next state after acquiring a feature.Source: §3.2 · p. 3
• The Bellman recursions characterize state and action values across acquisition horizons; regret measures expected loss above that of the optimal policy.The value at horizon k allows at most k further acquisitions.Source: §3.2 · p. 3

3.3 MISSINGNESS MECHANISMS

• The formulation distinguishes MCAR, MAR, and MNAR by whether missingness depends on the instance, available features, or missing feature values.Source: §3.3 · p. 3

3.4 AFA WITH INCOMPLETE TRAINING DATA (AFA-ITD)

• With incomplete training data, a training instance’s missing features are excluded from its action space, whereas evaluation permits any unacquired feature within budget.Under MCAR, the missingness mask is independent of the instance, leaving the conditionals unchanged in the training recursions; evaluation Bellman equations remain as defined for the complete-feature setting.Source: §3.4 · p. 4

4.1 HOW THE (ACTION-)VALUE FUNCTIONS ARE AFFECTED BY INCOMPLETE TRAINING DATA

• Under MCAR, one-step optimal values are unchanged, but multi-step values can differ between training and evaluation when the training action space is restricted.The proposition allows equality at k = 1 while showing that values can be lower for longer horizons.Source: Figure 1 · p. 4, §4.1 · p. 5
• In the shortcut example, missing branch features can make acquiring context feature x1 worse than the shortcut, despite x1 being optimal for evaluation.The complete-data optimal policy acquires x1 and its branch, reaching accuracy 1 at cost b; the shortcut reaches accuracy 3/4 at the same cost.Source: §4.1 · pp. 4–5

4.2 ALIASING, FILTERING, AND RESTORATION

• Aliasing omits the missingness mask, pooling values across masks; in the example it prefers shortcut x4 when p > 1/2, even with unlimited data.The optimal evaluation policy should acquire x1.Source: §4.2 · p. 5
• Filtering augments the state with the missingness mask but uses only complete instances for evaluation, so under independent MCAR only an expected n(1 − p)^d training instances contribute directly.With unlimited data and positive probability of complete instances, filtering can recover the evaluation Bellman problem.Source: §4.2 · p. 6
• Generative restoration learns acquisition dynamics and stopping values from available features to restore unavailable transitions; under independent MCAR, it can recover evaluation conditionals with unlimited data.This requires every feature to be observable with positive probability.Source: §4.2 · p. 6

4.3 USABLE INSTANCES AND DATA REQUIREMENTS FOR FILTERING AND RESTORATION

• Filtering has an exponential data dependency on dimension d, whereas generative restoration has an exponential dependency on acquisition budget b.The stated high-probability filtering bound requires n ≥ (1 − δ)(1 − p)^−d; the text also establishes that filtering's dimension dependence is necessary in a constructed setting.Source: §4.3 · p. 7

5.1 SYNTHETIC CONTROLLED STUDY (EXAMPLE 1)

• In the synthetic study, myopic policies and aliasing converge to a shortcut with regret 1/4, while full-horizon filtering and restoration reach zero regret given enough data.Filtering becomes more data-intensive as dimension rises, whereas restoration’s data requirements increase with acquisition budget at fixed dimension.Source: §5.1 · p. 7, Figure 3 · p. 8
• Filtering and restoration regret curves nearly coincide across dimensions and missingness rates when plotted against effective training counts n(1 −p)^d and n(1 −p)^b, respectively.The dimension sweep uses b = 2 and p ∈{0.3, 0.5, 0.7}.Source: §5.1 · p. 7, Figure 4 · p. 8

5.2 AFA METHODS UNDER AFA-ITD

• Under MCAR at p = 0.7, DIME is least damaged, the three most damaged methods are non-myopic, and restoration recovers some—but not all—lost performance.In some configurations, restoration performs worse than restricted training because missingness can remove redundant or noisy features and make the problem easier.Source: Figure 5 · p. 9, §5.2 · p. 10

5.3 DATASET STRUCTURE

• CUBE-NM has the lowest static-route score and route overlap, while NHANES has the largest overlap and smallest route sensitivity; MiniBooNE combines the highest static score with low overlap and route sensitivity.Table 1 reports independent dataset rankings for each fixed-route quantity, with validation values averaged over five splits.Source: §5.3 · p. 11, Table 1 · p. 11

5.4 MISSINGNESS DAMAGE AND ADAPTIVE STRUCTURE

• Under MCAR, one-step values remain unchanged while multi-step values can fall; GDFS is nevertheless damaged because its trajectory-based estimates use fewer instances at greater acquisition depth.For GDFS, a training instance follows the evaluation trajectory to depth t only when all t acquired features are available, with probability (1 −p)^t.Source: §5.4 · p. 11
• Across method–dataset cells, margin over static route Vstatic and missingness damage under MCAR at p = 0.7 have Pearson r = 0.59 and Spearman ρ = 0.34.The scores are averaged over eight datasets and, for JAFA, OL, and ODIN, over both state representations.Source: Table 2 · p. 11

• Incomplete training data mainly damages methods that exploit multi-step acquisitions, in line with Proposition 1.Source: §6 · p. 12
• In the tabular setting, filtering’s data requirement grows exponentially with dimension, whereas generative restoration’s grows exponentially with acquisition budget.Source: §6 · p. 12
• Generative restoration can reduce the resulting performance gap for non-myopic methods in practice.Source: §6 · p. 12
• The authors suggest jointly leveraging AFA and generative learning to restore informative features while leaving uninformative ones blocked.Source: §6 · p. 12

• The proof proceeds by induction on the number of remaining acquisitions k.Source: §A.1 · p. 15
• Under MCAR, p(y | s, m) = p(y | s), which supports the stopping-value base case across states reachable under a mask.Source: §A.1 · p. 15
• The induction step applies the induction hypothesis and MCAR to establish the action-value and value-function inequalities, completing the proof.Source: §A.1 · p. 15

A.2 PROOF OF THEOREM 1

• The proof compares filtering and restoration through estimates of stopping values and acquisition dynamics used in the Bellman recursion.Source: §A.2 · p. 15

A.2.1 COUNT THE NUMBER OF USABLE TRAINING INSTANCES

• Under MCAR, restoration’s usable instances must match observed values and have the relevant features available; filtering can use only complete instances.For restoration, the cited bound includes a factor (1 −p)^b.Source: §A.2.1 · p. 16

A.2.2 COUNT THE NUMBER OF ESTIMATES

• With j acquired features, the proof counts feature sets and possible value assignments, then bounds the total required estimates by J := (Kd)^b+2.Each state has one stopping-value estimate and at most d acquisition-dynamics estimates.Source: §A.2.2 · p. 16

A.2.3 BOUND THE ERROR OF EACH ESTIMATE

• For each stopping-value and transition estimate, failure can arise from too few usable instances or an excessive estimation deviation.Transition-distribution deviations are controlled over subsets of the acquisition outcomes.Source: §A.2.3 · pp. 16–17
• When expected support n q P_s is below 8Λ_J, the proof makes no concentration claim and instead uses boundedness to obtain e_s ≤ ℓ_max.The low- and sufficient-support cases are combined into one error bound.Source: §A.2.3 · p. 18
• With probability at least 1−δ, the per-state error bounds hold simultaneously at every state with P_s > 0.The union bound covers count failures, stopping-value deviations, and transition-distribution deviations.Source: §A.2.3 · pp. 16, 18

A.2.4 BOUND THE EVALUATION REGRET IN TERMS OF ERRORS OF THE INDIVIDUAL ESTIMATES

• The value error at an acquisition combines transition-probability error, measured in total variation, with successor-state value errors.Unrolling the recursion weights local errors by the probability of reaching each state; the acquisition tree has at most K^t states at depth t.Source: §A.2.4 · pp. 18–19
• Policy regret is at most ε when value-estimation errors are bounded by ε/2 for every deterministic policy, because empirical optimality makes the middle term nonpositive.The remaining two terms in the regret decomposition are each at most ε/2.Source: §A.2.4 · p. 20
• Substituting q = (1−p)d for filtering and q = (1−p)b for restoration gives the respective sufficient sample-size bounds.The proof first controls value-estimation error and then transfers it to evaluation regret.Source: §A.2.4 · pp. 19–20
• Filtering can have regret at least 1/4 with probability greater than δ when n(1−p)^d < 1−δ, whereas restoration guarantees the same regret with n scaling as (1−p)^−b.The filtering example considers the event that no training instance is complete.Source: §A.2.4 · p. 20

B.1 EXPERIMENTAL DETAILS

• Training data are tested under MCAR, MAR, logistic MNAR, and self-masking MNAR at missingness rates p ∈ {0.3, 0.5, 0.7}.Masks are fixed across epochs and AFA episodes; instances whose masks remove all acquisitions are resampled.Source: §B.1 · pp. 20–21
• Restricted-data methods remove unavailable acquisitions from legal actions; aliasing omits availability from the decision state, while filtering includes it.AACO uses shared-support distances and excludes training instances with no shared support.Source: §B.1 · p. 21
• The benchmark uses five dataset splits and each dataset’s largest predefined hard budget, reporting accuracy on balanced synthetic datasets and macro-F1 on real-world datasets.Predictors are trained before synthetic missingness is imposed and held fixed across approaches.Source: §B.1 · pp. 20–21

B.2 PSEUDOCOUNT SMOOTHING IN THE SYNTHETIC CONTROLLED STUDY

• The synthetic controlled study’s 1/2 pseudocount smoothing preserves the same sufficient sample-size bounds for filtering and restoration estimates.The bounded-error argument also covers smaller counts, including N = 0.Source: §B.2 · pp. 21–22

B.3 COMPUTATIONAL COST OF RESTORATION

• 1.15 was the median generative-to-restricted wall-clock ratio; 59% of pairs were within 1.25× and 74% within 1.5×.Amortized PVAE fitting and restoration took a median of 29.3 seconds per trained method, with overhead varying substantially across methods.Source: §B.3 · p. 22, Figure 6 · p. 22

B.4 RESULTS BEYOND MCAR

• Across the four missingness mechanisms, missingness has little or substantial effect depending on the setting, and restoration does not uniformly improve every method.The comparison is reported at p = 0.7 for MCAR, MAR, logistic MNAR, and self-masking MNAR.Source: §B.4 · p. 22, Figure 7 · p. 23
• Figure 8 compares restoration gain with missingness damage across methods, mechanisms, eight datasets, and three rates; fitted-ray slopes use only cells with damage ≥ 0.01.The threshold restricts slope summaries to settings with a non-negligible gap to recover.Source: §B.4 · p. 22, Figure 8 · p. 24