Counterfactual Explanations and Algorithmic Recourse

An applicant earning $75,000 with $25,000 in savings is refused a loan by the rule \(h = \operatorname{sgn}(X_1 + 5X_2 - 225{,}000)\), where \(X_1\) is salary and \(X_2\) is balance: their score is \(75{,}000 + 125{,}000 = 200{,}000\). The nearest counterfactuals are a salary of $100,000, up 33 percent, or a balance of $30,000, up 20 percent. But if people in this population save 30 percent of their salary, a raise to $85,000, only 14 percent, brings $3,000 of extra savings with it and reaches the threshold on its own (Karimi, Schölkopf & Valera, 2021, Algorithmic Recourse: from Counterfactual Explanations to Interventions, FAccT, arXiv:2002.06278). The explanation that is closest in feature space is not the cheapest thing to do.

Explaining a decision to the person affected argues why counterfactuals suit a data subject better than feature weights. This concept is about how they are computed and where the computation misleads.

The optimisation

Wachter, Mittelstadt and Russell proposed finding, for input \(x\) and desired output \(y'\),

where \(f\) is the model, \(\lambda\) is increased until the prediction is close enough to \(y'\), and \(\mathrm{MAD}_k\) is the median absolute deviation of feature \(k\) over the training data (Wachter et al., 2018, Counterfactual Explanations Without Opening the Black Box, Harvard JOLT 31(2), arXiv:1711.00399). Dividing by MAD puts features on comparable scales and resists outliers; the \(L_1\) form favours changing few features, which keeps the advice short. The method needs only gradient or query access to \(f\), which is why it appealed as a way to satisfy explanation duties without disclosing the model.

A single nearest point is fragile advice, so later methods return several. DiCE generates a diverse set of counterfactuals using a determinantal point process term, trading proximity against diversity so a person sees different routes rather than five variants of one (Mothilal, Sharma & Tan, 2020, Explaining Machine Learning Classifiers through Diverse Counterfactual Explanations, FAT*, arXiv:1905.07697).

From explanation to recourse

A counterfactual answers "what would have had to be different". Recourse asks "what can I do". Ustun, Spangher and Liu defined recourse as the ability to change a model's decision by altering actionable inputs, and used integer programming to find minimal-cost actions for linear classifiers while forbidding changes to immutable features such as age (Ustun, Spangher & Liu, 2019, Actionable Recourse in Linear Classification, FAT*, arXiv:1809.06514). Their credit-scoring experiments showed that recourse "can be significantly affected by standard practices in model development": a model can leave some people with no feasible action at all, and that is a property to audit before deployment, not discover afterwards.

Karimi, Schölkopf and Valera pointed out that both formulations still treat features as independent dials. They recast recourse as choosing interventions \(\mathcal{A}\) in a structural causal model:

where \(x^F\) is the factual individual, \(\mathcal{F}\) the feasible actions, and \(x^{SCF}\) the structural counterfactual obtained by abduction (recover the individual's background noise), action (apply the intervention) and prediction (propagate it to descendants). They prove that the minimal intervention never costs more than an action read off a nearest counterfactual. The salary example is exactly that gap: acting on salary moves savings downstream for free.

When it breaks

The causal model is rarely known. Minimal interventions need the structural equations, and a wrong model gives confident, wrong advice. Without one, the feature-space counterfactual is not guaranteed to be achievable, and can be more expensive than necessary.

Models change after the advice is given. A person told to raise savings by $5,000 may reach the target and find a retrained model has moved the boundary. Upadhyay, Joshi and Lakkaraju showed such recourses are likely to become invalid under model shifts and proposed adversarially robust recourse, at a bounded extra cost to the person (Upadhyay et al., 2021, Towards Robust and Reliable Algorithmic Recourse, NeurIPS, arXiv:2102.13620). Honouring a recommendation for a fixed period is an institutional fix no algorithm supplies.

The distance function smuggles in assumptions. Barocas, Selbst and Raghavan show that counterfactual explanations assume feature changes map cleanly to real-world actions, that training-data spread makes features commensurate, and that features matter only to this decision (Barocas et al., 2020, The Hidden Assumptions Behind Counterfactual Explanations and Principal Reasons, FAT*). A MAD-scaled unit of income and a MAD-scaled unit of credit age are not equally hard to change.

Recourse and gaming are hard to tell apart. Publishing a recipe for flipping the outcome invites changing the measured feature without changing the underlying risk. Miller, Milli and Hardt proved that designing a classifier that rewards genuine improvement rather than gaming requires solving a non-trivial causal inference problem about the outcome itself, not just the model (Miller, Milli & Hardt, 2020, Strategic Classification is Causal Modeling in Disguise, ICML, arXiv:1910.10362). Whether recourse is owed on every feature, or only on those whose change reflects real improvement, is a live disagreement between the explanation-as-right and robustness camps.