Counterfactual Explanations in Sequential Decision Making Under Uncertainty
Authors: Stratis Tsirtsis
Abir De
Manuel Gomez Rodriguez
Venue: NeurIPS 2021 Poster (2021)
Keywords: counterfactual explanations
markov decision process
structural causal model
decision making
dynamic programming
explainability

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

Counterfactual Explanations in
Sequential Decision Making Under Uncertainty
Stratis Tsirtsis
Abir De IIT Bombay abir@cse. wit..
Manuel Gomez-Rodriguer MPI-SWS
MPI-SWS
stsirtsiis0ppi-ss.. org
manuelgr@mpi-sss. org
Abstract
Methods find counterfactual explanations have predominantly focused on one- step decision making processes. In this work, initiate the development of methods to find counterfactual explanations for decision making processes 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 problem formulation, the counterfactual explanation specifies an alternative sequence of actions differing in most A 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 build 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.
Introduction
In recent years, there has been a rising interest on the potential of machine learning models assist and enhance decision making in high-stakes applications such as justice, education and healthcare [I- 3. In this context, machine learning models and algorithms have been used not only to predict the outcome of decision making process from set of observable features but also to find what would have change in (some of) the features for outcome specific process realization to change. For example, in loan decisions, 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 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 the one described above 64 In such settings, the probability that an outcome occurs is typically estimated using 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 [4) 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 cxplanation specifies alternative sequence of actions differing in at most k actions from the observed sequence that could have led the process realization to better outcome. For example, in medical treatment, assume physician takes
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

sequence of actions to treat patient but the patient's '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 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. Moreaver, 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 using machine learning to enhance sequential (clinical) decisions [[5] 18. However, rather than finding counterfactual explanations, this line of work has predominantly focused on using reinforcement learning to design better treatment policies. notable exception 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 we see their contributions as complementary to ours.
means of explanation for the process's outcome. Therefore,
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 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 discussion of further related work.
Our contributions. We start by formally characterizing 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 [8. This model has been shown to have a desirable counterfactual stability property and, given sequence of actions and states, it allows us 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 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 uncertainty
2 Characterizing Sequential Decision Making using Causal Markov Decision Processes
Our starting point is the following stylized setting, which resembles variety of real-worle sequential decision making processes. At each time step t E {0,.... T' 1}. the decision making process is characterized by a state s, E S, where S is a space of states, an action a, E A, where A is a space of m actions, and a reward R(s 4:) E R. Moreover, given realization of a decision making process
T = {(, az T-1 TT the outcome of the decision making process o(T) = Σ, R(s az) 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, consider an MDP R,,T), T"), where S is the state space, A is the set of actions, I' denotes the transition probability P(S
M = (S,A, P, P,R,R,
S S. St, A, az), It denotes the immediate reward R(s,, at), and T is the time horizon. While this characterization is helpful to make predictions about future states and design action policies (II. it is not sufficient to make counterfactual predictions, e.g., given realization of a decision making process + {( a,) [=) cannot know what would have
OOur code is accessible at http://siiiinoooaoeeossoeiieieet

---

A
U
U
Figure 1: Structural causal model C for Markov decision process M. Green boxes represent endogenous random variables and pink boxes represent exogenous noise variables. The value of each endogenous variable is given by function of the values of its ancestors in the structural causal model, as defined by Eq. [ The value of each exogenous noise variable is sampled independently from given distribution. An intervention do(A, a) breaks the dependence of the variable A, from its ancestors (highlighted by dotted lines) and sets its value to a. After observing an event S St+1, St St, A, dg. a counterfactual prediction can be thought of as the result of an intervention do(A, A, = a) in a modified SCM where U, takes values u, from a posterior distribution with support such that 1 (5t; Or, Ut).
happened if, instead of taking action a at time we had taken action a' * az. To be able to overcome this limitation, we will now augment the above characterization using a particular class of structural with desirable properties.
causal model (SCM) 22 23
Let C be a structural causal model defined by the assignments
S = (s, A,, U+) and A, = (S,, Vi),
where U, and V, are n- and m-dimensional independent noise variables, respectively, and is and SA are two given functions, and let pe be the distribution entailed by C. Then, as argued by Buesing et al. [191, we can always find a distribution for the noise variables and function gs that the transition probability of the MDP of interest given by the following interventional distribution over the SCM C:
P(S++1 = st-1 | S: = St. 4 = az) = pe: do(A.=a:) (St+1 = $t+1 | = 8t)
(2)
where do(A,, = az) denotes a (hard) intervention in which the second assignment in Eq. Dis replaced
by the value az.
Under this view, given an observed realization of a decision making process T = {(s,, ax) a we can compute the posterior distribution pel
(U,) of each noise variable Ur. Building on the conditional density function of this posterior distribution, which we denote as
JU.
St
(u), we can define (non-stationary) counterfactual transition probability
(S s' s'1S, 8, A,- a) = p S141 #8:41 AA do(A, =a) (S1+1 =s S:
pel St
do(A (S = =s s'SS = 8, U. = u.)
R"
JU, S1 do(A:=a) (u)du
1 = gs a, u)] J S1 (u)du
(3) where, in (a), we drop the do(-) because U, and A, are independent in the modified SCM. Importantly, the above counterfactual transition probability allows us to make counterfactual predictions, e.g., given that, at time the state was st and, at time + 1, the process transitioned state 8t+1 after taking action ag, what would have been the probability of transitioning to state s' after taking action a * ag if the state had been s time t. Refer to Figure for visual description of our model and the notion of counterfactual predictions.
EU. SS S.41 S
[|s gs a, U.]]].
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 [8]. 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.,
S = gs A., U.) == argmax flog P(S =1 St, A.) + Un,)): SES
(4)
3

---

where Ut., ~ G0mbel(O. 1) and S(. At) is the transition probability of the MDP. More specifi- cally, this class of SCMs has been shown to satisfy desirable counterfactual stability property, which goes intuitively as follows. Assume that, at time I. the process transitioned from state to state Sc+1 after taking action a;- Then, a counterfactual scenario, it is unlikely that, at time f, the process would transition from a state s to a state s' other than s,+1- the factual one one-unless choosing an action a that decreases the relative chances of $141 compared to the other states. More formally, for a model satisfying counterfactual stability, given T {(st, (r) 3 for all 8, s' with s' + 8141 such that
P(S 8 |s 8, A, a) P(S[+1= = 5 St = St, A. = an) P(S = S St, A, az)
P(S++1 = 81+1 S: 8, A, = a)
z
holds that (S = s'| s, 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 pel S;=st 11.Aca 1. (Uz), described elsewhere [8 [4]] 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:
Pr.1S = = A, = a) =
E1ss' = 9s(s, a, uz)]
(5)
d
%E/d
3 Counterfactual Explanations in Markov Decision Processes
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, will look for 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 & actions from the observed one.
More specifically, let r = {(st, T be an observed realization of a decision making process characterized by a Markov decision process (MDP) M = (S, A, P, R, 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 non-stationary counterfactual MDP M, R+ (S+ A, P .T) Here, S+ = x {o..... T 1} is an enhanced state space such that each pair (s, () indicating that the original decision making process would have
st E S corresponds been at state s E S had already taken actions differently from the observed sequence. Following this definition, R+ denotes the reward function which any (s, E S and a E 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. Then, the transition probability P for the enhanced state space is defined as:
define as r+ ((s. I). a) R(s, a) for
Pr. (S = S = =, A, = a) if (a= = a; A II (a
pt (st (8'1') = (8,1),
otherwise,
where note that the dynamics of the original states s are equivalent both under P and Pr,.. however, under T.* we also keep track of the number of actions differing from the observed actions. Now, let S+ x {O...., T 1} A be a policy that deterministically decides about the counterfactual action of that should have been taken if the process's 's enhanced state had been x; (s/, 4t), i.e., the counterfactual state at time was sy after performing I action changes. Then, given such a counter- factual policy π, we can compute the corresponding average counterfactual outcome as follows:
ox (T) = E.inp! 10) (<a.0)
Σ ((+))))))))))
(6)
where r'= (((((( (()
is a realization of the non-stationary counterfactual MDP Mr with af = 7(66/ 46), !) and the expectation is taken over all the realizations induced by the transition probability Pff and the policy æ. Here, note that, if (( 0), () = o, for all & E (O...., 1}.
then o, (T) o(T) matches the outcome of the observed realization.

---

ALGORITHM I: It samples a counterfactual explanation from the counterfactual policy π
Input: counterfactual policy π, horizon 7, counterfactual transition probability Pr, reward function R.
initial state
5 90
< 0
reward + 0
for = -0..., -1
d (($),(1),t)
reward reward R(s). at)
if * 7 then
8+1 (S Ss = 5/, A, o!))
if a 4+1 11 +
then
else
4+1
end
end end
+ ((.),)))
o(r') < reward Return o()
Then, our goal is to find the optimal counterfactual policy के that maximizes the counterfactual outcome subject to constraint on the number of counterfactual actions that can differ from the observed ones, ie.,
maximize
oz (T)
subject
E 1a, + dd)s VT P
where ai. - is one realization of counterfactual actions and (i,..., 0T-1 are the observed ac- tions. The constraint guarantees that any counterfactual action sequence induced by the counterfactual transition probability P+ and the counterfactual policy т can differ in at most actions from the ob- served sequence. Finally, once we have found the optimal policy n, can sample counterfactual realization of the process and the optimal counterfactual explanation using Algorithm [
4 Finding Optimal Counterfactual Explanations via Dynamic Programming
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. for one time step.
We start by computing the highest average cumulative reward h(s, e) that one could have achieved in the last steps of the decision making process, starting from state ST s, if at most c actions had been different to the observed ones in those last steps. For e > O, we proceed recursively:
h(s,r,c) max
R [(s, P.rrrr(s 18.0-16111.000-,)666,, -L,e),
N'ES
-. 1I)- (8)
R(s,a) + Pri-r (,a)((sss -0
max aEA: :afarr
s'ES
and, for c= 0, we trivially have that:
11(, = R(s, Σ
8, - 500 1,0),
E'ES
with & E S, E (I..... T). (1....,) k), and h(s,, 0, = for s and e. In Eq. the first
parameter of the outer maximization corresponds to the case where, at time T - the observed action ar- is taken and second parameter corresponds to the case where, instead of the observed action, the best alternative action is taken.
5

---

ALGORITHM 2: It returns the optimal counterfactual policy and its average counterfactual outcome
Input: States S, actions A, realization т, horizon T, counterfactual transition probability Pr, reward function R. constraint k.
Initialize: h(,, <- =E
o....,k.
I.....T for E do r)), t- R(s, ar-r);
/+ Base cases: No action changes left (Eq. 9 */
for E do r,s, < ((8,T,0) + Pr.--(('
1,0)
end
(; k),
ar-ri
/- Take the observed action */
end end
do for c 1, I...., do
for s E S do
reward H(s, aT ar-r):
/+ Compute the first part of Eq.
for s' E do
reward reward Pr (8, 8,0r-r)((s,, 1, end
reward <- reward
best_ action f- dr-r for E A {ar-r] ) do
reward alt + R(s
/+ Compute the second part of Eq-
*/
for E do
| reward alt + reward alt + P. as a))((' 1,c-1) 1) end
if reward all best reward then best_reward reward_alt
action <-
end end
h( ,. ((s, c), -) f- best_action;
Take action maximizing Eq.
end
end
end
Return 1i,, T.k)
By definition, we can easily conclude that h(sp. T, is the average counterfactual outcome of the optimal counterfactual policy a;, 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. and The overall procedure, summarized by Algorithm uses dynamic programming- it first computes the values fi(s, 1, c) for all and e and then proceeds with the rest of computations in a bottom-up fashion- and has complexity mīT'mTKk). Finally, we have the following proposition (proven by induction Appendix B
The counterfactual policy n returned by Algorithm 2 is the solution to the optimiza- tion problem defined by Eq. 7
Proposition 1
5 Experiments on Synthetic Data
In this section, we evaluate Algorithm 2 realizations of synthetic decision making process To this end, we first look into the average outcome improvement that could have been achieved if at most & actions had been different to the observed ones in every realization, 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 machine equipped with 48 Intel(R) Xeon(R) 3.00GHz CPU cores and 1.STB memory.

---

60
93 15 2005 oxcsterfaattall
506E
15.8
500
factaal Iegenweceet
2
(h) k
(c) k 10
Figure 2: Empirical distribution of the relative difference between the average counterfactual out- come On; (T) achieved by the optimal counterfactual policy & and the observed outcome o(T). i.e.
P( (7) - ((T))//(TT) in synthetic decision making process. In all panels, we set 20, m = 10, a = 0.4, d = 1,000 and estimate the distributions using 500 realizations from 10 different instances of the decision making process (50 realizations per instance), each with different W.
3300
0.00
Avee coontecbortall
00%5
CURI
D.01
300
250
0.50
355
of unii
1.00
255
0.0
0.2
0.4
0.0
(a) E.y (ox; (T) vs. A
(b) IB, [Gx; (r) o(T))/((r) vs. (c) # of uniq. explanations vs. &
Figure 3: Influence that the level of uncertainty of a synthetic decision making process has on the average counterfactual outcome (T) achieved by the optimal counterfactual policy "F well as on the number of distinct counterfactual explanations x; provides. In all panels, we set n = 20, m 10 and d 1,000 and, in each experiment, use 500 realizations from 10 different instances of the decision making process (50 realizations per instance), each with different w. In panel (c), for each realization, we sample 100 counterfactual realizations and compute the average number of unique explanations across realizations. Shaded regions correspond to 95% confidence intervals.
Experimental setup. We characterize the synthetic decision making process using an MDP with states $ = (O....,2 n 1} and actions AA = (o,..., m - 1}. where n = 20 and m = 10, and time horizon T = 20. For each state 8 and action a, 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(S S. = St, A = de), we proceed follows. First we pick one s* S uniformly random and we set a weight w,- = 1 and then, for the remaining states E S \ s*, we sample weights w. ~ U00 a). where a I 1. Next, for all s S, we set P(S w./Eves Eves Wyr is easy to check that, for each state-action pair (st, az) ) at time t. St41 s* is most likely to observed in the next timestep + The parameter a controls the level of uncertainty.
s S = St, Ar 0e) =
Then, we compute the optimal policy that maximizes the average outcome of the decision making process by solving Bellman's equation using dynamic programming (2] and use this policy sample the (observed) realizations as follows. For each realization, we start from a random initial state so S and, at each time step f, 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 o Finally, compute the counterfactual transition probability Pr. for each observed realization we follow the procedure described in Section 2 with d = 1,000 samples for each noise posterior distribution F
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
We introduce this randomization to emulate slightly suboptimal (human) policies. However, note that an observed action sequence may be suboptimal retrospect even it was picked using an optimal policy. 'For the estimation of the counterfactual transition probabilities P. of a single realization 7, we report an average execution time of 62 seconds.
7

---

optimal counterfactual outcome and the observed outcome, i.e., (Tr: - ooT)) Figure 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 surprise given that the counterfactual policy π. is optimal, as shown in Proposition] [ In this context, note that, in the worst case, the counterfactual policy ,, would trivially repeat the observed action sequence, leading an average counterfactual outcome equal to the observed outcome with probability 1. Moreover, we observe that, the sequences of actions specified by the counterfactual explanations differ more from the observed actions (i.e., I increases), the improvement in terms of expected outcome increases.
Next, we investigate how the level of uncertainty a of the decision making process influences the average counterfactual outcome achieved by the optimal counterfactual policy n. 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 a increases, the average counterfactull 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 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 & to be able to effectively show the counterfactual explanations to decision maker in practice.
6 Experiments on Real Data
In this section, we evaluate Algorithm 2 using real patient data from a series of cognitive behavioral therapy sessions. Similarly as in Section []
we first measure the average outcome improvement that could have been achieved if at most & 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 A together with Algorithm| [ can be used to highlight specific patients and actions of interest for closer inspection[] Appendix D contains additional experiments benchmarking the optimal counterfactual policy against several baselines
Experimental setup. We anonymized data from clinical trial comparing the efficacy of hyp- notherapy and cogmitive behavioral therapy (25) for the treatment of patients with mild to moderate symptoms of major d 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 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 5 states and m 11 actions. Each state s E S = {0.... .., 4} corresponds where small numbers represent lower severity, and each action a E 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 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.
severity score,
In addition, to estimate the values of the transition probabilities, we proceed follows. For every state-action pair (s,, a), we assume a n-dimensional Dirichlet(a:1, am) prior on the probabilities Pj i. P(S = sj S. Si, A, =),, where aij 1 jf E {i i, 1}
*Our results should be interpreted in the context of our modeling assumptions and they do not suggest the existence of medical malpractice.
"We do not evaluate our algorithm against prior work on counterfactual explanations for one-step decision making processes since the settings are not directly comparable.
All participants gave written informed consent and the study protocol was peer-reviewed 26
8

---

Armma wwstedaatrall
66-
03
8f oito
2012 27%
(a) (7)
(b)
1 Σ+e7 Ouz (T) vs. k
(c) # of uniq. explanations &
[7]
Figure Performance achieved by the optimal counterfactual policy प. in a series of real manualized cognitive behavioral therapy sessions T, where each realization E includes all the sessions of an individual patient sorted in chronological order. Panel (a) shows the distribution of the relative difference between the average counterfactual outcome ox; (T) achieved by गτ. and the observed outcome o(T), i.e., (Om; (T) - o(T)), for k = 3 (refer to Appendix E for additional results under other h values). Panels (b) and (c) show the average counterfactual outcome ox; (T) achieved by ग and the average number of unique counterfactual explanations provided by each πT. averaged across patients, against the number of actions k differing from the observed ones. In panel (c), for each realization, the average number of unique counterfactual explanations provided by ", is estimated using 1, 1,000 counterfactual realizations. In all panels, we set d = 1,000 and use data from 73 patients. Shaded regions correspond 95% confidence intervals.
and 0gj 0.01 otherwise. Then, if we observe ej transitions from state 8; each state 8j after action a in the patients' therapy sessions TT, we have that the posterior of the probabilities Py s.o is a Dirichlet(aaa + +1 CI.... Onnn + c,). Finally, to estimate the value of the transition probabilities P(S St St, A, = a), Pyli, 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 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 E {1,..., 5), iee, the lower the patient's s severity level, the higher the reward. Here, if some state-action pair (s, a) is never observed in the data, set its immediate reward to R(s,a) state-action pairs never appear in a realization induced by the optimal counterfactual policy. Finally, to compute the counterfactual transition probability Pr. for each realization T. we follow the procedure described in Section with d = 1,000 samples for each noise posterior distribution.
take the average of 100,000 samples from the posterior probability
-o. This ensures that those
Results. We first measure to what extent the counterfactual explanations provided by the optimal counterfactual policy क would have improved each patient's 's severity of depressive symptoms over time. To this end, for each observed realization E T corresponding to each patient, we compute the same quality metrics as in experiments on synthetic data in Section 5 summariiss the results. Panel (a) reveals that, for most patients, the improvement in terms of relative difference between the average optimal counterfactual outcome 0z.: (T) and the observed outcome o(T) is rather modest. Moreover, panel (b) also shows that the absolute average optimal counterfactual outcome o,; (T). averaged across patients, does not increase significantly even if one allows for more changes A 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 23 % 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 < 4, the number of unique counterfactual explanations is smaller than 10. This latter finding suggests that, in practice, it may be possible effectively show, or summarize, the optimal counterfactual explanations, a possibility that we investigate next.
We focus patient for whom the average counterfactual outcome ã (r) achieved by the optimal policy ग. with k 3 improves 9.5% over the observed outcome o(T). Then, using the policy x;, also with A: = 3, and the counterfactual transition probability P,, we sample multiple counterfactual explanations r' using Algorithm [ and look at each counterfactual outcome o(7'). Figure 5 a) sum- marizes the results, which show that, in most of these counterfactual realizations, the counterfacual outcome is greater than the observed outcome- if at most & actions had been different to the observed

---

113
Uherred ornonce Arg. enstorfactall
Lenyaracy aetice
0.2
Obereed aonityy kodi pe: thass stop
ISAA
0.1
5
MIRR 12 15
REV
Bist contiee Dral cncvity level per trae step
CIT EMM
Quanniciaditall
OFF
ERT
CKT
CII
RFP
(a) P(o(T')]
(b) Action changes, severity vs. (c) Unique explanations
Figure 5: Insights on the counterfactual explanations provided by the optimal counterfactual policy T for one real patient who received manualized cognitive behavioral therapy. Panel (a) shows the distribution of the counterfactual outcomes o(T') for the counterfactual realizations r' induced by m and P.. Panel (b) shows, for each time step, how frequently a counterfactual explanation changes the observed action 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 Appendix [oror 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 what extent there are specific time steps within the counterfactual realizations r' where पæ is more likely to suggest an action change. Figure b) shows that, for the patient under study, there are indeed time steps that are overrepresented in the optimal counterfactual explanations. namely t E {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 r' 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 म. FigureBjer summarizes the results, which reveal that गF recommends replacing some of the sessions on cognitive restructuring techniques (CRT) by behavioral activation (BHA) consistently across counterfactual realizations T', 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, 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.
7 Conclusions, Limitations and Future Work
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 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 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.
10

---

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 's Horizon 2020 research and innovation programme (grant agreement No. 945719). De has been partially supported by DST Inspire Faculty Award.
References
[1] Jon Kleinberg, Himabindu Lakkaraju, Jure Leskovec, Jens Ludwig, and Sendhil Mullainathan. Human decisions and machine predictions. The quarterly journal of economics, 133(1):237-295 2018.
[2] Xiaojin Zhu. Machine teaching: An inverse problem machine learning and approach toward optimal education. In Proceedings of the AAAI Conference on Artificial Intelligence, 2015.
[3] Muhammad Aurangzeb Ahmad, Carly Eckert, and Ankur Teredesai. Interpretable machine learn- ing in healthcare. In Proceedings of the 2018 ACM international conference on bioinformatics, computational biology, and health informatics, pages 559-560, 2018.
[4] Sahil Verma, John Dickerson, and Keegan Hines. Counterfactual explanations for machine learning: A review. arXiv preprint arXiv:2010.. 10596, 2020.
[5] Amir-Hossein Karimi, Gilles Barthe, Bernhard Schölkopf, and Isabel Valera. A survey of algorithmic recourse: definitions, formulations, solutions, and prospects. arXiv preprint arXiv:2010.04050, 2020.
[6] Ilia Stepin, Alonso, Alejandro Catala, and Martín Pereira-Fariña. survey of contrastive and counterfactual explanation generation methods for explainable artificial intelligence. IEEE Access, 9: 1974-1 2021.
[7] Sandra Wachter, Brent Mittelstadt, and Chris Russell. Counterfactual explanations without opening the black box: Automated decisions and the gdpr. Harv. JL & Tech., 31:841, 2017.
[8] Berk Ustun, Alexander Spangher, and Yang Liu. Actionable recourse in linear classification. In Proceedings of the Conference on Fairness, Accountability, and Transparency, pages 10-19, 2019.
[9] Amir-Hossein Karimi, Gilles Barthe, Borja Balle, and Isabel Valera. Model-agnostic coun- terfactual explanations for consequential decisions. In International Conference on Artificial Intelligence and Statistics, pages 895-905. PMLR, 2020.
[10] Ramaravind K Mothilal, Amit Sharma, and Chenhao Tan. Explaining machine learning classifiers through diverse counterfactual explanations. In Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency, pages 607-617, 2020.
[11] Kaivalya Rawal and Himabindu Lakkaraju. Beyond individualized recourse: Interpretable and interactive summaries of actionable recourses. Advances in Neural Information Processing Systems, 33, 2020.
[12] Amir-Hossein Karimi, Julius von Kügelgen,, Bernhard Schölkopf, and Isabel Valera. Algorithmic recourse under imperfect causal knowledge: probabilistic approach. In Advances in Neural Information Processing Systems, volume 33, pages 265-277, 2020.
[13] Amir-Hosseff Karimi, Bernhard Schölkopf, and Isabel Valera. Algorithmic recourse: from counterfactual explanations to interventions. In Proceedings of the 2021 ACM Conference on
Fairness, Accountability, and Transpurency, pages 353-362, 2021.
[14] Stratis Tsirtsis and Manuel Gomez Rodriguez. Decisions, counterfactual explanations and strategic behavior. In Advances in Neural Information Processing Systems, volume 33, pages 16749-16760, 2020.
[15] Sonali Parbhoo, Jasmina Bogojeska, Maurizio Zazzi, Volker Roth, and Finale Doshi- Velez. Combining kernel and model based learning for hiv therapy selection. AMIA Summits on Translational Science Proceedings, 2017:239, 2017.
[16] Arthur Guez, Robert D Vincent, Massimo Avoli, and Joelle Pineau. Adaptive treatment of epilepsy via batch-mode reinforcement learning. In AAAL, pages 167 1671-1678, 2008

---

[17] Matthieu Komorowski, Leo A Celi, Omar Badawi, Anthony C Gordon, and A Aldo Faisal. The artificial intelligence clinician learns optimal treatment strategies for sepsis in intensive care. Nature medicine, 24(11):171-177)
2018.
[18] Michael Oberst and David Sontag. Counterfactual off-po evaluation with gumbel-max structural causal models. In International Conference on Machine Learning, pages
PMLR, 2019.
[19] Lars Buesing, Theophane Weber, Yori Zwols, Sebastien Racaniere, Arthur Guez, San-Baptiste Lespiau, and Nicolas Heess. Woulda, coulda, shoulda: Counterfactually-gee policy search. arXiv preprint arXiv: /8/ 1.06272, 2018
[20] Prashan Madumal, Tim Miller, Liz Sonenberg, and Frank Vetere. Explainable reinforcement learning through a causal lens. In Proceedings of the AAAI Conference on Artificial Intelligence, 2020.
[21] Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press. 2018.
[22] Judea Pearl. Causality. Cambridge university press, 2009.
[23] Jonas Peters, Dominik Janzing, and Bernhard Schölkopf. Elements of causal inference: founda- tions and learning algorithms. The MIT Press, 2017.
[24] Chris J. Maddison and Danny Tarlow. Gumbel machinery, Jan 2017.
[25] Kristina Fuhr, Cornelie Schweizer, Christoph Meisner, and Anil Batra. Efficacy of hypnotherapy compared to segnitivee-bhaviourre therapy for mild-to-moderate depression: study protocol of a randomised-controolee rater-blind trial (wiki-d). BMJ open, 7(1 7(11):001677,, 2017.
[26] Kristina Fuhr, Christoph Meisner, Angela Broch, Barbara Cyrny, Juliane Hinkel, Joana Jaberg, Monika Petrasch, Cornelie Schweizer, Anette Stiegler, Christina Zeep, al. Efficacy of hypnotherapy compared to cognitive behavioral therapy for mild to moderate depression-resuuls of randomized controlled rater-blind clinical trial. Journal of Affective Disorders, 286:166-173 2021.
[27] Kurt Kroenke, Robert L Spitzer, and Janet BW Williams. The phq-9: validity of a brief depression severity measure. Journal of general internal medicine, 16(9):606-61) 613, 2001.
[28] Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. " why should trust you?" explaining the predictions of any classifier. In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining. pages 1 1135-1144, 2016.
[29] Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions. In International Conference on Machine Learning, pages 1894. PMLR, 2017.
[30] Scott Lundberg and Su-In Lee. A unified approach to interpreting model predictions. arXiv
preprint arXiv:1705. 07874, 2017.
[31] Samuel Greydanus, Anurag Koul, Jonathan Dodge, and Alan Fern. Visualizing and understand- ing atari agents. In International Conference on Machine Learning, pages 1792-1801. PMLR, 2018.
[32] Akanksha Atrey, Kaleigh Clary, and David D. Jensen. Exploratory not explanatory: Counterfac- tual analysis of saliency maps for deep reinforcement learning. In 8th International Conference on Learning Representations, ICLR, 2020.
[33] Nikaash Puri, Sukriti Verma, Piyush Gupta, Dhruv Kayastha, Shripad Deshmukh, Balaji Krish- namurthy, and Sameer Singh. Explain your move: Understanding agent actions using specific and relevant feature attribution. In 8th International Conference on Learning Representations, ICIR, 2020.
[34] Guido W Imbens and Donald B Rubin. Causal inference in statisfics, social, and biomedical sciences. Cambridge University Press, 2015.
[35] Daniel Kasenberg, Ravenna Thielstrom, and Matthias Scheutz. Generating explanations for temporal logic planner decisions. In Proceedings of the International Conference on Automated Planning and Scheduling, volume 30, pages 449-458, 2020.
[36] Sergio Jiménez, Tomás De La Rosa, Susana Fernández, Fernando Fernández, and Daniel Borrajo. review of machine learning for automated planning. The Knowledge Engineering Review, 27(():433-44) 2012.
12

---

[37] Doina Precup. Eligibility traces for officc policy evaluation. Computer Science Department Faculty Publication Series, page 80, 2000.
[38] Carles Gelada and Mare G Bellemare. Off-policy deep reinforcement learning by bootstrapping the covariate shift. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 3647-3655, 2019.
[39] Josiah Hanna, Scott Nickum, and Peter Stone. Importance sampling policy evaluation with an estimated behavior policy. In International Conference on Machine Learning, pages 2605-2613.
PMLR, 2019.
13


Reviews:
[{"review_id": "f6gfnylA0S", "reviewer": "Reviewer_QEFf", "summary": "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality:\nThe idea of applying counterfactual explanations in decision making process with multiple, dependent actions taken sequentially overtime is referred as original.\nThe algorithm is not replicated comparing to papers with the same topics. \n\nQuality:\nThe paper is well-structured, it has solid research foundations based on previous work and has some originality concerning the whole experiment procedure. The inductions are very clear, though the dataset used is somehow lack of explanation. Provided more statistics in the experiments will certainly help to convince the audience.\n\nClarity:\nThe paper clearly describes its motivation, the method and experimental results. The method applied is introduced in an intuitive and clear way. \n\nSignificance:\nThe paper mainly contributes in illustrating the idea of finding optimal dependent sequences and validating the result in experiment. It is a solid practice of using Markov decision process, Gumbel-Max structural model in finding optimal decision sequence. Therefore, the idea and the experiment setting within this paper can be great reference for further work.  \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper mentioned the limitations: only discrete states and actions used; only one real dataset validated; manually decide the transition probability; limit the process to satisfy Markov property.  \nThe paper fails to mention its potential negative societal impact. However, it is more of a theoretical research and thus few societal negativities can be concerned.\nExperimental details. Please report the details required to reproduce the experiments. It would be more convinced if a GitHub repo is cited.\n\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "KJJWCEW-5bQ", "reviewer": "Reviewer_vTQ9", "summary": "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. \n", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper extends existing counterfactual explanations on DNN to MDP and generates explanations for target policies acting in the corresponding MDPs. First of all, I like the idea of generating counterfactual explanations for MDPs. This explanation method takes into account the sequential decision process and can be potentially used to identify the important actions/time steps in a trajectory of a target policy. In the context of DRL explanations, most of the existing research focuses on explaining the neural policies or the Q networks. Not too many works tried to explain the whole decision-making process. Although the problem studied in this paper is novel, the following concerns pause me from supporting it.\n\n1. I found the paper is relatively hard to follow, especially the technical part. The reasons come from three folds: (1) The paper does not provide a sufficient introduction of the necessary backgrounds. For example, it would be helpful if the authors could quickly introduce and summarize the SCM used in this work. The arguments in this work largely depend on [18] and [19]. It would be easier for readers to understand these arguments if the authors could review those two works and summarize their key points. These backgrounds can go to the appendix. For readers that are not familiar with causal influence and causal-based explanations, they are super-helpful.  (2) Some important notations and formulations are not very clearly explained (See the below comments for more details). (3) This work frequently uses long and complicated sentences. For example, lines 103-107 are one sentence. To improve the readability, I would highly suggest rewriting those sentences with simpler structures. Overall, I found it is relatively hard for me to understand every component of the proposed technique because of the above reasons. I can only get the high-level idea is that given a trajectory of a target policy, the proposed technique seeks to search for the best K actions to change, keep the other actions, and increase the collected rewards.\n\n2. Here, I list the places where I found it is hard to understand. They may be caused by the reasons I mentioned above or my lack of relative knowledge. IMHO, addressing these comments could help readers better understand the technique proposed in this paper. I would really appreciate it if the authors could do so.\n\n(1) The motivation of using an SCM to remodel an MDP is unclear. In the sentence starting from line 89, the authors argue the weakness of MDP is that MDP is not able to tell what would happen if changing one action $a_t$ in a trajectory. I found this argument is relatively vague. \"What would happen\" is an especially unclear description. From my point of view, what would happen is starting from the time step $t+1$, the agent will jump into a different state from the previous one, and the following actions/states will change correspondingly. The changed trajectory can be obtained by running the target agent in the corresponding MDP (repeating the trajectory till the $t$-th step, taking a different action at that step, and continuing running the agent in the following steps). To this end, MDP could tell what would happen if changing $a_t$. The above argument is invalid. I guess what the authors want to express if MDP is not able to simulate the case where only $a_t$ is changed, and the following states/actions keep the same. According to the above discussion, in MDPs, changing one action will likely trigger the changes in the following states/actions. With the unclear limitation, I was also not able to understand the benefits of using SCM. To make it more clear, maybe the authors could consider reexpressing the limitation of MDP and clarifying what is the characterization in line 93 and what are the desirable properties in line 94.\n\n(2) The posterior distribution in line 104 is not clearly presented. First, what does it represent? My understanding is it defines a distribution of $U_t$. If the agent takes $a_t$ at $s_t$, sampling any $u_t$ from this distribution can transit the system from $s_t$ to $s_{t+1}$. Second, It would be easier to understand if the authors could demo one such distribution. My understand is the distribution should be 1[g_s(s_t, a_t, u_t) = s_{t+1}]. If this is the case, how to compute the density function. (3) What is the prior and what is the likelihood.\n\n(3) Without a clear understanding of the above posterior, it is hard for me to fully understand Enq. (3). I would appreciate it if the authors could provide more explanations of the first step. First, what does the left-hand side of the equation stands for? Second, the right-hand side looks very similar to the right-hand side of Eqn.(2). What is the difference? Some text descriptions of those two terms are needed. They are important and deserve more explanations.\n\n(4) Regarding the non-identifiable problem, the paper refers to the argument [19]. As is discussed above, it would be helpful if the authors could summarize what the argument in [19] is. \n\n(5) The condition after 122 implies the equation in line 126, and it also implies the conditions after line 125. However, since the conditions after line 125 cannot infer the condition after line 122, it cannot imply the equation in 126.\n\n(6) What is the connection between the model and the condition?\n\n(7) Algorithm 1 is redundant, It just expresses a normal testing process. I would highly suggest explaining more about Algorithm 2. With all the above questions, I found Algorithm 2 very hard to understand.\n\n3. Comments about the evaluation:\n\n(1) It worth clarifying what an explanation is. My understanding is that an explanation refers to a trajectory with counterfactual actions. \n\n(2) I would suggest reporting the runtime of the proposed method.\n\n(3) It is important to study the boundary and failure cases of a proposed technique. I am wondering if there are cases where the proposed method fails to generate explanations. \n\n(4) I would like to see the applications of the proposed method to more complicated environments with more discrete actions and states. \n\n4. Finally, the paper does not discuss the possible limitations and how to solve them.  Below, I point out some possible limitations of the proposed technique that worth discussing. \n\n(1) Scalability. As is mentioned above, the environments evaluated in this paper are relatively simple ones with a small number of states and actions. It worth discussing the scalability of the proposed technique to more complicated environments.\n\n(2) Practicability is another major concern. The proposed technique is limited to environments with discrete actions and states. If the authors are not able to demonstrate the scalability of the proposed technique, then its practicability will also be largely restricted. \n\n(3) As is mentioned above, it is worth evaluating and discussing the boundary of a new technique. For the proposed method, I am wondering if it still works if the target policy is an optimal one. In addition, I assume the proposed technique may fail if the game has only a final reward without an instant reward.  I would suggest discussing these cases. \n\n(4) Existing counterfactual explanations of DNN are able to identify the most important input features, modifying which may cause the target model to make a mistake. The proposed technique aims to improve the target policy's performance via action modification. I am wondering if it can operate in the opposite way, i.e., modifying actions to trigger the highest reward deduction. \n\n\n=========Post rebuttal=============\n\nThanks to the authors for providing the rebuttal. It indeed addresses some of my concerns. Regarding that, I will not be strongly against accepting this work if the other reviewers and AC all vote for an acceptance. IMHO, the paper still has room for improvement. Below, I listed some comments that the authors could consider addressing if the paper got accepted (The authors do not need to reply to the following comments at this moment given the discussion is coming to an end. They are (non-mandatory) suggestions for camera-ready if the paper got accepted). \n\n**Clarity and readability.** I read the responses together with the paper multiple times. Despite having a better understanding of the overall procedure of the proposed technique, unfortunately, I was still not able to understand most of the technical details. This may be due to my lack of knowledge in causal inference and causal model (My knowledge about causal inference is at a relatively high level - understand the definition of the casual model, intervention, and counterfactual. But I do not have a detailed grasp of specific casual models, such as the one used in this work.). Maybe for casual inference experts, the current version is enough for them to understand more details. However, for general audiences, the current descriptions of the proposed technique are not that clear. Specifically, it is quite intuitive that $P(S_{t+1}=s_{t+1}|S_{t}=s_{t}, A_{t}=a_{t})$ with/without the corresponding trajectory. From this fact, it seems natural to infer that $P(S_{t+1}=s_{t+1}|S_{t}=s_{t}, A_{t}=a')$ would be also different. However, it is still not entirely clear to me what's the difference between the original state transition function and the intervention/counterfactual distribution. Eqn. (3) deserves more space to explain each line of derivation. The non-identification problem is more clear with the response. Line 122-126 has logical errors (as I pointed out in my review). I would suggest correcting them. If the posterior in line 105 is different from the general definition, it should definitely be pointed out. Otherwise, it will cause misunderstanding. In Sec. 3, the authors define another model - the counterfactual MDP model, with a new set of state transitions. I would suggest emphasizing their difference from the ones defined in Sec. 2, especially a text description of Eqn. (6) would be very helpful. The last point that can be more clear is Algorithm 2. IMHO, Algorithm 2 is much more important than Algorithm 1, given that it is the one used to generate explanations. I read the current version in the Appendix. Again, I can only get a high-level idea - recursively search for a better action at each step within the budget K. I would suggest moving Algorithm 2 to the main text and add a line-by-line explanation to the Appendix to help readers better understand it. Overall, IMHO, the current version is enough for the general audience to understand the proposed technique at a high level. However, to make the technical details more clear and accurate, the paper may require some major revisions, as I suggested earlier. \n\n**Faithfulness of SCM.**\nAs the authors mentioned in the response, the reason for using SCM is to model what would have happened if manipulating some actions in a given trajectory of an agent. The example of the current state and action given by the authors makes sense to me. However, this example may not be enough to justify that MDP cannot capture what would have happened if the actions in a given trajectory are changed. A counterargument is MDP reflects the state transition of the original system. If an existing action changes, the new action would be given to the system, and the system transits according to the transition function of the MDP. I would appreciate it that if the authors could explain more about the difference between normal state transition ($P(S_{t+1}| S_{t}, A_{t})$) and the state transition when changing the actions of a given trajectory ($P_{\\tau}(S_{t+1}| S_{t}, A_{t})$). My point is as long as the action is acted in the same environment, they should be the same. Note that this is different from the example given in the authors' responses, where no action changing is involved (P(S_{t+1}=s_{t+1}| S_{t}=s_{t}, A_{t}=a_{t})). Of course, my understanding may be wrong. Despite $P(S_{t+1}| S_{t}, A_{t})$ and $P_{\\tau}(S_{t+1}| S_{t}, A_{t})$ are different, my second question is why SCM could model the $P_{\\tau}(S_{t+1}| S_{t}, A_{t})$. This is where more backgrounds of SCM are needed. In SCM, there is a noise term. I would doubt that whether introducing this noise term could still represent the original system. The same question can also be raised for the counterfactual MDP model. Those questions make me doubt the accuracy of the model (the same question pointed out by the reviewer bT61). The author didn't directly respond to that question with an evaluation. These concerns may still stand.\n\n**Explainability of the proposed technique.**\nTo me, the proposed method is more like a policy fine-tuning approach rather than explanation methods. The proposed method generates a set of counterfactual trajectories that have higher rewards than the original ones. By comparing these trajectories with the original ones, some insights about the original policy can be drawn. The explainability of the proposed approach was qualitatively demonstrated in some simple environments. To further justify the explainability, the authors may need to design and conduct some quantitive evaluation or human studies, just like most of the existing DRL explanation works have done (e.g., [1], [2], [3]).\n\n**Scalability, Practiabilty, and generalizability.**\nAnother major concern is about Scalability, Practiabilty, and generalizability. Regarding scalability, the computational cost is quadratic to the number of states. This significantly limits the applications of the proposed technique. In the evaluation, the authors only tried a real-world dataset with $4$ states. Besides, the proposed technique can only be applied to systems with discrete state space. I would highly doubt the practicability of the proposed technique to environments that are widely used in the DRL (explanation) community - openAI gym [1], Atari games [1,3], Go game [2], etc. and derive useful insights. This is a fundamental weakness that may not be addressed through paper revising or additional experiments.\n\nRelatively minor points: 1. a comprehensive literature review of the existing DRL explanation techniques is highly encouraged. 2. In the responses, the authors state that \"Finally, there are no cases where our method “fails” to generate counterfactual explanations. The only interesting edge cases are the ones where there is no action change which, in retrospect, could have given an average counterfactual outcome higher than the observed one\". I would like to see how often those cases will happen. If the target agent has an optimal policy, It may be quite frequent that the proposed technique cannot find better actions that would have given a higher reward. \n\n[1] Visualizing and understanding atari agents.\n\n[2] Explain your move: understand agent actions using specific and relevant feature attribution.\n\n[3] Exploratory Not Explanatory: Counterfactual Analysis of Saliency Maps for Deep Reinforcement Learning.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "IMHO, this paper neither sufficiently discusses the limitations nor the negative social impacts. Regarding limitations, the authors could refer to my above comments. For the potential negative societal impact, they are only briefly discussed in the checklist. More strictly, the discussion in checklist 1(c) is actually not about the \"negative\" social impact. I would suggest the authors include such a section in the paper or appendix to discuss the negative impact of their proposed technique. For example, as an explanation tool, it can be used by attackers to generate attacks against MDPs or a target policy.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7 hours"}, "extra_text": {}}, {"review_id": "BLxx0fPh94", "reviewer": "Reviewer_161w", "summary": "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.\n", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: \nThis is an exciting piece of work. The idea of using an MDP to do something similar has been introduced recently elsewhere, but the model introduced in this paper is novel.\n\nA slightly related field I think is automated planning and learning. See for example:\n\nJiménez, S., De La Rosa, T., Fernández, S., Fernández, F., & Borrajo, D. (2012). A review of machine learning for automated planning. The Knowledge Engineering Review, 27(4), 433-467.\n\nQuality: \nOverall, the paper appears to be technically sound. However, I think the evaluation needs to improve in two ways:\n\n1) As with standard ML-based approaches, there should be a training and test set. This will allow the authors to evaluate the effectiveness of the approach better.\n\n2) Comparison with existing methods: I understand the conceptual difference between existing methods and the model proposed in this paper. However, I feel that there is nothing stopping people from taking sequential action of the existing method suggests changing multiple features -- I could change each feature one at a time. \n\nClarity: \nThe paper was well organised, the concepts easy to follow, and the results were explained reasonably well.\n\nSignificance: \nThis work is important to the algorithmic recourse community and has the potential to open a very interesting and promising area of research.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations are not sufficiently discussed.", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1-2"}, "extra_text": {}}, {"review_id": "8TxTpm8w4bK", "reviewer": "Reviewer_bT61", "summary": "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall this is a nice and fairly well-written paper. It is clear in what it does, the formalization and algorithms make sense, and the experiments are insightful and effective. Downsides are a limited treatment of related work and connections to other work, some doubts about the relative novelty/significance, and some missed opportunities to structure the conceptual story in a better way. I do not think the specific modeling choices are well motivated nor put well in the context of the literature. I will elaborate.\n\nSection 1 is informative and clear, but I wish the authors would have had a better grasp of the surroundings, and had provided a better story to situate the work. On one hand this is about the build-up of the motivation. So far, the story is \"counterfactual explanations can be done in single decisions and typical machine learning contexts\" followed by \"and now we move to sequential decisions\". This is also reflected in the related work. However, counterfactual explanations are typically used in a different way as in this paper: namely to show that alternative paths are not as optimal as the chosen one, instead of showing that alternative paths are indeed better than what is chosen now (reflected in the data). Other work in explainable RL and planning exist where such typical meanings of \"counterfactual explanations\" are computed. That side of the story is not related to at all, also not acknowledging that there is a body of work on explainable AI for sequential decision making. The other point is about novelty. It seems that references such as [19] are used for some technical aspects, but in fact, [19] already does many (conceptual) things as in this paper, such as the structural causal models, counterfactual explanations, but then even for POMDPs. A clear separation between this paper and other ones using these kinds of models is needed to clearly see the contributions of the paper, and is lacking now in the paper. \n\nThe storyline in sections 2-4 sometimes looks quite difficult but can be (and should be) summarized much more clearly. As far as I can see, the paper takes offline data of some decision making process (traces) and uses that to estimate a model of an MDP. This is not an easy task (identifiability) hence structured causal models are employed, and some sampling mechanisms in there, but the bottom line is that from that point on, there is a model which can be used to find better traces (better action selection). In order to do that structuredly, the authors look at \"at most k differences\" in alternative traces. The construction of the extended MDP (with how many alternatives left) and the corresponding dynamic programming frame are straightforward then, but the specifics not much relevant (alternatives exists, since this is all based on a fully specified MDP at that point). This clear conceptual story (I'm assuming I read it right, of course) is lacking and could make the paper much better. Also, some better explanation/illustration of the structured causal models (as in [19]) could help a lot. Some of the formalization of the probabilities is not concise, and layout-wise formulas such as in (3) can be structured much better and clearly. The \"do-notation\" should be formalized better here too. The stability aspects at the end of page 3 can be illustrated better, since these are quite important because they determine the possibility of learning the model.\n\nA main question that is not asked in this paper, and would be highly relevant also for interpreting the results is: how good is the model that is estimated from data? The better the model, the more credible are statements about the relative quality of solutions (and thus the quality of counterfactual explanations). Not much is said about this, even though it is crucial for everything. This should be answered in some way.\n\nAnother question that is not asked in the paper (related to the previous) is how well the counterfactual explanations would do in the real world. I mean, the model is an approximation of the real world, with assumptions to make things work. What would happen if it would be possible to really apply them, and how would the outcomes differ? The first experiment could give some insight here, but it is not easy to see whether the setup is too clean/regular or easy (for the model approximation) for that? \n\nI like the experiments. They mostly make sense and clearly shows the main dimensions of the approach. Fig 1 is clear and logical. Fig 2 is mostly ok, but (c) and the description in the text raises some questions since it is quite a binary thing: either alpha is 0, or it is larger than 0. If alpha is only 0.1 we already get the same kind of pattern as with alpha = 1.0. This is not well explained yet. Also the sentence \"however.... increases\" (232/233) is not clear to me. The second experiment is called \"real data\" but the underlying MDP is very tiny, which asks for a good description of how particular aspects of this dataset (that is is from real treatments, how many trials, how long the trials are, and how large or small the underlying MDP is (in this case 5x9=45 state-action pairs max)). These questions are triggered since the \"artificial\" problem in the first experiment is larger (the MDP size) but more regular possibly. For Fig 3 the results make sense and the corresponding text too, but the choice for k=3 is not motivated (although intuitive maybe given the small MDP size, but on the other hand the total length of traces is about 20, so why not k=10?). Fig 4a is not clear to me, but 4b and 4c are, and I think that the analysis of this particular case is nice, although I wish a more comprehensive analysis would be done on more traces (this one feels illustrative, but also somewhat anecdotical).\n\nThere some small typos such as \"a MDP\" -> \"an MDP\" (end of page 2). Some references are made to Algorithm 2, but sometimes it is not clear it is in an appendix.\n\nPOST-REBUTTAL: thank you for your adequate answers and promises. I will keep my score.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not discussed (limitations; the paper merely lists future work but not addresses the limitations explicitly) and the societal benefits/impact is seen in the contribution to interpretable machine learning. I think that the latter point is fair and does not require further elaboration than is now in the paper. ", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Based on the review, rating and discussion, I recommend acceptance of this work.

* there is no fundamental flaws in this work
* while the required background for reading the paper is heavy, the overall paper is well written.
* the significance of the contribution is high
Decision: Accept (Poster)