LOW-COST ALGORITHMIC RECOURSE FOR USERS WITH UNCERTAIN COST FUNCTIONS
Year: 2021

Abstract:
The problem of identifying algorithmic recourse for people affected by machine learning model decisions has received much attention recently. Existing approaches for recourse generation obtain solutions using properties like diversity, proximity, sparsity, and validity. Yet, these objectives are only heuristics for what we truly care about, which is whether a user is satisfied with the recourses offered to them. Some recent works try to model user-incurred cost, which is more directly linked to user satisfaction. But they assume a single global cost function that is shared across all users. This is an unrealistic assumption when users have dissimilar preferences about their willingness to act upon a feature and different costs associated with changing that feature. In this work, we formalize the notion of user-specific cost functions and introduce a new method for identifying actionable recourses for users. By default, we assume that users’ cost functions are hidden from the recourse method, though our framework allows users to partially or completely specify their preferences or cost function. We propose an objective function, Expected Minimum Cost (EMC), based on two key ideas: (1) when presenting a set of options to a user, it is vital that there is at least one lowcost solution the user could adopt; (2) when we do not know the user’s true cost function, we can approximately optimize for user satisfaction by first sampling plausible cost functions, then finding a set that achieves a good cost for the user in expectation. We optimize EMC with a novel discrete optimization algorithm, Cost-Optimized Local Search (COLS), which is guaranteed to improve the recourse set quality over iterations. Experimental evaluation on popular real-world datasets with simulated user costs demonstrates that our method satisfies up to 25.89 percentage points more users compared to strong baseline methods. Using standard fairness metrics, we also show that our method can provide more fair solutions across demographic groups than comparable methods, and we verify that our method is robust to misspecification of the cost function distribution.

heading: 1 INTRODUCTION
text: Over the past few years ML models have been increasingly deployed to make critical decisions related to loan approval (Siddiqi, 2012), insurance (Scism, 2019), allocation of public resources (Chouldechova et al., 2018; Shroff, 2017) and hiring decisions (Ajunwa et al., 2016). Decisions from these models have real-life consequences for the individuals (users) involved. As a result, there is a growing emphasis on explaining these models’ decisions (Ribeiro et al., 2018; Lundberg & Lee, 2017; Poulin et al., 2006) and providing recourse for unfavorable decisions (Voigt & dem Bussche, 2018; Karimi et al., 2020a). A recourse is an actionable plan that is given to someone allowing them to change the decision of a deployed model to a desired alternative (Wachter et al., 2017). Recourses can be highly valuable for users in situations where model decisions determine important life outcomes. Or, in cases where no feasible recourse is possible, users may wish to dispute the use of a model in the first place, and we might take this as evidence that greater reforms to the decision-making system are needed (Venkatasubramanian & Alfano, 2020).
Recourses are desired to be actionable, feasible, and non-discriminatory. Actionable means that only features which can be changed by the user are requested to be changed. These changes should also be possible under the data distribution. For example, Education level cannot be decreased from a Masters to Bachelors degree but can be increased from Masters to PhD. It is also not actionable to change your Race (Mothilal et al., 2020). A recourse is feasible if it is reasonably easy for the
user to adopt, i.e. it is actionable and has a low cost for the user. Non-Discriminatory means that the recourse method should be equitable across population subgroups. There are now many fairness metrics that can be used to measure this (Hinnefeld et al., 2018), e.g. the ratio between the average cost of recourse for two subgroups in a population.
While we want recourses to be feasible for all users, it is difficult to directly optimize for a user’s incurred cost unless we have access to their ground-truth cost function. In the absence of detailed cost function data, prior work has used other heuristic objectives for feasibility. For instance, Mothilal et al. (2020) and Wachter et al. (2017) assume that if the vector distance between the user’s current state and the recourse is small, then recourse will be low cost. These works encourage this property via a proximity objective. Meanwhile, sparsity quantifies the number of features that require modification to implement a recourse (Mothilal et al., 2020). When providing multiple recourse options, diversity in proposed recourses is used to counter uncertainty around the user cost function (Mothilal et al., 2020; Cheng et al., 2021). The assumption is that if users are provided with diverse options then they are more likely to find at least one feasible solution. Later in section 5.2, we show that diversity as an objective correlates poorly with user cost, suggesting it would be strongly preferable to optimize for user cost directly.
A few approaches to recourse do directly optimize for the cost of recourse, but they assume there is a single cost function shared by all users (Ustun et al., 2019; Rawal & Lakkaraju, 2020; Karimi et al., 2020c;d; Cui et al., 2015). We believe it is crucial to have user-specific cost functions, as a global cost function might poorly represent different users in a diverse population.
In this work, we propose a method for identifying a user-specific recourse set that contain at least one good solution for the user. We directly optimize for user cost by quantifying the actionability and feasibility of proposed recourses. In the absence of data about user cost functions, we treat them as hidden from the recourse method and assume they follow an underlying cost distribution. However, we provide users with an option to specify their preferred editable features or the complete cost function detailing the costs of transitions between features values. We model this cost distribution via a highly flexible hierarchical cost sampling procedure which makes minimal assumptions about user preferences (Algorithm 1). Based on this distribution, we propose an objective function, Expected Minimum Cost (EMC), which allows us to approximately optimize for user satisfaction by first sampling plausible cost functions, then finding a set that achieves a good cost in expectation. The EMC objective encourages the solution set to consist of counterfactuals that are each a good counterfactual under some particular cluster of cost functions from the distribution. Hence, no matter what the user’s ground-truth cost function is, we will have some counterfactual that is well suited to the user’s cost function (shown in Figure 1). Next, we propose a simple discrete optimization method, Cost-Optimized Local Search (COLS), in order to optimize for Expected Minimum Cost. COLS guarantees a monotonic reduction in the Expected Minimum Cost of the counterfactual set, which we show leads to large empirical reductions in user-incurred cost.
To evaluate the effectiveness of our proposed techniques, we run experiments on two popular realworld datasets: Adult-Income (Dua & Graff, 2017) and COMPAS (Larson et al., 2016). We compare our method with multiple strong baselines methods like Diverse Counterfactual Explanations (DICE) (Mothilal et al., 2020), Feasible and Actionable Counterfactual Explanations (FACE) (Poyi-
adzi et al., 2020), and Actionable Recourse (AR) (Ustun et al., 2019). We evaluate these methods on existing metrics from the literature like diversity, proximity, sparsity, and validity (Section 5.1) along with two cost-based metrics. In particular, we measure the fraction of satisfied users, based on whether their cost of recourse is below a certain threshold k. We also report coverage, which is the fraction of users with at least one actionable recourse (Rawal & Lakkaraju, 2020). Using simulated user cost functions, we show that our method satisfies 25.89% and 17.93% percentage points more users than strong baseline methods while covering 22.35% and 17.13% more users, on the Adult-Income and COMPAS dataset respectively. We perform important ablations to show whether performance can be attributed to the COLS optimization method or the EMC objective. Additionally, we evaluate the robustness of our method to various distribution shifts that can occur between the user’s hidden cost distribution and the hierarchical cost sampling distribution. We find that our method is robust to these distribution shifts and generalizes well to user cost function from these shifted distributions. Lastly, we perform a fairness analysis of all the methods across demographic subgroups based on Gender and Race. Standard fairness metrics demonstrate that, in most comparisons, our method is more fair relative to the strongest baseline methods. Our primary contributions in this paper are listed below.
1. We propose to evaluate user-incurred cost and fraction of satisfied users by means of hidden user-specific cost functions, rather than a known global cost function. 2. We propose a new objective function, Expected Minimum Cost (EMC), which allows us to approximately optimize for user satisfaction when user cost functions are not known. 3. We propose a discrete optimization method, Cost-Optimized Local Search (COLS), which achieves up to 25.89% percentage points higher user satisfaction relative to the next-best baseline. COLS guarantees a monotonic reduction in EMC, which we find provides a 19% point improvement over a simple local search. 4. We show that in most settings, COLS provides more fair solutions across demographics subgroup than comparable recourse methods, while offering recourse to a substantially higher fraction of users.

heading: 2 RELATED WORK
text: A wide variety of methods have been proposed for generating recourses. For a comprehensive survey of existing recourse methods, we refer readers to Karimi et al. (2020b). Here, we distinguish our approach based on our recourse objectives, optimizer, and evaluation. We primarily discuss recourse methods, though there is useful complementary work on problems such as providing recourse when there is distribution shift in the data (Upadhyay et al., 2021; Slack et al., 2021) and training models which guarantee recourse to affected individuals with high probability (Ross et al., 2021).
Objectives: The most prominent family of objectives for recourse includes distance-based objectives (Wachter et al., 2017; Karimi et al., 2020a; Dhurandhar et al., 2018; Mothilal et al., 2020; Rasouli & Yu, 2021). These methods seek recourses that are close to the original data point. In DICE, Mothilal et al. (2020) provide users with a set of counterfactuals while trading off between proximity, a distance-based objective, and diversity. Diversity-based methods assume that providing diverse options will increase the chance a user is satisfied by one of the options. A second category of methods uses other heuristics based on the data distribution (Aguilar-Palacios et al., 2020; Gomez et al., 2020) to come up with counterfactuals. FACE constructs a graph from the given data and then tries to find a high-density path between points in order to generate counterfactuals (Poyiadzi et al., 2020). Lastly, the works closest to ours are the cost-based objectives, which capture feasibility in terms of the cost of recourse: (1) Cui et al. (2015) define a cost function based on the minimum and maximum values a factor can take in their additive tree model. (2) Karimi et al. (2020c;d) take a causal intervention perspective on the task and define cost in terms of the normalized distance between the user state and the counterfactual. (3) Ustun et al. (2019) define cost in terms of the number of changed features and frame recourse generation as an Integer Linear Program. (4) Rawal & Lakkaraju (2020) infer a cost function from simulated rankings of features for actionability, then optimize recourses for this cost function. Importantly, all of these works assume there is a known global cost function that is shared by all users. In our work, we drop this assumption, and instead we optimize for cost over a distribution of plausible user-specific cost functions.
Optimization: Early work on recourse methods uses gradient-based optimization to search for counterfactuals close to a user’s data point (Wachter et al., 2017). Several methods since then also use gradient-based optimization (Mothilal et al., 2020; Chen et al., 2020). Some recent approaches
use tree-based techniques (Rawal & Lakkaraju, 2020; Aguilar-Palacios et al., 2020; von Kügelgen et al., 2020; Hashemi & Fathi, 2020; Kanamori et al., 2020), kernel-based methods (Dandl et al., 2020; Gomez et al., 2020; Ramon et al., 2020), while others employ some heuristic (Poyiadzi et al., 2020; Aguilar-Palacios et al., 2020) to generate counterfactuals. A few works use latent space perturbation with autoencoders to generate recourses (Pawelczyk et al., 2020; Joshi et al., 2019), while Karimi et al. (2020a) and Ustun et al. (2019) utilize SAT and ILP solvers, respectively. Here, we introduce a discrete optimization method specialized for our Expected Minimum Cost objective.
Evaluation: Besides ensuring that recourses are classified as the favorable class by a model (validity), the most prominent approaches to evaluate recourses rely on Distance-based metrics. In DICE, Mothilal et al. (2020) evaluate recourses according to their proximity, sparsity, and diversity. Meanwhile, several works directly consider the cost of the recourses, using a known global cost function as a metric, meaning that all users share a cost function, which is available to the recourse generation method (Cui et al., 2015; Karimi et al., 2020c;d). In a slight departure from this setting, Rawal & Lakkaraju (2020) estimate a cost function from simulated pairwise feature comparisons, but this single estimate is used for both recourse generation and evaluation. In contrast, we evaluate a recourse method by simulating user-specific cost functions which can very greatly across users, and these cost functions are not known in advance to recourse generation methods. We will also measure recourse coverage as defined by Rawal & Lakkaraju (2020), which measures the fraction of users that were provided with a recourse by the method.

heading: 3 PROBLEM STATEMENT
text: Notation. We assume that we have a dataset with features F = {f1, f2, ...fk}. Each feature can either be continuous Fcon ⊂ F or categorical Fcat ⊂ F . Each continuous feature f coni takes values in the range [rmini , r max i ], which we discretize to integer values. For a continuous feature fi, we define the range Q(fi) = {k ∈ Z : k ∈ [rmini , rmaxi ]} and for a categorical feature fi, we define it as Q(fi) = {qfi1 , q fi 2 , ..., q fi di }, where qfi(.) are the states that feature fi can take. Features can either be mutable (Fm), conditionally mutable (Fcm), or immutable (F⊘), according to the real-world causal processes that generate the data. Mutable features can transition from between any pair of states in Q(fi); conditionally mutable features can transition between pairs of states only when permitted by certain conditions; and immutable features cannot be changed under any circumstances. For example, Race is an immutable feature (Mothilal et al., 2020), Age and Education are conditionally mutable (cannot be decreased under any circumstances), and number of work hours is mutable (can both increase and decrease). Lastly, while continuous features inherently define an ordering in its values, categorical features can either be ordered or unordered based on its semantic meaning. For instance, Age is an ordered feature that is conditionally mutable (can only increase).
Cost Function. In this work, we assume that each user has a hidden preference regarding the ease of changing a particular feature, where different users can have different preferences. Such differential preferences can be expressed via user-specific costs of transitioning between feature states. We define a cost function for each user C : R|F| → R|F| as a set of feature-specific functions which provide the user-incurred cost when transitioning between feature states. Formally, a cost function is parametrized as a set of transition matrices, C = {C(f) ∈ R|Q(f)|×|Q(f)| | ∀f ∈ F}, where each element of the transition matrix C(f)ij ∈ [0, 1]∪{∞} is the cost of transition from state i→ j for the feature f . Here, 0 means the transition has no associated cost incurred, and 1 means the transition is maximally difficult to make. Infeasible transitions have a cost of∞ (associated with immutable features). For the remainder of the paper, we interchangeably write C(f) as matrix or a function where C(f)(m,n) = C(f)m,n. User Definition. A user u is defined as a tuple u = (su, C∗u), where su is the state vector of length |F| containing the user’s features values and C∗u is their unknown ground-truth cost function (see Appendix Table 5 for qualitative example). This ground-truth cost function, C∗u = {C ∗(f) u | ∀f ∈ F}, provides the cost of transitioning between different feature states. Following past work (Rawal & Lakkaraju, 2020), we note that it may be difficult for users to precisely quantify their own cost functions in practice, but we do assume that each user has some hidden cost function that specifies which recourses they would prefer. Different from past work (Rawal & Lakkaraju, 2020; Ustun et al., 2019), we suppose that each user in a population has their own cost function, rather than assuming there is a global cost function (single shared and fixed cost function across users).
Transition Costs. Given two state vectors si, sj and any cost function C, transition cost is the summation of transition costs for individual features, defined as Cost(si, sj ; C) =∑
f∈F C(f)(s (f) i , s (f) j ), where s (f) is the value of feature f in the state vector. Now, given a recourse set S, we suppose that the cost a user will incur is the minimum transition cost across possible recourses, since a rational user will select the least costly option. So, given a user u with state vector su and a counterfactual set S, the cost of transition under a cost function C is defined as
MinCost(su,S; C) = min sj∈S Cost(su, sj ; C). (1)
Problem Definition. For a given user u our goal is to find a recourse set Su such that, Su = argmin
S MinCost(su,S; C∗u) s.t. ∃ si ∈ S s.t. f(si) = +1 (2)
where f is the black-box ML model and +1 is the desired outcome class. We want to offer users at least one counterfactual that is a good solution under their hidden cost function C∗u. Since we are uncertain about which cost function is the user’s true cost function, we minimize the expected cost for each user using a distribution over plausible cost functions (Section 4.1).
Measuring Recourse Quality. While we could measure average population cost as our metric for recourse method quality, it is also helpful to ask: what proportion of users are satisfied with the recourses they are given? We say that a user is satisfied by a recourse set if the best option in that set achieves a sufficiently low cost. Formally, given a set of users U and a set of sets of generated counterfactuals {Su}u∈U from a recourse method, the fraction of user’s satisfied at a particular cost threshold k, FS@k, can be defined as:
FS@k(U , {Su}u∈U ) = ∑ u∈U 1{MinCost(su,Su;C∗u)<k} |U| (3)
We note that optimizing Equation 2 is equivalent to finding the set of counterfactuals that maximizes the probability that a user is satisfied by some counterfactual in the set.
Another important quantity is the Coverage (Cov) which measures the fraction of users to which the recourse algorithm can provide any actionable recourse.
Cov(U , {Su}u∈U ) = ∑ u∈U 1{MinCost(su,Su;C∗u)<∞} |U| (4)

heading: 4 PROPOSED METHOD: EMC AND COLS
text: In this section, we define our proposed objective function, Expected Minimum Cost (EMC), cost sampling distribution, and Cost-Optimized Local Search (COLS) optimization method.

heading: 4.1 APPROXIMATELY OPTIMIZING FOR USER COST UNDER UNCERTAIN COST FUNCTIONS
text: In most use cases, the cost functions associated with each user C∗u ∼ D∗ are unknown to us and follow the population’s true cost function distribution D∗ which is also unknown. Hence, we cannot exactly minimize the user cost in Equation 1 with respect to C∗u. Yet we can approximately optimize for the true user cost C∗u by means of a plausible cost function sampling distribution Dtrain if it can model diversity in user preferences and cost function effectively. Given samples from this distribution, we can minimize the Expected Minimum Cost (EMC) of a transition for a user. Formally, for any given user u = (su, C∗u), we want to optimize for ECi∼Dtrain [MinCost(su,S; Ci)] (5) In practice, we employ Monte Carlo Estimation (Robert & Casella, 2010) to approximate this expectation by sampling M cost functions {Ci}Mi=1 from Dtrain, which we term our EMC objective:
ExpMinCost(su,S; {Ci}Mi=1) = ∑M
i=1 MinCost(su,S; Ci) M =
∑M i=1 minsj∈S Cost(su, sj ; Ci)
M (6)
Remark: Note that there is an important interaction between the expectation and the MinCost terms in this objective. EMC encourages the solution set to consist of recourses that are each a good option under some particular cluster of cost functions from the distribution. That is, the min term allows for different recourses to cater to different regions of the cost function distribution. As a result, no matter what the user’s ground truth cost function is, we are likely to have found at least one counterfactual that is well suited to that cost function (see Figure 1).

heading: 4.2 HIERARCHICAL COST SAMPLING PROCEDURE
text: To optimize for EMC, we need a plausible distribution Dtrain which is capable of generating cost functions which model a diverse set of user preferences. We propose, three hierarchical cost sampling distribution, Dperc, Dlin, Dmix which are highly flexible and makes minimal assumptions about the user preference (see Algorithm 1). The samples from Dperc and Dlin model the transition cost with percentile shift and linear cost respectively. Whereas, the samples from Dmix distribution models a linear combination of percentile shift cost (Ustun et al., 2019) and linear cost, where the mixture weights of this combination are user-specific, capturing their disposition towards these two types of costs. Percentile shift cost for ordered features is proportional to the change in a feature’s percentile value with the change from an old feature value to a new one (see Algorithm 4). The Linear cost for ordered features is proportional to the number of intermediate states in Q(f) which a user will have to go through while transitioning from their current state to the final state (see Algorithm 5). For a detailed description of the sampling procedure, please refer to Appendix A.2.1 and Algorithm 1.
We emphasize a few core properties of Dmix distribution: (1) The distribution is very flexible. It is able to capture all possible feature subsets which different users might consider editable as well as possible mixing weights for combining linear and percentile costs. Critically, the difficulty of editing each feature can range from “trivial” to “maximally difficult” (relative to other features), meaning almost all plausible user cost functions should be represented in the distribution. (2) The cost distribution mean follows the monotonicity property, i.e. if the user has to make more drastic changes to the feature, then the associated cost will be higher. (3) The user has an option to adapt this distribution to their needs by providing either the editable features or the feature scores. Together, these properties allow us to represent a large space of plausible user cost functions, which helps us ensure our recourses can satisfy a diverse user preferences.

heading: 4.3 SEARCH METHODS FOR FINDING LOW COST COUNTERFACTUALS.
text: COLS: To optimize for Expected Minimum Cost (Equation 6), we propose two simple, efficient, and optimized discrete search algorithms (Ebrahimi et al., 2018; Baptista & Poloczek, 2018), namely Cost-Optimized Local Search (COLS) and Parallel Cost-Optimized Local Search (P-COLS) (refer to Algorithm 2). COLS maintains a best set which will be the final recourse provided to the user. At each iteration, a candidate set is generated by locally perturbing each element of the best set with a Hamming distance of two, then it is evaluated against the EMC objective. Instead of making a direct comparison between the best-set-so-far and the candidate set, at this point we evaluate whether any counterfactuals from the candidate set would improve the best set if we swapped out individual counterfactuals. Specifically, if the benefit of replacing si ∈ St with sj ∈ Sbest is positive then we make the replacement. The ability to assess the benefit of each candidate counterfactual is critical because it allows us to constantly update the best set instead of waiting for an entire candidate set with lower EMC. For objectives like diversity, evaluating the benefit of individual replacement becomes prohibitively expensive (see Appendix A.1). We note that, for COLS, we can guarantee that the EMC of the best set will monotonically decrease over time, which we formally state below:
Theorem 4.1 (Monotonicity of Cost-Optimized Local Search Algorithm). Given the best set, Sbestt−1 ∈ RN×d, the candidate set at iteration t, St ∈ RN×d, the matrix C
b ∈ RN×M and C ∈ RN×M containing the incurred cost of each counterfactual in Sbestt−1 and St with respect to all the M sampled cost functions {Ci}Mi=1, there always exist a Sbestt constructed from Sbestt−1 and St such that
ExpMinCost(su,Sbestt ; {Ci}Mi=1) ≤ ExpMinCost(su,Sbestt−1 ; {Ci}Mi=1)
For a formal proof of the theorem, please refer to Appendix A.2.2.
P-COLS: The method P-COLS is a variant of COLS which starts multiple parallel runs of COLS with different initial sets. The run with the least objective value is selected as recourse for the user.
Random Search: We use Random Search as a baseline, which selects random counterfactuals from the whole space to obtain the next candidate set at each iteration.

heading: 5 EXPERIMENTS

heading: 5.1 EXPERIMENTAL SETUP
text: Dataset: We conduct our experiments on the Adult-Income (Dua & Graff, 2017) and COMPAS (Larson et al., 2016) datasets. The Adult-Income dataset is based on the 1994 Census database, and it contains 12 features. The model’s task is to classify whether the income of an individual is over $50, 000. COMPAS was collected by ProPublica, and it contains information about the criminal history of defendants from Broward County for analyzing recidivism in the United States. The processed dataset contains 7 features. A model needs to decide bail based on predicting which of the bail applicants will recidivate in the next two years. We preprocess both datasets based on a previous analysis where all categorical features are mapped onto two classes (Pawelczyk et al., 2021). 1 Our black-box model is a neural network model with 2-layers. Please refer to Appendix B.1 and Table 4 for more details about experiments, data statistics, and the black-box model.
Baselines: We compare our methods COLS and P-COLS with Random Search, DICE (Mothilal et al., 2020), FACE-Knn and FACE-Epsilon (Poyiadzi et al., 2020), and Actionable Recourse (Ustun et al., 2019). Importantly, we control for compute by restricting the number of forward passes to the black-box model, which are needed to decide if a counterfactual produces the desired class. Additionally, for most big models this is the rate limiting step. For a description of the objective function and other details of these methods refer to Appendix A.1.1, A.2.3.
Metrics: To compare with past work, we evaluate methods on Distance based metrics like diversity, proximity, sparsity and validity metrics. Proximity is defined as prox(x,Y) = 1− 1N ∑|Y| i=1 dist(x,Yi), where Yi is a counterfactual. The Sparsity metric
(Mothilal et al., 2020) is defined as spar(x,Y) = 1− 1Nd ∑|Y| i=1 ∑|x| j=1 1{xj ̸=Yij}. The Diversity
metric (Mothilal et al., 2020) is defined as div(Y) = − 1Z ∑|Y|−1 i=1 ∑|Y| j=i+1 dist(Yi,Yj), where Z is the number of terms in the summation. Validity is defined as val(Y ) = |{unique si∈S : f(si)=+1}||S| . Additionally, we show results on cost based metrics like Fraction Satisfied (FS@k), Population Coverage (Cov) (see Section 3) and the average incurred cost by the users (PAC) covered by the method.
Simulated Cost Functions: Given true user cost functions C∗u ∼ D∗ are not known in practice, hence for the experiments we simulated them from a distribution Dtest for method evaluation. There are two phases in the experiments, the recourse generation phase where we optimize for EMC and the cost functions required are sampled Dtrain. In the evaluation phase, we use the simulated user cost function which is hidden during training to compute cost-based metrics for all the re-
1 The code for the Actionable Recourse method (Ustun et al., 2019) requires binary categorical variables.
course methods (see Appendix B.1.2). For all experiments apart from distribution shift experiments, Dtrain = Dtest = Dmix.

heading: 5.2 RESEARCH QUESTIONS

heading: Q1. Which Method Satisfies the Most Users?
text: Design: In this experiment, we compare different recourse methods (Section 5.1 and Appendix A.2.3) with respect to distance and cost-based metrics (Section 5.1). We set a fixed budget of 5000 and a set size |S| = 10 for all the methods. We perform five runs for each method with different random seeds and report the mean results in Table 1. We omit the variances from the table as 97% of the values have variance less than 0.01%, with the maximum value being 3.3% for validity of Random Search on COMPAS dataset. Results: We can see from these results that DICE, which optimizes for a combination of distancebased metrics, performs much worse on the direct metrics like Population Coverage (Cov) and FS@k. On the other hand, COLS and P-COLS, which optimize for EMC, achieve 22.64% and 25.89% point higher user satisfaction while covering 19.28% and 22.42% point more users on the Adult-Income dataset, with similar improvements on COMPAS. We also observe that COLS and P-COLS demonstrate high sparsity and proximity in the solutions. Regarding recourse diversity, we find that COLS and P-COLS do not exhibit high diversity. The second-best method on cost metrics, Actionable Recourse, also promotes proximate and sparse solutions rather than diverse options, while Random Search achieves high diversity but low FS@1. These results provide evidence that diversity is not a necessary condition for high user satisfaction. Hence, it is preferable to provide users with recourse based on expected cost as opposed to providing them diverse options which might not align well with their preferences. Lastly, we note that FACE does the best on proximity as it finds the shortest high-density path in the generated graph.
Q2. Is the Performance Improved by the Optimization Method or by the Objective?
Design: We perform an ablation study to attribute the improvements from our method to either the COLS optimization method or the EMC objective function. To do so, we run a basic local search (LS) to optimize for diversity, proximity, and sparsity along with validity. We use a basic nonoptimized local search, because there is no simple and efficient way to guarantee a reduction in the diversity objective by swapping out single elements from the solution set (see Appendix A.1). For a fair comparison across these objectives, we also optimize for EMC using basic local search. Results: We provide the results for this experiment in Table 2. These results suggest that optimizing for metrics besides EMC is sub-optimal. For diversity, proximity, and sparsity objectives, the FS@1 score and population coverage is very low, while they perform well on the respective metrics. The low FS@1 score for distance metrics is expected as they ignore user-specific preference while optimizing for their objectives, and therefore the generated recourses might be infeasible under the user’s cost function. We find that EMC with LS outperforms all Distance Metrics with LS on FS@1, which suggests that the EMC objective function leads to higher user satisfaction. Meanwhile, the 19% point difference in the performance of EMC with LS and COLS can be attributed to our Cost Optimization described in Section 4.3 and Theorem 4.1, which allows COLS to more efficiently search the solution space. In this experiment, we observe that COLS again does poorly on diversity, whereas it promotes proximity and sparsity in the recourse. Based on results from Q1 and Q2, we conclude that having high diversity is neither a necessary or sufficient condition to satisfy individual users with inherent feature preferences. Additionally, we observe that sparsity and proximity are positively correlated with higher user satisfaction and inherently emerge from the idea of satisfying more users.

heading: Q3. Are Recourses Fair Across Subgroups?
text: Design: Here, we want to understand whether recourse methods provide equitable solutions across subgroups based on demographic features like Gender and Race. In this experiment, we assume Gender is non-actionable for the sake of analysis. Existing works on algorithmic fairness present a number of metrics for characterizing the disparate impact of black-box classification models across population subgroups (Feldman et al., 2015). We adapt the Disparate Impact metric for the recourse outcomes we study, which we denote by Disparate (DIR). Given a metricM, DIR is a ratio between metric scores across two subgroups. DIR-M =M(S=1)/M(S=0). We use either Cov or FS@1 as M. Under the DIR metric, a maximally fair method achieves a score of 1. We run experiments on the Adult-Income dataset, with a budget of 5000 and |S| = 10. Results: We present the subgroup-based results in Table 3. We observe that COLS and P-COLS typically have a lower difference in FS@1 and Cov across subgroups (Gender and Race) as compared to other baselines while satisfying and covering significantly more users. In particular, we find that our method achieves a score very close to 1 on DIR-FS and DIR-Cov for the gender-based subgroup, and scores relatively close to 1 on the race-based subgroup. We attribute the fairness of our method to (1) the fact that our recourses are individualized, rather than making use of the data distribution, and (2) the use of a diverse set of cost functions when generating recourses. We see condition (2) as important since there are other individualized methods that do not rely on the data distribution, such as Actionable Recourse, which can generate less fair solutions than COLS. Overall, we conclude that our method is typically more fair than baselines on both Gender and Race-based subgroups while providing recourse to a larger fraction of people in both subgroups.

heading: 5.3 ADDITIONAL RESULTS
text: We provide experiments for several additional research questions in the Appendix B.2, which we summarize here: (1) We find that our method is robust to misspecification of the cost function distribution (Figure 2, 3); (2) We can make use of a larger compute budget to scale up the performance (Figure 4); The recourse sets provide high quality solutions to users using as few as 3 counterfactuals (Figure 5); and (4) we can achieve high user satisfaction with as few as 20 Monte Carlo samples, rather than 1000 (Figure 6). We also show some qualitative examples of recourses provided by our method in Table 5.

heading: 6 CONCLUSION
text: In this paper, we propose a cost-based recourse generation method which can optimize for an unknown user-specific cost function. With simulated cost functions, we show that our method achieves much higher rates of user satisfaction than comparable baselines. This is particularly promising since detailed user cost function data is not readily available for most applications. We attribute the method’s efficacy to our Expected Minimum Cost (EMC) objective term, and we also show that our discrete optimization algorithm, Cost-Optimized Local Search (COLS), produces large improvements over baseline search methods. Lastly, we observe that our recourses are often more fair than baseline recourse methods, while offering recourse to a much larger fraction of the user population.

heading: 7 ETHICS STATEMENT
text: We hope that our recourse method is adopted by institutions seeking to provide reasonable paths to users for achieving more favorable outcomes under the decisions of black-box machine learning models or other inscrutable models. We see this as a “robust good,” similar to past commentators Venkatasubramanian & Alfano (2020). Below, we comment on a few other ethical aspects of the algorithmic recourse problem.
First, we suggest that fairness is an important value which recourse methods should always be evaluated along, but we note that evaluations will depend heavily on the model, training algorithm, and training data. For instance, a sufficiently biased model might not even allow for suitable recourses for certain subgroups. As a result, any recourse method will fail to identify an equitable set of solutions for the population. That said, recourse methods can still be designed to be more or less fair. This much is evident from our varying results on fairness metrics using a number of recourse methods. What will be valuable in future work is to design experiments that separate the effects on fairness of the model, training algorithm, training data, and recourse algorithm. Until then, we risk blaming the recourse algorithm for the bias of a model, or vice versa.
Additionally, there are possible dual-use risks from developing stronger recourse methods. For instance, malicious actors may use recourse methods when developing models in order to exclude certain groups from having available recourse, which is essentially a reversal of the objective of training models for which recourse is guaranteed (Ross et al., 2021). We view this use case as generally unlikely, but pernicious outcomes are possible. We also note that these kinds of outcomes may be difficult to detect, and actors may make bad-faith arguments about the fairness of their deployed models based on other notions of fairness (like whether or not a model has access to protected demographic features) that distract from an underlying problem in the fairness of recourses.

heading: 8 REPRODUCIBILITY STATEMENT
text: To encourage reproducibility, we provide our source code, including all the data pre-processing, model training, recourse generation, and evaluation metric scripts in the supplementary material. The details about the datasets and the pre-processing is provided in Appendix B.1.1. We also provide clear and concise Algorithms 1, 4, 5 for our cost sampling procedures and our optimization method COLS in Algorithm 2. Additionally, we also provide formal proof of the Theorem 4.1 stated in paper in Appendix A.2.2 along with the constructive procedure for the proof is provided in Algorithm 2.

heading: A APPENDIX - OBJECTIVE AND OPTIMIZATION

heading: A.1 PROPOSED METHOD

heading: A.1.1 OTHER OBJECTIVES
text: To obtain feasible a counterfactual set, past works have used various objective terms. We list objectives below from methods we compare with.
1. DICE (Mothilal et al., 2020) optimizes for a combination of Distance Metrics like diversity and proximity. They model diversity via Determinantal Point Processes (Kulesza & Taskar, 2012) adopted for solving subset selection problems with diversity constraints. They use determinant of the kernel matrix given by the counterfactuals as their diversity objective as defined below.
dpp diversity(S) = det(K), whereKij = 1
1 + dist(si, sj)
Here, dist(si, sj) is the normalized distance metric as defined in Wachter et al. (2017) between two state vectors. Proximity is defined in terms of the distance between the original state vector and the counterfacutals, prox(x,Y) = 1− 1N ∑|Y| i=1 dist(x,Yi), where Yi is a counterfactual.
2. Actionable Recourse (Ustun et al., 2019) work under the assumption that all features have equal preference scores for all the users. They define cost function based on the log-percentile shift is given by,
cost(s+ a; s) = ∑ j∈JA log 1−Qj(sj + aj) 1−Qj(sj)
where Qj(.) is the cumulative distribution function of sj in the target population, JA is the set of actionable features and aj is the action performed on the feature j.
Algorithm 1: Procedure for sampling Cost Functions. Input: A state vector s, Optional: Preferred featured Fp, feature preference scores p, cost distribution mixing weight α Output: Sample preference scores p and the cost functions C.
1 function sampleCostAndPreference(s, α = NoneFp = {}, p = None) 2 if Fp is empty then 3 Fp ∼ RandomSubset(Fm) ▷ Sample preferred features. 4 5 if p is None then 6 concentration = [1 if f ∈ Fp else 0 for f in F ] 7 p ∼ Dirichlet(concentration) ▷ Sample feature preference scores. 8
9 if α is None then 10 α ∼ Uniform(0, 1) ▷ Sample cost mixing weight. 11 12 C = {} 13 forall fi ∈ F do 14 µ(fi,Lin), σ(fi,Lin) ←− getLinearCostMean(s, p(fi), fi,Fp) 15 µ(fi,Perc), σ(fi,Perc) ←− getPercentileCostMean(s, p(fi), fi,Fp) 16 µ(fi) ←− α ∗ µ(fi,Lin) + (1− α) ∗ µ(fi,Perc) 17 σ(fi) ←− α ∗ σ(fi,Lin) + (1− α) ∗ σ(fi,Perc) 18 C(fi) ←− Beta(µ(fi), σ(fi)) ▷ Beta with mean and variance µ(fi), σ(fi) 19 C ← C ∪ C(fi)
20 return p, Cp
Algorithm 2: Cost-Optimized Local Search Algorithm Input: A state vector s, {Ci}Mi=1 ∼ Du cost distributions Output: Sbest, a set of generated counterfactuals of size N .
1 function LocalSearch(s, {Ci}Mi=1, hammingDistance = 2) 2 Initialize 3 Sbest ∈ RN×d ← pertubCFS(s, hammingDistance) ▷ Perturb s, N times. 4 Cb ← getCostMatrix(s,Sbest; {Ci}Mi=1) ▷ Incurred costs for Sbest. 5 while usedBudget < Budget do 6 S ∈ RN×d ← pertubCFS(Sbest, hammingDistance) 7 C ∈ RN×M ← getCostMatrix(s,S; {Ci}Mi=1) ▷ Incurred costs for the S. // Bij = Change in objective when Sbest[i]← S[j]. 8 B ∈ RN×N ← computeBenefits(Cb,C) ▷ Refer to Algorithm 3
// Greedily select which pairs to swap given B 9 replaceIndices← getReplaceIdx(B)
// Swap these pairs and update Cb. 10 forall originalIdx, replaceIdx ∈ replaceIndices do 11 Sbest[originalIdx] = S[replaceIdx] 12 Cb ← getCostMatrix(s,Sbest; {Ci}Mi=1) 13 return Sbest,Cb
Algorithm 3: Algorithm for Theorem 4.1 Input: Cb,C ∈ RN×M matrices containing the costs with respect to all cost samples.. Output: B ∈ RN×N , matrix containing the benefits of replacing pairs from Sbestt−1 × St
1 function computeBenefits(Cb,C) 2 Initialize 3 B ∈ RN×N ← 0
// Find the indices of the best and second best counterfactual in Sbest for each of the M cost function.
4 b1 ∈ RM = argmaxi C b ij 5 b2 ∈ RM = arg second maxiC b ij // Iterate over all pairs of counterfactuals. 6 forall p, q ∈ [N ]× [N ] do
// Iterate over cost functions for which pth counterfactual in Sbest has the minimum cost.
7 forall r ∈ {i ∈ [M ] | b1i = p} do 8 if Cbpr > Cqr then // This replacement reduces the cost of Sbest by Cbpr − Cqr. 9 Bpq+ = Cbpr − Cqr
10 else // Cbb2r,r = cost of second best counterfactual in S best for rth
cost function.
11 Bpq+ = Cbpr −min(Cqr,C b b2r,r )
12 return B

heading: A.2 OPTIMIZATION METHODS

heading: A.2.1 HIERARCHICAL COST SAMPLING PROCEDURE
text: To optimize for EMC, we need a plausible distribution which can model users’ cost functions. We propose a hierarchical cost sampling distribution which provides cost samples that are a linear combination of percentile shift cost (Ustun et al., 2019) and linear cost, where the weights of this combination are user-specific. Percentile shift cost for ordered features is proportional to the change in a feature’s percentile associated with the change from an old feature value to a new one. E.g., if a user is asked to increase the number of work hours from 40 to 70, then given the whole dataset, we can estimate the percentile of users working 40 and 70 hours a week. The cost incurred is then proportional to the difference in these percentiles. The Linear cost for ordered features is proportional to the number of intermediate states in Q(f) which a user will have to go through while transitioning from their current state to the final state. E.g., if a user is asked to change their education level from Highschool to Masters then there are two steps involved in the process. First, they need to get a Bachelors degree and then a Masters degree in which case, the user’s cost is proportional to 2 because of the two steps involved in the process. To sample a cost function C = {C(f) ∈ R|Q(f)|×|Q(f)| | ∀f ∈ F}, we independently sample C(f) for each feature (see Algorithm 1). We first randomly sample a subset of editable features for the user, and then we sample feature preference score pu from a Dirichlet distribution with a uniform prior over selected features. These will be used to scale costs, such that a higher value of p(f)u implies a lower transition cost for feature f . For both the percentile and linear cost, the cost C(f)ij of transitioning from feature state i → j, is sampled from a Beta distribution on the interval [0, 1]. The mean of this distribution depends on the types of cost (linear or percentile) and the feature type (ordered or unordered). Here, we first obtain one mean for linear cost (µ(f,lin)ij ) and one mean for percentile cost (µ(f,perc)ij ) and then combine them to form a single Beta mean. Each of the two means is proportional to the change in the feature (in either linear or percentile terms) when the feature is ordered. For unordered features, the mean is randomly sampled from
the unit interval (see Algorithms 5, 4). Then, the linear and percentile means are multiplied with (1−p(f)u ) to scale the transition cost according to the feature preference score. Next, the two means are combined to obtain a single mean, µ(f)ij = α ∗ µ (f,lin) ij + (1 − α) ∗ µ (f,perc) ij , where α ∈ [0, 1] represents whether a user thinks of cost in terms of linear or percentile shift (sampled randomly from unit interval). Note that the value µ(f)ij are monotonic, i.e. if the user has to make more drastic changes to the feature, then the associated cost will be higher. The variance for the Beta distribution, σ (f) ij , is set to constant value of 0.01. Finally, the cost C (f) ij is sampled from Beta(µ (f) ij , σ (f) ij ). We emphasize that this sampling procedure allows users to partially specify their cost functions, e.g. by denoting which features they prefer to edit (the Dirichlet mean) or the relative difficulty of editing one feature versus another (pu). If we set α = 0, then the resulting distribution is Dperc and with α = 1 we get the distribution Dlin.

heading: A.2.2 MERGING COUNTERFACTUAL SETS
text: When searching for a good solution set, it would be useful to have the option of improving on the best set we have obtained so far using individual counterfactuals in the next candidate set we see, rather than waiting for a new, higher-scoring set to come along. While optimizing for objectives like diversity, which operate over all pairs of elements in the set, it is computationally complex to evaluate the change in the objective function if one element of the set is replaced by a new one. To evaluate the change in objective in such cases, we need iterate over all pairs of element in the best and the candidate set and then evaluate the objective for the whole set again. The iteration over both the sets here is not the hard part but the computation that needs to be done within. For our objective, we can compute costs for individual recourses rather than sets, meaning we can do a trivial operation to compute the benefits of each pair replacement. But, if we wanted to do this with diversity then for each pair of replacement we need to compute additional S distances for each replacement because the distance of the new replace vector needs to be computed with respect to all the other vectors, for each iteration of the nested loop. This quickly makes it infeasible to improve the best set by replacing individual candidates with the best set elements. However, for metrics where it is easy to evaluate the effect of individual elements on the objective function, we can easily merge the best set and any other set St from time t to monotonically increase the objective function value. In our objective function, EMC, we can compute the goodness of individual counterfactuals with respect to all the Monte Carlo samples (Robert & Casella, 2010). Given a set of counterfactuals we can obtain a matrix of incurred cost C ∈ RN×M , which specifies the cost of each counterfactual for each of the Monte Carlo samples. We can use this to update the best set Sbest using elements from the perturbed set St at time t. This procedure is defined in algorithm 3. It iterates over all pairs of element in si ∈ Sbest and sj ∈ St and computes the change that will occur in the objective function by replacing si → sj . Note that we are not recomputing the costs here. Given Sbest, St, Cb and C, we can guarantee that we will update the best set Sbest in a way to improve the mean of the minimum costs incurred for all the Monte Carlo samples. This is shown in algorithm 3 and the monotonicity of the EMC objective under this case can be formally stated as,
Theorem (Monotonicity of Cost-Optimized Local Search Algorithm). Given the best set, Sbestt−1 ∈ RN×d, the candidate counterfactual at iteration t, St ∈ RN×d, the matrix Cb ∈ RN×M and C ∈ RN×M containing the incurred cost of each counterfactual in Sbestt−1 and St with respect to all the M sampled cost functions {Ci}Mi=1, there always exist a Sbestt constructed from Sbestt−1 and St such that
ExpMinCost(su,Sbestt ; {Ci}Mi=1) ≤ ExpMinCost(su,Sbestt−1 ; {Ci}Mi=1)
Proof. To prove this theorem, we construct a procedure that ensures that the ExpMinCost is monotonic. For this procedure, we prove that the monotonicity of EMC holds. Check algorithm 3 for a constructive procedure for this proof, which is more intuitive to understand.
We start off by noting that each element of Cbij is the cost of the ith counterfactual sbi in the best set Sbestt−1 with respect to the cost function Cj given by Cost(su, sbi ; Cj). Similarly Cij = Cost(su, si; Cj) where si is the ith candidate counterfactual. Note that, the EMC is the average of the MinCost with respect to all the sampled cost function Cj . What this means is that given a pair of counterfactual from Sbestt−1 × St and for each Cj , we can compute the change in the MinCost which we describe
later. These replacements can lead to an increase in the cost with respect to certain cost function but the overall reduction depend on the aggregate change over all the cost functions. Given this, for each replacement candidate pair in Sbestt−1 × St, we can compute the change in EMC by summing up the changes in the MinCost across all cost functions Cj ; this is called the cost-benefit for this replacement pair. The cost benefit can be negative for certain replacements as well if the candidate counterfactual increases the cost across all the cost functions. The pairs with the highest positive cost benefits are replaced to construct the set Sbestt , if no pair has a positive benefit then we keep set Sbestt−1 = Sbestt . Hence, this procedure monotonically reduces EMC. We now specify how the change in MinCost can be computed to complete the proof.
To compute the change in MinCost for a single cost function Ci, first we find the counterfactual in Sbestt−1 with the lowest and second lowest cost which we denote by sbl1 and s b l2
. These are the counterfactuals which can affect the MinCost with respect to a particular cost function Ci. This is true because when we replace the counterfactual sbl1 which has the lowest cost for Cj with a new candidate counterfactual si, there are two cases. Either, Cbl1j > Cij or C b l1j ≤ Cij . In case when the candidate si has lower cost for Cj than Cbl1j , i.e. C b l1j > Cij , then the replacement reduces the cost by Cbl1j − Cij . In case when the candidate cost for Cj , Cij , is higher than the lowest cost in the best set Cbl1j , i.e. C b l1j ≤ Cij , it means that this replacement will increase the cost for Ci by Cbl1j − min(Cij ,C b l2j). Here, C b l2j is the second lowest cost counterfactual for Ci. Note that the change in this case will be negative and also depend on the second best counterfactual because once the sbl1 is removed from the set, the best cost for Ci will either be for s b l2
or si, hence we take the minimum of those two and then take the difference as the increase in cost. Please refer to Algorithm 3 for a cognitively easier way to understand the proof.

heading: A.2.3 OTHER METHODS
text: In this section, we describe some of the optimization methods used by relevant baselines.
1. DICE (Mothilal et al., 2020) perform gradient-based optimization in this continuous space while optimizing for objective defined in Section A.1.1. Their final objective function is defined as
C(x) = argmin c1,...,ck
1
k k∑ i=1 loss(f(ci), y) + λ1 k k∑ i=1 dist(ci,x)− λ2 dpp diversity(c1, . . . , ck)
where ci is a counterfactual, k is the number of counterfactuals, f(.) is the black box ML model, yloss(.) is the metric which minimizes the distance between models prediction and the desired outcome y. dpp diversity(.) is the diversity metric as defined in Section A.1.1 and λ1 and λ2 are hyperparameters to balance the components in the objective. Please refer to Mothilal et al. (2020) for more details.
2. FACE (Poyiadzi et al., 2020) operates under the idea that to obtain actionable counterfactuals they need to be connected to the user state via paths that are probable under the original data distribution aka high-density path. They construct two different types of graphs based on nearest neighbors (Face-knn) and the ϵ-graph (Face-Eps). They define geodesic distance which trades-off between the path length and the density along this path. Lastly, they use the Shortest Path First Algorithm (Dijkstra’s algorithm) to get the final counterfactuals. Please refer to (Poyiadzi et al., 2020) for more details.
3. Actionable Recourse (Ustun et al., 2019) tries to find an action set a for a user such that taking the action changes the black-box models decision to the desired outcome class, denoted by +1. They try to minimize the cost incurred by the user while restricting the set of actions within an action set A(x). The set A(x) imposes constraints related to feasibility and actionability with respect to features. They optimize the log-percentile shift objective (see Section A.1.1). Their final optimization equation is
min cost(a;x) s.t. f(x+ a) = +1, a ∈ A(x)
which is cast as an Integer Linear Program (Mittleman, 2018) to provide users with recourses. Their publicly available implementation is limited to a binary case for categorical features,2 hence we demonstrate results on the binarized version of the dataset.

heading: B APPENDIX - EXPERIMENTS AND DETAILS

heading: B.1 EXPERIMENTAL SETUP

heading: B.1.1 DATASETS AND BLACK-BOX MODEL
text: In our experiments, we have two versions of the dataset, one with binary categorical features, whereas the other with non-binary categorical features. In the main paper, we show results on the binarized version (Table 1) as an important baseline, Actionable Recourse (Ustun et al., 2019), operates with binary categorical features.3 The data statistics for all the datasets can be found in Table 4. In our experiments, for all the datasets, the features gender and race are considered to be immutable (Mothilal et al., 2020), since we perform subgroup analysis with these variables that would be rendered meaningless if users could switch subgroups. Other features can either be mutable or conditionally mutable depending on semantics. These constraints can be incorporated into the methods by providing a schema of feature mutability criterion. Our black-box model is a multi-layer perceptron model with 2 hidden layers trained on the trained set and validated on the dev set. The accuracy numbers are shown in Table 4. The test set which is used in the counterfactual generation experiments only contains users which are classified to the undesired class by the trained black-box model. Note that our frameworks can operate with any type of model, the only requirement is the ability to query the model for outcome given a user’s state vector.

heading: B.1.2 RECOURSE GENERATION AND EVALUATION PIPELINE
text: To approximate the expectation in equation 5, our algorithm samples a set of random cost functions {Ci}Mi=1 ∼ Dtrain, which are used at the generation time to optimize for the user’s hidden cost function. In the generation phase, we use Equation 6 as our objective. Note that, this objective promotes that the generated counterfactual set contains at least one good counterfactual for each of the cost samples, hence this set satisfies a large variety of samples from Dtrain. This is achieved via minimizing the mean of the minimum cost incurred for each of the Monte Carlo samples (Robert & Casella, 2010). Equivalently, the objective is minimized by a set of counterfactuals S where for each cost function there exists an element in S which incurs the least possible cost. In practice the size of set S is restricted, hence we may not achieve the absolute minimum cost but the objective tries to ensure that the counterfactuals which belong to the set have a low cost at least with respect to one Monte Carlo cost sample. The generation phase outputs a set of counterfactuals S which is to be provided to the users as recourse options. Given this set Su, in the evaluation phase, we use the users simulated cost functions which are hidden in the generation phase, to compute the cost incurred by the user as defined in Equation 1 and calculate the metrics defined in the Section 5.1.
2Please refer to the this example where they mention about these restricted abilities https://github.com/ustunb/actionable-recourse/blob/master/examples/ex 01 quickstart.ipynb
3The binary datasets can be downloaded from https://github.com/carla-recourse/cf-data, whereas the nonbinary data can be found on https://github.com/interpretml/DiCE.
Remark 1. In the limiting case, as |S| → M and Budget → ∞, RHS of equation 6; min S
MinCost(su,S; Ci) → optimum cost, ∀ i ∈ [M ], if feasible solutions are possible for all cost functions samples {Ci}Mi=1.
What this remark implies is that, as the set size increases to the number of Monte Carlo samples M , then the methods can trivially generate one counterfactual for each cost function sample which minimizes its cost. In that limiting case, we get custom counterfactual for each cost function. Hence, in the limiting case we can find optimum solution. In the experiment B.2, we show that even with very less number of counterfactual we are able to achieve good performance implying that in practice we do not need large set size.

heading: B.2 ADDITIONAL RESEARCH QUESTIONS

heading: Q4. Are Solutions Robust to Misspecified Cost Distributions?
text: Design: In our hierarchical cost sampling procedure, we make minimal assumptions about the user’s feature preferences if they are not provided by the user. When finding recourses, we select a random subset of features along with their preference score for each user. However, there are situations where user preferences may be relatively homogeneous for certain features where people usually share common preferences. For example, to increase their income, many users might prefer to edit their occupation type or education level rather than their work hours or marital status. Given the possibility of this kind of distribution shift in feature preferences, we want to measure how robust our method is to distribution shift between our hierarchical sampling distribution and the actual cost distribution followed by users.
In this experiment, we test a case of this kind of distribution shift over cost functions. For users in the Adult-Income data, we generate recourse sets using Monte Carlo samples from our standard distributionDc (Algorithm 1). To obtain hidden user cost functions that differ from this distribution, we first generate 500 different feature subsets indicating which features are editable, where each subset corresponds to a binary vector concentration representing a user having specific preferences for some features over others (see Sec. 4.2 and Alg. 1). Since having different editable features induces a different distribution over cost functions, we obtain a measure of distribution shift for each of the 500 concentration vectors by taking an l2 distance between the vector and its nearest neighbor in the space of concentration vectors used to generate the recourses. We use the nearest neighbor because the most outlying concentration vectors are least likely to be satisfied by the recourse set. In other words, the likelihood that a user is satisfied depends on the minimum distance between their concentration vector and its nearest neighbor in the cost samples used at recourse
generation time. Therefore, when the minimum distance increases, there is a greater distribution shift between the user’s cost functions and those obtained from Dc. Finally, we measure how many users are satisfied for a given degree of distribution shift.
Results: In Figure 2, we show a binned plot of FS@1 against our measure of distribution shift. We observe that as the distance between the distributions increases, the fraction of users satisfied decreases slightly and then plateaus. Even at the maximum distance we obtain, performance has only dropped about 3 points. This implies that our method is robust to distribution shift in the cost distribution in terms of which features people prefer to edit. We attribute this result to the fact that our method assumes random feature preferences and provides multiple recourse options, each of which can cater to different kinds of preferences. As a result, we achieve a good covering of the cost function space (see experiments w.r.t. varying recourse set size and number of sampled cost functions in the Appendix B.2).

heading: Q5. Robustness to Misspecification in Linear vs Percentile based costs?
text: Design: Our sampling procedure samples cost by taking an α-weighted combination of two different types of costs, linear and percentile costs. These two cost have different underlying assumptions about the how users view the cost of transition between the states. We want to test the robustness of our method in terms of misspecification in users disposition to these types of cost. We perform a robustness analysis where the users cost function has a different α mixing weight as compared to the Monte Carlo samples we use to optimize for EMC. This creates a distribution shift in the user cost function distribution and the Monte Carlo sampling distribution. We vary the user and Monte Carlo distributions α-weights within the range of 0 to 1 in steps of 0.2. At the extremes values of α = 0, 1, the shifts are very drastic as the underlying distribution changes completely. In the case when monte carlo α weight is 0 and user α weight is 1 then Dtrain = Dperc and Dtest = Dlin, simlarly for the other case we getDtrain = Dlin andDtest = Dperc. Please note that the distributionDlin andDperc have completely different underlying principles and are two completely different distributions.
Results: In Figure 3, we show a heatmap plot to which demonstrates the robustness of our method. The color of the block corresponding to Monte Carlo alpha, αmc = x and the users alpha, αuser = y represents the fraction of users that were satisfied when αmc = x and αuser = y. This means that if the user thought of costs only in terms of Linear step involved but the recourse method used samples with only percentile based cost, still the recourse set can satisfy almost the same number of users. In Figure 3, the corners correspond to these extreme cases described above, the user satisfaction for the top left corner (Dtrain = Dperc and Dtest = Dlin) is similar to the bottom left corner (Dtrain = Dlin and Dtest = Dlin). Similarly things happen for the opposite case which is denoted by the top-right (Dtrain = Dperc and Dtest = Dperc) and bottom-right (Dtrain = Dlin and Dtest = Dperc) corners. This means that even when a complete distribution shift occurs the performance user satisfaction remains similar. This can be attributed to the hierarchical step for user preference sampling in the procedure because the preferences values can be arbitrary and they scale the raw percentile and linear cost hence the distribution designed this way to model extremely diverse types of transition costs.
This means that our methods is robust to misspecification in the users’ notions of thinking about cost in terms of (relative) percentile shifts or (absolute) linear shifts. The almost consistent color of the grid means that there is very slight variation in the Fraction of Satisfied users when the model is tested on out of distribution user cost types.

heading: Q6. Does Method Performance Scale with Available Compute?
text: Design: In this experiment on the Adult-Income dataset, we measure the change in performance of all the models as the number of access to the black-box model (budget) increases. Ideally, a good recourse method should be able to exploit these extra queries and use it to satisfy more users. We vary the allocated budget in the set {500, 1000, 2000, 3000, 5000, 10000} and report the FS@1. We run the experiment on a random subset of 100 users for 5 independent runs and then report the average performance with standard deviation-based error bars in Figure 4.
Results: In Figure 4, we can see that as the allocated budget increases the performance of the COLS and P-COLS increases and then saturates. This suggests that our method can exploit the additional black-box access to improve the performance. Other methods like AR and Face-Knn also
show performance improvement but our method COLS and P-COLS consistently upper-bound their performance. Our method satisfies approximately 70% of the user with a small budget of 500 and quickly starts to saturate around a budget of 1000. This suggests that our methods are suitable even under tight budget constraints as they can achieve good performance rapidly. For example, in a real-world scenario where the recourse method is deployed and has to cater to a large population, in such cases there might be budget constraints imposed onto the method where achieving good quality solution quickly is required. Lastly, for DICE and Random search the performance on the FS@1 increase by a very small margin and then stays constant as these methods are trying to optimize for different objectives which don’t align well with user satisfaction as demonstrated in Section 5.2.

heading: Q7. Does providing more options to users help?
text: Design: In this experiment, we measure the effect of having flexibility to provide the user with more options, i.e. a bigger set S. The question here is that can the methods effectively exploit this advantage and provide lower cost solution sets to the user such that the overall user satisfaction is improved. In this experiment on the Adult-Income dataset, we take a random subset of 100 users and fix the budget to 5000, Monte Carlo cost sample is set to 1000 and then vary the size of the set S in the set {1, 2, 3, 5, 10, 20, 30}. We restrict the size of the set to a maximum of 30 as beyond a point it becomes hard for users to evaluate all the recourse options and decide which one to act upon. We run 5 independent runs for all the data points and plot the mean performance along with standard deviation error bars. In Figure 5, we plot the fraction of users satisfied @1 as the size of set S is increased. Result: We observed that COLS and P-COLS monotonically increase the FS@1 metric as |S| increases from 1 to 30. This is consistent with the intuition behind our methods (See Figure 1, section 4.1, B.1.2 for more details). It is a fundamental property of our objective that as |S| increases towards M which is 1000 in this case, then the quality of the solution set should increase and reach the best possible value that can be provided under the user’s cost function. We note empirically that smaller set size |S| between 3 to 10 is enough in most practical cases to reach close to maximum performance. Additionally, even with |S| ∈ {1, 2, 3} our methods significantly outperform all the other methods in terms of the number of users satisfied. This property is useful in real-world scenarios where the deployed recourse method can provide as little as 3 options while still satisfying a large fraction of users. Additionally, we also see improvement in the case of AR and Face-Knn methods as |S| increases. Note that Randoms Search’s performance doesn’t change as we increase the set size because the method doesn’t take local steps from the best set and samples random points from a very large space, hence it is much harder to end up with low-cost counterfactuals.

heading: Q8. Does increase the number of Monte Carlo samples help with user satisfaction?
text: Design: In this experiment, we want to demonstrate the effect of increasing the number of Monte Carlo samples on the performance of our COLS method. We take a random subset of 100 users, a budget of 5000, |S| = 10. We vary the number of Monte Carlo samples (M) in the set {1, 5, 10, 20, 30, 100, 200, 300, 500, 1000} and compute the user satisfaction. We ran 5 different runs with different Monte Carlo samples and show the average FS@1 along with the standard deviation in the Figure 6. Results: We observe that as the number of Monte Carlo samples increases, the performance of the method on the FS@1 metric monotonically increases. This supports the intuition underlying our method (see Figure 1). That is, given a user with a cost function Cu as we get more and more samples from the cost distribution Du the probability of having a cost sample similar to Cu increases and hence the fraction of satisfied users increase. It is impor-
tant to note that empirically the method’s performance approaches maximum user satisfaction with as low as 20 Monte Carlo samples. In real-world scenarios, where the deployed model is catering to a large population this can lead to small recourse generation time, hence making it more practical.

heading: Q9. Qualitative examples of the recourses generated for some of the users.
text: In Table 5, we show a few examples of users along with their state vector, their editable features, their preference scores along with the recourses provided to them and their cost.

heading: Q10. Comparison of methods on Non Binary Dataset?
text: In Table 6, we show the results on the non-binary version of the dataset. We observe similar performance on and trends in these results as well. COLS and P-COLS performs the best in terms of user satisfaction.
Algorithm 4: Sampling procedure for Percentile Cost Mean 1 function getPercentileCostMean(s, p(fi), fi,Fp) // si value of feature fi in s. 2 if fi /∈ Fp then 3 µ(fi)(si, .) =∞ 4 µ(fi)(si, si) = 0 5 else 6 if fi is ordered then 7 if fi can only increase then
8 µ(fi)(si, x) =  |getPercentile(x)− getPercentile(si)| ∀x > si 0 ∀x = si ∞ ∀x < si 9 else if fi can only decrease then
10 µ(fi)(si, x) =  |getPercentile(si)− getPercentile(x)| ∀x < si 0 ∀x = si ∞ ∀x > si 11 else if fi can both increase or decrease then
12 µ(fi)(si, x) =  |getPercentile(x)− getPercentile(si)| ∀x > si 0 ∀x = si |getPercentile(si)− getPercentile(x)| ∀x < si 13 else if fi is unordered then 14 µ(fi)(si, .) = Uniform(0, 1) 15 µ(fi)(si, .)← µ(fi)(si, .) ∗ (1− p(fi)) 16 σ(fi)(si, .)← 0.01 17 return µ(fi), σ(fi)
Algorithm 5: Sampling procedure for Linear Cost Means 1 function getLinearCostMean(s, p(fi), fi,Fp) 2 if fi /∈ Fp then 3 µ(fi)(si, .) =∞ 4 µ(fi)(si, si) = 0 5 else 6 if fi is ordered then 7 if fi can only increase then
8 µ(fi)(si, x) =  |{y | y>si∧y≤x}| |{y | y>si}| ∀x > si 0 ∀x = si ∞ ∀x < si 9 else if fi can only decrease then
10 µ(fi)(si, x) =  |{y | y<si∧y≥x}| |{y | y<si}| ∀x < si 0 ∀x = si ∞ ∀x > si 11 else if fi can both increase or decrease then
12 µ(fi)(si, x) =  |{y | y>si∧y≤x}| |{y | y>si}| ∀x > si 0 ∀x = si |{y | y<si∧y≥x}| |{y | y<si}| ∀x < si 13 else if fi is unordered then 14 µ(fi)(si, .) = Uniform(0, 1) 15 µ(fi)(si, .)← µ(fi)(si, .) ∗ (1− p(fi)) 16 σ(fi)(si, .)← 0.01 17 return µ(fi), σ(fi)

Review summaries:
In this paper, the problem of algorithmic recourse is studied where the goal is to find best recourse (counterfactual set) that is optimized for user cost. The author proposed new user-incurred cost evaluation method, Expected Minimum Cost (EMC), which approximate user satisfaction without assuming a fixed global user cost function, and instead consider user cost functions as hidden and user-specific. Specifically, the authors define cost function for each user as a set of feature-specific functions of user-incurred cost when transitioning between feature states, and define MinCost as the minimum transition cost across possible recourses. To cover diverse user cost functions, they propose to model user cost distribution with a hierarchical sampling procedure and estimated expected minimum cost by drawing samples from it. Next, they formulate a discrete optimization problem using EMC as objective, and propose a search algorithm (COLS) for best recourse generation. They introduce three new metrics for user satisfaction (all related to MinCost): FS@k, Coverage and PAC. Finally, they test with two real-world datasets and show that COLS achieves significant outperformance against baselines (that optimize for distance-based metrics) on the newly proposed metrics and show that their method is doing better in fairness as well. 

This work introduces a new method for identifying actionable recourses for users with user-specific cost functions. Users’ cost functions are hidden from the recourse method. The paper proposed a discrete optimization algorithm COLS to solve the objective EMC. It further used a popular real-world dataset to illustrate the performance.