Our work addresses a fundamental problem in the context of counterfactual
inference for Markov Decision Processes (MDPs). Given an MDP path $\tau$, this
kind of inference allows us to derive counterfactual paths $\tau'$ describing
what-if versions of $\tau$ obtained under different action sequences than those
observed in $\tau$. However, as the counterfactual states and actions deviate
from the observed ones over time, the observation $\tau$ may no longer
influence the counterfactual world, meaning that the analysis is no longer
tailored to the individual observation, resulting in interventional outcomes
rather than counterfactual ones. Even though this issue specifically affects
the popular Gumbel-max structural causal model used for MDP counterfactuals, it
has remained overlooked until now. In this work, we introduce a formal
characterisation of influence based on comparing counterfactual and
interventional distributions. We devise an algorithm to construct
counterfactual models that automatically satisfy influence constraints.
Leveraging such models, we derive counterfactual policies that are not just
optimal for a given reward structure but also remain tailored to the observed
path. Even though there is an unavoidable trade-off between policy optimality
and strength of influence constraints, our experiments demonstrate that it is
possible to derive (near-)optimal policies while remaining under the influence
of the observation.

我们的工作解决了马尔可夫决策过程中反事实推断的基本问题，介绍了基于对比反事实和干预分布的影响比较的算法构建反事实模型，并推导出非最优政策以适应观察路径时的影响约束。

马尔可夫决策过程中的反事实影响

Counterfactual Influence in Markov Decision Processes

Methods to find counterfactual explanations have predominantly focused on one
step decision making processes. In this work, we initiate the development of
methods to find counterfactual explanations for decision making processes in
which multiple, dependent actions are taken sequentially over time. We start by
formally characterizing a sequence of actions and states using finite horizon
Markov decision processes and the Gumbel-Max structural causal model. Building
upon this characterization, we formally state the problem of finding
counterfactual explanations for sequential decision making processes. In our
problem formulation, the counterfactual explanation specifies an alternative
sequence of actions differing in at most k actions from the observed sequence
that could have led the observed process realization to a better outcome. Then,
we introduce a polynomial time algorithm based on dynamic programming to build
a counterfactual policy that is guaranteed to always provide the optimal
counterfactual explanation on every possible realization of the counterfactual
environment dynamics. We validate our algorithm using both synthetic and real
data from cognitive behavioral therapy and show that the counterfactual
explanations our algorithm finds can provide valuable insights to enhance
sequential decision making under uncertainty.

本文提出了一种基于马尔可夫决策过程和 Gumbel-Max 结构因果模型的动态规划算法寻找决策过程中的反事实解释来优化决策，并在认知行为治疗的合成和真实数据上进行了验证。