Learning Models for Actionable Recourse
Year: 2022

Abstract:
As machine learning models are increasingly deployed in high-stakes domains such as legal and financial decision-making, there has been growing interest in post-hoc methods for generating counterfactual explanations. Such explanations provide individuals adversely impacted by predicted outcomes (e.g., an applicant denied a loan) with recourse—i.e., a description of how they can change their features to obtain a positive outcome. We propose a novel algorithm that leverages adversarial training and PAC confidence sets to learn models that theoretically guarantee recourse to affected individuals with high probability. We demonstrate the efficacy of our approach with extensive experiments on real data.

heading: 1 Introduction
text: In recent years, there has been a growing interest in using machine learning to inform consequential decisions in legal and financial decision-making—e.g., deciding whether to give an applicant a loan [Hardt et al., 2016], bail to a defendant [Lakkaraju and Rudin, 2017], or parole to a prisoner [Zeng et al., 2017]. Because these decisions have an impact on the lives of the concerned individuals, it is critical to explain why the model made its prediction. Explanations are important not only to ensure that there are no issues with the way the prediction is made (e.g., making sure the decision is free of racial/gender bias [Hardt et al., 2016] and does not suffer from causal issues [Bastani et al., 2017]), but also to give the affected individual a justification for the decision. Thus, there has been a great deal of recent interest in explainable machine learning [Lou et al., 2012, Wang and Rudin, 2015, Ribeiro et al., 2016b, Lakkaraju et al., 2019].
We focus on counterfactual explanations [Wachter et al., 2017], which specify how features can be changed to obtain a different model prediction. These explanations can be used to provide individuals who are negatively impacted by model outcomes with actionable recourses—i.e., actions they can take to receive a positive outcome [Ustun et al., 2019]. For instance, for an applicant denied a loan, an actionable recourse might be: “to get a loan, increase your income by $1,000.” Such a recourse must satisfy two properties to be actionable: (i) it only changes features that the individual can realistically modify—e.g., it cannot change race or gender, but can change income, and (ii) the magnitude of the change must be reasonable. An actionable recourse like this may be considered necessary in some settings because it provides an individual with agency over a consequential decision that affects them.
Prior research has addressed the need for recourses through post-hoc algorithms for computing individual recourses corresponding to certain kinds of models—e.g., using integer linear programming
⇤Work started at Harvard University.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
in the context of linear models [Ustun et al., 2019], or using gradient descent on the input for differentiable models [Wachter et al., 2017]. However, these approaches do not guarantee that actionable recourses exist; at best, Ustun et al. [2019] guarantee that they find one if it exists, and only for linear models. In other words, many affected individuals may not even be prescribed any actions that they can take to change their outcome.
We aim to provide tools for guaranteeing the existence of actionable recourses for domains in which recourses may be necessary. We propose a novel algorithm for learning models in a way that is designed to ensure the existence of actionable recourses so that affected individuals receive recourse with a high probability. To the best of our knowledge, our approach is the first to train models for which recourse is likely to exist with a high probability. It builds on adversarial training [Goodfellow et al., 2015a], which is designed to ensure that models are robust to adversarial examples. At a high level, given a binary classification model f✓ : X ! Y , where Y = {0, 1}, an adversarial example is a perturbation 2 to an input x 2 X such that f✓(x+ ) 6= f✓(x). In a typical adversarial training setting, we choose to be “small” in some sense (e.g., in terms of L1 norm of 2 ) and aim to guarantee that adversarial examples do not exist—i.e., f(x+ ) = f(x) for all 2 . In contrast, in our setting, we intuitively want to ensure that adversarial examples do exist. In particular, given an input x for which f(x) = 0, we want there to exist recourse 2 such that f(x + ) = 1, where in our case, is the given set of all permissible recourses for the application domain. Thus, we adapt existing adversarial training algorithms to ensure the existence of recourse. As an added benefit, these algorithms can compute recourse significantly faster than existing techniques for general differentiable models [Wachter et al., 2017].
While adversarial training heuristically encourages recourse to exist, it does not provide any theoretical guarantees. We build on PAC confidence sets [Park et al., 2020] to guarantee that recourse exists with high probability (assuming the test distribution is the same as the training distribution).
We evaluate our approach on four real world datasets that cover lending, recidivism, bail, and credit outcomes. Our results demonstrate that our approach is very effective at improving recourse rates (i.e., the probability that individuals are given recourse) without noticeably reducing accuracy.
In addition, we show that we achieve this improvement in recourse rates without noticeably harming the quality of recourses or the brittleness of the underlying model. Firstly, we empirically demonstrate that our approach improves the rate at which models provide recourses that are grounded in reality: We find that our approach encourages the existence of recourses that both obey causal constraints driven by real-world causal relationships and are in-distribution to the original data. Secondly, we show that our approach encourages the existence of robust recourses (i.e., recourses that result in positive outcomes even when changed in small ways). Lastly, we show that these improvements in recourse rates do not render the underlying classifier brittle.2
Related work. Beyond Wachter et al. [2017], Ustun et al. [2019], other approaches have been proposed for generating recourses [Zhang et al., 2018, Hendricks et al., 2018, Mothilal et al., 2020, Looveren and Klaise, 2019, Poyiadzi et al., 2020, Karimi et al., 2020a,b,c]. However, all these works focus on how to compute recourse for given predictive models; in contrast, our goal is to learn predictive models that provide recourses at high rates. Any of these methods can be used in conjunction with ours. Our work also builds on adversarial training [Szegedy et al., 2014, Goodfellow et al., 2015b, Bastani et al., 2016, Shaham et al., 2018]. While recent work in model explainability has leveraged adversarial training to improve robustness of explanations [Lakkaraju et al., 2020b], their goal is to reduce the rate of adversarial examples, whereas ours is to increase the rate of recourses.

heading: 2 Problem Formulation
text: Preliminaries. Consider a binary classifier f✓ : X ! Y , where x 2 X ✓ RnX are the features, y 2 Y = {0, 1} are the labels, and ✓ 2 ⇥ ✓ Rn⇥ are the parameters. We assume that f✓ has the form f✓(x) = (g✓(x) ✓0), where g✓ : X ! [0, 1] is a scoring function and ✓0 2 R is a decision threshold. We assume that g✓ is differentiable in x—i.e., rxg✓(x) exists almost everywhere.3
2Our code is available at https://github.com/alexisjihyeross/adversarial_recourse. 3Note that we have focused on real-valued features. We discuss how our algorithm can be extended to
handling categorical features in Section B.4.
Recourse. We seek to ensure that individuals given negative outcomes by f✓ are also given recourse. Definition 2.1. Given a classifier f✓ : X ! Y and a set ✓ RnX , an input x 2 X has recourse if there exists 2 such that f(x+ ) = 1.
We use XR✓ to denote the set of inputs for which recourse exists. The specific design of the set of permissible recourses ✓ RnX is domain specific. We assume that 0 2 ; then, recourse automatically exists for positive outcomes f✓(x) = 1 by taking = 0. In addition, we assume that is a polytope—i.e., = { 2 RnX | A + b 0} for some A 2 Rk·nX and b 2 Rk. That is, can be expressed as a set of affine constraints. This assumption is required for computational tractability.
A standard choice is = { | k k1  max}, which says that the recourse can suggest changes to any feature by a bounded amount. We can apply this constraint after an affine transformation of that appropriately scales different covariates. In addition, we often want to restrict features—e.g., to avoid suggesting that an individual change their age, we can constrain i = 0, or to avoid suggesting that an individual decrease their income to qualify for a loan, we can constrain i 0. In principle, can also be tailored to individuals—e.g., disallow suggesting increased education for individuals who cannot afford to do so. Finally, should be designed large enough so it includes a plausible recourse for every individual, yet small enough to ensure that the recourses do not overburden the individuals. All of these considerations are domain-specific; we describe our choices for datasets in our experiments in Section 4.
Probably Approximately has REcourse (PARE). Our goal is to ensure that recourse exists for most individuals. Given a confidence level ✏ 2 R>0, we say that ✓ approximately has recourse if
Pp(x) ⇥ x 2 XR✓ ⇤ 1 ✏,
i.e., recourse exists for f✓ with probability at least 1 ✏ w.r.t. the distribution p(x) over individuals. Then, our goal is to design an algorithm for estimating the model parameters ✓ so that f✓ approximately has recourse. To do so, our algorithm takes as input a held-out calibration dataset Z ✓ X ⇥Y of examples (x, y) ⇠ p, where p(x, y) is the distribution over labeled examples, and outputs model parameters ✓̂(Z). Then, as in the probably approximately correct (PAC) learning framework [Valiant, 1984], our algorithm might additionally fail due to the randomness in Z. Thus, given a second confidence level ↵ 2 R>0, we say that ✓̂ Probably Approximately has REcourse (PARE) if
Pp(Z) h ✓̂(Z) approximately has recourse i 1 ↵,
where p(Z) = Q
(x,y)2Z p(x, y). In other words, our algorithm produces a model that approximately has recourse with probability at least 1 over p(Z). Constructing a PARE classifier. Note that we can trivially obtain a PARE classifier f✓ by choosing the decision threshold ✓0 = 0, in which case f✓(x) = 1 for all x 2 X . However, this approach is undesirable since it assigns a positive outcome to all individuals. Instead, we want to maximize the performance of f✓ (e.g., in terms of accuracy, F1 score, etc.) subject to a constraint that f✓ is PARE. Thus, we divide the problem of constructing a PARE classifier into two parts (i) increasing recourse rate: we train g✓ in a way that heuristically increases the rate at which inputs x 2 X have recourse (for any ✓0), and (ii) guaranteeing recourse: we choose ✓0 to guarantee that the resulting f✓ is PARE.

heading: 3 Our Algorithm
text: We describe our algorithm for learning models that satisfy PARE while achieving good performance. We describe Step 1 (increasing recourse rate) in Section 3.1 and Step 2 (guaranteeing recourse) in Section 3.3. We describe ways to compute recourse in Section 3.2.

heading: 3.1 Step 1: Increasing Recourse Rate
text: Background: adversarial training. Consider a classifier f✓ : X ! Y and perturbations ✓ RnX . Given x 2 X , an adversarial example [Szegedy et al., 2014] for x is a perturbation 2 such that f✓(x+ ) 6= f✓(x)—i.e., the perturbation (restricted to be small) changes the predicted label of x. Adversarial examples are undesirable because they indicate that f✓ is not robust to small changes to the input that should not affect the class label (e.g., according to human predictions). Thus, there has
been a great deal of interest in designing algorithms for improving robustness to adversarial examples. The basic approach is adversarial training [Goodfellow et al., 2015b], which dynamically computes adversarial examples for inputs in the training set and adds these to the objective as additional training examples, as in data augmentation. In particular, given a loss function ` : R ⇥ Y ! R, where `(g✓(x), y) is the loss for training example (x, y), they seek to compute
✓⇤ = argmin ✓2⇥
`A(✓) where `A(✓) = Ep(x,y)  `(g✓(x), y) + ·max
2 `(g✓(x+ ), y) .
In `A(✓), the first term is the supervised learning loss, the second is the adversarially robust loss (i.e., encourage g✓ to be robust to adversarial examples x+ ), and 2 R 0 is a hyperparameter. The challenge in optimizing `A(✓) is computing the maximum over 2 . To address this challenge, existing adversarial training algorithms leverage approximations enabling efficient computation of .
Our approach. We use adversarial training to learn a model f✓ for which inputs x 2 X have recourse at higher rates compared to models trained using conventional approaches. There are two key differences compared to adversarial training. First, we want recourse to exist, which corresponds to encouraging the existence of adversarial examples. Second, we only care about changing negative labels f✓(x) = 0 to positive ones f✓(x+ ) = 1, not vice versa. Thus, we want to solve
✓⇤ = argmin ✓2⇥
`R(✓) where `R(✓) = Ep(x,y)  `(g✓(x), y) + ·min
2 `(g✓(x+ ), 1) . (1)
Compared to `A, `R has a different second term in two ways: (i) the maximum over with a minimum, and (ii) the label y is replaced with the label 1. We note that when = 0, Eq. 1 is supervised learning.
We optimize Eq. 1 using adversarial training [Goodfellow et al., 2015a, Shaham et al., 2018, Lakkaraju et al., 2020a], which performs stochastic gradient descent on `R(✓). The key challenge to computing r✓`R(✓) is computing the gradient of the second term, which can be rewritten as follows:
r✓ min 2
`(g✓(x+ ), 1) = r✓`(g✓(x+ ⇤), 1),
where ⇤ is the perturbation that maximizes the likelihood of positive outcome, or minimizes the loss between predicted and positive outcomes—i.e.,
⇤ = argmin 2 `(g✓(x+ ), 1). (2)
Computing ⇤ is computationally challenging; thus, we use a Taylor approximation of the loss `(g✓(x+ ), 1) ⇡ `(g✓(x), 1) +rx`(g✓(x), 1)> . Using this approximation, Eq. 2 becomes
⇤ = argmin 2 `(g✓(x+ ), 1) ⇡ argmin 2 rx`(g✓(x), 1)> ,
where we have dropped the term `(g✓(x), 1) since it is constant with respect to . Finally, note that the optimization problem on the last step is a linear program (LP), since we have assumed that 2 can be expressed as a set of affine constraints and since the objective is linear in . In summary, we optimize Eq. 1 using stochastic gradient descent, where at each step we solve an LP to approximate the second term—i.e., given parameters ✓i and example (xi, yi) on gradient step i, and step size ⌘i 2 R>0 on step i, we use the stochastic gradient update
✓i+1 = ✓i + ⌘i (r✓`(g✓(x), y) + ·r✓`(g✓(x+ ⇤i , 1)) where ⇤i = argmin 2 rx`(g✓(x), 1)> .

heading: 3.2 Computing Recourse
text: So far, we have focused on how to train a model f✓ that provides recourse. Once we have trained f✓, we still need a way to compute recourse for a given individual x—i.e., an algorithm A : X ! for computing x = A(x) such that f(x+ x) = 1. We describe three such algorithms; in general, any algorithm designed to output recourses can be used [Karimi et al., 2020a, Poyiadzi et al., 2020].
Gradient descent. The approach proposed in Wachter et al. [2017] can directly be applied to compute recourse. They solve the problem
x = argmin 2
{`(g✓(x+ , 1) + 0 · k k2},
where 0 2 R 0 is a hyperparameter, using gradient descent on . The term k k2 is designed to encourage the recourse to be small, which is often desirable in practice (we have excluded it from our formulation for simplicity). While this approach is generally effective, it can be very slow since we need to solve an optimization problem for each individual.
Adversarial training. We can also use adversarial training to compute recourse—i.e.,
x = argmin 2
rx`(g✓(x), 1)> .
This approach approximates the gradient descent approach, but can be computed much more efficiently. Furthermore, since our objective in Eq. 1 is designed to encourage this specific perturbation to provide recourse, it performs nearly as well as gradient descent when f✓ is trained with > 0.
Linear approximation. Finally, Ustun et al. [2019] propose an approach to compute recourse when f✓(x) = ( >x 0) is a linear model. In this case, they compute x using an integer linear program (ILP). For nonlinear models, we can instead use the linear approximation of g✓ near x. Letting x = A(x; 0, ) be the recourse generated by their algorithm, and using the Taylor expansion g✓(x0) ⇡ g✓(x) +rxg✓(x)>(x0 x), we can use their approach to compute the recourse
x = A(x; ✓0 g✓(x),rxg✓(x)).
However, this approach only works well when g✓ is approximately linear as a function of x; otherwise, the Taylor approximation may be poor and x may not satisfy the desired condition f✓(x+ x) = 1.

heading: 3.3 Step 2: Guaranteeing Recourse
text: Finally, we describe how we choose ✓0 to ensure f✓ provides recourse with high probability. Note that ✓0 also controls the fraction of individuals given a positive outcome without the need for recourse; thus, we choose ✓0 to optimize the performance of f✓ subject to a constraint that f✓ is PARE.
Background: PAC confidence sets. We build on work constructing PAC confidence sets [Park et al., 2020]. Given x 2 X , they construct a model h̃✓,⌧ : X ! P(Y) (where P is the power set) that returns the set of all labels y with score above threshold ⌧ 2 R—i.e.,
h̃✓,⌧ (x) = {y 2 Y | h✓(x, y) ⌧} where h✓(x, y) = ⇢ g✓(x) if y = 1 1 g✓(x) if y = 0.
Given ✏ 2 R>0, we say ⌧ is approximately correct if
Pp(x,y)[y 2 h̃✓,⌧ (x)] 1 ✏,
i.e., h̃✓,⌧ (x) contains the true label for x with high probability over p(x, y). Note that ⌧ = 0 satisfies this condition, since h̃✓,0(x) = {0, 1} for all x. The goal is to choose ⌧ as large as possible while ensuring approximate correctness.
Park et al. [2020] proposes an estimator ⌧̂ that takes as input (i) the pretrained model g✓ : X ! [0, 1], (ii) a calibration dataset Z ✓ X ⇥ Y of i.i.d. samples (x, y) ⇠ p, and (iii) confidence levels ✏,↵ 2 R>0, and constructs a threshold ⌧̂(Z) 2 [0, 1] that is probably approximately correct (PAC):
Pp(Z)[⌧̂(Z) is approximately correct] 1 ↵. (3)
In other words, ⌧̂(Z) is approximately correct with probability at least 1 ↵ according to p(Z). Their approach leverages the fact that ⌧̂(Z) is an estimator for a single parameter; thus, they can use learning theory to obtain PAC guarantees [Kearns et al., 1994].
PARE models via PAC confidence sets. Given a model g✓ : X ! R, an algorithm A : X ! for computing recourse, and a calibration set Z ✓ X ⇥ Y , our algorithm leverages PAC confidence sets to choose a threshold ✓0 = ✓̂0(Z) that ensures the resulting model f✓̂ satisfies the PARE constraint.
First, our algorithm uses the PAC confidence set algorithm to construct the new calibration dataset
Z 0 = {(x+A(x), 1) | (x, y) 2 Z}.
Intuitively, Z 0 says that the “correct” label for every input x + A should be 1—i.e., the recourse constructed by A should satisfy f✓(x+A(x)) = 1.
Then, our algorithm constructs h̃✓,⌧̂(Z) using g✓, Z 0, and the given ✏,↵. The PAC guarantee in Eq. 3 says that with probability at least 1 ↵ over p(Z), we have
Pp(Z) h Pp(x,y)[y0 2 h̃✓,⌧̂(Z0)(x0)] 1 ✏ i 1 ↵, (4)
where (x0, y0) 2 Z 0 is the example constructed from (x, y) 2 Z as described above. Note that the outer probability is over p(Z) since Z 0 is a deterministic function of the random variable Z. Plugging in the definitions x0 = x+A(x) and y0 = 1, Eq. 4 becomes
Pp(Z) h Pp(x,y)[1 2 h̃✓,⌧̂(Z0)(x+A(x))] 1 ✏ i 1 ↵,
and plugging in the definition of h̃✓,⌧ , it becomes
Pp(Z) ⇥ Pp(x,y)[g✓(x+A(x)) ⌧̂(Z 0)] 1 ✏ ⇤ 1 ↵. (5)
Then, our algorithm returns ✓̂0(Z) = ⌧̂(Z 0) (with given parameters ✓ as the remaining parameters). Since Eq. 5 is equivalent to the PARE condition, we have:
Theorem 3.1. ✓̂ satisfies the PARE condition.

heading: 4 Experiments
text: We evaluate our approach and show how it can effectively improve recourse rates while preserving accuracy. We also demonstrate how it can improve the correctness and robustness of recourses. In Appendix B, we provide additional results on how our approach affects fairness of models, as well as results on an NLP task with discrete covariates to demonstrate the flexibility of our framework.

heading: 4.1 Experimental Setup
text: Datasets. We use four real-world datasets. The first contains adult income information from the 1994 United States Census Bureau [Dua and Graff, 2017]. It includes information about adults’ demographics, education, and occupations. Each adult is labeled as making below or > $50K a year, which can be thought of as a proxy for whether an individual will be able to repay a loan or not. The second contains information collected by Propublica about criminal defendants’ compas recidivism scores [Angwin et al., 2016]. This dataset includes information about defendants’ demographics and crimes, and each defendant is labeled as having either a high or low likelihood of reoffending,
as measured by the compas assessment tool. The third dataset represents bail outcomes from two different U.S. state courts from 1990-2009 [Schmidt and Witte, 1988]. It includes information about individuals’ criminal histories and demographics. Each defendant is labeled as having a high or low risk of recidivism. The fourth dataset is the german credit dataset [Dua and Graff, 2017], which contains individuals’ demographic, personal, and financial information. Each applicant is labeled as either having high or low credit risk.
We standardize all continuous features to have mean 0 and variance 1. We randomly split each dataset into 80% train and 20% validation sets. We use 3 random data splits and report the mean across splits for the rest of this section, unless otherwise specified. For compas and adult, we hold out 500 examples from the validation set to form a test set; for german, we hold out 100 examples. For bail, we evaluate on a 500-instance subset of the test set. All results are reported on the test set.4
Models. All models are neural networks with 3 100-node hidden layers, dropout probability 0.3, and tanh activations. For evaluation, we choose the epoch achieving the highest validation F1 score.
Parameters. We experimented with values between 0.0 to 2.0 in increments of 0.2 and found that = 0.8 provided the best tradeoff between F1 score and recourse rate across all datasets; we evaluate how our results vary with below. For , we choose the set of actionable features (i.e., features that can be changed as part of the recourse) based on the dataset (two features for adult, bail, german; one for compas); we set max = 0.75 after standardizing features. (See Appendix B.2 for experiments investigating the effect of varying values of max). We also include domain-specific linear constraints in —e.g., for the adult dataset, recourse can only require that hours worked increases. See Appendix A.3 for more details about our choices of .
4Our processed datasets have sizes: adult ⇡ 32.5K, compas ⇡ 6K, bail ⇡ 8K, german ⇡ 1K.
We choose the decision threshold ✓0 to maximize F1 score rather than to obtain PAC guarantees, since our goal is to understand the tradeoffs between model performance and recourse rates with a fixed underlying predictive model f✓. We evaluate the effects of rigorously choosing ✓0 in Section 4.2.
Baselines. To the best of our knowledge, our approach is the first to train models with the objective of providing recourse at a higher rate. Thus, we compare to a baseline that omits our recourse loss—i.e., = 0.0. For our approach and this baseline, we evaluate the performance of each of the three different algorithms for computing recourse described in Section 3.2. We use the alibi implementation [Klaise et al., 2019] of the gradient descent algorithm for computing recourse [Wachter et al., 2017] and set the initial value of the hyperparameter 0 = 0.001. We use LIME [Ribeiro et al., 2016a] as our linear approximation method with the approach proposed by Ustun et al. [2019].
Metrics. We evaluate our approach and the baselines with the following metrics: (i) standard performance metrics of accuracy and F1 score, (ii) “recourse neg,” the proportion of instances x with negative original outcomes that receive recourse such that f(x) = 0 but f(x + ⇤) = 1, and (iii) “recourse all,” the proportion of all instances x such that either f(x) = 1 or f(x) = 0 but f(x+ ⇤) = 1. Metric (iii) is most useful for measuring rate of positive outcomes, since we want to include individuals who are originally assigned a positive outcome.

heading: 4.2 Efficacy of Our Framework
text: In Table 1, we show the performance and recourse rates of models trained with our approach and baseline models. Overall, our approach significantly improves recourse without sacrificing performance. Across datasets, models trained using our approach offer recourse at significantly higher rates than the baseline model, for both the “adversarial training” and “gradient descent” approaches to computing recourse. We do not observe this trend when using “linear approximation” to compute recourse; in this case, both the baseline and our approach perform poorly. We believe this effect can be explained by poor LIME approximations of f✓, which are exacerbated by adversarial training since it increases the nonlinearity of f✓. Figure 1 shows how these results vary with : F1 scores and accuracies are relatively stable as a function of .
In Figure 2, we plot how these results vary with ✓0 (for classifiers trained with = 0 and = 0.8 on a single data split), using the “adversarial training” method of computing recourse.5 High values of ✓0 lead to lower recourse rates in all cases. The curves for performance are similar for the baseline and for our approach, but the decline in recourse values begins at lower thresholds in the case of the baseline. Thus, our approach improves recourse for most choices of ✓0 without sacrificing performance. The trade-off between recourse and performance depends on the dataset. For adult, performance increases while recourse decreases since the majority label in this dataset is negative, whereas for bail and compas, performance and recourse both decrease as ✓0 increases since the majority label is positive.
Performance under PARE guarantees. Next, we show that we can often obtain PARE guarantees without significantly reducing performance. We compare the performance of choosing the decision threshold ✓0 to maximize F1 score to that of ✓0 chosen to obtain PARE classifiers. Specifically, for the latter, we compute ✓0 using the approach described in Section 3.3 with parameters ✏ = ↵ = 0.05. Then, we evaluate models at thresholds in 10 equally spaced increments from 0 to the upper bound and fix ✓0 to maximize F1 score. For these experiments, we use the “adversarial training” algorithm to compute recourse; we observed similar trends for the “gradient descent” algorithm.
Results are shown in Table 2. In all cases, choosing ✓0 to satisfy the PARE condition yields a classifier that returns recourse at a rate 1 ✏ = 0.95, which validates our theoretical guarantees. Furthermore, on all three datasets, the F1 score does not significantly decrease when imposing the PARE condition. We do see a decrease in F1 score for the baseline model on the adult dataset, but the decrease for our model is smaller, suggesting that our end-to-end framework of training models and fixing ✓0 is successful at guaranteeing recourse without a big drop in accuracy.6
5Note that the “recourse neg” values are low for = 0 because we use the “adversarial training” method to compute recourse, which builds on a fast linear approximation and thus does not exhaustively find recourses. We use this method instead of the more effective “gradient descent” method for efficiency, since the latter is less efficient and would require recomputing recourses for each threshold.
6We can obtain a weaker theoretical guarantee at a smaller cost in performance. For instance, applying PARE to our model in Table 2 with ✏ = ↵ = 0.25 results in an F1 score of 0.613 on the adult dataset.
Groundedness of recourses. One key question is whether the recourses of models trained with our approach are grounded in reality—i.e., whether they are plausible modifications of the ground truth label. For instance, if an individual is denied a loan, they should be given a recourse such that if they take the specified action, they actually increase their likelihood of paying back the loan; an individual may increase their income and be given a loan, but still fail to repay it. We want to ensure that our training approach increases the rate of recourses that obey causal relationships in the world, rather than recourses that exploit spurious correlations between features. Directly evaluating groundedness of recourses is challenging, since we do not know the ground truth labels for suggested recourses. Thus, we evaluate whether they are causally grounded and in-distribution.
First, we measure the rate at which causally grounded recourses are offered by models trained with our approach. We apply the algorithm for computing causal recourses (CR) introduced by Karimi et al. [2020b] to evaluate whether our proposed training algorithm improves the rate at which causally grounded recourses are offered. Because CR requires access to an underlying structural causal model (SCM) of the world, we only experiment with the german dataset, for which Karimi et al. [2020b] provide an associated SCM. We measure the proportion of test instances x for which the CR algorithm computes a valid recourse that satisfies the constraint that perturbations be bounded by max—i.e. “recourse neg”.7 As shown in Figure 3, with increasing , the rate at which recourses are by the CR algorithm increases. This finding suggests that our training algorithm encourages the existence of causally grounded recourses.
Second, we evaluate whether the recourses offered by models trained with our approach are indistribution with respect to the original training data. In line with prior work [Slack et al., 2020], we train classifiers to distinguish between original data instances and recourses computed by the “gradient descent” algorithm for models trained with our approach ( = 0.8). In Table 3, we report the accuracies of these classifiers on a held out test set. The low classifier accuracies across all datasets indicate that these recourses are indistinguishable from original data instances. Thus, our framework encourages the existence of recourses that are in-distribution to the original data.
Robustness. Another key question is whether the recourses generated using our approach are robust— i.e., whether small changes to the recourse result in valid recourses. For instance, if an individual
7We select hyperparameters for the CR algorithm that maximize “recourse neg” on the train set.
increases their income by more (or even slightly less) than the amount suggested in the recourse, they would expect to still be provided with a positive decision.
For each computed recourse , we compute a noisy recourse 0 by adding i.i.d. Gaussian noise to each actionable feature of —i.e., 0i = i +N (0, 0.1). We consider a recourse robust if its noisy recourse 0 is valid—i.e. if f(x + 0) = 1. In the top row of Table 4, we report the percentage of recourses found that are robust for a baseline model and model trained with our adversarial approach. As shown, our training approach does not significantly reduce the robustness of recourses: There is a slight drop in robustness for the adult dataset and for the “gradient descent” recourse algorithm for the german dataset; however, for compas and bail, recourses remain robust.
Effect on classifier brittleness. We also investigate the effect of our adversarial training approach on model brittleness. In particular, we measure how sensitive models trained with our adversarial algorithm are to noises in the recourse dimensions, as compared to baseline models. We add i.i.d. Gaussian noise, as described above, to the actionable dimensions of original inputs, and compute the proportion of test instances for which the trained model is robust to this noise. As shown in the bottom row of Table 4, our training approach does not significantly increase model brittleness—we observe a small drop in model robustness in the recourse dimensions for the adult and german datasets and a small increase in robustness for the compas and bail datasets. These results suggest that our training approach effectively ensures recourse without rendering classifiers brittle.

heading: 5 Conclusion
text: We have proposed a novel algorithm for training models that are guaranteed to provide recourse for reversing adverse outcomes with high probability. Our experiments show that our algorithm trains models that provide recourse at high rates without sacrificing accuracy compared to traditional learning algorithms. Future work includes extending our techniques beyond binary classification.

heading: Acknowledgements
text: We would like to thank the anonymous reviewers for their insightful feedback. This work is supported in part by the NSF awards #IIS-2008461, #IIS-2040989, and #CCF-1910769, and research awards from the Harvard Data Science Institute, Amazon, Bayer, and Google. The views expressed are those of the authors and do not reflect the official policy or position of the funding agencies.

Review summaries:
The paper proposes the idea of training machine models that are effectively recourse ready. The authors propose leveraging adversarial training and PAC confidence sets to train models that "theoretically guarantee recourse". The experiments with four datasets demonstrate increased recourse rates while sacrificing accuracy mildly.  

The author(s) proposed an adversarial training-based classification algorithm that guarantees affected individuals receive recourse with a high probability. The paper considers an interesting topic. The numerical experiments demonstrate the effectiveness of the proposed algorithm.