INSPIRE: A Framework for Integrating Individual User Preferences in Recourse
Authors: Prateek Yadav
Peter Hase
Mohit Bansal
Venue: Submitted to ICLR 2023 (2023)

Abstract: Most recourse generation approaches optimize for indirect distance-based metrics like diversity, proximity, and sparsity, or a shared cost function across all users to generate recourse. The latter is an unrealistic assumption because users can have diverse feature preferences which they might be willing to act upon and any changes to any undesirable feature might lead to an impractical recourse. In this work, we propose a novel framework to incorporate the individuality of users in both recourse generation and evaluation procedure by focusing on the cost incurred by a user when opting for a recourse. To achieve this, we first propose an objective function, Expected Minimum Cost (EMC) that is based on two key ideas: (1) the user should be comfortable adopting at least one solution when presented with multiple options, and (2) we can approximately optimize for users' satisfaction even when their true cost functions (i.e., costs associated with feature changes) are unknown. EMC samples multiple plausible cost functions based on diverse feature preferences in the population and then finds a recourse set with one good solution for each category of user preferences. We optimize EMC with a novel discrete optimization algorithm, Cost-Optimized Local Search (COLS), that is guaranteed to improve the quality of the recourse set over iterations. Our evaluation framework computes the fraction of satisfied users by simulating each user's cost function and then computing the incurred cost for the provided recourse set. Experimental evaluation on popular real-world datasets demonstrates that our method satisfies up to 25.9% more users compared to strong baselines. Moreover, the human evaluation shows that our recourses are preferred more than twice as often as the strongest baseline.

Under review as a conference paper at ICLR 2023
INSPIRE: A FRAMEWORK FOR INTEGRATING INDIVIDUAL USER PREFERENCES IN RECOURSE
Anonymous authors Paper under double-blind review
ABSTRACT
Most recourse generation approaches optimize for indirect distance- metrics like diversity, proximity, and sparsity, or shared cost function across all users to generate recourse. The latter is an unrealistic assumption because users can have diverse feature preferences which they might be willing to act upon and any changes to any undesirable feature might lead to an impractical recourse. In this work, we propose a novel framework to incorporate the individuality of users both recourse generation and evaluation procedure by focusing on the cost in- curred by user when opting for a recourse. To achieve this, we first propose objective function, Expected Minimum Cost (EMC) that is based on two key ideas: (1) the user should be comfortable adopting at least one solution when pre- sented with multiple options, and (2) we can approximately optimize for users' satisfaction even when their true cost functions (i.e., costs associated with feature changes) are unknown. EMC samples multiple plausible cost functions based on diverse feature preferences in the population and then finds a recourse set with good solution for each category of user preferences. We optimize EMC with a novel discrete optimization algorithm, Cost-Optimized Local Search (COLS), that is guaranteed improve the quality of the recourse set over iterations. Our evaluation framework computes the fraction of satisfied users by simulating each user's 's cost function and then computing the incurred cost for the provided recourse set. Experimental evaluation on popular real-world datasets demonstrates that our method satisfies up to 25.9% more users compared to strong baselines. Moreover, human evaluation shows that our recourses are preferred more than twice as often as the strongest baseline.'
INTRODUCTION
Over the past few years, ML models have been increasingly deployed to make critical decisions related to loan approval (Siddiqi, 2012), allocation of public resources (Chouldechova et al., 2018), and hiring decisions (Ajunwa et al., 2016). These decisions have real-life consequences for the involved users. As a result, there is a growing emphasis on explaining these models' decisions (Poulin et al., 2006; Ribeiro et al., 2018) and providing recourse for unfavorable decisions (Voigt & dem Bussche, 2018). A recourse is an actionable plan that allows a user to change the decision of a deployed model to desired alternative (Wachter al., 2017). Recourses are often presented to users as a set of counterfactuals (cfs), where each of details the changes to the user's 's state vector (i.c., their feature vector). Recourses are desired be actionable, and feasible. Actionable means that only features which can be changed by the user are requested to be changed. A recourse is feasible if it is easy for the user to adopt, in other words, it is actionable and has a low cost for the user.
To achieve these objectives, prior work used feature distance-based objectives like proximity, spar- sity, and feature diversity. For instance, Mothilal et al. (2020) and Wachter al. (2017) encourage proximity by minimizing the distance between the user's state vector and the counterfactuals (cfs) with the assumption that proximal cfs are easier to adopt. Whereas, sparsity quantifies the number of features that require modification to implement a recourse (Mothilal et al., 2020). In contrast to these, feature diversity (Mothilal et al., 2020; Cheng et al., 2021) provides a user with multiple cfs that change diverse subsets of features assuming that users are more likely to find at least one feasible
Our code is uploaded supplementary material.

---

Under review as a conference paper at ICLR 2023
solution. These objectives capture the desired properties of recourses but do not account for individ- ual user preferences that should be the primary objective. For instance, if a user prefers to change features fi and f2, then providing them with recourses that change undesirable features make them infeasible even if they are proximal, sparse, and diverse. To address this, some recourse methods de- fine single cost function that is shared by all the users. A cost function i, denotes the cost of changing a feature/ f from value i to j. They optimize and evaluate for low-cost solutions under this function (Ustun et al., 2019; Rawal & Lakkaraju, 2020; Karimi et al., 2020c;d; Cui et al., 2015). We question this assumption and argue for the importance of user-specific cost functions as shared cost function is likely to poorly represent different users in a diverse population. Hence, these indirect objectives and global cost functions might be necessary but are not sufficient for feasible recourse.
In this work, we propose a novel frame- work, INSPIRE (INdividual uSer Preferences In RecoursE), that incorporates individual user preference via user-specific cost function to generating algorithmic recourse. INSPIRE pro- vides each user with recourse set that contains multiple ef options such that there is at least one feasible solution adhering the user's personal feature preference (if possible). As noted by Rawal & Lakkaraju (2020), in most cases it is difficult for users to specify their exact feature preferences or cost functions. INSPIRE solves this issue by focusing and improving upon four major components - (1) the procedure to for- malize and define individual user preferences via user-specific cost functions, (2) the recourse (3) the optimization algo- rithm, and (4) the evaluation procedure.
C.
0
00
00.00
0
0
0
0
0
00000
81
82
0
25
0
True Cost Function
Sampled Cost Functions
objective function,
Diagram showing the intuition behind the Expected Minimum Cost Objective. This figure rep- resents an abstract cost function space where squares denote cost function samples that are the same color if they are similar and form a cluster. We aim to find re- course where each cf (here, {81,82, under particular cluster of cost functions. The shaded big circles each represent a single of s, that caters to the enclosed cost functions. Here the user's 's hidden ground- truth cost function (grey circle) is served well by s1.
Figure 1:
Next, we propose novel objective function, Expected Minimum Cost (EMC) that approxi- mately optimizes for the cost incurred by the user under their cost function (which is un- known). To do this, (1) we build on Ustun et al. (2019) to propose three distributions over cost functions. Diin Dpere. and Dmiz. that repre- sent diverse user preferences in a population. These distributions are based on linear and percentile changes in the feature values ($3.1). (2) Next, we compute the expected minimum cost of the generated cfs with respect to multiple sampled cost functions from one of the proposed distributions ($3.2). In order to efficiently optimize for EMC, we propose a discrete optimization method, Cost-Optimized Local Search (COLS) ($3.3). COLS guarantees a monotonic reduction in EMC of the recourse set, leading to large empirical reductions in the user-incurred cost. Note that, the EMC objective encourages diversity in the solution set with respect to the diverse feature preferences a user might possess by ensuring that each of is a good of under some particular cluster of cost functions from the sampling distribution. Hence, if the user's ground-truth cost function is well represented by any of the clusters, then we will have some coun- terfactual that is feasible (actionable and low-cost) under their cost function (shown in Figure 1).
82, $3}) does well
To evaluate the effectiveness of EMC and COLS, we run experiments on two popular real-world datasets: Adult-Income (Dua & Graff, 2017) and COMPAS (Larson et al., 2016). We compare our method with multiple strong baselines methods like DICE (Mothilal et al., 2020), FACE (Poyiadzi 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 ($4.1) along with our novel cost-based evaluation framework ($3.4) and a human evaluation. In particular, we define the fraction of satisfied users based on whether their cost of recourse is below certain satisfiability threshold k. We also report coverage, which is the fraction of users with at least one actionable recourse (Rawal& & Lakkaraju, 2020). Using simulated user cost functions, we show that our method satisfies up to 25.89% more users than strong baseline methods while covering up to 22.35% more users across datasets. Furthermore, our human evaluation shows that the recourses generated by our
2

---

Under review as a conference paper at ICLR 2023
method are preferred by humans 57% of the time compared to 25% for strongest baseline (Ac- tionable Recourse), a difference of 32%. We also perform important ablations to show what fraction of the performance can be attributed to COLS optimization method or the EMC objective. Finally, we perform a fairness analysis of all the methods across demographic subgroups to show that our method is more fair than baseline methods. Our primary contributions in this paper are listed below.
1. We conceptualize a novel framework, INSPIRE that accounts for the individuality of users while generating and evaluating recourse options. INSPIRE provides the flexibility for future researchers to further innovate on its four components.
2. We propose new objective function, Expected Minimum Cost that upproximately optimizes for a user's ' true cost function by using diverse plausible cost functions from a distribution.
3. We propose a discrete optimization method, Cost-Optimized Local Search which generates recourses that lead to higher user satisfaction. In human evaluation, we find that our recourses are preferred more than twice as often as the strongest baseline recourses while being fairer.
4. We propose novel evaluation procedure to simulate users' hidden cost functions to asses individual user satisfaction by using our proposed metric FS@K k.
PROBLEM STATEMENT
Features Types. We assume dataset with features F = (f1, fn.. Features can be mutable, conditionally mutable, or immutable, according to the causal processes that generates it. For exam- ple, Race an immutable feature (Mothilal et al., 2020), Age and Education are conditionally mu- table (cannot be decreased), and number of work hours is mutable (can both increase and decrease). Following Ustun et al. (2019), continuous features are always discretized into appropriate sized bins.
Cost Function. In this work, we assume that each user has an inherent captures the ease of changing a particular features, and different users can have different FPs. We express such differential FPs via user-specific cost- cost-funciion. A cost function C(f, j) denotes the cost of changing feature/ f from to j and lies in [0. 1] U (Do). Here, 0 means that the transition has no associated cost, whereas 1 means it is maximally difficult, and oo means that it is infeasible.
(FP) that
Transition Costs. Given a cost function C and two feature vectors 8; 8j, the cost of transition from 8: 8j is the summation of the cost of changing individual features. Hence, Cost(s;; C): ΣJEr EJe=C(f, s/ s(.s)). where sf is the value of feature f in the state vector.
User Definition. A user is defined as a tuple = Ct), where s, the user's current state vector of length |Fi containing their feature values and C,, is their ground-truth cost function. See Appendix Table 7 for examples of 8, and feature preferences. Next, we define the cost incurred by a user when acting on a recourse set S consisting of cfs S. As rational user will select the least costly option, the cost they will incur is the minimum transition cost across of in the recourse set, defined as,
MinCost( su, S;C,)
min Cost(su, $j; C,), where Cost(su, sy;C,) ES
CCUU, JEF
(I)
Problem Definition. For a user u. our goal is to find a recourse set S, such that there exists at least one low-cost cf with the desired outcome. Hence, if the user's ground-truth cost function Cg is provided then we can provide them with a good recourse by directly optimizing for,
S. = arg min MinCost( &u, S:C.)) s.t. F& E S s.t. F(a)= 1,
mig S
where F is the black-box ML model and 1 is the desired class. Similar to Rawal & Lakkaraju (2020), we note that in practice function. Hence, in most practical scenarios C₁ is not provided and we propose the EMC objective to approximately optimize for the user incurred cost.
difficult for a user to precisely quantify their FP and cost
INSPIRE: INCORPORATING INDIVIDUALITY OF USERS IN RECOURSE
Given a user, we first sample some plausible cost functions from our proposed distribution that capture diverse user feature preferences (FP) in a population ($3.1). Then our COLS optimization method to generate candidate recourse set ($3.3). Next, compute our EMC objective for this candidate cfs with respect to multiple samples of cost functions ($3.2). We perform this iteratively to generate final candidate recourse set which is evaluated using our evaluate procedure ($3.4).
3

---

Under review as a conference paper at ICLR 2023
3.1 CHARACTERISING TRANSITION COST AND COST FUNCTION DISTRIBUTIONS
Our first goal is to carefully design distributions to sample cost functions that (1) adhere to the fundamental concepts of how the population quantifies the transition costs between two feature values, and (2) can quantify and integrate different user FPs to represent a diverse population.
Recent works like Ustun et al. (2019) argue that users in population fundamentally quantify the transition cost of changing a feature value from to y as being proportional to (1) the difference in percentile of and y: (2) the number of major steps involved transition from to y. For instance, when changing the education feature from Bachelors to Ph.D., the percentile might be appropriate as very few people have Ph.D. degrees as compared to Bachelors, leading to a higher cost. While in contrast, when changing the number of working hours from 30 to 35, users might associate fixed cost for every additional hour as opposed to percentile differences. We recognize these different underlying phenomena for quantiffying transition costs and call them percentile cost and linear cost.
Even though most users quantify transition costs for features in the two ways described above, they can find it easier harder to act upon certain features depending on their personal cireumstances. We quantify these user FPs via preference-sconee
denoted by p = [p',..... : pf which sum to and each p [0, 1] represents the willingness of the user u to change feature fú- We use these FPs to scale the transition costs (percentile and linear costs) of each feature /; by (1 (I-p") which decreases the cost of transition for preferred features and vere-versa. This allows us to create user-specific cost-function that accounts for their FPs. Now, given a FP scores p. Algorithm 2 and 3 allow us to generate cost functions based on percentile and linear costs respectively that adhere to the FPs.
Next, we propose three distributions, Dpere: Diin Dmiz, that are highly flexible and can generate cost-functions that model diverse FPs better represent a population. The distributions Dpere. Diin are based on percentile and linear transition costs. Whereas, Dmiz is our most general distribution that combines both linear and percentile transition costs using a user-specific cost-type weight a. To generate samples from Dmiz, we use Algorithm 4 that first samples a FP scores p by (1) randomly sampling a subset of preferred features for a hypothetical user that are easy to act upon, and (2) sampling their FP scores p from Dirichlet distribution with concentration parameter with all ones for preferred features and zero otherwise. Then, we use FP score p along with a state vector s in Algorithm 2 and 3 to sample percentile and linear transition cost. We then obtain the mixed-costs by taking a convex combination of the percentile and linear transition costs with randomly sampled cost-type weight
Jni 1) that capture the user's fundamental way to quantify transition cost. These mixed-costs represent transition cost for a hypothetical user with FP score p and cost-type weight a. In order to capture the slight variance amongst users with similar preference, we use a Beta distribution with the mixed-costs as mean with a small noise (std = 0.01) to get the final cost function.
We highlight some desired properties of our Dinc distribution - (1) The distribution captures all possible FP score vectors p because we randomly sample the preferred features. (2) It captures user's predilection towards linear and percentile costs by combining them with cost-type weight. (3) The Linear and Percentile costs are monotonic, i.e., more drastic changes have higher the asso- ciated costs. (4) Following Watson et al. (2021), we provide the user with an option to specify their needs by providing their preferred features, or FP scores p. These properties allow to represent a much larger space of plausible cost functions compared to past works that assume a shared cost function with no user FPs. Hence, these distributions better represent population.
3.2 EXPECTED MINIMUM COST (EMC) OBJECTIVE FUNCTION
As noted by Rawal & Lakkaraju (2020), in most practical scenarios the user's 's true cost-function C₁ is hard to obtain thus we cannot exactly minimize for Equation 2. Hence, we propose the Expected Minimum Cost (EMC) objective function. Give state vector s, recourse set S, and a distribution Drrain to sample cost functions, we compute EMC as follows,
1 EMC(s, S) = Be, |MinCost(s, S;C.) x M
Σ min Cost(s, C.). EEES
(3)
We employ Monte Carlo Estimation (Robert & Casella, 2010) to approximate the expectation by M sampling M cost functions { from D Derain and then expand MinCost using Equation 1. More- over, the distribution Dtrain can be any of the three distributions we proposed. Next, for the user u,
4

---

Under review as a conference paper at ICLR 2023
obtain the recourse set S, by minimizing the EMC objective as follows,
S arg min EMC(
(4)
8
3.3 COST OPTIMIZED LOCAL SEARCH (COLS)
To generate a recourse set S, for user u, we optimize for EMC as shown Equation 4. We propose two simple, and efficient discrete search algorithms (Pir- lot, 1996), namely Cost-Optimized Lo- cal Search (COLS) and Parallel Cost- Optimized Local Search (P-COLS) pre- sented in Algorithm 1. COLS maintains best set gheat which will be the final re- course provided to the user. At each it- eration candidate set S, is generated by locally perturbing each element of the best with Hamming distance of two, ie. making small changes to two features once. Then it is evaluated against the EMC objective as defined in Equation 3. For efficient implementation we store the costs of all the N cf's with respect to all the M cost functions C,. Instead of mak- ing direct comparison of EMC for the best-set-so-fal and the candidate set, we evaluate whether any cfs from the candi- date set S, would improve the EMC of the best set Shest if we swapped out individual cfs. Specifically, if the benefit of replacing 8; S, with 8j Shest is positive, i.e., reduces EMC of Shest then we make the replacement (see Algorithm 5). The abil- ity to assess the benefit of each candidate of is critical because it allows us to con-
Algorithm 1 Cost-Optimized Local Search Algorithm
Input: A state vector {C= Derain cost distributions
Output: Sheat set with N generated counterfactuals.
function COLS(s, {C:) AM Budget, hamDist = 2)
Initialize
11 Perturb N times. Sheat e BRdxd <- pertubCFS(s,, hamDist)
1/ Incurred costs for Sheat
C + getCostMatrix(s. Sheat [C.)
= 0; maxiter = Budget//N
while / < maxtter do
S. E Nxd + pertubCFS(S" hamDist)
C R NxM S (C.))))))
1/ Bi Change in objective ive when Sheat + Slj]. See Algorithm 5. B RNN +- computeBenffis((C C)
// Greedily select which pairs to swap given B replacelndices + (cdeplacelld)))
// Swap these pairs and update ch. forall originalldx, replacelds repplcalldd E replacelndices do
Shea (riginalldxx] = S(replaceldx
end
C³ getCostMatri(ss Sheat, )
end return Sheat c*
end
stantly update the best set using cfs from candidate set instead of waiting for an entire candidate set with lower EMC. For objectives like feature diversity, evaluating the benefit of individual placement becomes expensive (see Appendix 1). Moreover, for COLS we can guarantee that the EMC of the best set will monotonically decrease over time, which formally state below:
Theorem 3.1 (Monotonicity of COLS Algorithm). Given the best set, Steet R the candidate set at iteration St T Nxd the matrix Ch N and E RNXM containing the incurred cost of each counterfactual in Steat and S₁ with respect to all the M sampled cost functions {C, ( ii=
M
there always exist Shest constructed from Sheat and S₁ such that
EMC(8 Shest, (C.))Mm) S EMC(8u, SMCCss,,Stat. (C.).M))
Sheat, M
For the proof of the theorem, please refer to Appendix B.2.2.
P-COLS:
The P-COLS method is variant of COLS that starts multiple parallel runs of COLS with different initial sets. With a given computational budget, each run allocated a fraction of the budget. The recourse of the run with the least objective value is provide to the user.
3.4 EVALUATION PROCEDURE AND INDIVIDUAL USER BASED METRICS
Given that users' ground-truth cost functions C are unknown, in order to asses user's satisfaction, we need to ask them. Generally, obtaining such feedback challenging. Hence, for every user u, we simulate evaluation cost function C# from distribution Drest and use Equation 1 to compute their
5

---

Under review as a conference paper at ICLR 2023
Table 1: Recourse method performance various cost and distance metries (Section 4.1). The numbers reported are averaged across different runs. For the metries higher better except PAC.
Data
Method
Metrics
Cost Metries
Distance Metries
FS@1
PAC(C)
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.0
Face-Knn
25.30
0.74
35.00
8.62
89.07
71.85
100.0
Adult-Income
Act. Recourse
49.93
0.55
56.85
18.38
74.68
73.57
78.67
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.0
Face-Knn
12.20
0.29
12.20
2.60
94.10
60.60
100.0
COMPAS
Act. Recourse
65.80
0.40
66.60
11.87
80.53
74.07
COLS P-COLS
82.23
0.24
82.23
29.32
77.82
70.05
95.48
83.73
0.24
83.73
29.38
78.48
71.30
92.78
incurred cost. If the distribution Drest can model diverse users in population then this procedure can be used to compare different recourse methods.
cost-based metric that directly captures user satisfaction and is computed using each user's simulated cost function C We say that user is satisfied by recourse set if the best option in that set achieves sufficiently low cost under C# Formally, given a set of users and the recourse sets (Sulueu provided to them, we define the fraction of users satisfied at satisfiability threshold as:
Proposed Metrics FS@k & and Coverage: We introduce
FS@ hueu)
E 1(MinCost((s S.iCi) < <}} WEL
In reality, & can vary from user to user, we keep fixed across users in our experiments because the goal of any method is to find low-cost recourses regardless of k. In deployment scenarios, reasonable values of can be estimated by doing a user survey. addition to FS@ k. we also mea- sure Population Average Cost (PAC), which is defined as PAC _ Eneu MinCost(s,, S. C Another important measure the Coverage (Cov) which the fraction of users which the course method can provide at least one actionable recourse (Rawal & Lakkaraju, 2020), defined as Cou (Su).eu)= FS@x [24] Eueu [MinCost(ss Su. Sy: C < oo}.
EXPERIMENTS
4.1 EXPERIMENTAL SETUP
Dataset: We use the which are available under Open Data Commons PDDL license. The Adult- adult-Income dataset is based on the 1994 US Census data and contains 12 features. The model has predict whether an individ- ual's income is over $50, 000. COMPAS contains 7 features and was collected by ProPublica and contains information about the criminal history of defendants for analyzing recidivism. The model needs to decide bail based on predicting which applicants will recidivate in the next two years. These datasets are anonymized to prevent privacy. We preprocess both datasets based on previous anal- ysis where categorical features are binarized (Pawelezyk et al., 2021).² Our black- box model is an Multi-Layer Perceptron with 2-layers. Please refer to Appendix Tables 9 and 10 for experiments with logistic regression and Appendix A. and Table 5 for further experimental details.
(Dua Graff, 2017) and COMPAS (Larson al., 2016) datasets
We compare our methods COLS and P-COLS with DICE (Mothilal et al., 2020), FACE- Knn and FACE-Epsilon (Poyiadzi et al., 2020), and Actionable Recourse (Ustun et al., 2019). Im- portantly, control for compute across methods by restricting the number of forward passes to the black-box model, which are needed to decide a counterfactual produces the desired class. For most big models, this is the rate-nini step for each method. We ran our experiments local
Baselines:
The code for the Actionable Recourse method (Ustun al., 2019) requires binary categorical variables.

---

Under review as a conference paper at ICLR 2023
Table 4: Fairness analysis of recourse meth- ods Gender based subgroups. DIR: Dis- parate Impact Ratio; M: Male, F: Female.
Table 2: Ablation results with Search algorithms trained on different objectives.
Search Alg.
Objective
Cost Metries
Distance Metrics
Method
Geuder
Fs@1
Cor
DIRES
DiR-Cor
F8
PAC())
Cov
Div
Prox
Spars
Sparsity
29:0
06.2
DICE
15.6
LS
Diversity
Preximity
9.7
0.0
2.393
1.275
27.0
7.6
53.3
42.1
50.8
67.5
55.0
35.6
Face- Eps
18.8
12.5
22.1
24.7
1.504
1.118
LS COLS
EMC
EMC
49.8
68.8
0.391
0.597
72.6
59.1
37.8
27.1
77.5
73.3
67.5
73.5
Face-Kon
M
21.5
20.9
32.3
36.3
0.719
0.89
Table 3: Percentage of times each method was preferred by human annotators (Fleiss kappa=0.74 74 and 1e-4).
Act. Recours
53.8
47.4
56.3
58.7
0.581
0.959
Random
34.6
0.859
No Preference
Actionable Recourse
Ours
COLS
72.7
72.3
76.2
75.6
0.994
0.992
18%
25%
$7 %
P-COLS
M
76.8
76.5
80.2
80.2
1.004
1.0
server using single Nvidia 1080 Ti GPU. We set a fixed budget of 5000 model queries, set size |S| 10, and number of cost function sample M = 1000 for all methods. For a description of the objective function and other details of these baselines refer to Appendix B.1.1, B.2.3.
For our main experiments, we set Dirain and Diest to our most general dis- tribution mis as it is able to generate samples that are diverse and captures a wide variety of user FPs. This is analogous to supervised learning where train and test data comes from the same distri- bution. Note that, in contrast to past works (see $5), the cost samples {C used during training to evaluate EMC are different from C# which is used for evaluation. For completeness, in Section 4.2 Q5, and Appendix A.2 Q5, Q6, we provide additional results in cases where Dtraen and Drest different to show that our method is robust to choices of these distributions.
Evaluation Details:
Distance Based Recourse Metrics: To compare with past work, we evaluate meth- ods distance-based metries like feature diversity, proximity, sparsity, and validity that lie between [0, 1] with higher values being better. We report the average of these metrics, in percentage across all users. For single user, Proximity is defined as pror(a, S)
[St D.S (a), where S; is a counterfactual. Sparsity (Mothilal et al., T E E)=l (ay Feature diversity (Mothilal Si
2020) is defined as spar(æ, (æx S) et al., 2020) is defined div(S)= = Σ Σ j==+1 dist(S,, Sy), where 2 is the number of terms in the double summation. Validity is defined as vY) [unique &, [())=+111
S
4.2 RESEARCH QUESTIONS
Q1. Which Recourse Method Satisfies the Most Users?
In this experiment, we compare different recourse methods our cost-based evaluation framework and distance-based metrics. We report the average performance over five random seeds in Table 1. We observe that COLS and P-COLS, that optimize for EMC, achieve 22.64% and 25. 25.89% higher user satisfaction while covering 19.28% and 22.42% more users compared to the strongest baseline on Adult-Inconne and COMPAS, respectively. Meanwhile, other methods that optimize for a com- bination of distance- based metrics, perform worse on user cost-based metrics that directly model user satisfaction. Interestingly, we find that COLS and P-COLS solutions exhibit very high feature diversity, proximity, and sparsity. This implies that (1) the Diii distribution is generating cost functions that model diverse FPs and COLS along with EMC allows us to obtain the highest diversity even compared to other methods that directly optimize for it, and (2) proximity, sparsity, and diver- sity emerge as necessary metrics even under our cost-based evaluation framework but they are not sufficient satisfy users with preferences shown by other methods performance cost-metrics.
Q2. Is the Performance Improved by the COLS Optimization Method or the EMC Objective?
We perform an ablation study understand the impact of COLS optimization method and the EMC objective. To do so, we run a basic local search (LS) to optimize objectives used by other methods like feature diversity, proximity, and sparsity along with validity. We use basic local search because
7

---

Under review as a conference paper at ICLR 2023
there are no simple and efficient way to guarantee reductions in the diversity objective by swapping out single elements from the solution set that is required for using COLS (see Appendix B.1). To quantify the usefulness of COLS, we also optimize EMC using a basic local search.
The results in Table 2 suggest that optimizing for distance-metrice is sub-optimal. For proximity, sparsity, and feature diversity objectives, the FS score and coverage are very low, while they perform well on their respective metrics. The low FS score for distance metrics is expected as they ignore user preferences and hence can edit features that are not preferred making the generated recourses infeasible under the user's ' cost function. We find that EMC with LS outperforms all distance ob- jectives not only on FS, PAC but also proximity, and sparsity suggesting that the EMC is better objective. Meanwhile, the 19% difference in the performance of EMC with LS and COLS can be attributed to our cost optimization ($3.3) that allows COLS to efficiently search the solution space.
Q3. Do Recourse Methods Provide Fair Solutions Across Subgroups?
Next, We assess if the recourse methods provide equitable solutions across subgroups based on demographic features like Gender and Race. This is important because we want to ensure that recourse methods are not further inducing bias towards any particular group because directly affects the life of users. We adapt existing faimess metries for disparate impact across population subgroups (Feldman et al., 2015) for the recourse outcomes we study, which we denote by the Disparate Impact Ratio (DIR). Given a metric M. DIR is ratio between metric scores across two subgroups. DIR-M = M(S=I)/MMS-D) We use either Cov or @S@ as M. Under the DIR metric, the maximum fairness score that can be achieved is 1, though this might not be achievable depending on the black-box model. We run experiments on the Adult-Income dataset, with a budget of 5000 model queries and [S] 10.
We present the gender and race based subgroup results in Table 4 and Appendix Table 6 respectively. We observe that methods are typically more fair than baselines both Gender and Race- based subgroups while providing recourse to a larger fracctin of people in both subgroups. In particular, we find that our method achieves score very close to 1 on DIR-FS and DIR-Cov implying a very high degree of fairness. We attribute the fairness of our method to (1) the fact that our method does not depend on the data distribution, and (2) the use of diverse cost functions to generate recourse. Condition (2) is important since there are other individualized methods that do not rely on the data distribution, such as Face, which can generate less fair solutions than COLS.
Q4. Which Recourse Method Do Humans Prefer?
Next, we are interested in whether humans would consider recourses to be reasonable for our synthetic users. We designed small study where we provided human annotators with state vectors 8, and the sampled FP scores P.. for 100 users from the Adult-Income dataset (see Appendix A. 1.4 for details). We presented the recourse generated by COLS and Actionable Recourse (strongest baseline) to the annotators while anonymizing each method's 's name and asked them two questions: (1) Acting if they were the user with the provided preferences and state vector, which recourse would they prefer to adopt? (2) Does the recourse generated by each method seem reasonable to them? We collect three annotations for each sample and take majority vote for each response; allow for users to indicate "no preference" between the two proposed recourses, and if there was tie in annotation we record the majority vote as "no preference." We found that our method was preferred 57% % of the time, while AR was preferred only 25% of the time, difference of 32% (+/- 16 points variance, Fleiss' kappa=0.74 74, and p=le-4). Furthermore, human annotators found 60% of the recourses generated by COLS to be reasonable as compared to 33% for AR, 27% difference with le-4. This study shows that our method is preferred by humans over the baseline.
Q5. Robustness to Distribution Shifts And Other Research Questions
In this experiment, we test our evaluation framework's robustness in cases where the train and test distributions. Derain and Drest are different. In Appendix Figure 2, the top-left and bottom-right corners shows cases where Dtrain = Din while the users' evaluation cost functions C# are drawn from Drest = Dper (and vice versa). This is complete distribution shift and our method performs equally well for these cases demonstrating that our method is robust to distribution shift during test time. For full experimental design and conclusions please refer to Appendix Section A.2 and Figures 2 and 3. We also provide several additional research questions in the Appendix A.2, which we summarize here: (1) We make use of larger compute budget to scale up the performance (Fig-
8

---

Under review as a conference paper at ICLR 2023
ure 4); (2) The recourse sets provide high quality solutions to users using as few as 3 counterfactuals (Figure 5) (3) We can achieve high user satisfaction with as few as 20 Monte Carlo samples, rather than 1000 (Figure 6); (4) Our method works for other classification models as well (Table 10); and (5) We present the computational complexity and runtimes in Appendix A.1.2. We also show some qualitative examples of recourses provided by method in Table 7.
RELATED WORK
Here, distinguish our approach based our recourse objectives, optimizer, and evaluation. We point readers to Venkatasubramanian & Alfano (2020) for a philosophical basis for algorithmic recourse and to Karimi et al. (2020b) for a comprehensive survey of the existing recourse methods.
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 primarily seek recourses that are close to the original data point. In DICE, Mothilal et al. (2020) provide users with set of counterfactuals while trading off between proximity and feature diversity. A second category of methods uses other heuristics based on the data distribution (Aguilar-Palacios et al., 2020; Gomez et al., 2020) to come up with coun- terfactuals. FACE constructs graph from the given data and then tries to find a high-density path between points in order to generate counterfactuals (Poyiadzi et al., 2020). Lastly, the works closest to ours are the cost-based objectives, which capture feasibility in terms of the cost of recourse: (I) Cui et al. (2015) define a cost function specifically for tree-based classifiers, which compares the different paths that two data points follow in tree to obtain dassiffer-dependeer measure of cost. (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.
Objectives:
(3) Ustun 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 global cost function from pairwise compar- isons of features that are drawn from simulated users. However, they take a different approach to the recourse generation problem, which is to find list of rules that can apply to any user to obtain a recourse, rather than specially generating recourses for each user as in this work. Importantly, all of these works assume there a known and single cost function that is shared by all users.
Several recourse methods uses gradient-based optimization to generate counterfac- tuals close to a user's data point (Wachter et al., 2017; Mothilal et al., 2020). Some recent approaches use tree-based techniques (Rawal & Lakkaraju, 2020; von Kügelgen et al., 2020; Kanamori et al., 2020) or kernel-based methods (Dandl et al., 2020; Gomez et al., 2020; Ramon et al., 2020), while others employ some heuristic (Poyiadzi et al., 2020; aguilar-Palacios et al., 2020) to generate coun- terfactuals. A few works use autoencoders to generate recourses (Pawelczyk et al., 2020; Joshi et al., 2019), while Karimi al. (2020a) and Ustun et al. (2019) utilize SAT and ILP solvers, respectively.
Optimization:
Besides ensuring that recourses are classified as the desired outcome by a model (valid- ity), the most prominent approaches to evaluate recourses rely on sattance-bssed metries. In DICE, Mothilal et al. (2020) evaluate recourses according to their proximity, sparsity, and feature diver- sity. Mcanwhile, several works directly consider the cost of the recourses, using a single known cost function as a metric, meaning that all users share the same cost function. In contrast, Rawal & Lakkaraju (2020) estimate a cost function from simulated pairwise feature comparisons. For all these method, a single cost function is used for both recourse generation and evaluation, i.e. the so- lutions are optimized and tested on the same cost function (Cui et al., 2015; Karimi et al., 2020e;d; Rawal & Lakkaraju, 2020). In contrast, we evaluate recourse methods by simulating user-specific cost functions that can vary greatly across users to capture their preference.
Evaluation:
6 DISCUSSION AND CONCLUSION
Our novel framework INSPIRE provides a way to incorporate the individuality of the user in the recourse generation and evaluation process. INSPIRE lays a foundation for the future works to build more complex distributions to better represent the population by designing non-linear transition costs or modifying the COLS procedure to account for the causal relationships between features while accounting for individual user preferences. We show that method achieves much higher rates of user satisfaction than comparable baselines and observe that diversity, proximity, and spar- sity emerge important metrics even in framework but are not sufficient for user satisfaction.

---

Under review as a conference paper at ICLR 2023
ETHICS STATEMENT
We hope that our recourse method is adopted by institutions seeking to provide reasonable paths users for achieving more favorable outcomes under the decisions of black-box machine learning models or other inscrutable models. We see this as a "robust good," similar to past commentators Venkatasubramanian Alfano (2020). Below, we comment on few other ethical aspects of the algorithmic recourse problem.
First, we suggest that fairness is an important value that recourse methods should always be evalu- ated along, but we note that evaluations will depend heavily on the model, training algorithm, and training data. For instance, a sufficiently biased model might not even allow for suitable recourses for certain subgroups. As a result, any recourse method will fail to identify an equitable set of solutions for the population. That said, recourse methods can still be designed to be more or less fair. This much is evident from 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 the fairness of the model, training algorithm, training data, and recourse algorithm. Until then, risk blaming the recourse algorithm for the bias of a model, or vice versa.
Additionally, there possible dual-use risks from developing stronger recourse methods. For in- stance, malicious actors may use recourse methods when developing models in order to exclude certain groups from having available recourse, which is essentially a reversal of the objective of training models for which recourse is guaranteed (Ross et al., 2021). We view this use case as gen- erally unlikely, but pernicious outcomes are possible. We also note that these kinds of outcomes may be difficuul to detect, and actors may make bad-faith arguments about the fairness of their de- ployed models based on other notions of fairness (like whether or not model has access to protected demographic features) that distract from underlying problem in the fairness of recourses.
REPRODUCIBILITY STATEMENT
To encourage reproducibility, provide source code, including all the data pre-processing, model training, recourse generation, and evaluation metric scripts as supplementary material. The details about the datasets and the pre-processing are provided in Appendix A.1.1. We also provide clear and concise Algorithms 4, 2, for our cost sampling procedures and our optimization method COLS in Algorithm 1. Additionally,
also provide formal proof of the Theorem 3.1 stated in the main paper in Appendix B.2.2 along with the constructive procedure for the proof provided in Algorithm
REFERENCES
Carlos Aguilar-Palacion Sergio Muñoz-Romero, and José Luis Rojo-álvarez. Cold-start promo- tional sales forecasting through gradient doosted-based contrastive explanations. IEEE Access, 2020.
Ifcoma Ajunwa, Sorelle Friedler, Carlos E Scheidegger, and Suresh Venkatasubramaniia.. Hiring by algorithm: Predicting and preventing disparate impact. Available SSRN, 2016.
Furui Cheng, Yao Ming, and Huamin Qu. Dece: Decision explorer with counterfactual explanations for machine learning models. IEEE Transactions Visualization and Computer Graphics, 27:
1438-1444 1444, 2021.
Alexandra Chouldechova, Diana Sonavides-Praddee Oleksandr Fialko, and Rhema Vaithianathan. A case study of algorithm-assiste decision making child maltreatment hotline screening deci- sions. In Conference Fairness, Accountability and Transparency, pp. 134-148, 2018.
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, 188, 2015.
Susanne Dandl, Christoph Molnar, Martin Binder, and Bernd Bischl. Multi-objective counterfactual explanations. In Thomas Bäck, Mike Preuss, André Deutz, Hao Wang, Carola Doem, Michael
10

---

Under review as a conference paper at ICLR 2023
Emmerich, and Heike Trautmann (eds.). Parallel Problem Solving from Nature PPSN XVI, pp- Cham, 2020. Springer International Publishing. ISBN 978-3-030-58112-1.
Amit Dhurandhar, Pin-Yu Yu 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. URL https::/arcciive.. aarchive.. res.uci.oom edw/ml/ dat asets adult.
Michael Feldman, Sorelle A. Friedler, John Moeller, C. 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. 531-535, 2020.
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 on Safe ML, abs/1907 1901,09615, 2019.
Kentaro Kanamori, Takuya Takagi, Ken Kobayashi, and Hiroki Arimura. Dace: Distribution-awwn awware counterfactual explanation by mixed-integer linear optimization. In Christian Bessiere (cd.), Pro- ceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI-20, pp. 2855-2865 International Joint Conferences Artificial Intelligence Organization, 7 2020. doi: 10.24 00.24966/ijccii222207355 URL https: https::/t///tttt http::///dooooooo htt.///ooooooooooo//////../ //./ 21......./..ee.. 20200395.
Main track.
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/ 1190, 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 www.thttp:/tm //ts://aaaeee /ttp/aaxvvvvoo/ org/ ab//a/sss/0000 04050.
Amir-Hossein Karimi, Bernhard Schölkopf, and Isabel Valera. Algorithmic recourse: from counter- factual explanations interventions. FAccT, 2020c.
Karimi, Julius von Kügelgen, Bernhard Schölkopf, and Isabel Valera. Algorithmic recourse under imperfect causal knowledge: probabilistic approach. Advances in Neural Infor- mation Processing Systems, 2020d.
A. Kulesza and B. Taskar. Determinantal point processes for machine learning. Found. Trends Mach. Learn., 5:123-286, 2012.
Jeff Larson, Surya Mattu, Lauren 2016.
Kirchner,
and
Julia
Angwin.
Hans Mittleman. Mixed integer linear programming benchmarks (miplib 2010). http://plato.
asu. edu/ http://tpmmmmppccp// htm1, 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 Pawelczyk, Klaus Broelemann, and Gjergji Kasneci. Learning aggess-g counterfac- tual explanations for tabular data. In WwW. pp. 3126-3132, New York, NY, USA, 2020. Associ- ation for Computing Machinery. ISBN 978 9781450370233, doi: 10. 10.1145/33664233338000 URL https: //o.i/d///// http//di.org//////// wwwg///..11//3666..6 3380087

---

Under review as a conference paper at ICLR 2023
Martin Pawelczyk, Sascha Bielawski, 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: /opnoeveeevveeeeeeeeeeeeeee ew net/ forum? ?id= vDi KaNNNx.
Mare Pirlot. General local search methods. European Journal of Operational Research, 92(3):493- 511, 1996. ISSN 0377-2217. doi: http://d.....g/11....01001777711 / www.www.... 8c encedi rect com/ science/
URL https:
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. In 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- Rodrios-, Tijl De Bie, and Peter Flach. Face: Feasible and actionable counterfactual explanations. In Proceedings of the AAAI/ACM Conference AI, Ethics, and Society, AIES '20, pp. 3443350, New York, NY, USA, 2020. Association for Computing Machinery. ISBN 978 4503311000 doi: (0.11455/37552773335550 URL https:
100. 19...114555 1145/3375622 3375850.
Yanou Ramon, David Martens, Foster Provost, and Theodoros Evgeniou. Counterfactual explana- tion algorithms for behavioral and textual data. Advances in Duta 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. In 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: /ttpps:/prrcceeennggss... neurips. ccc/appe/20200 file/ l 77e 473 4
Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. Anchors: High-precision model-agnostic explanations. In AAAI Conference on Artificial Intelligence, 2018.
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.
Naeem Siddiqi. Credit Risk Scorecards: Developing and Implementing Intelligent Credit Scoring, volume 3. John Wiley & Sons, 2012.
Berk Ustun, Alexander Spangher, and Yang Liu. Actionable recourse in linear classification. In Pro- ceedings of the Conference on Fairness, Accountability, and Transparency, FAT* '19, pp. 10-19, New York. NY, USA, 2019. Association for Computing Machinery, ISBN 978 1450361255 doi: 00.1145//287550.32876666 URL https: doi. /ttg/...... 1145/ 32873288775 3287566.
Suresh Venkatasubramanian 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
hwwpp//cceee...eeeeeeeeeee...a.e wwwrropaa.eeeeeo fLLee//attt-ppotettiio---feeeeee wwwngehaanngeeeeeeeeeeeeeeeeeeee pdf.
eu/comm commi ss on/ s testee//e
Julius von Kügelgen, Amir-Hossein Karimi, Umang Bhatt, Isabel Valera, Adrian Weller, and Bern- hard Schölkopf. On the faimess of causal algorithmic recourse. NeurIPS AFCI Workshop, 2020.
12

---

Under review as a conference paper at ICLR 2023
Table 5:
Table containing data statistics and black- box model details. The binary version of the datasets take from (Pawelezyk al., 2021) whereas the non-binary version are taken from (Mothilal al., 2020).
Adult Income Binary
COMPAS Binary
Adult Income
COMPAS
# Continuous features
3
2
3
Categorical features
Undesired class
< 50k
Will Recidivate
50k
Will Recidivate Won't It Recidivate
Desired cluss
> 50k
Won't 't Recidivate
>- 50k
Trate/val/test
20088/2338/749
1415/229/491 ANN(2, 20) 69%
16172/15697748
1705/405/444
Model Type
ANN(2. 20)
ANN(2, 20)
ANN(2. 20)
Val Accuracy
82%
81%
61%
Sandra Wachter, B. Mittelstadt, and Chris Russell. Counterfactual explanations without opening the black box: Automated decisions and the gdpr. Cybersecurity. 2017.
David S. Watson, Limor Gultchin, Ankur Taly, and Luciano Floridi. Local explanations via necessity and sufficiency: unifying theory and practice. In Cassio de Campos and Marloes H. Maathuis (eds.). Proceedings of the Thirtt-Seventh Conference on Uncertainty in Artificial Intelligence, volume 161 of Proceedings of Machine Learning Research, pp. 1382-1392. PMLR, 27-30 Jul 2021. URL https: httpsss//ooccceeeeeeeeo nggs, mwr.press///pp..m.m.m..m.. panees/vl6t wwt.ttottttlnla htmml.
A APPENDIX FOR INSPIRE: A FRAMEWORK FOR INTEGRATING INDIVIDUAL USER PREFERENCES IN RECOURSE
A.1 EXPERIMENTAL SETUP
A.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, show results on the binarized version (Table 1) as an important baseline, Actionable Recourse (Ustun et al., 2019), operates with binary categorical features. The data statistics for all the datasets can be found in Table 5. 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 be incorporated into the methods by providing a 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 are shown in Table 5. The test set which is used in the counterfactual generation experiments only contains users which are classified to the undesired class by the trained black-box model. Note that our frameworks operate with any type of model, the only requirement is the ability to query the model for outcome given a user's 's state vector.
A.1.2 COMPUTATIONAL COMPLEXITY:
COLS is local search-based method and runs for O ( iterations for each recourse set, where B is the budget (see section 5.1 Baselines). The complexity of the cost op- timization step in COLS is O[SS)2 .)) per iteration. Values of |.S] and M as low as 3 and 10 respectively work well in practice (see Appendix B.2 and Figure 5, 6). Finally for the current im- plementation the wall clock time on the adult dataset for each user with |S| 10, M 100, B = 5000 setting is COLS = 20s, Random = 7.5s, DICE = 7.5s, AR = 11s, Face-knn = 7s, Face-Eps = 6s (can be parallelized across users). Cost function samples can be pre-computed once and saved for all experiments, this typically takes a few minutes (< min) across all users.
generate the
'The binary datasets can be downloaded from http:://gihuh.com/aaaarrrroooooe hinary data can be found https//giihuu.ccm//meettttm/////
whereas the non-
13

---

Under review as a conference paper at ICLR 2023
Linear vs Percentile Cost Robustness
Monte Carlo a-weight
100
1.0
Methods Robustness Distribution Shifts
100
0.8
COLS
99
0.6
0.4
Binned
97
20
96-
95
0.0
0.00
0.05
0.10
0.15
0.20
0.25
0.30
50
Distribution Shift
0.0
0.2
0.4
0.6
0.8
1.0
User a-weight
Figure 3: this plot we show the fraction of users Figure 2: This figure shows the performance of the satisfied vs the distance between the train and test method on FS@ when recourses are generated with distributions. The results demonstrate that as the Monte Carlo cost samples from a distribution with distance increases the performance drops bit and a-weight varying between 0 and 1, where the user then plateaus, which means that the method ro- costs follow different a-weight values varying he- bust to this kind of distribution shift. Please refer to tween O, 1. Performance robust misspecifica- Section A.2 for more details. tion a. Refer to Section A.2 for more details.
A.1.3 RECOURSE GENERATION AND EVALUATION PIPELINE
To approximate the expectation in equation 3, our algorithm samples a set of random cost functions (C.). Dtrain. which are used the generation time optimize for the user's hidden cost function. In the generation phase, we use Equation 4 as our objective. Note that, this objective promotes that the generated counterfactual set contains least one good counterfactual for each of the cost samples, hence this set satisfies a large variety of samples from Dirain. This is achieved via minimizing the mean of the minimum cost incurred for each of the Monte Carlo samples (Robert & Casella, 2010). Equivalently, the objective is minimized by set of counterfactuals S where for each cost function there exists an element in S which incurs the least possible cost. In practice the size of set S is restricted, hence we may not achieve the absolute minimum cost but the objective tries to ensure that the counterfactuals which belong to the set have a low cost at least with respect to one Monte Carlo cost sample. The generation phase outputs a set of counterfactuals S which is to be provided to the users as recourse options. Given this set S., in the evaluation phase, we use the users simulated cost functions which are hidden in the generation phase, to compute the cost incurred by the user MinCost( su, S;Cf)) and calculate the metrics defined in the Section 4.1.
1.1.4 DETAILS OF HUMAN EVALUATION
For our human evaluation experiments, we had three undergraduate research assistants with a back- ground in computer science. They were provided with set of instructions how to interpret and perform the task. Specifically, in virtual meetings, we provided them with an overview of the dataset along with the feature descriptions, description of the task, and an overview of the recourse generation problem. Before testing, we conducted a small understanding quiz including example problems, and we corrected any misunderstandings of the study procedure. For each data point, they were asked to assume that they were hypothetical user with the given state vector and pref- erence scores in the sample and then were provided with the recourses generated by our method and Actionable Recourse Ustun et al. (2019) (in a blind format with randomized ordering). In total, we collected three annotations each for 100 samples from the Adult-Income dataset. We don't see any participant risks from doing the study, the participant were asked to assume the identity of hypothetical user and asked to guess which recourse are better. The hourly rate for for the annota- tors 12.5$/hours and it took around 2.5 hours for the whole study which leads to total cost of 93.75S. The instructions provided to the participants of the human study are shown in Figure 7 and screenshot of how the study was conducted is provided in Figure 8.
14

---

Under review as a conference paper at ICLR 2023
A.2
ADDITIONAL RESEARCH QUESTIONS
Q5. Robustness to Misspecification in population's true and proposed cost function distribu- tion?
Design: Our Dmix distribution samples cost by taking an a-weighted combination of linear and percentile costs. These two cost have different underlying assumptions about the how users view the cost of transition between the states. We want to test the robustness of our method in terms of misspecification in users disposition to these types of cost. We perform robustness analysis where the users cost function has different a mixing weight compared to the Monte Carlo samples we use to optimize for EMC. This creates a distribution shift in the user cost function distribution (Drest) and the Monte Carlo sampling distribution (Dtrain) used in EMC. We vary the user and Monte Carlo distributions a-weights within the range of 0 to in steps of 0.2. At the extremes values of In the case when monte carlo a weight is O and user a weight is I then Drrain = Pere and Dtest- = Diins simlarly for the other case we get Dtrain Disn and Diest = D Dpere. Please note that the distribution Diin and Dpere have completely different underlying principles and are two completely different distributions. Hence, the corners of the heatmap represent drastic distribution shifts.
0, 1, the shifts are very drastic the underlying distribution changes completely.
Results: In Figure 2, we show a heatmap plot to which demonstrates the robustness of our method. The color of the block corresponding Monte Carlo alpha, ame and the users alpha, Quser y represents the fraction of users that were satisfied when Ome = I and Quser = y. This means that if the user thought of costs only in terms of Linear step involved but the recourse method used samples with only percentile based cost, still the recourse set can satisfy almost the same number of users. In Figure 3, the corners correspond to these extreme cases described above, the user satisfaction for the top left corner (Dtrain = Dpere and Drest = Dia.) is similar to the bottom left corner (Dtrain Diin and Drest Dii.). Similarly things happen for the opposite case which is denoted by the top-right (Dtrasn = Dpere and Diest = Dpere) and bottom-right (Dtrain = Dinn and Drest- Dpere) corners. This means that even when a complete distribution shift occurs the performance user satisfaction remains similar. This can be attributed to the hierarchical step for user preference sampling in the procedure because the preferences values can be arbitrary and they scale the raw percentile and linear cost hence the distribution designed this way to model extremely diverse types of transition costs.
This means that our methods is robust to misspecification in the train and test distributions. 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. Are Solutions Robust to Misspecified Cost Distributions?
Design: In our 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 or education level rather than their work hours or marital status. Given the possibility of this kind of distribution shift in feature preferences, we want to measure how robust our method is to distribution shift between our sampling distribution and the actual cost distribution followed by users.
In this experiment, we test a case of this kind of distribution shift over cost functions. For users in the Adult-Income data, we generate recourse sets using Monte Carlo samples from our standard dis- tribution Diiix (Algorithm 4). 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 sub- set corresponds to a binary vector concentration representing a user having specific preferences for some features over others (see Sec. 3.1 and Alg. 4). Since having different editable features induces a different distribution over cost functions, we obtain a measure of distribution shift for each of the 500 concentration vectors by taking 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 least likely to be satisfied by the recourse set.
15

---

Under review as a conference paper at ICLR 2023
User Satisfaction vs Counterfactuals
User Satisfaction black-box access
80
FK
AR
60
R
60-
FS@1
COLS
F5@1
P-COLS
0-
0-
10 20 30
500
1000
2000
3000
5000
10000
Number of Counterfactuals [S]
Budget
Figure 5: Figure showing the performance differ- ent recourse methods as the the number of counter- facuals be generated is increased. These the average number across 5 different runs along with standard deviation error bars. We see that there a monotonic increase in the fraction of users satis- fied the size of the set increases. We also observe that most of the performance small set size. Please refer Section A.2 for more details.
Figure 4: Figure showing the performance of dif- Budget is increased.
ferent recourse methods These are the average number across 5 different runs along with the standard deviation error hars. For some methods the standard deviation is very low hence visible as hars in the plot. It be seen that as the budget increases the performance COLS and P-COLS increases. Please refer to Sec- tion A.2 for more details.
be obtained with
Satisfaction
Sample
Table 6: Fairness analysis of recourse methods for subgroups with respect to Race. DIR: Disparate Impact Ratio; W: White, NW: Non White (Section 4.2).
F5
Method
Race
FS@1
Cov
DIR-FS
DIR-Cov
NW
0.0
0.0
DICE
10.4
Face-Eps
NW
7.7
12.7
2.312
2.047
1
5
10 20
30
100 200 30u s00 1000
26.0
Num MC Samples
NW
12.7
25.4
Face-Kun
2.228
1.425
28.3
36.2
Figure 6: Figure showing the performance of the COLS method the number of Monte Carlo samples increase. These the average number across different runs along with standard deviation error bars. There a steep increase and then the performance sat- urates. This implies that in practice not need large number of samples to con- verge to the higher user satisfaction. Refer to Section A.2 for more details.
NW
46.5
54.9
Act. Recourse
1.101
1.056
W
51.2
58.0
NW
4.9
28.9
Random
7.7
31.1
NW
67.6
71.1
COLS
73.6
76.9
1.089
1.082
do
P-COLS
NW
72.5
74.6
1.07
1.092
77.6
81.5
In other words, the likelihood that a user is satisfied depends on the minimum distance between their concentration vector and its nearest neighbor in the cost samples used at recourse generation time. Therefore, when the minimum distance increases, there is a greater distribution shift between the user's cost functions and those obtained from Dyniz Finally, we measure how many users are satisfied for a given degree of distribution shift.
Results: Figure 3, we show binned plot of FS@1 against our measure of distribution shift. We observe that as the distance between the distributions increases, the fraction of users satisfied decreases slightly and then plateaus. Even at the maximum distance we obtain, performance has only dropped about 3 points. This implics that 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 method (1) assumes random feature preferences which subsumes these skewed preferences and (2) provides multiple recourse options, each of which can cater to different kinds of preferences. As result, we achieve good covering of the cost function space (see experiments with respect to varying recourse set size and number of sampled cost functions in the Appendix A.2).
Q7. Does Method Performance Scale with Available Compute?
16

---

Under review as a conference paper at ICLR 2023
teek as owe:
Instruction for Human Evalustion
Asot fosture
numbers ronging
belvwen (end
that you how feature (highar econe for fiature os compare leature maans you more willing change fasure X than You should protend you ane fiis incivduaa with hoos pratererces over featre
change that
Bannh you your telp
credit This application getk rejected and the credit card prayy providos you with two oct ons that you could take orter to get your agp loaliin spprowed. Thons actixes oh possu of your dhearudee rutica on permar, vench mearr they charge gei the
Geou:: Assume
the credil agency lodka at (we provide scample "Tattune
You Should Provide:
your have these proferences) Basedd on these piur pirformeioos your took to evdk une vi of two provited astion you would profor to takeo in order to char the docisiion made by the arciit agenty.
glve
Wiite z.b cor indicolo wheth yourtlle
take ditle
should pertend
a. Actice is buteer than Action
Actice better tham Actionn
equalit good
beshvo)
bosed diesll relevant the oviluut on we sew purformeng tu lans; aocheed lou wert to mnsama sciichuu of th provided scilo tu the sganny in prefereet by the user given their preturence. for comp complettneess and better underttantigg am prosiding featuree by
with
the incoms inchiis od shrow 50c5yyan
soluzan B resoonabir?? (ymiina)
dome sot of ficouuros These featuris ios and their valuos
Exemple:
An scxmpis can thund here in the sheed linkl whene los has featurm names folowod
the greforence scores user. next two daathe
Age: Age of and vilual jour aloous
Workchea: deasime addiicud aod wore thivorte News frivate ocanbuutio (Cateportcu)
hore illed the
which masorablely We have three questoon
rightrwad columee
(Hamaan Proferena reno ls reasonadle le ment oned allow and on arrowar from can be enlorrd in the firs row of samplle and the comneporting oolumn..
martar-enn martar-asttuc In the indiicual cnd in Marmid or biccaaadde (Caagorr sad
eecopelive: Conpaation ype of intivecual Managemna Speccal or (Delepokoa))
race: whit or No--WWite (Cellgoriss)
tiss esamplo. Amorg the asttora and licat which and ccilaci theae actions have
nad fusture occupetion which followed mertall stotus
pie (Culngeeoe)))
Capttiigaies 2:1
Copttallowe 1.2
(sontruust)
follww ng proference order mar ttal stata capiai-boa cac Bal gain Actien A adit martal
daakus prodenonce scom on much highte then both capiti-ioss and gain
nathve-puurtyy Uld (lelll suf
musing changes
change
unvasamelle, can uevouoorable la you feel Fiee ktss nol worth
heatrre valuee
Figure 7: Instructions for Human Evaluation. Please refer to Section 1.1.4 for more details.
hanerosa
11
Marine
Mors
Mariae
Varted
Mariec
Figure Screenshots of how the human evaluation test was conducted. Please refer to Section 1.1.4 for details.
17

---

Under review as a conference paper at ICLR 2023
Table 7: 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 to 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 Education-Num but the changes suggested in the recourse requires three steps 7-8-9-10, 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.
Feature Name
State Vector
Editable Features
Preference scores
Recourses
Cost
Age
Education
Workelass
Private
10
No
No
(Capital Loss: 0 -
0.009
Martial Status
Married
No
Occupation
Other
Yes
0.055
Race
Relationship
White
No
(Occapation: Other Manager)
0.378
Gender
Male
No
Capital Gain
Capital Loss
0
Yes
0,944
Occapationn Other + Manager
Work Hours
Capital Loss:
0.387
Country
US
No
Age
Workelass Education Num
Private
No
Yes
0.537
(Capital Loss: O + 1)
0.071
Martial-Status
Married
Occupation
Other
No
(Capital Gain: 0 1)
Relationship
Non-Husband
No
0.106
Race
White
Gender
Female
No
(Education-Num: 7 10)
0,187
Capital Gain
0
Yes
0.078
Capital Loss
0
Yes
0.240
Work Hours
32
Yes
0.142
(# Work Hours: 32 - 70)
0.695
Country
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, good recourse method should be able to exploit these extra queries and use it to satisfy more users. We vary the allocated budget in the set (500, 1000, 2000, 3000, 5000, 10000} and report the FS 1. We run the experiment on a random subset of 100 users for 5 independent runs and then report the average performance with standard deviation-basee
error bars in Figure 4.
Results: In Figure 4, we can see that as the allocated budget increases the performance of the COLS and P-COLS increases and then saturates. This suggests that our method can exploit the additional black-box access to improve the performance. Other methods like AR and Face-Kmn also show performance improvement but method COLS and P-COLS consistently upper-bound their performance. Our method satisfies approximately 70 % of the user with a small budget of 500 and quickly starts to saturate around budget of 1000. This suggests that our methods are suitable even under tight budget constraints as they can achieve good performance rapidly. For example, in real-world scenario where the recourse method is deployed and has cater large population, in such cases there might be budget constraints imposed onto the method where achieving good quality solution quickly required. Lastly, for DICE and Random search the performance on the FS increase by very small margin and then stays constant as these methods are trying to optimize for different objectives which don't align well with user satisfaction as demonstrated in Section 4.2.
Q8. 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. a bigger set S. The question here is that can the methods effectively exploit this advantage and provide lower cost solution sets to the user such that the overall user satisfaction is improved. In this experiment
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 S in the set (1,2,3 3, 5, 10. 20, 30). We restrict the size of the set to maximum of 30 beyond a point 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
18

---

Under review as a conference paper at ICLR 2023
Table 8: Table comparing different recourse methods across various cost and distance metrics Non-Binary versions of the datasets (Section T.e numbers reported are averaged across different runs. Variance values have been as 89% of them were lower than 0.05, with the maximum being 0.86. FS@ I: Fraction of users satisfied at k = 1. PAC: Population Average Cost. Cov: Population Coverage. For all the metries higher is better except for PAC where lower is better.
Data
Method
Metries
Cost Metries
Distance Metries
FS@1 1
PAC(L)
Cov
Div
Prox
Spars
Val
DICE
6.28
1.45
27.01
53.01
57.02
47.80
86.20
Random
2.42
17.41
70.35
33.32
22.45
Adult-Income- NB
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 69.44
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
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 30. This is consistent with the intuition behind our methods (See Figure 1, sec- tion 3.2, A.1.3 for more details). It is fundamental property of our objective that as |S] increases towards M which 1000 in this case, then the quality of the solution set should increase and reach the best possible value that can be provided under the user's cost function. We note empirically that smaller set size |S| between to 10 enough in most practical cases to reach close to maximum performance. Additionally, even with |S| E 2, 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 3 options while still satisfying a large fraction of users. Additionally, we also see improvement in the case of AR and Face- Knn methods [S] increases. Note that Randoms Search's performance doesn't 't change as we increase the set size because the method doesn't it take local steps from the best set and samples random points from very large space, hence it is much harder end up with low-cost counterfactuals.
Q9. Does increase the number of Monte Carlo samples help with user satisfaction?
Design: In this experiment, we want to demonstrate the effect of increasing the number of Monte Carlo samples on the performance of our COLS method. We take a random subset of 100 users, budget of 5000, |S| 10. We vary the number of Monte Carlo samples (M) in the set 51 10, 20, 30, 100, 200, 300, 500, 1000} and compute the user satisfaction. We ran 5 different runs with different Monte Carlo samples and show the average FS@ I along with the standard devi- ation in the Figure 6.
Results: We observe that as the number of Monte Carlo samples increases, the performance of the method the FS@ 1 metric monotonically increases. This supports the intuition underlying our method (see Figure 1). That is, given a user with a cost function Cg as we get more and more samples from the cost distribution Dirain the probability of having cost sample similar to Cr in- creases and hence the fraction of satisfied users increase. It is important 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.
Q10. Qualitative examples of the recourses generated for some of the users.
In Table 7, show a few examples of users along with their state vector, their editable features, their preference scores along with the recourses provided to them and their cost.
Q11. Comparison of methods Non Binary Dataset?
19

---

Under review as a conference paper at ICLR 2023
Table 9: Table comparing different recourse methods various cost and distance metrics for black-bol model with different seed but belonging to same model family. numbers reported are averaged across 5 different runs.
Data
Method
Metrics
Cost Metrics
Distance Metrics
FS@1
PAC(L)
Cov
Div
Prox
Spars
Val
DICE
2.70
1.24
7.10
3.80
66.20
47.30
97.80
Eace-Eps
13.32
0.79
19.88
5,43
91.97
74.80
100.00
Face-Knn
21.78
0.83
34.13
8.67
88.68
71.43
100.00
Adult-Income
Act. Recourse
46.55
0.58
53.82
19.07
74.33
73.25
80.72
Random
5.71
1.42
28.24
48.93
55.10
39.30
78.73
COLS
75.12
0.36
77.40
25.43
81.00
77.70
P-COLS
75.76
0.38
79.14
25.54
81.84
78.38
95.10
DICE
0.90
0.88
1.50
12.50
63.90
30.70
99.30
Face-Eps
6.80
0.29
6.80
2.40
95,00
60.40
100.00
Face-Kun
6.80
0.29
6.80
2.40
94.90
60.30
100.00
COMPAS
Act. Recourse
56.24
0.45
58.48
9.72
80.12
73.62
39.10
Random
27.44
0.78
35.70
41.76
58.14
33.06
49.34
COLS
77.08
0.24
77.90
29.33
76.90
68.87
95.78
P-COLS
78.32
0.24
79.02
29.02
77.88
70.08
92.10
In Table 8, we show the results on the non-binary version of the dataset. We observe similar perfor- mance on and trends in these results as well. COLS and P-COLS performs the best in terms of user satisfaction.
Q12. Robustness to black-box model architecture families and randomness?
In this experiment we demonstrate the result of our model when we train the same ANN architecture with different random seed (Table 9) and when we change the model family logistic regression classifier (Table 10). These obtained results have similar trends and demonstrate the effectiveness and robustness of our methods COLS and P-COLS which consistently satisfy cover and satisfy more users with low average population costs. In Table 9, we show the results when we train another black-box model with different seed the effect of having different trained model from the same model family.
Q13. Additional results for different values of in FS@k In Table 11, we report the fraction of satisfied user metric FS@k for four different values of k E 1,2,3, These results an extension the results presented in Table 1.
B APPENDIX OBJECTIVE AND OPTIMIZATION
B.1 PROPOSED METHOD
B.I.I OTHER OBJECTIVES
To obtain feasible a counterfactual set, past works have used various objective terms. We list objec- tives below from methods we compare with.
1. DICE (Mothilal et al., 2020) optimizes for 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.
dpp diversity(S) det(K), whereK,,
dist(s,, 85)
Here, dist(s;, 85) 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, proz (x., S)
! dist(ær, (,, S.), where S, is counterfactual.
20

---

Under review as a conference paper at ICLR 2023
Tabbee 10: Table comparing different recourse methods various and distance metrics for logistic
regression black-box model. numbers reported are averaged across different runs.
Data
Method
Metrics
Cost Metrics
Distance Metrics
FS@1
PAC(L)
Cov
Div
Prox
Spars
Val
1.30
1.47
7.10
6.50
64.80
49.20
76.60
FE
2.82
0.99
5.46
9.44
83.08
65.90
100.00
FK
17.04
0.90
28.08
7.22
83.98
67.80
100.00
Adult-Income
AR
44.40
0.62
52.62
21.74
74.00
72.92
87.58
3.60
1.59
24.10
48.14
54.76
38,94
79.46
COLS
67.93
0.39
69.97
27.83
78.40
74.43
99.13
P-COLS
69.17
0.40
71.57
27.20
79.30
76.70
95.67
D
0.00
0.00
11.10
63.10
29.20
100.00
FE
0.16
6.30
3.60
95.00
60.50
100.00
FK
6.30
0.16
6.30
3.60
95.00
60.50
100.00
COMPAS
AR
74,32
0.31
74.32
15.66
80.98
74.26
53.66
R
28.76
0.77
36.96
43.22
56.22
32.00
82.10
COLS P-COLS
87,88
0.18
87.88
31.92
76.93
71.63
89,33
89.25
0.17
89.25
28.17
81.13
74.73
91.62
Table 11: Cost metries additional & values FS@k results presented the main Table
Method
Cost Metries
FS
FS@1
FS@2
FS@3
0.4
6.9
8.23
Face-Eps
7.32
15.23
22.57
22.6
Face-Knn
11.08
25.3
34,82
35
Adult-Income
Act. Recourse
28.03
49.93
56.78
56.85
Random
0.82
6.27
28.5
31.68
53.4
72.57
76.05
76.07
P-COLS
53.42
75.82
79.18
79.2
DICE
0.2
0.4
Face-Eps
10.4
12.2
12.2
12.2
Face-Knn
10.4
12.2
12.2
12.2
COMPAS
Act. Recourse
42.47
66.6
66.6
Random
7.85
29.95
39.2
COLS
73.07
82.23
82.23
P-COLS
74.33
83.73
83.73
83.73
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- perceeecettile shift is given by,
1- Q,(5, +a,)
cost(s + aa
Σ log 1 Q5(8,)
JEJA
where (.).) the cumulative distribution function s, in the target population, JA is the set of actionable features and a, is the action performed on the feature
B.2 OPTIMIZATION METHODS
Notation:
We assume that we have a dataset with features F {f1, fe. Each feature can either be continuous Fron C F or categorical Foat C F. Each continuous feature from takes values the range [r-min r-maa]] which we discretize to integer values. For continuous feature ft, define the range QiA) {k Z k E [rmmin sımar]} and for a categorical feature fr. define as (ff.) = (qf . ...,, Tá. ), where q.) are the states that feature f; can take. Features can either be mutable (FF"), conditionaly mutable (Fom), immutable (FF), according the real-world causal
21

---

Under review as a conference paper at ICLR 2023
Algorithm 2 Sampling procedure for Percentile Transition Costs
Input: State vector Optional: Feature Preference Scores p Percentile based Transition Cost functions C.
Output:
function PerCost(s,, s. None)
forall fi E F do
// 8: value of feature fi in 8.
p 5.. =
then
8,, =0
else
if fi is ordered then if Ja can only increase then
(getPercettile(a) getPercentile
Vr $5
C(Ji, 81,
Ar $5
4x 2 45
else if fi can only decrease then
get Percenttt))))))))) - get Percentile(r))
4A < 81
MA 88
0
Do
4y 58
else if Se can both increase or decrease then
getPerreettile(z)) - getPercenttle(s:))
Vr > 8 Vr = 8i
x1, (geteercettile(s)) - getPeeecet))e())
Vr 84
else if fi is unordered then C(fi, 8t,.) Uni
end
if p is not None then
C(fi, st..) + C(f (1 (1-)
return
end
processes that generate the data. Mutable features can transition from between any pair of states in Q(F); 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 immutable feature (Mothilal 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 an ordered feature that is conditionally mutable (can only increase).
B.2.1 HIERARCHICAL COST SAMPLING PROCEDURE
To optimize for EMC, we need plausible distribution which can model users' cost functions. We propose a hierarchical cost sampling distribution which provides samples that are 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 proportional to the change in feature's 's percentile associated with the change from an old feature value to new one. E.g., if user asked to increase the number of work hours from 40 70, then given the whole dataset, we can estimate the percentile of users working 40 and 70 hours week. The cost incurred is then propor- tional to the difference in these percentiles. The Linear cost for ordered features is proportional to the number of intermediate states user will have to go through while transitioning from their cur- rent state to the final state. E.g.. if user is asked to change their education level from High-school to Masters then there two steps involved in the process. First, they need to get Bachelors degree and then a Masters degree in which case, the user's ' cost proportional to 2 because of the two steps involved in the process.
22

---

Under review as a conference paper at ICLR 2023
Algorithm 3 Sampling procedure for Linear Transition Costs
State vector Optional: Feature Preference Scores p Linear change based Transition Cost functions C. function LinCost(s,, p None)
Input:
Output:
if pf 0 then
St. = oc C(J,,
else
if ft ordered then if fi can only increase then
[v y>s, Sg) Hy 1osth
4e 81
C(fi, 81,
24 $t
44 i8
else if Sa can only decrease then
Ky A92,)) (y v<
4a < 88
C(fi, s1,
4x 34
> 84
else if St can both increase or decrease then My AyscA v
Wx
C(fi, 81,))
4x 8t
My vc
else if fo is unordered then Uniform(0,1] 1)
C(fé, 81..) ((.)))...)
if p is not None then
C(f,, s). t C(fi,8 )
return C
end
Algorithm Sampling Cost Functions from Dmiz.
Input:
State vector s, Optional: Preferred features F,, feature preference scores p. cost-type mixing weight & Output: Preference scores and the cost functions C.
function sampleCost(s, = None, F, O.. None)
if F, is () then (anudoomSusse((Fnnnnaa
Fpp
if p is None then
concentration = if Fp else for f in F)
p Diriehle((coneentralinn)
if is None then a ~ Unifform(..)
C= O c
b Get means and varlance Ior costs,
((Lin) +- LinCost (,, ((f.) ft.
((Pere) +- PerCost(s, (f)) Fr. C(lin)
((Mix)
a) ((eece)
Beta paramotrizod with mean and variance
Cp <- (ela( 00000 0.01)
return p. Cp
end
B.2.2 MERGING COUNTERPACTUAL SETS
When searching for a good solution set, would be useful to have the option of improving on the best set we have obtained far using individual counterfactuals in the next candidate set see, rather than waiting for a new, higher-scoring set to come along While optimizing for objectives like diversity, which operate over all pairs of elements in the set, it is computationally complex to
23

---

Under review as a conference paper at ICLR 2023
Algorithm Algorithm for Theorem 3.1
Input: C², C R-XM matrices containing the costs with respect to all cost samples..
Output: e RNN, matrix containing the benefits of replacing pairs from S x S
function computeBenefiss( C)
Initialize B BERN 0
// Find the indices of the best and second best counterfactual in Sheat for each the cost function.
ba RRM = max C
ba E RM arg second max, C.
// Iterate over all pairs of counterfactuals.
forall p.q E [N] x [N] do
// Iterate over cost functions which ndh counterfactual in gheat has the minimum cost.
forall r E (i [M] bj p) do if > Cor then
This replacement reduces the cost of gheat by co Car.
pay pr Crr
else
Czsir cost of second best counterfactual in gheat for p cost function.
B Ppy Ch min CUr, C
end
end
return B end
24

---

Under review as a conference paper at ICLR 2023
evaluate the change in the objective function if one element of the set is replaced by 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, can compute costs for individual recourses rather than sets, meaning we can do 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 compute additional & distances for each replacement because the distance of the new replace vector needs to be computed with respect to all the other vectors, for each iteration of the nested loop. This quickly makes it infeasible to improve the best set by replacing individual candidates with the best set elements. However, for metrics where it is easy to evaluate the effect of individual elements on the objective function, we can easily merge the best set and any other set St from time / 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 set of counterfactuals we can obtain a matrix of incurred cost C E IR IRN 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 St at time t. This procedure is defined in algorithm 5. It iterates over all pairs of element in 8; E Sbeet and 8 E S₁ and computes the change that will occur in the objective function by replacing 8; + 8z. Note that are not recomputing the costs here. Given Sheat, St, C² and C, we can guarantee that we will update the best set Sbest in way to improve the mean of the minimum costs incurred for all the Monte Carlo samples. This is shown in algorithm 5 and the monotonicity of the EMC objective under this case can be formally stated as,
Theorem B.1 (Monotonicity of Cost-Optimized Local Search Algorithm). Given the best set, Sheat E Nxd, the candidate counterfactual at iteration t, S, E Nxd the matrix C² E N and C E NNM containing the incurred cost of each counterfactual in St and Se with respect to there always exist a Shest constructed from Steat and Se all the M sampled cost functions {
such that
(M, Steeat (C.).M)) EMC(ss,, Sheat: (C.))1))
M
Proof. To prove this theorem, we construct a procedure that ensures that the EMC is monotonic. For this procedure, we prove that the monotonicity of EMC holds. Check algorithm 5 for a constructive procedure for this proof, which is more intuitive understand.
We start off by noting that each element of C22 is the cost of the 8th counterfactual si in the best set Sheat with respect to the cost function C, given by Cost(s,, (s,, si: C2). Similarly C;₁ = Cost(s s; C2) where s; is the 5th candidate counterfactual. Note that, the EMC is the average of the MinCost with respect to all the sampled cost function Cy. What this means is that given pair of counterfactual from Sheet x S₁ and for each Cj. we can compute the change in the MinCost which we describe later. These replacements can lead to an increase in the cost with respect to certain cost function but the overall reduction depend the aggregate change over all the cost functions. Given this, for S
each replacement candidate pair in Sheef 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-benefit for this replacement pair. The cost benefit can be negative for certain replacements as well if the candidate counterfactual increases the cost across all the cost functions. The pairs with the highest positive cost benefits are replaced to construct the set Shestt, if no pair has a positive benefit then we keep set Sheat Sheat Hence, this procedure monotonically reduces EMC. We now specify how the change in MinCost can be computed to complete the proof.
To compute the change in MinCost for a single cost function C, first we find the counterfactual in Steet with the lowest and second lowest cost which we denote by s and sf These are the counterfactuals which can affect the MinCost with respect to a particular cost function C. This is true because when we replace the counterfactual sy which has the lowest cost for C₁ with new candidate counterfactual s;, there are two cases. Either, Ch,j > Ciy or Ch,, < Cij. In case when the candidate 8; has lower cost for C, than Ch i.e Ch2 > 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 Ch i.e Ch, S Cijs it means that this replacement will increase the cost for C2 by
25

---

Under review as a conference paper at ICLR 2023
- --mmi(C CiAz). Here, Cl2y is the second lowest cost counterfactual for C. Note that the change this case will be negative and also depend on the second best counterfactual because once the si is removed from the set, the best cost for C, will either be for st or 8;, hence take the minimum of those two and then take the difference as the increase in cost. Please refer to Algorithm 5 for cognitively easier way understand the proof.
B.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-base optimization in this continuous space while optimizing for objective defined in Section B.1.1. Their final objective function is defined as
A k Σ dist(c;, æ)) X2 ppp_ diversityyci,....... Ck)
C(x) ch....
arg min
loss (oss(f(c;),))) +
where is a counterfactual, k is the number of counterfactuals, f(.) is the black box ML model, yloss(.) is the metric which minimizes the distance between models prediction and the desired outcome y. dpp diversity(.) is the diversity metrie defined in Section B.1.1 and λ and d2 hyperparameters to balance the components in the objective. Please refer to Mothilal et al. (2020) for more details.
2. FACE (Poyiadzi et al., 2020) operates under the idea that to obtain actionable counterfactuals they need be connected 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 is algorithm) get the final counterfactuals. Please refer (Poyiadzi al., 2020) for more details.
Actionable Recourse (Ustun et al., 2019) tries to find an action set a for a user such that taking the action changes the black-box models decision to the desired outcome class, denoted by +1. They try to minimize the cost incurred by the user while restricting the set of actions within an action set A(x). The set A(x:) imposes constraints related to feasibility and actionability with respect to fea- tures. They optimize the log-percentile shift objective (see Section B.1.1). Their final optimization equation
min cost a; x) s.t. f(x + a) = +1, a E A(x)
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.
'Please refer to the this example where they mention about these restricted abilities http:///iweeeeaaaammmmm////////e hitpssseee__.oguuiccsttttiiinni
26


Reviews:
[{"review_id": "xPJ7Tr-Axd", "reviewer": "Reviewer_LeNz", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "", "summary_of_the_paper": "This paper investigates the problem of recourse generation -- generating plans that allow a user to change the decision of a model to some other option. The paper proposes to incorporate the individuality of user preferences into both training and evaluation. This involves both a new objective function, Expected Minimum Cost (EMC), and a new discrete optimization algorithm (COLS). They report improved performance (in terms of % of satisfied simulated users and actual human evaluations) over baselines across 2 datasets: Adult-Income (predicting whether someone has an income >$50k based on a set of features) and COMPAS (predicting whether defendants will commit another crime within 2 years). ", "summary_of_the_review": "Overall, this paper seems to make a strong contribution to the field of recourse generation. It is clearly written, the proposed method seems valuable, and improves significantly upon baselines. I remain quite uncertain in my review given that I have little background in this field, and I remain confused about the applicability of the datasets used to real-world recourse generation, but nonetheless I tentatively recommend acceptance.", "strength_and_weaknesses": "My background (deep learning, NLP, AI alignment) is quite different from the background of this paper, and thus my review should be taken with a huge grain of salt (I have more questions than judgments). \n\nStrengths: \n+ The paper is written very clearly. \n+ There are many details included in the paper that allow for ease of reproducibility (including hyperparameter details, information in the appendix, a reproducibility statement, etc.)\n+ The problem tackled by the paper seems important. Incorporating individual user preferences into recourse generation seems like a good idea. The results are quite strong, including on their human evaluations.\n+ The paper performs an ablation of COLS and EMC, finding that each piece is important (though particularly EMC). In general the set of experiments performed in the paper is very thorough (see also Appendix A.2).\n+ I really like the formatting of Section 4.2 -- it lays out a sequence of research questions along with the findings as supported by the evidence in the paper. In my opinion this is exactly how papers should be written.\n\nWeaknesses:\n- As an outsider to the field, the paper could have done a slightly better job explaining how the datasets + evaluation methodologies used in the paper (Adult-Income and COMPAS) relate to recourse generation 'in the wild'. In particular, it's not obvious to me that recourses involving changing the space of user features is the most natural way for useful recourse to happen. For example, in the Adult-Income dataset it feels like some recourses that could be generated involve changing the user's age or marital status. In practice would this mean that the user would have to go get married to change the decision made by the algorithm? That seems quite unrealistic (let alone changing age from 34 to 84, as seen in Figure 8). What seems more natural are interventions that lay outside of the technical domain (eg having a human review your application rather than a model). Perhaps this should be more naturally viewed as a kind of interpretability, for explaining the models' decisions (as alluded to in Section 1). However, it seems like this would be most naturally done using interpretable ML methods like decision trees to make the judgments in the first place. Overall, I find myself confused about how these datasets apply to real-world recourse generation and thus, am unclear about the impact of the proposed method.\n- Similarly, diving into the human evaluation instructions in Figure 7 in the Appendix, I feel like I would have a hard time making a decision about whether or not a recourse is reasonable, or whether one recourse is better than another. For instance, if a user has a preference_score > 0 for age, and the recourse suggest changing their age, is that reasonable? It seems like the main thing to do is a manual investigation to ensure that the features being changed correspond to positive preference_scores, but it feels like this could be done automatically -- it's not clear to me how much human evaluation is adding (as someone who is usually a huge fan of human evaluation).\n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and 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": "jn3XjAx0ppN", "reviewer": "Reviewer_93yL", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "", "summary_of_the_paper": "The paper describes INSPIRE, a methodology to provide recourse sets to users from which they can select a counterfactual instance which can overturn a potentially bad decision taken by a machine learning model. The authors show a method to efficiently sample counterfactuals tailored to the personal user’s cost function, thus making them more appealing to the users. They present COLS, a novel optimization algorithm which optimizes for the EMC (Expected Minimum Cost) and can refine the recourse sets iteratively. Lastly, the authors demonstrate the advantages of their method with an extensive evaluation.", "summary_of_the_review": "The paper presents a new methodology to obtain counterfactuals to achieve recourse. The authors try to move away from the shared cost assumption by providing a sample-based method which can mimic many different cost functions. However, the method itself is very involved, and it does not really provide user-tailored counterfactuals. \n", "strength_and_weaknesses": "The paper is interesting, and it tries to tackle one of the challenges of algorithmic recourse. They outline a method that accounts for different cost functions and provides recourse sets from which the user can select. However, from the problem statement and assumptions, the problem the authors try to solve does not match the claim made by the paper. \n\nFrom Section 2 and Section 3, it seems that the assumption just shifted from having a shared cost function to a shared set of distributions describing all the possible user cost functions. D_{perc}, D_{lin} and D_{mix} need to be well-design to provide meaningful results. In a paper titled “integrating individual user preferences in recourse,” I would expect to see a way to integrate a single user’s preferences to provide recourse while the user is still not considered in the estimation process. \n\nThe authors do define preferred features (FP) as a means to incorporate real individualised preferences (see Section 3.1). However, they assume that the user can provide them directly (which is generally not true), and they do not elaborate on them much further. I think providing a way to estimate them would be an important contribution instead. \n\nIn Section 3.4, the authors argue that obtaining user feedback to assess satisfaction is challenging. This statement is not true since there is extensive literature [1] about estimating user preferences via several types of interaction, which has been applied in many fields, such as recommender systems. \n\nMinor:\nSection 2 does not specify exactly how the cf is converted into actionable feedback for the user. Does the user select the less costly cf from the recourse set only? or is this cf presented in a “sequential” way to the user (e.g., first, get a degree, second, get a better job, etc.)?\n\n[1] Viappiani, Paolo, Boi Faltings, and Pearl Pu. \"Preference-based search using example-critiquing with suggestions.\" Journal of artificial intelligence Research 27 (2006): 465-503.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "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": "Ev7BHpsxr1e", "reviewer": "Reviewer_7m29", "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": "", "summary_of_the_paper": "The work proposes an algorithm, Cost-Optimized Local Search (COLS) to optimize the objective Expected Minimum Cost (EMC) [proxy to the original cost matrix of a user] to come up with a recourse set (actionable and feasible requests) personalized to the preferences of a user.", "summary_of_the_review": "The work attempts to solve an interesting problem of accounting for specific user preferences while coming up with recourse recommendations. The reading could be improved with addition of more examples. The work utilizes three baselines over two datasets for their evaluations.", "strength_and_weaknesses": "Strengths : \nThe problem statement was well specified formally, which was extremely helpful in understanding the work (but mostly because of the absence of a running example).\n\nThe method evaluates both on the devised metrics as well as existing metrics to compare with baselines. \n\nCOLS seems to be a simple genetic algorithm like method which I can see could be used in further research in this direction.\n\nWeaknesses : \nI would have really appreciated it if the work had a running example to explain “recourse”, the role of the EMC objective, diverse cost function, COLS and so on. Readability of the paper was severely hampered without it. \n\nSeveral works in other literature like database systems and web mining have used measures like coverage & at least some seminal work should be cited.\n\nThe method relies on a good cost function generation method. Were there any studies conducted to support that the method would be able to cover human preferences? [With real humans in the loop?]\n", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "AFXuYlyRbY", "reviewer": "Reviewer_Zf2f", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "", "summary_of_the_paper": "Existing recourse generation methods optimize for any single objective that is shared across different users not paying attention to a user’s individuality. This might result in impractical recourses due to undesirable feature changes. Different individuals’ preferences may associate different costs to the same feature-change. Thus modeling integrating user-preference into recourse generation enhances its acceptability in the real-world. The unavailability of user-specific feature change costs further compounds the problem. The authors solution - INSPIRE provides each user with a recourse set that contains multiple options such that if possible, there is at least one feasible solution adhering to the user’s unknown personal feature preference. A diverse set of recourses are generated assuming the user-specific cost is sampled from a specific distribution. The authors propose COLS, a discrete optimization procedure to generate the recourses. The results from simulated user-preferences on benchmarking datasets demonstrates the solution’s efficacy. ", "summary_of_the_review": "Overall, I find the paper to be a work-in-progress on an important problem on generating recourses. While the methodology is technically sound, the fundamental issues related to the cost function assumptions, and the human subject experiments make me lean towards a reject. I would like to see this work getting published eventually.\n", "strength_and_weaknesses": "Strengths\n\nProblem statement: The authors address a pertinent problem faced by the algorithmic recourse research community. While prior approaches assume a cost function that is shared by all users, the authors formulate the problem to overcome this assumption, thus extending the research boundary. \n\nSolution: The solution - EMC objective and COLS are quite intuitive, non-trivial, and simple to follow. The search procedure is also theoretically grounded. \n\nExperiments: The authors conduct exhaustive experiments to validate the approach, including fairness analysis and ‘simulated’ human subject experiments resulting in strong evidence suggesting the approach’s efficacy.\n\nWeakness\n\nI have two major concerns with the proposed cost functions. Firstly, I believe it is impractical if not unrealistic to expect users to express the cost function in the required form. Users might provide some sort of ordinal rankings of the attributes, but to expect cardinal utilities for feature changes is unrealistic. More evidence from the authors to support their definition of cost function will strengthen the paper. Secondly, even though the authors claim on modeling unknown user cost function, it is strictly not unknown. There is a strong assumption-  the user cost function belongs to a larger family of functions. The structure of the cost function remains the same. Is there any evidence to suggest that the behavior of the cost functions are fundamentally different? That is, the cost functions (lin and per) are uncorrelated on a given dataset? While the experiments using distribution shifts(Q5) are perhaps in the right direction, evidence supporting the behavior of cost functions will further strengthen the observations from Figure 2 in the appendix. Furthermore, the results presented in Figure 3 are incomplete. It would help to see the distribution shift spanning from [0, 1], instead of stopping at 0.3.\n\nThere are also concerns with the human subject experiments. Firstly, asking annotators to pretend to be the end users of the system takes away the real-life changing situations under which customers might use the system. This has severe trust issues- A company is deploying a system for their clients based on hypothetical experiences of annotators. I recognize that designing and conducting an experiment involving real-users is a daunting task and also appreciate the authors’ effort in attempting to address this issue. However, I worry that these experiments involving pretend annotators may inaccurately portray the acceptance and usability of such systems . It is important to perform human subject experiments to validate the method, but the experimental design needs more care and technical soundness. Secondly, the experiment is basically asking the pretend annotators to check if the proposed recourse is following the feature scores. Considering that INSPIRE suggests recourses satisfying the feature scores, it is not surprising that the users favored INSPIRE over actionable recourses. I would rather argue that the acceptance rate of INSPIRE (57%) is quite low! More importantly, the experiment does not measure whether the recourse generated by INSPIRE is in accordance with the user’s cost function (not the vector $p_u$), which would require the user to provide a cost function!\n\nI would also like to see some discussion on selecting $k$ in the feature satisfaction metric. How sound is it to assume a constant $k$ across the users? How does one decide on this value in the real world?\n\nA minor concern is the comparison of INSPIRE against other actionable recourse approaches. One might view the comparison on cost metrics as unfair as the other methods are not designed to consider the user cost functions. ", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "2Hm1E4XrxJk", "reviewer": "Reviewer_guRt", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "", "summary_of_the_paper": "The paper introduces a new framework to create recourse to algorithms with higher user satisfaction than comparable approaches, using Expected Minimum Risk and a novel optimization algorithm. Recourse here is meant to enable users to make changes in algorithmic classification, altering the result according to their preferences. Other recourse methods reportedly did not take into account individual preferences but optimized for several general metrics, such as proximity and diversity. Here this is achieved by drawing from several distributions of counterfactuals which are spread out so that the likelihood of increasing user satisfaction is higher. The proposed method is reportedly fairer, more performant and leads to higher user satisfaction.", "summary_of_the_review": "Personally I had issues of understanding, which could also result from my lack of familiarity with the topic. I think that the paper can be rendered more comprehensible and stronger in terms of motivation and context with a few changes. Elaborating on the use case of the presented method and providing examples can go a long way, restructuring could also help. In terms of the technical execution and mathematical formulations the work appears sound to me. However, better defining the user, their satisfaction and their perceived fairness is important, as well as discussing limitations of the approach.", "strength_and_weaknesses": "I have to say in advance that I did not understand all parts of the paper fully, therefore my feedback should be taken with a grain of salt. Which parts I did not comprehend I will describe shortly.\n\nStrengths\n\nThe idea of the paper and its constitutent parts are discussed in a clear manner. Technical explanations are used sensefully, the algorithm is helpfully added in pseudocode, most unfamiliar terms are introduced. It also appears to be concise regarding the brevity and thus aims to convey the core information on as little space as possible. Visualizations and tables are used to help the reader, as well as comprehensive supplementary material. Reproduction of results is encouraged by providing the source code, an ethics statement further makes some important statements about the ethical nature of the work.\n\nProposals for modification\n\nA stronger explanation of the motivation and conrete use case would be very welcome, complemented by a handful of examples to help the reader picture it. The purpose, concept and feasibility of deploying this method in practical terms could be described in a discussion section, which presently is really very short.\nFurther, terms like \"user satisfaction\" and \"fairness\" are very charged concepts that tend to be multi-dimensional, in this work however they appear to have been mathematically formalized without discussion of the validity of such an approach. A brief exploration of the conceptual meanings attached to these terms and reflection on how they are made operational in this context would be helpful. Lastly, the user experiments, if I understood correctly, were conducted with only three users, who were additionally close to the research team -- a rather low number to draw general conclusions from, while also inviting biases of different sorts to eschew study results. This limitation should be mentioned in the text and user studies should perhaps be conducted with a broader, more diverse sample. \n", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject