INSPIRE: Incorporating Diverse Feature Preferences in Recourse
Authors: Prateek Yadav
Peter Hase
Mohit Bansal
Venue: Accepted by TMLR ()

Abstract: Most recourse generation approaches optimize for indirect distance-based metrics like diversity, proximity, and sparsity, or a shared cost function across all users. A shared cost function in particular is an unrealistic assumption because users can have diverse feature preferences (FPs), i.e. the features they are willing to act upon to obtain recourse. In this work, we propose a novel method, INSPIRE to incorporate diverse feature preferences in both recourse generation and evaluation procedures 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) 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 provide users with multiple options that cover a wide variety of FPs when the user's FPs are unknown. To optimize for EMC, we propose a novel discrete optimization algorithm, Cost-Optimized Local Search (COLS), that is guaranteed to improve the quality of the recourse set over iterations. Next, we propose a cost-based evaluation procedure that computes user satisfaction by simulating each user's cost function and then computing the incurred cost for the provided recourse set. Experiments on popular real-world datasets demonstrate that our method is more fair compared to baselines and satisfies up to 25.9% more users. We also show that our method is robust to misspecifications of the cost function distribution. Our code is available at \href{https://github.com/prateeky2806/EMC-COLS-recourse}{https://github.com/prateeky2806/EMC-COLS-recourse}.

Published in Transactions on Machine Learning Research (04/2024)
INSPIRE: Incorporating Diverse Feature Preferences in Recourse
Prateek Yadav
proty@es. unc. edu peter unc. edu mbansal@c cs. unc. edu
Peter Hase
Mohit Bansal
UNC-Chapel Hill
Reviewed on OpenReview: https: openreview. net/ form?? id= 6yzIugkGng
Abstract
Most recourse generation approaches optimize for indirect distance-based metrics like di- versity, proximity, and sparsity, or a shared cost function across all users. A shared cost function particular is an unrealistic assumption because users can have diverse feature preferences (FPs), i.e. the features they are willing to act upon to obtain recourse. In this work, we propose novel method, INSPIRE to incorporate diverse feature preferences in both recourse generation and evaluation procodures by focusing on the cost incurred by user when opting for recourse. To achieve this, we first propose an objective function, Expected Minimum Cost (EMC) 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 pro- vide users with multiple options that cover a wide variety of FPs when the user's FPs are unknown. To optimize for EMC, we propose a novel discrete optimization algorithm, Cost- Optimized Local Search (COLS), that is guarantoed to improve the quality of the recourse set over iteralions. Next, we propose a cost-based evaluation procedure that computes user satisfaction by simulating each user's cost function and then computing the incurred cost for the provided recourse set. Experiments on popular real-world datasets demonstrates that our method is more fair compared to baselines and satisfies up to 25.9% more users. We also show that our method is robust to misspecifications of the cost function distribution.
1 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). recourse is an actionable plan that allows user to change the decision of deployed model a desired alternative (Wachter et al., 2017). Recourses often presented to users set of counterfactuals (CFs), where each CF details the changes to the user's state vector (i.e., their feature vector). Recourses are desired to be actionable, and feasible. Actionable means that only features that can be changed by the user are requested to be changed. A recourse is feasible it is actionable and easy to adopt for the user.
To achieve these objectives, prior work used indirect feature distance- based objectives like prozimety sparsily, and feature diversity. For instance, Mothilal et al. (2020) and Wachter al. (2017) encourage prozimity by minimizing the distance between the user's state vector and the counterfactuals (CFs) with the assumption that proximal CFs are casier to adopt. Whercas, sparsity quantifics the number of features that require modi- fication to implement a recourse (Mothilal et al., 2020). In contrast. to these, feature diversily (Mothilal el al., 2020; Cheng et al., 2021) provides a user with multiple CFss that change diverse subsets of features assuming
1 'Qur code available at http:///ithhdbcco///ateeeeee

---

Published in Transactions on Machine Learning Research (04/2024)
that users are more likely to find at least one feasible solution. Any of these objectives alone is not sufficient to provide feasible recourse to the user and it is hard and subjective to decide what combination of them will lead to a satisfied user. Moreover, these objectives do not account for individual user preferences which should be of primary focus. For instance, if a user prefers to change features fi and f2, then providing them with re- courses that change undesirable features makes them infeasible even if they are proximal, sparse, and diverse.
To address this, some recourse methods define and use cost functions. A cost function, c(f,i.)) denotes the cost of changing feature f from value to j. The methods of Ustun ct al. (2019); Rawal & Lakkaraju (2020); Karimi et al. (2020c;d) assume that all the users share single cost function. They define this cost function and then for cach user, they optimize the same cost function to generate CFs with low overall costs under this function. Next, they evaluate the cost of CF's under the same cost function. We question the utilization of a single cost function for all users, as it may not accurately reflect the preferences of a diverse user population.
We argue that is crucial to assume that cach user has a different cost function in order to ef- fectively cater to the unique characteristics of individual users. However, as noted by Rawal & Lakkaraju (2020), in most practical cases it is difficult for a user to specify their feature preferences or cost function. Therefore, we as- sume that these are not provided and we only assume access to the user's state vector. To overcome this limitation, we propose novel method, INSPIRE (INcorporating diverSe fea- ture Preferences In RecoursE) that generates a diverse set of cost functions to capture vari- ous feature proferences (FPs) a user might pos- sess and utilizes them to provide a recourse set containing multiple CFs to the user. IN- SPIRE provides each user with a recourse set that is constructed such that the likelihood of having at least one feasible solution adher- ing to the user's personal feature preference is maximized. INSPIRE focuses on and im- proves upon four major components - (1) the procedure to generate diverse cost functions with underlying FPs, (2) the recourse objec- tive function, (3) the recourse generation algo- rithm, and (4) the evaluation procedure.
Cu
0
00
0
0
0
0
0
0
81
0
82
0
True Cost Function
Sampled Cost Functions
Figure 1: Diagram showing the intuition behind the Ex- pected Minimum Cost Objective. The axes represent an ab- stract cost function space where squares denote cost func- tion samples that are the same color if they have similar underlying FPs and hence form a cluster. We aim to find a recourse set where each CF (here, $21, does well for certain types of FPs represented by clusters of cost func- tions. The shaded big circles each represent a single CF s that caters to the enclosed cost functions. Here the user's ground-truth cost function (grey circle) is served well by st.
We build on the cost functions defined in Us- tun et al. (2019) to propose three distributions, Datep: D Dperes and Dmix that can be used to sample cost functions with different underlying FPs that users in a population might possess. These dis- tributions generate cost functions based on steps needed and percentile changes (Ustun et al., 2019) in the feature values 1$4.1). Next, we propose novel objective function, Expected Minimum Cost (EMC) that ap- proximately optimizes the cost a user will incur when their FPs are unknown. The EMC objective encourages diversity in the solution set with respect to the different FPs a user might possess. This is done by ensuring that each CF is a good CF under some particular cluster of cost functions representing similar FPs (see Figure 1). We minimize the EMC of the generated recourse set with respect to multiple sampled cost functions from one of the proposed distributions ($4.2). Hence, if the user's ground-trut cost function is well represented by any of the clusters, then will have some counterfactual that is feasible (actionable and low-cost) for them (See Figure 1). In order to efficiently optimize for EMC, we propose genetic algorithm (Mitchell, 1998) based optimization method,
Local Search (COLS) ($1.3). COLS guarantees a monotonic reduction in EMC of the recourse set, leading to large empirical reductions in the user-incurred cost.
2

---

Published in Transactions on Machine Learning Research (04/2024)
Lastly, we propose novel cost-based evaluation procedure to compare different methods that accounts for the individuality of the users by having different cost. functions for each user ($4.4). We simulate an evaluation cost function for each user and then assess the fraction of satisfied users based on whether their incurred cost of recourse is below a certain satisfiability threshold k. Even though the cost functions are simulated, this setup can be used to rank different methods to assess their recourse generation abilities. We also report coverage, which the fraction of users with least one actionable recourse (Rawal & Lakkaraju, 2020). Moreover, we evaluate all methods on existing indirect metrics from the literature like diversity, proximity, sparsity, and validity ($5.1).
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 multi- ple popular and recent baseline methods like DICE (Mothilal et al., 2020), FACE (Poyiadzi et al., 2020), and Actionable Recourse (AR) (Ustun et al., 2019). We show that our method satisfies up to 25.89% more users than strong bascline methods while covering up to 22.35% more users across datasets. We also perform im- portant ablations to show the ad advantages of using the EMC objective and the COLS optimization procedure. Next, perform fairness analysis of methods across demographic subgroups to show that our method is fairer than bascline methods. Finally, we evaluate the robustness of our method to various types of distribu- tion shifts that can occur between the evaluation cost functions distribution and the distributions used in the FMC objective (see Section 5). We find that our method is robust to multiple types of distribution shifts and leads to an improvement of at least 11% even in such scenarios. Our primary contributions are listed below.
1. We conceptualize a novel method, INSPIRE that accounts for diverse feature preferences while generat- ing and evaluating recourse options. INSPIRE provides the flexibility for future researchers to further innovate on all of its four components.
2. We propose new objective function, Expected Minimum Cost that approximately optimizes the cost a user will incur when their FPs are unknown using diverse samples from a distribution.
3. We propose a discrete optimization method, Cost- Optimipttd Local Search which generates recourses that lead to higher user salisfaction while being fairer.
4. We propose an evaluation procedure that allows us to compare different methods on individual user satisfaction by simulating users' evaluation cost functions.
2 Related Work
Here, distinguish our approach based on our recourse objectives, optimizer, and evaluation. We point readers to Venkatasubramanian & Alfano (2020) for a philosophical basis of algorithmic recourse and to Karimi et al. (2020b) for comprehensive survey of the existing recourse methods.
Objectives: The most prominent family of objectives for recourse includes distance-based objectives (Wachter et al., 2017; Karimi et al., 2020a; Dhurandhar et al., 2018; Mothilal et al., 2020; Rasouli & Yu, 2021). These methods primarily seek recourses that are close the original data point. In DICE, Mothilal et al. (2020) provides users with set of counterfactuals while trading off between proximity and feature di- versity. A second calegory of methods uses oer heuristics based on the data distribution (Aguilar-Palacios et al., 2020; Gomez et al., 2020) to come up with counterfactuals. 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: (1) Cui et al. (2015) define a cost function specifically for tree-based classifiers, which compare the different paths that two data points follow in a tree to obtain a dlessiferrdeeeeddntt 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. (3) Ustun et al. (2019) define cost in terms of the number of changed fcatures and frame recourse generation as an Integer Lincar Program. (4) Rawal& & Lakkaraju (2020) infer global cost function from pairwise comparisons of features that are drawn from simulated users. However, they take a different approach to the recourse generation problem, which is to find a list of rules that can apply to any user to obtain recourse, rather than especially generating recourses for each user as in this work. Importantly, all of these works assume there is a known and single cost. function that is shared by all users.
3

---

Published in Transactions on Machine Learning Research (04/2024)
Optimization: Several recourse methods use gradient-based optimization to generate counterfactuals 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 (Poyiadki et al., 2020; Aguilar-Palacios et al., 2020) to generate counterfactuals. A few works use autoencoders to generate recourses (Pawelezyk et al., 2020; Joshi et al., 2019), while (Karimi et al., 2020a) and (Ustun et al., 2019) utilize SAT and ILP solvers, respectively. In contrast to these methods, we also suspect that ideas from distributionally robust optimization (Rahimian & Mchrotra, 2019) can also be used to come up with alternative objective functions or even better ways to optimize the EMC objective.
Besides ensuring recourse validity, the most prominent approaches to evaluate recourses rely on bastance-based metrics. In DICE, Mothilal et al. (2020) evaluate recourses according to their proximity, spansity, and feature diversity. Meanwhile, 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 single rank order amongst the feature from simulated pairwise feature comparisons from experts. For all these methods, a single cost function is used for both recourse generation and evaluation, i.c. the solutions are optimized and tested on the same cost function (Cui et al., 2015; Karimi et al., 2020c;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 preferences.
Evaluation:
3 Problem Statement
Features Types. We assume a dataset with features F = f2, fih Features can be mutable, conditionally mutable, or immutable, according to the causal processes that generate them. For example, Race is an immutable feature (Mothilal et al., 2020), Age and Education are conditionally mutable (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 appropriately sized bins. Moreover, the feature values can be ordered unordered, c-g., Workclass can be business, private, government, etc and none of these feature values are more difficult then the other to achieve.
Cost Function. In this work, we assume that each user has an inherent an ordering of the features with respect to the case of changing them, and different users will likely have different FPs. We quantily these user FPs via fealure-scores denoted by p = [p/r..... .,"), which sum to and each pf E [0, 1] represents the willingness of the user to change feature f.. A cost function C(f, x, y) takes into account the user FPs and provides an elaborate cost of changing feature f from to y and lies in [o. 1] U (oo}. Here, 0 means that the transition has no associated cost, whereas 1 means it is maximally difficult, and oc means that it is infeasible under the cost. function.
(FP) that is
Transition Costs. Given a cost function C and two state vectors 8;, 8j, the cost of transition from 8, 8j is the sum of the cost of changing individual features. Hence, Cost(s,, (5; C(erC(f,s( s/), where sf is the value of feature f in the state vector s. Cost can be greater than 1 when changing multiple features.
User Definition. A user is defined as a tuple u = (Su,C)). where 8, is the user's current state vector of length FI containing their feature values and C; is their ground-truth cost function. See Appendix Table for examples of 8, and FPs. Next, we define the cost incurred by a user when acting on a recourse set S. As a rational user will select the least costly option, the cost they will incur is the minimum transition cost across all CF in the recourse set,, defined as,
MinCost(s,,
min Cost(s (su, sy: Ci). sjES
(1)
Problem Definition. For a user u. our goal is to find recourse set Sn such that there exists at least one low-cost CF with the desired outcome. Hence, if the user's ground-truth cost function C, is provided then we can provide them with a good recourse by directly optimizing for,
S = arg min MinCost(s... (inCost(s..,;C))) s.t. 3s, S and F(s.) = 1,
(2)
S
4

---

Published in Transactions on Machine Learning Research (04/2024)
where F is the underlying ML model assigning decision and 1 is the desired class user wants to achieve. In general, F(s;) can take multiple different values denoting different class a user can be categorized into. In our experiments, we restrict to two classes as Actionable recourse (Ustun et al., 2019) method only works with two classes. Morcover, we note that in practice it is difficult for a user to precisely quantify their FP and cost function. Therefore, in most practical scenarios C₁ is not provided, and hence we use the EMC objective account for user FPs (S 4. 4.2).
4 INSPIRE: Integrating Diverse Feature Preferences in Recourse
To generate recourse for a user, we utilize their state vector as the sole input. We begin by using our proposed distributions ($4.1) to sample multiple potential cost functions that may align with the FPs of the user. Subsequently, we compute our EMC objective for the candidate recourse set with respect to the sampled cost functions ($4.2). Then, our COLS optimization method generates an updated candidate recourse set (64.3). Then this process is repeated iteratively to arrive at final candidate recourse set, which is evaluated through our proposed evaluation procedure ($4.4).
4.1 Characterising Feature Preferences and Cost Function Distributions
This section aims to enhance the existing ways of defining cost functions by incorporating FPs by scaling the cost of transition with feature scores. Recent works like Ustun et al. (2019) argue that users in a population fundamentally quantify the transition cost. of changing a feature I from a to y as being proportional to (1) the difference in percentile of x and y, i.e. to [Q}(z)- (()),, where Qy(.) is the CDF of the feature f in the target population (Ustun et al., 2019), and (2) the number of steps between to go from x to y (Ustun et al., 2019). For instance, when changing the education feature from Bachelors to Ph.D. the percentile might be appropriate very few people have Ph.D. degrees as compared to Bachelors leading to a higher cost. 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 call these the Percentile and the Step based transition cost. In Algorithm 2, and 3, we define procedures to sample cost function that adheres to percentile and step-based transition costs respectively. Moreover, these algorithms assign different costs based on feature properties- like being ordered or unordered, if the feature is ordered then can it both just increase, just decrease, or both increase and decrease, and if the feature is mutable, conditionally mutable, immutable. For Example, if a feature is ordered and can only increase then transition to any lower value leads to an infinite cost whereas transitioning to higher value depends on either the percentile difference (percentile cost) or the number of steps (step cost) between the initial and final feature value. More details can be found in Algorithm 2, and 3. We note that both of these costs are monotonic, i.e., more drastic changes have higher associated costs and are useful depending on the scenario. However, these functions assign equal importance to all the features which is suboptimal.
Therefore, to incorporate the notion of FP in costs, we use the feature scores, p (see $3) to scale these costs. We scale the transition costs of each feature by (1-)'), i.c Cost(f..,.) (1- pp), resulting in decreased cost for preferred features and vere-versa. This creates cost. functions adhering to feature score p.
Ideally, we want the user to provide us with the feature scores p but Rawal & Lakkaraju (2020) highlighted that even for experts, it is hard to specify their feature scores. Hence, to generate diverse cost functions, we want a procedure to sample feature scores p which can represent diverse FPs that users in a population might possess. Therefore, in Algorithm 4, we propose a feature score sampling procodure with minimal assumptions. We first randomly sample subset of FPs and then for the selected features, we sample the feature scores p from Dirichlet distribution. Note, that this procedure is very customizable, and in cases where users can specify their FPs or feature scores, we can skip this step.
Next, we combine the feature score sampling procedure (Algorithm 4) with percentile (Algorithm 2) and step (Algorithm 3) based cost function generation procedures respectively and call them Dperes Datep distributions. Finally, we propose Dmni (Algorithm 5) as our most general distribution that takes a convex combination of both step and percentile- based costs using a cost-type weight a. Hence, given a state vector s and feature scores P. we can use any of these three distributions generate cost. function with an underlying FP. Note
5

---

Published in Transactions on Machine Learning Research (04/2024)
that these distributions are using existing concepts of step and percentile-based cost functions along with feature score-based scaling. This allows us to cover a much larger space of cost functions compared to past works that assume a single fixed cost function.
4.2 Expected Minimum Cost Objective Function
As noted by Rawal & Lakkaraju (2020), in most practical scenarios the user's true cost-function C2 is hard to obtain thus cannot exactly minimize for Equation 2. Hence, propose the Expected Minimum Cost (EMC) objective function that utilizes samples of cost functions that depict a variety of underlying FPs that may be close to the user's true cost function, in order to generate a recourse set with at least one low-cost CF for all of these sampled cost. functions (see Figure 1). Give a state vector 8, a recourse set S, and a distribution Perain: we compute EMC as follows,
M
EMC(s, = IEC (M (MinCost(s,,;
&
min (s, syES
(3)
M
We employ Monte Carlo Estimation (Robert & Casella, 2010) to approximate the expectation by sampling M cost functions { from Derain and then expand MinCost using Equation 1. Next, for the user u, we obtain the recourse set S. by minimizing the EMC objective as follows,
S, = arg min EMC(s., s.t. 3s E S and F(s) = 1,
(4)
s
4.3 Cost Optimized Local Search (COLS)
To generate recourse set S, for user u, we optimize for EMC as shown in Equa- tion 4. We propose two simple, and elfi- cient genetic algorithms (Mitchell, 1998) for discrete search (Pirlot, 1996), namely Cost- Optimized Local Search (COLS) and Parallel Cost-Optimized Local Search (P-COLS) pre- sented in Algorithm 1. COLS maintains best set Shest which will be the final recourse provided to the user. We initialize all the el- ements of Sp as su- At cach iteration t, a candidate set S, generated by locally per- turbing each element of the best set with a Hamming distance of two, iee. making small changes to two features at once. For fea- tures with no ordering, we uniformly select any other potential value, whereas, for fea- tures with natural ordering we select values that are closest to the original values. Then we assess the validity of the generated CFs and do not use invalid CFs to compute met- rics in any subsequent steps. However, for simplicity for the pseudocode, we omit such details. Then S, is evaluated against end return Stest C+
Algorithm Cost-Optimizes Local Search Algorithm
Input: A state vector [C:) Dirain cost distributions Output: Sbest set with N generated countorfactuals. function COLS(s, M (. Initialize
Budget, hamDist)
// Parturb 8, N times.
Ghest E RRxx pertubCFS(ss, hamDist) ghest,
// Incurred
c + getCostMatrix(s, gheat (C:),s)
t == 0; maxlter = Budget//A /NV
while < mazlter do
S: E Nxd +- pertubCFS(Shoa hamDist)
C NNMM Mc (C.) 11=1
// B.j Change in cost when Sher( + Stbs]. See Algorithm 6.
B RNN computeeeneffts(CC (C., C) Sea App. Code Block
// If any avaps lead to cost-benefit then greedily select which pairs to swap batveen gheet and S, given B such that the cost only reduce. See Code Block 2 replaceIndices getReplaccldx(B) // Swap these pairs and update c².
forall originalldz, replaceldz replace/ndices do Sheal (originall)) S]replaceldx]
end C² gedCostMMarriss, (M
the EMC objective as defined in Equation 3. For efficient implementation, we store the costs of all the N CFs with respect all the
end
M cost functions C, Instead of making a direct comparison of EMC for the best-set-so-fie Speat and the candidate set S₁ we evaluate whether any CFs from the candidate set S, would improve the EMC of the best

---

Published in Transactions on Machine Learning Research (04/2024)
set Sta1 if we swapped out individual CFs. Specifically, if the benefit of replacing 8; St with 8, E Shest is positive, L.e., reduces FMC of Shest then we make the replacement. (see Algorithm 6 to see how we estimate benefit). Algorithm 6 initializes the benefit matrix B with zeros. For each sampled cost function (there are M of them), the algorithm finds the indices of the best and second-best counterfactuals. Then we consider all pairs of counterfactuals (p, q pairs), p from St and q from S, and checks the benefit. of replacing one with another. For cach counterfactual, the algorithm checks all cost functions where the pth counterfactual is the cheapest. If the cost of the td counterfactual in C' is greater than that in Co, the benefit of replacement is the difference in costs (Cp Crr). Otherwise, the benefit is calculated counterfactual from Ch minus the minimum of the current cost and the cost of the second-best counterfactual in Co for the 4th cost. fuucciio. We then greedily replace the CFs in Steat with efs from S, obtain Sheat which has either similar or better cost than Stoat. See Algorithm 1 or Code Block 2 for details. The ability to assess the benefit of each candidate CF is critical because it allows us to constantly update the best set using CFss from a candidate set instead of waiting for an entire candidate set with lower EMC. For objectives like feature diversity, evaluating the benefit. is expensive (see Appendix B.1). Moreover, for COLS we can guarantee that the EMC of the best set will monotonically decrease over time, which is formalized below:
the cost of the second-best
Theorem 4.1 (Monotonicity of COLS Algorithm). Given the best set, Stert E ENxd, , the condidate set at ileration 1, S, E RRNxd, the matrir C³ E RRN and C E RNX containing the incurred cost of each counterfactual in Steet and St with respect to all the M sampled cost functions (im) there always crist Steat constructed from Stert and St such that
EMC(su, Sheat, (c.) S EMC(s Start (c.)
For the proof of the theorem, please refer to Appendix B.2.2.
The P-COLS method is a 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 total budget. The recourse set of the run with the least EMC value provided to the user.
P-COLS:
4.4 Evaluation Procedure and Cost Based Metrics
Given that users' ground-truth cost functions C are unknown, it is hard to computationally compare different methods for user satisfaction and metrics like diversity, proximily, and sparsity do not directly measure this. To address this issue, for every user u, we propose to simulate an evaluation cost function C# from a distribu- tion Diest. We can use Equation 1 to compute the incurred cost under C# which can be used to rank order dif- ferent recourse methods. Note that, no method is allowed to use C# when generating recourse and this is ex- clusively kept for comparing methods. The effectiveness of this evaluation procedure increase the distribu- tion Drest becomes more expressive in terms of accounting for user FPs as it would align better with real users.
Given a set of users U, each user u E U is provided with a recourse set Sy. We compute the MinCost of (s,,
Sn given the user's state vector s and their evaluation cost function as MinCost, we report multiple aggregated versions of it for comparing other methods.
Given this
Population Average Cost: We report the Population Average Cost (PAC), that is the average cost of recourse for users in the population, defined as PAC / Eueu MinCost Su: Cu:
User Coverage: Next, we follow Rawal & Lakkaraju (2020) and define Coverage (Cov) that counts the fraction of users in the population who were provided with at least one actionable recourse. Given a set of users U and the recourse sets (Su)neu provided to them, Coverage is defined as,
Cov(U, (Suhuu)) =
Σ uEN
(s C.i < xc).
[24T
Fraction of Users Satisfied (FS@k): Finally, we note that PAC cannot be used to assess individual users' satisfaction. Hence, we go a step further and introduce a new cost-based metric that directly aggregates based on each user's satisfaction. We say that user is satisfied if the MinCost is below a certain acceptability
7

---

Published in Transactions on Machine Learning Research (04/2024)
Table 1: Recourse method performance across various cost and distance metrics (Section 5.1). The numbers
reported are averaged across 5 different runs. *-' means that higher or lower values are not necessarily better when looking at individual metrics.
Data
Method
Metrics
Cost. Metrics
Indirect Metrics
FS@1(()
PAC(.)
Cov(t)
Div(-)
Prox(-)
Spars(-)
Val(t)
DICE
2.47
1.37
8.32
3.90
65.80
47.20
97.90
Face-Epp 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
78.00
94.78
DICE
0.40
0.54
0.40
11.30
65.00
32.00
98.90
Face- Face-Eps
12.20
0.29
12.20
2.50
60.60
100.0
Pace-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
44.23
COLS
82.23
0.24
82.23
29.32
77.82
70.05
95.48
P-COLS
83.73
0.24
83.73
29.38
78.48
71.30
92.78
(hreshold k. Formally, we define the fruction of users salisfied a satisfiabllity threshold k as:
FS@K(U, (Suhueu)
1 [24]
Σ NEW
1(MinCost(su Su: C#)
k}}
(5)
Reporting FS@k is similar reporting accuracy as opposed to test loss. This is better for comparing methods because it aggregates an example level before performing averaging. In reality, the k can vary from user to user but we keep &o fixed across users in experiments because the goal of any method is to find low-cost recourses regardless of k. Moreover, any fixed & can be used to rank-order different methods. In deployment scenarios, reasonable values of k can be estimated by doing user survey.
5
Experiments
5.1
Experimental Setup
We use the Adult-Income (Dua & Graff, 2017) and COMPAS (Larson et al., 2016) datasets with Open Data Commons PDDL license. The Adult-Income datasel is based on the 1994 US Census data and contains 12 features. The model has to predict whether an individual's income is over $50, 000. COMPAS contains 7 fcatures 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 a previous analysis where categorical features are binarized (Pawelczyk et al., 2021).² 2 Our black-box model is an Multi-Layer Perceptron with 2-layers. Please refer to Appendix Tables 10 and 11 for experiments with logistic regression and Appendix A.3 and Table 5 for further experimental details.
Dataset:
Baselines: 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). Importantly, we 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 rale-limiting step for each method. We ran our experiments on a local server using a single Nvidia 1080 Ti GPU, We set a fixed budget 5000 model queries, a set size |S = 10, and the number of cost function samples M = 1000 for all methods. For description of the objective function and other dctails of these baselines refer to Appendix B.1.1, B.2.3.
Distance Based Recourse Metrics: We also report indirect metrics like feature diversity, proximity, sparsity, and validity that are used in past works. We report the average of these metrics in percent- age across all users. These metrics are a proxy for user satisfaction and any individual metric might not
2 The code for the Actionable Recourse method (Ustun et al., 2019) requires hinary categorical variables.

---

Published in Transactions on Machine Learning Research (04/2024)
Table 2: Ablation on Search algorithms and objective functions.
Search Alg.
Objective
Cost Metries
Indirect Metrics
Ft@1(t))
PAC(L)
Cov(1)
Div(-)
Prox(-)
Spars(-)
LS
Sparsity
10.1
1.304
29.0
42.7
66.2
55.8
LS
Proximity
9.7
1.275
27.0
42.1
67.5
55.0
LS
Diversity
0.3
2.393
7.6
53.3
50.8
35.6
LS
EMC
49.8
0.597
59.1
37.8
73.3
67.5
COLS
EMC
68.8
0.391
72.6
27.1
77.5
73.5
strongly correlate with the satisfaction of user. For example, a recourse might. have really high diver- sity but low proximity resulting in the recourse being infeasible. For single user, Proximity is defined as prox(æ, S) 1 [ss E| dist( (x. S.), where S is a counterfactual. Sparsity (Mothilal et al., 2020) is defined as spar(z, 5) =1 15id E E,= 1 [x,) Feature diversity (Mothilal et al., 2020) is defined as div(S) = / - E j=++ (S,, Sj), where Z is the number of terms in the double summation. Validity is defined as vY) [unique s,ES : [(+)=+1H1
[8]
Sampling Cost Functions for Real World Practitioner: Real-world practitioners can design system where they can ask each user to provide either the features (Fp) that they find easy to change (which can be converted to preference scores using Algorithm 4 or directly provide a preference score (p) for each feature if they can. Given this our Algorithm can be used to sample cost functions that are a better estimate of the user's real cost function. Note that these cost functions are still estimates and try to capture different ways a user can think of cost, i.c. in terms of percentiles or steps (absolute change in feature). The practitioner can use these more aligned samples to optimize the EMC objective to generate better recourse for the user.
Evaluation Details: By default, use Dmix distribution to obtain the cost function sample for the EMC objective (i.e Dirain -mir)) and the evaluation cost function C# (i.c Drest = Dmiz). We use Dmiz because it is the most expressive distribution and can combine percentile and step-based costs. Hence, it is more likely to generate samples close to the user's true cost function. See Figure 1 and Section 4.4 to understand why this is important. Note that, this is a significantly better procedure than past works (see $2) which uses a single cost function both during training and evaluation. In our evaluations, the cost samples {C, ( used during training to optimize for EMC are different from C# which is used for evaluation even if they come from the same distribution. Moreover, in Section 5.2;Q3,4,55 we perform distribution shift experiments, where Drrain + Drest and show that even in such cases INSPIRE generates the best quality recourse.
5.2 Research Questions
Q1. Which Recourse Method Satisfics the Most Users?
Tn this experiment, we compare different recourse methods on our cost-based evaluation procedure and other indirect metrics. We report the average performance over five random seeds in Table 1. We observe that COLS and P-COLS, which optimize for EMC, achieve 22. 22.64% and 25.89% higher user satisfaction (FS@1) while covering 19.28% and 22.42% more users compared to the strongest baseline on Adult-Income and COMPAS, respectively. We provide results for additional values of A E (0.5,1,2,3) 1,2,3) 3} for FS@k in Appendix Table 12. Meanwhile, other methods that optimize for a combination of other indirect objectives, perform worse on user cost-based metrics that directly model user satisfaction. Interestingly, we find that COLS and P-COLS solutions exhibit high feature diversity, proximity, and sparsity. This implics that - (1) the Dinix distribution is generating cost functions that model diverse FPs and COLS along with EMC allowing us to obtain the highest diversity even compared to other methods that directly optimize for it, and (2) proximity, sparsity, and diversity emerge necessary metrics even under our cost-based evaluation procedure but they are not sufficient to satisfy users with preferences as shown by other methods performance on cost-metrics. This is because il is non-trivial to find the right balance when optimizing for these metrics.
Q2. Is the Performance Improved by the COLS Optimization Method or the EMC Objective?
We perform ablations to understand the impact of the COLS optimization and the EMC objective. We run basic local search (T.S) to optimize for feature diversity, proximity, and sparsity along with validity. We

---

Published in Transactions on Machine Learning Research (04/2024)
Robustness to distribution shift. EMC used miir to sample cost function for recourse generation while evaluation cost functions are log-percentile shift cost functions from the AR (Ustun et al., 2019).
Table 3:
Data
Method
FS)1((1)
PAC(L)
Cov(t)
Act. Recourse
56,42
0.49
61.21
Adult-Income
COLS
71.32
0.43
74.89
P-COLS
73.68
0.42
77.11
Act. Recourse
70.26
0.35
76.31
COMPAS
COLS
80.51
0.29
81.68
P-COLS
82.13
0.26
83.24
use basic local search because there is no 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 the indirect distance metrics is sub-optimal for user satisfaction. 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 F$ score for distance metrics expected as they ignore user preferences and hence can edit features that are not preferred making the generated recourses infeasible under the user's evaluation cost function. We find that EMC with LS ourperrs all distance objectives on all cost-based metrics, 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 ($4.3) that allows COLS to efficiently search the solution space.
Q3. Robustness to Using Different Distribution for Training and Evaluation Cost Functions
Next, we test the robustness of our method in cases where the evaluation cost functions C for the users are not from the training distribution used in EMC, i.e. Derein # Drest- We set Derain Diic and use log- percentile shift cost. function from Actionable recourse (Ustun et al., 2019) as the evaluation cost function. The log-percentile shift cost function is defined as cost(f, x, y) = log( (r()( feature f across the population. This leads to a scenario where train and evaluation time cost functions are from a completely different distribution.
(-0r(0)) where Q, is the CDF of
In Table 3, we compare with our strongest baseline, Actionable Recourse (AR) (Ustun et al., 2019) which also uses the per-erceetilee shift cost function during training as an objective. Hence, we observe that the performance of AR improves by 6.49% and 4.46% on Adult- and COMPAS datasets respectively when using the log-percentile cost function during evaluation (sce Table 1). Morcover, we find that COLS and P-COLS still outperform the AR baseline by 17.26% and 11.87% on Adult-Income and COMPAS datasets respectively. We observe only a slight decrease in the performance of COLS and P-COLS even in this case of a complete distribution shift. This demonstrates the robustness of our method which arises from (1) This ability of the distribution Dinix to capture a wide varicty of plausible cost functions, and (2) The effective exploration of the search space when using COLS with EMC objective.
Q4. Robustness to Misspecification in cost-type weight
Design: Our Dmie 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 a robustness analysis where the users cost function has a different a mixing weight as compared to the Monte Carlo samples we use to optimize for EMC. This creates a distribution shift the user cost function distribution (Dtest) and the Monte Carlo sampling distribution (Drrain) used in EMC. We vary the user and Monte Carlo distributions a-weights within the range of 0 to I in steps of 0.2. At the extremes values of = 0, 1, the shifts are very drastic the underlying distribution changes completely. In the case when monte carlo weight is 0 and user a weight is 1 then Dtrain Dpere and Diest = Datep: simlarly for the other case we get Dtrain = Dstep and Drest = D pere- Please note that the distribution Datep and D ppere have completely different underlying principles and are two completely different distributions. Hence, the corners of the heatmap represent drastic distribution shifts.
Results: In Figure 2, we show a heatmap plot which demonstrates the robustness of our method. The color of the block corresponding to Monte Carlo alpha, One = x and the users alpha, Quser = y represents the
10

---

Published in Transactions on Machine Learning Research (04/2024)
Linear vs Percentile Cost Robustness
80
Monte Carlo a-
1.0
Methods Robustness to Distribution Shifts
100
78
COLS
0.8
Binned FS@1
99-
0.6
76
98-
97-
4
0.4
74
96
220
95
-72
0.00
0.05
0.10
0.15
0.20
0.25
0.30
Distribution Shift
0.0
0.0
0.2
0.4
0.6
0.8
1.0
User a-weight
In this plot show the fraction of users satisfied vs the distance between the train and test distributions. The results demonstrate that as the distance increases the performance drops a bit and then plateaus, which mcans that the method is ro- bust this kind of distribution shift. Please refer Section 5.2 for more details.
Figure 3:
Figure 2: This figure shows the performance of the method on FS@k when recourses are generated with Monte Carlo cost samples from a distribution with a-weight varying between and 1, where the user costs follow different a-weight values varying between 0, 1. Performance is robust misspecifi- cation of Refer to Section 5.2 for more details.
Traction of users that were satisfied when Ome I and Quser = y- This means that the user thought of costs only in terms of the Linear step involved but the recourse method used samples with only percentile- basedd cost, still the recourse set can satisfy almost the same number of users. In Figure 3, the corners correspond these extreme cases described above, the user satisfaction for the top left corner (Drrein D Dpere and Drest step)) is similar to the bottom left corner (Dirain Dteep and Diest DD Dstep). Similarly, things happen for the opposite case which is denoted by the top-right (Dtrain D Perc and Drest Dpero) and bottom-right (Dirain = Dstep and Drest Dpere) corners. This means that even when complete distribution shift occurs the performance user satisfaction remains similar. This can be attributed to the hierarchical step for user preference sampling in the procedure because the preference values can be arbitrary and they scale the raw percentile and linear cost hence the distribution models diverse types of transition costs.
This means that our methods are robust 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.
Q5. Are Solutions Robust to Misspecifted Feature Scores?
Design: In Section and Algorithm 4, we define the procedure our distributtinns use to generale feature scores p, assuming random FPs. However, in a population, FPs for users may be clustered form of subsets of foatures. For example, to increase income, subgroup of users might prefer to edit their work hours whereas another subgroup might prefer combination of occupation type and education level as it is casier to change the occupation after attaining a higher degree. Hence, the feature score p for users in a population might be clustered. This is a potential distribution shift in the types of feature scores we generate vs what might exist in real world. Therefore, we consider a scenario where Dtrain = Dmáz but Dzest has these clustered feature scores. Hence, the evaluation cost functions C# are generated from a different distribution.
For users in the Adult-Income data, we use COLS to optimise for EMC using Monte Carlo samples from Dmiz (Algorithm 5). To obtain user's evaluation cost functions that differ from this distribution, first generate 500 different feature subsets indicating which features are editable, where each subset corresponds to binary vector concentration representing user having specific preferences for some features over others (see Sec. 4.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 an l2 distance between the vector and nearest neighbor in the space of concentration vectors used to generate the recourses. We use the nearest neighbor because the most outlying concentration vectors are least likely to be satisfied by the recourse set. In other words, the likelihood that user is satisfied depends the
11

---

Published in Transactions on Machine Learning Research (04/2024)
minimum distance between their concentration vector and its nearest neighbor in the cost samples used recourse generation time. Therefore, when the minimum distance increases, there is greater distribution shift between the user's cost functions and those obtained from Dmig. Finally, we measure how many users are satisfied for a given degree of distribution shift.
Figure 3 shows a binned plot of FS@1 against our measure of distribution shift. We observe that as the distance between the distributions increases, the fraction of users satisfied decreases slightly and then plateaus. Even at the maximum distance we obtain, performance has only dropped about 3 points. This implies that our method is robust to distribution shift in the cost distribution in terms of which fcatures people prefer to edit. We attribute this to the fact that our Dmir (1) assumes random feature preferences that subsune these skewed preferences and (2) provides multiple recourse options, each of which can cater to different kinds of preferences. Hence, we achieve a good covering of the cost function space.
Results:
Q6. Fairness of Recourse Methods 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 induc- ing bias towards any particular group because it directly affects the life of users. We adapt existing fairness metrics for disparate impact across population subgroups (Feldman et al., 2015) for the recourse outcomes we study, which we denote by the Disparate Impact Ra- tio (DIR). Given a metric M, DIR is a ratio between metric scores across two subgroups. DIR-M M(S=1) We use either Cov or FS@1 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.
Table 4: Fairness analysis of recourse methods for Gender- based subgroups. DIR: Disparate Impact Ratio; M: Male, F: Female.
Method
Gender
FS81
Cov
DIR-FS
DIR-Cov
0.0
0.0
DICE
M
4.7
15.6
F
12.5
22.1
Ppoo-Eps
M
18.8
24.7
1.504
1.118
Face-Kun
M
28.9
21.5
32.3
36.3
0.718
0.89
Act. Recourse
F
58.8
58.7
0.881
0.959
47.4
56.3
Random
7.8
34.6
0.830
0.792
27.4
COLS
72.3
72.7
75.6
76.2
0, 0.994
0.992
P.COLS
F
76.5
80.2
1.004
1.0
76.8
We present the gender and race based subgroup results in Table 4 and Appendix Table 6 respectively. We observe that our methods are lypically more fair than baselines on both Gender and Race-based subgroups while providing recourse to a larger fraction of people in both subgroups. In particular, we find that our method achieves a score very close to 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 COLS does not depend on the data distribution, and (2) the use of diverse cost functions to generate recourse.
Additional Research Questions: We summarize the additional research questions from Appendix here:
1. We present the computational complexity and runtimes in Appendix A.3.2.
2. Using a larger compute budget improves the performance (Figure 4);
3. We can provide high-quality solutions to the user even with as few as 3 CFs (Figure 5);
4. We can achieve high FS@k with as few 20 Monte Carlo samples (Figure 7);
5. Our method works for other black-box classification models well (Table 11);
6. We also present some qualitative examples of recourses provided by our method in Table 8.
6 Discussion and Conclusion
Our novel method INSPIRE provides a way to incorporate FPs in the recourse generation and evaluation process. INSPIRE lays foundation for 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 our method achieves much higher rates of user satisfaction than comparable baselines and is robust to distribution shifts. Additionally, we provide Ethics and Reproducibility statement in Appendix A.1 and A.2.
12

---

Published in Transactions on Machine Learning Research (04/2024)
References
Carlos Aguilar-Palacios, Sergio Muñoz-Romero, and José Luis Rojo-Ålvarez. Cold-start promotional sales forecasting through gradient boosted-based contrastive explanations. IEEE Access, 2020.
Ifeoma Ajunwa, Sorelle Friedler, Carlos E Scheidegger, and Suresh Venkatasubramanian. Hiring by algo- rithm: Predicting and preventing disparate impact. Available at 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-148 2021.
Alexandra Chouldechova, Diana Benavides- Oleksandr Fialko, and Rhema Vaithianathan. A case study of algorithm-assisteed decision making in child maltreatment hotline screening decisions. Tn Confer- ence on 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 knowledge discovery and data mining, pp. 179-188, 2015.
Susanne Dandl, Christoph Molnar, Martin Binder, and Bernd Bischl. Multi-objective counterfactual expla- nations. In Thomas Bäck, Mike Preuss, André Deutz, Hao Wang, Carola Doerr, Michael Emmerich, and Heike Trautmann (eds.), Parallel Problem Solving from Nature -PPSN XVI, pp. 448 469, Cham, 2020.
Springer International Publishing. ISBN 978-3-030-58112--1
Amit Dhurandhar, Yu Chen, Ronny Luss, Chun-Chen Tu, Pai-Shun Ting, Karthikeyan Shanmugam, and Payel Das. Explanations based 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://archive. ics. uci. ccu/mn/dataaset//adda
Michael Feldman, Sorelle A. Friedler, John Moeller, C. Scheidegger, and S. Venkatasuuramaanian 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. Vijitbenjaronk, Been Kim, and Joydeep Ghosh. Towards real- istic individual recourse and actionable explanations in black-box decision making systems. International 2019. Kentaro Kanamori, Takuya Takagi, Ken Kobayashi, and Hiroki Arimura. Dace: Distribution-awann counter- factual explanation by mixed-integer linear optimization. In Christian Bessiore (ed.), Proceedings of the -witty-Ninth International Joônt Conference on Artificial Intelligence, IJCA1-20, pp. 2855 2862. Inter-
Conference Learning Represendations; Workshop on Safe MT,,
national Joint Conferences Artificial Intelligence Organization, 7 2020. doi: 10.24963 n..24963/jjcai..20 2020/ URL htt.httts://do org/10 24963/29633344 /it//////jaaaa////// 2020/395. Main track.
Amir-Hossein Karimi, G. Barthe, B. Balle, and Isabel Valera. Model-agnostic counterfactual explanations for consequential decisions. International Conference on Artificial Intelligence and Statistics, abs/ Abs/1195.11199, 2020a.
mosr-Hossein Karimi, Gilles Barthe, Bernhard Schölkopf, and Isabel Valera. A survey of algorithmic recourse: definitions, formulations, solutions, and prospects. CoRR, abs/2010.04050, 2020b. URL https: org/abs/2010. 04050.
Amir-Hossehn Karimi, Bernhard Schölkopf, and Isabel Valera. Algorithmic recourse: from counterfactual explanations to interventions. FAceT, 2020c.
13

---

Published in Transactions on Machine Learning Research (04/2024)
Amir-Hossein Karimi, Julius von Küggelgen, Bernhard Schölkopf, and Isabel Valera. Algorithmic recourse under imperfect causal knowledge: a probabilistic approach. Advances in Neural Information Processing Systems, 2020d.
A. Kulesza and B. Taskar. Determinantal point processes for machine learning. Found. Trends Mach. Learn., 5:123-286, 2012.
Jeff Tarson, Surya Mattu, Lauren Kirchner, and Julia Angwin. https///glhhbbcco///ppaalla///pp analysis, 2016.
Melanie Mitchell. An introduction genetic algorithms. MIT press, 1998.
Hans Mittleman. Mixed integer linear programming benchmarks (miplib 2010). http://plato. asu. edu/ ftp/milpc.hean html, 2018.
Ramaravind K Mothilal, Amit Sharma, and Chenhao Tan. Explaining machine learning classifiers through diverse counterfactual explanations. In Proceedings of the 2020 Conference on Fairness, Accountability, and Transporency, pp. 607 617, 2020.
Martin Pawelczyk, Klaus Broelemann, and Gjergji Kasneci. Learning model-agnostic counterfactual explana- tions for tabular data. In WWW, pp. 3126-3132, New York, NY, USA, 2020. Association for Computing URL https://doi. wtteeoo...rr.... 1044//
Machinery. TSBN 9781450370233. doi: 10. 10.1145/333644233330000 33.0000 3366423. 33864277.3
Martin Pawelczyk, Sascha Bielawski, Johan Van den Heuvel, Tobias Richter, and Gjergji. Kasneci. CARLA: A python library to benchmark algorithmic recourse and counterfactual explanation algorithms. In Thirty- fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 1), 2021. URL https://openreevier www.:etoooom.ddddiiiiaaaea..
Mare Pirlot General local search methods. European Journal of Operational Research, 92(3):493 511, 1996. ISSN 0377-2217. doi: https://doo..org110.000 (0000000000007772227700001100000 URL betps:///wx.
Brett Poulin, Roman Fisner, Duane Szafron, Paul Lu, Russell Greiner, David S Wishart, Alona Fysho, Brandon Pearcy, Cam MacDonell, and John Anvik. Visual explanation of evidence with additive classifiers. In Proceedings Of The National Conference On Artificial Inlelligence, volume 21, pp. 1822. Menlo Park, CA; Cambridge, MA; London; AAAI Press; MIT Press; 1999, 2006.
Rafael Poyiadzi, Kacper Sokol, Raul Santos- Rodriguez, Tijl De Bie, and Peter Flach. Face: Feasible and actionable counterfactual explanations. Tn Proceedings of the AAAT/ACM Conference on AT, Ethics, and Society, AIES '20, pp. 344 350, New York, NY, USA, 2020. Association for Computing Machinery. ISBN 00555//335677.33777555
9781450371100. doi:
URL https: org/10. 1145/3375627, /3 3375850.
Hamed Rahimian and Sanjay Mchrotra. Distributionally robust optimization: A review. arXiv preprint
arXiv:1908.0560 2019.
Yanou Ramon, David Martens, Foster Provost, and Thcodoros Evgeniou. Counterfactual explanation algo- rithms for behavioral and textual data. Advances in Dala Analysis and Classificution, 2020.
Peyman Rasouli and Ingrid Chieh Yu. Care: Coherent actionable recourse based on sound counterfactual explanations, 2021.
Kaivalya Rawal and Himabindu Lakkaraju. Beyond individualized recourse: Interpretable and inter- active summaries of actionable recourses. In H. Tarochelle, M. Ranzato, R. Hadsell, M. F. Bal- can, and Н. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 12187 12198. Curran Associates, Inc., 2020. URL https://proceeeings.. http:://pppoeeeengs..rrr....... wwtpaippcccppppp///2///eeeeee 6e677500976677733222ccfffff488 Paper. pdf.
Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. Anchors: High-precision model-agnostic explana- tions. In AAAT Conference Artificial Intelligence, 2018.
14

---

Published in Transactions on Machine Learning Research (04/2024)
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. Aduances in Newral Information Processing Systems, 2021.
Naeem Siddiqi. Credit Risk Scorecards: Developing and Emplementing Intelligent Credit Scoring, volume
John Wiley Sons, 2012.
Berk Ustun, Alexander Spangher, and Yang Liu. Actionable recourse in linear classification. In Proceedings of the Conference on Fairness, Accountability, and Transparency, FAT* '19, pp. 10-19, New York, NY, USA, 2019. Association for Computing Machinery. ISBN 9781450361255. doi:
URL https://doi http////oo.orooo./// 1145/3287560 3287566..
Suresh Venkalasubramanian 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. In European Commission, 2018.
Julius von Kügelgen, Amir-Hossein Karimi, Umang Bhatt, Tsabel Valera, Adrian Weller, and Bernhard Schölkopf. On the fairness of causal algorithmic recourse. NewrIPS AFCI Workshop, 2020.
Sandra Wachter, B. Mittelstadt, and Chris Russell. Counterfactual explanations without opening the black box: Automated decisions and the gdpr. Cybersecurity, 2017.
A Appendix for INSPIRE: Incorporating Diverse Feature Preferences in Recourse
A.1 Ethics Statement
We hope that our recourse method is adopted by institutions socking to provide reasonable paths to users for achieving more favorable outcomes under the decisions of black-box machine learning models or other inscrutable models. We see this as a "robust good," similar to past commentators Venkatasubramanian & Alfano (2020). Below, we comment on a few other ethical aspects of the algorithmic recourse problem.
First, we suggest that fairness is an important value that recourse methods should always be evaluated along, but 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 result, any recourse method will fail to identify an equitable set of solutions for the population. That said, recourse methods can still be designed to be more or less fair. This much is evident from our varying results on fairness metrics using a number of recourse mothods. 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, we risk blaming the recourse algorithm for the bias of model, or vice versa.
Additionally, there are possible dual-use risks from developing stronger recourse methods. For instance, malicious actors may use recourse methods when developing models in order to exclude certain groups from having available recourse, which is essentially a reversal of the objective of training models for which recourse is guaranteed (Ross et al., 2021). We view this use case as generally unlikely, but pernicious outcomes are possible. We also note that these kinds of outcomes may be difficult to detect, and actors may make bad-faith arguments about the fairness of their deployed models based on other notions of fairness (like whether or not model has access protected demographic features) that distract from an underlying problem in the fairness of recourses.
A.2 Reproducibility Statement
To encourage reproducibllity we provide our source code, including all the data pre-processing, model training, recourse generation, and evaluation metric scripts supplementary material. The details about
15

---

Published in Transactions on Machine Learning Research (04/2024)
Table 5: Table containing data statistics and black-box model details. The binary version of the datasets
are take from (Pawelezyk et al., 2021) whereas the non-binary version are taken from (Mothilal et al., 2020).
Adult-Tncome Binary
COMPAS Binary
Adult-Tncome
COMPAS
# Contimuous features
3
# Categorical features
12 Will Recidivate Won't Recidivate
Undesired class
< 50k
Will Recidivate
I 50k
Desired class
>. 50k
Won't 't Recidivate 1415 1415/229/ 2229/299999/
>- 50k
Train/ven Sraai/val/ane /test /ttst
20088/ /2338/749
13172/ (3172/156//745
2491/705/444
Model Type
(N 20)
(N 20) 69%
ANN 20)
ANN(2, 20) 61%
Val Accuracy
82%
81
the datasets and the pre-processing are provided in Appendix A.3.1. We also provide clear and concise Algorithms 5, 2, for our cost sampling procedures and our optimization method COLS in Algorithm 1. Additionally, we also provide formal proof of the Theorem 4.1 stated in the main paper in Appendix B.2.2 along with the constructive procedure for the proof provided in Algorithm 1.
A.3 Experimental Setup
A.3.1 Datasets and Black- Box Model
In our experiments, we have two versions of the dataset, one with binary categorical features, whereas the other with non-binary categorical features. In the main paper, we show results on the binarized version (Table 1) as an important baseline, Actionable Recourse (Ustun ct al., 2019), operates with binary categorical leatures.* 3 The data statistics for all the datasels 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 mutable or conditionally mutable depending constraints can be incorporated into the methods by providing a schema of feature mutability criterion. Our black-box model is a multi-layer perceptron model with 2 hidden layers trained on the trained set and validated on the dev set. The accuracy numbers are shown in Table 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 method can operate with any type of model, the only requirement is the ability to query the model for outcome given a user's state vector.
semantics. These
A.3.2 Computational Complexity:
COLS is a local search-based method and runs for O(S)) iterations for each user to generate the recourse set, where B is the budget (see section 5.1 Baselines). The complexity of the cost optimization step in COLS is O(SS|2 * M) per iteration. Values of |S| and M as low 3 and 10 respectively work well in practice (sce Appendix B.2 and Figure 5, 7). Finally for the current implementation the wall clock time on the adult dataset for each user with ||| = 10, M = 100, B = 5000 setting is COLS- = 20s, Random = 7.5s, DICE = 7.5s, AR = 11s Face-knn = 7s, Saace-Ess = 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.
A.3.3 Recourse Generation and Evaluation Pipeline
To approximate the expectation in equation 3, our algorithm samples multiple cost functions [ Dtrain, which are used in EMC to generate the recourse set for the user. In the generation phase, we use Equation as our objective. Note that, this objective promotes that the generated recourse set contains at least one good CF for each of the cost samples, hence this set satisfics large variety of samples from Derain- This is schieved via minimizing the mean of the minimum cost incurred for each of the Monte Carlo samples
The binary datasets can be downloaded from http:///ghhaabccm////rrreoeee/ee whereas the non-binary data can be found htips:/ http://.ttthhh.//.o/. httgghhhw.ooo////teeeeemm///////
16

---

Published in Transactions on Machine Learning Research (04/2024)
User Satisfaction vs # Counterfactuals
User Satisfaction vs # black-box access
80
80
FK
FK AR
AR
60
FS@1
FS@1
COLS P:COLS
P-COLS
20
1
2
3
10
20 30
500
1000
2000
3000
5000
10000
Number of Counterfactuals |s|
Budget
Figure 5: Figure showing the performance of differ- ent recourse methods as the the number of counter- facuals to be generated increased. These are the average number across 5 different runs along with standard deviation error bars. We see that there is monotonic increase in the fraction of users satis- fied as the size of the set increases. We also observe that most of the performance can be obtained with a small set size. Please refer to Section A.4 for more details.
Figure 4: Figure showing the performance differ- ent. recourse methods as the Budget increased. These are the average number across 5 different runs along with the standard deviation error bars. For some methods the standard deviation is very low hence not visible as bars in the plot. It can be seen that as the budget increases the performance of COLS and P-COLS increases. Please refer to Section A.4 for more details.
(Robert & Casella, 2010). Equivalently, the objective is minimized by set of counterfactuals S where for each cost function there exists 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 which is to be provided to the users as recourse options. Given this set S,, in the evaluation phase, we use the user's simulated evaluation cost functions which are not available in the generation phase to compare different methods, to compute the cost incurred by the user MinCost(s S; and calculate the metrics defined in the Section 5.1.
A.4 Additional Research Questions
Q7. Does Method Performance Scale with Available Compute?
Design: In this experiment on the Adult-Income dataset, we measure the change in performance of all the models as the number of access to the black-box model (budget) increases. Idcally, 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 a random subset of 100 users for 5 independent runs and then report the average performance with standard deviation-baser 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 ad- ditional black-box access to improve the performance. Other methods like AR and Face-Knn also show performance improvement but method COLS and P-COLS consistently upper-bound their performance. Our method satisfies approximately 70% of the user with small budget of 500 and quickly starts to saturale around a budget of 1000. This suggests that our methods are suitable even under tight budget constraints as they can achieve good performance rapidly. For example, in a real-world scenario where the recourse method is deployed and has to cater to a large population, in such cases there might be budget constraints imposed onto the method where achieving good quality solution quickly is required. Lastly, for DICE and Random search the performance the FS@1 increase by very small margin and
17

---

Published in Transactions on Machine Learning Research (04/2024)
User Satisfaction vs # Monte Carlo Sample
80
COLS
75
Table 6: Fairness analysis of recourse methods for subgroups with respect to Race. DIR: Disparate Impact Ratio; W: White, NW: Non- White (Section 5.2).
60-
Method
Race
FSa1
Cov
DIR-FS
DIR-Cov
55
DICE
NW
W
3.1
0.0
10.4
0.0
10
100 200
300 500 1000
Face-Eps
W
17.8
7.7
26.0
12.7
2.312
2,077
Num MC Samples
Face-Kun
NW
12.7
25.4
2.228
1.425
28.3
Table Figure showing the performance of the COLS method as the number of Monte Carlo samples increase. These are the av- erage number across 5 different runs along with standard deviation error bars. There is a steep increase and then the performance saturates. This implies that in practice we do not need a large number of samples converge to the higher user satisfaction. Re- fer to Section A.4 for more details.
Recourse
NW
W
51.2
46.5
51.9
58.0
1.001
1.056
Random
W
7.7
4.9
31.1
25.9
1.571
1.076
COLS
NW
67.6
71.1
1.089
1.022
73.6
76.9
P-COLS
NW
72.5
74.6
1.07
1.092
77.6
81.5
then stays constant as these methods are trying to optimize for different objectives which don't align well with user satisfaction demonstrated in Section 5.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 improved. In this experiment on the edult-Income dataset, we take a random subset of 100 users and fix the budget to 5000, Monte Carlo cost sample is set to 1000 and then vary the size of the set S in the set 21, 5, 10, 20, 30). We restrict the size of the set to a maximum of 30 as beyond a point it becomes hard for users to evaluate all the recourse options and decide which one to act upon. We run 5 independent runs for all the data points and plot the mean performance along with standard deviation error bars. In Figure 5, we plot the fraction of users satisfied @1 as the size of set S is increasod.
Result:: We observed that COLS and P-COLS monotonically increase the FS@1 metric as [S] increases from to 30. This is consistent with the intuition behind our methods (See Figure 1, section 4.2, A.3.3 for more details). It is fundamental property of our objective that as |S] increases towards M which is 1000 in this case, then the quality of the solution set should increase and reach the best possible value that can be provided under the user's cost function. We note empirically that smaller set size |S] between 3 to 10 is enough in most practical cases to reach close to maximum performance. Additionally, even with [S] E (1,2,3} our methods significantly outperform all the other methods in terms of the number of users satisfied. This property is useful real-world scenarios where the deployed recourse method can provide as little as options while still satisfying large fraction of users. Additionally, we also see improvement in the case of AR and Face-Kmn methods |S| increases. Note that Randoms Search's performance doesn't 't change we increase the set size because the method doesn't take local steps from the best set and samples random points from very large space, hence it is much harder to 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 incrcasing the number of Monte Carlo samples on the performance of our COLS method. We take a random subset of 100 users, a budget 5000, [S] = 10. We vary the number of Monte Carlo samples (M) in the set {1,5, 10, 20, 30, 100, 200, 300, 500, 1000)
18

---

Published in Transactions on Machine Learning Research (04/2024)
Table 8: 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 feature copital 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 sleps 7-8-9-10, hence the cost. for that recourse not the lowest but still relatively low. Whereas, the recourse suggesting smaller changes Capital Loss which the second most preferred feature has the lowest cost for the user.
see that user highly prefers the
Feature Name
State Vector
Editable Features
Preference
Recourses
Cost
Age
No
Education-Num
Workelass
10
Private
No
No
(Capital Loss: + 1)
0.009
Martial-Status
Married
No
Occupation
Other
Yes
0.055
Relationship
Husband
No
(Ovcapation: Other + Manages)
0.378
Race
White
No
Gender
Male
No
Capital Gain
0
No
Capital Loss
Yes
0
(Occupation: Other + Manager
0.387
Work Hours
No
Capital Loss: +
Country
US
No
Age
No
Workelass
Private
No
(Capital Loss: ++1)
0.071
Education-Nunt
Yes
0.537
Martial-Status
Married
No
Occupation
Other
No
(Capital Gain: 0 + 1)
0.106
Relationsip
Non- Has-Hu
No
Race
White
No
Gender
Female
No
[Education-Num: 10)
0.187
Capital Gain
Yes
0.078
Capital Loss
0
Yes
0.240
# Work Hours
32
Yes
0.142
(# Work Hours: 32 - 70)
0.695
Countey
No
and compute the user satisfaction. We ran 5 different runs with different Monte Carlo samples and show the average FS@1 along with the standard deviation in the Figure 7.
Results: We observe that as the number of Monte Carlo samples increases, the performance of the method on the F metric monotonically increases. This supports the intuition underlying our mothod (see Figure 1). That is, given a user with a cost function С as we get more and more samples from the cost distribution Dtrain the probability of having a cost sample similar to C increases and hence the fraction of satisfied users increase. is important to note that empirically the method's performance approaches maximum user satisfaction with as low as 20 Monte Carlo samples. In real-world scenarios, where the deployed model is catering to 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 8, we show a few examples 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 on Non Binary Dataset?
In Table 9, show the results the non-binary version of the dataset. We observe similar performance on and trends in these results as well. COLS and P-COLS performs the best in terms of user satisfaction.
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 10) and when we change the model family to logistic regression classifier (Table 11). These obtained results have similar trends and demonstrate the effectiveness and robustness of
19

---

Published in Transactions on Machine Learning Research (04/2024)
Table 9: Table comparing different recourse methods across various cost and distance metries on Non-Binary versions of the datasets (Section A.h. numbers reported averaged across 5 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 &o = 1. PAC: Population Average Cost. Cov: Population Coverage. For all the metrics higher is better except for PAC where lower is better.
Data
Method
Metries
Cost Metrics
Distance Metries
FS0(
PAC(()
Cov
Div
Prox
Spars
Val
DICE
6.28
1.45
27.01
53.01
57.02
47.80
86.20
Adult-Income NB
Random
0.08
2-22
17.41
70.35
33.32
22.45
75.71
COLS
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.58
82.38
69.44
99.86
Random
1.31
1.87
21.76
54.10
42.34
67.82
COLS
67.34
0.31
68.11
20.53
85.47
82.34
95.97
P-COLS
0.35
72.08
82.88
91.83
Table 10: Table comparing different recourse methods across various cost and distance metrics for black- box model with different seed but belonging to the same model lamily. The numbers reported are averaged across 5 different runs.
Data
Method
Metries
Cost Metrics
Distance Metrics
FS@1
PAC(J)
Cov
Div
Prox
Spars
Val
DICE
2.70
1.24
7.10
3.80
66.20
47.30
97.80
Face- Face-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
Recourse
46.55
0.58
53.82
19.07
74.33
73.25
80.72
Random
5.71
1.42
55.10
39.30
78.73
COLS
75.12
0.36
77.40
25.43
81.00
77.70
98.28
P-COLS
75.76
0.38
79.14
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-Knn
6.80
6.80
60.30
100.00
COMPAS
Act. Recourse
56.24
0.45
58.48
9.72
80.12
73.62
39.10
Random
27.41
0.78
35.70
41.76
58.14
33,06
49.31
COLS
77.08
0.24
77.90
76.90
68.87
95.78
P-COLS
78.32
0.24
79.02
29.02
77.88
70.08
92.10
methods COLS and P-COLS which consistently satisfy cover and satisfy more users with low average population costs. In Table 10, we show the results when we train another black-box model with different seed to see the effect of having a different trained model from the same model family.
Q13. Additional results for different values of à in FS@k In Table 12, we report the fraction of satisfied user metric FS@k for four different values of k E 1,,5,1,2.3) 1,2.3). These results extension of the results presented in Table 1.
B Appendix- Objective and Optimization
B.1 Proposed Method
B.1.1 Other Objectives
To obtain feasible counterfactual set, past. works have used various objective terms. We list objectives below from methods we compare with.
DICE (Mothilal al., 2020) optimizes for a combination of Distance Metrics like diversity and prozimity. They model diversity via Determinantal Point Processes (Kulesza & Taskar, 2012) adopted for solving subset
1.
20

---

Published in Transactions on Machine Learning Research (04/2024)
Table 11: Table comparing different recourse methods across various cost and distance metrics for logistic regression
black-box model. The numbers reported are averaged across 5 different runs.
Data
Method
Metrics
Cost Metries
Distance Metrics
FS@1
PAC(()
Cov
Div
Prox
Spars
Val
D
1.30
1.47
7.10
6.50
61.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
$3.98
67.80
100.00
Adult-Income
AR
44.40
0.62
52.62
21.74
74.00
72.92
87.58
R
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
0.00
0.00
11.10
63.10
29.20
100.00
FE
6.30
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
R
28.76
0.77
36.96
43.22
56.22
32.00
82.10
COLS
87.88
0.18
87.88
31.92
76.93
71.63
89.33
P-COLS
89.25
0.17
89.25
28.17
81.13
74.73
91.62
Table 12: Cost metrics for additional & values in FSOk for the results presented in the main Table 1.
Data
Method
Cost Metrics
FS80.5
FS@1
FS@2
FS03
DICE
0.4
2.47
6.9
8.23
Pace-Eps
7.32
15.23
22.57
22.6
Face-Knn
11.08
25.3
34.82
Adult-Income
Act. Recourse
28.03
49.93
56.78
56.85
Random
0.82
6.27
28.5
31.68
COLS
53.4
72.57
76.05
76.07
P-COLS
53.42
75.82
79.18
79.2
DICE
0.2
0.4
0.4
0.4
Face-Eps
10.4
12.2
12.2
12.2
Face-Knn
10.4
12.2
12.2
COMPAS
Act. Recourse
42.47
65.8
66.6
66.6
Random
7.85
29.95
39.2
39.2
COLS
73.07
82.23
82.23
82.23
P-COLS
74.33
83.73
83.73
83.73
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), whereKij = 1 disl 83)
Here, disl(8;, 8;) is the normalized distance metric as defined in Wachter et al. (2017) between two state vec- tors. Prozimity defined in terms the distance between the original state vector and the counterfacutals, proz(x, = N |Sl dist(æ, S;), where S is counterfactual.
2. Actionable Recourse (Ustun et al., 2019) work under the assumption that all features have equal preference scores for all the users. They define cost function based on the log-percentile shift is given by,
Q, +a,)
cost(s a;
Σ log 1 Q5(s))
JEJA
21

---

Published in Transactions on Machine Learning Research (04/2024)
Algorithm 2 Sampling Cost Functions from D Perr
Input: State vector 8, Feature Scores p
Output: Percentile based Transition Cost functions C. function Pe None)
forall F do
// #; value of feature Jt in
if pf: then
((f(,8,,)) = C(fi, 8;) =0
else
if Js ordered then
if can only increase then
get Percenttt))))))) - get getPerccntile(s))
Vr > 8t
s;,
0
4/ 84
Az <
else if ft can only decrease then
gel geleeeeentile(s)) - ggerPeeeeliilenn
Yr < 8:
81,
Va
else if fi can both increase or decrease then
getPercentile(()) - getPercentile(s.)
Vz >>
C(fa, 0
VE 8t
(getPercentile(ss) getPercentile(x))
Væ 58
else if Si wnordered then
S(f..s,..) = Uniform((, 1) if is not None then
((S1,88,)) + C(J, 8...) * *11- p())
end
return C end
where (.).) is the cumulative distribution function of 8y in the target population, JA is the set actionable features and aj the action performed on the fcature j.
B.2 Optimization Methods
We assume that we have a dataset with features F = fe.. Each feature can either be continuous Jron C. F categorical Feat с F. Each continuous feature from takes values in the range frmin, mmaa], which we discretize to integer values. For a continnous feature fi, we define the rango Q {k Z: : E Iyminn .]mer]] [nmr), and for categorical feature f:, we define it as Q(A)) = (qf' . ...., where of are the states that feature fi can take. Features can either be mutable (FMM,, conditionally mutable (FrT), or immutable (FO), according to the real-world causal processes that generate the data. Mutable features transition from between any pair of states in Q(A); conditionally mutable features can transition between pairs of states only when permitted by certain conditions; and immutable features cannot be changed under any circunstances. For example, Race is an immutable feature (Mothilal et al., 2020), Age and Education are conditionally mutable (cannot be decreased under any circumstances), and number of work hours is mutable (can both increase and decrease). Lastly, while contimuous features inherently define an ordering in its values, categorical features can either be ordered or unordered based on its semantic meaning. For instance, Age is ordered feature that is conditionally mutable (can only increase).
Notation:
dd ....!!...
22

---

Published in Transactions on Machine Learning Research (04/2024)
Algorithm 3 Sampling Cost Functions from D Dstep
Input: State vector 8, Feature Scores
Output: Number of Steps based Transition Cost functions C. function StepCost(s, p None)
for Ji F do
if pl: = 0 then C(f., = 0c 81,
else
if Ja is ordered then
if fo only increase then Ky A2 Ry 1>84
Vr > 85.
St,
Ar 8
Vx < 96
else if Ji can only decrease then Ky 9<2AA Ky vca)]l
Yr < 8 Vr 8i
81,
0
Vr > 8;
else if ft can both increase or decrease then
Hy 9>8AA55H
Vo 8i
R8 938.
C(fi,
Vr 84
Ky DSHANZZ R8 9-8.
Vr < 8i
else if Si unordered then C(fi, = Uniforrm((,1) if is not None then
&(1,) + C(S,,),)) .). * (1 - p):)
end return C end
Algorithm Sampling Random Feature Scores.
Output: Feature Scores p. function sample/FatuurSScrrs(,,, = O.P = None)
if Fp is O then Fg RondomSuuscc (Fmutable)
if None then concentration if f Jo else for f in F.
p ~ Divichlef(conenntration)
return P end
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 cost samples that are a linear combination of percentile shift cost (Ustun et al., 2019) and linear cost, where the weights of this combination Percentile shift cost for ordered features is proportional to the change in feature's percentile associated with the change from an old feature value to a new one. E.g, if a user is asked to increase the nunber of work hours from 40 to 70, then given the whole dataset, we can estimate the percentile of users working 40 and 70 hours a week. The cost incurred then proportional 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 current state to the final state. F.g., if is asked change their
user-specifie
23

---

Published in Transactions on Machine Learning Research (04/2024)
Algorithm Sampling Cost Functions from D Pmiz.
Input: State a, feature p, Optional: cost-type mixing weight Output: Cost functions
function sampleCost(s, p, Nonc)
a None then
Uniform(0,) 1)
Get Step and Percentile cost. C(Lin) LinCost(a,
((Pere) PerCost(s, p)
((Mri)) ((Lin) return ((Msx))
a) C(Pene)
end
Algorithm Algorithm for Theorem 4.1
Input: C² C CERO NxM CxRN matrices containing the costs with respect to all cost samples..
Output: B RNNN, matrix containing the benefits of replacing pairs from Staat x S
function computeBenefits((C C)
Initialize
B BERNNN +-
// Find the indices of the best and second best counterfactual in gheat for each of the N cost function.
6' R-M arg max, C
62 E RM = arg second max; C
// Iterate
all pairs of counterfactuale.
forall p,q E [N] [N] do
// Iterate over cost functions for which pth counterfactual in Sheet has the minimum coat.
forall r E {i [M] b = p} do
if C
pr > Cp then
/1 This replacement reduces the cost of Sbeat by of Cyr.
B Bpg Ch Cgr
clse
/1 cb b2 of second best counterfactual gbest ,th cost function.
B Bpg
h pr
min( (Cgn Ch.
end
end
return B
end
24

---

Published in Transactions on Machine Learning Research (04/2024)
Listing 1: Code to Compute Benefits
def computeBenefita (self, best metrica, curr _mmerricc:::
best_idx_per, pest best_metrics test_ second_best.ce _tt_bee__dd___e_eceee_ benefit_matrix = np. ze.zeros( (len for bb, best best_met met anuterate
best_metrics.. argsort [1]
len len(cur__merris))
for cc, curr_met in couneraat(curr_nttrriie
ben
for j in np. ap.where (wteooeee__d_pe__eoeeee sei__dd__x____eee == bb) [o]:
if best_met(j) > curr __rr_mm[]]]] [j]:
ben +- (best_met) pest_met[oe [j] curr_met[]]] [j])
else:
ben (best_ met [j] (inr [[]]rr___mt[],,, best cert_metricssie [second best_ ceatt_dx__eerr___ wwwpppeeerroolpeeeeeeeeeeeeeeeee [j]] ( (j]))
benefit_ cecefit_matiixliee [bb, cc] return tanefitmatrix
Listing 2: Code for getting pair to replace
def getReplaceIdx (benefit_matrixx List [Tuple]:
# If there is no benefit on any replacement then just return an empty list. (benefit matrix tbenefit_matrix return 0
sum 0:
else:
Greedily replace the current cfs with of from the best-so-far set that leads to the most benefit. Note that this can be a sub-optimal replacement strategy as it's greedy but works well in practice.
org Indices in the best-so-far cfs set.
Indices of the current set.
Iterate each of the current cfs for ca in range (bweeffttmatrrianee
# Iterate over from the best-so-far set descending order of benefit from replacement.
idx in benefit_matrin If best-so-far of has not already been replaced and has positive benefit then indices to org new list.
ec] argsort [::-1]:
if idx not in org and benefit mnnffit_matrixiddy ec] 0:
org. arg.append
(c))
create a list of tuples of (org, new) and return. return (zat(ziporg, new))
education level from High-school to Masters then there are two steps involved the process. First, they need to get a Bachelors degree and then a Masters degree which case, the user's cost is proportional to 2 because of the two steps involved in the process.
B.2.2 Merging Counterfactual Sets
When searching for good solution set, it would be useful to have the option of improving on the best set we have obtained so far using individual counterfactuals in the next candidate set we see, rather than waiting for new, higher-scoring
come along. While optimizing for objectives like diversity, which operate over all pairs of elements in the set, it is computationally complex to evaluate the change in the objective
25

---

Published in Transactions on Machine Learning Research (04/2024)
function if one element of the set is replaced by a new one. To evaluate the change in objective in such cases, we need iterate over all pairs of element in the best and the candidate set and then evaluate the objective for the whole set again. The iteration over both the sets here is not the hard part but the computation that nceds to be done within. For our objective, we can compute costs for individual recourses rather than sets, meaning we can do a trivial operation to compute the benefits of each pair replacement. But, if we wanted to do this with diversity then for each pair of replacement we need to compute additional S distances for each replacement because the distance of the new replace vector needs to be computed with respect to all the other vectors, for each iteration of the nested loop. This quickly makes it infeasible to improve the best set by replacing individual candidates with the best set elements. However, for metrics where it is easy to evaluate the effect of individual elements on the objective function, we can easily merge the best set and any other set St from time / to monotonically increase the objective function value.
In our objective function, FMC, we can compute the goodness of individual counterfactuals with respect to all the Monte Carlo samples (Robert& & Casella, 2010). Given a set of counterfactuals we can obtain a matrix of incurred cost C E RN which specifies the cost of each counterfactual for each of the Monte Carlo samples. We can use this to update the best set Shest using elements from the perturbed set S, at time t. This procedure is defined in algorithm 6. It iterates over all pairs of element in 8; E Shest and 8, E S; and computes the change that will occur in the objective function by replacing + sj. Note that we are not recomputing the costs here. Given Shest, St, C³ and C, we can guarantee that we will update the best set Shest in a way to improve the mean of the minimum costs incurred for all the Monte Carlo samples. This is shown in algorithm 6 and the monotonicity of the EMC objective under this case can be formally stated as, Theorem B.1 (Monotonicity of Cost- Dosti-Optimized Local Search Algorithm). Given the best set, Stoett E &Nd, the condidate counterfactual at iteration t, S₁ E IR the matrix C' E RNN and C'E R.NM containing the incurred cost of each counterfactual in Stinet and S, with respect to all the M sampled cost functions [C there always erist a Shest constructed from Staat and S, such that
EMO(s., s. Shest, (C.).M)) S EMC(s,, Steat: MM
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 6 for a constructive procedure for this proof, which is more intuitive to understand.
We start off by noting that each element of City is the cost of the 8th counterfactual s in the best set Stee with respect to the cost. function C, given by Cost( si: Cy). Similarly Ci₃ Cost 81; Cz) where 8; is the ith candidate counterfactual. Note that, the EMC is the average of the MinCost with respect to all the sampled cost function Cj. What this mcans is that given a pair of counterfactual from Steat SS and for cach Cj. we can compute the change in the MinCost which we describe later. These replacements can lead to an increase in the cost with respect to certain cost function but the overall reduction depend on the aggregate change over all the cost functions. Given this, for each replacement candidate pair in Steet x S,, we can compute the change in EMC by summing up the changes in the MinCost across all cost functions C₁ : 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 Sheat, if no pair has a positive benefit then we keep set Steat = Spest, 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 Cs, first we find the counterfactual in Stey with the lowest and second lowest cost which we denote by si, and st 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 sf which has the lowest cost for C₁ with a new candidate counterfactual 8,, there are two cases. Either, Ch > Cit or Ct,, < Cij. In case when the candidate s; has lower cost for C2 than Ch i.c. Ch > Cijy then the replacement reduces the cost by Ci Cij- In case when the candidate cost for Cy. Cty, is higher than the lowest cost in the best set Ch i.e. Ch, S City it means that this replacement will increase the cost for C, by ch,- - min( Cijy C.y)). Here, Ch,y is the second lowest cost counterfactual for C. Note that the change in this case will be negative and also depend the second best counterfactual
26

---

Published in Transactions on Machine Learning Research (04/2024)
because once the st, is removed from the set, the best cost for C, will cither be for sf, or St, hence take the minimum of those two and then take the difference as the increase in cost. Please refer to Algorithm 6 for cognitively easier way to 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-basse based optimization in this continuous space while opti- mizing for objective defined in Section B.1.1. Their final objective function is defined as
1
A1 (Jss(
C(x) arg min Cinon R
dist (c) X2 dpp diversity(et,...... .c)
where C; is a counterfactual, A is the number of counterfactuals, f(.) is the black box ML model, yloss(.) is the metric which minimizes the distance between models prodiction and the desired outcome y- dpp (ip__iiicy)tt()) is the diversity metric as defined Section B.1.1 and λ and X2 are hyperparameters to balance the com- ponents in the objective. Please refer Mothilal al. (2020) for more details.
2. FACE (Poyiadzi et al., 2020) operates under the idea that to obtain actionable counterfactuals they need to be connected to the user state via paths that are probable under the original data distribution aka high-density path. They construct two different types of graphs based on nearest neighbors (Face-knn) and the e-graph (Face-Eps). They define geodesic distance which trades-off between the path length and the density along this path. Lastly, they use the Shortest Path First Algorithm (Dijkstra's algorithm) to get the final counterfactuals. Please refer (Poyiadzi al., 2020) for more details.
3. Actionable Recourse (Ustun et al., 2019) tries find an action set for 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 fcasibility and actionability with respect to features. They optimize the log-percentile shift objective (see Section B.1.1). Their final optimization ion equation is
min cost(a; x) s.t. f(æ + a) = +1, a E A(x)
which is cast as an Integer Lincar Program (Mittleman, 2018) to provide users with recourses. Their publicly available implementation is limited to a binary case for categorical features," hence we demonstrate results on the binarized version of the dataset.
'Please refer this example where they mention about these restricted abilities httpp::/ hrcourse/blob// httb///aateeee//mmmaaeee 01 quidkstarrt.pyyn
27


Reviews:
[{"review_id": "lMWNIrj3xJ", "reviewer": "Reviewer_btjX", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\nThe paper addresses a problem of practical interest.\n\nThe proposed optimization criterion is simple and intuitive: search for a set of CFs such that any cost function (in a large set) is small for at least one of the CFs. Despite this simplicity, in experiments this criterion leads to better sets than DICE, which optimizes a diversity criterion.\n\n## Weaknesses\nThe metrics introduced for the experiments can be misleading.\n> One of the criteria for a CF example is its closeness with respect to the original example, either to make it actionable, or to make it understandable to the user why the original example is not in the class of the CF. In the current paper, this criterion is evaluated by *proximity*, *population average cost* (PAC), *user coverage* (Cov), and *fraction of users satisfied* (FS@k). All these metrics are defined based on an average criterion over the set of proposed CFs, which is a misleading criterion. Typically, if the algorithm proposes a set that contains a unique valid CF (an example that is classified differently from the original), even if this CF is far from the original example, these metrics can be made good by adding to this set a large number of non-valid examples (examples that are classified as the original one) that are extremely close to the original. It would be more appropriate to define these metrics as averaged only over valid CFs.\n> \n> This risk is mitigated in the paper by limiting the size of the sets to 10, but 9 non-valid examples are already sufficient to drastically reduce *proximity*, PAC, Cov, and FS@k.\n\n\nThe presentation of some algorithms could be clarified.\n\n> The feature cost function for ordered variables drastically differs from the one for unordered variables. This point is actually not mentioned in the main paper, the reader as to look at Alg 2 and 3 (in Appendix) to be aware of it. The main paper should at least contain a warning.\n> \n> Also, the term \"Euclidean\" is overused for Algorithm 3. This cost function does not depend on the Euclidean distance between two points, but on the number of points in some intervals. As in Algorithm 2, this cost function refers to quantiles, except that Algorithm 3 is limited to the distribution of points either above or below the value of the original example.\n> \n> Finally, Theorem 4.1 is only valid if there is one unique replacement per iteration in Algorithm 1. However, the current pseudocode of Algorithm 1 is unclear on this point.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper deals with the generation of counterfactual examples (CF) that take into account the cost of change to the user. The proposed approach addresses the situation where the cost function varies from user to user and is unknown. The solution is not to propose a single CF, but a set of CFs, so that the user can find a suitable CF from this set.\n\nThe paper introduces a new criterion to be optimized for selecting a set of relevant CFs, as well as an algorithm (COLS) for optimizing this criterion. The paper compares the quality of the CFs provided by this approach with that of CFs provided by other state-of-the-art approaches (DICE, FACE, and Actionable Recourse).", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "(critical) Clarify the behavior of `getReplaceIdx()` in Algorithm 1.\n\n(greatly recommended) Clarify, in the main paper, the definition of Algorithms 2 and 3\n\n(greatly recommended) Clarify the high-level presentation of Algorithm 3. Consider chaging its name.\n\nConsider changing the metrics in the experiments.\n\nTypos\n- legend of Figure 1: \"... does well [under a for] certain types ...\"\n- bottom of page 2: a space is missing after the sentence ending with \"(See Figure 1).\"\n- top of page 3: \" ... this setup can be used to compare and [rank order] different methods...\"\n- Section 4.1: one occurence of \"FP\" has been misspelled by \"PF\"", "broader_impact_concerns": "Nothing to mention", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "qxcWOPfRUG", "reviewer": "Reviewer_hHv7", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The issues with actionable recourse that the paper addresses are compelling and worthy of study.\n- Given sampled cost functions, the idea of expected minimum cost seems like the \"right\" way to do things under their model.\n- The result of this model is a really gnarly optimization problem to find the recourse options and their COLS procedure seems like a useful way to attack it.\n- The experiments seemed to me to be convincing, including ablation studies showing that while both of their core contributions give some performance improvement, it is the use of the expected minimum cost objective that makes the bigger contribution.\n\n\nWeaknesses:\n- The method for generating cost functions seems fine, but also somewhat arbitrary. It's not clear that this \"really\" captures what user preferences would look like in any meaningful sense. On the other hand, that type of \"realism\" may be outside the scope of the paper, which only works on standard datasets anyway, and more of a modeling question for someone who wants to use this method in the real world.\nFurther moderating the above weakness somewhat, the authors do show some experiments where even when the train-time distribution is misspecified, their approach still is able to outperform baselines.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The focus of the paper is on the longstanding problem in fair ML of \"actionable recourse\". If a classification system is to be used to allow or deny access of users to scarce resources (paradigmatically a credit decision) based on some features, then it may be desirable or even legally necessary to tell them how they could change their features in order to change the decision from negative to positive. It may also be desirable to ensure that the cost to the user is sufficiently small (feasible), according to some cost model where changing certain features may be more or less difficult.\n\nThe authors first point out that there is no reason to assume that every user has the same cost function; moreover, users' cost functions are likely unknown (even to themselves). So the authors present a technique that they call INSPIRE which involves sampling a large number of possible cost functions, then generating a recourse set in order to minimize the mean (over each cost function) of the cost of the best recourse for that function. This is a difficult optimization problem for many reasons, and they propose a local search procedure to tackle it. The sampling scheme, the new objective, and the local search procedure together constitute INSPIRE.\n\nThe authors then present a set of experiments on the classic Adult and COMPAS datasets. They assume that each simulated user in this dataset has some unknown ground truth cost function, which will be used to measure performance but not made available to any of the recourse methods. They measure the quality of generated recourses in terms of a number of cost metrics based on this ground truth as well as other standard distance metrics. They consider a number of \"ablation studies\" to show that their new contributions really do improve performance, and they consider robustness to various incorrect modeling choices as well as measuring impacts on demographic fairness.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I think more discussion of modeling choices about generating the sampled cost functions, and how a \"real-world\" practitioner might go about this (perhaps in scenarios with different levels of information about the true user preferences) would be helpful, though not essential.\n\nI also weakly speculate that tools from robust and distributionally robust optimization might be useful for this problem, and some discussion about these optimization frameworks may be worthwhile.", "broader_impact_concerns": "The authors include a broader impact statement in appendix A.1 which seems to sufficiently address concerns with this general type of work. I tentatively agree with the authors' claim that work on actionable recourse is a \"robust good\". I don't think the novel contributions of the work introduce any novel issues of broader impact.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "LvrZVG4j3I", "reviewer": "Reviewer_1jrs", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper studies an interesting problem. Moreover, the paper is well written: the problem is clearly described and the contribution are well explained. Finally, the extensive experimental analysis compares the method with previous approach on several aspects, showing the superiority of the proposed method.\n\nThe main weakness of the paper is the algorithmic contribution. Indeed, the main contribution of the paper is the proposal of new approaches/models and the algorithmic contribution is limited to Algorithm 1.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper study a new approach for recourse generation. In this problem, there is a model that outputs a decision on the basis of the user's features given in input. The goal is the design of an algorithm that suggests to the user how to change their features in order to change the model decision. The authors propose a novel method for recourse generation that account for diverse features preference. Moreover, they propose a new model that account for the fact that different users have different costs in changing their features. Finally, they propose an optimization method to generate recourses. The proposed method is then evaluated according to a new evaluation procedure.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I suggest to expand the textual description of Algorithm 1 in Section 4.3.", "broader_impact_concerns": "No", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers recommended acceptance of the submitted paper or leaned towards acceptance. The authors also addressed all the issues and concerns raised by the reviewers. Given that the topic is relevant and the paper makes counterfactual generation more realistic/useful, I follow their recommendations. Nevertheless, upon a final reading of the paper, I noticed several glitches in the paper that the authors should finally address (sorry for partly being picky):
* Improve the description of Algorithm 1. Present the algorithm as general as possible, i.e., do not fix hamDist to 2 (or is there a reason for doing so?). There are references to "Code 1" and "Code Block 2" which are unclear if one prints the paper (what they refer to only becomes clear through the links in the pdf); the update to $S^{best}$ is hard to parse given the used notation - can this be put abstractly and more understandably; it is not specified how you pick the hamDist=2 features you change - I assume you pick them uniformly at random? In the return line, $C^b$ is set differently than before.
* Verify that Theorem 4.1 is still consistent with the updated Algorithm 1.
* "we propose a genetic algorithm Mitchell (1998)" => put citation in brackets or similar
* $F = {f1, f2, ...fh}$ => $F = {f1, f2, ..., fh}$
* "there is no particular ordering of the feature values in terms of difficulty" => "difficulty" is unclear.
* "where s^f is the value of feature f in the state vector" => s^f should not be bold; end sentence with $\mathbf{s}$
* In Eq. (1) you spell out the constraints while you omit them in Eq. (4) => unify
* "where F is the black-box ML model and 1 is the desired class" => clarify, up to this point the ML model wasn't mentioned much, that it is black-box was mentioned at all (also the relevance is unclear); clarify what a desired class is and that there are only 2 classes (?)
* "hence we use the EMC objective account for user FP" => add a forward reference
* There are several more typos (capitalization, commas) in the newly added text, e.g., in section 4.1. Please revise those carefully.
Decision: Accept (poster)