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

• URL: http://arxiv.org/abs/2608.02305v1
• Date: Mon, 03 Aug 2026 14:30:44 GMT
• Title: BRiG-AFA: Bellman Risk-to-Go Learning for Non-Myopic Active Feature Acquisition
• Abstract summary: Active feature acquisition asks which unobserved feature to measure next for each test instance under a budget.<n>We introduce method, a deployable, supervised alternative that learns a separate candidate-conditioned risk-to-go function for every remaining budget.
• Score: 8.363536351727978
• License: http://creativecommons.org/publicdomain/zero/1.0/
• 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.

Related papers

• AgentWorld: Personality-Aware Reliability Evaluation for Agentic Information Retrieval [1.1647715835517187]
  AgentWorld is a simulation framework combining personality-driven user populations with stateful tool-use environments.<n>Three experiments demonstrate the framework: a conversational analytics agent across 10 OCEAN personas (240 evaluator judgments); a customer-support agent across 5 tasks $times$ 4 persona variants; and adversarial stress-testing of 5 tasks revealing pre-existing trajectory brittleness.
  arXiv  Detail & Related papers  (2026-08-25T05:15:33Z)
• Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions [51.50375419691955]
  Distributionally robust Markov decision processes provide a principled framework for sequential decision making under model uncertainty.<n>We study how many samples are necessary and sufficient to learn an $varepsilon$-optimal robust policy under the average-reward criterion.
  arXiv  Detail & Related papers  (2026-08-06T19:49:48Z)
• When Does Learning to Stop Help? A Cost-Aware Study of Early Exits in Reasoning Models [4.8190992438931035]
  LearnStop is a hidden-state-free logistic stopper over prefix-observable features.<n>A trajectory decomposition predicts the regime: learning pays where answers oscillate and correctness evidence is spread.<n>Cost accounting sharpens the picture further -- the same policy that saves 32% of tokens under KV-cache forking costs 121% extra under black-box repeated prefilling.
  arXiv  Detail & Related papers  (2026-06-29T19:33:42Z)
• Bayesian Best-Arm Identification with Abstention: A Polynomial-to-Exponential Phase Transition [51.253617466579335]
  We study the Bayesian fixed-budget best-arm identification problem in which a learner can abstain from making a terminal recommendation.<n>We analyze the probability of undetected error--the risk of recommending a suboptimal arm without abstaining.
  arXiv  Detail & Related papers  (2026-06-28T05:07:27Z)
• A Complexity Measure for Active Learning in Multi-group Mean Estimation [8.550300650352732]
  We study a emphmax-risk objective for active learning in a multi-group mean estimation $d$-armed bandits.<n>A learner adaptively allocates a budget of $T$ samples across $d$ groups to minimize the worst-case uncertainty index.<n>For smooth classes, the $mathrmVLC$ is a reparametrization of a variance--Fisher information, with closed-form values for common families.
  arXiv  Detail & Related papers  (2026-06-12T17:54:26Z)
• A Spectral Phase Diagram for Binary Few-Shot Classification: Intrinsic Dimensionality, Geometric Saturation, and Representational Diagnosis [0.0]
  The saturation index $S(K) = operatornameerank(widehat_W(K)) / K$ measures the ratio of the effective rank of the pooled within-class sample covariance to the shot count.<n>The index is computable in $O(d3)$ time from support features alone, requiring no test labels or trained classifier.
  arXiv  Detail & Related papers  (2026-06-12T16:46:24Z)
• The Sample Complexity of Multiclass and Sparse Contextual Bandits [106.74652380822778]
  We aim to identify an approximately optimal policy from a given class based on bandit feedback.<n>Motivated by bandit multiclass classification with zero-one rewards, we focus on the emph$s$-sparse setting.<n>We show that, with $s$-sparse rewards, the induced model class admits a sharp DEC bound that scales with $s$ and directly yields the optimal rate.
  arXiv  Detail & Related papers  (2026-05-28T09:12:20Z)
• MEMSAD: Gradient-Coupled Anomaly Detection for Memory Poisoning in Retrieval-Augmented Agents [0.0]
  We formalize memory poisoning attacks on retrieval-augmented agents as a Stackelberg game with a unified evaluation framework.<n>We show faithful evaluation increases measured attack success by $4times$ (ASR-R: 0.25 to 1.00$)<n>Our primary contribution is MEMSAD, a calibration-based defense grounded in a gradient coupling.
  arXiv  Detail & Related papers  (2026-05-05T08:15:41Z)
• Polynomial Resource Classification of Quantum Circuit Familes via Classical Shadows [4.519665961894666]
  We classify three quantum circuit families: I, Clifford, and Clifford$+T$.<n>We find $Z$-only measurements outperform multi-basis and classical shadows across all qubit counts.<n>All four strategies collapse to near-chance accuracy ($approx 0.33$) above approximately 12 qubits under the quadratic shot budget.
  arXiv  Detail & Related papers  (2026-04-28T14:34:25Z)
• Low-Rank Bandits via Tight Two-to-Infinity Singular Subspace Recovery [45.601316850669406]
  We present efficient algorithms for policy evaluation, best policy identification and regret minimization. For policy evaluation and best policy identification, we show that our algorithms are nearly minimax optimal. All the proposed algorithms consist of two phases: they first leverage spectral methods to estimate the left and right singular subspaces of the low-rank reward matrix.
  arXiv  Detail & Related papers  (2024-02-24T06:36:08Z)
• Contextual Combinatorial Bandits with Probabilistically Triggered Arms [55.9237004478033]
  We study contextual bandits with probabilistically triggered arms (C$2$MAB-T) under a variety of smoothness conditions. Under the triggering modulated (TPM) condition, we devise the C$2$-UC-T algorithm and derive a regret bound $tildeO(dsqrtT)$.
  arXiv  Detail & Related papers  (2023-03-30T02:51:00Z)
• Sharp Statistical Guarantees for Adversarially Robust Gaussian Classification [54.22421582955454]
  We provide the first result of the optimal minimax guarantees for the excess risk for adversarially robust classification. Results are stated in terms of the Adversarial Signal-to-Noise Ratio (AdvSNR), which generalizes a similar notion for standard linear classification to the adversarial setting.
  arXiv  Detail & Related papers  (2020-06-29T21:06:52Z)
• Risk-Sensitive Reinforcement Learning: Near-Optimal Risk-Sample Tradeoff in Regret [115.85354306623368]
  We study risk-sensitive reinforcement learning in episodic Markov decision processes with unknown transition kernels. We propose two provably efficient model-free algorithms, Risk-Sensitive Value Iteration (RSVI) and Risk-Sensitive Q-learning (RSQ) We prove that RSVI attains an $tildeObig(lambda(|beta| H2) cdot sqrtH3 S2AT big)$ regret, while RSQ attains an $tildeObig(lambda
  arXiv  Detail & Related papers  (2020-06-22T19:28:26Z)
• Learning Near Optimal Policies with Low Inherent Bellman Error [115.16037976819331]
  We study the exploration problem with approximate linear action-value functions in episodic reinforcement learning. We show that exploration is possible using only emphbatch assumptions with an algorithm that achieves the optimal statistical rate for the setting we consider.
  arXiv  Detail & Related papers  (2020-02-29T02:02:40Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.