Whenever a clinician reflects on the efficacy of a sequence of treatment decisions for a patient, they may try to identify critical time steps where, had they made different decisions, the patient's health would have improved. While recent methods at the intersection of causal inference and reinforcement learning promise to aid human experts, as the clinician above, to retrospectively analyze sequential decision making processes, they have focused on environments with finitely many discrete states. However, in many practical applications, the state of the environment is inherently continuous in nature. In this paper, we aim to fill this gap. We start by formally characterizing a sequence of discrete actions and continuous states using finite horizon Markov decision processes and a broad class of bijective structural causal models. Building upon this characterization, we formalize the problem of finding counterfactually optimal action sequences and show that, in general, we cannot expect to solve it in polynomial time. Then, we develop a search method based on the $A^*$ algorithm that, under a natural form of Lipschitz continuity of the environment's dynamics, is guaranteed to return the optimal solution to the problem. Experiments on real clinical data show that our method is very efficient in practice, and it has the potential to offer interesting insights for sequential decision making tasks.
Paper
Similar papers
Peer review
Summary
The authors present a method for finding c/f (optimal) action sequences in sequential decision making problems with uncertainty, with the novelty that they consider continuous state dynamics. They apply their method to the interesting setting of sepsis treatment at the end of the paper and therein demonstrate impressive results for their method (compared to the actual, observed, action sequences).
Strengths
Please see the Questions section for the full review.
Weaknesses
Please see the Questions section for the full review.
Questions
## Abstract - I re-read the abstract multiple times and I unfortunately struggle with the first half. Consider changing the sentence construction or just simplify the first half. It is very unclear what you are trying to say and I fear that the positioning of the paper suffers because of it. One suggestion could be to anchor the paper with one or two real examples and then take the justification from there. - The first paragraph of the introduction does a much better job of framing your paper, I would suggest adapting that approach for the first half of the abstract. ## Introduction - Spell out ICU before you use it; it is common-enough term in the West but may be unfamiliar to a non-native speaker (or indeed anyone who does not frequently use English). - Excellent second paragraph. - Line 49: an SCM does not have the concept of state or transitions, merely a distribution P() over the endogenous and exogenous variables in the model (as defined originally by Pearl). Consequently how you have chosen to introduce it here does not quite follows. Consider re-phrasing. Moreover, SCMs are, as originally defined, state-less representations of a causal environment. - It would be helpful to the reader and yourselves if you could show us (the readers) a quadrant of work which has considered MDPs with: (continuous states, discrete actions), (continuous states, continuous action) … and so on — so that we understand what gap you are filling with this work (certainly you spell it out, but I would argue that a quadrant would be more useful and visually more powerful). - Line 60: please explain what a bijective SCM is. It is not enough to simply cite the original paper it if it is going to be key to your method. ## A Causal Model of Sequential Decision Making Processes - Line 76: presumably $a_t \in \mathcal{A} = \mathbb{Z}_+$? - How come you are not considered the discounted cumulative reward? - I think you should differentiate your setting more than what you are currently doing. At present it sounds as if eq (2) is part of the standard SCM definition. Perhaps introduce a definition paragraph for your SCM? That way the reader is clear that your are formalising a new concept and there is now ambiguity between yours and Pearl’s definition. - I would like to see a much longer discussion on why you make the causal sufficiency assumption (Line 97) in this work (no unobserved confounders). It is a common assumption as you say, but merely saying that other works make the same assumption, is not good enough justification to make it a tenable assumption. It is a huge assumption and highly unrealistic in most realistic scenarions. It makes life computationally far easier but trades-off usability down the line. Consequently, please discuss why you make this assumption. - Line 104: the do() express does not have to constitute a hard (atomic) intervention, it can also be a soft intervention (and others). Please consider or at least mention these settings too and why you settle for hard interventions. - Definition 1: is this definition somehow different from the standard one? Perhaps you ought to also give it a source since this is common fare but it may differ from the one readers are used to (and would also elucidate on the matter if it the standard definition or not). - The paragraph at the bottom of page 3 is great, very interesting application of Lipschitz continuity on a real problem. - Define the indicator function in equation 5. - Lines 149-161: I wonder if it may be not better for you to formally have a small lemma here, possibly even a theorem, explicating the results for which you have a proof. It currently reads as if it was merely a by-product of your method, whereas I imagine it is rather more important than that? ## Problem statement - I would recommend revising the structure of your paper given that the problem statement appears on page four at conference with a page limit of nine. The paper will read far better if you frame the problem early on, allowing the reader to understand your angle of attack from the very start. - Line 163: you already introduced the episode on line 78. - Where is practically relevant to know that eq 9 is NP hard? A trivial question no doubt, but I would be interested to hear what the authors have in mind with regards to this theorem (is it really a theorem?) ## Finding the optimal counterfactual action sequence via A* search - Line 210: I think a diagram here would be very helpful, explaining algorithm 1; a lot of page six could gainfully be explained with a figure rather than paragraphs of (rather dense) text. ## Experiments using clinical sepsis management data - Looking at figure 2(a) I would have thought that as k increased we would have seen a much larger increase in the y-axis but this does not seem to be the case, the increase is fairly modest. Can you explain? - According to panel 2(b), 50% of patients see less than or equal to ~5% c/f improvement? Is that correctly read? - I enjoyed this section and the example is good but it is long and arduous, and we have no evidence to suggest that your method works for more (even synthetic) settings. It is an old trope of reviewing that we (reviewers) always want more experiments but in this case I think it is a fair request. Simply because I am struggling to understand how your ideas generalise across different settings and applications (even synthetic) nor do we have a comparison against other methods (are there any to which you can gainfully compare against?)
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
2 fair
Presentation
2 fair
Contribution
3 good
Limitations
Please see the Questions section for the full review.
Summary
This paper tackles the problem of finding counterfactual action sequences in sequential decision making problems. The main difference to previous methods is that this paper regards a continuous state space instead of a discrete one, which renders previous solution methods infeasible. The authors formalize the problem as an SCM and show that the solution in general is NP hard. As a solution, they present a new method based on the A-star algorithm, which yields for many problems an efficient solution. They evaluate the method on clinical data.
Strengths
The paper is well-written and easy to follow. The problem of efficiently finding counterfactual action sequences for the continuous state space seems new to me and relevant to the community. Even if the SCM formulation follows closely the work of Tsirtsis et al. (2021), a likewise dynamic programming approach would require enumerating all possible action sequences. From my point of view, the main contribution lies therefore in the A-star-based search method (and the anchor set selection), which requires further technical details such as bijectivity and Lipschitz continuity of the SCM for the heuristics. Therefore, the technical contribution seems good to me. The method is evaluated with regard to the influence of different parameters.
Weaknesses
The worse case complexity of the method is the same as for brute-force search. The efficiency of the method depends on the number of samples of the Monte Carlo samples in the anchor set. It is not clear to me, which conditions the problem must have in order for the method to work effiently and when it falls back to worse case complexity. Minor (typos): line 190 comma before "such that"
Questions
How important are the assumptions that the SCM is bijective and Lipschitz-continuous? You need this assumption for the bounds in your algorithm. Can you still approach the problem if one condition is violated? How much do you think do the conditions restrict the field of applications of your method? Any thoughts about the conditions of the problem under which the method works efficiently?
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
4 excellent
Contribution
3 good
Limitations
Limitations and directions for future work are adequately addressed.
Summary
The paper tackles the problem of finding optimal action sequences in domains with continuous state spaces with counterfactual reasoning. They propose an A* based search approach and show the efficacy of the approach on a clinical sepsis management problem.
Strengths
* The paper focuses on a very significant research problem * The experimental evaluation on a real-world clinical dataset demonstrates the strong utility of the approach
Weaknesses
* I have some concerns regarding the causal d-separation assumption (see Q1 & Q2).
Questions
1. Graphical implication of an intervention on a variable $X$ (ie. $do(X=x)$ ) is that all the incoming edges to $X$ are removed. In other words, as we are intervening on X, the influence from the $PA_X$ (parent nodes of X) on the node $X$ becomes zero. Refer to paragraph after Def 3.2.1 in Chapter 3 of Pearl. In Equation 3, it seems that all the arrows pointing out of $A_t$ are removed to adjust for $do(A_t = a_t)$ (as mentioned in line 106). So, the d-separation assumed does not follow from the do-calculus. 2. Similar d-separation assumptions are made in Eq. 4 and 6. 1. Equation 1. suggests that two variables have a parent-child relationship: $S_t \rightarrow A_t$. 2. Equation 2 suggests that their variable form a collider: $S_t \rightarrow S_{t+1} \leftarrow A_{t}$. 3. On performing do-operation on $A_t$ would remove the parent-child relationship. But still maintain the collider $S_t \rightarrow S_{t+1} \leftarrow A_{t}$. So, $S_{t+1}$ and $A_t$ are not d-separated by $S_t$. 3. What are the implications of modifying the d-separation assumption on the proposed algorithms? 4. How was the generated counterfactual action sequence evaluated? The SOFA score requires vital signs for calculations, how were the vital signs obtained? 5. Figure 1 needs a legend. It is not clear what the pink & green lines represent. 6. Did any physician analyze the counterfactual action sequences? Was any physian involved at any stage of the process? 7. I recommend authors provide a reference table for notations in the appendix, it was really difficult to keep track of all the notations used in the paper.
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
1 poor
Presentation
1 poor
Contribution
2 fair
Summary
This paper studies a question that is very natural for a sequential decision maker to ask itself: "how could I best improve the return I obtained in a trajectory by only changing a fixed (k) number of actions from the sequence of actions I just executed while keeping the rest of the actions fixed". Authors study this question in a context where the state space is continuous but the action space is discrete. The paper generalizes the result of previous work which studied a similar question, but in the context of discrete states. The setting is very nicely motivated and the problem is quite relevant and important. This formulation seems to be novel, general, and useful. However, the paper shows that answering this question is in fact an NP-hard, one that we can only solve in the worst case using exhaustive search. Therefore, the paper goes on to find an admissible heuristic to be used in conjunction with the A* algorithm to reduce the complexity of the search space. To propose a consistent/admissible heuristic, one needs to find reasonable upper bounds for the value of unseen states which are found using counterfactual reasonings. The paper proposes to get this done using the notion of Lipschitz continuity where intuitively, the difference between the value of the two states is upper bounded by a constant times the norm of the difference of the two states. This may be a stringent requirement generally, but it seems to make sense in the domain that is of interest in the paper, namely in medical trials. Experiments show that using this heuristic does result in significantly reducing the average runtime of the search. Overall, this is a fair contribution in the intersection of causal reasoning and planning/reinforcement learning.
Strengths
The competency that the paper attempts to develop, namely being able to answer counterfactual questions in the context of planning and reinforcement learning, is quite interesting. Formulating this problem and showing that the original problem is NP-hard also sheds some light on the complexity of asking such questions. Some of the assumptions made, such as using a bijective causal model does limit the scope of the result, but I still find the formulation very interesting.
Weaknesses
We know that Lipchitz continuity can be a pretty lose upper bound for the function value. Especially in the context of this paper, when data is sparse, the upper bounds derived in Lemma 4 can be pretty bad. Moreover, recently there have been more efforts to develop Lipschitz-like tools that are more conducive to RL algorithms by ensuring that the new tool are Coarse-Grained. See for example "Coarse-Grained Smoothness for Reinforcement Learning in Metric Spaces", by Gottesman et al, 2023 or "Zooming for Efficient Model-Free Reinforcement Learning in Metric Spaces" by Touati et al 2020. This paper though relies on more classical notions of smoothness (vanilla Lipchitz continuity) which is not the most effective in the context of RL. Another point is that under the assumptions made in this paper (namely Lipschitz reward and transition dynamics), the value function itself becomes Lipschitz, so when learning the value function one can restrict the set of feasible value functions to be Lipschitz also. Is there any reason why this is not leveraged? In the same vein, we clearly know that the value function is always between (1-\gamma) R_max and -(1-\gamma) R_max. Can you elaborate if the bounds that are obtained by the Lipschitz interpolation would be able to provide much tighter bounds or that the bounds become vacuous? Can you also elaborate on the amount of data needed in your medical domains before these bound become non vacuous? In practice, we also need to make sure that we do not underestimate the Lipschitz constant, because otherwise the heuristic used in A* will no longer be admissible. The estimate also needs to be tight enough so as to make sure that it is effective when used as a heuristic. But I am not sure how this trade-off will be maintained in problems where the Lipschitz constant is unknown.
Questions
I would like to see a comparison with the discrete case, in particular the "Woulda, coulda, shoulda: Counterfactually-guided policy search" paper of Buesing et al, 2018. I do understand that this paper is dealing with the continuous state space. But one natural baseline to compare against could for example be the paper mentioned above where one can simply discretize the continuous state space and then apply their algorithm to compare against. How important is the kick-starting part with the monte carlo anchoring? In particular, it would have been nice to see ablations where the monte-carlo anchoring is performed more or less to understand its effect on performance.
Rating
5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
3 good
Contribution
2 fair
Limitations
Authors maintain that they will release code for their experiments if accepted, but they seem to have access to confidential patient data. I hope and trust that authors will they take sufficient precautions to ensure the anonymity of patients whose information is used in these experiments.
Summary
The paper studies the problem of finding a counterfactual action sequence to maximize the outcome of a trajectory in an MDP characterized by a structural causal model. The focus is on continuous state spaces under a set of Lipschitz constraints. The authors show that this problem is NP hard and propose an algorithm based on A* search, which they test empirical on a dataset on clinical decision making.
Strengths
- The paper studies a relevant well-motivated problem that will be of interest to the NeurIPS community - The authors do a good job in clarifying and formalizing the problem - Showing that the proposed problem is NP-hard is a valuable insight to guide future theoretical and empirical work - The proposed algorithm is a natural choice and it's formulation is sound - The empirical evaluation is performed on a realistic dataset, and the results are promising
Weaknesses
- The discussion of related work is too limited. I think there is a lot of related work about related problems in SCM (outside RL) that should be mentioned. I'm not very familiar with this literature myself, which made it difficult to judge the potential impact of the contribution the present paper makes. - Theorem 3 (NP-hardness) is a key contribution of the paper. However, it is only stated in the paper and almost not discussed. It would be valuable to give a high level picture of the reduction used to prove the result, as well as a discussion of the implications of this result and how it results in the choice of algorithm later in the paper. - The empirical results are difficult to interpret due to a lack of baselines. While the efficiency results in Figure 1 and performance results in Figure 2 look as expected qualitatively, there is no point of comparison. - For efficiency it would be useful to compare to some naive baselines, like a search based method without a specific heuristic. - The counterfactual performance improvements in Figure 2 are pretty small which makes me wonder if the dataset is a good enough benchmark to evaluate the present method. Maybe the trajectories in the dataset are too close to optimal? - It could be interesting to compare to an approach the discretizes the environment and uses prior methods for discrete state spaces.
Questions
- What could be baselines to compare the empirical results to? - What impact does the chosen heuristic have on the performance of the search algorithm? - How much worse would be a method that discretizes the environment? - How can we be confident that the present dataset is a good benchmark to evaluate the approach?
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
4 excellent
Contribution
3 good
Limitations
Yes
D-separation
Thank you for the clarification on the D-separation assumption. That was my only major concern. As this is addressed, I will update my score accordingly.
Thank you for engaging in the discussion
We would like to thank the reviewer for engaging in the discussion and for updating their score.
Thanks for the response! The responses address my primary concerns, and if the author update the paper as promised, I think the paper would be improved quite a bit. I appreciate the comments regarding the difficulty to choose suitable baselines; I think this should also be discussed in the paper. Overall, I am still a bit skeptical about how reliable the experimental results are; especially, because it is only a single dataset. But given that my other concerns were addressed, I will increase my score from 6 to 7 (assuming the authors make the promised changes to the paper).
Thank you for engaging in the discussion
We would like to thank the reviewer for engaging in the discussion and for updating their score. We will make sure to perform all edits mentioned in the rebuttal, when revising our paper.
Thank you for your detailed response. I am happy to raise my score but will note that I do not think the authors have it right on the unobserved confounder assumption. Whilst I accept the logic for making this assumption here, in the first pass at the problem, it is and remains a significant assumption that rarely holds true save for toy problems. But I agree with the authors that this assumption, nonetheless, does not nullify your contribution. Again, well done, it is a fine paper.
Thank you for engaging in the discussion
We would like to thank the reviewer for engaging in the discussion and for updating their score. When revising the paper, we will make sure to highlight the assumption of no unobserved confounders and its implications, as mentioned in the rebuttal.
Lipschitz Nets
Thanks for the pointer to the Appendix. What I originally meant is that the Lipschitz constants $L_{\phi}$ and $L_h$ could be estimated based on the data. The discussion on how these are chosen is currently pretty limited. For example, the Appendix reads that the Lipschitz models are only 6% worse in terms of log-likelihood. What does this mean? Is this log-likelihood on a single set of data, or log-likelihood on a held out test data? Moreover, when applying this approach to a new domain, how do I know what is a reasonable $L_{\phi}$ and $L_h$?
Response to follow-up question
We would like to thank the reviewer for engaging in the discussion. Perhaps this is already clear to the reviewer, but we would like to highlight that our goal is not to use data to train and estimate the Lipschitz constant of a *single* SCM, since that could lead to an underestimation of its value and could end up being problematic for the optimality of our proposed method, as correctly mentioned by the reviewer in the original review. Instead, our approach is to train *multiple* SCMs that are Lipschitz continuous by design—each one is *guaranteed* to consist of neural networks $h$ and $\phi$ with Lipschitz constants $L_h$ and $L_\phi$ whose values we can control. Then, we evaluate the log-likelihood achieved by each of these SCMs using 5-fold cross validation, as discussed in lines 831-832, and pick the SCM with the best tradeoff between log-likelihood, $L_h$ and $L_\phi$. This procedure is described in lines 830-841 in Appendix F in the supplementary. To evaluate the log-likelihood using 5-fold cross validation, for each configuration of $L_h$ and $L_\phi$, we randomly split the dataset into a training and a validation set (with a size ratio 4-to-1), we train the corresponding SCM using the training set, and we evaluate the log-likelihood of the validation set based on the trained SCM. We repeat the procedure 5 times and we take the average of the achieved log-likelihoods. In the revised version of our paper, we will clarify that the log-likelihood is always measured on a different set of data points than the one used for training. Whenever we write that the Lipschitz models are only 6% worse in terms of log-likelihood, we mean that the log-likelihood achieved by the Lipschitz models is only 6% lower than the log-likelihood achieved by a baseline model whose Lipschitz constants are unconstrained. To pick $L_h$ and $L_\phi$ in a new domain, we would repeat the aforementioned procedure using data from the new domain and defer to domain experts to elucidate what is an acceptable trade-off between log-likelihood, $L_h$ and $L_\phi$.
Decision
Accept (poster)