Venue: CLeaR 2022 Conference

Reviews:

final_score: rating: 9: Top 15% of accepted papers, strong accept
review_content: Summary: The authors introduce a new type of learning problem called CMDPs, and they generalize UCBVI algorithms to CMDPs.
Main review: Although I am far from an expert in this area, this appears to be a highly innovative paper.

The authors first introduce a new type of decision problem -- causal Markov decision problems CMDPs.  A CMDP is a special case of a Markov decision problems (MDP), but reasonable performance in MDPs is typically achieved by assuming either (i) the state and action spaces are both finite and relatively small, OR (ii)  the state and action space can be factored in  a very particular way.  The authors note that, in certain settings (like healthcare and digital marketing), neither of those assumptions is realistic.  The authors then introduce CMDPs to model decision problems like those encountered in healthcare and marketing.  They briefly argue that, in such situations, a different type of factorization condition is plausible if one assumes the underlying actions, state, and reward structures  reflect some underlying causal  structure.  The authors then generalize UCBVI algorithms to CMDPs, prove a regret bound, and analyze the performance of their algorithms on simulated data.  

The paper is clearly written and well-organized.  Assuming the details of the arguments are correct, I think the only major weakness of the paper is that the authors do not apply their algorithms to real data from the healthcare and marketing settings the purportedly motivated this theoretical work.  Perhaps the application is trivial, but as a non-expert, it's not immediately clear  to me if the assumption used to derive the regret bounds is plausible in those settings.  Nonetheless, considered as a theoretical paper, this seems strong to me.
review_title: null

final_score: rating: 6: Marginally above acceptance threshold
review_content: Summary: The authors introduce methods in reinforcement learning to deal with action and state spaces that have a large cardinality. For large action spaces, they propose Causal Markov Decision Processes (C-MDP), an extension of MDPs that incorporate a lower-dimensional set of variables Z that create a conditional independence between intervenable actions A and rewards R/states S. To deal with large state (and action) spaces they propose Causal Factored MDPs (CF-MDPs) that, like factored MDPs, have a factorizable state space. They propose C-UCBVI and CF-UCBVI algorithms and show that regret bounds for these cases are better than conventional bounds. 
Main review: Originality: The authors have used simple assumptions like conditional independence and factored representations to gain on regret bounds. They make comparisons to prior work in causal reinforcement learning [Zhang et al.]. The work is closely linked to causal DBNs [Blondel et al., International Journal of Data Science and Analytics 2017] and path dependent causal models [Srinivasan et al. UAI 2021]: these papers introduce the concept of interventions in time-dependent systems, whose evolution changes with actions/interventions along the way. They also address confounding and effects on a system’s evolution upon intervention. Citing these would be beneficial to the scholarship of this work.

Significance: The paper claims to introduce causal MDPs. It would be important to understand the authors’ view on two issues:
(1) The usage of the word causality in this paper: The methodology in the paper does not seem to make use of counterfactual outcomes or the do-operator and the framework of causality. The main argument is that there is directionality in the dependence between A, Z and R/S. But does this extend beyond simple conditional independence, and is causality required for the arguments? Is it essential for nomenclature? 
(2) Unobserved Confounding: The authors state they do not deal with unobserved confounding in this paper. However, the main draw of causal methods is their ability to deal with confounding and bias. It is not clear why this strong assumption about lack of confounding was made in the paper.

Technical quality: The methods introduced are conceptually fairly straightforward. The bounds can be valuable if the settings of use obey the assumptions in the paper. The experiments are simple, and the paper could have benefitted from a real-data example to show the true power of the method, and validity of assumptions.

Clarity: The paper is clearly written and easy to follow. It would be prudent to highlight the trail of assumptions that lead to the final results as they are currently sprinkled all over the writing, making it hard to reconcile the claims in the abstract with the actual ability of the method to deal with large cardinality of A and S. For eg, an assumption is that the states all have the same structure. But this isn’t evident from the writing in the rest of the paper.
The examples can be better structured to convey ideas more effectively. The paper could have benefitted from an experiment that retains any of the motivating example scenarios introduced in the paper.
review_title: null

final_score: rating: 6: Marginally above acceptance threshold
review_content: Summary: Official review of Reviewer 18wK
Main review: The authors propose modifications to the existing UCB-type RL algorithms that rely on causal (actually more so probabilistic since they seem to have mainly utilized conditional independence) knowledge available a priori to achieve better regret than those that do not utilize such information. I liked the paper and the results make sense. But the proofs are missing and I cannot recommend acceptance without complete proofs. I would, however, be happy to change my score based on the authors' input to some clarification questions I have.


My detailed comments are as follows:
-------------------------------------------

"Otherwise, one can simply restrict the intervention set to those only intervening over PaR ∪ PaS, then the problem is trivially reduced to a standard MDP problem."  
I believe a better way to handle this case is to present this as the solution first and then move onto the case when these cannot be intervened by - possibly by giving realistic examples of when that might happen - and then move onto the actual contribution. 

The notion of "graphs at each state" is a bit confusing to me. Figure 1 does not really help clarify this. Is it possible to add an example graph that explicitly shows everything, time steps, states and graphs?

Could you comment on the assumption of having access to p(z|s,a)? Drawing connections to classical RL papers that make the same assumption might help.

"P(s'|s,a)"  
In the factorization, the assumption S'\indep A|S,Z is used. Could you explain, justify this assumption? Hard to see without an explicit graph. Similarly, please explain R(s,a).

Along the same lines as the above, it is very hard to parse how strong factored MDP and factored reward definitons/assumptions are without seeing a causal graph structure. 

"We note that extending RL algorithms from known rewards to unknown stochastic rewards poses no real difficulty (Azar et al., 2017)."  
Could you elaborate on this statement? What is the high-level methodology for that? What do we lose in that case?

Unfortunately, I believe the authors have forgotten to add the appendix since Sections A and B are often cited but are not included in the pdf. Therefore, proofs are currently missing. 

If I am understanding correctly, the proposed UCB-type algorithm changes exploration of S\times A to exploration of S\times Z since Z determines everything - being the parents of the quantities of interest. Then it is expected that when Z is much smaller, regret will be lower accordingly, which explains the form of regret in Theorem 4. Still, other terms also are different: for example we have S instead of \sqrt{S}, why is that? In general, seeing the proof will definitely help. But I also think it would be good to comment on why these other dependencies are changing for your algorithm.\

Causal factored-UCBVI seems to be utilizing the additional knowledge that states can be factorized into singletons (this part is not very clear to me since the definition was hard to parse - a graph example there will help here too). Again the reduction in regret with this side information is expected.

I think it will be good to make a clear point on exactly where causal knowledge is used. The fact that actions and their effects are the key to the RL settings makes me think that causality must have been used crucially but I was mostly able to identify the probabilistic information (conditional independence). Please point out exactly where ideas from causality is used. For example, what will fail if the given graph is not causal but only a Bayesian network? A walk-through over an example graph would be very helpful. 

I am not sure what the conclusion is in Section 6. Is a theorem missing here? "Thus, we can easily extend linear MDP algorithms to" Perhaps authors didn't add a result since maybe they think it is trivial but I think adding an explicit result (even with a citation) would make the paper self-contained.

AFTER THE REBUTTAL

I am increasing my score based on the proofs and the comments of authors. My main comment is to really clarify where causality is used in the method, i.e., it is only used at the observational level to derive independence statements and use them in the algorithm.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: Summary: This paper introduces causal MDPs, which uses causal structures over both state and reward graphs. The motivation is that in practice many problems have causal structures which can be exploited to reduce the complexity of the relationship between the interventions and the states or rewards. This is done by assuming that a set of variables Z exists, such that the interventions A affect the reward only through these variables (and similarly for the state transitions). This leads to improved bounds on a variety of MDP algorithms since the relevant distributions now scale with respect to Z, not A.
Main review: Quality: Overall this is a work of good quality. The motivating idea is interesting, and the solution is explained well and conveyed to the reader with precision.
Clarity: The work is generally well presented. The problem is motivated well, and the reader is introduced to the necessary notation in advance of reading the theorems. Furthermore, the use of diagrams to illustrate the problem is appreciated.
Originality: I have encountered some work which attempts to fuse causal graphical models with MDPs (e.g. Path Dependent Structural Equation Models by Srinivasan et al. 2020), so I would not call this a completely novel take on the problem. However, to my knowledge I have not encountered an approach that seeks to exploit structure using the Z variables in the manner that this paper discusses.
Significance: The work appears to be moderately significant, although as I discuss in the cons, I am not completely convinced of its practical utility. 
Pros: The authors provide novel bounds on the regret of the policy by exploiting the structure afforded by Z. The authors provide a causal UCB value iteration algorithm and extend this to the factored MDP setting. Provided we believe the setup of the problem, these results drastically improve performance and should prove useful to analysts in complex settings such as healthcare.
Cons: My main concerns are about the quantity Z. In figure 1 there are graphs with e.g. $R$, the parent variables $Z^R$, and the intervention  variables $X^I$. What happens if there are edges $X^I \to R$? 
Whilst I think that in many cases such an assumption is justifiable and indeed reasonable, this paper does not go far enough in checking the implications of making such an assumption. For instance, do promotional offers only affect purchase through exactly the three variables listed? How can we know if there aren’t other pathways, such as a person’s personal opinion about the brand (which might not be an observed quantity)?
It seems to me that this is a testable CI assumption that is being made here, and if it is violated then the factorizations in the second/third last equations of p. 6 are violated. As far as I can tell this is also assumed in the causal factor MDP, so all the presented algorithms hinge upon this testable assumption being true
What method do you propose to check this? Will you also consider sensitivity analysis to the violation of this assumption? In practice, if there are mild violations, how biased are the results? What happens to the bounds of these algorithms if such edges exist? 
Answers to some of these questions would help a potential analyst figure out if their parent variables Z are suitable for the task.
review_title: null

Meta-review: In this paper, the authors aim to generalize MDPs to allow modeling causal relationships within each state, by using ideas from the causal bandits literature. The authors use this factored representation to derive regret bounds that depend do not necessarily depend on the number of interventions and states.

It seems that the causal MDP representation isn't novel, but is a special case of existing approaches that generalize MDPs to allow states to be represented by causal graphs (possibly with unobserved confounding), see e.g. comments of reviewer ex9n. That said, the regret bound results appear to me to be novel.

Overall the reviewers received the paper positively, and the paper ought to be published. However, the authors should be clear about relationship of their proposal to prior work.
Decision: Accept (Poster)