Provably Efficient Causal Reinforcement Learning with Confounded Observational Data
Authors: Lingxiao Wang
Zhuoran Yang
Zhaoran Wang
Venue: NeurIPS 2021 Poster (2021)
Keywords: Reinforcement Learning
Causal Inference

Abstract: Empowered by neural networks, deep reinforcement learning (DRL) achieves tremendous empirical success. However, DRL requires a large dataset by interacting with the environment, which is unrealistic in critical scenarios such as autonomous driving and personalized medicine. In this paper, we study how to incorporate the dataset collected in the offline setting to improve the sample efficiency in the online setting. To incorporate the observational data, we face two challenges. (a) The behavior policy that generates the observational data may depend on unobserved random variables (confounders), which affect the received rewards and transition dynamics. (b) Exploration in the online setting requires quantifying the uncertainty given both the observational and interventional data. To tackle such challenges, we propose the deconfounded optimistic value iteration (DOVI) algorithm, which incorporates the confounded observational data in a provably efficient manner. DOVI explicitly adjusts for the confounding bias in the observational data, where the confounders are partially observed or unobserved. In both cases, such adjustments allow us to construct the bonus based on a notion of information gain, which takes into account the amount of information acquired from the offline setting. In particular, we prove that the regret of DOVI is smaller than the optimal regret achievable in the pure online setting when the confounded observational data are informative upon the adjustments.

Provably Efficient Causal Reinforcement Learning with Confounded Observational Data
Lingxiao Wang Northwestern University lwanguu www.noewtee..nnnommomoo edu
Zhuoran Yang Princeton University zy6@princeton. edu
Zhaoran Wang Northwestern University
zhaoranxangogmail.. com
Abstract
Empowered by neural networks, deep reinforcement learning (DRL) achieves tremendous empirical success. However, DRL requires a large dataset by in- teracting with the environment, which is unrealistic in critical scenarios such as autonomous driving and personalized medicine. In this paper, we study how to incorporate the dataset collected the offline setting to improve the sample ef- ficiency in the online setting. To incorporate the observational data, we face two challenges. (a) The behavior policy that generates the observational data may de- pend on unobserved random variables (confounders), which affect the received rewards and transition dynamics. (b) Exploration in the online setting requires quantifying the uncertainty given both the observational and interventional data. To tackle such challenges, we propose the deconfounded optimistic value itera- tion (DOVI) algorithm, which incorporates the confounded observational data in a provably efficient manner. DOVI explicitly adjusts for the confounding bias partially observed or unob-
in the observational data, where the confounders served. In both cases, such adjustments allow us to construct the bonus based on notion of information gain, which takes into account the amount of information acquired from the offline setting. In particular, we prove that the regret of DOVI is smaller than the optimal regret achievable in the pure online setting when the confounded observational data are informative upon the adjustments.
Introduction
Empowered by the breakthrough in neural networks, deep reinforeement learning (DRL) achieves significant empirical successes in various scenarios [19, 23, 36, 37]. Learning expressive function approximator necessitates collecting large dataset. Specifically, in the online setting, it requires the agent to interact with the environment for large number of steps. For example, to learn human-level policy for playing Atari games, the agent has to interact with simulator for more than 10 steps [13]. However, in most scenarios, we do not have access for trial and error without any cost. Meanwhile, in critical scenarios, e.g., autonomous driving and personalized medicine, trial and error in the real world is unsafe and even unethical. As result, it remains challenging to apply DRL to more scenarios.
simulator that allows
To bypass such a barrier, we study how to incorporate the dataset collected offline, namely the observational data, to improve the sample efficiency of RL in the online setting [21]. In contrast to the interventional data collected online in possibly expensive ways, observational data are often abundantly available in various scenarios. For example, autonomous driving, we have access to trajectories generated by the drivers. As another example, in personalized medicine, we have access to electronic health records from doctors. However, to incorporate the observational data in provably efficient way, we have to address two challenges.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

The observational data are possibly confounded. Specifically, there often exist unobserved ran- dom variables, namely confounders, that causally affect the agent and the environment at the same time. In particular, the policy used to generate the observational data, namely the behavior policy, possibly depends on the confounders. Meanwhile, the confounders possibly affect the received rewards and the transition dynamics.
In the example of autonomous driving [9, 22]. the drivers may be affected by complicated traffic or poor road design, resulting in traffic accidents even without misconduct. The complicated traffic and poor road design subsequently affect both the action of the drivers and the outcome. Therefore, it is unclear from the observational data whether the accidents are due to the actions adopted by the drivers. Agents trained with such observational data may be unwilling to take any actions under complicated traffic, jeopardizing the safety of passengers.
In the example of personalized medicine [8, 29], the patients may not be compliant with pre- scriptions and instructions, which subsequently affects both the treatment and the outcome. As another example, the doctor may prescribe medicine to patients based on patients' socioeconomic status (which could be inferred by the doctor through interacting with the patients). Mcanwhile, socioeconomic status affects the patients' health condition and subsequently plays the role of the confounder. In both scenarios, such confounders may be unavailable due to privacy or ethical con- cerns. Such confounding issue makes the observational data uninformative and even misleading for identifying and estimating the causal effect, which is crucial for decision-making in the online setting. In all the examples, is unclear from the observational data whether the outcome is due to the actions adopted.
Even without the confounding issue, remains unclear how the observational data may facilitate exploration in the online setting, which is the key the sample efficiency of RL. At the core of exploration is uncertainty quantification. Specifically, quantifying the uncertainty that remains given the dataset collected up the current step, including the observational data and the inter- ventional data, allows us to construct bonus. When incorporated into the reward, such a bonus encourages the agent to explore the less visited state-action pairs with more uncertainty. In par- ticular, constructing such bonus requires quantifying the amount of information carried over by the observational data from the offline setting. which also plays a key role in characterizing the regret, especially how much the observational data may facilitate reducing the regret.
Uncertainty quantification becomes even more challenging when the observational data are founded. Specifically, as the behavior policy depends on the confounders, there is a mismatch between the data generating processes in the offline setting and the online setting. As result, it remains challenging to quantify how much information carried over from the offline setting is useful for the online setting, as the observational data are uninformative and even misleading due to the confounding issue.
Contribution. To study causal reinforcement learning, we propose a class of Markov decision processes (MDPs), namely confounded MDPs, which captures the data generating processes both the offline setting and the online setting as well as their mismatch due to the confounding issue. In particular, we study two tractable cases of confounded MDPs in the episodic setting with linear function approximation [7, 16, 42, 43].
In the first case, the confounders are partially observed in the observational data. Assuming that an observed subset of the confounders satisfies the backdoor criterion [32], propose the deconfounded optimistic value iteration (DOVI) algorithm, which explicitly corrects for the con- founding bias in the observational data using the backdoor adjustment.
In the second case, the confounders are unobserved in the observational data. Assuming that there exists an observed set of intermediate states that satisfies the frontdoor criterion [32], we propose an extension of DOVI, namely DOVI+, which explicitly corrects for the confounding bias in the observational data using the composition of two backdoor adjustments. We remark that D follows the same principle of design DOVI and defer the discussion of DOVI+ to SA.
In both cases, the adjustments allow DOVI and DOVI+ to incorporate the observational data into the interventional data while bypassing the confounding issue. It further enables estimating the causal effect of policy on the received rewards and the transition dynamics with enlarged effective sample size. Moreover, such adjustments allow us to construct the bonus based on a notion of information gain, which takes into account the amount of information carried over from the offline setting.

---

In particular, we prove that DOVI and DOVI* attain the Ay Vd -Teggee up to logarithmic factors, where the dimension of features, H is the length of each episode, and T НK is the number of steps taken in the online setting, where K is the number of episodes. Here the multiplicative factor An > depends on d, H, and a notion of information gain that quantifies the amount of information obtained from the interventional data additionally when given the properly adjusted observational data. When the observational data are unavailable or uninformative upon the adjustments, Ah is a logarithmic factor. Correspondingly, DOVI and DOVI* attain the optimal VT-regret achievable in the pure online setting [7, 16, 42, 43J. When the observational data are sufficienlly informative upon the adjustments, AH decreases towards zero as the effective sample size of the observational data increases, which quantifies how much the observational data may facilitate exploration in the online setting.
Related Work. Our work is related to the study of causal bandit [20]. The goal of causal bandit is to obtain the optimal intervention in the online setting where the data generating process is described by a causal diagram. The previous study establishes causal bandit algorithms in the online setting [26, 34], the offline setting [17, 18]. and a combination of both settings [11]. In contrast to this line of work, we study causal RL in combination of the online setting and the offline setting. Causal RL is more challenging than causal bandit, which corresponds to H = 1, as it involves the transition dynamics and is more challenging in exploration. See 3B for detailed literature review on causal bandit.
Our work is related the study of causal RL considered in various settings. [45] propose model- based RI. algorithm that solves dynamic treatment regimes (DTR), which involve a combination of the online setting and the offline setting. Their algorithm hinges on the analysis of sensitivity [3, 27, 38, 44], which constructs a set of feasible models of the transition dynamics based on the confounded observational data. Correspondingly, their algorithm achieves exploration by choosing an optimistic model of the transition dynamics from such a feasible set. In contrast, we propose a model-free RL algorithm, which achieves exploration through the bonus based on a notion of in- formation gain. It is worth mentioning that the assumption of [45] is weaker than ours as theirs does not allow for identifying the causal effect. As a result of partial identification, the regret of their algorithm is the same as the regret in the pure online setting as T + +00, In contrast, our work instantiates the following framework in handling confounders for reinforcement learning. (a) First, we propose the estimation equation based on the observations, which identifies the causal ef- fect of actions on the cumulative reward. (b) Second, we conduct point estimation and uncertainty quantification based on observations and the estimation equation. (c) Finally, we conduct explo- ration based on the uncertainty quantification and achieve the regret reduction in the online setting. Consequently, the regret of our algorithm is smaller than the regret in the pure online setting by a multiplicative factor for all T. [25] propose a model-based RL algorithm a combination of the online setting and the offline setting. Their algorithm uses variational autoencoder (VAE) for estimating a structural causal model (SCM) based on the confounded observational data. In partic- ular, their algorithm utilizes the actor-critic algorithm obtain the optimal policy in such SCM. However, the regret of their algorithm remains unclear. [6] propose a model-based RI. algorithm in the pure online setting that learns the optimal policy in a partially observable Markov decision process (POMDP). The regret of their algorithm also remains unclear. [35] utilize generative adver- sarial reinforcement learning to reconstruct transition dynamics with confounder, and [40] propose a model-based approach for POMDP based on adjustment with proxy variables. [30] consider off- policy policy evaluation under one-decision confounding and constructs worst-case bounds with theoretical guarantee. [4] utilizes states and actions as proxy variables to tackle off-policy policy evaluation with confounders. In contrast, our work utilizes backdoor and frontdoor adjustments to handle confounded observation.
2 Confounded Reinforcement Learning
Structural Causal Model. We denote a structural causal model (SCM) [32] by a tuple (A, B, Here A is the set of exogenous (unobserved) variables, B is the set of endogenous (observed) vari- ables, is the set of structural functions capturing the causal relations, which determines an en- dogenous variable v B based on the other exogenous and endogenous variables, and P is the distribution of all the exogenous variables. We say that a pair of variables Y and are confounded by variable W if they are both caused by W.
3

---

An intervention on set of endogenous variables X C B assigns a value to X regardless of the other exogenous and endogenous variables as well as the structural functions. We denote by do(X = .) the intervention on X and write do(x)) if it is clear from the context. Similarly, stochastic intervention [10, 28] on set of endogenous variables X S B assigns a distribution p to X regardless of the other exogenous and endogenous variables as well as the structural functions. We denote by do(X ~ p) the stochastic intervention on X.
To characterize Markov decision process (MDP) in the offline setting with observational data, which are possibly confounded, we introduce an SCM, where the endogenous variables are the states {&x [M) actions {ar Me(f)) and rewards {rx he(M)- Let {wn he(H)) be the confounders. In 83, we assume that the confounders are partially observed, while in $A, we assume that they are unobserved. The set of structural functions consists of the tran- sition of states 84+1 ~ ( [h, Oh, Wh), the transition of confounders w/ ~ (- 8h), the be- havior policy an (-(-1 (-| 8h, wa), which depends on the confounder wh, and the reward function rh (8h, Wh). See Figure for the causal diagram that describes such an SCM.
Confounded Markov Decision Process.
Shw1
Sn
S
(a) Offline Setting
(b) Online Setting
Figure I: Causal diagrams of the h-th step of the confounded MDP (a) in the offline setting and (b) in the online
setting, respectively.
Here Gg and 8h+1 are confounded by WA in addition to 8h- We denote such a confounded MDP by the tuple AS,A, W. H,P,r), where is the length of an episode, S, A, and W are the spaces of states, actions, and confounders, respectively,
{rx he(M) is the set of reward functions, and P = [Pr, PARNCH is the set of transition kernels. In the sequel, we assume without loss of generality that Th takes value in [0, 1] for all h [M].
In the online setting that allows for intervention, we assume that the confounders {wo hE([ are unobserved. A policy æ = (mл)eе()) induces the stochastic intervention do(a: (1(-1s1),.... aH ( sH)), which does depend on the confounders. In particular, an agent interacts with the environment as follows. At the beginning of the k-th episode, the environ- ment arbitrarily selects an initial state s and the agent selects a policy z² f he(pF) At the h-th step of the k-th episode, the agent observes the state s and takes the action aB ~ (- ())) The environment randomly selects the confounder w PA s which is unobserved, and the agent receives the reward r ra(s f, at, w The environment then transits into the next state * ~ (- s ai w.))
For policy т = ThEH, which does not depend on the confounders {w) (wnhee(M) we define the value function V [VA ]Ne(H; as follows,
H Σ (r,
(s) = Ex
8h = s.. Vh E [H],
(2.1)
where we denote by E, the expectation with respect to the confounders {wy) and the trajectory ((8), /- starting from the state sj and following the policy m. Correspondingly, we define the action-value function Q" (QT as follows.
H
8h = s. d, s,do(an- =a)
Q7 0) E
ry(35 a,, W))))))))))))))
vh E [H].
(2.2)

---

We assess the performance of an algorithm using the regret against the globally optimal policy n² (Thhee(m) in hindsight after K episodes. which is defined as follows,
K
K Σ 1m
(T) = max Σ (VT
VT (st)
(V (51) - (s
(2.3)
Here HK is the total number of steps.
Our goal is to design an algorithm that minimizes the regret defined in (2.3), where x² does not depend on the confounders {wH, he[HH] In the online setting that allows for intervention, it is well understood how to minimize such a regret [2. 14-16]. However, it remains unclear how to efficiently utilize the observational data obtained in the offline setting, which are possibly confounded. In real- world applications, e.g., autonomous driving and personalized medicine, such observational data are often abundant, whereas intervention in the online setting is often restricted. We refer to &C for comparison between the confounded MDP and other extensions of MDP, including the dynamics treatment regime (DTR), partially observable MDP (POMDP), and contextual MDP (CMDP).
Why is Incorporating Confounded Observational Data Challenging? Straightforwardly incor- porating the confounded observational data into an online algorithm possibly leads to an undesirable regret due to the mismatch between the online and offline data generating processes. In particular, due to the existence of the confounders (w,, [w RE(H)) which are partially observed ($3) or unobserved
(BA), the conditional probability P(s 8h aij) in the offline setting is different from the causal effect P( Sh do(ax)) in the online setting [33]. More specifically. it holds that
E
( shh ah, wp. (aa 8h, w))]
= P
mN)
1 1 1h, aA))
IE
Par sn)) P/h (a,, Sh, wh) Wr
PP(8++1 8h, do(an)) = E uy, 1- (Px 8h, An; wx)]-
In other words, without proper covariate adjustments [32], the confounded observational data may be not informative for estimating the transition dynamics and the associated action-value function the online setting. To this end, propose algorithm that incorporates the confounded observational data in a provably efficient manner. Moreover, our analysis quantifies the amount of information carried over by the confounded observational data from the offline setting and to what extent it helps reducing the regret in the online setting.
3 Algorithm and Theory for Partially Observed Confounder
In this section, we propose the Deconfounded Optimistic Value Iteration (DOVT) algorithm. DOVT handles the case where the confounders are unobserved in the online setting but are partially ob- served in the offline setting. We then characterize the regret of DOVI. We defer the extension of DOVI, namely DOVI+, to ŠA which handles the case where the confounders are unobserved in both the online setting and the offline setting.
3.1 Algorithm
Backdoor Adjustment. In the online setting that allows for intervention. the causal effect of a, on 8h+11 given 8h, that is, P(8 8h, do(on)), plays key role in the estimation of the action-value function. Meanwhile, the confounded observational data may not allow us to identify the causal effect P(SN+1 8h. do(ax)) if the confounder wh is unobserved. However, if the confounder wn. is partially observed in the offline setting, the observed subset up, of wp, allows us to identify the causal effect [S sh,, (ax)))) as long as uy satisfies the following backdoor criterion.
Assumption 3.1 (Backdoor Criterion [32, 331). In the SCM defined in $2 and its induced directed acyclic graph (DAG), for all E [H]]. there exists an observed subset un of wy that satisfies the backdoor criterion, that is,
the elements un are not the descendants of ag, and
conditioning on 8he the elements of un d-separate every path between os and 81+11 Th that has an incoming arrow into dg.
5

---

See Figure 2 for an example that satisfies the backdoor criterion. In particular, we identify the causal effect P( Sh, do(ax)) as follows.
Figure 2: illustration the backdoor criterion modified from [32]. The causal diagram corresponds to
the h-th step of the confounded MDP conditioning on $4, Here wy, (wi,b, W2,6, W3,6) is the unobserved confounders and the subset U. = [U1,k, U2.4 satisfies the backdoor criterion.
Proposition 3.2 (Backdoor Adjustment [32]). Under Assumption 3.1, it holds for all E [H] that
P(sh+1 Sh, do(aa)) = Bug PP(- [aa) [[(sh+1 5h, Uhs un)],
E (Sh, ane wh) 8h, do(ax)] = PP P()lea) E [r 4h wx) 8h, an un]]
Here (8h+1; 8h, an, un) follows the SCM defined in $2, which generates the confounded observa- tional data.
Proof. See [32] for a detailed proof.
With a slight abuse of notation, we write P(SN+1 Sh. Oh, un) as Ph 8h. ab. un) and
P(ua (h) as Pa (u,, sx), since they induced by the SCM defined in $2. In the sequel, define L/ the space of observed state Ur and write гΛ = (8(,,, Ob, wy) for notational simplicity.
Bockdoor-Adjustee Bellman Equation. We now formulate the Bellman equation for the con- founded MDP. It holds for all (8h, an.) E x A that
H
(sh, an) = ES Ers(ss,a,,0u j=h
Shi do(an) EE ET 8h, do(an) + Eeati (s
where Esgar denotes the expectation with respect 8h+1 P(- sh, do(an)). Here E[ra sh: do(a;)) and (- sh. do(az)) are characterized in Proposition 3.2. In the sequel, we define the following transition operator and counterfactual reward function,
(PA an) = Beat en.do(a))) (+(++))), : R, (sh, ESx
(3.1)
Ra (8h, an) = E [rr 8h, do(ax)) V(Sh, ESXA We have the following Bellman equation,
(3.2)
(s,, an) = R4 ($h, ax) + (PA, (sta))s an), vh [H], (sh, an) E x A. Correspondingly. the Bellman optimality equation takes the following form, Q (sh, aa)
(3.3)
on) + (Pn, (it1))sn,,)))
(sx) max (s,, an), EA
(3.4)
which holds for all E [H] and (sh, ax) E S x A. Such a Bellman optimality equation allows us to adapt the least-squares value iteration (LSVVI) algorithm [2, 5, 14, 16, 31].
Linear Function Approximation. We focus on the following setting with linear transition kernels and reward functions [7, 16, 42, 43], which corresponds to linear SCM [33].
Assumption 3.3 (Linear Confounded MDP). We assume that (s(nnt1 8h, ah. ux)) = (dn(st, an, wx), (8h+1)), vh E [H), (8h+1, Sh, an) E S x S x A. where d and (n((-) (,.,, (a.b...,,,,,,.))) (+) Rd-valued functions. We assume that
EL= I| < d and (sh, an, un)ll2 < 1 for all h [H] and (sh, an, un) E S x A x U. Meanwhile, assume that
E[rn]] sh. on, un] = on (sh, an, un) Op. wh E [H], (s), an, un) eSxAxxx
(3.5)
where Or dd and [|0x12 for all h [H]]

---

Such linear setting generalizes the tabular setting where S, A, and U are finite. Proposition 3.4. We define the backdoor-adjusted feature as follows,
t/ (Sh, an.) = un P- an) [on (Sh, On, un)],
vh E [H, (sn. an) ESXA.
(3.6)
Under Assumption 3.1, it holds that
P(sh+1 Sh, ()))) = (sn, an), pn (5h+1))) Vh E [M]] (sh+1, sh, an) ESXX A. Moreover, the action-value functions 2% and Q% are linear in the backdoor-adjusted feature 2/ for all n.
Proof. See SF.1 1 for a detailed proof.
Such an observation allows us to estimate the action-value function based on the backdoor-adjusted features (1h heeur] in the online setting, See $D for detailed discussion. In the sequel, we assume that either the density (: 8h.) he) is known or the backdoor-adjusted feature } he is known.
In the sequel, we introduce the DOVI algorithm (Algorithm 1). Each iteration of DOVI consists of two components, namely point estimation, where we estimate Q7, based on the confounded observa- tional data and the interventional data, and uncertainty quantification, where we construct the upper confidence bound (UCB) of the point estimator.
Algorithm Deconfounded Optimistic Value Iteration (DOVI) for Confounded MDP
Require: Observational data {(s oi u ri) (E()) tuning parameters X, B > 0, backdoor- adjusted feature (v/A ]HEHH, which is defined in (3.6).
1: Initialization: Set {Q), Vo he(m as zero functions and HH1 as a zero function for k E [K].
2: for ===1 1...., K do
3: for h H...... do
4: Set w +- argmin Et=i0r (r% + ( T (s), + A||w|1 + (w),
where L is defined in (3.8).
5:
Set (+--) min min(f/n( (enn (T.-)Te T w -,, h). where r defined in (3.12).
6:
Set m sh) +- argmax EA (sh, an) for all sy S.
7:
Set v.) (.))) (h.:))
8:
end for
9:
Obtain of from the environment.
10: for l = ..... H do
11: Take af ~ ( st. Obtain r (s ab u//) and s
12: end for
13:
end for
Point Estimation. To solve the Bellman optimality equation in (3.4), we minimize the empirical mean-squared Bellman error follows at each step,
1-1
w + argmin WERi
Σ (rT + (i+i(sh w To 2 + A|[W|2 + IN(w), h H H,..., 1,
(3.7)
where we V (r, E [K] x [ - 1]. Here & is the index of episode, À > is a tuning parameter, and L is a regularizer, which is constructed based the confounded observational data. More specifically, define
for all e [K] and VT+ defined in Line 7 of Algorithm for all
(WW (r (5h11) - w Tn ah wh)) ((k,)) E [K] [H],
(3.8)
which corresponds to the least-squares loss for regressing rí + V++1 ($/+1) against on (s), of w/)) for all i E [n]. Here {(s), we (() are the confounded observational data, where
7

---

2/ ~ ( s%)), $/41 ~ Pa(-1 sy d d,), and aj ~ 1%(- (-11,,,, w/)) with v = fu hne(m being the behavior policy. Here recall that, with a slight abuse of notation, we write P( 8h ahs un) as (sh+2 sh. Oh, un) and P(u, (h) as Ph(up, sh), since they are induced by the SCM defined in $2.
The update in (3.7) takes the following explicit form,
wh
(AA) -1
Σ (sh añ) Vitt(ch+11 rT))
nh (s ais u/) ( (1 + + )
(3.9)
where
k-1 A Σ
( a
+
on (n ah (sh abs u/) + AI.
(3.10)
Uncertainty Quantification. We now construct the UCB ( of the point estimator tha (t..)) Tuft obtained from (3.9), which encourages the exploration of the less visited state-action pairs. To this end, we employ the following notion of information gain to motivate the UCB,
1% (s a x H (w* (x-1) 11 (w Ex- (( a)))),
(3.11)
where Hw (k-1) is the differential entropy of the random variable w given the data & In particular, Ek-1 = {(5%, 47 (r.t)e(--1))) U {(s) of " r ra) confounded observational data and the interventional data up to the (k - 1)-th episode. However, challenging to characterize the distribution of w To this end, we consider a Bayesian counterpart of the confounded MDP, where the prior of w [N, and the residual the regression problem (3.7) (0, 1). In such "parallel" confounded MDP, the posterior of w follows N (uu.,, (1)) where A defined in (3.10) and Pæ, coincides with the right-hand side of (3.9). Moreover, holds for all (sh at) E x A that
consists of the
(w (x-1) = 1/2 log det (2 (A)) H (w]) Ex-1 U (55.. o(1)) 1/2 log det (2Te)) (A + tha (s dh (sh, a )
Correspondingly, employ the following UCB, which instantiates (3.11), that is,
( att 3. det det (Af, + (n a vn (5% T) log det det(A 1/2
(3.12)
for all (s), af) E ES A. Here > 0 is a tuning parameter. We highlight that, although the information gain in relies on the "parallel" confounded MDP, the UCB in (3.12), which is used in Line of Algorithm 1, does not rely on the Bayesian perspective. Also, our analysis establishes the frequentist regret.
Regularization with Observational Data: Bayesian Perspective. In the "parallel" confounded MDP, it holds that
w 1/AA, w/th Eo ~ N (PLA, (A)) wht 1 ~ N (HR,A (A
where Pksh coincides with the right-hand side of (3.9) and μ4, is defined by setting k = 1 in PAR, Here &o = {s), af (..ri. ht..rraaaeee are the confounded observational data. Hence, the regularizer Т in (3.8) corresponds to using wh Eo as the prior for the Bayesian regression problem given only the interventional data E Eo {(8), 0% (r)))
3.2 Theory
The following theorem characterizes the regret of DOVI, which is defined in (2.3).

---

Theorem 3,5 (Regret of DOVI), Let 3 = CdH CdH /log(d(T + +H) and À = 1, where C > 0 and ç E (0, 1] are absolute constants. Under Assumptions 3.1 and 3.3, it holds with probability least
1 - 5C/2 that
(egret(T) S C² AH WHTT. /log(d((+n/f)/)
(3.13)
where C' > 00 is am absolute constant and
H
(log (At, (Axtt) - log del(A 1/2
AH
(3.14)
vHH2
Proof. See gF.3 for a detailed proof.
Note that A AKt (n + K + X)T and A1, ž AT for all h. E [H]. Hence, it holds that Aи Olv ((ylog(n + K + 1)) in the worst case. Thus, the regret of DOVI ((vBsH3T)) up logarithmic factors, which is optimal in the total number of steps T if we only consider the online setting. However, Δи is possibly much smaller than (V + K + 1)), depending on the amount of information carried over by the confounded observational data from the offline setting, which is quantified in the following.
Interpretation of A An Information-Theoreti Perspective. Let w7 be the parameter of the globally optimal action-value function Qh which corresponds to x² in (2.3). Recall that we de- note by Eo and Êx the confounded observational data {( of u/, r%) (r.)))))) and the union {(s), a who ((.))) (H) U {( oh J x of the confounded observational data and the interventional data up to the K-th episode, respectively. We consider the aforementioned Bayesian counterpart of the confounded MDP, where the prior of w is also N (00, In such "parallel" confounded MDP, we have
wh, N(O, where
wf (HLLA, w/ WE NuKK -
(3.15)
Fi, (AA) Σ
sn ai u/) (Vi+n(5h+z) ( +rh):
s=1
PkA (A
Σ
(n (oaoaa(-VViiitaaa (Vi+z((h++a) + +r))
then holds for the right-hand side of (3.14) that
1/2 log (A
( - 1/2 log det(AA) H (W (5)) H(W (k)
(3.16)
The left-hand side of (3.16) characterizes the information gain of intervention in the online setting given the confounded observational data in the offline setting. In other words, if the confounded observational data are sufficiently informative upon the backdoor adjustment, then Ay is small, which implies that the regret is small. More specifically. the matrices (A1) and (A + de- fined in 13) characterize the ellipsoidal confidence sets given Eo and εK. respectively. If the confounded observational data sufficiently informative upon the backdoor adjustment, AK+1 is close A/.- To illustrate, let (1%, aT)) (r, ()E[K] and ( i af, u/, ((,))) be sampled uniformly random from the canonical basis fer)rejd) of Ed. It then holds that A K-1 ~ (K + 1)//dd + AI and A3 R nl/d+ + XI. Hence, for X ==1 1 and sufficiently large n and K, we have Aи O( Vlo((1 K/(n d])) O (K/K/(n + d)). For example, for n 9(K3), holds that A O1222) which implies that the regret DOVI is O1n H3*H In other words, if the confounded observational data are sufficiently informative upon the backdoor adjustment, the regret of DOVI can be arbitrarily small given sufficiently large sample size n of the confounded observational data, which is often the case in practice [8, 9, 21, 22, 29].

---

4 Conclusion
In this paper, propose the deconfounded optimistic value iteration (DOVT) algorithm and its variant DOVI* which incorporate the confounded observational data to the online reinforcement learning in provably efficient manner. DOVI and DOVI+ explicitly adjust for the confounding bias in the observational data via the backdoor and frontdoor adjustments, respectively. In both cases, such adjustments allow us to construct the bonus based on a notion of information gain, which considers the amount of information acquired from the offline dataset. We further conduct regret analysis of DOVI and DOVI* Our analysis suggests that practitioners can tackle the confounding issue in the offiin dataset by estimating the counterfactual reward for value function estimations, given that a proper adjustment such as the backdoor or frontdoor adjustment is available. In the case of backdoor and frontdoor adjustment, we prove that the regret of DOVI is smaller than the optimal regret achievable in the pure online setting when the confounded observational data are informative upon the adjustments, suggesting that one can exploit the confounded observational data in reinforcement learning upon proper adjustments. In our future study, we wish to incorporate proxy variables that are native to MDPs for the adjustments of the offline dataset, such the variables exploited by [4, 24, 40].
Acknolodgements
Zhaoran Wang acknowledges National Science Foundation (Awards 2048075, 2008827, 2015568, 1934931), Simons Institute (Theory of Reinforcement Learning), Amazon, J.P. Morgan, and Two Sigma for their supports. Zhuoran Yang acknowledges Simons Institute (Theory of Reinforcement Learning). The authors also thank the anonymous reviewers, whose invaluable suggestions help the authors to improve the paper.
References
[1] Abbasi-Yadkori, Y., Pál, D. and Szepesvári, C. (2011). Improved algorithms for linear stochas- tic bandits. In Advances in Neural Information Processing Systems.
[2] Azar, M. G., Osband, I. and Munos, R. (2017). Minimax regret bounds for reinforcement learning. In International Conference on Machine Learning.
[3] Balke, A. and Pearl, J. (2013). Counterfactuals and policy analysis in structural models. arXiv preprint 1rXiv:1302.449 4309.4929.
[4] Bennett, A., Kallus, N., Li, L. and Mousavi, A. (2021). Off-policy evaluation in infinite- horizon reinforcement learning with latent confounders. In International Conference on Arti- ficial Intelligence and Statistics.
[5] Bradtke, S. and Barto, A. G. (1996). Linear least-squares algorithms for temporal difference learning. Machine Learning, 22 33-57.
[6] Buesing, L., Weber, T., Zwols, Y., Racaniere, S., Guez, A.. Lespiau, J.-B. and Heess, N. (2018). Woulda, coulda, shoulda: Counterfactually-guue policy search. arXiv preprint 1811.0211
[7] Cai, Q. Yang, Z., Jin, C. and Wang, Z. (2019). Provably efficient exploration in policy opti- mization. arXiv preprint arXiv: 1912.05830.
[8] Chakraborty, B. and Murphy, S. A. (2014). Dynamic treatment regimes. Annual Review of Statistics and Its Application, 1 447-464.
[9] de Haan, P., Jayaraman, D. and Levine, S. (2019). Causal confusion in imitation learning. In Advances in Neural Information Processing Systems.
[10] Díaz, I. and Hejazi, N. (2019). Causal mediation analysis for stochastic interventions. arXiv preprint arviv: /900100007777 02776.
[11] Forney, A., Pearl, J. and Bareinboim, E. (2017). Counterfactual data-fusion for online rein- forcement learners. In International Conference on Machine Learning.
10

---

[12] Hallak, A., Di Castro, D. and Mannor, S. (2015). Contextual Markov decision processes. arXiv preprint arXiv: 1502::25020222
[13] Hessel, M., Modayil, J., Van Hasselt, H., Schaul, T., Ostrovski, G., Dabney, W., Horgan, D., Piot, B., Azar, M. and Silver, D. (2018). Rainbow: Combining improvements in deep rein- forcement learning. In AAAT Conference on Artificial Intelligence.
[14] Jaksch, T., Ortner, R. and Auer, P. (2010). Near-optimal regret bounds for reinforcement learn- ing. Journal of Machine Learning Research, 11 1563-1600.
[15] Jin, C., Allen-Zhu, Z., Bubeck, S. and Jordan, M. I. (2018), Is Q-learning provably efficient? In Advances in Neural Information Processing Systems.
[16] Jin, C., Yang. Z., Wang. Z. and Jordan, M. I. (2019). Provably efficient reinforcement learning with linear function approximation. arXiv preprint arXiv:1907.05388
[17] Kallus, N. and Zhou, (2018). ronfounding-robust policy improvement. In Advances in Neural Information Processing Systems.
[18] Kallus, N. and Zhou, A. (2018). Policy evaluation and optimization with continuous treat- ments. arXiv preprint
[19] Kober, J., Bagnell, J. A. and Peters, J. (2013). Reinforcement learning in robotics: Asurvey. International Journal of Robotics Research, 32 1238-1277 1274.
[20] Lattimore, F., Lattimore, T. and Reid, M. D. (2016). Causal bandits:
Learning good interven-
tions via causal inference. In Advances in Neural Information Processing Systems.
[21] Levine, S., Kumar, A., Tucker, G. and Fu, J. (2020). Offline reinforcement learning: Tutorial, review, and perspectives on open problems. arXiv preprint arXiv:2005.01643.
[22] Li, C., Chan, S. H. and Chen, Y.TT. (2020). Who make drivers stop? Towards driver- centric risk assessment: Risk object identification via causal inference. arXiv:2003.02425.
arXiv preprint
[23] Li, J., Monroe, W., Ritter, A., Galley, M., Gao, J. and Jurafsky, D. (2016). Deep reinforcement learning for dialogue generation. arXiv preprint orXiv:1606.015:
[24] Liao, L., Fu, Z., Yang, Z., Kolar, M. and Wang, Z. (2021). Instrumental variable value iteration for causal offline reinforcement learning. arXiv preprint arXiv:2102.09907,
[25] Lu, C., Schölkopf, B. and Hernández-Lobato, J. M. (2018). Deconfounding reinforcement learning in observational settings. arXiv preprint arXiv:1812.10575
[26] Lu, Y., Meisami, A., Tewari, A. and Yan, Z. (2019). Regret analysis of causal bandit problems. arXiv preprint arXiv: 010.049993.
[27] Manski, C. F. (1990). Nonparametric bounds on treatment effects. American Economic Re- view, 80 319-323.
[28] Muñoz, I. D. and van der Laan, M. (2012). Population intervention causal effects based on stochastic interventions. Biometrics, 68 541-549.
[29] Murphy, S. A. (2003). Optimal dynamic treatment regimes. Journal of the Royal Statistical Society: Series (Statistical Methodology), 65 331-355.
[30] Namkoong, H., Keramati, R., Yadlowsky, S. and Brunskill, E. (2020). Off-policy pol- icy evaluation for sequential decisions under unobserved confounding. arXiv:2003.05623.
arXiv preprint
[31] Osband, I,, Van Roy, B. and Wen, Z. (2014). Generalization and exploration via randomized value functions. arXiv preprint
[32] Pearl, J. (2009). Causality. Cambridge university press.

---

[33] Peters, J.. Janzing, D. and Schölkopf. B. (2017). Elements of Causal Inference: Foundations and Learning Algorithms. MIT press.
[34] Sen, R., Shanmugam, K., Dimakis, A. G. and Shakkottai, S. (2017). Identifying best interven- tions through online importance sampling. In International Conference Machine Learning.
[35] Shang, W., Yu, Y., Li, Q., Qin, Z., Meng, Y. and Ye, J. (2019). Environment reconstruction with hidden confounders for reinforcement learning based recommendation. In Proceedings of the 25th ACM SIGKDD International Conference Knowledge Discovery & Data Mining-
[36] Silver, D., Huang, A., Maddison, J., Guez, A., Sifre, L., Van Den Driessche, G., Schrittwieser, J., Antonoglou, I., Pamneershelvam, V., Lanctot, M. et al. (2016). Master- ing the game of Go with deep neural networks and tree search. Nature, 529 484.
[37] Silver, D., Schrittwieser, J., Simonyan, K., Antonoglou, I., Huang. A., Guez, A., Hubert, T., Baker, I.,, Lai, M., Bolton, A. et al. (2017). Mastering the game of Go without human knowl- edge. Nature, 550 354.
[38] Tan, Z. (2006). A distributional approach for causal inference using propensity scores. Journal of the American Statistical Association, 101 1619-1637.
[39] Tennenholtz, G., Mannor, S. and Shalit, U. (2019). Off-policy evaluation in partially observ- able environments. arXiv preprint urXiv:1909. 1909.03739.
[40] Tennenholtz, G., Shalit, U. and Mannor, S. (2020). Off-policy evaluation in partially observ- able environments. In Proceedings of the AAAI Conference on Artificial Intelligence, vol. 34.
[41] Vershynin, (2010). Introduction to the non-asymptotic analysis of random matrices. arXiv preprint arXiv: 1r1 001011111....
[42] Yang, L. and Wang. M. (2019). Samplc-optimal parametric Q-learning using linearly additive features. In International Conference on Machine Learning.
[43] Yang, L. F. and Wang, M. (2019). Reinforcement leaning in feature space: Matrix bandit, kernels, and regret bound. arXiv preprint arXiv:1905. 10389.
[44] Zhang, J. and Bareinboim, E. (2017). Transfer learning in multi-armed bandit: A causal ap- proach. In Autonomous Agents and Multi-Agent Systems.
[45] Zhang, J. and Bareinboim, E. (2019). Near-optimal reinforcement learning in dynamic treat- ment regimes. In Advances Neural Information Processing Systems.
12


Reviews:
[{"review_id": "rEuFOdTBJbi", "reviewer": "Reviewer_8cdv", "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.", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nMajor weaknesses:\n- 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.\n- 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.\n- 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.\n- 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.\n- 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”.\n\nOther minor issues / comments / suggestions / typos:\n- Typo in line 4 “semple\" -> “sample”\n- 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.\n- For fairness, since all presentation and discussion of DOVI+ was deferred to appendix, I am not taking it into account when assessing the paper.\n- 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.\n- 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?\n- You refer to Figure 4 on line 216, but there appears to be no Figure 4 in the paper.\n- 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.\n- In assumption 3.3, is $\\phi_h$ meant to be a fixed given feature map? This is not explained.\n- 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$.\n- Typo on lines 249-250 “is know” -> “is known”.\n- 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?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I have no concerns here.", "review_text": "", "extra_scores": {"ethical_concerns": "I have no ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "X559JlrSoBZ", "reviewer": "Reviewer_uXJG", "summary": "This is a technical paper presenting how to incorporate offline observational data to improve the sample efficiency in the online reinforcement learning setting.\nThe 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.\nThe 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.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nThe 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.\n\nMajor comments:\n- 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.\n- Are the authors the first to state a Backdoor Adjusted Bellman Equation? this is not clear in the paper.\n- It is also not clear to me where the distinction between the observational and interventional data is in algorithm 1?\n\nMinor comments:\n- the abstract format is not correct.\n- line 4: semple -> sample\n- lines 56 and 57: please give references.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "-", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "RnBtRZ7hjEK", "reviewer": "Reviewer_wam3", "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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. \n\n(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?\n\n(2) Experiments:\n- 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. \n- Since the regret guarantee greatly depends on the linear confounded MDPs assumption, performing some sensitivity analysis on that would be very important.\n\nOverall, 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.\n\nMinor typo:\n- L4: \"semple\" -> \"sample\"\n\n*Update after the author response*\nI 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. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Based on the checklist answer, the authors did not address the limitations of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2 hours"}, "extra_text": {}}, {"review_id": "KiTaNyucEj6", "reviewer": "Reviewer_czeu", "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.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nQuality: The work is technically sound,while an empirical evaluation is needed to confirm the effectiveness of the proposed algorithms\n\n\nClarity: The paper is well-written and easy to follow. Necessary assumptions are stated.\n\nSignificance: 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. \n\n\nDetailed comments:\n\nThe 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. \n\nThe 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. \n\nIs 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). \n\nIn 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? \n\nHow do these assumptions, frontdoor exist, be mapped from the real-world example?\n\nHow 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.\n\n\n\n\nHow 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.\nHow to derive a practical RL algorithm?\n\nBackdoor adjustment limits the applicability of the algorithm/method. Can you give some practical scenarios where these are held?\n\nWhat 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?\n\nNot clear why the reward function in equation 3.2 is called the counterfactual reward function.\n\n\n\nIs 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?\n\n\n\nEmpirical 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.\n\nThe 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.\n\nHow does the confounded MDP relate to the previously proposed Block MDP[1]?\n\nThe 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.\n\nThe paper seems to end abruptly without a proper conclusion. I suggest adding a conclusion or discussion section summarizing the contribution and results.\n\n\n\nReference:\n[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.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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).\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6 hours"}, "extra_text": {}}]

Author rebuttal:

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)