Technical Summary: Causal Algorithmic Recourse: Foundations and Methods

Problem Definition and Motivation

The paper addresses the challenge of algorithmic recourse, which involves providing actionable recommendations to individuals to reverse negative decisions made by automated systems (e.g., loan denials, medical treatment rejections). While existing literature offers counterfactual explanations, the authors argue that standard approaches often fail to capture the inherent uncertainty of real-world recourse.

Specifically, traditional methods treat recourse outcomes as exact counterfactuals of a fixed unit, assuming that latent variables (e.g., ability, stress, sleep) remain identical before and after an intervention. The authors posit that in reality, recourse involves repeated decisions on the same individual under potentially different latent conditions. For instance, a student retaking an exam after attending office hours may have the same underlying ability but different stress or sleep levels. This introduces a structural uncertainty where pre- and post-intervention latent variables ($u_T$ and $u^*_T$) are related but not identical.

Furthermore, the paper highlights that standard causal recourse formulations often rely on the Independently Manipulable Features (IMF) assumption, which ignores causal dependencies between covariates. The authors demonstrate through examples that ignoring these dependencies (e.g., income affecting expenditure) can lead to suboptimal or infeasible recommendations. Finally, they note that inferring recourse effects typically requires reasoning about joint counterfactual distributions, which are generally non-identifiable from observational data alone without strong assumptions.

Methodology and Framework

The authors propose a causal framework based on Structural Causal Models (SCMs) that explicitly models the resampling of latent variables during the recourse process.

1. Recourse SCM and Post-Recourse Stability (PRS)

The core of the methodology is the Recourse SCM, defined as a tuple $\langle F, P(u), R=r, P(u^*|u) \rangle$, where $P(u^*|u)$ represents the distribution of latent variables after a recourse action $do(R=r)$.

• Latent Decomposition: Units are decomposed into fixed ($u^{(f)}$) and variable ($u^{(v)}$) components. The fixed component (e.g., intrinsic ability) remains invariant, while the variable component (e.g., stress) may be resampled.
• Post-Recourse Stability (PRS): The authors define PRS as a condition where the distribution of latent variables for non-descendants of the recourse action remains unchanged, and for descendants, the fixed part is invariant while the variable part is resampled from the same conditional distribution given the fixed part.
• Implication: Under PRS, the marginal distribution of post-recourse variables given their parents is identical to the observational distribution (Margin Stability). This allows for inference from observational data alone.

2. Inference Strategies

The paper develops three distinct algorithms based on data availability and the validity of PRS:

• Algorithm 1 (Observational Data + PRS):

  • Assumes PRS holds and only observational data is available.
  • Uses Frank's copula to model the coupling between pre-recourse quantiles ($q_i$) and post-recourse quantiles ($q^*_i$).
  • Since the copula parameter $\tau$ (Kendall's $\tau$) cannot be identified from observational data alone, the algorithm performs a sensitivity analysis by varying $\tau$ to generate a range of possible recourse outcomes.

• Algorithm 2 (Observational + Recourse Data + PRS):

  • Assumes PRS holds and paired data (pre- and post-recourse for the same individuals) is available.
  • Uses the paired data to infer the copula parameter $\tau$ via maximum likelihood estimation.
  • Includes a goodness-of-fit test (using a bootstrap procedure and Cramer-von Mises statistic) to verify if Frank's copula is an appropriate model. This addresses the selection bias inherent in recourse data (only available for individuals who initially failed).

• Algorithm 3 (Observational + Recourse Data + No PRS):

  • Addresses the case where PRS does not hold (margin stability is violated).
  • Instead of relying on a specific copula, it learns a non-parametric quantile function $Q(v^*_i | v_i, pa_i, pa^*_i)$ directly from the combined observational and recourse data.
  • This approach leverages the correlation between pre-recourse residuals and post-recourse noise to improve prediction accuracy, theoretically reducing the expected mean squared prediction error (EMSPE) compared to standard regression on recourse parents alone.

Key Contributions

1. Causal Formulation of Recourse: The paper introduces a formulation of algorithmic recourse that accounts for the resampling of latent variables, moving beyond the assumption of fixed units. It defines Post-Recourse Stability (PRS) as a critical condition for inference.
2. Theoretical Guarantees:
   • Theorem 1: Proves that PRS implies margin stability, enabling the identification of recourse effects from observational data.
   • Theorem 2: Provides theoretical guarantees for the "augmented" regression approach (Alg. 3) in linear Gaussian settings, showing it reduces prediction risk compared to standard approaches when pre- and post-recourse noise terms are correlated.
3. Algorithmic Suite:
   • Development of Alg. 1 for sensitivity analysis using observational data.
   • Development of Alg. 2 for learning copula parameters and testing model fit using recourse data.
   • Development of Alg. 3 for distribution-free inference when stability assumptions fail.
4. Recourse Data Concept: The authors formally define recourse data (paired pre- and post-intervention samples for the same individual) and the associated learning problem, distinguishing it from standard observational or experimental data combinations.

Experimental Results

The authors validate their methods using the HELOC (Home Equity Line of Credit) dataset and a semi-synthetic variant:

• Sensitivity Analysis (Alg. 1): Applied to real HELOC data, the algorithm demonstrated how varying the copula parameter $\tau$ affects the spread of predicted recourse outcomes, illustrating the uncertainty inherent in the absence of recourse data.
• Goodness-of-Fit (Alg. 2): Using semi-synthetic data, the authors showed that the proposed bootstrap test correctly identifies when Frank's copula is valid (uniform p-value distribution) and when it is violated (skewed p-values towards 0).
• Copula-Free Learning (Alg. 3): In scenarios where PRS was violated (SeS-HELOC B), Alg. 3 outperformed both the standard regression approach and the copula-based approach. The Kolmogorov-Smirnov statistics showed that Alg. 3's predictions were closer to the true underlying distribution, empirically verifying the theoretical advantage of leveraging pre-recourse information even when margin stability does not hold.

Significance and Claims

The paper claims to be the first to formalize an inference problem that combines observational and experimental data corresponding to the same individual in the context of algorithmic recourse. By moving away from the assumption of fixed counterfactual units, the framework provides a more realistic model of how individuals respond to interventions over time.

The authors emphasize that their work bridges the gap between theoretical causal inference and practical recourse applications. They argue that while standard causal recourse methods often require full structural knowledge or rigid assumptions (like IMF), their framework offers a flexible hierarchy of methods:

1. Sensitivity analysis when only observational data is available.
2. Parameter inference and model testing when recourse data is available.
3. Distribution-free learning when stability assumptions are violated.

The significance lies in providing a rigorous, causal foundation for understanding the variability in recourse outcomes and offering practical algorithms that adapt to the specific data availability and stability conditions of a given application.