Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
main_review: Originality:
The idea of applying counterfactual explanations in decision making process with multiple, dependent actions taken sequentially overtime is referred as original.
The algorithm is not replicated comparing to papers with the same topics. 

Quality:
The 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.

Clarity:
The paper clearly describes its motivation, the method and experimental results. The method applied is introduced in an intuitive and clear way. 

Significance:
The 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.  

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.  
The 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.
Experimental details. Please report the details required to reproduce the experiments. It would be more convinced if a GitHub repo is cited.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: 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.

main_review: Originality: 
This 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.

A slightly related field I think is automated planning and learning. See for example:

Jimé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.

Quality: 
Overall, the paper appears to be technically sound. However, I think the evaluation needs to improve in two ways:

1) 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.

2) 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. 

Clarity: 
The paper was well organised, the concepts easy to follow, and the results were explained reasonably well.

Significance: 
This work is important to the algorithmic recourse community and has the potential to open a very interesting and promising area of research.
limitations_and_societal_impact: Limitations are not sufficiently discussed.
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: 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. 

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.

1. 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.

2. 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.

(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.

(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.

(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.

(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. 

(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.

(6) What is the connection between the model and the condition?

(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.

3. Comments about the evaluation:

(1) It worth clarifying what an explanation is. My understanding is that an explanation refers to a trajectory with counterfactual actions. 

(2) I would suggest reporting the runtime of the proposed method.

(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. 

(4) I would like to see the applications of the proposed method to more complicated environments with more discrete actions and states. 

4. 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. 

(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.

(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. 

(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. 

(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. 


=========Post rebuttal=============

Thanks 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). 

**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. 

**Faithfulness of SCM.**
As 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.

**Explainability of the proposed technique.**
To 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]).

**Scalability, Practiabilty, and generalizability.**
Another 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.

Relatively 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. 

[1] Visualizing and understanding atari agents.

[2] Explain your move: understand agent actions using specific and relevant feature attribution.

[3] Exploratory Not Explanatory: Counterfactual Analysis of Saliency Maps for Deep Reinforcement Learning.
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_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.
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.

Section 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. 

The 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.

A 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.

Another 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? 

I 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).

There 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.

POST-REBUTTAL: thank you for your adequate answers and promises. I will keep my score.
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_title: null

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)