Time Can Invalidate Algorithmic Recourse

1. it would increase the clarity of the paper if Q and P are briefly described in Def. 1

We revised Definition 1 to include the potential choices of Q within the definition.

2. Eq. 5: It is unclear how θ and Δ are related

We revised Definition 3 to describe $\Delta$ as “perturbations” instead of interventions to underline their distinction from $\theta$.

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

By a linear approximation of a non-linear model we mean simple models such as LIME [1] which provide a local linear approximation of the decision boundary near a given point $\mathbf{x}$ by training a single linear model $h(\mathbf{x})$. Following the reviewer's suggestion, we clarified the statement in the revised manuscript.

4. An additional time-specific plot would be beneficial to underline the statement made in Fig. 3.

As suggested by the reviewer, we added a time-specific plot in Appendix D and referenced it in the main manuscript (line 429).

5. Experimental setup: 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.

We describe the structure of the approximate SCM and additional details in Appendix C.4 and C.5. In practice, following previous approaches [2], we learn a separate generative model for each structural equation of the SCM and we train it. We assume we can represent the actionable features $X_i$ as Gaussian random variables $\mathcal{N}(\mu^t_i, 1)$ with constant variance and time-dependent $\mu^t$. For each random variable $X_i$, we define the mean as the output of a regressor $f_i$ taking as input the parents $\mathbf{Pa}^t_{X_i}$ and the time $t$. We train each regressor by minimizing the MSE over a batch of observations over the corresponding random variable $X_i$. We report here the MSE over 50 timesteps (2000 individuals) for the approximate SCMs we used in Section 4.2. We compute the MSE for each feature for each timestep, and then we average. We show the empirical average MSE and standard deviation over 10 runs: $1.162 \pm 0.005$ (Adult), $258.226 \pm 7.328$ (COMPAS) and $10.447 \pm 0.037$ (Loan). We revised Appendix C.5 to add these results.

6. Def. 4: Is P(Yt|Xt) assumed to be stationary here

No, we assume $P(Y^t \mid \mathbf{X}^t)$ is not stationary in Definition 4. We clarified this point in the revised version of the manuscript (lines 304-305).

7. line 364: Why could the proposed algorithm not be used for CAR?

In practice, the reviewer is right and Algorithm 1 could also be used to optimise CAR over time, rather than SAR. However, in Section 3.2, we showed the optimum for CAR cannot be recovered when the exogenous variables have non-zero variance, which happens in the vast majority of situations. Thus, we felt that optimising for SAR was more appropriate because this setup – following the relevant literature [2] - is considered more easily implementable and realistic.

8. Fig. 5: Why is the standard deviation so high on Loan for T-SAR?

Loan represents a non-linear SCM (as described in Appendix C.3) and we empirically found it was the most difficult to optimize for. Our suggested recourses are still robust to time in expectation but since our estimator of $P(\mathbf{X}^t)$ is not perfect, they exhibit a larger standard deviation. Indeed, in the experiments with a perfect estimator (Appendix G), the standard deviation is much smaller.

[1] Ribeiro et al. "" Why should I trust you?" Explaining the predictions of any classifier." SIGKDD (2016)

[2] Karimi et al. "Algorithmic recourse under imperfect causal knowledge: a probabilistic approach." NeurIPS (2020)

1. The problem formulation is not clear and kind of vague. [...]. And the notation do(\theta) is confusing, because it is not clear that at which time step the intervention is conducted

Given the current state of the user $x^t$, Definition 1 considers the problem where we want to find the recourse $\theta$ which, if applied at time $t+\tau$ would achieve recourse at $t+\tau$. Following the reviewer’s suggestion, we revised Definition (1) to state more clearly the problem statement and we added a clarification to the $do(\theta)$ notation (lines 207-208) about the time when the intervention $\theta$ is applied.

2. [...] the key component about label is the classifer h. After h is trained, the true label makes no effect on the generation of AR. [...] I guess it is needed to adjust the statement in the theoretical analysis.

We would like to clarify how our theoretical analysis always considers a classifier $h$ approximating the conditional $P(Y \mid \mathbf{X})$ in line with the recourse literature. The only exception is Proposition 1 since it concerns the feasibility of computing the counterfactual distribution over the future from a causal perspective. We believe the confusion stemmed from us reporting the joint distribution $P(\mathbf{X}^t, Y^t)$, rather than simply $P(\mathbf{X}^t)$. We corrected this in the revised manuscript by updating all the theorems, propositions and corollaries.

3. I think some notations are confusing. For example, in E.q.(9) the B(x^t;τ) refers to the future feature after time τ. However, in line 388, the example of B(x^t;τ) is not relevant to time interval τ.

We revised the notation in the manuscript by removing the dependence over $\tau$ for the uncertainty set $B$ defined for non-causal recourse (page 8, lines 388-389).

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

This naive solution would be to wait until the user reaches $t+\tau$, so that we can observe her new state $\mathbf{x}^{t+\tau}$, and then compute a new recourse suggestion. However, in our setting, the user could still implement this new suggestion at a later time $t+\tau’$, where $\tau’ > \tau$ and she would not be guaranteed to obtain recourse.

5. [...] how the causality play the role in the proposed method.

In our work, we assume the stochastic process $P(\mathbf{X}^t, Y^t)$ factorizes following a causal structure represented by a structural causal model (SCM) [1]. We define a recourse suggestion as a causal soft intervention $do(\mathbf{X}=\mathbf{x}+\theta)$. Thus, our recourse problem boils down to finding the cheapest intervention $\theta$ such that the user will obtain a positive classification (in expectation), as per Definition 1. Moreover, given a recourse intervention $\theta$, the SCM enables us to compute the causal effects it produces (in expectation) on the user’s features once it is applied e.g., via the interventional or counterfactual distributions (Eq. 2). Lastly, the SCM enables us to simulate the user evolution over time to compute the uncertainty set B (Equation 9, line 371). All these aspects are used by Algorithm 1 to generate recourse suggestions robust to time by exploiting the causal structure of the stochastic process by design.

6. Did the authors examine whether the produced recourse is compatible with the causal relationship among variables.

Following the answer for (5.), we remark that Algorithm 1 produces recourse interventions satisfying the causal relationship among variables by design. This also includes considering their potential non-actionability, as noted in footnote 1. E.g., we cannot ask someone to get younger as an intervention.

[1] Pearl, Judea. Causality. Cambridge University Press, 2009.

1. The explanation of how temporal sensitivity interacts with causality is unclear.

[The paper] doesn’t sufficiently explain how different timing of interventions might lead to varied results, especially in non-stationary environments.

We would like to clarify that we consider a setting where any recourse is implemented, and its total causal effects are observed, at time $t + \tau$, and $\tau > 0$ is fixed. Therefore, the timing $\tau$ when the user chooses to perform the intervention is crucial to determine the validity of the recourse. We remark that in this setting, time hinders the validity of recourse because of the potential non-stationarity in the stochastic process, producing diverse causal effects depending on $\tau$. Following the reviewer’s comment, we revised Definition 1 and “Limitations” to better underline our modelling choice and the dynamic of the actions.

2. The paper assumes precise trend estimation [...]. [This] affects T-SAR’s practical applicability.

[The paper] lacks a thorough discussion of the limitations that could arise if the trend estimator is flawed.

We wish to remark how, in Section 4.2, we show empirical evidence on realistic datasets that an imperfect estimator of $P(\mathbf{X}^t)$ can still be beneficial. We agree that estimating $P(\mathbf{X}^t)$ can be hard, and we revised the “Limitations” (Section 5) to better state our assumptions and the underlying difficulty of learning a good estimator.

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

We would like to clarify that Algorithm 1 solves the temporal subpopulation recourse problem (T-SAR) since it considers the interventional distribution in Definition 1, rather than the counterfactual one. This fact enables us to sidestep the negative results of Proposition 1. Moreover, Algorithm 1 robustifies by design against the uncertainty coming from the exogenous factors by returning an intervention $\theta$ valid within an uncertainty set $B(\mathbf{x}^t; \tau)$ (Equation 9, Section 3.6). We construct the uncertainty set by sampling a finite number of individuals from the estimator $\tilde{P}(\mathbf{X}^{t+\tau} \mid \mathbf{X}^t = \mathbf{x}^t)$ conditioned on the current state of the individual $\mathbf{x}^t$. In practice, we are simulating the evolution of the user until $t+\tau$ by considering a “set” of likely future versions of the user, and we ensure the recourse suggestion is valid for all of them. Since the data manifold generated by the uncertainty set $B(\mathbf{x}^t; \tau)$ conforms to the causal generative process (under the assumption of having a reasonable estimator), we are effectively taking into account and counteracting the uncertainty coming from the exogenous factors when computing recourse.

4. 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? discuss alternative methods to ensure robust recourse

In our work, we account for the non-stationarity of the process by giving Algorithm 1 access to an estimator $\tilde{P}(\mathbf{X}^t)$ such to provide robust recourse suggestions accounting for both stationary and non-stationary time series. As described in (3.), this feature enables Algorithm 1 to provide by design robust recourse solving T-SAR. Moreover, we would like to point the reviewer to Sections 4.1 and 4.2 where we provide an empirical evaluation showing that Algorithm 1 effectively provides robust recourse under several synthetic and realistic non-stationary time series.

1. It requires an estimator that [...] is never available [and] could be misspecified.

We agree that estimating $P(\mathbf{X}^t)$ can be difficult, but we disagree that doing so is hopeless. The time series literature keeps proposing new techniques (some more successful than others [1]) and validating them in multiple scenarios, such as the M4 competition [2], and its successive editions, where they benchmark 61 distinct methods on 100000 different time series. Moreover, our experiments show how even imperfect estimators can be beneficial in some settings (Section 4.2). But even if such an estimator is impossible to obtain, all our negative results -- which are the core message of our work -- still apply: time compromises the validity of recourse, which can have serious consequences.

We understand the reviewer's concerns, so we updated the Abstract and “Limitations” to clarify our assumptions and the underlying difficulty of learning an estimator.

2. It omits the feedback loop

We would like to clarify that we consider a setting where any recourse is implemented, and its total causal effects observed, at time $t + \tau$, and $\tau > 0$ is fixed. In causal terms, we assume our SCM exhibits instantaneous effects [5]. Therefore, we do not need to extend the $\tau$ interval, and the only uncertainty lies in which $\tau$ the user will choose to perform the intervention. We remark that even in this setting, time still hinders the validity of recourse because of the potential trends in the stochastic process, and modelling delayed causal effects would be a nice extension, but it would not invalidate our theoretical analysis. We do agree with the reviewer that, if the total causal effects of recourse cannot be observed within $t+\tau$, we would need to adaptively adjust $\tau$ in Algorithm 1 by looking at when the last causal effect will take place.

Following the reviewer's concern, we revised Definition 1 and “Limitations” to better underline our modelling choice.

3. The authors should [study] the trade-off of cost-validity.

Following the reviewer’s suggestion, we performed additional experiments to study the trade-off between cost and validity by varying the $\lambda$ parameter in Algorithm 1 controlling the penalty for not achieving recourse. We report the results in Appendix E. These illustrate a trade-off between the cost of an intervention and its validity over time: cheaper interventions almost surely have reduced validity over time. Therefore, T-SAR suggests more conservative actions: this is sensible because what matters for users is overturning the classification e.g., being granted the loan. However, the magnitude of the reduction in validity depends on the setting, classifier $h$ and quality of the estimator.

4. separate sub-population and counterfactual recourse in exposition

Following the reviewer's comment, we added a table in Appendix A (to be moved to the main text later on, for visibility) summarizing the differences between all the various methods we considered, referencing our theoretical results. We also reference this table in Sec. 3 (lines 153-154) of the main text.

5. missing stationary in Prop 3

Thank you, we fixed the statement.

6. p4: ``However, this does not prevent invalidation if the user implements this updated recourse later on.”

Following our previous clarification on our setting in (2.), we remark the naive solution would be to wait until the user reaches $t+\tau$, so that we can observe her new state $\mathbf{x}^{t+\tau}$, and then compute the new recourse suggestion. However, in our setting, the user could still implement this new suggestion at a later time $t+\tau’$, where $\tau’ > \tau$ and she would not be guaranteed to obtain recourse.

7. Should the RHS of Eqs (7) and (8) be $< 1$? [When] are these bounds meaningful?

Eqs (7) and (8) consider a linear classifier $h(\mathbf{x}) = \langle \mathbf{x}, \beta \rangle$. Thus, the difference between $h^t$ and $h^{t+\tau}$ can be greater than 1 depending on whether $\mathbf{X}^t$ and $\beta$ are normalized in a $k$-ball. The bound can be meaningful to compare a-priori two interventions $\theta_1$ and $\theta_2$ to understand their “risk” to be invalidated before suggesting them to the user e.g., a time-agnostic intervention might cause a larger $\Delta(h, \theta)$.

[1] Lim et al. "Temporal fusion transformers for interpretable multi-horizon time series forecasting" International Journal of Forecasting (2021)

[2] Makridakis et al. "The M4 Competition: 100,000 time series and 61 forecasting methods" International Journal of Forecasting (2020)

[3] Karimi et al. "Algorithmic recourse under imperfect causal knowledge: a probabilistic approach" NeurIPS (2020)

[4] Dominguez-Olmedo et al., "On the adversarial robustness of causal algorithmic recourse" ICML (2022)

[5] Peters et al., Elements of causal inference: foundations and learning algorithms (2017)

I thank the authors for their replies.

1. I do not doubt that our field is making better prediction models. But the authors cite M4 competition, which has nothing to do with human data. Recourse problems are applied to consequential domains where human lives are at stake. Unfortunately, in these domains, data are quite scarce. There is a big gap here between what the authors need (prediction model for human behavior) and the availability of data for a practical and relevant application.

Time can invalidate recourses is also not something too insightful, in my opinion. This is just a simple "robustness" claim: the solution of an optimization problem is not robust when the underlying input changes. Our field has been talking about robustness for decades.

3. Could the authors explain why varying lambda is meaningful? My concern is with line 4 of Algorithm 1, where x* is already very conservative. It has nothing to do with lambda in line 5.

4. I don't understand this argument. Why don't we wait until time $t+\tau'$ and recommend another recourse when we reach time $t + \tau'$? In fact, we should first ask the person: "Are you ready to implement the recourse now?" If the answer is Yes, we compute the recourse. If the answer is No, then we respond: "Here is an example of recourse if you can implement now. But come back later for a more appropriate recourse when you are ready to implement" <I am just state roughly the idea, please do not quote>