Algorithmic Recourse for Long-Term Improvement
Authors: Kentaro Kanamori
Ken Kobayashi
Satoshi Hara
Takuya Takagi
Venue: ICML 2025 poster (2025)
Keywords: algorithmic recourse
counterfactual explanation
contextual linear bandit
contextual Bayesian optimization
Primary area: social_aspects->accountability_transparency_and_interpretability

Abstract: Algorithmic recourse aims to provide a recourse action for altering an unfavorable prediction given by a model into a favorable one (e.g., loan approval). In practice, it is also desirable to ensure that an action makes the real-world outcome better (e.g., loan repayment). We call this requirement *improvement*. Unfortunately, existing methods cannot ensure improvement unless we know the true oracle.  To address this issue, we propose a framework for suggesting improvement-oriented actions from a long-term perspective. Specifically, we introduce a new online learning task of assigning actions to a given sequence of instances. We assume that we can observe delayed feedback on whether the past suggested action achieved improvement. Using the feedback, we estimate an action that can achieve improvement for each instance. To solve this task, we propose two approaches based on contextual linear bandit and contextual Bayesian optimization. Experimental results demonstrated that our approaches could assign improvement-oriented actions to more instances than the existing methods.

Algorithmic Recourse for Long- Long-Term Improvement
Kentaro Kanamori
Ken Kobayashi?
Satoshi Hara Takuya Takagi"
Abstract
to æ can regard the perturbation a as recourse action for obtaining the desired decision result y from the classifier h (Karimi et al., 2022). For example, let us consider a situation where a bank deploys a model h for predicting whether a loan applicant will repay the loan or default, and a user æ gets the loan application rejected by h. To help the user z get the loan approved, AR suggests an action a that changes the prediction result of h from "default" to "repayment." We call such action as valid with respect to h, or h-valid for short, across the paper.
Algorithmic recourse aims to provide a recourse action for altering unfavorable prediction given by a model into a favorable one (c.g., loan ap- proval). In practice, it is also desirable to ensure that an action makes the real-world outcome better (e.g., loan repayment). We call this requirement improvement. Unfortunately, existing methods cannot ensure improvement unless we know the true oracle. To address this issue, we propose a framework for suggesting improvement-orientee actions from a long-term perspective. Specifi- cally, we introduce a new online learning task of assigning actions a given sequence of instances. We assume that we can observe delayed feedback whether the past suggested action achieved improvement. Using the feedback, we estimate an action that can achieve improvement for each instance. To solve this task, we propose two ap- proaches based on contextual linear bandit and contextual Bayesian optimization. Experimental results demonstrated that our approaches could assign improvement-oriente actions to more in- stances than the existing methods.
While conventional AR methods focus on providing ac- tions that change the prediction result by a model h (i.e., h- validity), they often overlook whether the user's real- world outcome actually improves. This gap is critical in real-world applications. For example, in the loan approval scenario. even if the prediction of h changes from "default" to "re- payment" by executing the suggested action a, the user may fail to repay the loan if the suggested action a does not actually improve the user's 's underlying payment capability. Such a gap between the prediction result and real-world out- come can result in degrading the quality and reliability of decision-making (Hardt et al., 2016; Rosenfeld et al., 2020; Estornell et al., 2023; Friedbaum et al., 2024).
To fill this gap, (König et al., 2023) introduced improvement as an additional requirement for AR, which focuses on pro- viding actions that improve the user's real-world outcome. Let ht: + y be the unknown oracle that returns the real-world outcome corresponding to a given input. (König et al., 2023) claims that actions should be valid with respect to the oracle h", which we refer to ht* i--validity to dis- tinguish it from the validity for the classifier h. While the classifier h is commonly trained to be a proxy for the oracle h", it is not completely equivalent to h² in practice due to various factors such as data limitations, model complexity, and evolving real-world conditions. Thus, since completely filling the gap between h and h" is unrealistic, h- h-validity does not always imply h h-avviidity. It indicates that ensuring ht -valiiiyyty is fundamentally difficult for the conventional formulation of AR that relies solely on h.
1. Introduction
Machine learning models have been applied to real-world critical decision-making tasks like loan approvals, where predictions significantly impact human users (Rudin, 2019). Thus, decision pacciisnn-makrss are expected to explain how users can alter undesired predictions (Miller, 2019; Wachter et al., 2018). Algorithmic Recourse (AR) aims to provide such information (Ustun et al., 2019). For a classifier h: X + V, desired class y" E D, and an instance æ E X, AR provides perturbation vector a that leads the instance x the desired class y", i.e., h(x + a)= = y", with minimum effort measured by some cost function The user corresponding
'Fujitsu Limited, Japan Insstitte of Science Tokyo, Japan 'The University of Electro- ConettttCommmiictionnn Japan. Correspondence to: Kentaro Kanamori <k..kanaorri fujitsu.com>.
To address this issue, this paper aims to introduce a new framework of AR for ensuring improvement from a long- term perspective. While the oracle h" is unknown, it natural assume that we can observe the outcome h" (x+a)
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Algorithmic Recourse for Long-Term Improvement
Outcome
know the costs of candidate actions for each instance Øt- Then, we apply the existing efficient algorithm based on LinUCB (Li et al., 2010) to solve our task. We also show that the average improvement achieved by our algorithm is guaranteed to increase with high probability as the number of rounds progresses.
Action suggestion
User (agres to execule)
ropayment
default
Agent
No feodhack
User
(disagro to execute)
We also propose a heuristic approach based on the contextual Bayesian optimization (CBO) that can be applicable even if we do not know the cost function c. We show that our task can be regarded as a CBO prob- lem under delayed feedback (Verma et al., 2022). To alleviate the scalability issue of the existing algorithm based on the Gaussian process, we propose scalable algorithm by leveraging a surrogate model based on the extremely randomized trees (Kim & Choi, 2022).
Delayed feedback
Figure 1. Outline of our proposed framework. For given instance x conreponning to a user, our agent suggests an action a that is estimated as h -valid for æz Then, the user determines whether to execute a based on its cost. If the user executes a, the agent observes the delayed feedback on its outcome li" {æ + a). Using the observed feedback, the agent estimates a / -valid action a' for the subsequent instance x'. The agent repeats this procedure.
Our experimental results on real datasets demonstrated that our approaches could achieve improvement for more instances than the existing AR methods. Further- more, our CLB-based approach could provide actions with comparable costs to the existing methods in the situation where we know the cost function e. We also confirmed that when the cost function includes un- certainty, the performance of our CBO-based approach is close to or better than our CLB- -LB-based approach.
after user executes suggested action a. In the loan approval example, bank cannot know in advance whether user a will successfully repay the loan. However, once the loan is approved after executing the suggested action a, the bank can monitor whether the user æ truly manages to repay it. Thus, we consider a situation in which instances arrive one by one, and for each instance æ, we suggest an action a and later observe its outcome h (x + a). as shown in Figure 1. Our goal is to suggest h""valid actions with low costs for as many instances as possible by exploring potentially improvement-orientte actions and exploiting the sequentially observed outcomes, which we refer to as long- term improvement. To this end, we aim to train an agent that can suggest -valid actions for each instance with high probability as the agent obtains more feedback.
1.2. Related Work
Algorithmic Recourse (AR) (Ustun et al., 2019), also referred to as Counterfactual Explanation (Wachter et al., 2018), has attracted increasing attention in recent years. While the pre- vious studies have proposed several extended formulations of AR (Kanamori et al., 2020; 2021; 2022; 2024), almost all of the existing AR methods focus on providing actions that achieve only fo-validity (Karimi et al., 2022; Verma et al., 2020; Guidotti, 2022). To the best of our knowledge, (König et al., 2023) and (Friedbaum et al., 2024) are the two exceptions. (König et al., 2023) first introduced the concept of improvement, or --aviiiiity. To evaluate the --lviiidity, their proposed method uses a causal graph between features and the target class. However, their method can be applica- ble only to situations where we are given true causal graph of the underlying data (Karimi et al., 2020). (Friedbaum et al., 2024) trains verifier that estimates the h- -validity of each action. As we demonstrate in the experiments, the quality of the verifier hinders the accuracy of this approach.
1.1. Our Contributions
In this paper, we propose Algorithmic Recourse for Long- Term IMprovement (ARLIM), new framework of AR for ensuring improvement. Our contributions are summarized as follows:
We introduce a new online learning task where an agent aims to provide/ h² -valid actions a1,.... ar to a given sequence of instances æi.... Vy. In each round f, the agent can observe delayed feedback on whether the suggested action a, was -vaiid for the instance x of the past round < if x. has executed ag. Using the feedback, the agent estimates an action a; that is -vaiid for the current instance x, with a low cost. The goal of the agent is to assign /1" "valid actions with reasonable costs to as many instances as possible.
There exist few papers that study the online setting of AR. For example, (Creager & Zemel, 2023) proposed the setting of online AR where the model h is updated dynamically. However, they focus on updating the model and do not consider long-term improvement. Another example is the work by (Cao et al., 2025) that proposed AR for CLB. In contrast, we study AR for a model h trained by supervised learning method and use CLB to suggest h -valid actions.
For our formulated task, we propose an efficient ap- proach based on the contextual linear bandit (CLB). We show that our task can be reduced to a CLB problem under delayed feedback (Vernade et al., 2020a) if we
2

---

Algorithmic Recourse for Long-Term Improvement
2. Algorithmic Recourse
outcomes, we aim to suggest actions that are both h- and h" -valid with low costs for many instances as possible, which we refer to as long-term improvement. In this section, we formulate this task as an online learning problem.
For a positive integer n E N, we write [x]] : (I..... n). As with the previous studies, we consider binary classification task between undesired and desired classes. Let X' _ RD and V = {0, 1} be input and output domains, respectively. We call vector x = (x1, (x1,...,, xD) E X' an instance, and function h: X' + Y' a classifier. Without loss of generality, we assume that f((x)= = 1 is a desirable result. For example, in a loan approval task, h(z) = 1 means that a classifier h predicts a user xr has the capability to repay the loan.
3.1. Reward Model and Stochastic Delay
To formulate our task, we define our criterion for evaluating an action ag assigned to an instance D; as a reward. In this paper, we assume that we can observe the outcome h" (æz + ar) following the unknown distribution P(Y | X = xt + az) if the suggested action a, is executed by æt However, the user 2, may not execute a if its cost c(a: mx) is higher than expected (Wu et al., 2024), which makes its outcome h" (x; + ar) unobservable. To encourage the user Φ, to execute the suggested action a,, its cost c(a; | x;)) should be as low as possible. Therefore, our reward model needs to take into account the cost c, as well as h -validiity.
For an instance Φ E X, we define an action as a perturbation vector E R such that + a E X. Let A(x:) be set of feasible actions for x such that A(æ) C {a E TRD a + +aa E X}. For a classifier h. an action a is valid with respect to h. or hivalid for an instance x if h(e + a) = 1.
For æ E X' and a E A(x)), a cost function e: A(x) + Rg0 measures the required effort for æ to execute a.
Based on the above motivation, we define our reward model. Let B(p) be the Bernoulli distribution with p E [0, 1]. Then, we define reward R₂ E (0, 1) of assigning an action a to an instance æ, of round / as follows:
Given a classifier h: X' + y' and instance x X, Algo- rithmic Recourse (AR) aims to find feasible action that is h-valid and minimizes its cost c(a x)) for æ. It can be formulated as follows (Karimi et al., 2022):
Re ~ ((E(aa ax)) I(a; [x)),
(2)
A(m) caa x) s.t. h(x + +a)= 1.
(L)
where E(a x) and I(a | x)) are the probabilities that an instance x executes a and that an action a achieves improve- ment (i.e., -vaaviidyyy) for æ, respectively. Following the existing work (Fokkema et al., 2024), we define the former as F. x) == exp(-v c(a a:)) with a parameter By definition, the executing probability E(a | x) of an action decreases exponentially in its cost c(a x)) We de- fine the latter as I(a x) == P(Y = =1 X = x+a)) which is unknown for us. Note that we can relax the definition of the improvement probability / I(a x) to the deterministic one by setting [(a x) h² (z + a), which is a special case of our definition of L(a x)) In a nutshell, if an action a, is valid for an instance œ, and its cost c(a, xx) is low, its reward R. takes 1 with high probability.
Throughout this paper, we assume that set of feasible
actions can be expressed as A(x)) = [1, un] x x... ....X x [ uD] with lower and upper bounds la, Ud E R for d E [D]. For example, we can express an immutable feature (e.g.. gender) by setting la = ud = 0, and a feature that is allowed to be only increased (e.g., education level) by la = and ua > O, respectively. We also assume that a classifier h is fixed.
O.
3. Problem Formulation
The goal of this paper is to suggest an action a that achieves improvement (König et al., 2023) for a given instance xc Let ht: X + y be the unknown oracle that maps an input to its real-world outcome. Then, ensuring improvement is equivalent satisfying h² (ar a)= = 1, i.e., h"-validity. In practice, however, we can not evaluate the ht" -aliiiiyyy for arbitrary x and in advance. Thus, it is fundamentally diffi- cult for the existing formulation (1) to ensure improvement.
In our scenario, it is natural that we can not immediately observe the reward Rd after assigning a to It. This is because there are delays until the instance æt executes at and its outcome h² (x, + a.) becomes observable. To model such delays, we consider the stochastic delayed feedback setting (Vernade et al., 2017) where observe the reward Rd of round & at the future round + D., where D, E N is delay variable drawn from an unknown distribution D.
To ensure improvement, we extend the existing problem set- ting of AR from the long-term perspective. While the oracle h is unknown, it is natural to assume that we can observe the outcome h" h"(x + a) after a user æ executes a suggested action a, as described in Section 1. Thus, we consider situation in which instances 1;, 222 ................................ .T arrive one by one. For each instance It, we suggest an action a and later observe delayed feedback on its outcome h² (xx + a,), as shown in Figure 1. By exploring potentially improvement- oriented actions and exploiting the sequentially observed
3.2. Overall Problem Setup
Using our reward model, we formulate our task as an online learning problem between an agent and an environment. In each round f E [T], the agent receives an instance 2, and selects an action a among feasible and h-valid actions (i.c., a, E A(xx) and h(s, + a.) = 1). Then, the environment
3

---

Algorithmic Recourse for Long-Term Improvement
samples a reward Rg following our reward model defined in (2). The goal of the agent is maximize the mean expected reward R(T)= := + of E[ that is, to assign actions a; that achieve h" -validity with low costs to as many instances Dt as possible. Our task, named Algorithmic Recourse for Long-Term IMprovement (ARLIM), is formulated as follows.
Using X, we construct A, as follows:
A = A(z)) n {a ak
(3)
Note that any action a E A is feasible and h-valid for æy by definition. We also assume that the agent knows the cost function c and parameter v. It means that the agent can compute E' xx) for any a E A,. Note that any existing cost function can be used as c, such E f1-norm (Wachter et al., 2018) or max percentile shift (Ustun et al., 2019).
Problem 3.1 (Algorithmic Recourse for Long-Term IM- provement, ARLIM). We assume a classifier h: X + V For each round E {1, ...,,..; repeated between an agent and environment:
; T), the following procedure
Under the above assumptions, we show that Problem 3.1 can be reduced to a variant of the CLB problem.
1. The agent receives an instance 2e E X' with h(x)= = 0 from the enviromment, and constructs a set of candidate actions As that are feasible and h-valid for æt.
Proposition 4.1. We assume that At of each E [T] is constructed as (3) and the cost function e and parameter v are known. Then, Problem 3.1 is reduced to a CLB problem under stochastic delayed feedback (Vermade et al., 2020a).
2. The agent selects an action a₁ Ar based on past observations and sends it to the environment.
3. The environment samples reward R2 and delay D, from ((E(a,)) xz4) I(a ax))) and D, respectively.
Proof (sketch). We denote A, = -aa........ aL). By def- inition, there exists mapping my: [L] [K] such that Dt + a: zz,(1) for any 1 E [L]. Let (c(as) E(a; x.) (x)()), where eg E {0, 1] is the binary vector where its k-th element is 1 and the others are O. By definition, we have 7(a: xx.) = P(Y = 1 X = (x)())) We denote 0 = (P(Y = 1 1 X = "i....,,(("" = 1| X = =xx)) and A, (a,)) respectively. Then. we have ATO F(a, x.)- I(a; sr.). Therefore, our reward R2 of the round t can be expressed as R2 BB4, 0). Furthermore, oe (a) 0 E [0, 1] and [()(a))l2 S hold for any a E A.. The above facts and the definition imply that Problem 3.1 is reduced to the CLB problem under stochastic delayed feedback defined in (Vernade et al., 2020a).
4. The agent observes a set of the past rewards {Rs
$ + D2- = = that become observable at round
The goal of the agent is to maximize the mean expected reward R(T)= = + Σ E[R.] over the total rounds T.
By solving Problem 3.1, we are expected to suggest recourse actions that achieve improvement with reasonable costs for as many instances as possible. In Sections and 5, we propose two practical approaches for solving Problem 3.1.
4. Contextual Linear Bandit Approach
Proposition 4.1 shows that Problem 3.1 can be reduced to the CLB problem under stochastic delayed feedback if how to construct the candidate actions Ag limited to (3) and the executing probability E is known for the agent. It implies that we can apply the existing algorithm with regret guarantee (Vernade et al., 2020a) to solve Problem 3.1.
In this section, we propose an algorithm to solve Problem 3.1 based on the contextual linear bandit (CLB) approach. We show that Problem 3.1 can be reduced to the contextual lin- ear bandit problem under stochastic felayef (Ver- nade al., 2020a) if we can compute the executing proba- bility E of each candidate action E A,. Then, we apply the existing efficient algorithm based on LinUCB to solve Problem 3.1 and provide its theoretical analyses. All the proofs of the statements are presented in Appendix A.
4.2. Algorithm
Algorithm I presents our algorithm for Problem 3.1 based on the CLB. As with the proof of Proposition 4.1, we define (:(ai) == E(ay æ:) (I) Algorithm 1 is based on the OTFLinUCB algorithm proposed by (Vernade et al., 2020a), which an extension of the well-known LinUCB algorithm (Abbasi-Yadkori et al., 2011) to the stochastic delayed feedback setting. In the delayed feedback setting, it is not suitable to wait for the rewards of all the past actions until they are observed. Hence, the OTFLinUCB algorithm uses a sliding window of size m and ignores an unobserved reward R, whose delay D, exceeds m by regarding R, = O. Using such censored rewards, Algorithm estimates the unknown parameter by fz-regularized least squares with
4.1. Basic Idea
To show that Problem 3.1 can be reduced to a CLB problem, we make some assumptions on the candidate actions A, and the executing probability E. First, to construct A₁ in each round f, we follow the existing AR methods based on the prototypes (Van Looveren & Klaise, 2021) or nearest unlike neighbors (Brughmans et al., 2024). We assume that the agent is given a fixed set of K instances X {øI,..., ēx) with h()x) 1 for any & E [K], which we call recourse instances. For A E [K], we denote by a = St Dt.
4

---

Algorithmic Recourse for Long-Term Improvement
Algorithm 1 LinUCB
that value. This adaptation would likely lead to improved performance compared to the stochastic delay setting.
Input: Set of K recourse instances X', window parameter T7 > 0, regularization parameter À > O, and confidence level 5 > 0.
1: V/= +- A-; bi < O:
Time Complexity. We can analyze the time complexity of Algorithm in each round E [T] as follows. From the equation (3) and assumption on A(æz), we can construct A in O(K D) time. In addition, by the definition of Φ we can compute (i) V and 0, in ((3)); (ii) ne and be+1 in (m)) (iii) a, in (K)). In total, the time complexity of Algorithm 1 in each round is O(K D K2 + m).
2: for t= 1,..., .....,'o do
3: Receive æi and construct A. by (3);
4: V t - + V/ A,1 144/-1 1-
5: ò. bi:
6: at VX + 2 log (1/0) + K log (1 + 1/KA);
7: Re - 2. ar + Ex=t A, V-= 'A:
8: a: f- arg A, (1 T 0. Ki (e( ()(a)
9: Suggest ar and set At f- @ (aa))
10: Observe {R, + D. = 1)
5. Contextual Bayesian Optimization Approach with BwO Forest
11: D141 + b. + 2 R. I[s D2 = A.;
12:
end for
In this section, we propose an algorithm to solve Problem 3.1 based on the contextual Bayesian optimization (CBO) ap- proach. In contrast to the CLB approach in Section 4, this approach does not require the executing probability E to be known. To this end, we regard Problem 3.1 as the con- textual Bayesian optimization problem under stochastic de- layed feedback (Verma et al., 2022). Then, we propose UCB- based heuristic algorithm that leverages extremely randomized trees surrogate model (Kim & Choi, 2022).
given regularization parameter À= >> O. Then, it determines an action a with the estimated parameter 0 and modified upper confidence bound that takes into account the bias caused by unobserved rewards.
4.3. Theoretical Analysis
Using the regret bound of the OTFLLinUB algorithm (Ver- nade et al., 2020a), we show lower bound on the mean expected reward RT) that can be achieved by Algorithm 1. Proposition 4.2. Algorithm/ I satisfies the following inequal- ity with probability 1 - 8 for any 8 > 0:
5.1. Basic Idea
x x 10, 1] be unknown function such that R2 = g( az) + where A = Ai U...U and e, E R is a sub-Gaussian noise. Then, we can regard Problem 3.1 as the CBO problem under stochastic delayed feedback (Verma et al., 2022) with the unknown objective function g. It indi- cates that we are expected to apply the existing algorithm that is based on the Gaussian process (GP) and has the- oretical guarantees (Verma al., 2022) to Problem 3.1. Unfortunately, in our preliminary experiments shown in Ap- pendix B, we confirmed that the existing algorithm based on GP was significantly slower compared to Algorithm 1.
Let g:
R(T)= 2 RT- IT,
(4)
where R₁ ΣT maxaEA. E(a xx) I(a xt),
IT 4 Verv2KT log YT + mK log yr). Tm
T-mm
P(D1 m), or = vx+ + / log (1/5) + K log YT, and T== = =
Proposition 4.2 implies that the mean expected reward at- tained by Algorithm 1 converges to its upper bound with high probability as increasing T. The first term Ry is the empirical average of the best expected reward, which is the upper bound of RT)). In addition, we have roughly Tr = Olog T/ T)) and thus I' converges to 0 as increas- ing T. This result indicates that the longer our algorithm is deployed, the higher its probability of suggesting actions that achieve improvement with reasonable costs is.
To improve scalability, we employ the bagging with over- sampling (BwO) forest (Kim & Choi, 2022) as a surrogate model instead of GP. The BwO forest is variant of tree- based ensemble models that elaborates prediction uncer- tainty estimation. Tree-based surrogate models are known to have practical merits over GP due to their scalability and ability to naturally deal with categorical features (Hutter et al., 2011). While the BwO forest was originally pro- posed for sequential model-based optimization, it is also suitable as a surrogate model in the CBO problem since it can estimate the mean and variance of the reward for an instance-action pair (I,, a) E X x A.
Note that the delay distribution D impacts the term Fie in our bound of Proposition 4.2. This term increases as the delay D2 ~ DD for the first instance I1 tends to be smaller than the window parameter of our algorithm, which makes our bound better. In essence, the more quickly feedback is received, the better our algorithm performs. In addition, if the delay Dm of each round t is some fixed value and we know it in advance, we can set our window parameter m to
Each decision tree f: X x A + J0, 1] in the BwO forest is trained by bootstrap sampling with oversampling. In each node of the tree, both a split feature and threshold are selected randomly, as with the extremely randomized
5

---

Algorithmic Recourse for Long-Term Term Improvement
Algorithm 2 BwOUCB
it does not require the executing probability E to be known, which is often difficult estimate due to user preferences and uncertainties in the cost function (Laugel et al., 2023; Toni et al., 2024). The BwO forest in Algorithm 2 estimates both E and T from past observations. We also note that Algorithm 2 has no constraints on constructing A,.
Input: Set of K recourse instances X,, window parameter m > O, and number of trees B.
1: Initialize a BwO forest F = [f] with B trees;
2: Z + 00;
3: for t 111=,... ,,..., do
T
4: Receive 2; and construct As;
5: Kit ((//t) logt:
However, Algorithm 2 lacks the theoretical guarantees that Algorithm has, as shown in Proposition 4.2. Additionally, Algorithm 2 requires retraining the BwO forest F in each round, which is computationally expensive compared to the fz-regularized least squares of Algorithm 1. In summary, Algorithm 2 is more practical in situations where estimat- ing E is challenging, such as when the user's 's demographic features are diverse (TTmmnnga et al., 2024; Venkatasubra- manian & Alfano, 2020; Sullivan & Verreault-Julien, 2022). In contrast, Algorithm I is more suitable for tasks with less uncertainty due to its theoretical guarantees and efficiency.
6: a: + arg maxaEA, (( az F) + Ke o(a,, F);
7: 2: + ( dz, 0):0); 2 ZU {
8: Suggest a/:
9: Observe {R, s D. D+
10: for 1- m....., 1oo
11: i D. = 1 and R = then
12:
2 2 (2sti 2 + 2 u {(),, as, R.)}:
13:
end if
14:
end for
15: Train F using 2:
16:
end for
trees (Geurts et al., 2006). Such randomized strategy is known to improve scalability without significantly degrad- ing generalization performance. Using an ensemble of B trained trees F = (/,...., [n]. the BwO forest estimates the mean and variance of the reward of (x, a) as follows:
6. Experiments
To investigate the efficacy of our framework, we conducted experiments on real datasets. All the code was implemented in Python 3.10 and is available at https: github. com/kelice /arlim. All the experiments were con- ducted on macOS Sequoia with Apple M2 Ultra CPU and 128 GB memory. Our experimental evaluation aims to an- swer the following questions: (i) How are the improvement and cost of the recourse actions suggested by our algorithms compared the existing baselines? (ii) Can our algorithms become to suggest better actions as the round progresses? (iii) In which situations is the performance of our CBO- based algorithm (Algorithm 2) close to that of our CLB- based algorithm (Algorithm 1)? Due to page limitations, the complete results are shown in Appendix B.
1 Σ
Ti 1=1 Mbd1 (6, a),
M(x, F) B
b=1
(0, a,, F) = B
_
1
Da
(o%,1 + 13.1) (T, a) - (m(( a; F))
b=1
1=1
where Lg is the total number of leaves in fo. mb. X' x A {0, 1} is the indicator whether sample (zz a) reaches the leaf/ I of fo. and Ma, and of, are the mean and variance of the training samples that reach the leaf l of fs, respectively.
5.2. Algorithm
6.1. Experimental Settings
Algorithm 2 presents our algorithm for Problem 3.1 based on the CBO with the BoW forest. Algorithm 2 is an extension of the GP-UCB-SDF algorithm proposed by (Verma et al., 2022). We replace its surrogate model based on GP with that based on the BoW forest (Kim & Choi, 2022) so as to handle our problem. The surrogate model F is trained using the past histories Z, which a set of tuples consisting of an instance x.. action ag, and reward Rg for the past round s < t. As with OTFLinUCB, GP-UCB-SDE uses sliding window of size m and replaces unobserved rewards whose delays exceed m with R. = O. In each round I, Algorithm 2 determines an action a, based on the upper confidence bound score estimated by the BwO forest F.
Datasets. We used three real-world datasets: Credit (N- 30000, D = 13) (Yeh & hui Lien, 2009), Diabetes (N- 769, D = 8) (Dua & Graff, 2017), and COMPAS (NV 6167, D = 9) (Angwin et al., 2016). All the categorical features in each dataset were one-hot encoded, and all the numerical features were normalized to [0, 1). Details of the datasets and our preprocessing are shown in Appendix B.
Protocol. Since we do not know the oracle h+ in each real dataset, we can not evaluate the outcome h² fxx + a.) if we allow arbitrary actions Φ, for a, However, if there exists a sample (æ, y) in the dataset such that 5 σ; + ai, can regard the label y of ã as a proxy for the oracle outcome h" (xz + aa). Based on this idea, we restrict the candidate actions a, E A, to those that can shift to one of the recourse instances ã E X. More precisely, we randomly collect some instances ã from the dataset as & and construct A,
5.3. Comparison to Contextual Linear Bandit Approach
Here, we discuss the pros and cons of Algorithm 2 compared to Algorithm 1. One main advantage of Algorithm 2 that
6

---

Algorithmic Recourse for Long-Tern Term Improvement
Credit
Diabctos
COMPAS
1.5
Average Cost
ProioAR
Average Cost
Average Cost
LinUCR DwOUCD
1.0
1.01
0.8
0.5
0.00
12.4
0.5
10.5
0.7
0.8
0.9
0.2
0.4
0ub
0.8
1.0
00.2
0.4
0.6
0.5
Average Improvement
Average Improvement
Average Improvement
(a) Average Improvement (higher is better) and Average Cost (lower is better)
Credit
Diabetes
COMPAS
Average MER
ProtoAR
Averagge MER
Average MER
0.3
0.8
TAP
0.7
BrDUCB
066
0.0
0.4
1000
200
600
200
400
1000
Number of Rounds
Number Rounds
Number of Rounds
(b) Average Mean Expected Reward (MER) in Each Round (higher better)
Figure 2. Experimental results of baseline comparison under the noiseless cost evaluation situation. Our LinUCB and BwOUCB attained higher improvement than the baselines, and their the mean expected reward increased the round progressed.
Credit
Diabetos
COMPAS
Average Cost
1.8
Average Chsst
1.2
Average Cust
1.0
10-
ProtoAR
TAP
LinUCCD
1.0
05
BwOUCB
Average Improvement
Average Improvement
Average Improvement
(a) Average Improvement (higher is better) and Average Cost (lower is better)
Credit
Diahetes
COMPAS
Average MER
Avorage MER
Average MER
0.8
ProtoARt LinUCR BwOUCB
0.4
0.0
200
100
1000
200
400
600
800
1000
400
600
1000
Number of Rounds
Number of Rounds
Number of Rounds
(b) Average Mean Expected Reward (MER) in Each Round (higher is better)
Figure 3. Experimental results of baseline comparison under the noisy evaluation situation with the noise level & 0.25. Compared to the results under the noiseless situation, we observed that the performance of BwOUCB was better than or close to that of LinUCB.
by following (3) with X. By constraining each method to select action a, from Ar, we can evaluate h=x + az) by the label of & such that à = æ, a, To simulate the noise of the outcome, we set its improvement probability T(a; 2x)) by adding random noise to y and scaling it in [0, 1]. In summary, we conducted the following procedures:
with ratio of 2: 1::1.
We trained classifier h on the training set S As h, we used random forest (RF) with 100 trees two-layer neural network (NN) with 100 neurons.
We constructed the recourse instance set X with max- imum size = 200 by randomly collecting the in- stances C, in the recourse set S.e such that h(x,,)
1. We randomly split the dataset = {(xn, yn) yn) J into the training set Sur, recourse set Sre, test set Sie

---

Algorithmic Recourse for Long-Term Improvement
Acorage Improveent
Crodit
Averago Inprroveent
Diabeses
Acurago lngoeemeen
COMPAS
imizes E over At, which is equivalent to the standard AR method that solves the problem (1). By the definition of A,, it can be regarded as the existing AR method based on the class prototypes (ProtoAR) (Van Looveren & Klaise, 2021), Another baseline is the trustworthy actionable perturbation (TAP) (Friedbaum et al., 2024) that solves (1) under the con- straint on trustworthiness, which is the true label probability of + a. The trustworthiness is estimated using a verifier that is trained to predict whether a given instance is ad- versarial example. For both LinUCB and BwOUCB, we set m = 10. We also set À = 20.0 for LinUCB and B = 50 for BwOUCB, respectively. The sensitivity analyses of these parameters are shown in Appendix B.
Bartiss DresAR
TAP
Lericts
94
60
211
03
01
65
Noiee Lovel
4
Noti Level
C
Noise Level
(a) Average Improvement (higher is better)
Oradit
Tishbrae
COMPAS
Avenage Clo.
Arrena Cost
Avergg Clud
PrELAR JAI
0.0
Noise Lovd
Nobse Level
Nuise Levd
(b) Average Cost (lower is better)
6.2. Comparison under Noiseless Cost Evaluation
Credit
Diabeses
COMPAS
First, we evaluate the improvement and cost of actions ob- tained by each method. Figure 2(a) presents the results on the average improvement and cost. From Figure 2(a), we observe that (i) both LinUCB and BwOUCB stably outper- formed the baselines in terms of the average improvement all the datasets; (ii) LinUCB attained comparable aver- age cost to the baselines. These results indicate that our methods could suggest actions that stably achieve higher improvement than the baselines, and our LinUCB achieved higher improvement while maintaining comparable costs.
Average MER.
Aver MER
Astrago MER.
44
02:
0.1
Noion Tavell 5
Neion Tevel
Noise Taveel
(c) Average MER of the Final Round (higher is better)
Figure 4. Sensitivity analyses the noise level &. BwOUCB does
not use the executing probability E. its performance is independent of g. We can see that the performance of BwOUCB became close to better than the other methods as & increased.
Figure 2(b) shows the average mean expected reward of each round. From Figure 2(b), see that the average mean expected rewards of LinUCB and BwOUCB increased as the number of rounds progressed, which are consistent with Proposition 4.2. Therefore, we confirmed that our methods became to suggest better actions in the sense of their improvement and cost as the round progressed.
For each F E X, we set P(Y 1 1 x.)) max(min(( + 0.1 E,, 1.0), 0.0), where 1).
4. We obtained a sequence of instances 2 2i,..., Br with T 1000 by randomly sampling the instances x,, in the test set Ste such that h(x.) 0 and yn 0. Then, we started the procedure of Problem 3.1.
6.3. Comparison under Noisy Cost Evaluation
Next, we examine each method under the noisy cost eval- uation situation. To simulate the uncertainty the cost evaluation, we added a noise & E to the execution probabil- ity E(a æx) and scaled it in [0, 1]. where E 2 0 is a noise level parameter and ~ (/ 1). Such noisy information on E was passed to methods other than BwOUCB. Figure 3 presents the results with the noise level & = 0.25. From Figure 3(a), we can see that both LinUCB and BwOUCB tended to achieve higher average improvement than the base- lines, as with the results shown in Figure 2(a). On the other hand, the gap between the average cost of BwOUCB and the others decreased compared to the results under the noiseless situation. Furthermore, from Figure 3(b), we observe that BWOUCB achieved higher average mean expected rewards than LinUCB on all the datasets in the final round.
We repeated the above procedures 10 times. We used the f1-norm ||a]/ as the cost function e and set v = 1/D for computing the executing probability E. In each round E (T), all the methods receive the instance æ, and its candidate actions A. constructed by (3). In addition, the methods other than BwOUCB receive the execution probability E(a æz) for each a E Ar. As the delay distribution D, we used the geometric distribution with the parameter 0.2. We measured the average of (i) improvement (i.e., h² -validiity),, (ii) cost c(a; xt), and (iii) mean expected reward (MER) R(t) in each round t. Due to the page limitation, we report the results on RF here, and those on NN in Appendix B.
Baseline and Our Algorithm. To the best of our knowl- edge, there is no existing AR method that ensures improve- ment from the long-term perspective. Thus, we compare our algorithms (LinUCB and BwOUCB) with two existing methods as baselines. One baseline is a method that max-
Finally, we analyze the sensitivity of the performance of each method to the noise level &. Figure 4 shows the results of the sensitivity analyses of the average improvement, cost,
8

---

Algorithmic Recourse for Long-Term Improvement
and mean expected reward in the final round by varying S. Note that since BwOUCB does not use the executing probability E, its performance is independent of the noise level Ç. From Figures 4(a) and 4(b), we can see that the av- erage improvement and cost of LinUCB were worse than or close to those of BwOUCB as & increased. In addition, from Figure 4(c), we observed that the average mean expected reward of LinUCB became lower than BwOUCB as & in- creased. In summary, we confirmed that the performance of BwOUCB was close to or better than that of LinUCB in the situation where the cost evaluation includes uncertainty.
over time (Upadhyay et al., 2021). While we empirically confirmed that our methods work better than the baselines even in the scenario where the classifier is frequently up- dated in Appendix B.5, extending our framework so as to adaptively handle such a non-stationary setting is interest- ing. Second, our framework implicitly assumes that users execute their suggested actions completely if they accept to execute the actions. In practice, users may execute the ac- tions partially or incorrectly (Pawelezyk et al., 2023), which can lead to a gap between the observed feedback and the true outcomes. Finally, deriving better theoretical guaran- tees for our algorithms is important for practical applica- tions. While we show a theoretical bound of Algorithm I in Proposition 4.2, it depends on the total number of arms K, which weak in the literature of CLB (Vernade et al.. 2020a). is also important to derive a theoretical guarantee for Algorithm 2 by extending the existing regret bound of CBO (Verma et al., 2022). Furthermore, since our model and algorithm are direct applications of the previous studies on CLB and CBO, is an interesting direction for future research to design more suited models and algorithms for Problem 3.1 (Bouneffouf et al., 2020; Wang et al., 2023).
7. Conclusion
This paper proposed algorithmic recourse for long-term improvement (ARLIM), new framework for providing recourse actions that not only alter the undesired prediction results but also improve the real-world outcomes. We intro- duced a new problem setting in which instances arrive one by one, and the agent suggests an action for each instance and later observes delayed feedback on its outcome. By exploiting such feedback, we aimed to train an agent to suggest an action that improves the real-world outcome for each instance. We formulated our task as online learning problem and proposed two practical algorithms based on contextual linear bandit and contextual Bayesian optimiza- tion. Experimental results demonstrated the efficacy of our methods in comparison to the existing baselines.
Acknowledgments
We wish to thank Yuichi Ike and Shion Takeno for mak- ing a number of valuable suggestions. We also thank the anonymous reviewers for their insightful comments. This work was supported in part by JST ACT-X JPMJAX23C6, JSPS KAKENHI Grant-in-Aid for Early-Career Scien- tists 24K17465, Grant-in-Aid for Scientific Research(B) 23K28146, 146, and IMI Joint Usage/Research Center in Kyushu University (FY2024 Short-term Joint Research 2024a032).
Limitations and Future Work
Our framework has some limitations that should be ad- dressed in future work. One major limitation is the inherent challenges posed by the long-term nature of recourse im- plementation. There exist real-world applications where it may take several years until we observe the feedback the outcomes of suggested recourse actions. Such situations correspond to the case where the delay variable D, ~ D of each round is large. Because such a long-delayed feed- back may lead to a lack of sufficient data for training the agent, it can be problematic for our framework. Note that we are the first to demonstrate the feasibility of suggesting auprovement-orienter actions by exploiting feedback, even when only delayed feedback is available. Even if it takes a long time to observe the first feedback, our framework is expected to work well once it starts to observe feedback. However, to ensure improvement-orienter actions for in- stances in the early rounds, we need to address long delays (e.g., by exploiting intermediate observations (Vernade et al.,
Impact Statement
Our proposed method, algorithmic recourse for long-term improvement (ARLIM), is a new framework for providing recourse actions that not only alter the undesired predictions but also improve real-world outcomes. As mentioned in the paper, this framework can lead to more reliable and ben- eficial decision-making processes by suggesting recourse actions that ensure improvement for as many users as possi- ble. Our focus on long-term improvement can lead to more sustainable and positive outcomes for users, which is benefi- cial for both users and decision-makers. On the other hand, our framework also has potential societal impacts that need careful consideration. For example, our methods rely on the availability of feedback that tracks users over time, which requires us to carefully consider its privacy risk. Overall, the proposed method has the potential to significantly improve the effectiveness and reliability of the decision decision-making pro- cess, but we need careful consideration of its risks before incorporating it into the actual decision-male making process.
2020b; Esposito et al., 2023)), but such an extension of our framework is toivial and remains challenge.
In addition, there are several interesting directions to make our framework more practical. First, while we assume that a classifier h is fixed over all the rounds, it is often updated

---

Algorithmic Recourse for Long-Tern Term Improvement
References
Hardt, M., Megiddo, N., Papadimitriou, C., and Wootters, M. Strategic classification. In Proceedings of the 2016 ACM Conference Innovations in Theoretical Computer Science, pp. 11 111-122, 2016.
Yadkki,,adkori, Y., Pál. D., and Szepesvári, C. Improved algorithms for linear stochastic bandits. In Proceedings of the 25th Conference on Neural Information Processing Systems, pp. 2312-2320, 2011.
Hutter, F., Hoos, H. H., and Leyton-Brows K. Sequential model-based optimization for general algorithm configu- ration. In Proceedings the 5th International Conference on Learning and Intelligent Optimization, pp. 507-523, 2011.
Angwin, J., Larson, J., Mattu, S., and Kirchner, L. Machine Bias. ProPublica, 2016.
Bouneffouf, D., Rish, I,, and Aggarwal, C. Survey on applications of multi-armed and contextual bandits. In Proceedings of the 2020 IEEE Congress on Evolutionary Computation, pp. 1-8, 2020.
Kanamori, K., Takagi, T., Kobayashi, K., and Arimura, H. DACE: Distribution-aware counterfactual explanation by mixed-integer linear optimization. In Proceedings of the 29th International Joint Conference on Artificial Intelligence, pp. 2865-2862, 2020.
Brughmans, D., Leyman, P., and Martens, D. NICE: An al- gorithm for nearest instance counterfactual explanations. Data Mining and Knowledge Discovery, 0222666-2703,, 2024.
Kanamori, K., Takagi, T., Kobayashi, K., Ike, Y., Uemura, K., and Arimura, H. Ordered counterfactual explanation by mixed-integer linear optimization. In Proceedings of the 35th AAAI Conference on Artificial Intelligence, pp. 1 11564-11574 2021.
Cao, J., Gao, R., and Keyvanshokooh, E. HR-Bandit: Human-Al AI collaborated linear recourse bandit. In Pro- ceedings of the 28th International Conference on Artifi- cial Intelligence and Statistics, pp. 2016-3024, 2025.
Creager, E. and Zemel, R. Online algorithmic recourse by collective action. arXiv, arXiv:2401. 100055, 2023.
Kanamori, K., Takagi, T., Kobayashi, K., and Ike, Y. Coun- terfactual explanation trees: Transparent and consistent actionable recourse with decision trees. In Proceedings of the 25th International Conference on Artificial Intelli- gence and Statistics, pp. 1846-1870, 2022.
Dua, D. and Graff, C. UCI machine learning repository. http:/ /aarch ive icss wuc..uii....cccccooooo.......... edc/me 2017. Ac- cessed: 2025-05-20.
Esposito, E., Masoudian, S., Qiu, H., Van Der Hoeven, D., Cesa-Bianchi, N., and Seldin, Y. Delayed bandits: When do intermediate observations help? In Proceedings of the 40th International Conference on Machine Learning, pp. 9374-9395, 2023.
Kanamori, K., Takagi, T., Kobayashi, K., and lke, Y. Learn- ing decision trees and forests with algorithmic recourse. Proceedings of the 41st International Conference on Machine Learning, pp. 22936 229622, 2024.
Karimi, A.H.,, von Kügelgen, J., Schölkopf, B., and Valera, I. Algorithmic recourse under imperfect causal knowl- edge: probabilistic approach. In Proceedings of the 34th Conference on Neural Information Processing Systems, pp. 265-277, 2020.
Estornell, A., Chen, Y., Das, S., Liu, Y., and Vorobeychik, Y. Incentivizing recourse through auditing in strategic classification. In Proceedings of the 32nd International Joint Conference on Artificial Intelligence, pp. 400-408, 2023.
Fokkema, H., Garreau, D., and van Erven, T. The risks of recourse in binary classification. In Proceedings of the 27th International Conference on Artificial Intelligence and Statistics, pp. 550-558, 2024.
Karimi, A.-H., Barthe, G., Schölkopf, B., and Valera, I. A survey of algorithmic recourse: Contrastive explanations and consequential recommendations. ACM Computing Surveys, 55(5): 2022.
Friedbaum, J., Adiga, S., and Tandon, R. Trustworthy tionable perturbations. In Proceedings of the 41st Inter- national Conference on Machine Learning, pp. 14006- 14034, 2024.
Kim, J. and Choi, S. On uncertainty estimation by tree-based surrogate models in sequential model-based optimization. Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, pp. 4359-4375, 2022.
Geurts, P., Ernst, D., and Wehenkel, L. Extremely random- ized trees. Machine Learning, 63(1):3 42, 2006.
König. G., Freiesleben, T., and Grosse- Weesee-e M. Improvement-focusee causal recourse (ICR). Pro- ceedings of the 37th AAAI Conference on Artificial Intel- ligence, pp. 11847-11855, 2023.
Guidotti, R. Counterfactual explanations and how to find them: literature review and benchmarking, Data Mining and Knowledge Discovery, 38:2770-2822 2022.
10

---

Algorithmic Recourse for Long-Term Term Improvement
Laugel, T., Jeyasothy, A., Lesot, M.-.,, Marsala, C., and Detyniecki, M. Achieving diversity in counterfactual explanations: review and discussion. In Proceedings of the 2023 ACM Conference on Fairness, Accountabiliry, and Transparency, pp. 1859-1869, 2023.
Ustun, B., Spangher, A., and Liu, Y. Actionable recourse in linear classification. In Proceedings of the 2019 Confer- ence Fairness, Accountability, and Transparency, pp. 10-19, 2019.
Van Looveren, A. and Klaise, J. Interpretable counterfactual explanations guided by prototypes. In Proceedings of the Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 650-665, 2021.
Li, L., Chu, W. Langford, J., and Schapire, R. E. A contextual- approach to personalized news arti- cle recommendation. In Proceedings of the 19th Inter- national Conference on World Wide Web, pp. 661-670, 2010.
Venkatasubramanian, S. and Alfano, M. The philosoph- ical basis of algorithmic recourse. In Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency, pp. 284 293, 2020.
Miller, T. Explanation in artificial intelligence: Insights from the social sciences. Artificial Intelligence, 267:1-38, 2019.
Verma, A., Dai, Z., and Low, B. K. H. Bayesian optimization under stochastic delayed feedback. In Proceedings of the 39th International Conference on Machine Learning, pp. 22145 22167, 2022.
Pawelczyk, M. Datta, T., van-den Heuvel, J., Kasneci, G., and Lakkaraju, H. Probabilistically robust recourse: Navigating the trade-offs between costs and robustness in algorithmic recourse. Proceedings of the 11th International Conference on Leurning Representations, 2023. URL Id=sC-PMTsi7B.
Verma, S., Boonsanong, V., Hoang, M., Hines, K. E., Dick- erson, J. P., and Shah, C. Counterfactual explanations and algorithmic recourses for machine learning: A review. arXiv, arXiv:2010.10596, 2020.
weteeervvieeneee/forreeeeeeee net/forum?
Vernade, C., Cappé, O., and Perchet, V. Stochastic bandit models for delayed conversions. In Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence, 2017.
Rosenfeld, N., Hilgard, A., Ravindranath, S. S., and Parkes, D. C. From predictions to decisions: Using lookahead regularization. In Proceedings of the 34th Conference on Neural Information Processing Systems, pp. 4115-4126, 2020.
Vernade, C., Carpentier, A., Lattimore, T., Zappella, G., Er- mis, B., and Brückker, M. Linear bandits with stochastic delayed feedback. In Proceedings of the 37th Interna- tional Conference on Machine Learning, pp. 9712-9721, 2020a.
Rudin, C. Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead. Nature Machine Intelligence, 1: 1:206-211 215, 2019.
Vernade, C., Gyorgy, A., and Mann, T. Non-stationary de- layed bandits with intermediate observations. In Proceed- ings of the 37th International Conference on Machine Learning, pp. 9732-9732, 2020b.
Sullivan, and Verreault-Julien, From explanation to rec- ommendation: Ethical standards for algorithmic recourse. In Proceedings of the 2022 AAAI/ACM Conference AI, Ethics, and Society, pp. 712-722, 2022.
Wachter, S., Mittelstadt, B., and Russell, C. Counterfactual explanations without opening the black box: Automated decisions and the GDPR. Harvard Journal of Law & Technology. 31:8418887 2018.
Tominaga, T., Yamashita, N., and Kurashima, T. Reassess- ing evaluation functions in algorithmic recourse: An em- pirical study from a human- centered perspective. In Pro- ceedings of the 33rd International Joint Conference on Artificial Intelligence. pp. 7911- 2024.
Wang, X., Jin, Y., Schmitt, S., and Olhofer, M. Recent advances in bayesian optimization. ACM Computing Surveys, 55(13s), 2023.
Toni, G. D., Viappiani, P., Teso, S., Lepri, B., and Passerini, A. Personalized algorithmic recourse with preference elicitation. Transactions on Machine Learning Research, 2024. URL https: / http///wwwwwe..ee/e///// httpiiiwwwwweeeeeeeeeeem.eeeeeee id id-8sg2I92Xg0.
Wu, H., Sharma, S., Patra, S., and Gopalakrishnam, S. Safear: Towards safer algorithmic recourse by risk-aware policies. In Proceedings of the 38th AAAI Conference on Artificial Intelligence, pp. 15915-15923, 2024.
Upadhyay. S., Joshi, S., and Lakkaraju, H. Towards ro- bust and reliable algorithmic recourse. In Proceedings of the 35th Conference on Neural Information Processing Systems, pp. 5512-8519, 2021.
Yeh, I.-C. and hui Lien, C. The comparisons of data min- ing techniques for the predictive accuracy of probability of default of credit card clients. Expert Systems with Applications, 36(2, Part 1):2473-2480. 2009.

---

(1)) Algorithmic Recourse for Long-Term Improvement
A. Omitted Proofs
A.I. Proof of Proposition 4.1
We show that Problem 3.1 is an instance of the contextual linear bandit problem under stochastic delayed feedback defined as follows (Vernade et al., 2020a).
Problem A.1 (Contextual Linear Bandit Problem under Stochastic Delayed Feedback (Vernade al., 2020a)). We assume a
number of rounds? T E N and unknown parameter 0 E Iº' with ||0 2| S For each round [T]. the following procedure repeated between an agent and environment:
1. The agent receives set of K2 candidate arms V. C E with v T E [o, 1] and ||a|| s 1 for any v Va.
2. The agent selects an arm Vi E V. based on past observations and sends it to the environment.
3. The environment samples reward R₂ E {0, 1} and delay D, E N from B(V 0) and D, respectively.
4. The agent observes of the past rewards (R,s s D, + that becomes observable at round t.
The goal of the agent is to minimize the cumulative regret regret(T)) = ( - -0 where Vi arg max TTv.
Vi),
Proof of Proposition 4.1. For Problem 3.1, we denote A; = fa......, a,))- Recall that there exists a mapping nT [L] + [K] such that æ, + a = (I) for any E [L] by definition. Let de (ax) = E(a; ax)) (x) where e, E {0, 1] the binary vector where its k-tth element 1 and the others are 0. By definition, we have [(a; xx) = P(Y =
We denote (P = X .I....., P(Y
X Øx)) and A, =v((a)) for a, in Problem 3.1. Then, reward R, of the round t can be expressed R. B(A, 0).
have A, 0 = E(a, xx) I(a x2). Therefore, Furthermore, (a) T0 E [0, and [a)]22)] I hold for any a E A.. Finally, minimizing our mean expected reward R(T") is equivalent maximizing Σ (0 A; 0 At), where Aï arg E. 0 (a()). In summary, we can that Problem 3.1 is reduced Problem A.1 by replacing (i) V. with (or(ai)...... di (aL)); (ii) V2 with (a:);; ); (iii) O with (P(Y = X = P(Y 1 X ix)), respectively.
A.2. Proof of Proposition 4.2
Proof. By definition, E[R E(a, xz)) I(a xx) holds. Let R; maXae4, E(a xx) -[a | xx) be the maximum expected reward in round I. Then, by applying Theorem 2 of (Vernade et al., 2020a), we have
T
4
KY Kλ+ + T KX
KA+1
R - [Re)
<
22 log
+ +mK
Tm
KA
1
1
4
KX+
KA+TY
R
B[R
QT
2K log
+mKlog log
T
T
Tm
KA
Kλ
4
R7
R(T) <
Tm
R(T)= 2 Rイ
IT:
Tm
which concludes the proof.
B. Additional Experimental Results
B.1. Details of Datasets and Preprocessing
Table presents the details on the value type, minimum value, mean value, maximum value, and immutability of each feature of the datasets that we used in our experiments. For numerical immutable features such as age in each dataset, we transformed them into binary features by comparing them with their medians. All the categorical features were transformed into binary features by ooe-hot encoding. All the numerical features were normalized [0, 1).
12

---

Algorithmic Recourse for Long-Term Improvement
B.2. Complete Experimental Results of Section 6
present the complete experimental results of the baseline comparison for random forests (RF) and two-layer neural networks (NN) under the noiseless and noisy cost evaluation situations, respectively. Figures 9 and 10 show the sensitivity analyses of the noise level for RF and NN, respectively.
Figures 5
B.3. Problem Settings beyond Assumptions
Here, we examine methods under the scenarios beyond the assumptions of Problem 3.1. First, consider the situation where the cost function that each method knows is different from that is used to compute the reward. In this case, each method receives the executing probability E computed by one cost function e and the reward Rg computed by another cost function c'. We used the &n-norm as and the max percentile shift (Ustun et al., 2019) as c'. Figures 11 to 14 present the results of the cost-mixture scenario. We can see that the performance of BwOUCB was close to or better than that of LinUCB, even in the noiseless cost evaluation situation.
Second, we consider the situation where the delay D, depends on the instance æt. In this case, we sample D, from the geometric distribution with the parameter p 0.2 2t,d + 0.05 (1 zr,a), where Zd E {0, 1} is the feature value of æ that indicates whether its age is younger than the median of the dataset or not. That is, the delay variable Dr is sampled from different distributions depending on the age of the instance I₁. Figures 15 and 16 present the results of the adaptive delay scenario. We observed that LinUCB and BwOUCB performed similarly to the results under the delay distribution that is independent of the instance shown in Figures 5 and
B.4. Sensitivity Analyses of Parameters
Figures 17 and 18 show the sensitivity analyses of the total number of recourse instances K. Figures 19 and 20 present the sensitivity analyses of the window parameter m. Figures 21 to 24 show the sensitivity analyses of the regularization parameter Ả of LinUCB. Figures 25 and 26 present the sensitivity analyses of the number of trees B of BwOUCB.
B.5. Comparison under Non-stationary Setting
We examine the performance of each method under a non-stationary setting where the classifier is updated over time. To simulate this situation, we updated the classifier h using the set of the past instance-reward pairs (æ,, + as R₂) that become observable until round & > s. By varying the frequency of the update, we examined the performance of each method. Figures 27 and 28 present the results of the model update scenario where the update frequency once every 25 rounds. Figures 29 and 30 show the sensitivity analyses of the update frequency. We method was not significantly affected by the update frequency and that these results were not so different from those of the stationary setting.
that the performance of each
B.6. Comparison to Algorithm Based on Gaussian Process
We compare our methods with the existing algorithm based on the Gaussian process (CGPUCB) (Verma et al., 2022) under the same setting with Figure 2. For CGPUCB, we used the radial basis function (RBF) kemel and optimized the kernel parameters once every 10 rounds. Figures 31 and 32 present the results of the comparison. We observed that the performance of CGPUCB was close to or worse than that of BwOUCB. Table 2 shows the average running time of each method each round. We can see that the running time of CGPUCB was significantly longer than that of BwOUCB. summary, we confirmed that the performance of BwOUCB was close or better than that of CGPUCB and BwOUCB was significantly faster than CGPUCB
C. Additional Comments Existing Assets
All the code used in our experiments was implemented in Python 3.10 with scikit-learn 1.5.2. Scikit-learn 1.5.2 is publicly available under the BSD-3-Clause license. All the scripts and datasets are available in our GitHub repository at https: : / git.bb..../. com/kell weeeelcht/rrlll All the datasets used our experiments are publicly available and do not contain any identifiable information or offensive content. As they are accompanied by appropriate citations in the main body, see the corresponding references for more details, All the experiments were conducted on macOS Sequoia with Apple M2 Ultra CPU and 128 GB memory.
13

---

Algorithmic Recourse for Long-Term Improvement
Table 1. Details of the datascts used the experiments.
(a) Credit (Yeh & hui Lien, 2009)
Feature
Type
Min
Mean
Max
Immutable
Married Single
Binary
0
0,455300
1
Yes
Binary
0
0.532133
1
Yes
Age It 40
Binary
0
0.724200
1
Yes
EducationLevel
Numerical
2.157733
3
No
MaaBBilAAmmommovvrsssssttoottt
Numerical
1849.565000
50810
No
Numerical
483.785333 0
51430
No
Numerical
0.788833 0
6
No
Numerical
2.833133 0
6
No
Months Sootts-WWihhiigSSSeeuuungvrvvroo
Numerical
1,208333 0
6
No
MostRecentBillAmount
Numerical
1564.743000
29450
No
MostReceetPaynnentAAmuuu
Numerical
172.783000
26670
No
TotalOverdueCounts
Numerical
0.371600
3
No
TotalMontsSOverdue
Numerical
1.687700
36
No
(b) Diabetes (Dua & Graff, 2017)
Feature
Type
Min
Mean
Max
Immutable
Pregnancies. 3t.33
Binary
0.000
0.454427
1.00
Yes
Glucose
Numerical
44.000
121.681605
199.00
No
BloodPressure
Numerical
24.000
72.254807
122.00
No
SkinThickness
Numerical
0.000
20.536458
99.00
No
Insulin
Numerical
0.000
79.799479
846.00
No
BMI
Numerical 18.200
32.450805
67.10
No
DiabetesPcdigreeunntioo
Numerical 0.078
0.471876
2.42
No
Age.ge 2t.2
Binary 0.000
0.484375
1.00
Yes
(c) COMPAS (Angwin et al., 2016)
Feature
Type
Min
Mean
Max
Immutable
juv fel count
Numerical
0
0.059186
20
No
juv hww_misd_com countt juv nuv_other.cm count
Numerical
0
0.09
13 No
Numerical
0
0.110751
No
priors_count
Numerical
O
3.247446
38 No
charge degree:F
Binary
0
0.643100
No
M
Binary
0
0.356900
No
at33lt.31
Binary
0
0.512567
Yes
gender
Binary
0
0.809794
Yes
race
Binary
0
0.514513
Yes
14

---

Algorithmic Recourse for Term-Term Improvement
Credit
Diabetes
COMPAS
1.6
ProtAR
1.30
TAP
1.25
LanUCBB DwOUCD
Average Cost
Average Cusl
1.2
1.0
Averuge
1.0
0.8
0.6
0.20
Average Insprovement
Average Improvement
Average Improvementt
(a) Average Improvement (higher is better) and Average Cost (lower is better)
Credit
Diabetes
COMPAS
11.8
0.8
0.8
Average MEn
FostARR
Average MER
0.7
Average MER
0.7
0.7
0.6
LinUCD BROUCD
0.5
0.5
0.4
0.3
200
100
600
900
1000
0
200
400
600
800
1000
200
400
6000
800
1003
Number Rounds
Number of Rounds
Number of Rounds
(b) Average Mean Expected Reward in Each Round (higher is better)
Figure Experimental results baseline comparison RF under noiseless cost evaluation situation.
Crodit
Diabetes
COMPAS
1.4
1.2
Average Cost
Awerage Cost
Average
1.1
0.8
1.4
TAP
ProteAR
0.6
DwOUCB
0.75
Awirage Imprrnement
Average Improvemnnt
Averago Improvementt
(a) Average Improvement (higher is better) and Average Cost (lower is hetter)
Credit
Diabetes
COMPAS
0.85
0.8
Avorage MEN
Average MER
Averaee MER
0.75
0.6
0.5
0.70
0.5
0.65
LadUCB
TAP
0.4
BwOWON
0.90
200
400
CAID
500
1000
200
400
500
800
1000
2001
4000
6000
8001
3000
Number
Rounds
Number Rounds
Number of Rounds
(b) Average Mean Expected Reward in Each Round (higher is better)
Figure Experimental results of baseline comparison for RF under the noisy cost evaluation situation with the noise level ş 0.25.
15

---

Algorithmic Recourse for Lenn-Term Improvement
Credit
Diabetes
COMPAS
2,00
ProtoAi
1.4
1.4
1.75
LinUC DeOUCD
TAP
Average Cos
1.2
1.2
Averug
1.25
1.0
0.5
1.00
0.6
Average Improvement
Average Inprovvemntt
Average Imprrvveent
(a) Average Improvement (higher is better) and Average Cost (lower is better)
Credit
Diabetes
COMPAS
0.31
0.8
Average MER
0.8
FostAR
Averngg MER
0.7
Average MER
0.7
LinUCD BrOUCD
0.0
0.4
014
200
100
600
800
1000
0
200
400
600
800
1000
200
400
6000
800
1003
Number Rounds
Nomber of Rounds
Number of Rounds
(b) Average Mean Expected Reward in Each Round (higher is better)
Figure Experimental results of baseline comparison for NN under noiseless cost evaluation situation.
Credit
Diabetes
COMPAS
1.9
Averago Cost
Average Cost
1.3
Average Cost
1.2
1.8
1.2
1.7
ProteAR
1.5
TAP
LánUCC
DwOUCB
0.9
0.4
0.75
Average Improvement
Average Improvemntt
Averagy Improvement
(a) Average Improvement (higher is better) and Average Cost (lower is hetter)
Credit
Diabetes
COMPAS
0.90
0.8
Averuge MEi
0.75
Average MER
0.7
Average MER
0.6
0.6
0.70
0.5
01:33
BAP
LaiUCR
0.90
BwOWOC
03
03:
200
400
500
1000
200
400
600
800
1000
2001
4000
6000
800
3000
Number
Rounds
Number Rounds
Number of Rounds
(b) Average Mean Expected Reward in Each Round (higher is better)
Figure Experimental results of baseline comparison for NN under the noisy cost evaluation situation with the noise level & 0.25.
16

---

Algorithmic Recourse for Long-Tern Improvement
Averuge Improweneei
Credit
Average Improvenneti
Diabetes
Averoge Improweeesntt
COMPAS
0.5
BwOUCB PiotoAR
0:76
0.75
TAP Lint/Cn
0.50
0.05
0.30
0.15
0.00
Nniso Lovel {
Noise Level
Noise Tevel
(a) Average Improvement (higher is better)
Credit
Diabetes
COMPAS
Average Cost
Average Cuel.
DwOUCB
PiotoAR
1.00
Avurage
1.0
TAP
0.75
LintCCn
0.3
0.30
0.15
3.00
Noise Level {
Noise Level
Noise Leved
(b) Average Cost (lower is better)
Credit
Diabetes
COMPAS
Averuge MER
BwOUGB
Avernge MER
01.8
Average MER
0.8
ProteAR
0..6-
0.0
0.6
LintiCBB
0.1
0.10
Noise Level
Noise Level
Noise Level
(c) Average Mean Expected Reward of Final Round (higher is hetter)
Figure 9. Sensitivity analyses of the noise level for RF
Average Improweneet
Credit
Average Iuptovenent
Diabetes
Average Improvemnnt
COMPAS
0.8
DrOUCB
ProtoAk
0.75
0.75
TAP
0.50
0.5-
LintiCiR
0:50
0.30
Noise Level
Nolse Level
Noise Level
(a) Average Improvement (higher is better)
Credit
Diabetes
COMPAS
1.25
Average Cool
Average Coot
Coe
1.5
BwOUCCB
ProteAR
ListiC
IAP
0.75
0.5
0.5
0.10
Noise Level
Noise Level
Noise Level
(b) Average Cost (lower is better)
Credit
Diabetes
COMPAS
Avarage MER
Average MER
0.8
Axorage MER
BwOUCB
0.75
ProteAR
TAP
0.50
LisUCB
0.4
Noise Level g
Naisu Level
Noise Level
(c) Average Mean Expected Reward of Final Round (higher is better)
Figure 10. Sensitivity analyses of the noise level for NN.
17

---

Algorithmic Recourse for Long-Term Term Improvement
Credit
Diabetes
COMPAS
ProbAR
018
TAP
Avrrgg: Cost
LaaUCB
0.7
BwOUCB
0.7
Awrag
0.6
0.5
0.4
0.7
0.9
0.4
1.0
0.4
0.6
0.8
Average improvement
Average Improvement
Average Improvemeeut
(a) Average Improvement (higher is better) and Average Cost (lower is better)
Diahetes
COMPAS
Averuge MER
0.8
Average MER
Average MER
ProteAR
TAP
0.7
LiaUCC
0.66
BwODCB
0.4
0.3
200
400
600
800
1000
0
200
400
800
800
1000
200
600
000
800
1003
Number
Number Rounds
(b) Average Mean Expected Reward in Each Round (higher is better)
Pigure 11, Experimental results the cost-mixture scenario for RF under the noiseless cost evaluation situation.
COMPAS
ProcoAR
TAP
Averige Coel
LiaDCB RROUCR
Aneage Cual
0.75
0.50
0.50
Average
0.75
0.78
0.70
0.70
0.74
0.65
0.65
0.70
0.75
0.80
0.85
0.90
0.95
0.4
0.5
0.6
0.7
0.5
0.9
1.0
0.3
0.1
0.5
0.6
0.7
0.8
0.9
Average Improvement
Average Imgrrovement
Average Improvement
(a) Average Improvement (higher is better) and Average Cost (lower is better)
Credit
Diahetes
COMPAS
0.90
0.8
0.7
Avergg MER
vezage MER
Average MER
0.7
0.6
0.5
0.75
ProiAR
0.4
0.70
LiaUCC BwOUCH
0.85
200
400
600
500
1000
200
400
600
1003
200
100
800
1000
Number Hounds
Number Hounds
Number of Hounds
(b) Average Mean Expected Reward Each Round (higher better)
Figure 12. Experimental results of the cost-mixture scenario for RF under the noisy cost evaluation situation with the noise level { = 0.25.
18

---

Algorithmic Recourse for Long-Term Term Improvement
Credic
Diabetes
COMPAS
ProtAR
0.8
"AP
Avurage: Cost
0.7
LarUCB
BwOUCB
Aruage Cost
Awrrge Coot
0.7
0.6
0.0
0.6-
0.6
0.4
0.4
0.3
0.6
0.9
0.2
0.4
1.0
0.4
0.8
Average Improvement
Average Improvement
Average Improvement
(a) Average Improvement (higher is better) and Average Cost (lower is better)
Dishetes
COMPAS
0.9
0.8
Averuge MER
0.8
ProtoAR TAP
Average MER
Average MER
0.7
0.7
LiaUCU BwOUCH
0.6
0.6
0.5
0.6
0.5
200
400
600
800
1000
0
200
400
800
800
1000
200
600
000
800
1000
Number
Nomber
Number Rounds
(b) Average Mean Expected Reward in Each Round (higher is better)
Figure 13. Experimental results of the cost-m misttmixtur scenario for NN under the noiseless cost evaluation situation.
Crodit
COMPAS
0.90
ProcoAft
TAP
11.75
0.8
Average Cool
LiaUCB RROUCR
Avergge Coet
Avenge Cret
0.82
0.70
0.6
0.90
0.85
0.4
0.70
0.75
0.50
0.55
0.00
0.95
0.5
0.6
0.7
0.5
0.9
1.0
0.4
0.6
0.8
Average Improweneent
Average Imgrovvemnnt
Averago Impeovement
(a) Average Improvement (higher is better) and Average Cost (lower is better)
Credit
Diahetes
COMPAS
0.85
0.7
Averug MER
0.50
Avrage MER
0.7
Average MER
0.6
0.75
0.6
PaRtAR
0.
0.5
LiaUCB
0.4
RaOUCR
0.3
200
400
600
500
1000
200
400
600
1003
200
100
800
1000
Number Hounds
Number Hounds
Number of Hounds
(b) Average Mean Expected Reward in Each Round (higher better)
Figure 14. Experimental results of the cost-mixture scenario for NN under the noisy cost evaluation situation with the noise level { = 0.25.
19

---

Algorithmic Recourse for Term-Term Improvement
Credit
Diabetes
COMPAS
1.50
ProiAR
1.2
TAP
Averuge Coot
LantCCB DwOUCD
Averug Chs
Average Cuui
1.0
1.00
0.70
0.3
1.0
0.8
0.5
0.3
Average Impprovement
Average Improvement
Average Improvement
(a) Average Improvement (higher is better) and Average Cost (lower is better)
Credit
Diabetes
COMPAS
0.8
0.8
Avtrige MEI
Average MER
0.7
Average MER
ProtAR
0.70
TAP
0.6
LmUCB #wQUCU
0.65
0.5
0.00
0.55
0.3
200
400
600
800
1000
200
400
600
800
1000
200
400
600
800
1000
Number Rounds
Number Rounds
Number of Rounds
(b) Average Mean Expected Reward in Each Round (higher is better)
Figure 15. Experimental results the adaptive delay scenario for
Credit
Diabetes
COMPAS
ProteAR
1.76
2.0
TAP
1.2
Average Cost
LanUCB BwOUCC
Averge Cont
1.25
Average
1.0
0.75
0.6
Average Improvement
Average Improvement
Averagy Improvement
(a) Average Improvement (higher is better) and Average Cost (lower is hetter)
Credit
Dinbetes
COMPAS
0.8
Avorage MEn
Avergee ME3R
Average MER
0.7
PootoAR
LinUCB BeOUCD
0.0
0.6
0.5
0.5
0.6
0.4
200
400
600
500
1000
0
200
400
600
800
1000
200
400
600
800
1000
Number
Rounds
Number of Roonds
Number of Roodds
(b) Average Mean Expected Reward in Each Round (higher is better)
Figure Experimental results of the adaptive delay scenario for NN.
20

---

Algorithmic Recourse for Long-Teree Improvement
Averuge Improweneei
Credit
Avernge Improwvment
Diabetes
Averago Improvmmnnt
COMPAS
1.0
1.0
ProtoAR
TAP
MitEC BeOUCB
0.5
0.6
Total Number of Recourse Irstanons K
Total Number of Recourse Tristanees K
Total Number of Recoarso Instances K
(a) Average Improvement (higher is better)
Credit
Diahetes
COMPAS
Average Cost.
ProtoAR
Average Cost.
Average Coot
TAP
1.0
LinUCD
BwOUCB
0.5
Total Number of Recousee Irstamons K
Total Number of Recourse Instanees K
Total Number of Revourse Instances R
(b) Average Cost (lower is better)
Credit
Diabetes
COMPAS
Averuge MER
Average MER
Average MER
ProtoAR
0.75
0.75
IAP
0.8
LiaUC
0.50
ReOUCR
0.25
Total Numaber of Revourse Instamers K
Total Number of Recourse Irastances K
Total Number of Receurse Instances K
(c) Average Mean Expected Reward of Final Round (higher is hetter)
Figure 17. Sensitivity analyses of the total number of recourse instances K for RE.
Average Improvenent
Credit
Average Improvemen
Diabetes
Average Inprovvenent
COMPAS
1.0
2.01
ProtoAR
TAP
LiuUCH BwOUCR
0.5
Total Number of Recouuse Instances K
Total Number of Recousse Instances K
Total Number of Recourse Instances K
(a) Average Improvement (higher is better)
Credit
Diabetes
COMPAS
Average Cost
Average Cost
Average Cost
TAP
1.0
2.01
Litton
BeOUCD
0.5
Total Number of Recousse Iostances K
Total Number of Recourse Instances K
Total Number of Recourse Instances K
(b) Average Cost (lower is better)
Credit
Diabetes
COMPAS
Avurage MEI
Average MER
Axorage MER
ProteAR
LiaUCI
0.50
0.50
BwOUCB
0.25
0.25
Total Nuraber of Revourse Instances K
Total Nunber of Recourse Instaaness K
Total Namaber of Reveurse Instances N
(c) Average Mean Expected Reward of Final Round (higher is better)
Figure 18. Sensitivity analyses of the total number of recourse instances K for NN.
21

---

Algorithmic Recourse for Long- Term Improvement
Average Improweneei
Credit
Average Improveneet
Diabetes
Averoge Imprroveuusnt
COMPAS
ProtoAR
0.76
0.75
TAP
0.5
LintiC
DwOUCB
0.50
0.50
Window Parameter
Window Parameter
Window Parameter
(a) Average Improvement (higher better)
Credit
Diabetes
COMPAS
Average Cost
PastoAR
Average Cost
Averoge Cost
TAP
1.0
LinUCD
BeDUCB
0.5
Window Purametter
Window Parameser
Window Parmeeter
(b) Average Cost (lower is better)
Credit
Diabetes
COMPAS
Average MER
Average MER
Average MER
ProtoAR
0.75
0..
TAP
0.6
0.6
LisUCCB
0.50
PwOUCR
Window Panameter
Window Purameter
Window Parameter
(c) Average Mean Expected Reward of Final Round (higher is hetter)
Figure 19, Sensitivity analyses of the window parameter m for RF
Average Improweneut
Credit
Average Iuptovenent
Diabetes
Average Improveeentt
COMPAS
1.00
ProtoAR
0.75
0.8
TAP
LiaUCB
0.50
0.50
BwOUCR
0.6
0.25
Window Patameter
Window Parameter
Window Parameter
(a) Average Improvement (higher better)
Czedit
Diabetes
COMPAS
Avorage Coot
ProtoAK
Average Coot
Average Coed
TAP
1.00
1.0
LMCCB
DwOUCB
0.5
Window Porameter
Window Parameter
Window Parametet
(b) Average Cost (lower is better)
Credit
Diabetes
COMPAS
Average MER
Average MER
ProteAR TAP
0.75
Avorage
LISUCH
0.50
BwOUCB
0.25
Window Panametur
Window Paramneter
Windoww Parumcter
(c) Average Mean Expected Reward of Final Round (higher is better)
Figure 20. Sensitivity analyses of the window parameter for NN.
22

---

Algorithmic Recourse for Long- Term Improvement
Credit
Diabetes
COMPAS
0.95
0.40
Avorage: Coos
Antage Clost
Anrage Cost
1.0
0.85
0.35
10.0
0.80
0.9
30.0
0.25
0.8
30.0
0.70
0.20
0.7
0.90
0.85
0.00
0.05
1.00
0.75
0.50
0.55
0.00
0.05
1.00
0.7
0.9
Average Inprovemennt
Average Improvement
Average Improvement
(a) Average Improvement (higher is better) and Average Cost (lower is better)
Dishetes
COMPAS
Averuge MER
Average MERR
Axerage MER
30.0
15.0
20.0
0.4
25.0
012
200
400
600
500
1000
0
200
400
900
800
1000
200
600
000
800
1003
Number
Number Rounds
(b) Average Mean Expected Reward in Each Round (higher is better)
Figure 21. Sensitivity analyses the regularization parameter Algorithm for RF under the noiscless cost evaluation situation.
Crodli
COMPAS
1.0
1.85
1.15
0.9
Average Cost
Average Coet
Avengge Coet
1.80
1.10
11.8
1.75
10.0
20.0
0.7
1.00
10.6
0.50
0.55
0.90
0.95
0.70
0.75
0.80
0.85
0.90
0.95
0.0
0.7
0.8
0.9
Average Improwement
Average Inggrovement
Averago Impeovemnnt
(a) Average Improvement (higher is better) and Average Cost (lower is better)
Crodit
Diahetes
COMPAS
0.8
0.8
Averrgg MER
0.7
Average MI3
Average MER
0.7
0.7
0.6
30.0
35.0
0.6
0.0
25.0
0.55
0.5
0.4
0.4
200
600
1000
200
400
000
800
1000
800
1003
Number Hounds
Number of Hoxnds
Number of Rounds
(b) Average Mean Expected Reward Each Round (higher better)
Figure 22. Sensitivity analyses of the regularization parameter À of Algorithm for RF under the noisy cost evaluation situation with the noise level & = 0.25.
23

---

Algorithmic Recourse for Long-Term Term Improvement
Credit
Diabetes
COMPAS
1.3
1,00
0.40
1.2
10.0
0.35
Avarage: Coat
1.1
210
0.90
Avrage Cost
0.30
250
Anmagg
0.85
0.30
0.30
0.8
0.25
0.75
0.7
0.85
0.95
0.25
0.80
0.00
0.05
1.00
0.70
0.75
0.50
0.00
0.85
1.00
Average Improvement
Average Improvement
Average Improvementt
(a) Average Improvement (higher is better) and Average Cost (lower is better)
Dishetes
COMPAS
0..9
0.8
Averuge MER
0.8
Average MER
Axerage MER
0.8
30.0
0.6
0.5
20.0
25.0
104
0.5
0.4
200
400
600
800
1000
0
200
400
800
800
1000
200
600
000
800
1003
Number
Number Rounds
(b) Average Mean Expected Reward in Each Round (higher is better)
Figure 23, Sensitivity analyses the regularization parameter Algorithm for under the noiseless cost evaluation situation.
Crvlit
COMPAS
10.0
1.20
Average Cost
15:0
Average Cuel
Average Cosl
25.0
1.7
1.5
0.50
0.85
0.00
0.05
0.75
0.80
0:85
0.00
0.95
0.70
0.75
0.80
0.55
0.00
0.05
Average Improvementt
Averago Improvementt
Average Improvement
(a) Average Improvement (higher is better) and Average Cost (lower is better)
Crodit
Diahetes
COMPAS
11.8
Averuge MER
MER
Average MER
0.7
10.1
15.01
0.5
25.11
0.5
0.2
200
600
1000
200
400
000
800
1000
200
800
1003
Number Hounds
Number of Hoxnds
Numberr of Rounds
(b) Average Expected Reward Each Round (higher better)
Figure 24. Sensitivity analyses of the regularization parameter of Algorithm for NN under the noisy cost evaluation situation with the noise level & = 0.25.
24

---

Algorithmic Recourse for Tern-Term Improvement
Credit
Diabetes
COMPAS
24
1.4
1.2
Averugo Coot
2.0
Clos
Average Coss
1.0
1.8
4.1
0.8
25
1.0
0.0
144
1.2
100
0.9
Average Inpprovement
Average Improvement
Average Inpprovement
(a) Average Improvement (higher is better) and Average Cost (lower is better)
Credit
Diabetes
COMPAS
0.9
0.50
0.8
Avtrige MEHI
0.75
Avenage MER
0.7
Average MER
0.7
0.70
0.6
0.3
0.90
100
0.4
200
400
600
800
1000
200
400
600
800
1000
200
400
600
800
1000
Number Rounds
Number Rounds
Number of Rounds
(b) Average Mean Expected Reward in Each Round (higher is better)
Figure 25, Sensitivity analyses of number trees B of Algorithm RF.
Credit
Diabetes
COMPAS
25
2.25
50
1.25
Averag Cost
2,00
100
Average Cost
1.20
Average Cost
1.22
1.15
1.00
1.10
1,30
1.05
1.00
Avenage Improsement
Awerage Irpprvvement
Averago Improvement
(a) Average Improvement (higher is better) and Average Cost (lower is hetter)
Credit
Diabetes
COMPAS
0.8
0.8
Avorage MEl
Average MER
Average MER
0.6
0.75
0.70
0.4
50
100
0.2
0.5
200
400
500
1000
200
400
500
800
1000
2001
4000
6000
800
3000
Number Rounds
Number Rounds
Number of Rounds
(b) Average Mean Expected Reward in Each Round (higher is better)
Figure 26. Sensitivity analyses the total number of trees of Algorithm 2 for NN.
25

---

Algorithmic Recourse for Lenn-Term Improvement
Cyedit
Diabetes
COMPAS
1.75
ProtAs
1.2
TAP
1.1
LinUCn DeOUCD
Average Cost
1.0
1.0
Averuge
0.9
Axirage
0.8
6.4
0.30
Average Improvements
Average Improvement
Average Toprovement
(a) Average Improvement (higher is better) and Average Cost (lower is better)
Credit
Diabetes
COMPAS
0.8
Antrage 312
Average MER
Average MER
0.7
0.7
0.6
0.0
0.3
TAP LinUCB BrOUCD
0.5
0.4
0.4
200
100
600
500
1000
200
400
600
800
1000
200
400
6000
800
1003
Number
Rounds
Number of Rounds
Number of Rounds
(b) Average Mean Expected Reward in Each Round (higher is better)
Figure Experimental results the model update scenario for where update frequency once every 25 rounds.
Credit
Diabetes
COMPAS
2.00
ProteAil
1.1
TAP
1.2
Average Cost
1.76
LinUCB BeOUCB
Average Cost
1.0
Avarage Cosi
0.9
0.8
0.7
04
0.6
0.50
Average Improvvments
Awerage Traprvvement
Asertagy Impreveeent
(a) Average Improvement (higher is better) and Average Cost (lower is hetter)
Credit
Dinbetes
COMPAS
0.9
0.8
0.5
Average MEn
Average MEN
Average MER
0.7
0.6
0.4
TAP
LinUCR
0.5
BwOUCB
0.2
200
400
600
1000
200
4001
600
800
1000
200
400
600
800
1000
Number
Rounds
Number of Roonds
Number of Roonds
(b) Average Mean Expected Reward in Each Round (higher is better)
Figure 28. Experimental results the model update seenario for NN where the update frequeney is once every rounds.
26

---

Algorithmic Recourse for Long-Tern Improvement
Averugo Improwsueei
Credit
Averoge Improvemenn
Diahetes
Average Improwenesnt
COMPAS
ProtoAR
0.8
IAP
LinliCI
DwOtCC
0.25
100
Model Updaate Proqueency
Model Update Prequency
Model Update Proquency
(a) Average Improvement (higher is better)
Credit
Diabetes
COMPAS
Averuge Cost
Avernge Coot
Average Cost
1.3
TAP
ProtoAR
1.0
1.0
1.0
BrOUCB
0.5
Model Update Proquency
Model Update Prequeney
Model Update Frequency
(b) Average Cost (lower is better)
Credit
Diabetes
COMPAS
Averuge MER
Average MER
Average MER
0.8
ProteARt
0.75
0.75
TAP
LudUCB
0.5
BwODOn
0.25
0.25
Model Update Proqueney
Model Update Prequency
Model Update Frequency
(c) Average Mean Expected Reward of Final Round (higher is hetter)
Pigure 29, Sensitivity analyses of the model update frequency for RF
Average Improweneut
Credit
Average Improvement
Diabetes
Average Improvement
COMPAS
1.0
0.78
I
TAP
ProtoAR
0.75
Liaten BwOUCC
0.5
0.30
Model Update Frequency
Model Update Frequency
Model Update Frequency
(a) Average Improvement (higher better)
Credit
Diahetes
COMPAS
Avonage Coot
ProloAk
Average Coot
Average Coel
I
TAP
1.00
1.0
LinUCC
BROUCH
0.75
Model Update Frequency
Model Update Frequency
Model Update Frequency
(b) Average Cost (lower is better)
Credit
Diabetes
COMPAS
Average MER
Average MER
Axorage MER
0.8
ProteAR
0.75
TAP
0.6
LiaUCB
0.50
BwOUCB
0.25
Model Update Frequency
Model Update Prequrncy
Model Update Frequency
(c) Average Mean Expected Reward of Final Round (higher is better)
Figure 30. Sensitivity analyses of the model update frequency for NN.
27

---

Algorithmic Recourse for Term-Term Improvement
Credit
Diabetes
COMPAS
ProtAR
2.5
TAP
1.2
Averuge Cood.
LanUCBB
Averago Cost
Averag Coot
1.5
DwOUCD OGPUCH
1.0
1.5
1.0
0.5
0.6
0.3
Average Improvvment
Average Toprovement
Average Itaprovementt
(a) Average Improvement (higher is better) and Average Cost (lower is better)
Credit
Diabetes
COMPAS
0.8
0.8
0.8
Average MEn
Avernge MER
Azerage MER
0.7
0.6
ProtoAR
0.5
0.6
LiuUCR BwOUCB
0.4
0.5
CGPUCB
0.3
0.2
200
100
600
800
1000
0
200
400
600
800
1000
200
400
600
800
1003
Number
Rounds
Number of Rounds
Number of Rounds
(b) Average Mean Expected Reward in Each Round (higher is better)
Figure 31. Experimental results comparison to algorithm based on Gaussian process (CGPUCB) for RF.
Credit
Diabetes
COMPAS
1.70
ProteAit
1.75
TAP
1,50
*
Average Cost
1.50
LinUCB
BeOUCB
Average Cosl
Average Cost
CGPUCB
1.0
1.00
1.00
0.75
0.50
0.5
0.30
0.8
Avenage Improvement
Awerage Traprvvement
Averago Improvement
(a) Average Improvement (higher is better) and Average Cost (lower is hetter)
Credit
Dinbetes
COMPAS
0.55
0.8
Average MEn
0.8
Avergee MElI.
Average MER
0.7
0.7
ProtoAR
Lin
0.5
BeQUCB OGPUCR
0.5
0.2
0.3
200
400
600
1000
0
200
400
600
800
1000
2001
400
600
800
1000
Number
Rounds
Number of Roonds
Number of Roudds
(b) Average Mean Expected Reward in Each Round (higher is better)
Figure 32, Experimental results of comparison the algorithm based the Gaussian process (CGPUCB) for NN.
28

---

Algorithmic Recourse for Long-Term Improvement
Table Experimental results on average running time [s] per round of each method. We can see that the rumning time LinUCB was not significantly different from those of ProtoAR and TAP. In addition, BwOUCB was significantly faster than CGPUCB, while their performance was close to each other.
(a) RF
Dataset
ProtoAR
TAP
LinUCB
BwOUCB
CGPUCB
Credit
0.000496 + 0.0002
0.00045 + 0.0001
0.00099 + 0.0023
0.01782 + 0.0125
4.524303 + 3.3757
Diabetes
0.000406 = 0.0002
0.000389 + 0.0
0.000952 + 0.0046
0.017913 = 0.0124
4.984736 3.955
COMPAS
0.000447 1: 0.0006
0.000379 1 0.0001
0.000871 1 0.0028
0.017919 1 0.0126
4.92054 1. 3.8675
(b) NN
Dataset
ProtoAR
ТАP
LinUCB
BwOUCB
CGPUCB
Credit
0.000506
0.0002
0.00053 = 0.0002
0.000936 0.0024
0.017705
0.0128
4.813339 3.7733
Diabctes
0.000439 0.0003
0.000443 + 0.0002
0.000835 0.0026
0.017724
0.0126
4.765345 + 3.5786
COMPAS
0.000427 0.0003
0.00038 = 0.0003
0.000938 0.0027
0.017427
0.0124
5.024779 + 3.896
29


Reviews:
[{"review_id": "3ygOdM9JAu", "reviewer": "Reviewer_NJwZ", "summary": "The paper studies Algorithmic Recourse (AR), i.e., providing a recourse action $a$ to individuals $x$ to improve so that their classification changes from $h(x)=0$ to $h(x+a)=1$ or “h-valid.”  The authors frame their problem in the “improvement” setting (König et al.), where the goal is also to improve classification on some unknown classification oracle $h^*$ that correctly captures long-term improvement; thus, they want $h^*(x+a) = 1$ too.  \n\nThey study this problem in the online setting, where in round $t$, the agent i) gets an individual $x_t$, ii) selects an action from the feasible actions $A_t$ (based on $x_t$ manipulation cost and whether they are h-valid), and iii) gets a reward related to being $h^*$-valid. This reward is delayed and revealed after some rounds (the delay distribution is unknown).  \n\nThe authors propose two algorithms: contextual linear bandits (CLB) and contextual Bayesian optimization (CBO), which are used to solve the problem when the costs are known/unknown, respectively, and provide a regret bound for the CLB approach. They then run experiments on three datasets and compare these two methods against two baselines, showing improvement in reward and lower average cost.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for valuable and thoughtful feedback. We will reflect all of them in our final version. In the following, we will respond to the key comments and questions raised by the reviewer. \n\n---\n\n> The Bernoulli reward model in equation (2) needs more description. Can you mention what exactly in Fokkema et al. you’re referencing for $E(a \\mid x)$? This seems to be a softmax sample of actions inversely proportional to cost. Also, can the reward be relaxed to something not distributional, e.g., simply the output of $h^\\ast(x_t + a_t)$, which is revealed in a later round?\n\nThank you for your important comment on our reward model. \nWe define $E(a \\mid x)$ as the probability that an instance $x$ executes an action $a$ and assume that it decreases depending on the cost $c(a \\mid x)$, as you pointed out. In particular, we define $E(a \\mid x) = \\exp (-\\nu \\cdot c(a \\mid x))$ so that it decreases exponentially in $c(a \\mid x)$. This definition is also employed by Fokkema et al. to model the probability that $x$ executes $a$. \nIn addition, our reward model $R_t$ can be relaxed to a model that simply outputs $h^\\ast(x_t + a_t)$. It corresponds to a special case of our Bernoulli reward model where we set $E(a_t \\mid x_t) = 1$ and $I(a_t \\mid x_t) = h^\\ast(x_t + a_t)$ for any $x_t$ and $a_t$. \n\n\n> On a similar note, can you expand on the motivations behind the $P(Y=1 \\mid X=x_n)$ in the experiment Protocol paragraph, bullet point 3? How is this evaluated on the test instances from bullet point 4? Do you assume the test instances can shift only to one of the recourse instances?\n\nThank you for your important comment on our experimental protocol. As you said, for each test instance $x_t$, we restricted its candidate actions $a_t$ to those that can shift to one of the recourse instances $\\tilde{\\mathcal{X}}$. If we allow arbitrary actions $a_t$ for $x_t$, we can not evaluate the improvement of $a_t$ for $x_t$ because we do not know the oracle outcome $h^\\ast(x_t + a_t)$ in real datasets. Our motivation to restrict candidates to the actions leading to recourse instances is to ensure the existence of a recourse instance $x_n$ such that $x_n = x_t + a_t$. This allows us to evaluate $h^\\ast(x_t + a_t)$ using the label $y_n$ associated with $x_n$ as a proxy for the oracle outcome. In addition, to simulate a noisy oracle, we set the probability of improvement $P(Y=1 \\mid X=x_t+a_t)$ using the value of $y_n$ with a noise $\\varepsilon \\sim \\mathcal{N}(0, 1)$ and scaling the result to the range $[0, 1]$. In our final version, we will clarify this point and provide more description. \n\n\n> What is the impact of the stochastic delay distribution on your results, i.e., can you point out where it’s appearing in Proposition 4.2? Also, what can you say about fixed deterministic delays modeling some practical cases, e.g., when credit defaults are evaluated every month?\n\nThank you for your important question. \nThe delay distribution $\\mathcal{D}$ impacts the term $\\tau_m = P(D_1 \\leq m)$ in our bound. This term increases as the delay $D_1 \\sim \\mathcal{D}$ for the first instance $x_1$ tends to be smaller than the window parameter $m$ of our algorithm, which makes our bound in Proposition 4.2 better. In essence, the more quickly feedback is received, the better our algorithm performs. \nIn addition, if the delay is a fixed value and we know it in advance, we can set our window parameter $m$ to the value. This adaptation would likely lead to improved performance compared to the stochastic delay setting. \n\n---\n\nWe hope that we have adequately addressed all your questions and concerns. Please let us know if we can provide any further details and/or clarifications. Thank you again for your valuable feedback.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes the 3 datasets seem to be standard for algorithmic recourse problems. The experimental description and details are thorough.", "theoretical_claims": "Yes, the claims for CLB are sound and have a proof of Proposition 4.2 in the Appendix.", "experimental_designs_or_analyses": "Yes, the experiments are sound and the supplementary code has sufficient details.", "relation_to_broader_scientific_literature": "The paper is a good contribution to AR, and the online improvement setting is novel.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strengths\n\n1. The paper is well written, and the experimental evaluation is thorough.  \n\n2. The most insightful sections are the reduction to CLB in Section 4 and the BwO-based optimization in Section 5.1 to speed up CBO.  \n\nWeaknesses\n\n1. The Bernoulli reward model in equation (2) needs more description. Can you mention what exactly in Fokkema et al. you’re referencing for $E(a|x)$? This seems to be a softmax sample of actions inversely proportional to cost. Also, can the reward be relaxed to something not distributional, e.g., simply the output of $h^*(x_t + a_t)$, which is revealed in a later round?  \n\n2. On a similar note, can you expand on the motivations behind the $P(Y=1| X=x_n)$ in the experiment Protocol paragraph, bullet point 3? How is this evaluated on the test instances from bullet point 4? Do you assume the test instances can shift only to one of the recourse instances?", "other_comments_or_suggestions": "N/A", "questions_for_authors": "What is the impact of the stochastic delay distribution on your results, i.e., can you point out where it’s appearing in Proposition 4.2? Also, what can you say about fixed deterministic delays modeling some practical cases, e.g., when credit defaults are evaluated every month?", "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": "", "extra_scores": {}}, {"review_id": "1gR4OQ0jNO", "reviewer": "Reviewer_f6gN", "summary": "This paper is about algorithmic recourse: it aims to help individuals take actions to change unfavorable predictions made by machine learning models (like getting a loan rejection changed to approval). The issue that this paper tries to resolve is that many current methods only focus on changing the prediction itself, without ensuring that the action actually improves the individual's real-world outcome (e.g., ensuring that the person can actually repay the loan).\nThe authors propose a new framework to suggest actions that not only change the prediction but also improve the real-world outcome over the long term. They use tools from bandit problems with delayed feedback (it may take some time to observe whether the action worked in the real world or not) and suggest actions accordingly. The paper compares two approaches—contextual linear bandit (section 4) and contextual Bayesian optimization (section 5)—for selecting these actions based on past outcomes. Some further comparison between two approaches are presented in section 5.3. Experiments show that their methods lead to better long-term improvement than two baselines (ProtoAR and TAP).", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for valuable and thoughtful feedback. We will reflect all of them in our final version. In the following, we will respond to the key comments and questions raised by the reviewer.\n\n---\n\n> **Methods And Evaluation Criteria** \n> No. The critical weak point of this paper is that the bandit setting with delayed feedback is not a good tool to address the recourse problem. [...] and we need to avoid hacking/gaming [...].\n\nThank you for your important comment. We acknowledge the inherent challenges posed by the long-term nature of recourse implementation. However, we maintain that our bandit-based approach offers valuable contributions and can be a foundational step for the following reasons: \n- We are the first to demonstrate the feasibility of achieving long-term improvement by exploiting feedback in the recourse problem, even if only delayed feedback is available. This addresses real-world recourse challenges even when feedback is not given immediately.\n- While we recognize that effectively handling long delays remains a challenge, long delays do not preclude the potential of our method. Even if it takes a long time to observe the first feedback, our framework can work well once we start to observe feedback.  \n- Since our method considers the real-world outcome $h^\\ast(x + a)$, it avoids suggesting hacking/gaming actions that only meet the decision criteria of $h$. \n\n> **Questions For Authors**  1. Could the authors provide the readers with several reasonable scenarios [...] validating that the support of $\\mathcal{D}$ is appropriate with the horizon $T$ of the online learning framework.\n\nWe summarize three scenarios where an online learning approach could be suitable for consequential decision-making:\n\n| Task | User / Decision Maker | Outcome | Action | Delay |\n| - | - | - | - | - |\n| Healthcare | Patient / Doctor | Physiological indicator (blood pressure or blood sugar level) | Dietary restrictions, exercise routine | 1--4 weeks |\n| Job Hiring | Job Seeker / Staffing Agency | Whether a job seeker is employed by a company to which he or she has applied | Regime revision, interview preparation | 4--6 weeks |\n| Human Resource | Employee / Company | Employee attrition within months | Reducing overtime, getting counselling |  3--6 months |\n\nIn each case, round $t$ corresponds to a decision for a user $x_t$, and $T$ is the total number of users who receive actions, not elapsed real time. Let us consider the Healthcare task, for example. If the doctor provides actions with five patients every weekday and we deploy our method for at least one year, the horizon $T$ exceeds $1000$. Meanwhile, the maximum delay $D_t \\sim \\mathcal{D}$ is at most about $100$ (corresponding to four weeks), which is small compared to the overall horizon $T$. In such scenarios, we believe the delay distribution $\\mathcal D$ remains appropriate throughout $T$, and our method can effectively provide improvement-oriented actions within a realistic time frame by collecting feedback from past users.\n\n> **Other Strengths And Weaknesses**\n> It is unclear to me why the authors would like to include Section 4. [...] For that, having Section 4 in the paper is a distraction.\n\nThank you for your important comment. While we understand the reviewer's concern regarding Section 4, we still believe this section is essential for the following two reasons:\n- While we admit Proposition 4.2 is a direct application of the existing result by Vernade et al. 2020, we believe this proposition is valuable in clarifying the required assumptions to reduce Problem 1 to a mathematical model that can be solved with a theoretical guarantee. \n- We agree that knowing $\\nu$ looks a strong assumption. However, even in the noisy cost situation of Section 6.3, which can be also interpreted as a misspecification of $\\nu$, our algorithm of Section 4 outperformed existing baselines except for cost in Figure 3. Moreover, in early rounds until $t = 200$, it outperformed the algorithm of Section 5 in terms of MER in Figure 3(b). This suggests that our algorithm of Section 4 is practically robust to some degree of misspecification.\n\n> **Questions For Authors**\n> 2. Is it possible to provide any guarantees for the algorithms proposed in Section 5?\n\nThank you for your important suggestion. Theoretical guarantees for Algorithm 2 are a valuable research direction. Replacing the BwO forest-based surrogate model with the Gaussian process, and leveraging the regret bound from Verma et al. (2022), might be possible. However, since their analysis relies on continuous outcomes, extending their results to our binary outcome setting is not trivial.\n\n---\n\nWe hope that we have adequately addressed all your questions and concerns. Please let us know if we can provide any further details and/or clarifications. Thank you again for your valuable feedback.", "claims_and_evidence": "What is good:\n- The paper states clearly the assumptions in each result.\n- The theoretical result in Proposition 4.2 comes with a proof. The proof is correct.\n- The claim that the proposed methods outperform the baselines are supported by the numerical results with several setting (noisy costs, etc.)", "methods_and_evaluation_criteria": "No. The critical weak point of this paper is that the bandit setting with delayed feedback is not a good tool to address the recourse problem.\n\nFor a recourse problem, the individual may take a long time to implement the actions: in loan applications (the Credit dataset), whether the person will repay the loan or not is an event that is realized in a few years' horizon. Similarly, in healthcare (the Diabetes dataset), the patient may take years to get on with a healthy lifestyles.\n\nThe paper does not discuss the temporal horizon of the problem. I can see there is a huge conflict between the real-world recourse problem (delayed feedbacks measured in years) with the online learning setting (the recourse is generated at a daily frequency, and the learning horizon could be a few months, the feedback is still short-term). Once again, I need to emphasize that we are focusing on consequential domains, and the actions has to be impactful (in Credit, the person may need to save more money/reduce spending in a serious manner to meet the criteria), and we need to avoid hacking/gaming (in Credit, the person can instantaneously borrow money to meet the criteria -- this is considered cheating).", "theoretical_claims": "The proof of Proposition 4.2 is correct, but it follows largely from Vernade et al. (2020).\n\nThere is no theoretical guarantee for Section 5, which is another weak point of this paper.", "experimental_designs_or_analyses": "The experiment settings are reasonable to me.", "relation_to_broader_scientific_literature": "Unclear. The paper is mainly about formulating the algorithmic recourse problem into the bandit with delayed feedback setting, and then use existing results from bandit to solve the problem. \n\nThere does not seem to be any direct contribution to the broader scientific literature.", "essential_references_not_discussed": "No. The paper has cited most relevant papers that I am aware of.", "other_strengths_and_weaknesses": "It is unclear to me why the authors would like to include Section 4. The assumptions of Section 4 is really strong (knowing $\\nu$). Moreover, the algorithm of Section 5 seems to be better than LinUCB anyways. I can think that the authors include Section 4 because it has some theoretical support, however, the theoretical results therein is nearly a \"copy-and-paste\" result from the literature. For that, having Section 4 in the paper is a distraction. \n\nI recommend the authors to study the theoretical guarantees of the contextual Bayesian algorithm in Section 5.", "other_comments_or_suggestions": "- The function $\\phi$ is used in Algorithm 1, but $\\phi$ is defined in the proof of Proposition 4.1. I recommend defining phi in the main text", "questions_for_authors": "1. Could the authors provide the readers with several reasonable scenarios where online learning could be blended with *consequential* decision making with long delayed feedbacks? This requires specifying the distribution $\\mathcal D$ (see end of Section 3.1) and validating that the support of $\\mathcal D$ is appropriate with the horizon $T$ of the online learning framework.\n\n2. Is it possible to provide any guarantees for the algorithms proposed in Section 5?", "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": "", "extra_scores": {}}, {"review_id": "wXVJrDcnV8", "reviewer": "Reviewer_aPEN", "summary": "This paper proposes an online algorithmic recourse setting where an unknown oracle returns the real-world outcome for a given input. The authors introduce bandit algorithms to address this problem. Experiments demonstrate that their proposed methods outperform existing recourse approaches.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for valuable and thoughtful feedback. We will reflect all of them in our final version. In the following, we will respond to the key comments and questions raised by the reviewer. \n\n---\n\n> The main concern I have is the real-world application (i.e., why should we care about the long-term improvement?). The algorithmic recourse algorithm operates under the assumption that the underlying model $h$ describes the whole world (which is an unrealistic assumption rightly pointed out by the authors). In other words, the real $h^\\ast$ does not really matter, because it is $h$ which makes the decision. Let's consider the loan application scenario, and let $x'$ be the generated recourse of $x$. I would argue that the bank should always grant the loan if $h(x') = 1$, even if in reality, $h^\\ast(x') = 0$, and in such case, it might be more important to make $h \\approx h^\\ast$, rather than creating a new method to take into account this scenario.\n\nThank you for your insightful comment. We agree with the reviewer's comment that banks should grant the loan for $x'$ with $h(x') = 1$, even if $h^\\ast(x') = 0$, and that making $h$ close to $h^\\ast$ might be a direct solution. However, we believe that filling the gap between $h$ and $h^\\ast$ completely is unrealistic due to various factors such as data limitations, model complexity, and evolving real-world conditions. Therefore, we argue that it is still valuable to consider providing improvement-oriented actions even with the inherent limitations of $h$. \nIn addition, we conducted experiments in Appendix B.5 where we iteratively updated $h$ using the obtained feedbacks $(x', h^\\ast(x'))$ as new training samples. We observed that the existing baselines often failed to provide recourses $x'$ such that $h^\\ast(x') = 1$ even with the updated $h$. This suggests that making $h$ sufficiently close to $h^\\ast$ is still challenging in real-world scenarios. \nIn summary, our method contributes to bridging the gap between the practical necessity of using $h$ and the ideal scenario of knowing $h^\\ast$. We will add the above discussion to our final version. \n\n\n> In addition, I would also argue that such an online setting is definitely undesirable for the banks. If the user takes the first action $a_1$, and it results in $h^\\ast(x + a_1) = 0$ (meaning that the user defaults the loan), the bank will undertake the loss.\n> I would suggest the authors to come up with a concrete scenario that optimizing for the long-term improvements is useful and desirable.\n\nThank you for your important suggestion. As you mentioned, the banks may undertake the losses $h^\\ast(x_t+a_t) \\not= 1$ during the early phase $t$ where our algorithm explores improvement-oriented actions. However, we note that this issue with early losses is indeed the reason why we focus on minimizing the entire regret with respect to the loss over time $t = 1, 2, \\dots, T$. By explicitly optimizing for long-term improvement, we aim to balance the exploration of potentially beneficial actions with the need to mitigate immediate losses. From this perspective, we think that the loan application scenario you raised is a concrete scenario where optimizing long-term improvements is useful and desirable. While there may be initial defaults, the long-term benefits of guiding users towards actions that genuinely improve their repayment ability will outweigh the short-term risks. We will emphasize this point in our final version. \n\n\n> I am interested in learning how the recourse are generated for the categorical features, as they are one-hot encoded.\n\nIn our experiments, we employ the recourse generation algorithm based on the class prototypes (Van Looveren & Klaise, 2021). For an input instance $x$, this approach finds a recourse instance $\\tilde{x}$ from a subset of a training set such that $h(\\tilde{x}) = 1$ and that the input $x$ can reach with the minimum cost $c(a \\mid x)$, where $a = \\tilde{x} - x$. Because recourse instances $\\tilde{x}$ are selected from a training set, they inherently satisfy the one-hot constraints for categorical features. Consequently, the obtained recourse action $a$ naturally preserves the structure of categorical features. Note that we evaluate the cost of one-hot encoded features in the same manner as numerical ones and impose constraints on immutable features to prevent them from being altered by actions (e.g., gender and race in the COMPAS dataset). \n\n---\n\nWe hope that we have adequately addressed all your questions and concerns. Please let us know if we can provide any further details and/or clarifications. Thank you again for your valuable feedback.", "claims_and_evidence": "As far as I can tell, the claims made in the paper are supported by theoretical and empirical evidence.", "methods_and_evaluation_criteria": "The method is solid and makes sense, although it might lack novelty as this is a direct application from the bandit algorithms.", "theoretical_claims": "I glanced through the theoretical claims, and I did not catch an error.", "experimental_designs_or_analyses": "I think the experiment procedure is appropriate.", "relation_to_broader_scientific_literature": "To my knowledge, this paper addressed a novel problem.", "essential_references_not_discussed": "Not to my knowledge.", "other_strengths_and_weaknesses": "I find this paper addressing a novel algorithmic recourse problem, which is interesting. I also find the paper to be very well-written. \n\nThe main concern I have is the real-world application (i.e., why should we care about the long-term improvement?). The algorithmic recourse algorithm operates under the assumption that the underlying model $h$ describes the whole world (which is an unrealistic assumption rightly pointed out by the authors). In other words, the real $h^*$ does not really matter, because it is $h$ which makes the decision. Let's consider the loan application scenario, and let $x'$ be the generated recourse of $x$. I would argue that the bank should always grant the loan if $h(x')=1$, even if in reality, $h^*(x')=0$, and in such case, it might be more important to make $h \\approx h^*$, rather than creating a new method to take into account this scenario.\n\nIn addition, I would also argue that such an online setting is definitely undesirable for the banks. If the user takes the first action $a_1$, and it results in $h^*(x+a_1)=0$ (meaning that the user defaults the loan), the bank will undertake the loss. \n\nI would suggest the authors to come up with a concrete scenario that optimizing for the long-term improvements is useful and desirable.", "other_comments_or_suggestions": "NA", "questions_for_authors": "1. I am interested in learning how the recourse are generated for the categorical features, as they are one-hot encoded.", "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": "", "extra_scores": {}}, {"review_id": "lXeGeeWIsH", "reviewer": "Reviewer_3WCv", "summary": "Existing work in improvement-oriented algorithmic recourse assumes access to an accurate underlying model of whether or not a user taking an action improves their outcome. The paper proposes to overcome this limitation by using a bandit algorithm to learn a more accurate improvement model over time based on delayed feedback, while assuming that the action costs are known. The paper reduces this problem to a contextual bandit problem with delayed feedback, and proves that the resulting algorithm asymptotically achieves zero regret. They then propose a heuristic method to account for unknown costs. They then compare to class prototype-based algorithmic recourse, trustworthy actionable perturbation, and LinUCB.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for valuable and thoughtful feedback. We will reflect all of them in our final version. In the following, we will respond to the key comments and questions raised by the reviewer. \n\n---\n\n> What specifically is meant by \"long-term perspective\"? The phrase comes up repeatedly, but it never gets defined explicitly, and seems to mean something like \"the oracle used to estimate improvement becomes more correct over time\". This question is pretty minor, but could help me better understand the significance of the results.\n\nThank you for your important question. As you pointed out, the phrase \"long-term perspective\" in this paper refers to the idea that our framework becomes to accurately estimate the improvement of recourse actions over time as we obtain more feedback. In our final version, we will clarify and emphasize this point to avoid any ambiguity. \n\n\n> Isn't the LinUCB formulation somewhat misspecified? The outcome labels seem to be binary which is fine for LinUCB formally, but it seems like you could probably get better performance by using a more suited model.\n\nThank you for your insightful comment regarding our model. Because our algorithm is based on the OTFLinUCB algorithm (Vernade et al. 2020) that is tailored for the formulation where the outcome is binary, we think our LinUCB formulation is not misspecified. Of course, we acknowledge the potential to get better performance by designing more suited models and algorithms for our problem, which is an important direction for future research. \n\n---\n\nWe hope that we have adequately addressed all your questions and concerns. Please let us know if we can provide any further details and/or clarifications. Thank you again for your valuable feedback.", "claims_and_evidence": "1) The paper claims that the task can be reduced to a contextual linear bandit problem with delayed feedback. This is supported by Proposition 4.1.\n\n2) The paper claims that LinUCB can solve the problem well when the costs are known. This is supported by the experiments in Figures 2, 3, and 4 though primarily 2.\n\n3) The paper claims that a proposed heuristic method can solve the problem well, as supported by the empirical results.", "methods_and_evaluation_criteria": "Yes, though the choice of baseline is critical for making this argument and I am not familiar enough with the recourse literature to evaluate it.", "theoretical_claims": "I did not carefully check the", "experimental_designs_or_analyses": "The experimental designs seemed valid, though the choice of baseline is a critical question that I'm not familiar enough with the literature to comment on further.", "relation_to_broader_scientific_literature": "They clearly show their relationship to contextual bandits with delayed feedback, as well as the algorithmic recourse literature.", "essential_references_not_discussed": "I am unaware of any critical missing references, though I am not an expert in the algorithmic recourse literature.", "other_strengths_and_weaknesses": "Originality: This paper, as far as I know, makes original contributions in combining algorithmic recourse with contextual bandits with delayed feedback.\n\nSignificance: The results are significant, improving over current algorithmic recourse methods.\n\nClarity: The paper is generally clear, though it could be clarified what is meant by \"long term perspective\".", "other_comments_or_suggestions": "n/a", "questions_for_authors": "1) What specifically is meant by \"long-term perspective\"? The phrase comes up repeatedly, but it never gets defined explicitly, and seems to mean something like \"the oracle used to estimate improvement becomes more correct over time\". This question is pretty minor, but could help me better understand the significance of the results.\n2) Isn't the LinUCB formulation somewhat misspecified? The outcome labels seem to be binary which is fine for LinUCB formally, but it seems like you could probably get better performance by using a more suited model.", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper studies algorithmic recourse in a setting where the goal is to both be approved by the classifier and achieve the desired true label. They model this problem as a delayed feedback and use tools from bandit literature to provide no regret algorithms. 

This is an important problem and studies an overlooked aspect of the original recourse problem. The reviewers generally liked the paper and its contribution. They found the paper well written and the experimental setting to be convincing.

The reviewers also had some concerns about the reasonability of the assumption (for example, the long feedback delay) or straightforward applications of previously studied bandit settings. I encourage the authors to discuss all of these concerns in the limitation section.
Decision: Accept (poster)