Eligibility Traces for Confounding Robust Off-Policy Evaluation: A Causal Approach

Authors: Junzhe Zhang, Elias Bareinboim
Primary area: causal reasoning
Keywords: Causal Inference, Graphical Models

Abstract:
A unifying theme in Artificial Intelligence is learning an effective policy to control an agent in an unknown environment in order to optimize a certain performance measure. Off-policy methods can significantly improve the sample efficiency during training since they allow an agent to learn from observed trajectories generated by different behavior policies, without directly deploying the target policies in the underlying environment. This paper studies off-policy evaluation from biased offline data where (1) unobserved confounding bias cannot be ruled out a priori; or (2) the observed trajectories do not overlap with intended behaviors of the learner, i.e., the target and behavior policies do not share a common support. Specifically, we first extend the Bellman's equation to derive effective closed-form bounds over value functions from the observational distribution contaminated with unobserved confounding and no-overlap. Second, we propose two novel algorithms that use eligibility traces to estimate these bounds from finite observational data. Compared to other partial identification methods for off-policy evaluation in sequential environments, these methods are model-free and do not rely on additional parametric knowledge about the system dynamics in the underlying environment.

Decision: reject
Reviewer scores: 6, 8, 6, 3

Reviews and discussion:
<thread>
creation date:
1730170491626

thread_type:
official_review

<thread_object>
creator: reviewer_srdk

<content>
summary:
This paper studies off-policy evaluation with offline data in Markov Decision Processes, where the actions taken by the behavior policy may be affected by unobserved confounders, causing standard estimation techniques to fail. The authors propose a variant of the Bellman equation that takes this confounding into account, and show they are able to obtain a consistent estimate of it from data. They demonstrate their approach on a gridworld experiment.

strengths:
There is limited work on causality and handling unobserved confounders in RL, but this is an important problem, with possible practical applications. This work takes a step towards deepening our understanding of how we should think about RL in these settings.

weaknesses:
1. The theoretical results, while a good first step, need further refinement to be convincing. In particular, the following aspects could be improved:
	* Theorem 1 and 2 give upper and lower bounds on the value and Q-value function in the confounded setting, but it is unclear how tight these bounds are. Can we obtain tighter upper and lower bounds, or is this the tightest possible? Is it possible to come up with a clean bound on the gap between the upper and lower bounds? Without answers to these questions, it is difficult to see how significant Theorem 1 and 2 are.
	* Theorem 3 and 4 are asymptotic consistency results. What are the finite-time properties of Algorithm 1? That is, for a fixed number of samples $n$, how small is the estimation error on the value function? While an asymptotic consistency result is nice, more refined analysis of this is required in order to show how practical this approach is.

2. The experimental results are limited to an extremely simple 3x3 grid world environment. Given the aforementioned shortcomings of the theoretical results, these experiments are not sufficient for illustrating the effectiveness of the proposed approach. More extensive experiments on more complex environments are necessary here with the current theoretical results.

3. Several notational issues. In particular, the $\langle$, $\rangle$ notation in Theorem 1 and 2 is not defined. I believe this is attempting to simultaneously state the upper and lower bounds, but unless I missed it, this was not stated. This should be clarified. It was also unclear and somewhat distracting why in Theorem 1 and Theorem 2 some of the font is blue.

4. More practical justification for why this problem is important would help better motivate the paper.

5. There are a variety of existing works on causality in bandits and RL that are not mentioned or cited here. See works [1]-[5] given below. These should be cited, and some discussion given of relation to the current work.

[1] Lattimore, Finnian, Tor Lattimore, and Mark D. Reid. "Causal bandits: Learning good interventions via causal inference." Advances in neural information processing systems 29 (2016).

[2] Lee, Sanghack, and Elias Bareinboim. "Structural causal bandits: Where to intervene?." Advances in neural information processing systems 31 (2018).

[3] Lu, Yangyi, Amirhossein Meisami, and Ambuj Tewari. "Causal bandits with unknown graph structure." Advances in Neural Information Processing Systems 34 (2021): 24817-24828.

[4] Lu, Chaochao, Bernhard Schölkopf, and José Miguel Hernández-Lobato. "Deconfounding reinforcement learning in observational settings." arXiv preprint arXiv:1812.10576 (2018).

[5] Wang, Lingxiao, Zhuoran Yang, and Zhaoran Wang. "Provably efficient causal reinforcement learning with confounded observational data." Advances in Neural Information Processing Systems 34 (2021): 21164-21175.

questions:
See weaknesses section.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730617672537

thread_type:
official_review

<thread_object>
creator: reviewer_nuhy

<content>
summary:
This paper addresses the challenges of off-policy evaluation in reinforcement learning (RL) when faced with confounded offline data and non-overlapping support between behavior and target policies. In such cases, traditional methods struggle to produce accurate value estimates due to unobserved confounders and the lack of common support, resulting in biased evaluations. The authors propose a novel model-free approach leveraging eligibility traces for partial identification of policy values that gives upper and lower bounds of the underlying true expected returns.

strengths:
1. The problem of confounding in OPE studied by this paper is well motivated and is an important topic towards reliable and robust RL.
2. The model-free approach by leveraging temporal difference learning and eligibility traces for partial identification in OPE is new and interesting.
3. Theoretical results prove the convergence of the proposed algorithms to the partial identification interval given exact observational distributions.

weaknesses:
1. The experiments of the proposed methods are limited to simple synthesis setups. 
2. Lacking empirical comparisons with extensive body of partial identification OPE methods as mentioned in the related work section.

questions:
1. How does the proposed algorithms perform on large-scale RL experiments? A direct difficulty of scaling up the algorithm is the need of solving $\min_{s\in\mathcal{S}}V(s)$ and $\max_{s\in\mathcal{S}}V(s)$ for some value estimate $V$.
2. Despite that the true partial identification interval (defined through Theorem 1) gives valid upper and lower bounds of the true policy value, it seems that the resulting bound could be too optimistic or too pessimistic since the observational data can be induced by arbitrarily bad behavior policy (and sure this makes sense). Is it possible to provide further analysis how does the behavior policy influence the accuracy of the true partial identification interval? Or are there methods to avoid such kind of potential looseness under some circumstances?
3. In addition to the asymptotic convergence results (Theorem 3 and 4), how does the behavior policy influence the convergence?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730704173532

thread_type:
official_review

<thread_object>
creator: reviewer_euhx

<content>
summary:
The paper studies off-policy evaluation in reinforcement learning when unobserved confounding exists in the data such that the causal consistency assumption is violated. Under this scenario, the paper derives causal Bellman equations to bound the value function and Q-function under a target policy. Two algorithms using eligibility traces are proposed to estimate the bounds of the value an Q-functions in both online and offline settings.

strengths:
The paper is original in effectively integrating standard off-policy methods into bounding the value function in causal reinforcement learning, and the proposed algorithms seem straightforward to implement. It creatively addresses the causal inconsistency assumption that is present in many real-world applications. The problem formulation is clear. The properties of the proposed algorithms are backed with theoretical guarantee.

weaknesses:
1. The environment considered in the paper is a little too restrictive, with finite action and state spaces, and bounded rewards. 

2. The synthetic experiments are conducted in simple Windy Gridworld settings with a small action and state space.

questions:
## Major comments:
1. The paper states that the proposed method relies on weaker assumptions than exisiting methods. In particular, the paper mentions that existing partial identification methods for off-policy evaluation rely on strong assumptions, including parametric assumptions about the system dynamics, model-based algorithm, and finite horizon. However, the settings consider in this paper actually rely on strong assumptions, including Markovness, finite action and state spaces, and bounded rewards. It would be great if the authors can review and compare other methods that consider the same settings, provided there are any.

2. The experiments are conducted in the simple synthetic Windy Gridworld environment. It would be helpful if the authors can comment on real-world scenarios to which the proposed methods are applicable, such as healthcare or robotics or something else. Experiments on real-world examples and comparisons with competing methods will further strengthen the paper.



## Minor comments:

1. Line 97 on page 2: "represents" --> "as"
2. Line 101 on page 2: Better to mention the full name before using the abbreviation "SCM"
3. Line 104 on page 2: Better to explicitly mention that $PA_V$ is the set of parents.
4. Line 361: "we" --> "We"
</content>
</thread_object>

</thread>
<thread>
creation date:
1731413634284

thread_type:
official_review

<thread_object>
creator: reviewer_pp72

<content>
summary:
The paper studies causal reinforcement learning (RL), i.e., RL in the presence of unmeasured confounding. The author(s) introduces a causal temporal difference (TD) learning and a causal eligibility traces algorithm for off-policy evaluation in causal RL, which combine TD or eligibility traces with the partial identification bounds developed in the econometrics or causal inference literature. Theoretically, causal Bellman equations were introduced to bound the Q- or value functions. Empirically, the author(s) also conducted numerical experiments to investigate the finite sample performance of their proposed algorithm.

strengths:
As far as I can tell, the strengths of the paper include:

* The development of the proposed causal TD and causal eligibility traces algorithms, which appear novel;
* The proposed causal Bellman equations, which may provide practitioners with valuable insights into the value or Q-functions, especially in scenarios involving unmeasured confounders;
* The main text of the paper is technically sound. I did not review the Appendix, but I did not spot any errors in the main text;
* The writing is generally clear.

weaknesses:
The paper suffers from two potential limitations:

* First, the numerical example is overly simplified. It only considers a 3 by 3 Windy Gridworld example. Additionally, the author(s) only reports the performance of their proposed algorithm, but did not compare their proposal against existing state-of-the-art methods. Given the huge literature on RL or/and off-policy evaluation (OPE) in the presence of unmeasured confounders, a comparison with these established methods would be highly beneficial. Such a comparison could highlight the most effective approaches for various applications. For instance, the methods developed by Kallus and Zhou (2020) and Bruns-Smith & Zhou (2023) seem directly relevant to addressing similar OPE challenges with unmeasured confounders. Additionally, POMDP-based methods, which use the POMDP framework to model the unmeasured confounding problem—such as those by Tennenholtz et al. (2020), Nair and Jiang (2021), and Shi et al. (2022) — would also be pertinent to this setting.

* Second, there is a lack of adequate discussions of the related literature. The last paragraph on Page 1 discusses the difference between this paper and other related works that use partial identification bounds. In particular, there is a line of work that "requires to additional parametric assumptions about the system dynamics". However, it would be better to detail this point later in the main text. What are the additional assumptions these papers imposed? How your proposal avoid imposing these assumptions? For instance, the paper by Namkoong (2020) needs a single-time unmeasured confounding assumption (I do not think this is a "parametric" assumption), which could be explicitly mentioned. Additionally, the paper by Bruns-Smith & Zhou (2023) also developed robust Bellman-operators using partial identification bounds. It would be better to clarify the difference between your proposal and theirs in detail. Moreover, the DGP mentioned on Page 2 suggests that you also relies on additional assumptions, more specifically, the memoryless unmeasured confounding assumption. It would be better to mention other related works that also rely on this assumption and discuss how to potentially verify this assumption in practice. Finally, as I mentioned, in addition to the use of partial identification methods, there are other methodologies, e.g., the POMDP-type methods to handle unmeasured confounding. These works are relevant as well.

questions:
Refer to "Weaknesses"
</content>
</thread_object>

</thread>
<thread>
creation date:
1732322783987

thread_type:
official_comment

<thread_object>
creator: reviewer_euhx

<content>
comment:
I would like to thank the authors for the detailed responses and comments. I think the paper targets an important issue, unconfoundedness, in causal learning. The authors' responses are reasonable. I would like to maintain my positive rating for the paper.
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper studies off-policy evaluation from biased offline data where target and behavior policy do not share a common support and where the bias due to unobserved confounding cannot be ruled out a priori.
The reviewers praise the novelty of the causal temporal difference and eligibility traces methods, the analysis with the causal Bellman equations, and the writing of the paper.
Potential limitation, highlighted by all reviewers, include the fact that the experiments operate in a setting that is too simplistic, and there seems to be a lack of discussion of important related literature.