acceptodds
Under review as a conference paper at ICLR 2027

Non-Myopic Active Feature Acquisition via Pathwise Policy Gradients

Abstract

Active feature acquisition (AFA) considers prediction problems in which features are costly to obtain and the learner adaptively decides which feature values to acquire for each instance and when to stop and predict. In this paper, we introduce a continuous relaxation of the acquisition process that enables non-myopic pathwise policy gradients (NM-PPG) through the full acquisition trajectory, avoiding the high variance of standard score-function policy gradients while allowing end-to-end optimization of the acquisition policy. To better align training with deployment, we develop a straight-through rollout that follows discrete feature acquisitions in the forward pass while backpropagating through the corresponding soft relaxation. We derive an AFA-specific average-case upper bound on the variance of this gradient estimator, which characterizes instability and motivates staged temperature sharpening. Experiments on both synthetic and real-world datasets demonstrate that NM-PPG yields superior performance relative to state-of-the-art AFA baselines.

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
active learning, active feature acquisition, dynamic feature selection

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 2 reviews, above 85% of the others.
Reviewer_eKT5OpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies non-myopic active feature acquisition (AFA), where a policy sequentially selects costly features and decides when to stop and predict. The authors propose NM-PPG, which uses Gumbel-Softmax relaxation and straight-through estimation to enable pathwise gradients through complete feature-acquisition trajectories. The method further introduces survival-weighted stopping to support differentiable optimization of acquisition decisions and stopping behavior.

The paper provides theoretical results on relaxation consistency, gradient computation complexity, and an AFA-specific upper bound on gradient variance, which motivates staged temperature sharpening. Experiments on 12 synthetic and real-world datasets compare NM-PPG against seven baselines under both hard- and soft-budget settings. The proposed method achieves the highest overall average cost-performance AUC in both settings, although its advantage over the strongest non-myopic RL baseline is relatively modest.

Critical strengths
  1. Meaningful methodological contribution. The paper presents a reasonable approach to non-myopic AFA by enabling pathwise gradients through full acquisition trajectories, including differentiable stopping decisions.

  2. Solid theoretical and empirical evaluation. The paper provides theoretical analyses of gradient variance and computational complexity, along with extensive experiments across 12 datasets and seven baselines.

Critical weaknesses
  1. Insufficient isolation of the core contribution. The method combines several established techniques, but the benefit of full-trajectory pathwise gradients is not clearly isolated. A controlled comparison between one-step and full-trajectory gradients would strengthen the contribution. Moreover, the straight-through estimator introduces bias, while the theoretical analysis primarily focuses on variance.

  2. Limited practical gains relative to complexity. NM-PPG achieves only modest improvements over the strongest non-myopic RL baseline (GSMRL), despite introducing several additional training mechanisms. The ablations also suggest that some components are not consistently necessary. It remains unclear whether the added complexity is justified by the empirical gains.

Questions for authors

My main concern is whether NM-PPG offers a meaningful advantage over existing non-myopic RL methods such as GSMRL (PPO). The overall performance improvements are relatively modest, and the training time is not consistently lower. Moreover, the proposed straight-through estimator introduces bias while reducing gradient variance.

Could the authors clarify what fundamental limitation of conventional RL is addressed by NM-PPG, and under what conditions the proposed approach is expected to perform better? In particular, is there evidence that the pathwise formulation provides meaningful advantages in training stability, sample efficiency, or optimization quality?

A convincing clarification of these advantages would substantially strengthen my assessment of the paper.

2 comments
AuthorsOpenReview ↗

Response to reviewer eKT5

We thank the reviewer for the insightful feedback. All new results are included in Appendix G of updated PDF.

Q1: My main concern is whether NM-PPG offers a meaningful advantage over existing non-myopic RL methods such as GSMRL (PPO).

See response to question Q3 for Reviewer c1k6 regarding GSMRL

Q2: Could the authors clarify what fundamental limitation of conventional RL is addressed by NM-PPG, and under what conditions the proposed approach is expected to perform better? In particular, is there evidence that the pathwise formulation provides meaningful advantages in training stability, sample efficiency, or optimization quality?

Generic RL methods, e.g. value based methods like DQN or methods that compute policy gradients based on the score function like PPO, infer long-term action effects from sampled returns or learned value estimates. This can lead to large variance, and learning can become unstable, in particular in larger state spaces. There are a number of works in the RL literature that instead propose to compute policy gradients where gradients are propagated directly through the transition dynamics of the MDP (sometimes referred to as pathwise gradients). This provides direct temporal credit assignment without a learned critic. I.e. it provides richer local gradient information at every step of the acquisition process, which reduces variance of the gradient estimator and often makes learning more stable. However, this is only possible if the full dynamics of the MDP is differentiable. In this paper, we propose a continuous relaxation of the AFA acquisition process such that pathwise gradients can be utilized in the context of AFA. This is mainly motivated by the fact that existing non-myopic methods that use generic RL are often unstable, because the state space of the AFA MDP is very large (exponential in number of features).

This is also supported by our experimental evaluation. Our method (NM-PPG), clearly outperforms the RL baselines (OL which uses DQN and GSMRL which uses PPO) on higher-dimensional datasets like MNIST and Fashion-MNIST.

In the paper, we emphasize that our method NM-PPG is the only method which performs consistently well across many different settings, including: soft-budget, hard-budget, datasets with myopic structure, datasets with non-myopic structure, and high-dimensional datasets where the state space is very large. Existing baselines struggle in at least one of these scenarios.

Q3: The straight-through estimator introduces bias, while the theoretical analysis primarily focuses on variance.

See response to question Q4 for Reviewer c1k6.

Thank you for the clarification. The response helps me better appreciate the motivation and design of NM-PPG. I particularly appreciate the simple and direct idea of exploiting the differentiable structure of the feature acquisition process to enable pathwise gradient optimization over complete trajectories, rather than relying solely on sampled returns as in conventional RL methods. The results on MNIST and Fashion-MNIST also provide encouraging evidence of its advantages over PPO in high-dimensional settings.

While the bias introduced by the straight-through estimator and the necessity of some additional components remain interesting aspects for further investigation, I do not consider them fundamental issues that undermine the contribution.

Overall, I find the proposed method simple, intuitive, and meaningful. The authors' clarification has addressed my main concern regarding its advantages over existing RL methods, and I am willing to raise my rating from Weak Reject to Weak Accept.

Reviewer_5GUDOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The authors focus on the problem of adaptive feature acquisition (AFA). Arguing that myopic feature selection is too limited, they formulate the problem as a policy-gradient method that learns from training-time transitions, relying on a Gumbel-Softmax approach to avoid high-variance gradients. The proposed method is evaluated on a wide range of benchmarks against a broad set of baselines.

Critical strengths
  • Well-written and well-motivated method for non-myopic AFA.
  • Careful evaluation. The evaluation is very extensive with respect to both the number of benchmarks and the baselines in various settings.
Critical weaknesses
  • Despite the strong claims of superiority, the method performs essentially on par with or only slightly better than GSMRL, and of its components, only removing the entropy regularization has any serious impact on performance (see the ablation in Figure 5).
Questions for authors
  1. Importance of the components: In the ablations, only removing the entropy regularizer significantly changes the performance of the method.
    In the synthetic cases, it barely improves upon the existing non-myopic GSMRL approach, while in the hard-budget cases, the myopic GFDS performs identically (within one standard deviation). Can the authors clarify which component of their approach is the most important?
  2. Most results report normalized AUC, yet how it is computed is never defined in the paper. Can the authors provide further details on that?

Minor

  • Please include the seed variance in the main paper, not just the appendix, as several performance differences disappear when accounting for seed variance.
13 comments
AuthorsOpenReview ↗

Response to reviewer 5GUD

We thank the reviewer for the good feedback. All new results are included in Appendix G of updated PDF.

Q1: Importance of the components: In the ablations, only removing the entropy regularizer significantly changes the performance of the method.

The ablation study in Figure 5 studies the following components: entropy regularization, no ST-rollout, and using a fixed value of the temperature τsoft\tau_{\text{soft}}. No ST-rollout means we optimize the relaxed rollout in Eq. 8 directly, without the added ST forward pass introduced in Section 3.3. A fixed τsoft\tau_{\text{soft}} means we do not modify τsoft\tau_{\text{soft}} during training unlike standard NM-PPG which decreases τsoft\tau_{\text{soft}} over time to reduce bias (see training in Alg. 1 for details).

The performance of standard NM-PPG (with these components included) does perform consistently better than without them. However, as you correctly point out, removing these components does not significantly impact performance on some datasets (although, it importantly does not make performance worse). The reason is as follows. The role of both (1) the staged temperature sharpening in Alg. 1 and (2) the ST-rollout is to reduce the relaxation bias introduced by our continuous AFA process in Eq. 8. Hence, when we remove the ST-rollout, the staged temperature sharpening likely reduces bias sufficiently by itself such that the performance remains quite good. In addition, for the fixed τsoft\tau_{\text{soft}} ablation, we specifically use the value of τsoft\tau_{\text{soft}} found by standard NM-PPG (during staged temperature sharpening). This means it can be understood as a very well tuned value of τsoft\tau_{\text{soft}}. This leads to decent performance on a number of datasets, but we also see that the performance is clearly worse on a number of datasets with fixed τsoft\tau_{\text{soft}}. This further motivates the temperature sharpening used by NM-PPG rather than using one fixed temperature (as motivated by Theorem 3).

In addition, these ablation methods should also be viewed as alternative and novel variations of our method NM-PPG. In other words, they are not existing methods in the literature, but rather other interesting alternatives to optimize Eq. 8 that are interesting to further investigate in future work. The core component of our method is optimization of Eq. 8 itself. In other words, the core components that make our method superior to baselines is the fact that (1) it performs non-myopic planning, and (2) it performs the non-myopic planning via pathwise policy gradients using a continuous relaxation of the AFA process (rather than generic large variance RL methods).

Finally, the ST-rollout is also very well motivated theoretically. It is well known that such straight-throught estimators are very effective at reducing bias introduced by continuous relaxations, both in the broader machine learning literature and also in the context of AFA (see the DiFA baseline in our paper for example).

Q2: In the synthetic cases, it barely improves upon the existing non-myopic GSMRL approach, while in the hard-budget cases, the myopic GFDS performs identically (within one standard deviation).

See response to question Q3 for Reviewer c1k6 regarding GSMRL.

For GDFS (and other myopic baselines), the performance is significantly worse compared to NM-PPG on synthetic datasets. This proves our method is capable of identifying non-myopic structure in datasets, unlike these myopic baselines. For the real-world datasets in the hard-budget setting, the performance of NM-PPG is still better, but myopic baselines are quite close as you point out. This can, for example, happen for the following three reasons: (1) the optimal policy for a dataset is myopic, (2) the optimal policy for a dataset is non-myopic, but there exist myopic policies that are close in performance. This can for example be seen for the datasets Mortality, Diabetes and Metabric (see analysis in Appendix E.4.5). (3) The optimal policy for a dataset requires non-myopic instance-adaptive stopping for best possible performance. This can not be captured in the hard-budget setting, since there is no learned stopping in this case. However, in the soft-budget setting, where learned stopping is present, the benefit of our method over the myopic baselines is more clear.

In the paper, we emphasize that our method NM-PPG is the only method which performs consistently well across many different settings, including: soft-budget, hard-budget, datasets with myopic structure, datasets with non-myopic structure, and high-dimensional datasets where the state space is very large. Existing baselines struggle in at least one of these scenarios.

AuthorsOpenReview ↗

Response to reviewer 5GUD (continued)

Q3: Most results report normalized AUC, yet how it is computed is never defined in the paper. Can the authors provide further details on that?

It is a standard normalized area under the curve (AUC) metric. The curve we compute the area under is simply the cost-performance curve produced by a method on a particular dataset (i.e. the curves in Figure 1). The metric is then computed in a standard way given such a curve. The metric quantifies the performance of a method across different costs for a particular dataset. It is a commonly used metric in previous work on AFA

I would still appreciate an actual answer with a definition beyond "a standard way". I might just be missing the obvious, but for Figure 1, the ranges differ vastly, as does the α\alpha grid for each method (α\alpha's meaning even differs between methods, as discussed in E.1.4). Table 4 looks to me as if every method was averaged over its own cost range. If that is the case, then the AUCs are not comparable across methods, and it could also explain the finding that AUCs are higher under soft budgets than under hard ones. I would therefore appreciate an answer that clarifies the integration ranges, normalization, and interpolation/extrapolation. If I merely misunderstood something, that's great news, but if not, I need to know whether I can trust the results.

Comments on the paper

6 comments
AuthorsOpenReview ↗

Response to reviewer c1k6

We thank the reviewer for the detailed and insightful feedback. All new results are included in Appendix G of updated PDF.

Q1: Role of non-myopic planning is not isolated, can we report NM-PPG with h=1h=1 using the rooted estimator of Appendix B, keeping all other components fixed?

We have experiments running for the baseline suggested by the reviewer (for soft-budget, see below), and will report them as soon as possible. (EDIT: see Appendix G of updated PDF for results). However, see discussion below.

As discussed in Appendix B, the rooted estimator introduced in the same appendix is different to the estimator used by NM-PPG (even at h=kh=k). We simply include this to (1) suggest how to compute pathwise gradients for arbitrary planning depth hh, and (2) to highlight the computational benefit of NM-PPG (see Proposition 2). Hence, the suggested baseline would not be “NM-PPG with h=1h=1”. It would be a different (and novel) estimator altogether. In the paper, the goal was to compare our method to existing methods in the AFA literature.

Notably, in the hard-budget case where there is no learned stopping (α=0\alpha=0), the rooted estimator would in fact be equivalent to DiFA with a ST-rollout, and equivalent to GDFS without a ST-rollout (see Proposition 4 in Appendix B). Thus, in the hard-budget case, these two baselines already provide results for the baseline suggested by the reviewer.

In addition, DIME is a myopic method which does include learned stopping. I.e., it was proposed for the soft-budget setting in the original paper, but does not use pathwise gradients (it is a value-based method). The performance of DIME is hence representative of the suggested baseline in the soft-budget case (since training of myopic methods are typically stable regardless of optimization method).

Furthermore, as noted by the reviewer, in the experiments we report non-myopic behavior on 7 out of the 12 datasets: Cube-NM (σ=0.1\sigma=0.1), Cube-NM (σ=0.2\sigma=0.2), Syn1, Syn3, Mortality, Diabetes, Metabric (the 4 synthetic datasets, and 3 of the real-world datasets). This is supported by the analysis of acquisition paths in Appendix E.4.5. Our method finds a non-myopic policy on these datasets, which none of the myopic baselines (DiFA, GDFS, DIME) find. This analysis isolates the role of non-myopic planning, because we see clear improved performance of our method with concrete evidence that it finds a non-myopic policy unlike the myopic baselines.

For the remaining datasets, it is a bit harder to analyze acquisition paths due to large number of features or unclear meaning of each feature. For these datasets, we agree that it is unclear if the improved performance comes from the non-myopic planning of our method or other components. However, as argued above, the results of GDFS, DiFA, and DIME should confirm that the benefit is still about non-myopic planning. In particular since the other components mentioned by the reviewer are kept as consistent as possible between NM-PPG and all the baselines.

Q2: In the soft-budget setting, how much of NM-PPG's advantage over GDFS, DiFA and SEFA comes from learned stopping rather than from non-myopic acquisition? For example, what happens if NM-PPG uses the same entropy-threshold stopping, or if GDFS is equipped with a learned stopping head?

Firstly, in the hard-budget case α=0\alpha=0, there is no learned stopping, and we still see a benefit of our method. In the soft-budget case, as argued in the previous question, DIME is a representative (myopic) baseline with principled learned stopping. Our method NM-PPG clearly outperforms DIME across datasets.

Despite this, we have started some experiments with NM-PPG using entropy-threshold stopping (EDIT: see Appendix G of updated PDF for results). Moreover, GDFS equipped with learned stopping is essentially the baseline suggested in the previous question (except we include ST-rollout, so it is more DiFA with learned stopping).

AuthorsOpenReview ↗

Response to reviewer c1k6 (continued)

Q3: The gains over the strongest non-myopic baseline (GSMRL) are marginal

The table below compares the performance of NM-PPG and GSMRL, since the reviewer specifically asked for this. There are 12 datasets in total.

The first column shows the number of datasets where NM-PPG had larger AUC than GSMRL. The second column shows the number of datasets where the difference in AUC between NM-PPG and GSMRL exceeds one standard deviation (the maximum standard deviation of the two methods). This is specifically what the reviewer asked for. The third and fourth columns show the same thing, but for GSMRL. The fifth column shows the number of datasets where their AUC was the same (tie).

SettingNM-PPG: higher AUCNM-PPG: advantage >1 SDGSMRL: higher AUCGSMRL: advantage >1 SDTies
Soft budget84410
Hard budget75401

From the table we observe that NM-PPG achieves higher AUC on twice as many datasets compared to GSMRL. Moreover, we observe that the advantage of NM-PPG is larger than a standard deviation for 4 datasets in the soft-budget setting and 5 datasets in the hard-budget setting. In contrast, the benefit of GSMRL over NM-PPG is never more than one standard deviation, except for one dataset in the soft-budget setting.

The datasets where the advantage of NM-PPG exceeds one standard deviation are:

For soft-budget: Connect4, EngineFaultDB, MNIST, Fashion-MNIST

For hard-budget: Syn1, Connect4, Diabetes, MNIST, Fashion-MNIST

In the paper, we emphasize that our method NM-PPG is the only method which performs consistently well across many different settings, including: soft-budget, hard-budget, datasets with myopic structure, datasets with non-myopic structure, and high-dimensional datasets where the state space is very large.

Existing baselines struggle in at least one of these scenarios. GSMRL primarily struggles in larger state spaces. This is evident by the fact that it is clearly worse than NM-PPG on datasets like Connect4, MNIST, Fashion-MNIST, which are higher dimensional datasets. This can be seen both in Table 4, and also in the plots in Figure 4 in Appendix E. In AFA, the size of the state space is exponential in the number of features. This is also consistent with the broader (PO)MDP literature, where policy gradient methods that use score-function estimators (like PPO, used by GSMRL) can be very unstable (due to large variance) in larger state spaces.

Based on this discussion, we would consider NM-PPG superior to GSMRL in terms of performance. However, the contribution here goes beyond better empirical performance. The benefit of pathwise gradients to obtain more stable training compared to score-function gradient estimators (and value-based RL methods) is well known in the broader (PO)MDP literature. Our paper provides the foundations for pathwise gradients in the context of AFA. We strongly believe that these foundations will inspire a lot of interesting future work in the context of AFA.

AuthorsOpenReview ↗

Response to reviewer c1k6 (continued)

Q4: The theory does not address the estimator's main risk, its bias. Theorem 3 bounds only the variance of a biased straight-through surrogate, depends on unspecified constants and an exponential factor that seems vacuous at the final temperature, and is never checked numerically. Theorem 2 covers the fully relaxed objective rather than the straight-through surrogate actually used for training.

Firstly, the purpose of Theorem 2 is to confirm that the proposed continuous relaxation of the AFA acquisition process is reasonable. We confirm this by showing that it converges to the true discrete process as the temperature goes to zero. Moreover, the ST surrogate only impacts the forward pass (to reduce bias). The fully relaxed objective (addressed by Theorem 2), is still used in the backward pass when gradients are computed w.r.t. the ST surrogate.

Moreover, essentially no prior AFA work offers any theoretical analysis of their proposed method. This is primarily due to the complexity of the problem (the state space grows exponentially with number of features). We are the first to attempt to offer some theoretical insight into the behavior of our method.

We do not claim that the bound in Theorem 3 is guaranteed to be tight, but simply that it provides intuition into what impacts the variance of our gradient estimator. This is useful because it provides insight into what should be controlled during training to keep variance low, which can stabilize learning. This ultimately motivates our staged temperature sharpening during training (and may inspire future bounds and training algorithms for AFA).

As discussed below the bound in Theorem 3, the analysis exploits AFA-specific structure in the transition dynamics, removing sources of amplification that variance bounds from the broader literature on continuous MDPs must take into account (see e.g. (Zhang et al., 2023a;b) cited in the paper). This allows us to derive an average-case bound along realized trajectories, rather than repeatedly applying the same worst-case sensitivity as in the existing works on generic MDPs discussed in the paper.

A bound on the bias of our gradient estimator is a significantly more complex problem. The reason is that one has to keep track of the mismatch between our surrogate estimator and the true discrete estimator across an adaptive trajectory. We hence leave this to future work, but believe that some of the ideas in our bound can be used to derive a bound on the bias. In addition, the fact that our method is consistent with or better than all baselines across all datasets/settings, is clear evidence that the introduced bias is not an issue in practice. The bias is primarily addressed by the ST-rollout and the staged temperature sharpening during training.

We are running experiments to numerically investigate the bound, see next question. (EDIT: see Appendix G of updated PDF for results).

Q5: Can you evaluate (or estimate) the bound's right-hand side. It is hard to see what Thm. 3 adds beyond the known local O(1/τ)O(1/\tau) rate.

We have experiments running to evaluate the right-hand side of the bound, they will be added to Appendix G when finished. Regarding the last sentence, please see answer to the previous question for discussion about the usefulness of the bound. (EDIT: see Appendix G of updated PDF for results).

Q6: More detailed investigation of variance and bias

We have experiments running that compute the quantities suggested by the reviewer. This will include cosine similarity between ∇STJˉ\nabla^{ST}\bar J and ∇J(πθ)\nabla J(\pi_{\theta}), and extended version of Figure 6 that includes the variance of the PPO+GAE method. (EDIT: see Appendix G of updated PDF for results).

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.