Paper deep dive
Active Feature Acquisition With Incomplete Training Data
Reza Rezvan, Valter Schütz, Han Wu, Linus Aronsson, Morteza Haghir Chehreghani
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract: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 this https URL.
Tags
Links
- Source: https://arxiv.org/abs/2609.32325v1
- Canonical: https://arxiv.org/abs/2609.32325v1
Trouble viewing inline? Open PDF directly →
Full Text
80,766 characters extracted from source content.
Expand or collapse full text
Active Feature Acquisition With Incomplete Training Data Reza Rezvan Valter Schütz Han Wu Linus Aronsson Morteza Haghir Chehreghani Affiliation: Department of Computer Science and Engineering Affiliation: Chalmers University of Technology & University of Gothenburg Email: rezvan,valter.schutz,hanwu,linaro,morteza.chehreghani@chalmers.se Abstract 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. 1 Introduction Obtaining information in the real world is often a laborious and costly task. Medical tests require considerable time and resources, recommender systems need a continual collection of information at the price of compromising user privacy, and robotic systems expend energy on every sensor measurement (Gorry & Barnett, 1968; Jeckmans et al., 2013; Lauri et al., 2023). Also, acquiring all features before producing a prediction may be unnecessary or impractical. This has motivated cost-sensitive learning with feature acquisition costs, where the goal is to balance predictive performance against the cost of acquiring features. Further, the information required for an accurate prediction might differ between instances: the relevance of certain tests may only become apparent after observing the results of previous ones, with the appropriate sequence of tests differing between patients. Active Feature Acquisition (AFA) models this problem as the sequential selection of features to acquire for each instance, balancing predictive performance against acquisition cost (Aronsson & Haghir Chehreghani, 2026; Guney et al., 2025; Norcliffe et al., 2025). AFA methods are often categorized into myopic and non-myopic approaches, depending on whether they consider the long-term consequences of acquisitions or not (Aronsson et al., 2026). However, the current AFA literature has largely assumed access to complete training data (Aronsson et al., 2026), which is often hard to come by in practice. For example, medical records often only contain the specific test results that were ordered for each patient; it is unrealistic to assume that every test was performed on every patient. In contrast, during medical checkups it may be possible to request any relevant test for a patient. This resulting mismatch between what is available during training and evaluation is a common challenge. Motivated by this, we study AFA with Incomplete Training Data (AFA-ITD), formalizing it and analyzing the effect incomplete training data has on the learning process. Our main contributions are the following. • We formulate the AFA-ITD problem (Section 3.4) and characterize the difference between its training and evaluation MDPs (Section 4.1). • We analyze the effects of incomplete training data on the Bellman recursions and show that, under missing completely at random (MCAR), missingness can lower non-myopic action values even when one-step values are unchanged (Proposition 1). • We define and distinguish three approaches to learning from incomplete training data: the aliasing, filtering, and generative restoration approaches, and characterize their data requirements (Theorem 1). • We experimentally test our theory on a synthetic controlled study, and on eight common AFA datasets using six AFA baselines. In line with our theory, missingness mainly damages methods that exploit multi-step acquisitions, and generative restoration is often able to recover lost performance (Section 5). 2 Related Work In this section, we review related work, highlighting the works closest to our problem setting. Active Feature Acquisition. AFA methods are generally characterized along two orthogonal axes. The first axis is their planning horizon: myopic methods only plan for the immediate next feature according to some one-step acquisition criterion. Notable myopic AFA methods include EDDI (Ma et al., 2019), GDFS (Covert et al., 2023), and DIME (Gadgil et al., 2024). In contrast, non-myopic methods plan for the potential multi-step effect an acquisition can have, often using reinforcement learning methods or other longer-horizon supervision formulations (Dulac-Arnold et al., 2011; Shim et al., 2018; Janisch et al., 2019; Aronsson & Haghir Chehreghani, 2026). The second axis is whether they model the acquisition dynamics. Model-based methods estimate these conditional distributions and use them during training, whereas model-free methods train directly from experience and interaction. Hybrid methods combine both, learning from experience with an explicit acquisition model (Aronsson et al., 2026). AFA from Incomplete Training Data. To the best of our knowledge, the AFA literature on incomplete training data remains very limited. Janisch et al. (2020) were the first to investigate the AFA-ITD problem setting. During training, they restrict feature-acquisition actions to available features and compare methods with mean and MICE imputation baselines. Although their approach is empirically effective, the resulting restricted Bellman problem is not formally analyzed. More recently, Kobayashi et al. (2026) studied AFA from incomplete data and characterized specific conditions under which a greedy conditional-mutual-information acquisition objective remains identifiable. von Kleist et al. (2023) instead investigated the evaluation of AFA policies from incomplete data using semi-offline estimators. Wendland et al. (2026) have also proposed miss-MDPs, a general class of POMDPs in which missingness remains part of the observation process at deployment. None of these works have formalized the AFA-ITD problem setting and characterized how incomplete training data affects the Bellman recursions. Generative Models in AFA. Generative models are commonly used in AFA to approximate acquisition dynamics. Ma et al. (2019) introduced the Partial Variational Autoencoder (PVAE) architecture to estimate conditionals and to evaluate a myopic information-gain acquisition criterion. Zannone et al. (2019) later used the PVAE architecture to generate synthetic acquisition trajectories, primarily to improve data efficiency, while Li & Oliva (2021) learned a generative surrogate model to provide intermediate rewards and auxiliary information during learning. However, the benefit of generative modeling remains unclear in the literature. Schütz et al. (2026) find that the gap between model-free and model-based approaches is often smaller than previously reported on common AFA datasets using a fair benchmarking setting. In this work, we will show that using a generative model is a natural solution to incomplete training data and not only an ad-hoc extension for data efficiency. 3 Problem Formulation In this section, we introduce and formalize the AFA optimization problem, its formulation as a (Partially Observable) Markov Decision Process ((PO)MDP), the standard taxonomy of missingness mechanisms, and formulate the AFA problem with incomplete training data. 3.1 Active Feature Acquisition (AFA) Active Feature Acquisition (AFA) formulates an explicit trade-off mechanism between acquiring features at a cost and their (expected) predictive performance. Usually, this trade-off is formulated as an optimization problem. We use the formulation of Aronsson et al. (2026) and only consider the hard-budget classification objective. Let x≔(x1,…,xd)∈x (x_1,…,x_d) be an instance with the corresponding label y∈y , distributed according to (x,y)∼p(x,y)(x,y) p(x,y). For S⊆[d]≔1,…,dS [d] \1,…,d\ we write xSx_S for the acquired values and U≔[d]∖SU [d] S with xUx_U for the unacquired values. Taking action a∈Ua∈ U reveals feature xax_a and incurs cost cac_a, and we define the accumulated cost as c(S)≔∑i∈Scic(S) _i∈ Sc_i. Furthermore, a policy π maps the current state (xS,S)(x_S,S) to an unacquired feature a∈Ua∈ U and a predictor f maps the final observation to a label prediction. Together, they define the following optimization problem: minf,π _f,π (x,y)π[ℓ(f(xπ[x],π[x]),y)] _(x,y)E_π[ (f(x_π[x],π[x]),y)] (1) subject to to c(π[x])≤bfor all x, c(π[x])≤ b all x, where ℓ is a loss function, b is the hard budget, and π[x]⊆[d]π[x] [d] is the final set of acquired features for instance x under policy π. Throughout, we assume access to a well-trained predictor f, since learning the predictor is not the objective of interest in this work. 3.2 AFA as a (Partially Observable) Markov Decision Process AFA can be modeled as a Partially Observable Markov Decision Process (POMDP) whose latent state contains the fully observed instance x and the label y, and whose observations are the features acquired so far xSx_S (Aronsson et al., 2026). Because the latent state does not change over time, the POMDP can be reduced to a fully observable MDP on the state s=(xS,S)s=(x_S,S) (Dulac-Arnold et al., 2011). In this fully observable MDP, the acquisition dynamics can be written in terms of the individual feature probabilities p(s′∣s,a) p(s s,a) =p(xS∪a,S∪a∣xS,S,a) =p(x_S∪\a\,S∪\a\ x_S,S,a) (2) =p(xa∣xS,S) =p(x_a x_S,S) (3) where s′≔(xS∪a,S∪a)s (x_S∪\a\,S∪\a\). The quality of a state s and an acquisition a is captured by truncated (action-)value functions, for which the following Bellman recursions (Sutton & Barto, 2018) hold: V0(s) V_0(s) =y|s[−ℓ(f(s),y)], =E_y s[- (f(s),y)], (4) Qk(s,a) Q_k(s,a) =xa|s[Vk−1(s′)], =E_x_a s[V_k-1(s )], Vk(s) V_k(s) =maxV0(s),maxa∈b(S)Qk(s,a). = \V_0(s),\ _a _b(S)Q_k(s,a) \. Here VkV_k is the optimal value when at most k further acquisitions are allowed and b(S)≔a∈U:c(S)+ca≤bA_b(S) \a∈ U:c(S)+c_a≤ b\. Finally, to measure the gap from an optimal policy one usually uses the regret. Let ℒ(π)≔(x,y)π[ℓ(f(xπ[x],π[x]),y)]L(π) _(x,y)E_π[ (f(x_π[x],π[x]),y)] be the expected loss, and let π∗π^* be the optimal policy that minimizes ℒ(π)L(π). The regret of π is then Reg(π)≔ℒ(π)−ℒ(π∗)Reg(π) (π)-L(π^*). 3.3 Missingness Mechanisms Let m∈0,1dm∈\0,1\^d be a binary missingness mask of dimension d, where mi=1m_i=1 indicates that feature i is missing from the training instance. The missingness mask is drawn once per instance from p(m∣x,y)p(m x,y) and remains fixed for that instance. We write M≔i:mi=1M \i:m_i=1\ and M¯≔i:mi=0 M \i:m_i=0\ for the missing and available indices, with the corresponding feature values xMx_M and xM¯x_ M, respectively. Classically, Rubin’s taxonomy (Rubin, 1976; Little & Rubin, 2002) classifies mechanisms as • Missing Completely At Random (MCAR): the missingness is independent of the instance, p(m∣x,y)=p(m)p(m x,y)=p(m). • Missing At Random (MAR): the missingness may depend on the available features, but not the missing features, p(m∣x,y)=p(m∣xM¯)p(m x,y)=p(m x_ M). • Missing Not At Random (MNAR): the missingness may depend on the missing feature values themselves, either through a feature’s own value (self-masking MNAR) or through other unavailable features (e.g., logistic MNAR). 3.4 AFA with Incomplete Training Data (AFA-ITD) In the AFA-ITD problem setting, missing features cannot be part of the training action space: for a training instance with missingness mask m, we define the training action space as btrain(S,m)≔a∈U:ma=0,c(S)+ca≤bA^train_b(S,m) \a∈ U:m_a=0,\ c(S)+c_a≤ b\. In contrast, the evaluation action space does not have any missing features and is defined as beval(S)≔a∈U:c(S)+ca≤bA^eval_b(S) \a∈ U:c(S)+c_a≤ b\. Consequently, btrain(S,m)⊆beval(S)A^train_b(S,m) ^eval_b(S). Thus, the training Bellman recursion can be written as V0train(s,m) V_0^train(s,m) =y|s,m[−ℓ(f(s),y)], =E_y s,m[- (f(s),y)], (5) Qktrain(s,m,a) Q_k^train(s,m,a) =xa|s,m[Vk−1train(s′,m)], =E_x_a s,m [V_k-1^train(s ,m) ], Vktrain(s,m) V_k^train(s,m) =maxV0train(s,m),maxa∈btrain(S,m)Qktrain(s,m,a). = \V_0^train(s,m), _a ^train_b(S,m)Q_k^train(s,m,a) \. These recursions hold under MCAR because the missingness mask m is independent of (x,y)(x,y), leaving the conditionals unchanged. By contrast, the evaluation Bellman equations remain unchanged and are defined as in Equation 4. 4 Theoretical Analysis In this section, we analyze the effect incomplete training data can have on the Bellman recursions between training and evaluation. We then analyze the aliasing approach and how omitting the missingness mask from the state affects the learning process. Afterwards, we consider the filtering approach, through state augmentation with the missingness mask m, and the generative restoration approach. Finally, we theoretically compare their data requirements. All proofs can be found in Appendix A. 4.1 How the (Action-)Value Functions Are Affected by Incomplete Training Data Inspecting Equation 5 and Equation 4 side by side, we see that the only difference between them is their respective action spaces. To better understand what effect this can have, we introduce a simple non-myopic AFA problem with binary features. Example 1 (The Shortcut Problem). Consider d≥2bd≥ 2b binary features xi∈0,1x_i∈\0,1\ with a hard budget of b≥2b≥ 2. The features consist of the context feature x1x_1, the two branch blocks of features B1=2,…,b,B2=b+1,…,2b−1B_1=\2,…,b\,B_2=\b+1,…,2b-1\, with block length b−1b-1, and the shortcut feature x2bx_2b. The corresponding label is defined as y=⨁j∈Bx1+1xjy= _j∈ B_x_1+1x_j, where ⊕ denotes the XOR operation. The shortcut feature x2bx_2b is equal to the label y with probability 3/43/4 but has a cost of b, while all other features have a cost of one. The remaining features x2b+1,…,xdx_2b+1,…,x_d are independent uniform noise. Example 1 serves as a simple non-myopic AFA problem. The optimal policy is to always first acquire the context feature x1x_1, then acquire all the features in the corresponding branch block. This yields a total cost of b and an accuracy of 11. In contrast, the shortcut also costs b but only attains an accuracy of 3/43/4. Evaluationx1x_1x2x_2x3x_3x4x_4x5x_5x6x_6yyTrainingx1x_1x2x_2x3x_3x4x_4x5x_5x6x_6y×y=x2y=x_2 or y=x3y=x_3P(x4=y)=34P(x_4=y)= 34 (a) A realization of an instance of the shortcut problem where the branch features x2x_2 and x3x_3 are missing. 0.500.500.750.751.001.001+Qk1+Q_kk=1k=1Acquire x1x_1Acquire x4x_4k=2k=2Acquire x1x_1Acquire x4x_4EvaluationTraining (b) The expected accuracy (1+Qk1+Q_k) for the corresponding instance in Figure 1(a). Figure 1: The shortcut problem for a fixed missingness mask m where the branch features x2x_2 and x3x_3 are missing (a), and the unchanged one-step and differing two-step 1+Qk1+Q_k optimal values for both training and evaluation (b). Figure 1(a) illustrates the problem for b=2b=2 and d=6d=6 for one instance where the two branch features x2,x3x_2,x_3 are missing. We now analyze the effect of the mismatch between training and evaluation in Figure 1(a) on the (action-)value functions. For our analysis, we use the zero-one loss function ℓ(f(s),y)=f(s)≠y (f(s),y)=1\f(s)≠ y\ and report the action values as 1+Q(…)1+Q(…), corresponding to expected accuracy under zero-one loss, for easier interpretation. For a myopic policy, the context feature x1x_1 has no immediate predictive value and the best prediction after acquiring it is a guess. In contrast, the shortcut feature is preferable for myopic methods because it has immediate predictive value, predicting the label with probability 34 34. Thus, we have Q1train(s0,m,a=1)=Q1eval(s0,a=1) Q_1^train(s_0,m,a=1)=Q_1^eval(s_0,a=1) =12, = 12, Q1train(s0,m,a=4)=Q1eval(s0,a=4) Q_1^train(s_0,m,a=4)=Q_1^eval(s_0,a=4) =34, = 34, where s0≔(x∅,∅)s_0 (x_ , ) is the initial state. In contrast, a non-myopic policy can plan for the full acquisition of both the context feature and the corresponding branch block features. However, in Figure 1(a) neither x2x_2 nor x3x_3 is available, which means that acquiring the context feature x1x_1 will yield poorer performance than the shortcut feature x4x_4, leaving x1x_1 as good as a guess. Consequently, Q2train(s0,m,a=1)=12≠Q2eval(s0,a=1) Q_2^train(s_0,m,a=1)= 12≠ Q_2^eval(s_0,a=1) =1, =1, Q2train(s0,m,a=4)=Q2eval(s0,a=4) Q_2^train(s_0,m,a=4)=Q_2^eval(s_0,a=4) =34. = 34. Figure 1 illustrates that the restricted training action space can impact the learned action values, and the following proposition states how this holds more generally for an arbitrary planning horizon. Proposition 1 ((Action-)values under the restricted action space). Assume that the missingness mask m is independent of (x,y)(x,y) (MCAR). Then, for every state s=(xS,S)s=(x_S,S) reachable under mask m and every k≥0k≥ 0, Vktrain(s,m)≤Vkeval(s),V_k^train(s,m)≤ V_k^eval(s), with equality when k=0k=0. For every a∈btrain(S,m)a ^train_b(S,m) and k≥1k≥ 1, Qktrain(s,m,a)≤Qkeval(s,a),Q_k^train(s,m,a)≤ Q_k^eval(s,a), with equality when k=1k=1. Thus, we are left with a potential gap in the (action-)value functions that can impact performance. Hereafter, we seek to answer the following two questions: (i) what happens if we still try to learn the (action-)value functions from finite training data with varying missingness masks? and (i) what are some possible mitigation methods that ensure we learn the correct evaluation problem? 4.2 Aliasing, Filtering, and Restoration Proposition 1 does not guarantee that the restricted action space results in the wrong (action-)value functions, only that it is possible. However, it is clear that if we omit the missingness mask m from our state representation, we will suffer from an aliasing issue. Definition 1 (Tabular Aliasing). The tabular aliasing approach learns one (action-)value Qkalias(s,a)Q_k^alias(s,a), Vkalias(s)V_k^alias(s), or a policy πalias(a∣s)π^alias(a s), omitting the missingness mask m entirely. Across instances with different missingness masks m and corresponding action spaces btrain(S,m)A^train_b(S,m), the aliasing approach will assign different values to the same state-action pair (s,a)(s,a), pooling them. We can observe this issue in Figure 1. Conditional on the context feature x1x_1 being observed, the relevant branch feature x2x_2 or x3x_3 is available with probability 1−p1-p. The corresponding action-value for acquiring the context feature x1x_1 is then Q2alias(s0,a=1)=(1−p)⋅1+p⋅12=1−p2.Q_2^alias(s_0,a=1)=(1-p)· 1+p· 12=1- p2. (6) The aliasing approach will therefore prefer the shortcut feature x4x_4 whenever p>1/2p>1/2, even though the optimal evaluation policy should always acquire the context feature x1x_1. This error remains even with unlimited training data. In contrast, if we augment the state representation with the missingness mask m, we can learn separate values for different masks. Definition 2 (Tabular Filtering). The tabular filtering approach augments the state with the missingness mask (s,m)(s,m) when learning Qkfilter(s,m,a)Q_k^filter(s,m,a), Vkfilter(s,m)V_k^filter(s,m), or a policy πfilter(a∣s,m)π^filter(a s,m). During evaluation, the filtering approach will only use the learned values for the missingness mask m=0m=0, meaning that only complete instances are used for the values. Thus, provided that complete instances occur with positive probability, the filtering approach will be able to fully recover the evaluation Bellman problem with unlimited data. However, this approach can be statistically inefficient: under independent MCAR, a training instance is complete with probability (1−p)d(1-p)^d, scaling exponentially with the dimension d. Consequently, only (an expected) n(1−p)dn(1-p)^d of the n training instances contribute directly. An alternative approach is to restore the unavailable acquisition dynamics p(xa∣s,m)p(x_a s,m) using a generative model, thereby recovering Equation 4 from Equation 5. Definition 3 (Tabular Generative Restoration). The tabular generative restoration approach learns acquisition dynamics p^(xa∣s) p(x_a s) and stopping values V^0(s) V_0(s) from all instances with the features of s available, and uses them to restore unavailable transitions when learning Qkrestore(s,a)Q_k^restore(s,a), Vkrestore(s)V_k^restore(s), or a policy πrestore(a∣s)π^restore(a s). Note that under independent MCAR, the empirical acquisition dynamics p^(xa∣s) p(x_a s) will be consistent because the missingness is independent of the corresponding feature and label values, i.e., p(m∣x,y)=p(m)p(m x,y)=p(m). Thus, if all features are observable with positive probability, the restoration approach can fully recover the evaluation conditionals with unlimited data, solving the exact evaluation problem (Equation 4). 4.3 Usable Instances and Data Requirements for Filtering and Restoration Both the filtering and the generative restoration approaches solve the correct evaluation Bellman recursions under MCAR and unlimited data. However, with a finite amount of training data, the approaches will have different numbers of usable training instances. (a) Aliasingx1x_1x2x_2x3x_3x4x_4x5x_5x6x_6All 6 instances(b) Filteringx1x_1x2x_2x3x_3x4x_4x5x_5x6x_61 complete instance(c) Generative restorationx1x_1x2x_2x3x_3x4x_4x5x_5x6x_6All 6 instancesObservedMissingGenerated Figure 2: The usable training instances for each of the approaches, on Example 1 under MCAR with p=0.3p=0.3. Figure 2 illustrates the difference in usable training instances for all three approaches. Both the aliasing and generative restoration approaches, the latter after restoring all missing features, can use all instances for learning, while filtering is only able to use complete instances. In the tabular setting, each approach can be viewed as solving a distinct Bellman problem: aliasing solves the restricted Bellman recursions (Equation 5), generative restoration solves the approximate evaluation Bellman recursions, and filtering solves the exact evaluation Bellman recursions (Equation 4). Since generative restoration and filtering solve the correct Bellman recursions, we are interested in their data requirements to achieve a certain regret with high probability. The following theorem quantifies this. Theorem 1 (Data requirements under MCAR). Consider d discrete features xa∈ax_a _a with |a|≤K|X_a|≤ K for an integer K≥2K≥ 2, and costs ca≥1c_a≥ 1 under the integer hard budget 1≤b≤d1≤ b≤ d. Let f be a fixed predictor, independent of the n i.i.d. training instances, with bounded loss ℓ∈[0,ℓmax] ∈[0, _ ]. Assume MCAR, with each feature independently missing with probability p<1p<1. Let πfilterπ^filter and πrestoreπ^restore be the exact corresponding policies obtained by their respective Bellman recursions. For every 0<ε≤ℓmax0< ≤ _ and δ∈(0,1)δ∈(0,1), filtering satisfies Reg(πfilter)≤εReg(π^filter)≤ with probability at least 1−δ1-δ whenever n≥Cℓmax2Kbε2(1−p)d(blog(Kd)+K+log2δ).n≥ C _ ^2K^b ^2(1-p)^d (b (Kd)+K+ 2δ ). In contrast, generative restoration satisfies Reg(πrestore)≤εReg(π^restore)≤ with probability at least 1−δ1-δ whenever n≥Cℓmax2Kbε2(1−p)b(blog(Kd)+K+log2δ),n≥ C _ ^2K^b ^2(1-p)^b (b (Kd)+K+ 2δ ), where C>0C>0 is a numerical constant independent of all of the above parameters. Thus, the filtering approach has an exponential dependency on the dimension d, whereas the generative restoration approach has an exponential dependency on the acquisition budget b. The following proposition shows that the dependency on d is necessary for filtering. Proposition 2 (Filtering requires complete instances). Consider Example 1 with d≥2b+1d≥ 2b+1 under the zero-one loss, where each feature is independently missing with probability p. Let filtering use fixed fallback estimates when a state has no usable instances (Section A.2.1) and a fixed tie-breaking rule. Then, for some relabeling of the unit-cost features, with probability at least 1−n(1−p)d1-n(1-p)^d, Reg(πfilter)≥14.Reg(π^filter)≥ 14. Consequently, for ε<1/4 <1/4, Reg(πfilter)≤εReg(π^filter)≤ with probability at least 1−δ1-δ requires n≥(1−δ)(1−p)−dn≥(1-δ)(1-p)^-d. 5 Experiments In this section, we solve and evaluate the synthetic controlled study of Example 1 to isolate the dimension-budget dependency in Theorem 1. Then, we benchmark restricted training (training in which acquisitions are restricted to the features available in each instance) against generative restoration on eight common AFA datasets with synthetic missingness, and connect the results to the theory. 5.1 Synthetic Controlled Study (Example 1) To test the three approaches and our theory, we solve Example 1 exactly. The problem is parameterized by both the dimension d and the acquisition budget b, so we sweep the dimension over d∈6,8,10d∈\6,8,10\ with a fixed acquisition budget of b=2b=2 and sweep the budget over b∈2,3,4b∈\2,3,4\ with a fixed dimension of d=10d=10, both under MCAR with missingness rate fixed at p=0.6p=0.6. The approaches first estimate the acquisition dynamics p^(xa∣s) p(x_a s) and the expected terminal losses V^0(s) V_0(s) from the usable training instances with a fixed Bayes predictor, using a pseudocount of 1/21/2 (Section B.2). Then, they solve their respective Bellman problem exactly with dynamic programming using these estimates. Finally, they are evaluated against the optimal oracle policy in terms of evaluation regret. Figure 3: Evaluation regret of the myopic Q^1 Q_1 (gray, dashed) and full planning-horizon Q^b Q_b (solid) methods, across the three learning approaches swept over the dimension d (top row) and the acquisition budget b (bottom row), under MCAR at p=0.6p=0.6, with 95% confidence bands. Figure 3 illustrates the myopic policy Q^1 Q_1 along with full-horizon planning Q^b Q_b on the same instances over 150 independent replicates, each with a freshly sampled training set and missingness masks, of the three approaches for Example 1. As expected from the one-step values in Section 4.1, the myopic policy prefers the shortcut and only achieves a regret of 1/41/4 across all configurations. By contrast, the full-horizon filtering and restoration policies achieve zero regret given enough training data. In the dimension sweep, the filtering approach becomes more data-intensive as d increases, whereas restoration converges at the same training size across the tested dimensions. In contrast, in the budget sweep, increasing b lengthens the optimal acquisition route and consequently increases restoration’s data requirements at fixed d, reflecting what is described in Theorem 1 in both sweeps. Finally, the aliasing approach converges to the shortcut and a regret of 1/41/4, since the relevant branch block is available with probability (1−p)b−1<1/2(1-p)^b-1<1/2 (Equation 6). Figure 4 plots the full-horizon regret of the dimension sweep against the effective number of training instances in Theorem 1, n(1−p)dn(1-p)^d for filtering and n(1−p)bn(1-p)^b for restoration, at p∈0.3,0.5,0.7p∈\0.3,0.5,0.7\. The curves of all dimensions and missingness rates nearly coincide for both approaches. Figure 4: Evaluation regret of the full planning-horizon Q^b Q_b policies of filtering (a) and generative restoration (b) in the dimension sweep at b=2b=2, against the effective number of training instances n(1−p)dn(1-p)^d and n(1−p)bn(1-p)^b, respectively, for d∈6,8,10d∈\6,8,10\ and p∈0.3,0.5,0.7p∈\0.3,0.5,0.7\. 5.2 AFA Methods under AFA-ITD Figure 5: Restricted training vs. generative restoration under MCAR at p=0.7p=0.7. Arrows point from restricted training to generative restoration, and bars are 95% bootstrap intervals over five splits. Methods and datasets are ordered by descending mean missingness damage. Gray rows denote myopic methods (DIME, GDFS), hatched rows denote non-myopic methods with intermediate predictive rewards (OL, ODIN), and white rows denote non-myopic acquisition with a terminal prediction objective (AACO, JAFA). Evaluation Setup and Protocol. We use the AFA benchmark framework of Schütz et al. (2026) and adapt it to our AFA-ITD problem setting. We evaluate six AFA methods: the myopic DIME (Gadgil et al., 2024) and GDFS (Covert et al., 2023) methods, and the non-myopic AACO (Valancius et al., 2024), JAFA (Shim et al., 2018), OL (Kachuee et al., 2019), and ODIN (Zannone et al., 2019) methods. For each method, we train three variants: a complete-data version without any missingness, another with generative restoration applied to the training data beforehand, and a restricted training version with acquisitions restricted to available features. The non-myopic RL-based methods JAFA, OL, and ODIN are each represented by two separate methods, depending on whether they include the missingness mask in the state (e.g., OL (s,m)(s,m)) or not (e.g., OL (s)(s)), corresponding to the filtering and aliasing approaches, respectively. For restoration, we fit a label-conditioned Partial Variational Autoencoder (PVAE) (Ma et al., 2019; Zannone et al., 2019) on incomplete training data and replace only missing values with a joint sample conditioned on the observed features and label. We use the benchmark’s synthetic CUBE (Zannone et al., 2019), CUBE-NM (Schütz et al., 2026), and CUBE with non-uniform costs (CUBE-NUC) datasets. For real-world datasets, we use ACTG175 (Hammer et al., 1996), Diabetes (Kachuee et al., 2019), NHANES mortality (NHANES) (Erion et al., 2022), MiniBooNE (Roe, 2005), and Heart Disease (Janosi et al., 1989). We synthetically induce MCAR, MAR, logistic MNAR, and self-masking MNAR at rates p∈0.3,0.5,0.7p∈\0.3,0.5,0.7\. We use five dataset splits, pairing restricted and restored treatments within each split. The predictor is trained before masking and held fixed across treatments, isolating the effect on acquisition. Missingness masks remain fixed across epochs and acquisition episodes; evaluation instances are fully observed. We report mean accuracy on the synthetic datasets and mean macro-F1 on the real-world datasets, at each dataset’s largest predefined acquisition budget under Equation 1. RL training budgets are selected by convergence on complete data and held fixed across treatments. Exact budgets, optimization settings, missingness mechanisms, and method adaptations are given in Section B.1. Figure 5 illustrates our primary findings under MCAR at p=0.7p=0.7. We only report results for the highest missingness rate as we observe the same patterns, but weaker, at the other missingness rates. The figure orders both methods and datasets according to their mean missingness damage: the difference in performance between the complete-data version (vertical line) and the restricted version (hollow circle). First, we note that the myopic method DIME is the least damaged, and the three most damaged methods are all non-myopic, consistent with Proposition 1. Second, restoration (filled circle) recovers part of the damage across a variety of methods and datasets, indicating that the advantage that Theorem 1 predicted in the tabular setting can hold true for methods using function approximation on real-world datasets. However, restoration is far from a “free lunch”: in some configurations, restoration performs worse than restricted training. This is because missingness can remove redundant or noisy features, making the problem easier; restoring all features then returns the method to the harder original problem. Among the datasets, CUBE-NM is the most affected, aligning with its non-myopic structure (Schütz et al., 2026). In contrast, we note that the two least affected datasets are the real-world MiniBooNE and NHANES mortality datasets. We further investigate the structure of all eight datasets and its relation to missingness damage in Sections 5.3 and 5.4, report the computational cost of restoration in Section B.3, and repeat the comparison under MAR and MNAR in Section B.4. 5.3 Dataset Structure Equation 6 shows that aliasing can converge to the wrong policy, but not that every dataset must be damaged by the restricted action space. If missingness only blocks irrelevant features, then restricting the action space does not change the optimal policy. Similarly, if several strong acquisition routes are interchangeable, blocking one route can have little effect because another route remains available. Missingness damage also depends on the acquisition structure of a dataset, for which we introduce two empirical measures. To compute both quantities, we first split the training data into a selection and a validation set. Then, we sample L feasible acquisition routes (action sequences) R1,…,RLR_1,…,R_L under budget b. Let Vsel(R)V_sel(R) and Vval(R)V_val(R) denote the static scores of route R on the selection and validation splits, respectively, and let R⋆∈argmaxR∈R1,…,RLVsel(R),Vstatic≔Vval(R⋆).R_ ∈ _R∈\R_1,…,R_L\V_sel(R),\ V_static V_val(R_ ). We define route sensitivity as Δroute≔Vstatic−1L∑k=1LVval(Rk). _route V_static- 1L _k=1^LV_val(R_k). A large Δroute _route indicates that the selected route outperforms a typical feasible route, while a small value indicates little separation in their validation scores. To measure whether high-performing routes use the same acquisitions, let wk≔[Vsel(Rk)−Vsel(∅)]+w_k [V_sel(R_k)-V_sel( ) ]_+ denote the positive predictive gain over the empty route. Treating each route as a set of legal acquisition actions, we define performance-weighted route overlap as ωroute≔∑1≤i<j≤Lwiwj|Ri∩Rj||Ri∪Rj|∑1≤i<j≤Lwiwj. _route _1≤ i<j≤ Lw_iw_j |R_i∩ R_j||R_i∪ R_j| _1≤ i<j≤ Lw_iw_j. A large value indicates that predictive gain is concentrated on routes with overlapping acquisition sets, whereas a small value indicates that the gain is distributed across structurally distinct routes. Table 1: Fixed-route structure. Each column ranks the datasets by that quantity alone, largest first, so the three rankings are independent. Mean ± standard error over five dataset splits. Static references and route weights are selected on training data; VstaticV_static and Δroute _route are reported on validation data. Each dataset is at its largest evaluation budget b, which is 15 for Diabetes and MiniBooNE, 14 for CUBE-NM, 10 for ACTG175, CUBE and NHANES, 7 for CUBE-NUC and Heart disease. VstaticV_static Δroute _route ωroute _route MiniBooNE 0.894±0.0040.894± 0.004 CUBE 0.245±0.0100.245± 0.010 NHANES 0.669±0.0000.669± 0.000 CUBE-NUC 0.847±0.0190.847± 0.019 ACTG175 0.175±0.0120.175± 0.012 CUBE 0.342±0.0000.342± 0.000 ACTG175 0.846±0.0120.846± 0.012 CUBE-NUC 0.174±0.0170.174± 0.017 ACTG175 0.287±0.0010.287± 0.001 CUBE 0.824±0.0100.824± 0.010 Diabetes 0.166±0.0010.166± 0.001 Heart disease 0.264±0.0030.264± 0.003 NHANES 0.731±0.0050.731± 0.005 Heart disease 0.127±0.0150.127± 0.015 CUBE-NUC 0.221±0.0000.221± 0.000 Heart disease 0.720±0.0190.720± 0.019 CUBE-NM 0.059±0.0100.059± 0.010 Diabetes 0.205±0.0000.205± 0.000 Diabetes 0.679±0.0030.679± 0.003 MiniBooNE 0.058±0.0030.058± 0.003 MiniBooNE 0.181±0.0000.181± 0.000 CUBE-NM 0.317±0.0200.317± 0.020 NHANES 0.009±0.0020.009± 0.002 CUBE-NM 0.164±0.0000.164± 0.000 Table 1 shows VstaticV_static, Δroute _route, and ωroute _route across the datasets, with additional results available in Section B.4. Observations on Table 1. CUBE-NM has by far the lowest VstaticV_static, indicating that a static route does not yield good performance. It also has the lowest ωroute _route, so what predictive gain there is comes from structurally distinct routes. In contrast, NHANES has the largest ωroute _route and the smallest Δroute _route, indicating that we should expect low missingness damage. We want to highlight MiniBooNE’s interesting structure; it has the highest VstaticV_static while also having the second-smallest ωroute _route and a small Δroute _route, indicating that there exist a few top-performing routes with minimal overlap. 5.4 Missingness Damage and Adaptive Structure By Proposition 1, MCAR leaves one-step values unchanged and can only lower multi-step values. Thus, only methods that exploit multi-step acquisitions can have their exact values damaged. Table 2 compares each method’s complete-data score with the static route VstaticV_static of Table 1. DIME and ODIN score below the static route on average, and on CUBE-NM, where the other methods are damaged the most, they score 0.240.24 and 0.270.27 against Vstatic=0.32V_static=0.32. In contrast, GDFS, AACO, and OL exceed the static route and are damaged. GDFS is myopic, so its exact one-step values are unchanged, but it estimates them from its own acquisition trajectories: a training instance follows the evaluation trajectory to depth t only if all t acquired features are available, which under MCAR occurs with probability (1−p)t(1-p)^t, the same factor as in Theorem 1. Restoration removes this factor, in line with its gain for GDFS. JAFA is the exception, scoring below the static route on average while being damaged on Heart Disease and CUBE-NUC. Finally, the correlation between margin and damage across method–dataset cells is moderate and driven mainly by CUBE-NM. Table 2: Complete-data score, its margin over the static route VstaticV_static (Table 1), and missingness damage under MCAR at p=0.7p=0.7, averaged over the eight datasets and, for JAFA, OL and ODIN, over both state representations. Across method–dataset cells, Pearson r=0.59r=0.59 and Spearman ρ=0.34ρ=0.34 between margin and damage. Method Complete Margin over VstaticV_static Damage DIME 0.7050.705 −0.027-0.027 +0.002+0.002 ODIN 0.6670.667 −0.065-0.065 +0.009+0.009 GDFS 0.7450.745 +0.013+0.013 +0.059+0.059 AACO 0.7580.758 +0.026+0.026 +0.062+0.062 JAFA 0.7070.707 −0.026-0.026 +0.072+0.072 OL 0.7450.745 +0.013+0.013 +0.092+0.092 6 Conclusion We have investigated the AFA-ITD problem setting and found that: (i) in line with our theory (Proposition 1), incomplete training data mainly damages methods that exploit multi-step acquisitions; (i) in the tabular setting, the data requirement of filtering grows exponentially with the dimension, whereas that of generative restoration grows only with the acquisition budget (Theorem 1); (i) generative restoration can in practice reduce the resulting performance gap for non-myopic methods. We hope that our work opens up the development of AFA methods that leverage the theoretical framework of AFA-ITD. For example, by leveraging AFA learning and generative learning jointly, it might be possible to restore only the informative features and leave the uninformative ones blocked. Acknowledgments The work of Valter Schütz and Morteza Haghir Chehreghani was partially supported by the Swedish Research Council VR (grant number 2023-04809). The work of Linus Aronsson and Morteza Haghir Chehreghani was partially supported by the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation. Finally, the computations and data handling were enabled by resources provided by the National Academic Infrastructure for Supercomputing in Sweden (NAISS). References Aronsson & Haghir Chehreghani (2026) Linus Aronsson and Morteza Haghir Chehreghani. Non-myopic active feature acquisition via pathwise policy gradients, 2026. URL https://arxiv.org/abs/2605.05511. Aronsson et al. (2026) Linus Aronsson, Arman Rahbar, and Morteza Haghir Chehreghani. A survey on active feature acquisition strategies. In Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence, 2026. URL https://arxiv.org/abs/2502.11067. Covert et al. (2023) Ian Connick Covert, Wei Qiu, Mingyu Lu, Na Yoon Kim, Nathan J. White, and Su-In Lee. Learning to maximize mutual information for dynamic feature selection. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, p. 6424–6447. PMLR, 2023. URL https://proceedings.mlr.press/v202/covert23a.html. Dulac-Arnold et al. (2011) Gabriel Dulac-Arnold, Ludovic Denoyer, Philippe Preux, and Patrick Gallinari. Datum-wise classification: A sequential approach to sparsity. In Machine Learning and Knowledge Discovery in Databases (ECML PKDD), volume 6911 of Lecture Notes in Computer Science, p. 375–390. Springer, 2011. doi: 10.1007/978-3-642-23780-5_34. Erion et al. (2022) Gabriel Erion, Joseph D. Janizek, Carly Hudelson, Richard B. Utarnachitt, Andrew M. McCoy, Michael R. Sayre, Nathan J. White, and Su-In Lee. A cost-aware framework for the development of AI models for healthcare applications. Nature Biomedical Engineering, 2022. Gadgil et al. (2024) Soham Gadgil, Ian Connick Covert, and Su-In Lee. Estimating conditional mutual information for dynamic feature selection. In The Twelfth International Conference on Learning Representations, 2024. URL https://openreview.net/forum?id=Oju2Qu9jvn. Gorry & Barnett (1968) G. Anthony Gorry and G. Octo Barnett. Experience with a model of sequential diagnosis. Computers and Biomedical Research, 1(5):490–507, 1968. doi: 10.1016/0010-4809(68)90016-5. Guney et al. (2025) Osman Berke Guney, Ketan Suhaas Saichandran, Karim Elzokm, Ziming Zhang, and Vijaya B Kolachalama. Active feature acquisition via explainability-driven ranking. In Aarti Singh, Maryam Fazel, Daniel Hsu, Simon Lacoste-Julien, Felix Berkenkamp, Tegan Maharaj, Kiri Wagstaff, and Jerry Zhu (eds.), Proceedings of the 42nd International Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research, p. 20748–20765. PMLR, 13–19 Jul 2025. URL https://proceedings.mlr.press/v267/guney25a.html. Hammer et al. (1996) Scott M. Hammer, David A. Katzenstein, Michael D. Hughes, Holly Gundacker, Robert T. Schooley, Richard H. Haubrich, W. Keith Henry, Michael M. Lederman, John P. Phair, Manette Niu, Martin S. Hirsch, and Thomas C. Merigan. AIDS clinical trials group study 175. UCI Machine Learning Repository, 1996. URL https://doi.org/10.24432/C5ZG8F. Janisch et al. (2019) Jaromír Janisch, Tomáš Pevný, and Viliam Lisý. Classification with costly features using deep reinforcement learning. In Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence. AAAI Press, 2019. doi: 10.1609/aaai.v33i01.33013959. URL https://doi.org/10.1609/aaai.v33i01.33013959. Janisch et al. (2020) Jaromír Janisch, Tomáš Pevný, and Viliam Lisý. Classification with costly features as a sequential decision-making problem. Machine Learning, 109(8):1587–1615, 2020. doi: 10.1007/s10994-020-05874-8. URL https://doi.org/10.1007/s10994-020-05874-8. Janosi et al. (1989) Andras Janosi, William Steinbrunn, Matthias Pfisterer, and Robert Detrano. Heart disease. UCI Machine Learning Repository, 1989. Jeckmans et al. (2013) Arjan J. P. Jeckmans, Michael Beye, Zekeriya Erkin, Pieter Hartel, Reginald L. Lagendijk, and Qiang Tang. Privacy in recommender systems. In Social Media Retrieval. Springer, 2013. Kachuee et al. (2019) Mohammad Kachuee, Orpaz Goldstein, Kimmo Kärkkäinen, Sajad Darabi, and Majid Sarrafzadeh. Opportunistic learning: Budgeted cost-sensitive learning from data streams. In International Conference on Learning Representations, 2019. URL https://openreview.net/forum?id=S1eOHo09KX. Kobayashi et al. (2026) Yuta Kobayashi, Zilin Jing, Jiayu Yao, Hongseok Namkoong, and Shalmali Joshi. Learning-to-measure: In-context active feature acquisition. In Forty-third International Conference on Machine Learning, 2026. URL https://openreview.net/forum?id=ZumBSRsRbE. Lauri et al. (2023) Mikko Lauri, David Hsu, and Joni Pajarinen. Partially observable markov decision processes in robotics: A survey. IEEE Transactions on Robotics, 39(1):21–40, 2023. Li & Oliva (2021) Yang Li and Junier Oliva. Active feature acquisition with generative surrogate models. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, p. 6450–6459. PMLR, 2021. Little & Rubin (2002) R. J. A. Little and D. B. Rubin. Statistical Analysis with Missing Data. Wiley Series in Probability and Mathematical Statistics. Wiley, 2002. ISBN 9780471183860. Ma et al. (2019) Chao Ma, Sebastian Tschiatschek, Konstantina Palla, Jose Miguel Hernandez-Lobato, Sebastian Nowozin, and Cheng Zhang. EDDI: Efficient dynamic discovery of high-value information with partial VAE. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, p. 4234–4243. PMLR, 2019. URL https://proceedings.mlr.press/v97/ma19c.html. Norcliffe et al. (2025) Alexander Norcliffe, Changhee Lee, Fergus Imrie, Mihaela van der Schaar, and Pietro Lio. Stochastic encodings for active feature acquisition, 2025. URL https://arxiv.org/abs/2508.01957. Roe (2005) Byron Roe. MiniBooNE particle identification. UCI Machine Learning Repository, 2005. Rubin (1976) Donald B. Rubin. Inference and missing data. Biometrika, 63(3):581–592, 1976. doi: 10.2307/2335739. Schütz et al. (2026) Valter Schütz, Han Wu, Reza Rezvan, Linus Aronsson, and Morteza Haghir Chehreghani. AFABench: A generic framework for benchmarking active feature acquisition. In Proceedings of the 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2026. URL https://doi.org/10.1145/3770855.3817493. Shim et al. (2018) Hajin Shim, Sung Ju Hwang, and Eunho Yang. Joint active feature acquisition and classification with variable-size set encoding. In Advances in Neural Information Processing Systems, volume 31, 2018. Sutton & Barto (2018) Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. The MIT Press, second edition, 2018. URL http://incompleteideas.net/book/the-book-2nd.html. Valancius et al. (2024) Michael Valancius, Maxwell Lennon, and Junier Oliva. Acquisition conditioned oracle for nongreedy active feature acquisition. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp (eds.), Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, p. 48957–48975. PMLR, 2024. URL https://proceedings.mlr.press/v235/valancius24a.html. von Kleist et al. (2023) Henrik von Kleist, Alireza Zamanian, Ilya Shpitser, and Narges Ahmidi. Evaluation of active feature acquisition methods for static feature settings. arXiv preprint arXiv:2312.03619, 2023. URL https://arxiv.org/abs/2312.03619. Wendland et al. (2026) Joshua Wendland, Markel Zubia, Roman Andriushchenko, Maris F. L. Galesloot, Milan Ceska, Henrik von Kleist, Thiago D. Simão, Maximilian Weininger, and Nils Jansen. Missingness-MDPs: Bridging the theory of missing data and POMDP s, 2026. URL https://arxiv.org/abs/2605.12262. Zannone et al. (2019) Sara Zannone, Jose Miguel Hernandez Lobato, Cheng Zhang, and Konstantina Palla. ODIN: Optimal discovery of high-value information using model-based deep reinforcement learning. In Real-world Sequential Decision Making Workshop, ICML, June 2019. URL https://w.microsoft.com/en-us/research/publication/odin-optimal-discovery-of-high-value-information-using-model-based-deep-reinforcement-learning/. Appendix A Proofs A.1 Proof of Proposition 1 Proof. The proof proceeds by induction on the number of remaining acquisitions k. Under MCAR, we know that p(y∣s,m)=p(y∣s)p(y s,m)=p(y s), so the stopping values must satisfy V0train(s,m) V_0^train(s,m) =y|s,m[−ℓ(f(s),y)] =E_y s,m[- (f(s),y)] =y|s[−ℓ(f(s),y)]=V0eval(s). =E_y s[- (f(s),y)]=V_0^eval(s). This establishes the case for k=0k=0. For the induction step, we assume that Vk−1train(s′,m)≤Vk−1eval(s′)V_k-1^train(s ,m)≤ V_k-1^eval(s ) at every successor state s′s reachable under mask m. Consequently, for all training actions a∈btrain(S,m)a ^train_b(S,m), we have Qktrain(s,m,a) Q_k^train(s,m,a) =xa|s,m[Vk−1train(s′,m)] =E_x_a s,m [V_k-1^train(s ,m) ] ≤xa|s[Vk−1eval(s′)]=Qkeval(s,a), _x_a s [V_k-1^eval(s ) ]=Q_k^eval(s,a), where the inequality step uses the induction hypothesis and MCAR. For the value function, we have Vktrain(s,m) V_k^train(s,m) =maxV0train(s,m),maxa∈btrain(S,m)Qktrain(s,m,a) = \V_0^train(s,m), _a ^train_b(S,m)Q_k^train(s,m,a) \ ≤maxV0eval(s),maxa∈btrain(S,m)Qkeval(s,a) ≤ \V_0^eval(s), _a ^train_b(S,m)Q_k^eval(s,a) \ ≤maxV0eval(s),maxa∈beval(S)Qkeval(s,a)=Vkeval(s), ≤ \V_0^eval(s), _a ^eval_b(S)Q_k^eval(s,a) \=V_k^eval(s), where the last inequality follows from the fact that btrain(S,m)⊆beval(S)A^train_b(S,m) ^eval_b(S). For k=1k=1, we further have Q1train(s,m,a)=xa|s,m[V0train(s′,m)]=xa|s[V0eval(s′)]=Q1eval(s,a),Q_1^train(s,m,a)=E_x_a s,m[V_0^train(s ,m)]=E_x_a s[V_0^eval(s )]=Q_1^eval(s,a), which concludes the proof. ∎ A.2 Proof of Theorem 1 Proof. Both the filtering and restoration approaches need to estimate two things: the expected stopping values V0(s)V_0(s) and the acquisition dynamics p(xa∣s)p(x_a s) for the Bellman recursion, but they differ in how many usable training instances contribute to these estimates. The proof will proceed in the following steps: 1. We count the number of usable training instances for both approaches (Section A.2.1). 2. We count the total number of estimates each approach needs (Section A.2.2). 3. We bound the error of each estimate type (Section A.2.3). 4. Finally, we bound the total evaluation regret in terms of errors of the individual estimates (Section A.2.4). For the bounding steps, we make use of the following two inequalities: Multiplicative Chernoff bound Let X=∑i=1nXiX= _i=1^nX_i be a sum of independent binary random variables with mean μ=[X]μ=E[X]. For a fixed γ∈(0,1)γ∈(0,1) the multiplicative Chernoff bound is P(X<(1−γ)μ)≤exp(−γ2μ2).P (X<(1-γ)μ )≤ (- γ^2μ2 ). Hoeffding bound Let Z¯=1N∑i=1NZi Z= 1N _i=1^NZ_i be an average of N independent random variables, each taking values in an interval of length R. For any t>0t>0 the one-sided Hoeffding bound is P(Z¯−[Z¯]≥t) P ( Z-E[ Z]≥ t ) ≤exp(−2Nt2R2) ≤ (- 2Nt^2R^2 ) with the two-sided form P(|Z¯−[Z¯]|≥t)≤2exp(−2Nt2R2).P (| Z-E[ Z]|≥ t )≤ 2 (- 2Nt^2R^2 ). A.2.1 Count the Number of Usable Training Instances Let NsgenN_s^gen and Ns,agenN_s,a^gen denote the number of training instances that the restoration approach can use to estimate V0(s)V_0(s) and p(xa∣s)p(x_a s), respectively. NsgenN_s^gen counts the number of instances that match xSx_S and have every feature in S available, while Ns,agenN_s,a^gen counts instances that additionally have feature a available, Nsgen N_s^gen ≔∑i=1nxS(i)=xS,S⊆M¯(i), _i=1^n1\x_S^(i)=x_S,\ S M^(i)\, Ns,agen N_s,a^gen ≔∑i=1nxS(i)=xS,S∪a⊆M¯(i). _i=1^n1\x_S^(i)=x_S,\ S∪\a\ M^(i)\. Under MCAR, the feature values and labels are independent of availability, thus [Nsgen] [N_s^gen] =nPs(1−p)|S|, =nP_s(1-p)^|S|, [Ns,agen] [N_s,a^gen] =nPs(1−p)|S|+1, =nP_s(1-p)^|S|+1, where PsP_s is the probability that a random data instance agrees with the observed values xSx_S. Every acquisition costs at least one, which means that |S|≤b|S|≤ b and an available next acquisition satisfies |S|+1≤b|S|+1≤ b. In contrast, the filtering approach can only use complete instances [Nsfilt]=[Ns,afilt]=nPs(1−p)d.E[N_s^filt]=E[N_s,a^filt]=nP_s(1-p)^d. For brevity, we write the common bound for both methods [Ns]≥nqPs,[Ns,a]≥nqPs,E[N_s]≥ nqP_s,\ E[N_s,a]≥ nqP_s, where q=(1−p)d,for filtering,(1−p)b,for restoration.q= cases(1-p)^d,&for filtering,\\ (1-p)^b,&for restoration. cases If Ns=0N_s=0, we set V^0(s) V_0(s) to a fixed value in [−ℓmax,0][- _ ,0], and if Ns,a=0N_s,a=0, we set p^(⋅∣s) p(· s) to a fixed distribution on aX_a, e.g., the uniform distribution. A.2.2 Count the Number of Estimates With j acquired features, there are (dj) dj feature sets and at most KjK^j possible value assignments. Each state s has one stopping-value estimate V^0(s) V_0(s) and at most d acquisition dynamics to estimate p^(⋅∣s) p(· s). The total number of estimates is therefore at most (d+1)∑j=0b(dj)Kj≤(d+1)∑j=0b(Kd)j≤2(d+1)(Kd)b≤(Kd)b+2,(d+1) _j=0^b djK^j≤(d+1) _j=0^b(Kd)^j≤ 2(d+1)(Kd)^b≤(Kd)^b+2, and we write J≔(Kd)b+2J (Kd)^b+2 for an upper bound on the number of estimates needed. A.2.3 Bound the Error of Each Estimate Failure possibilities and confidence allocation. For each stopping-value estimate V^0(s) V_0(s), failure can occur if (i) the number of usable instances is too small, or (i) the estimate deviates too far in either direction. For each transition-distribution estimate p^(⋅∣s) p(· s), failure can occur if (i) the number of usable instances is too small, or (i) for some A⊆aA _a, the empirical probability p^(A∣s) p(A s) deviates too far from p(A∣s)p(A s). There are at most J estimates of both types combined. Hence, there are at most J count-failure events, 2J2J stopping-value deviation events, and 2KJ2^KJ transition-subset deviation events. Since K≥2K≥ 2, their total number is at most J(1+2+2K)≤2K+1J.J(1+2+2^K)≤ 2^K+1J. Thus, we allocate a failure probability of δ/(2K+1J)δ/(2^K+1J) to each event and define ΛJ≔log2K+1Jδ=(b+2)log(Kd)+(K+1)log2+log1δ. _J 2^K+1Jδ=(b+2) (Kd)+(K+1) 2+ 1δ. Thus, whenever an individual failure probability is bounded by exp(−A) (-A), requiring A≥ΛJA≥ _J makes it at most δ/(2K+1J)δ/(2^K+1J). Finally, after deriving the individual bounds, a union bound controls all estimates simultaneously with probability at least 1−δ1-δ. Concentration of the sample counts. The count NsN_s is a sum of independent binary variables, so we apply the Chernoff bound at γ=1/2γ=1/2 with μ=[Ns]≥nqPsμ=E[N_s]≥ nqP_s, P(Ns<nqPs2) P (N_s< nqP_s2 ) ≤P(Ns<[Ns]2) ≤ P (N_s< E[N_s]2 ) ≤exp(−[Ns]8) ≤ (- E[N_s]8 ) ≤exp(−nqPs8). ≤ (- nqP_s8 ). Hence, whenever nqPs≥8ΛJnqP_s≥ 8 _J, P(Ns<nqPs2)≤e−ΛJ.P (N_s< nqP_s2 )≤ e^- _J. Since [Ns,a]≥nqPsE[N_s,a]≥ nqP_s as well, the same bound holds for Ns,aN_s,a. Concentration of the estimates. Now suppose that nqPs≥8ΛJnqP_s≥ 8 _J. On the event Ns≥nqPs/2N_s≥ nqP_s/2, the two-sided Hoeffding bound gives P(|V^0(s)−V0(s)|>t,Ns≥nqPs2)≤2exp(−nqPst2ℓmax2).P (| V_0(s)-V_0(s)|>t,\,N_s≥ nqP_s2 )≤ 2 (- nqP_st^2 _ ^2 ). Choosing t=ℓmaxΛJnqPs,t= _ _JnqP_s, makes this probability at most 2e−ΛJ2e^- _J. For a transition estimate, we write Δ(xa)≔p^(xa∣s)−p(xa∣s) (x_a) p(x_a s)-p(x_a s) and define its total-variation error by TV(p^,p)≔12∑xa∈a|Δ(xa)|.TV( p,p) 12 _x_a _a| (x_a)|. Since p^(⋅∣s) p(· s) and p(⋅∣s)p(· s) both sum to one, ∑xaΔ(xa)=0 _x_a (x_a)=0. Consequently, the total positive and negative deviations are equal, and TV(p^,p)=∑xa:Δ(xa)>0Δ(xa)=maxA⊆a(p^(A∣s)−p(A∣s)).TV( p,p)= _x_a:\, (x_a)>0 (x_a)= _A _a ( p(A s)-p(A s) ). Thus, it is sufficient to control the empirical probability of every subset A⊆aA _a. Conditional on Ns,a=N_s,a=N, for any fixed A we have p^(A∣s)=1N∑i=1Nxa(i)∈A, p(A s)= 1N _i=1^N1\x_a^(i)∈ A\, which is an average of independent binary variables with expectation p(A∣s)p(A s). The one-sided Hoeffding bound and a union bound over the at most 2K2^K subsets of aX_a therefore give P(TV(p^,p)>t|Ns,a=N)≤2Kexp(−2Nt2).P (TV( p,p)>t\, |\,N_s,a=N )≤ 2^K (-2Nt^2). Hence, on the event Ns,a≥nqPs/2N_s,a≥ nqP_s/2, P(TV(p^,p)>t,Ns,a≥nqPs2)≤2Kexp(−nqPst2).P (TV( p,p)>t,\,N_s,a≥ nqP_s2 )≤ 2^K (-nqP_st^2). Taking t=ΛJ/(nqPs)t= _J/(nqP_s) makes this probability at most 2Ke−ΛJ2^Ke^- _J. A uniform bound over all states. To express both kinds of deviation error (in V V and p p) on the scale of the value function, let es≔max|V^0(s)−V0(s)|,ℓmaxmaxa∈beval(S)TV(p^(⋅∣s),p(⋅∣s)).e_s \| V_0(s)-V_0(s)|, _ _a ^eval_b(S)TV\! ( p(· s),p(· s) ) \. If no acquisition is legal, only the stopping-value error is present. The concentration bound above applies when nqPs≥8ΛJnqP_s≥ 8 _J. When instead nqPs<8ΛJnqP_s<8 _J, the sample counts may be small or zero, so we make no concentration claim. However, boundedness still gives es≤ℓmaxe_s≤ _ . The two cases can therefore be combined as es≤ℓmaxmin1,8ΛJnqPs.e_s≤ _ \1, 8 _JnqP_s \. Indeed, when nqPs<8ΛJnqP_s<8 _J the minimum equals 11, while when nqPs≥8ΛJnqP_s≥ 8 _J this is only a constant-factor weakening of the concentration bound above. There are at most J estimates of both types combined. A union bound over their count failures, stopping-value deviations, and transition-distribution deviations is at most J(1+2+2K)e−ΛJ≤2K+1Je−ΛJ=δ.J(1+2+2^K)e^- _J≤ 2^K+1Je^- _J=δ. Consequently, with probability at least 1−δ1-δ, the bound on ese_s holds at every state with Ps>0P_s>0 simultaneously. The error budget in the notation of the theorem. It remains to replace ΛJ _J by the quantity Λ≔blog(Kd)+K+log2δ b (Kd)+K+ 2δ used in the theorem. Since b≥1b≥ 1, K≥2K≥ 2, and δ<1δ<1, we have (b+2)log(Kd)≤3blog(Kd),(K+1)log2≤2K,log1δ≤log2δ.(b+2) (Kd)≤ 3b (Kd),\ (K+1) 2≤ 2K,\ 1δ≤ 2δ. Thus ΛJ≤3Λ _J≤ 3 and 8ΛJ≤24Λ8 _J≤ 24 . Since min1,⋅ \1,·\ is nondecreasing, we obtain es≤ℓmaxmin1,24ΛnqPs.e_s≤ _ \1, 24 nqP_s \. (7) A.2.4 Bound the Evaluation Regret in Terms of Errors of the Individual Estimates How local errors affect value estimates of the initial state. Fix a deterministic policy π. Let Vkπ(s)V_k^π(s) be its true value with at most k acquisitions remaining, and let V^kπ(s) V_k^π(s) be its value using the empirical estimates. Both values lie in [−ℓmax,0][- _ ,0], since the only reward is the negative loss when the policy stops. This also holds at states without training samples because their fallback estimates (Section A.2.1) lie in the same ranges. If the policy stops at s, its value error is |V^0(s)−V0(s)|≤es| V_0(s)-V_0(s)|≤ e_s. Otherwise, let a be its chosen acquisition. The current value error can be decomposed in terms of transition probability errors and next-state value errors: V^kπ(s)−Vkπ(s) V_k^π(s)-V_k^π(s) =∑xa∈ap^(xa∣s)V^k−1π(s′)−∑xa∈ap(xa∣s)Vk−1π(s′) = _x_a _a p(x_a s) V_k-1^π(s )- _x_a _ap(x_a s)V_k-1^π(s ) =∑xa∈a(p^(xa∣s)−p(xa∣s))V^k−1π(s′) = _x_a _a ( p(x_a s)-p(x_a s) ) V_k-1^π(s ) +∑xa∈ap(xa∣s)(V^k−1π(s′)−Vk−1π(s′)). + _x_a _ap(x_a s) ( V_k-1^π(s )-V_k-1^π(s ) ). Since the successor values lie in an interval of length at most ℓmax _ , the definition of total variation gives |∑xa∈a(p^(xa∣s)−p(xa∣s))V^k−1π(s′)|≤ℓmaxTV(p^,p)≤es. | _x_a _a ( p(x_a s)-p(x_a s) ) V_k-1^π(s ) |≤ _ TV( p,p)≤ e_s. Indeed, subtracting the midpoint of the successor-value range from every value leaves the sum unchanged, after which the bound follows from TV(p^,p)=12‖p^−p‖1TV( p,p)= 12\| p-p\|_1. The second sum carries the remaining value errors forward, weighted by the true probabilities. Taking absolute values consequently gives |V^kπ(s)−Vkπ(s)|≤es+∑xa∈ap(xa∣s)|V^k−1π(s′)−Vk−1π(s′)|.| V_k^π(s)-V_k^π(s)|≤ e_s+ _x_a _ap(x_a s)| V_k-1^π(s )-V_k-1^π(s )|. (8) Starting at the initial state s0s_0 and unrolling the recursion in Equation 8, |V^bπ(s0)−Vbπ(s0)|≤∑t=0b∑s reached aftert acquisitionsrses,| V^π_b(s_0)-V^π_b(s_0)|≤ _t=0^b _ subarraycs reached after\\ t acquisitions subarrayr_se_s, (9) where rsr_s is the probability that π reaches s. Summing the errors over acquisitions. After t acquisitions, a deterministic policy has observed t feature values, each with at most K possible outcomes. Its acquisition tree therefore contains at most KtK^t states at that depth. Reaching a state s=(xS,S)s=(x_S,S) requires an instance to match xSx_S, so rs≤Psr_s≤ P_s. Furthermore, for any instance the policy visits at most one state at depth t, and hence ∑s:|S|=trs≤1 _s:\ |S|=tr_s≤ 1. The sum may be smaller than one because some instances lead to earlier stopping. For the states at depth t, these observations give ∑s:|S|=trsPs _s:\ |S|=t r_s P_s ≤∑s:|S|=trs ≤ _s:\ |S|=t r_s ≤Kt∑s:|S|=trs≤Kt/2, ≤ K^t _s:\ |S|=tr_s≤ K^t/2, where the last inequality uses Cauchy–Schwarz over at most KtK^t states. Multiplying Equation 7 by rsr_s and summing gives ∑s:|S|=trses≤ℓmax24Λnq∑s:|S|=trsPs _s:|S|=tr_se_s≤ _ 24 nq _s:|S|=t r_s P_s ≤ℓmax24KtΛnq. ≤ _ 24K^t nq. Substituting into Equation 9 and summing over depths yields |V^bπ−Vbπ| | V_b^π-V_b^π| ≤ℓmax24Λnq∑t=0bKt/2 ≤ _ 24 nq _t=0^bK^t/2 (10) ≤424ℓmaxKbΛnq, ≤ 4 24\, _ K^b nq, where ∑t=0bKt/2=K(b+1)/2−1K−1≤4Kb/2, _t=0^bK^t/2= K^(b+1)/2-1 K-1≤ 4K^b/2, for K≥2K≥ 2. From value error to regret. To bound the value estimation error in Equation 10 by ε/2 /2, it is sufficient to require nq≥Cℓmax2KbΛε2,nq≥ C _ ^2K^b ^2, where C>0C>0 is a numerical constant chosen large enough to absorb the fixed constants. Under this condition, |V^bπ−Vbπ|≤424Cε.| V_b^π-V_b^π|≤ 4 24 C . Choosing, for example, C≥1536C≥ 1536 ensures that |V^bπ−Vbπ|≤ε2.| V_b^π-V_b^π|≤ 2. Both finite Bellman problems admit deterministic optimal policies. Let π∗π^* be optimal for evaluation and let πj _j be the policy returned by the chosen empirical method. Empirical optimality gives V^bπj≥V^bπ∗ V_b _j≥ V_b^π^*. The regret can be decomposed into a sum of value estimation errors: Reg(πj) ( _j) =Vbπ∗−Vbπj =V_b^π^*-V_b _j =(Vbπ∗−V^bπ∗)+(V^bπ∗−V^bπj)+(V^bπj−Vbπj) = (V_b^π^*- V_b^π^* )+ ( V_b^π^*- V_b _j )+ ( V_b _j-V_b _j ) ≤|Vbπ∗−V^bπ∗|+|V^bπj−Vbπj| ≤|V_b^π^*- V_b^π^*|+| V_b _j-V_b _j| ≤ε2+ε2=ε. ≤ 2+ 2= . The middle term is nonpositive by empirical optimality, and the remaining two terms are each at most ε/2 /2 because the value-error bound holds for every deterministic policy. Finally, substituting q=(1−p)dq=(1-p)^d for filtering and q=(1−p)bq=(1-p)^b for restoration gives the two stated sample-size bounds. ∎ A.3 Proof of Proposition 2 Proof. A training instance is complete with probability (1−p)d(1-p)^d, so by a union bound, no training instance is complete with probability at least 1−n(1−p)d1-n(1-p)^d. On this event, every estimate V^0(s) V_0(s) and p^(⋅∣s) p(· s) equals its fallback, so the empirical Bellman recursion returns a fixed policy π0 _0 that depends only on the costs, the fallbacks, and the tie-breaking rule. Relabeling the unit-cost features leaves all three unchanged, and hence also π0 _0. Since the optimal policy attains accuracy 11, the regret of a policy is one minus its accuracy, and we consider the first action of π0 _0. • If π0 _0 stops immediately, nothing is observed, and since y is uniform, its accuracy is 1/21/2. • If π0 _0 acquires the shortcut x2bx_2b, it spends the whole budget b and its accuracy is 3/43/4. • Otherwise, π0 _0 acquires a unit-cost feature xjx_j, and since d≥2b+1d≥ 2b+1, we relabel the unit-cost features so that xjx_j is noise. The remaining budget b−1b-1 excludes the shortcut. If π0 _0 acquires the context x1x_1, at most b−2b-2 features of the relevant block Bx1+1B_x_1+1 remain affordable. Otherwise, π0 _0 observes neither x1x_1 nor the shortcut, so its acquisitions are independent of x1x_1, and it can afford at most one full block, which is the relevant one with probability at most 1/21/2. If a bit of the relevant block is unobserved, it is uniform and independent of the observations, so y is uniform given the observations. Thus, the accuracy is at most 12⋅1+12⋅12=34 12· 1+ 12· 12= 34. Hence, the regret of π0 _0 is at least 1/41/4 in every case. Finally, if n(1−p)d<1−δn(1-p)^d<1-δ, then Reg(πfilter)≥1/4Reg(π^filter)≥ 1/4 with probability greater than δ. ∎ In contrast, Theorem 1 guarantees the same regret for generative restoration with n scaling as (1−p)−b(1-p)^-b. Appendix B Experimental Details & Additional Results B.1 Experimental Details Benchmark and evaluation protocol. We use the AFABench benchmarking framework (Schütz et al., 2026) and inherit its dataset implementations, preprocessing, predictors, method architectures, and hard-budget evaluation protocol unless stated otherwise. We use five dataset splits for every reported setting. CUBE-NUC contains two independently noisy copies of the CUBE features, one twice as costly as the other. For each split, the predictor is trained before synthetic missingness is imposed and held fixed for all approaches. Training missingness. For each dataset split, a fixed missingness mechanism is instantiated on the training split, and the missingness masks are fixed across epochs and AFA episodes. We implement synthetic MCAR, MAR, logistic MNAR, and self-masking MNAR at missingness rates p∈0.3,0.5,0.7p∈\0.3,0.5,0.7\. Under MCAR, features are independently unavailable with probability p. For MAR and logistic MNAR, we randomly select 30% of the features to determine the missingness probabilities of the remaining features through a logistic function. The intercepts are calibrated to match the requested missingness rate. The selected features remain available under MAR but are independently masked at the same rate under logistic MNAR. Under self-masking MNAR, the missingness probability of a feature depends on its own value. Missingness masks that would remove all acquisitions from an instance are resampled. Generative restoration. We implement generative restoration using the PVAE architecture from Zannone et al. (2019), which is based on the Partial VAE of Ma et al. (2019). For each training–validation pair with artificially induced missingness, we fit a separate PVAE on the training split and use the validation split for model selection. During training, random input masks are applied on top of each instance’s missingness, and reconstruction loss is computed only for its available features. We then condition the PVAE on each instance’s available features and label, draw a single joint sample of all d features from its decoder, and replace only the unavailable values. We use latent dimension 2020, batch size 128128, Adam with learning rate 10−310^-3, KL weight 0.10.1, and sample the additional masking probability uniformly from [0,0.9][0,0.9]. All remaining architecture and optimization settings follow AFABench’s ODIN configuration. Method adaptations. For every method trained on restricted data, acquisitions unavailable in a training instance are removed from its legal action set throughout the trajectory. We evaluate ODIN in its model-free configuration by disabling the additional synthetic-data generation used by its model-based variant. For JAFA, OL, and model-free ODIN, we additionally compare two state representations. In the aliasing variant, the availability mask is used only to block illegal actions and is not provided to the learned decision function. In the filtering variant, the availability of the remaining acquisitions is included in the state: JAFA and OL learn Q(s,m,a)Q(s,m,a), while both the actor and critic of ODIN condition on m. The variants are otherwise identical. For DIME and GDFS, we retain the standard AFABench architectures and objectives, but initialize unavailable acquisitions as already exhausted in their selection masks. AACO requires further adaptation because its nearest-neighbor search compares a query against incomplete training instances. For a query with acquired set S and a training instance with availability mask m¯(i) m^(i), we use the shared-support distance di2(s)=∑j∈Sm¯j(i)(xj−xj(i))2∑j∈Sm¯j(i).d_i^2(s)= _j∈ S m_j^(i) (x_j-x_j^(i) )^2 _j∈ S m_j^(i). Training instances with no shared support are excluded. Normalizing by the shared-support size prevents instances with fewer comparable features from appearing artificially close, and candidate losses are evaluated using only features available in each neighbor. Training, budgets, and metrics. All remaining settings follow AFABench, except for RL training lengths selected by convergence on complete data. This yielded 2,0002,000 batches for OL and 4,0004,000 for JAFA and model-free ODIN, with 256256 frames per batch. These lengths are fixed across missingness mechanisms, rates, state representations, and restoration treatments. We report each dataset at its largest predefined hard budget: 1010 for CUBE, ACTG175, and NHANES mortality; 1414 for CUBE-NM; 77 for CUBE non-uniform and Heart Disease; and 1515 for Diabetes and MiniBooNE. We report accuracy on the balanced synthetic datasets and macro-F1 on the real-world datasets, with means over the five dataset splits. B.2 Pseudocount Smoothing in the Synthetic Controlled Study The synthetic controlled study uses a pseudocount of 1/21/2 for each binary outcome. For N1N_1 occurrences of outcome one among N>0N>0 compatible instances, the change from the empirical frequency is |N1+1/2N+1−N1N|=|N/2−N1|N(N+1)≤12(N+1). | N_1+1/2N+1- N_1N |= |N/2-N_1|N(N+1)≤ 12(N+1). The fixed binary predictor’s expected zero-one loss is either the label-one probability or its complement, so the same bound applies to the stopping-value estimate. On the count event of the proof of Theorem 1 (Section A.2.3), N≥nqPs/2N≥ nqP_s/2. At a state with sufficient expected support, we have nqPs≥8ΛJnqP_s≥ 8 _J and ΛJ≥log24>1 _J≥ 24>1, so ΛJnqPs>1 _JnqP_s>1 and the additional error satisfies 12(N+1)≤1nqPs≤ΛJnqPs. 12(N+1)≤ 1nqP_s≤ _JnqP_s. Adding this to the Hoeffding deviation ℓmaxΛJ/(nqPs) _ _J/(nqP_s) of that proof at most doubles it, and 4ΛJ≤12Λ≤24Λ4 _J≤ 12 ≤ 24 . Thus, Equation 7 still holds. For smaller counts, including N=0N=0, the smoothed probability remains in [0,1][0,1], so the same bounded-error argument applies. The remainder of that proof is unchanged, giving the same sufficient sample-size bounds for the smoothed filtering and restoration estimates used in the synthetic controlled study. B.3 Computational Cost of Restoration Generative restoration introduces an additional model, but that model is trained once per dataset split and missingness setting and then reused across downstream AFA methods. Across the runs in Figure 6, the median generative-to-restricted wall-clock ratio is 1.151.15; 59%59\% of pairs are within 1.25×1.25× and 74%74\% within 1.5×1.5×. The amortized PVAE fitting and restoration steps contribute a median of 29.329.3 seconds per trained method. Thus, the additional computational cost is typically modest relative to downstream AFA training, although the overhead varies substantially across methods. Figure 6: Predictive performance against wall-clock time per trained method. Each arrow points from restricted training to generative restoration for the same dataset and method. B.4 Results beyond MCAR The main text focuses on MCAR, where the theoretical comparison is sharpest. Figure 7 reports the restricted training and restoration comparison for all four mechanisms (MCAR, MAR, MNAR (logistic), and MNAR (self-masking)). We observe similar patterns as in Figure 5, namely that missingness can have little effect in some settings and substantial effect in others, and restoration does not uniformly improve every method. Figure 7: Restricted training against generative restoration at p=0.7p=0.7 under all four missingness mechanisms. To separate the amount of damage caused by missingness from the amount recovered by restoration, Figure 8 plots restoration gain against missingness damage for each method and mechanism. The fitted rays use cells with damage at least 0.010.01, so their slopes summarize recovery only where there is a non-negligible gap to recover. Figure 8: Restoration gain against missingness damage, one panel per method and one block per mechanism, over all eight datasets and three rates.