Time Can Invalidate Algorithmic Recourse

Authors: Giovanni De Toni, Stefano Teso, Bruno Lepri, Andrea Passerini
Primary area: interpretability and explainable AI
Keywords: algorithmic recourse, counterfactual explanations, causality, explainable ai

Abstract:
Algorithmic Recourse (AR) aims to provide users with actionable steps to overturn unfavourable decisions made by machine learning predictors. However, these actions often take time to implement (e.g., getting a degree can take years), and their effects may vary as the world evolves. Thus, it is natural to ask for recourse that remains valid in a dynamic environment. In this paper, we study the robustness of algorithmic recourse over time by casting the problem through the lens of causality. We demonstrate theoretically and empirically that (even robust) causal AR methods can fail over time except in the -- unlikely -- case that the world is stationary. Even more critically, unless the world is fully deterministic, counterfactual AR cannot be solved optimally. To account for this, we propose a simple yet effective algorithm for temporal AR that explicitly accounts for time under the assumption of having access to an estimator of the stochastic process. Our simulations on synthetic and realistic datasets show how considering time produces more resilient solutions to potential trends in the data distribution.

Decision: reject
Reviewer scores: 3, 5, 5, 8

Reviews and discussion:
<thread>
creation date:
1730133922243

thread_type:
official_review

<thread_object>
creator: reviewer_g3t6

<content>
summary:
The authors argue that some features based on which decision are made might change over time and theoretically study the robustness of algorithmic recourse in this context. They find that algorithmic recourse can be invalidated by non-stationary and exogeneous noise over time. Upon their theoretical findings, the paper proposes a novel algorithm that explicitly incorporates time in the recourse computation and empirically shows that the proposed algorithm suggests recourses with higher validity over time.

strengths:
- the paper is well-written and easy to follow
- the theoretical insights are novel and important for practical applications of algorithmic recourse
- proofs and derivations are complete and correct
- the empirical evaluation demonstrates the advantages of the proposed algorithm incorporating time explicitly

weaknesses:
- Def. 1 could be discussed a bit more in detail. It is not immediately clear what $P$ and $Q$ refer to in the definition. Although it is mentioned a bit further below, it would increase the clarity of the paper if $Q$ and $P$ are briefly described in Def. 1.
- Eq. 5: It is unclear how $\theta$ and $\Delta$ are related. Since $\Delta$ denotes a set of interventions, the notation is not intuitive. The authors should describe their relationship in a brief sentence.
- in lines 338-340, the authors write: "The upper bound is also useful for non-linear classifiers $h$ since we can represent their decision function close to a realization $\mathbf{x}^t$ with a local linear approximation." While I agree that non-linear functions can be approximated using a set of linear functions, it is not immediately clear why the upper bound from Theorem 6 should be useful for non-linear approximators in general. Having a set of linear functions approximating some non-linear function requires somehow merging/combining the upper bounds of the linear functions. Doing this is generally non-trivial since each linear function only considers a local subspace; thus, straightforward solutions like taking the $\max$ of all upper bounds would not work in general to obtain a global upper bound, would it?
- Fig. 3: I agree that the uncertainty clearly has a negative effect on validity. However, one cannot directly see the effect of time in this plot. An additional time-specific plot would be beneficial to underline the statement made in Fig. 3.
- Experimental Setup (4.2): A brief discussion on how the structure of the approximate SCM was obtained, as well as on how good the approximations of the structural equations were, would be beneficial.

questions:
- Def. 4: Is $P(Y^t | \mathbf{X}^t)$ assumed to be stationary here (since it was mentioned that only covariate-shift-like distribution shifts are considered in Sec. 3.1)? Because if so, distinguishing different $h^t$ would not make sense in my opinion.
- line 364: Why could the proposed algorithm not be used for CAR? 
- Fig. 5: Why is the standard deviation so high on Loan for T-SAR?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730275719756

thread_type:
official_review

<thread_object>
creator: reviewer_l6zz

<content>
summary:
This paper studies the problem of algorithmic recourse in the time series setting. Previous works on algorithmic recourse neglect the impact of time evolution on the variables. The authors theoretically analyze the validity of original algorithmic recourse in non-stationary and uncertain world and the stability of recourse over time. Based on the theroretical analysis, the authors propose a simple yet effective algorithm to produce the AR that can counteract the time. The experimental results on synthetic datasets and real-world datasets shows that the AR generated by the proposed method (T-SAR) can remain valid across time steps.

strengths:
This paper investigate an important but not studied problem, that is the influence of time on algorithmic recourse. This paper explore the problem from the pespective of both theory and empirical examinations. Extensive theoretical analysis is sound and comprehensive. The empirical improvement in experiements is significant, showing the effectiveness of the proposed method.

weaknesses:
1. The presentation of the paper could be further improved. The problem formulation is not clear and kind of vague. I guess the problem is to determine the intervention $\theta$ at time $t$ and implement it at a later time $t+\tau$ instead of determining intervention at $t+\tau$. However, it is not distinguished in the manuscript. And the notation $do(\theta)$ is confusing, because it is not clear that at which time step the intervention $\theta$ is conducted.
2. I think in the field of algorithmic recourse, the key component about label is the classifer $h$. After $h$ is trained, the true label makes no effect on the generation of AR, since the AR is computed to reverse the predicted label instead of true label. I guess it is needed to adjust the statement in the theoretical analysis.

questions:
1. I think some notations are confusing. For example, in E.q.(9) the $B(\mathbf{x}^t;\tau)$ refers to the future feature after time $\tau$. However, in line 388, the example of $B(\mathbf{x}^t;\tau)$ is not relevant to time interval $\tau$. 
2. I want the authors to explain the sentence "However, this does not prevent invalidation if the user implements this updated
recourse later on." in line 208.
3. I want to know how the causality play the role in the proposed method.
4. Did the authors examine whether the produced recourse is compatible with the causal relationship among variables.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730374198209

thread_type:
official_review

<thread_object>
creator: reviewer_tspd

<content>
summary:
This work investigates the temporal robustness of Algorithmic Recourse (AR), focusing on how AR methods often lose validity over time due to non-stationary data environments. The authors propose a time-aware causal recourse approach, "Temporal Sub-population Algorithmic Recourse (T-SAR)," designed to adapt to dynamic conditions by forecasting recourse stability. They theoretically and empirically demonstrate that both conventional and robust AR techniques struggle to maintain relevance over time, especially in non-deterministic environments, where optimal solutions are typically unattainable. The proposed T-SAR method shows promising results in maintaining recourse validity under various temporal trends and uncertainties.

strengths:
The concept of Temporal Sub-population Algorithmic Recourse (T-SAR) adds a unique dimension by incorporating time-awareness, which is relatively novel in the field of causal AR. The theoretical contributions are well-grounded in causal inference, and the authors provide a robust theoretical framework that explains why existing AR models may fail over time. By addressing the challenges of AR in non-static environments, this work highlights an important area for improvement in AR techniques. The emphasis on time-sensitive solutions could stimulate further research in ensuring AR methods remain effective as conditions change.

weaknesses:
The explanation of how temporal sensitivity interacts with causality is unclear. For instance, while the paper mentions the impact of time on causal interventions, it doesn’t sufficiently explain how different timing of interventions might lead to varied results, especially in non-stationary environments. This leaves readers uncertain about the long-term implications of time on AR effectiveness, as the dynamic causal effects of time-sensitive actions are only superficially addressed. 
The paper assumes precise trend estimation, which is unrealistic in many real-world applications where trend data is noisy and unreliable. This assumption affects T-SAR’s practical applicability, as trend inaccuracies could lead to degraded performance. Although the paper mentions non-stationary conditions, it lacks a thorough discussion of the limitations that could arise if the trend estimator is flawed.

questions:
1.	Proposition 1 states that achieving optimal counterfactual recourse depends on zero variance in exogenous factors.  In cases where variance is unavoidable, how significant is the impact on the effectiveness of T-SAR recommendations? Could you quantify this impact and discuss alternative methods to ensure robust recourse.
2.	Proposition 3 claims that optimal recourse remains valid as long as the stochastic process is stationary. However, real-world processes rarely exhibit perfect stationarity. Could you discuss specific non-stationary scenarios where T-SAR might underperform? Are there any adaptive features in T-SAR to account for non-stationary processes, or must stationarity be a prerequisite for its application?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730740468470

thread_type:
official_review

<thread_object>
creator: reviewer_ydw8

<content>
summary:
The paper raises an interesting point: because it takes time to implement the recourse, the distributions of the features may shift. Thus, in the future, after the recourse has been correctly implemented, the new feature is still possible to get invalidated by the classifier.

To resolve this problem, the paper proposes to estimate the future distribution of the features, and then solve a min-max iterative algorithm to find the recourse (Algorithm 1).

strengths:
1. The paper studies an interesting phenomenon: the temporal dimension of algorithmic recourse. It is a relevant problem since implementing recourses can take a long time. Thus, we need to have a mechanism to take the time-horizon (in this paper is $\tau$) into the recourse problem.

weaknesses:
The main downsides of this approach are

1. It requires an estimator $\tilde P(X^t)$. I would argue that in most practical settings, this distribution is never available. If it is available, it could be easily misspecified as well.

I believe there is a big gap between what the authors think are practical, and what I think are practical. It is extremely unclear to me how I could use the proposed method in a real-world deployment. The problem is complex when time is taken into account, and having access to a stochastic model $\tilde P$ in my opinion is the most difficult barrier. 

2. It omits the feedback loop: the robust recourse proposed in this paper will lead to a time-horizon of interest longer than $\tau$. To see this, suppose that a non-robust recourse recommends the loan applicant to get a Master’s degree. The robust recourse will recommend a larger cost action such as to get a PhD degree. However, getting a PhD degree takes even more time, and one needs to stretch the time horizon of interest longer. Nevertheless, this feedback effect is not taken into account in this paper.

3. Algorithm 1 is a robust approach where $x$ can take any possible values in the support of $\tilde P(X^{t + \tau} | X^t = x^t)$, which can be really conservative. This can be reflected by the high costs reported in Appendix C. The authors should conduct a multi-objective analysis, for example, by studying the trade-off of cost-validity.

Some minor concerns:

1. Regarding the exposition, the paper constantly switches between the sub-population recourse and the counterfactual recourse, making it a bit hard to follow. It would be better if the authors can separate the two cases and treat them in a clear, explicit manner. This will help the readers to distinguish the characteristics of the two cases.

2. The authors even forget to state that the stochastic process should be stationary in Proposition 3.

3. The last paragraph on page 4: ``However, this does not prevent invalidation if the user implements this updated recourse later on.” I do not fully understand this argument. And on the contrary, I believe that the naive approach seems to work best! With the complexity of the problem, a simple “recompute” with proper recalibration may be the best solution. The authors should (at the very least) benchmark against this naive solution.

4. Should the right-hand side of equation (7) and (8) be smaller than 1? Could the authors please provide explicit conditions for these bounds to be meaningful?

questions:
I hope the authors can address some of the weaknesses highlighted above
</content>
</thread_object>

</thread>
<thread>
creation date:
1731935605803

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
We would like to thank all reviewers for their careful and insightful comments, which helped us improve our paper. Please, find a point-by-point response below and the **revised PDF** incorporating the reviewers' suggestions with additional experimental results and clarifications. The changes are marked in **red** within the manuscript.
</content>
</thread_object>

</thread>


Metareview:
metareview:
I read the paper and all review/rebuttals.

The paper presents a way of setting up algorithmic recourse (AR) in the context of longitudinal causal models. This makes a lot of sense, as recourses take time to implement, and ultimately are meant to modify the state of the system in the future, even when coming from a counterfactual interpretation of changing a state that is already established. AR lacks longitudinal models (to the best of my knowledge) and I don't see much coming from the dynamic treatment regime (DTR) literature in causal inference that covers AR.

Having read the paper and being familiar with AR and DTRs, and causal inference in general, I still felt challenged to fully embrace the way the problem is framed. There is much in the control/causal Markov decision processes (MDPs) literature about the influence of dynamics on the timing and type of action we take to achieve a particular state of interest at a particular time, with more classical control problems being directly amenable to constrained optimization.

Say we take a purely control-based approach, where I choose an action $A^t$ *now* to be at a particular state in $X^{t + \tau}$ the future. (Here, I use $A$ instead of $\theta$ to denote actionable variables - I really appreciate that the paper distinguishes $\theta$ from $X$, but it's not unusual in DTRs to separate actionable from non-actionable variables in a very general way.) In DTRs, actionable variables can encode arbitrary soft interventions of $X$. If I'm an athlete, and classifier $\hat Y^t$ decided that with my running time $X^t$ I shouldn't be selected to be part of an Olympic training team, then I can enter a training regime now (and incur the corresponding costs), as indexed by $A^t$, so that in the next Olympics selection in $\tau$ time steps I'm expected to be ready with a good enough running time. Action $A^t$ can be a shift intervention in some current state variables (say, $X_1^t$ is my weekly leg workout time, and my new value of $A^t$ encodes that I should add 10 to my current $X_1^{t - 1}$ for the next $\tau' \leq \tau$ time steps). The policy $\pi_^t$ encodes whether $A^t$ was controlled as $do(A^t = a^t)$ or whether it was observational and uncontrolled - I can still infer the $do(\cdot)$ effect from observational data based on assumptions such as sequential ignorability etc.

All of the above is to say that it's a great direction to take AR toward dynamic causal models, but I found the framing hard to follow when there is already so much in the literature of sequential causal models from the point of view of pure reinforcement learning, control theory, or the causal community perspective of dynamic treatment regimes. I don't fully agree with several points of the reviewers, but I think that some of the points about framing are vindicated, despite fully acknowledging the positive points made by g3T6. It is very jarring to see a paper on longitudinal causal modeling without a single connection to the vast literature on dynamic treatment regimes that started in the 1980s (or even optimization of Markov Decision Processes in general) and is subject of popular textbooks such as Hernan and Robins's "Causal Inference: What If" - and I'm speaking as someone who is firmly in the machine learning community.

My conclusion: I thoroughly support the authors in their research program, but they will have a bigger impact, and be better understood not only within the machine learning community but the broader range of disciplines where AR is valued, if they add the extra effort of tapping as much as possible into the existing, and cross-disciplinary, immense literature on longitudinal causal modeling. I don't see in this literature almost anything explicit about AR. I think the authors will benefit much from trying to establish these links, as evidenced by most of the reviewers struggling to get into the finer points presented here (and we shouldn't write off their concerns, even if not perfectly formulated).