Off-Policy Evaluation for Episodic Partially Observable Markov Decision Processes under Non-Parametric Models
Authors: Rui Miao
Zhengling Qi
Xiaoke Zhang
Venue: NeurIPS 2022 Accept (2022)
Keywords: Off-Policy Evaluation
Non-parametric Instrumental Variable
Reinforcement Learning Theory
Ill-posedness

Abstract: We study the problem of off-policy evaluation (OPE) for episodic Partially Observable Markov Decision Processes (POMDPs) with continuous states. Motivated by the recently proposed proximal causal inference framework, we develop a non-parametric identification result for estimating the policy value via a sequence of so-called V-bridge functions with the help of time-dependent proxy variables. We then develop a fitted-Q-evaluation-type algorithm to estimate V-bridge functions recursively, where a non-parametric instrumental variable (NPIV) problem is solved at each step. By analyzing this challenging sequential NPIV estimation, we establish the finite-sample error bounds for estimating the V-bridge functions and accordingly that for evaluating the policy value, in terms of the sample size, length of horizon and so-called (local) measure of ill-posedness at each step. To the best of our knowledge, this is the first finite-sample error bound for OPE in POMDPs under non-parametric models.

Off-Policy Evaluation for Episodic Partially Observable Markov Decision Processes under Non-Parametric Models
Rui Miao
Zhengling Qi' The George Washington University qizhenglingggwm.cco edu
University of California, Irvine
rmiao20uci.cm edu
Xiaoke Zhang
The George Washington University
xkzhangggwu.cm
Abstract
We study the problem of off-policy evaluation (OPE) for episodic Partially Ob- servable Markov Decision Processes (POMDPs) with continuous states. Motivated by the recently proposed proximal causal inference framework, we develop a non non-parametric identification result for estimating the policy value via sequence of so-called V-bridge functions with the help of dime-dependent proxy variables. We then develop a serrdd---valuatio--yypa algorithm to estimate V-bridge func- tions recursively, where non- parameeric instrumental variable (NPIV) problem is solved at each step. By analyzing this challenging sequential NPIV problem, we establish the finite-sample error bounds for estimating the V-bridge functions and accordingly that for evaluating the policy value, in terms of the sample size, length of horizon and so-called (local) measure of ill-posedness at each step. To the best of our knowledge, this is the first Lnite-sample error bound for OPE in POMDPs under non- -araameetii models.
Introduction
In practical reinforcement learning (RL), representation of the full state which makes the system Markovian and therefore amenable to most existing RL algorithms is not known a priori. Decision makers are often facing so-called partial observability of the state information, which significantly hinders the task of RI. In general, agents have to maintain all historical information and establish a belief system on the hidden state for optimal decision making. A partially observable Markov decision process (POMDP) is often used to model the data generating process. See examples in robotics [Rafferty et al., 2011], precision medicine [Tssukalas et al., 2015], stochastic game [Hansen al., 2004] and many others. However, it is well known that learning optimal policies in POMDP is computationally intractable [Papadimitriou and Tsitsiklis, 1987]. The issue of partial observability becomes more serious in the batch setting, where agents not able to actively collect additional data and further explore the environment. For example, standard off-policy evaluation (OPE) methods, which aim to learn policy value from the batch data generated from some behavior policy, would fail to give a consistent estimate because of unobserved state variables.
Due to this practical concern, there is a recent line of research studying the OPE under the framework of a confounded POMDP, where the behavior policy to generate the batch data is allowed to depend
Corresponding author.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

on some unobserved state variables [e.g. Tennenholtz et al.. 2020, Nair and Jiang, 2021, Bennett and Kallus, 2021, Shi et al., 2021]. Their identification results on the policy value are inspired by the negative controls or so-called proxy variables in the literature of causal inference [e.g., Miao et al., 2018a, Tchetgen Tchetgen et al., 2020]. A building block of these results is the existence of some bridge functions, namely Q/V-bridge or weight-bridge functions, which are projections of the QUV or importance weights defined over the original state space onto the observation space. The corresponding statistical estimation of these bridge functions mainly relies on solving linear integral equations [e.g., Kress, 1989]. Different from the tabular case studied by Tennenholtz et al. [2020] and Nair and Jiang [2021] and linear models studied by Shi et al. [2021] theoretically, solving linear integral equations with non con-mmamitricc models in the continuous state/observation space are known to be challenging due to the potential ill ill-posedness [Chen and Reiss, 2011]. I]. leading to slow statistical convergence rates. However, existing theoretical results developed by Bennett and Kallus [2021] and Shi et al. [2021] require fast enough convergence rates for these bridge function estimators in order to establish the asymptotic normality of their estimators for OPE, which could be illusive when the problem is seriously ill-posed under con-parametric models. This is different from the supervised learning where a fast enough convergence rate can be easily achieved under non-parametric models. Therefore, to fill this important theoretical gap, it is necessary to study the finite-sample performance of OPE of which bridge functions are estimated non-parametrically.
Motivated by these, in this paper, study the OPE for confounded and episodic POMDPs with continuous states, where we non- non- parametricallly estimate V-bridge functions. Our main contribution to the literature is three-fold. First, relying on some time-dependent proxy variables, we establish a non--naanaen non-parametric identification result for OPE using V-bridge functions for time-inhomooeneous confounded POMDPs. Based on the identification result, we develop new fitted- Seeeeddd--allatiooOOOO0 type approach to estimating V-bridge functions recursively and obtain an estimator for OPE based on the bridge function estimators. At each step of our algorithm, we propose to fit non-parametric instrumental variable (NPIV) regression using min-max estimation method, i.e., solving a linear integral equation with non-parametric model. Our algorithm can be viewed sequential NPIV estimation, which is not well studied in the literature. Second and most importantly, we establish the sample error bound for estimating V-bridge functions and accordingly that for evaluating the policy value, in terms of the sample size, length of horizon and (local) measure of ill-posedsees at each step. Unlike the well studied standard NPIV model in the econometries literature [c.g.. Ai and Chen, 2003, Newey and Powell, 2003] where the response variable is directly observed, the response variable in our NPIV model at each step of the algorithm relies on the model estimate at its previous step. This difference makes our theoretical analysis substantially difficult. By carefully characterizing the statistical error due to the NPIV estimation at each step and more importantly, its propagation effect on future estimates, we are able to establish the first finite-sample result of OPE for confounded POMDPs under non parametric models, which achieves a polynomial order over the length of horizon generally conditional moment restriction problems. The development of
and sample size. Finally, our theoretical results on the sequential NPIV estimation applicable to other sequential-tyy the uniform snite-sample error bounds of the NPIV estimation, extending the pointwise result in the previous literature such as Dikkala et al. [2020], may be of independent interest.
2 Related Work
Recently there is surge of interest in studying OPE with unobserved variables in the sequential decision making problem. Specifically, Zhang and Bareinboim [2016] are among the first who proposed the framework of confounded MDPs, which essentially considers i.i.d. confounders in the dynamic system and therefore preserves the Markovian property. Along this direction, OPE methods are developed under various identification conditions such as partial identification using sensitivity analysis [Namkoong et al., 2020, Kallus and Zhou, 2020, Bruns-Smith, 2021], instrumental variable or mediator assisted OPE [Liao et al., 2021, Li et al., 2021, Shi et al., 2022] and many others. Another line of research focuses on more general confounded POMDP models. where the Markovian assumption is violated, under which several point estimation results were developed such as the aforementioned proxy variables related methods [Tennenholtz et al., 2020, Deaner, 2018, Ying et al., 2021, Bennett and Kallus, 2021, Nair and Jiang, 2021. Shi et al., 2021], spectral methods in undercomplete POMDPs [Hsu et al., 2012, Anandkumar et al., 2014, Jin et al., 2020] and predictive state representation related methods [Littman and Sutton, 2001, Singh et al., 2012, Cai et al., 2022].

---

Our proposed method, which uses proxy variables for OPE. is closely related to those recently developed by Bennett and Kallus [2021], Shi et al. [2021], and Ying et al. [2021]. Bennett and Kallus [2021] and Ying et al. [2021] studied episodie POMDPs (or complex longitudinal studies) and mainly focused on developing asymptotic normality results of their policy value estimators. Their results rely on some high level rate conditions on the bridge function estimation, which are unknown if they would be satisfied when using non-parametric models due to the aforementioned measure of ill- ill-posedness. Shi et al. [2021] mainly focused POMDPs and developed asymptotic normality for their estimators under similar high-level conditions, which therefore has the same issue. Besides, while Shi et al. [2021] also established finite- sample bounds for their bridge function estimation and corresponding OPE, they only study the tabular case or linear/parametric models, where the issue of ill poseddesss does not exist. In this paper, provide a systematic investigation on the estimation of --ridge functions and establish finite-sample guarantees for them and the corresponding OPE under non-parametric models. Specifically, tackle the challenging episodic setting, where V-bridge functions are estimated sequentially. Without carefully controlling the effect of ill-posedness at each step and its propagation effect on future steps, the estimation error for these V-bridge functions and also that for OPE could be exponentially large in terms of the length of horizon. Motivated by the chaining argument in the empirical process theory, we successfully disentangle the effects of ill-posedness on the current step and future steps separately sample bounds for V-bridge functions and OPE both with a polynomial
time-homogeneout infinite-horizon
and thus establish dependence on the length of horizon, which are new theoretical results we contribute to the literature.
Since our V V-bridge function estimation can be formulated a sequential NPIV problem, it natually related to classical NPIV estimations, which have been extensively studied in the econometrics literature [see, e.g., Newey and Powell, 2003, Ai and Chen, 2003, 2012, Hall and Horowitz, 2005, Chen and Reiss, 2011, Chen and Christensen, 2018, Darolles et al., 2011, 1, Blundell et al., 2007, for earlier reference]. Recently there is also a growing interest in the min-max estimation for NPIV models [see, e.g.. Muandet et al., 2020, Dikkala et al., 2020, Hartford et al., 2017, for some recent developments]. As commented before, existing theoretical results for standard NPIV models cannot be directly applied to our setting due to the sequential structure of our FQE algorithm. so we need to develop new theory address our setting. Technically, in order to establish a polynomial-ore order smite-sample error bound over the length of horizon for OPE, which is particularly important in RL, we decompose the measure of ill- poledoseesesss each step of our sequential NPIV estimation into two components: the so-called (local) measure of one-step transition ill- ill-posedness and the standard (local) measure of ill- po-eddddddess (e.g.. Chen and Pouzo, 2012]. Thanks to this novel decomposition, the effect of the first component on the estimation error of V- V-bridge functions and OPE is multiplicative but can be properly controlled while that of the second component could be large but is only cumulative. See Theorem 6.1. Finally, we remark that Ai and Chen [2012] also studied the sequential NPIV estimation problem, where the parammerrii components are estimated jointly. However, this method could be computationally inefficient in RL with long horizon. More importantly, their results are built on the nested structure among conditional moment restriction models, which are not satisfied in our setting.
3 Preliminaries and Notations
In this section, we introduce the framework of discrete-time confounded POMDPs and its related OPE problem. Consider an episodic and confounded POMDP denoted by M (S,U, A, T,P,r), with S and Ui as the observed and unobserved continuous state spaces respectively, A as the discrete action space, as the length of horizon, P = {P:) as the transition kernel over and r = {ri)== as the reward function over S x l x A. S can also be treated as the observation space in the classical POMDP. Then the process of M can be summarized as {Se, Ur, A,, B with S, and U, as observed and unobserved state variables, At as the action, and R2 as the reward, where re(s, u, a) = R S. = s, U2 = u, A, = a] for any (s, u, a) E S x U x A. For simplicity, we assume that R2 1 uniformly in 1 < < T.
x A to x U,
The goal of OPE in a confounded POMDP is to evaluate the performance of target policy using the batch data collected by some behavior policy. In this paper, the target policy we focus on is a sequence of functions mapping from the state space to probability mass function over the action space A, denoted by given the state value S. = s. We remark that our proposed identification results stated in Section can be generalized to other policies such as distory-dependee ones. Given target policy n, define
(Te) f where Tz 8) is the probability of choosing an action A,
3

---

its state value function as
(s, u) = = Ry |S = 8, s,U,- = u/, for every (s, u) E S x U where Ex denotes the expectation with respect to the distribution whose action at decision time follows for any > 1. We consider the batch setting, where the observed action A, is generated by some behavior policy मं depending on both S, and U, for 1 S S T. We aim to use the batch data to estimate the policy value of a target policy which is defined as
(I)
V(T) = EIV (S1. U1),
(2)
where denotes the expectation with respect to the behavior policy. Due to the unobserved Uz- standard OPE methods that rely the Markovianity will give bias estimations. In the following, introduce an identification result for estimating the policy value using some proxy variables.
Notations: For two sequences (=) and (0(n))n21, the notation w (n)) ž ((n) (resp. (n) S
((n)) means that there exists sufficiently large constant (resp. small) constant c > 0 (resp. 02 > 0)
such that (N) 2 0₁ (N)) (resp. (m)) I (c2(()). We use (n)) x 0(n) when w (n) 2 (()) and
(n)) S (n)). For any random variable X. we use [X( } to denote the class of all measurable
functions with finite q-th moments for 1 S S Then the L'-norm is denoted by ||||| cx().
When there is no confusion in the underlying distribution, we also write it as ll or ll. In particular,
bo denotes the sup-norm. In addition, we use Big and small o as the convention.
4 Identification Results
Inspired by the proximal causal inference recently proposed by Tchetgen Tchergen et al. [2020], we develop non-parametric identification result for estimating V(TT), which similar to those by Bennett and Kallus [2021] and Shi et al. [2021]. Assume that we can additionally observe the so-called reward-inducing proxy variables W. that are only related to the action A, through (S,, U2) and action- induucig proxy variables Z, that are only related to the reward Rg through (St, U2) at each decision time See Figure I for a directed acyclic graph (DAG) illustrate their relationships and a time series data example in Miao et al. [2018b]. For another example, the action-inducing proxy variables Ze can be defined as the observed history before time f, then Z, and related arrows in Figure I can be removed. Detailed assumptions and discussion are given in Appendix A. Denote the spaces of { (Ze Z and (W.)T- by W and 2 respectively.
W
R
R+
Wess
Rews
S
A
&
A
SKAT
Figure I: A representative DAG to illustrate the variables involved in the confounded POMDP.
Since the states {U T unmeasured, cannot estimate the value function by the celebrated Bellman equation. However, with the help of confounding proxies (We, 2 the value of a target policy can be non- pan--aamtttrilllyy identified using observed variables under proper assumptions.
To proceed, we define a class of V-bridge functions (or V-brigees for short) {uī } defined over W x S such that for every (s, u) E S x U and f. 2 1,
E jo (W,, S.) U. = u, St
= प Er Re U. = S. S.
(3)
If such V-bridges exist, then we obtain the following identification result for the policy value in (2). Proposition 4.1 (Identification). If there exist (o that satisfy (3), then the value of target policy can be identified by V(=) =
Note that V-bridges {vī [r that satisfy (3) are not necessarily unique, but we can uniquely identify (TT) based on any of them. Next, we provide a theoretical guarantee for the existence of --ridgess TT {uf Ji=1 in terms of sequence of linear integral equations.

---

Theorem 4.1. For POMDP model of which variables satisfy the relationships illustrated in Figure I and some regularity conditions given in Appendix A, there always exist V brrddggss {uz ft=1 satisfying
(3). With +1 = 0, particular sequence of V-bridges {uī ) can be obtained by solving the following linear integral equations:
E { (W,, St, A.) Rs (1 S(+1) I Ze, St. Ar} = =0,
(4)
where {aZ TT are Q-bridges defined over W x S x A such that
E O7 (W,, Se, Ad) U2= u. St = s, A a| E Er Re Ui==u u, s, A, A,A.= o].
(5)
for every (8, u, a) E S x u x A and 1 2 1, and of (w, = ExEA s)ug (w, 8, a,a. Clearly
Q-bridges {g. It=1 also exist.
Theorem 4.1 guarantees the existence of both V-bridges and Q-bridges, and also provides a natural procedure (4) to find {er) and eventually estimate the policy value V(T).. Then based on Proposition 4. I and Theorem 4.1, we can perform OPE via Algorithm in the population level. Specifically each step we will solve (4) via non-parametric model, which is NPIV problem.
Algorithm 1: Identification of V(TT
Input: {(S,, W,, Z,, As, R2) Be) a target policy {
2 Let +T+1 = 0.
3 Repeat for 1= T....,, Solve 27 and q.. by E (9 (W,, A1) R₂ - - (W4+1, Z,, St, Ar] = 0 with oW, St) _ E.EA ae(a St)qE (W,.S.,).
Output: (TT) Elu (W,,S)).
5 Estimation
In this section, we discuss how to estimate (T) using batch data based on results given in Theorem 4.1 and Algorithm 1. Let a pre-collected training dataset be D, {(S... We,,, Ze,,, Ar,s, R) i 1= 1......,, n}. which consists of n i.i.d. copies of the observable trajectory (St. We, Zz Re of a confounded POMDP. Following Algorithm 1, we develop FQE-type approach where we propose to solve a min-max problem for estimating oi at the I-th step using the idea of Dikkala et al. [2020], and then apply Proposition 4. for OPE.
For convenience, we first rewrite the linear integral equations (4) for solving V-bridges in terms of operators. Define an operator P: (R + L z S x A} such that [Pro] (z, St A,)
Eig(R, W141, S(+1) Ze, A,] for any g E [² x W x S}. Define another operator P.
(W x S x A} + [2 x S x A} such that for any h E 2 x S x A). (P,A]( St, A,)
T (W, St, A,) Z,, Sr, A,]- Motivated by (4), we define the V-bridge transition operator PT
[ x W x S) + [W x S} such that
Pīg (T, Pag), where Pig = P. P for all g E (R
In particular, (m S.). (P:g) (W,, :), - EaEA Te(a (p) St, a), and Peg is invertible by P.. The invertibility is ensured by Assumption 8 in Appendix A. Then by the definition of V-bridges and (4), we can identify {oe (e via solving
of" = P!" + Re), for 2 1.
(6)
To find the estimated V-bridges {6r |ー_, it suffices to estimate PT. Note that one can regard (6) as series of conditional moment model restrictions and we propose to solve them via sequential NPIV estimation. particular, at the /-th step, we adopt the min-max estimation method proposed
by Dikkala al. [2020] to estimate P non-parametrically follows: Pīg <TTe (P.). where
PT -++ arg min
sup h)H()) fEF()
{ {
+
M
11f111)) } + 11 14000 (7)
82
5

---

where Il n f A..)) for e F()), H on W x S x A and F(()) on 2 x are two user-defined function spaces endowed with norms respectively, N,H,M M, > 0 are tuning parameters, and Vi,n
((00) and ||are
f.g) (,,g = n - [h(W,, St,i, (Ta))-(T++))-1pp0 (R,,,, W4+15, S141,)) St,i, At.)),
where gBR,, Wi+1, 1 Rs + ((W+1,, S(+1) for some g(++)) on W x S, endowed with norm
lgge++s)
The rational behind (7) is that when A, Au + 0 0 x 1, the following two population-version min-max optimization problems
min kEM())
sup E[h(We, At) (T -+ 1) Sc A,) - (2,, -T 1) g R2, W S Z,, St A,])²
fej())
min E, NER())
have the same solution h when the space F(() of testing functions is rich enough. Note that (T' (T'-+ 1- (1-1+))-- used above and in (7) are for scaling purpose.
After T steps, we output our estimator for the policy value based on the empirical counterpart of Proposition 4.1. Our FQE-type algorithm is summarized in Algorithms and in Appendix E.
6 Theoretical Results
In this section, we establish the finite-sample bounds for the L error of estimating V-bridge ef and the error of OPE, in terms of the sample size, length of horizon and (local) measures of ill-posedness. Our bounds also rely on the critical radii of certain spaces related to the user-defined function spaces (((*) and (() in (7), and also g(t) V-bridge functions.
1. Technical preliminaries. Before presenting our main results, we first introduce some concepts from the empirical process theory [Wainwright, 2019].
Definition 6.1 (Local Rademacher Complexity). Given any real-valued function class F defined over a random vector X and any radius ò > 0, the local Rademacher complexity is given by
Rr (F, 5) = Ex,xx / |n- E.= (xX())l
where (X:) are i.i.d. copies of X and {+>]= are i.i.d. Rademacher random variables.
By bounding the local Rademacher complexity, which measures the complexity of the functional class F locally in neighborhood of the ground truth, V-bridge estimator in each step. A crucial parameter for local Rademacher complexity a function class F is called critical radius.
control the eπror rate of the proposed
Definition 6.2 (Critical Radius). Assume that F is a star-shaped function class, i.e. as E F for any E F and scalar E [0, 1). and also that F is b-uniformly bounded, i.e., |1 < b < oc, of F. The critical radius of F, denoted by 6, is the solution to the inequality RR, 50) < 8//b.
Additional Notations: We assume that the test functions f belong to a star shaped, symmetric space (F))) S. (2 x S x A) endowed with norm || -l For brevity of notation, hereafter we suppress the time-step indicator (t) in the context unless necessary. For a function space F, we define aF {af f F). for some a R. Define Fn = [ F: | S B}. for any B > 0. Define the projected root mean squared error proj, = / T2 (X) S,, A.] for any squared integrable f with respect the conditional distribution of X given (Z,, St)
Standard (Local) Measures of ill-posedness: Let F = sup
Si]l2 be the measure of ill ill-posedness for (WV x Si) projected on 2, x S. Let T. = Su [[,,W, S,, Az) (proj.h(W,, St, A,)l12 be the standard measure of ill-posedness for H(9 (W x S x A) projected on Z
A. It can be seen that 71 Ti 2 1 for 2 1. Indeed we only require measuring 7i and 7, locally. See more details in Appendix C.
Results. We first give Assumption 1 used develop our theoretical results below. Assumption 1. For each 1, 1....,T.

---

(1) Closeness. For any g E , + Ri) E H1 For any h E H(1t), (Te, h) g())
(2) For any E (T - t) we have IP: R. ( Ileeoo S 5117-allec
7-1+1
(3) There exists a constant Cg such that || (Ie,, h) 11ges I Cgllb|1 for h E H
(4) of E (T ++ 1)7( (W, A) and 11 S MH. where MX > 0 is a constant.
(5) Testing function class F(t) sufficiently rich such that there exists L > 0, Il -rroj ll2 S 1/n
where f E arg min fe L
|ff projjhh 12, for all h2 E 7(09)
(6) Behavior policies: there exists a constant 6x such that aā(a (s B|ab(a (a| Uz. S.) S 8] 2
by 0 for all (s,a) E S x A. Assumption 1 (1) is similar to Bellman completeness, which has been widely used in RL without unobserved states [e.g., Antos et al., 2008]. Note that both ( and Hg(*) can be chosen as infinite- dimensional spaces, e.g., RKHSs. Hence this assumption is relatively mild. Assumption (2) requires the operator P. to be bounded, which can be ensured under some continuity conditions on transition kernels [Kress, 1989]. Assumption 1 (3) is a technical condition for controlling the complexity of G by H. Assumption 1 (4) essentially assumes that we can model qd' (and v*)) correctly at each t-step, which is again mild as (((()) for 2 1 can all be chosen as infinite-dimen dimensional spaces. This assumption is also called realizability of value functions, which is commonly seen in the literature of RL [e.g.. Antos et al., 2008J. Assumption 1 (5) is imposed to ensure that the space of testing functions F is large enough so that we are able to capture the conditional expectation operator in each min-max estimation (7). Assumption 1 (6) basically requires full coverage of our batch data generating process induced by the behavior policy, which is widely used in OPE [Precup, 2000, Antos et al., 2008]. Next, we provide key decomposition of the La error for V V-bridge estimation.
Theorem 6.1 (Error decomposition). Under Assumption 1 (1) and (6), we can decompose the L error of the estimated V-bridge by
||T - 07112 S t
El=
(p. (p) + Re)l12,
where the measures of one-step transition ill-posedness C/, A and & 1 2 < 1' SIST T are defined after Corollary 6.2.
Theorem 6.1 shows that there are four key components for upper bounding the L error of 07. The first component the probability ratio /m//=//l which is used to measure the distributional mismatch between the target and behavior policies. The second component is ||proj, (P. ( + R2), the one-step projected error of P. Pt, where 07 is the estimate for u/41 depending the observed data after (-step. We remark that this is different from the analysis in the standard NPIV estimation with a directly measured outcome. Hence the results, e.g., from Dikkala et al. [2020], cannot be directly applied to bound this component. The last two components are related to the (local) measure of ill-posedness. The third component Te is the measure of ill- posedddes for characterizing the difficulty of estimating of by (4) using 7((0) the t-th step. {T, Dr
similar those used in the standard NPIV estimation such as Chen and Reiss [2011]. and the effect of each T. on the y' upper bound is cumulative. The last component C VT_ quantify the propagation effect of estimation errors in previous steps on the last step of estimating vj. which is multiplicative in terms of c(()) ----r1 We call c(O) -r the measure of one-step transition ill-posedness from t' to t' - 1 related to t-step NPIV estimations. Next we provide detailed bounds for the second and last components. The discussion of the third component can be found in Appendix C.4.
Component 2: one-step projected error. In the following, we show that (PP + Relle
gil+1) is bounded by the critical radii of some spaces defined as balls 7 Co((T in hypothesis
spaces H()), g(++1) respectively and a ball (()) in testing space FF(), for some fixed constants 3M
M, B > such that functions in z((!) and F((() have uniformly bounded ranges in [-1, 1] for all
1 < t T. Let
(2) (sL,, We: Re, 0es S1+1, we+1 1) + r ((,) (wi, St, a.) ((1)4) a)): g (o(TT S F()).
((+1)
3M. E [0. 1]} and
7

---

E = (81, We; Ze, ue) - r(h -h (wr, 81, az) T (Et, 0r)
E H00 h hi E H ,9 E Gotl 1))
g(++))
[0, 1]]
where hn E 7(00) is the solution to E (We. 4, S,, g(W+11, S1+1) Z,, St, 0, and fr²n - (h - 12)1l2 for a given L > O. An upper bound for prroj, (P: -P: (o7(1
arg min fe n
R&) 222 is given in Theorem 6.2.
Theorem 6.2. Suppose that Assumption holds. Let 8h 5 + cu [oR(e,T/() for some universal "
(t) 3M (2 and E("), Assume that the approximation error in Assumption (5) can bounded by 1Jn - d( Furthermore, letting tuning parameters satisfy MM )2 and 2 ( + M/ with probability at least 1 S, we have
constants co. ci > 0 where _ is the upper bound of the critical radii of F(t)
pproj (P: - P.) R2)l12
X MT - 2) for all StST.
Depending on the choices of 7(00 g(++1), and F(i), we can obtain different finite-sample error bounds of the one-step projected error for each t. Below we provide two examples.
Corollary 6.1. Let F((), H(()) and G((+1) be VC-subgraph classes with VC dimensions V(F(1),
V(H(0) and v(g(+1)) respectively. Then with probability at least 1 - Ç. for all 1 SIST
ppooj (P: - (1)(C - Ra)lla S (T t ++1) /lgie T/O (V((O)
The definition of the VC-subga class can be found in, e.g., Wainwright [2019]. This a broad class. For example, if one lets each of F()) H(4) and g(++1) be linear space FF {ØT o(.) A E Fd with basis functions Φ(-) then V(F) = d + 1. Then the upper bound for the one-step projected error becomes O(T + 1)2 2.5 d/ VT).
Corollary 6.2. Let H()), g(++1) and JF(t) be reproducing kernel Hilbert spaces (RKHSs) equipped with kernels K Ret,, Kgo+n) and Kyts respectively. For a given positive definite kernel K, we denote its nonincreasing eigenvalue sequence by { We consider two scenarios for () (K))
(1) Polynomial cigen-decay: If (K(()))) S aj 22z, (((gen) S aj-2ag and (K(())) S aj 2nz for constants a', ag, aF > 1/2 and a >> then under the assumptions in Theorem 6.2. with probability at least 1 - ç, for all 1 < < T, we have
[P: - P.) + R.)lla S (T - 1)2.5 Vlog(eiT(()n 2n0astt//a log(n).
(2) Exponential eigen-decay: If (K(()))) S a22" (Kgre))) I are a1e-a and (K(() < a1e-azj"> for constants 01, a2, Br,, $g, BF > O, then under the assumptions in Theorem 6.2, with probability at least S. for all st T, we have
|proj (P. - -Pi((E + R.)l2 $ (T 1)25
(log 1/ mint gg.0g)
log(es T/C) TL
Kernels of the two types of eigen- eigen-decay considered above are very common. For example, the kernel of the a-order Soblev space with 1/2, has a polynomial eigen-decat while the Gaussian kernll has an exponential eigen-decay, with B = 2 for Lebesgue measure on real line and / = on a compact domain [Wei et al., 2017).
Components 4: measure of one-step transition ill ill-posedness. We first provide more insights on ( before providing an upper bound. We formally define the local measure of one-step transition ill-posedness Cr'+1,' recursively based C,,-1 to 2,1
E [o(We=1, Sy+1) Ze, Sr
sup SED(W.r.1SS.c (
subject to
Zp-1, Sr+1ll2
[[[g(We41, Sv41) Ze41, Sctillla - (T t 1)2 1 / bloo I1 d00
C+1.s
8

---

14411 1 for each t = T. the projected error lIproj, (P: + Ra)ll2 multiplied by the ill- ill-posedness Ty- By Theorem 6.2, the projected error can be well controlled by o with high probability, so C, can be defined locally. Therefore, we can provide an upper bound for the denominator sequentially and define all
with ((t)
T. For C (, we can upper bound |[ (W,, St) Z,, Silla by
c( 244,0' locally, which indicates that all C/41, could be small.
For example, if we use the observed history as the action-inducing proxy, then a x Si) C (2 x S2) C... C((r x Sr) is a filtration. In this case, I - are expected to be small for 1 2 2 if the target policy is stationary. While this can enlarge the critical radii 8/²) due to the dimension of the action-inat iinluinng proxy, this only affects one-step errors. See detailed discussion in Appendix B. Motivated by this, it is reasonable to impose Assumption below on c(+) Cr+
Assumption 2. For every 2 and 2 < S t, C m S 1+
ot_ with time-dependent constants mos
a, > 0, 2 a > 1.
Corollary 6.3. If Assumption 2 holds, then II G I exp(ai((ai)). where ((ar) = Ex= is uniformly bounded for t 1.
Main result: error bounds for V-bridge estimation and OPE. Define trans-ill
maxisisT (xp{a and let illmax = F1 51 Tel s0. Summarizing all afore- mentioned results, we have the following main theorem based on the polynomial eigen-decay case in Corollary 6.2. Other cases can be found in Appendix B.
Theorem 6.3 samile error bounds for V V-bridges and policy value). Under Assumptions and 2, and assumptions in Theorem 6.2 and Corollary 6.2 (1), with probability at least Ç. we have
||u] - l22 $ illmax X trans-ill x T//2 Vlog(cTT/()n
2000x (1og) 1/0g log(n), and log(n).
[V())) - (T)) illmax X trans-ill x T TT/22 /loo((cT//(/m
Theorem 6.3 provides the first finite-sample error bound for OPE under confounded and episodic POMDPs in terms of the sample size, length of horizon and two (local) measures of ill-posedness. Without considering the measures of ill-posedness, the derived error bound for V-bridge func- tion nearly achieves the optimal L co-covvereence rate in the classical non-parametric regression [Stone, 1982]. Moreover, our OPE error bound depends on a polynomial order of T, i.e., 77/2, which is larger than the standard O(T3) in the OPE without unobserved variables. However, when the function class consider (7) grows with the sample size n, illmax will also in- crease and therefore the convergence rates in Theorem 6.3 could be much slower. Next study a case when we can control the local measures of ill-posedness {Te)==1 by assuming that Amin (T()) 2 Vm for all < 1 T almost surely and other regularity conditions in Lemma C.I, where r(f)) A E [lee S., Z,, St, A/e/ (We, S₁, Ad) Ze. St, Ad]]
with ej = (c)
(1)) as the first m eigenfunctions of kernel Kn Similar conditions can be imposed to control F1. which is omitted here for simplicity. Let 17n, T. Ç, an, a,,, ag, b) A -x-1/2 /Vog(e]T/((r [-mxx(1/ a//gg//////////////// log(n)) "x "12112 with b defined below. Corollary 6.4. If assumptions in Theorem 6.3 holds and V/
7(0 106 T 2009 +/2
2b for some b 2 0, then |ooT 07 S Ft maxigisT /T// x trans- ill x 17n, T, Ç. ar, ax, ag. b). [VT)) - (+)) FL maxigisT ////////oo x trans-ill x v7(n, T, C, OF,, (g, b).
Corollary C.5.2 considers the mildly ill-posed case, i.e., Pm 2 m -25, and shows that the local measure of ill-posedness can deteriorate convergence rate of 6J significantly. If b is large relative to O'H or further severely ill-posed case is considered (i.e., Mm decays exponentially fast, see Appendix C.5.2), then the convergence rate of V-bridge estimation could be much slower and the typical requirement on the nuisance parameter for achieving asymptotic normality for the policy value will fail. On the other hand, it can be seen that when b 0, the finite sample error bounds match the results in Theorem 6.3.
7 Simulation
In this section, we perform a simulation study to evaluate the performance of our proposed OPE estimation and to verify the finite-sample error bound of our OPE estimator in Theorem 6.3.

---

Let S = - R.W = R R. and A = (1,-1). At time t, the hidden state Us, two proximal variables Z, W2 satisfy the following multivariate normal distribution given (S,, At):
(1
[a + aa + a;
o
Jzu
Zzv
(Z,, W,WWUU I (St, A.) ~ N
Po MoAi + U.S:
Σ =
auw
Jaru
(9)
Ko NaAe KgSL_
azu
O wwu
Tu
where parameters are given in the Appendix.
The behavior policy is given by (A Ut, expit, (xpitt(-A. {-A, (to + tnU, 1. S.) }. where
to 0. tu 1, and t = [-0.5, 0.5). Then by Assumption 1 (6), <A, St)
expit (-A (lo + 1,,00 + (1, (x T.))) The initial S1 is uniformly sampled from R2. At time t, given (St, Uz. At), we generate S41 S, A,U,12 + CS411 where 12 = [1, 1] and the random error 1s ~ [N[[ 0]_, I2) with 1 denoting the 2-by-2 identity matrix. The reward given by R = expit { AcU, + [1, 2 + ct, where e ~ Unifonm[
0.1]. One can verify
that our simulation setting satisfies the conditions in Section A. so that our method can be applied.
Trakinng n=312
Near www.llleeeeeee
24.
Nears aleglide
2-
2.5
2-
2-3
2-7
2b
Training set diz
(a)
(b)
Figure 2: Simulation results for OPE errors [7()) (TT) Mean absolute errors (solid lines) and their standard error bands (shaded regions) are displayed for different combinations of (n, T).
We choose F(()) and 70() as RKHSs endowed with Gaussian kernels, with bandwidths selected according to the median heuristic trick by Fukumizu et al. [2009] for each S S The pool of scaling factors SCALE contains 30 positive numbers spaced evenly on a log scale between 0.001 to 0.05. The number of cross- valsddaniontinn partition K 5. The true target policy value of a is estimated by the mean cumulative rewards of 50, 000 Monte Carlo trajectories with policy n. We compare our OPE estimator (T) with the target policy value by computing mean absolute error (MAE) for each setting of (n, 7), as reported Figure 2. Figure validate the derived finite-sample error bound of our OPE estimator in Theorem 6.3. Specifically, Figure 2 (a) shows that the OPE estimation error is polynomial in T, but with order slightly smaller than (T? as stated in Theorem 6.3. Figure (b) shows that the convergence rate in terms of the sample size n for our OPE estimator is slower than On 1/2), which also justifies our theoretical results.
8 Discussion
In this paper, we propose a non-parametric identification and estimation method for OPE in episodic confounded POMDPs with continuous states, relying on time-dependent proxy variables. We develop a seleld--evaluuation-tppe algorithm for estimating the V-bridge functions sequentially and for OPE based on the estimated V -bbridges. The first finite-sample error bound for estimating the policy value under confounded POMDPs is established, which achieves a polynomial order with respect to the sample size and the length of horizon. Our OPE results can serve as a foundation for developing new policy optimization algorithms in the confounded POMDP, which We will leave for future work.
Acknowledgement
Zhang's 's research is partially supported by GW University Facilitating Fund.
10

---

References
C. Ai and X. Chen. Efficient estimation of models with conditional moment restrictions containing unknown functions. Econometrica,
2003.
C. Ai and X. Chen. The semiparametric efficiency bound for models of sequential moment restrictions containing unknown functions. Journal of Econometrics, 17002)442-457, 2012.
A. Anandkumar, Ge, D. Hsu, latent variable models. Journal of Machine Learning Research, 15:2773-2832, 2014.
Kakade, and M. Telgarsky, Tensor decompositions for learning
A. Antos, C. Szepesvári, and R. Munos. Learning near-optimal policies with bellman-residual minimization based fitted policy iteration and a single sample path. Machine Learning, 71(1): 89-129, 2008
A. Bennett and N. Kallus. Proximal reinforcement learning: Efficient off-policy evaluation in partially observed markov decision processes. arXiv preprint arXiv:21 2021.
R. Blundell, X. Chen, and Kristensen. Semi-nonparamettrcc IV estimation of curves. Econometrica, 75(6):1613-166, 2007.
Engel
D. A. Bruns-Smith. Model-free and model-based policy evaluation when causality is uncertain. In International Conference on Machine Learning, pages 1116-1126. PMLR, 2021.
Q Cai, Yang, and Z.. Wang. Sample-efficient reinforcement learning for pomdps with linear function approximations, arXiv preprint arXiv:2204.09787, 2022.
M. Carrasco, J.-P. Florens, and E. Renault. Linear inverse problems in structural econometries estimation based on spectral decomposition and regularization. Handbook of Econometrics, 5633-5751 2007.
X. Chen and T. M. Christensen. Optimal sup-norm rates and uniform inference on nonlinear functionals of nonparametric iv regression. Quantitative Economics, 91):399-84 2018.
X. Chen and D. Pouzo. Estimation of nonparametric conditional moment models with possibly nonsmooth generalized residuals. Econometrica, 80(1):277-321, 2012.
X. Chen and M. Reiss. On rate optimality for ill-posed inverse problems in econometrics. Econometric Theory, 27(3):497-521, 2011.
X. Chen, Chernozhukov. S. Lee, and W. K. Newey, Local identification nonparametric and semiparametric models. Econometrica, 82(2):785-809, 2014.
S. Darolles, Y. Fan, J.PP. Florens, and E. Renault. Nonparametric instrumental regression. Economet- rica, 194511154- 2011.
B. Deaner. Proxy controls and panel data. arXiv preprint arXiv: 2018
N. Dikkala, G. Lewis, L. Mackey, and V. Syrgkanis. Minimax estimation of conditional moment models. Advances in Neural Information Processing Systems, 13:12228-12262, 2020.
X. D' D'Haulffoeuill. On the completeness condition in nonparametric instrumental problems. Econo- metric Theory, 2763)440--71,, 2011.
D. Foster and V. Syrgkanis. Orthogonal statistical learning. arXiv preprint wrXiv:1901.09038 2019.
K. Fukumizu, A. Gretton, G. R. Lanckriet, B. Schölkopf, and B. K. Sriperumbudur. Kernel choice and classifiability for RKHS embeddings of probability distributions. Advances in Neural Information Processing Systems, pages 1750-1758, 2009.
P. Hall and J. L. Horowitz. Nonparametric methods for inference in the presence of instrumental variables. Annals of Statistics, 33(6):2904-2929, 2005.
E. Hansen, D. S. Bernstein, and S. Zilberstein. Dynamic programming for partially observable stochastic games. In AAAI, volume 4, pages 709-715, 2004.

---

J. Hartford, G. Lewis, K. Leyton-Brown, factual prediction. In International Conference on Machine Learning, pages 1423. PMLR. 2017.
Brown, and M. Taddy, Deep IV: A flexible approach for counter-
A. Hinrichs. Optimal Weyl inequality in Banach spaces. Proceedings of the American Mathematical Sociery, 134(3)731-7355 2006.
D. Hsu, S. M. Kakade, and T. Zhang. A spectral algorithm for learning hidden Markov models. Journal of Computer and System Sciences, 78(5):1460-148) 2012.
C. Jin, S. Kakade, A. Krishnamurthy, and Q. Liu. Samplc-efficient reinforcement learning of undercomplete pomdps. Advances Neural Information Processing Systems, 33:18530-18539 2020.
N. Kallus and A. Zhou. cinfounding-robus policy evaluation in infinite- -oriitee-oozzon reinforcement learning. Advances Neural Information Processing Systems, 33:22293-22233 22304, 2020.
R. Kress. Linear Integral Equations, volume 82. Springer, 1989.
D. Krieg. Tensor power sequences and the approximation of tensor product operators. Journal of Complexiry, 44:30-51, 2018.
J. Li, Y. Luo, and X. Zhang. Causal reinforcement learning: An instrumental variable approach. arXiv preprini arXiv:2103.04021, 2021.
L. Liao, Z. Fu, Yang. Y. Wang. M. Kolar, and Z. Wang. Instrumental variable value iteration for causal offline reinforcement learning. arXiv preprint arXiv:2102.09907, 2021.
M. Littman and R. S. Sutton. Predictive representations of state. Advances in Neural Information Processing Systems, 14, 2001.
W. Miao, Z. Geng, and Tchetgen Tchetgen. Identifying causal effects with proxy variables of an unmeasured confounder. Biometrika, 105(4):987-993, 2018a.
W. Miao, X. Shi, and E. T. Tchetgen. confounding bridge approach for double negative control inference on causal effects. arXiv preprint arXiv: 04945, 2018b.
K. Muandet, A. Mehrjou, S. K. Lee, and A. Raj. Dual instrumental variable regression. Advances in Neural Information Processing Systems, 33:2710-2721, 2020.
Y. Nair and N. Jiang. A spectral approach to off-policy evaluation for POMDPs. arXiv preprint arXiv:2109. 10502, 2021.
H. Namkoong, R. Keramati, S. Yadlowsky, and E. Brunskill. Off Off-policy policy evaluation for sequential decisions under unobserved confounding. Advances in Neural Information Processing Systems, 33:18819-1888
2020.
W. K. Newey and J. L. Powell. Instrumental variable estimation of nonparametric models. Economet- rica, (1(5): 155_1 2003.
C. H. Papadimitriou and J. N. Tsitsiklis. The complexity of markov decision processes. Mathematics of Operations Research, 12(3):441453 4500, 1987.
A. Pietsch. Eigenvalues and s-numbers. Cambridge Studies in Advanced Mathematics, 13, 1987.
D. Precup. Eligibility traces for off-policy policy evaluation. Computer Science Department Faculty Publication Series, page 80, 2000.
A. N. Rafferty, E. Brunskill, T. L. Griffiths, and P. Shafto. Faster teaching by POMDP planning. In International Conference Artificial Intelligence in Education, pages 280-287. Springer, 2011.
C. Shi, M. Uchara, and N. Jiang A minimax learning approach to offlcy evaluation in partially observable Markov decision processes. arXiv preprint arXiv:2111.06784 2021.
C. Shi, J. Zhu, Y. Shen, S. Luo, Zhu, and R. Song. Off-policy confidence interval estimation with confounded Markov decision process. arXiv preprint 2xX1v:2202.10539, 2022.
12

---

X. Shi. W. Miao, J. C. Nelson, and E. J. Tchetgen Tchetgen. Multiply robust causal inference with double-negative control adjustment for categorical unmeasured confounding, Journal of the Royal Statistical Society: Series B (Statistical Methodology), 82(2):521-555 2020.
R. Singh. Kernel methods for unobserved confounding: Negative controls, proxies, and instruments.
arXiv preprini urXiv:2012. 10315, 2020.
S. Singh, M. James, and M. Rudary, Predictive state representations: A new theory for modeling dynamical systems. arXiv preprint arXiv: 2012.
C. J. Stone. Optimal global rates of convergence for nonparametric regression. Annals of Statistics, pages 1050,1053, 1982.
J. J. Tchetgen Tchetgen, A. Ying. Y. Cui, X. Shi, and W. Miao. An introduction to proximal causal learning. arXiv preprint arXiv:2009. 2020.
G. Tennenholtz, U. Shalit, and S. Mannor. Off-policy evaluation in partially observable environments. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 10276-10283, 2020.
A. Tsoukalas, T. Albertson, and I. Tagkopoulos. From data to optimal decision making: a data-driven probabilistic machine learning approach decision support for patients with sepsis. JMIR Medical Informatics, 3(1):e3445, 2015.
M. Wainwright. High-Dimennn Dimensional Statistics: A Non-Asymptotic Viewpoint, volume 48. Cambridge University Press, 2019.
Y. Wei, F. Yang, and M. J. Wainwright. Early stopping for kernel boosting algorithms: A general analysis with localized complexities. Advances Neural Information Processing Systems, 30, 2017.
A. Ying, W. Miao, X. Shi, and E. J. Tchetgen Tchetgen. Proximal causal inference for complex longitudinal studies. arXiv preprint urXiv:2109.0700: 2021.
J. Zhang and E. Bareinboim. Markov decision processes with unobserved confounders: A causal approach. Technical report, Technical Report R-23, Purdue Al Lab, 2016.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's s contributions and scope? [Yes] The paper's contributions and scope are summarized in the abstract and then emphasized in Sections and 2.
(b) Did you describe the limitations of your work? [Yes] We did not provide results of minimax lower bound for our estimation problem.
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] Main assumptions are stated in Sections and 6. Some regularity conditions are provided in Appendix
(b) Did you include complete proofs of all theoretical results? [Yes] All proofs for theoret- ical results are provided in Appendices and D.
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL.)? [Yes] We attached the code and instructions in the supplemental materials.
13

---

(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] Provided in Appendix
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/relcasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(d) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "mXX0K4hy8e", "reviewer": "Reviewer_UaZS", "summary": "This paper studies off-policy evaluation (OPE) on POMDPs where the states are unobserved confounders. This paper establishes a nonparametric identification result that links the value of the policy to a sequence of V-bridge functions. Moreover, the V-bridge functions can be learned from data via nonparametric instrumental estimation. This paper establishes a sample complexity result for the proposed estimator. ", "questions": "1. When can we expect the ill-posed condition to hold? How to interpret it? \n\n2. Why the bound depends on the ratio between $\\pi_b$ and $\\pi$, rather than the ratio between their visitation measures?\n\n3. How does the estimation of V-bridge function differs from standard nonparametric IV? ", "limitations": "1. This paper requires multiple assumptions which are not carefully explained. \n\n2. This paper only considers the policy evaluation setting. It would be nice to consider how to extend to the setting of policy learning. ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: OPE for POMDP is an important problem and the theoretical results in this paper are solid. \n\nWeakness: This paper has many assumptions and conditions. It would be nice to have careful discussions on why the assumptions are reasonable and when should we expect them to hold. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Rv5Bj4Arsjm", "reviewer": "Reviewer_ah8v", "summary": "The paper proposes an off-policy evaluation method for episodic POMDPs alongside theoretical analyses. It first summarizes the POMDP as a directed acyclic graph with added reward- and action-inducing proxy variables, then shows that the value of a policy can be computed from a sequence of V-bridges, each of which may be found by solving a linear integral equation with a non-parametric model. For the purpose of OPE, the sequential linear integral equations are interpreted through a V-bridge transition operator and estimated in a minimax process. The overall algorithms takes the form of fitted-Q evaluation. Finally, the paper provides finite-sample error bounds for the estimated V-bridges and policy value and measures of ill-posedness.", "questions": "1 is the mismatch between sampling distribution and true data distribution accounted for somewhere?\n2 it's unclear to me what is the point of defining the V-bridge transition operator\n3 is there an error bound for all cases of eigen decay (not just those exemplified in the main text and supplementary)?", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 1, "presentation": 1, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Main strengths:\n1 approached a meaningful problem of OPE for POMDPs from a unconventional angle\n2 clear model assumption \n\nMain weaknesses:\n1 the presentation of the paper is hardly intelligible, with way too many notations and little intuition\n2 no experiments\n3 a practical algorithm with all functions and added variables exemplified would be helpful", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "MUdhDlHe3vW", "reviewer": "Reviewer_9Zzj", "summary": "This paper studies the problem of off-policy policy evaluation (OPE) in partially observable MDPs. Specifically, they consider a model where the environment state consists of an observable component and an unobservable component. Actions in the recorded data could have depended on both components and the objective is to estimate the expected return of a policy that only conditions action selection on the observable components. The partially observable nature of the problems means that estimating the reward that the evaluation policy will obtain is potentially confounded by the unobservable state components. To resolve confounding, the paper proposes to recursively estimate a state value function that conditions on the observable components and an additional variable that the per-step reward depends on but the action is independent of (conditioned on the state). The estimator is reminiscint of fitted q-evaluation except partial observability and potential confoundedness requires a minimax estimation procedure instead of simple regression. After proposing the estimator, the paper theoretically analyzes and bounds error with respect to different settings and amounts of ill-posedness.", "questions": "1. What is the importance of non-parametric estimation in this setting?\n2. How are tuning parameters set (210-211)?\n3. Suppose one just performed FQE using S x W x A as the state-action space. This seems like it might perform reasonably well. Could the authors comment on the limitations of this approach?", "limitations": "See weaknesses above.\n\nMinor critique: the paper lacks a conclusion or future work section. While this doesn't impact the technical contribution, I believe that summarizing what has been done and saying what needs to happen next is important for future readers and researchers who wish to build on this work.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n(+) Addresses a challenging, real world problem setting for OPE.\n\n(+) Work is novel to the best of my knowledge though I lack familiarity with the causal inference side of the OPE literature.\n\n(+) Broad theoretical results considering error bounds and also misspecification.\n\n(+) Paper is well organized: moves from establishing the correct estimands to estimators and then to theoretical properties.\n\nWeaknesses\n\n(-) Method appears to require a set of hyper-parameters to be tuned. Tuning isn't possible in OPE since you don't know the true value you are estimating. It is unclear how misspecification of these would impact error.\n\n(-) No empirical analysis. The paper is clearly a theory paper so I don't see this as a reason to reject but some simple simulations would be nice to confirm the analysis.\n\n(-) Paper addresses a problem that is of interest to causal inference and OPE communities. In my opinion the work is more accessible to causal inference community and could obtain higher impact if assumed less familiarity with causal inference challenges. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept