Counterfactual Effect Decomposition in Multi-Agent Sequential Decision Making

## Abstract

Abstract We address the challenge of explaining counterfactual outcomes in multi-agent Markov decision processes. In particular, we aim to explain the total counterfactual effect of an agent’s action on the outcome of a realized scenario through its influence on the environment dynamics and the agents’ behavior. To achieve this, we introduce a novel causal explanation formula that decomposes the counterfactual effect by attributing to each agent and state variable a score reflecting their respective contributions to the effect. First, we show that the total counterfactual effect of an agent’s action can be decomposed into two components: one measuring the effect that propagates through all subsequent agents’ actions and another related to the effect that propagates through the state transitions. Building on recent advancements in causal contribution analysis, we further decompose these two effects as follows. For the former, we consider agent-specific effects – a causal concept that quantifies the counterfactual effect of an agent’s action that propagates through a subset of agents. Based on this notion, we use Shapley value to attribute the effect to individual agents. For the latter, we consider the concept of structure-preserving interventions and attribute the effect to state variables based on their “intrinsic” contributions. Through extensive experimentation, we demonstrate the interpretability of our decomposition approach in a Gridworld environment with LLM-assisted agents and a sepsis management simulator.

## 1 Introduction

Applying counterfactual reasoning to retrospectively analyze the impact of different actions in decision making scenarios is fundamental
for accountability.
For instance, counterfactual reasoning can be employed to
identify actual causes (Halpern, ; Triantafyllou et al., ),
attribute responsibility (Chockler & Halpern, ; Friedenberg & Halpern, ),
generate explanations (Madumal et al., ; Tsirtsis et al., ),
evaluate fairness (Kusner et al., ; Huang et al., )
and measure harm (Richens et al., ; Beckers et al., ).
To achieve such objectives, many studies often rely on the notion of total counterfactual effects, which quantifies the extent to which an alternative action would have affected the outcome of a realized scenario.

In multi-agent sequential decision making, an agent’s action typically affects the outcome indirectly. To illustrate this, consider the problem of AI-assisted decision making in healthcare (Lynn, ), where a clinician and their AI assistant treat a patient over a period of time.
Fig. [1(a)](#S1.F1.sf1) depicts a specific example, where treatment fails. We estimate that if the clinician had not followed the AI’s recommendation at step $10$ and administered vasopressors (V) instead of mechanical ventilation (E), the treatment would have been successful with an $82\%$ likelihood.
Therefore, the considered alternative action admits a high total counterfactual effect.
This effect, however, propagates through all subsequent actions of the clinician and the AI, as well as all the changes in the patient’s state. This makes the interpretability of the effect more nuanced, as the change from action to outcome can be transmitted by multiple distinct causal mechanisms.
In this work, we ask:

How to explain an action’s total counterfactual effect in multi-agent sequential decision making?

Much prior work in causality has focused on decomposing causal effects (Pearl, ; Zhang & Bareinboim, ; ) under the rubric of mediation analysis (Imai et al., ; ; Hicks & Tingley, ; VanderWeele, ), which aims to understand how effects propagate through causal paths.
However, such an approach would not yield interpretability in multi-agent sequential decision making. There can be exponentially many paths connecting an action to the outcome, and not all of them have a clear operational meaning to help explain the effect intuitively.
We instead posit that it is more natural to interpret the effect of an action in terms of its influence on the agents’ behavior and the environment dynamics.
Therefore, we need to analyze how the effect propagates through: (a) the subsequent agents’ actions and (b) the state transitions of the environment.
In the previous example, the total counterfactual effect of the considered action can be decomposed as shown in Plot [1(b)](#S1.F1.sf2).
This approach explains the effect by attributing a score to each doctor (clinician and AI) and patient state, reflecting their respective contributions to the overall effect.

Figure: (a) Factual and Counterfactual Trajectory
Refer to caption: /html/2410.12539/assets/x1.png

Contributions. Focusing on Multi-Agent Markov Decision Processes and Structural Causal Models, we provide a systematic approach to attributing the total counterfactual effect of an agent’s action on the outcome of a given trajectory, based on the following bi-level decomposition.

(Level 1) We first introduce a causal explanation formula, which decomposes the total counterfactual effect of an agent’s action into the total agent-specific effect and the reverse state-specific effect.
The former refers to the effect that propagates through all subsequent agents’ actions, and is formulated via the recently introduced notion of agent-specific effects (Triantafyllou et al., ).
The latter refers to the effect that would have been lost or gained had the action not been propagated through the state transitions, and it is a special case of path-specific effects (Avin et al., ).

(Level 2a) To further decompose the total agent-specific effect (tot-ASE), we propose an axiomatic framework based on agent-specific effects for attributing the total effect to individual agents. The set of axioms includes efficiency, which requires that the agents’ contributions sum up to tot-ASE. We show how to operationalize Shapley value with agent-specific effects, in order to obtain a method for decomposing tot-ASE, which uniquely satisfies the set of proposed axioms.

(Level 2b) To further decompose the reverse state-specific effect (r-SSE), we utilize the notion of intrinsic causal contributions (ICC) (Janzing et al., ). ICC enables us to quantify the informativeness of individual state variables regarding the counterfactual outcomes needed for the computation of r-SSE. We propose a method for decomposing r-SSE that is efficient under a relatively mild assumption that at least one state variable has non-zero ICC.

We experimentally validate the interpretability of our approach using two multi-agent environments with heterogeneous agents: a grid-world environment, where two RL actors are instructed by an LLM planner to complete a sequence of tasks, and the sepsis management simulator from Fig. [1](#S1.F1).

### 1.1 Additional Related Work

This paper is related to works on mediation analysis and especially to those that consider multiple (sequentially dependent) mediators (Daniel et al., ; Steen et al., ; VanderWeele & Vansteelandt, ; Chiappa, ). As mentioned earlier, the main distinction between this line of work and ours is that we analyze how effects propagate through agents and state variables in an MMDP, instead of causal paths in general SCMs.
In a similar sense, our work also relates to the areas of causal contributions (Janzing et al., ; Jung et al., ; Heskes et al., ) and flow-based attribution methods (Singal et al., ; Wang et al., ). The former studies how to attribute a target effect to different causes (often model features) based on their degree of some notion of contribution to that effect. The latter considers the problem of assigning credit to the edges of a causal graph, instead of the nodes, for explaining causal effects.

## 2 Background and formal framework

In this section, we present our formal framework, which is adopted from Triantafyllou et al. () and builds on Multi-Agent Markov Decision Processes (MMDPs) (Boutilier, ) and Structural Causal Models (SCMs) (Pearl, ).

### 2.1 Multi-agent Markov decision processes

An MMDP is represented as a tuple $\langle\mathcal{S},\{1,...,n\},\mathcal{A},T,h,\sigma\rangle$, where: $\mathcal{S}$ is the state space; $\{1,...,n\}$ is the set of agents; $\mathcal{A}=\times_{i=1}^{n}\mathcal{A}_{i}$ is the joint action space, with $\mathcal{A}_{i}$ being the action space of agent $i$; $T:\mathcal{S}\times\mathcal{A}\times\mathcal{S}\rightarrow[0,1]$ is the transitions probability function; $h$ is the finite time horizon; $\sigma$ is the initial state distribution.(^1^11For ease of notation, rewards are considered part of the states.)
Each agent $i\in\{1,...,n\}$ has a stationary decision-making policy $\pi_{i}$, with the joint policy of all agents represented as $\pi$.
The probability of agents jointly taking action $\mathbf{a}_{t}=(a_{1,t},...,a_{n,t})$ in state $s_{t}$ at time $t$ is thus given by $\pi(\mathbf{a}_{t}|s_{t})=\pi_{1}(a_{1,t}|s_{t})\cdots\pi_{n}(a_{n,t}|s_{t})$, while the probability of transitioning from state $s_{t}$ to state $s_{t+1}$ is determined by $T(s_{t+1}|s_{t},\mathbf{a}_{t})$. A sequence of such state-action pairs $\{(s_{t},\mathbf{a}_{t})\}_{t\in\{0,...,h-1\}}$ and final state $s_{h}$ is called a trajectory. With $\tau(X)$, we denote the value of variable $X$ in trajectory $\tau$.

### 2.2 MMDPs and structural causal models

We utilize the MMDP-SCM framework (Triantafyllou et al., ) to express an MMDP coupled with a joint policy $\pi$ as an SCM.
Specifically, an MMDP-SCM $\langle\mathbf{V},\mathbf{U},P(\mathbf{u}),\mathcal{F}\rangle$ consists of

- (i)
a tuple $\mathbf{V}=\langle S_{0},A_{1,0},...,A_{n,0},...,S_{h}\rangle$ of the observed variables whose causal relations are modelled, i.e., all state and action variables of the MMDP;
- (ii)
a tuple $\mathbf{U}=\langle U^{S_{0}},U^{A_{1,0}},...,U^{A_{n,0}},...,U^{S_{h}}\rangle$ of mutually independent unobserved noise variables which capture any underlying stochasticity of the MMDP and agents’ policies;
- (iii)
A joint probability distribution $P(\mathbf{u})=\prod_{u^{i}\in\mathbf{u}}P(u^{i})$ over $\mathbf{U}$;
- (iv)
A collection $\mathcal{F}$ of deterministic functions that determine the values of all observed variables in $\mathbf{V}$ via the following structural equations
$\displaystyle S_{0}:=f^{S_{0}}(U^{S_{0}});\quad S_{t}:=f^{S_{t}}(S_{t-1},\mathbf{A}_{t-1},U^{S_{t}});\quad A_{i,t}:=f^{A_{i,t}}(S^{t},U^{A_{i,t}}).$
(1)

Note that any context $\mathbf{u}\sim P(\mathbf{u})$ induces a unique trajectory $\tau$, such that $\forall X\in\mathbf{V}$ it holds that $\tau(X)$ is the solution of $X$, for the particular $\mathbf{u}$, in the MMDP-SCM.
Furthermore, similar to general SCMs, the MMDP-SCM induces a directed causal graph, which can be found in Appendix [C](#A3).
Appendix [B](#A2) also describes the conditions under which the observational distribution of an MMDP-SCM is consistent with some MMDP and joint policy.
In this paper, we focus on categorical MMDP-SCMs.

### 2.3 Interventions and counterfactuals

Consider an MMDP-SCM $M$. An intervention on the action variable $A_{i,t}$ of $M$ corresponds to the process of modifying the structural equation $A_{i,t}:=f^{A_{i,t}}(S^{t},U^{A_{i,t}})$ from Eq. [1](#S2.E1).
More specifically, a hard intervention $do(A_{i,t}:=a_{i,t})$ fixes the value of $A_{i,t}$ to the constant $a_{i,t}$, resulting in a new MMDP-SCM denoted by $M^{do(A_{i,t}:=a_{i,t})}$. Similar to Correa et al. (), when random variables have subscripts we will use square brackets to denote interventions.

Let now $Z\in\mathbf{V}$ and $\mathbf{u}\sim P(\mathbf{u})$. We denote with $Z_{do(A_{i,t}:=a_{i,t})}(\mathbf{u})$ or $Z_{a_{i,t}}(\mathbf{u})$ for short, the solution of $Z$ for $\mathbf{u}$ in $M^{do(A_{i,t}:=a_{i,t})}$, and with $Z_{a_{i,t}}$ the random variable induced by averaging over $\mathbf{U}$. Typically, $Z_{a_{i,t}}(\mathbf{u})$ is referred to as the potential response of $Z$ to $do(A_{i,t}:=a_{i,t})$.
A natural intervention $do(A_{j,t^{\prime}}:=A_{j,t^{\prime}[a_{i,t}]})$ replaces the structural equation of $A_{j,t^{\prime}}$ in $M$ with the potential response of $A_{j,t^{\prime}}$ to the (hard) intervention $do(A_{i,t}:=a_{i,t})$.

Given a trajectory $\tau$ and a response variable $Y\in\mathbf{V}$, the counterfactual probability $P(Y_{a_{i,t}}=y|\tau)_{M}$ or $P(y_{a_{i,t}}|\tau)_{M}$ for short, measures the probability of $Y$ taking the value $y$ in $\tau$ had $A_{i,t}$ been set to $a_{i,t}$.
Subscript $M$ here implies that the probability is defined over the MMDP-SCM $M$.
We may drop the subscript when the underlying model is obvious. Next, we define a standard causal notion that is used to quantify the counterfactual impact of intervention $do(A_{i,t}:=a_{i,t})$ on $Y$.(^2^22In this paper, we consider counterfactual effects mostly relative to the factual action $\tau(A_{i,t})$. However, we note that generally any valid action can be used as a reference value.)

###### Definition 2.1 (TCFE) .

Given an MMDP-SCM $M$ and a trajectory $\tau$ of $M$, the total counterfactual effect of intervention $do(A_{i,t}:=a_{i,t})$ on $Y\in\mathbf{V}$, relative to reference $\tau(A_{i,t})$, is defined as

$$ $\displaystyle\mathrm{TCFE}_{a_{i,t},\tau(A_{i,t})}(Y|\tau)_{M}$ $\displaystyle=\mathbb{E}[Y_{a_{i,t}}|\tau]_{M}-\mathbb{E}[Y_{\tau(A_{i,t})}|\tau]_{M}$ $\displaystyle=\mathbb{E}[Y_{a_{i,t}}|\tau]_{M}-\tau(Y).$ $$

Assumptions and counterfactual identifiability. Note that there might be multiple MMDP-SCMs whose observational distribution is consistent with some MMDP-joint policy pair, but yield different counterfactuals, e.g., different values for TCFE. This means that without further assumptions, counterfactuals cannot be identified from observations alone.
To enable counterfactual identifiability, we thus make the following assumptions.
First, we consider unobserved variables to be mutually independent.
Second, we assume that MMDP-SCMs satisfy the (weak) noise monotonicity condition introduced by Triantafyllou et al. ().
Note that the latter assumption is not limiting for the MMDP distribution or the agents’ policies, i.e., every MMDP can be consistently represented by a noise-monotonic MMDP-SCM. What is restricted instead is the expressivity of the model’s counterfactual distributions.
More details about noise monotonicity can be found in Appendix [D](#A4).

###### Definition 2.1 (TCFE) .

## 3 Decomposing the total counterfactual effect

The total counterfactual effect can inform us about the extent to which an alternative action would have affected the outcome of a trajectory. However, this measure alone does not provide any further insights on why or how that action would have affected the outcome.
In this section, we introduce a novel causal explanation formula that decomposes TCFE w.r.t. the two building blocks of an MMDP – its states and its agents.
First, based on prior work we define two causal quantities for measuring how much of the total counterfactual effect of an agent’s action on some response variable is mediated by (a) all future agents’ actions and (b) the subsequent MMDP’s state transitions.

###### Definition 3.1 (tot-ASE) .

Given an MMDP-SCM $M$ and a trajectory $\tau$ of $M$, the total agent-specific effect of intervention $do(A_{i,t}:=a_{i,t})$ on $Y\in\mathbf{V}$, relative to reference $\tau(A_{i,t})$, is defined as

$$ $\displaystyle\mathrm{ASE}_{a_{i,t},\tau(A_{i,t})}^{\{1,...,n\}}(Y|\tau)_{M}$ $\displaystyle=\mathbb{E}[Y|\tau;M]_{M^{do(I)}}-\mathbb{E}[Y_{\tau(A_{i,t})}|\tau]_{M}$ $\displaystyle=\mathbb{E}[Y|\tau;M]_{M^{do(I)}}-\tau(Y),$ $$

where $I=\{A_{i^{\prime},t^{\prime}}:=A_{i^{\prime},t^{\prime}[a_{i,t}]}\}_{i^{\prime}\in\{1,...,n\},t^{\prime}>t}$.

###### Definition 3.2 (SSE) .

Given an MMDP-SCM $M$ and a trajectory $\tau$ of $M$, the state-specific effect of intervention $do(A_{i,t}:=a_{i,t})$ on $Y\in\mathbf{V}$, relative to reference $\tau(A_{i,t})$, is defined as

$$ $\displaystyle\mathrm{SSE}_{a_{i,t},\tau(A_{i,t})}(Y|\tau)_{M}$ $\displaystyle=\mathbb{E}[Y_{a_{i,t}}|\tau;M]_{M^{do(I)}}-\mathbb{E}[Y_{\tau(A_{i,t})}|\tau]_{M}$ $\displaystyle=\mathbb{E}[Y_{a_{i,t}}|\tau;M]_{M^{do(I)}}-\tau(Y),$ $$

where $I=\{A_{i^{\prime},t^{\prime}}:=A_{i^{\prime},t^{\prime}[\tau(A_{i^{\prime},t^{\prime}})]}\}_{i^{\prime}\in\{1,...,n\},t^{\prime}>t}$.

In words, Definition [3.1](#S3.Thmtheorem1) measures the difference between the factual value of $Y$, i.e., $\tau(Y)$, and the (expected) counterfactual value of $Y$ had all agents taken the actions that they would naturally take under intervention $do(A_{i,t}:=a_{i,t})$ after time-step $t$.
On the other hand, Definition [3.2](#S3.Thmtheorem2) measures the counterfactual effect of intervention $do(A_{i,t}:=a_{i,t})$ on $Y$ in a modified model where all subsequent agents’ actions are fixed to their factual values, i.e., their actions in $\tau$.
Definition [3.1](#S3.Thmtheorem1) is in line with the notion of agent-specific effects introduced by Triantafyllou et al. () and revisited here in Section [5](#S5), while SSE can be seen as a special case of path-specific effects (Avin et al., ).

Perhaps counter to intuition, TCFE is not always decomposed into tot-ASE and SSE, i.e., the relationship $\mathrm{TCFE}_{a_{i,t},\tau(A_{i,t})}(Y|\tau)_{M}=\mathrm{ASE}_{a_{i,t},\tau(A_{i,t})}^{\{1,...,n\}}(Y|\tau)_{M}+\mathrm{SSE}_{a_{i,t},\tau(A_{i,t})}(Y|\tau)_{M}$ is not necessarily true. An empirical counter-example for this is provided in Section [6.1](#S6.SS1).
However, by comparing Definitions [3.1](#S3.Thmtheorem1) and [3.2](#S3.Thmtheorem2), we observe that the total agent-specific effect associated with the transition from the factual action $\tau(A_{i,t})$ to the counterfactual action $a_{i,t}$ is closely related to the state-specific effect associated with the reverse transition, i.e., the effect

$$ $\displaystyle\mathrm{SSE}_{\tau(A_{i,t}),a_{i,t}}(Y|\tau)_{M}$ $\displaystyle=\mathbb{E}[Y_{\tau(A_{i,t})}|\tau;M]_{M^{do(I)}}-\mathbb{E}[Y_{a_{i,t}}|\tau]_{M}$ $\displaystyle=\mathbb{E}[Y|\tau;M]_{M^{do(I)}}-\mathbb{E}[Y_{a_{i,t}}|\tau]_{M},$ (2) $$

where $I=\{A_{i^{\prime},t^{\prime}}:=A_{i^{\prime},t^{\prime}[a_{i,t}]}\}_{i^{\prime}\in\{1,...,n\},t^{\prime}>t}$.
We will refer to the latter as the reverse state-specific effect or r-SSE for short, to clearly distinguish it from SSE.
In words, r-SSE measures the difference in the counterfactual value of $Y$ under intervention $do(A_{i,t}:=a_{i,t})$, assuming that the state $S_{t+1}$ had not been affected by the intervention, but all subsequent agents’ actions had.
Based on this observation, we derive the following decomposition of the total counterfactual effect.

###### Theorem 3.3 .

The total counterfactual effect, total agent-specific effect and reverse state-specific effect obey the following relationship

$$ $\displaystyle\mathrm{TCFE}_{a_{i,t},\tau(A_{i,t})}(Y|\tau)_{M}=\mathrm{ASE}_{a_{i,t},\tau(A_{i,t})}^{\{1,...,n\}}(Y|\tau)_{M}-\mathrm{SSE}_{\tau(A_{i,t}),a_{i,t}}(Y|\tau)_{M}.$ (3) $$

Theorem [3.3](#S3.Thmtheorem3) states that the total counterfactual effect of $do(A_{i,t}:=a_{i,t})$ on $Y$ equals to the effect that propagates only through the agents minus the effect that would have been lost or gained had the intervention not been propagated through the states.

Connection to prior work.
Our result is similar in principle with the well-known causal mediation formula for arbitrary SCMs (Pearl, ), which decomposes the total causal effect of an intervention into the natural direct and indirect effects.
Thus, Theorem [3.3](#S3.Thmtheorem3) can be viewed as an extension of Theorem $3$ from Pearl (), applied to the problem of counterfactual effect decomposition in multi-agent MDPs.
More details on the interpretation of this result can be found in Pearl ().

Sepsis example. Going back to our example scenario from the introduction, the result of our decomposition can be interpreted as follows: (a) $45.6\%$ of the TCFE is attributed to how the AI and the clinician would have responded to the intervention; (b) the rest $54.4\%$ is attributed to the (direct) influence that the intervention has on the patient state.

###### Definition 3.1 (tot-ASE) .

###### Definition 3.2 (SSE) .

###### Theorem 3.3 .

## 4 Decomposing the reverse state-specific effect

In this section, we focus on further decomposing the reverse state-specific effect. More specifically, our goal is to attribute to each state variable a score reflecting its contribution to r-SSE.
Our approach utilizes the notion of intrinsic causal contributions (ICC) introduced by Janzing et al. ().
For general SCMs, the ICC of an observed variable $X$ to a target variable $Y$ measures the reduction of uncertainty in $Y$ when conditioning on the noise variable $U^{X}$.
In our work, we model uncertainty using the expected conditional variance and modify the ICC definition to quantify the influence of state variables on the variation of r-SSE.

Let $k\in\{0,...,h\}$. We denote with $\mathbf{U}^{S_{k}}$ the set $\langle U^{S_{k}},U^{A_{1,k}},...,U^{A_{n,k}}\rangle$ for $k<h$, and with $\mathbf{U}^{S_{h}}$ the set $\langle U^{S_{h}}\rangle$. We also denote with $\mathbf{U}^{<S_{k}}$ the set of noise terms associated with the observed variables preceding (chronologically) $S_{k}$.
Note that r-SSE essentially measures the expected value of the difference $\Delta Y_{I,a_{i,t}}=Y_{I}-Y_{a_{i,t}}$ in $M$, when noise terms $\mathbf{U}$ are sampled from the posterior distribution $P(\mathbf{u}|\tau)$.
Thus, the ICC can be defined in our context as follows

$$ $\displaystyle\mathrm{ICC}(S_{k}\rightarrow\Delta Y_{I,a_{i,t}}|\tau)=\mathbb{E}[\mathrm{Var}(\Delta Y_{I,a_{i,t}}|\tau,\mathbf{U}^{<S_{k}})|\tau]-\mathbb{E}[\mathrm{Var}(\Delta Y_{I,a_{i,t}}|\tau,\mathbf{U}^{<S_{k}},\mathbf{U}^{S_{k}})|\tau],$ (4) $$

where $I=\{A_{i^{\prime},t^{\prime}}:=A_{i^{\prime},t^{\prime}[a_{i,t}]}\}_{i^{\prime}\in\{1,...,n\},t^{\prime}>t}$.
In words,
Eq. [4](#S4.E4) measures the reduction of variance in $\Delta Y_{I,a_{i,t}}$ caused by conditioning on the noise variables associated with state $S_{k}$ and the agents’ actions taken therein.
Based on this, we can now define our attribution method for r-SSE.

###### Definition 4.1 (r-SSE-ICC) .

Given an MMDP-SCM $M$ and a trajectory $\tau$ of $M$, r-SSE-ICC assigns to each state variable $S_{k}$ for $k\in\{0,...,h\}$ a contribution score for
the reverse state-specific effect $\mathrm{SSE}_{\tau(A_{i,t}),a_{i,t}}(Y|\tau)_{M}$, equal to

$$ $\displaystyle\psi_{S_{k}}:=\frac{\mathrm{ICC}(S_{k}\rightarrow\Delta Y_{I,a_{i,t}}|\tau)_{M}}{\mathrm{Var}(\Delta Y_{I,a_{i,t}}|\tau)}\cdot\mathrm{SSE}_{\tau(A_{i,t}),a_{i,t}}(Y|\tau)_{M},$ $$

if the unconditional variance $\mathrm{Var}(\Delta Y_{I,a_{i,t}}|\tau)>0$, and equal to 0 0 otherwise.

According to Definition [4.1](#S4.Thmtheorem1), the reverse state-specific effect is allocated among state variables in proportion to their intrinsic contribution to the effect.
Intuitively, this means that the influence of a state variable to the r-SSE is represented by the relative degree to which we can more precisely estimate the effect if we could also predict the counterfactual value of that state under the interventions $do(I)$ and $do(A_{i,t}:=a_{i,t})$.
Thus, if knowing what would have happened in state $S_{k}$ is pivotal for the accuracy of our counterfactual prediction then contribution score $\psi_{S_{k}}$ would be high, whereas if it has small influence then $\psi_{S_{k}}$ would be closer to zero.
In the case where we can exactly compute $\mathrm{SSE}_{\tau(A_{i,t}),a_{i,t}}(Y|\tau)_{M}$ without conditioning on any noise term, e.g., if environment and policies are deterministic, then our approach does not decompose the r-SSE any further.

Algorithm. Appendix [F](#A6) includes an algorithm for the approximation of the expected conditional variance of $\Delta Y_{I,a_{i,t}}$.
Our algorithm follows the standard abduction-action-prediction methodology for counterfactual inference (Pearl, ): it samples conditioning and non-conditioning noise variables independently from the posterior distribution,
estimates the noise-conditional variance for r-SSE and returns the average value.

Causal interpretation. The attribution method described in Definition [4.1](#S4.Thmtheorem1) relies on do interventions that are performed only on agents’ actions, meaning that the causal mechanisms of the environment remain intact.
Conditioning on noise terms can be considered as a form of structure-preserving interventions, i.e., interventions that depend on the values of the parents of the exposure variable (here previous state and actions), and do not perturb the observed distribution. For a more detailed discussion on the causal meaning of ICC we refer the reader to Section $3.1$ in Janzing et al. ().

Plain ICC. Since there is a unique causal order among the state variables of an MMDP-SCM, the time order, there is no arbitrariness due to order-dependence. For that reason, we consider the “plain” ICC for our approach instead of the Shapley based symmeterization used in Janzing et al. ().

Finally, we show that r-SSE-ICC fully allocates r-SSE among the states following the intervention.

###### Theorem 4.2 .

Let $t_{Y}$ denote the time-step of response variable $Y$ and $\psi$ be the output of $\mathrm{r\text{-}SSE\text{-}ICC}$ for the reverse state-specific effect $\mathrm{SSE}_{\tau(A_{i,t}),a_{i,t}}(Y|\tau)_{M}$. If $\mathrm{Var}(\Delta Y_{I,a_{i,t}}|\tau)>0$, then it holds that $\sum_{k\in[t+1,t_{Y}]}\psi_{S_{k}}=\mathrm{SSE}_{\tau(A_{i,t}),a_{i,t}}(Y|\tau)_{M}$.

Sepsis example. The result of the r-SSE-ICC method in the introductory example can be interpreted as follows: if we knew the counterfactual state of the patient at step $13$, following the intervention at step $10$, we could estimate the reverse state-specific effect of that intervention on the treatment with almost no uncertainty.
On the other hand, knowing the exact counterfactual value for any of the previous states would not lead to a comparable reduction in uncertainty.

###### Definition 4.1 (r-SSE-ICC) .

###### Theorem 4.2 .

## 5 Decomposing the total agent-specific effect

In this section, we focus on further decomposing the total agent-specific effect.
More specifically, our goal is to attribute to each agent a score reflecting its contribution to tot-ASE. Our approach is based on a well-established solution concept in cooperative game theory, the Shapley value (Shapley, ), and it utilizes the notion of agent-specific effects introduced by Triantafyllou et al. ().

###### Definition 5.1 (ASE) .

Given an MMDP-SCM $M$, a non-empty subset of agents $\mathbf{N}$ in $M$ and a trajectory $\tau$ of $M$, the $\mathbf{N}$-specific effect of intervention $do(A_{i,t}:=a_{i,t})$ on $Y\in\mathbf{V}$, relative to reference $\tau(A_{i,t})$, is defined as

$$ $\displaystyle\mathrm{ASE}^{\mathbf{N}}_{a_{i,t},\tau(A_{i,t})}(Y|\tau)_{M}$ $\displaystyle=\mathbb{E}[Y|\tau;M]_{M^{do(I)}}-\mathbb{E}[Y_{\tau(A_{i,t})}|\tau]_{M}$ $\displaystyle=\mathbb{E}[Y|\tau;M]_{M^{do(I)}}-\tau(Y),$ $$

where $I=\{A_{i^{\prime},t^{\prime}}:=\tau(A_{i^{\prime},t^{\prime}})\}_{i^{\prime}\notin\mathbf{N},t^{\prime}>t}\cup\{A_{i^{\prime},t^{\prime}}:=A_{i^{\prime},t^{\prime}[a_{i,t}]}\}_{i^{\prime}\in\mathbf{N},t^{\prime}>t}\}$.

In contrast to the total ASE, the $\mathbf{N}$-specific effect quantifies the counterfactual effect of an intervention that propagates only through a subset of agents in the system, the effect agents, instead of all agents.
Compared to Definition [3.1](#S3.Thmtheorem1), here the actions of the non-effect agents are set to their factual values.
In the context of agent-specific effects studied here, Shapley value can be defined as follows.

###### Definition 5.2 (ASE-SV) .

Given an MMDP-SCM $M$ and a trajectory $\tau$ of $M$, ASE-SV assigns to each agent $j\in\{1,...,n\}$ a contribution score for the total agent-specific effect
$\mathrm{ASE}_{a_{i,t},\tau(A_{i,t})}^{\{1,...,n\}}(Y|\tau)_{M}$, equal to

$$ $\displaystyle\phi_{j}:=\sum_{S\subseteq\{1,...,n\}\backslash\{j\}}w_{S}\cdot\big{[}\mathrm{ASE}^{S\cup\{j\}}_{a_{i,t},\tau(A_{i,t})}(Y|\tau)_{M}-\mathrm{ASE}^{S}_{a_{i,t},\tau(A_{i,t})}(Y|\tau)_{M}\big{]},$ $$

where coefficients $w_{S}$ are set to $w_{S}=\frac{|S|!(n-|S|-1)!}{n!}$.

Next, we define a number of desirable properties for the attribution of the total agent-specific effect. These properties are inspired from the game theory literature (Jain & Mahdian, ; Shoham & Leyton-Brown, ; Young, ) and translated to our setting.

Efficiency: The total sum of agents’ contribution scores is equal to tot-ASE.

Invariance: Agents who do not contribute to tot-ASE are assigned a zero contribution score.

Symmetry: Agents who contribute equally to tot-ASE are assigned the same contribution score.

Contribution monotonicity: The contribution score assigned to an agent depends only on its marginal contributions to tot-ASE and monotonically so.

We formally state these properties in Appendix [E](#A5).
We now restate in the setting of agent-specific effects studied here an existing uniqueness result for Shapley value.

###### Theorem 5.3 .

Young ()
$\mathrm{ASE\text{-}SV}$ is a unique attribution method for the total agent-specific effect that satisfies efficiency, invariance, symmetry and contribution monotonicity.

Sepsis example. The ASE-SV method in this example attributes the total agent-specific effect to both the AI agent and the clinician.
As illustrated in Plot [1(b)](#S1.F1.sf2), a larger portion of the effect is attributed to how the AI would have responded to the intervention.

###### Definition 5.1 (ASE) .

###### Definition 5.2 (ASE-SV) .

###### Theorem 5.3 .

## 6 Experiments

In this section, we empirically evaluate our approach to counterfactual effect decomposition using two environments, Gridworld and Sepsis.
We refer the reader to Appendix [I](#A9) for more details on our experimental setup and implementation, and to Appendix [J](#A10) for additional results.(^3^33Code to reproduce our experiments is available at [https://github.com/stelios30/cf-effect-decomposition.git](https://github.com/stelios30/cf-effect-decomposition.git).)
Throughout both experiments, we use $100$ posterior samples for estimating counterfactual effects. For the r-SSE-ICC method, we use $20$ additional samples for the conditioning noise variables.

### 6.1 Gridworld experiments with LLM-assisted RL agents

Figure: (a) Factual and Counterfactual Trajectory
Refer to caption: /html/2410.12539/assets/x3.png

Environment. We consider the gridworld depicted in Fig. [2(a)](#S6.F2.sf1), where two actors, $\mathcal{A}_{1}$ and $\mathcal{A}_{2}$, are tasked with delivering objects.
In the beginning of each trajectory, two randomly sampled objects spawn in each of the boxes located on the rightmost corners of the gridworld.
The color of each object determines its value.
Colored cells indicate areas of large stochastic penalty, which is significantly reduced when actors carry an object of a matching color.
Cells denoted with stars are delivery locations. If an object is delivered to the location with the matching color, then its value is rewarded.

Implementation. We adopt a Planner-Actor-Reporter system akin to Dasgupta et al. ().
Planner is implemented using a pre-trained LLM and few-shot learning, to provide actors with instructions. More specifically, Planner can instruct actors to: examine a box, pickup an object and deliver that object to a specific destination.
Furthermore, we assume an optimal Reporter whose task is to report to Planner the necessary information about the state of the environment. In particular, Reporter provides information about the boxes’ contents and which objects were picked up by the actors.
Finally, the two actors are trained with deep RL to follow the Planner’s instructions.

Setup. For our demonstration purposes, we consider the (factual) trajectory illustrated in Fig. [2(a)](#S6.F2.sf1). We intervene on the pickup action of actor $\mathcal{A}_{2}$ forcing it to disobey Planner and choose the green object. The resulting counterfactual trajectory can be seen in Fig. [2(a)](#S6.F2.sf1) as well. Additional results from a second experiment, where we intervene on the Planner’s action, can be found in Appendix [J.1](#A10.SS1).

Counterfactual effects. To measure the total counterfactual effect in this scenario, we estimate the value of the total reward collected in the counterfactual trajectory, and subtract from it the observed return.
For the total agent-specific effect (Definition [3.1](#S3.Thmtheorem1)), we need to isolate the effect of the intervention that propagates only through the agents ($\mathcal{A}_{1}$, $\mathcal{A}_{2}$ and Planner). Compared to TCFE, we thus estimate the return of the counterfactual trajectory in which the stochastic penalties are realized as if $\mathcal{A}_{2}$ carries the pink object.
For the state-specific effect (Definition [3.2](#S3.Thmtheorem2)), we have to isolate the effect of the intervention that propagates only through the states. Therefore, we estimate the return of the counterfactual trajectory in which agents take their factual actions, but stochastic penalties are realized as if $\mathcal{A}_{2}$ carries the green object.
For the reverse SSE (Eq. [3](#S3.Ex7)), it suffices to compute the difference between the returns of the counterfactual trajectories considered for tot-ASE and TCFE.

Causal explanation formula. Plot [2(b)](#S6.F2.sf2) indicates that indeed TCFE is not decomposed into tot-ASE and SSE. Theorem [3.3](#S3.Thmtheorem3), on the other hand, is empirically validated in this scenario.

ASE-SV. According to Plot [2(b)](#S6.F2.sf2), the ASE-SV attributes zero scores to both $\mathcal{A}_{1}$ and Planner, while assigning the full tot-ASE to $\mathcal{A}_{2}$. $\mathcal{A}_{1}$’s lack of contribution to the effect is due to its unresponsiveness to $\mathcal{A}_{2}$’s actions. Although the Planner does respond to $\mathcal{A}_{2}$, it is unable to directly influence the environment’s state. As a result, the effect of our intervention on the total reward does not propagate through the Planner’s actions. These represent two distinct mechanisms by which agents can be excluded from contributing to the total agent-specific effect.

r-SSE-ICC. Plot [2(c)](#S6.F2.sf3) shows that r-SSE-ICC pinpoints four state variables with non-zero contributions to the reverse state-specific effect. As expected, the time-steps of these variables coincide with the time-steps at which $\mathcal{A}_{2}$ traverses the colored cells in the counterfactual trajectory, as these are the only sources of stochasticity in the environment.
Moreover, we observe that the scores attributed to the four states decrease over time. Since penalties are sampled independently, this can be interpreted as follows: the uncertainty over the counterfactual penalty estimates is greater in earlier time-steps.
The latter can be confirmed by comparing the penalty distributions from Table [1](#A9.T1) in Appendix [I](#A9).

### 6.2 Experiments on sepsis

Figure: (a) Decomposition: AI
Refer to caption: /html/2410.12539/assets/x6.png

Environment. The two-agent variant of the sepsis treatment setting (Triantafyllou et al., ) we consider here involves a clinician and an AI agent who take sequential actions in a turn-based manner for treating an ICU patient.
At each round, the AI recommends one of $8$ possible treatments, which is then reviewed and potentially overridden by the clinician. The likelihood of the clinician overriding the AI’s treatment at any given state is modeled by a parameter $\mu$, which is varied in our experiment. Intuitively, $\mu$ serves as a proxy for the clinician’s level of trust in the AI’s recommendations: higher values of $\mu$ correspond to greater levels of trust.
If the AI’s action is not overridden, then its selected treatment is applied. Otherwise, a new treatment selected by the clinician is applied instead.
The outcome of a trajectory is deemed successful if the patient is kept alive for $20$ rounds or an earlier discharge is achieved.

Evaluation of ASE-SV. We generate $600$ trajectories with unsuccessful outcomes. We then measure the total counterfactual effect of all possible alternative actions on the final state of these trajectories and keep those that exhibit $\text{TCFE}\geq 0.8$. Through that process, $8728$ alternative actions are selected for the evaluation of ASE-SV.
For all selected actions, we compute their total agent-specific effect, clinician-specific effect and AI-specific effect. As expected, the sum of the two individual effects does not equal the total one, with discrepancies of up to $95\%$.
In contrast, in our experiments, ASE-SV always attributes the effect efficiently to the clinician and AI, as supported by Theorem [5.3](#S5.Thmtheorem3).

Plots [3(a)](#S6.F3.sf1) and [3(b)](#S6.F3.sf2) show the average percentage composition of the reverse state-specific effect and the agent scores attributed by ASE-SV w.r.t. the total counterfactual effect, for different trust levels. Plot [3(a)](#S6.F3.sf1) (resp. Plot [3(b)](#S6.F3.sf2)) considers the average over all selected AI (resp. clinician) actions.
Results reveal that our method demonstrates a trend similar to the one described in Triantafyllou et al. (). In particular, the amount of tot-ASE attributed to the clinician (resp. AI) decreases (resp. increases) as the level of trust rises, eventually reaching zero (resp. full) when the clinician completely trusts the AI’s recommendations.
This observation is intuitive, since the clinician is expected to contribute less to the effect as it acts more infrequently in the environment, while at the same time the AI is expected to contribute more as it assumes greater agency.
Thus, we conclude that ASE-SV can efficiently attribute tot-ASE without sacrificing the conceptual power of agent-specific effects.

Evaluation of r-SSE-ICC. We consider the same setup as before and categorize all selected actions based on the difference between the round that they were taken and the final round of their respective trajectory. For instance, if the action we consider was taken by the AI at the third round of a trajectory with $8$ rounds in total then the round difference for that action is $5$.
For our analysis, we maintain actions with round difference between $4$ and $10$. For all selected actions, we compute their reverse state-specific effect together with its variance. We keep those with absolute r-SSE $\geq 0.1$ and variance $\geq 0.01$, which yields a total of $437$ alternative actions for the evaluation of r-SSE-ICC.

For each selected action and its reverse state-specific effect, we compute the contribution scores assigned to all state variables by the r-SSE-ICC method.
We are interested in seeing how spread the scores are across the states, i.e., if our method attributes the effect equally or if it assigns larger scores to few states.
To achieve this, we depict the Gini coefficient distribution (Gini, ) of these scores for various round differences in Plot [3(c)](#S6.F3.sf3).(^4^44In measuring the Gini coefficient we consider only the state variables that follow the intervention. These are the only states that can be attributed a non-zero contribution by r-SSE-ICC, according to Theorem [4.2](#S4.Thmtheorem2).)
Our results indicate that, independently of the trajectory size, r-SSE-ICC pinpoints for most trajectories only a small subset of state variables with significant (intrinsic) contribution to the reverse state-specific effect.
In practice, this means that for this setting we actually need to infer the counterfactual values of only a few key states in each trajectory in order to accurately estimate r-SSE.
This is an interesting observation, as it implies that given a set of trajectories, r-SSE-ICC can reveal aspects of the underlying counterfactual distribution.

## 7 Discussion

In this paper, we introduce a causal explanation framework tailored to multi-agent MDPs. Specifically, we decompose the total counterfactual effect of an agent’s action by attributing it to the agents’ behavior or environment dynamics.
Our experimental results demonstrate that our decomposition provides valuable insights into the distinct roles that agents and environment play in influencing the effect.
To the best of our knowledge, this is the first work
that looks into the problem of counterfactual effect decomposition in the context of multi-agent sequential decision making.
While our findings are promising, there are several directions for future exploration, which we outline below.

Computational complexity. The computational complexity of our decomposition approach depends on the total number of agents and the length of the MMDP’s time horizon.
In our experiments, we use a relatively small number of agents and a horizon of a few dozen time-steps. We believe that many interesting multi-agent settings belong to this regime, e.g., human-AI collaboration. Nevertheless, there are settings in which computational complexity considerations can be important, and we see this as an interesting future research direction to explore.
In Appendix [H](#A8), we analyze the computational complexity of the ASE-SV and r-SSE-ICC methods, and discuss some potential mitigation strategies for when the number of agents or the time horizon are prohibitively large.

Causal assumptions. Making causal assumptions in order to enable counterfactual identifiability is quite common in the literature. There is a plethora of works at the intersection of decision making and counterfactual reasoning that assumes exogeneity alongside additional causal properties, such as weak (Triantafyllou et al., ) or strong (Tsirtsis & Rodriguez, ) noise monotonicity, counterfactual stability (Oberst & Sontag, ), or access to the ground-truth causal model (Richens et al., ).
However, these assumptions are often violated in practice. Thus, extending the applicability of our proposed approach to domains where our theoretical assumptions (exogeneity and weak noise monotonicity) do not hold would be of significant practical importance.

Applications to accountable decision making. We deem the problem of decomposing counterfactual effects particularly relevant for multi-agent decision-making settings where accountability is paramount.
Our approach can be applied in these settings, by integrating it into existing causal tools for retrospectively analyzing decision-making failures.
For instance, consider methods for blame attribution in multi-agent systems (Halpern & Kleiman-Weiner, ; Friedenberg & Halpern, ). Typically, these methods first identify the agents’ actions that were critical to the outcome, i.e., those that, had they been different, would have likely prevented failure. Next, they assess the agents’ epistemic states, determining to what extent each agent could or should have predicted the consequences of acting differently.
Our approach can enhance these methods by offering a more granular notion of blame.
In the Sepsis scenario described in Section [1](#S1), for example, the clinician may be expected to predict how their actions directly affect the patient’s state, but may not be expected to predict the AI’s responses, especially if they have never worked with the current version of the model before. According to the output of our decomposition approach (Plot [1(b)](#S1.F1.sf2)), the clinician would then receive $73.5\%$ of the total blame for their action, rather than bearing full responsibility. We see significant potential in combining our approach with existing works on blame attribution and related concepts in accountable decision making, offering practical benefits across various multi-agent domains.

## Acknowledgements

This research was, in part, funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) – project number $467367360$.

## Appendix A List of Appendices

In this section, we provide a brief description of the content provided in the appendices of the paper.

- •
Appendix [B](#A2) provides additional information on MMDP-SCMs.
- •
Appendix [C](#A3) contains the causal graph of the MMDP-SCM from Section [2.2](#S2.SS2).
- •
Appendix [D](#A4) provides additional information on noise monotonicity.
- •
Appendix [E](#A5) formally states the properties defined in Section [5](#S5) for the ASE-SV method.
- •
Appendix [F](#A6) outlines an algorithm for approximating the conditional variance from Eq. [4](#S4.E4).
- •
Appendix [G](#A7) contains the proofs of Theorems [3.3](#S3.Thmtheorem3) and [4.2](#S4.Thmtheorem2).
- •
Appendix [H](#A8) provides a discussion on the computational complexity of the ASE-SV and r-SSE-ICC methods.
- •
Appendix [I](#A9) provides additional information on the experimental setup and implementation details.
- •
Appendix [J](#A10) includes additional experimental results.

## Appendix B Additional information on MMDP-SCMs

Consider an MMDP-SCM $M=\langle\mathbf{V},\mathbf{U},P(\mathbf{u}),\mathcal{F}\rangle$. For the observational distribution of $M$, $P(\mathbf{V})$, to be consistent with an MMDP $\langle\mathcal{S},\{1,...,n\},\mathcal{A},T,h,\sigma\rangle$ and a joint policy $\pi$, functions in $\mathcal{F}$ and noise distribution $P(\mathbf{u})$ need to satisfy the following conditions for every $(s,\mathbf{a},s^{\prime})$ triplet:

$$ $\displaystyle\int_{u^{S_{0}}:f^{S_{0}}(u^{S_{0}})=s}P(u^{S_{0}})=P(S_{0}=s|\sigma);\quad\int_{u^{S_{t}}:f^{S_{t}}(s,\mathbf{a},u^{S_{t}})=s^{\prime}}P(u^{S_{t}})=T(s^{\prime}|s,\mathbf{a});$ $\displaystyle\int_{u^{A_{i,t}}:f^{A_{i,t}}(s,u^{A_{i,t}})=a_{i}}P(u^{A_{i,t}})=\pi_{i}(a_{i}|s).$ (5) $$

The first two conditions in Eq. [B](#A2.Ex12) guarantee that $M$ induces the initial state distribution and state transition dynamics of the MMDP. The third condition makes sure that the action variables in $M$ agree with the joint policy $\pi$.

## Appendix C Causal graph of MMDP-SCM

This section contains the causal graph of the MMDP-SCM described in Section [2.2](#S2.SS2). The causal graph is shown in Fig. [4](#A3.F4).

Figure: Figure 4: The causal graph of an MMDP-SCM with $n$ agents and horizon $h$. Exogenous variables are omitted.

## Appendix D Additional information on noise monotonicity

In this section, we define the (weak) noise monotonicity property for categorical SCMs. It has been shown that noise monotonicity enables counterfactual identifiability. For more details on noise monotonicity and its connection to the identifiability problem, we refer the interested reader to Triantafyllou et al. ().

###### Definition D.1 (Noise Monotonicity) .

Given an SCM $M$ with causal graph $G$, we say that variable $V^{i}\in\mathbf{V}$ is noise-monotonic in $M$ w.r.t. a total ordering $\leq_{i}$ on $\mathrm{dom}\{V^{i}\}$, if for any $pa^{i}\in\mathrm{dom}\{Pa^{i}(G)\}$ and $u^{i}_{1},u^{i}_{2}\sim P(U^{i})$ s.t. $u^{i}_{1}<u^{i}_{2}$, it holds that
$f^{i}(pa^{i},u^{i}_{1})\leq_{i}f^{i}(pa^{i},u^{i}_{2})$.

Essentially, noise monotonicity assumes that all observed variables in an SCM, or MMDP-SCM in our paper, are monotonic w.r.t. their corresponding noise variable (for some specified total ordering). Note that noise monotonicity is not limiting for the MMDPs or agents’ policies. In simple words, what noise monotonicity assumption restricts is the expressivity of counterfactual distributions. There can be many MMDP-SCMs whose observational distribution is consistent with the MMDP, but admit different counterfactual distributions. Theorem 4.3 in Triantafyllou et al. () shows that by limiting the class of possible MMDP-SCMs to the ones that satisfy noise monotonicity, counterfactual identifiability is guaranteed.

###### Definition D.1 (Noise Monotonicity) .

## Appendix E Properties for ASE-SV

In this section, we formally state the properties defined in Section [5](#S5) for the ASE-SV method.

Efficiency: The total sum of agents’ contribution scores is equal to the total agent-specific effect. Formally,

$$ $\sum_{j\in\{1,...,n\}}\phi_{j}=\mathrm{ASE}^{\{1,...,n\}}_{a_{i,t},\tau(A_{i,t})}(Y|\tau)_{M}.$ $$

Invariance: Agents who do not marginally contribute to the total agent-specific effect are assigned a zero contribution score.
Formally, if for every $S\subseteq\{1,...,n\}\backslash\{j\}$

$$ $\mathrm{ASE}^{S\cup\{j\}}_{a_{i,t},\tau(A_{i,t})}(Y|\tau)_{M}-\mathrm{ASE}^{S}_{a_{i,t},\tau(A_{i,t})}(Y|\tau)_{M}=0,$ $$

then $\phi_{j}=0$.

Symmetry: Agents who contribute equally to the total agent-specific effect are assigned the same contribution score.
Formally, if for every $S\subseteq\{1,...,n\}\backslash\{j,k\}$

$$ $\displaystyle\mathrm{ASE}^{S\cup\{j\}}_{a_{i,t},\tau(A_{i,t})}(Y|\tau)_{M}$ $\displaystyle-\mathrm{ASE}^{S}_{a_{i,t},\tau(A_{i,t})}(Y|\tau)_{M}=\mathrm{ASE}^{S\cup\{k\}}_{a_{i,t},\tau(A_{i,t})}(Y|\tau)_{M}-\mathrm{ASE}^{S}_{a_{i,t},\tau(A_{i,t})}(Y|\tau)_{M},$ $$

then $\phi_{j}=\phi_{k}$.

Contribution monotonicity: The contribution score assigned to an agent depends only on its marginal contributions to the total agent-specific effect and monotonically so.
Formally, let $M_{1}$ and $M_{2}$ be two MMDP-SCMs with $n$ agents, if for every $S\subseteq\{1,...,n\}\backslash\{j\}$

$$ $\displaystyle\mathrm{ASE}^{S\cup\{j\}}_{a_{i,t},\tau(A_{i,t})}(Y|\tau)_{M_{1}}$ $\displaystyle-\mathrm{ASE}^{S}_{a_{i,t},\tau(A_{i,t})}(Y|\tau)_{M_{1}}\geq\mathrm{ASE}^{S\cup\{j\}}_{a_{i,t},\tau(A_{i,t})}(Y|\tau)_{M_{2}}-\mathrm{ASE}^{S}_{a_{i,t},\tau(A_{i,t})}(Y|\tau)_{M_{2}},$ $$

then $\phi_{j}^{M_{1}}\geq\phi_{j}^{M_{2}}$.

## Appendix F Algorithm for conditional variance

In this section, we present our approach for approximating the expected conditional variance from Eq. [4](#S4.E4). Algorithm [1](#alg1) estimates $\mathbb{E}[\mathrm{Var}(\Delta Y_{I,a_{i,t}}|\tau,\mathbf{U}^{<S_{k}})|\tau]_{M}$.
To estimate the conditional variance $\mathbb{E}[\mathrm{Var}(\Delta Y_{I,a_{i,t}}|\tau,\mathbf{U}^{<S_{k}},\mathbf{U}^{S_{k}})|\tau]_{M}$, it suffices to modify Algorithm [1](#alg1) to sampling conditioning noise variables from $P(\mathbf{u}^{<S_{k}},\mathbf{u}^{S_{k}}|\tau)$ and non-conditioning ones from $P(\mathbf{u}^{\geq S_{k+1}}|\tau)$.

Figure: Algorithm 1 Estimates $\mathbb{E}[\mathrm{Var}(\Delta Y_{I,a_{i,t}}|\tau,\mathbf{U}^{<S_{k}})|\tau]_{M}$

## Appendix G Proofs

### G.1 Proof of Theorem 3.3

###### Proof.

Eq. [3](#S3.E3) follows directly from Definition [2.1](#S2.Thmtheorem1), Definition [3.1](#S3.Thmtheorem1) and Eq. [3](#S3.Ex7):

$$ $\displaystyle\mathrm{TCFE}_{a_{i,t},\tau(A_{i,t})}(Y|\tau)_{M}$ $\displaystyle=\mathbb{E}[Y_{a_{i,t}}|\tau]_{M}-\tau(Y)$ $\displaystyle=\mathbb{E}[Y_{a_{i,t}}|\tau]_{M}-\tau(Y)+\mathbb{E}[Y|\tau;M]_{M^{do(I)}}-\mathbb{E}[Y|\tau;M]_{M^{do(I)}}$ $\displaystyle=\mathrm{ASE}_{a_{i,t},\tau(A_{i,t})}^{\{1,...,n\}}(Y|\tau)_{M}-\mathrm{SSE}_{\tau(A_{i,t}),a_{i,t}}(Y|\tau)_{M},$ $$

where $I=\{A_{i^{\prime},t^{\prime}}:=A_{i^{\prime},t^{\prime}[a_{i,t}]}\}_{i^{\prime}\in\{1,...,n\},t^{\prime}>t}$.

∎

###### Proof.

### G.2 Proof of Theorem 4.2

###### Proof.

It holds that

$$ $\displaystyle\sum_{k\in[t+1,t_{Y}]}\psi_{S_{k}}$ $\displaystyle=\frac{\mathbb{E}[\mathrm{Var}(\Delta Y_{I,a_{i,t}}|\tau,\mathbf{U}^{<S_{t+1}})|\tau]_{M}-\mathbb{E}[\mathrm{Var}(\Delta Y_{I,a_{i,t}}|\tau,\mathbf{U}^{<S_{t_{Y}}},\mathbf{U}^{S_{t_{Y}}})|\tau]_{M}}{\mathrm{Var}(\Delta Y_{I,a_{i,t}}|\tau)}\cdot\mathrm{SSE}_{\tau(A_{i,t}),a_{i,t}}(Y|\tau)_{M}$ $\displaystyle=\frac{\mathbb{E}[\mathrm{Var}(\Delta Y_{I,a_{i,t}}|\tau,\mathbf{U}^{<S_{t+1}})|\tau]_{M}-\mathbb{E}[\mathrm{Var}(\Delta Y_{I,a_{i,t}}|\tau,\mathbf{U})|\tau]_{M}}{\mathrm{Var}(\Delta Y_{I,a_{i,t}}|\tau)}\cdot\mathrm{SSE}_{\tau(A_{i,t}),a_{i,t}}(Y|\tau)_{M}$ $\displaystyle=\frac{\mathbb{E}[\mathrm{Var}(\Delta Y_{I,a_{i,t}}|\tau,\mathbf{U}^{<S_{t+1}})|\tau]_{M}}{\mathrm{Var}(\Delta Y_{I,a_{i,t}}|\tau)}\cdot\mathrm{SSE}_{\tau(A_{i,t}),a_{i,t}}(Y|\tau)_{M}.$ $$

First step holds because $\mathbb{E}[\mathrm{Var}(\Delta Y_{I,a_{i,t}}|\tau,\mathbf{U}^{<S_{k}},\mathbf{U}^{S_{k}})|\tau]_{M}=\mathbb{E}[\mathrm{Var}(\Delta Y_{I,a_{i,t}}|\tau,\mathbf{U}^{<S_{k+1}})|\tau]_{M}$, for every $k\in\{t+1,...,t_{Y}-1\}$.
The second step follows from the fact that noise terms associated with observed variables which (chronologically) proceed $t_{Y}$ do not influence the value of $\Delta Y_{I,a_{i,t}}$.
The third step holds because the expected conditional variance satisfies calibration, i.e., $\mathbb{E}[\mathrm{Var}(\Delta Y_{I,a_{i,t}}|\tau,\mathbf{U})|\tau]_{M}=0$.

Let now $X$ be any ancestor of $S_{t+1}$ in the causal graph of $M$, apart from $A_{i,t}$. Note that $X$ is not affected by interventions $do(I)$ and $do(A_{i,t}:=a_{i,t})$. Therefore, the solution of $X$ in the MMDP-SCMs $M^{do(I)}$ and $M^{do(A_{i,t}:=a_{i,t})}$ will be equal to its factual value in $\tau$, i.e, $\tau(X)$, for every context $\mathbf{u}$ sampled from the posterior $P(\mathbf{u}|\tau)$.
Furthermore, $A_{i,t}$ is fixed to $a_{i,t}$ in $M^{do(A_{i,t}:=a_{i,t})}$, while it is also not affected by $do(I)$.
It follows that conditioning on the noise terms associated with $X$ or $A_{i,t}$ does not reduce the variance of $\Delta Y_{I,a_{i,t}}$. Therefore, it holds that

$$ $\mathbb{E}[\mathrm{Var}(\Delta Y_{I,a_{i,t}}|\tau,\mathbf{U}^{<S_{t+1}})|\tau]_{M}=\mathrm{Var}(\Delta Y_{I,a_{i,t}}|\tau),$ $$

which concludes our proof.

∎

###### Proof.

## Appendix H Discussion on computational complexity

In this section, we analyze the computational complexity of the ASE-SV (Definition [5.2](#S5.Thmtheorem2)) and r-SSE-ICC (Definition [4.1](#S4.Thmtheorem1)) methods, and discuss some potential mitigation strategies for when the number of agents or the length of the time horizon are prohibitively large.

### H.1 Computational complexity of ASE-SV

The number of agent-specific effect evaluations required by the exact ASE-SV calculation grows exponentially with the number of agents $n$. One potential mitigation strategy for this problem is to adapt to our setting sampling based approaches that efficiently approximate Shapley value without violating efficiency, i.e., attributing the entire effect.
Jia et al. () propose such an algorithmic approach, which requires $O(n(\log n)^{2})$ evaluations for any bounded utility. This means that their algorithm is applicable to ASE-SV in settings where the value of agent-specific effects is bounded, as is the case in both our experiments.

### H.2 Computational complexity of r-SSE-ICC

Computing the contribution scores assigned by the r-SSE-ICC method to all state variables requires $O(h)$, where $h$ denotes the time horizon, executions of Algorithm [1](#alg1).
When we deal with long-horizon MMDPs, this linear dependence on the number of time-steps can slow down our method.
One intuitive strategy to reduce the number of computations in this case is by grouping together state variables from consecutive time-steps. That way, the r-SSE-ICC method would attribute the effect to sets of consecutive state variables instead of individual ones. If the time horizon (between action and outcome) is partitioned in groups of the same fixed size $k$, except maybe for the last one, then the modified r-SSE-ICC method would require $O(\frac{h}{k})$ executions of Algorithm [1](#alg1).

In settings where it is reasonable to assume or empirically verify that r-SSE-ICC is sparse, in the sense that only a few state variables have significant (intrinsic) contributions to the effect, as it is the case in both our experiments, then we are able to further reduce the number of Algorithm [1](#alg1) executions. More specifically, we can utilize the fact that the expected noise-conditional variance measure satisfies monotonicity, i.e., $E[\mathrm{Var}(\Delta Y_{I,a_{i,t}}|\tau,\mathbf{U}^{<S_{k}})|\tau]_{M}\geq E[\mathrm{Var}(\Delta Y_{I,a_{i,t}}|\tau,\mathbf{U}^{<S_{k}},\mathbf{U}^{S_{k}})|\tau]_{M}$.
If we know, for example, that for most of the times there is at most one state variable with non-negligible (intrinsic) contribution to the effect, we can simply use a binary search approach to pinpoint that state. This can reduce the complexity of r-SSE-ICC to $O(\log(h))$ executions.

## Appendix I Experimental Setup and Implementation

In this section, we provide additional information on the experimental setup and implementation.

### I.1 Gridworld Experiments

Setup. Our setup is an adaptation of the Planner-Actor-Reporter system from Dasgupta et al. (). The Planner is tasked with understanding the high-level steps necessary for the completion of a task and then breaking it down to a sequence of instructions.
Actors are RL agents pre-trained to complete a set of simple instructions in the environment. Lastly, the Reporter is tasked with translating environment observations into a textual representation comprehensible by the Planner.

Environment. We consider the gridworld environment depicted in Fig. [2(a)](#S6.F2.sf1) with two actors, $\mathcal{A}_{1}$ and $\mathcal{A}_{2}$.
There are two boxes located on the rightmost corners, each of which contains two objects.
Each object has a color that determines its value, in particular, pink $>$ green $>$ yellow. The object’s color is randomly sampled at the beginning of each trajectory.
Objects can be picked up and carried by the actors – each actor can pick up only one object, and only one object can be picked up from each box.
Grey-colored cells represent walls.
Blank cells indicate areas of small negative cost.
Colored cells indicate areas of larger stochastic penalty, which is significantly reduced when actors carry an object of a matching color. Penalties induced by cells of the same color share the same means, but might differ in their underlying distributions.
Moreover, in expectation, pink cells inflict higher penalties than green ones, and green cells higher than yellow ones.
Cells denoted with stars are delivery locations. If an object is delivered to the location with the matching color, then the object’s value is rewarded. The objective in this environment is to maximize the combined total return of both actors. The full reward specification can be found in Table [1](#A9.T1).

**Table 1: Reward specification for Gridworld. An empty distribution column implies a deterministic reward issued upon entering the cell. For the green corridor, penalties are specified on a per-cell basis, identified by their zero-based indices into the associated row and column.**
| Cell | Values | Distribution |
| --- | --- | --- |
| All | -0.2 | - |
| Pink Penalty | [-30, -50, -70] | [1/3, 1/3, 1/3] |
| Pink Penalty (Reduced) | [-5, -15, -25] | [1/3, 1/3, 1/3] |
| Pink Delivery | +180 | - |
| Green Penalty $C_{2,4}$ | [-30, -40, -50] | [0.3, 0.4, 0.3] |
| Green Penalty $C_{2,4}$ (Reduced) | [-5, -10, -15] | [0.3, 0.4, 0.3] |
| Green Penalty $C_{2,5}$ | [-30, -40, -50] | [0.25, 0.5, 0.25] |
| Green Penalty $C_{2,5}$ (Reduced) | [-5, -10, -15] | [0.25, 0.5, 0.25] |
| Green Penalty $C_{2,6}$ | [-30, -40, -50] | [0.2, 0.6, 0.2] |
| Green Penalty $C_{2,6}$ (Reduced) | [-5, -10, -15] | [0.2, 0.6, 0.2] |
| Green Penalty $C_{2,7}$ | [-30, -40, -50] | [0.15, 0.7, 0.15] |
| Green Penalty $C_{2,7}$ (Reduced) | [-5, -10, -15] | [0.15, 0.7, 0.15] |
| Green Delivery | +150 | - |
| Yellow Penalty | [-25, -30, -35] | [1/3, 1/3, 1/3] |
| Yellow Penalty (Reduced) | [-2.5, -5, -7.5] | [1/3, 1/3, 1/3] |
| Yellow Delivery | +90 | - |

Instructions.
The Gridworld environment supports a simplified set of $8$ instructions: *examine box 1*, *examine box 2*, *pickup pink*, *pickup green*, *pickup yellow*, *goto pink*, *goto green* and, *goto yellow*. We pre-train both actors to learn a goal-conditioned policy for executing each of the available instructions. During training, we sample a new instruction at the beginning of each trajectory. Additionally, we initialize an actor according to the instruction and randomize over its valid observation space. For example, for the instruction *goto pink*, we initialize the actor to its respective position (under/above the first/second box for $\mathcal{A}_{1}$ and $\mathcal{A}_{2}$ respectively) and randomly select the object it’s carrying. The actor is rewarded positively whenever it completes the instruction.

Actors.
Actors $\mathcal{A}_{1}$ and $\mathcal{A}_{2}$ spawn on the same fixed locations at the beginning of each trajectory. Apart from movement actions, actors can also perform pickup actions when located next to a box. The policies are represented via neural network parameters and are learned using double deep Q-learning (Mnih et al., ; Van Hasselt et al., ). Both agents take as their input concatenated, one-hot encoded vectors, which include their instruction, their current position and the color of the object they are carrying. We provide a full list of hyperparameters in Table [2](#A9.T2). The hyperparameter optimization method was performed by randomly sampling $50$ candidates from the specified ranges and selecting the combination that yielded the best test reward, averaged over all instructions.

**Table 2: Hyperparameters used for the Gridworld actors’ policies.**
| Parameter name | Parameter value | Tuning Range |
| --- | --- | --- |
| Discount | 0.99 | [0.99, 0.9, 0.8] |
| Target Update Freq. | 1000 | [500, 1000, 1500] |
| Batch size | 512 | [256, 512, 1024, 2048] |
| Hidden Dim | 128 | [64, 128, 256] |
| Hidden Depth | 3 | [2, 3] |
| Learning Rate | 1e-4 | [1e-5, 5e-5, 1e-4, 5e-4, 1e-3] |
| Num. Estimation Step | 1 | [1, 3, 5, 10, 15] |

Planner and Reporter.
Planner is implemented using a pre-trained LLama 2.7B model (Touvron et al., ) and few-shot learning, to provide actors with instructions. More specifically, Planner can instruct actors to: examine a box, pickup an object and deliver that object to a specific destination.
Furthermore, we assume an optimal Reporter whose task is to report to the Planner the necessary information about the state of the environment. In particular, the Reporter provides information about the boxes’ contents and which objects were picked up by the actors (see Trajectories [1](#alg1a) and [2](#alg2) for an illustrative example).

### I.2 Sepsis Experiments

Our experimental setup and implementation closely follow that of Triantafyllou et al. ().

### I.3 Compute Resource

All experiments were run on a 64bit Debian-based machine having 2x12 CPU cores clocked at 3GHz with access to 1 TB of DDR3 1600MHz RAM and an NVIDIA A40 GPU. The software stack relied on Python 3.9.13, with installed standard scientific packages for numeric calculations and visualization (we provide a full list of dependencies and their exact versions as part of our code).

## Appendix J Additional Results

### J.1 Gridworld

Additional experiment. We repeat the experiment from Section [6.1](#S6.SS1), but instead of intervening on $\mathcal{A}_{2}$’s pickup action we intervene on the Planner’s action. In particular, we intervene on the Planner’s action at Step $2$, forcing it to instruct $\mathcal{A}_{2}$ to pick up the green object instead of the pink one. The total counterfactual effect of this intervention is equal to that of the intervention on $\mathcal{A}_{2}$’s action. However, the result of our decomposition approach for these two effects is different.

According to Plot [5(a)](#A10.F5.sf1), the TCFE in this scenario is fully attributed to how the agents would respond to the intervention, and more specifically to the response of agent $\mathcal{A}_{2}$. Both the SSE and the r-SSE in this scenario are zero. This result is intuitive, as the Planner is not able to influence the state transitions directly, and hence the effect of its actions do not propagate through the environment dynamics. In contrast, the actions of $\mathcal{A}_{2}$ can influence the outcome through both the environment and future agent actions, and hence the decomposition of their effect is more nuanced (see Plot [2(b)](#S6.F2.sf2)).

Figure: (a) Counterfactual Effects
Refer to caption: /html/2410.12539/assets/x9.png

Trajectories. We provide a textual depiction of the factual (Trajectory [1](#alg1a)) and counterfactual (Trajectory [2](#alg2)) trajectories from Fig. [2(a)](#S6.F2.sf1). We also provide a textual depiction of the counterfactual trajectory from the experiment described above (Trajectory [3](#alg3)).

Figure: Algorithm 1 : Factual

Figure: Algorithm 2 : Counterfactual ($\mathcal{A}_{2}$’s action)

Figure: Algorithm 3 : Counterfactual (Planner’s action)

### J.2 Sepsis

Fig. [6](#A10.F6) illustrates the distribution of the r-SSE contribution scores computed by the r-SSE-ICC method in Section [6.2](#S6.SS2).

Figure: (a) Round Difference 4
Refer to caption: /html/2410.12539/assets/x10.png

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 5
presentation: 3
questions: Please see Weaknesses.
soundness: 3
strengths: 1. This paper bridges reinforcement learning with the causal reasoning community, extending several well-established concepts—such as natural direct/indirect effect decomposition, intrinsic causal contributions, and flow-based attribution methods—into multi-agent MDPs.

2. It provides insights into the distinct roles that agents and the environment play in influencing effects, demonstrated through real-world examples.
summary: This paper studied counterfactual effect decomposition in multi-agent MDPs under the structural causal model framework. Specifically, it first shows that the total counterfactual effect of an agent's action can be decomposed into the agent-specific effect and the reverse state-specific effect. Second, it proposes an axiomatic framework based on agent-specific effects to attribute the total effect to individual agents, and introduces a method for attributing the reverse state-specific effect to state variables based on their "intrinsic" contributions.
weaknesses: **Novelty** The paper examines the counterfactual effect of a single agent’s action. However, it would be more impactful and interesting to investigate the estimands for multiple agents' actions in a multi-agent MDP, especially under varying interaction structures. Additionally, under the single-agent action setting, Theorems 3.3 and 4.2 are straightforward extensions of the causal mediation formula (Pearl, 2001) and intrinsic causal contributions (Janzing et al., 2024).

**Experiment** I find the validity of conclusions such as the causal explanation formula (lines 411 and 412) questionable, given that both TCFE and tot-ASE are estimated quantities. I also find there is no experiment to demonstrate the estimation accuracy. It would be more insightful to first use simulations to assess whether the estimation algorithm accurately approximates the true values.

**Assumption** The interpretation of the key assumption for identification, noise monotonicity, is unclear. A discussion on the conditions under which it is valid, and when it may not hold, would clarify its applicability. Additionally, an illustration using the sepsis example would be helpful.

---

confidence: 4
contribution: 3
initial_rating: 8
presentation: 3
questions: 1. In Figure 1(b), what does the unannotated section of the pie chart represent?

2. Adding a causal graph to illustrate ASE and r-SSE would improve clarity and enhance understanding of the counterfactual effect decomposition. 

3. In Figures 3(a) and 3(b), why is the trust parameter allowed to be 0 in (b) but not in (a)?

4. While the identifiability of TCFE is discussed under the condition of noise monotonicity, what about the identifiability of r-SSE and ASE?

5. For the proposed decomposition of TCFE, is there a way to verify the validity of the results? Specifically, how reliable are the percentage contributions assigned to each agent or state transition? Could simulations with known ground-truth causal graphs be included to demonstrate their reliability? By comparing the estimated contributions of each agent and state with the ground truth, the causal explanation formula and subsequent algorithm would be more compelling.
soundness: 3
strengths: 1. This paper addresses an interesting and meaningful topic by explaining the counterfactual effect in MMDP through a two-part decomposition, which enables a clear, separate bi-level evaluation of each component's contribution.

2. The paper is well-written, and the proposed causal explanation formula is concise. Modifying the state-specific effect into a reverse state-specific effect, which can be combined with agent-specific effects, offers a reasonable way to evaluate counterfactual effects.

3. The experimental results seem promising, particularly in terms of supporting causal interpretation.
summary: The paper investigates the counterfactual effect of an agent's action within a multi-agent Markov decision process (MDP) environment by decomposing it into two components: effects propagating through subsequent actions and effects propagating through subsequent states. For the first component, the study introduces agent-specific effects to assess the contribution of each agent. For the second component, the reverse state-specific effect (r-SSE), the paper applies the concept of intrinsic causal contributions (ICC) to measure the impact of each state.

This decomposition is evaluated across two experimental environments, with results providing insights into the distinct roles that agents and the environment play in shaping the overall effect. The paper discusses the implications and highlights the contributions of each factor in influencing outcomes, which is helpful in decision making process.
weaknesses: 1. The explanation of the decomposition of TCFE, especially for r-SSE, lacks clarity and is somewhat difficult to follow since it's a reverse version. Including a toy example or a causal graph for Theorem 3.3 would improve comprehension.

2. The decision-making process in the Gridworld experiment (Section 6.1) is not clearly conveyed. A simplified trajectory or causal graph—such as a plot similar to Figure 1(a) or Table 1 in Appendix I—would help clarify the process.

3. While the experimental results allow for reasonable causal interpretation, there is limited evidence supporting their robustness or reliability. The results are reasonable under the specific settings, but can the reported percentages be considered reliable?

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: - Percentage conversion: Theorem 3.3 suggests the "total counterfactual effect" can be decomposed into "total agent-specific effect" **minus** "reverse state-specific effect". How are the two parts converted to a percentage contribution, for example in the pie chart in Fig 1b? It might be useful to show the raw effect values as well. 
- L370: cells denoted with stars are delivery locations - where are these?
soundness: 3
strengths: - Exposition is clear. 
- Good use of the sepsis example, which helps contextualize the abstract math throughout the text . 
- Principled development of mathematical tools to achieve the desired effect decomposition.
summary: This paper proposes a causal explanation framework for multi-agent MDPs, by decomposing the total counterfactual effect of an intervention into a part that influences the agents’ behavior and and a part that depends on environment dynamics.
weaknesses: - The mathematical notation are quite dense and at times a little hard to grasp. For example, Def 2.1, 3.1, 3.2 all look similar but clearly they are different. The authors included textual descriptions of these mathematical definitions (individually) which is great, but I would appreciate a paragraph comparing these definitions and highlighting the differences (for example, Y vs Y_{a_{i,t}}).

---

confidence: 3
contribution: 2
initial_rating: 6
presentation: 2
questions: - Can the authors provide more detailed examples for each proposed measure? For instance, can the authors explain these measures and the decomposition in the context of Figure 1 or Figure 2a? What causal mechanisms are these metrics evaluating, and what are their implications?
soundness: 3
strengths: - The proposed measures seem reasonable. All parametric assumptions have been explicitly stated. The proposed methods seem technically sound.
- Comprehensive simulations were performed. The results support the proposed algorithms.
summary: This paper proposes new counterfactual measures that can be used to explain the observed behaviors of multi-agent systems. First, the authors proposed the total counterfactual effect, which measures the difference in the expected reward if every agent took a different action compared to the observed trajectories (as a baseline). The authors then decomposed the total counterfactual effect into two components: one measuring the effect that propagates through all subsequent agents’ actions, called the total agent-specific effect, and another related to the effect that propagates through the state transitions, called the reverse state-specific effect. Building on the method of path analysis in structural causality, the authors then further decomposed the total agent-specific effect into a series of more refined agent-specific effects. Counterfactual measures based on the Shapley value are proposed to attribute the effect to each individual agent. Similarly, the authors also proposed more refined counterfactual measures, based on the notion of intrinsic causal contributions, to decompose the reverse state-specific effects. These proposed counterfactual measures could be seen as explanations evaluating the influence of underlying causal mechanisms on the difference in the observed outcome.
weaknesses: - The identification of the proposed counterfactual measures relies on the additional parametric assumption of weak monotonicity. This assumption is restrictive and may limit the paper's application to many practical domains.
- The paper is quite notation dense. It would be best improved by including a table summarizing all the proposed measures and necessary notations.
- The introduction of each new counterfactual measure could be more gentle. This might be challenging for readers unfamiliar with counterfactual notations and structural causality. I suggest including a detailed example following each definition of the proposed counterfactual measure.

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
questions: 1. In Lines 242-250, the authors discuss connections between this work and mediation analysis in causal inference, where the total effect is typically decomposed into direct and indirect effects. In the multi-agent MDP setting, however, the total effect is expressed as a difference (rather than a sum) between the ASE and SSE. Could the authors elaborate on how this decomposition aligns with classical mediation analysis? Is the similarity primarily conceptual (i.e., decomposing into two parts), or is there a more detailed mapping between single-stage mediation analysis and the multi-agent MDP framework?

2. The proposed causal explanation framework relies on counterfactual estimation under a fixed action assignment sequence, which in turn requires accurate and consistent counterfactual estimates with minimal variance. In many real-world applications involving only observational data, would it be overly challenging to apply this decomposition using off-policy evaluation methods? I am curious to hear the authors’ thoughts on the feasibility of such approaches.
soundness: 3
strengths: 1. The motivation for this work is clear, with significant relevance to causal attribution in multi-agent MDPs. 

2. The theoretical decomposition is accompanied by detailed explanations, and I appreciate the authors' efforts in providing sufficient context in Sections 4 and 5.
summary: This paper presents a causal effect attribution approach that decomposes the total counterfactual effect into an agent-specific effect and an inverse state transition effect within the framework of a multi-agent Markov Decision Process (MDP). The authors further refine this decomposition at a granular level to attribute causal effects to individual agents and states. Comprehensive simulations are provided to illustrate the proposed decomposition formula, with detailed discussions on future directions.

Overall, the paper is well-written and well-structured, with ideas that are direct and easy to follow, supplemented by clear examples. While there are minor concerns regarding the degree of innovation and scalability, this work nonetheless advances the understanding of causal effects in complex multi-agent sequential decision-making systems, which I believe will be valuable for guiding future research in decision-making.
weaknesses: 1. The work appears to be a direct extension of Triantafyllou et al. (2024) in decomposing the agent-specific effect and Janzing et al. (2024) in decomposing the reverse state-specific effect. The main innovation of this work, as I understand, is the extension to a multi-agent MDP system. However, it is not clear which specific challenges of the multi-agent MDP framework are addressed that go beyond these previous works. For instance, if the primary challenge arises from the sequential decision-making nature of MDPs, it would be beneficial to further emphasize how the authors handle these complexities.

2. The paper addresses the computational complexity of counterfactual effect decomposition with a large number of agents and time steps, and I appreciate the discussion in Appendix H on approximation and scalability improvements. However, the simulations in the main paper are limited to two agents. It would be informative to see how the method performs with more agents (e.g., $3$ or $5$) and how the results might differ. Additionally, has the performance of the approximation methods in Appendix H been empirically evaluated, or is it based solely on theoretical considerations? Some empirical analysis of the time-accuracy tradeoff would strengthen the discussion.

---

confidence: 2
contribution: 3
initial_rating: 6
presentation: 3
questions: 1) Could you please clarify the notation I mentioned in Weakness 1) above? (Just to be sure I understood the paper as I think I did!)

2) To what extent does the complexity of the agents themselves contribute to the complexity of computing these scores? Some multi-agent systems consist of large populations of boundedly rational agents making decisions according to relatively simple rules, or according to "satisficing" criteria. This is the other extreme to the examples considered in this paper, which consists of a very small number of agents, but who have good domain expertise/cognitive capabilities (e.g., your LLM-assisted RL agents). Does using agents with simpler cognitive rules mean it is easier to scale up these scores to larger numbers of agents?
soundness: 3
strengths: The paper is well-written and covers a topic that I see will be very useful in the study of multi-agent systems. Using causal inference methods to understand the importance of agent decisions in complex multi-agent systems is something that will help scientists to reason about such systems. The authors also provide a good discussion of the relation of their approach to a variety of pre-existing works and notations of counterfactual effect decomposition (causal mediation formula etc.).
summary: This paper proposes an approach to decomposing the counterfactual effect of the actions taken by agents comprising a multi-agent Markov decision process into the effect arising directly from the other agents' resultant behaviours, and the effect coming from the resultant environmental dynamics. This provides a way to explain counterfactual outcomes in multi-agent sequential decision making settings.
weaknesses: 1) Some of the notation could be better explained. For example (and sorry if I missed this explanation somewhere in the paper), for someone like me – where I am perhaps an example of someone who is not fully a member of this particular research subfield – it wasn't clear to me why it is necessary to write $\mathbb{E}[Y \mid \tau; M]_{M^{do(I)}}$ and why someone couldn't instead just write $\mathbb{E}[Y \mid \tau; M^{do(I)}]$. Having consulted other papers (e.g., some of the references in the current paper), it does indeed seem like the former is standard notation, but it might benefit the reader and make the paper more accessible to those not directly in this research subfield to explain what exactly the subscripts mean in these expectations and why it is necessary to both "condition" on $M$ and include a subscript $M^{do(I)}$ in some of these expectations.

2) Both experiments considered only two interacting agents simulated over relatively short time horizons, and the approach isn't demonstrated on larger-scale systems. I appreciate that this is explicitly discussed as a limitation in the Discussion section, however.

Meta-review: This paper studied counterfactual effect decomposition in multi-agent MDPs under the structural causal model framework. The author nicely bridged reinforcement learning with the causal reasoning community, extending several well-established concepts into multi-agent MDPs. The paper is well written and organized. While there are remaining concerns from reviewers regarding the novelty, contribution, and utilities of this work. As raised by several reviewers, this paper is a direct extension of Triantafyllou et al. (2024) and Janzing et al. (2024) with the effect defined on a more granular level. The considered Shapley value is already well established and the proposed attribution method is similar to the causal mediation formula (Pearl, 2001). I appreciate the authors' efforts in connecting all these dots but the utility of the proposed effect decomposition is not quite clear for multi-agent MDPs. Considering this work focus on the framework of sequential decision making, it is crucial to justify how the proposed method is useful besides interpretation of effects. There are other comments regarding the strong assumptions of noise monotonicity which further limited the practical utility of this work.

Overall, this paper was rather borderline; we'd encourage the authors to take into consideration all the feedback provided by the reviewers to further strengthen their manuscript for resubmission.

Decision: Reject