BRiG-AFA: Bellman Risk-to-Go Learning for Non-Myopic Active Feature Acquisition

Jiaorong Feng; Qian Li; Ying Li

REVIEW 2 major objections 4 minor 12 references

BRiG-AFA claims that budget-specific Bellman risk-to-go, fitted backward from one-step terminal risk, can outperform a matched one-step greedy acquisition policy.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-04 09:37 UTC pith:SKQFWAQP

load-bearing objection A solid, honestly-scoped empirical paper whose central mechanism claim is probably right, but the reported gains are slightly less clean than they look because of a training/deployment distribution mismatch that falls unevenly on the two compared policies. the 2 major comments →

arxiv 2608.02305 v1 pith:SKQFWAQP submitted 2026-08-03 cs.LG cs.AI

BRiG-AFA: Bellman Risk-to-Go Learning for Non-Myopic Active Feature Acquisition

Jiaorong Feng , Qian Li , Ying Li This is my paper

classification cs.LG cs.AI

keywords active feature acquisitionBellman risk-to-gobudgeted classificationnon-myopic decision makingsupervised learningsequential feature selectionrisk regressionfitted dynamic programming

verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Active feature acquisition asks which unmeasured feature to query next, under a budget. The paper tries to establish that non-myopic acquisition can be learned without reinforcement learning or generative modeling: train one small network per remaining budget to predict the final classification loss, fit them backward, and act greedily on those risk-to-go scores. Its controlled experiments show that this budget-specific regression beats a matched one-step greedy policy by about 4.8 and 4.4 percentage points at budgets two and three on a synthetic context-dependent task, and by 10.2 points at four acquisitions on a 20-pixel Fashion-MNIST task, while results on MiniBooNE are mixed at small budgets and positive at larger ones. The paper is careful to say this establishes a mechanism, not broad superiority over all prior methods.

Core claim

The central claim is that with the predictor, state sampler, and evaluation protocol held fixed, budget-specific risk-to-go can outperform repeatedly applying a one-step action value. Concretely, BRiG-AFA fits Q_r(x_m, m, a), the expected terminal cross-entropy after acquiring candidate a with r acquisitions left, using Q_1 equal to the one-step loss and Q_r bootstrapped from the minimum of Q_{r-1} over all still-available candidates. At deployment it picks the candidate with smallest Q_{B-t} using only observed values, the mask, candidate identity, and remaining budget. On Fashion-MNIST it improves accuracy at every nontrivial reported budget relative to the one-step ablation, with the larg

What carries the argument

The load-bearing object is the budget-specific risk-to-go function: for each remaining budget r, Q_r(x_m, m, a) is a small MLP that predicts the terminal classification risk after choosing candidate a and then following the learned policy for r−1 further acquisitions. Q_1 is trained directly on the frozen predictor's one-step loss; each longer-horizon Q_r is fitted by squared-error regression to targets that take the minimum of the already-fitted Q_{r-1} over all still-available candidates—fitted dynamic programming rather than online temporal-difference learning. At inference, greedy minimization of the learned Q over available candidates gives a deployable policy whose inputs are only obse

Load-bearing premise

Everything depends on risk-to-go networks trained on randomly sampled masks retaining their accuracy on masks the learned policy actually generates—a distribution shift the paper itself flags in Section 7 when it notes the predictor is trained with randomly sampled masks rather than jointly with the induced acquisition distribution.

What would settle it

A direct test: retrain BRiG-AFA using policy-induced rollouts as the state sampler instead of the generic random-mask sampler, keeping every other component fixed. If the paired accuracy gain over the one-step ablation disappears or reverses on Fashion-MNIST, the reported non-myopic gains are explained by training-state distribution rather than by genuine budget-conditioned planning.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

If the central claim holds, non-myopic active feature acquisition can be built from supervised backward risk regression with no RL loop, no generative model, and no task-specific metadata at inference.
Budget-specific planning should pay off most at intermediate budgets—large enough to act on context but small enough that one-step rules are shortsighted—matching the CUBE-NM and Fashion-MNIST gain profiles.
The one-step ablation isolates the Bellman-horizon effect: any gain over it is attributable to the longer-horizon recursion, not to the predictor or state representation.
Deployment cost scales as O(Bd) Q-network evaluations per instance, so the approach is practical for moderate action spaces and budgets without batching or pruning.
MiniBooNE's mixed results imply the benefit is task-dependent; the method should not be expected to help when the one-step ranking already captures most signal.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

A natural next test is to retrain the Q-functions on rollouts from the learned policy instead of random masks; if the gains shrink, the reported advantage is partly an artifact of training-state distribution rather than purely non-myopic planning.
The same backward risk-regression scheme could be extended to non-unit feature costs and an explicit stop action by folding cost into the terminal value; the paper leaves this open, and it would broaden applicability to clinical or sensor settings.
The method's O(Bd) enumeration suggests it will need candidate pruning or a scoring-network architecture before it scales to very high-dimensional tabular data, where random-budget Q-fitting may also be harder.
The CUBE-NM regime-switching construction offers a template for diagnosing when non-myopic acquisition matters: future work could probe the connection between the presence of context-gate features and the size of the paired gain.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Desk Editor's Note

A solid, honestly-scoped empirical paper whose central mechanism claim is probably right, but the reported gains are slightly less clean than they look because of a training/deployment distribution mismatch that falls unevenly on the two compared policies.

read the letter

Quick take: this is a solid empirical paper, and the central mechanism claim is probably right, but the reported gains are a bit less clean than the tables suggest because of a training/deployment distribution mismatch that falls unevenly on the two compared policies.

What's new: the idea of freezing a partial-input predictor and fitting budget-specific Q-functions backward with Bellman targets is a genuine alternative to RL and generative approaches. I don't see it in the cited SEFA/ACO/DIME/GDFS line. The paired-seed design with a myopic Q ablation is exactly the right control to isolate the horizon effect, and the authors deserve credit for measuring it that way.

What it does well: the paper is honest about its boundaries. It reports the MiniBooNE mixed results rather than hiding them, it explicitly says SOTA comparison is future work, and it lists its technical limitations in Section 7. The code release is a plus.

Soft spots: the stress-test note about distribution shift is worth taking seriously. Q_r and Q1 are trained on masks from a generic sampler, but deployed on policy-induced masks, and the empty-mask rollout target is only added for r>1. That asymmetry could give BRiG-AFA an advantage at the initial state that is not really about the Bellman recursion. On the other hand, the generic sampler does include empty masks for all r, so Q1 also sees those states; the rollout target is an extra anchor, not the only source of empty-mask coverage. Still, the authors do not test whether the gain persists when Q1 is given the same rollout treatment or when the Q-functions are trained on policy-induced states. That is a real gap, and it tempers the mechanism-level conclusion. The lack of protocol-matched SOTA comparison is a lesser issue because the paper is careful to scope its claim.

Who it's for: anyone working on AFA or budgeted prediction. It's a useful middle-ground method and a good template for controlled evaluation.

Recommendation: send it to peer review. The referee should focus on the distribution-shift asymmetry and ask for a robustness check, but the contribution is meaningful and honestly presented.

Referee Report

2 major / 4 minor

Summary. The paper introduces BRiG-AFA, a supervised method for active feature acquisition that learns budget-specific risk-to-go functions via backward fitted dynamic programming. Starting from a frozen partial-input classifier, it trains Q_r networks by regressing on Bellman targets: Q_1 predicts the terminal loss after one acquisition, and Q_r bootstraps from the minimum of Q_{r-1}. At inference, the policy greedily selects the candidate with minimal predicted remaining risk. The authors evaluate against a myopic-Q ablation (repeatedly using Q_1) on a synthetic context-dependent task (CUBE-NM), Fashion-MNIST-20, and MiniBooNE, reporting paired-seed gains at several budgets and honestly discussing limitations, including the lack of protocol-matched comparisons with recent non-greedy methods and the potential for error compounding.

Significance. If the central claim holds, the paper offers a simple, deployable alternative to RL-based and generative AFA methods, with a reproducible codebase and a carefully controlled experimental protocol. The paired-seed design and the explicit separation of the Bellman-horizon effect from predictor improvements are strengths. The work does not claim state-of-the-art performance, and the MiniBooNE boundary is reported candidly. The main value is a mechanism-level demonstration that direct risk regression can capture non-myopic value, which is a useful contribution if the concerns below about the ablation and distribution shift are resolved.

major comments (2)

[§4.2, Eq. (5), Table 2] The decisive myopic-Q ablation does not fully isolate the Bellman recursion because only Q_r for r>1 receives the additional empty-mask rollout targets described in §4.2. Since evaluation always starts at m=0, BRiG-AFA's first action is trained with rollout-based targets that myopic Q does not receive. The reported gains (e.g., 10.20±0.74 pp on Fashion-MNIST at budget 4) may therefore reflect this extra anchor at the initial state rather than the longer-horizon recursion itself. Please add an ablation of BRiG-AFA without the empty-mask rollout term, and report Q-value calibration or accuracy on policy-induced states for Q_1 and Q_r.
[§4.2, §7] The paper acknowledges that the predictor and Q-functions are trained on randomly sampled masks while deployment follows policy-induced masks, but it does not quantify this state-distribution shift. Because both Q_r and Q1 face the shift, this is not automatically fatal, but it threatens the mechanism-level conclusion. A concrete diagnostic would be to compare the distribution of masks visited by the deployed policies to the training mask distribution, or to retrain the Q-functions on policy-induced states (e.g., iterative re-collection) and check whether the paired gains persist. Without such evidence, the measured effect could be a training-distribution artifact rather than non-myopic planning.

minor comments (4)

[§4.1, Eq. (5)] The paper says a separate function is learned for every remaining budget, but the input vector includes r/d and Eq. (5) indexes θ_r. Clarify whether this is a single network with r/d as input or a set of B separate networks. Also specify what value of r/d myopic Q feeds at each step: the actual remaining budget or a fixed 1/d.
[§4.2] The empty-mask rollout term is described in the text but not included in the loss expression in Eq. (5). Please make the complete objective explicit, including the weight of this term.
[Table 2, §6.3] The MiniBooNE budget-8 row reports 0.93 ± 1.33 with 2/3 positive seeds. The text says the method is 'positive at 8 and 16 acquisitions,' but the budget-8 gain is not statistically distinguishable from zero. Consider softening this wording to avoid overstating the boundary result.
[Appendix A] There is a typo in the section title: 'F ashion-MNIST candidates' should read 'Fashion-MNIST candidates.'

Circularity Check

0 steps flagged

No significant circularity: the central claim is an empirical ablation result, not a derivation equivalent to its inputs.

full rationale

The paper's core claim is empirical: with the predictor, sampler, and protocol held fixed, budget-specific risk-to-go can beat repeatedly applying the one-step action value (Section 7). This is tested by paired-seed experiments, not derived from definitions. The Q-functions are trained with fitted dynamic programming: Q1 is regressed on the terminal one-step loss (Eq. 3), and each longer-horizon Qr is regressed on Bellman targets built from the already-frozen Q_{r-1} (Eqs. 4-5). This is a constructive training scheme, not a circular prediction. The myopic-Q ablation is a matched control using the same Q1, predictor, and inputs, so the reported gains are not forced by construction or by sharing the fitted Q1. The paper does not rely on self-citations or imported uniqueness theorems; cited prior work is external and not load-bearing for the conclusion. The limitation that the predictor is trained on random masks rather than the induced acquisition distribution (Section 7) is a legitimate generalization and evaluation threat, but it is not a circularity: it concerns distribution shift, not the conclusion being equivalent to the training objective. The MiniBooNE mixed results further show the method does not automatically impose its advantage. Overall, the derivation chain is self-contained and the claims are appropriately hedged, so no circular step rises above zero.

Axiom & Free-Parameter Ledger

4 free parameters · 4 axioms · 0 invented entities

No new physical or conceptual entities are introduced; the method is an algorithmic framework. All assumptions are standard for regression-based dynamic programming or explicitly acknowledged by the authors as limitations.

free parameters (4)

MLP hidden width = 128
Two-hidden-layer ReLU MLP width 128; chosen by hand, not fitted to the test metric. Affects capacity of Q-functions.
Adam learning rate = 1e-3
Standard choice; not tuned to the reported gains.
Minimum epochs per budget level = 8
Enforced at least eight epochs at each budget level during Q training; an ad hoc training schedule choice.
Empty-mask rollout term weight = 1
Unit weight given to the empty-mask rollout term for r>1 (Section 4.1); an ad hoc balancing choice.

axioms (4)

standard math Bellman recursion / dynamic programming assumption
The method assumes the terminal risk can be decomposed as a recursion over remaining acquisitions (Eq. 4).
domain assumption Markov state for acquisition decisions
The Q-functions take only current observed values, mask, candidate, and budget as input, assuming this summarizes all relevant history (Section 4.1).
ad hoc to paper Training masks sampled generically are representative enough
Section 4.2 samples random masks and empty masks; the paper acknowledges in Section 7 that this does not match the induced acquisition distribution.
domain assumption Frozen predictor is a good oracle for terminal risk
The method uses a fixed partial-input classifier and never retrains it against the acquisition policy (Section 4.1/7).

pith-pipeline@v1.3.0-daily-deepseek · 6651 in / 14567 out tokens · 118615 ms · 2026-08-04T09:37:09.698188+00:00 · methodology

0 comments

read the original abstract

Active feature acquisition (AFA) asks which unobserved feature to measure next for each test instance under a budget. Greedy rules are easy to train but can overlook context features whose value is realized only through later acquisitions, while reinforcement-learning and generative approaches introduce difficult optimization or conditional-density estimation. We introduce \method, a deployable, supervised alternative that learns a separate candidate-conditioned risk-to-go function for every remaining budget. Starting from the one-step terminal classification risk, the functions are fitted backward with Bellman targets; inference greedily minimizes the learned terminal risk using only observed values, the mask, candidate identity, and remaining budget. A controlled non-myopic benchmark shows the expected mechanism: at budgets two and three, \method improves accuracy over its one-step ablation by $4.84\pm2.17$ and $4.39\pm1.10$ percentage points (mean $\pm$ standard error over five seeds). On Fashion-MNIST with 20 candidate pixels, it improves accuracy at every nontrivial reported budget on average, including $10.20\pm0.74$ points at four acquisitions; its mean paired gain across budgets $\{2,4,8,12,16\}$ is $3.50\pm0.37$ points. A three-seed MiniBooNE study is mixed at small budgets but positive at 8 and 16 acquisitions, identifying a current boundary rather than supporting a universal claim. These results establish a reproducible mechanism-level case for direct Bellman risk regression and delimit the experiments still needed for state-of-the-art comparison.

Figures

Figures reproduced from arXiv: 2608.02305 by Jiaorong Feng, Qian Li, Ying Li.

**Figure 1.** Figure 1: BRiG-AFA separates offline backward risk fitting from deployable sequential acquisition. At test time only [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗

**Figure 2.** Figure 2: CUBE-NM results over five paired seeds. Left: accuracy by acquisition budget. Right: within-seed [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗

**Figure 3.** Figure 3: Fashion-MNIST with 20 candidate pixels, five paired seeds. BRiG-AFA provides its largest advantage at [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗

**Figure 4.** Figure 4: Illustrative Fashion-MNIST acquisition frequencies at budget four (seed 7). Each panel maps the 20 [PITH_FULL_IMAGE:figures/full_fig_p006_4.png] view at source ↗

**Figure 5.** Figure 5: Terminal cross-entropy for CUBE-NM and Fashion-MNIST. Lower is better; ribbons/error bars denote one [PITH_FULL_IMAGE:figures/full_fig_p007_5.png] view at source ↗

**Figure 6.** Figure 6: MiniBooNE accuracy and terminal cross-entropy over three seeds. BRiG-AFA trails myopic Q at budgets [PITH_FULL_IMAGE:figures/full_fig_p007_6.png] view at source ↗

**Figure 7.** Figure 7: Diagnostic CUBE-NM policies. Context-first uses known task structure, whereas regime oracle receives the [PITH_FULL_IMAGE:figures/full_fig_p008_7.png] view at source ↗

discussion (0)

Reference graph

Works this paper leans on

12 extracted references · 2 linked inside Pith

[1]

White, and Su-In Lee

Ian Covert, Wei Qiu, Ming Lu, Na Young Kim, Nathaniel J. White, and Su-In Lee. Learning to maximize mutual information for dynamic feature selection. InProceedings of the 40th International Conference on Machine Learning, volume 202 ofPMLR, pages 6424–6447, 2023

2023
[2]

Estimating conditional mutual information for dynamic feature selection.arXiv preprint arXiv:2306.03301, 2023

Soham Gadgil, Ian Covert, and Su-In Lee. Estimating conditional mutual information for dynamic feature selection.arXiv preprint arXiv:2306.03301, 2023

Pith/arXiv arXiv 2023
[3]

Kolachalama

Osman Berke Guney, Ketan Suhaas Saichandran, Karim Elzokm, Ziming Zhang, and Vijaya B. Kolachalama. Active feature acquisition via explainability-driven ranking. InProceedings of the 42nd International Conference on Machine Learning, volume 267 ofPMLR, pages 20748–20765, 2025

2025
[4]

Opportunistic learning: Budgeted cost-sensitive learning from data streams

Mohammad Kachuee, Orpaz Goldstein, Kimmo Karkkainen, Sajad Darabi, and Majid Sarrafzadeh. Opportunistic learning: Budgeted cost-sensitive learning from data streams. InInternational Conference on Learning Representations, 2019

2019
[5]

Yang Li and Junier B. Oliva. Active feature acquisition with generative surrogate models. InProceedings of the 38th International Conference on Machine Learning, volume 139 ofPMLR, pages 6450–6459, 2021

2021
[6]

EDDI: Efficient dynamic discovery of high-value information with partial V AE

Chao Ma, Sebastian Tschiatschek, Konstantina Palla, Jose Miguel Hernandez-Lobato, Sebastian Nowozin, and Cheng Zhang. EDDI: Efficient dynamic discovery of high-value information with partial V AE. InProceedings of the 36th International Conference on Machine Learning, volume 97 ofPMLR, pages 4234–4243, 2019

2019
[7]

Stochastic encodings for active feature acquisition

Alexander Norcliffe, Changhee Lee, Fergus Imrie, Mihaela van der Schaar, and Pietro Li` o. Stochastic encodings for active feature acquisition. InProceedings of the 42nd International Conference on Machine Learning, volume 267 ofPMLR, 2025

2025
[8]

Kaelbling, and Armando Solar-Lezama

Yewen Pu, Leslie P. Kaelbling, and Armando Solar-Lezama. Learning to acquire information. InProceedings of the Thirty-Third Conference on Uncertainty in Artificial Intelligence, 2017

2017
[9]

Joint active feature acquisition and classification with variable-size set encoding

Hajin Shim, Sung Ju Hwang, and Eunho Yang. Joint active feature acquisition and classification with variable-size set encoding. InAdvances in Neural Information Processing Systems, volume 31, 2018

2018
[10]

Supervised sequential classification under budget constraints

Kirill Trapeznikov and Venkatesh Saligrama. Supervised sequential classification under budget constraints. In Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics, volume 31 of PMLR, pages 581–589, 2013

2013
[11]

Acquisition conditioned oracle for nongreedy active feature acquisition

Michael Valancius, Maxwell Lennon, and Junier Oliva. Acquisition conditioned oracle for nongreedy active feature acquisition. InProceedings of the 41st International Conference on Machine Learning, volume 235 of PMLR, pages 48957–48975, 2024

2024
[12]

Evaluation of active feature acquisition methods for time-varying feature settings.arXiv preprint arXiv:2312.01530, 2023

Henrik von Kleist, Alireza Zamanian, Ilya Shpitser, and Narges Ahmidi. Evaluation of active feature acquisition methods for time-varying feature settings.arXiv preprint arXiv:2312.01530, 2023. 9

Pith/arXiv arXiv 2023

[1] [1]

White, and Su-In Lee

Ian Covert, Wei Qiu, Ming Lu, Na Young Kim, Nathaniel J. White, and Su-In Lee. Learning to maximize mutual information for dynamic feature selection. InProceedings of the 40th International Conference on Machine Learning, volume 202 ofPMLR, pages 6424–6447, 2023

2023

[2] [2]

Estimating conditional mutual information for dynamic feature selection.arXiv preprint arXiv:2306.03301, 2023

Soham Gadgil, Ian Covert, and Su-In Lee. Estimating conditional mutual information for dynamic feature selection.arXiv preprint arXiv:2306.03301, 2023

Pith/arXiv arXiv 2023

[3] [3]

Kolachalama

Osman Berke Guney, Ketan Suhaas Saichandran, Karim Elzokm, Ziming Zhang, and Vijaya B. Kolachalama. Active feature acquisition via explainability-driven ranking. InProceedings of the 42nd International Conference on Machine Learning, volume 267 ofPMLR, pages 20748–20765, 2025

2025

[4] [4]

Opportunistic learning: Budgeted cost-sensitive learning from data streams

Mohammad Kachuee, Orpaz Goldstein, Kimmo Karkkainen, Sajad Darabi, and Majid Sarrafzadeh. Opportunistic learning: Budgeted cost-sensitive learning from data streams. InInternational Conference on Learning Representations, 2019

2019

[5] [5]

Yang Li and Junier B. Oliva. Active feature acquisition with generative surrogate models. InProceedings of the 38th International Conference on Machine Learning, volume 139 ofPMLR, pages 6450–6459, 2021

2021

[6] [6]

EDDI: Efficient dynamic discovery of high-value information with partial V AE

Chao Ma, Sebastian Tschiatschek, Konstantina Palla, Jose Miguel Hernandez-Lobato, Sebastian Nowozin, and Cheng Zhang. EDDI: Efficient dynamic discovery of high-value information with partial V AE. InProceedings of the 36th International Conference on Machine Learning, volume 97 ofPMLR, pages 4234–4243, 2019

2019

[7] [7]

Stochastic encodings for active feature acquisition

Alexander Norcliffe, Changhee Lee, Fergus Imrie, Mihaela van der Schaar, and Pietro Li` o. Stochastic encodings for active feature acquisition. InProceedings of the 42nd International Conference on Machine Learning, volume 267 ofPMLR, 2025

2025

[8] [8]

Kaelbling, and Armando Solar-Lezama

Yewen Pu, Leslie P. Kaelbling, and Armando Solar-Lezama. Learning to acquire information. InProceedings of the Thirty-Third Conference on Uncertainty in Artificial Intelligence, 2017

2017

[9] [9]

Joint active feature acquisition and classification with variable-size set encoding

Hajin Shim, Sung Ju Hwang, and Eunho Yang. Joint active feature acquisition and classification with variable-size set encoding. InAdvances in Neural Information Processing Systems, volume 31, 2018

2018

[10] [10]

Supervised sequential classification under budget constraints

Kirill Trapeznikov and Venkatesh Saligrama. Supervised sequential classification under budget constraints. In Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics, volume 31 of PMLR, pages 581–589, 2013

2013

[11] [11]

Acquisition conditioned oracle for nongreedy active feature acquisition

Michael Valancius, Maxwell Lennon, and Junier Oliva. Acquisition conditioned oracle for nongreedy active feature acquisition. InProceedings of the 41st International Conference on Machine Learning, volume 235 of PMLR, pages 48957–48975, 2024

2024

[12] [12]

Evaluation of active feature acquisition methods for time-varying feature settings.arXiv preprint arXiv:2312.01530, 2023

Henrik von Kleist, Alireza Zamanian, Ilya Shpitser, and Narges Ahmidi. Evaluation of active feature acquisition methods for time-varying feature settings.arXiv preprint arXiv:2312.01530, 2023. 9

Pith/arXiv arXiv 2023