Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: In the main paper, the authors study the problem of performing value iteration using confounded observational data where the confounders are partially observable. Applying for backdoor adjustment to correct the observational data, the authors propose de-confounded optimistic value iteration (DOVI) in this setting. Finally, a sublinear regret bound of DOVI is provided for linear confounded MDPs and cases where the observed subset of the confounders satisfy the backdoor criterion.
main_review: The paper proposes an interesting problem to study and has a clear motivation. DOVI is an adaptation of least squares value iteration in linear confounded MDPs. The authors have given a clear description of the algorithm and its guarantee. 

(1) Can the authors comment on whether DOVI can be considered an instantiation of https://arxiv.org/pdf/2011.04622.pdf with a particular feature map and regularization? Given that we only observe samples of s_h, u_h, how should one obtain the back-door adjusted feature in general? And how will the estimation error of the back-door adjusted feature play a role in the regret?

(2) Experiments:
- It would be very helpful to showcase how DOVI performs empirically compared to VI methods that do not take confounding into account, i.e., treating u_h as part of the state variable. 
- Since the regret guarantee greatly depends on the linear confounded MDPs assumption, performing some sensitivity analysis on that would be very important.

Overall, the strengths of the paper are (1) a clean formulation of confounded MDPs and (2) DOVI which achieves sublinear regret for linear confounded MDPs. The main weaknesses of the paper are (1) (theoretical and empirical) comparison of DOVI with other algorithms in tackling confounded MDPs (e.g., general algorithms for solving POMDPs or algorithms that are designed for unconfounded MDPs); (2) a clearer description on how DOVI is related to existing least-squares based VI algorithms.

Minor typo:
- L4: "semple" -> "sample"

*Update after the author response*
I have read through the author response and other reviews. The author response has clarified some of my concerns. Similar to reviewer czeu and 8cdv, I believe that an adequate experiment section is needed for the paper. Hence, I am maintaining my score. 
limitations_and_societal_impact: Based on the checklist answer, the authors did not address the limitations of their work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposed an algorithm to learn optimal policy reinforcement learning in the presence of confounded observational data. It proposes to remove confounders from the data and improve sample efficiency in online settings. It addresses two scenarios, partially observed and unobserved confounder, by using two techniques, the frontdoor, and backdoor criterion. It further theoretically analyzes the regret bound in these settings.

main_review: Originality:  This paper addresses an important problem of leveraging confounded observational data in learning optimal policy in the reinforcement learning framework. The work is novel, and it incorporates some well-known techniques (Frontdoor, backdoor adjustment) in the context of reinforcement learning. Related works need to be included in how these works fall under the existing (deep) reinforcement learning framework.

Quality: The work is technically sound,while an empirical evaluation is needed to confirm the effectiveness of the proposed algorithms


Clarity: The paper is well-written and easy to follow. Necessary assumptions are stated.

Significance: The work has value and has the potential to be used by others. However, there are further discussions needed on how the works fit into the existing reinforcement learning literature. 


Detailed comments:

The proposed algorithms and bound is analyzed based on the linearity assumptions (i.e., linear SCM, linear confounded MDP). How is the analysis dependent on this assumption? How can it be generalized to non-linear cases? If it is not straightforward, I suggest explicitly mentioning this assumption in the abstract and introduction. 

The paper motivates the neural network function approximation in deep reinforcement learning. However, it is still unclear to me if such a scenario is discussed in the context of the proposed method. 

Is Algorithm 1 assumed a tabular reinforcement learning setup? If that is the case, how those bounds hold with function approximation, such as using a neural network to approximate value function, Q-function, and policy. These are the setups used extensively in current RL literature (deep reinforcement learning). 

In Algorithm 1, how the online data is used to estimate Value, Q-function, and policy? It seems the online data line 10-12 is not saved in any buffer. How does it then influence the policy? 

How do these assumptions, frontdoor exist, be mapped from the real-world example?

How are these methods relevant to deep reinforcement learning, as is motivated in the abstract and intro? Need some discussion on this line, though the author mentions this is relevant to causal bandits.




How partially observed MDP is handled, that is, backdoor criterion assumption limits the use of the proposed algorithms. What are some practical scenarios that hold this assumption in the context of reinforcement learning? Justifying this would be useful for readers.
How to derive a practical RL algorithm?

Backdoor adjustment limits the applicability of the algorithm/method. Can you give some practical scenarios where these are held?

What if the confounder is fully observed? What difference it will make compared to partially observed. How does it impact the regret bound or algorithmic convergence?

Not clear why the reward function in equation 3.2 is called the counterfactual reward function.



Is the observational data (first line of Algorithm 1) collected in an offline setting? How the online data (line 10-12 in Algorithm 1) is used? Is it stored in a buffer and then merged with the observational data? What policy (random or human demonstration) was used to collect the observational data?



Empirical evaluation will strengthen the papers and verify the feasibility of the proposed algorithm in practice. While I understand this paper focuses on theory, the feasibility of the assumptions needs to be discussed in the paper. For example, an example can be added with stating the assumptions of how they relate to some real-world settings, which will help readers better understand the implication of the proposed algorithms.

The literature review should address how this paper’s algorithm fits into existing RL literature, which seems to be missing in the paper. Section B discusses the comparison with causal bandits.

How does the confounded MDP relate to the previously proposed Block MDP[1]?

The observational data requires an additional record of confounders (partially observed confounders and intermediate state) which standard policy in the RL framework does not provide. So how do the observational data need to be collected to be incorporated in the online setup? Need to discuss in the paper.

The paper seems to end abruptly without a proper conclusion. I suggest adding a conclusion or discussion section summarizing the contribution and results.



Reference:
[1] Provably efficient rl with rich observations via latent state decoding. Simon Du, Akshay Krishnamurthy, Nan Jiang, Alekh Agarwal, Miroslav Dudik, and John Langford. In International Conference on Machine Learning, pages 1665–1674. PMLR, 2019.


limitations_and_societal_impact: The assumptions are stated clearly in the papers. However, additional discussion about the feasibility of these assumptions needs to be discussed (as suggested in detailed comments).
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This is a technical paper presenting how to incorporate offline observational data to improve the sample efficiency in the online reinforcement learning setting.
The issue is the potential presence of unobserved confounders in the observational data which impact the transition dynamics and the rewards and how to adjust the exploration bonus used in the online setting.
The authors suggest an algorithm (DOVI) which adjusts for the confounding bias (where the coufounders are partially observed or unobserved). They then derive a bound on the regret when using linear function approximation which shows that the regret is smaller than the optimal online regret thanks to the use of offline observational data if they are informative.
main_review: The paper is well-written and clear. There are no experiments. While this is not particularly an issue for this kind of technical paper, a toy example illustrating the advantage of using offline observational data and the different regimes of the regret bound would have been beneficial.

The paper is well-motivated: it is very often the case that observational data are available and it is indeed relevant to try to use this data to reduce the sample cost of existing deep reinforcement learning solutions, especially when simulators are not available as is the case for most real-life problems (engineering systems, health, ....). Leveraging tools from causal inference is an interesting direction that is increasingly popular. I believe the theoretical result to be interesting for the community.

Major comments:
- the definition of an intervention states that the value is assigned regardless of the other exogenous and endogenous variables. However in the online context, when using a policy, the authors uses the do operator (as an intervention) but the policy selects an action based on the state $s$. This is confusing as the action is thus not assigned regardless of the state which is an endogenous variable.
- Are the authors the first to state a Backdoor Adjusted Bellman Equation? this is not clear in the paper.
- It is also not clear to me where the distinction between the observational and interventional data is in algorithm 1?

Minor comments:
- the abstract format is not correct.
- line 4: semple -> sample
- lines 56 and 57: please give references.
limitations_and_societal_impact: -
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper studies the problem of online reinforcement learning, while making use existing offline data that was previously logged by some behavior policy, where there is unobserved confounding in the logged data. They provide some conditions under which the RL model can be identified from the confounded logged data, and under these conditions propose a variant of optimistic value iteration for online learning that incorporates this offline data as a regularization term, which has an intuitive Bayesian interpretation based on conditioning on this data. Finally, they provide regret bounds for their algorithm, which has a leading term incorporating the effect of the logged data, which decays to zero as the amount of logged data grows to infinity.
main_review: Overall, the paper has many positive aspects; it presents a well-motivated algorithm for an important problem, and provides regret bounds that shrink in terms of the amount of confounded logged data available. In this sense, the paper seems to fill an important niche in the literature. That being said, the paper has several significant weaknesses outlined below, which limits my recommendation. In particular, it feels somewhat lacking/incomplete without any kind of empirical evaluation.

Major weaknesses:
- There is no empirical evaluation of their proposed algorithm, or even an empirical “proof of concept” on synthetic data. This makes it extremely difficult to assess how the algorithm is likely to fair in practice.
- The backdoor criterion in Assumption 3.1 seems to be extremely central to the theory, but it is not explained at all. Ideally, there would be an explanation of when we expect this requirement to be satisfied versus not. Furthermore, it would be very beneficial in motivating the entire paper to provide a compelling clear/concrete example of a problem with unmeasured confounding that fits within your framework and satisfies assumption 3.1. Without such an example, it is difficult to assess how useful the theory is.
- Along a similar vein to the previous concern, the confounding model presented in section 2 seems very weird and non-standard (since, the way it is written, it seems like the confounders are caused by the observed state). This is in contrast to standard kinds of confounding models, where e.g. confounders are independent at each time step, follow in a Markov chain, or follow the POMDP model, etc. Again, it would be great to have a compelling example of a problem with this kind of confounding structure.
- The method is presented as being “provably efficient”. But what does this actually mean? It doesn’t seem to be actually justified as efficient in any concrete sense. One possible sense of efficiency is in terms of semi parametric estimation, but that doesn’t seem to be applied anywhere here. Another sense could be in terms of optimal regret, but this doesn’t seem to be established; although the $\Delta_H$ term in the regret bound has the nice property that it should decay as $n \to \infty$ as discussed in the paper, nothing as far as I can tell rules out the possibility of an alternative algorithm that has faster regret decay as $n \to \infty$. Given this, presenting the work as “provably efficient” in the title is extremely misleading.
- There seems to be a bunch of important recent literature on using confounded off-line RL data that is missing from the related work, for example Namkoong et al. (2020) “Off-policy Policy Evaluation For Sequential Decisions Under Unobserved Confounding”, and Bennett et al. (2021) “Off-policy Evaluation in Infinite-horizon Reinforcement Learning with Latent Confounders”.

Other minor issues / comments / suggestions / typos:
- Typo in line 4 “semple" -> “sample”
- On line 41 you say that “The complicated traffic and poor road design subsequently affect both the action of the drivers and the outcome”. But do we expect these things to be unobserved? This only makes sense as an example of confounding if they are things not observed in the state space, but which the agent took into account. It would be good to elaborate here.
- For fairness, since all presentation and discussion of DOVI+ was deferred to appendix, I am not taking it into account when assessing the paper.
- The discussion of structural causal models at the start of section 2 is very confusingly presented and mostly doesn’t seem to contribute much other than defining the “do” notation (it presents a bunch of notation that is then never used). Also, it would be good to define what the “do calculus” notation means more explicitly for people not already familiar with it.
- The definition of Regret in equation 2.3 defines it as a random quantity (since the definition involves the initial state $s_1^k$ for each $k \in [K]$, which seems somewhat odd. Should there have been an expectation over the initial state?
- You refer to Figure 4 on line 216, but there appears to be no Figure 4 in the paper.
- In a bunch of different places, you talk about replacing  $\mathbb P$ with $\mathcal P_h$. I don’t understand what is meant to be the difference between these two functions; this needs to be explained concretely.
- In assumption 3.3, is $\phi_h$ meant to be a fixed given feature map? This is not explained.
- Also, in assumption 3.3, you refer to the reward function parameters as $\theta_h$, but later in the paper this appears to instead be referred to as $\omega_h$.
- Typo on lines 249-250 “is know” -> “is known”.
- What is the interpretation of the $\beta$ tuning parameter in your algorithm? This doesn’t not appear to be clearly explained. Also, what would be the expected impact of increasing versus decreasing $\beta$ on how the algorithm operates?

limitations_and_societal_impact: I have no concerns here.
review_title: null

Meta-review: Reviewers were mostly agreed that the paper makes an important contribution at the interface of RL and causal inference, proposing new ways of using confounded offline data to help online RL and rigorously proving their value. Thus, the paper brings together familiar tools from both fields (causality and RL) in a fruitful way that could serve as a basis for future work.
The major weakness of the paper is lack of any experimental validation. While the theoretical contribution is sufficiently important in itself, adding even a synthetic experiment would make the paper stronger.
Finally, the reviewers pointed out several aspects where the paper could be made clearer, and I urge the authors to address these issues in their final version. 



Decision: Accept (Poster)