A Survey on Active Feature Acquisition Strategies

1 Introduction

Many predictive systems rely on features that are costly, slow, invasive, or privacy sensitive to obtain. In medical decision support, ordering all tests for every patient can be expensive and burdensome, and it may delay treatment [Turney, 1995]. In personalized marketing and recommender systems, collecting all behavioral signals can be costly and raises privacy concerns. In interactive troubleshooting, diagnostic queries (for example, checks, measurements, or questions) consume time and user effort. Similar constraints arise in sensor systems and robotics, where measurements require power, time, or motion [Golovin and Krause, 2011; Lauri et al., 2023]. These settings motivate active feature acquisition (AFA), where an agent sequentially decides which feature values to acquire for each instance, and when to stop and predict, trading accuracy against feature acquisition cost.

AFA differs fundamentally from standard (static) feature selection, which commits to a single fixed subset used for all instances [Guyon and Elisseeff, 2003]. The advantage of AFA is most apparent when the informative features vary across instances. For example, suppose there is one feature that indicates which of many otherwise independent features is the only one relevant for predicting the label on the current instance. In order to be accurate on all instances, a static subset rule must include the indicator feature and all other features. In contrast, AFA learns an adaptive acquisition policy: it can first acquire the indicator feature and then, based on its realized value, choose the next feature accordingly, achieving the same accuracy while using far fewer features per instance [Valancius et al., 2024].

At a conceptual level, AFA is a form of optimal information acquisition. Optimal information acquisition problems are typically instances of adaptive stochastic optimization and are often computationally intractable, which explains the prevalence of approximations such as myopic value of information rules [Golovin and Krause, 2011]. AFA connects to a broad set of related fields that study cost aware information gathering, including sequential experimental design, active learning, bandits, decision analysis, and information gathering in robotics and perception [Howard, 1966; Settles, 2009; Lauri et al., 2023].

As described in Section 3, AFA can be formulated as a partially observable Markov decision process (POMDP) [ ˚Astr¨om, 1965]. Existing approaches largely differ in how they approximate the optimal action-value function in (10). Methods for decision-making in the broader POMDP literature are commonly organized by when computation is performed (offline versus online planning) and by whether the environment model is assumed known or must be learned (planning with a model versus reinforcement learning approaches, including model-based and model-free variants) [Ross et al., 2008]. While many AFA papers do not explicitly adopt POMDP terminology, their algorithmic choices map naturally onto these paradigms. The goal of this survey is to structure the AFA literature around the underlying POMDP formulation and the approximation decisions it entails. Accordingly, we group AFAmethods into four families (Table 1): (i) embedded costaware predictors, such as cost-sensitive decision trees and ensembles; (ii) model-based methods that learn or approximate the probabilistic components of the acquisition process and use them for model-based POMDP planning; (iii) model-free methods that learn a policy or action-value function directly from simulated acquisition episodes; and (iv) hybrid methods that combine complementary elements of model-based and model-free approaches.

Historical precursors of AFA include decision theoretic medical expert systems, with the Pathfinder system as a canonical example [Heckerman et al., 1992]. In parallel, cost sensitive decision trees embedded instance-wise feature selection into a tree policy and introduced cost adjusted split criteria [N´u˜nez, 1991; Norton, 1989]. Modern AFA generalizes these ideas to arbitrary predictors and richer policy classes, and it makes the sequential decision structure explicit, enabling generic planning and reinforcement learning (RL) methods.

Finally, [Attenberg et al., 2011] surveys selective data acquisition and briefly mentions AFA, and [Zois and Chelmis, 2024] surveys feature selection and acquisition across multiple settings (including AFA to some extent). To the best of our knowledge, this is the first survey focused specifically on AFA that (i) formulates AFA in detail as a POMDP, (ii) uses this framework to unify the diverse literature under a common lens, and (iii) provides a up-to-date taxonomy of AFA methods.

2 ProblemFormulation

In this section, we define the AFA problem. For each instance, an agent sequentially acquires feature values (incurring costs) and decides when to stop and predict.

Notation. Let (x, y) ∼ p(x, y) be the data distribution, where x = (x1, . . . , xd) ∈ X and y ∈ Y. In this paper, we represent random variables using bold symbols (e.g. x, y), while their possible values are shown in regular font. Acquiring feature a ∈ [d] ≜ {1, . . . , d} reveals xa at cost ca ∈ R+. For S ⊆ [d], let xS = {xa : a ∈ S} ∈ XS, and c(S) = ∑a∈S ca.

Predictor Under Partial Observability. A predictor must handle arbitrary subsets of observed features:

For brevity, we write f(xS) as shorthand for f(S, xS) whenever S is clear from context. In practice, f is often probabilistic, meaning it outputs a distribution p(y | xS), from which a point prediction can be obtained (for example, ˆ y = argmaxy p(y | xS)). To apply f to partially observed inputs, one typically maps (S, xS) to a fixed-dimensional representation. A common approach is masking: represent the current information by a binary mask m ∈ {0, 1}d together with a full-length feature vector ˜x ∈ Rd , where mi = 1 indicates that feature i has been acquired and mi = 0 otherwise. The input to f is then a concatenation such as (m, ˜x). The unobserved entries of ˜x can be filled with (i) a fixed placeholder value (for example, 0) or (ii) imputed values produced by an imputation rule or model, for example ˜xj ∼ p(xj | xS).

Acquisition Process. The features to be acquired for an instance x ∈ X are determined adaptively by a (stochastic) policy π. Let (S, xS) be the features acquired so far, U = [d] \ S the remaining unobserved features, and B ≥ 0 the acquisition budget per instance. The policy maps the current partial observation to an action π(S, xS) ∈ AB(S), where

is the set of available actions, and FB(S) ≜ AB(S)\{STOP}. In practice, the policy often outputs a probability distribution over actions. If π chooses a ∈ FB(S), we observe xa and update S = S∪{a} and U = U \{a}. If π chooses STOP, we output ˆ y = f(xS) and terminate. We write π[x] for the final acquired set when the policy stops on instance x. In practice, the policy π is usually implemented via masking, similar to the predictor f.

Optimization Objective. A standard objective trades off prediction loss and acquisition cost under a budget constraint:

where α ≥ 0 controls the cost-accuracy trade-off and ℓ is a loss function. The term αc(π[x]) lets acquisition cost vary across instances, so harder instances can use more resources. Thus, α induces a soft budget, whereas B imposes a hard budget. Two common special cases are α = 0 (only a hard budget) and B = c([d]) (all features are acquirable, so only the soft-budget term matters). The extended version of this survey will cover other AFA formulations, but the formulation in (3) is by far the most common.

Training. Most AFA papers assume access to i.i.d. training samples (x, y) ∼ p(x, y) with fully observed features and labels (costs are only incurred at test time). The predictor f and policy π are learned on this fully observed data (either jointly or separately) and then deployed on test instances from the same distribution, where features are initially unobserved and must be acquired sequentially at a cost. Only a small fraction of work studies an online variant in which the learner acquires features during training as well and updates f and π from streaming experience, so learning is cost-sensitive from the start rather than relying on fully observed training data (see e.g., [Kachuee et al., 2019; Rahbar et al., 2023; Rahbar et al., 2025]).

3 AFA-POMDP Formulation

The objective in (3) can be formulated as reward maximization in an episodic, finite-horizon POMDP. We provide a formal definition of the AFA-POMDP in the extended version of this survey.

State and Action Space. Let S ⊆ [d], U = [d] \ S, and S = {(S, x, y) : S ∈ 2[d] , x ∈ X, y ∈ Y}. Since x = (xS, xU), we write states as (S, xS, xU, y) ∈ S, with observed part (S, xS) and latent part (xU, y). Given budget B, the available actions are AB(S) from (2).

Transition and Observation Model. Given state (S, xS, xU, y), both the transition and observation model are deterministic. If a ∈ FB(S) is chosen, xa is observed from the latent component xU and the next state is (S ∪ {a}, xS∪{a}, xU\{a}, y). If STOP is chosen, the episode terminates and the predictor outputs a label.

Belief State and Observation Probability. The belief state corresponds to our current belief over the latent part (xU, y) given the observed information (S, xS). We write

The probability of observing o ∈ Xa after acquiring a ∈ FB(S) in the current belief state is

Belief Update. After acquiring a ∈ FB(S) and observing o ∈ Xa in current belief state b(xS), let

denote the updated belief given the new evidence. This belief can be obtained via Bayesian updating. The updated label belief is

(7) is the standard belief update rule in POMDPs [ ˚Astr¨om, 1965]. The Bayesian update of the full belief in (6) will be given in the extended version of this survey.

Belief-MDP and Sufficient Statistic. Any POMDP can be rewritten as a fully observable belief-MDP. For the exact AFAPOMDP, when the full belief is explicitly represented, the pair (S, b(xS)) is a sufficient statistic for the current observation history (S, xS) and defines the belief-MDP state: Bayesian updating folds observed values into b(xS), so the value function need not separately store xS. The set S determines feasible actions and acquired costs, while b(xS) determines observation probabilities, belief updates, and stopping rewards.

Reward. For a state s = (S, xS, xU, y), define the immediate reward R(s, a) = -αca for each acquisition action a ∈ FB(S), and R(s, STOP) = -ℓ(f(xS), y) for stopping. The expected stopping reward in belief state (S, b(xS)) is

Similarly, for any acquisition action a ∈ FB(S), r(S, b(xS), a) = ExU,y|xS [R((S, xS, xU, y), a)] = -αca. Here f(xS) represents the predictive distribution p(y | xS) in the Bayes-optimal case. In the exact POMDP, this distribution is the label marginal of b(xS) and can be maintained by Bayesian updating as in (7). In approximate implementations that query a predictive model directly, the computational state must still retain xS (or an equivalent encoding) to evaluate f(xS). Under log loss this gives r(S, b(xS), STOP) = -H(y | xS), while under 0-1 loss it gives r(S, b(xS), STOP) = maxy p(y | xS).

Optimal Value Function of Belief-MDP. We show the kstep truncated value function Vk over the belief-MDP state (S, b(xS)), where STOP is forced after k selections:

Here V0(S, b(xS)) = r(S, b(xS), STOP), p(xa | xS) is given by (5), and b(xS, a, xa) is the updated belief in (6).

Equivalence to the AFA Objective. Consider an acquisition episode for (x, y) ∼ p(x, y), and let T be the first step where STOP is chosen. The undiscounted return is Gπ(x, y) = ∑T -1 t=1 (-αcat ) +R(sT , STOP), where st = (St, xSt , xUt , y) is the state at step t. Hence -Ex,yEπ[Gπ(x, y)] is exactly the objective in (3); maximizing expected return is therefore equivalent to minimizing the AFA objective. This connection was first made in [Dulac-Arnold et al., 2012].

Model-Free vs. Model-Based Methods. Every AFA method needs a predictor for y to evaluate the stopping reward, typically through p(y | xS). We use model-based to denote methods that also explicitly model the unobserved features, e.g., p(xU | xS) or the marginals p(xa | xS) that determine the transition dynamics in (9). Exact POMDP planning is expressed in terms of the full belief b(xS) over (xU, y), which the Bellman recursion uses through the next-observation distribution p(xa | xS) and the predictive distribution p(y | xS) needed for the stopping reward. These quantities can be obtained in two ways: (i) By marginalizing the full joint belief p(xU , y | xS), which is maintained via sequential Bayesian updating (see (7)). (ii) By using predictive models that take xS (or an equivalent history encoding) as input to directly predict the marginals p(xa | xS) and p(y | xS). Model-free methods do not explicitly model the feature dynamics, but instead learn a policy directly from acquisition rollouts.

AFA as an MDP. As in any POMDP, the full actionobservation history induces a belief state and can be used to define a fully observable history-MDP. In AFA, this history has the compact form (S, xS): it records which features have been acquired and their values. Thus the corresponding MDP has states (S, xS) ∈ {(O, xO) : O ⊆ [d], xO ∈ XO}, and each state induces a unique belief b(xS). Its value function is exactly as in (9), with the belief terms understood as functions of the current MDP state (S, xS). Much prior AFA work effectively uses this MDP view, often without making the underlying POMDP explicit; in this survey, we make the POMDP formulation explicit because it clarifies the role of beliefs and the probabilistic quantities required for planning.

Reduced Sufficient Statistics under Conditional Independence. Under a Naive Bayes assumption, p(xa | xS, y) = p(xa | y), so xS affects future decisions only through the posterior p(y | xS). The information state can then be reduced from (S, b(xS)) to (S, p(y | xS)), which greatly improves tractability and explains why conditional independence assumptions are common in AFA [Liyanage and Zois, 2021].

Motivation for POMDP View of AFA. The MDP view over partial observations is conceptually simple, but highly intractable: the number of states (S, xS) grows combinatorially with d and becomes effectively infinite for continuous features. The POMDP perspective helps mitigate this by making the belief dynamics of sequential acquisition explicit and by clarifying which probabilistic quantities, such as p(xa | xS) and p(y | xS), must be estimated. It also exposes distributional conditions on p(x, y) under which reduced sufficient statistics can be used, as in the preceding paragraph, thereby reducing the search space for planning. It also emphasizes that planning can focus on reachable belief states along observed trajectories, rather than every possible subset-value pair. For discretized features, the AFA-POMDP admits the standard piecewise-linear structure of value functions over beliefs [Liyanage and Zois, 2021], which connects AFA to point-based and online POMDP solvers [Ross et al., 2008].

Properties of the AFA-POMDP. The AFA-POMDP has mixed observability: the agent observes (S, xS), while (xU , y) remains latent. Thus, AFA belongs to the class of mixedobservability MDPs (MOMDPs), where the belief only needs to track the latent components. It is also an informationgathering POMDP in a passive environment, since actions reveal features but do not alter the underlying instance. A distinctive property of the AFA-POMDP is that different belief marginals play different roles: the belief over unobserved features determines the observation distribution, and hence the transition dynamics of the belief-MDP in (9), while the label marginal determines the stopping reward in (8). Thus the reward is belief-dependent, and maximizing terminal reward often corresponds to reducing uncertainty in p(y | xS). This interpretation is not automatic in general POMDPs, where rewards and transitions need not decompose around information about the current belief over states. Finally, the explicit STOP action gives action-based termination, so the undiscounted objective can be viewed as a stochastic shortest path problem.

4 Myopic vs. Non-Myopic AFA

A policy can be derived from the value function Vk in (9) by defining the corresponding action-value function over (S, b(xS)). For a = STOP, Qk(S, b(xS), STOP) = V0(S, b(xS)) for all k. Then, for any a ∈ FB(S),

An optimal (deterministic) k-step truncated policy is then πk(S, b(xS)) ∈ argmaxa∈AB(S) Qk(S, b(xS), a). All AFA methods effectively amount to approximating the action-value function Q ≈ Qd (or directly the policy πd for policy-gradient methods) by making different modeling and computational choices. A natural approximation is Qk ≈ Qd for k < d.

Myopic AFA. The myopic approximation corresponds to the 1-step truncated action-value function Q1, replacing the continuation value Vk-1(S ∪ {a}, b(xS, a, xa)) in (10) with the value of stopping immediately after acquiring a. Concretely, Q1(S, b(xS), STOP) = r(S, b(xS), STOP), and for any a ∈ FB(S),

Computing Q1 requires no planning beyond the marginalization over xa. Assuming the log-loss stopping reward r(S, b(xS), STOP) = -H(y | xS), the benefit of acquiring feature a ∈ FB(S) over stopping is

I(y; xa | xS) is the conditional mutual information (CMI) between xa and y. Hence, the myopic CMI policy stops (a = STOP) if I(y; xa | xS) - αca ≤ 0 for all a ∈ FB(S), and selects the feasible feature with largest information gain (relative to its cost) about the label y otherwise. The myopic CMI policy is one of the most common heuristics in the AFA literature (often in combination with the Naive Bayes assumption), and often performs well. Other variants of this heuristic exist (e.g., I(y; xa | xS)/ca [Gadgil et al., 2024; Golovin and Krause, 2011]).

Non-Myopic AFA. The optimal action-value function in (10) and the myopic heuristic in (11) are at the two extreme ends of policies for AFA. However, it is often of interest to find a policy between these extreme ends that finds a balance between (i) computation time, and (ii) performance. To understand what makes a policy non-myopic (i.e., planning beyond a one-step lookahead), we consider the two-step truncated action-value function under log loss. For a ∈ FB(S), we have

(13) compares stopping after observing xa, with reward -H(y | xS, xa), against acquiring a second feature j and then stopping, with expected reward Exj|xS,xa [-H(y | xS, xa, xj)] minus the acquisition cost αcj . Equivalently, the incremental value of the second acquisition relative to stopping is I(y; xj | xS, xa) - αcj. The nested entropy term Exa|xS Exj|xS,xa [H(y | xS, xa, xj)] makes explicit that nonmyopic planning must account for interactions between a candidate feature a ∈ U and remaining unobserved features in U \ {a}. For example, two features a ̸= j can each be individually uninformative (small I(y; xa | xS) and I(y; xj | xS)) yet be jointly decisive, meaning H(y | xS, xa, xj) can drop close to zero, an effect the myopic one-step heuristic in (11) cannot capture. This motivates intermediate heuristics that condition on a small lookahead group O containing a and score a by

where a ∈ O ⊆ U. This score reasons about jointly informative feature groups by averaging the marginal utility of acquiring a over sampled partial completions xO\{a} of other unobserved features. It can also be viewed as a non-adaptive approximation to the value function, where a lookahead group is fixed or sampled rather than chosen adaptively after each observation. This will be discussed in detail in the extended version of this survey. The main difficulty is that selecting the subsets O to consider (and how to sample them) is problemdependent and can strongly affect performance.

5 AFAMethods

As discussed in Section 3, AFA is naturally a POMDP, and existing methods mainly differ in how they approximate the optimal action-value in (10). We group existing AFA methods into four categories: (i) embedded cost-aware predictors, where the model structure implicitly defines an acquisition trajectory; (ii) model-based methods, which estimate the probabilistic quantities of the POMDP (i.e., p(xU | xS)) and then find a policy via model-based planning; (iii) model-free methods, which learn a policy directly from acquisition rollouts; and (iv) hybrid methods, which combine acquisition rollouts with a learned model to improve stability. See Table 1 for a taxonomy of all papers. This taxonomy also parallels standard POMDP solution paradigms [Ross et al., 2008; Lauri et al., 2023] (often not stated in AFA papers). Some approaches are primarily offline (they learn or precompute a policy from training data or a learned model), while others are online (they plan at test time from the current state). In addition, some are myopic while others are non-myopic by planning over a longer future horizon.

5.1 Embedded Cost-Aware Predictors

Any deterministic AFA policy π can be represented as a decision tree [Quinlan, 1993]. At test time, a decision tree evaluates only a subset of features, thereby implementing adaptive, instance-wise feature acquisition within the model itself. Consequently, decision-tree learners that explicitly incorporate feature costs yield valid policies for AFA. This section covers such cost-aware decision tree methods. All methods in this section also fall under one of the broader (POMDP-based) categories introduced later, since they can be interpreted as approximations to the underlying POMDP for AFA (as any AFA policy can). We nevertheless present them as a separate category to emphasize that they are specific to decision tree learning. Moreover, in contrast to other AFA methods introduced later, they inherit familiar limitations of standard decision trees (e.g., overfitting and discretizing continuous features). Notably, they are rarely included in modern AFA benchmarks.

Cost-Sensitive Decision Trees and Ensembles. A standard decision tree is typically constructed myopically. For example, it decides which feature to split based on the feature with largest information gain I(y; xa | xS) [Quinlan, 1993]. An early example of a cost-sensitive decision tree is [Norton, 1989], where the split criterion now takes the cost of the feature into account as I(y; xa | xS)/ca (i.e., connected to the myopic CMI heuristic in (12)). This requires access to p(xa | xS) and p(y | xS), which are estimated from the empirical frequencies of the training examples that reach the current node (i.e., consistent with xS). This is a form of generative estimation of these probabilities. These methods hence also belong to the category myopic generative heuristics in Section 5.2. Other methods are similar in spirit, but consider other myopic costsensitive split criteria [N´u˜nez, 1991; Tan, 1990; Turney, 1995; Ling et al., 2004; Sheng and Ling, 2006; Ling et al., 2006; Yang et al., 2006]. Some of these methods also consider nonmyopic variants via lookahead during splits [Norton, 1989] or post-processing of the myopic tree by optimizing some global objective (e.g., (3)) [Turney, 1995]. This aligns them with one of the non-myopic heuristic categories discussed later. Notably, [Ling et al., 2006] rebuilds a cost-sensitive decision tree at test time after each feature is acquired, with cost of already acquired features set to zero. This corresponds to a kind of online planning (a common approach to solve complex POMDPs [Ross et al., 2008]).

This idea has also been extended to ensemble methods, e.g., random forests [Xu et al., 2012; Nan et al., 2015] and boosting methods [Peter et al., 2017]. The general idea is to build multiple cost-sensitive decision trees and combine them similar to standard ensemble methods. A feature is only acquired the first time it is used by a tree in the ensemble.

5.2 Model-BasedMethods

Model-based methods estimate the distribution over unobserved features given the observed features, p(xU | xS), to perform model-based planning in the AFA-POMDP (see Section 3). These estimates are needed to evaluate observation probabilities, belief updates, and lookahead values. The main difference across methods is how they approximate the actionvalue in (10), ranging from one-step proxies (myopic) to objectives that explicitly account for interactions with other unobserved features (non-myopic), and to explicit planning via dynamic programming or search (non-myopic).

Myopic Generative Heuristics. These methods use the myopic approximation in (11) (with different choices of the terminal reward r(S, b(xS), STOP) in (8)). Early methods include [Geman and Jedynak, 1996; Chai et al., 2004], both of which assume a Naive Bayes setting. [Ji and Carin, 2007] goes beyond the Naive Bayes assumption to richer classconditional generative models (e.g., IOHMM/HMM beliefs to compute both p(y | xS) and p(xa | xS)). More recently, deep models have been used to estimate these probabilities without making any simplifying assumptions. This is implemented using arbitrary-conditional deep generative models (e.g., Partial VAE) to approximate the required conditionals efficiently [Ma et al., 2019; Rangrej and Clark, 2021; Chattopadhyay et al., 2023b]. For these methods, the deep model learns to directly predict relevant probabilities for arbitrary subset xS, instead of sequential Bayesian updating. Consequently, they are very hard to train and often have difficulties converging.

Non-Myopic Generative Heuristics. The methods in this category are non-myopic because they consider the unobserved features beyond a one-step lookahead. However, they do not use standard POMDP planning to achieve this. Instead, they are non-myopic by exploiting the specific structure of the AFA problem (i.e., by estimating the joint informativeness of unobserved features, see discussion in Section 4).

[Bilgic and Getoor, 2007] estimate the joint informativeness of feature groups and then select a single feature from the most informative group. To make this tractable, they assume conditional independence among features. Subsequently, the EC2 objective was introduced in [Golovin and Krause, 2011] and used for AFA in [Rahbar et al., 2023; Rahbar et al., 2025]. EC2 prioritizes features that reduce uncertainty in both p(y | xS) (aligning with the myopic CMI rule in (12)) and p(x | xS) (rapidly eliminating feature vectors x ∈ X that are inconsistent with the observations). EC2 is also adaptive submodular [Golovin and Krause, 2011], which yields a near-optimality guarantee.

Recently, [Valancius et al., 2024] proposed a method that randomly samples subsets of unobserved feature indices from U. For each subset, it evaluates the features' joint informativeness about the label, then selects the most informative feature (under the myopic CMI rule) within the most informative subset. When log loss is used, this procedure is related to the non-myopic CMI heuristic in (14). To compute the required probabilities, they rely on neighborhood-based probability estimation: they identify instances close to xS and evaluate the objective using this local neighborhood. This approach is reminiscent of probability estimation in decision trees and avoids training a deep generative model for arbitrary S. [Huang et al., 2025] extend this framework by learning to identify subsets that outperform random sampling via an offline set-optimization problem. Similarly, [Norcliffe et al., 2025] use gradient-based local attributions and a deep generative model to estimate expectations over unobserved features in a latent space, which is related to (14) with gradient-based feature attributions replacing mutual information. Because these methods compute their scores at test time, they can be viewed as a form of online planning, as is common in expensive POMDP settings where full offline planning is intractable [Ross et al., 2008].

Dynamic Programming and Search. [Liyanage and Zois, 2021] proposes to solve the POMDP of AFA via dynamic programming. To make it tractable, they utilize (i) the piecewiselinear structure of the value function of the AFA-POMDP, and (ii) the reduced sufficient statistic via conditional independence as described in Section 3. An alternative is to discretize the information state via learned abstractions, for example using the leaves of decision trees as surrogate states [Maliah and Shani, 2018]. Moreover, the state space of the AFA-POMDP corresponds to an AND-OR graph. [Bayer-Zubek and Dietterich, 2005] proposes to search for a policy in this graph using the AO∗ search algorithm. They propose an admissible heuristic and statistical pruning to make it tractable.

5.3 Model-Free and HybridMethods

Model-free methods sidestep explicit probabilistic modeling of p(xU | xS), and instead learn acquisition behavior directly from data instances (x, y) ∼ p(x, y). Rather than estimating probabilities and plugging them into an acquisition objective, they learn to predict the value of actions in a given state (e.g., via an action-value function), typically using a neural network.

Myopic Discriminative Heuristics (Oracle Guided). Oracle guided methods can be viewed as imitation learning (often simple behavioral cloning) for AFA: using fully observed training instances, one simulates states (S, xS) along rollouts (see the MDP view of AFA in Section 3), computes an oracle action for each visited state, and trains a parametric policy to imitate this oracle. The oracle action is typically computed by utilizing the true label y and unobserved features xU of the instance (as both are assumed to be known in the offline setting). This perspective was made explicit early on by [He et al., 2012]. They can also be seen as simplified variants of the RL methods discussed later: rather than learning from delayed returns, they replace credit assignment with supervised oracle labels, which makes training easier but typically biases the learned policy toward the oracle's (often more myopic) structure.

[Covert et al., 2023] learns a policy network πθ (represented by a neural net). It simulates episodes on training instances by following πθ. At any state (S, xS), an action is drawn a ∼ πθ(S, xS). Subsequently, the loss ℓ(f(xS∪{a}), y) is computed in the resulting state. The policy parameters are then updated based on this loss. In essence, they allow gradients to backpropagate from the loss to the policy network via the reparameterization trick. The predictor f is also trained jointly. This is a unique aspect of the POMDP of AFA: we can optimize policies via gradient methods without having to rely on high-variance methods such as the REINFORCE algorithm [Ghosh and Lan, 2023]. This is because, via a continuous relaxation of the AFA problem, the terminal reward can be made differentiable w.r.t. the action. Moreover, [Covert et al., 2023] shows that this policy is equivalent to the selections made by the myopic CMI criterion in (12) (assuming log loss). Note that the method in [He et al., 2012] is very similar to this. Similar methods were concurrently proposed by [Ghosh and Lan, 2023] and [Chattopadhyay et al., 2023a]. [Gadgil et al., 2024] is closely related too, but it learns to predict the one-step action-value function instead of the policy directly.

Non-Myopic Discriminative Heuristics (Oracle Guided). The methods covered here are similar to those above, but they use a non-myopic oracle signal instead of a myopic one, yielding a non-myopic policy. The work in [He et al., 2016] simulates episodes on training instances (x, y) ∼ p(x, y). At any state (S, xS) during an episode, it executes each candidate action and rolls it out to termination to obtain a terminal loss. This yields a non-myopic signal for each action. Explainability-driven rankings provide another oracle signal: [Guney et al., 2025] compute local SHAP/LIME feature attributions on fully observed instances and train a policy to follow the highest-ranked unacquired feature. Because some explanation methods (notably SHAP) can reflect feature interactions and joint informativeness, the resulting signal may be non-myopic to a limited extent.

Model-Free RL. [Dulac-Arnold et al., 2012] were the first to show the connection between (3) and maximizing long-term reward in the corresponding MDP of AFA. Motivated by this connection, they use RL to learn a policy in a model-free way by simulating trajectories offline on fully observed data. They learn the predictor and policy jointly via approximate policy iteration. [R¨uckstieß et al., 2013] also uses model-free RL to solve the problem, but uses a slightly different state representation and uses fitted Q-iteration. More recently, it has also been extended to deep RL by, e.g., [Shim et al., 2018; Kachuee et al., 2019; Janisch et al., 2020] using deep RL algorithms such as DQN and PPO. [Aronsson and Chehreghani, 2026] also considers a continuous relaxation of the AFA problem, similar to [Covert et al., 2023; Ghosh and Lan, 2023]. However, it is non-myopic because gradients flow through the entire acquisition trajectory rather than a single acquisition step. It also focuses on the soft-budget setting, whereas these myopic relaxation-based methods are limited to hard budgets with uniform feature costs.

Model-Based RL (Hybrid). Some RL-based methods train an auxiliary surrogate model (for example, the PVAE in [Ma et al., 2019]) to approximate the conditional distribution p(xa | xS). This surrogate can improve training stability in otherwise model-free approaches. For instance, [Zannone et al., 2019] uses it to generate synthetic trajectories by sampling from p(xa | xS), though the empirical benefit of this augmentation appears limited [Sch¨utz et al., 2026]. By contrast, [Li and Oliva, 2021] uses the surrogate more directly to support learning, enriching the policy input (for example, with imputations and uncertainty summaries) and providing denser reward signals than those obtained from purely model-free rollouts. Although these methods learn a dynamics model (as model-based methods covered in Section 5.2), they remain primarily model-free RL, using it mainly to stabilize training.

6 Conclusion and Future Directions

This survey organizes AFA around its underlying POMDP structure, showing that most methods can be understood as different approximations to the same sequential decision problem. We introduced a unified taxonomy that separates four categories: (i) embedded cost-aware predictors, (ii) model-based methods, (iii) model-free methods, and (iv) hybrid methods. We hope this POMDP-centric view both clarifies existing work and motivates new AFA methods that more directly build on the mature literature on POMDP planning and approximation.

Despite substantial progress, several research directions remain open. First, recent myopic discriminative heuristics [Covert et al., 2023; Gadgil et al., 2024] often perform remarkably well on common AFA datasets, in many cases outperforming non-myopic approaches, including RL-based methods [Sch¨utz et al., 2026]. At the same time, it has been shown that when datasets are synthetically constructed so that optimal performance requires non-myopic selection, non-myopic methods expectedly outperform myopic ones [Sch¨utz et al., 2026; Aronsson and Chehreghani, 2026]. This motivates a more principled understanding of when non-myopic policies are necessary for a given data distribution p(x, y), and whether such insights can be used to decide when the additional complexity of non-myopic planning is justified.

Second, most AFA papers assume an offline setting with fully observed feature vectors, split into training and test sets for learning and evaluation. This can conflict with the premise that features are costly, and real datasets often have missing values (e.g., medical records include only ordered tests). Consequently, if a policy acquires a feature that is systematically missing in the logged data, it cannot be reliably evaluated. This motivates online and semi-offline settings and evaluation protocols that account for realistic logging and missingness. Notably, [von Kleist et al., 2025] studies this issue, and further work is needed to develop realistic AFA systems.

Third, most AFA methods come without performance guarantees. A notable exception constitutes the methods based on the EC2 objective [Rahbar et al., 2023; Rahbar et al., 2025], which admit near-optimality guarantees, but the objective is typically expensive to compute.

Due to space constraints, several specialized and less common AFA settings were not covered in depth here. In addition, many methods in Section 5 were covered only briefly, and a number of additional AFA works were omitted from this shorter version. The extended version of this survey will treat these works and settings in more detail and provides a more extensive discussion of future directions.

Acknowledgments

This work was partially supported by the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation. We would like to thank Daphney-Stavroula Zois for pointing us to a number of relevant works.