arXiv:2410.02273cs.LG2024-10中稿 · KDD被引 3

考虑行动执行中的逐步噪声,生成更可靠且低成本的分步救济方案。

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

  • 将救济过程建模为马尔可夫决策过程,模拟每步累积的局部噪声
  • 在真实数据上实现高成功率,同时保持救济路径稀疏和计算高效
  • 适合需要稳健、可执行救济建议的公平决策系统使用者

算法救济为受自动化决策负面影响的个体提供行动建议,帮助其达成期望结果。然而,用户可能无法完美执行建议,由于环境变化或个人选择,导致执行偏差。因此,救济生成应预判其非理想或有噪声的执行。现有方法虽能应对微小扰动,但假设所有动作一次性完成,噪声为单次均匀分布,这与实际不符。现实中,救济常由多步骤构成,执行难度递增,噪声逐层累积。本文提出符合局部数据几何、随步骤积累的合理噪声模型,并将其建模为马尔可夫决策过程,证明该噪声分布满足马尔可夫性质。我们提出针对表格数据的鲁棒分步(ROSE)救济生成器,生成即使在不完美执行下仍能导向目标的多步序列。实证表明,该方法在救济鲁棒性与成本间取得良好平衡,具备稀疏性与计算效率。

原文摘要 · Abstract (English)

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.

算法救济马尔可夫决策噪声建模

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。