Counterfactual Explanations in Sequential Decision Making Under Uncertainty

Abstract:
Methods to find counterfactual explanations have predominantly focused on onestep 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.

heading: 1 Introduction
text: In recent years, there has been a rising interest on the potential of machine learning models to assist and enhance decision making in high-stakes applications such as justice, education and healthcare [1– 3]. In this context, machine learning models and algorithms have been used not only to predict the outcome of a decision making process from a set of observable features but also to find what would have to change in (some of) the features for the outcome of a specific process realization to change. For example, in loan decisions, a bank may use machine learning both to estimate the probability that a customer repays a loan and to find by how much a customer may need to reduce her credit card debt to increase the probability of repayment over a given threshold. Here, our focus is on the latter, which has been often referred to as counterfactual explanations.
The rapidly growing literature on counterfactual explanations has predominantly focused on one-step decision making processes as the one described above [4–6]. In such settings, the probability that an outcome occurs is typically estimated using a supervised learning model and finding counterfactual explanations reduces to a search problem across the space of features and model predictions [7–11]. Moreover, it has been argued that, to obtain counterfactual explanations that are actionable and have the predicted effect on the outcome, one should favor causal models [12–14]. In this work, our goal is instead to find counterfactual explanations for decision making processes in which multiple, dependent actions are taken sequentially over time. In this setting, the (final) outcome of the process depends on the overall sequence of actions and the counterfactual explanation specifies an alternative sequence of actions differing in at most k actions from the observed sequence that could have led the process realization to a better outcome. For example, in medical treatment, assume a physician takes a
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
sequence of actions to treat a patient but the patient’s prognosis does not improve, then a counterfactual explanation would help the physician understand how a small number of actions taken differently could have improved the patient’s prognosis. However, since there is (typically) uncertainty on the counterfactual dynamics of the environment, there may be a different counterfactual explanation that is optimal under each possible realization of the counterfactual dynamics. Moreover, since, in many realistic scenarios, a decision maker needs to decide among a small number of actions on the basis of a few observable covariates, which are often discretized into (percentile) ranges, in this work, we focus on decision making processes where the state and action spaces are discrete and low-dimensional.
The work most closely related to ours, which lies within the area of machine learning for healthcare, has achieved early success at using machine learning to enhance sequential (clinical) decisions [15– 18]. However, rather than finding counterfactual explanations, this line of work has predominantly focused on using reinforcement learning to design better treatment policies. A notable exception is by Oberst and Sontag [18], which introduces an off-policy evaluation procedure for highlighting specific realizations of a sequential decision making process where a policy trained using reinforcement learning would have led to a substantially different outcome. While our work builds upon their modeling framework, we do not focus on off-policy evaluation but, instead, on the generation of (better) alternative action sequences as a means of explanation for the process’s outcome. Therefore, we see their contributions as complementary to ours.
More broadly, our work is not the first to use counterfactual reasoning in the context of sequential decision making in the machine learning literature [19, 20]. However, previous work has used counterfactual reasoning either to learn optimal policies using limited observational data [19] or to explain the action choices of a reinforcement learning agent [20]. In contrast, our work uses a causal model of the environment to compute alternative action sequences, close to the observed one, which, in retrospect, could have improved the outcome of the decision making process. Refer to Appendix A for a discussion of further related work.
Our contributions. We start by formally characterizing a sequence of (discrete) actions and (discrete) states using finite horizon Markov decision processes (MDPs). Here, we model the transition probabilities between a pair of states, given an action, using the Gumbel-Max structural causal model [18]. This model has been shown to have a desirable counterfactual stability property and, given a sequence of actions and states, it allows us to reliably estimate the counterfactual outcome under an alternative sequence of actions. Building upon this characterization, we formally state the problem of finding the counterfactual explanation for an observed realization of a sequential decision making process as a constrained search problem over the set of alternative sequences of actions differing in at most k actions from the observed sequence. Then, we present a polynomial time algorithm based on dynamic programming that finds a counterfactual policy that is guaranteed to always provide the optimal counterfactual explanation on every possible realization of the counterfactual transition probability induced by the observed process realization. Finally, we validate our algorithm using both synthetic and real data from cognitive behavioral therapy and show that the counterfactual explanations can provide valuable insights to enhance sequential decision making under uncertainty1.

heading: 2 Characterizing Sequential Decision Making using Causal Markov Decision Processes
text: Our starting point is the following stylized setting, which resembles a variety of real-world sequential decision making processes. At each time step t ∈ {0, . . . , T − 1}, the decision making process is characterized by a state st ∈ S , where S is a space of n states, an action at ∈ A, where A is a space of m actions, and a reward R(st, at) ∈ R. Moreover, given a realization of a decision making process τ = {(st, at)}T−1t=0 , the outcome of the decision making process o(τ) = ∑ tR(st, at) is given by the sum of the rewards.
Given the above setting, we characterize the relationship between actions, states and outcomes using finite horizon Markov decision processes (MDPs). More specifically, we consider an MDP M = (S,A, P,R, T ), where S is the state space, A is the set of actions, P denotes the transition probability P (St+1 = st+1 |St = st, At = at), R denotes the immediate reward R(st, at), and T is the time horizon. While this characterization is helpful to make predictions about future states and design action policies [21], it is not sufficient to make counterfactual predictions, e.g., given a realization of a decision making process τ = {(st, at)}T−1t=0 , we cannot know what would have
1Our code is accessible at https://github.com/Networks-Learning/counterfactual-explanations-mdp.
happened if, instead of taking action at at time t, we had taken action a′ 6= at. To be able to overcome this limitation, we will now augment the above characterization using a particular class of structural causal model (SCM) [22, 23] with desirable properties.
Let C be a structural causal model defined by the assignments St+1 = gS(St, At,Ut) and At = gA(St,Vt), (1)
where Ut and Vt are n- and m-dimensional independent noise variables, respectively, and gS and gA are two given functions, and let P C be the distribution entailed by C. Then, as argued by Buesing et al. [19], we can always find a distribution for the noise variables and a function gS so that the transition probability of the MDP of interest is given by the following interventional distribution over the SCM C:
P (St+1 = st+1 |St = st, At = at) = P C ; do(At=at)(St+1 = st+1 |St = st) (2) where do(At = at) denotes a (hard) intervention in which the second assignment in Eq. 1 is replaced by the value at.
Under this view, given an observed realization of a decision making process τ = {(st, at)}T−1t=0 , we can compute the posterior distribution P C |St=st,St+1=st+1,At=at(Ut) of each noise variable Ut. Building on the conditional density function of this posterior distribution, which we denote as f C |St=st,St+1=st+1,At=at Ut (u), we can define a (non-stationary) counterfactual transition probability
Pτ,t(St+1 = s ′ |St = s,At = a) = P C |St=st,St+1=st+1,At=at ; do(At=a)(St+1 = s′ |St = s)
= ∫ Rn P C |St=st,St+1=st+1,At=at ; do(At=a)(St+1 = s ′ |St = s,Ut = u) × fC |St=st,St+1=st+1,At=at ; do(At=a)Ut (u)du (a) =
∫ Rn 1[s′ = gS(s, a,u)] · fC |St=st,St+1=st+1,At=atUt (u)du
= EUt |St=st,St+1=st+1,At=at [1[s ′ = gS(s, a,Ut)]], (3)
where, in (a), we drop the do(·) because Ut andAt are independent in the modified SCM. Importantly, the above counterfactual transition probability allows us to make counterfactual predictions, e.g., given that, at time t the state was st and, at time t + 1, the process transitioned to state st+1 after taking action at, what would have been the probability of transitioning to state s′ after taking action a 6= at if the state had been s at time t. Refer to Figure 1 for a visual description of our model and the notion of counterfactual predictions.
However, for state variables taking discrete values, the posterior distribution of the noise may be non-identifiable without further assumptions, as argued by Oberst and Sontag [18]. This is because there may be several noise distributions and functions gS which give interventional distributions consistent with the MDP’s transition probabilities but result in different counterfactual transition distributions. To avoid these non-identifiability issues, we follow Oberst and Sontag and restrict our attention to the class of Gumbel-Max SCMs, i.e.,
St+1 = gS(St, At,Ut) := argmax s∈S
{logP (St+1 = s |St, At) + Ut,s}, (4)
where Ut,s ∼ Gumbel(0, 1) and P (· |St, At) is the transition probability of the MDP. More specifically, this class of SCMs has been shown to satisfy a desirable counterfactual stability property, which goes intuitively as follows. Assume that, at time t, the process transitioned from state st to state st+1 after taking action at. Then, in a counterfactual scenario, it is unlikely that, at time t, the process would transition from a state s to a state s′ other than st+1—the factual one—unless choosing an action a that decreases the relative chances of st+1 compared to the other states. More formally, for a model satisfying counterfactual stability, given τ = {(st, at)}T−1t=0 , for all s, s′ with s′ 6= st+1 such that
P (St+1 = st+1 |St = s,At = a) P (St+1 = st+1 |St = st, At = at) ≥ P (St+1 = s ′ |St = s,At = a) P (St+1 = s′ |St = st, At = at) ,
it holds that Pτ,t(St+1 = s′ |St = s,At = a) = 0. In practice, in addition to solving the non-identifiability issues, the use of Gumbel-Max SCMs allows for an efficient procedure to sample from the corresponding noise posterior distribution P C |St=st,St+1=st+1,At=at(Ut), described elsewhere [18, 24], and given a set of d samples from the noise posterior distribution, we can compute an unbiased finite sample Monte-Carlo estimator for the counterfactual transition probability, as defined in Eq. 3, as follows:
Pτ,t(St+1 = s ′ |St = s,At = a) ≈
1
d ∑ j∈[d] 1[s′ = gS(s, a,uj)] (5)

heading: 3 Counterfactual Explanations in Markov Decision Processes
text: Inspired by previous work on counterfactual explanations in supervised learning [7, 8], we focus on counterfactual outcomes that could have occurred if the alternative action sequence was “close” to the observed one. However, since in our setting, there is uncertainty on the counterfactual dynamics of the environment, we will look for a non-stationary counterfactual policy π that, under every possible realization of the counterfactual transition probability defined in Eq. 3, is guaranteed to provide the optimal alternative sequence of actions differing in at most k actions from the observed one.
More specifically, let τ = {(st, at)}T−1t=0 be an observed realization of a decision making process characterized by a Markov decision process (MDP)M = (S,A, P,R, T ) with a transition probability defined via a Gumbel-Max structural causal model (SCM), as described in Section 2. Then, to characterize the effect that any alternative action sequence would have had on the outcome of the above process realization, we start by building a non-stationary counterfactual MDP Mτ = (S+,A, P+τ , R+, T ). Here, S+ = S × {0, . . . , T − 1} is an enhanced state space such that each s+ ∈ S+ corresponds to a pair (s, l) indicating that the original decision making process would have been at state s ∈ S had already taken l actions differently from the observed sequence. Following this definition, R+ denotes the reward function which we define as r+((s, l), a) = R(s, a) for any (s, l) ∈ S+ and a ∈ A, i.e., the counterfactual rewards remain independent of the number of modifications in the action sequence. Lastly, let Pτ be the counterfactual transition probability, as defined by Eq. 3. Then, the transition probability P+τ for the enhanced state space is defined as: P+τ,t ( S+t+1 = (s ′, l′) |S+t = (s, l) , At = a ) =  Pτ,t (St+1 = s ′ |St = s,At = a) if (a = at ∧ l′ = l) ∨ (a 6= at ∧ l′ = l + 1)
0 otherwise,
where note that the dynamics of the original states s are equivalent both under P+τ,t and Pτ,t, however, under P+τ,t, we also keep track of the number of actions differing from the observed actions. Now, let π : S+ × {0, . . . , T − 1} → A be a policy that deterministically decides about the counterfactual action a′t that should have been taken if the process’s enhanced state had been s + t = (s ′ t, lt), i.e., the counterfactual state at time t was s′t after performing lt action changes. Then, given such a counterfactual policy π, we can compute the corresponding average counterfactual outcome as follows:
ōπ(τ) := Eτ ′∼P+τ | s+0 =(s0,0) [ T−1∑ t=0 r+((s′t, lt), a ′ t) ] (6)
where τ ′ = {((s′t, lt), a′t)}T−1t=0 is a realization of the non-stationary counterfactual MDPMτ with a′t = π((s ′ t, lt), t) and the expectation is taken over all the realizations induced by the transition probability P+τ and the policy π. Here, note that, if π((st, 0), t) = at for all t ∈ {0, . . . , T − 1}, then ōπ(τ) = o(τ) matches the outcome of the observed realization.
ALGORITHM 1: It samples a counterfactual explanation from the counterfactual policy π Input: counterfactual policy π, horizon T , counterfactual transition probability Pτ , reward function R,
initial state s0. s′0 ← s0 l0 ← 0 reward← 0 for t = 0, . . . , T − 1 do
a′t ← π((s′t, lt), t) reward← reward +R(s′t, a′t) if t 6= T − 1 then
s′t+1 ∼ Pτ,t(St+1 |St = s′t, At = a′t) if a′t 6= at then
lt+1 ← lt + 1 else
lt+1 ← lt end
end end τ ′ ← {((s′t, lt), a′t)}T−1t=0 o(τ ′)← reward Return τ ′, o(τ ′)
Then, our goal is to find the optimal counterfactual policy π∗τ that maximizes the counterfactual outcome subject to a constraint on the number of counterfactual actions that can differ from the observed ones, i.e.,
maximize π ōπ(τ) subject to T−1∑ t=0 1[at 6= a′t] ≤ k ∀τ ′ ∼ P+τ (7)
where a′1, . . . , a ′ T−1 is one realization of counterfactual actions and a1, . . . , aT−1 are the observed actions. The constraint guarantees that any counterfactual action sequence induced by the counterfactual transition probability P+τ and the counterfactual policy π can differ in at most k actions from the observed sequence. Finally, once we have found the optimal policy π∗τ , we can sample a counterfactual realization of the process and the optimal counterfactual explanation using Algorithm 1.

heading: 4 Finding Optimal Counterfactual Explanations via Dynamic Programming
text: To solve the problem defined by Eq. 7, we break the problem into several smaller sub-problems. Here, the key idea is to compute the counterfactual policy values that lead to the optimal counterfactual outcome recursively by expanding the expectation in Eq. 6 for one time step.
We start by computing the highest average cumulative reward h(s, r, c) that one could have achieved in the last r steps of the decision making process, starting from state ST−r = s, if at most c actions had been different to the observed ones in those last steps. For c > 0, we proceed recursively:
h(s, r, c) = max ( R(s, aT−r) +
∑ s′∈S Pτ,T−r(s ′ | s, aT−r)h(s′, r − 1, c),
max a∈A : a 6=aT−r
[ R(s, a) +
∑ s′∈S Pτ,T−r(s ′ | s, a)h(s′, r − 1, c− 1)
]) , (8)
and, for c = 0, we trivially have that: h(s, r, 0) = R(s, aT−r) + ∑ s′∈S Pτ,T−r(s ′ | s, aT−r)h(s′, r − 1, 0), (9)
with s ∈ S, r ∈ {1, . . . , T}, c ∈ {1, . . . , k}, and h(s, 0, c) = 0 for all s and c. In Eq. 8, the first parameter of the outer maximization corresponds to the case where, at time T − r, the observed action aT−r is taken and the second parameter corresponds to the case where, instead of the observed action, the best alternative action is taken.
ALGORITHM 2: It returns the optimal counterfactual policy and its average counterfactual outcome Input: States S, actions A, realization τ , horizon T , counterfactual transition probability Pτ , reward
function R, constraint k. Initialize: h(s, r, c)← 0, s ∈ S, r = 0, . . . , T, c = 0, . . . , k. for r = 1, . . . , T do
for s ∈ S do h(s, r, 0)← R(s, aT−r) ; /* Base cases: No action changes left (Eq. 9) */ for s′ ∈ S do
h(s, r, 0)← h(s, r, 0) + Pτ,T−r(s′ | s, aT−r)h(s′, r − 1, 0) end π∗τ ((s, k), T − r)← aT−r ; /* Take the observed action */
end end for r = 1, . . . , T do
for c = 1, . . . , k do for s ∈ S do
reward← R(s, aT−r) ; /* Compute the first part of Eq. 8 */ for s′ ∈ S do
reward← reward + Pτ,T−r(s′ | s, aT−r)h(s′, r − 1, c) end best_reward← reward best_action← aT−r for a ∈ A \ {aT−r} do
reward_alt← R(s, a) ; /* Compute the second part of Eq. 8 */ for s′ ∈ S do
reward_alt← reward_alt + Pτ,T−r(s′ | s, a)h(s′, r − 1, c− 1) end if reward_alt > best_reward then
best_reward← reward_alt best_action← a
end end h(s, r, c)← best_reward π∗τ ((s, k − c), T − r)← best_action ; /* Take the action maximizing Eq. 8 */
end end
end Return π∗τ , h(s0, T, k)
By definition, we can easily conclude that h(s0, T, k) is the average counterfactual outcome of the optimal counterfactual policy π∗τ , i.e., the objective value of the solution to the optimization problem defined by Eq. 7, and we can recover the optimal counterfactual policy π∗τ by keeping track of the action chosen at each recursive step in Eq. 8 and 9. The overall procedure, summarized by Algorithm 2, uses dynamic programming—it first computes the values h(s, 1, c) for all s and c and then proceeds with the rest of computations in a bottom-up fashion—and has complexityO(n2mTk). Finally, we have the following proposition (proven by induction in Appendix B):
Proposition 1 The counterfactual policy π∗τ returned by Algorithm 2 is the solution to the optimization problem defined by Eq. 7.

heading: 5 Experiments on Synthetic Data
text: In this section, we evaluate Algorithm 2 on realizations of a synthetic decision making process2. To this end, we first look into the average outcome improvement that could have been achieved if at most k actions had been different to the observed ones in every realization, as dictated by the optimal counterfactual policy. Then, we investigate to what extent the level of uncertainty of the decision making process influences the average counterfactual outcome achieved by the optimal counterfactual policy as well as the number of distinct counterfactual explanations it provides.
2 All experiments were performed on a machine equipped with 48 Intel(R) Xeon(R) 3.00GHz CPU cores and 1.5TB memory.
Experimental setup. We characterize the synthetic decision making process using an MDP with states S = {0, . . . , n− 1} and actions A = {0, . . . ,m− 1}, where n = 20 and m = 10, and time horizon T = 20. For each state s and action a, we set the immediate reward equal to R(s, a) = s, i.e., the higher the state, the higher the reward. To set the values of the transition probabilities P (St+1 |St = st, At = at), we proceed as follows. First we pick one s? ∈ S uniformly at random and we set a weight ws? = 1 and then, for the remaining states s ∈ S \ s?, we sample weights ws ∼ U [0, α], where α ≤ 1. Next, for all s ∈ S, we set P (St+1 = s |St = st, At = at) = ws/ ∑ s′∈S ws′ . It is easy to check that, for each state-action pair (st, at) at time t, st+1 = s
? is most likely to be observed in the next timestep t+ 1. The parameter α controls the level of uncertainty.
Then, we compute the optimal policy that maximizes the average outcome of the decision making process by solving Bellman’s equation using dynamic programming [21] and use this policy to sample the (observed) realizations as follows. For each realization, we start from a random initial state s0 ∈ S and, at each time step t, we pick the action indicated by the optimal policy with probability 0.95 and a different action uniformly at random with probability 0.05. This leads to action sequences that are slightly suboptimal in terms of average outcome3. Finally, to compute the counterfactual transition probability Pτ,t for each observed realization τ , we follow the procedure described in Section 2 with d = 1,000 samples for each noise posterior distribution4.
Results. We first measure to what extent the counterfactual explanations provided by the optimal counterfactual policy π∗τ would have improved the outcome of the decision making process. To this end, for each observed realization τ , we compute the relative difference between the average
3We introduce this randomization to emulate slightly suboptimal (human) policies. However, note that an observed action sequence may be suboptimal in retrospect even if it was picked using an optimal policy.
4For the estimation of the counterfactual transition probabilities Pτ of a single realization τ , we report an average execution time of 62 seconds.
optimal counterfactual outcome and the observed outcome, i.e., (ōπ∗τ (τ) − o(τ))/o(τ). Figure 2 summarizes the results for different values of k. We find that the relative difference between the average counterfactual outcome and the observed outcome is always positive, i.e., the sequence of actions specified by the counterfactual explanations would have led the process realization to a better outcome in expectation. However, this may not come as a surprise given that the counterfactual policy π∗τ is optimal, as shown in Proposition 1. In this context, note that, in the worst case, the counterfactual policy π∗τ would trivially repeat the observed action sequence, leading to an average counterfactual outcome equal to the observed outcome with probability 1. Moreover, we observe that, as the sequences of actions specified by the counterfactual explanations differ more from the observed actions (i.e., k increases), the improvement in terms of expected outcome increases.
Next, we investigate how the level of uncertainty α of the decision making process influences the average counterfactual outcome achieved by the optimal counterfactual policy π∗τ as well as the number of distinct counterfactual explanations π∗τ provides. Figure 3 summarizes the results, which reveal several interesting insights. As the level of uncertainty α increases, the average counterfactual outcome decreases, as shown in panel (a), however, the relative difference with respect to the observed outcome increases, as shown in panel (b). This suggest that, under high level of uncertainty, the counterfactual explanations may be more valuable to a decision maker who aims to improve her actions over time. However, in this context, we also find that, under high levels of uncertainty, the number of distinct counterfactual explanations increases rapidly with k. As a result, it may be preferable to use relatively low values of k to be able to effectively show the counterfactual explanations to a decision maker in practice.

heading: 6 Experiments on Real Data
text: In this section, we evaluate Algorithm 2 using real patient data from a series of cognitive behavioral therapy sessions. Similarly as in Section 5, we first measure the average outcome improvement that could have been achieved if at most k actions had been different to the observed ones in every therapy session, as dictated by the optimal counterfactual policy. Then, we look into individual therapy sessions and showcase how Algorithm 2, together with Algorithm 1, can be used to highlight specific patients and actions of interest for closer inspection5. Appendix D contains additional experiments benchmarking the optimal counterfactual policy against several baselines6.
Experimental setup. We use anonymized data from a clinical trial comparing the efficacy of hypnotherapy and cognitive behavioral therapy [25] for the treatment of patients with mild to moderate symptoms of major depression7. In our experiments, we use data from the 77 patients who received manualized cognitive behavioral therapy, which is one of the gold standards in depression treatment. Among these patients, we discard four of them because they attended less than 10 sessions. Each patient attended up to 20 weekly therapy sessions and, for each session, the dataset contains the theme of discussion, chosen by the therapist from a pre-defined set of themes (e.g., psychoeducation, behavioural activation, cognitive restructuring techniques). Additionally, a severity score is included, based on a standardized questionnaire [27], filled by the patient at each session, which assesses the severity of depressive symptoms. For more details about the severity score and the pre-defined set of discussion themes refer to Appendix C.
To derive the counterfactual transition probability for each patient, we start by creating an MDP with n = 5 states and m = 11 actions. Each state s ∈ S = {0, . . . , 4} corresponds to a severity score, where small numbers represent lower severity, and each action a ∈ A corresponds to a theme from the pre-defined list of themes that the therapists discussed during the sessions. Moreover, each realization of the MDP corresponds to the therapy sessions of a single patient ordered in chronological order and time horizon T ∈ {10, . . . , 20} is the number of therapy sessions per patient. Here, we denote the set of realizations for all patients as T . In addition, to estimate the values of the transition probabilities, we proceed as follows. For every state-action pair (si, a), we assume a n-dimensional Dirichlet(αi1, . . . , αi1) prior on the probabilities pj | i,a = P (St+1 = sj |St = si, At = a), where αij = 1 if j ∈ {i − 1, i, i + 1}
5Our results should be interpreted in the context of our modeling assumptions and they do not suggest the existence of medical malpractice.
6We do not evaluate our algorithm against prior work on counterfactual explanations for one-step decision making processes since the settings are not directly comparable.
7All participants gave written informed consent and the study protocol was peer-reviewed [26].
and αij = 0.01 otherwise. Then, if we observe cj transitions from state si to each state sj after action a in the patients’ therapy sessions T , we have that the posterior of the probabilities pj | i,a is a Dirichlet(αi1 + c1, . . . , αin + cn). Finally, to estimate the value of the transition probabilities P (St+1 |St = si, At = a), we take the average of 100,000 samples from the posterior probability pj | i,a. This procedure sets the value of the transition probabilities proportionally to the number of times they appeared in the data, however, it ensures that all transition probability values are non zero and transitions between adjacent severity levels are much more likely to happen. Moreover, we set the immediate reward for a pair of state and action (s, a) equal to R(s, a) = 5− s ∈ {1, . . . , 5}, i.e., the lower the patient’s severity level, the higher the reward. Here, if some state-action pair (s, a) is never observed in the data, we set its immediate reward to R(s, a) = −∞. This ensures that those state-action pairs never appear in a realization induced by the optimal counterfactual policy. Finally, to compute the counterfactual transition probability Pτ,t for each realization τ ∈ T , we follow the procedure described in Section 2 with d = 1,000 samples for each noise posterior distribution.
Results. We first measure to what extent the counterfactual explanations provided by the optimal counterfactual policy π∗τ would have improved each patient’s severity of depressive symptoms over time. To this end, for each observed realization τ ∈ T corresponding to each patient, we compute the same quality metrics as in experiments on synthetic data in Section 5. Figure 4 summarizes the results. Panel (a) reveals that, for most patients, the improvement in terms of relative difference between the average optimal counterfactual outcome ōπ∗τ (τ) and the observed outcome o(τ) is rather modest. Moreover, panel (b) also shows that the absolute average optimal counterfactual outcome ōπ∗τ (τ), averaged across patients, does not increase significantly even if one allows for more changes k in the sequence of observed actions. These findings suggest that, in retrospect, the choice of themes by most therapists in the sessions was almost optimal. That being said, for 20% of the patients, the average counterfactual outcome improves a ≥3 % over the observed outcome and, as we will later discuss, there exist individual counterfactual realizations in which the counterfactual outcome improves much more than 3%. In that context, it is also important to note that, as shown in panel (c), the growth in the number of unique counterfactual explanations with respect to k is weaker than the growth found in the experiments with synthetic data and, for k ≤ 4, the number of unique counterfactual explanations is smaller than 10. This latter finding suggests that, in practice, it may be possible to effectively show, or summarize, the optimal counterfactual explanations, a possibility that we investigate next.
We focus on a patient for whom the average counterfactual outcome ōπ∗τ (τ) achieved by the optimal policy π∗τ with k = 3 improves 9.5% over the observed outcome o(τ). Then, using the policy π ∗ τ , also with k = 3, and the counterfactual transition probability Pτ , we sample multiple counterfactual explanations τ ′ using Algorithm 1 and look at each counterfactual outcome o(τ ′). Figure 5(a) summarizes the results, which show that, in most of these counterfactual realizations, the counterfactual outcome is greater than the observed outcome—if at most k actions had been different to the observed
40 45 50
Counterfactual outcome
0.0
0.1
0.2
0.3
P ro
b ab
il it
y
Observed outcome Avg. counterfactual
(a) P[o(τ ′)]
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
Frequency of action changes per time step
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
Observed severity level per time step
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
Best counterfactual severity level per time step
(b) Action changes, severity vs. t (c) Unique explanations
Figure 5: Insights on the counterfactual explanations provided by the optimal counterfactual policy π∗τ for one real patient who received manualized cognitive behavioral therapy. Panel (a) shows the distribution of the counterfactual outcomes o(τ ′) for the counterfactual realizations τ ′ induced by π∗τ and Pτ . Panel (b) shows, for each time step, how frequently a counterfactual explanation changes the observed action as well as the observed severity level and the severity level in the counterfactual realization with the highest counterfactual outcome. Here, darker colors correspond to higher frequencies and higher severities. Panel (c) shows the action changes in the unique counterfactual explanations (green) provided by π∗τ along with the mean of counterfactual outcomes (r) that each one achieves and how frequently (f) they appear across the counterfactual realizations. Here, the bottom row shows the observed actions that were changed by at least one of the counterfactual explanations. Refer to Appendix C for a definition of the actions (i.e., themes). In all panels, we set d = 1,000 and the results are estimated using 1,000 counterfactual realizations.
ones, as dictated by the optimal policy, there is a high probability that the outcome would have improved. Next, we investigate to what extent there are specific time steps within the counterfactual realizations τ ′ where π∗τ is more likely to suggest an action change. Figure 5(b) shows that, for the patient under study, there are indeed time steps that are overrepresented in the optimal counterfactual explanations, namely t ∈ {10, 13, 16}. Moreover, the first of these time steps (t = 10) is when the patient had started worsening their depression after an earlier period in which they showed signs of recovery. Remarkably, we find that, in the counterfactual realization τ ′ with the best counterfactual outcome, the worsening is mostly avoided. Finally, we look closer into the actual action changes suggested by the optimal counterfactual policy π∗τ . Figure 5(c) summarizes the results, which reveal that π∗τ recommends replacing some of the sessions on cognitive restructuring techniques (CRT) by behavioral activation (BHA) consistently across counterfactual realizations τ ′, particularly at the start of the worsening period. We discussed this recommendation with one of the researchers on clinical psychology who co-authored Fuhr et al. [25] and she told us that, from a clinical perspective, such recommendation is sensible since, whenever the severity of depressive symptoms is high, it is very challenging to apply CRT and instead it is quite common to use BHA. Appendix F contains additional insights about other patients in the dataset.

heading: 7 Conclusions, Limitations and Future Work
text: We have initiated the study of counterfactual explanations in decision making processes in which multiple, dependent actions are taken sequentially over time. Building on a characterization of sequential decision making processes using MDPs and the Gumbel-Max SCM, we have developed a polynomial time algorithm to find optimal counterfactual explanations. Using synthetic and real data from cognitive behavioral therapy, we have shown that the counterfactual explanations our algorithm finds can provide valuable insights to enhance sequential decision making under uncertainty.
Our work opens up many interesting avenues for future work, which may solve some of its limitations. For example, we have considered sequential decision making processes with discrete states and actions satisfying the Markov property. Although this setting may fit a plethora of real-world applications, it would be interesting to extend our work to continuous states and actions and/or semi-Markov processes. Moreover, we experimentally validated our method using a single real dataset. It would be valuable to evaluate counterfactual explanations generated by our algorithm using additional datasets from other (medical) applications. In this context, it would be worth to consider applications in which the true transition probabilities are due to a machine learning algorithm. Finally, the usefulness of the counterfactual explanations given by our algorithm crucially depends on the particular structural causal model we have focused on. To make such explanations more practical, it would be important to consider alternative structural causal models and carry out a user study in which the counterfactual explanations are shared with the human experts (e.g., therapists) who took the observed actions.
Acknowledgements. We would like to thank Kristina Fuhr and Anil Batra for giving us access to the cognitive behavioral therapy data that made this work possible. Tsirtsis and Gomez-Rodriguez acknowledge support from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No. 945719). De has been partially supported by a DST Inspire Faculty Award.

Review summaries:
This paper proposes a novel technique to generate counterfactual explanations for Markov decision processes (MDPs). Technically, it first remodels the state transition of MDPs with a Gumbel-Max structural causal model. Then, it formalizes the counterfactual explanation generation as an optimization problem and proposes an algorithm to generate the explanations. With the experiments on both a synthetic and a real-world dataset, the paper demonstrates the effectiveness of the proposed technique in finetuning a given policy to collect more rewards, especially when the corresponding environments have uncertainties.  

This paper is about counterfactual explanations for Markov decision processes. Instead of the usual counterfactual explanations as "alternative traces which can be used to explain that the chosen (optimal) choices are in fact optimal" as in explainable AI and reinforcement learning (RL), this paper uses them in offline settings, where data is available of the chosen paths, and where potentially better alternatives (counterfactual) can be computed. The main idea is to employ structural causal models to capture the model of the MDP such that better alternatives (here: action sequences that differ at most in k actions) can be computed in that model. The paper features experiments in two domains; one artifical and one in a small (in terms of the model) medical treatment domain. The experiments clearly show the benefits and characteristics of the approach.

The paper proposes a method using Markov decision process and dynamic programming to build alternative sequences with better reward/ outcome. The algorithms used can find optimal counterfactual explanations in polynomial time, testing in both synthetic and real dataset. With different uncertainty (defined manually), optimal counterfactual sequence outperformed the observed one considering the outcome in most cases. Thus the paper validated the contribution in finding the optimal counterfactual sequence in multiple, dependent sequence under discrete and low-dimensional situation.

The paper proposed a novel method to generate counterfactual explanations. The authors view the problem as sequential decision-making processes using Markov decision processes and the Gumbel-Max structural causal model. They discuss an algorithm based on dynamic programming to find optimal CFEs. The model was validated on synthetic and cognitive behavioural therapy datasets.