PaperlayerView exact revision on arXiv

Source-linked AI summary

Explanations-Driven Active Feature Acquisition for Algorithmic Recourse

Vinura Galwaduge, Jagath Samarabandu

arXiv:2609.12179v1cs.LGcs.AI

TL;DR

When decisions use partial information, feature acquisition costs matter, but conventional AFA does not use explanations to guide which features it acquires. This paper combines recourse and acquisition through a Markov Blanket framework and EDFA; experiments report lower-cost, more decision-relevant recourse with comparable predictive performance.

  • Problem

    Conventional active feature acquisition accounts for acquisition cost but disregards explanations, although acquired features affect explanation quality.

    Source: §1 · p. 2

  • Method

    The paper uses Markov Blanket theory to unify counterfactual, semifactual, and alterfactual recourse and proposes EDFA, which bases acquisition on feature cost and explanatory power.

    Source: §1 · p. 2, §4.1 · p. 8

  • Results

    EDFA yields lower-cost, more decision-relevant and actionable recourse than baseline AFA methods while maintaining comparable predictive performance.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Validation guarantees can signal whether early recourse is worth acting on with limited information rather than waiting for all features.

    Source: §1 · p. 2

    The current setup assumes acquired Markov Blanket features are actionable, which may not hold, particularly for spouse features that can be exogenous context variables.

    Source: §6 · p. 24

Abstract

from arXiv · show

Algorithmic recourse methods typically assume that a predictive model has access to all features of an individual. In practice, decisions are often made with partial information, because features are costly to acquire. Active feature acquisition addresses cost-constrained prediction, but existing methods are explanation-agnostic: prior work provides explanations only after acquiring additional features, rather than using explanations to drive acquisition. This work flips that and treats algorithmic recourse and feature acquisition jointly. We use Markov Blanket theory to unify counterfactual, semifactual, and alterfactual explanations and to characterize how available recourse grows as features are acquired. Building on this framework, we propose an Explanation-Driven Feature Acquisition (EDFA) method that selects features by explanatory value per unit cost. The framework is further extended with distribution-free validity guarantees for recourse issued from partial information, which signal trustworthy, lower-cost recourse, along with a lower bound on the calibration data required to certify them. Experiments on 7 publicly available datasets with neural network-based predictive models show that EDFA acquires substantially fewer features than state-of-the-art AFA baselines while maintaining comparable accuracy and yielding more decision-relevant, actionable recourse. The implementation is available on GitHub.

1 Introduction

The paper addresses feature acquisition that accounts for recourse, not just prediction, when decisions use partial information and acquiring features is costly. It unifies three recourse types with Markov Blanket theory, proposes EDFA and early-recourse validation guarantees, and reports lower-cost, more decision-relevant recourse with comparable predictive performance.

1 Introduction

  • Conventional AFA selects features for predictive performance but does not account for explanations, even though acquired features affect explanation quality.The paper studies whether making explainability an additional acquisition requirement yields better explanations.Source: §1 · p. 2
  • The paper proposes an EDFA method based on a Markov Blanket framework that unifies counterfactual, semifactual, and alterfactual explanations.The framework treats explanations as an objective of active feature acquisition rather than only explaining acquisition decisions.Source: §1 · p. 2
  • Semifactual features can signal which unacquired features may unlock new counterfactual recourse, and EDFA operationalizes this principle in its acquisition policy.Semifactuals were previously treated as passive complements to counterfactuals.Source: §1 · p. 2
  • The paper proposes validation guarantees for early recourse that indicate whether users should act with limited information rather than wait for all features.It also proposes a method to find the minimal sufficient calibration dataset size for calculating those guarantees.Source: §1 · p. 2
  • EDFA produces lower-cost, more decision-relevant and actionable recourse than baseline AFA methods while maintaining comparable predictive performance.The experiments cover seven real-world tabular datasets from financial and medical domains.Source: §1 · p. 2

2 Related Work

Related work covers Markov Blanket discovery, cost-constrained active feature acquisition, and algorithmic recourse. The paper distinguishes its aim of using recourse to guide acquisition from prior work that explains acquisition decisions or addresses different information settings.

2.1 Markov Blanket (MB) Discovery

  • Markov Blanket discovery methods identify predictive feature sets; the paper uses three distinct algorithms as approaches to MB search.The literature includes IAMB and later methods designed to improve data efficiency, as well as work connecting MB discovery to causal partial DAG recovery.Source: §2.1 · p. 3

2.2 Active Feature Acquisition (AFA)

  • AFA sequentially selects instance-specific features under a budget, while much explainable-AFA work explains acquisition decisions rather than using recourse to drive acquisition.Prior work also links MB search with sequential feature selection through conditional likelihood.Source: §2.2 · p. 3

2.3 Algorithmic Recourse

  • Recourse research addresses actionable counterfactuals and related concerns, while semifactual and alterfactual explanations provide complementary perspectives.The closest related settings differ: sequential recourse assumes full information, whereas recourse under missing information focuses on features unavailable to the model; personalized recourse accounts for user preferences or perceived feature costs.Source: §2.3 · p. 4

3 Theoretical Background

The theoretical background uses Markov Blanket assumptions to characterize recourse as features are observed and to derive guarantees for recourse from partial information. It establishes when semifactual features can signal acquisition opportunities and how calibration data supports validity guarantees.

3.1 Markov Blanket Theory

  • Under the causal Markov and faithfulness assumptions, the Markov Blanket separates a target from variables outside it; the paper additionally assumes an ideal model trained on MB features.Figure 2 depicts the blanket and currently observed features.Source: §3.1 · pp. 4–5, Figure 2 · p. 5

3.2 Explainability and Markov Blanket theory

  • Tripartite recourse partitions features into counterfactual, semifactual, and alterfactual sets: observed MB features that flip predictions, currently non-necessary MB features, and irrelevant non-MB features.Semifactual MB features may be unobserved or have a blocked causal pathway to the target.Source: §3.2 · pp. 5–6
  • Theorem 1 states that the MB is observationally sufficient and its features are probabilistically necessary; under a label-flipping condition, a feature can also be observationally necessary.An MB feature that cannot cross the decision boundary at plausible values remains semifactual.Source: §3.2 · p. 6
  • A semifactual spouse can signal an unobserved shared child whose acquisition may activate a counterfactual pathway.After observing the child, the spouse may transition from semifactual to counterfactual; this transition depends on the stated conditions.Source: §3.2 · p. 6
  • Within an MB unit without its shared child, a conditional-mutual-information policy prioritizes a parent or child over a spouse, weakly enlarging the one-step recourse frontier.The enlargement is strict when the label-flipping condition holds for an unlocked spouse.Source: §3.2 · pp. 6–7

3.3 Probabilistic Bounds of Recourse Validity

  • The validity framework uses RCPS-HB to bound mean recourse invalidation risk, rather than providing an instance-specific guarantee.The guarantee states that risk is at most α with probability at least 1 − δ; its confidence threshold certifies the mean loss under the specified error rate.Source: §3.3 · p. 7
  • The per-instance loss checks both whether a prediction remains consistent through the final acquisition step and whether recourse remains valid there.The empirical risk is calculated over calibration samples; a theoretical calibration-size lower bound omits the Binomial Bentkus term and is stricter, so the experiments use an empirical curve.Source: §3.3 · pp. 7–8

4 Methodology

EDFA selects features using both acquisition cost and explanatory power, while Markov Blanket structure guides how acquisition can unlock counterfactual recourse. The method adds RCPS-HB validity guarantees and evaluates recourse, prediction, and acquisition costs across datasets and model settings.

4.1 Explanation Driven active Feature Acquisition (EDFA)

  • EDFA selects features using cost and explanatory power, with MB-unit acquisitions able to turn semifactual features into counterfactuals.Its heuristic estimates potential counterfactual features unlocked per unit cost; the authors note the resulting sequence is myopic under the budget constraint.Source: §4.1 · p. 8

4.2 Recourse validity guarantees

  • RCPS-HB derives probabilistic validity bounds from held-out calibration data, and the safe rule stops when prediction uncertainty meets its threshold.The baseline stopping rules did not provide satisfactory robust guarantees, so the safe rule is used in the reported results.Source: §4.2 · p. 8

4.3 Experimental Setup

  • Experiments use FTT and XGBoost, Adult-only Bayesian Networks, 10 test-sample repetitions, three AFA baselines, and plausible-CF search methods for validation.EDFA is tested with three Markov Blanket discovery methods; phase 2 compares DiCE, NICE, and PROBE within EDFA.Source: §4.3 · pp. 9, 11

4.3.1 Datasets

  • Seven finance and healthcare tabular datasets form the testbed, with dataset size capped at 50K and stratified subsampling used for Diabetes130.The stratified sampling preserves class distributions.Source: §4.3.1 · p. 11

4.3.2 Evaluation Metrics

  • Metrics track recourse and semifactual trajectories against normalized acquisition cost, alongside accuracy, acquired-counterfactual share, CF Valid@K, and counterfactual quality.Counterfactual quality includes sparsity, proximity, and plausibility; the reported risk levels use α values of 0.2 and 0.3.Source: §4.3.2 · pp. 11–12

5 Results

EDFA acquires the fewest features on average while maintaining comparable accuracy, though baseline AFA methods produce more recourse by relying increasingly on non-Markov-Blanket features. The results also examine recourse growth, validity guarantees from partial information, calibration-data requirements, and ablations of EDFA components.

5.1 Phase 1 - Counterfactual recourse growth

  • EDFA acquires the fewest features on average and produces sparse, plausible counterfactuals closer to original instances in most scenarios.Table 2 reports the feature-acquisition comparison; Table 3 describes counterfactual quality, with missing EDFA entries because it yields too few counterfactuals to average.Source: §5.1 · p. 12, Table 2 · p. 12, Table 3 · p. 16
  • As features are acquired, EDFA’s recourse frontier grows and semifactuals decline while accuracy remains stable or acceptable, except on GMSC.The reported examples show acquired features unlocking counterfactual recourse, including when a previously available semifactual feature becomes actionable after MB-unit completion.Source: §5.1 · pp. 12–14, Figure 3 · p. 13, Figure 4 · p. 14
  • Baseline AFA methods generate more recourse options than EDFA, but increasingly rely on features outside the Markov Blanket.EDFA maintains comparable predictive performance while acquiring fewer features; the German Credit FTT results were omitted because of dataset size.Source: §5.1 · p. 12

5.2 Phase 2 - Validation Guarantees

  • At α = 0.2 and δ = 0.05, at least 80% of early-stopping users receive recourse that remains valid with full information, at 95% confidence.EDFA and other counterfactual search methods can meet the stated validation guarantees without spending the full acquisition budget in some scenarios; PROBE provides more lower-cost guaranteed options on Diabetes130, while NICE falls behind on HELOC.Source: §5.2 · p. 18, Figure 11 · p. 19, Figure 12 · p. 19
  • Calibration-data limits separate cases where more data may enable a guarantee from cases where observed risk already exceeds the requested α.The empirical lower-bound curve approximates the stricter theoretical bound; relaxing α from 0.2 to 0.3 lets more model–counterfactual combinations qualify with current data.Source: §5.2 · p. 18, Figure 13 · p. 20

5.3 Ablation studies

  • Most EDFA ablations stay close to the default, but random within-blanket selection degrades recourse count and accuracy on Taiwan Credit and HELOC as feature count grows.Removing PC-first enforcement or replacing CMI/cost spouse ranking with 1/cost shows little deviation in the reported settings; random selection remains competitive on Diabetes.Source: §5.3 · pp. 18, 21, Figure 14 · p. 21

6 Discussion

EDFA’s Markov Blanket focus yields more decision-relevant recourse than baselines that increasingly rely on non-MB features, while predictive performance remains comparable. The discussion also examines recourse guarantees and notes limitations in actionability, robustness to MB structure, and evaluation scope.

6 Discussion

  • Baselines produce more recourse options but increasingly rely on non-MB features, while EDFA selects structurally connected MB features that are more decision-relevant and faithful to the MB.Some baseline-selected features may be decision-irrelevant or non-actionable.Source: §6 · p. 21
  • EDFA’s observed recourse options are not significantly altered by the MB discovery algorithm, but differences in recovered MB-unit structure remain a possible limitation.The authors suggest manually verifying that recovered MB units align with decision-relevant or actionable features.Source: §6 · p. 23
  • EDFA is on par with other AFA methods in predictive performance, although EDFA-random degrades on Taiwan Credit and HELOC as feature counts rise, while Diabetes is an exception.The EDFA-random variant shows lower recourse counts and accuracy at some stages on Taiwan Credit and HELOC, but slightly better accuracy on Diabetes.Source: Figure 16 · p. 22, Figure 15 · p. 22, Figure 17 · p. 23
  • Validation guarantees can indicate whether early recourse remains stable as features arrive, but their availability depends on the dataset and its size.The guarantees concern population failure rates rather than an individual user’s risk, and do not establish real-world actionability.Source: §6 · pp. 24–25
  • EDFA’s recourse can be valid without being truly actionable, because the setup assumes acquired MB features are actionable and spouse features may be exogenous context.Directionality filtering to assess actionability remains future work.Source: §6 · p. 24
  • EDFA limits manipulability by restricting perturbable features to the MB, but the paper does not evaluate this effect quantitatively and assumes a global setting for users’ actionable features.All users are assumed to share the same starting and actionable features.Source: §6 · p. 25

7 Conclusion

The paper connects algorithmic recourse with active feature acquisition through Markov Blanket theory and introduces EDFA. Experiments support more decision-relevant recourse while maintaining predictive performance, and the paper proposes validation guarantees for early recourse.

7 Conclusion

  • The experiments show EDFA can provide more decision-relevant recourse while maintaining predictive performance, and the paper proposes validation guarantees for early recourse.Future work includes additional scenarios and datasets, recourse distance, and causal frameworks that incorporate feature directionality.Source: §7 · p. 25

A Proofs of the Theorem 1, Propositions 1 and 2

The proof section sets out the graph and predictor assumptions and invokes standard consequences of d-separation, faithfulness, and Markov Blanket shielding. These provide the probabilistic basis for the subsequent results.

A Proofs of the Theorem 1, Propositions 1 and 2

  • The setup defines a DAG over the outcome and features, with the Markov Blanket comprising the outcome’s parents, children, and spouses.Under the aligned-model assumption, the predictor uses MB features and is invariant to coordinates outside the MB.Source: A Proofs of the Theorem 1,… · p. 31
  • The proof invokes d-separation soundness and faithfulness: d-separation implies conditional independence, while an active path implies conditional dependence.These are stated as consequences of Assumptions 1 and 2.Source: A Proofs of the Theorem 1,… · p. 31
  • Markov Blanket shielding states that the MB d-separates the outcome from every variable outside the blanket.Consequently, the outcome is conditionally independent of outside variables given the MB.Source: A Proofs of the Theorem 1,… · p. 31

A.1 Proof of Theorem 1

Theorem 1’s proof establishes blanket sufficiency and the irrelevance of alterfactual features outside the MB, then derives individual necessity for MB features under an explicit label-flipping condition.

A.1 Proof of Theorem 1

  • The full Markov Blanket is observationally sufficient, with β(MB(Y), x, y*) = 1 for all x.The blanket-restricted Bayes rule is optimal given all features, and the aligned predictor is invariant to outside-blanket replacements.Source: §A.1 · p. 31
  • Features outside the MB are alterfactual: replacing one leaves the prediction unchanged, so α({Xi}, x, y*) = 0.The predictor does not depend on coordinates outside the MB under Assumption 3.Source: §A.1 · p. 31
  • For an MB feature, an active path to the outcome given the rest of the MB implies conditional dependence and positive conditional mutual information.The proof handles parents and children through adjacency, and spouses through an opened v-structure.Source: §A.1 · p. 31
  • Probabilistic relevance alone does not guarantee a label change; the proof assumes a label-flipping condition to establish positive counterfactual necessity for MB features.The condition requires plausible feature values and a fixed configuration of the other MB features that yield different predicted labels.Source: §A.1 · pp. 31–32

A.2 Proof of Proposition 1

Before the shared child is observed, the pure spouse is conditionally independent of the outcome given acquired features and belongs to the semifactual set. Observing the child opens the collider path, so the spouse may become a counterfactual feature.

A.2 Proof of Proposition 1

  • Before the shared child is acquired, conditioning blocks the pure spouse’s only path to Y, making its conditional mutual information zero and placing it in the semifactual set.The pure-spouse assumption requires that the spouse’s only connection to Y not already blocked by acquired features is the shared-child collider path.Source: §A.2 · p. 32
  • After the shared child is acquired, the collider path opens; on some instances, decisive posterior variation can make the spouse a counterfactual feature.The population conditional mutual information is positive, but the instance-wise value need only be positive on a set of instances with positive probability.Source: §A.2 · p. 32

A.3 Proof of Proposition 2

Before acquiring a shared child, its conditional mutual information is positive while the spouse’s is zero. The policy therefore acquires parent-child members first, which can unlock spouses as new counterfactual recourse options.

A.3 Proof of Proposition 2

  • Before the shared child is acquired, the child has positive conditional mutual information while the spouse’s is zero.The spouse’s zero value follows when the child and its descendants are unacquired.Source: §A.3 · p. 32
  • Algorithm 1 enforces parent-child-first acquisition, matching the information-per-cost ordering with a structural guarantee rather than noisy per-instance estimates.The policy ranks unacquired features by conditional mutual information or mutual information per unit cost.Source: §A.3 · p. 32
  • Acquiring parent-child members first can unlock spouses as new counterfactual features and increase the rate at which recourse options become available.Source: §A.3 · p. 32
Loading 2609.12179v1…