Probabilistically Robust Recourse: Navigating the Trade-offs between Costs and Robustness in Algorithmic Recourse

Introduction

Machine learning (ML) models are increasingly being deployed to make a variety of consequential decisions in domains such as finance, healthcare, and policy. Consequently, there is a growing emphasis on designing tools and techniques which can provide recourse to individuals who have been adversely impacted by the predictions of these models (Voigt & Von dem Bussche, 2017). For example, when an individual is denied a loan by a model employed by a bank, they should be informed about the reasons for this decision and what can be done to reverse it. To this end, several approaches in recent literature tackled the problem of providing recourse by generating counterfactual explanations (Wachter et al., 2018; Ustun et al., 2019; Karimi et al., 2020a). which highlight what features need to be changed and by how much to flip a model’s prediction. While the aforementioned approaches output low cost recourses that are easy to implement (i.e., the corresponding counterfactuals are close to the original instances), the resulting recourses suffer from a severe lack of robustness as demonstrated by prior works (Pawelczyk et al., 2020b; Rawal et al., 2021). For example, the aforementioned approaches generate recourses which do not remain valid (i.e., result in a positive model prediction) if/when small changes are made to them (See Figure 1(a)). However, recourses are often noisily implemented in real world settings as noted by prior research (Björkegren et al., 2020). For instance, an individual who was asked to increase their salary by $500 may get a promotion which comes with a raise of$505 or even $499.95.

Prior works by Upadhyay et al. (2021) and Dominguez-Olmedo et al. (2022) proposed methods to address some of the aforementioned challenges and generate robust recourses. While the former constructed recourses that are robust to small shifts in the underlying model, the latter constructed recourses that are robust to small input perturbations. These approaches adapted the classic minimax objective functions commonly employed in adversarial robustness and robust optimization literature to the setting of algorithmic recourse, and used gradient descent style approaches to optimize these functions. In an attempt to generate recourses that are robust to either small shifts in the model or to small input perturbations, the above approaches find recourses that are farther away from the underlying model’s decision boundaries (Tsipras et al., 2018; Raghunathan et al., 2019), thereby increasing the recourse costs i.e., the distance between the counterfactuals (recourses) and the original instances. Higher cost recourses are harder to implement for end users as they are farther away from the original instance vectors (current user profiles). Putting it all together, the aforementioned approaches generate robust recourses that are often high in cost and are therefore harder to implement (See Figure 1(c)), without providing end users with any say in the matter. In practice, each individual user may have a different preference for navigating the trade-offs between recourse costs and robustness – e.g., some users may be willing to tolerate additional cost to avail more robustness to noisy responses, whereas other users may not.

In this work, we address the aforementioned challenges by proposing a novel algorithmic framework called Probabilistically ROBust rEcourse (PROBE) which enables end users to effectively manage the recourse cost vs. robustness trade-offs by letting users choose the probability with which a recourse could get invalidated (recourse invalidation rate) if small changes are made to the recourse i.e., the recourse is implemented somewhat noisily (See Figure 1(b)). To the best of our knowledge, this work is the first to formulate and address the problem of enabling users to navigate the trade-offs between recourse costs and robustness. Our framework can ensure that a resulting recourse is invalidated at most $r\%$ of the time when it is noisily implemented, where $r$ is provided as input by the end user requesting recourse. To operationalize this, we propose a novel objective function which simultaneously minimizes the gap between the achieved (resulting) and desired recourse invalidation rates, minimizes recourse costs, and also ensures that the resulting recourse achieves a positive model prediction. We develop novel theoretical results to characterize the recourse invalidation rates corresponding to any given instance w.r.t. different classes of underlying models (e.g., linear models, tree based models etc.), and leverage these results to efficiently optimize the proposed objective.

We also carried out extensive experimentation with multiple real-world datasets. Our empirical analysis not only validated our theoretical results, but also demonstrated the efficacy of our proposed framework. More specifically, we found that our framework PROBE generates recourses that are not only three times less costly than the recourses output by the baseline approaches (Upadhyay et al., 2021; Dominguez-Olmedo et al., 2022), but also more robust (See Table 1). Further, our framework PROBE reliably identified low cost recourses at various target recourse invalidation rates $r$ in case of both linear and non-linear classifiers (See Table 1 and Figure 4). On the other hand, the baseline approaches were not only ill-suited to achieve target recourse invalidation rates but also had trouble finding recourses in case of non-linear classifiers.

Related Work

Algorithmic Approaches to Recourse. As discussed earlier, several approaches have been proposed in literature to provide recourse to individuals who have been negatively impacted by model predictions (Tolomei et al., 2017; Laugel et al., 2017; Wachter et al., 2018; Ustun et al., 2019; Van Looveren & Klaise, 2019; Pawelczyk et al., 2020a; Mahajan et al., 2019; Mothilal et al., 2020; Karimi et al., 2020a; Rawal & Lakkaraju, 2020; Karimi et al., 2020b; Dandl et al., 2020; Antorán et al., 2021; Spooner et al., 2021). These approaches can be roughly categorized along the following dimensions (Verma et al., 2020): type of the underlying predictive model (e.g., tree based vs. differentiable classifier), whether they encourage sparsity in counterfactuals (i.e., only a small number of features should be changed), whether counterfactuals should lie on the data manifold and whether the underlying causal relationships should be accounted for when generating counterfactuals, All these approaches generate recourses assuming that the prescribed recourses will be correctly implemented by users.

Robustness of Algorithmic Recourse. Prior works have focused on determining the extent to which recourses remain robust to the choice of the underlying model (Pawelczyk et al., 2020b; Black et al., 2021; Pawelczyk et al., 2023), shifts or changes in the underlying models (Rawal et al., 2021; Upadhyay et al., 2021), or small perturbations to the input instances (Artelt et al., 2021; Dominguez-Olmedo et al., 2022; Slack et al., 2021). To address these problems, these works have primarily proposed adversarial inimax objectives to minimize the worst-case loss over a plausible set of instance perturbations for linear models to generate robust recourses (Upadhyay et al., 2021; Dominguez-Olmedo et al., 2022), which are known to generate overly costly recourse suggestions.

In contrast to the aforementioned approaches our work focuses on a user-driven framework for navigating the trade-offs between recourse costs and robustness to noisy responses by suggesting a novel probabilistic recourse framework. To this end, we present several algorithms that enable us to handle both linear and non-linear models (e.g., deep neural networks, tree based models) effectively, resulting in better recourse cost/invalidation rate tradeoffs compared to both Upadhyay et al. (2021) and Dominguez-Olmedo et al. (2022).

Preliminaries

Here, we first discuss the generic formulation leveraged by several state-of-the-art recourse methods including Wachter et al. (2018). We then define the notion of recourse invalidation rate formally.

2 Defining the Recourse Invalidation Rate

In order to enable end users to effectively navigate the trade-offs between recourse costs and robustness, we let them choose the probability with which a recourse could get invalidated (recourse invalidation rate) if small changes are made to it i.e., the recourse is implemented somewhat noisily. To this end, we formally define the notion of Recourse Invalidation Rate (IR) in this section. We first introduce two key terms, namely, prescribed recourses and implemented recourses. A prescribed recourse is a recourse that was provided to an end user by some recourse method (e.g., increase salary by $500). An implemented recourse corresponds to the recourse that the end user finally implemented (e.g., salary increment of$505) upon being provided with the prescribed recourse. With this basic terminology in place, we now proceed to formally define the Recourse Invalidation Rate (IR) below.

For a given classifier $h$, the recourse invalidation rate corresponding to the counterfactual $\check{\mathbf{x}}_{E}=\mathbf{x}+\bm{\delta}_{E}$ output by a recourse method $E$ is given by:

where the expectation is taken with respect to a random variable $\bm{\varepsilon}$ with probability distribution $p_{\bm{\varepsilon}}$ which captures the noise in human responses.

Since the implemented recourses do not typically match the prescribed recourses $\check{\mathbf{x}}_{E}$ (Björkegren et al., 2020), we add $\bm{\varepsilon}$ to model the noise in human responses. As we primarily compute recourses for individuals $\mathbf{x}$ such that $h(\mathbf{x})=0$, the label corresponding to the counterfactual is given by $h(\check{\mathbf{x}}_{E}){=}1$ and therefore $\Delta\in$. For example, the following cases help understand our recourse invalidation rate metric better: When $\Delta{=}0$, then the prescribed recourse and the recourse implemented by the user agree all the time; when $\Delta{=}0.5$, the prescribed recourse and the implemented recourse agree half of the time, and finally, when $\Delta{=}1$ then the prescribed recourse and the recourse implemented by the user never agree. To illustrate our ideas, we will use our IR measure with a Gaussian probability distribution (i.e., $\bm{\varepsilon}\sim\mathcal{N}(\mathbf{0},\sigma^{2}\mathbf{I}))$ to model the noise in human responses.

Our Framework: Probabilistically Robust Recourse

Below we present our objective function, which is followed by a discussion on how to operationalize it efficiently.

The core idea is to find a recourse $\check{\mathbf{x}}$ whose prediction at any point y within some set around $\check{\mathbf{x}}$ belongs to the positive class with probability $1-r$. Hence, our goal is to devise an algorithm that reliably guides the recourse search towards regions of low invalidation probability while maintaining low cost recourse (see Fig. 2 for a practical example). For a fixed model, our objective reads:

where $s$ is the target score for the input $\mathbf{x}$, $R(\mathbf{x}^{\prime};r,\sigma^{2}\mathbf{I})=\max(0,\Delta(\mathbf{x}^{\prime};\sigma^{2}\mathbf{I})-r)$ with $r$ being the target IR, $\Delta(\mathbf{x}^{\prime};\sigma^{2}\mathbf{I})$ is the recourse invalidation rate from equation 1, $\lambda_{1}$ to $\lambda_{3}$ are the balance parameters, and $d_{c}$ quantifies the distance between the input and the prescribed recourse. To arrive at a output probability of $0.5$, the target score for $f(\mathbf{x})$ for a sigmoid function is $s=0$, where the score corresponds to a $0.5$ probability for $y=1$.

The new component $R$ is a Hinge loss encouraging that the prescribed recourse has a low probability of invalidation, and the parameter $\sigma^{2}$ is the uncertainty magnitude and controls the size of the neighbourhood in which the recourse has to be robust. The middle term encourages the score at the prescribed recourse $f(\check{\mathbf{x}})$ to be close to the target score $s$, while the last term promotes the distance between the input $\mathbf{x}$ and the recourse $\check{\mathbf{x}}$ to be small.

In practice, the choice of $r$ depends on the risk-aversion of the end-user. If the end-user is not confident about achieving a ‘precision landing’, then a rather low invalidation target should be chosen (i.e., $r<0.5$).

2 Optimizing the recourse invalidation rate aware objective

where $\Phi$ is the CDF of the univariate standard normal distribution $\mathcal{N}(0,1)$, $f(\check{\mathbf{x}}_{E})$ denotes the logit score at $\check{\mathbf{x}}_{E}$ which is the recourse output by a recourse method $E$, and $h(\check{\mathbf{x}}_{E})\in\{0,1\}$.

We now leverage the recourse invalidation rate derived in Theorem 1 to show how the recourses output by Wachter et al. (2018) can be made more robust. Pawelczyk et al. (2022) provide a closed-form solution for the recourse output by Wachter et al. (2018) w.r.t. the special case of a logistic regression classifier when $d_{c}=\lVert\mathbf{x}-\mathbf{x}^{\prime}\rVert_{2}$ and the MSE-loss is used. This solution takes the following form: $\check{\mathbf{x}}_{\text{Wachter}}(s)=\mathbf{x}+\frac{s-f(\mathbf{x})}{\lVert\nabla f(\mathbf{x})\rVert_{2}^{2}}\nabla f(\mathbf{x})$, where $s$ is the target logit score. More specifically, to arrive at the desired class with probability of $0.5$, the target score for a sigmoid function is $s=0$, where the logit corresponds to a $0.5$ probability for $y=1$. The next statement quantifies the IR of recourses output by Wachter et al. (2018).

For logistic regression, consider the recourse output by Wachter et al. (2018): $\check{\mathbf{x}}_{\text{Wachter}}(s)=\mathbf{x}+\frac{s-f(\mathbf{x})}{\lVert\nabla f(\mathbf{x})\rVert_{2}^{2}}\nabla f(\mathbf{x})$. Then the recourse invalidation rate is given by:

A recourse generated by Wachter et al. (2018) such that $f(\check{\mathbf{x}}_{\text{Wachter}})=s=0$ will result in $\Delta=0.5$. To obtain recourse that is more robust to noisy responses from users, i.e., $\Delta\xrightarrow{}0$, the decision maker can choose a higher logit target score of $s^{\prime}>s\geq 0$ since this decreases the recourse invalidation rate, i.e., $\Delta(\check{\mathbf{x}}_{\text{Wachter}}(s))>\Delta(\check{\mathbf{x}}_{\text{Wachter}}(s^{\prime}))$. The next statement makes precise how $s$ should be chosen to achieve a desired robustness level.

Under the conditions of Proposition 1, choosing $s_{r}=\sigma\lVert\nabla f(\mathbf{x})\rVert_{2}\Phi^{-1}(1-r)$ guarantees a recourse invalidation rate of $r$, i.e., $\Delta(\check{\mathbf{x}}_{\text{Wachter}}(s_{r});\sigma^{2}\mathbf{I})=r$.

On extensions to general noise distributions, and tree-based classifiers. In Appendix A we present extensions of our framework to obtain (i) reliable recourses for general noise distributions and (ii) tree-based classifiers. These two cases pose non-trivial difficulties as the recourse invalidation rate is generally non-differentiable. As for the more general noise distributions, we develop a Monte-Carlo approach in appendix A.1, which relies on a differentiable approximation of the indicator function required to obtain a Monte-Carlo estimate of the invalidation rate. For tree-based classifiers, we develop a closed-form solution for the recourse invalidation rate (see Theorem 2).

3 Additional Theoretical Results

In this section, we leverage the recourse invalidation rate expression derived in the previous section to theoretically show i) that an additional cost has to be incurred to generate robust recourses in the face of noisy human responses, and ii) we derive a general upper bound on the IR which is applicable to any valid recourse provided by any method with the underlying classifier being a differentiable model.

Next, we show that there exists a trade-off between robustness to noisy human responses and cost. To this end, we fix the target invalidation rate $r$, and ask what costs are needed to achieve a fixed level $r$:

For a linear classifier, let $r\in(0,1)$ and let $\check{\mathbf{x}}_{E}=\mathbf{x}+\bm{\delta}_{E}$ be the output produced by some recourse method $E$ such that $h(\check{\mathbf{x}}_{E})=1$. Then the cost required to achieve a fixed invalidation target $r$ is:

where $c=\frac{f(\mathbf{x})}{\sigma\cdot\lVert\nabla f(\mathbf{x})\rVert_{2}}$ is a constant, and $\omega>0$ is the cosine of the angle between $\nabla f(\mathbf{x})$ and $\bm{\delta}_{E}$.

From Proposition 2, we see that the target invalidation rate $r$ decreases as the recourse cost increases for a given uncertainty magnitude $\sigma^{2}$. To make this more precise the next statement demonstrates the cost-robustness tradeoff.

Under the same conditions as in Proposition 2, we have $\frac{\partial\lVert\bm{\delta}_{E}\rVert_{2}}{\partial(1-r)}=\frac{\sigma}{\omega}\frac{1}{\phi(\Phi^{-1}(1-r))}>0$, i.e., an infinitesimal increase in robustness (i.e.,$1-r$) increases the cost of recourse by $\frac{\sigma}{\omega}\frac{1}{\phi(\Phi^{-1}(1-r))}$.

Now, we derive a general upper bound on the recourse invalidation rate. This bound is applicable to any method $E$ that provides recourses resulting in a positive outcome.

where $c=\frac{f(\mathbf{x})}{\sigma\cdot\lVert\nabla f(\mathbf{x})\rVert_{2}}$, $\bm{\delta}_{E}=\check{\mathbf{x}}_{E}-\mathbf{x}$, and $\omega>0$ is the cosine of the angle between $\nabla f(\mathbf{x})$ and $\bm{\delta}_{E}$.

Experimental Evaluation

We now present our empirical analysis. First, we validate our theoretical results on the recourse invalidation rates across various recourse methods. Second, we study the effectiveness of PROBE at finding robust recourses in the presence of noisy human responses.

Real-World Data and Noisy Responses. Regarding real-world data, we use the same data sets as provided in the recourse and counterfactual explanation library CARLA (Pawelczyk et al., 2021). The Adult data set Dua & Graff (2017) originates from the 1994 Census database, consisting of 14 attributes and 48,842 instances. The class label indicates whether an individual has an income greater than 50,000 USD/year. The Give Me Some Credit (GMC) data set Kaggle-Competition (2011) is a credit scoring data set, consisting of 150,000 observations and 11 features. The class label indicates if the corresponding individual will experience financial distress within the next two years (SeriousDlqin2yrs is 1) or not. The COMPAS data set Angwin et al. (2016) contains data for more than 10,000 criminal defendants in Florida. It is used by the jurisdiction to score defendant’s likelihood of re-offending. The class label indicates if the corresponding defendant is high or low risk for recidivism. All the data sets were normalized so that $\mathbf{x}\in^{d}$. Across all experiments, we add noise $\bm{\varepsilon}$ to the prescribed recourse $\check{\mathbf{x}}_{E}$, where $\bm{\varepsilon}\sim\mathcal{N}(\mathbf{0},\sigma^{2}\cdot\mathbf{I})$ and $\sigma^{2}=0.01$.

Methods. We compare the recourses generated by PROBE to four different baseline methods which aim to generate low-cost recourses using fundamentally different principles: AR (-LIME) uses an integer-programming-based objective Ustun et al. (2019), Wachter uses a gradient-based objective (Wachter et al., 2018), DICE uses a diversity-based objectve (Mothilal et al., 2020), and GS is based on a random search algorithm (Laugel et al., 2017). Further, we compare with methods that use adversarial minmax objectives to generate robust recourse (Dominguez-Olmedo et al., 2022; Upadhyay et al., 2021). We used the recourse implementations from CARLA (Pawelczyk et al., 2021). Following Upadhyay et al. (2021), all methods search for counterfactuals over the same set of balance parameters $\lambda\in\{0,0.25,0.5,0.75,1\}$ when applicable.

Prediction Models. For all data sets, we trained both ReLU-based NN models with 50 hidden layers (App. B) and a logistic regerssion (LR). All recourses were generated with respect to these classifiers.

Computing Bounds. We empirically validate the theoretical upper bounds derived in Section 4.3. To do that, we first estimate the bounds for each instance in the test set according to Proposition 4, and compare them with the empirical estimates of the IR. The empirical IR, in turn, we obtain from Monte-Carlo estimates of the IR in equation 2; we used 10,000 samples to get a stable estimate of IR.

2 Evaluating the PROBE Framework

Results. Here, we evaluate the robustness, costs and recourse accuracy of the recourses generated by our framework PROBE relative to the baselines. We consider a recourse robust if the recourse remains valid (i.e., results in positive outcome) even after small changes are made to it (i.e., humans implement it in a noisy manner). Table 1 shows the average IR for different methods across different real world data sets and classifiers when $\sigma^{2}=0.01$. Further, in Table 1(a) we see that PROBE has the lowest invalidation rate across all real-world data sets and classifiers among the non-robust recourse methods, while PROBE provides the lowest cost recourses among the robust recourse methods (see Table 1(b)). We also consider if the robustness achieved by our framework is coming at an additional cost i.e., by sacrificing recourse accuracy (RA) or by increasing the average recourse cost (AC). We compute AC of the recourses output by all the algorithms and find that PROBE usually has the highest or second highest recourse costs, while the RA is at 100% across classifiers and data sets.

Finally, we provide a more detailed comparison between PROBE and the adversarially robust recourse methods ARAR and ROAR. To do so, we plot pareto frontiers in Figure 4 which demonstrate the inherent tradeoffs between the average cost of recourse and the average recourse invalidation rate computed over all recousre seeking individuals for different uncertainty magnitudes $\sigma^{2},\epsilon\in\{0.005,0.01,0.15\}$. For ARAR and ROAR we expect to see AIRs close to 0 (by construction). However, this is only the case for the linear classifiers. Moreover, ROAR provide recourses with up to 3 times higher cost relative to our method PROBE. Note also that ARAR and ROAR have trouble finding recourses for non-linear classifiers, resulting in RA scores of around 5% in the worst case, while not being able to maintain low invalidation scores. This is likely due to the local linear approximation used by these methods. In summary, PROBE finds recourses for 100% of the test instances in line with the promise of having an invalidation probability of at most $r$, while being less costly than ROAR and ARAR.

Relegated results. The relegated experiments in Appendix C (i) demonstrate that baseline recourse methods are not robust to noisy human responses (Figures 8 - 9), (ii) verify that the targeted invalidation rates match the empirical recourse invalidation rates (Figures 13 - 15) and (iii) demonstrate the trade-off between recourse costs and robustness verifying Corollary 3 (Figures 16 - 17).

Conclusion

In this work, we proposed a novel algorithmic framework called Probabilistically ROBust rEcourse (PROBE) which enables end users to effectively manage the recourse cost vs. robustness trade-offs by letting users choose the probability with which a recourse could get invalidated (recourse invalidation rate) if small changes are made to the recourse i.e., the recourse is implemented somewhat noisily. To the best of our knowledge, this work is the first to formulate and address the problem of enabling users to navigate the trade-offs between recourse costs and robustness. Our framework can ensure that a resulting recourse is invalidated at most $r\%$ of the time when it is noisily implemented, where $r$ is provided as input by the end user requesting recourse. To operationalize this, we proposed a novel objective function which simultaneously minimizes the gap between the achieved (resulting) and desired recourse invalidation rates, minimizes recourse costs, and also ensures that the resulting recourse achieves a positive model prediction. We developed novel theoretical results to characterize the recourse invalidation rates corresponding to any given instance w.r.t. different classes of underlying models (e.g., linear models, tree based models etc.), and leveraged these results to efficiently optimize the proposed objective. Experimental evaluation with multiple real world datasets not only demonstrated the efficacy of the proposed framework, but also validated our theoretical findings. Our work also paves the way for several interesting future research directions in the field of algorithmic recourse. For instance, it would be interesting to build on this work to develop approaches which can generate recourses that are simultaneously robust to noisy human responses, noise in the inputs, as well as shifts in the underlying models.

We would like to thank the anonymous reviewers for their insightful feedback. This work is supported in part by the NSF awards #IIS-2008461 and #IIS-2040989, and research awards from Google, JP Morgan, Amazon, Bayer, Harvard Data Science Initiative, and D^3 Institute at Harvard. HL would like to thank Sujatha and Mohan Lakkaraju for their continued support and encouragement. The views expressed here are those of the authors and do not reflect the official policy or position of the funding agencies.

References

Appendix A Extensions to Other Noise Distributions and Tree Based Classifiers

In section 4 we have introduced our PROBE framework, which enables us to guide the search for counterfactual explanations towards regions with a targeted low invalidation rate. Recall that the optimization procedure in Section 4 relied on a first-order approximation to the recourse invalidation rate under Gaussian distributed noisy human responses. In this section, we develop an algorithm that is agnostic to the specifics of the parameterized noise distribution. To this end, we suggest a Monte Carlo estimator of the recourse IR from Def. 1, i.e.,

Since it is up to us to choose $K$, we can make the MSE arbitrarily small and reliably estimate the true invalidation rate $\Delta(\mathbf{x}^{\prime})$.

A.2 Extensions to tree based classifiers

The recourse literature commonly considers consequential decision problems which heavily rely on the usage of tabular data. For this data modality, ensembles of decision trees such as Random Forest (RF) (Breiman, 2001) or Gradient Boosted Boosted Decision Trees (GBDT) (Friedman, 2001) are considered among the state-of-the-art models (Borisov et al., 2021). As a consequence, some recourse methods were developed to find recourses for tree ensembles (Tolomei et al., 2017; Lucic et al., 2022) where the non-differentiability prevents a direct application of the recourse objective in equation 1. To extend our method to tree-based classifiers, we also derive an IR expression for tree ensembles, and develop a method which computes low IR recourses for these models.

An object of interest is the predicted output of a decision tree:

where $c_{\mathcal{T}}(R)\in\{0,1\}$ is the constant prediction assigned in region $R\in\mathcal{R}_{\mathcal{T}}$ for tree $\mathcal{T}$. Moreover, a decision forest is formed by a set of $M_{T}$ decision trees, and forms the probabilistic output:

The predicted class of an input $\mathbf{x}$ is formed via a vote by the trees where each tree assigns a probability estimate to the input. That is, the predicted class is the one with highest mean probability estimate across the trees. After the trees are combined, the multiple models form a single model again (Domingos, 1997). Thus, the corresponding predicted class of equation 13 is given by:

where $c_{\mathcal{F}}(R)\in\{0,1\}$ is the constant prediction assigned in region $R\in\mathcal{R}_{\mathcal{F}}$ for the ensemble of trees $\mathcal{F}$. Furthermore, note that for each ensemble, there is an active subset of ensemble-specific features $\mathcal{S}_{\mathcal{F}}\subseteq\{1,\dots,d\}$ on which axis-aligned splits took place. Finally, we note that this formulation is quite general as it subsumes a large class of popular tree-based models such as Random Forests (RF) and Gradient Boosted Decision Trees (GBDT).

A.3 The Recourse IR for Tree Ensemble Classifiers

Consider the decision forest classifier in equation 14. The recourse invalidation rate under Gaussian distributed response inconsistencies $\bm{\varepsilon}\sim\mathcal{N}(\mathbf{0},\bm{\sigma}^{2}\mathbf{I})$ is given by:

and where $\Phi$ is the Gaussian CDF, $\bar{t}_{j,R}$ and $\underline{t}_{j,R}$ are the upper and lower points corresponding to feature $j\in\mathcal{S}_{\mathcal{F}}$ that define the hypercube formed by region $R$.

The proof uses the insight that a decision forest based on trees with axis-aligned splits partions the input space into hypercubes where the prediction is either or $1$. It then remains to evaluate Gaussian integrals subject to the constrains set by the hypercubes. The full proof is given in Appendix D.3. ∎

Our proof of Theorem 2 assumed that the split points $\bar{t}_{j,R}$ and $\underline{t}_{j,R}$, corresponding to the tree-ensemble, are readily available. However, the hypercubes formed by the tree-ensemble, for which the prediction is constant, is a function of all individual trees, and of how they are combined. Thus, the clear-cut division into hypecrubes present in each of the trees got lost in the process of model averaging.

We suggest a solution to this problem by using a technique called model distillation (Domingos, 1997; Bucilua et al., 2006; Hinton et al., 2015; Phuong & Lampert, 2019). In a nutshell: We wish to change the form of the model (to a simpler decision tree) while keeping the same knowledge (from our tree ensemble) (Hinton et al., 2015). Thus, the goal of this technique is to distil the knowledge of a larger model (possibly an ensemble) into a single, small (and interpretable) model. In our case, the ensemble is formed by decision trees, and the target model is a decision tree as well. Second, the method is simple to operationalize: let $h$ be your complex model, and $g$ denotes the simple model. Then we use our data $\{\mathbf{x}_{i},y_{i}\}_{i=1}^{n}$ to train and validate the model $h$. The target model, however, is trained on samples from $\{\mathbf{x}_{i},h(\mathbf{x}_{i})\}_{i=1}^{n}$ to mimic the behaviour of the complex model. We refer to panels 1 to 3 in Figure 7 to gain some intuition on how this technique works on a non-linear 2-dimensional data set.

Appendix B Experimental Details

In this section, we describe the hyperparameter choices and how the classification models were fitted. We have used CARLA’s built-in functionality to fit classifiers using PyTorch (Paszke et al., 2019) and treat all variables as continuous. We set $\lambda_{1}=2$, $\lambda_{2}=1$ and search over $\lambda_{3}$ in the usual way (Wachter et al., 2018). All models use a $80-20$ train-test split for model training and evaluation. We evaluate model quality based on the model accuracy. All models are trained with the same architectures across the data sets:

Appendix C Additional Experiments

In this Section we show a set of additional experiments. Since this work is the first to highlight and address the problem of recourse invalidation in the face of noisy human responses, we demonstrate in Figures 8 and 9 that recourses generated by state-of-the-art approaches are, on average, invalidated up to 50% of the time when small changes are made to them. It is worth highlighting that the maximum invalidation scores can become as high as 61%, which motivates the need for a recourse method that rightly controls the invalidation rate.

C.2 Missing Figures from the Main Text

Below, we show the Figure that was missing from the main text due to space constraints. To keep the plots below more readable, we have omitted DICE from them as both the bounds implied by DICE, the results on cost and the remaining measures are similar to the one by Wachter.

C.3 Verifying the Validity of the Empirical Invalidation Rate

In Figures 13, 14, and 15 we show that the IRs of the recourses by our framework can be controlled setting $r$ to desired values.

C.4 Demonstrating the Cost-Robustness Tradeoff

In Figures 16 and 17 we demonstrate that there exists a tradeoff between recourse costs and the robustness of recourse to noisy response.

C.5 Detailed Comparison with ROAR and ARAR

In this section we compare our method with two approaches that aim at generating robust algorithmic recourse in different settings. We further report results by DICE, which does not generate robust recourse. Thus, we PROBE the cost performance (i.e., AC) by DICE to serve as a lower bound, while its robustness performance would serve as an upper bound (i.e., AIR). Regarding the methods that suggest robust recourse we refer to Upadhyay et al. (2021) who proposed a minimax objective to generate recourses that are robust to model updates (ROAR), while Dominguez-Olmedo et al. (2022) use a slight variation of this objective to find recourses that are robust to uncertainty in the inputs (ARAR). Moreover, on a high-level, these objectives differ from our approach since the epsilon neighborhoods that PROBE constructs are probabilistic.

The AIR for PROBE should be at most $0.35$, in line with our results. For ARAR and ROAR, we should expect AIRs close to 0, which is only the case for the linear classifiers. Additionally, ARAR and ROAR provide recourses with up to 10 times higher cost relative to our method PROBE. Note also that ARAR and ROAR have trouble finding recourses for non-linear classifiers, resulting in RA scores of around 5% in the worst case, while not being able to maintain low invalidation scores. This is likely due to the local linear approximation that needs to be used by these methods. For ARAR, only up to 5 percent of all recourse are found (i.e., it only finds recourse with low cost to the decision boundary), and for those identified recourses the average invalidation rate is close to a random coin flip. In summary, PROBE finds recourses for 100% of the test instances in line with the promise of having an invalidation probability of at most $0.35$, while being substantially less costly than ROAR.

Appendix D Proofs

First, recall that the empirical Monte-Carlo estimator is given by:

which gives the bias-variance decomposition. We first compute the squared bias term:

where we have used that the $\bm{\varepsilon}$s are identically distributed. We now turn to the variance term for which we find the following expression:

Combining the expression for the squared bias and the upper bound on the variance yields the desired result. ∎

D.2 Proofs of Theorem 1, Propositions 1 - 4 and Corollary 1

where $\Phi$ is the CDF of the univariate standard normal distribution $\mathcal{N}(0,1)$, $f(\check{\mathbf{x}}_{E})$ denotes the logit score at $\check{\mathbf{x}}_{E}$ which is the recourse output by a recourse method $E$, and $h(\check{\mathbf{x}}_{E})\in\{0,1\}$.

Again, we are interested in the second term, which evaluates to:

Next, consider the first-order Taylor approximation: $f(\check{\mathbf{x}}_{E}+\bm{\varepsilon})\approx f(\check{\mathbf{x}}_{E})+\nabla f(\check{\mathbf{x}}_{E})^{\top}\bm{\varepsilon}$. Hence, we know $\nabla f(\check{\mathbf{x}}_{E})^{\top}\bm{\varepsilon}$ approximately follows $\mathcal{N}(\mathbf{0},\nabla f(\check{\mathbf{x}}_{E})\mathbf{\Sigma}\nabla f(\check{\mathbf{x}}_{E})^{\top})$. Now, the second term can be computed as follows:

where the last line follows due to symmetry of the standard normal distribution (i.e., $\Phi(-u)=1-\Phi(u)$). Putting the pieces together, we have:

For a linear classifier, let $r\in(0,1)$ and let $\check{\mathbf{x}}_{E}=\mathbf{x}+\bm{\delta}_{E}$ be the output produced by some recourse method $E$ such that $h(\check{\mathbf{x}}_{E})=1$. Then the cost required to achieve a fixed invalidation target $r$ is given by:

where $c=\frac{f(\mathbf{x})}{\sigma\cdot\lVert\nabla f(\mathbf{x})\rVert_{2}}$ is a constant, and $\omega>0$ is the cosine of the angle between the vectors $\nabla f(\mathbf{x})$ and $\bm{\delta}_{E}$.

Under a logistic classifier, the result immediately follows by setting the expression from Theorem 1 equal to $r$, using the identity $\nabla f(\mathbf{x})^{\top}\bm{\delta}_{E}=\omega\cdot\lVert\nabla f(\mathbf{x})\rVert_{2}\cdot\lVert\bm{\delta}_{E}\rVert_{2}$ where $\omega$ is the cosine of the angle between the vectors $\nabla f(\mathbf{x})$ and $\bm{\delta}_{E}$, and rearranging for $\lVert\bm{\delta}_{E}\rVert_{2}$. ∎

Under the same conditions as in Proposition 2, we have $\frac{\partial\lVert\bm{\delta}_{E}\rVert_{2}}{\partial(1-r)}=\frac{\sigma}{\omega}\frac{1}{\phi(\Phi^{-1}(1-r))}>0$, i.e., an infinitesimal increase in robustness (i.e.,$1-r$) increases the cost of recourse by $\frac{\sigma}{\omega}\frac{1}{\phi(\Phi^{-1}(1-r))}$.

We will compute the derivative of \lVert\bm{\delta}_{E}\rVert_{2}=\frac{\sigma}{\omega}\big{(}\Phi^{-1}(1-r)-c\big{)} with respect to $1-r$ and show that it is positive for all $r\in(0,1)$:

where $\phi$ is the probability density function (PDF) of the standard Gaussian distribution. Since the PDF must be positive, we have that $\phi(\Phi^{-1}(1-r))>0$, and we know that $\sigma,\omega>0$. Thus, the results follows. ∎

where $c=\frac{f(\mathbf{x})}{\sigma\cdot\lVert\nabla f(\mathbf{x})\rVert_{2}}$ is a constant, $\bm{\delta}_{E}=\check{\mathbf{x}}_{E}-\mathbf{x}$, and $\omega>0$ is the cosine of the angle between the vectors $\nabla f(\mathbf{x})$ and $\bm{\delta}_{E}$.

We start by noting the following basic inequality:

Going forward, we will refer to these inequalities as basic inequalities. Moreover, note that $\Phi$ is a monotonic function. Thus, we have $\Phi(a)\leq\Phi(a^{\prime})$ for $a\leq a^{\prime}$. Note that $f(\check{\mathbf{x}}_{E})\approx f(\mathbf{x})+\nabla f(\mathbf{x})^{\top}\bm{\delta}_{E}$. Thus we obtain the following approximation:

Next, we will find upper bounds for the term on the right: Before we will do that, we will express the above expression more conveniently to highlight the impact of the counterfactual action $\bm{\delta}_{E}$ more explicitly. To do that, note that $\nabla f(\mathbf{x})^{\top}\bm{\delta}_{E}=\omega\cdot\lVert\nabla f(\mathbf{x})\rVert_{2}\cdot\lVert\bm{\delta}_{E}\rVert_{2}$ where $\omega$ is the cosine of the angle between the vectors $\nabla f(\mathbf{x})$ and $\bm{\delta}_{E}$. Using $\mathbf{\Sigma}=\sigma^{2}\mathbf{I}$, we obtain:

where we defined a constant $c=\frac{f(\mathbf{x})}{\sigma\lVert\nabla f(\check{\mathbf{x}}_{E})\rVert_{2}}$ using quantities that we will keep fixed in our analysis, namely $\mathbf{x},\nabla f(\mathbf{x})$ and $\sigma$. Also note that $\mathbf{x}$ is the factual input, and thus its logit score satisfies: $f(\mathbf{x})<0$. Since $\bm{\delta}_{E}$ is a valid perturbation, we must have that $\omega>0$ for the perturbation to change the class prediction.

Note that the following lower bound holds by the basic inequality stated above:

As a consequence we obtain the following upper bound on the IR:

For the logistic regression classifier, consider the recourse output by Wachter et al. (2018): $\check{\mathbf{x}}_{\text{Wachter}}(s)=\mathbf{x}+\frac{s-f(\mathbf{x})}{\lVert\nabla f(\mathbf{x})\rVert_{2}^{2}}\nabla f(\mathbf{x})$. Then the recourse invalidation rate has the following closed-form:

Since we are in the linear case, we have: $\nabla f(\check{\mathbf{x}}_{E})=\nabla f(\mathbf{x})$. Also, note that $f(\check{\mathbf{x}}_{E})=f(\mathbf{x})+\nabla f(\mathbf{x})^{\top}\bm{\delta}_{E}$. Using $\mathbf{\Sigma}=\sigma^{2}\mathbf{I}$, we obtain the following exact expression:

Plugging equation 43 into equation 42 we obtain:

Under the conditions of Proposition 1, choosing $s_{r}=\sigma\lVert\nabla f(\mathbf{x})\rVert_{2}\Phi^{-1}(1-r)$ guarantees a recourse invalidation rate of $r$, i.e., $\Delta(\check{\mathbf{x}}_{\text{Wachter}}(s_{r});\sigma^{2}\mathbf{I})=r$.

The result directly follows from plugging in $s_{r}=\sigma\lVert\nabla f(\mathbf{x})\rVert_{2}\Phi^{-1}(1-r)$ into the optimal recourse from $\bm{\delta}_{\text{Wachter}}$ from equation 43 and subsequently evaluating the recourse invalidation rate from equation 5. ∎

D.3 Proof of Theorem 2

Using our Definition of robustness, we have