Reinforcement learning (RL) has been successfully applied in online settings (e.g., video games) where interaction with environments is easy and the data can be adaptively generated. However, online interaction is often costly and dangerous for a number of high-stake domains ranging from health science to social science and economics. Offline (batch) reinforcement learning is concerned with policy learning and evaluation with limited and pre-collected data in a sample efficient manner (Levine et al., 2020). The focus of this paper is the off-policy evaluation (OPE) problem, which refers to the task of estimating the value of an evaluation policy offline using data collected under a different behavior policy. It is critical in sequential decision-making problems from healthcare, robotics, and education where new policies need to be evaluated offline before online validation.
There is a growing literature on OPE (see e.g., Precup, 2000;Jiang & Li, 2016;Thomas & Brunskill, 2016;Liu et al., 2018;Xie et al., 2019;Yin & Wang, 2020;Liao et al., 2020;Yang et al., 2020;Pananjady & Wainwright, 2021;Kuzborskij et al., 2021;Zhang et al., 2021;Shi et al., 2021). A common assumption made in the aforementioned works is that of no unmeasured confounders. Specifically, they assume the time-varying state variables are fully observed and no unmeasured variables exist that confound the observed actions. However, this assumption is not testable from the data. It is often violated in observational datasets generated from healthcare applications.
To allow unmeasured confounders to exist, we model the observed data by a Partially Observable Markov Decision Process (POMDP). Under this framework, the behavior policy is allowed to depend on some unobserved state variables that confound the action-reward association. The goal of OPE in POMDPs is to estimate the value of an evaluation policy, which is a function of observed variables, using the data generated by such a behavior policy. This is a highly challenging problem. Directly applying the importance sampling methods (Precup, 2000;Liu et al., 2018) or the value function-based method (Munos & Szepesvári, 2008) would yield a biased estimator, as we do not have access to the unobserved state variables. Tennenholtz et al. (2020); Nair & Jiang (2021) have made important progresses on this problem by outlining a consistent OPE estimator in tabular settings. However, they are not applicable to settings with continuous observation/state spaces.
In this paper, we study OPE in non-tabular POMDPs. Our contributions are summarized as follows. First, we provide a novel identification method for OPE with latent confounders. We only require the existence of two bridge functions, corresponding to a weight bridge function and a value bridge function. These bridge functions are defined as solutions to some integral equations. They can be interpreted as projections of the marginalized importance sampling weight and value functions defined on the latent state space onto the observation space. They are not always uniquely defined, but we do not require the uniqueness assumption to achieve consistent estimation.
Second, we propose minimax learning methods to estimate the two bridge functions with function approximation. The proposed method allows us to model these bridge functions via certain highly flexible function approximators (e.g., neural networks) and is thus applicable to settings with continuous or large observation/state spaces. Based on the estimated bridge functions, we further propose three estimators for the target policy's value, corresponding to a value functionbased estimator, a marginalized importance sampling (IS) estimator and a doubly-robust (DR) estimator.
Finally, we systematically study the nonasymptotic and asymptotic properties of the proposed estimators. Specifically, we first show the finite-sample rate of convergence under the realizability and Bellman closedness assumptions on value bridge function. Similar assumptions are imposed on the Q-or density ratio function in fully observable MDP settings (Munos & Szepesvári, 2008;Uehara et al., 2021). Second, when the realizability assumption holds for both bridge functions, we establish the finite-sample rate of convergence of the proposed estimators without assuming Bellman closedness. Finally, when the bridge functions are uniquely defined, we prove that the DR estimator is asymptotically normal and achieves the Cramér-Rao lower bound. We expect our findings to contribute to the theoretical understanding of offline RL (see e.g., Munos & Szepesvári, 2008;Chen & Jiang, 2019;Kallus & Uehara, 2019).
We discuss some related works on OPE with unmeasured confounders and spectral learning in this section. To save space, some additional related works on minimax estimation and negative controls are discussed in Appendix A.
To handle unmeasured confounders, existing OPE methods can be roughly divided into the following three categories. The first type of methods proposes to develop partial identification bounds for the policy value based on sensitivity analysis (Kallus & Zhou, 2020;Namkoong et al., 2020;Zhang & Bareinboim, 2021). These methods rely on certain assumptions that might be difficult to validate in practice. For instance, Kallus & Zhou (2020) imposes a memoryless unmeasured confounding assumption.
The second type of methods derive the value estimates by making use of some auxiliary variables in the observed data (Zhang & Bareinboim, 2016;Futoma et al., 2020;Wang et al., 2020;Bennett et al., 2021;Liao et al., 2021;Ying et al., 2021;Shi et al., 2022b). These methods are not directly applicable to the POMDP setting we consider. For instance, Zhang & Bareinboim (2016); Wang et al. (2020); Liao et al. (2021); Shi et al. (2022b) propose to model the observed data via a confounded MDP. In these settings, the time-varying observations satisfy the Markov property. However, the Markov assumption is violated in POMDPs.
The third type of methods adopt the POMDP model to formulate the confounded OPE problem and develop value estimators in tabular settings (Tennenholtz et al., 2020;Nair & Jiang, 2021). However, as we have commented, these methods are ineffective in non-tabular settings with continuous or large observation/state spaces.
Spectral learning in POMDPs Our proposal is closely related to a line of works on developing spectral learning methods in the POMDP literature (Song et al., 2010;Boots et al., 2011;Hsu et al., 2012;Anandkumar et al., 2014;Hefny et al., 2015;Kulesza et al., 2015;Jin et al., 2020a). These methods are originally designed for learning system dynamics in the absence of unmeasured confounders. They would yield biased value estimators in the presence of unmeasured confounders.
We consider a discounted Partially Observable Markov Decision Process (POMDP) defined as S, A, O, {r t } t≥0 , {P t } t≥0 , {Z t } t≥0 , γ , where S denotes the state space, A denotes the finite action space, O denotes the observation space, P t : S × A → ∆(S) denotes the state transition kernel at time t, Z t : S → ∆(O) denotes the observation function that defines the conditional distribution of the observation given the state at time t, r t : S × A → R denotes a bounded reward function that depends on the state-action pair at time t, and γ ∈ [0, 1) is a discount factor that balances the immediate and future rewards. P t , r t and Z t are unknown to us and need to be inferred from the observed data.
The data generating process in POMDPs is depicted in Figure 1. Suppose the environment is in a given state s ∈ S. The agent selects an action a ∈ A. Then the system transits into a new state s and gives an immediate reward r(s, a) to the agent. While we cannot directly observe the latent state s, we have access to an observation o ∼ Z(•|s). This model is adopted from Tennenholtz et al. (2020) where the observation does not depend on the previous action. Nonetheless,
where ν 0 denotes the initial state distribution. The observed data up to t is given by τ
We denote its distribution by P π . The policy value J(π) is defined as the expected cumulative reward E π [ H t=0 γ t R t ] for some 0 < H ≤ +∞, where the expectation is taken w.r.t. the distribution of trajectories induced by policy π.
For a given evaluation policy π e = {π e t } t , the goal of OPE is to estimate J(π e ) from an observational dataset generated by a behavior policy π b = {π b t } t . Similar to Tennenholtz et al. (2020), we focus on the setting where π b depends only on the latent state and π e depends only on the observation. See also Figure 1. Under this model assumption, the state variables serve as a confounder between the action and the reward at each time. Since the state is not fully observed, the no unmeasured confounder assumption is violated.
Finally, we illustrate the challenge of OPE with latent confounders. If we were to observe the latent state, following the standard OPE methods, we could identify the policy value using the marginalized IS or the value function-based estimator. However, since we cannot observe the state, these methods are not applicable. Naively replacing the state with the observation would yield biased estimators.
To elaborate, we design a toy example with binary observation, state, and action spaces. Specifically, the target policy is a uniform random policy and the behavior policy is given by π b t (1|1) = π b t (0|0) = 1-ε, for some constant 0 < ε < 1 and any t ≥ 0. When ε = 0.5, the action is independent of the latent state and no unmeasured confounders exist. The naive IS or value function-based estimator which replaces the state with the observation is expected to be consistent in that case. We report the true value (computed via the
The data generating process in POMDPs. The evaluation policy in red depends on the observed variables. The behavior policy depends on the hidden state variables.
Monte-Carlo method), our proposed value estimator and the naive estimator when applied to a large dataset with 1e4 trajectories and 100 time points per trajectory in Table 1. It can be seen that the naive method works only when ε = 0.5, as expected. In contrast, the proposed estimator is consistent in all cases.
As a warm-up, we start with a partially observable contextual bandit setting (a special case of POMDP with horizon that equals 1) to present our main idea. Suppose we have N data tuples that are i.i.d. {O -1 , A 0 , O 0 , R 0 } tuples where O -1 denotes the additional observation that is conditionally independent of (A 0 , O 0 , R 0 ) given S 0 . The corresponding Bayesian network is depicted in Figure 2a.
The IS and value-function based estimators are given by
respectively, where q 0 (S 0 , A 0 ) = E[R 0 | S 0 , A 0 ], η 0 = π e 0 /π b 0 denotes the IS ratio, a is an abbreviation of a∈A , and the expectation E without any subscript is taken w.r.t. to the distribution of the offline data. As we have commented, these methods are not applicable since S 0 is unobserved.
To handle unmeasured confounders, we first assume the existence of certain bridge functions that link the target policy's value and the observed data distribution.
We refer to b V (•) as a value bridge function and b W (•) as a weight bridge function.
By definition, weight bridge and value bridge functions can be interpreted as projections of the importance sampling weight (i.e., inverse propensity score) and value functions defined on the latent state space onto the observation space.
It is worthwhile to mention that we do not require these bridge functions to be uniquely defined. When S and O are discrete, the existence of solutions to the integral equations in ( 1) and ( 2) is equivalent to certain matrix rank assumptions; see the assumptions in Nair & Jiang (2021); Boots et al. (2011);Hsu et al. (2012). These assumptions require observed variables to contain sufficient information about unobserved states. Specifically, define a matrix
where o i denotes the ith element in the observation space. Then they require rank(Ω a ) = |S| for any a ∈ A. See Appendix B for details. When S and O are continuous, it follows from Picard's theorem that Assumption 1 is implied by several conditions (Carrasco et al., 2007, Theorem 2.41). Here, we remark the value bridge function is target policy dependent and it might be more appropriate to write b V as b π e V . Nonetheless, to ease the notation, we will remove the superscript π e throughout the paper.
Next, we show that Assumption 1 is a sufficient condition for policy value identification. The following theorem shows that if we know b V and b W in advance, we can consistently estimate the target value J(π e ) from the offline data.
Lemma 1 (Pseudo identification formula). Suppose Assumption 1 holds. Then, for any b V , b W that solve (1),
and
(3)
These formulas outline an IS estimator and a value functionbased estimator for J(π e ). It remains to identify the bridge functions b V and b W . However, even if Assumption 1 holds, it is still very challenging to learn b V and b W from the observed data as their definitions involve the unobserved state S 0 . As such, we refer to Lemma 1 as the "pseudo" identification formula. In the following, we introduce some versions of bridge functions that are identifiable from the observed data.
Definition 1 (Learnable bridge functions). The learnable value bridge function b
Throughout this paper, we use b to denote a bridge function and b to denote a learnable bridge function. The following lemma shows that any bridge function is a learnable bridge function.
Lemma 2. Bridge functions defined as solutions to (1) and
(2) are learnable bridge functions.
We next present an equivalent definition for b W . This characterization is useful when extending our results to the POMDP setting.
As we have commented, the class of bridge functions are difficult to estimate from the observed data. On the other hand, the class of learnable bridge functions is identifiable. However, they are not necessarily bridge functions. Thus, we cannot invoke Lemma 1 for value identification. Nonetheless, perhaps surprisingly, the following theorem shows that we can plug-in any learnable bridge function b V and b W for b V and b W in (3) under Assumption 1.
Theorem 1 (Key identification formula). Assume the existence of value bridge functions and learnable weight bridge functions. Then, letting b W (•) be a learnable weight bridge function, we have
Suppose the existence of weight bridge functions and learnable value bridge functions. Then, letting b V (•) be a learnable value bridge function, we have
We make a few remarks. First, the assumptions in the first and second statements do not imply each other. In both cases, Assumption 1, the existence of bridge functions, plays a critical role in ensuring the validity of the above equations. Specifically, when Assumption 1 holds, the assumptions in both the first and second statements are automatically satisfied, since bridge functions are learnable bridge functions. If we naively replace Assumption 1 with the existence of learnable bridge functions that satisfy equation 2, then Theorem 1 is no longer valid.
Second, Theorem 1 implies that we only need bridge functions to exist, but do not need to identify them. As long as they exist, learnable bridge functions can be used for estimation, which are not necessarily bridge functions.
Third, similar identification methods have been developed in the causal inference literature for evaluating the average treatment effect with double negative controls; see Appendix A. However, their settings differ from ours. For instance, those works require policies to be constant functions of negative controls. In contrast, we allow our evaluation policy to depend on the observation which serves as negative controls in their setting. Finally, Theorem 1 requires the existence of both the value and the (learnable) weight bridge functions. Under certain completeness assumptions, J(π e ) can be uniquely identified by assuming the existence of value bridge functions only, and the discussion is deferred to Appendix C.
In this section, we focus on time-homogeneous POMDPs where P t , Z t , r t , π e t , π b t are stationary over time. We denote them by P, Z, r, π e , π b , respectively. OPE in timeinhomogeneous POMDPs is investigated in Appendices F and G. Our goal is to estimate the target policy's value in the infinite horizon setting (H = ∞). Consider a data tuple (O -, S, O, A, R, S + , O + ) following
where P π b denotes certain distribution over O × S. The observed data tuple is given by (O -, O, A, R, O + ). For example, for a data trajectory {(O t , A t , R t )} 0≤t≤n+1 under π b , the observations can be summarized as {(O t-1 , O t , A t , R t , O t+1 )} 1≤t≤n . The above configuration is satisfied with P π b equal to the occupancy distribution under π b over O × S. This conversion from trajectories to tuples is commonly used in the offline RL literature (Chen & Jiang, 2019). We assume the initial observation distribution
First, we extend our definitions of the bridge functions to the POMDP setting and require their existence in the assumption below. Let w(s) = t≥0 γ t P π e ,t (s)/P π b (s) denote the marginal density ratio where P π e ,t (•) denotes the probability density function of S t under the evaluation policy. In addition, let q π e (a, s) = E π e [ t≥0 γ t R t |A 0 = a, S 0 = s] denote the Q-function. These functions play an important role in constructing marginalized IS and value functionbased estimators in fully observable MDPs. The following bridge functions play similar roles in POMDPs.
Assumption 2 (Existence of bridge functions). There exist value bridge functions b
.
We make several remarks. First, the existence of b W implicitly requires π b (a|s) > 0 and w(s) < ∞ for any a and s. The latter condition is weaker than requiring P π b (s) > 0 for any s. In other words, we do not require the full coverage assumption. Second, when the states are fully observed and S = O, it follows immediately that b V (a, s) = q π e (a, s)π e (a | s) and b W (a, s) = w(s)/π b (a | s). Similar to the bandit setting, these bridge functions can thus be interpreted as projections of the value functions and the marginalized IS weights onto the the observation space. Third, we do not require the bridge functions to be uniquely defined.
Next, we define the learnable bridge functions. They are consistent with those in Definition 1 when γ = 0.
Definition 2 (Learnable bridge functions). Learnable value bridge functions b V are defined as solutions to
Learnable weight bridge functions b W are defined as solutions to
where
Finally, we show our key identification formula under Assumption 2. It extends Lemma 2 and Theorem 1 to the POMDP setting.
Theorem 2 (Key identification theorem).
1. Any bridge function is a learnable bridge function.
2. Suppose the existence of the value bridge function and learnable weight bridge function b W (•). Then,
3. Suppose the existence of the weight bridge function and learnable value bridge function b V (•). Then,
Similar to the bandit setting, any bridge function is a learnable bridge function, but the reverse is not true. However, the target policy's value can be consistently estimated based on any learnable bridge function. In addition, similar to the bandit setting, the existence is equivalent to the rank assumption rank(Pr
Theorem 2 forms the basis of our estimation procedure. It outlines a marginalized IS estimator and a value functionbased estimator for policy evaluation. We remark that conditions in bullet points 2 and 3 do not imply each other. In addition, when Assumption 2 holds, conditions in 2 and 3 are automatically satisfied.
We first propose three value estimators given certain consistently estimated learnable bridge functions bV and bW . We next introduce minimax estimation methods for b V and b W .
Given some bV and bW , we can construct the following IS and value function-based estimators accordingly to Theorem 2. Specifically, define ĴIS and ĴVM to be
respectively, where E D denotes the empirical average over all observed data tuples.
In addition, we can combine the aforementioned two estimators for policy evaluation. This yields the following doubly-robust estimator, ĴDR = E D [J( bW , bV )] where In fully observable MDPs, ĴIS reduces to the marginalized IS estimator (Liu et al., 2018), and ĴDR reduces to the doubly-robust estimator (Kallus & Uehara, 2019). We remark that our proposal is not a trivial extension of these existing methods to the POMDP setting. The major challenge lies in developing identification formulas in Theorem 2 to correctly identify the target policy's value. These results are not needed in settings without unmeasured confounders.
Next, we present our proposal to estimate b V and b W . To estimate b V , a key observation is that, it satisfies the following integral equation,
This motivates us to develop the following minimax learning methods. Specifically, we begin with two function classes V, V † ⊂ {A × O → R} and a regularization parameter λ ∈ R + . We next define the following minimax estimator, bV = arg min
Here, we use the function class V to model the oracle value bridge function, and the function class V † to measure the discrepancy between a given g ∈ V and the oracle learnable value bridge function. In practice, we can use linear basis functions, neural networks, random forests, reproducing kernel Hilbert spaces (RKHSs), etc., to parameterize these functions. In the fully observable MDP setting, the above optimization reduces to Modified Bellman Residual Minimization (MBRM) when λ = 0.5 (Antos et al., 2008) and Minimax Q-learning (MQL) when λ = 0 (Uehara et al., 2020). It is worthwhile to mention that fitted Q-iteration (FQI, Ernst et al., 2005), a popular policy learning method in MDPs, cannot be straightforwardly extended to the POMDP setting. This is because the regression estimator in each iteration of FQI will be biased under the POMDP setting.
Similarly, according to (6), we consider the following estimator for the weight bridge function, bW = arg min
for some function classes W, W † ⊂ {A × O → R} and some λ ∈ R + .
In practice, we recommend to use linear models or RKHSs to parametrize V † and W † . This allows us to get the closedform expression for the inner maximization. To the contrary, V and W can be parametrized by any function classes such as neural networks. When V and W are linear models or RKHSs as well, we can obtain the complete closed-form solution for bW . We discuss this further in Appendix D.
We first investigate the nonasymptotic properties of the value function-based estimator ĴVM . We next study the asymp-totic property of the DR estimator ĴDR . Results of the importance sampling estimator can be similarly derived. We discuss this in Appendix D. Our results extend some recently established OPE theories in MDPs (Munos & Szepesvári, 2008;Chen & Jiang, 2019;Kallus & Uehara, 2019;Uehara et al., 2021) to the POMDP setting. We assume the observed dataset D consist of n i.i.d. copies of (O -, O, A, R, O + ). This i.i.d. assumption is commonly employed in the RL literature to simplify the proof (see e.g., Dai et al., 2020).
We begin with the value function-based estimator. First, to measure the discrepancy between the estimated learnable value bridge function bV and b V , we introduce the Bellman residual error for POMDPs as follows:
Definition 3. The Bellman residual operator T maps a given function
The bellman residual error is defined as
By definition, the Bellman residual error is zero for any learnable bridge function. As such, it quantifies how a given function f deviates from the oracle value bridge functions.
In MDPs, it reduces to the standard Bellman residual error.
We next establish the rate of convergence of bV in the following theorem.
Theorem 3 (Convergence rate of bV ). Set λ > 0 in Equation 8. Suppose (a) there exists certain learnable bridge function that satisfies Equation 5; (b) V and V † are finite hypothesis classes; (c) V contains at least one learnable bridge function; (d) T V ⊂ V † ; (e) There exist some constants
Then, there exists some universal constant c > 0 such that for any δ > 0, with probability
It is important to note we only assume the existence of the learnable value bridge function in (a). We do not impose any assumptions on weight bridge functions. Assumption (b) can be further relaxed by assuming that V and V † are general hypothesis classes. In that case, the convergence rate will be characterized by the critical radii of function classes constructed by V and V † . See e.g., Uehara et al. (2021) for details. Assumption (c) is the realizability assumption. Since learnable bridge functions are not unique, we only require V to contain one of them. Assumption (d) is the (Bellman) closedness assumption. It requires that the discriminator class V † is sufficiently rich and the operator B is sufficiently smooth. These assumptions are valid in several examples, including tabular and linear models. To save space, we relegate the related discussions to Appendix D.
Next, we derive the convergence guarantee of the policy value estimator.
Theorem 4 (Convergence rate of ĴVM ). Suppose the weight bridge functions b W (•) and learnable value bridge functions exist, and Assumption (a)-(e) in Theorem 3 hold. Then, there exists some universal constant c > 0 such that for any δ > 0,
Theorem 4 requires a stronger condition than Theorem 3, as we assume the existence of weight bridge function. Its proof relies on the following key equation,
, where the upper bound for the second term on the righthand-side is given in Theorem 3.
Notice that Theorem 3 relies on the closedness assumption, e.g., Assumption (d). We remark that this condition is not necessary to derive the convergence rate of the final policy value estimator. In Theorem 10 (see Appendix D), we show that when b V ∈ V, b W ∈ V † , similar results can be established without any closedness conditions.
We focus on the DR estimator in this section. We first establish its doubly-robustness property in Theorem 5. It implies that as long as either bW or bV is consistent, the final estimator ĴDR is consistent. Theorem 5 (Doubly-robustness property). Suppose Assumption 2 holds. Then J(f, g) defined in Equation 7 equals J(π e ) as long as either f = b W or g = b V .
We next show that ĴDR is efficient in the sense that it is asymptotically normal with asymptotic variance equal to the Cramér-Rao Lower Bound.
First, we provide the Cramér-Rao Lower Bound. To simplify the technical proof, we focus on the tabular setting. Nonetheless, we conjecture that the same result still holds in the non-tabular setting as well. We leave further investigation of this conjecture to future work. Theorem 6. Suppose S, A, O are finite discrete spaces. Assume rank(Pr
The Cramér-Rao Lower Bound is given by
We impose a rank assumption in Theorem 6. This condition implies that the bridge functions are uniquely defined, and so are the learnable bridge functions. We remark that without such a uniqueness assumption, the Cramér-Rao Lower Bound is not well-defined.
Next, we analyze the property of DR estimator. To avoid imposing certain Donsker conditions (van der Vaart, 1998), we focus on a sample-split version of ĴDR as in Zheng & van der Laan (2011). It splits all data trajectories in D into two independent subsets D 1 , D 2 , computes the estimated bridge function b(1)
W ) based on the data subset in D 2 (D 1 ), and does the estimation of the value based on the remaining dataset. Finally, we aggregate the resulting two estimates to get full efficiency. This yields the following DR estimator,
We summarize the results in the following theorem. Notice that they are valid in the non-tabular setting as well. Theorem 7. Assume the existence and uniqueness of bridge and learnable bridge functions. Suppose bW , b W , bV , b V are uniformly bounded by some constants,
weakly converges to a normal distribution with mean 0 and variance V EIF .
We again, make a few remarks. First, although the estimated bridge functions are required to satisfy certain nonparametric rates only, the resulting value estimator achieves a parametric rate of convergence (e.g. n -1/2 ). This is essentially due to the doubly-robustness property, which ensures that the bias of the estimator can be represented as a product of the difference between the two estimated bridge functions and their oracle values. Second, Theorem 7 derives the asymptotic variance of Ĵ * DR , which can be consistently estimated from the data. This allows us to perform a handy Wald-type hypothesis testing. Finally, Theorem 7 requires a stronger assumption, i.e., the uniqueness of bridge functions, which implies that |S| = |O|. Without this assumption, it remains unclear how to define the L 2 error of the estimated bridge function. However, we would like to remark that imposing the uniqueness condition is not a weakness of our analysis, but the CR lower bound statement we hope to prove does not make sense if the condition fails.
In this section, we evaluate the empirical performance of our method using two synthetic datasets. In both datasets, the state spaces are continuous. Hence, existing POMDP evaluation methods such as Tennenholtz et al. (2020) and Nair & Jiang (2021) are not directly applicable. The discounted factor γ is fixed to 0.95 in all experiments.
Environment We first consider a simple dynamic process with a one-dimensional continuous state space and binary actions. Similar environments have been considered in the literature (see e.g., Shi et al., 2022a). The initial state distribution, reward function and state transition are given by
respectively. The observation is generated according to the additive noise model,
Here, the variance parameter σ O characterizes the degree of partial observability and hence the degree of unmeasured confounding. In the extreme case where σ O = 0, the states become fully-observable and no unmeasured confounders exist. We set the behavior and target policies to be sigmoid functions of the state and the observation, respectively,
Implementation and Baseline Method We use linear basis functions to approximate the bridge functions. In this case, the proposed three estimators ( ĴVM , ĴIS , ĴDR ) coincide with each other (see a similar phenomenon in Uehara et al., 2020), so we compute the value function-based estimator only. We compare our estimator to the standard linear value function-based estimator that assumes no unmeasured confounders, i.e., LSTDQ (Lagoudakis & Parr, 2003). See additional implementation details in Appendix E.
For each simulation, we first generate 2000 trajectories with 100 time points per trajectory. This yields a total of 2e5 observations. Reported in the upper panels of Figure 3 are the logarithms of relative mean squared errors of the proposed and baseline methods, with different choices of ω and σ O . We make a few observations. First, when σ O ≥ 1, the proposed estimator is significantly better than the baseline estimator. Second, when σ O = 0.5, the two methods perform comparably. As we have commented, σ O measures the degree of unmeasured confounding. For moderately large σ O , the baseline estimator cannot handle unmeasured confounders, yielding a biased estimator. In contrast, a smaller σ O produces a less confounded dataset. The two estimators thus achieve similar performance.
We next fix σ O to 1.0, vary the number of trajectories generated in each simulation, and report the corresponding relative biases and mean squared errors of the proposed and baseline methods as well as the associated confidence intervals in the bottom panels of Figure 3 and Figure 5 (see Appendix E). It can be seen that the baseline estimator suffers from a large bias. Their bias and MSE are constant as functions of sample size. To the contrary, the bias and MSE of the proposed estimator generally decrease with the sample size, demonstrating its consistency.
We next consider the CartPole environment from the Ope-nAI Gym environment (Brockman et al., 2016). The state variables are 4-dimensional and fully-observable. To create partially observable environments, we simulate observations by either adding independent Gaussian noises to each dimension of the states, i.e., O (j) = S (j) (1 + N (0, 0.1 2 )), 1 ≤ j ≤ 4, or removing the location of the cart from the observation. To generate data, we apply DQN (Mnih et al., 2015) to the data that include latent states instead of observations, and set the behavior policy to a softmax policy based on the estimated Q-function. The evaluation policy is set to another softmax policy based on DQN applied to the observational data (i.e., no latent states) with the temperature parameter given by τ O . For each simulation, we collect the dataset according to the behavior policy until the sample size reaches 2e5. We consider three
We study OPE on POMDPs where behavior policies depend on unobserved state variables. We propose a novel identification method for the target policy's value in the presence of unmeasured confounders. Our proposal only relies on the existence of bridge functions. We further propose minimax learning methods for computing these estimated bridge functions that can be naturally coupled with function approximation to handle a continuous or large state/observation space. We also develop three types of policy value estimators based on the bridge function estimators and provide their nonasymptotic and asymptotic properties. In Section A, we discuss the different between our proposal and a highlyrelated concurrent work by Bennett & Kallus (2021).
We discuss some additional related works in this section.
Minimax Estimation Our proposal defines the value and weight bridge functions as solutions to some integral equations.
Nonparametrically estimating these bridge functions is closely related to nonparametric instrumental variables (NPIV) estimation. In NPIV estimation, the standard regression estimator is biased and variants of minimax estimation methods have been developed to correct the bias (Dikkala et al., 2020;Muandet et al., 2019;Hartford et al., 2017;Bennett & Kallus, 2020).
In the RL literature, the minimax learning method has also been widely used for OPE without unmeasured confounders (Antos et al., 2008;Chen & Jiang, 2019;Nachum et al., 2019;Feng et al., 2019;Uehara et al., 2020).
Negative Controls Our proposal is closely related to a line of research on developing causal inference methods to evaluate the average treatment effect (ATE) with double-negative control adjustment. Among those works, Miao et al. (2018) outlined a consistent estimator for ATE with a categorical confounder. More recent methods generalize their approach to the continuous confounder setting (Deaner, 2018;Cui et al., 2020;Singh, 2020;Ghassami et al., 2021;Xu et al., 2021;Mastouri et al., 2021). All the aforementioned methods focus on a contextual bandit setting (i.e., one-shot decision making) and are not directly applicable to POMDPs that involve sequential decision making.
Comparison with Bennett & Kallus (2021) The difference between the work of Bennett & Kallus (2021) and our proposal can be summarized as follows. Methodologically, the IS, VM, DR estimators developed in the two papers are different. First, consider the IS estimator as an example. In fully-observable MDPs, our proposed estimator is reduced to marginal IS estimators (Liu et al., 2018;Xie et al., 2019) whereas the IS estimator developed by Bennett & Kallus (2021) is reduced to the cumulative IS estimator (Precup, 2000). Second, Bennett & Kallus (2021) do not introduce value bridge functions as in our paper. Instead, they introduce an outcome bridge function to approximate the reward function at each time step 0 ≤ t ≤ H -1. Because of the difference between these definitions, their estimating procedure for the outcome bridge functions involves the estimated weight bridge functions. In contrast, the estimation of value bridge functions in our paper is agnostic to the estimation of weight bridge function.
Theoretically, we focus on the derivation of finite-sample error bounds. To the contrary, Bennett & Kallus (2021) focus on establishing asymptotic properties. In addition, the efficiency bound they developed differs from ours (see Theorem 6). Specifically, they focused on the non-tabular case whereas our bounded is limited to the tabular setting. Moreover, since we focus on evaluating Markovian and stationary policies, in fully-observable MDPs, our bounds are reduced to those in Kallus & Uehara (2019) whereas their bound is reduced to the one in Jiang & Li (2016).
We specialize our results in Section 3 to tabular settings. We use the following notation. Let X, Y be random variables taking values {x 1 , • • • , x n } and {y 1 , • • • , y m }, respectively. Then we denote a n × m matrix with elements Pr(x i | y j ) by Pr(X | Y). Similarly, Pr(X) denotes a n-dimensional vector with elements x i . We denote the Moore-penrose inverse of
We next introduce the following assumption.
As we have mentioned, Assumption 3 implies that |O| ≥ |S| and is weaker than the condition in Tennenholtz et al. (2020) that requires the state and observation spaces have the same cardinality. The following lemma states that 3 is equivalent to Assumption 2 in Nair & Jiang (2021).
Lemma 4. Suppose overlap conditions: Then following Nair & Jiang (2021), the policy value can be explicitly identified as follows:
Theorem 8 (Identification formula in the tabular setting).
To identify policy values, we have so far imposed the following assumptions: (a) learnable value bridge functions exist and weight bridge functions exist; (b) learnable weight functions exist and value bridge functions exist. In this section, we show that the policy value can also be identified with the existence of the learnable value bridge functions only. However, in that case, we would need to impose some completeness conditions. We summarize the results in the following theorem.
Theorem 9 (Identification with completeness). Suppose a learnable value bridge function b V exists, and a completeness assumption holds:
Then, we have
Compared to Theorem 2, the existence of weight bridge functions is replaced with the completeness assumption.
As we have commented, we can use linear basis functions or RKHSs to estimate the bridge functions. Specifically, when V † or W † is set to be the unit ball in an RKHS, then there exists a close form expression for the inner maximization problem (see e.g., Liu et al., 2018). When linear basis functions are used, the proposed minimax optimization has explicit solutions, as we elaborate in the example below.
Example 1 (Linear models).
The resulting policy value estimator is given by
Consider the standard MDP setting where S = O = O -, S + = O + . By setting V = {(s, a) → θ π e (a | s)φ(a, s)}, V † = {(s, a) → θ φ(a, s)/π e (a | s)}, the above estimator reduces to classical LSTDQ estimator (Lagoudakis & Parr, 2003):
where φ(π e , s) = E a∼π e (s) [φ(a, s)].
Alternatively, we may set V := {(a, o) → π e (a|o)θ φ(a, o) : θ ∈ Θ} instead. As discussed in Section 5.1, we find such a parametrization has smaller approximation error in the implementation. The corresponding estimator is given by
We next introduce two examples to further elaborate Theorem 3.
Example 2 (Tabular models). Consider the tabular case, and V and V † are fully expressive classes, i.e., linear in the one-hot encoding vector over (A × O). Then, log(|V||V † |) is substituted by |O||A|. The Bellman closedness T V ⊂ V † is satisfied. Our finite sample result circumvents the potentially complicated matrix concentration argument in POMDPs (see e.g., Hsu et al., 2012) by viewing the problem from a general perspective.
Example 3 (Linear models). Consider the case where V and V † are linear models. Then, log(|V||V| † ) can be substituted by the dimension of the feature vector d. The Bellman closedness assumption is satisfied when
In fully-observable MDPs, this reduces to the linear MDP model (Jin et al., 2020b), i.e., P π b (R, S + | A, S) is linear in φ(A, S).
The next theorem shows that the finite sample rate of convergence for the value function-based estimator can be established without any closedness assumption.
Theorem 10 (Convergence rate without closedness). Set λ in equations 8 and 9 to zero. Suppose (a) Assumption 2 holds so that the bridge functions exist; (b) V and V † are symmetric finite hypothesis classes; (c) V contains certain learnable reward bridge function; (d) V † contains learnable weight bridge function;
Then, with probability 1 -δ,
for some universal constant c > 0.
Next, we discuss the theoretical properties of the IS estimator. To establish its convergence rate, we can define the adjoint Bellman residual operator T as in (Uehara et al., 2021), and derive the convergence rate of E[{T bW (A, O + )} 2 ] 1/2 under realizability (b W ∈ W) and (adjoint) closedness (T W ⊂ W † ). Similar to the proof of Theorem 4, this (adjoint) Bellman residual error can be translated into the error of the estimated policy value. Without the closedness assumption, similar results can be derived when b W ∈ W and b V ∈ W † .
Measure of Estimation Error Given n datasets D 1 , D 2 , ..., D n , the estimators computed based on each dataset V1 , ..., Vn , and the true value V , we define the relative bias to be
Define the relative mean squared error to be:
In our experiments, we use the above two definitions to measure the estimation error of different estimators.
Additional Details for the 1d Continuous Dynamic Process Example Notice that the definition of the bridge value function involves the evaluation policy. Instead of directly using linear models to parametrize b V , we set the function space to V := {(a, o) → π e (a|o)θ φ(a, o) : θ ∈ Θ}. We find that such a parametrization has smaller approximation error. The closed-form expression of the resulting estimator is given in Section D. We use the Python function RBFsampler to generate random Fourier features. To mitigate the randomness arising from the features, for each dataset and each method, we use 5 different random seeds to generate 5 sets of RBF features and use the average value as the final estimator. The RBF kernel is set to exp(-5x 2 ), and the feature dimension is set to 100.
We next report the relative MSE of the two estimators in the following figure. CartPole Environment The state space is 4-dimensional, including position and velocity of cart, and angle and angle velocity of pole. The action space is {0, 1}, corresponding to pushing the cart to the left or to the right. In addition, we use a modified reward function to better distinguish values among different policies. Specifically, the reward is defined as
where x and θ are the position of Cart and angle of Pole, respectively, and x clip and θ clip are the thresholds such that the episode will terminate (done = True) when either |x| ≥ x clip or |θ| ≥ θ clip . Under this definition, the reward will be larger when the cart is closer to the center and the angle of the pole is closer to perpendicular. It is straightforward to show that r is bounded between 0 and 3. Since we set γ = 0.5, the value is bounded between 0 and 60. In the following, we use K(x 1 ; x 2 ) to denote the RBF kernel:
where β denotes the bandwidth parameter. We choose β = med/2 during the training of PO-MWL (b w ) or MWL, and β = med/5 for PO-MQL (b v ) or MQL, where "med" is the median of the l2-distance over the samples in the dataset.
Derivation of the Loss Function for PO-MQL (b v ) Similar to the experiments in Toy environments, we reparameterize g function with ḡ • π e , and therefore the predictor with g should be adjusted by replacing g with ḡ • π e :
The loss function is given by:
• Rπ e ( Ā| Ō) + γE ā ∼π e [g(ā , Ō+ )]π e ( Ā| Ō) -π e ( Ā| Ō)g( Ā, Ō) ].
Derivation of the Loss Function for PO-MWL (b w ) Similarly, we reparameterize f function with f • π e . Since we do not change the parameterization of b w , we only need to adjust the loss function without changing the estimator:
where we denote
Loss Function for Baseline Estimators We follow Uehara et al. (2020) to define the MQL and MWL loss function with the adversarial function space given by RHKSs. The loss function for MQL is given by:
The loss function for MWL is given by:
In addition, we use the same neural network architecture and the same choice of bandwidth during the training of MQL/MWL as those for PO-MQL/PO-MWL.
We consider the time-inhomogeneous setting in this section where the system dynamics, evaluation and behavior policies are allowed to vary over time. We first introduce the identification method for the target policy's value by introducing value and weight bridge functions. We next present the proposed value function-based, IS and DR estimators. We remark that although we focus on evaluation of Markovian policies in this section, the proposed value function-based estimator can be extended to settings where evaluation policies are history-dependent in Section G.
The case where we use the prior observation as a negative control.
The case where we use the prior history as a negative control.
We first introduce the bridge function and the learnable bridge function. For any j ≥ 1, Let µ j (s j ) =
P π e ,j (sj ) P π b ,j (sj )
where P π e ,j and P π b ,j are the marginal density functions of S j under π e and π b , respectively. Let
Assumption 4 (Existence of bridge functions). There exist value bridge functions {b
[j]
V } H-1 j=0 and weight bridge functions {b
j=0 , defined as solutions to
Definition 4 (Learnable bridge functions). Learnable value bridge functions {b
[j]
V } H-1 j=0 and learnable weight bridge functions {b
W } H-1 j=0 are defined as solutions to
It is important to note that we use the whole history J j-1 in the integral equations to define the learnable bridge functions. Alternatively, one can replace J j-1 with the most recent observation O j-1 . The advantage of using the whole history over a single observation is that it requires weaker assumptions to ensure the existence of the bridge functions. See the discussion below Assumption 5 for details.
Next, we present our key identification theorem under Assumption 4.
Theorem 11. Suppose Assumption 4 holds. Then, bridge functions are learnable bridge functions. In addition, any learnable bridge function satisfies
The next theorem states we can similarly identify the policy value by assuming the completeness. Theorem 12. Suppose the existence of leanrbale value bridge functions and the completeness:
Then, any learnable bridge function satisfies
To further elaborate Assumptions in Theorem 11 and Theorem 12, we focus on the tabular setting in the rest of this section when S, O, and the reward space are discrete.
First, we see sufficient conditions to ensure Assumptions in Theorem 11. Assumptions in Theorem 11, i.e., Assumption 4, are immediately implied by the following conditions. Assumption 5. For any 0
Next, we see sufficient conditions to ensure Assumption in Theorem 12. Assumptions in Theorem 12 are immediately implied by the following conditions. Assumption 6. For any 0
These assumptions imply that the state space is sufficiently informative and |O| ≥ |S|. Clearly, this shows the advantage of using the whole J j-1 as a negative control rather than O j-1 itself since rank(Pr
In addition, Assumption 6 is equivalent to Assumption 2 in Nair & Jiang (2021) (rank(Pr(O j | J j-1 , A j = a)) = |S| ) as we see in the bandit setting. Under this assumption, the policy value is identifiable, as we show in the following lemma. Lemma 5. Suppose Assumption 6 holds. Then the policy value equals
where τ k = k t=1 π e t (at | ot).
We present the estimation method in this section. Suppose we have certain consistent
W }, respectively. Theorem 11 suggests that we can estimate the policy value based on the following value function-based and IS estimators.
In addition, we can similarly combine these two estimators to construct the DR estimator ĴDR = E D [J( bV , bW )] where
where f = {f [t] } and g = {g [t] } such that f [t] : A × O → R, g [t] : A × J t-1 → R. Here, J t denotes the domain over J t .
In the fully observable MDP setting, ĴIS reduces to the one in Xie et al. (2019) and ĴDR reduces to the one in Kallus & Uehara (2020). The following theorem proves the doubly-robustness property of ĴDR .
Theorem 13 (Doubly robust property). Under Assumption 4, for any f = {f [t] } and g = {g [t] } such that g [t] :
Finally, we discuss how to estimate the learnable bridge functions. Similar to equation 8 and equation 9, we can employ minimax learning to estimate b V and b W based on the integral equations in equation 12. However, different from equation 8 and equation 9, b V and b W need to be estimated in a recursive fashion in the time-inhomogeneous setting. Specifically, to estimate b V , we begin by defining b
W in a forward manner. Theoretical properties of these minimax estimators can be similarly established, as in Section 4.3, and we omit the technical details.
We have so far assumed that the evaluation policies are Markovian. In this section, we consider the case when evaluation policies are history-dependent, i.e., π e :
We mainly analyze the value-function based estimator in this section. We introduce the value and learnable bridge functions as follows. They are natural extensions of Assumption 4 and Definition 4 for history-dependent policies. Let
V } H-1 j=0 defined as solutions to
There exist weight bridge functions {b
W } H-1 j=0 defined as solutions to
where µ j (S j , Jj-1 ) is P π e ,j (S j , Jj-1 )/P π b ,j (S j , Jj-1 ).
Definition 5 (Learnable bridge functions). Learnable value bridge functions {b
[j]
V } H-1 j=0 are defined as solutions to
It is worthwhile to note J j is contained in Jj . If evaluation policies depend on the whole J j , it is unclear how to identify the policy value in our framework. Now, we are ready to prove the identification formula. Theorem 14.
• Suppose Assumption 7. Then, any learnable bridge function satisfies
• Suppose the existence of value bridge functions and the completness assumption:
for any 0 ≤ j ≤ H -1. Then, any learnable bridge function satisfies
Similar to Section F, b V can be estimated in a recursive fashion. In the tabular setting, the sufficient conditions to ensure the existence of value bridge functions and the completness is
The nonasymptotic properties of the resulting estimator can be similarly established as in Section 4.3
Proof of Lemma 1. First, we prove the value-function based identification formula:
(From standard regression formula)
Second, we prove the importance sampling identification formula:
(From standard IPW formula)
Proof of Lemma 2. We first prove reward bridge functions are learnable reward bridge functions:
Next, we prove weight bridge functions are learnable weight bridge functions:
We show this Q(s, a) satisfies a recursion formula.
Lemma 6.
Proof of Lemma 6. From the definition,
Then, we have
In conclusion,
By using the above lemma, we show learnable reward bridge functions are reward bridge functions. This is a part of the statement in Theorem 2.
Lemma 7 (Learnable reward bridge functions are reward bridge functions).
Proof. From Lemma 6, we have
In conclusion,
Next, we show learnable weight bridge functions are action bridge functions. This is a part of the statement in Theorem 2.
Here, letting w(s) = d π e (s)/b(s), recall
from Kallus & Uehara (2019, Lemma 16 ) which is a modification of the lemma in (Liu et al., 2018). Recall ν is an initial distribution.
Lemma 8 (Learnable weight bridge functions are weight bridge functions.).
Similarly,
Proof. We first prove the first statement:
The second statement is proved by taking summation over the action space.
Finally, we show if bridge functions exist, we can identify the policy value. Before proceeding, we prove the following helpful lemma. Lemma 9 (Identification formula with (unlearnable) bridge functions ). Assume the existence of bridge functions. Then, let b V , b W be any bridge functions. Then, we have
Proof. The first formula is proved as follows:
Here, we define E π e [ ∞ t=0 γ t R t |A 0 = a, S 0 = s] = q π e (a, s). The second formula is proved as follows:
We are ready to give the proof of the final identification formula Theorem 2. The statement is as follows.
Theorem 15. Assume the existence of bridge functions. Let b V , b W be any learnable bridge functions. Then,
Proof. First, we prove the first formula. This is concluded by
Next, we prove the second formula. This is concluded by
Proof of Theorem 9. We show any learnable value bridge functions also are value bridge functions. Then, from Lemma 9, the statement is immediately concluded.
From the completeness assumption,
Then, from a fixed-point theorem, this implies
Thus, b V is a value bridge function.
H.3. Proof of Section 4.3.1
Proof of Theorem 3. By simple algebra, the estimator is written as
where
In this proof, we define
Furthermore, c is some universal constant.
Show the convergence of inner maximizer For fixed f ∈ V, we define
we want to prove with probability 1 -δ:
Note since T f is the Bayes optimal regressor, we have
Hereafter, to simplify the notation, we often drop (A, O -). Then, from Bernstein's inequality, with probability 1 -δ,
Hereafter, we condition on the above event. In addition, from Bellman closedness assumption T V ⊂ V † ,
Then,
(From ( 16))
This concludes
Then, 16) and from ( 18)) 15)) ≤ 2cError.
(From ( 18))
Show the convergence of outer minimizer From the first observation, we can see
Here, from Bernstein's inequality, with probability 1 -δ,
Hereafter, we condition on the above event. Then,
In the last line, we use ( 21) and ( 19). This concludes
Proof of Theorem 4. Recall
from Theorem 15 and the existence of b W . Furthermore,
(b W 's are also observe bridge functions form Theorem 2)
Thus, this concludes
Then, from CS inequality, we have
This concludes the final statement.
H.4. Proof of Section 4.3.2
Proof of Theorem 5. The first statement J(π e ) = E[J(f, b V )] is proved by Lemma 8:
(From Theorem 15)
The second statement J(π e ) = E[J(b W , f )] is proved by Lemma 7:
(Definition of weight bridge functions) = J(π e ).
(From Theorem 15)
Proof of Theorem 6. Recall we have the observation:
We define
From (Nair & Jiang, 2021;Tennenholtz et al., 2020), the target functional is
We use the assumption rank(Pr
We will show the existence of EIF (Z) s.t.
Then, E[φ EIF (Z)φ EIF (Z)] is the Cramér-Rao lower bound.
Before the calculation, we introduce the bridge functions. Due to the assumptions, these are unique. By letting
Next, we define b W (a, o -). Recall
where
Now, we are ready to calculate the Cramér-Rao lower bound. We have
where B 1 , B 2 and B 3 are given by
respectively. Here, we use the notation j = {s 0 , a 0 , r 0 , • • • }.
We first analyze B 1 : It is equal to
where is an element-wise product. Then, we have
Next, we analyze B 2 :
Further, we have
Finally, we analyze B 3 :
Combine all things. Thus,
Proof of Theorem 10. From Hoeffding inequality, we use with probability 1 -δ:
Hereafter, we condition this event.
In this proof, we often use the following:
As a first step, we have
Here, we have
In the final line, we use
We denote E[b j V (A j , O i ) | A j = a, S j = s] by Q j (a, s). Lemma 10.
Q j (A j , S j ) = E[R j π e j (A j | O j ) | A j , S j ] + γE a Q j+1 (a , S j+1 )π e j (A j | O j ) | A j , S j .
Proof. From the definition, we have
Then, Lemma 11 (Learnable reward bridge functions are reward bridge functions).
[j]
Proof. From Lemma 10, we have Then, from O j , O j+1 , R j ⊥ J j-1 | A j , S j , the statement is concluded by
(a , O j+1 )π e j (A j | O j ) | A j , J j-1 .
Lemma 12 (Learnable weight bridge functions are weight bridge functions).
W (A j , J j-1 )π e j (A j |O j )f (O j+1 , a ) -I(A j+1 = a )b Then, we can prove the second statement by taking summation over the action space.
Lemma 13 (Identification formula with unlearnable bridge functions). Assume the existence of bridge functions. Then, let b V = {b Proof. We prove the first formula:
V (a, O j ) -b
W (A j , J j-1 )b V (a, O j ) -b
[j]
W (A j , J j-1 )b W (A j , J j-1 )π e j (A j | O j )R j .
Proof of Lemma 5. This is proved in Nair & Jiang (2021, Theorem 3). Especially, our formula is their specific formula when using left singular vectors for M . We refer the readers to read their proof.
Next, we prove the doubly robust property.
Proof of Theorem 13. The first statement J(π e ) = E[J(b V , g)] is proved by the definition of reward bridge functions:
V (a, O 0 ) (From the definition of reward bridge functions)
= J(π e ).
(From identification results, Theorem 14)
The second statement J(π e ) = E[J(f, b W )] is proved by the definition of weight bridge functions:
(From the definition of weight bridge functions)
= J(π e ).
(From identification results, Theorem 14)