Personalized Algorithmic Recourse with Preference Elicitation
Authors: Giovanni De Toni
Paolo Viappiani
Stefano Teso
Bruno Lepri
Andrea Passerini
Venue: Accepted by TMLR ()

Abstract: Algorithmic Recourse (AR) is the problem of computing a sequence of actions that -- once performed by a user -- overturns an undesirable machine decision. It is paramount that the sequence of actions does not require too much effort for users to implement. Yet, most approaches to AR assume that actions cost the same for all users, and thus may recommend unfairly expensive recourse plans to certain users. Prompted by this observation, we introduce PEAR, the first human-in-the-loop approach capable of providing personalized algorithmic recourse tailored to the needs of any end-user. PEAR builds on insights from Bayesian Preference Elicitation to iteratively refine an estimate of the costs of actions by asking choice set queries to the target user. The queries themselves are computed by maximizing the Expected Utility of Selection, a principled measure of information gain accounting for uncertainty on both the cost estimate and the user's responses. PEAR integrates elicitation into a Reinforcement Learning agent coupled with Monte Carlo Tree Search to quickly identify promising recourse plans. Our empirical evaluation on real-world datasets highlights how PEAR produces high-quality personalized recourse in only a handful of iterations.

Published in Transactions on Machine Learning Research (01/2024)
Personalized Algorithmic Recourse with Preference Elicitation
Giovanni De Toni
giovanni.detonieee
Augmented Intelligence Center, Fondazione Bruno Kessler, Italy DISI, University of Trento Italy
Paolo Viappiani
paolo.
LAMSADE, CNRS, Université Paris-Dauphine, PSL, Prance
Stefano Teso
stefono. @unitn..
CIMcC & DISI, University of Trento, Itly
Bruno Lepri
lepri&ffbk.c eu
Augmented Intelliennce Center, Pondazione Brano Kessler, Italy
Andrea Passerini
andraa.passerbnihhmii..
DISI, University of Trento, Italy
Reviewed on OpenReview: https: // openreview. net/ formm? id= Xs9
Abstract
Algorilhmicc Recourse (AR) is the problem of computing a sequence of aclions that once performed by a user overturns an undesirable machine decision. is paramount that the sequence of actions does not require too much effort for users to implement. Yet, most approaches to AR assume that actions cost the same for all users, and thus may recommend unfairly expensive recourse plans certain users. Prompted by this observation, we introduce PEAR, the first human-in-the-loop approach capable of providing personalized algorithmic recourse tailored to the needs of any end-user. PEAR builds on insights from Bayesian Preference Elicitation to iteratively refine an estimate of the costs of actions by asking choice set queries to the target user. The queries themselves are computed by maximizing the Expected Ubilly of Selection, a principled measure of information gain accounting for uncertainty on both the cost estimate and the user's responses. PEAR integrates elicitation into Reinforcement Learning agent coupled with Monte Carlo Tree Search quickly identify promising recourse plans. Our empirical evaluation real-world datasets highlights how PEAR produces high-quality personalized recourse in only a handful of iterations.
1 Introduction
Automated decision support systems are increasingly employed high-risk decision tasks with the aim of empowering human decision-makers and improving the quality of their decisions. Example applications include bail requests (Dressel & Farid, 2018), loan approvals (Sheikh et al., 2020), job applications (Liem et al., 2018), and prescription of medications and treatments (Yoo et al., 2019). Despite their promise, often these systems are opaque mcaning that users, and even engincers, have trouble understanding and controlling their decision process and provide no means for overt urning unwanted outcomes, such as denied loan requests. One way addressing these issues is through the lens Algorithmic Recourse (AR) (Venkatasubramaniks & Alfano, 2020; Karimi et al., 2021). In AR, given an undesirable machin--generated decision, the goal is identify a sequence of actions or interventions for short that once implemented by the user overturns said decision, for instance, changing job obtaining master's degree. Motivated by this, number of

---

Published in Transactions on Machine Learning Research (01/2024)
approaches have been recently proposed for computing AR (De Toni et al., 2023; Naumann & Ntoutsi, 2021; Karimi et al., 2022; Ramakrishnan et al., 2020; Yonadav & Moses, 2019; Ustun et al., 2019; Karimi et al., 2020; Tsirtsis & Rodriguez, 2020; Russell, 2019; Mothilal et al., 2020; Wang et al., 2023; Dandl et al., 2020).
It critical that the suggested recourse plans are not too difficult or expensive to carry out. This entails that recourse should be personalized, because different users in the same situation may need substantially different recourse plans. To see this, consider user who is denied a loan. Based on a profile made by the financial institution, an AR algorithm might suggest the user reduce their monthly expenses. However, unlike the "average" customer, our user is incurring high medical expenses because they recently contracted an invalidating illness. Thus, the AR suggestion is highly inappropriate. Clearly, it is impossible to infer such a constraint from their profile alone. Most approaches, however, completely neglect the user's own preferences. The few that do require feedback that is difficult to obtaín in practice, e.g., preferences over a large pool of alternatives (Russell, 2019; Mothilal et al., 2020; Wang et al., 2023; Dandl et al., 2020) or upfront quantification of action costs (Yadav et al., 2021; Karimi et al., 2022; Rawal & Lakkaraju, 2020; Wang et al., 2023; Mahajan et al., 2019).
We argue that algorithmic recourse should make users first-class citizens in the recourse generation process rather than viewing them as passive observers. To this end, we introduce PEAR (Preference Elicitation for Algorithmic Recourse), the first human-in-the-loop approach for generating personalized recourse tailored for a target end-user. Our algorithm integrates AR and ideas from interactive Preference Elicitation (PE) (Chajewska et al., 2000; Boutilier, 2002; Braziunas & Boutilier, 2007; Guo & Sanner, 2010; Viappiani & Boutilier, 2010; Dragone al., 2018) in a fully Bayesian setup. PEAR goes beyond existing approaches in that the costs of actions are estimated from user feedback and prior information. In each iteration, PEAR identifies small selection of alternative interventions a choice set that optimizes sound measure of information gain (the Expected Utility of Selection (EUS) (Viappiani & Boutilier, 2010; 2020)) and then asks the user to pick their preferred option. Using this feedback, PEAR quickly improves its estimate of the user's preferences and generates interventions that get progressively closer to the user's idcal. Furthermore, PEAR takes interactions and dependencies between actions costs into account when computing suggested recourse, whenever this information is available. See Fig. for an overview.
Contributions: Summarizing, we:
Introduce the problem of personalized algorithmic recourse, and show that existing approaches are insufficient to solve it.
Develop PEAR, the first human-in- in-t----ttee-oop, Bayesian approach for computing personalized interventions that is robust to noise in user feedback and minimizes user effort.
Evaluate PEAR on synthetic and real-world datasots and show that can generate substantially up 50% cheaper interventions than asgr-agnottic competitors after only handful of queries.
2 Problem Statement
The user state s= (81, sa) E S RR is a vector of d categorical and real-valued features encoding, e.g-, instruction level and income. An action a E A is a map that takes a state s and changes a single feature, yielding new state s' = a(s), and expresses a recommendation of the form "Increase your income by $100." Given a (black-box) binary classifier h S - {0, 1} and user state leading to undesirable decision y= h(s), AR computes
intervention i.c., an ordered set of actions I = be applied to s to obtain a counterfactual state s' associated to more desirable outcome h(s') + y, all while minimizing user effort. We formalize the user effort required to perform an action via a cost function C:AXS - R+ The cost of an intervention is the sum of the costs of all actions it contains, that is C(T) = D. = (0)) = is the initial state. We denote with 1 (() the operation of applying each action a E I sequentially.
e(/)) that
11| ((((0,(()) Here, s( is the state obtained by applying action (+-1) to state g(i-1), and
Tt. forward to adapt our approach deal with multiclass classification problems.
2

---

Published in Transactions on Machine Learning Research (01/2024)
O C I
{T) U D(O)
Compute choice set
3) Ask question to the user
I (I...... Im}
(+f++1)
4) Improve the weights Bayesian Estimation
(0) w(0)
s(f-1)
Initial
1) Recourse Generator
5) Update
and weights
Final Intervention
Figure Overview PEAR. (1) Given the initial state s (()) of the user and weights w(O), PEAR computes a pool of candidate interventions achieving recourse. (2) choice set O(9) is selected from the pool and presented the user. (3) The user picks their preferred intervention from the set. (4) An improved estimate of the weights w(++1) is computed using this feedback, and (5) the user's state g(++1) is updated. After T rounds, the estimated weights are used to compute final intervention l"
Approaches to AR assume the user effort is proportional to the number of actions that need to be carried out, and minimize it by searching for short interventions I. However, this is unrealistic and impractical. For instance, changing job into a highly skilled one may not be realistic without obtaining a Master's degree first. In reality, the user effort also depends on users' preferences w E W S Rd which we represent as d-dimensional vectors. For example, for some people, might be casier improve their education than get new employment. Thus, we parameterize the cost function using the user preferences C(T w), C(a, w) if refer to single actions. In the following, the preferences used by the recourse algorithm, which might differ from the former. Motivated by this, we introduce new problem setting, denoted personalized algorithmic recourse:
distinguish between the (typically unknown) user preferences W and
Definition 1 (Personalized Algorithmic Recourse) Given a black- box binary classifier h and a user state acquire cost function C(I w) for interventions such that the intervention I' obtained by solving the following oplimization problem:
1" argmin, C(1 I w) s.t. h(I(s(0))) + h(s(0))
(1)
has minimal regret for the target user, defined as:
Reg(I", 10T) = C(I w C(IGT w
(2)
where w GT E W encodes the ground-trui truth but unobservable preferences of the user and GT is the "ideal"
intervention that would be obtained by solving Eq. (1) using GGT
The similarity of Eq. (1) to existing formulations of AR can be misleading, as here the key challenge is that of obtaining weights w that reflect the user's own preferences. We discuss how PEAR does so in Section 4.
3 Related work
Counterfactual explanations (CEs) are class of local, human-understandaal explanations (Wachter et al., 2017; Byrue, 2019) that convey information about changes to input variables that overturn a machine decision (Guidotti et al., 2018; Stepin et al., 2021). AR aims to identify actionable CEs that attain recourse for the user (Verma et al., 2020; Karimi et al., 2022). Existing approaches methods (Wachter et al., 2017; Ramakrishnan et al., 2020: Poyiadzi al., 2020: Naumann & Ntoutsi, 2021; Russell, 2019; Mothilal et al., 2020; Wang et al., 2023; Dandl et al., 2020) by learning general policy
AR solve Eq. (1) via diverse optimization
3

---

Published in Transactions on Machine Learning Research (01/2024)
(Yonadav & Moses, 2019; De Toni et al., 2023; Verma et al., 2022). Most methods simply return set of actions, disregarding their order. However, recent research showed that ignoring the causal relationship between features prevents reaching optimal recourse (Karimi et al., 2021). Some methods thus optimize for recourse plans, i.e., sequences of actions attaining recourse, following a purely causal or causal-inspired setup (Ustun et al., 2019; Karimi et al., 2021; 2020; De Toni et al., 2023; Naumann & Ntoutsi, 2021; Mahajan et al., 2019). PEAR fully supports this paradigm and considers the interplay between features when finding recourse, whenever this information is available.
Most AR approaches assume that the cost function is fully specified beforehand (Wachter et al. 2017; Ramakrishnan et al., 2020; Rawal & Lakkaraju, 2020; Wang et al., 2023; Mahajan et al., 2019), ignoring the problem of modelling user preferences altogether. The few that explicilly deal with user preferences do so in a naive manner. Some of them (Russell, 2019; Mothilal et al., 2020; Dandl et al., 2020; Yadav et al., 2021) ask users to pick their preferred option from a large pool of user-agnostic recourse plans, that not guaranteed to contain a low-cost option for the user. This is also impractical, as users can only properly evaluate limitod number of alternatives at a time (Simon, 1955; March, 1978). Others require users to quanlify the cost of each possible action upfront (Karimi et al., 2022; Rawal & Lakkaraju, 2020; Wang et al., 2023; Mahajan et al., 2019), or via numerical constraints (Poyiadzi ct al., 2020; Wang et al., 2023), yet end-users can rarely articulate their preferences in quantitative manner (Keeney & Raiff,, 1993). PEAR sidesteps this issue by learning preferences from ranking data, i.e., relative judgments of the form "I prefer option A to option B" (Furnkranz & Hullermeier, 2010).
AR is specifically concerned with high-stakes scenarios, such as loan requests, that users face at most a handful of times in their lifetime. In these settings, it is impossible to estimate user preferences from historical data. In recommender systems, this issue has been solved through preference elicitation, whereby the user's 's preferences are estimated through human- numan-friendly interaction protocol (Boutilier, 2002). In order to converge to high-quality options with minimal user effort, PE algorithms select queries (i.e., questions to the user) that maximize information gain and that are casy to answer. A popular option is choice queries, in which the user has to select a preferred item from a small set of alternatives. PEAR builds on Bayesian PE methods, as they account for imprecision in users' answers (Chajewska et al., 2000; Guo & Sanner, 2010; Viappiani & Boutilier, 2010) in a principled way by mcasuring the information gain of choice sets in terms of Expected Utility of Selection (Viappiani & Boutilier, 2020). Similarly to PEAR, Rawal & Lakkaraju (2020) estimate cost weights from preference feedback. However, they collect feedback from domain experts in a non-interactive fashion and learn population-leres preferences that are not personalized, thus failing to minimize Eqq (2). Population-Ieva estimates can lead to recourse that is largely suboptimal for specific individuals, as will be shown in our experimental evaluation.
4 Personalized Algorithmic Recourse with PEAR
Before describing PEAR, we discuss how we model the user's preferences and how these impact the costs of actions and interventions. Equally importantly, actions influence each other's costs e.g., obtaining an additional degree can dramatically lower the cost of landing a better-paying job - and we need to account for this if we wish to minimize the cost of recourse. In order to account for interactions between action costs, we model C using a set of linear equations, parameterized by weights w E W, by taking inspiration from generalised additive independence models (Pigozzi et al., 2016) from decision theory and structural causal models (Pearl, 2009). We call such formalization cost correlation structure (CCS). A CCS corresponds to a directed acyelic graph (DAG) where each node is associated with the cost wa of changing a single fcature 8a and each edge represents a (causal) relationship between two costs, parameterized by wys E RR Then, following the equation induced by the DAG, we define the cost of applying an action Os to a state s to change the k-th feature from 8k to sy as a linear combination:
Clar, S w) wylss skl + +E, Pas Wyk-3
33
Here, Paş are the parents of the k-th node in the graph. For example, we can use Eq. (3) to describe the cost of the action 'increase your salary'. Such cost depends linearly on the raise asked (11g sxl). However, it also depends on some causally related variables (E, Pas Wyx8j), such the user's current job. We can
4

---

Published in Transactions on Machine Learning Research (01/2024)
Clfar,a a)) (w) 27
81
(1, $2, 83)
Cla (w) -4
C(aza" - Clas, //// 14
A = {a1, 022 a3}
B1 (s)
B2(s!
a (2)
83
82
s 0
1, 1]
8 (3)
5,
C(a1, s () = w1 8 81
83(s(0)
az(s
a1 (8))
Cla2, s w) w2 8/ 82
+ W1281
Clos, (w))=
clans"//w =5
Clas,>")ww)
C(a3, s/ w) w3 w3 $3 + W1381 + $23$2
Cl(as, ag ay a1hss!))
w)
(a) Cost Correlation Structure (CCS)
(b) The cost of an intervention I
Figure 2: The cost model (Left) A cost correlation structure (CCS) for cost modelling. (Right) Given 5(O) = [1,1,1] and unit w, let us imagine we want to reach g( = [5, 5, 5] by following the presented CCS and the intervention 1 = {ai, 02 (2,03)) as), where og assign t- 5 for all i E 2,).. Clearly, we incur different costs by applying permuted versions of I. The green path indicates the lower-cost intervention.
imagine that it might be easier to ask for a raise for a company's manager rather than a simple employee. A formal example of a cost function and of its corresponding DAG is shown Fig. 2a. Again, the cost of an intervention is the sum of the costs of all actions contains applied sequentially, that is:
C(1 w) = E!' C(a()) w)
(4)
Eq. (3) does not define simple lincar model, but it accounts for a richer set of interactions. For example, given two actions and 02 their cost is not additive, meaning C(a1, S +) s | w) + C((a1, a2), w). We can show it with a simple example.
Example of non-additivity of Eq. (3). Consider simple CCS with two nodes 8 + $2, with s (s $2) and w (w1, w2, W12), and an instance s = (1, and w (1, 0.5, 1). We define two actions, a1 and 02. which simply set the corresponding features 8; to 2. Using Eq. (3), we can compute the cost of applying the single action as
C(a w) = 1 - 11 1|=1
C(az, w) = 0.5|2 - 1/ + 1- 1.5
(5)
By Eq. (4), the cost of the intervention {ai,az) is C(fai, C(Har,a2h,s s w) = 3.5 + 1.5 1, hence the costs are not additively independent. Moreover, Eq. (4) considers the order in which actions are applicd, í.e., 3 w such that C(fa), + C((a2, a1 ) w), as shown Fig. 2b.
Note that if dependencies between actions costs are not available, Eq. (3) boils down to a simple linear function, namely C(ay, w) =x ssll- This case matches the typical setup of algorithmic recourse methods, which assume the weights are independent from one another. Eq. (3) is however more flexible in that, if dependencies between costs are in fact available, they are automatically leveraged by PEAR.
We formalized the cost of an action (Eq. (3)) by following a standard assumption made in decision theory (Keeney & Raiffa, 1993) called 'generalised additive independence" (GAT) (Pigozzi et al., 2016) which is shared by many preference clicitation algorithms. It defines utility functions that mcasure both the contribution of a single feature and the contribution of subset of features. Following causality theory (Pearl, 2009), each subset consists of features causally related to the one we are acting on. In support of this strategy, previous rescarch highlighted how it is impossible to offer optimal recourse recommendations without considering relationships between features (Karimi et al., 2020).
In Karimi et al. (2020), the authors refer to knowing the impact of an intervention on causally related features (c.g., will getting a new dogree incrcase my salary?). However, is known that such cansal knowledge about the world is hard to obtain unless we make specific restricting assumptions (Pearl, 2009). In our work, rather than considering how features causally change after intervention, we focus on learning how the "cost."
5

---

Published in Transactions on Machine Learning Research (01/2024)
of acting on those features changes after an intervention (e.g., will getting new degree make it easier to increase my salary?). In our case, the cost of modifying feature is something we can easily learn by asking the user.
Ultimately, with our setup, we make learning the cost function feasible, and we can also represent complex non-additive behaviour which arises from the sequential nature of recourse. Our formalization Eq. (3) and Eq. (4) goes along the lines of previous works (Naumann & Ntoutsi, 2021; De Toni et al., 2023), that address the problem from the same perspective, but assume to know these costs a-priori.
On Cost Correlation Structure and Causality. The cost correlation structure shares some similarities with Structural Causal Models (SCMs) (Pearl, 2009), since they both use a directed acyclic graph, also called causal graph, to represent causal relationships ween features X. In the context of AR, SCMs model relationships between features rather than between costs. For example, Karimi et al. (2020) frames the recourse problem as finding a counterfactual sox optimizing Eq. (1) given an approximated SCM describing the joint distribution P(X), while the cost. function is simple p-norm, such as C(s ,)) = ||s -||2. In our case, CCSs do not allow for do-actions to compute counterfactuals via abduction, since they do not model P(X). Similarly to Naumann & Ntoutsi (2021), use the causal DAG to represent consequence-awar cost equations as shown in Eq. (3), without taking any explicit causal angle. Indeed, following the non-causal AR literature, we assume actions a E A to influence only the target feature 8k, without any causal effect on any of its children 8j in the DAG, However, actions over Sy will affect the cost of subsequent actions changing the user features.
4.1 The PEAR Algorithm
In order to account for uncertainty over the user's weights w, PEAR explicitly models a distribution P(w) over them and progressively refines it by interacting with a target user. A high-level overview of PEAR is given in Fig. and the pseudo-code is listed in Algorithm
In each iteration 1,..., T, where T is the iteration budget, PEAR computes a choice set O(1) I containing k candidate interventions achieving recourse (for small k, e.g. 2 to 4) and asks the user to indicate their most preferred option in the set. Importantly, ((t) is chosen so as to maximize the (expected) information gained from the user, and in a way that is robust to noise in their feedback. We detail the exact procedure used by PEAR in Section 4.3. These user choices are stored in an initially empty dataset D(t), In each step, PEAR integrates the user's foedback by inferring a posterior over the weights P(w D(9) x P(D()) P(W) using Bayesian inference, and updates the user state by applying the first action f of the chosen intervention. We apply single action so elicit user preferences in all intermediate states. Tf state achieving recourse is reached, the user state is reinitialized. After T rounds,² 2 PEAR computes low-cost personalized intervention by applying the intervention generation procedure described in Section 4.2, biased according to the latest posterior p(w (.
PEAR makes no assumption on the form of the prior P(w), meaning that the prior can be adjusted based on the application. In order to model both variances across the preferences of individuals and for sub-groups in the population, in this work we model them as a mixture of Gaussians with M components Ni E,), for i= 1,...., M. This choice works well in our experiments, see Section 5. Note that, analogously to Rawal & Lakkaraju (2020), it is also possible to fit the prior on population-level preference data or domain expert input, whenever this is available. In our experiments, we do this for all competitors.
4.2 Generating Personalized Interventions with W-FARE
PEAR generates personalized interventions by leveraging novel, user-aware extension of FARE (De Toni et al., 2023), a state-of-the-art algorithm for generating short - but user-agmostic interventions, which we briefly outline next. In FARE, each action a E AA is implemented as tuple (f,z), where f is a function changing one feature and x is the value that feature takes, e.g., (change_income $1000). Given an initial state s, FARE uses reinforcement learning to learn two probabilistic policies x (s) and (s(s,, which are used as priors to guide a Monte Carlo Tree Scarch procodure that incrementally builds an intervention I by selecting actions
In practice, the loop can be terminated as soon as the user is satisfied with one of the interventions in O(t)
6

---

Published in Transactions on Machine Learning Research (01/2024)
The PEAR algorithm: h - {0, 1 is a classifier, s E S the initial state, the available actions, p(w) the prior, T 2 the query budget, le 2 2 is the size of choice sets.
Algorithm 1
procedure PEAR(h, ( kk Initialize t +- 0, D +- Ø 3: for t= ,,. T do
4:
O(0 + UU
A, D((-1)) Ask the user to pick the best intervention I e O
D Algorithm 2
5:
D(A) + D(t-1) u {L}
6:
Update weight estimate p(w D())
s(1) < (s(1-1))
if h(s(t)) * h()()) then
((() f- (0)
10:
11:
I' = W-FARE(h, (0), w with w = DEp( [w]
> Section 4.2
12: return 1
a E A. In order to ensure interventions are actionable, actions a are only chosen they satisfy given preconditions. The reward used by FARE r(]) p 1()(T(((0)) # h(s(")),, factor and the indicator evaluates to if I attains recourse and to otherwise. FARE is highly scalable and very effective identifying counterfactual interventions even under minimal training budget (De Toni el al., 2023).
where p > 0 is a discount.
FARE is uscr-agnostic, while PEAR needs to generate personalized interventions. We fill this gap by introducing W-FARE, novel extension of FARE that integrates the user's costs into the reward while inheriting all benefits of the latter. Recall that PEAR maintains a posterior over the weights. The expected cost of an action can thus be obtained by marginalizing over the posterior:
E[C(a, s) [D(t]] = Jw C(a,s w)P(w D(9) dw
(6)
Analogously, the cost of an intervention is replaced by the expectation:
E(C(I) D = = ((C(a()) (()) [D(0]
(7)
The W-FARE reward function then given by r(I w) x ( I. 1 ((((I())))) + h(s("))) (see Appendix B for more in-depth description of W-FARE). This explicitly drives RL to learn policies that optimize user-
specific action costs and that, therefore, help MCTS to more quickly converge to personalized interventions. We show empirically that PEAR is substantially more effective than FARE at computing personalized interventions
in Section 5.
4.3 Computing Informative Choice Sets
Given the current posterior P(w D(()), PEAR computes a choice set containing k interventions I that maximizes information gain (Chajewska et al., 2000). We measure the latter using the Expected Utility of Selection (EUS) (Viappiani Boutilier, 2020), a measure of the goodness of set defined as the expectation, under the uncertainty over w, of the utility of its most preferred element. EUS is closely related to the Expected Value of Information (EVOI), and frequently used in Bayesian PE (Price & Messinger, 2005; Viappiani & Boutilier, 2010; Akrour et al., 2012; Viappianí & Boutilier, 2020). The EUS builds on the notion of expecled ulility of an intervention I, which is defined as:
EU(T (()) R(-C(T) D()) - So C(T w) D(1)) dw
(8)
The EUS of a choice set O can then be defined as:
EUSn(O) (D()) = Eieo Pn(O ~ T)EU(T D(O)
= = |ErEO PR(O w)C(1 w)] P(w D(t) dw
(9)
7

---

Published in Transactions on Machine Learning Research (01/2024)
Algorithm 2 Greedy procedure to efficiently compute a choice set O: s(() E S the current state, A the available actions, h 2 is the size of choice sots, D(t) the user choices so far.
1: procedure "U A(()()
2: 0+
3: w + Dipiw (())
4: while |0| < k do
5:
Generate the candidate interventions I with W-FARE using A and + argmax, EUSNZ(OUT ((t)) EUS D(())
7:
0 Ou
return O
Here, Pnr(O~ ~ 7| w) is the probability that user with weights picks 7 from O under a specific choice of response model R modelling noise in user choices. Intuitively, we expect users to prefer the cheapest interventions I E O. Moreover, we also expect that interventions in O with similar costs have similar probability of being chosen. Motivated by this, and following common practice in choice modelling (Luce, 2012), in PEAR we implement a logistic response model (L), defined as:
exp(-AC(1 w)) Pe(O Iw = Σieo exp(-XC(I [w)
(10)
Here, À E R is temperature parameter. Finding choice set O maximizing the EUS is intractable in general NP-hard (Nemhauser et al., 1978; Krause & Golovin, 2014), in fact and computationally intensive in practice, and risks slowing down the interaction loop to the point of estranging users. We observe that, however, under some response models R, the EUS becomes submodular and monotomic (Viappiani & Boutilier, 2010). This is the case for the noiseless response model (NT), according to which the user always prefers the lowest-cost option, i.e.,
PN ~ I ()w) II.. 1(C(T w) C(T' w)]
(11)
This means that, for NI, greedy optimization is sufficient to find a choice set O that achieves high EUS with approximation guarantees. Formally, it holds that for choice sets O found via greedy optimization, D), where O is the truly optimal choice set (Viappiani & Boutilier, 2010; Nemhauser al., 1978; Krause Golovin, 2014). In PEAR, we leverage the fact that EUS, - EUS z is always smaller than problem independent (tight) bound (Viappiani & Boutilier, 2010), meaning that instead of minimizing EUS, directly, we can compute high-quality choice set by greedily maximizing EUS This immediately leads to a practical algorithm for the logistic response model L, listed in Algorithm 2.
(O D) 2 (1 - e EE))
4.4 Benefits and limitations
PEAR is designed to facilitate the application of AR to practical high-stakes tasks like loan approval. The main benefit of PEAR is that it provides personalized algorithmic recourse, which existing approaches are not capable of. Also, it follows a fully Bayesian setup for handling uncertainly over the estimated preferences and noise in user feedback. It also leverages ideas from preference elicitation such as small choice sets and elicitation of relative preferences - to ensure the interaction is coguitively affordable. Finally, PEAR makes use of a novel cost. function that automatically lakes dependencies between action costs into consideration, whenever these are known or can be estimated, thus facilitating the identification of better recourse suggestions. At the same time, the cost function is linear, enabling PEAR to leverage efficient algorithms from preference elicitation tailored for eliciting such cost functions.
Several steps of the algorithm namely, evaluating the EUS (Eq. (9)) and the expected cost of interventions (Eq. (7)), and updating the posterior p(w D(()) require marginalizing over the weights. Doing so involves evaluating a complex integral that cannot be solved analytically. We sidestep this issue by leveraging
For the sake presentation, assume that there ties. Nate that the EUS formula invariant to the way ties are broken. In our implementation,
broken uniformly at random.
8

---

Published in Transactions on Machine Learning Research (01/2024)
Normalized Average Regret
1.00
Adult
GiveMesoomereditt
0.75
Choice Set
2
0.50
Resp. Model
0.25
Noiseless
Logistic
0.00
2
8
10
8
10
# of Questions
# of Questions
Figure 3: Normalized Average Regrot for PEAR when varying the number of questions, the choice set size and the user response model on both datasets (sampled from All users).
an efficient Monte Carlo approximation, and specifically ensemble split sampling (Karamanis Boutler, 2020; Karamanis al., 2021) and then averaging over the samples with the highest likelihood. We find that, empirically, this procedure is efficient much that it can support interactive usage and leads to competitive results in our experiments, cf. Section 5.
Lastly, as is typical in PE, our approach focuses on the "myopic" value of information by looking to maximize the expected posterior utility, thus reducing as much as possible the regret one step ahead. As we ask more questions, the regret will tend to zero. However, one main theoretical challenge currently faced the PE domain the development of optimal elicitation policies that consider sequential version of the value of information, which may be more efficient but intractable in general (Boutilier, 2002).
5 Experiments
Our experimental evaluation is aimed at answering the following research questions:
Q1 Does PEAR succeed in minimizing regret for an increasing amount of user feedback?
Q2 Does PEAR outperform competitors in terms of validity and cost?
Q3 Is PEAR robust to imprecise knowledge of the cost correlation structure the user?
Datasets and Classifiers. We evaluated our approach on two real-world datasets laken from the relevant. literature: GiveMeSomeCredit (Kaggle, 2011) and Adult (Dua & Graff, 2017). They are (unbalanced) binary classification problems for income prediction and loan assignment, respectively. The datascts have both categorical and numerical features. Some of these features actionable (e.g., occupation, education), while others are immutable (e.g., age, 862, matiive_counlly preferences over the features. Following previous work (Karimi et al., 2021; De Toni et al., 2023; Naumann & Ntoutsi, 2021), we manually defined and fixed the cost correlation structures for both. We randomly generated user-specific weights for each instance by sampling from a (dataset-specific) mixture of Gaussians with M 6 components and uniform mixture weights. In Appendix A, we give a description of the feature space, action space and the directed acyelic graphs needed by the CCS for both datasets. We then split the data into training (70%), validation (10%) and test (20%) sets. For each dataset, designed the black-bor classifier h as an MLP with two hidden layers. We trained it by cross-entropy minimization, selecting the typerparameters which maximise the F score on the validation set. In Appendix C we show additional experiments with shallow classifiers, such as a logistic model and a decision tree.
These datasets come without. causal graph and users'
"Easy" vs. "Hard" Users. Intuitively, users close to the docision boundary of the black-box will require few actions achieve recourse, while users whom h assigns a low score might need longer and more complex interventions. Understanding the preferences of these "hard" users is crucial since wrong suggestion might.

---

Published in Transactions on Machine Learning Research (01/2024)
Table 1: Performance of all competitors averaged over 10 runs. A +.7 indicates that the method did not find any successful intervention for any user. P and PEAR, indicate PEAR associated with the noiscless and logistic response model, respectively. The best results are boldfaced.
Adult Cost
GiveMeSomeCredit Cost
Users
Method
Validity
Length
Validity
Length
FARE
0.90 + 0.27
285.63 = 195.68
3.45 = 1.19
0.86 + 0.23
161.77 + 107.4
3.27 1.13
CSCF
0.78 0.28
154.28
125.34
2.53 = 0.57
0.57 = 0.42
100.69 + 120.22
2.51 1.12
EFARE
0.76 0.39
306.11
199.02
3.54 + 1.25
0.67 + 0.38
155.92 + 109.19
3.18 + 1.18
0.76 0.38
283.31
167.86
3.36 + 1.08
0.12 + 0.32
59.66 + 0.00
2.00 0.00
A11
MCTS
0.44 1 0.44
445.65
201.28
4.60 + 1.19
0.70 i 0.42
214.33 1 119.38
4.09 1 1.31
FACE
0.15 1: 0.27
397.49 + 128.43
3.76 1 0.64
0.24 0.38
327.18 1 78.85
5.97 1 0.62
PEARNL (ours)
1.00 + 0.03
142.23 + 61.75
2.84 + 0.59
0.89 + 0.00
96.04 + 31.96
2.79 0.42
PEAR,, (ours)
1.00 + 0.04
146.54 + 63.09
2.84 + 0.56
0.89 + 0.00
100.19 + 29.53
2.85 + 0.48
FARE
0.71 + 0.44
438.97 + 188.50
4.54 +: 1.21
0.47 + 0.37
319.46 1 96.36
4.97 1 0.70
EFARE
0.55 0.48
454.05 202.76
4.52 1.25
0.22 + 0.36
371.58 1 82.18
5.31 0.71
RL
0.55 + 0.47
433.64 = 152.67
4.33 = 1.24
CSCF
0.36
382.84 126.31
3.70 - 0.56
0.13 0.32
190.81 + 119.99
1.11
Hard
MCTS
0.21 + 0.40
599.20 = 153.44
5.53 + 0.72
0.40 + 0.43
353.75 t 99.26
5.43 + 0.88
FACE
0.00 0.04
448.72 + 0.00
5.20 = 0.00
0.20 - 0.36
455.20 92.10
7.09 0.53
vEAR (ours)
0.99 + 0.08
296.37 + 43.84
3.35 + 0.55
0.58 + 0.04
251.60 = 51.16
4.59 + 0.40
PEAR,, (ours)
0.99 0.09
301.13 + 52.61
3.34 + 0.58
0.58 0.02
262.23 = 45.36
4.64 0.36
substantially increase the overall cost for them. For each dataset, thus built two separate testing sets. The first one, named All, is obtained by sampling 300 users s with an unfavourable classification (h(s) < 0.5), regardless of the actual value of h. The second one, named Hard, is obtained by sampling 300 users with an unfavourable classification having a score in the lower quartile of the black-box score distribution.
Competitors. We compare PEAR against several baselines: FARE and its explainable version EFARE (De Toni et al., 2023), CSCF (Naumann & Ntoutsi, 2021), an evolutionary algorithm which, similarly to FARE, generates recourse options by considering consequence-aware cost. functions and action sets A, and FACE (Poyiadzi et al., 2020), well-know ARR algorithm, which optimizes for population-based 'feasible paths" to achieve recourse. We also consider two simpler baselines, brute-force search (MCTS) and a vanilla. reinforcement learning agent (RL), trained in similar way as in (Hamrick et al., 2019; Verma et al., 2022). Note that all the competitors are model-agnostic and not interactive, since they assume the users' costs to be fixed. Wo provide more in-depth details on the baselines and their implementattions Appendix A.
Experimental Protocol. For PEAR, we vary the number of questions T to the user from 0 to 10. For T 0, initialize the weights with the expected value of the prior, [EPt)[w]] that represents uscr-indopendent population-based prior. Moreover, we employ two user response models, the noiseless model (Eq. (11)), to check the effectiveness of our approach in the best-case scenario where the user can perfectly express their preferences, and the logistic model (Eq. (10)), to challenge our approach in more realistic scenario. To provide a fair comparison, we equip the competitors with our cost function (Eq. (3)) and set their weights to the expected value of the prior.
Q1: PEAR successfully minimizes the regret. Fig. 3 shows the evaluation of the regret as a function of the number of queries to the user. Here the ground-truth intervention G (which is unknown) is approximated by running PEAR with the correct user costs GT and the regret is normalized by rescaling the costs between C(TGT WCT) and (( WCT where we generate (()) using the expectation of the prior. We run PEAR with two different choice set dimensions, k = 2 and k = 4, and for both noiseless and logistic response models. After a few questions, PEAR reaches a low regret in all settings. Generally, a larger choice set produces a lower regret, irrespective of the response model, with the downside increasing the cognitive burden for the user. We now briefly summarize the results when T 10. For the Adult dataset, the best regret 0.09 for the noiseless user and k 4, while the worst regret is 0.40 for the logistic response model and 2. For
10

---

Published in Transactions on Machine Learning Research (01/2024)
Table 2: Evaluation of PEAR (with g = 10 and a logistic noise model) for an increasing amount CCS graph corruption, averaged over 10 runs. "None' indicates that the correct causal graph is being used.
Adult
GiveMeSomeCredit Cost
Users
Corruption
Validity
Cost
Length
Validity
Length
None
1.00 0.04
146.54 = 63.09
2.84 + 0.56
0.89 0.00
100.19 + 29.53
2.85 = 0.48
0.15
1.00 0.00
165.11 = 46.19
2.79 0.24
0.90 + 0.00
98.02 + 18.37
2.46 = 0.16
All
0.25
1.00 = 0.00
162.05 = 48.05
2.89 0.34
0.90 + 0.07
99.51 = 18.53
2.48 0.18
0.5
1.00 = 0.00
175.54 = 62.29
0.36
0.90 0.11
110.35 = 19.93
2.56 0.20
1.0
0.99 + 0.02
172.51 = 61.13
2.96 + 0.40
0.91 + 0.04
106.63 + 28.84
2.64 = 0.28
None
0.99 = 0.09
301.13 = 52.61
3,34 + 0.58
0.58 + 0.02
262.23 + 45.36
4.64 = 0.36
0.15
1.00 = 0.00
308.22 = 38.40
3.47 0.26
0.26
0.63 + 0.04
237.00 = 35.72
4.06 = 0.31
Hard
0.25
1.00 0.02
305.62 = 39.73
3.32 + 0.35
0.66 + 0.11
238.92 + 28.66
3.90 = 0.27
0.5
1.00 0.03
314.36 + 37.93
3.38 + 0.32
0.59 0.14
250.17 + 29.71
4.16 - 0.21
1.0
0.99 0.03
313.51 = 61.64
3.69 = 0.44
0.64 + 0.09
256.24 12.04
4.24 = 0.18
GiveleeSomeCrdiit, get 0.15 (noiseless, k = 4) and x 0.45 (logistic, k 2). Overall, can provide interventions which are at least 50% cheaper than their preferenco-agnostic counterparts.
Q2: PEAR outperforms competitors in terms of validity and cost. Following the AR literature (Karimi et al., 2022; Verma et al., 2020), we compare PEAR (with T = 10) and all competitors in terms of average validity, i.e., fraction of users for which we obtained recourse, intervention cost and length (or sparsity), i.e., the number of features that have to be changed. Intervention costs are computed by using the true weights w Table 1 shows the results. PEAR manages to achieve the highest validity while also providing substantially cheaper interventions than the non-personalized competitors on average. This is true both for the noiseless and logistic response models. While CSCF tends to produce shorter interventions, these are in general more costly and have a larger cost variance with respect to those found by PEAR, confirming the intuition that length is a suboptimal proxy of intervention complexity. The only exception the Hard setting of GiveMeSomeCredit, where however CSCF manages to achieve recourse for only 22% of the users, whereas PEAR achieves recourse in 58% of the cases. The difficulty of CSCF in achieving recourse is visible in all settings and severely limits its applicability. Furthermore, CSCF is 10 to 50 times more computationally expensive than PEAR, making it unsuitable for real-time interactive scenarios. The MCTS baseline has rather poor performance both in terms of validity and cost in all settings, while the RL baseline has a reasonably high validity on Adult but it completely fails to learn a policy achieving recourse on GiveMeSomeCredit. On the other hand, mothods which combine MCTS and RL (FARE and EFARE) give better performance, which is aligned with previous results (De Toni et al., 2023), but are still suboptimal with respect. to PEAR in terms of both validity and cost. Finally, FACE struggles to achieve recourse since needs find a "feasible path' from the current user to similar one in the training set, which is favourably classified.
Q3: PEAR is robust to misspecifications of the cost correlation structure. In the previous experiments, following other research works (Karimi et al., 2021; De Toni et al., 2023; Naumann & Ntoutsi, 2021), we assumed to know the structure of the CCS a-priori. However, in a real scenario, we might have instead an approrimate causal graph from which to derive the CCS. Table 2 shows the validity, cost and length of the interventions found by removing X% of edges from the causal graph, with X E (0.15, 0.25, 0.50, 1.00). Validity is almost unaffected by corruption in all settings since it only impacts the computation of the cost. On the other hand, expected, increasing the amount of graph corruption reduces the effectiveness of user feedback. However, the degradation is not dramatic. Indeed, if we look at the Hard evaluation, the increase in cost is negligible (around 4%) with up to 50% randomly removed edges. On GiveMeSomeCredis we do not see any significant increase in costs. Surprisingly, we see instead an improvement for 15% and 25% corruption levels. We hypothesize that lacking causal knowledge about features which are not needed for recourse can be beneficial since it simplifies the clicitation process. However, at higher levels of corruption, this effect disappears. The setting X 1.0 is equivalent to a non-causal cost function, in which acting on a feature has always the same cost, irrespective of the others. It is the common choice of many works dealing with
11

---

Published in Transactions on Machine Learning Research (01/2024)
AR (Wachter et al., 2017; Ramakrishnan et al., 2020; Poyiadzi et al., 2020). Under such setting, when considering All users, the degradation is more evident, but still within 6% for GiveMeSomeCredit while for Adult it goes up to 15%. Overall, results clearly indicate that PEAR can suggest reasonable cost interventions even with a largely misspecified cost correlation structure. This is apparent when comparing these results with those in Table 1. Even with 50% randomly removed edges, PEAR recommends interventions that are cheaper than all competitors but CSCF, that however has a substantially lower validity.
Further experimental evaluations. We performed some additional experiments which explored the relationship between the cost and length of an intervention I and validated the usage of the model score h(x) as proxy for identifying the difficulty of finding a recourse suggestion. We report our findings in Appendix E. Lastly, following the example of De Toni et al. (2023), we also provide an explainable version of our method, XPEAR, which complements interventions with Boolean explanations during the elicitation process by taking into consideration the user effort. We then compared XPEAR against the corresponding basclines EFARE (De Toni et al., 2023) and while it provides good performanccs at the expense of being more interpretable, it is still outperformed by PEAR. The results are presented in Appendix D.
6 Broader Impact
Algorithmic recourse focuses on developing methods to increase the user's agency in contesting automated decision systems outcomes and the fairness of the current machine learning models. As for all systems impacting humans, need to consider the possible bad ethical ramifications of these technologies and potential mitigation strategies. In the context of personalized algorithmic recourse systems, we can identify two sources of algorithmic bias which could hinder the quality of our recommendations:
(1) Different recourse suggestions when conditioned on a protected attribute. Users who share a similar profile, but differ in some sensitive features (e.g., sex; age, etc.) might. obtain different interventions 1. We believe this might be the most important source of unfairness. In such a scenario, a method might successfully optimize both Eq. (1) and Eq. (2), but some categories of users will always get costlier interventions. However, this is an issue shared by almost the totality of methods in the AR literature.
(2) Uninformative prior lacking information about sensitive categories. The prior P(w) used by the Bayesian procedure in PEAR might not describe the preferences of less-represented groups, thus making it more difficult to learn such cost functions. Critically, methods employing a population-Ievel estimate of w or which relies on expert cvaluation (Rawal & Lakkaraju, 2020) have the same limitation.
We believe issue (1) relates to the quality underlying recourse generator method (e.g., W-FARE, CSCF, FACE, etc.). A solution could be employing AR strategies that are specifically optimized to satisfy a notion of fairness (Gupta et al., 2019; Haldar et al., 2022; von Küggeggnn et al., 2022). However, to the best of our knowledge, this is a little-explored area in the recourse literature which would require additional investigation beyond the scope of the present work. Regarding issue (2), we could imagine focusing our efforts on collecting additional data on sensitive groups to learn a more informative prior to running PEAR. Additionally, we could raise the iteration budget (T) to increase the number of pairwise constraints we apply to our MCMC procedure. However, it would also increase the cognitive burden for the user.
Lastly, eliciting users' preferences might entail asking sensitive questions, or malicious entities could exploit these procedures to 'hack" and twist the intervention generation via strategic behaviour (Hardt et al., 2016). These considerations can be mitigated by research on adversarial attacks to ensure the method's 's robustness (Chen et al., 2020). Morcover, legal advice might be noeded to manage personal user data.
7 Conclusion
In this work, we identify the problem of personalized algorithmic recourse as a fundamental stepping stone for ensuring recourse is usable in real-world applications, and develop PEAR, the first algorithm able to provide personalized interventions. Our experimental evaluation shows that PEAR substantially outperforms existing poon-personalized) solutions in terms of both validity and intervention cost with only a handful of queries to the user. We hope that this initial contribution can foster further research in the community to work towards
12

---

Published in Transactions on Machine Learning Research (01/2024)
more realistic form of algorithmic recourse that can be successfully deployed in real-world scenarios. As for all methods dealing with algorithmic recourse, the effectiveness of the approach should, in principle, be evaluated on real users. However, this evaluation is highly non-trivial (and thus still missing in the algorithmic recourse literature) because roquires the creation a realistic scenario where a user feels to be unfairly Ireated in some machine-driven decision involving her life. The legal requirements that are progressively being introduced to regulate Al systems (Voigt & Von dem Bussche, 2017) could contribute making the information needed set up such scenario available in the near future.
Acknowledgments
Funded by the European Union. Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union the European Health and Digital Executive Agency (HaDEA). Neither the European Union nor the granting authority can be held responsible for them. Grant Agreement no. 101120763 TANGO. AP and BL also acknowledge the support of the MUR PNRR project FAIR Future AI Research (PE00000013) funded by the NextGenerationEU. BL also acknowledges the support of the European Commission under Horizon Europe Programme, grant number 101120237 ELIAS. The work of Giovanni De Toni was partially supported by the project Al@Trento (FBK-Unita).
References
Riad Akrour, Marc Schoenauer, and Michèle Sebag. APRIL: active preference learning based reinforcement
learning. In Peter A. Flach, Tijl De Bie, and Nello Cristianini (eds.), Machine Learning and Knowledge
Discovery in Datahases- European Conference, ECML, PKDD 2012, Bristol, UK, Seplember 24-28, 2012. Proceedings, Part II, volume 7524 of Lecture Notes in Computer Science, pp. 116-131. Springer, 2012. doi: 111007/978-3-661-33233
8. URL
htt////i.oog/1110000001 111111099778---2---44444-- 3-642-33486-
Craig Boutilier. A pomdp formulation of preference clicitation problems. In AAAI, pp. 239-246, 2002.
Darius Braziunas and Craig Boutilier. Minimax regret based elicitation of generalized additive utilities. In UAI, pp. 25 32, 2007.
Ruth M. J. Byrne. Counterfactuals in explainable artificial intelligence (xai): Evidence from human reasoning. In Proceedings of the Twghty-Eighth International Joint Conference Artificial Intelligence, IJCAI- 19, pp. 6276 6282. International Joint Conferences on Artificial Intelligence Organization, 7 2019. doi: 10.24963 hij/:///jciiii// 2019//7.011/87.. URL https: /ttpp/////oooo/1...... 24963/1jcaa 24966/Ajca1.2019/877 2019/876.
Urszula Chajewska, Daphne Koller, and Ronald Parr. Making rational decisions using adaptive utility elicitation. In AAAT/TAAT, pp. 363-369, 2000.
Yatong Chen, Jialu Wang, and Yang Liu. Strategic recourse in linear classification. ar preprinl arXiv:2011.00355 236, 2020.
Rémi Coulom. Efficient selectivity and backup operators in monte-carlo tree search. In Compulers and Games: 5th International Conference, CG 2006, Turin, Italy, May 29-31, 2006. Revised Popers pp- 72 83. Springer, 2007.
S. Dandl, C. Molnar, M. Binder, and B. Bischl. Multi-objective counterfactual explanations. In PPSN, pp- 448 469. Springer, 2020.
Giovanni De Toni, Bruno Lepri, and Andrea Passerini. Synthesizing explainable counterfactual policies for algorithmic recourse with program synthesis. Mach. Learn., 112(4):1380-1400) 1409, feb 2023. ISSN 0885-6125. doi: 10. 10.1007//119944-22--00222
URL https://doi.org:: 1007 00t0://00000//00004-00000002-220
Paolo Dragone, Stefano Teso, and Andrea Passerini. Constructive preference elicitation. Frontiers in Robolics and AI, 4:71, 2018.
Julia Dressel and Hany Farid. The accuracy, fairness, and limits of predicting recidivism. Science advances, (1 (1)5e50555,, 2018.
13

---

Published in Transactions on Machine Learning Research (01/2024)
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL http://aarch..e..c...... edu/ m1.
Johannes Furnkranz and Eyke Hullermeier. Preference Learning. Springer-Verlatt Berlin, Heidelberg, 1st edition, 2010. ISBN 3642141242.
José Fernando Gonçalves and Mauricio GC Resende. Biased random-key genetic algorithms for combinatorial optimization. Journal of Heurislies, 17(5):487 525, 2011.
R. Guidotti, A. Monreale, S. Ruggieri, D. Pedreschi, F. Turini, and F. Giannotti, Local rule-based explanations of black box decision systems. CoRR, abs/1805.10820, 2018. URL http://arxiv.org/// www.:oo///////..5/// 1000p/.00000.0000....0 10820.
Shengbo Guo and Scott Sanner. Real-time multiattribute bayesian preference clicitation with pairwise comparison queries. In AISTATS, pp. 289-296, 296, 2010.
Vivek Gupta, Pegah Nokhiz, Chitradeep Dutta Roy, and Suresh Venkatasubramaniaa.. Equalizing recourse across groups. Xi preprint 10Xiv:1909.091 2019.
Aparajita Haldar, Teddy Cunningham, and Hakan Ferhatosmanoghu. Raguel: Recourso-aware group unfairness elimination. In Proceedings of the 31st ACM International Conference on Information Knowledge Management, pp. 666 676,675,220 2022.
Jessica B Hamrick, Victor Bapst, Alvaro Sanchez- Sanchez-Gonzaler Tobias Pfaff, Theophane Weber, Lars Buesing, and Peter W Battaglia. Combining q-lcarning and scarch with amortized value estimates. arXiv preprint or wwxii:1912.02880 2019.
Moritz Hardt, Nimrod Megiddo, Christos Papadimitrion, and Mary Wootters. Strategic classification. In Proceedings of the 2016 ACM conference on innovations in theorelical computer science, pp. 111-122, 2016.
Kaggle. Give me some credit, Sep 2011. URL https::///:::: http:ttt////ukkkaleeee... /tt.aarrrr///o/oea..aaaaaaaooooa hwtp:////caatttttta/ottt//ttttaa overview.
Minas Karamanis and Florian Beutler. Ensemble slice sampling: Parallel, black- and gradient-free
inference for correlated & multimodal distributions. arXiv preprint arXiv: 2002. 06212, 2020.
Minas Karamanis, Florian Beutler, and John A Peacock. zeus: A python implementation of ensemble slice sampling for efficient bayesian parameter inference. arXiv preprint arXiv:2105. 000o:2000000468,, 2021.
Amir-Hosscin Karimi, Julius Von Küggeggnn, Bernhard Schölkopf, and Isabel Valera. Algorithmic recourse under imperfect causal knowledge: a probabilistic approach. Advances in Neural Information Processing Systems, 33:265 277, 2020.
Amir-Hossein Karimi, Bernhard Schölkopf, and Isabel Valera. Algorithmic recourse: from counterfactual explanations interventions. In Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transporency, pp. 353 302,362,200 2021.
Amir-Hossein Karimi, Gilles Barthe, Bernhard Schölkopf, and Isabel Valera. A survey of algorithmic recourse: Contrastive explanations and consequential recommendations. ACM Comput. Surv., 55(5), dec 2022. ISSN 0360-0300. doi: 10.1145/3527844 URL https://doi. 1145/3527848.
Ralph L. Keeney and Howard Raiffa. Decisions with Multiple Objectives: Preferences and Value Trade- Offe 1398099711199740033
Cambridge University Press, 1993. doi:
Levente Kocsis and Csaba Szepesvári. Bandit based monte-carlo planning. In Machine Learning: ECML 2006: 17th European Conference on Machine Learning Berlin, Germany, September 18-22, 2006 Proceedings 17, pp. 282-201 293. Springer, 2006.
Andreas Krause and Daniel Golovin. Submodular function maximization. Tractability, 3:71-104 2014.
14

---

Published in Transactions on Machine Learning Research (01/2024)
Cynthia Liem, Markus Langer, Andrew Demetriou, Annemarie MF Hiemstra, Achmadnoer Sukma Wicaksana, Marise Ph Born, and Cornelius J König. Psychology meets machine learning: Interdisciplinary perspectives on algorithmic job candidate screening. In Explainable and interpretable models in computer vision and machine learning, pp. 197-253. Springer, 2018.
R. Duncan Luce. Individual choice behavior: theoretical analysis. Courier Corporation, 2012.
Divyat Mahajan, Chenhao Tan, and Amit Sharma. Preserving causal constraints in counterfactur ual explanations for machine learning classifiers. arXiv preprint arXie:1912.03277 2019.
James March. Bounded rationality, ambiguity, and the engineering choice. The bell journal of economics, pp. 587-608, 1978.
R. K. Mothilal, A. Sharma, and C. Tan. Explaining machine learning classifiers through diverse counterfactual explanations. In FAT", pp. 607 617, 2020.
Philip Naumann and Eirini Ntoutsi. Consequence-aware sequential counterfactual generation. In Joint
European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 692-698. Springer, 2021.
George I, Nemhauser, Laurence A Wolsey, and Marshall I. Fisher. An analysis of approximations for maximizing submodular set functions-i. Mathematical programming. 14(1):265-294, 1978.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang. Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high- performance deep learning library. In Advances in Neural Information Processing Systems 32, pp. 8024-8035. Curran Associates, Inc., 2019. URL http://papers..eurr/ cc/paper/ httt-pprrrrrmaeee---e-eeeen-eeee
Martin Pawelczyk, Sascha Bielawski, Johan Van den Heuvel, Tobias Richter, and Gjergii Kasneci. CARLA: A python library to benchmark algorithmic recourse and counterfactual explanation algorithms. In Thirty-fifth Conference on Newral Information Processing Systems Datasets and Benchmarks Track (Round 1), 2021. URL attps://openrevier net//orrum?dddwDiiBBBun
Judea Pearl. Causality. Cambridge university press, 2009.
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 112285528830 2011.
Gabriella Pigozzi, Alexis Tsoukias, and Paolo Viappiani. Preferences in artificial intelligence. Annals of Mathematics and Artificial Intelligence, 77:361-401, 2016.
Rafacl Poyiadzi, Kacper Sokol, Raul Rodriguez Tijl De Bic, and Peter Flach. Face: feasible and actionable counterfactual explanations. In Proceedings of the AAAI/ACM Conference AI, Ethics, and 2020.
Society, pp.
Robert Price and Paul R. Messinger. Optimal recommendation sets: Covering uncertainty over user preferences. In Manuela M. Veloso and Subbarao Kambhampati (eds.), Proceedings, The Twentieth National Conference on Artificial Intelligence and the Seventeenth Innovative Applications of Artificial Intelligence Conference, July 9-13, 2005, Pittshurgh, Pennsglvania, USA, pp. 541-548. AAAT Press / The MTT Press, 2005. URL attp://www aaai. org /ttp///arrrr/AAA////////11111--/
G. Ramakrishnan, Y. C. Lee, and A. Albarghouthi. Synthesizing action sequences for modifying model decisions. In A AAAI, volume 34, pp. 5462-54444 2020.
15

---

Published in Transactions on Machine Learning Research (01/2024)
Kaivalya Rawal and Himabindu Lakkaraju. Beyond individualized recourse: Interpretable and interactive summaries of actionable recourses. Advances in Newral Information. Processing Systems, 18:12187-12198, 2020.
Christopher Rosin. Multi-armed bandits with episode context. Annals of Mathematics and Artificial Intelligence, (1(3))203 230, 2011.
Chris Russell. Efficient search for diverse coherent explanations. In Proceedings of the Conference on Fairness, Accountability, and Transporency. FAT* '19, pp. 20-28, New York, NY, USA, 2019. Association URL https://doi.orr
for Computing Machinery. ISBN 9781450361255. doi: 10. 1145/3287560 7228877660.887669 3287569.
Mohammad Ahmad Sheikh, Amit Kumar Goel, and Tapas Kumar. An approach for prediction of loan approval using machine learning algorithm. 2020 International Conference on Electronics and Sustainable Communication Systems (ICESC), pp. 490 494. IEEE, 2020.
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schritlwieser, Toannis Antonoglou, Veda Panneershelvam, Marc Lanclot, el. al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):484 489, 2016.
Herbert A Simon. A behavioral model of rational choice. The quarterly journal of economics, pp. 99-118, 1955.
Nidamarthi Srinivas and Kalyanmoy Deb. Muiltiobjective optimization using nondominated sorting in genetic algorithms. Foobutionary compulation, 2(3):221 248, 1994.
Stepin, M. Alonso, and A. Catalaand M. Pereira-Fariiat A survey of contrastive and counterfactual explanation generation methods for explainable artificial intelligence. IEEE Access, 9:11974-12001, 2021.
S. Thirtsis and M. Rodriguez. Decisions, counterfactual explanations and strategic be- havior. In NewrIPS, 2020. cD01b6542229008437100000003 aat.:as-.-.ttttt..........
URL https://proceeddnngs ietpreedddinnneennis..ee.e neurips. 2200pp//0000/ashh.
B. Ustun, A. Spangher, and Y. Liu. Actionable recourse in linear classification. In FAT* pp. 10-19, 2019.
Suresh Venkatasubramannaa and Mark Alfano. The philosophical basis algorithmic recourse. In Proceedings of the 2020 conference on fairness, accountabllity, and transparency, pp. 284-293, 2020.
Sahil Verma, Varich Boonsanong, Minh Hoang, Keegan E Hines, John P Dickerson, and Chirag Shah. Counterfactual explanations and algorithmic recourses for machine learning: A review. arXiv preprint arXi::2010.1 10596, 2020.
Sahil Verma, Keegan Hines, and John P Dickerson. Amortized generation of sequential algorithmic recourses for black-box models. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 8512 8519, 2022.
Paolo Viappiani and Craig Boutilier. Optimal Bayesian recommendation sets and myopically optimal choice query sets. Advances in neural information processing systems, 23, 2010.
Paolo Viappiani and Craig Boutilier. On the equivalence of optimal recommendation sets and myopically optimal query sets. Artificial Intelligence, 286:103328, 2020.
Paul Voigt and Axel Von dem Bussche. The EU general data protection regulation (gdpr). A Practical Guide, 1st Ed., Cham: Springer International Publishing, 10(3152670::1-55555, 2017.
Julius von Kügelgen, Amir-Hossein Karimi, Umang Bhatt, Isabel Valera, Adrian Weller, and Bernhard Schölkopf. On the fairness of causal algorithmic recourse. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 9584 9594, 2022.
16

---

Published in Transactions on Machine Learning Research (01/2024)
Sandra Wachter, Brent Mittelstadt, and Chris Russell. Counterfactual explanations without opening the black box: Automated decisions and the gdpr. Harv. JL. & Tech., 31:841, 2017.
Zijie J Wang, Jennifer Wortman Vaughan, Rich Caruana, and Duen Horng Chau. Gam coach: Towards interactive and user-centered algorithmic recourse. In Proceedings of the 2023 CHT Conference Human Factors in Computing Systems, pp. 1-20, 2023.
Prateek Yadav, Peter Hase, and Mohit Bansal. Low-cost algorithmic recourse for users with uncertain cost functions. arXiv preprint arXiv:2111.01293 2021.
S. Yonadav and W. S. Moses. Extracting incentives from black-box decisions. ColR, abs 1910.05664, 2019. URL http:// http://arxiv http:/iv.rr//bb//111000 05664.
Tae Kenn Yoo, Ik Hee Ryu, Geunyoung Lee, Youngnam Kim, Jin Kuk Kim, In Sik Lee, Jung Sub Kim, and Tyler Hyungtaek Rim. Adopting machine learning to automatically identify candidate patients for corneal refractive surgery. NPJ digital medicine, 2(1):1-9 9, 2019.
17

---

Published in Transactions on Machine Learning Research (01/2024)
A Competitors and Experimental Settings
We now briefly illustrate the competitors' main principles and describe their most important hyperparameters. We also discuss W-FARE and its new reward function in more detail.
Implementation details. We implemented PEAR, the competitors and the black box classifiers using Python (>=33 3.7) and PyTorch (Paszke et al., 2019). For reproducibility purposes, the code and the pre-trained models are freely available online". We used the original code for both FARE and CSCF", with minimal modifications to make them compatible with our experimental setting. For FACE, we used the implementation available in the CARLA library (Pawelezyk et al., 2021). As for the basclines, adapted MCTS and the RL agent from the FARE repository. All the experiments were run on virtual machine running CentOS 7.6.18 18 with 165 cores, and 25 GiB of RAM. The full set of hyperparameter configurations is available in the code.
State space and Action space. Given the raw datascts, we onc-hot encoded categorical features and we performed min-max normalization for the continuous features using scikit-learn (Pedregosa et al., 2011). We also manually performed additional standard data engineering tasks, such as removing entries with null values or checking for potential outliers. After the data cleaning and preprocessing steps, we kept. the following features for each dataset:
Adult: age, popital_gain,, capital_loss hours_per__u week (contimuous) workclass, education, mar- ital status, occupation, relationship, race, sex, native_country (categorical). We considered the features age, relationship, race, sex, and native_countty to be unactionable.
age. NumberOfTimee30- RebiRalio MondhlyInnomme, NumberOJOyee ArerrOeeeeeeeiiiiieeeeesiiiee Loans, NumberOft OfT'mmemm00ayslaaaaaaa 89DaysPastDueNN Worse, age and NumberOffepenne OfDependents to be unactionable.
GiveMeSomeCredit:
Revolving Saatiinggittaattttooo/sseereeere
PasluusPa Worse,
httpr//annnOiiiiiss.uuuerrrr/ffe Numeer (contimnous). We considered the features
These features represent the state e S of a user. Table 3 reports the action space A used by W-FARE and the baselines for each of the experimental datasets. For Adult, we adopted the same action set used by De Toni et al. (2023), while for GiveMeSomeCredit we devised the functions ourselves. Please note that the actions a E A operate directly in the original feature space, without encoding or rescaling, to ensure the interventions are understandable by humans. The features assigned as non-actionable do not have any action available. We refer the reader to the code implementation for additional details.
Cost Correlation Structure. Following the previous literature, (Karimi et al., 2021; De Toni et al., 2023; Naumann & Ntoutsi, 2021), manually designed the directed acyelic graph for both experiments. Fig. 4 shows the resulting graphs. During the graph corruption experiments, we incrementally remove subset of edges laken uniformly at random.
A.1 Monte Carlo Tree Search (MCTS)
MCTS (Kocsis & Szepesvári, 2006; Coulom, 2007) is efficient tree-based heuristic search procedure that can solve difficult tasks where computing directly the exact solution is intractable (Silver et al., 2016). MCTS builds a tree representing all possible moves and outcomes. Each tree node represents a state s(1) and each edge represents performing an action E A. In each iteration, MCTS builds this tree following four main steps: selection, expansion, simulation, and backpropagation. The selection step takes state s(t) and selects the next action (1++1), based on some strategy such as UCB1 (Kocsis & Szepesvári, 2006). In our experiments, MCTS uses the P-UCT (Rosin, 2011; Silver et al., 2016) criterion, defined as:
(1+1) argmax E(rls(0) (t) ,a'' + +U(S")))))) L(s(1)) ,a)) a'EA
(12)
18

---

Published in Transactions on Machine Learning Research (01/2024)
Table 3: Action set A for Adult and GiveleSomeeredit datasets used by W-FARE and the baselines. We report the functions, their arguments and which feature each of them modifies For Adult, we adopted the same action set as De Toni et al. (2023), but we added two additional functions, CHANGE DAP_LOR and CHANGE CAPNGE_CAP__ CAP_GAIN for CiveMeSomeCredit. In the case continuous features, we constructed the argument sets by picking evenly spaced numbers from an interval since MCTS cannot handle continuous search spaces. We report the intervals from which selected the argument values. For categorical features, simply report the full set of options available.
GAIN to increase the available interventions. We manually crafted the action space
Adult
Feature
Function (f)
Argument Type
Argument (s)
workclass
CHANGE WORKCLASS
Categorical
Never-worked, Without-pay, Self-emp-not-inge
Self-emp-ine, Private, Local-gov, State-gov,
Federal-gov
education
CHANGE BAANGE_EDUCATIO
Categorical
Preschool, 1st-4th, 5th-6th, 7th-8th, 9th, 10th, 11th, 12th, HS-grad, Some-college, Bachelors, Masters, Doctorate, Assoc-acdm, Assoc-voc, Prof-school
occupation
CHANGE_OCCUTEE LOCCUPATIOONN
Categorical
Tech-support, Craft-repair, Other-service, Sales, Exec-managerial, Prof-specialty, Handlens-cleaners, Machine-op-inspet,, Adm- clerical, Farming-fihingg Transport-moving,
Priv-house-serv, Protective-serv, Armed-
Forces
capital gain gain capital loss hours_ _pre__er_________ _ee___eekk_____eeee_eeeeep
CHANGE CAPP GAIN CHANGE CAP LOSS CHANGE HOURS HOUNE
Integer
15000, - 1 [1, 5000
Integer
-5000, - - 50000 5000
Integer
25, [1,25]
CiveMeeomeeredit
Feature
Function (f)
Argument Type
Argument (x)
BALANCE
Real
[-1. -1.00.01 0..00
SumnlerroFThmmms300s0sssssseeee Worse
PAST DUE _0
Integer
DebtRatio
DEBT RATIO
Real
- -1.00.01] U0.01,
MonthlyIncome
INCOME
Integer
100000 -1] J [1, 10000]
OPEN LOANS
Integer
25,
PAST DUE 90
Integer
-2,
NumberReall oeaeeereeeestttteooooooOOoooLL
OPEN REAL ESTATE
Integer
-25
Number OimbbrrOTiimebf DemeeedossDDassssstteeeeotrrrr
PAST DUE_ 60
Integer
25,
19

---

Published in Transactions on Machine Learning Research (01/2024)
MA
DBR
30L
OCC
EEDU
AGE
REL
WO
AGE
CAL
ROU
SEX
NA
90L
DP
CA.G
HO
CA.L
NEL
60L
(a) Adult
(b) GiveMeSomeCredit
Figure 4: Directed Acyclic Graphs used for the Cost Correlation Structures. Each node corresponds specific user feature. The complete mapping between node acronyms and features can be found in the experimental configuration files.
Here, E[rls', a'] is the expected reward of taking action in state s'. The reward ( if we achieve recourse and -1 otherwise. |/] is the length of the intervention while 7 E (0, 1] discount factor. I(s(0, aa) is a penalty is equal to cost exp(-C(a' s(t) w)). U(s(t), ((s(t))a') trades off exploration and exploitation, and
it is defined as
N
(s
a)
Cpuct P(a s(1))
(13)
1 NAain
where P(a s(O)) is the prior probability of choosing such action, Nu is the visit count of node s(1) and Ngatn the visit count of the child node being evaluated. our experiments, the prior P(a (t)) is a uniform distribution over the actions.
The erpansion step adds new child nodes to the current node based on the available actions. The simulation step then carries out a playout, selecting moves randomly until terminal state is reached. The value of the outcome of this terminal state is then backpropagated up the tree (backpropagation step), incrementing the visit Ng and reward counts of nodes along the path that was traversed to reach the outcome. We use the reward counts to compute E(rls(*),at) a'). The number of simulations is a hyperparameter. Once the simulations are done, start over from the selection step. MCTS keeps expanding and selecting nodes until reach recourse, user-defined marimum intervention length. Once MCTS ends, return the successful intervention to the user. An intervention here is path from the root node (s(")) to terminal node (s!T)).
Hyperparameters. In our experiments, we set the number of simulations to 15 and 10 for Adult and GiveMeSomeCredit, respectively. We also set the marimum intervention length to 6 and 8, for Adult and GiveeeeSomeCredit, respectively. The value Cast_enst and Cpuct are also hyperparameters. We set them to and 0.5 respectively, for both experiments.
A.2 Recourse Policy (RL)
simple agent which learns a recourse policy. Following the architecture described in De Toni al. (2023), it has four different components: an encoder Jencs an LSTM controller fe, a function network gy, an argument network f* and value network gv- Jene produces latent representation of the current state s(!) which is sent to the controller fo. Given the hidden states he coming from fex the function and argument network generates the policies x and which we use to get the tuple (f.z)(++1) which corresponds to the next action a. We use the value network Jv to approximate the value function V(s((),,),
Training the agent. We train RL such to minimize the following loss function
Σ (V
,2)
true T log(mT) - π true log(TT.) न.
(14)
batch
20

---

Published in Transactions on Machine Learning Research (01/2024)
where we assume to have access to the ground truth policies xiru and x either by having a previous dataset of recourse options, by optimizing over an MDP following (Verma et al., 2022), or by discovering such traces by direct search. In our paper, we follow the last approach by using MCTS as the search component. At inference time, we run the agent until we either find recourse, reach the mazimum intervention length, or call an illegal action (e.g., an action whose precondition not satisfied).
Hyperparameters. As in De Toni et al. (2023), genos 9s and 9e are all MLPs and we manually defined their structure for each experimental setting (e.g., number of layers, dimensions, etc.). We do the same for the controller fe. We optimize Eq. (14) via Adam and we set the learning rate to 0.001 for Adult, and 0.003 for GiveMeSomeCredit.
A.3 (Explainable) eFficient counterfActual REcourse (FARE and EFARE)
FARE (De Toni et al., 2023) is model-agnostic method which exploits the synergy between learned (RL) policy and a discrete search procedure (MCTS) to discover recourse options efficiently. At training time, differently from MCTS and RL, we do not use a uniform prior, but we leverage the agent instead P(a ((0) = (s()))) (s(t)). Similarly to Silver et al. (2016), we foster additional exploration by replacing P(a s(0) with a linear combination, P(a s(9) + (1 - <p) where Up ~ Dir(ca)- We manually set the parameters ag and Ep for each setting.
EFARE is deterministic model which provides sequential counterfactuals together with explanations. Given trained FARE model, a sample of successful interventions for the training set users is extracted. These interventions are merged to form a graph, where each node represents an action a, and each arch represents which actions (f, 2) can be taken from the said node. Then, for each node, a small decision tree is trained to indicate, given a user state s(!), which is the next. recommended action. Given this trained automaton, we can traverse the graph using the decision trees to transition between nodes. Morcover, the decision trees can give us Boolean explanations for each transition.
Hyperparameters. FARE shares the same hyperparameters of MCTS and RL. During training, set the number of simulations to 15 and 10, for Adult and GiveMeSomeCredit respectively. The noise fraction is instead set to ep 0.3 for both, with 1/p = 0.3. At inference time, we add no noise (ep = 0) and the number of simulations is fixed at 3, Lastly, for each dataset, we train a corresponding EFARE version by sampling 300 interventions from the training set using FARE.
A.4 Consequence-aware Sequential Counterfactuals (CSCF)
CSCF (Naumann & Ntoutsi, 2021) is a model-agnostic evolutionary algorithm which can generate sequential recourse plans by taking into consideration feature relationships. CSCF uses the Biased Random-Key Genetic Algorithm (BRKGA) (Gonçalves & Resende, 2011) together with non-dominated sorting (NDS) (Srinivas & Deb, 1994) to perform multi-objective optimization. BRKGA optimizes over the solution genotype (real-values vectors G E [0, 1)) and evaluates its phenolype instead (sequences of actions E A). Thus, they propose also a decoder to deterministically derive a single phenotype from a genotype.
At each iteration, CSCF evaluates the decoded solutions phenotypes by computing their fitness. We use the same fitness function as proposed in the original paper. Then, following NDS, a new population is formed by genetic mating and biased crossover between the elites (feasible and valid solutions in the Pareto front) and non-elites. The loop then continues until we reach a termination condition (e.g,, we reach the maximum number of generations). From the last population set, pick the lowest cost valid intervention with ties broken uniformly at random.
Hyperparameters. In our experiments, we mainly used the default hyperparameters provided by the authors (Naumann & Ntoutsi, 2021). We set the population size, p = 50, and the maximum number of generations, n = 25, for both Adult and CiveMeSomeCredit, to keep the computation time manageable. Higher values might improve the performances, but it would make CSCF unusable in an online setting (c.g., web interface provided by the bank).
21

---

Published in Transactions on Machine Learning Research (01/2024)
A.5 Feasible and Actionable Counterfactual Explanations (FACE)
FACE (Poyiadzi et al., 2020) is a model-agnostic method which can find actionable counterfactual examples respecting the underlying data distribution. The main idea is to propose recourse options based on the shortest path between the current state of the user and a state reaching recourse. FACE proposes different density-weighted metrics to find these "feasible paths'. FACE starts by building a graph over the training set data points. Then, the user can specify certain properties (e-g., prediction threshold, custom weight function, etc.), which restrict the graph by removing edges pointing to unfeasible counterfactuals. FACE then uses the Shortest Path First Algorithm (Dijkstra's algorithm) over all the instances matching the requirements in the graph.
We use FACE based on the proposed k-NN construction algorithm. Since FACE provides counterfactual eramples and not sequences, we then return the lowest-cost counterfactual by applying all the changes sequentially The action order is randomly chosen.
Hyperparameters. CARLA's implementation of FACE requires computing an adjacency matrix given the instances in the training set. The procedure is quite expensive since it requires Onn²) memory, where n is the number of instances. Thus, at inference time, we sample only fraction of the original dataset. In both Adult and CiveMeCredit, we pick only 10% of the total instances. We set the number of neighbours, k. to 50 and the distance threshold to e = 1.0 for both datasets.
B Weighted-FARE (W-FARE)
FARE is user-agnostic since is trained by assuming a shared w for all instances. Morcover, its reward function optimizes only for the length of the intervention, without explicating the cost C(T w) In our experiments, we train FARE with (e(w) [w]. Thus, push FARE to learn a general policy which works best in the average case, rather than for a specific user. To overcome this limitation, W-FARE proposes a new reward function ion which optimizes for the optimal intervention and tailors its answers to a given set of preferences w. The new reward is computed as
y [ (C(TEp 1 () C(T w)) h(s(0) + h(T(s(0))
(15)
otherwise
where (x) = I+exp(-ay) and r 0.01 and 7 = 0.97. The first term +l(++0(l optimizes for short and cheap interventions, while the second term aC (F [w] w) C(I w)) encourages W-FARE to provide personalized recourse options, by generating sequences which have lower costs than the intervention found by assuming the expected value [p(w)[w]. We also set the L(s((), aa) term of the MCTS's P-UCT criterion to haet_cost -[((+C([))) (C((EEP(W)W)) w) C(I [)) to help the model converge.
In both RL and FARE, the user preferences are not visible in the state s. Given a user state s(4), W-FARE adds the cost of every valid action A as an additional feature. Since an action a = (f,x) is combination of function f and an argument x, we combine actions relating to the same function into a single feature, averaging their cost over the set of argument values. This simplification allows adding FF additional features to the user state, where F is the set of all possible functions. More formally, the user's state s' becomes
ss=so
{ 1 ExEx, C(U,,), w) JEF
(16)
where Xy is the set of all the possible arguments for function f. We also considered adding directly the weights w, but we discovered that such representation makes it harder to learn optimal policy. Ultimately, we train W-FARE by assigning to cach user in the training set a dummy weight vector sampled from the prior w ~ P(w).
C Evaluating PEAR on shallow classifiers
We evaluated the performances of PEAR also by using non-neural machine learning models. Namely, we trained logistic regression and tree-based classifier. We performed hyperparameter optimization using grid
22

---

Published in Transactions on Machine Learning Research (01/2024)
Table 4: Performance of all compelitors averaged over 10 runs. A indicales that the method did not find any successful intervention for any user. PEARNL and PEAR, indicate PEAR associated with the noiseless and logistic response model, respectively. Please note that while some competitors can sometimes achieve a slightly lower cost. compared to PEAR, they suffer from much worse validity.
Logistic Regression
Adult
GiveNeSomeCredit Cost
Users
Corruption
Vakdity
Cost
Length
Validity
Length
FARE
0.97 1 0.16
266.48 1 166.07
3.44 1 0.87
0.89 1 0.18
156.40 88.92
3.15 1 0.92
EFARE
0.79
296.51
182.87
3.59
0.72
161.22 90.93
3.18 1
RL
0.78 + 0.37
268.07 + 170.85
3.43 = 0.94
0.15 + 0.36
58.43 = 8.93
2.00 = 0.00
CSCF
0.26
167.41
94.55
2.81 0.44
0.61
109.48 113.21
2.54 1.04
A11
MCTS
0.45 + 0.44
435.23 206.31
4.55 = 1.17
0.72 = 0.41
214.38 # 109.90
4.02 = 1.22
FACE
0.21 0.20
419.92 97.07
3.92 0.45
0.37 0.36
319.30 48.95
5.79 + 0.49
NE v. (ours)
0.99 0.09
146.28 + 64.08
2.96 + 0.31
0.95 + 0.07
90.07 + 22.64
2.50 + 0.25
PEARs. (ours)
0.99 + 0.09
154.29 + 66.55
2.98 + 0.38
0.95 0.08
90.88 + 28.86
2.49 + 0.28
FARE
0.90 + 0.28
471.54 + 167.12 .12
4.83 = 0.97
0.46 0.32
332.35 81.30
5.02 = 0.75
EFARE
0.59 0.45
484.60 171.43
4.84 0.96
0.25 0.36
346.12 92.08
5.16 - 0.82
RL
0.56 1 0.47
466.73 1 175.00
4.74 = 1.04
0.00 1 0.03
83.53 0.00
2.00 + 0.00
CSCF
0.22 0.34
395.80
124.63
4.20 0.67
0.12 0.30
190.70 1: 110.23
3.40 1 0.94
Hard
MCTS
0.20 1 0.38
583.91 1 119.72
5.56 1 0.59
0.40 1 0.43
348.86 848.86 94.76
5.36 1 0.94
FACE
0.02 1 0.10
598.63 11.96
4.88 0.15
0.29 0.36
448.70 39.45
6.96 1 0.49
PEARNL (ours)
0.95
320.97
89.93
4.23 = 0.36
0.73 + 0.16
259.74 45.29
4.28 + 0.46
PEARL (ours)
0.96 + 0.15
329.40 + 93.83
4.27 = 0.42
0.74 0.74 0.17
261.38 + 45.67
4.28 + 0.47
Decision Tree
Adult
GiveNeSomeCredit Cost
Users
Corruption
Vakdily
Cost
Length
Validily
Length
FARE
0.94 + 0.15
142.19 + 80.14
2.33 + 0.39
0.67 1 0.40
129.17 1: 148.29
2.70 1: 1.18
EFARE
0.71 0.22
261.22
188.57
3.18
0.81
213.55 105.56
3.93 1.09
RL
0.70 + 0.31
288.06 + 198.03
3.37 = 1.13
0.64 = 0.39
235.94 # 109.32
4.14 = 1.16
CSCF
0.55 0.31
294.45
200.01
3.43 1.07
0.07 0.25
96.50 + 105.43
2.65 - 0.81
A11
MCTS
0.47 + 0.46
452.30 + 225.37
4.50 = 1.31
0.73 173+10 0.42
229.19 + 122.03
4.13 = 1.32
FACE
0.23 + 0.25
450.83 112.93
4.05 0.57
0.59 0.39
328.81 55.37
5.72 - 0.58
PEAR L (ours)
0.88 + 0.14
169.03 + 64.91
2.64 = 0.36
0.95 1 0.11
113.21 +: 29.33
2.70 + 0.28
PEAR, (ours)
0.88 0.13
168.41 + 57.40
2.65 0.38
0.95 1 0.11
113.47 31.94
2.69 + 0.31
FARE
0.92 0.14
117.19 + 54.11
2.32 + 0.34
0.44
171.40 1: 153.66
3.00 1 1.27
EFARE
0.80 0.18
226.16
191.83
3.12 1.05
0.56 0.39
270.40 1. 126.42
4.44 1 1.16
RL
0.76 0.24
233.65
197.26
3.19 1.06
0.35 1 0.41
318.28 28 1 132.66
4.81 1 1.13
CSCF
0.62 0.29
229.10
198.01
3.07
1.04
0.02 1 0.15
129 69 23.40
2.68 1 0.45
Hard
MCTS
0.44 0.46
424.77
228.23
4.52 1 1.31
0.57 1 0.45
300.49 1. 134.82
4.77 1 1.27
FACE
0.08 0.20
463.89
86.34
4.36
0.51
0.49 1 0.41
457.94 57.34
6.65 1 0.58
PEAR (ours)
0.84 0.12
123.20
44.21
2.50 0.30
2.50
183+-00 0.21
174.23
41.69
3.44 + 0.40
PEAR (ours)
0.84 + 0.12
124.37 + 60.78
2.50 0.33
0.84 0.84 0.20
175.30 42.79
3.47 + 0.44
23

---

Published in Transactions on Machine Learning Research (01/2024)
(4] w)
(ra) -- Sunberrppnrreeitliiiio 2-
MontalyInccme 300
A
(iajaa
A
A
(F.x)00
(S (t)
ReduceepannCredi tl.cee
(ff m (2)
Micressssaaaar(10000
(aa)
STOP
(ff.)) (3)
TechuceTiineedOPastDaee (-1)
P' HL.
Figure 5: The W-EFARE method. Given (s', w), we traverse the graph (green path) using the decision tree (orange components) to choose the next action (f, (+) from the available transitions. When we reach the STOP node, we return the found intervention I", On the right, have generated intervention achieving recourse for the GiveMeSomeCredi dataset. On the top-right, we have the Boolcan rule extracted from the decision tree motivating the first recommended action ReduceOpenCreditLinnes As we can see, W-EFARE can generate rules that also depend on the cost function C, achieving the desired user awareness.
scarch e.g., the splitting criterion (docision tree) and strength for the regularizer (logistic model). We then replicated the experiments described in Section following the same protocol. In the case of the decision tree, the score of the classifier h(x) is represented by the fraction of the examples of the same class in a leaf. Table 4 shows the evaluation results. PEAR tends to outperform the competitors in terms of cost and validity in 6 out of 6 (GiveMeSomeCredit) and 4 out of 6 (Adult) experiments. The only exception is decision trees Adult, where PEAR is the runner-up behind CSCF, and still purperos all other competitors.
D Explaining Recommended Interventions with XPEAR
PEAR asks the users to choose the best option from a small set of interventions. The task of picking the best. intervention requires cognilive elfort since the user must understand all the recommended sequences of actions. This can be problematic if the user does not comprehend the reason behind the recommendations, undormining the quality of the feedback they provide and their overall trust in the system. To overcome this problem, we additionally developed a variant of PEAR that can complement interventions with action-specific explanations.
As detailed in Appendix A.3, EFARE (De Toni et al., 2023) is deterministic uscr-agnostic model for generating recourse by providing Boolean explanations for each action in the intervention. The procedure be adapted to account for user-specific costs. The resulting model, which we call W-EFARE, is a user-aware version of EFARE that can provide personalized explanations complementing the interventions. Fig. 5 shows a graphical illustration how W-EFARE works in practice. We use this method to develop XPEAR, an explainable version of PEAR, which uses W-EFARE to generate both interventions and explanations which can be shown to the user in the choice set O.
Table 5 shows the evaluation results for XPEAR. We compare it against PEAR, FARE and EFARE since they share similar characteristics and assumptions. For the Adult dataset, XPEAR provides cheaper recourse options than the competitors (FARE and EFARE) by keeping comparable or better validity. The behaviour is consistent for both All and Hard users. For the GiveMesSmeCredit dataset, XPEAR generates sequences with better or similar validity and cost than the competitors, although the effect is diminished. In both datasets, XPEAR has higher validity than its deterministic counterpart EFARE. Overall, PEAR maintains the upper hand. However, it is worth noticing that XPEAR provides additional foedback the users, which might be valuable addition during the elicitation process.
24

---

Published in Transactions on Machine Learning Research (01/2024)
Table 5: Performance of XPEAR averaged over 10 runs. x and XPEAR, indicate XPEAR associated with the noiseless and logistic response model, respectively. The best results are boldfaced.
Adult
GiveMeSomeCredit
Users
Corruption
Valdity
Cost
Length
Validity
Cost
Length
FARE
0.90 + 0.27
285.63 + 195.68
3.45 1.19
0.86 + 0.23
161.77 + 107.42
3.27 1.13
EFARE
0.76 + 0.39
306.11 199.02
3.54 1.25
0.67 + 0.38
155.92 109.19
+ 1.18
PE
1.00 + 0.03
142.23 + 61.75
2.84 + 0.59
0.89 + 0.00
96.04 = 31.96
2.79 + 0.42
A11
PEARL
1.00 + 0.04
146.54 + 63.09
2.84 + 0.56
0.89 + 0.00
100.19 + 29.58
2.85 0.48
X
0.97 + 0.13
181.28 + 96.83
2.97 0.73
0.83 0.18
125.00 = 44.88
2.84 0.40
XPEAR₂
0.97 + 0.13
203.08 = 112.29
2.99 0.78
0.85 + 0.19
128.01 = 50.77
2.84 0.46
FARE
0.71 0.44
438.97 + 188.50
4.54 1.21
0.47 0.37
319.46 + 96.36
4.97 0.70
EFARE
0.55 + 0.48
454.03 = 202.76
4.52 + 1.25
0.22 + 0.36
371.58 = 82.18
5.31 0.71
PEAR
0.99 + 0.08
296.37 + 43.84
3.35 0.55
0.58 0.04
251.60 + 51.16
4.59 0.40
Hard
PEAR,
0.99 + 0.09
301.13 + 52.61
3.34 + 0.58
0.58 0.02
262.23 + 45.36
4.64 + 0.36
X
0.97 + 0.13
326.68 + 98.44
3.46 0.66
0.44 0.30
300.97 + 62.14
4.81 + 0.50
XPEAR
0.97 + 0.13
334.58 + 96.28
3.46 0.66
0.45 0.31
313.95 = 66.94
4.88 0.56
E
Further evaluations of PEAR
We now present some graphs showing the relationship between the cost and length of the interventions (Fig. 6) and between the black box model score and the validity iitiiittyninteentionss length (Fig. 7).
In Fig. 6, we can see that the length of an intervention Namely, there are long interventions which still retain small cost effort for the user. Thus, need to optimize for both the length and cost of interventions simultancously. This notion is reflected in the reward function of N-FARE as we mentioned in Appendix B.
be bad proxy for the intervention's difficulty.
In Fig. 7, we see how the black box prediction score is a good metric to understand how hard is for user to obtain recourse. Namely, we suggest longer interventions for users obtaining a low score with respect the others. Moreover, all the methods tend fail to provide recourse users with low scores. Interestingly, methods which learn recourse policy rather than performing direct optimization (e.g., PEAR and FARE) are more capable of providing recourse generalizing over the low-score users.
25

---

Published in Transactions on Machine Learning Research (01/2024)
Adult (Users Bard)
GivetleSomeCredit (Users Hard)
800
000
Cost
600
200
Method
Adult (Users A11)
Givetee8omeCredtt (Users A11)
PEARs:
3000
PEAR,
000
Length 5
Length
(a) PEARNT. and PEAR,..
Adult (Users Hard)
GiveNeScasCredit (Users Hard)
1000
Cost
730
Method
250-
PEARyZ
PEAR;
RC.
Adult (Users A11)
GiveNeeoneeredii (Users A11)
FACE
1250
CSCP
1000
MCT3
Cost
300
250
11
8
2
Length
Length
(b) All the methods.
Figure 6: Cost vs Intervention Length. (Top) In the Adult dataset, PEAR generates interventions whose costs do not depend their length (for both All and Hard users). The relationship is more pronounced on the CàveMeSomeCredit dataset, but longer interventions (e-g., 7| 5) still present high variability in the costs. These results hint at the fact that length alone can be bad proxy to measure the "effort" of a user. (Bottom) We plot the same results for all the methods. The relationship between cost and length is well represented here, and it aligns with the previous findings.
26

---

Published in Transactions on Machine Learning Research (01/2024)
Adult (Users = Al1)
CiveMeeonnCreddls (Users A11)
Method
PEARML
Model Score
PEAR;
FACE
0.0
8
2
3
8
FFARF.
Length
Length
Model Score Length.
Adult (Users = Al1)
GiveMeBoneCredi1 (Users A11)
Method
PEARMA
0.4
Model Score
PEAR,
0.24
FACE
CSCP
0.0
1.0
0.0
1.0
Validity
Validity
(b) Model Score Validity.
Figure 7: Model Score Length (Top). In the Adult dataset there is a clear correlation between the score and the length of the interventions. Lower scores indicate harder individuals who need longer sequences to obtain recourse. In the CiveMeSomeCredit case, can still see the trend, even if FACE and MCTS seem to be less susceptible. Model Score vs Length (Validity) (bottom). In the Adult experiment, all the models have low validity only in the lower-scoring users. In the GiveMeSomeCredit experiments, PEAR and FARE are the only two methods which have low validity only for the Hard users, while the others tend to fail more often, irrespectively of the classifier score.
27


Reviews:
[{"review_id": "eNNFFDzOJT", "reviewer": "Reviewer_3FLo", "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": "strength:\n* the paper is well-written, I am not up-to-date with the latest literature on AR but the approach seems original to me\n* the paper presents a self-contained approach that addresses several technical challenges (learning the parameter of the cost model, exploring action sets and infering best actions) in a meaningful way. The technical novelty is not that large, but the overall approach and makes sense\n\nweaknesses:\n* the main weakness I see (as for many if not all papers on AR) is that we are still in the realm of theoretical experiments. It is unclear from the paper how realistic the assumptions and approach is.\n* there is no discussion regarding potential biases of the approach (either hidden in the prior, or maybe in the learning algorithm that would favor \"majority\" costs if they exist). Would there be ways to address/measure those?", "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 proposes the study of personnalized algorithmic recourse, which is the problem of finding an intervention of minimal cost that overturns an algorithmic decision, where the cost is unknown and depends on the individual who is affected by the decision.\n\nThe authors propose PEAR, which is based on a bayesian preference ellicitation algorithm to explore the space of possible actions and costs. The various components of the approach, namely the cost correlation structure which mimics a causal model, the inference of actions based on the current knowledge of the costs and the learning algorithm per se are described. The experiments are made using two standard ML datasets and contain relatively thorough ablations/robustness analyses.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "no requested change. From what I can see and what I understand of TMLR criteria, the submission is up to TMLR publication standards", "broader_impact_concerns": "none that I can think of", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "414WgWb0Ke", "reviewer": "Reviewer_uhhX", "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": "[Disclaimer, I am not an expert in algorithmic recourse and I cannot judge of the contributions compared to the vast literature on the topic]\n\n== Strengths ==\n* The paper is impeccably written, which made it accessible to me as a non-expert of the domain \n* Experiments are strong and show competitive performance\n* The core idea of the algorithm is elegant. It builds on existing work but I would not call it incremental as it introduces several improvement, most importantly the personalized aspect. \n\n== Weaknesses == \n\nAppart from theoretical principles used to build the algorithm(s), the paper proposes no theoretical guarantees on the defined regret of the algorithm. For instance, I am a bit surprised that the number of users in the data, and perhaps the number of their 'type' does not appear anywhere. Shouldn't it affect how efficient the algorithm is at personalising the interventions? \n\nThe influence of T (the iteration budget, or horizon in the online learning parlance) on the quality of the learnt cost and interventions is only studied experimentally, for T=10. \n\nI also wonder how the number of base actions influence these performances. \n\nThat being said, I recognise that this may be beyond the scope of the paper.", "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 proposes a new personalized algorithm for algorithmic recourse that is based on RL principles and an elegant submodular optimization idea. The goal is to find an 'intervention' I, which is a combinatorial set of actions (recommendations) that will be presented to a user so they can work out a way to change a decision initially made by a system (like a credit attribution). Each action of this set has a cost for the user so the system must find a personalized and *least costly* set of action that still manages to have a positive impact on the decision for the user. In general this problem involves solving a complex combinatorial cost minimization problem, but under a specific 'noiseless' response model, the problem becomes submodular and can be solved greedily. \n\nResults are evaluated empirically on several real datasets and show that the algorithm achieves the goal it was trying to reach (minimizing a certain regret with low cost interventions), and outperforms existing state of the art methods.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I don't have specific request, but I'd find it interesting if the authors could at least highlight the main interesting theoretical questions that their work could raise and, if they can, explain what are the main technical challenges.", "broader_impact_concerns": "This question is addressed in the paper and I have no further concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "iwf3G9ktQc", "reviewer": "Reviewer_8wdY", "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": "While the probleem looks interesting, there are many aspects of the paper that I find unclear. \n\n1. One key aspect of the paper is the cost of an intervention, in Equation (3) and (4). Yet, I do not understand (at all) why should this model make sense. Especially, this cost involves some weight vector\"w\" -> is it important that the cost has this form (linear in w plus effect of intervention)?  Could the authors explain why the cost is like this? (e.hg. provide references)? Does this make sense for the application that is used as an example? \n\n2. The experiment setting is not clear to me:\n- I think that the part about the dataset could serve to illustrate the model and for instance illustrate the concept of dependence graphs, cost of actions... For now, there is very little details about what are \"s\" and \"a\" for the considered problems/\n- Q1: what is the \"rescaling\" used? The authors claim that PEAR \"minimizes\" regret: should the minimum be 0? It probably reaches a \"low\" regret but does it really \"minimize\" the regret? Would the \"regret\" goes to 0 as T goes to infinity?\n- Q2: the authors compare their algorithm to other algorithms in the literature. But do these algorithm try to minimize the same cost as the one defined in the paper? If not, it seems quite obvious that they will not perform well for the chosen metrics.\n\n3. Notations and writing should be improved:\n- Section 2 \"problem statement\" is (I think) impossible to understand before having read section 4 because nothing is defined here: what is w? What is s^{(0)}? What is I^{GT}?... \n- Section 4 is really confusing, partly because notations are not always consistent (e.g., some \"s\" become s^{(0)} or s^{(1)} but not always, for instance between (4) and (5)). The non-additivity is quite obvious once the correlation structure is understood. I would encourage the authors to completely rewrite the section between 4 and 4.1 (and probably mix this with section 2), and to try to justify the correlation model. The rest of the section (4.1 to 4.4) is relatively classical but could have its own section.", "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 studies the problem of \"algorithmic recourse\" where an algorithm proposes a user a sequence of actions so that this user can improve its classification score. The originality of the algorithm is that the sequence of actions is tailored to some (unknown) user's preference. The authors uses a Bayesian approach to learn this (unknown) preferences by using a weight vector. Some simulations illustrate that this algorithm works;", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please correct Weaknesses 1 to 3 above:\n1. justify the cost model\n2. clarify the role of the numerical section\n3. improve notation consistency and general organization of the paper.", "broader_impact_concerns": "This paper does discuss some impact of the paper which seems appropriate.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies algorithmic recourse, the problem of suggesting a sequence of actions to a user impacted by an algorithmic decision to change the decision in the future. The difference from prior works is personalization based on user preferences, which are elicited by interacting with the user. The proposed approach is compared to multiple baselines on two real-world datasets.

The reviewers generally praised the paper for good writing and convincing experiments. The concerns of the reviewers were addressed in the rebuttal and the authors also updated the paper. One limitation of this work is that it does not come with any theoretical guarantees on regret minimization. The reviewers agreed that this is not necessary.

Congratulations for acceptance!
Decision: Accept (poster)