Perfect Counterfactuals in Imperfect Worlds: Modelling Noisy Implementation of Actions in Sequential Algorithmic Recourse

Algorithmic recourse suggests actions to individuals who have been adversely affected by automated decision-making, helping them to achieve the desired outcome. Knowing the recourse, however, does not guarantee that users can implement it perfectly, either due to environmental variability or personal choices. Recourse generation should thus anticipate its sub-optimal or noisy implementation. While several approaches construct recourse that is robust to small perturbations -- e.g., arising due to its noisy implementation -- they assume that the entire recourse is implemented in a single step, thus model the noise as one-off and uniform. But these assumptions are unrealistic since recourse often entails multiple sequential steps, which makes it harder to implement and subject to increasing noise. In this work, we consider recourse under plausible noise that adheres to the local data geometry and accumulates at every step of the way. We frame this problem as a Markov Decision Process and demonstrate that such a distribution of plausible noise satisfies the Markov property. We then propose the RObust SEquential (ROSE) recourse generator for tabular data; our method produces a series of steps leading to the desired outcome even when they are implemented imperfectly. Given plausible modelling of sub-optimal human actions and greater recourse robustness to accumulated uncertainty, ROSE provides users with a high chance of success while maintaining low recourse cost. Empirical evaluation shows that our algorithm effectively navigates the inherent trade-off between recourse robustness and cost while ensuring its sparsity and computational efficiency.