Low-Cost Algorithmic Recourse for Users With Uncertain Cost Functions
Authors: Prateek Yadav
Peter Hase
Mohit Bansal
Venue: ICLR 2022 Submitted (2022)
Keywords: Explainability
Interpretability
Counterfactuals
Algorithmic Recourse
Black-box Models
Machine Learning
Accountability
Consumer Protection
Adverse Action Notices

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 low-cost 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. 

Under review as a conference paper at ICLR 2022
Low-COST ALGORITHMIC RECOURSE FOR USERS WITH UNCERTAIN COST FUNCTIONS
Anonymous authors Paper under double-blind review
ABSTRACT
The problem of identifying algorithmic recourse for people affected by machine learning model decisions has received much attention recently. Existing ap- proaches 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 user is satisfied with the recourses offered to them. Some recent works try to model user-incurred cost, which is more di- rectly linked 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 costs associated with changing that feature. In this work, we formalize the no- tion user-specific cost functions and introduce a new method for identifying actionable recourses for users. By default, assume that users' cost functions are hidden from the recourse method, though our framework allows users to par- tially completely specify their preferences objective function, Expected Minimum Cost (EMC), based on two key ideas: (1) when presenting set of options to user, it is vital that there is at least one low- cost solution the user could adopt: (2) when we do not know the user's 's true cost function, we can approximately optimize for user satisfaction by first sampling plausible cost functions, then finding a set that achieves good cost for the user expectation. We optimize EMC with novel discrete optimization algorithm, Cost- Dast-Optimized Local Search (COLS), which is guaranteed to improve the re- course set quality over iterations. Experimental evaluation on popular real-world datasets with simulated user costs demonstrates that our method satisfies up 25.89 percentage points more users compared to strong baseline methods. Using standard fairness metrics, also show that our method can provide more fair so- lutions across demographic groups than comparable methods, and we verify that method is robust misspecification of the cost function distribution.
act upon feature and different
cost function. We propose
INTRODUCTION
Over the past few years ML models have been increasingly deployed to make critical decisions related loan approval (Siddiqi, 2012), insurance (Scism, 2019), allocation of public resources (Chouldechova et al., 2018; 8; Shroff, 2017) and hiring decisions (Ajunwa et al., 2016). Decisions from these models have real-life consequences for the individuals (users) involved. As result, there is growing emphasis on explaining these models' decisions (Ribeiro et al., 2018; Lundberg & Lee, 2017; Poulin 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 deployed model to a desired alternative (Wachter 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 possible, users may wish to dispute the use of model in the first place, and might take this evidence that greater reforms to the prrision-making system are needed (Venkatasubramaniaa & Alfano, 2020).
Recourses are desired 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 change your Race (Mothilal et al., 2020). A recourse is feasible if it is reasonably easy for the

---

Under review as a conference paper at ICLR 2022
user to adopt, i.e. it is actionable and has low cost for the user. Non-Discrininatory means that the recourse method should be equitable across population subgroups. There are now many fairesss metries 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 want recourses be feasible for all users, is difficult to directly optimize for a user's incurred cost unless we have access 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 objec- tive. Meanwhile, sparsity quantifies the num- ber of features that require modification to im- plement recourse (Mothilal 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 least one fea- sible solution. Later in section 5.2, we show that diversity as an objective correlates poorly with user cost, suggesting it would be strongly prefer- able to optimize for user cost directly.
C₂
0
00
0
8
8
0
8
000
81 :
: 82
83
0
User Cost Function
8
Cost Function Samples
Method diagram showing the intuition behind the Expected Minimum Cost Objective. The squares denote cost function samples, which are the same color when they are similar. We aim to find solution set of generated counterfac- tuals where each counterfactual does well under a particular region of cost function space (here, { 82, sa)). The shaded regions each represent a set of cost functions which single s; caters to. In this case, we do not have enough counterfactuals to "cover" every region of the cost function space, so a single counterfactual (s2) must cater to two different regions. Here the user's hidden ground- truth cost function, Cu, is served well by 81.
Figure I:
A few approaches to recourse do directly opti- mize for the cost of recourse, but they assume there is single cost function shared by all users (Ustun et al., 2019; Rawal & Lakkaraju, 2020; Karimi al., 2020c;d; Cui al., 2015). We be- lieve it is crucial to have user-specific cost func- tions, as global cost function might poorly rep- resent different users in a diverse population.
In this work, we propose a method for identifying a user-specific recourse set that contain 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 distribu- tion via a highly flexible hicrarchical cost sampling procedure which makes minimal assumptions about user preferences (Algorithm 1). Based 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 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 mat- ter what the user's ground-truth -ruth 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- Dost-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 real- world datasets: Adult- (Dua & Graff, 2017) and COMPAS (Larson et al., 2016). We com- pare our method with multiple strong baselines methods like Diverse Counterfactual Explanations (DICE) (Mothilal et al., 2020), Feasible and Actionable Counterfactual Explanations (FACE) (Poyi-
2

---

Under review as a conference paper at ICLR 2022
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 simu- lated 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-Incoms and COMPAS dataset respectively. We perform important ablations to show whether performance can be attributed the COLS optimization method or the EMC objective. Addition- ally, 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 metries demonstrate that, in most compar- isons, 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-ineurred 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-Optinen Sestmipi Local Search (COLS), which achieves up 25.89% percentage points higher user satisfaction relative the next-best baseline. COLS guarantees a monotonic reduction in EMC, which we find provides a 19% point improvement over 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.
2 RELATED WORK
A wide variety of methods have been proposed for generating recourses. For a comprehensive survey of existing recourse methods, we refer readers 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 objec- tives (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- 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 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 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 al. (2015) define cost function based on the minimum and maximum values 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 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.
ggulcir-Palacios al., 2020; Gomez
Optimization: Early work 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-basee based optimization (Mothilal et al., 2020; Chen et al., 2020). Some recent approaches
3

---

Under review as a conference paper at ICLR 2022
use tree-based techniques (Rawal & Lakkaraju, 2020; Aguilar-Palacion et al., 2020; von Kü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 al., 2020; Aguilar-Palacion et al., 2020) to generate counterfactuals. A few works use latent space per- turbation with autoencoders generate recourses (Pawelezyk 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 model (va- lidity), the most prominent approaches to evaluate recourses rely on Distance-bast based metries. 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 metric, meaning that all users share 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 cost function from simulated pairwise feature comparisons, but this single estimate is used for both recourse generation and evaluation. In contrast, we evaluate 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.
3 PROBLEM STATEMENT
Notation. We assume that we have a dataset with features F f2...e........ Each feature can either be continuous From C F or categorical Fout C F. Each continuous feature fron takes values in the range [rmin rymaa), which we discretize to integer values. For a continuous feature fi, we define the range Q(A)= (k E Z. k E [rmin, rymae]} and for a categorical feature fú, we define as Q(f+) = (q i. ..... Ld. fc). where u.) are the states that feature fi can take. Features can either be mutable (F""), conditionally mutable (JFm)), 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 QUA; 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 IFl + RR Fl as set of feature-specifie functions which provide the user-incurred cost when transitioning between feature states. Formally, a cost function parametrized as set of transition matrices, C {ClF) E (l0491x10(9) VVf E F}. where each element of the transition matrix CI E [0, [oo} is the cost of transition from state i - j for the feature f. Here, 0 means the transition has no associated cost incurred, and means the transition is maximally difficult make. Infeasible transitions have cost of co (associated with immutable features). For the remainder of the paper, we interchangeably write c()) matrix function where (L,) n) Cm..a
User Definition. A user u is defined as a tuple u = (s.,, Ci), where s, is the state vector of length [F] containing the user's features values and C₁ is their unknown ground-truth cost function (see Appendix Table 5 for qualitative example). This ground-truth cost function, C = (ct()) |Vf E 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 global cost function (single shared and fixed cost function across users).
4

---

Under review as a conference paper at ICLR 2022
Transition Costs. Given two state vectors 8,. 8, and any cost function C, transition cost is the summation of transition costs for individual features, defined as Cost( sy; Cinss ()) .8 )) where g(f) is the value of feature f in the state vector. Now, given a re- course set S, suppose that the cost 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 counterfactual set S, the cost of transition under cost function C is defined as MinCost($s. S:C) = min Cost( su. 8y;
syeS
Problem Definition. For given user u our goal is to find a recourse set S,, such that, S. arg min MinCoot((aa::))) C.)) s.t. 3& S f(xx) = +1
8
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 good solution under their hidden cost function C. Since we are uncertain about which cost function is the user's true cost function, we minimize the expected cost for each user using 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 xatisfied by a recourse set if the best option in that set achieves sufficiently low cost. Formally, given set of users 2/ and set of sets of generated counterfactuals {Sw] wel from recourse method, the fraction of user's satisfied at particular cost threshold k, FS@k, k, can be defined as:
FS (S.)
[24
EEM
We note that optimizing Equation 2 is equivalent to finding the set of counterfactuals that maximizes the probability that 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.
Cou(U1, (Su
- WEU
(MinCost( S.,C),
(4)
M
4
PROPOSED METHOD: EMC AND COLS
In this section, we define our proposed objective function, Expected Minimum Cost (EMC), cost sampling distribution, and Cost-Optimized Local Search (COLS) optimization method.
4.1 APPROXIMATELY OPTIMIZING FOR USER COST UNDER UNCERTAIN COST FUNCTIONS
In most use cases, the cost functions associated with each user C; ~ DD' are unknown to us and follow the population's '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. Yet we can approximately optimize for the true user cost C by means of a plausible cost function sampling distribution Dirain it can model diversity in preferences and cost function effectively. Given samples from this distribu- tion, we can minimize the Expected Minimum Cost (EMC) of a transition for a user. Formally, for any given user (8, Ct), want optimize for
Ee.-Deraia MinCost(s_,, S;C.)]
(5)
In practice, we employ Monte Carlo Estimation (Robert & Casella, 2010) to approximate this ex- pectation by sampling M cost functions { from Derains which we term our EMC objective:
M.
M MinCost(s., S;C.) ΣM min Cost(s.,,y;C..) AGES
S:
(6)
M
M
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 least one counterfactual that is well suited to that cost function (see Figure 1).
Remark:
5

---

Under review as a conference paper at ICLR 2022
4.2 HIERARCHICAL COST SAMPLING PROCEDURE
To optimize for EMC, we need a plausible distribution Derain which is capable of generating cost functions which model a diverse set of user preferences. We propose, three hierarchical cost sam- pling distribution, D Perros Diin. Dmii which are highly flexible and makes minimal assumptions about the user preference (see Algorithm 1). The samples from D Derre and Diin model the transition cost with percentile shift and linear cost respectively. Whereas, the samples from Dmi distribution models 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 new one (see Algorithm 4). The Linear cost for ordered features is proportional to the number of intermediate states in QiJ) which a user will have to go through while transitioning from their current state to the final state (see Algo- rithm 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 Miix 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 represent a large space of plausible user cost functions, which helps us ensure our recourses can satisfy a diverse user preferences.
4.3 SEARCH METHODS FOR FINDING LOW COST COUNTERFACTUALS.
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- Cost-Optimized Local Search (COLS) and Parallel Cost-Optimize to Algorithm 2). COLS maintains a best set which will be the final recourse provided to the user. At each iteration, candidate set is generated by locally perturbing each element of the best set with Hamming distance of two, then it is evaluated against the EMC objective. Instead of making a direct comparison between the best-set-so-fes and the candidate set, at this point 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 8; E St with 8j Shest 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 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:
COLS:
Local Search (P-COLS) (refer
Theorem 4.1 (Monotonicity of Cost-Optimized Local Search Algorithm). Given the best set, Sheat E TRNN Nxd, the candidate set at iteration 1, S, E Nxd, the matrix C² N and C E N containing the incurred cost of each counterfactual in Steet and S, with respect to all the M sampled cost functions {C, M there always exist Shest constructed from Sheet and S, such that
ExpMinCost(s.., (8., Steat, (C:) ExpMinCos((s., S/ (
For formal proof of the theorem, please refer 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.

---

Under review as a conference paper at ICLR 2022
Data
Method
Metries
Cost Metrics
Distance Metries
FS@1
PAC(L)
Cov
Div
Prox
Spars
Val
DICE
2.47
1.37
8.32
3.90
65.80
47.20
97.90
Face-Eps
15.23
0.76
22.60
4.75
92.22
74.98
100
Face-Kun
25.30
0.74
35.00
8.62
89.07
71.85
100
Adult-Income
Act. Recourse
49.93
0.55
56.85
18.38
74.68
73.57
78.67
Random
6.27
1.40
31.83
48.30
55.83
39.85
95.55
COLS
72.57
0.38
76.07
25.77
80.22
76.48
97.15
P-COLS
75.82
0.40
79.20
25.57
81.67
78.00
94.78
DICE
0.40
0.54
0.40
11.30
65.00
32.00
98.90
Face-Eps
12.20
0.29
12.20
2.50
94.20
60.60
100
Face-Knn
12.20
0.29
12.20
2.60
94.10
60.60
100
COMPAS
Act. Recourse
65.80
0.40
66.60
11.87
80.53
74.07
44.23
Random
29.95
0.77
39.20
42.22
55.90
31,25
71.88
COLS
82.23
0.24
82.23
29.32
77.82
70.05
95.48
P-COLS
83.73
0.24
83,73
29.38
78.48
71.30
92.78
Table 1: Table comparing different recourse methods across various cost and distance metrics (Sec- tion 5.1). The numbers reported are averaged across different runs. For all the metrics higher is better except for PAC where lower is better. Refer to section 5.2 for more details.
5
EXPERIMENTS
5.1 EXPERIMENTAL SETUP
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 over $50, 000. COMPAS was collected by ProPublica, and 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). Our black-box model is neural network model with 2-layers. Please refer Appendix B.1 and Table 4 for more details about experiments, data statistics, and the black-box model.
Baselines: We compare methods COLS and P-COLS with Random Search, DICE (Mothilal et al., 2020), FACE-Knn and FACE-Eppilon (Poyiadzi et al., 2020), and Actionable Recourse (Ustun 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 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.
To compare with past work, we evaluate methods on Distance based met- rics like diversity, proximity, sparsity and validity metrics. Proximity is defined as pro Y) / E.V dist(æ Y,), where Y; is counterfactual. The Sparsity metric (Mothilal et al., 2020) is defined as spar(æ, Y) metric (Mothilal et al., 2020) is defined as dio(Y) = - Σ Σ is the number of terms in the summation. Validity is defined as val(Y) Additionally, we show results cost based metrics like Fraction Satisfied (FS@k), Population Cov- erage (Cov) (see Section 3) and the average incurred cost by the users (PAC) covered by the method.
Metrics:
Na EM Σ 1 (aaxY.)) The Diversity
Σ)=4+ dist(Y, V2), where Z [unique s;ES f(+;)++1)
[S]
Simulated Cost Functions: Given true cost functions C₁ D* are not known in practice, hence for the experiments we simulated them from a distribution Drest 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 Drrain. In the evaluation phase, we use the simulated user cost function which hidden during training to compute cost-based metrics for all the re-
The code for the Actionable Recourse method (Ustun al., 2019) requires binary categorical variables.

---

Under review as a conference paper at ICLR 2022
Optim. Method
Objective
Cost Metries
Distance Metries
FS@ 1
PAC(J)
Cov
Diversity
Proximity
Sparsity
LS
Sparsity
10.1
1.304
29.0
42.7
66.2
55.8
I.S
Proximity
9.7
1.275
27.0
42.1
67.5
55.0
LS
Diversity
0.0
2.393
7.6
53.3
50.8
35.6
LS COLS
EMC EMC
49.8
0.597
59.1
37.8
73.3
67.5
68.8
0.391
72.6
27.1
77.5
73.5
Table 2: Ablation results with Search algorithms trained on different objectives (Section 5.2).
course methods (see Appendix B.1.2). For all experiments apart from distribution shift experiments,
Dtrain Drest D miz-
5.2 RESEARCH QUESTIONS
Q1. Which Method Satisfies the Most Users?
Design: In this experiment, we compare different recourse methods (Section 5.1 and Appendix A.2.3) with respect 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 combination of distance- based metrics, performs much worse on the direct metries 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 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 @ 1. These results provide evidence that diversity is not 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 finds the shortest high-density path in the generated graph.
COMPAS. We also observe that COLS
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 basic local search (LS) to optimize for diversity, proximity, and sparsity along with validity. We use a basic non- optimized local search, because there is no simple and efficient way to guarantee 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.
We provide the results for this experiment in Table 2. These results suggest that optimiz- ing for metrics besides EMC is sub-optimal. For diversity, proximity, and sparsity objectives, the FS @ I 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 Metries with LS on FS@ I, which suggests that the EMC objective function leads to higher user satisfaction. Mcanwhile, 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. this experiment, we observe that COLS again does poorly on diversity, whereas it promotes proximity and sparsity in the recourse. Based results from QI 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 spar- sity and proximity are positively correlated with higher user satisfaction and inherently emerge from the idea of satisfying more users.
Results:
8

---

Under review as a conference paper at ICLR 2022
Method
Gender
FS@1
Cov
DIR-FS DIR-Cov
Race
FS@1
Cov
DIR-FS DIR-Cov
F
0.0
0.0
NW
0.0
0.0
DICE
M
4.7
15.6
W
3.1
10.4
12.5
22.1
NW
7.7
12.7
Face-Eps
M
18.8
24.7
1,504
1.118
W
17.8
26.0
2.312
2.047
F
29.9
36.3
NW
12.7
25.4
Face-Knn
0.719
0.89
2.228
1.425
21.5
32.3
W
28.3
36.2
F
53.8
58.7
NW
46.5
54.9
Act. Recourse
0.881
0.959
1.056
M
47.4
56.3
W
51.2
58.0
Random
34.6
0.859
0.792
NW
4.9
28.9
1.571
1.076
M
6.7
27.4
W
7.7
31.1
F
72.7
76.2
NW
67.6
71.1
COLS
0.994
0.992
1.089
1.082
72.3
75.6
73.6
76.9
F 76.5
80.2
NW
72.5
74.6
P-COLS
1.004
M
76.8
80.2
W
77.6
81.5
Table 3: Fairness analysis of recourse methods for subgroups with respect to Gender and Race. DIR: Disparate Impact Ratio; M: Male, F: Female; W: White, NW: Non- Non-White (Section 5.2).
Q3. Are Recourses Fair Across Subgroups?
Here, want to understand whether recourse methods provide equitable solutions across subgroups based on demographic features like Gender and Race. this experiment, we assume Gender is non-actionable for the sake of analysis. Existing works on algorithmic fairness present number of metrics for characterizing the disparate impact of black-box classification models across population subgroups (Feldman al., 2015). We adapt the Disparate Impact metric for the recourse outcomes we study, which we denote by Disparate (DIR). Given a metric M, DIR is ratio between metric scores across two subgroups. DIR-M 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.
Design:
((S=1)/M(S-0)) We use either Cov FS@) @ I as
Results: We present the subgroup- basuu results in Table 3. We observe that COLS and P-COLS typ- ically 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 on DIR-FS and DIR-Cov for the gender-based subgroup, and scores relatively close to 1 the race- mased 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 diverse set of cost functions when generating recourses. We condition (2) as important since there are other individualized methods that do not rely on the data distribution, such Actionable Recourse, which can generate less fair solutions than COLS. Overall, we clude that our method is typically more fair than baselines on both Gender and Race-based subgroups while providing recourse larger fractton of people in both subgroups.
5.3 ADDITIONAL RESULTS
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 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.
6 CONCLUSION
In this paper, we propose cost-based recourse generation method which can optimize for an un- known 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-Optimin ments over baseline search methods. Lastly, we observe that our recourses are often more fair than baseline recourse methods, while offering recourse to much larger fraction of the user population.
Local Search (COLS), produces large improve-

---

Under review as a conference paper at ICLR 2022
7 ETHICS STATEMENT
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, comment few other ethical aspects of the algorithmic recourse problem.
First, we suggest that fairness is important value which recourse methods should always be eval- uated along, but we note that evaluations will depend heavily on the model, training algorithm, and training data. For instance, 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 faimess metries using 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 in- stance, malicious actors may use recourse methods when developing models order to exclude certain groups from having available recourse, which is essentially reversal of the objective of training models for which recourse is guaranteed (Ross et al., 2021). We view this use case as gen- erally unlikely, but pernicious outcomes may be difficult to detect, and actors may make bad-faith arguments about the fairness of their de- ployed models based other notions of fairness (like whether or not model has access protected demographic features) that distract from an underlying problem in the fairness of recourses.
possible. We also note that these kinds of outcomes
8 REPRODUCIBILITY STATEMENT
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- pre-processing is provided in Appendix B.I.1. We also provide clear and concise Algorithms I, 4, 5 for cost sampling procedures and our optimization method COLS in Algorithm 2. Additionally, we also provide formal proof of the Theorem 4. stated in paper in Appendix A.2.2 along with the constructive procedure for the proof is provided in Algorithm 2.
REFERENCES
Carlos Aguilar- Paaaaioo Sergio Muñoz-Romero, and José Luis Rojo-álvarez. Cold-start promo- tional sales forecasting through gradient boosted-based contrastive explanations. IEEE Access, 2020.
Ifeoma Ajunwa, Sorelle Friedler, Carlos H Scheidegger, and Suresh Venkatasubramannin. Hiring by algorithm: Predicting and preventing disparate impact. Available SSRN, 2016.
Ricardo Baptista and Matthias Poloczek. Bayesian optimization of combinatorial structures. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Confer- ence Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp-
462-471. PMLR, 10-15 Jul 2018. URL https: nttpps:/prroceedingg wwt.:ssss.....p..pp...es bapt baptistall 8a html.
Yatong Chen, Jialu Wang, and Yang Liu. Strategic recourse in linear classification. CDMDE work- shop, 2020.
Furui Cheng, Yao Ming, and Huamin Qu. Dece: Decision explorer with counterfactual explanations for machine learning models. IEEE Transactions on Visualization and Computer Graphics, 27: 1438-1447, 2021.
Alexandra Chouldechova, Diana Benavides-Prado Oleksandr Fialko, and Rhema Vaithianathan. A case study of algorithm- assisted decision making in child maltreatment hotline screening deci- sions. In Conference on Fairness, Accountability and Transparency, pp. 134-148, 2018
10

---

Under review as a conference paper at ICLR 2022
Zhicheng Cui, Wenlin Chen, Yujie He, and Yixin Chen. Optimal action extraction for random forests and boosted trees. In Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pp. 179,188,40 2015.
Susanne DandI, Christoph Molnar, Martin Binder, and Bernd Bischl. Multi-objective counterfactual explanations. In Thomas Bäck, Mike Preuss, André Deutz, Hao Wang, Carola Doem, Michael Emmerich, and Heike Trautmann (eds.), Parallel Problem Solving from Nature PPSN XVI, pp. 448-469, Cham, 2020. Springer International Publishing. ISBN 978-3-030-58112-1.
Amit Dhurandhar, Pin- Chen, Ronny Luss, Chun-Chen Tu, Pai-Shun Ting, Karthikeyan Shan- mugam, and Payel Das. Explanations based on the missing: Towards contrastive explanations with pertinent negatives. In Advances in Neural Information Processing Systems, 2018.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. https: / archive. ics. uci. www/ee//aa/eeeeeeeeeeee dat aset / adult.
Javid Ebrahimi, Anyi Rao, Daniel Lowd, and Dejing Dou. HotFlip: White-box adversarial ex- amples for text classification. In Proceedings of the 56th Annual Meeting of the Associa- fion for Computational Linguistics (Volume 2: Short Papers), pp. 31-36, Melbourne, Aus- tralia, July 2018. Association for Computational Linguistics. doi: 10.18653/v1/P18- 2006. URL https: hatps////caaaahhllooo.. org/P18 2001/P188006.....
Michael Feldman, Sorelle Friedler, John Moeller, Scheidegger, and Nenkatasubramanian. Certifying and removing disparate impact. Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2015.
Oscar Gomez, Steffen Holter, Jun Yuan, and Enrico Bertini. Vice: visual counterfactual explanations for machine learning models. In Proceedings of the 25th International Conference on Intelligent User Interfaces, pp. 53 531-535, 2020.
Masoud Hashemi and Ali Fathi. Permuteattack: Counterfactual explanation of machine learning credit scorecards. arXiv preprint arXiv:2008. /0138, 2020.
Henry Hinnefeld, Peter Cooman, Nat Mammo, and Rupert Deese. Evaluating fairness metrics in the presence of dataset bias. ArXiv, abs/ 0ts/1809009245 2018.
Shalmali Joshi, Oluwasanmi Koyejo, Warut D. Vijithenjaronk, Been Kim, and Joydeep Ghosh. Towards realistic individual recourse and actionable explanations in black-box decision mak- ing systems. International Conference on Learning Representations; Workshop Safe ML, abs/1907.00615, 2019.
Kentaro Kanamori, Takuya Takagi, Ken Kobayashi, and Hiroki Arimura. Dace: Distribution-awwn counterfactual explanation by mixed-integer linear optimization. In Christian Bessiere (ed.), Pro- ceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI-20, pp. 2855-2861 International Joint Conferences Artificial Intelligence Organization, 7 2020. doi: 10. 244963/jjcai.22200399 URL pittps://cae orq 2..0..499 24963 /1//66//j/caa 2020 395. Main track.
10.
Amir-Hossein Karimi, G. Barthe, B. Balle, and Isabel Valera. Model-agnostic counterfactual ex- planations for consequential decisions. International Conference on Artificial Intelligence and Statistics, abs/1905. 11900 2020a.
Amir-Hossein Karimi, Gilles Barthe, Bernhard Schölkopf, and Isabel Valera. A survey of algorith- mic recourse: definitions, formulations, solutions, and prospects. CoRR, abs/2010.04050, 2020b. URL httph::///// /ttr://rzaa aaaaaaiivvvv.....a...aa...aa.... org/ abs/2010. 04050.
Amir-Hossein Karimi, Bernhard Schölkopf, and Isabel Valera. Algorithmic recourse: from counter- factual explanations to interventions. FAceT, 2020c.
Amir-Hossein Karimi, Julius Kügelgen, Bernhard Schölkopf, and Isabel Valera. Algorithmic recourse under imperfect causal knowledge: a probabilistic approach. Advances in Neural Infor- mation Processing Systems, 2020d.
11

---

Under review as a conference paper at ICLR 2022
A. Kulesza and B. Taskar. Determinantal point processes for machine learning. Found. Trends Mach. Learn., 5:123-288 286, 2012.
Jeff Larson Surya Mattu,
Lauren Kirchner, http://giiihb..ommpopppolloaoopp analysis, 2016.
and Julia
Angwin.
Scott M. Lundberg and Su-In Lee. A unified approach to interpreting model predictions. NIPS, 2017.
Hans Mittleman. Mixed integer linear programming benchmarks (miplib 2010). http://plato. asu. edu/ Etp/mi ppc. html, 2018.
Ramaravind K Mothilal, Amit Sharma, and Chenhao Tan. Explaining machine learning classifiers through diverse counterfactual explanations. In Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency, pp. 607-617, 2020.
Martin Pawelezyk, Klaus Broelemann, and Gjergji Kasneci. Learning model-agnostic counterfac- tual explanations for tabular data. In WWW, pp. 3126-3132, New York, NY, USA, 2020. Associ- ation for Computing Machinery. ISBN 470145037 doi: 10.1145/33642333380077 URL
ht.ps: /10.gg11..0 145/ 3355/3366422... 3380087
Martin Pawelczyk, Sascha Biclawski, Johan Van den Heuvel, Tobias Richter, and Gjergji. Kas- neci. CARLA: A python library to benchmark algorithmic recourse and counterfactual explana- tion algorithms. In Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 1), 2021. URL https: wwwpoeeeeeiieeeee/eeeeee net forum? did= vDi1kBNNbx6.
Brett Poulin, Roman Eisner, Duane Szafron, Paul Lu, Russell Greiner, David S Wishart, Alona Fyshe, Brandon Pearcy, Cam MacDonell, and John Anvik. Visual explanation of evidence with additive classifiers. Proceedings Of The National Conference On Artificial Intelligence, vol- ume 21, pp. 1822. Menlo Park, CA; Cambridge, MA; London; AAAI Press; MIT Press; 1999, 2006.
Rafael Poyiadzi, Kacper Sokol, Raul Santos-Rodriguez, Tijl De Bie, and Peter Flach. Face: Feasible and actionable counterfactual explanations. In Proceedings of the AAAI/ACM Conference on AI, Ethics, and Sociery, AIES '20, pp. 344-350, New York, NY, USA, 2020. Association for Computing Machinery. ISBN 9781450371100. doi: 10.11145/337567.3335550 URL https:
100 1145/3375627 000.7776777337750 33758550.
Yanou Ramon, David Martens, Foster Provost, and Theodoros Evgeniou. Counterfactual explana- tion algorithms for behavioral and textual data. Advances in Data Analysis and Classification, 2020.
Peyman Rasouli and Ingrid Chieh Yu. Care: Coherent actionable recourse based on sound counter- factual explanations, 2021.
Kaivalya Rawal and Himabindu Lakkaraju. Beyond individualized recourse: Interpretable and in- teractive summaries of actionable recourses. H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp- 12187-12198. Curran Associates, Inc., 2020. URL https: http:////oooee//eeeeeeoe/oe neurips. cc/paper/2020 htt////0//22///////// /ttp://2eeeeee277379797774444443 (aw.a3aaaaaAeceeefaaaaa00000000. Paper pdf.
Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. Anchors: High-precision model-agnostic explanations. In AAAI Conference Artificial Intelligence, 2018.
Christian P. Robert and George Casella. Monte Carlo Statistical Methods. Springer Publishing Company, Incorporated, 2010. ISBN 1441919392.
Alexis Ross, Himabindu Lakkaraju, and Osbert Bastani. Learning models for algorithmic recourse. In Advances Neural Information Processing Systems, 2021.
Leslie Scism. New york insurers can evaluate your social media use they can prove why it's needed, January 2019.
12

---

Under review as a conference paper at ICLR 2022
Ravi Shroff. Predictive analytics for city agencies: Lessons from children's services. Big data, 5(3): 189-196, 2017.
Naeem Siddiqi. Credit Risk Scorecards: Developing and Implementing Intelligent Credit Scoring, volume 3. John Wiley & Sons, 2012.
Dylan Slack, Sophie Hilgard, Himabindu Lakkaraju, and Sameer Singh. Counterfactual explana- tions can be manipulated. Advances in Neural Information Processing Systems, abs/2106.02666, 2021.
Sohini Upadhyay, Shalmali Joshi, and Himabindu Lakkaraju. Towards robust and reliable algorith- mic recourse. Advances Neural Information Processing Systems, 2021.
Berk Ustun, Alexander Spangher, and Yang Liu. Actionable recourse linear classification. Pro- ceedings of the Conference Fairness, Accountability, and Transparency, FAT* '19, pp. 10-19, New York, NY, USA. 2019, Association for Computing Machinery, ISBN 978 1410361155555 doi:
10. 00.1145//288560.22875666 URL https: / /oii www.ooog//.......o..ooooo 1 110.0011111218111110 3287560 3287566
Suresh Venkatasubramaniaa and Mark Alfano. The philosophical basis of algorithmic recourse. In Proceedings of the 2020 conference on fairness, accountability, and transparency, pp. 284-293, 2020.
Paul Voigt and Axel Von dem Bussche. 2018 reform of EU data protection rules. 2018. URL https://ec.eurpge
cowmission/ssssseeooccsooos www.setttttteeeeeeeeeeeee wttpeaatatatiicaall..aaaaaaaaaaa pdf..
Julius von Kügelgen, Amir-Hossein Karimi, Umang Bhatt, Isabel Valera, Adrian Weller, and Bern- hard Schölkopf. On the fairness of causal algorithmic recourse. NeurlPS AFCI Workshop, 2020.
Sandra Wachter, B. Mittelstadt, and Chris Russell. Counterfactual explanations without opening the black box: Automated decisions and the gdpr. Cybersecurity, 2017.
A APPENDIX OBJECTIVE AND OPTIMIZATION
A.1 PROPOSED METHOD
A.1.1 OTHER OBJECTIVES
To obtain feasible a counterfactual set, past works have used various objective terms. We list objec- tives below from methods 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 their diversity objective as defined below.
d = (e), whereK. = 1 dist dist(s 8 85)
Here, dist(si, 8j) 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, (ro Y) = - N E disl(æ, Y.), where Y, is counterfactual.
2. Actionable Recourse (Ustun 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,
Σ log 1- Q,(5 +a,) -
cosl(& (8 + a)
JEJA
where (.(.) the cumulative distribution function s; in the target population, JA is the set of actionable features and aj is the action performed on the feature j.
13

---

Under review as a conference paper at ICLR 2022
Algorithm 1: Procedure for sampling Cost Functions.
Input: 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. function sampleCostAnndPPeeereneee
NoneFp {t.p None)
Fr is empry then
F, GandonSuuseel(F..
sample preferred features.
p None then = else O for f in F]
concentration
p ~ Dirichled(comncnntraaon))
Sample feature preference scores.
if a is None then | Uniform(0,)
10
Sample cost mixing weight.
11
C=0
12
13
forall Si E F do
altitin) o Liii,
- getlimearCCstMMeenss..ll F(, plf.), CettPercenttlcCCosMMeelll pl.f), Fp)
14
Per,) Pll.Porc)
a(Si) a plt.tim)) + (1 - a) p Perc)
16
offi) - a (fintin)
+ (1 - a) * ofi Perc)
17
c(a) - Detalulii,,lla
b Beta with mean and variance 10) x00
C C- C cuc(s))
20
return p. Cp
Algorithm 2: Cost-Optimized Local Search Algorithm
Input: A state vector s, [M Da cost distributions
Output: Shest a set of generated counterfactuals of size N. function LocalSearch(s, (C: J= hammingDistance 2)
Initialize
Sbratt E Nxd + pertubCFS(ss. bamtingDistance)
b Perturb 8, N times. Incurred costs for great
C² getCostMaarix(s,, Sheat, Sheat, (C.)
while usedBudget < Budget do Nxd + pertubCFS Shest hammingDistance)
CER Nx + getCostMatrix (C.))M)) b Incurred costs for the S. // B Change in objective when Sheat + S-D]. B E N + computeBenefits(CC C)
D Refer to Algorithm
// Greedily select which pairs to swap given B replaceIndices gelReplaceldx(B)
// Swap these pairs and update c².
10
forall originalldx, replaceldx E replacelndices do
Shest [originalddx] S(replaceldx]
11
getCostMatrix (8, Sbeat, {C, AM
12
return Sheat C³
13
14

---

Under review as a conference paper at ICLR 2022
Algorithm 3: Algorithm for Theorem 4.1
Input: C². Ce RxM matrices containing the costs with respect all cost samples..
Output: E RNN,, matrix containing the benefits of replacing pairs from St x S
function computeBencffts(C..
Initialize
RERNNN <-
// Find the indices the best and second best counterfactual in gheat for each of the M cost function.
b¹ RM arg max; C
6a E GRA= arg second max, Cj
// Iterate over all pairs of counterfactualss
forall p,q E [N] x [N] do
cost functions which n counterfactual in gheat has the minimum cost. forall ii [M] 6 p)
// Iterate
do
if C > Cor then
// This replacement reduces the cost of gheat by d Car.
B By C), Cgr
else
c/2 cost of second best counterfactual in gheat for p ccst function.
B Bpg C min(Cap Cg
12
return B
A.2 OPTIMIZATION METHODS
A.2.1 HIERARCHICAL COST SAMPLING PROCEDURE
To optimize for EMC, we need plausible distribution which model users' cost functions. We propose a hierarchical cost sampling distribution which provides cost samples that are a linear com- bination of percentile shift cost (Ustun et al., 2019) and linear cost, where the weights of this com- bination 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 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 week. The cost incurred then propor- tional to the difference in these percentiles. The Linear cost for ordered features is proportional to the number of intermediate states in Q() which a user will have to go through while transitioning from their current state the final state. E.g., if user is asked change their education level from High- school to Masters then there are two steps involved in the process. First, they need to get a Bachelors degree and then 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(O) E IR (111x Aʃ E F), we independently sample C()) for each feature (see Algorithm 1). We first randomly sample a subset of editable features for the user, and then sample feature preference score P., from Dirichlet distribution with a uniform prior over selected features. These will be used to scale costs, such that
one. F.g., if
(f) implies lower transition cost for feature For both the percentile and linear cost, the cost c(f) of transitioning from feature state + j. is sampled from a Beta distribution on
higher value of pu
ij the interval [o, 1]. The mean of this distribution depends on the types of cost (linear or percentile) and the feature type (ordered unordered). Here, first obtain one mean for linear cost (H4 (f.lin)
and mean for percentile cost (1)) (((feero)) and then combine them to form single Beta mean. Each 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
15

---

Under review as a conference paper at ICLR 2022
the unit interval (see Algorithms 5, 4). Then, the linear and percentile means multiplied with (1 - (1-pl() to scale the transition cost according to the feature preference score. Next, the two means are combined to obtain a single mean, Hig
(f) = * pig (f.lim) + (1 a.) (1) (f-pere) where E [0. 1] represents whether a user thinks of cost in terms of linear or percentile shift (sampled randomly (f)
from unit interval). Note that the value Pig 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) ojj is set to constant value of 0.01. Finally, the cost C(P) is sampled from Beta , oi ((f)). 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 (p..). If we set a 0, then the resulting distribution Ppere and with a= 1 we get the distribution Diin-
A.2.2 MERGING COUNTERFACTUAL SETS
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 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 S₁ from time 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 E IR N M which specifies the cost of each counterfactual for each of the Monte Carlo samples. We can use this to update the best set Shest using elements from the perturbed set S; at time t. This procedure is defined in algorithm 3. It iterates over all pairs of element in 8; E Sheat and 8, E S₁ and computes the change that will occur in the objective function by replacing 8; + 8,. Note that we are not recomputing the costs here. Given Shest, S., C and C. we can guarantee that we will update the best set Shest 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, Steat e R Nxd the candidate counterfactual at iteration t, S, N the matrix C² E R and C e xai containing the incurred cost of each counterfactual in Sheaf and St with respect to all the M sampled cost functions {C. there always exist a Spest constructed from Steet and S, such that
ExpMinCost(S su, Shest, (C.) S ExpMinCos((s.. Sheat, (M
M
Proof. To prove this theorem, we construct a procedure that ensures that the ExpMinCost is mono- tonic. For this procedure, we prove that the monotonicity of EMC holds. Check algorithm for a constructive procedure for this proof, which is more intuitive to understand.
We start off by noting that each element of Ct the cost of the 7th counterfactual sy in the best set Staat with respect to the cost function C, given by Cost(s,, s C,). Similarly C.₁- = Cost( s; C2) where s; is the tth 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 pair of counterfactual from Sheat x S, and for each Cj. compute the change in the MinCost which we describe
16

---

Under review as a conference paper at ICLR 2022
later. These replacements lead 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 Steaf X 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-henefit for this replacement pair. The cost benefit can be negative for certain replacements counterfactual increases the cost across all the cost functions. The pairs with the highest positive cost benefits are replaced to construct the set Sheat, if no pair has positive benefit then keep set Sheas Stest. Hence, this procedure monotonically reduces EMC. We now specify how the change in MinCost can be computed to complete the proof.
well if the candidate
To compute the change in MinCost for a single cost function C, first we find the counterfactual in Steet with the lowest and second lowest cost which we denote by st, and sf. These are the counterfactuals which can affect the MinCost with respect to particular cost function C, This is true because when we replace the counterfactual st, which has the lowest cost for C2 with new candidate counterfactual 8;, there are two cases. Either, Ch, > Ciy Ch,s I Cij. In case when the candidate 8; has lower cost for C, than Ch,y, i.. Ch,, > C.j. then the replacement reduces the cost by Ch,; Cij- In case when the candidate cost for C,. Cij. is higher than the lowest cost in the best set C i.e. Ch, S Cij. it means that this replacement will increase the cost for C; by Ch -minn (Cij; Claz) Here, C2 is the second lowest cost counterfactual for C.. Note that the change in this case will be negative and also depend on the second best counterfactual because once the 8f, is removed from the set, the best cost for C, will either be for st, or 8t, 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 understand the proof.
A.2.3 OTHER METHODS
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
A
A k
C(x) = arg min Ciumi
+ (Css)
dist(c; x) - A2 dip_diversity(ee..... Ck)
where C; is a counterfactual, & 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 λ and A2 are hyperparameters to balance the components in the objective. Please refer to Mothilal 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 e-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 ss 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 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 action set A(z). The set A(x) imposes constraints related to feasibility and actionability with respect to fea- tures. They optimize the percentlee shift objective (see Section A.1. Their final optimization equation is
min cost(a; a)) s.l. f(x a) +1, E A(x)
17

---

Under review as a conference paper at ICLR 2022
Adult Income Binary
COMPAS Binary
Adult-Income
COMPAS
# Continuous features
3
4
2
3
# Categorical features
10
12 Will Recidivate Won't Recidivate
Undesired class
< 50k
Will Recidivate
50k
Desired cluss
>> 50k
Won't Recidivate 1415/229/491
>. 50k
Train/val/test
20088/2333/749
13172/15697748
5491/705/444
Model Type
ANN(2. 20)
ANN(2. 20) 69%
ANN(2. 20)
ANNI2.
Val Accuracy
82%
81%
61%
Table 4: Table containing data statistics and black-box model details. The binary version of the datasets are take from (Pawelczyk et al., 2021) whereas the non-binary version are taken from (Mothilal al., 2020).
which is cast as an Integer Linear Program (Mittleman, 2018) to provide users with recourses. Their publicly available implementation is limited to binary case for categorical features," hence we demonstrate results on the binarized version of the dataset.
B APPENDIX EXXPRIMENTSS AND DETAILS
B.I EXPERIMENTAL SETUP
B.1.1 DATASETS AND BLACK-BOX MODEL.
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 muta- ble or conditionally mutable depending on semantics. These constraints can incorporated into the methods by providing schema of feature mutability criterion. Our black-box model is multi-layer perceptron model with hidden layers trained on the trained set and validated on the dev set. The accuracy numbers shown in Table 4. The test 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 the ability to query the model for outcome given user's state vector.
B.1.2 RECOURSE GENERATION AND EVALUATION PIPELINE
To approximate the expectation in equation 5, our algorithm samples set of random cost functions (C,).21 D Drrain. 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 cost samples, hence this set satisfies a large variety of samples from Dirain. This 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 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 the set have low cost at least with respect to one Monte Carlo cost sample. The generation phase outputs a set counterfactuals which is be provided the users recourse options. Given this set S,, in the evaluation phase, the users simulated cost functions which are hidden in the generation phase, to compute the cost incurred by the user as defined in Equation and calculate the metries defined in the Section 5.1.
Pllease refer the this example where they mention about these restricted ahilities htt.s//wwwaaccttiaaaoooooeeeeeta "The binary datasets can be downloaded from http://ggttuuccco//aaaaaaaaaomm binary data can be found https://ggthhh.cm/m/mrrre//////p
whereas the non-
18

---

Under review as a conference paper at ICLR 2022
Linear vs Percentile Cost Robustness
Monte Carlo a-weight
100
Methods Robustness to Distribution Shifts
100
Binned FS@1
OOLS
90
0.6
80
0.4
70
96
03
60
0.00
0.05
0.10
0.15
0.20
0.25
0.30
0.9
Distribution Shift
1.0 50
0.0
0.6 User a-weight
Figure 2: In this plot we show the fraction of users satisfied the distance between the train and test distributions. The results demonstrate that the distance increases the performance drops a bit and then plateaus, which means that the method robust this kind of distribution shift. Please refer to Section B.2 for more de- tails.
Figure This figure shows the performance of the method on FS @ when recourses are gen- erated with Monte Carlo cost samples from distribution with a-weight varying between 0 and 1, where the user costs follow different a- weight values varying between O, 1. Perfor- mance robust to misspecification of a. Refer Section B.2 for more details.
Remark 1. In the limiting case, |S| M and Budget oc, RHS of equation 6; min MinCost(# S;C,) - optimum cost, 4 i E [M], if feasible solutions are possible for all cost S functions samples (C.).M..
What this remark implies is that, the size increases 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, 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 do not need large set size.
able to achieve good performance implying that in practice
B.2 ADDITIONAL. RESEARCH QUESTIONS
Q4. Are Solutions Robust to Misspecified Cost Distributions?
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, select 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 education level rather than their work hours 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.
Design:
In this experiment, in the Adult-Income data, we generate recourse sets using Monte Carlo samples from our standard distribution D. (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 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 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 recourse
case of this kind of distribution shift over cost functions. For users
subset corresponds
19

---

Under review as a conference paper at ICLR 2022
generation time. Therefore, when the minimum distance increases, there is greater distribution shift between the user's 's cost functions and those obtained from De. Finally, we measure how many users are satisfied for given degree of distribution shift.
Results: In Figure 2, we show a binned plot of FS@1 I 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 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 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).
Q5. Robustness to Misspecification in Linear vs Percentile based costs?
Design: Our sampling procedure samples cost by taking an a-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 rypes of cost. We perform a robustness analysis where the users cost function has 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 a a-weights within the range of 0 to in steps of 0.2. At the extremes values of a = 0, 1, the shifts are very drastic the underlying distribution changes completely. In the case when monte carlo a weight is O and user a weight is then Dirain = Dpere and Drest. Diin, simlarly for the other case we get Dirain Din and D Plest = Perr.. Please note that the distribution Din and D Ppere have completely different underlying principles and are two completely different distributions.
Results: In Figure we show heatmap plot which demonstrates the robustness of our method. The color of the block corresponding to Monte Carlo alpha, O'm = I and the users alpha, Oaser represents the fraction of users that were satisfied when Ome and Qaser = 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 (D (Derain = Ppere and Drest = Din is similar to the bottom left corner (D Dinn and Drest = Dún)). Similarly things happen for the opposite case which is denoted by the top-right (Dtrain = Dpere and Dtest = D ppere) and bottom-right (Dtrain = Díin and Drest perre) corners. This means that even when 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.
Q6. Does Method Performance Seale with Available Compute?
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 average performance with standard deviation erriattio-bbsedd error bars in Figure 4.
random subset of 100 users for 5 independent runs and then report the
Results: In Figure 4, we
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
20

---

Under review as a conference paper at ICLR 2022
User Satisfaction vs Counterfactuals
User Satisfaction vs # black-bor box access
80
AR
All
60-
R
60-
RI
F
COLS
COLS
P-COLS
P-COLS
40-
0-
0-
10
20
30
500
1000
2000
3000
5000
10000
Number of Counterfactuals [S]
Budget
Figure 5: Figure showing the performance of different recourse methods as the the number of counterfacuals to be generated is increased. These are the average number across differ- ent runs along with standard deviation error bars. We see that there is a monotonic increase in the fraction of users satisfied as the size of the set increases. We also observe that most of the performance set size. Please refer to Section B.2 for more details.
Figure 4: Figure showing the performance of different recourse methods as the Budget is in- creased. These are the average number across 5 different runs along with the standard devia- tion error bars. For some methods the standard deviation is very low hence not visible as bars in the plot. It can be seen that as the budget in- creases the performance of COLS and P-COLS increases. Please refer to Section B.2 for more details.
be obtained with small
show performance improvement but our method COLS and P-COLS consistently upper- their performance. Our method satisfies approximately 70 % of the user with small budget of 500 and quickly starts to saturate around a budget 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 very small margin and then stays constant these methods are trying optimize for different objectives which don't It align well with user satisfaction as demonstrated in Section 5.2.
Q7. Does providing more options to users help?
Design: In this experiment, we measure the effect of having flexibility to provide the user with more options, i.e. 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 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 in the set 3,5, 10, 20,33 30). We restrict the size of the set to maximum of 30 as beyond 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 @ 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 to 30. This is consistent with the intuition behind our methods (See Figure 1, sec- tion 4.1, 1.2 for more details). It is fundamental property of our objective that |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 '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| E 21, our methods significantly outperform all the other methods in terms of the number of users satisfied. This property is useful in real-world sce- narios where the deployed recourse method can provide as little 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 't change as we increase the set size because the method doesn't 't take local steps from the best set and samples random points from a very large space, hence is much harder to end up with low-cost counterfactuals.
21

---

Under review as a conference paper at ICLR 2022
Fenture Name
State Vector
Editable Features
Preference scores
Recourses
Cost
Age
Education-Ning
Workelass
Private
10
No
No
(Capital Loss: O
1)
0.009
Mariial-Starus
Married
Occupation
Other
Yes
0.085
Relationship
White
Husband
No
(Occupation: Other Manager)
0.378
Gender
Male
No
Capital Gain
0
Capital Loss
Work Hours
0
40
No
Yes
0.944
Occupation: Other Manager
Capital Loss: 0
0.387
Country
Age
45
No
Workelass
Private
(Capital Loss: -1
Education-Num
Yes
0.537
Martial-Sae Status
Married
No
Occupation
(Capital 1)
Relationship
Non-Husband
No
0.106
Race
White
No
(Educatioon-Num) 10)
Cupital Gain
0
Yes
0.078
0.187
Capital Loss
0
Yes
0.240
Country
Work Hours
US
No
Yes
0.142
(+ Work Hours: 32
70)
0.695
Table 5: Table providing qualitative examples for two users from the dataset. We show each users state vector, the features that user is willing to edit, the preference scores for those editable features, the recourses provided and the cost of the generated recourses. In the first example we see that user highly prefers the feature capital loss and the recourse which suggests edit that has the lowest cost for the user. Whereas, the recourse which makes changes to both Occupation and Capital Loss has the highest cost as its changing multiple features. For the second user, we see that the most preferred feature is EducattionNNum but the changes suggested in the recourse requires three steps 7-8-9-10, hence the cost for that recourse is not the lowest but still relatively low. Whereas, the recourse suggesting smaller changes to Capital Loss which is the second most preferred feature has the lowest cost for the user.
Q8. Does increase the number of Monte Carlo samples help with user satisfaction?
User Satisfaction Monte Carlo Sample
80
COLS
Design: In this experiment, want demon- strate the effect of increasing the number of Monte Carlo samples on the performance of our COLS method. We take random subset of 100 users, 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 dif- ferent runs with different Monte Carlo samples and show the average FS@ I along with the standard deviation in the Figure 6.
75
70
65
60
55
10
200 360 500 1000 Num MC Samples
30 100
Figure 6: Figure showing the performance of the COLS method as the number of Monte Carlo samples increase. These are the average number across 5 different runs along with standard devia- tion error bars. There is a steep increase and then the performance saturates. This implies that in practice we do not need large number of samples to converge to the higher user satisfaction. Refer to Section B.2 for more details.
Results: We observe that as the number of Monte Carlo samples increases, the perfor- mance of the method the FS@1 metric monotonically increases. This supports the in- tuition underlying our method (see Figure 1). That is, given a user with a cost function C, as we get more and more samples from the cost distribution D., the probability of having cost sample similar to C, 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 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.
22

---

Under review as a conference paper at ICLR 2022
Data
Method
Metries
Cost Metries
Distance Metrics
FS@
PAC(4)
Cov
Div
Prox
Spars
Val
DICE
6.28
1,45
27.01
53.01
57.02
47.80
86.20
Random
0.08
2.42
17.41
70.35
33.32
22.45
75.71
Adult-Income - .B
COLS 72.67
0.36
74.60
29.27
79.06
76.64
97.85
P-COLS
70.03
0.39
72.81
29.85
78.45
76.29
92.30
DICE 14.86
1.02
25.45
27.88
82.38
69.44
99.86
Random
1.31
1.87
21.76
49.07
54.10
42.34
67.82
COMPAS NB
COLS
67.34
0.31
68.11
20.53
85.47
82.34
95,97
P-COLS 70.86
0.35
72.03
21.03
85.48
82.88
91.93
Table 6: Table comparing different recourse methods across various cost and distance metrics Non-Binary versions of the datasets (Section The numbers reported are averaged across different runs. Variance values have been 89% of them were lower than 0.05, with the maximum being 0.86. FS@1 I: Fraction of users satisfied at & 1. PAC: Population Average Cost. Cov: Population Coverage. For all the metrics higher better except for PAC where lower better.
Q9. Qualitative examples of the recourses generated for some of the users.
In Table show few examples of along with their state vector, their editable features, their preference scores along with the recourses provided to them and their cost.
Q10. Comparison of methods Non Binary Dataset?
In Table 6, we show the results on the non-binary version of the dataset. We observe similar perfor- mance on and trends in these results well. COLS and P-COLS performs the best terms of user satisfaction.
23

---

Under review as a conference paper at ICLR 2022
Algorithm 4: Sampling procedure for Percentile Cost Mean
function gePPecentileCosMeenn (a (s,p(t), , Fi) /1 Si value feature fa in s.
if fi $ Fp then (st.)) = 00
(si 8:) =
else
if f. ordered then if fr can only increase then
))(Peeeen))le(() - petreneett)le(ss)
Wr >
0
Vr
DO
Vr 8:
else if Sa can only decrease then getPerenttile(s.) (et
Vx < 88
(s,) x)
Vr =
Va >
else if fo can both increase decrease then
get gereeneet))))))) get get
Vr: >
(s,
Vr 8
get Perceentile(s) getPercentile(z))
Vr < 8;
13
else if fa is unordered then ((.)) = Uniform((,11 1) (s...) + (s,,) (1 (1-) (f)))s - 0.01
14
15
return (1), ((.))
17
24

---

Under review as a conference paper at ICLR 2022
Algorithm 5: Sampling procedure for Linear Cost Means
function LoLiiearCostMeannss p(f) Fp)
if fi $ Fp then
(si..) 00
(3) 8:) =0
else
if ft is ordered then if Ji can only increase then
My WSorAASc 82ar
Vr >
(s
Vr = 81
4x <
else if fo can only decrease then
Hy y5 Ry v<
Va < 88
(s,
Vr 84
Vr > St else if fa can both increase or decrease then
DO
My Hy y>ach
Vr >
(s,
4A 88
1a < $s
13
else if fo unordered then (s..) Uniform(0,)
14
(s..) + (s,.) (1 (1)((())
15
(f.))s... t 0.01
16
return p(1)), ((f))
17
25


Reviews:
[{"review_id": "u-0M4E_V9XF", "reviewer": "Reviewer_Fy3U", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I enjoyed reading this paper in general. My major comments are:\n\n1.\tIn Section 4.1, it is assumed that there is a distribution over all the cost functions D_c for the population. Is the distribution D_c known or unknown? A more practical setting is that D_c is unknown. Then how to use Monte Carlo Estimation to approximate the expectation of the MinCost?\n\nFor different users u, it is assumed that C_u follows distribution D_c. However, in the introduction, it claims that “we propose a method for identifying a user-specific recourse set that contain at least one good solution for the user”. However, it seems inconsistent between the motivation and the assumption. Why do all users share the same distribution of the cost function? Is the framework generalizable to the setting with different distribution?\n\n2.\tTheorem 4.1 proves the monotonicity of Cost-Optimized Local Search Algorithm. But how does ExpMinCost(s_u, S_t^best; {C_i}_{i=1}^M) converge? Theorem 4.1 does not imply that, but it is a very important question.\n\n3.\tWhy choosing Equation (3) and Equation (4) as metrics to measure recourse quality? What is the advantage of choosing a threshold function? How to choose k in real cases?\n\n4.\tIn the numerical experiments, could you compare with other functions that measure the recourse quality in previous recourse papers? I think my main concern is on FS@k. Is using FS@k equivalent to the following: assume there exists a black-box algorithm that can output the indicator that if the total cost is smaller than k, then the distance function can be used to measure the recourse quality.\n Could you use numerical experiments to emphasize the advantage of using FS@k compare to other measure functions such as weighted sum of costs?\n\n5.   What is the computational complexity of your algorithm? How is that compared to other benchmarks?\n\n6.    Why is fairness an important issue in this work? Could you comment more on this part to motivate?\n", "summary_of_the_paper": "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.", "summary_of_the_review": "This paper studied an interesting problem. To improve the paper, the author may want to illustrate the advantage of using FS@k and how it is very different from state-of-art measure functions, both conceptually and numerically.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "oCbVi2w_otA", "reviewer": "Reviewer_cyuv", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros\n-\tThis paper proposes a new way of evaluating user satisfaction which differs from existing methods that measures on heuristics such as distance/diversity or assume a fixed global user cost function. It is more flexible and realistic, and thus could be an interesting direction to follow. The proposed formulation is quite novel and technically non-trivial, with some theoretical grounding.\n-\tThe experimental results are very strong on the 3 newly proposed metrics. The authors also conduct extensive ablation studies on different aspects of the problem, although many of them are deferred to the supplementary. \n-\tThe discussion is pretty comprehensive, and they also included a fairness analysis.\n\nConcerns\n-\tOne major issue is on the readability of the paper. It is certainly good that the paper contains a lot of information, however currently it seems that the main text is a bit too packed such that very limited detail about the main methodology is provided. In fact, both the core sampling and optimization algorithms are described in the appendix, and it is very hard for this reviewer to understand them solely based on the descriptions in section 4. Perhaps the authors could reorganize the content such that less space is spent on repeating the contributions/motivations. \n-\tAs algorithmic recourse is a rarely new domain and may not be well-known by general audience, it might be better to translate the domain-specific terminologies into plain language or more general language in ML in the introduction part. \n-\tIt seems the newly introduced evaluation metrics are generated using the same sampling distribution used for computing EMC, wouldn’t that be a bit circulated to evaluate something where the ground-truth is closely related to the objective used for optimization? Is there any way to evaluate on more realistic user cost rather than simulating it with the same distribution as the one used in EMC? The authors talk about distributional shift regime in the appendix, that still the ground-truth distribution is from the same family of the EMC distribution (mixture of percentile shift and linear cost). It might be more convincing if it is from a totally independent distribution.\n\nQuestions\n-\tWhat is used as the initial starting set for COLS? \n-\tIn the problem formulation in (2), does it mean that the best recourse set would consist at least one desired outcome solution but it may not be the one with lowest cost? If so how do one achieve balance between outcome and satisfaction?\n-\tWhat is the computational complexity of the algorithm?\n-  Is there any downside from the underperformance in distance-based metrics?\n", "summary_of_the_paper": "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. ", "summary_of_the_review": "In this paper the author proposed a new way for evaluating and optimizing user satisfaction. The technical contributions are solid and the results are rather promising despite the potential bias toward EMC. The paper contains fruitful discussion and ablation studies, although it can be further improved in terms of clarity. Therefore, I would like to give a weak accept.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "DmPOV4HnQiQ", "reviewer": "Reviewer_1gBz", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper addresses an important issue of dealing with model bias in producing fair user outcomes. My main concern with the paper is the lack of clear supporting arguments on why the choice of cost models (including knowing the distribution over the cost functions) is the right one? I am not clear about the assumptions made in the proposed cost function that each user adopts.  First, how is the cost function effectively computed even with the use of a recourse set? Next, how is the recourse set itself guaranteed to always produce at least one reasonable counterfactual in the set?  More specifically, even as the authors acknowledge knowing the exact cost function by each user is difficult, their explanation of using the recourse set to get around this problem with high confidence is unclear to me.  Intuitively, it seems a measure like diversity will be more effective when the cost functions are unknown/private to the user.  \n", "summary_of_the_paper": "The authors propose a recourse methodology to deal with model biases/fairness issues in producing equitable outcomes for all users (classes).  ", "summary_of_the_review": "I am not completely convinced the proposed model of computing a recourse set to minimize the expected cost for the user is always effective in the absence of knowing the cost function even approximately.   The experiments to show the effectiveness with respect to the proposed baseline are inconclusive with respect to natural measures like diversity.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "5N3Ba-AcXT3", "reviewer": "Reviewer_B3sM", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I do not think this papers achieves what it sets out to do. It is mentioned in the related work, how the closest literature to the paper is other cost-based approaches to finding recourse and different from those approaches, this paper drops the assumption that there is a known global cost function that is shared by all users. First, the paper formulates $\\mathrm{MinCost}(\\cdot;\\mathcal{C}_u)$ as the cost function of user $u$, which is characterized by the unknown transition matrices $\\mathcal{C}_u$. However then, the paper assumes a distribution $\\mathcal{D}$ over $\\mathcal{C}_u$ 's of different users is known and proposes to optimize $\\mathbb{E}_\\mathcal{C}{}_\\sim{}_\\mathcal{D}[\\mathrm{MinCost}(\\cdot;\\mathcal{C})]$, which is effectively a known global cost function (with respect to user state $\\mathbf{s}_u$ and recourse set $\\mathcal{S}$). Is this not the case?\n\nHaving said that, the proposed cost function has a certain structure and it is still novel: (i) authors propose a hierarchical cost distribution as the particular $\\mathcal{D}$ they consider and (ii) by only considering the element with the minimum cost for each sample from $\\mathcal{D}$, they exploit the fact that each users only really requires one recourse that they are happy with to be satisfied. Proposing a new cost-based objective like this could still be a valuable contribution. But then, the paper needs to be positioned accordingly and highlight the merits of optimizing a cost-based objective structured in this new way. Note that the current experiments are not helpful in comparing against other cost-based objectives proposed in previous work: cost functions of the users are simulated according to the proposed cost function, then of course, a method that optimizes it would perform better than methods optimizing other cost functions.\n\nSome of the conclusions made in the results section suffer from user preferences being simulated as well. For instance, at the end of \"Q2,\" the authors conclude that high diversity is not necessary to satisfy individual users; this is of course true for the simulated users since their cost function is designed to ignore diversity in the first place.\n", "summary_of_the_paper": "This paper aims to find algorithmic recourse that has low-cost to the users. Unlike previous work, the authors do not assume that there is a known global cost function that is shared by all users.", "summary_of_the_review": "I believe the claim that the paper relaxes the assumption of knowing a global cost function is not true. However, it still introduces an interesting new objective to optimize for when finding algorithmic recourse.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper makes an interesting contribution to the literature on algorithmic recourse. More specifically, while existing literature assumes that there is a global cost function that is applicable to all the users, this work addresses this limitation and models user specific cost functions. While the premise of this paper is interesting and novel, there are several concerns raised by the reviewers in their reviews and during the discussion: 1) While the authors allow flexibility to model user specific cost functions, they still make assumptions about the kind of cost functions. E.g., they consider three hierarchical cost sampling distributions, each of which model percentile shift, linear shift, and a mixture of these two shifts. The authors do not clearly justify why these shifts and a mixture of these shifts is reasonable. Prior work already considers lot more flexible ways of modeling cost functions (in a global fashion). For example, Rawal et. al. 2020 actually learns costs by asking users for pairwise feature comparisons. Isn't this kind of modeling allowing more flexibility than sticking to percentile/linear shifts and their mixture? 2) Several reviewers pointed out that the main paper does not clearly explain all the key contributions. While the authors have updated their draft to address some part of this concern, reviewers opine that the methods section of the paper still does not discuss the approach and the motivation for the various design choices (e.g., why a mixture of percentile and linear shifts?) clearly. 3) Reviewers also opine that some of the evaluation metrics also need more justification. For instance, Why is fraction satisfied measured at k = 1 i.e, FS@1 measured and why not FS@2 or FS@3? Will the results look different for other values of k here? 4) Given that Rawal et. al. 2020 is a close predecessor of this work, it would be important to compare with that baseline to demonstrate the efficacy of the proposed approach. This comparison is missing. 

Given all the above, we are unable to recommend acceptance at this time. We hope the authors find the reviewer feedback useful.
Decision: Reject