Time Can Invalidate Algorithmic Recourse

## Abstract

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.
Our simulations on synthetic and realistic datasets show how considering time produces more resilient solutions to potential trends in the data distribution.

## 1 Introduction

Machine Learning (ML) models play an increasingly prominent role in high-stakes decision-making tasks like credit lending [], bail approval [] and medical diagnosis [].
The general consensus is that, to ensure fairness, these systems need to provide users with tools to challenge their ruling, thus preserving human agency.
These requirements are also being mandated by recent AI legislation [].
Algorithmic Recourse (AR) [] aims to identify counterfactual explanations that users can follow to overturn unfavourable machine decisions.
For instance, AR methods might suggest a user obtain a master’s degree as this will net them a higher income and, in turn, higher chances of obtaining a loan.

In order to be of use, suggested recourse must be actionable [] and sufficiently inexpensive for the user to implement [].
We argue that actionability subsumes the notion of timing.
Indeed, in practical applications,
(i) recourse takes time to be implemented and to have an impact,
(ii) performing the same action at different times might produce different effects.
For instance, getting a degree takes years and only impacts salary after some time. Moreover, getting a degree at an older age reduces the expected salary increase.
Our key insight is that, since time plays a key role in the effectiveness of recourse, one has to ensure recourse suggestions should be robust to time, i.e., they should lead to a positive outcome irrespectively of when the user performs them, or at least for a user-defined point in the future.
See Fig. 1 for an illustration.

Many efforts have been directed at robustifying recourse suggestions in several scenarios [].
For example, Upadhyay et al. [] studies recourse under model shift due to, e.g., retraining, Pawelczyk et al. [] addresses recourse in case the user’s implementation of recourse is imperfect, and Dominguez-Olmedo et al. [] considers robustness to misspecification of the input instance.
To the best of our knowledge, little has been done to explicitly formalize recourse robustness over time.
Recently, Beretta and Cinquini [] evaluated the effect of time in AR by incorporating it in the recourse cost, thus not considering its effect on the validity.

Following Dominguez-Olmedo et al. [] and Beretta and Cinquini [], we study the problem of time in AR through the lens of causality [].
In causal recourse, recourse suggestions are modelled as interventions on the user’s features [], thus giving a reliable representation of how the features will change as the user acts on them to achieve recourse, provided we know the (approximate) causal model [].
We consider a novel setting in which we are asked to provide recourse for a causal (non-stationary) discrete-time stochastic process subjected to trends.
Our results challenge the usefulness of the mainstream variants of causal and non-causal AR extended in time, showing their recommendations can become invalid over time.

Our contributions. Summarizing, we (i) introduce a sound but intuitive formalization of temporal causal AR (Definition 1), based on causality [] and time-series with independent noise [],
(ii) show theoretically how uncertainty and non-stationarity hinder optimal counterfactual and sub-population recourse (CAR and SAR, []) for simple discrete-time stochastic processes,
(iii) show how robustifying recourse via uncertainty sets is not enough to counteract time (Proposition 5),
and (iv) present numerical simulations showcasing the detrimental effects of time on robust (non-)causal AR approaches, and showcase how a simple time-aware algorithm (Algorithm 1) can lessen such effects in synthetic and realistic settings (Section 4).

Figure: Figure 1: The validity of executed recourse suggestions can change over time $t$ (black) and AR methods should be robust to this effect (green).
Refer to caption: x1.png

## 2 Preliminaries and related work

Throughout, we indicate (random) variables $X$ in upper case, constants $x$ in lower case, vectors in bold ${\bm{\mathrm{x}}}$, and sets $\mathcal{X}$ in italics. We also abbreviate $\{1,\ldots,n\}$ as $[n]$.

Causality. Structural Causal Models (SCMs) [] allow us to formalize and reason about the causal behaviour of a system.
An SCM $\mathcal{M}=({\bm{\mathrm{X}}},{\bm{\mathrm{U}}},P,\mathcal{F})$ encompasses
endogenous variables ${\bm{\mathrm{X}}}=\{X_{i}\}^{d}_{i=1}$,
noise variables ${\bm{\mathrm{U}}}=\{U_{i}\}^{d}_{i=1}$ distributed according to $P({\bm{\mathrm{U}}})$,
and structural assignments $\mathcal{F}$ of the form $X_{i}\coloneqq f_{i}(\mathbf{Pa}_{i},U_{i})$ that describe all causal relationships between variables and their direct causes (or parents) $\mathbf{Pa}_{i}\subseteq{\bm{\mathrm{X}}}\setminus X_{i}$.
An SCM induces a pushforward distribution $P({\bm{\mathrm{X}}},{\bm{\mathrm{U}}})=P({\bm{\mathrm{X}}}\mid{\bm{\mathrm{U}}
})P({\bm{\mathrm{U}}})$, where $P({\bm{\mathrm{X}}}\mid{\bm{\mathrm{U}}})$ is deterministic.
Hard interventions $do({\bm{\mathrm{X}}}_{\mathcal{I}}={\bm{\mathrm{\theta}}})$ allow to implement external actions on an SCM. They replace a subset of variables ${\bm{\mathrm{X}}}_{\mathcal{I}}\subseteq{\bm{\mathrm{X}}}$ with constants ${\bm{\mathrm{\theta}}}\in\mathbb{R}^{|{\bm{\mathrm{X}}}_{\mathcal{I}}|}$, detached from their original parents, yielding a new SCM $\mathcal{M}^{do({\bm{\mathrm{\theta}}})}$ with updated structural assignments $\mathcal{F}^{do({\bm{\mathrm{\theta}}})}$ and an associated interventional distribution $P^{do({\bm{\mathrm{\theta}}})}({\bm{\mathrm{X}}})$.
Soft interventions $do({\bm{\mathrm{X}}}_{\mathcal{I}}={\bm{\mathrm{x}}}_{\mathcal{I}}+{\bm{
\mathrm{\theta}}})$ change how the affected variables depend on their parents without detaching them.
We shorten both kinds of intervention as $do({\bm{\mathrm{\theta}}})$, for simplicity.
SCMs also enable us to reason counterfactually about what would have happened if the world were different due to an intervention $do({\bm{\mathrm{\theta}}})$, all else being equal. Given a realization ${\bm{\mathrm{x}}}$, the counterfactual distribution $P^{do({\bm{\mathrm{\theta}}}),{\bm{\mathrm{X}}}={\bm{\mathrm{x}}}}({\bm{
\mathrm{X}}})$ is obtained by first abducing the exogenous factors ${\bm{\mathrm{U}}}$ in the original SCM and then inferring the state of ${\bm{\mathrm{X}}}$ in the intervened SCM, that is, $P^{do({\bm{\mathrm{\theta}}}),{\bm{\mathrm{X}}}={\bm{\mathrm{x}}}}({\bm{
\mathrm{X}}})=P^{do({\bm{\mathrm{\theta}}})}({\bm{\mathrm{X}}}\mid{\bm{\mathrm
{U}}})P({\bm{\mathrm{U}}}\mid{\bm{\mathrm{X}}}={\bm{\mathrm{x}}})$ [, Theorem 7.1.7]. If the structural equations are invertible, $P({\bm{\mathrm{U}}}\mid{\bm{\mathrm{x}}})$ is deterministic, and so is the counterfactual distribution.

Causal Algorithmic Recourse. In AR, the main quantities of interest are the user’s state ${\bm{\mathrm{x}}}\sim P({\bm{\mathrm{X}}})$ and the outcome $y\sim P(Y\mid{\bm{\mathrm{X}}})$, e.g., the event that the user will repay their loan.
The SCM underlying $P({\bm{\mathrm{X}}})$ is assumed to be known or estimated from data [], enabling us to apply interventions to evaluate the effect of changing the user’s state while considering all causal dependencies between variables.
Given a (potentially black-box) classifier $h:{\bm{\mathrm{x}}}\mapsto[0,1]$ approximating $P(Y\mid{\bm{\mathrm{X}}})$ and a realization ${\bm{\mathrm{x}}}$ yielding an undesirable outcome, i.e., $h({\bm{\mathrm{x}}})<1/2$, AR involves finding an intervention ${\bm{\mathrm{\theta}}}^{*}$ that, once implemented by the user, leads in expectation to a more favourable outcome.
There are two mainstream approaches to causal AR []. Sub-population recourse (SAR) provides recourse to users belonging to a specific sub-group, and it is defined as:(^1^11 The choice of ${\bm{\mathrm{\theta}}}$ is often restricted by actionability requirements (e.g., age cannot be changed at will) or other constraints (e.g., monotonicity: age can only increase). We omit this detail for readability.)

$$ $\displaystyle\textstyle{\bm{\mathrm{\theta}}}^{*}\in\operatorname*{argmin}_{{ \bm{\mathrm{\theta}}}\in\mathbb{R}^{d}}\ \mathbb{E}_{\hat{{\bm{\mathrm{x}}}} \sim P^{do({\bm{\mathrm{X}}}_{\mathcal{I}}={\bm{\mathrm{\theta}}})}({\bm{ \mathrm{X}}})}[C(\hat{{\bm{\mathrm{x}}}},{\bm{\mathrm{x}}})]\quad\mathrm{s.t.} \quad\mathbb{E}_{\hat{{\bm{\mathrm{x}}}}\sim P^{do({\bm{\mathrm{X}}}_{\mathcal {I}}={\bm{\mathrm{\theta}}})}({\bm{\mathrm{X}}})}[h(\hat{{\bm{\mathrm{x}}}})] \geq 1/2$ (1) $$

Here, $C$ is a non-negative cost function measuring the user’s effort, e.g., the $\ell_{2}$-norm.
Selecting a specific subgroup amounts to conditioning $P^{do({\bm{\mathrm{X}}}={\bm{\mathrm{\theta}}})}$ in Eq. 1 on a subset of variables ${\bm{\mathrm{X}}}_{nd(\mathcal{I})}={\bm{\mathrm{x}}}_{nd(\mathcal{I})}$ where $nd(\mathcal{I})$ indicates the non-descendants of the intervened upon variables $\mathcal{I}$.
Counterfactual recourse (CAR) allows computing individualized recourse for a specific individual, identified by ${\bm{\mathrm{x}}}$. It is formulated like Eq. 1, except that the interventional distribution $P^{do({\bm{\mathrm{\theta}}})}({\bm{\mathrm{X}}})$ is replaced with the counterfactual distribution $P^{do({\bm{\mathrm{\theta}}}),{\bm{\mathrm{X}}}={\bm{\mathrm{x}}}}({\bm{
\mathrm{X}}})$.
Lastly, since providing optimal recourse (Eq. 1) is harder for unrestricted SCMs [], causal AR typically assumes the SCM of $P({\bm{\mathrm{X}}})$ belongs to an identifiable and invertible class, e.g., Additive Noise Models (ANMs) [, , ].

Further related works.
Our work is related to works on robust AR, counterfactual explanations for time series and causality.
The literature on the robustness of algorithmic recourse aims at generating counterfactual explanations which are robust to the type of model $h$ updates and changes [, , , , ], endogenous dynamics [], model multiplicity [, ], noisy execution of the intervention [, ] or uncertainty on the input instance [, , ].
See Jiang et al. [] for a recent comprehensive survey on the topic.
None of these works explicitly formalize time as a dimension in their computational model.
Recently, Fonseca et al. [] studied empirically algorithmic recourse in a multi-agent setting where different users compete for resources over time, without a causal notion.
The literature on counterfactual explanations for multivariate time series provides instead techniques to generate explanations for stochastic processes [, ] by assuming either independent manipulable features (IMF) (i.e., no causal relationships between variables) or a simpler form of causality e.g., Granger causality [].

Figure: Figure 2: Algorithmic recourse is not robust in time. Empirical average validity and standard deviation of robust counterfactual (CAR), sub-population (SAR) and non-causal recourse (IMF) at time $t=50$ for synthetic (Section 4.1) and realistic (Section 4.2) time series with a non-linear trend. We report the validity varying the strength $\alpha$ of the trend. Legend: 0 0 $0.3$ $0.5$ $0.7$ $1.0$.
Refer to caption: x2.png

## 3 Algorithmic Recourse in Time

In real-world applications, users do not implement nor complete suggested interventions immediately. For instance, obtaining a degree can take years.
This is problematic because $P({\bm{\mathrm{X}}},Y)$ might change over time due to, e.g., inflation rates, seasonality of loan interests and classifier updates, respectively, meaning that recourse produced by existing approaches could become ineffective or even counterproductive in the future.
Fig. 2 shows the empirical average validity (% of interventions achieving recourse) of state-of-the-art robust (non-)causal recourse methods on different binary decision problems, where $P({\bm{\mathrm{X}}},Y)$ is a stochastic process exhibiting a non-linear trend.
Unfortunately, current robust (non-)causal recourse methods are increasingly fragile to time proportionally to the trend’s strength.
This section is devoted to this issue.

### 3.1 Formalizing Temporal Causal AR

Before proceeding, we need to extend causal AR with a time dimension.
We do so by considering a stochastic process $P({\bm{\mathrm{X}}}^{t},Y^{t})$ capturing the evolution of the user’s state and its relationship to the target variable over time $t\in\mathbb{N}$.
In the following, we assume that $P$ is induced by an SCM over the same variables in which the parents of each variable lie in the past, and specifically within a fixed (but otherwise arbitrary) horizon $\rho\geq 1$, i.e., $\mathbf{Pa}_{X_{i}^{t}}\subseteq\bigcup_{\delta=0}^{\rho}{\bm{\mathrm{X}}}^{t-\delta}$, and similarly for $Y^{t}$.
We also assume that the outcome $Y^{t}$ only depends on the user’s states ${\bm{\mathrm{X}}}^{1},\ldots,{\bm{\mathrm{X}}}^{t}$ up to time $t$.
We investigate the effect of time on recourse by considering stochastic processes where $P({\bm{\mathrm{X}}}^{t})$ might not be stationary, while the conditional distribution $P(Y^{t}\mid{\bm{\mathrm{X}}}^{t})$ is unchanged, similarly to covariate shift [].
For this reason, we can assume the classifier $h^{t}$ is fixed.(^2^22 If this is not the case, one option is to leverage existing techniques for addressing changes due to retraining, such as Upadhyay et al. [] and Pawelczyk et al. []. These works and ours are complementary and studying their interplay is a promising avenue for future work.)
This allows us to formulate Temporal Causal AR as follows:

###### Definition 1 (Temporal Causal AR) .

Consider a stochastic process $P({\bm{\mathrm{X}}}^{t},Y^{t})$, a cost function $C(\cdot,\cdot)$ (e.g., the $L_{2}$ norm), a constant classifier $h$ and a realization ${\bm{\mathrm{x}}}^{t}$ such that $h({\bm{\mathrm{x}}}^{t})<1/2$.
Given a time lag $\tau\in\mathbb{N}$, we want to find the cheapest intervention $do({\bm{\mathrm{X}}}^{t+\tau}_{\mathcal{I}}={\bm{\mathrm{x}}}^{t+\tau}_{
\mathcal{I}}+{\bm{\mathrm{\theta}}})$ that, in expectation, achieves recourse at time $t+\tau$:(^3^33 This formulation assumes that recourse is implemented, and its effects observed, at time $t+\tau$. However, it can be easily adapted to situations where recourse consists of multiple actions implemented asynchronously in between $t$ and $t+\tau$ by modifying the expected cost accordingly. Our results transfer to this case.)

$$ $\displaystyle{\bm{\mathrm{\theta}}}^{*}\in\min_{{\bm{\mathrm{\theta}}}\in \mathbb{R}^{d}}$ $\displaystyle\;\;\mathbb{E}_{\begin{subarray}{l}\hat{{\bm{\mathrm{x}}}}^{t+ \tau}\sim Q({\bm{\mathrm{X}}}^{t+\tau};{\bm{\mathrm{x}}}^{t+\tau},{\bm{\mathrm {\theta}}})\\ {\bm{\mathrm{x}}}^{t+\tau}\sim P({\bm{\mathrm{X}}}^{t+\tau}\mid{\bm{\mathrm{X} }}^{t}={\bm{\mathrm{x}}}^{t})\end{subarray}}[C(\hat{{\bm{\mathrm{x}}}}^{t+\tau },{\bm{\mathrm{x}}}^{t+\tau})]$ $\displaystyle\mathrm{s.t.}\;\;\mathbb{E}_{\begin{subarray}{l}\hat{{\bm{\mathrm {x}}}}^{t+\tau}\sim Q({\bm{\mathrm{X}}}^{t+\tau};{\bm{\mathrm{x}}}^{t+\tau},{ \bm{\mathrm{\theta}}})\\ {\bm{\mathrm{x}}}^{t+\tau}\sim P({\bm{\mathrm{X}}}^{t+\tau}\mid{\bm{\mathrm{X} }}^{t}={\bm{\mathrm{x}}}^{t})\end{subarray}}\left[h(\hat{{\bm{\mathrm{x}}}}^{t +\tau})\right]\geq 1/2$ (2) $$

Definition 1 deserves some discussion.
First of all, it describes both temporal subpopulation causal AR (T-SAR) and temporal counterfactual causal AR (T-CAR) depending on whether we take $Q({\bm{\mathrm{X}}}^{t+\tau};{\bm{\mathrm{x}}}^{t},{\bm{\mathrm{\theta}}})$ to be the interventional distribution $P^{do({\bm{\mathrm{X}}}^{t+\tau}_{\mathcal{I}}={\bm{\mathrm{x}}}^{t+\tau}_{
\mathcal{I}}+{\bm{\mathrm{\theta}}})}({\bm{\mathrm{X}}}^{t+\tau}\mid{\bm{
\mathrm{X}}}_{nd(\mathcal{I})}={\bm{\mathrm{x}}}_{nd(\mathcal{I})})$, or the counterfactual distribution $P^{do({\bm{\mathrm{X}}}^{t+\tau}_{\mathcal{I}}={\bm{\mathrm{x}}}^{t+\tau}_{
\mathcal{I}}+{\bm{\mathrm{\theta}}});{\bm{\mathrm{X}}}^{t+\tau}={\bm{\mathrm{x
}}}^{t+\tau}}({\bm{\mathrm{X}}}^{t+\tau})$.
We remark that, while practical solutions for T-SAR can be devised (see Section 3.6), T-CAR is intrinsically more challenging (as we discuss in Section 3.2).

Causal time series models. In the remainder we assume the stochastic process is a Time series Model with Independent Noise (TiMINo), adapted from []:

###### Definition 2 (TiMINo for Algorithmic Recourse) .

$P({\bm{\mathrm{X}}}^{t},Y^{t})$ satisfies TiMINo if it causally factorizes as $X^{t}_{i}=f_{X_{i}}(\mathbf{Pa}_{X_{i}^{t}})+U^{t}_{X_{i}}$ and $Y^{t}=f_{Y}^{t}({\bm{\mathrm{X}}}^{t})+U^{t}_{Y}$, for all $i\in[d]$, where $U_{X_{i}}^{t},U_{Y}^{t}$ are jointly independent and identically distributed for all $i\in[d]$ and $t\in\mathbb{N}$.

Under appropriate conditions, TiMINo SCMs are invertible, allowing us to apply causal reasoning to infer the counterfactual distribution when computing AR, and can be identified from observational data.
Specifically, under appropriate choices of the family of $f^{t}_{X_{i}}$, $f^{t}_{Y}$ – which still allow them to be non-linear – and $P({\bm{\mathrm{U}}}^{t})$ we are guaranteed to identify both the summary graph and full-time graph [].
Moreover, Peters et al. [] provide a causal discovery procedure for TiMINo time series that avoids drawing wrong causal conclusions in the presence of confounders.
Throughout the paper, we assume the full-time graph is sufficient (e.g., there are no unobserved confounders []).
We will show how, even in this optimistic scenario, our negative results for temporal recourse still hold.

Interventions in time. Intuitively, time can only invalidate recourse as long as those changes occurring after the time $t$ at which recourse is issued can influence the distribution of the future state ${\bm{\mathrm{X}}}^{t+\tau}$.
In the unlikely case that recourse is a hard intervention $do({\bm{\mathrm{X}}}^{t+\tau}={\bm{\mathrm{\theta}}})$ affecting all variables ${\bm{\mathrm{X}}}$, then ${\bm{\mathrm{X}}}^{t+\tau}$ no longer depends on its past states because such interventions detach all variables from their parents, overriding possible temporal effects []. Hence, recourse remains valid by construction.
In practice, however, recourse
i) is often restricted to few variables, due to, e.g., actionability and cost constraints, or
ii) may be defined as a soft intervention, that is, an intervention of the form $do({\bm{\mathrm{X}}}^{t}_{\mathcal{I}}={\bm{\mathrm{x}}}^{t}_{\mathcal{I}}+{
\bm{\mathrm{\theta}}})$, that does not detach ${\bm{\mathrm{X}}}^{t}$ [].
In the following, we focus on this more realistic setting with soft interventions.

On the naïve solution. One obvious “remedy” to counter the impact of time is to simply (allow users to) re-compute recourse (with CAR or SAR) at time $t+\tau$, assuming we have access to the new user’s state ${\bm{\mathrm{x}}}^{t+\tau}$. However, this does not prevent invalidation if the user implements this updated recourse later on.

###### Definition 1 (Temporal Causal AR) .

###### Definition 2 (TiMINo for Algorithmic Recourse) .

### 3.2 Uncertainty over time compromises counterfactual recourse

We begin by studying temporal counterfactual AR (T-CAR).
It provides invidividualized suggestions, thus achieving the true optimal intervention for a given user [].
According to Definition 1, it must be computed considering the future counterfactual distribution $P^{do({\bm{\mathrm{\theta}}});{\bm{\mathrm{X}}}^{t+\tau}={\bm{\mathrm{x}}}^{t+
\tau}}({\bm{\mathrm{X}}}^{t+\tau})$.
Unfortunately, this turns out to be problematic. The following proposition shows that this distribution cannot be recovered exactly except under strong assumptions.

###### Proposition 1 .

Let $P({\bm{\mathrm{X}}}^{t},Y^{t})$ satisfy TiMINo.
Given a realization ${\bm{\mathrm{x}}}^{t}$ and an intervention ${\bm{\mathrm{\theta}}}\in\mathbb{R}^{d}$, we can recover the counterfactual distribution over the future $P^{do({\bm{\mathrm{\theta}}}),{\bm{\mathrm{X}}}^{t}={\bm{\mathrm{x}}}^{t}}({
\bm{\mathrm{X}}}^{t+\tau})$ if and only if, for all $t>0$, $\mathrm{Var}({\bm{\mathrm{U}}}^{t})=0$ and $\mathbb{E}[{\bm{\mathrm{U}}}^{t}]$ are constant.

All proofs can be found in Appendix A.
In words, given ${\bm{\mathrm{x}}}^{t}$, one cannot know the true counterfactual distribution at time $t+\tau$ unless all exogenous factors have zero variance, that is, $P({\bm{\mathrm{X}}}^{t+\tau},\ldots,{\bm{\mathrm{X}}}^{t+1}\mid{\bm{\mathrm{x}
}}^{t})$ is deterministic.
Proposition 1 has profound consequences for recourse because, recalling the central role of the counterfactual distribution in Eq. 1, it entails that for non-deterministic processes we cannot solve T-CAR optimally.

###### Corollary 2 (Informal) .

Let $P({\bm{\mathrm{X}}}^{t},Y^{t})$ satisfy TiMINo.
Given a realization ${\bm{\mathrm{x}}}^{t}$, a counterfactual recourse ${\bm{\mathrm{\theta}}}\in\mathbb{R}^{d}$ applied at time $t+\tau$, with $\tau>0$, cannot be optimal unless exogenous factors have zero variance.

We explore this issue empirically in Section 4.
We remark that Proposition 1 also holds for non-TiMINo stochastic processes as long as they admit performing abduction (e.g., the structural equations are invertible), and so does Corollary 2.

###### Proposition 1 .

###### Corollary 2 (Informal) .

### 3.3 Sub-population AR deteriorates in a non-stationary world

Given the inherent limitations of temporal counterfactual AR, in the remainder, we focus on temporal sub-population AR (T-SAR), which is generally regarded as the most plausible form of recourse [].
The next proposition shows that, insofar as $P({\bm{\mathrm{X}}}^{t},Y^{t})$ is stationary(^4^44 A discrete stochastic process $\{{\bm{\mathrm{X}}}^{t}\}_{t\in\mathbb{N}}$ is (weak-sense) stationary when it satisfies the following properties: $\mathbb{E}[{\bm{\mathrm{X}}}^{t+\tau}-{\bm{\mathrm{X}}}^{t}]=0$ and $K(t+\tau,t)=K(\tau,0)$ for all $t,\tau\in\mathbb{N}$ where $K(p,q)=\mathbb{E}\left[(X^{p}-\mathbb{E}[X^{p}])(X^{q}-\mathbb{E}[X^{q}])\right]$ is the autocovariance and $\mathbb{E}[|{\bm{\mathrm{X}}}^{t}|^{2}]<\infty$ for all $t\in\mathbb{N}$.) and the classifier $h$ is constant and injective, recourse that is optimal for static sub-population recourse (Eq. 1) remains optimal over time (Eq. 2).

###### Proposition 3 .

Consider a stochastic process $P({\bm{\mathrm{X}}}^{t},Y^{t})$ and a constant injective classifier $h$. Any optimum ${\bm{\mathrm{\theta}}}^{*}$ of Eq. 1 is also optimal for Eq. 2 for any time lag $\tau\in\mathbb{N}$.

Despite this positive result, the issue is that stationarity is seldom satisfied in practice: many real-world processes exhibit trends (e.g., inflation rate, seasonality of loan interests, etc.).
The next example shows how recourse can become invalid if the $P({\bm{\mathrm{X}}}^{t},Y^{t})$ is not stationary, even for a simple one-dimensional trend-stationary(^5^55 A stochastic process $\{{\bm{\mathrm{X}}}^{t}\}_{t\in\mathbb{N}}$ is trend-stationary when it can be expressed as ${\bm{\mathrm{X}}}^{t}=f(t)+{\bm{\mathrm{e}}}^{t}$, where $f(t)$ is (non-)linear trend function and ${\bm{\mathrm{e}}}^{t}$ is a stationary stochastic process.) stochastic process.
Full derivations are in Appendix A.

###### Example 1 .

Consider a trend-stationary stochastic process defined by these structural equations:

$$ $\displaystyle X^{t}=\alpha X^{t-1}+m(t)+U_{X}^{t},$ $\displaystyle U_{X}^{t}\sim\mathcal{N}(\mu_{X},\sigma_{X})$ (3) $\displaystyle Y^{t}=\beta X^{t}+U_{Y}^{t},$ $\displaystyle U_{Y}^{t}\sim\mathcal{N}(0,1)$ $$

for all $t$, where $\alpha\in(0,1)$ and $\beta\in\mathbb{R}$.
The function $m(t):\mathbb{R}\rightarrow\mathbb{R}$ represents a trend independent of $X^{t}$ and $Y^{t}$.
We consider a linear trend $m(t)=-ct+U_{m}^{t}$, where $U_{m}^{t}\sim\mathcal{N}(\mu_{m},\sigma_{m})$ and $c\in\mathbb{R}^{+}$.
Consider the fixed classifier $h(X^{t})=\sigma(Y^{t}\mid X^{t})$ where $\sigma(x)=1/(1+e^{-x})$.
We have that the optimal intervention $\theta^{t+\tau}\in\mathbb{R}$ for which we have $\mathbb{E}[h(X^{t+\tau}+\theta)]\geq 1/2$ can be expressed as:

$$ $\textstyle\theta^{t+\tau}=-\alpha^{\tau+1}x^{t-1}-\sum_{i=0}^{\tau}\alpha^{ \tau-i}(-c(t+i)+\mu_{m}+\mu_{X})$ (4) $$

Since $m(t)$ is monotonically decreasing for $c>0$, we have the optimal interventions satisfy $\theta^{t}\leq\theta^{t+\tau}$, implying that a recourse issued at time $t$ becomes invalid as time passes.
Following Proposition 3, we can state the following general corollary regarding our ability to provide optimal subpopulation recourse for general stochastic processes:

###### Corollary 4 (Informal) .

Consider a discrete-time process $P({\bm{\mathrm{X}}}^{t},Y^{t})$. Unless it is stationary, the optimal intervention ${\bm{\mathrm{\theta}}}^{*}$ achieving recourse can vary depending on $t,\tau\in\mathbb{N}$.

###### Proposition 3 .

###### Example 1 .

###### Corollary 4 (Informal) .

### 3.4 Robust algorithmic recourse is not enough to counteract time

Given the previous results, we could imagine to robustify the recourse procedure to account for non-stationarity of $P({\bm{\mathrm{X}}}^{t},Y^{t})$.
For example, a common solution to robustify CAR and SAR is to provide an intervention ${\bm{\mathrm{\theta}}}$ achieving recourse within a causal “uncertainty set” $B({\bm{\mathrm{X}}};\Delta)$, defined below
[].
In this section, we show how set-based robust causal recourse method falls short when dealing with time.
We first start by defining robust causal AR:

###### Definition 3 (Adapted from Dominguez-Olmedo et al. [ 12 ] ) .

Consider a realization ${\bm{\mathrm{x}}}\in\mathbb{R}^{d}$, a norm $||\cdot||$, and a tolerance $\epsilon>0$. We define a causal uncertainty set $B({\bm{\mathrm{x}}};{\bm{\mathrm{\Delta}}})=\{{\bm{\mathrm{x}}}^{\prime}\sim P
^{do({\bm{\mathrm{\Delta}}}),{\bm{\mathrm{X}}}={\bm{\mathrm{x}}}}({\bm{\mathrm
{X}}}):||{\bm{\mathrm{\Delta}}}||\leq\epsilon\}$ as the collection of the causal counterfactuals under small additive interventions ${\bm{\mathrm{\Delta}}}\in\mathbb{R}^{d}$.
We want to find the cost-minimizing intervention ${\bm{\mathrm{\theta}}}$ achieving recourse in all the region defined by $B({\bm{\mathrm{x}}};{\bm{\mathrm{\Delta}}})$.
Thus, the optimization objective for robust recourse becomes:

$$ ${\bm{\mathrm{\theta}}}^{*}\in\operatorname*{argmin}_{{\bm{\mathrm{\theta}}}\in \mathbb{R}^{d}}\ \mathbb{E}[C({\bm{\mathrm{x}}},\hat{{\bm{\mathrm{x}}}})]\quad \mathrm{s.t.}\;\;\mathbb{E}[h(\hat{{\bm{\mathrm{x}}}})]\geq 1/2\quad\forall\;{ \bm{\mathrm{x}}}^{\prime}\sim B({\bm{\mathrm{x}}};{\bm{\mathrm{\Delta}}})$ (5) $$

where $\hat{{\bm{\mathrm{x}}}}$ is distributed according to either the counterfactual or interventional distribution e.g., $\hat{{\bm{\mathrm{x}}}}\sim P^{do({\bm{\mathrm{\theta}}})}({\bm{\mathrm{X}}}
\mid{\bm{\mathrm{X}}}_{nd(\mathcal{I})}={\bm{\mathrm{x}}}^{\prime}_{nd(
\mathcal{I})})$.

A robust intervention might still obtain recourse for later time steps depending on the tolerance $\epsilon$. Intuitively, by asking the user to perform a more difficult action (e.g., increase your income by $\$1000$, instead of $\$100$), we can provide interventions that are less susceptible to potential dynamics. However, if the intervention is applied too late, we will not achieve recourse:

###### Proposition 5 .

Consider a fixed $\epsilon>0$, a trend-stationary process $P({\bm{\mathrm{X}}}^{t},Y^{t})$, a constant injective classifier $h$ and realization ${\bm{\mathrm{x}}}^{t}$ where $h({\bm{\mathrm{x}}}^{t})<1/2$. Let us assume we have an optimal $\epsilon$-robust intervention ${\bm{\mathrm{\theta}}}$ for timestep $t$. There always exists a trend $m:\mathbb{N}\rightarrow\mathbb{R}$ and a positive $\tau$, such that $\mathbb{E}_{{\bm{\mathrm{x}}}^{t+\tau}\sim P^{do({\bm{\mathrm{\theta}}})}({\bm
{\mathrm{X}}}^{t+\tau}\mid{\bm{\mathrm{X}}}_{nd(\mathcal{I})}^{t+\tau}={\bm{
\mathrm{x}}}_{nd(\mathcal{I})}^{t+\tau},{\bm{\mathrm{X}}}^{t}={\bm{\mathrm{x}}
}^{t})}{[h({\bm{\mathrm{x}}}^{t+\tau})]}<1/2$.

###### Definition 3 (Adapted from Dominguez-Olmedo et al. [ 12 ] ) .

###### Proposition 5 .

### 3.5 On the stability of recourse over time

In Sections 3.2, 3.3 and 3.4, we showed how recourse validity can be compromised by the uncertainty and non-stationarity of the stochastic process $P({\bm{\mathrm{X}}}^{t},Y^{t})$, and we also showed how set-based robustness techniques fail over time.
However, users might be willing to accept recourses that slowly become less effective rather than performing more challenging interventions.
Thus, we now characterize instead the rate at which our recourse suggestion validity decreases.
Additionally, we consider a non-constant classifier $h^{t}$ to provide more comprehensive results.

###### Definition 4 (Temporal recourse invalidation rate) .

Consider a discrete-time stochastic process $P({\bm{\mathrm{X}}}^{t},Y^{t})$, and any classifier $h^{t}$ approximating $P(Y^{t}\mid{\bm{\mathrm{X}}}^{t})$ for each $t\in\mathbb{N}$.
Given a realization ${\bm{\mathrm{x}}}^{t}$ and an intervention ${\bm{\mathrm{\theta}}}$ such that $\mathbb{E}[h(\hat{{\bm{\mathrm{x}}}}^{t})]\geq 1/2$, where $\hat{{\bm{\mathrm{x}}}}^{t}\sim P^{do({\bm{\mathrm{\theta}}})}({\bm{\mathrm{X}
}}^{t}\mid{\bm{\mathrm{X}}}_{nd(\mathcal{I})}^{t}={\bm{\mathrm{x}}}_{nd(
\mathcal{I})}^{t})$, we define the temporal invalidation rate after a time-lag $\tau>0$ as:

$$ $\Delta h({\bm{\mathrm{\theta}}};\tau)=\mathbb{E}\left[\left|h^{t+\tau}(\hat{{ \bm{\mathrm{x}}}}^{t+\tau})-h^{t}(\hat{{\bm{\mathrm{x}}}}^{t})\right|\right]$ (6) $$

where $\hat{{\bm{\mathrm{x}}}}^{t+\tau}\sim P^{do({\bm{\mathrm{\theta}}})}({\bm{
\mathrm{X}}}^{t+\tau}\mid{\bm{\mathrm{X}}}_{nd(\mathcal{I})}^{t+\tau}={\bm{
\mathrm{x}}}_{nd(\mathcal{I})}^{t+\tau})$.

Let us now consider the setting in which we have a bounded stochastic process $P({\bm{\mathrm{X}}}^{t},Y^{t})$, where $-k\leq X^{t}_{i}\leq k$ for some $k\in\mathbb{R}^{+}$ for all $t\in\mathbb{N}$.
If we have access to a dataset $\mathcal{D}^{t}\sim P({\bm{\mathrm{X}}}^{t},Y^{t})$ sampled from the stochastic process, we can use it to train a classifier $h^{t}$ via empirical risk minimization.
Let us consider a linear classifier $h^{t}({\bm{\mathrm{x}}})=\langle{\bm{\mathrm{\beta}}}^{t},{\bm{\mathrm{x}}}^{t}\rangle$ with bounded weights $-k\leq\beta^{t}_{i}\leq k$ e.g., trained via Bounded Least-Squares (BLS) [].
Then, given an intervention ${\bm{\mathrm{\theta}}}$, we can derive the following upper bound on the recourse instability within a time interval $(t,t+\tau)$.

###### Theorem 6 (Upper-bound invalidation rate) .

Consider a discrete-time stochastic process $P({\bm{\mathrm{X}}}^{t},Y^{t})$ and a sequence of linear classifiers $h^{t}({\bm{\mathrm{x}}}^{t})=\langle{\bm{\mathrm{\beta}}}^{t},{\bm{\mathrm{x}}
}^{t}\rangle$ approximating $P(Y^{t}\mid{\bm{\mathrm{X}}}^{t})$.
We assume $-k\leq\beta_{i},X_{i}\leq k$ for $k\in\mathbb{R}^{+}$.
The temporal invalidation rate is upper bounded as follows:

$$ $\Delta h({\bm{\mathrm{\theta}}};\tau)\leq k\sqrt{d}\cdot\mathbb{E}\left[\lVert {\bm{\mathrm{\beta}}}^{t+\tau}-{\bm{\mathrm{\beta}}}^{t}\rVert\right]+\mathbb{ E}\left[\lVert\hat{{\bm{\mathrm{x}}}}^{t+\tau}-\hat{{\bm{\mathrm{x}}}}^{t} \rVert\right]$ (7) $$

where $\lVert\cdot\rVert$ is the $\ell_{2}$-norm and the expectation is over $\mathcal{D}^{t}\sim P({\bm{\mathrm{X}}}^{t},Y^{t})$ and the training process.

Theorem 6 shows how the recourse instability is upper bounded by how much the world varies between $t$ and $t+\tau$ in terms of the data distribution $P({\bm{\mathrm{X}}}^{t})$, and the classifier.
Moreover, the size of the problem $d$ concurs by increasing the worst-case error at a sublinear rate.
The upper bound is also useful for non-linear classifiers $h$ since we can represent their decision function close to a realization ${\bm{\mathrm{x}}}^{t}$ with a local linear approximation [, ].
If our stochastic process is trend-stationary as in Example 1, we can derive the following upper bound:

###### Corollary 7 .

Consider a discrete-time trend-stationary stochastic process $P({\bm{\mathrm{X}}}^{t},Y^{t})$, where $m_{i}:\mathbb{N}\rightarrow\mathbb{R}$ represents the trend for the random variable $X_{i}$.
Let us define $m^{*}(t)=\max_{i\in[d]}m_{i}(t)$ as the largest trend for $t\in\mathbb{N}$.
Then, the recourse stability is upper bounded by:

$$ $\Delta h({\bm{\mathrm{\theta}}};\tau)\leq k\left(\sqrt{d}\cdot\mathbb{E}\left[ \lVert{\bm{\mathrm{\beta}}}^{t+\tau}-{\bm{\mathrm{\beta}}}^{t}\rVert\right]+d \cdot\left(m^{*}(t+\tau)-m^{*}(t)\right)\right)$ (8) $$

These results assume that the cost function remains constant over time. In Appendix E, we present an analogous result that applies when this is not the case, as can occur in personalized cost functions [].

Figure: Algorithm 1 T-SAR: Generate robust recourse solutions given a future time-lag $\tau$, a differentiable classifier $h$, an estimator $\tilde{P}({\bm{\mathrm{X}}}^{t})$ and a subset of intervened nodes $\mathcal{I}\subseteq[d]$.

###### Definition 4 (Temporal recourse invalidation rate) .

###### Theorem 6 (Upper-bound invalidation rate) .

###### Corollary 7 .

### 3.6 Accounting for Time in Practice

In Sections 3.2, 3.3, 3.4 and 3.5, we showed how recourse validity is hindered by the uncertainty and non-stationarity of the stochastic process.
Given a factual instance ${\bm{\mathrm{x}}}$ and a recourse ${\bm{\mathrm{\theta}}}$, Theorem 6 also implies the upper bound can grow quickly depending on the difference of the induced interventional distributions and classifier $h$ between $t$ and $t+\tau$.
Unfortunately, for any model $h$ and tolerance $\epsilon$, there can exist multiple (robust) recourses ${\bm{\mathrm{\theta}}}$ to choose from [].
Since (robust) CAR and SAR have no means to differentiate between recourses, they might end up suggesting interventions which rapidly become invalid.
An alternative is to settle for classical robust AR, which can provide some amount of safety w.r.t. time depending on the chosen epsilon $\epsilon$ (cf. Section 4). The issue with this is that, as shown by Proposition 5, choosing $\epsilon$ without considering how the world changes can be dramatically suboptimal, i.e., robust AR might recommend expensive actions that risk becoming invalid.

Luckily, for SAR, we can mitigate these issues, as long as we have access to an estimator of the stochastic process.
We present a simple algorithm (Algorithm 1) for temporal sub-population algorithmic recourse (Eq. 2) drawing inspiration from adversarially robust recourse [].
Following the results of Section 3.4, we argue that, instead of providing robust recourse for an arbitrary uncertainty set with a fixed $\epsilon$, we need to provide a robust ${\bm{\mathrm{\theta}}}$ for a forecasted region of the feature space.
We do so by extending the notion of uncertainty set $B({\bm{\mathrm{x}}}^{t};\tau)$ to consider the distribution conditioned on the observed realization, $P({\bm{\mathrm{X}}}^{t+\tau}\mid{\bm{\mathrm{X}}}^{t}={\bm{\mathrm{x}}}^{t})$, after a time lag $\tau>0$:

$$ $B({\bm{\mathrm{x}}}^{t};\tau)=\{{\bm{\mathrm{x}}}^{\prime}\sim P({\bm{\mathrm{ X}}}^{t+\tau}\mid{\bm{\mathrm{X}}}^{t}={\bm{\mathrm{x}}}^{t})\}$ (9) $$

Such a region does not depend on a fixed $\epsilon$, thus sidestepping the issue shown by Proposition 5.
Algorithm 1 assumes to have access to a constant and differentiable classifier $h$, and to an estimator $\tilde{P}({\bm{\mathrm{X}}}^{t})$ of the stochastic process.
We define $\mathrm{ER}({\bm{\mathrm{x}}},\tau;{\bm{\mathrm{\theta}}})=\mathbb{E}[h(\hat{{
\bm{\mathrm{x}}}})]$ where $\hat{{\bm{\mathrm{x}}}}$ is sampled from the interventional distribution conditioned on the non-descendant $nd(\mathcal{I})$ of the intervened upon nodes $\mathcal{I}$.
Similarly to Dominguez-Olmedo et al. [], in practice, we approximate $B({\bm{\mathrm{x}}}^{t};\tau)$ by sampling a finite number of instances from $P({\bm{\mathrm{X}}}^{t+\tau}\mid{\bm{\mathrm{X}}}^{t}={\bm{\mathrm{x}}}^{t})$.
As usual, users can control the trade-off between cost and robustness by varying $\lambda$ within the Lagrangian (line 5, Algorithm 1).

Computational complexity. The running time of Algorithm 1 depends on (i) the number of epochs $N$, and (ii) an upper bound on the number of iterations $K$ of the inner loop (lines $3$-$6$).
Considering all potential variable subsets $\mathcal{I}\subset[d]$, the complexity is $O(NK2^{d})$.
Luckily, not all features are actionable, and the general wisdom is to provide sparse solutions (e.g., by considering only $|\mathcal{I}|\leq m$ sets) so we have $O(NK\binom{d}{m})$ if $m\ll d$.
Lastly, the time-lag $\tau$ has no impact on the running time of the algorithm, but in practice, we would need to run Algorithm 1 for each $\tau$ specified by the user.

Relationship between Algorithm 1 and other causal methods.
Algorithm 1 subsumes existing causal recourse methods.
If we replace $B({\bm{\mathrm{x}}}^{t};\tau)$ with the uncertainty set in Definition 3, we obtain the robust counterfactual (CAR) or sub-population (SAR) recourse method [], depending on how we define the distribution over the expectation in $\mathrm{ER}({\bm{\mathrm{x}}},\tau;{\bm{\mathrm{\theta}}})$.
Moreover, if we consider $\mathrm{ER}({\bm{\mathrm{x}}},\tau;{\bm{\mathrm{\theta}}})=h({\bm{\mathrm{x}}}
+{\bm{\mathrm{\theta}}})$ and $B({\bm{\mathrm{x}}}^{t};\tau)=\{{\bm{\mathrm{x}}}^{t}+{\bm{\mathrm{\Delta}}}:|
|{\bm{\mathrm{\Delta}}}||\leq\epsilon\}$, we obtain (robust) non-causal recourse [].

## 4 Experiments and results

In this section, we empirically study the effect of time on recourse validity in synthetic and realistic settings taken from the literature, by comparing Algorithm 1 against several robust (non-)causal AR methods.
See Appendix B for a detailed explanation of the experimental setting and techniques.

### 4.1 Experiments with synthetic time-series

Experimental setup. First, we consider the linear and non-linear 3-variable synthetic ANMs from Karimi et al. [] representing a binary decision problem (e.g., loan granted/denied).
We adapt them to describe a trend-stationary stochastic process by adding an additive trend function $m(t)=\alpha\cdot(\beta_{l}\cdot l(t)+\beta_{s}\cdot s(t))$ to the structural equations, where $l(t)$ and $s(t)$ are the linear and seasonal components.
The parameter $\alpha\in(0,1)$ governs the strength of the trend.
We consider three types of trends: linear ($\beta_{l}>0,\beta_{s}=0$), seasonal ($\beta_{l}=0,\beta_{s}>0$) and linear+seasonal ($\beta_{l}>0,\beta_{s}>0$).
Then, we sample a time series for each ANM with 10000 individuals for $t\in[0,100]$ timesteps.
We split the time series into training (8000) and testing (2000) and train a fixed 3-layer MLP to approximate $P(Y^{t}\mid{\bm{\mathrm{X}}}^{t})$ using only the training data at time $t=0$.
We pick 250 individuals negatively classified ($h({\bm{\mathrm{x}}})<1/2$) by the MLP from the test set at time $t=0$, and we compute recourse suggestions, by considering the $\ell_{1}$-norm as a cost function, with robust counterfactual and sub-population recourse (CAR and SAR, []), robust non-causal recourse (IMF, []) and time-aware sub-population recourse (T-SAR, Algorithm 1).

Figure: Figure 3: Effect of uncertainty on counterfactual AR. Empirical average validity and standard deviation over 10 runs of robust counterfactual algorithmic recourse (CAR) at $t=50$. We vary the variance $\sigma_{U}$ of the exogenous factors of the stochastic process. Legend ($\sigma_{U}$): 0 0 $0.3$ $0.5$ $0.7$ $1.0$.
Refer to caption: x3.png

We empirically choose a smaller and larger $\epsilon\in\{3,5\}$ maximizing the robust methods’ validity at $t=0$.
To simulate the user implementing the suggested intervention at a later time, we vary the time lag $\tau$ and compute the empirical average validity (% of interventions achieving recourse) for each method at time $\tau$.
We repeat the procedure 10 times.
In these experiments, we assume to know the true causal graph and structural equations.

Uncertainty invalidates counterfactual recourse (CAR) over time.
First, we consider a stationary version of the synthetic ANMs with exogenous noise $U_{i}\sim\mathcal{N}(0,\sigma_{U})$ for all $i\in[3]$ and vary the variance of the exogenous factors $\sigma_{U}\in\{0,0.3,0.5,0.7,1.0\}$, where $\sigma_{U}=0$ means that the ANM is deterministic.
For each value of $\sigma_{U}$, we compute the recourse suggestions using robust counterfactual recourse (CAR).
Fig. 3 displays how validity decreases as variance increases (e.g., $40\%$ drop with $\sigma_{U}=1.0$), showing that the validity over time of (robust) CAR recommendations is strongly impacted by the exogenous noise, as per Proposition 1, even in an ideal case in which the SCM is stationary and known.

Incorporating time is beneficial in causal algorithmic recourse.
Fig. 4 shows how T-SAR (Algorithm 1) achieves superior validity over time than robust (non-)causal methods on the synthetic settings considering the diverse type of trends $m(t)\in\{\hbox{Linear},\hbox{Seasonal},\hbox{Linear+Seasonal}\}$.
Interestingly, robust causal recourse methods depend highly on the chosen hyperparameters ($\epsilon$, $\eta$ and $\lambda$) while T-SAR requires less tuning.
For example, both CAR and IMF show worse validity on the non-linear ANM when increasing $\epsilon$.
Lastly, in Appendix C we provide further analysis concerning the cost and sparsity of recourses hinting at a potential tradeoff between validity over time and cost.

Figure: Figure 4: Causal algorithmic recourse on diverse time series. Empirical average validity and standard error (10 runs) for the robust ($\epsilon\in\{3,5\}$) and time-aware causal recourse methods for the synthetic ANMs under different trends ($\alpha=1.0$). Legend: T-SAR CAR ($\epsilon=3$) SAR ($\epsilon=3$) IMF ($\epsilon=3$) and CAR ($\epsilon=5$) SAR ($\epsilon=5$) IMF ($\epsilon=5$).
Refer to caption: x4.png

### 4.2 Experiment with realistic time-series

In Section 4.1, we assume perfect knowledge of the causal graph and structural equations governing the stochastic process.
We now relax these assumptions by learning the structural equations in a data-driven manner, using a simple generative model, on three datasets.

Experiments setup.
We consider three real-world datasets concerning high-risk decision tasks: recidivism prediction (COMPAS []), and loan approval (Adult [] and Loan []).
They involve categorical and continuous features, some of which are not actionable (e.g., age, ethnicity, etc.).
We use the causal graphs defined by Nabi and Shpitser [] for COMPAS and Adult, and Karimi et al. [] for Loan.
We extend these datasets by adding linear+seasonal trends reflecting real-world phenomena (e.g., income can fluctuate depending on the job market or individual expenses).
Full details are available in Appendix B.
Given the ground truth SCMs, we sample an additional separate time series with 2000 individuals for $t\in[0,100]$, and we use all the samples up to $t=50$ to learn an approximate SCM for each real-world dataset.
We approximate the structural equations using a CVAE-like generative model [].
In the experiment, all methods use the same approximate SCMs to compute recourse.
Lastly, we perform the same evaluation procedure used for the synthetic experiments.

Incorporating time is beneficial also with approximate SCMs.
Fig. 5 (top) shows how T-SAR provides better recourse recommendations than the robust counterparts by exploiting an estimator $\tilde{P}({\bm{\mathrm{X}}}^{t})$.
In both Adult and Loan, T-SAR shows equal or better validity than the non-temporal methods.
For example, in Loan, T-SAR achieve almost twice the average validity ($\sim 72\%$) of the best non-temporal approach SAR ($\sim 39\%$) for $t=50$.
Understandably, T-SAR’s performance hinges on the quality of the underlying estimator.
In COMPAS, while T-SAR has good performance for $t\in[0,20]$, it gracefully degrades afterwards. This occurs because the trend estimator it relies on underestimates the trend impact on the features.
In fact, Appendix D shows that, if we employ a perfect estimator $P({\bm{\mathrm{X}}}^{t})$, T-SAR outperforms all non-temporal methods (Fig. 10).
As in Section 4.1, the non-temporal methods are sensitive to the hyperparameters, e.g., for COMPAS, CAR provides higher validity for $\epsilon=0.05$ rather than $\epsilon=0.5$, while T-SAR needs less tuning.

Accounting for time ensures more targeted interventions.
Lastly, Fig. 5 (bottom) shows how T-SAR suggests interventions counteracting the effect of the trend more effectively than non-temporal methods. We excluded COMPAS from the analysis since it has a single actionable feature.
In Loan, we have two actionable features $\{\textit{income},\textit{savings}\}$, with income subject to a trend. T-SAR provide recourse including the trend variable, while the other methods exclude it from the recommendation, thus yielding a lower validity.
In Adult, we again have two actionable features $\{\textit{education},\textit{work-hours-per-week}\}$, where work-hours-per-week is subject to a trend. In this case, T-SAR suggests acting on $\{\textit{work-hours-per-week}\}$ only. Robust sub-population methods (SAR) will instead ask the user to act on both $\{\textit{education},\textit{work-hours-per-week}\}$ because they have to robustify on both variables since they cannot forecast how they will change.
Non-causal methods (IMF) act on all actionable features but achieve a lower validity since they cannot account for trend effects.

Figure: Figure 5: Effect of time on realistic datasets. (Top) Empirical average validity and standard error (10 runs) for the robust ($\epsilon\in\{0.05,0.5\}$) and time-aware causal recourse methods for the realistic datasets under a non-linear trend. (Bottom) Distribution of the intervention sets $\mathcal{I}$ over the actionable features achieving recourse on Loan for different $t$. Legend: T-SAR CAR ($\epsilon=0.05$) SAR ($\epsilon=0.05$) IMF ($\epsilon=0.05$) and CAR ($\epsilon=0.5$) SAR ($\epsilon=0.5$) IMF ($\epsilon=0.5$).
Refer to caption: x5.png

## 5 Limitations

We now discuss some limitations of our work which open up interesting avenues for future work.

Applicability of temporal recourse. One limitation of T-SAR is that the quality of the recourse it provides hinges on the historical data the estimator is fitted on and on the predictability of the world’s evolution. Naturally, issues like concept drift [] can thwart attempts at accurately predicting the future, compromising recourse validity over time.

Causal models, trends and interventions.
Our formalization assumes the stochastic process conforms to TiMiNo [], which might not always be the case in practice.
Future work might consider non-additive structural equations and data trends.
Moreover, we focused on modelling data trends in terms of $P({\bm{\mathrm{X}}}^{t})$, whereas it would be interesting to explore trend models for the classifier $h$ or the cost function $C(\cdot)$.

Evaluation. Our experiments on synthetic and semi-synthetic datasets are sufficient to confirm that time presents a non-trivial challenge for AR and to highlight the promise of T-SAR.
However, we could not fully evaluate the effectiveness of T-SAR in real-world situations as this requires temporal datasets, which are currently not available.
The scarcity of suitable data is a well-known issue affecting the evaluation of AR approaches at large [, ].

## 6 Conclusion

We have investigated the impact of time on algorithmic recourse.
Our formalization of temporal causal recourse extends both counterfactual and sub-population causal AR by modelling the world as a (possibly non-stationary) causal stochastic process $P({\bm{\mathrm{X}}}^{t},Y^{t})$.
It allows us to theoretically demonstrate how standard and robust AR approaches are fragile, as their solutions become invalid in the presence of trends and future uncertainty. We also show that a simple algorithm, leveraging an estimator of the stochastic process fitted on historical data, can deliver more robust solutions.
Our experiments with causal and non-causal approaches support our findings.
With this work, we aim to highlight the negative impact of time on existing AR approaches while demonstrating how these challenges can be at least partially mitigated by leveraging historical data.

### Ethics Statement

Our work aims at achieving algorithmic contestability [] via actionable counterfactual explanations, enabling users to overturn decisions taken by machine learning models.
However, recourses present diverse challenges from both technical and ethical standpoints [].
For example, fairness considerations [] may arise from the applications of recourse methods, and they should be taken into consideration before considering real applications.

### Reproducibility Statement

We report all the assumptions and proofs of the theorems, corollaries and propositions in Appendices A and E, making appropriate references to the relevant sections of the main paper (e.g., Sections 3.2, 3.3, 3.4 and 3.5).
In Appendix B we describe in-depth details regarding the experimental settings, the synthetic and realistic stochastic processes, the recourse methods, the generative model to learn approximate SCMs and the training pipeline adopted.
We released the source code and the raw results under a permissive license on GitHub. They are available at the following link [https://github.com/unitn-sml/temporal-algorithmic-recourse](https://github.com/unitn-sml/temporal-algorithmic-recourse).

### Acknowledgements

The authors thank Martin Pawelczyk for the helpful feedback and discussions on an initial version of the manuscript.
The work was partially supported by the following projects: MUR PNRR project FAIR - Future AI Research (PE00000013) funded by the NextGenerationEU (AP and BL), Horizon Europe Programme, grant #101120237-ELIAS (AP and BL) and grant #101120763-TANGO (ST, AP and BL).
Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Health and Digital Executive Agency (HaDEA). Neither the European Union nor the granting authority can be held responsible for
them.

## Appendix A Proofs

### A.1 Proof of Proposition 1

###### Proof.

Consider a TiMINo stochastic process $\{{\bm{\mathrm{X}}}_{t}\}_{t\in\mathbb{N}}$ with structural equations:

$$ $X_{i}^{t}=f(\mathbf{Pa}_{i}^{t-p},\ldots,\mathbf{Pa}_{i}^{t})+U_{i}^{t},\quad U _{i}^{t}\sim\mathcal{N}(\mu_{X},\sigma_{X}),\quad\mu_{X},\sigma_{X}>0$ (10) $$

where $U_{i}^{t}$ have positive mean and variance.
We prove the proposition by contradiction by looking at the value of the time lag $\tau$.
For the sake of clarity, we state the proof for $p=1$ (the proof for $p>1$ is similar).
Assume that we observed a sequence of realizations ${\bm{\mathrm{x}}}^{t-p:t}$ and we can compute the counterfactual distribution $P^{do({\bm{\mathrm{X}}}^{t+\tau}={\bm{\mathrm{x}}}^{t+\tau}+{\bm{\mathrm{
\theta}}}),{\bm{\mathrm{X}}}^{t-p:t}={\bm{\mathrm{x}}}^{t-p:t}}({\bm{\mathrm{X
}}}^{t+\tau})$ for any $\tau\geq 0$ and ${\bm{\mathrm{\theta}}}\in\mathbb{R}^{d}$.
If $\tau=0$, we can immediately recover the value of all exogenous factors via $u_{i}^{t}=x_{i}^{t}-f(\mathbf{Pa}_{i}^{t-p},\ldots,\mathbf{Pa}_{i}^{t})$, as we know ${\bm{\mathrm{x}}}^{t-p:t}$.
Let us assume we can also recover the exogenous factors for a time lag $\tau>0$ even if we did not observe future realizations $\{{\bm{\mathrm{x}}}^{t},\ldots,{\bm{\mathrm{x}}}^{t+\tau}\}$.
Since we did not observe such realizations, the classical abduction step to recover the exogenous factors within the $[t,t+\tau]$ interval is impossible.
Recently, Bynum et al. [] introduced forward-looking counterfactuals to overcome this challenge.
They postulate we can still compute counterfactuals over unseen realizations by propagating the latest exogenous factors we were able to abduce [, Section 3].
Similary, we assume we can propagate the latest exogenous factors we can recover (${\bm{\mathrm{u}}}^{t}$) into the future, e.g., $U^{t+\tau}_{i}=u^{t}_{i}$ for any $\tau>0$ and $i\in[d]$.
Since we assume we can compute the exact counterfactual distribution, the only setting where $U^{t+\tau}_{i}=u^{t}_{i}$ holds is if $\sigma_{X}=0$ and $\mu_{X}=0$.
However, we initially stated that $\mu_{X},\sigma_{X}>0$, so we have a contradiction.
∎

###### Proof.

### A.2 Proof of Proposition 3

###### Proof.

Consider a discrete-time stationary time series $\{({\bm{\mathrm{x}}},y)^{t}\}_{t\in\mathbb{N}}$ and wlog consider a fixed linear classifier $h({\bm{\mathrm{x}}})={\bm{\mathrm{\beta}}}^{\top}{\bm{\mathrm{x}}}$ that is injective, that is, ${\bm{\mathrm{x}}}\neq{\bm{\mathrm{x}}}^{\prime}\Rightarrow h({\bm{\mathrm{x}}}
)\neq h({\bm{\mathrm{x}}}^{\prime})$.
Given a realization ${\bm{\mathrm{x}}}^{t}$, let us assume ${\bm{\mathrm{\theta}}}^{*}$ is the optimal intervention for Eq. 2 at time $t$, but not at time $t+\tau$, with $\tau\in\mathbb{N}$.
Thus, either our recourse becomes invalid or exceedingly expensive.
We focus on the former since we assume a fixed cost function such as the $\ell_{1}$-norm of the intervention $C({\bm{\mathrm{\theta}}})=\|{\bm{\mathrm{\theta}}}\|$.
As a consequence, we have $\mathbb{E}[h(\hat{{\bm{\mathrm{x}}}}^{t+\tau})-h(\hat{{\bm{\mathrm{x}}}}^{t})]\neq
0$ where $\hat{{\bm{\mathrm{x}}}}^{t+\tau}\sim P^{do({\bm{\mathrm{\theta}}}^{*})}({\bm{
\mathrm{X}}}^{t+\tau}\mid{\bm{\mathrm{X}}}_{nd(\mathcal{I})}^{t+\tau}={\bm{
\mathrm{x}}}_{nd(\mathcal{I})}^{t+\tau})$ and $\hat{{\bm{\mathrm{x}}}}^{t}\sim P^{do({\bm{\mathrm{\theta}}}^{*})}({\bm{
\mathrm{X}}}^{t}\mid{\bm{\mathrm{X}}}_{nd(\mathcal{I})}^{t}={\bm{\mathrm{x}}}_
{nd(\mathcal{I})}^{t})$.
We denote with $\mathcal{I}\subseteq[d]$ the intervention set of the successful intervention ${\bm{\mathrm{\theta}}}^{*}$, and with $do({\bm{\mathrm{\theta}}}^{*})=do({\bm{\mathrm{X}}}_{\mathcal{I}}^{t}={\bm{
\mathrm{x}}}_{\mathcal{I}}^{t}+{\bm{\mathrm{\theta}}}^{*})$ the corresponding soft intervention.
Consider the case in which our intervention does not achieve recourse after $\tau$ time steps.
We can decompose the previous expectation as follows:

$$ $\displaystyle\mathbb{E}[h(\hat{{\bm{\mathrm{x}}}}^{t+\tau})-h(\hat{{\bm{ \mathrm{x}}}}^{t})]$ $\displaystyle=\mathbb{E}[{\bm{\mathrm{\beta}}}^{\top}\hat{{\bm{\mathrm{x}}}}^{ t+\tau}-{\bm{\mathrm{\beta}}}^{\top}\hat{{\bm{\mathrm{x}}}}^{t}]$ (11) $\displaystyle={\bm{\mathrm{\beta}}}^{\top}\mathbb{E}[\tilde{{\bm{\mathrm{x}}}} ^{t+\tau}-\tilde{{\bm{\mathrm{x}}}}^{t}]$ (12) $$

Thus, since ${\bm{\mathrm{\theta}}}^{*}$ is not optimal for $t+\tau$, we must have $\mathbb{E}[\tilde{{\bm{\mathrm{x}}}}^{t+\tau}-\tilde{{\bm{\mathrm{x}}}}^{t}]\neq
0$. This, however, is a contradiction since we assume the time series is stationary.
It follows that, since $\tau$ is arbitrary, for any $t$, the corresponding optimal solution ${\bm{\mathrm{\theta}}}^{*}$ is also optimal for all $\tau>0$.
Now, this also means that ${\bm{\mathrm{\theta}}}^{*}$ is also an optimal solution for the classical recourse optimization problem Eq. 1 as long as we optimize Eq. 1 by considering $P({\bm{\mathrm{X}}},Y)=P({\bm{\mathrm{X}}}^{t},Y^{t})$ for any time steps $t\in\mathbb{N}$.
∎

###### Proof.

### A.3 Full derivations for Example 1

###### Proof.

Consider a trend-stationary stochastic process defined by these structural equations:

$$ $\displaystyle X^{t}=\alpha X^{t-1}+m(t)+U_{X}^{t},$ $\displaystyle U_{X}^{t}\sim\mathcal{N}(\mu_{X},\sigma_{X})$ (13) $\displaystyle Y^{t}=\beta X^{t}+U_{Y}^{t},$ $\displaystyle U_{Y}^{t}\sim\mathcal{N}(0,1)$ $$

for all $t\in\mathbb{N}$, $\alpha\in(0,1)$ and $\beta\in\mathbb{R}$.
The function $m(t):\mathbb{R}\rightarrow\mathbb{R}$ represents a trend independent of $X^{t}$ and $Y^{t}$.
We consider a linear trend $m(t)=-ct+U_{m}^{t}$, where $U_{m}^{t}\sim\mathcal{N}(\mu_{m},\sigma_{m})$ and $c\in\mathbb{R}^{+}$.
Given a realization $x^{t-1}$, the state of $X^{t+\tau}$ admits the closed-form expression:

$$ $\displaystyle\textstyle X^{t}$ $\displaystyle=\alpha x^{t-1}+m(t)+U^{t}_{X}$ (14) $\displaystyle X^{t+1}$ $\displaystyle=\alpha^{2}x^{t-1}+\alpha m(t)+\alpha U^{t}_{X}+m(t+1)+U^{t+1}_{X}$ (15) $\displaystyle X^{t+2}$ $\displaystyle=\alpha^{3}x^{t-1}+\alpha^{2}m(t)+\alpha^{2}U^{t}_{X}+\alpha m(t+ 1)+\alpha U^{t+1}_{X}+m(t+2)+U_{X}^{t+2}$ (16) $\displaystyle\vdots$ (17) $\displaystyle X^{t+\tau}$ $\displaystyle=\alpha^{\tau+1}x^{t-1}+\sum_{i=0}^{\tau}\alpha^{\tau-i}\left(m(t +i)+U_{X}^{t+i}\right)$ (18) $$

Hence, the expectation of $Y^{t+\tau}$ with respect to the interventional distribution $P^{do(\theta)}(X^{t},Y^{t})$ is:

$$ $\displaystyle\mathbb{E}[Y^{t+\tau}]$ $\displaystyle=\mathbb{E}[\beta X^{t+\tau}+U_{Y}^{t+\tau}]$ $\displaystyle=\beta\mathbb{E}[X^{t+\tau}]+\mathbb{E}[U_{Y}^{t+\tau}]$ $\displaystyle\textstyle\overset{(i)}{=}\beta\mathbb{E}[\alpha^{\tau+1}x^{t-1}+ \sum_{i=0}^{\tau}\alpha^{\tau-i}\left(m(t+i)+U_{X}^{t+i}\right)]$ $\displaystyle\textstyle\overset{(i)}{=}\beta\alpha^{\tau+1}x^{t-1}+\sum_{i=0}^ {\tau}\alpha^{\tau-i}\left(\mathbb{E}[m(t+i)]+\mathbb{E}[U_{X}^{t+i}]\right)$ $\displaystyle\textstyle=\beta\left(\alpha^{\tau+1}x^{t-1}+\sum_{i=0}^{\tau} \alpha^{\tau-i}(-c(t+i)+\mu_{m}+\mu_{X})\right)$ $$

Here, $(i)$ follows by construction since $\mathbb{E}[U_{Y}^{t+\tau}]=0$ for all $t$, $\tau$ and $i\in[d]$.
We now consider the following fixed classifier $\sigma(Y^{t}\mid X^{t})$ where $\sigma(x)=1/(1+e^{-x})$. Thus, the expectation over the classifier output becomes:

$$ $\textstyle\mathbb{E}[h(X^{t+\tau})]=\sigma\left(\beta\left(\alpha^{\tau+1}x^{t -1}+\sum_{i=0}^{\tau}\alpha^{\tau-i}(-c(t+i)+\mu_{m}+\mu_{X})\right)\right)$ (19) $$

Given that we are considering soft interventions, we consider the cost function $C(\hat{x}^{t+\tau},x^{t+\tau})=\hat{x}^{t+\tau}-x^{t+\tau}=\theta$ since $\hat{x}^{t+\tau}=x^{t+\tau}+\theta$.
Given that $\sigma(x)\geq 1/2$ if and only if $x\geq 0$, we have that the optimal intervention $\theta^{t+\tau}\in\mathbb{R}$ for which we have $\mathbb{E}[h(X^{t+\tau}+\theta)]\geq 1/2$ can be expressed as:

$$ $\textstyle\theta^{t+\tau}=-\alpha^{\tau+1}x^{t-1}-\sum_{i=0}^{\tau}\alpha^{ \tau-i}(-c(t+i)+\mu_{m}+\mu_{X})$ (20) $$

∎

###### Proof.

### A.4 Proof of Proposition 5

We can prove Proposition 5 by showing how we can always find a simple trend invalidating any (robust) intervention.

###### Proof.

Let us consider a trend-stationary stochastic process $P({\bm{\mathrm{X}}}^{t},Y^{t})$ and fixed injective classifier $h$ approximating $P({\bm{\mathrm{X}}}^{t}\mid Y^{t})$.
We denote with ${\bm{\mathrm{m}}}(t):\mathbb{N}^{d}\rightarrow\mathbb{R}^{d}$ the $d$-variate trend function where $m_{i}(t)$ is the trend component for a single random variable $X_{i}^{t}$ for any $i\in[d]$ and $t\in\mathbb{N}$.
Given a negatively classified instance ${\bm{\mathrm{x}}}^{t}$, assume ${\bm{\mathrm{\theta}}}$ is the optimal robust intervention for a fixed $\epsilon>0$ and for the timestep $t$.

Consider the following trend function ${\bm{\mathrm{m}}}(t)=\bm{1}\{t\geq\tau\}(-{\bm{\mathrm{\theta}}})$ which is adding the inverse of the optimal intervention if an only if $t\geq\tau$.
Specifically, we define each trend component as $m_{i}(t)=\bm{1}\{t\geq\tau\}(-\theta_{i})$.
If our stochastic process exhibits such a trend, then, for any fixed $\tau>0$, the robust intervention is invalid e.g., $\mathbb{E}[h(\hat{{\bm{\mathrm{x}}}}^{t+\tau}])]<1/2$.
Moreover, we can always build such a trend for any ${\bm{\mathrm{\theta}}}$ and any unrestricted trend-stationary stochastic process.

∎

###### Proof.

### A.5 Proof of Theorem 6

###### Proof.

We first apply the following substitutions (a) ${\bm{\mathrm{\beta}}}^{\prime}={\bm{\mathrm{\beta}}}^{t+\tau}$ and ${\bm{\mathrm{x}}}^{\prime}=\hat{{\bm{\mathrm{x}}}}^{t+\tau}$ (b) ${\bm{\mathrm{\beta}}}={\bm{\mathrm{\beta}}}^{t}$ and ${\bm{\mathrm{x}}}=\hat{{\bm{\mathrm{x}}}}^{t}$, to improve the clarity of the proof.
Then, the proof is the following:

$$ $\displaystyle\mathbb{E}[|h^{t+\tau}(\hat{{\bm{\mathrm{x}}}}^{t+\tau})-h^{t}( \hat{{\bm{\mathrm{x}}}}^{t})|]$ $\displaystyle=\mathbb{E}[\left|\langle{\bm{\mathrm{\beta}}}^{\prime},{\bm{ \mathrm{x}}}^{\prime}\rangle-\langle{\bm{\mathrm{\beta}}},{\bm{\mathrm{x}}} \rangle\right|]$ $\displaystyle=\mathbb{E}[\left|\langle{\bm{\mathrm{\beta}}}^{\prime},{\bm{ \mathrm{x}}}^{\prime}\rangle+\langle{\bm{\mathrm{\beta}}},{\bm{\mathrm{x}}}^{ \prime}\rangle-\langle{\bm{\mathrm{\beta}}},{\bm{\mathrm{x}}}^{\prime}\rangle- \langle{\bm{\mathrm{\beta}}},{\bm{\mathrm{x}}}\rangle+\langle{\bm{\mathrm{ \beta}}},{\bm{\mathrm{x}}}^{\prime}\rangle-\langle{\bm{\mathrm{\beta}}},{\bm{ \mathrm{x}}}^{\prime}\rangle\right|]$ $\displaystyle=\mathbb{E}[\left|\langle{\bm{\mathrm{\beta}}}^{\prime}-{\bm{ \mathrm{\beta}}},{\bm{\mathrm{x}}}^{\prime}\rangle+\cancel{\langle{\bm{\mathrm {\beta}}},{\bm{\mathrm{x}}}^{\prime}\rangle}+\langle{\bm{\mathrm{\beta}}},{\bm {\mathrm{x}}}^{\prime}-{\bm{\mathrm{x}}}\rangle-\cancel{\langle{\bm{\mathrm{ \beta}}},{\bm{\mathrm{x}}}^{\prime}\rangle}\right|]$ $\displaystyle\leq\mathbb{E}[\left|\langle{\bm{\mathrm{\beta}}}^{\prime}-{\bm{ \mathrm{\beta}}},{\bm{\mathrm{x}}}^{\prime}\rangle\right|]+\mathbb{E}[\left| \langle{\bm{\mathrm{\beta}}},{\bm{\mathrm{x}}}^{\prime}-{\bm{\mathrm{x}}} \rangle\right|]$ $\displaystyle\overset{(i)}{\leq}\mathbb{E}[\lVert{\bm{\mathrm{\beta}}}^{\prime }-{\bm{\mathrm{\beta}}}\rVert\cdot\lVert{\bm{\mathrm{x}}}^{\prime}\rVert]+ \mathbb{E}[\lVert{\bm{\mathrm{\beta}}}\rVert\cdot\lVert{\bm{\mathrm{x}}}^{ \prime}-{\bm{\mathrm{x}}}\rVert]$ $\displaystyle\overset{(ii)}{\leq}k\sqrt{d}\cdot\mathbb{E}[\lVert{\bm{\mathrm{ \beta}}}^{\prime}-{\bm{\mathrm{\beta}}}\rVert]+k\sqrt{d}\cdot\mathbb{E}[\lVert {\bm{\mathrm{x}}}^{\prime}-{\bm{\mathrm{x}}}\rVert]$ $\displaystyle=k\sqrt{d}\cdot\left(\mathbb{E}\left[\lVert{\bm{\mathrm{\beta}}}^ {t+\tau}-{\bm{\mathrm{\beta}}}^{t}\rVert\right]+\mathbb{E}\left[\lVert\hat{{ \bm{\mathrm{x}}}}^{t+\tau}-\hat{{\bm{\mathrm{x}}}}^{t}\rVert\right]\right)$ $$

where (i) follows from the Cauchy-Schwarz inequality and (ii) from the bounds we placed on ${\bm{\mathrm{X}}}$ and ${\bm{\mathrm{\beta}}}$ (e.g., since $-{\bm{\mathrm{k}}}\leq{\bm{\mathrm{\beta}}}\leq{\bm{\mathrm{k}}}$ and since $|{\bm{\mathrm{\beta}}}|=d$ we have $\max_{\bm{\mathrm{\beta}}}\lVert{\bm{\mathrm{\beta}}}\rVert=k\sqrt{d}$).
Moreover, since $h^{t}$ is trained over a fixed dataset $\mathcal{D}^{t}$, we have that ${\bm{\mathrm{\beta}}}^{t}\bot\;{\bm{\mathrm{X}}}^{t}\mid\mathcal{D}^{t}$ for all $t\in\mathbb{N}$. We stress that the bounds placed on ${\bm{\mathrm{X}}}$ and ${\bm{\mathrm{\beta}}}$ enable us to constrain the $\Delta h({\bm{\mathrm{\theta}}};\tau)$ variation. In the unbounded case, where $k\to\infty$, clearly no upper bound is possible.
∎

###### Proof.

### A.6 Proof of Eq. 8

We begin the proof of Eq. 8 by starting from the previous proof for Theorem 6 (given in Section A.5).
Please recall that a stochastic process $P({\bm{\mathrm{X}}}^{t})$ is trend-stationary when it can be expressed as ${\bm{\mathrm{X}}}^{t}={\bm{\mathrm{m}}}(t)+{\bm{\mathrm{e}}}^{t}$, where ${\bm{\mathrm{m}}}(t)$ is a (non-)linear trend function and ${\bm{\mathrm{e}}}^{t}$ is a stationary stochastic process.
In the following, we denote with $\tilde{{\bm{\mathrm{x}}}}$ the stationary part of the stochastic process, and we consider deterministic trend functions.

###### Proof.

Let us assume that each random variable $X^{t}_{i}$ can be described as a trend-stationary univariate stochastic process.
Thus, let us define with ${\bm{\mathrm{m}}}(t)=\{m_{i}(t)\}^{d}_{i=1}$ the trend function, where $m_{i}(t)$ the trend component for the $i$-th variable.
Then, we define as $m^{*}=m_{j}$ the trend with the largest difference $j=\operatorname*{argmax}_{i\in[d]}m_{i}(t+\tau)-m_{i}(t)$ for $t\in\mathbb{N}$ and $\tau>0$.
The derivation for the upper bound is:

$$ $\displaystyle\mathbb{E}[|h^{t+\tau}(\hat{{\bm{\mathrm{x}}}}^{t+\tau})-h^{t}( \hat{{\bm{\mathrm{x}}}}^{t})|]$ $\displaystyle\leq k\sqrt{d}\cdot\left(\mathbb{E}\left[\lVert{\bm{\mathrm{\beta }}}^{t+\tau}-{\bm{\mathrm{\beta}}}^{t}\rVert\right]+\mathbb{E}\left[\lVert\hat {{\bm{\mathrm{x}}}}^{t+\tau}-\hat{{\bm{\mathrm{x}}}}^{t}\rVert\right]\right) \quad\hbox{(\lx@cref{creftype~refnum}{theorem:invalidation-rate})}$ (21) $\displaystyle\overset{(i)}{=}k\sqrt{d}\cdot\left(\mathbb{E}\left[\lVert{\bm{ \mathrm{\beta}}}^{t+\tau}-{\bm{\mathrm{\beta}}}^{t}\rVert\right]+\mathbb{E} \left[\lVert\tilde{{\bm{\mathrm{x}}}}^{t+\tau}+{\bm{\mathrm{m}}}(t+\tau)- \tilde{{\bm{\mathrm{x}}}}^{t}-{\bm{\mathrm{m}}}(t)\rVert\right]\right)$ (22) $\displaystyle=k\sqrt{d}\cdot\left(\mathbb{E}\left[\lVert{\bm{\mathrm{\beta}}}^ {t+\tau}-{\bm{\mathrm{\beta}}}^{t}\rVert\right]+\mathbb{E}\left[\lVert\tilde{{ \bm{\mathrm{x}}}}^{t+\tau}-\tilde{{\bm{\mathrm{x}}}}^{t}\rVert\right]+\mathbb{ E}\left[\lVert{\bm{\mathrm{m}}}(t+\tau)-{\bm{\mathrm{m}}}(t)\rVert\right]\right)$ (23) $\displaystyle\overset{(ii)}{=}k\sqrt{d}\cdot\left(\mathbb{E}\left[\lVert{\bm{ \mathrm{\beta}}}^{t+\tau}-{\bm{\mathrm{\beta}}}^{t}\rVert\right]+\mathbb{E} \left[\lVert{\bm{\mathrm{m}}}(t+\tau)-{\bm{\mathrm{m}}}(t)\rVert\right]\right)$ (24) $\displaystyle=k\sqrt{d}\cdot\left(\mathbb{E}\left[\lVert{\bm{\mathrm{\beta}}}^ {t+\tau}-{\bm{\mathrm{\beta}}}^{t}\rVert\right]+\sqrt{\sum_{i=1}^{d}(m_{i}(t+ \tau)-m_{i}(t))^{2}}\right)$ (25) $\displaystyle\overset{(iii)}{\leq}k\sqrt{d}\cdot\left(\mathbb{E}\left[\lVert{ \bm{\mathrm{\beta}}}^{t+\tau}-{\bm{\mathrm{\beta}}}^{t}\rVert\right]+\sqrt{ \sum_{i=1}^{d}(m^{*}(t+\tau)-m^{*}(t))^{2}}\right)$ (26) $\displaystyle=k\sqrt{d}\cdot\left(\mathbb{E}\left[\lVert{\bm{\mathrm{\beta}}}^ {t+\tau}-{\bm{\mathrm{\beta}}}^{t}\rVert\right]+\sqrt{d(m^{*}(t+\tau)-m^{*}(t) )^{2}}\right)$ (27) $\displaystyle=k\sqrt{d}\cdot\left(\mathbb{E}\left[\lVert{\bm{\mathrm{\beta}}}^ {t+\tau}-{\bm{\mathrm{\beta}}}^{t}\rVert\right]+\sqrt{d}(m^{*}(t+\tau)-m^{*}(t ))\right)$ (28) $\displaystyle=k\sqrt{d}\cdot\mathbb{E}\left[\lVert{\bm{\mathrm{\beta}}}^{t+ \tau}-{\bm{\mathrm{\beta}}}^{t}\rVert\right]+kd\left(m^{*}(t+\tau)-m^{*}(t)\right)$ (29) $$

where $(i)$ and $(ii)$ follows from the definition of a trend-stationary stochastic process.
Then, $(iii)$ follows since we can substitute each univariate trend $m_{i}(t)$ with the maximum $m^{*}(t)$ for the time step $t$ within the $\ell_{2}$-norm.
∎

###### Proof.

## Appendix B Implementation details for the experiments with synthetic and real data

In this section, we describe the synthetic and realistic stochastic processes we used in our experiments (cf. Section 4). We also describe the training steps and generative model used to approximate the SCMs. Lastly, we report several technical implementation details.

### B.1 Synthetic additive trend function.

We want our causal stochastic process to describe an environment where the changes to obtain a positive classification fluctuate over time.
For example, as an individual ages, it will become less likely for her to repay her loan in the case of a loan application (based on the survival rate of the population).
We define an additive trend function $m(t):\mathbb{N}\rightarrow\mathbb{R}^{+}$, which is a linear combination between a linear and seasonal trend.
We control the mixture of each component with two parameters, $\beta_{l}\in\mathbb{R}^{+}$ and $\beta_{s}\in\mathbb{R}^{+}$, respectively.
We also consider an additional parameter $\alpha\in[0,1]$ controlling the trend’s strength over the stationary causal process.

$$ $m(t)=\alpha\cdot\left(\beta_{l}\cdot\min(0.05\cdot t,10)+\beta_{s}\cdot|\sin(0 .5\cdot t)|\right)$ (30) $$

In our experiments, we set $\beta_{l}\in\{0,1\}$ and $\beta_{s}\in\{0,1.5\}$ for the linear ANM, and $\beta_{l}\in\{0,2\}$ and $\beta_{s}\in\{0,5\}$ for the non-linear ANM.
For the realistic experiments, we set $\beta_{l},\beta_{s}\in\{0,1\}$ for Adult, $\beta_{l}\in\{0,0.3\}$ and $\beta_{s}\in\{0,1\}$ for COMPAS, and $\beta_{l}\in\{0,0.5\}$ and $\beta_{s}\in\{0,5\}$ for Loan.

### B.2 Causal graphs for the experiments

For the synthetic experiments, we considered the synthetic 3-variables additive noise models (ANMs) from Karimi et al. [].
We extended them by transforming them into trend-stationary stochastic processes, by adding an autoregressive component and the trend $m(t)$ on the 3rd feature.
If $\alpha=0$, both ANMs give rise to stationary time series.

Linear Additive Noise Model.

$$ $\displaystyle X^{t}_{1}=0.5\cdot X^{t-1}_{1}+U^{t}_{1}$ $\displaystyle U^{t}_{1}$ $\displaystyle\sim\mathrm{MoG}(\mathcal{N}(-1,1.5),\mathcal{N}(1,1))$ (31) $\displaystyle X^{t}_{2}=0.5\cdot X^{t-1}_{2}-0.25\cdot X^{t}_{1}+U^{t}_{2}$ $\displaystyle U_{2}^{t}$ $\displaystyle\sim\mathcal{N}(0,0.1)$ $\displaystyle X^{t}_{3}=0.5\cdot X^{t-1}_{3}+0.05\cdot X^{t}_{1}+0.25\cdot X^{ t}_{1}-m(t)+U^{t}_{3}$ $\displaystyle U^{t}_{3}$ $\displaystyle\sim\mathcal{N}(0,1)$ $$

Non-linear Additive Noise Model.

$$ $\displaystyle X^{t}_{1}=0.5\cdot X^{t-1}_{1}+U^{t}_{1}$ $\displaystyle U^{t}_{1}$ $\displaystyle\sim\mathrm{MoG}(\mathcal{N}(-2,1.5),\mathcal{N}(1,1))$ (32) $\displaystyle X^{t}_{2}=0.5\cdot X^{t-1}_{2}-1\frac{3}{1+e^{-2X^{t}_{1}}}+U^{t }_{2}$ $\displaystyle U_{2}^{t}$ $\displaystyle\sim\mathcal{N}(0,0.1)$ $\displaystyle X^{t}_{3}=0.5\cdot X^{t-1}_{3}+0.05\cdot X^{t}_{1}+0.25\cdot(X^{ t}_{1})^{2}-m(t)+U^{t}_{3}$ $\displaystyle U^{t}_{3}$ $\displaystyle\sim\mathcal{N}(0,1)$ $$

Label function.
We also consider the following conditional distribution $P(Y^{t}\mid{\bm{\mathrm{X}}}^{t})$, again taken from Karimi et al. [], which produces roughly balanced groups:

$$ $Y^{t}\sim\mathrm{Binomial}\left(1/\left(1+\mathrm{exp}(-2.5\cdot(X^{t}_{1}+X^{ t}_{2}+X^{t}_{3})/\rho)\right)\right)$ (33) $$

where $\rho$ is the empirical mean of $X^{t}_{1}+X^{t}_{2}+X^{t}_{3}$ for $t=0$.
We use the label function only to train the classifier $h$ at time $t=0$, then it is discarded and we rely only on $h$ for our experiments.

### B.3 Causal graphs for the realistic experiments

We now describe the design choices for the realistic datasets.
We tried to find a balance between realism and simplicity, to provide scenarios close to potential real-world situations, that, however, we can easily control for our experiments.
Therefore, some of the design choices might not represent faithfully how the system can evolve in real life.

Adult []. We use the features and causal graph defined by Nabi and Shpitser [].
Eq. 34 shows the full causal graph.
We have the following features: $S$ (sex), $A$ (age), $US$ (resident of the United States of America), $M$ (married), $E$ (education level) and $H$ (working hours per week).
The features $S$, $US$, and $M$ are categorical variables, the others are represented as continuous random variables.
We assume $S$, $A$, $US$ and $M$ remain fixed over time.
The only actionable features are the education level $E$, and working hours per week $H$.
We apply a decreasing trend to $H$.
We employ non-linear structural equations $f_{M}$, $f_{E}$ and $f_{H}$ by using pre-trained 3-layer MLPs, trained on the original dataset, from Dominguez-Olmedo et al. [].
Moreover, as a label function, we also employ a classifier $h$ taken by Dominguez-Olmedo et al. [] to label the examples at $t=0$.

$$ $\displaystyle S^{t}=\bm{1}\{t>0\}\cdot S^{t-1}+\bm{1}\{t=0\}\cdot U_{S}$ $\displaystyle U_{S}\sim\mathrm{Binomial}(0.9)$ (34) $\displaystyle A^{t}=\bm{1}\{t>0\}\cdot U^{t-1}+\bm{1}\{t=0\}\cdot U^{t}_{A}$ $\displaystyle U^{t}_{A}\sim\mathcal{N}(0,1)$ $\displaystyle US^{t}=\bm{1}\{t>0\}\cdot US^{t-1}+\bm{1}\{t=0\}\cdot U_{US}$ $\displaystyle U_{US}\sim\mathrm{Binomial}(0.9)$ $\displaystyle M^{t}=\bm{1}\{\sigma(f_{M}(S^{t},A^{t},US^{t}))>1/2\}$ $\displaystyle E^{t}=0.5\cdot E^{t-1}+f_{E}(S^{t},A^{t},US^{t},M^{t})+U_{E}$ $\displaystyle U_{E}\sim\mathcal{N}(0,1)$ $\displaystyle H^{t}=0.5\cdot H^{t-1}+f_{H}(S^{t},A^{t},US^{t},M^{t})-m(t)+U_{H}$ $\displaystyle U_{H}\sim\mathcal{N}(0,1)$ $$

COMPAS []. We use the features and causal graph defined by Nabi and Shpitser [].
Eq. 35 shows the full causal graph.
We have the following features: $S$ (sex), $A$ (age), $C$ (ethnicity, if caucasian or not), and $P$ (prior counts).
The feature $S$ is categorical, and the others are represented as continuous random variables.
We assume $S$, $A$, and $C$ remain fixed over time, and that the only actionable feature is the prior count $P$.
We apply an increasing trend to $P$.
As we did for Adult, we obtain the pre-trained non-linear structural equations $f_{C}$ and $f_{P}$ and label function from Dominguez-Olmedo et al. [].

$$ $\displaystyle S^{t}=\bm{1}\{t>0\}\cdot S^{t-1}+\bm{1}\{t=0\}\cdot U_{S}$ $\displaystyle U_{S}$ $\displaystyle\sim\mathrm{Binomial}(0.8)$ (35) $\displaystyle A^{t}=\bm{1}\{t>0\}\cdot U^{t-1}+\bm{1}\{t=0\}\cdot U^{t}_{A}$ $\displaystyle U^{t}_{A}$ $\displaystyle\sim\mathrm{Poisson}(1)$ $\displaystyle C^{t}=\bm{1}\{t>0\}\cdot C^{t-1}+\bm{1}\{t=0\}\cdot\left(\sigma( f_{C}(S^{t},A^{t}))+U^{t}_{C}\right)$ $\displaystyle U^{t}_{C}$ $\displaystyle\sim\mathcal{N}(0,1)$ $\displaystyle P^{t}=0.5\cdot P^{t-1}+f_{P}(S^{t},A^{t},C^{t})+m(t)+U^{t}_{P}$ $\displaystyle U^{t}_{P}$ $\displaystyle\sim\mathcal{N}(0,1)$ $$

Loan []. We use the causal graph defined by Karimi et al. [] presenting a semi-synthetic loan approval scenario inspired by the German Credit dataset [].
For the structural equations, we use the one adapted by Dominguez-Olmedo et al. [] in their paper.
Eq. 36 shows the full causal graph.
We have the following features: $G$ (gender), $A$ (age), $E$ (education level), $L$ (loan amount), $D$ (loan duration), $I$ (income) and $S$ (savings).
$G$ is a categorical variable, while the rest are considered continuous. Moreover, $G$ remains fixed over time.
We assume the only actionable features are $S$ and $I$.
We apply a trend to the income $I$.

$$ $\displaystyle G^{t}$ $\displaystyle=\bm{1}\{t>0\}\cdot G^{t-1}+\bm{1}\{t=0\}\cdot U^{t}_{G}$ $\displaystyle U^{t}_{G}$ $\displaystyle\sim\mathrm{Binomial}(0.5)$ (36) $\displaystyle A^{t}$ $\displaystyle=0.5\cdot A^{t-1}-35+U^{t}_{A}$ $\displaystyle U^{t}_{A}$ $\displaystyle\sim\text{Gamma}(10,3.5)$ $\displaystyle E^{t}$ $\displaystyle=0.5\cdot E^{t-1}-0.5+\left(1+e^{-\left(-1+0.5G^{t}+\left(1+e^{-0 .1A^{t}}\right)^{-1}+U_{E}\right)}\right)^{-1}$ $\displaystyle U_{E}$ $\displaystyle\sim\mathcal{N}(0,\sqrt{0.25})$ $\displaystyle L^{t}$ $\displaystyle=0.5\cdot L^{t-1}+1+0.01(A^{t}-5)(5-A^{t})+G^{t}+U_{L},$ $\displaystyle U_{L}$ $\displaystyle\sim\mathcal{N}(0,2)$ $\displaystyle D^{t}$ $\displaystyle=0.5\cdot D^{t-1}-1+0.1A^{t}+2G^{t}+L^{t}+U_{D}$ $\displaystyle U_{D}$ $\displaystyle\sim\mathcal{N}(0,3)$ $\displaystyle I^{t}$ $\displaystyle=0.5\cdot I^{t-1}-4+0.1(A^{t}+35)+2G^{t}+G^{t}E^{t}+U_{I}-m(t)$ $\displaystyle U_{I}$ $\displaystyle\sim\mathcal{N}(0,2)$ $\displaystyle S^{t}$ $\displaystyle=0.5\cdot S^{t-1}-4+1.5\cdot\bm{1}{\{I^{t}>0\}}\cdot I^{t}+U_{S}$ $\displaystyle U_{S}$ $\displaystyle\sim\mathcal{N}(0,5)$ $$

We sample the labels from the function defined by Karimi et al. []:

$$ $Y^{t}\sim\text{Bernoulli}\left(\left(1+e^{-0.3(-L^{t}-D^{t}+I^{t}+S^{t}+IS^{t} )}\right)^{-1}\right).$ (37) $$

### B.4 On learning an approximate SCM

We now describe the simple generative model we used in the experiment in Section 4.2.
Similarly to Karimi et al. [] and Dominguez-Olmedo et al. [], we approximate the structural equations in a data-driven manner.
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, we define the mean as the output of a regressor $f_{i}$ taking as input: the autoregressive component ${\bm{\mathrm{X}}}_{i}^{t-1}$, the parents $\mathbf{Pa}^{t}_{i}$ and the time $t$.
Thus, we obtain the following structural equations:

$$ $\displaystyle X_{i}^{t}=\mu_{i}^{t}+U^{t}_{i}\qquad U^{t}_{i}\sim\mathcal{N}(0 ,1)\quad\mu^{t}_{i}=f_{i}(X_{i}^{t-1},\mathbf{Pa}_{i}^{t},t)$ (38) $$

Similarly to a conditional VAE [], we can both sample new instances from the approximate SCMs, but we can also compute the interventional or counterfactual distributions.

### B.5 Technical details and code

We based our implementation of CAR, SAR, IMF and T-SAR following adversarial robust algorithmic recourse [].
Namely, we leveraged their implementation(^6^66[https://github.com/RicardoDominguez/AdversariallyRobustRecourse](https://github.com/RicardoDominguez/AdversariallyRobustRecourse)) and we adapted their code to work with time-based uncertainty sets (cf. Section 3.6).
Moreover, we also used their causal graph implementations, pre-trained models, and preprocessing steps as a starting point for building our stochastic processes.
In the case of the synthetic datasets, we instead looked at Karimi et al. [] original implementation(^7^77[https://github.com/charmlab/recourse](https://github.com/charmlab/recourse)).
Our code and experimental results are released on Github with a permissive license(^8^88[https://github.com/unitn-sml/temporal-algorithmic-recourse](https://github.com/unitn-sml/temporal-algorithmic-recourse)).
Lastly, we run our experiments on a Linux machine (Ubuntu 22.04, 4 LTS) with 32 CPU cores and 125 GB of RAM.
Our implementation is written in Python 3.10, using standard scientific and deep learning libraries such as numpy [] and PyTorch [].
The various hyperparameters are duly specified in the source code, but we report the most important here for clarity.

Algorithm 1 hyperparameters. We approximate $B({\bm{\mathrm{x}}}^{t};\tau)$ by sampling only 20 instances for all datasets and we set the number of epochs to $N=30$.
As a penalty, we set $\lambda=1$ for the Lagrangian (line 5, Algorithm 1).
Please notice that Dominguez-Olmedo et al. [] uses a decaying rate to reduce the impact of the cost function on the loss $\mathcal{L}$ after each epoch (we kept the original hardcoded value of $0.02$).
As learning rate, we set $\eta=0.5$ for the synthetic experiments, and $\eta=3$ for the realistic datasets. The learning rate is the same for all the methods. We did not perform a full grid search over the parameter space, since we found empirically our chosen hyperparameters were giving satisfactory performances.

Classifiers $h$. For each setting, we trained a 3-layered MLP approximating $P(Y^{t}\mid{\bm{\mathrm{X}}}^{t})$, via empirical risk minimization by sampling a given dataset for $t=0$ (cf. Section 4). We use stochastic gradient descent (SGD) to minimize the binary cross entropy loss $\mathcal{L}=-\frac{1}{N}\sum_{{\bm{\mathrm{x}}}^{0},y^{0}\in\;\hbox{batch}}(y^
{0}\log{h({\bm{\mathrm{x}}}^{0})}+(1-y^{0})\log{(1-h({\bm{\mathrm{x}}}^{0}))}$ (e.g., torch.nn.BCELoss(^9^99[https://pytorch.org/docs/stable/generated/torch.nn.BCELoss.html](https://pytorch.org/docs/stable/generated/torch.nn.BCELoss.html))) where $y^{0}$ is the ground truth label.
In our experiments, we set the batch size to $100$, the number of epochs to 15 and the learning rate to $0.001$, for all datasets.
The accuracy of the models for a single seed are: $0.847$ (Linear ANM), $0.963$ (Non-Linear ANM), $0.817$ (Adult), $0.645$ (COMPAS) and $0.842$ (Loan).

Approximate structural equations.
In our experiments, we consider only linear $f_{i}$. We train each $f_{i}$ via empirical risk minimization following the procedure outlined in Section 4.2. For each feature $i\in[d]$, and for each epoch, we consider a batch $\{(x_{i}^{t},x_{i}^{t-1},\mathbf{Pa}_{i}^{t},t)_{j}\}_{j=1}^{b}$ and we minimize the mean squared error between the ground truth $x_{i}^{t}$ and the model output $f_{i}(X_{i}^{t-1},\mathbf{Pa}_{i}^{t},t)$ with stochastic gradient descent.
We fix the batch size to 100, the learning rate to $0.001$ and the number of epochs to 15 for all settings.

## Appendix C Further analysis on the empirical cost and sparsity

In this section, we report further analysis and results when considering the empirical average cost and sparsity (# of $\mathcal{I}$ achieving recourse) of the valid interventions.
They are both common metrics in the algorithmic recourse literature [, ].

Sparsity.
Figs. 6 and 7 shows the empirical average sparsity of the causal recourse methods for both synthetic and realistic stochastic processes.
We do not report values for IMF since it always acts on all the actionable features ($|\mathcal{I}|=3$).
In Fig. 6, T-SAR presents a similar or lower sparsity than other methods. However, as Section 4.1 shows, T-SAR is the only method achieving good validity over time.
Thus, these results suggest that incorporating time might not increase the sparsity of the solutions.
In the case of approximate SCMs, Fig. 7 shows how T-SAR provides sparse interventions for Adult, but increasingly larger interventions for Loan.
COMPAS has only one actionable feature, thus the sparsity is equal for all approaches.
As highlighted in Section 4.2, T-SAR performance is also dependent on the quality of the estimator $\tilde{P}({\bm{\mathrm{X}}}^{t})$.

Cost.
Figs. 8 and 9 shows the empirical average cost for the users for which all (non-)causal recourse methods found a valid intervention.
We consider only the top-3 methods achieving recourse for each time step $t$.
In realistic and synthetic settings, T-SAR can provide cost-adaptive interventions which follow the underlying trend.
For example, we can observe this phenomenon in both COMPAS and Loan (Fig. 9).
It is also visible for $m(t)\in\{\hbox{Linear},\hbox{Linear+Seasonal}\}$ in the Non-linear and Linear ANMs, respectively.
We also notice how T-SAR seems to provide costlier recourses than the standard robust methods.
However, in Adult, T-SAR produces cheaper interventions than the other approaches.
We can explain this behaviour for Adult by looking at the analysis of the successful interventions sets $\mathcal{I}$ in Section 4.2.

In conclusion, by incorporating an estimator of the stochastic process, we can provide sparse interventions more resilient to time.
These interventions tend to be costlier and the cost varies with the time lag $\tau$ when they will be applied.
However, robust (non-)causal methods achieve dissimilar validity, thus making them not fully comparable to each other by measuring their cost.
Nevertheless, we believe the analysis has merit since it hints at a tradeoff between sparsity, cost and validity.

Figure: Figure 6: Empirical average sparsity and standard deviation of interventions achieving recourse for all causal recourse methods in the Linear (top) and Non-Linear (bottom) ANMs. We report the results for all the available trends $m(t)\in\{\hbox{Linear},\hbox{Seasonal},\hbox{Linear+Seasonal}\}$ and for some time steps $t$. Legend: T-SAR CAR ($\epsilon=3$) SAR ($\epsilon=3$) and CAR ($\epsilon=5$) SAR ($\epsilon=5$).
Refer to caption: x7.png

Figure: Figure 7: Empirical average sparsity and standard deviation of interventions achieving recourse for all causal recourse methods in the realistic datasets. We report the results for $m(t)=\hbox{Linear+Seasonal}$ and for some time steps $t$. Legend: T-SAR CAR ($\epsilon=3$) SAR ($\epsilon=3$) and CAR ($\epsilon=5$) SAR ($\epsilon=5$).
Refer to caption: x9.png

Figure: Linear
Refer to caption: x10.png

Figure: Adult
Refer to caption: x16.png

## Appendix D Further experiments with a perfect estimator P ⁢ ( 𝐗 t ) 𝑃 superscript 𝐗 𝑡 P(\mathbf{X}^{t}) italic_P ( bold_X start_POSTSUPERSCRIPT italic_t end_POSTSUPERSCRIPT )

We replicated the experiments in Section 4.2 by using instead the perfect estimator $\tilde{P}({\bm{\mathrm{X}}}^{t})=P({\bm{\mathrm{X}}}^{t})$ of the stochastic process for each dataset.
Fig. 10 shows how T-SAR offers superior performances in terms of validity than robust (non-)causal algorithmic recourse methods.
In COMPAS and Loan, T-SAR achieves now perfect validity over all time steps.
These results highlight the importance of relying on a good estimator of the stochastic process and, as outlined in Section 6, we argue it is also a mandatory requirement for realistic applications of the proposed method.

Figure: Figure 10: Effect of time on realistic datasets. Empirical average validity and standard error (10 runs) for the robust ($\epsilon\in\{0.05,0.5\}$) and time-aware causal recourse methods for the realistic datasets under a non-linear trend. Legend: T-SAR CAR ($\epsilon=0.05$) SAR ($\epsilon=0.05$) IMF ($\epsilon=0.05$) and CAR ($\epsilon=0.5$) SAR ($\epsilon=0.5$) IMF ($\epsilon=0.5$).
Refer to caption: x19.png

## Appendix E Additional theoretical results on cost stability

In this section, we provide an upper bound on the cost stability of recourse suggestions under a more expressive cost function.

Previous research has shown how providing recourse without considering the user’s preferences can lead to sub-optimal interventions [].
This is why personalized AR, in line with multi-attribute decision making [, ], models the cost function as an additive independence model $C(\hat{{\bm{\mathrm{x}}}},{\bm{\mathrm{x}}})={\bm{\mathrm{w}}}^{\top}|\hat{{
\bm{\mathrm{x}}}}-{\bm{\mathrm{x}}}|$, where the weights ${\bm{\mathrm{w}}}\in\mathbb{R}^{d}$ encapsulate the user’s preferences [, ].
We assume we can learn these weights, either from historical data, e.g., surveys and interviews [], or by interacting with the end-user [].
In the following, we explicitly consider the evolution of the user’s preferences ${\bm{\mathrm{W}}}$, as it also impacts the effectiveness of recourse, although doing so can be avoided for non-personalized AR approaches.

We assume the user preferences can be represented as a stochastic process $P({\bm{\mathrm{W}}}^{t})$.
We do not put any prior assumption on how $P({\bm{\mathrm{W}}}^{t})$ factorizes, since it is not relevant for our results. In line with previous work [], we could imagine $P({\bm{\mathrm{W}}}^{t})$ follows a causal model.
Then, we can provide the following upper bound:

###### Theorem 8 .

Consider the discrete-time stochastic processes $P({\bm{\mathrm{X}}}^{t},Y^{t})$, $P({\bm{\mathrm{W}}}^{t})$ and a parametrized cost function $C(\hat{{\bm{\mathrm{x}}}},{\bm{\mathrm{x}}};{\bm{\mathrm{w}}})=\langle|\hat{{
\bm{\mathrm{x}}}}-{\bm{\mathrm{x}}}|,{\bm{\mathrm{w}}}\rangle$ with bounded $-k\leq w_{i}^{t},X_{i}^{t}\leq k$ for $k\in\mathbb{R}^{+}$.
Given a realization ${\bm{\mathrm{x}}}^{t}$ and user’s preferences ${\bm{\mathrm{w}}}^{t}$, the variation of the cost of an intervention ${\bm{\mathrm{\theta}}}$ is upper bounded by:

$$ $\displaystyle\mathbb{E}\left[\left|C(\hat{{\bm{\mathrm{x}}}}^{t+\tau},{\bm{ \mathrm{x}}}^{t+\tau};{\bm{\mathrm{w}}}^{t+\tau})-C(\hat{{\bm{\mathrm{x}}}}^{t },{\bm{\mathrm{x}}}^{t};{\bm{\mathrm{w}}}^{t})\right|\right]$ (39) $\displaystyle\qquad\qquad\qquad\leq k\sqrt{d}\cdot\mathbb{E}\left[\lVert{\bm{ \mathrm{w}}}^{t+\tau}-{\bm{\mathrm{w}}}^{t}\rVert+\lVert|\hat{{\bm{\mathrm{x}} }}^{t+\tau}-{\bm{\mathrm{x}}}^{t+\tau}|-|\hat{{\bm{\mathrm{x}}}}^{t}-{\bm{ \mathrm{x}}}^{t}|\rVert\right]$ $$

where $\hat{{\bm{\mathrm{x}}}}^{t}\sim P^{do({\bm{\mathrm{\theta}}})}({\bm{\mathrm{X}
}}^{t}\mid{\bm{\mathrm{X}}}_{nd(\mathcal{I})}^{t}={\bm{\mathrm{x}}}_{nd(
\mathcal{I})}^{t})$ and $\hat{{\bm{\mathrm{x}}}}^{t+\tau}\sim P^{do({\bm{\mathrm{\theta}}})}({\bm{
\mathrm{X}}}^{t+\tau}\mid{\bm{\mathrm{X}}}_{nd(\mathcal{I})}^{t+\tau}={\bm{
\mathrm{x}}}_{nd(\mathcal{I})}^{t+\tau})$.

Theorem 8 shows how the recourse cost changes based on how the users’ preferences evolve, and also over the relative difference of the proposed changes given the starting value.

###### Proof.

We first apply the following substitutions (a) ${\bm{\mathrm{w}}}^{\prime}={\bm{\mathrm{w}}}^{t+\tau}$ and $\hat{{\bm{\mathrm{x}}}}^{\prime}=\hat{{\bm{\mathrm{x}}}}^{t+\tau}$ (b) ${\bm{\mathrm{x}}}^{\prime}={\bm{\mathrm{x}}}^{t+\tau}$ $\hat{{\bm{\mathrm{x}}}}^{\prime\prime}=\hat{{\bm{\mathrm{x}}}}^{t}$ (c) ${\bm{\mathrm{w}}}={\bm{\mathrm{w}}}^{t}$ and ${\bm{\mathrm{x}}}^{\prime\prime}={\bm{\mathrm{x}}}^{t}$, to improve the clarity of the proof.
Then, the proof is the following:

$$ $\displaystyle\mathbb{E}\left[\left|C({\bm{\mathrm{x}}},{\bm{\mathrm{x}}};{\bm{ \mathrm{w}}}^{\prime})-C({\bm{\mathrm{x}}},{\bm{\mathrm{x}}};{\bm{\mathrm{w}}} )\right|\right]$ $\displaystyle=\mathbb{E}\left[\left|\langle\left|{\bm{\mathrm{x}}}^{\prime}-{ \bm{\mathrm{x}}}\right|,{\bm{\mathrm{w}}}^{\prime}\rangle-\langle\left|{\bm{ \mathrm{x}}}-{\bm{\mathrm{x}}}\right|,{\bm{\mathrm{w}}}\rangle\right|\right]$ (40) $\displaystyle=\mathbb{E}\left[\left|\langle\left|\hat{{\bm{\mathrm{x}}}}^{ \prime}-{\bm{\mathrm{x}}}^{\prime}\right|-\left|\hat{{\bm{\mathrm{x}}}}^{ \prime\prime}-{\bm{\mathrm{x}}}^{\prime\prime}\right|,{\bm{\mathrm{w}}}^{ \prime}\rangle+\langle\left|{\bm{\mathrm{w}}}^{\prime}-{\bm{\mathrm{w}}}\right |,\left|\hat{{\bm{\mathrm{x}}}}^{\prime\prime}-{\bm{\mathrm{x}}}^{\prime\prime }\right|\rangle\right|\right]$ $\displaystyle\overset{(i)}{\leq}\mathbb{E}\left[\lVert\left|\hat{{\bm{\mathrm{ x}}}}^{\prime}-{\bm{\mathrm{x}}}^{\prime}\right|-\left|\hat{{\bm{\mathrm{x}}}} ^{\prime\prime}-{\bm{\mathrm{x}}}^{\prime\prime}\right|\rVert\cdot\lVert{\bm{ \mathrm{w}}}^{\prime}\rVert\right]+\mathbb{E}\left[\lVert\left|{\bm{\mathrm{w} }}^{\prime}-{\bm{\mathrm{w}}}\right|\rVert\cdot\lVert\left|\hat{{\bm{\mathrm{x }}}}^{\prime\prime}-{\bm{\mathrm{x}}}^{\prime\prime}\right|\rVert\right]$ $\displaystyle\overset{(ii)}{\leq}k\sqrt{d}\cdot\mathbb{E}\left[\lVert\left| \hat{{\bm{\mathrm{x}}}}^{\prime}-{\bm{\mathrm{x}}}^{\prime}\right|-\left|\hat{ {\bm{\mathrm{x}}}}^{\prime\prime}-{\bm{\mathrm{x}}}^{\prime\prime}\right| \rVert\right]+k\sqrt{d}\cdot\mathbb{E}\left[\lVert\left|{\bm{\mathrm{w}}}^{ \prime}-{\bm{\mathrm{w}}}\right|\rVert\right]$ $\displaystyle=k\sqrt{d}\cdot\mathbb{E}\left[\lVert\left|\hat{{\bm{\mathrm{x}}} }^{\prime}-{\bm{\mathrm{x}}}^{\prime}\right|-\left|\hat{{\bm{\mathrm{x}}}}^{ \prime\prime}-{\bm{\mathrm{x}}}^{\prime\prime}\right|\rVert+\lVert\left|{\bm{ \mathrm{w}}}^{\prime}-{\bm{\mathrm{w}}}\right|\rVert\right]$ $\displaystyle=k\sqrt{d}\cdot\mathbb{E}\left[\lVert{\bm{\mathrm{w}}}^{t+\tau}-{ \bm{\mathrm{w}}}^{t}\rVert+\lVert|\hat{{\bm{\mathrm{x}}}}^{t+\tau}-{\bm{ \mathrm{x}}}^{t+\tau}|-|\hat{{\bm{\mathrm{x}}}}^{t}-{\bm{\mathrm{x}}}^{t}| \rVert\right]$ $$

where (i) follows from the Cauchy-Schwarz inequality, and (ii) from the bounds we placed on ${\bm{\mathrm{X}}}$ and ${\bm{\mathrm{W}}}$. On the last step, we reorder the terms and we substitute the temporary variables with the original values.
∎

###### Theorem 8 .

###### Proof.

## Peer Reviews

confidence: 4
contribution: 2
initial_rating: 3
presentation: 2
questions: I hope the authors can address some of the weaknesses highlighted above
soundness: 2
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.
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).
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?

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 3
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?
soundness: 3
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.
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.
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.

---

confidence: 4
contribution: 3
initial_rating: 5
presentation: 2
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.
soundness: 2
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.
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.
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.

---

confidence: 4
contribution: 3
initial_rating: 8
presentation: 3
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?
soundness: 3
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
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.
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.

Meta-review: 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).

Decision: Reject