acceptodds
Under review as a conference paper at ICLR 2027

-CMI: Non-Myopic Active Feature Acquisition via Probabilistic Lookahead

Abstract

Active Feature Acquisition (AFA) is a sequential decision-making process that selectively acquires unobserved features for each data instance independently to improve predictive performance under a limited acquisition budget. A common approach is to greedily select the next feature by maximizing its conditional mutual information (CMI) with the prediction target given the currently observed features. However, this criterion considers only the immediate information gain of each candidate feature and may therefore overlook feature interactions, where a feature becomes more informative when considered jointly with other features that may be acquired subsequently. To address this limitation, we propose -CMI, a generalization of the CMI acquisition criterion that evaluates candidate features under probabilistically sampled future observation contexts. -CMI provides a continuous spectrum of lookahead, ranging from evaluating a candidate's immediate information gain through Greedy CMI () to evaluating its information gain under the fully sampled future context of all remaining features (). Crucially, -CMI can be incorporated into existing CMI-based AFA methods in a plug-and-play manner, requiring only minor modifications to their acquisition criteria and no additional model retraining. We provide a theoretical analysis characterizing the acquisition behavior induced by -CMI, demonstrate its ability to capture feature interactions on diverse synthetic datasets, and show consistent improvements in early-stage acquisition performance across diverse real-world datasets and CMI-based backbones. Code is available https://anonymous.4open.science/r/gamma-cmi-E3EE/here.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
Active Feature Acquisition, Dynamic Feature Acquisition, Conditional Mutual Information, Feature Interactions

Reviews

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

The paper addresses limitations of traditional greedy CMI-based AFA policy optimization by constructing an objective that incorporates unseen features, where the number of included features is controlled by a γ\gamma regularizer. This novel objective can be interpreted as an additional lookahead term that captures interactions between the candidate feature and other unobserved features. The proposed method is experimentally validated to assess whether it can capture synergistic information on synthetic tasks, and real-world performance is also validated where gamma-CMI provides reliable gains relative to both generative and amortized approaches.

Critical strengths
  • The authors propose a practical method without significant implementation burden for incorporating lookahead signal in the AFA optimization that extends current CMI approaches

  • The authors provide interesting and novel theoretical insights about γ\gamma-CMI by decomposing the objective into a sum of all rr cardinality subsets of feature interactions, and also provides insights to connections to alternative objectives of feature acquisition such as reinforcement learning and Shapley values.

  • The paper is clearly written and well organized. For example, the modification to existing methods is clearly delineated in Algorithm 1, and the results are organized into key takeaways and insights.

Critical weaknesses
  • Reliance on a conditional generative model for unseen features given the observed features leads to a potential tradeoff in performance as γ\gamma is increased and the model approximation error accumulates. However, this tradeoff is characterized both theoretically and empirically.

  • Evaluating each feature candidate requires approximating expectations over M mask draws by performing forward passes for P(Y∣Xo,Xs)P(Y \mid X_o,X_s ) and P(Y∣Xi,Xo,Xs)P(Y \mid X_i,X_o,X_s ). While computationally intensive and difficult to scale in feature dimensionality, this is a standard limitation of generative frameworks that does not undermine the core conceptual contributions. However, it would be helpful to include a brief discussion of this practical limitation in the text.

Questions for authors

Clarification requests and missing details:

  • How was γ\gamma-CMI integrated into non-generative approaches (such as DIME and GDFS)? Specifically, given that γ\gamma-CMI generates MM hypothetical contexts of imputed unobserved features across varying cardinalities, how are these aggregated via the policy or reward model to yield a score for each candidate or select the optimal acquisition at each step?

  • Was M=5M=5 used across all real-world experiments? If so, this number of evaluated trajectories appears quite low for reliably uncovering complex feature interactions. Could increasing MM reduce estimation variance and thereby broaden or stabilize the tolerance for γ\gamma?

  • For the real world experiments, is it possible to provide the generative model error (i.e. average log loss) across the methods (or even just VAE)? It may be useful to see if the benefits of lookahead and γ\gamma is correlated with the ability to model the conditional feature distributions in Table 1/2 and Appendix I.

  • Additionally, would it be possible to provide the full performance curves (e.g., log loss, AUROC, or accuracy) across each acquisition step for the real-world experiments? While the conceptual contributions and empirical gains are already substantial, seeing these curves would provide insight into whether feature interactions are both helpful and captured early in the acquisition trajectory on real-world settings. My sense is that interactions may not always be helpful depending on the dataset and error of the generative model.

6 comments

We sincerely thank the reviewer for the positive evaluation of our paper. We have revised several parts of the manuscript to address the points raised, with the changes highlighted in blue for ease of reference. Below, we provide detailed responses to the reviewer's comments and questions.

[W1 & W2] Discussion on Generative Models

As the reviewer pointed out, the trade-off between γ\gamma and predictive performance, as well as the increased computational cost and scalability challenges as feature dimensionality grows, are fundamental limitations associated with the use of generative models. We have added further discussion of these limitations in Appendix B and referred to it in Section 3 of the main text. We thank the reviewer for encouraging us to elaborate on these practical considerations.

[Q1] Application of γ\gamma-CMI to DIME and GDFS

For methods that do not use generative models, such as DIME and GDFS, the currently observed feature values and observation mask are provided as inputs to compute candidate-specific acquisition scores, and the feature with the highest score is selected for acquisition. To apply γ\gamma-CMI to these methods, we first obtain KK samples generated by a VAE conditioned on the current observations. We then construct hypothetical future contexts for each generated sample by independently sampling M=5M= 5 future masks, where each unobserved feature is included with probability γ\gamma. When evaluating a candidate feature, that feature is excluded from the corresponding context. For each context, we compute either DIME's value-based score or the raw logits produced by GDFS's selector, and average these scores over the generated samples and future masks. Finally, we acquire the currently unobserved candidate feature with the highest average score, thereby incorporating hypothetical future observations into the acquisition decision.

However, directly introducing VAE-generated inputs may cause out-of-distribution (OOD) issues for DIME and GDFS, as these models were not originally trained on such inputs. To mitigate this issue, we additionally performed fine-tuning to align the models with the generated inputs. Since these experiments were intended as an exploratory investigation of whether our approach could also be applied to CMI-based methods that do not use generative models, we exceptionally performed fine-tuning in this setting, unlike the experiments with generative-model-based methods. Extending γ\gamma-CMI to these methods without introducing an additional VAE remains an important direction for future research. Furthermore, to distinguish whether the performance improvements of these two models were simply attributable to fine-tuning, we conducted the following additional experiments. Please refer to [W5 & Q3] in our response to Reviewer s3A4 for additional experiments.

[Q2] Whether MM = 5 Was Used Consistently Across All Experiments

We used MM = 5 in all experiments involving both synthetic and real-world datasets.

Also, we would like to clarify a potentially misleading description of mask sampling in our original manuscript. In the actual implementation, all samples generated by the generative model do not share the same set of MM masks. Instead, MM masks are independently sampled for each generated sample. Therefore, if KK denotes the number of samples produced by the generative model, up to KMKM distinct masks can be sampled. Since masks are sampled independently for each generated sample, even MM = 1 allows up to KK distinct masks to be evaluated. Compared with sharing a single mask across all generated samples, this enables the method to consider a wider variety of hypothetical future contexts. To avoid further confusion, we have revised the pseudocode and clarified this point in the manuscript. Notably, even with MM = 1, γ\gamma-CMI can improve acquisition performance while incurring virtually the same computational cost as Greedy CMI.

Regarding the choice of MM, we considered M=1,5,10,M = 1, 5, 10, and 2020. The resulting average standard deviations in performance for each MM are summarized below.

TaskM=1M=1M=5M=5M=10M=10M=20M=20
Overall (12 datasets)0.0057430.0051590.0050960.004528

We also report the average performance differences relative to MM = 5 below.

TaskM=1M=1M=5M=5M=10M=10M=20M=20
Overall (12 datasets)−0.277%0.000% (baseline)+0.074%+0.109%

We additionally measured the wall-clock time overhead for each value of MM, as shown below.

TaskM=1M=1M=5M=5M=10M=10M=20M=20
Overall (12 datasets)1.01±0.08×1.01 \pm 0.08\times1.08±0.18×1.08 \pm 0.18\times1.44±0.40×1.44 \pm 0.40\times1.87±0.79×1.87 \pm 0.79\times

The wall-clock time overhead starts at a level comparable to Greedy CMI when M=1M=1 and gradually increases with MM. We selected M=5M=5 by considering the trade-off between Monte Carlo estimation accuracy and increased wall-clock time overhead.

Also, in Table J.1 of the original manuscript, we labeled Greedy as M=1M=1. However, since Greedy does not consider diverse future contexts, we have refined the notation for clarity in the revised manuscript.

[Q3] Conditional Distribution Quality and Lookahead Performance

To examine how the quality of the conditional distributions learned by the generator relates to lookahead performance, we have added new experiments using VAE on all 12 real-world datasets to Appendix K.3 of the revised manuscript (Figures K.3 and K.4). Within each model repeat, we held the predictor fixed and varied only the generator, comparing the existing saved checkpoint (the reference) with generator checkpoints from epochs 1, 5, and 120 (the final epoch).

In the additional figures, dashed lines represent the reference, while solid lines represent the checkpoints from different epochs. The legends report the Energy Score (ES), a sample-based multivariate scoring rule (Gneiting and Raftery, 2007, Section 4.3). The energy score is computed as ES(Q,xU)=E[d(X,xU)]−12E[d(X,X′)]\mathrm{ES}(Q,x_U)=\mathbb{E}[d(X,x_U)]-\frac{1}{2}\mathbb{E}[d(X,X')], where XX and X′X' are independent samples from the conditional generative distribution QQ, xUx_U is the true unobserved feature vector, and dd is the distance used for evaluation. Lower ES indicates better conditional predictive quality. ES is evaluated on the same validation examples using identical observation masks across all generator checkpoints. The horizontal axis shows γ\gamma, and the vertical axis shows test performance averaged over all acquisition steps, consistent with Figures I.2–I.3. Each curve is averaged over five model repeats.

Across several datasets, the overall pattern of performance as a function of γ\gamma is preserved across generator checkpoints. On Bank Marketing, each evaluated checkpoint benefits from using a positive value of γ\gamma rather than γ=0\gamma=0, whereas on MNIST, performance consistently declines beyond small values of γ\gamma. Although the broad trends across γ\gamma are often preserved, the magnitude of the performance change varies across generator checkpoints. On Kin8nm and White Wine Quality, early checkpoints with higher ES exhibit relatively worse performance at large γ\gamma. On Parkinson, checkpoints with higher ES also show smaller improvements from lookahead.

Conversely, on Bank Marketing and MiniBooNE, improvements over γ=0\gamma=0 are maintained, or even become larger in some cases, for checkpoints with higher ES. Thus, across the datasets and checkpoints examined, we did not observe a consistent monotonic relationship in which greater generative error invariably leads to smaller lookahead gains.

These results suggest that the ability to model conditional distributions can affect the effectiveness of lookahead, but the measured average ES alone is insufficient to explain the favorable range of γ\gamma or the magnitude of the performance gains. Interaction structures, including synergy and redundancy, may also shape the information that lookahead can exploit. Consequently, improved generative model quality need not translate into greater lookahead gains. For example, even when generative model error decreases, additional gains may remain limited if there is little room to improve the acquisition order by considering future contexts.

Reference

Gneiting, T., & Raftery, A. E. (2007). Strictly proper scoring rules, prediction, and estimation. Journal of the American Statistical Association, 102(477), 359–378.

Reviewer_s3A4OpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper proposes γ\gamma-CMI, a new acquisition score for CMI-based active feature acquisition. For each candidate feature, it samples a random "future context" in which every other unobserved feature is included with probability γ\gamma, imputes those features with the backbone's generative model, and averages the candidate's CMI with the label over these contexts (Eq. 4). Setting γ=0\gamma = 0 recovers greedy CMI. Proposition 3.1 shows that an interaction of order r enters the score with weight γr−1\gamma^{r-1}, and Appendix A links the score to the Banzhaf and Shapley values. On synthetic data with oracle models, larger γ\gamma finds synergistic features earlier. On 12 tabular datasets, plugging γ\gamma-CMI into six CMI-based methods, with γ\gamma tuned on validation, gives mostly small gains.

Critical strengths
  • The idea is simple, and it plugs into existing CMI-based methods without retraining the generative backbones.
  • The synthetic experiments are well designed. Oracle models isolate the effect of the criterion, and the synergy and redundancy sweeps clearly show what γ\gamma does.
  • The paper is clearly written and marks the cells where γ\gamma-CMI does not help.
Critical weaknesses

1. The theory is largely known. With v(S) = I(Y; X_S | x_O), the γ\gamma-CMI score is a feature's expected marginal contribution when every other feature joins independently with probability γ\gamma. This is the gradient of Owen's (1972) multilinear extension of v, a standard probabilistic value, and Proposition 3.1 and the Banzhaf and Shapley connections follow directly from it. Appendix A.2 mentions probabilistic values, but the main text presents Proposition 3.1 as a new result, and the classical sources are not cited. Moreover, Proposition B.1 holds by construction, and Corollary B.2 is the generic fact that an argmax survives a small enough perturbation. None of the results says when a given γ\gamma leads to a better policy.

2. The method does not actually look ahead. The future context is a random subset of all unobserved features, chosen without regard to the budget or to which features the policy will acquire next. At γ\gamma near 1, it conditions on almost every noise feature. A real lookahead, even a two-step greedy search, would condition on the features the policy is likely to acquire. γ\gamma-CMI is better described as a budget-agnostic reweighting of interaction orders, so the "non-myopic" and "lookahead" framing overstates it.

3. Non-myopic baselines are missing. Every comparison is against the greedy version of the same backbone. Since the claim is about non-myopia, the paper should compare with methods built for it, such as RL-based AFA (JAFA Shim et al., 2018, GSMRL Li et al., 2020), the nongreedy approach of Valancius et al. (2024), or SEFA (Norcliffe et al., 2025), which the paper cites as motivation. A two-step lookahead that scores each feature by its best pairwise CMI would also directly handle the XOR-style synergy in the synthetic tasks. Without these baselines, it is unclear whether γ\gamma-CMI is a good way to be non-myopic or only better than greedy.

4. The real-world gains are small. γ\gamma is selected on validation from a grid that includes 0 (L733-735), so the method can always fall back to greedy. Even so, 15 of the 72 cells in Tables 1-2 are unchanged, two get worse, and most remaining gains are within one standard deviation (e.g., EDDI on MiniBooNE, 0.854 ± 0.024 to 0.859 ± 0.029). No paired test is reported. Moreover, the tables average only over the first half of the acquisition steps (L463-464). Over the full trajectory, the effect almost disappears: for VAE on Bank Marketing, AUROC spans only 0.883 to 0.887 across all γ\gamma (Figure I.2). In addition, the largest gain, ACFlow on Bank Marketing (0.690 to 0.811), comes from a backbone much weaker than the others on that dataset (0.849 for VAE).

5. The amortized results are confounded by fine-tuning. For DIME and GDFS, the authors add a VAE and fine-tune the pretrained models (L427-429), but the greedy baselines do not appear to get the same fine-tuning. The DIME gains (e.g., 0.411 to 0.372 RMSE on Air Quality) could therefore come from the extra training alone.

6. Cost and scale are not convincingly studied. The 1.08x overhead (Table J.1) uses only M = 5 sampled masks on small models, and γ\gamma-CMI is even faster than greedy in two cases (0.84x and 0.86x), which suggests noisy timings. Five samples is also very few for an expectation over exponentially many subsets, and the paper does not study sensitivity to M. Finally, every dataset has at most 20 features, with MNIST reduced to 20 pixels, so behavior with hundreds of features is unknown.

Questions for authors
  1. Which results in the paper do not follow from the multilinear-extension view of Owen (1972)?
  2. How does γ\gamma-CMI compare with a two-step greedy lookahead, SEFA, and an RL-based method?
  3. Did the greedy DIME and GDFS baselines receive the same fine-tuning?
  4. The best γ\gamma in Table J.1 differs from the markers in Figures I.2-I.3 (e.g., Bank Marketing 1.0 vs. 0.8, METABRIC 0.5 vs. 0.3). Which values were used in Tables 1-2, and are the Figure I curves computed on validation or test data?
  5. How does a single default γ\gamma perform across all datasets, without per-dataset tuning?
7 comments

We sincerely thank the reviewer for carefully reading our paper and providing detailed and constructive feedback. We believe that the concerns and questions raised by the reviewer are important for clarifying the contributions and limitations of our work. Below, we address each concern and question in detail and describe the corresponding revisions. We have also revised several parts of the manuscript to reflect the reviewer's comments, with all changes highlighted in blue for ease of reference.

[W1 & Q1] Novelty and Connection to Owen (1972)

First, we thank the reviewer for pointing out the connection between Owen (1972) and the theoretical results presented in our paper. We acknowledge these mathematical connections. However, we would like to emphasize that deriving γ\gamma-CMI from an existing mathematical framework and understanding its behavior as an acquisition criterion in practical AFA settings are distinct questions. Owen's multilinear extension alone does not establish whether such values are suitable as an acquisition criterion for AFA. Our work specifically addresses these questions.

More specifically, we propose γ\gamma-CMI as a general acquisition criterion that evaluates informational value not only under the currently observed features but also under hypothetical future contexts consisting of currently unobserved features, using pretrained models. The mathematical analysis is intended to characterize the properties and underlying mechanisms of this approach. Building on this interpretation, we analyze how γ\gamma affects feature acquisition behavior in AFA settings and validate these behaviors through controlled synthetic experiments. Additionally, regarding generative model error, rather than claiming a new general perturbation theorem, this analysis is intended to clarify the specific trade-offs that arise when applying γ\gamma-CMI in practical AFA settings.

So, we would like to clarify that we do not claim the existing mathematical results underlying γ\gamma-CMI as novel contributions. Rather, the main contribution of our work lies in formulating γ\gamma-CMI as a practical acquisition criterion for CMI-based AFA, analyzing and validating the resulting feature acquisition behaviors, the effects of generative model errors, and its applicability to existing models. We have revised the manuscript to appropriately acknowledge and cite the relevant prior work.

[W2] Meaning of Non-Myopic

γ\gamma-CMI does not explicitly plan or optimize future feature acquisition trajectories. However, incorporating future information into acquisition decisions does not necessarily require explicit planning over future acquisition trajectories. Similarly, RL-based AFA methods learn from rollouts that account for future rewards during training, but at test time, they make acquisition decisions based only on currently observed features, implicitly incorporating future information through the learned policy. In this sense, we use the term "non-myopic" to indicate that γ\gamma-CMI incorporates the informational value of candidate features under potential future observation states into the current acquisition decision.

This non-myopic behavior of γ\gamma-CMI is illustrated by the Indicator Tree experiment. In this experiment, indicator features play an important role in identifying which features will be useful to acquire subsequently. Our results show that γ\gamma-CMI effectively identifies these indicator features. This demonstrates that, even without explicitly planning future acquisition trajectories, γ\gamma-CMI can make acquisition decisions by considering information that may become important for subsequent feature acquisitions. This is why we describe γ\gamma-CMI as a non-myopic acquisition criterion.

In addition, we would appreciate it if the reviewer could clarify what exactly is meant by greedy two-step lookahead. Does this refer to an approach that considers one additional important unobserved feature beyond the current acquisition step? If so, identifying such a feature would require additional computational cost or a separately trained module. Moreover, while such an approach may be effective in settings where pairwise feature interactions are important, such as XOR, it may be limited in capturing higher-order interactions involving three or more features or feature dependencies extending across multiple steps, as in the synthetic tree dataset with depth 2.

[W3 & Q2] Comparison with Non-Myopic Baselines

We conducted additional experiments with two reinforcement learning-based methods, GSMRL and Opportunistic RL, as well as SEFA. Since these methods were primarily designed for classification tasks, we performed comparisons on the six classification datasets used in our paper and newly added the corresponding results in Appendix K.

Our original experiments focused on evaluating the performance improvements achieved by extending Greedy CMI to γ\gamma-CMI within the same model, rather than comparing performance across different models. Therefore, we compared Greedy CMI and γ\gamma-CMI using the same predictor. However, when directly comparing against non-myopic methods, it is difficult to determine whether the observed performance differences arise from the acquisition policies themselves or from differences in the underlying predictors. Therefore, to fairly compare the effectiveness of the acquisition policies, we evaluated all methods using the same separately trained predictor, feeding the acquired features in the order determined by each method. We also evaluated all methods three times, each using a different predictor, to assess their performance under diverse predictive performance conditions: EDDI, which exhibited relatively low predictive performance among the CMI-based models; VAE-MLP, which exhibited relatively high predictive performance; and SEFA, a non-myopic baseline.

    1. Results using EDDI as the shared predictor
ModelBank MarketingCalifornia HousingMiniBooNEMNISTFashion-MNISTMETABRIC
γ\gamma-CMI methods
ACFlow (Greedy)0.696±0.0470.696 \pm 0.0470.460±0.0060.460 \pm 0.0060.780±0.0230.780 \pm 0.0230.476±0.0140.476 \pm 0.0140.509±0.0090.509 \pm 0.0090.518±0.0210.518 \pm 0.021
ACFlow (Gamma)0.804±0.0330.804 \pm 0.0330.461±0.0070.461 \pm 0.0070.802±0.0210.802 \pm 0.0210.476±0.0140.476 \pm 0.0140.511±0.0070.511 \pm 0.0070.535±0.0150.535 \pm 0.015
EDDI (Greedy)0.656±0.0240.656 \pm 0.0240.363±0.0470.363 \pm 0.0470.854±0.0240.854 \pm 0.0240.476±0.0050.476 \pm 0.0050.530±0.0040.530 \pm 0.0040.493±0.0190.493 \pm 0.019
EDDI (Gamma)0.687±0.0370.687 \pm 0.0370.363±0.0470.363 \pm 0.0470.859±0.0290.859 \pm 0.0290.476±0.0050.476 \pm 0.0050.532±0.0040.532 \pm 0.0040.537±0.0260.537 \pm 0.026
EDDI+ (Greedy)0.644±0.0190.644 \pm 0.0190.360±0.0640.360 \pm 0.0640.876±0.006\boldsymbol{0.876 \pm 0.006}0.454±0.0120.454 \pm 0.0120.530±0.0040.530 \pm 0.0040.495±0.0130.495 \pm 0.013
EDDI+ (Gamma)0.655±0.0150.655 \pm 0.0150.360±0.0640.360 \pm 0.0640.876±0.006\boldsymbol{0.876 \pm 0.006}0.461±0.0090.461 \pm 0.0090.530±0.0040.530 \pm 0.0040.495±0.0130.495 \pm 0.013
VAE (Greedy)0.813±0.0080.813 \pm 0.0080.425±0.0120.425 \pm 0.0120.795±0.0480.795 \pm 0.0480.476±0.0150.476 \pm 0.0150.522±0.0040.522 \pm 0.0040.526±0.0050.526 \pm 0.005
VAE (Gamma)0.822±0.0050.822 \pm 0.0050.429±0.0090.429 \pm 0.0090.801±0.0310.801 \pm 0.0310.479±0.0110.479 \pm 0.0110.522±0.0040.522 \pm 0.0040.517±0.0170.517 \pm 0.017
DIME (Greedy)0.845±0.0030.845 \pm 0.0030.466±0.004\boldsymbol{0.466 \pm 0.004}0.870±0.0070.870 \pm 0.0070.543±0.0060.543 \pm 0.0060.563±0.0070.563 \pm 0.0070.542±0.0350.542 \pm 0.035
DIME (Gamma)0.846±0.003\boldsymbol{0.846 \pm 0.003}0.466±0.003\boldsymbol{0.466 \pm 0.003}0.874±0.0070.874 \pm 0.0070.539±0.0110.539 \pm 0.0110.568±0.0070.568 \pm 0.0070.543±0.0430.543 \pm 0.043
GDFS (Greedy)0.843±0.0040.843 \pm 0.0040.465±0.0050.465 \pm 0.0050.861±0.0040.861 \pm 0.0040.551±0.0040.551 \pm 0.0040.562±0.0140.562 \pm 0.0140.555±0.0240.555 \pm 0.024
GDFS (Gamma)0.843±0.0040.843 \pm 0.0040.465±0.0050.465 \pm 0.0050.863±0.0030.863 \pm 0.0030.555±0.0050.555 \pm 0.0050.568±0.0070.568 \pm 0.0070.560±0.0140.560 \pm 0.014
Non-Myopic baselines
GSMRL0.779±0.0180.779 \pm 0.0180.429±0.0080.429 \pm 0.0080.869±0.0030.869 \pm 0.0030.475±0.0040.475 \pm 0.0040.513±0.0090.513 \pm 0.0090.520±0.0210.520 \pm 0.021
Opportunistic RL0.844±0.0040.844 \pm 0.0040.460±0.0040.460 \pm 0.0040.864±0.0040.864 \pm 0.0040.557±0.0060.557 \pm 0.0060.580±0.003\boldsymbol{0.580 \pm 0.003}0.582±0.011\boldsymbol{0.582 \pm 0.011}
SEFA0.842±0.0030.842 \pm 0.0030.397±0.0320.397 \pm 0.0320.872±0.0060.872 \pm 0.0060.561±0.004\boldsymbol{0.561 \pm 0.004}0.574±0.0040.574 \pm 0.0040.578±0.0120.578 \pm 0.012
    1. Results using VAE-MLP as the shared predictor
ModelBank MarketingCalifornia HousingMiniBooNEMNISTFashion-MNISTMETABRIC
γ\gamma-CMI methods
ACFlow (Greedy)0.736±0.0440.736 \pm 0.0440.566±0.0070.566 \pm 0.0070.872±0.0240.872 \pm 0.0240.540±0.0110.540 \pm 0.0110.565±0.0090.565 \pm 0.0090.553±0.0190.553 \pm 0.019
ACFlow (Gamma)0.830±0.0270.830 \pm 0.0270.573±0.0030.573 \pm 0.0030.890±0.0100.890 \pm 0.0100.540±0.0110.540 \pm 0.0110.567±0.0060.567 \pm 0.0060.567±0.0180.567 \pm 0.018
EDDI (Greedy)0.700±0.0160.700 \pm 0.0160.458±0.0390.458 \pm 0.0390.896±0.0150.896 \pm 0.0150.535±0.0030.535 \pm 0.0030.579±0.0040.579 \pm 0.0040.547±0.0220.547 \pm 0.022
EDDI (Gamma)0.720±0.0310.720 \pm 0.0310.458±0.0390.458 \pm 0.0390.901±0.0160.901 \pm 0.0160.535±0.0030.535 \pm 0.0030.581±0.0020.581 \pm 0.0020.551±0.0210.551 \pm 0.021
EDDI+ (Greedy)0.694±0.0100.694 \pm 0.0100.454±0.0560.454 \pm 0.0560.912±0.0010.912 \pm 0.0010.522±0.0090.522 \pm 0.0090.582±0.0030.582 \pm 0.0030.526±0.0120.526 \pm 0.012
EDDI+ (Gamma)0.698±0.0150.698 \pm 0.0150.454±0.0560.454 \pm 0.0560.912±0.0010.912 \pm 0.0010.527±0.0060.527 \pm 0.0060.582±0.0030.582 \pm 0.0030.526±0.0120.526 \pm 0.012
VAE (Greedy)0.849±0.0060.849 \pm 0.0060.562±0.0060.562 \pm 0.0060.908±0.0080.908 \pm 0.0080.572±0.0030.572 \pm 0.0030.594±0.0040.594 \pm 0.0040.579±0.0140.579 \pm 0.014
VAE (Gamma)0.860±0.0030.860 \pm 0.0030.565±0.0070.565 \pm 0.0070.913±0.0040.913 \pm 0.0040.572±0.0020.572 \pm 0.0020.594±0.0040.594 \pm 0.0040.584±0.0100.584 \pm 0.010
DIME (Greedy)0.888±0.0020.888 \pm 0.0020.586±0.0080.586 \pm 0.0080.935±0.0020.935 \pm 0.0020.605±0.0020.605 \pm 0.0020.616±0.0070.616 \pm 0.0070.583±0.0210.583 \pm 0.021
DIME (Gamma)0.890±0.002\boldsymbol{0.890 \pm 0.002}0.586±0.0070.586 \pm 0.0070.935±0.0020.935 \pm 0.0020.604±0.0040.604 \pm 0.0040.622±0.0080.622 \pm 0.0080.581±0.0320.581 \pm 0.032
GDFS (Greedy)0.871±0.0020.871 \pm 0.0020.581±0.0050.581 \pm 0.0050.935±0.0020.935 \pm 0.0020.611±0.0020.611 \pm 0.0020.616±0.0150.616 \pm 0.0150.583±0.0160.583 \pm 0.016
GDFS (Gamma)0.872±0.0020.872 \pm 0.0020.584±0.0030.584 \pm 0.0030.936±0.002\boldsymbol{0.936 \pm 0.002}0.614±0.0050.614 \pm 0.0050.621±0.0040.621 \pm 0.0040.607±0.0090.607 \pm 0.009
Non-Myopic baselines
GSMRL0.818±0.0220.818 \pm 0.0220.546±0.0050.546 \pm 0.0050.921±0.0040.921 \pm 0.0040.546±0.0040.546 \pm 0.0040.572±0.0060.572 \pm 0.0060.558±0.0230.558 \pm 0.023
Opportunistic RL0.887±0.0020.887 \pm 0.0020.591±0.003\boldsymbol{0.591 \pm 0.003}0.936±0.001\boldsymbol{0.936 \pm 0.001}0.619±0.001\boldsymbol{0.619 \pm 0.001}0.631±0.002\boldsymbol{0.631 \pm 0.002}0.629±0.009\boldsymbol{0.629 \pm 0.009}
SEFA0.885±0.0010.885 \pm 0.0010.558±0.0130.558 \pm 0.0130.930±0.0030.930 \pm 0.0030.616±0.0030.616 \pm 0.0030.626±0.0030.626 \pm 0.0030.616±0.0090.616 \pm 0.009
    1. Results using SEFA as the shared predictor
ModelBank MarketingCalifornia HousingMiniBooNEMNISTFashion-MNISTMETABRIC
γ\gamma-CMI methods
ACFlow (Greedy)0.742±0.0470.742 \pm 0.0470.581±0.0110.581 \pm 0.0110.873±0.0230.873 \pm 0.0230.547±0.0120.547 \pm 0.0120.571±0.0090.571 \pm 0.0090.550±0.0300.550 \pm 0.030
ACFlow (Gamma)0.832±0.0300.832 \pm 0.0300.602±0.0110.602 \pm 0.0110.884±0.0170.884 \pm 0.0170.547±0.0120.547 \pm 0.0120.574±0.0060.574 \pm 0.0060.558±0.0170.558 \pm 0.017
EDDI (Greedy)0.708±0.0110.708 \pm 0.0110.461±0.0400.461 \pm 0.0400.897±0.0140.897 \pm 0.0140.542±0.0020.542 \pm 0.0020.586±0.0020.586 \pm 0.0020.529±0.0220.529 \pm 0.022
EDDI (Gamma)0.734±0.0450.734 \pm 0.0450.461±0.0400.461 \pm 0.0400.906±0.0110.906 \pm 0.0110.542±0.0020.542 \pm 0.0020.587±0.0010.587 \pm 0.0010.542±0.0260.542 \pm 0.026
EDDI+ (Greedy)0.709±0.0260.709 \pm 0.0260.456±0.0580.456 \pm 0.0580.913±0.0020.913 \pm 0.0020.527±0.0090.527 \pm 0.0090.588±0.0020.588 \pm 0.0020.522±0.0170.522 \pm 0.017
EDDI+ (Gamma)0.714±0.0120.714 \pm 0.0120.456±0.0580.456 \pm 0.0580.913±0.0020.913 \pm 0.0020.532±0.0060.532 \pm 0.0060.588±0.0020.588 \pm 0.0020.522±0.0170.522 \pm 0.017
VAE (Greedy)0.854±0.0040.854 \pm 0.0040.578±0.0090.578 \pm 0.0090.913±0.0070.913 \pm 0.0070.577±0.0040.577 \pm 0.0040.599±0.0020.599 \pm 0.0020.566±0.0110.566 \pm 0.011
VAE (Gamma)0.863±0.0050.863 \pm 0.0050.583±0.0090.583 \pm 0.0090.917±0.0040.917 \pm 0.0040.578±0.0010.578 \pm 0.0010.599±0.0020.599 \pm 0.0020.569±0.0140.569 \pm 0.014
DIME (Greedy)0.903±0.0020.903 \pm 0.0020.611±0.0100.611 \pm 0.0100.937±0.002\boldsymbol{0.937 \pm 0.002}0.611±0.0030.611 \pm 0.0030.621±0.0060.621 \pm 0.0060.578±0.0210.578 \pm 0.021
DIME (Gamma)0.905±0.0010.905 \pm 0.0010.613±0.0090.613 \pm 0.0090.937±0.002\boldsymbol{0.937 \pm 0.002}0.610±0.0050.610 \pm 0.0050.629±0.0080.629 \pm 0.0080.573±0.0290.573 \pm 0.029
GDFS (Greedy)0.894±0.0070.894 \pm 0.0070.614±0.008\boldsymbol{0.614 \pm 0.008}0.937±0.001\boldsymbol{0.937 \pm 0.001}0.617±0.0030.617 \pm 0.0030.623±0.0150.623 \pm 0.0150.577±0.0240.577 \pm 0.024
GDFS (Gamma)0.896±0.0050.896 \pm 0.0050.614±0.007\boldsymbol{0.614 \pm 0.007}0.937±0.001\boldsymbol{0.937 \pm 0.001}0.620±0.0040.620 \pm 0.0040.629±0.0060.629 \pm 0.0060.598±0.0120.598 \pm 0.012
Non-Myopic baselines
GSMRL0.836±0.0180.836 \pm 0.0180.578±0.0100.578 \pm 0.0100.921±0.0030.921 \pm 0.0030.553±0.0050.553 \pm 0.0050.579±0.0030.579 \pm 0.0030.550±0.0160.550 \pm 0.016
Opportunistic RL0.906±0.001\boldsymbol{0.906 \pm 0.001}0.611±0.0080.611 \pm 0.0080.937±0.001\boldsymbol{0.937 \pm 0.001}0.623±0.002\boldsymbol{0.623 \pm 0.002}0.637±0.003\boldsymbol{0.637 \pm 0.003}0.620±0.005\boldsymbol{0.620 \pm 0.005}
SEFA0.905±0.0010.905 \pm 0.0010.608±0.0120.608 \pm 0.0120.935±0.0010.935 \pm 0.0010.622±0.0040.622 \pm 0.0040.634±0.0030.634 \pm 0.0030.606±0.0160.606 \pm 0.016
Reviewer_iQrpOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper proposes γ\gamma-CMI to address the problem of myopia of greedy Conditional Mutual Information (CMI)-based Active Feature Acquisition (AFA), where scoring each candidate feature only under the current observation context causes synergistic features to be systematically undervalued. γ\gamma-CMI scores a candidate feature XiX_i by averaging its conditional mutual information over randomly sampled future observation contexts Φ⊆U∖{i}\Phi \subseteq \mathcal{U}\setminus\{i\}, where each remaining unobserved feature is independently included with probability γ∈[0,1]\gamma \in [0,1] (Bernoulli sampling). The score exactly recovers Greedy CMI at γ\gamma=0 and reduces to a fully-informed terminal-state CMI at γ\gamma=1. The central theoretical result (Proposition 3.1) shows, via a Mobius/Harsanyi-dividend decomposition, that γ\gamma-CMI decomposes as a γ\gamma-weighted sum of information contributions across interaction orders, with γ\gamma controlling the attenuation of higher-order interactions. It links to discounted returns in RL and to cooperative game theory (Banzhaf value at γ\gamma=1/2 and Shapley value when integrated over gamma). Also, γ\gamma-CMI is training-free and plug-and-play across CMI-based backbones

The paper validates gamma-CMI with a diverse set of experiments: (1). Controlled synthetic datasets (synergy, redundancy, higher-order dependencies, generative-model error) confirm each theoretical prediction; (2). 12 Real-world datasets across multiple CMI-based backbones show gamma-CMI mostly improves early-acquisition performance over Greedy CMI at 1.08x inference cost, and the best gamma is dataset-dependent.

Critical strengths

1. The core idea of this paper is novel. To the best of my knowledge, this is the first work to replace deterministic, greedy conditioning with a probabilistically sampled future conditioning set for CMI-based acquisition, offering a principled (rather than heuristic) way to interpolate between myopic and fully non-myopic evaluation. By independently including each remaining unobserved feature into the conditioning context with probability γ\gamma and averaging the resulting CMI, the method parameterizes the degree of lookahead with a single scalar.

2. The writing clarity is great. The paper is well written: the motivation, theory, and boundary cases (γ\gamma=0, γ\gamma=1) are introduced in a logically self-contained progression, which makes the core idea accessible even to readers outside the AFA subfield. The paper is enjoyable to read.

3. The plug-n-play design is practical. γ\gamma-CMI requires no architectural changes or retraining and can be applied as a plug-and-play extension to existing CMI-based backbones, lowering the barrier to adoption and making the contribution immediately usable by practitioners. This is reflected directly in the real-world experiments, where the authors retrofit γ\gamma-CMI onto several pretrained backbones (ACFlow, EDDI, VAE-MLP) at inference time.

4. The methods is theoretical grounded. Proposition 3.1 is a proven decomposition that gives γ\gamma a precise, interpretable role (interaction-order attenuation), and the connections to RL discounting and cooperative game theory strengthen the conceptual contribution.

Critical weaknesses

1. The real-world gains are often small. In Tables 1 and 2, several improvements are marginal relative to the baseline, yet the paper frames results as “consistent improvements”. Given that the best γ\gamma is selected per dataset via validation, a more rigorous statistical treatment is needed to support the claimed consistency of the benefit.

2. The computational overhead analysis is narrow. The reported inference overhead is measured only for the VAE-MLP backbone with M=5 future-context samples, with no sensitivity analysis of M or the resulting variance of the Monte Carlo estimate, which matters since it is unclear whether M=5 is sufficient to yield a reliable acquisition score.

Questions for authors
  1. Was M=5 chosen based on a convergence analysis? Would the reported 1.08x overhead still hold if a larger M is needed for a reliable estimate, especially on datasets with larger |U|?

  2. Given Appendix A frames γ\gamma-CMI as averaging marginal contributions over random coalitions rather than planning over sequential paths, could the authors clarify what precisely makes the method “non-myopic”?

4 comments

We sincerely thank the reviewer for carefully reading our paper and providing positive and constructive feedback. In response to the points raised, we have made several revisions to the manuscript, highlighted in blue. Below, we provide further details and address the reviewer's concerns and questions in order.

[W1] Small Improvements on Real-World Datasets

We agree that some of the performance improvements on real-world datasets are marginal. However, the goal of these experiments is not to achieve large performance gains on every dataset, but rather to improve the performance of existing methods by extending them without model retraining. This is because the key contribution of our work is a general framework that extends Greedy CMI across various pretrained models.

Following the reviewer's suggestion, we also conducted paired t-tests comparing the performance of Greedy CMI and γ\gamma-CMI under corresponding random seeds. To obtain more reliable p-values, we trained models using five additional training seeds, resulting in a total of 10 paired samples. Among the 72 comparisons, we observed performance improvements in 53 cases, of which 16 showed statistically significant improvements (p<0.05p < 0.05), while no statistically significant performance degradation was observed. These results suggest that extending Greedy CMI with γ\gamma-CMI can lead to performance improvements in certain cases.

[W2 & Q1] Choice of MM and Computational Overhead

First, we would like to clarify a potentially misleading description of mask sampling in our original manuscript. In the actual implementation, all samples generated by the generative model do not share the same set of MM masks. Instead, MM masks are independently sampled for each generated sample. Therefore, if KK denotes the number of samples produced by the generative model, up to KMKM distinct masks can be sampled. Since masks are sampled independently for each generated sample, even M=1M=1 allows up to KK distinct masks to be evaluated. Compared with sharing a single mask across all generated samples, this enables the method to consider a wider variety of hypothetical future contexts. To avoid further confusion, we have revised the pseudocode and clarified this point in the manuscript. Notably, even with M=1M=1, γ\gamma-CMI can improve acquisition performance while incurring virtually the same computational cost as Greedy CMI.

Regarding the choice of MM, we considered M=1,5,10M = 1, 5, 10, and 2020. The resulting average standard deviations in performance for each MM are summarized below.

TaskM=1M=1M=5M=5M=10M=10M=20M=20
Overall (12 datasets)0.0057430.0051590.0050960.004528

We also report the average performance differences relative to M=5M = 5 below.

TaskM=1M=1M=5M=5M=10M=10M=20M=20
Overall (12 datasets)−0.277%0.000% (baseline)+0.074%+0.109%

We additionally measured the wall-clock time overhead for each value of MM, as shown below.

TaskM=1M=1M=5M=5M=10M=10M=20M=20
Overall (12 datasets)1.01±0.08×1.01 \pm 0.08\times1.08±0.18×1.08 \pm 0.18\times1.44±0.40×1.44 \pm 0.40\times1.87±0.79×1.87 \pm 0.79\times

The wall-clock time overhead starts at a level comparable to Greedy CMI when M=1M = 1 and gradually increases with MM. We selected M=5M = 5 by considering the trade-off between Monte Carlo estimation accuracy and increased wall-clock time overhead. We have added a sensitivity analysis of MM to Appendix J of the revised manuscript.

Also, in Table J.1 of the original manuscript, we labeled Greedy as M=1M = 1. However, since Greedy does not consider diverse future contexts, we have refined the notation for clarity in the revised manuscript.

Furthermore, to investigate scalability with a larger number of features, as the reviewer suggested, we measured the wall-clock time overhead of VAE-MLP on MNIST downsampled to 14×1414 \times 14 pixels.

M=1M=1M=5M=5M=10M=10M=20M=20
0.99±0.07×0.99 \pm 0.07\times1.19±0.13×1.19 \pm 0.13\times1.66±0.18×1.66 \pm 0.18\times2.58±0.26×2.58 \pm 0.26\times

The experimental results show that a larger overhead is observed compared to the previous setting. Nevertheless, the computational overhead remains manageable even with a larger number of features.

[Q2] Meaning of Non-Myopic

As the reviewer correctly points out, γ\gamma-CMI does not explicitly plan or optimize future feature acquisition trajectories. However, incorporating future information into acquisition decisions does not necessarily require explicit planning over future acquisition trajectories. For example, reinforcement learning-based AFA methods generally optimize their policies to account for future rewards during training. At inference time, however, they typically select the next feature by evaluating a learned policy or value function rather than explicitly searching over future trajectories. Similarly, γ\gamma-CMI does not explicitly search over future feature acquisition trajectories. Instead, it directly incorporates hypothetical future observation contexts into the acquisition scores at inference time. Therefore, γ\gamma-CMI considers not only the immediate information gain but also how the informational value of a candidate feature may change when other features become observed.

This distinction is illustrated by the Indicator Tree experiment. In this experiment, indicator features play an important role in identifying which features will be useful to acquire subsequently. Our results show that γ\gamma-CMI effectively identifies these indicator features. This demonstrates that, even without explicitly planning future acquisition trajectories, γ\gamma-CMI can make acquisition decisions by considering information that may become important for subsequent feature acquisitions, beyond immediate information gain. It is in this sense that we describe γ\gamma-CMI as a non-myopic acquisition criterion.

I appreciate the authors’ response, I continue to support acceptance.

We sincerely thank the reviewer for taking the time to consider our responses and for their continued support for acceptance. We appreciate their constructive feedback, which has helped us improve the manuscript.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.