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

• URL: http://arxiv.org/abs/2410.02273v1
• Date: Thu, 3 Oct 2024 07:47:42 GMT
• Title: Perfect Counterfactuals in Imperfect Worlds: Modelling Noisy Implementation of Actions in Sequential Algorithmic Recourse
• Authors: Yueqing Xuan, Kacper Sokol, Mark Sanderson, Jeffrey Chan,
• Abstract summary: Algorithmic recourse provides actions to individuals who have been adversely affected by automated decision-making. Knowing the recourse does not guarantee that users would implement it perfectly, either due to environmental variability or personal choices. We propose the RObust SEquential (ROSE) recourse generator to output a sequence of steps that will lead to the desired outcome even under imperfect implementation.
• Score: 26.57812122315108
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Algorithmic recourse provides actions to individuals who have been adversely affected by automated decision-making and helps them achieve a desired outcome. Knowing the recourse, however, does not guarantee that users would 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 have constructed recourse that accounts for robustness to small perturbation (i.e., noisy recourse implementation), they assume an entire recourse to be implemented in a single step and thus apply one-off uniform noise to it. Such assumption is unrealistic since recourse often includes multiple sequential steps which becomes harder to implement and subject to more noise. In this work, we consider recourse under plausible noise that adapts 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 the distribution of our plausible noise satisfies the Markov property. We then propose the RObust SEquential (ROSE) recourse generator to output a sequence of steps that will lead to the desired outcome even under imperfect implementation. Given our plausible modelling of sub-optimal human actions and greater recourse robustness to accumulated uncertainty, ROSE can grant users higher chances of success under low recourse costs. Empirical evaluation shows our algorithm manages the inherent trade-off between recourse robustness and costs more effectively while ensuring its low sparsity and fast computation.

Related papers

• Accelerated zero-order SGD under high-order smoothness and overparameterized regime [79.85163929026146]
  We present a novel gradient-free algorithm to solve convex optimization problems. Such problems are encountered in medicine, physics, and machine learning. We provide convergence guarantees for the proposed algorithm under both types of noise.
  arXiv  Detail & Related papers  (2024-11-21T10:26:17Z)
• One-step Noisy Label Mitigation [86.57572253460125]
  Mitigating the detrimental effects of noisy labels on the training process has become increasingly critical. We propose One-step Anti-Noise (OSA), a model-agnostic noisy label mitigation paradigm. We empirically demonstrate the superiority of OSA, highlighting its enhanced training robustness, improved task transferability, ease of deployment, and reduced computational costs.
  arXiv  Detail & Related papers  (2024-10-02T18:42:56Z)
• ROPO: Robust Preference Optimization for Large Language Models [59.10763211091664]
  We propose an iterative alignment approach that integrates noise-tolerance and filtering of noisy samples without the aid of external models. Experiments on three widely-used datasets with Mistral-7B and Llama-2-7B demonstrate that ROPO significantly outperforms existing preference alignment methods.
  arXiv  Detail & Related papers  (2024-04-05T13:58:51Z)
• Distributionally Robust Recourse Action [12.139222986297263]
  A recourse action aims to explain a particular algorithmic decision by showing one specific way in which the instance could be modified to receive an alternate outcome. We propose the Distributionally Robust Recourse Action (DiRRAc) framework, which generates a recourse action that has a high probability of being valid under a mixture of model shifts.
  arXiv  Detail & Related papers  (2023-02-22T08:52:01Z)
• STEEL: Singularity-aware Reinforcement Learning [14.424199399139804]
  Batch reinforcement learning (RL) aims at leveraging pre-collected data to find an optimal policy. We propose a new batch RL algorithm that allows for singularity for both state and action spaces. By leveraging the idea of pessimism and under some technical conditions, we derive a first finite-sample regret guarantee for our proposed algorithm.
  arXiv  Detail & Related papers  (2023-01-30T18:29:35Z)
• Probabilistically Robust Recourse: Navigating the Trade-offs between Costs and Robustness in Algorithmic Recourse [34.39887495671287]
  We propose an objective function which simultaneously minimizes the gap between the achieved (resulting) and desired recourse invalidation rates. We develop novel theoretical results to characterize the recourse invalidation rates corresponding to any given instance. Experimental evaluation with multiple real world datasets demonstrates the efficacy of the proposed framework.
  arXiv  Detail & Related papers  (2022-03-13T21:39:24Z)
• Sampling-Based Robust Control of Autonomous Systems with Non-Gaussian Noise [59.47042225257565]
  We present a novel planning method that does not rely on any explicit representation of the noise distributions. First, we abstract the continuous system into a discrete-state model that captures noise by probabilistic transitions between states. We capture these bounds in the transition probability intervals of a so-called interval Markov decision process (iMDP)
  arXiv  Detail & Related papers  (2021-10-25T06:18:55Z)
• Algorithmic Recourse in Partially and Fully Confounded Settings Through Bounding Counterfactual Effects [0.6299766708197883]
  Algorithmic recourse aims to provide actionable recommendations to individuals to obtain a more favourable outcome from an automated decision-making system. Existing methods compute the effect of recourse actions using a causal model learnt from data under the assumption of no hidden confounding and modelling assumptions such as additive noise. We propose an alternative approach for discrete random variables which relaxes these assumptions and allows for unobserved confounding and arbitrary structural equations.
  arXiv  Detail & Related papers  (2021-06-22T15:07:49Z)
• Square Root Principal Component Pursuit: Tuning-Free Noisy Robust Matrix Recovery [8.581512812219737]
  We propose a new framework for low-rank matrix recovery from observations corrupted with noise and outliers. Inspired by the square root Lasso, this new formulation does not require prior knowledge of the noise level. We show that a single, universal choice of the regularization parameter suffices to achieve reconstruction error proportional to the (a priori unknown) noise level.
  arXiv  Detail & Related papers  (2021-06-17T02:28:11Z)
• Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
  We investigate the active pure exploration problem in Markov Decision Processes. Agent sequentially selects actions and, from the resulting system trajectory, aims at the best as fast as possible.
  arXiv  Detail & Related papers  (2021-06-05T09:16:28Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22:24Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.