Provably Efficient Causal Reinforcement Learning with Confounded Observational Data

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.

text: 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.

heading: 1 Introduction
text: Empowered by the breakthrough in neural networks, deep reinforcement learning (DRL) achieves significant empirical successes in various scenarios [19, 23, 36, 37]. Learning an expressive function approximator necessitates collecting a large dataset. Specifically, in the online setting, it requires the agent to interact with the environment for a large number of steps. For example, to learn a human-level policy for playing Atari games, the agent has to interact with a simulator for more than 108 steps [13]. However, in most scenarios, we do not have access to a simulator that allows 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 a result, it remains challenging to apply DRL to more scenarios.
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, in 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 a provably efficient way, we have to address two challenges.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
• The observational data are possibly confounded. Specifically, there often exist unobserved random 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 prescriptions 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). Meanwhile, 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 concerns. Such a 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, it is unclear from the observational data whether the outcome is due to the actions adopted.
• Even without the confounding issue, it remains unclear how the observational data may facilitate exploration in the online setting, which is the key to the sample efficiency of RL. At the core of exploration is uncertainty quantification. Specifically, quantifying the uncertainty that remains given the dataset collected up to the current step, including the observational data and the interventional data, allows us to construct a bonus. When incorporated into the reward, such a bonus encourages the agent to explore the less visited state-action pairs with more uncertainty. In particular, constructing such a 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 confounded. 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 a 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 in 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], we propose the deconfounded optimistic value iteration (DOVI) algorithm, which explicitly corrects for the confounding 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 DOVI+ follows the same principle of design as DOVI and defer the discussion of DOVI+ to §A.
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 a 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 ∆H · √ d3H3T -regret up to logarithmic factors, where d is the dimension of features, H is the length of each episode, and T = HK is the number of steps taken in the online setting, where K is the number of episodes. Here the multiplicative factor ∆H > 0 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, ∆H is a logarithmic factor. Correspondingly, DOVI and DOVI+ attain the optimal√ T -regret achievable in the pure online setting [7, 16, 42, 43]. When the observational data are sufficiently informative upon the adjustments, ∆H 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 a combination of the online setting and the offline setting. Causal RL is more challenging than causal bandit, which corresponds toH = 1, as it involves the transition dynamics and is more challenging in exploration. See §B for a detailed literature review on causal bandit.
Our work is related to the study of causal RL considered in various settings. [45] propose a modelbased RL 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 information 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 → +∞. 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 effect 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 exploration 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 in a combination of the online setting and the offline setting. Their algorithm uses a variational autoencoder (VAE) for estimating a structural causal model (SCM) based on the confounded observational data. In particular, their algorithm utilizes the actor-critic algorithm to obtain the optimal policy in such an SCM. However, the regret of their algorithm remains unclear. [6] propose a model-based RL 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 adversarial 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 offpolicy 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.

heading: 2 Confounded Reinforcement Learning
text: Structural Causal Model. We denote a structural causal model (SCM) [32] by a tuple (A,B, F, P ). Here A is the set of exogenous (unobserved) variables, B is the set of endogenous (observed) variables, F is the set of structural functions capturing the causal relations, which determines an endogenous 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 Z are confounded by a variable W if they are both caused by W .
An intervention on a set of endogenous variables X ⊆ B assigns a value x to X regardless of the other exogenous and endogenous variables as well as the structural functions. We denote by do(X = x) the intervention on X and write do(x) if it is clear from the context. Similarly, a stochastic intervention [10, 28] on a set of endogenous variables X ⊆ 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 .
Confounded Markov Decision Process. To characterize a 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 {sh}h∈[H], actions {ah}h∈[H], and rewards {rh}h∈[H]. Let {wh}h∈[H] be the confounders. In §3, we assume that the confounders are partially observed, while in §A, we assume that they are unobserved. The set of structural functions F consists of the transition of states sh+1 ∼ Ph(· | sh, ah, wh), the transition of confounders wh ∼ P̃h(· | sh), the behavior policy ah ∼ νh(· | sh, wh), which depends on the confounder wh, and the reward function rh(sh, ah, wh). See Figure 1 for the causal diagram that describes such an SCM.
Here ah and sh+1 are confounded by wh in addition to sh. We denote such a confounded MDP by the tuple (S,A,W, H,P, r), where H is the length of an episode, S, A, andW are the spaces of states, actions, and confounders, respectively, r = {rh}h∈[H] is the set of reward functions, and P = {Ph, P̃h}h∈H is the set of transition kernels. In the sequel, we assume without loss of generality that rh takes value in [0, 1] for all h ∈ [H]. In the online setting that allows for intervention, we assume that the confounders {wh}h∈[H] are unobserved. A policy π = {πh}h∈[H] induces the stochastic intervention do(a1 ∼ π1(· | s1), . . . , aH ∼ πH(· | sH)), which does not depend on the confounders. In particular, an agent interacts with the environment as follows. At the beginning of the k-th episode, the environment arbitrarily selects an initial state sk1 and the agent selects a policy π
k = {πkh}h∈[H]. At the h-th step of the k-th episode, the agent observes the state skh and takes the action a k h ∼ πkh(· | skh). The environment randomly selects the confounder wkh ∼ P̃h(· | skh), which is unobserved, and the agent receives the reward rkh = rh(s k h, a k h, w k h). The environment then transits into the next state skh+1 ∼ Ph(· | skh, akh, wkh).
For a policy π = {πh}h∈H , which does not depend on the confounders {wh}h∈[H], we define the value function V π = {V πh }h∈[H] as follows,
V πh (s) = Eπ [ H∑ j=h rj(sj , aj , wj) ∣∣∣∣ sh = s], ∀h ∈ [H], (2.1) where we denote by Eπ the expectation with respect to the confounders {wj}Hj=h and the trajectory {(sj , aj)}Hj=h, starting from the state sj = s and following the policy π. Correspondingly, we define the action-value function Qπ = {Qπh}h∈[H] as follows,
Qπh(s, a) = Eπ [ H∑ j=h rj(sj , aj , wj) ∣∣∣∣ sh = s,do(ah = a)], ∀h ∈ [H]. (2.2)
We assess the performance of an algorithm using the regret against the globally optimal policy π∗ = {π∗h}h∈[H] in hindsight after K episodes, which is defined as follows,
Regret(T ) = max π K∑ k=1 ( V π1 (s k 1)− V π k 1 (s k 1) ) = K∑ k=1 ( V π ∗ 1 (s k 1)− V π k 1 (s k 1) ) . (2.3)
Here T = HK is the total number of steps.
Our goal is to design an algorithm that minimizes the regret defined in (2.3), where π∗ does not depend on the confounders {wh}h∈[H]. 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 realworld 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 a 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 incorporating 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 {wh}h∈[H], which are partially observed (§3) or unobserved (§A), the conditional probability P(sh+1 | sh, ah) in the offline setting is different from the causal effect P(sh+1 | sh,do(ah)) in the online setting [33]. More specifically, it holds that
P(sh+1 | sh, ah) = Ewh∼P̃h(· | sh)
[ Ph(sh+1 | sh, ah, wh) · νh(ah | sh, wh) ] Ewh∼P̃h(· | sh) [ νh(ah | sh, wh)
] , P ( sh+1
∣∣ sh,do(ah)) = Ewh∼P̃h(· | sh)[Ph(· | sh, ah, wh)]. 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 in the online setting. To this end, we propose an 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.

heading: 3 Algorithm and Theory for Partially Observed Confounder
text: In this section, we propose the Deconfounded Optimistic Value Iteration (DOVI) algorithm. DOVI handles the case where the confounders are unobserved in the online setting but are partially observed 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.

heading: 3.1 Algorithm
text: Backdoor Adjustment. In the online setting that allows for intervention, the causal effect of ah on sh+1 given sh, that is, P(sh+1 | sh,do(ah)), plays a 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(sh+1 | sh,do(ah)) if the confounder wh is unobserved. However, if the confounder wh is partially observed in the offline setting, the observed subset uh of wh allows us to identify the causal effect P(sh+1 | sh,do(ah)), as long as uh satisfies the following backdoor criterion. Assumption 3.1 (Backdoor Criterion [32, 33]). In the SCM defined in §2 and its induced directed acyclic graph (DAG), for all h ∈ [H], there exists an observed subset uh of wh that satisfies the backdoor criterion, that is,
• the elements of uh are not the descendants of ah, and
• conditioning on sh, the elements of uh d-separate every path between ah and sh+1, rh that has an incoming arrow into ah.
See Figure 2 for an example that satisfies the backdoor criterion. In particular, we identify the causal effect P(sh+1 | sh,do(ah)) as follows.
Proposition 3.2 (Backdoor Adjustment [32]). Under Assumption 3.1, it holds for all h ∈ [H] that P ( sh+1 ∣∣ sh,do(ah)) = Euh∼P(· | sh)[P(sh+1 | sh, ah, uh)], E [ rh(sh, ah, wh)
∣∣ sh,do(ah)] = Euh∼P(· | sh)[E[rh(sh, ah, wh) ∣∣ sh, ah, uh]]. Here (sh+1, sh, ah, uh) follows the SCM defined in §2, which generates the confounded observational data.
Proof. See [32] for a detailed proof.
With a slight abuse of notation, we write P(sh+1 | sh, ah, uh) as Ph(sh+1 | sh, ah, uh) and P(uh | sh) as P̃h(uh | sh), since they are induced by the SCM defined in §2. In the sequel, we define U the space of observed state uh and write rh = rh(sh, ah, wh) for notational simplicity. Backdoor-Adjusted Bellman Equation. We now formulate the Bellman equation for the confounded MDP. It holds for all (sh, ah) ∈ S ×A that
Qπh(sh, ah) = Eπ [ H∑ j=h rj(sj , aj , uj) ∣∣∣∣ sh,do(ah)] = E[rh ∣∣ sh,do(ah)]+ Esh+1[V πh+1(sh+1)], where Esh+1 denotes the expectation with respect to sh+1 ∼ P(·
∣∣ sh,do(ah)). Here E[rh
∣∣ sh,do(ah)] and P(· ∣∣ sh,do(ah)) are characterized in Proposition 3.2. In the sequel, we define the following transition operator and counterfactual reward function,
(PhV )(sh, ah) = Esh+1∼P(· | sh,do(ah)) [ V (sh+1) ] , ∀V : S 7→ R, (sh, ah) ∈ S ×A, (3.1)
Rh(sh, ah) = E [ rh ∣∣ sh,do(ah)], ∀(sh, ah) ∈ S ×A. (3.2)
We have the following Bellman equation, Qπh(sh, ah) = Rh(sh, ah) + (PhV πh+1)(sh, ah), ∀h ∈ [H], (sh, ah) ∈ S ×A. (3.3)
Correspondingly, the Bellman optimality equation takes the following form, Q∗h(sh, ah) = Rh(sh, ah) + (PhV ∗h+1)(sh, ah), V ∗h (sh) = max
ah∈A Q∗h(sh, ah), (3.4)
which holds for all h ∈ [H] and (sh, ah) ∈ S × A. Such a Bellman optimality equation allows us to adapt the least-squares value iteration (LSVI) 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 a linear SCM [33]. Assumption 3.3 (Linear Confounded MDP). We assume that Ph(sh+1 | sh, ah, uh) = 〈φh(sh, ah, uh), µh(sh+1)〉, ∀h ∈ [H], (sh+1, sh, ah) ∈ S × S ×A, where φh(·, ·, ·) and µh(·) = (µ1,h(·), . . . , µd,h(·))> are Rd-valued functions. We assume that∑d i=1 ‖µi,h‖21 ≤ d and ‖φh(sh, ah, uh)‖2 ≤ 1 for all h ∈ [H] and (sh, ah, uh) ∈ S × A × U . Meanwhile, we assume that E[rh | sh, ah, uh] = φh(sh, ah, uh)>θh, ∀h ∈ [H], (sh, ah, uh) ∈ S ×A× U , (3.5) where θh ∈ Rd and ‖θh‖2 ≤ √ d for all h ∈ [H].
Such a linear setting generalizes the tabular setting where S , A, and U are finite. Proposition 3.4. We define the backdoor-adjusted feature as follows,
ψh(sh, ah) = Euh∼P̃h(· | sh) [ φh(sh, ah, uh) ] , ∀h ∈ [H], (sh, ah) ∈ S ×A. (3.6)
Under Assumption 3.1, it holds that
P(sh+1 | sh,do(ah)) = 〈ψh(sh, ah), µh(sh+1)〉, ∀h ∈ [H], (sh+1, sh, ah) ∈ S × S ×A. Moreover, the action-value functions Qπh and Q ∗ h are linear in the backdoor-adjusted feature ψh for all π.
Proof. See §F.1 for a detailed proof.
Such an observation allows us to estimate the action-value function based on the backdoor-adjusted features {ψh}h∈[H] in the online setting. See §D for a detailed discussion. In the sequel, we assume that either the density of {P̃h(· | sh)}h∈[H] is known or the backdoor-adjusted feature {ψh}h∈[H] 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 estimateQ∗h based on the confounded observational data and the interventional data, and uncertainty quantification, where we construct the upper confidence bound (UCB) of the point estimator.
Algorithm 1 Deconfounded Optimistic Value Iteration (DOVI) for Confounded MDP
Require: Observational data {(sih, aih, uih, rih)}i∈[n],h∈[H], tuning parameters λ, β > 0, backdooradjusted feature {ψh}h∈[H], which is defined in (3.6).
1: Initialization: Set {Q0h, V 0h }h∈[H] as zero functions and V kH+1 as a zero function for k ∈ [K]. 2: for k = 1, . . . ,K do 3: for h = H, . . . , 1 do 4: Set ωkh ← argminω∈Rd ∑k−1 τ=1(r τ h + V τ h+1(s τ h+1) − ω>ψh(sτh, aτh))2 + λ‖ω‖22 + Lkh(ω), where Lkh is defined in (3.8). 5: Set Qkh(·, ·)← min{ψh(·, ·)>ωkh + Γkh(·, ·), H − h}, where Γkh is defined in (3.12). 6: Set πkh(· | sh)← argmaxah∈AQ k h(sh, ah) for all sh ∈ S. 7: Set V kh (·)← 〈πkh(· | ·), Qkh(·, ·)〉A. 8: end for 9: Obtain sk1 from the environment.
10: for h = 1, . . . ,H do 11: Take akh ∼ πkh(· | skh). Obtain rkh = rh(skh, akh, ukh) and skh+1. 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 as follows at each step,
ωkh ← argmin ω∈Rd k−1∑ τ=1 ( rτh + V τ h+1(s τ h+1)− ω>ψh(sτh, aτh) )2 + λ‖ω‖22 + Lkh(ω), h = H, . . . , 1,
(3.7)
where we set V kH+1 = 0 for all k ∈ [K] and V τh+1 is defined in Line 7 of Algorithm 1 for all (τ, h) ∈ [K] × [H − 1]. Here k is the index of episode, λ > 0 is a tuning parameter, and Lkh is a regularizer, which is constructed based on the confounded observational data. More specifically, we define
Lkh(ω) = n∑ i=1 ( rih + V k h+1(s i h+1)− ω>φh(sih, aih, uih) )2 , ∀(k, h) ∈ [K]× [H], (3.8)
which corresponds to the least-squares loss for regressing rih + V k h+1(s i h+1) against φh(s i h, a i h, u i h) for all i ∈ [n]. Here {(sih, aih, uih, rih)}(i,h)∈[n]×[H] are the confounded observational data, where
uih ∼ P̃h(· | sih), sih+1 ∼ Ph(· | sih, aih, uih), and aih ∼ νh(· | sih, wih) with ν = {νh}h∈[H] being the behavior policy. Here recall that, with a slight abuse of notation, we write P(sh+1 | sh, ah, uh) as Ph(sh+1 | sh, ah, uh) and P(uh | sh) as P̃h(uh | sh), since they are induced by the SCM defined in §2. The update in (3.7) takes the following explicit form,
ωkh ← (Λkh)−1 ( k−1∑ τ=1 ψh(s τ h, a τ h) · ( V kh+1(s τ h+1) + r τ h ) +
n∑ i=1 φh(s i h, a i h, u i h) · ( V kh+1(s i h+1) + r i h )) , (3.9)
where
Λkh = k−1∑ τ=1 ψh(s τ h, a τ h)ψh(s τ h, a τ h) > + n∑ i=1 φh(s i h, a i h, u i h)φh(s i h, a i h, u i h) > + λI. (3.10)
Uncertainty Quantification. We now construct the UCB Γkh(·, ·) of the point estimator ψh(·, ·)>ωkh 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,
Γkh(s k h, a k h) ∝ H(ωkh | ξk−1)−H ( ωkh | ξk−1 ∪ {(skh, akh)} ) , (3.11)
where H(ωkh | ξk−1) is the differential entropy of the random variable ωkh given the data ξk−1. In particular, ξk−1 = {(sτh, aτh, rτh)}(τ,h)∈[k−1]×[H] ∪ {(sih, aih, uih, rih)}(i,h)∈[n]×[H] consists of the confounded observational data and the interventional data up to the (k − 1)-th episode. However, it is challenging to characterize the distribution of ωkh. To this end, we consider a Bayesian counterpart of the confounded MDP, where the prior of ωkh is N(0, I/λ) and the residual of the regression problem in (3.7) is N(0, 1). In such a “parallel” confounded MDP, the posterior of ωkh follows N(µk,h, (Λ k h) −1), where Λkh is defined in (3.10) and µk,h coincides with the right-hand side of (3.9). Moreover, it holds for all (skh, a k h) ∈ S ×A that
H(ωkh | ξk−1) = 1/2 · log det ( (2πe)d · (Λkh)−1 ) ,
H ( ωkh ∣∣ ξk−1 ∪ {(skh, akh)}) = 1/2 · log det((2πe)d · (Λkh + ψh(skh, akh)ψh(skh, akh)>)−1).
Correspondingly, we employ the following UCB, which instantiates (3.11), that is,
Γkh(s k h, a k h) = β ·
( log det ( Λkh + ψh(s k h, a k h)ψh(s k h, a k h) >)− log det(Λkh))1/2 (3.12)
for all (skh, a k h) ∈ S × A. Here β > 0 is a tuning parameter. We highlight that, although the information gain in (3.11) relies on the “parallel” confounded MDP, the UCB in (3.12), which is used in Line 5 of Algorithm 1, does not rely on the Bayesian perspective. Also, our analysis establishes the frequentist regret.
Regularization with Observational Data: A Bayesian Perspective. In the “parallel” confounded MDP, it holds that
ωkh ∼ N(0, I/λ), ωkh | ξ0 ∼ N ( µ1,h, (Λ 1 h) −1), ωkh | ξk−1 ∼ N(µk,h, (Λkh)−1),
where µk,h coincides with the right-hand side of (3.9) and µ1,h is defined by setting k = 1 in µk,h. Here ξ0 = {(sih, aih, uih, rih)}(i,h)∈[n]×[H] are the confounded observational data. Hence, the regularizer Lkh in (3.8) corresponds to using ω k h | ξ0 as the prior for the Bayesian regression problem given only the interventional data ξk−1 \ ξ0 = {(sτh, aτh, rτh)}(τ,h)∈[k−1]×[H].

heading: 3.2 Theory
text: The following theorem characterizes the regret of DOVI, which is defined in (2.3).
Theorem 3.5 (Regret of DOVI). Let β = CdH √
log(d(T + nH)/ζ) and λ = 1, where C > 0 and ζ ∈ (0, 1] are absolute constants. Under Assumptions 3.1 and 3.3, it holds with probability at least 1− 5ζ/2 that
Regret(T ) ≤ C ′ ·∆H · √ d3H3T · √ log ( d(T + nH)/ζ ) , (3.13)
where C ′ > 0 is an absolute constant and
∆H = 1√ dH2 H∑ h=1 ( log det(ΛK+1h )− log det(Λ 1 h) )1/2 . (3.14)
Proof. See §F.3 for a detailed proof.
Note that ΛK+1h (n + K + λ)I and Λ1h λI for all h ∈ [H]. Hence, it holds that ∆H = O( √ log(n+K + 1)) in the worst case. Thus, the regret of DOVI isO( √ d3H3T ) up to logarithmic factors, which is optimal in the total number of steps T if we only consider the online setting. However, ∆H is possibly much smaller than O( √ log(n+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 ∆H : An Information-Theoretic Perspective. Let ω∗h be the parameter of the globally optimal action-value function Q∗h, which corresponds to π
∗ in (2.3). Recall that we denote by ξ0 and ξK the confounded observational data {(sih, aih, uih, rih)}(i,h)∈[n]×[H] and the union {(sih, aih, uih, rih)}(i,h)∈[n]×[H] ∪ {(skh, akh, rkh)}(k,h)∈[K]×[H] 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 ω∗h is also N(0, I/λ). In such a “parallel” confounded MDP, we have
ω∗h ∼ N(0, I/λ), ω∗h | ξ0 ∼ N ( µ∗1,h, (Λ 1 h) −1), ω∗h | ξK ∼ N(µ∗K,h, (ΛK+1h )−1), (3.15)
where
µ∗1,h = (Λ 1 h) −1 n∑ i=1 φh(s i h, a i h, u i h) · ( V ∗h+1(s i h+1) + r i h ) ,
µ∗K,h = (Λ K+1 h )
−1 (
Λ1hµ ∗ 1,h + K∑ τ=1 ψh(s τ h, a τ h) · ( V ∗h+1(s τ h+1) + r τ h )) .
It then holds for the right-hand side of (3.14) that
1/2 · log det(ΛK+1h )− 1/2 · log det(Λ 1 h) = H(ω ∗ h | ξ0)−H(ω∗h | ξ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 ∆H is small, which implies that the regret is small. More specifically, the matrices (Λ1h) −1 and (ΛK+1h ) −1 defined in (3.10) characterize the ellipsoidal confidence sets given ξ0 and ξK , respectively. If the confounded observational data are sufficiently informative upon the backdoor adjustment, ΛK+1h is close to Λ1h. To illustrate, let {ψh(sτh, aτh)}(τ,h)∈[K]×[H] and {φh(sih, aih, uih)}(i,h)∈[n]×[H] be sampled uniformly at random from the canonical basis {e`}`∈[d] of Rd. It then holds that ΛK+1h ≈ (K + n)I/d + λI and Λ1h ≈ nI/d + λI . Hence, for λ = 1 and sufficiently large n and K, we have ∆H = O( √ log(1 +K/(n+ d))) = O( √ K/(n+ d)). For example, for n = Ω(K2), it holds that ∆H = O(n−1/2), which implies that the regret of DOVI is O(n−1/2 · √ d3H3T ). In other words, if the confounded observational data are sufficiently informative upon the backdoor adjustment, the regret of DOVI can be arbitrarily small given a sufficiently large sample size n of the confounded observational data, which is often the case in practice [8, 9, 21, 22, 29].

heading: 4 Conclusion
text: In this paper, we propose the deconfounded optimistic value iteration (DOVI) algorithm and its variant DOVI+, which incorporate the confounded observational data to the online reinforcement learning in a 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 offline 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 as 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.

Review summaries:
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.

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. 

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.

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.