Algorithmic Recourse for Long-Term Improvement

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.

---

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.

Thank 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.

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.

Thank 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.

---

We 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.

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.

---

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.

Thank 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$. In 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. In 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.

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. I would suggest the authors to come up with a concrete scenario that optimizing for the long-term improvements is useful and desirable.

Thank 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.

I am interested in learning how the recourse are generated for the categorical features, as they are one-hot encoded.

In 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).

---

We 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.

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.

---

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. [...] and we need to avoid hacking/gaming [...].

Thank 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:

• 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.
• 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.
• 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$.

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.

We summarize three scenarios where an online learning approach could be suitable for consequential decision-making:

In 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.

Other Strengths And Weaknesses 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.

Thank 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:

• 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.
• 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.

Questions For Authors 2. Is it possible to provide any guarantees for the algorithms proposed in Section 5?

Thank 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.

---

We 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.

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.

---

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?

Thank you for your important comment on our reward model. We 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$. In 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$.

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?

Thank 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.

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?

Thank you for your important question. The 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. In 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.

---

We 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.