Future-Dependent Value-Based Off-Policy Evaluation in POMDPs
Authors: Masatoshi Uehara
Haruka Kiyohara
Andrew Bennett
Victor Chernozhukov
Nan Jiang
Nathan Kallus
Chengchun Shi
Wen Sun
Venue: NeurIPS 2023 spotlight (2023)
Keywords: Reinforcement learning theory
POMDP
PAC RL
Off-policy evaluation
Offilne reinforcement learning
TL;DR: Model-free off-policy evaluation in POMDPs without a curse of horizon

Abstract: We study off-policy evaluation (OPE) for partially observable MDPs (POMDPs) with general function approximation. Existing methods such as sequential importance sampling estimators and fitted-Q evaluation suffer from the curse of horizon in POMDPs. To circumvent this problem, we develop a novel model-free OPE method by introducing future-dependent value functions that take future proxies as inputs. Future-dependent value functions play similar roles as classical value functions in fully-observable MDPs. We derive a new off-policy Bellman equation for future-dependent value functions as conditional moment equations that use history proxies as instrumental variables. We further propose a minimax learning method to learn future-dependent value functions using the new Bellman equation. We obtain the PAC result, which implies our OPE estimator is close to the true policy value as long as futures and histories contain sufficient information about latent states, and the Bellman completeness. Our code is available at https://github.com/aiueola/neurips2023-future-dependent-ope

Future-Dependent Value-Based Off-Policy Evaluation in POMDPs
Masatoshi Uehara
Haruka Kiyohara Cornell University hk 04.444corneel.com
Genentech
uehara masatosh @gene.
Andrew Bennett
Victor Chernozhukov MIT vchern&mitt.c edu
Morgan Stanley
Andrew, www.eeeeeeetomeeentttaaalle...e
Nan Jiang
Nathan Kallus
Chengchun Shi
UICC
Comell University
LSE
nanjiangeillinois
kallus@cornell.c edu
c. s...heelse..c ac.
Wen Sun Cornell University
ws455ecoomel1..ee
Abstract
We study off-policy evaluation (OPE) for partially observable MDPs (POMDPs) with general function approximation. Existing methods such as sequential im- portance sampling estimators suffer from the curse of horizon in POMDPs. To circumvent this problem, we develop novel model-free OPE method by introduc- ing future-dependent value functions that take future proxies inputs and perform a similar role to that of classical value functions in fully-observable MDPs. We derive new off-policy Bellman equation for future-dependent value functions conditional moment equations that use history proxies as instrumental variables. We further propose a minimax learning method to learn future-dependen value functions using the new Bellman equation. We obtain the PAC result, which implies our OPE estimator is close the true policy value under Bellman completeness, long as futures and histories contain sufficient information about latent states. Our code is available at https://github..om/// hwwpa///w/aaiaiaaaaaeie/222.22.. www.ee2222-uuuuuuueeeeeeeeeee future-ddpeedeentoop..
1 Introduction
Reinforcement learning (RL) has demonstrated success when it is possible to interact with the environment and collect data in an adaptive manner. However, for domains such as healthcare, education, robotics, and social sciences, online learning can be risky and unethical [e.g., KHS+ 15, KL119, TDHL19, SRRH21J. To address this issue, variety of offline RL methods have recently been developed for policy learning and evaluation using historical data in these domains [see LKTF20, for an overview]. In this paper, we focus on the off- policy evaluation (OPE) problem, which concerns estimating the value of new policy (called the evaluation policy) using offline log data that was
"Co-first author. This work was done at Cornell University
Coofirrtt author. This work was done Tokyo Institute of Technology This work was done at Corell University
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

generated under different policy (called the behavior policy) [TB16, JL16, TDHL19, CQ22]. OPE is especially useful in the aforementioned high-stakes domains.
We focus on off-policy evaluation (OPE) in partially observable Markov decision processes (POMDPs). Partial observability is common phenomenon in practical applications [Cas98, KLC98, XLSS20J, and it poses a serious challenge for sample-efficient learning. Most existing OPE methods are developed for MDPs and their statistical learning guarantees rely crucially on the Markov assumption. To extend these methods to POMDPs, one may use the entire history of observations as a state to satisfy Markovanity. This allows us to apply sequential importance sampling [SIS, Pre00, JSLZ19, HW21] or its variant [e.g.. sequential doubly robust (SDR) meth- ods RRS98, MvdLRG01, JL16, TB16, FCG18, BMVVDLI9] policy evaluation. An alternative approach is to employ value-basee methods by constructing a history-dependen Q-function that takes the entire history as input. These value functions can be estimated via fitted-Q evaluation [FQE, EGW05, MS08, LVY19] or minimax methods [ASM08, CJ19, FLL119, NCDL19, UHJ20, UIJ+21, 21, ZW22]. However, all aforementioned estimators suffer from the curse of horizon, their estimation emrors grow exponentially with respect to the (effective) horizon and become prohibitively large in long-horizon settings [LLTZI8, KU20, KU22].
the transformed data for valid
The goal of this paper is to devise practical and efficient OPE methods in large partially observable environments, while breaking the curse of horizon. As a first step, we restrict our attention to the evaluation of short memory- based policies that take several recent observations instead of the entire history as inputs. Short memory-based based policies are widely used in practice, since maintaining the whole previous observation leads to a well-known computational challenge dubbed as the curse of history [PGT06, GMR22]. For example, in the deep Q-network (DQN) algorithm, four game frames are stacked together to train the optimal policy in Atari [MKS+13] while Open Al Five uses a window of length 16 [BBC* 19]. Even when considering the evaluation of policies with short- memory or memory-less characteristics (i.e.. policies that depend solely on current observations), naive methods such as SIS, SDR, and FQE still suffer from the curse of horizon*.
Our proposal takes a model-fre perspective and introduces a new concept called "future-dependee value functions". The proposed value function does not involve latent states which are unobservable in POMDPs. Nor does it relies on the entire data history. It performs the role of standard value functions by incorporating future observations as proxies for latent states. We demonstrate that these future-dependent value functions satisfy a new off-policy Bellman equation for POMDPs, which involves past observations to approximate latent states. To estimate these future-dependent value functions from offline data using the new Bellman equation, we propose minimax learning methods that accommodate various function approximation, including deep neural networks, RKHS, and linear models. Notably, our method extends the classical LSTD [LP03] developed in MDPs to the POMDP setting when using linear models. To summarize, our contributions are as follows:
We propose novel model-free method for OPE that leverages future-depender value functions. Our key idea is to utilize future and historical observations as proxies for latent states.
We derive a new Bellman equation for learning future- -eturee-e value functions. The proposed estimator can accommodate various types of function approximations.
We provide PAC guarantees to demonstrate that our method can address the curse of horizon, and conduct numerical experiments showcase its superiority over existing methods.
Note that similar concepts of future seture-dependent value functions have recently been introduced in the context of OPE in confounded POMDPs [SUHJ22] and online RL in POMDPs 22]. However, we focus on OPE in non-confounded POMDPs. Further detailed discussions can be found in Section 1.1.
1.1 Related Literature
OPE in confounded POMDPs. OPE with unmeasured confounders has been actively stud- ied [ZB16, NKYB20, TSM20, WYW20, KZ20, LFY+21, NJ21, G SZY+22 22, XZS+ 22, LMWY22, CWWY23, BSZ23]. Among them, [TSM20] adopted the POMDP model to formu- late the OPE problem in the presence of unmeasured confounders. They borrowed ideas from the causal inference literature on double negative control adjustment [MGT18, MSTI8, -2,+
'Notiee that even when restricting to short- mheory policies, it is necessary to use the entire history instead of the short memory as the state meet the Markov property.

---

KMU2I, SMNTT20] to derive consistent value estimators in tabular settings. Later, [BKLM21] and [SUHI22] extend their proposal by incorporating confounding bridge functions, thereby enabling general function approximation. (see the difference between these bridge functions and the pro- posed future-dependent value function in Section B). However, these methods do not apply to our unconfounded POMDP setting. This is because these methods require the behavior policy to only depend on the latent state to ensure certain conditional independence assumptions. These assumptions are violated in our setting, where the behavior policy may depend on the observation scenario in practical applications. In addition, we show that in the unconfounded setting, it is feasible to leverage multi-step future observations to relax specific rank conditions in their proposal, which is found to be difficult in the confounded setting [NJ21]. Refer to Example 1.
common
Online learning in POMDPs. In the literature, statistically efficient online learning algorithms with polynomial sample complexity have been proposed in tabular POMDPs [GDBI6, ALA16, JKKL20, LCSJ22], linear quadratic Gaussian setting (LQG) [LAHA2I, SSH20J, latent POMDPs [KECM21] and reactive POMDPs/PSRs [KAL16, JKA + model assumptions. To provide a more unified framework, researchers have actively investigated online learning in POMDPs with general function approximation, evidenced by vast body of work [ZUSL22, LNSJ22, CBM22, ZXZ 22]. As the most relevant work, by leveraging future-dependen value functions, [USL + 22] propose an efficient PAC RL algorithm in the online setting. They require the existence of future-de value functions and a low-rank property of the Bellman loss. Instead, in our approach, while we similarly require the existence of future-dependent value functions, we do not require the low-rank property of Bellman loss. Instead, we use the invertibility condition in Theorem I, i.e., we have informative history proxies as instrumental variables. As a result, the strategies to ensure efficient PAC RL in POMDPs are quite different in the offline and online settings. Learning dynamical systems via spectral learning. There is a rich literature on POMDPs by representing them as predictive state representations (PSRs) [Jac00, LS01, RGT04, SJRO4). PSRs are models of dynamical systems that represent the state as a vector of predictions about future observable events. They are appealing because they can be defined directly from observable data without inferring hidden variables and are more expressive than Hidden Markov Models (HMMs) and POMDPs [SJR04]. Several spectral learning algorithms have been proposed for PSRs [BSGI HKZ12, BGG13], utilizing conditional mean embeddings or Hilbert space embeddings. These approaches provide closed-form learning solutions, which simplifies computation compared to EM-type approaches prone to local optima and non-singularity issues. While these methods have demonstrated success real-world applications [BSG1 ] and have seen subsequent improvements [KJS15, HDG15, VSH 16, DHB 17], it is still unclear how to incorporate more flexible function approximations such as neural networks in a model-free end-to-end manner with a valid PAC guarantee. Our proposed approach not only offers new model-free method for OPE, but it also incorporates these model-based spectral learning methods when specialized to dynamical system learning with linear models (see Section F).
17]. All the methods above require certain
Planning in POMDPs. There is a large amount of literature on planning in POMDPs. Even if the models are known, exact (or nearly optimal) planning in POMDPs is known to be NP-hard in the sense that it requires exponential time complexity with respect to the horizon [PT87, BDRS96]. This computational challenge is often referred to as the curse of history [PGT06]. A natural idea to mitigate this issue is to restrict our attention to mhort-memory policies [AYA18, MY20, KY22, GMR22J. Practically, a mhort-memory policy can achieve good empirical performance, as mentioned earlier. This motivates us to focus on evaluating short-memory policies in this paper.
2 Preliminaries
In this section, we introduce the model setup, describe the offline data and present some notations.
Model setup. We consider an infinite-horizon discounted POMDP M A8 O, Ty where denotes the state space, A denotes the action space, O denotes the observation space, O: D:3 S + ((O) denotes the emission kernel (i.e., the conditional distribution of the observation given the state), T: x A + ASS) denotes the state transition kernel (i.e., the conditional distribution of the next state given the current state-action pair), r S x A R denotes the reward function, and 7 E [0, 1) is the discount factor. All the three functions T. r. O are unknown to the learner.
For simplicity, we consider the evaluation of memory-less policies π O + A(A) that solely depend on the current observation in the main text. The extension to policies with short- short-memory is discussed in Section C.
3

---

Next, given a memory-less evaluation policy τ², we define the parameter interest, i.e. the policy value. Following policy π², the data generating process can described as follows. First, So is generated according to some ini- tial distribution Vs E A(S). Next, the agent observes On O(- So), executes the ini- tial action Ag ~ T-(- Oo), receives a reward r(So, Ao), the environment transits to the next state S1 ~ T(- Sb. An), and this process re- peats. Our objective is to estimate
F
H
P
O-1 A-1
Oo
Ao
0
A
O2
Figure 1: Case with MH = 1, M 2. An action
A is generated depending on O. The extension to memory-based policy is discussed Section
J==))==BA ==
IE 1 R
where the expectation E is taken by assuming the data trajectory follows the evaluation policy x².
Offline data. We convert the trajectory data generated by behavior policy T² : O - ((A), into set of history-observation watprationnnttiooewearrrr future transition tuples (denoted by Pira) and a set of initial observations (denoted by Pini). The first data subset enables to learn the reward, emission and transition kernels whereas the second data subset allows us to learn the initial observation distribution.
Specifically, the dataset Dira consists of N data tuples (HH(,, O61, A R ( } We use (H, O, A, R., F") to denote a generic history-observation action future tuple where denotes the -sse historical observations obtained prior to the observation O and F' denotes the M future observations after (O, A) for some integers MH, MM 1. Specifically, at given time step in the data trajectory, we use (O, A, R) to denote (Ot, A., R2), and set
H = (Ot- Mi:t A A- and F' (01+1=+Mr A411+MM-11).
We additionally set F = (Ot++M A 22) Note we use the prime symbol to represent the next time step. See Figure for details when we set
Throughout this paper, we use uppercase letters such as H,,,,,,,, F") to denote random variables in the offine data, and lowercase letters such as (h, 0, 0,,, (") to denote their real- izations, unless stated otherwise. To simplify the presentation, we assume the stationarity of the environment, i.e., the marginal distributions of (H, S, F') and (H', SH' F") are identical.
The dataset Dini consists N' data tuples (0..
0:Mp-11 M. 2 which is generated as follows:
(()
Sg ~ Vs, O, ~ 0(- S,). A, ~ 7 Og). S₁ ~ T(- S., Ag), "., until we observe O O and A M- We denote its distribution over J Mrr x Mr -MM---1 by v)()).
O and My = 0, MM In that case, we set H to S instead of histories. Then, Dera {0()) A(1), R(t), O'6)) We often assume vo (Vy in our setting) is known. This yields the standard OPE setting MDPs [CJ19, UHJ200.
Remark (Standard MDPs). Consider the setting where
Notation. We streamline the notation follows. We define state value function under n²: V= (8) = Ex k=== 7* Rg Sn = s) for any s E S. Let di (-) be the marginal distribution of S, under the policy n². Then, we define the discounted occupancy distribution d.- = (1 n) Ero 7' (-). We denote the domain of F, H by J (O x A)
O, H (0 AH, respectively. The notations E, EEp (without any subscripts) represent the population or sample average over the offline data D Dura U Dini. respectively. We denote the distribution of offline data by (-) We define the marginal density ratio (S) == (S)( Pr+ Given a matrix C, we denote its Moore-Penross inverse by C+ and smallest singular value by mC)) For given integer m > 0, let Im denote an m x m identity matrix. Let @ denote outer product and [T] (0, ... T} for any integer T 0.
3 Identification via Future-dependent Value Functions
In this section, we present our proposal to identify policy values under partial observability by introducing future-dependent value functions. We remark that the target policy's value is identifiable from the observed data via SIS or SDR. Nonetheless, as commented earlier in Section 1, these methods suffer from the curse of horizon. Here, we propose alternative identification approach that

---

can possibly circumvent the curse of horizon. It serves as building block to motivate the proposed estimation methods Section 4.
In fully observable MDPs, estimating policy's value is straightforward using the value function- based method ( = Bewws[(V' (s)]. However, in partial observable environments where the latent state is inaccessible, the state value function V* V**(s) unidentifiable. To address this challenge,
we propose the use of fulure-dependent value functions that are defined based on observed variables and serve a similar purpose to state value functions in MDPs.
Definition 1 (Future-dependent value functions). Future-dependent value functions gv E [F RJ are defined such that the following holds almost surely,
Elgv (F) |S] VT (S).
Recall that the expectation is taken with respect to the offline data generated by n².
Crucially, the future-dependent value functions mentioned above may not always exist, and they need not be unique. Existence is vital assumption in our framework, although we don't insist on uniqueness. We will return to the topics of existence and uniqueness after demonstrating their relevance in offline policy evaluation.
Hereafter, we explain the usefulness of future-dependen value functions. Tuture-dependent value functions are defined as embeddings of value functions on latent states onto multi-step futures. Notice that J(r²) Exway V (x)] Ey [gv] These future-dependent value functions are useful in the context of OPE as they enable us to accurately estimate the final policy value. However, the future- ceture-dependent value function itself cannot be identified since its definition relies on unobserved states. To overcome this challenge, we introduce learnable counterpart called the learnable future- dependent value function. This learnable version is defined based on observed quantities and thus can be identified.
Definition 2 (Learnable future- deteedddeeendett value functions). Define p(O, == (A O)/T²(
O). Learnable future-dependent value functions by E [F + R] are defined such that the following holds almost surely.
0= == (u(, (6v (F"))
by (F) H].
Recall that the expectation is taken with respect to the offline data generated by л.. We denote the set of solutions by By.
To motivate this definition, we recall that the off- off-policy Bellman equation in MDPs [DNP+ 14] can be expressed as follows:
V" (S) = ((0,))((RR)) +70"
( (S")
Then, by the definition of duture-dependent value functions and certain conditional independence relations (F' 1 (O,A) S'), we obtain that
0 = (μ(O,,) A) + (gv (F) S].
(3)
Since H (0, S, taking another conditional expectation given H on both sides yields that
0 = E [n(O, A) (R + (g') - (V)) H]
Therefore, (4) can be seen an off- off-policy Bellman equation for future-dependee value functions, analogous to the Bellman equation (2) in MDPs. Based on the above discussion, we present the following lemma.
Lemma 1. Future-dependent value functions are learnable fulure-dependent value functions.
Remark 2 (Non- statinttt case). When the offline data non-stationary. i.e, the pdfs of (H, S) and (H', ('.S S') are different, we need additionally require Elgv (F") S* = (8') in the definition. Remark 3 (Comparisons with related works). Similar concepts have been recently proposed in the context of confounded POMDPs [see e.g., SUHJ22, BK21]. However, our proposal significantly dif- from from theirs. First, their confounded setting does not cover our unconfounded setting because their behavior policies n² is not allowed to depend on current observations as mentioned in Section 1. 1.1. Secondly, their proposal heir proposal overlooks the significant aspect of incorporating multi-step future observations, which plays pivotal role in facilitating the existence of dependen value functions, as will be discussed in Example 1. For a detailed discussion, refer to Section B.
5

---

Algorithm 1 Minimax OPE on POMDPs
Require: Dataset D, function classes Q C F R. [H - R). hyperparameter À 2 0
I: by argminge@ maxgez ED... (=(44,) -(())E((H)) - -x²3))))))
2: return JVM = D (f)
Finally, we present a theorem to identify the policy value.
Theorem 1 (Identification). Suppose (Ia) the existence of futrre future-dependent value functions (need not be unique); (1b) the invertiblity condition, i.e., any g : S - R that satisfies ggg(S) H] = 0 must also satisfy g(S) = 0 i.e., g(s) = 0. for almost every 8 that belongs to the support of S). (1c) the overlap condition w-- (S) (5) (S) < 00, u(O, A) co. Then, for any by E Bv
((x)) = =
(5)
We assume three key conditions: the observability condition (i.e., Bv 0), the invertibility condition, and the overlap condition. We call Condition (la) the observability condition since it is reduced to the well-known concept of observability in the LQG control theory, as we will see in Section D. While Condition (Ia) itself is concerned with learnable future- deeueddde value functions, it is implied by the existence of unlearnable anture-dependend value functions according to Lemma I which can be verified using Picard's 's theorem in functional analysis [CFR07]. In general, the observability condition requires the future proxy F to contain sufficient information about S and is likely to hold when F consists of enough future observations. We will see more interpretable conditions in the tabular POMDPs (Example 1) and POMDPs with Hilbert space embeddings (HSE-POMDPs) where the underlying dynamical systems have linear conditional mean embeddings (Example 5 in Section D).
The invertibility condition is imposed to ensure that a learnable future-dependent value function by satisfies (3) (note that right hand side of Eq. 3 is a function of Z, S instead of H). Again, we will present more interpretable conditions in the tabular and linear settings below and in Section D. Roughly speaking, it requires H to retain sufficient information about S. In that sense, the history proxy serves as an instrumental variable (IV), which is widely used in economics [Horl1, New13]
Finally, the overlap condition is a standard assumption in OPE [UI]+21).
Example (Tabular Setting). In the tabular case, abstract assumptions in Theorem are reduced to certain rank assumptions. We first define S {s S (*) 0). We define a matrix PF, Sb) RIFixis whose (i, element is (F = z/}) where x; is the ith element in F, and a'y is the jth element in St. We similarly define another matrix Pr, (S, H) whose (1,5)- 1-th element is PS z',, H = x where z; denotes the jth element in H.
Lemma 2 (Sufficient conditions for observability and invertibility (a) When rank Sp)) Sel. future-dependen value functions exist. Then, from Lemma 1, learnable future-dependent value functions exist. (b) The invertiblity is satisfied when rank(Pr, (S,, H)) =Spl-
The first two conditions require that the cardinalities F F and H must be greater than or equal to So, respectively. The proof of Lemma 2 is straightforward, as integral equations reduce to matrix algebra in the tabular setting. We note that similar conditions have been assumed in the literature on HMMs and POMDPs [SBS+ 10, BSGI BGG13]. In particular, ( S²) = |Se) has been imposed in previous works [NJ21, SUHJ22] in the context of confounded POMDPs. Nonetheless, our condition Pr (F S.) = |S,) is strictly weaker when FF includes multi-step future observations. demonstrating the advantage of incorporating multi-step future observations compared to utilizing only the current observation. more detailed discussion can be found in Appendix D.
Estimation with General Function Approximation
In this section, we demonstrate how to estimate the value of a policy based on the results presented in Section 3. We begin by outlining the proposed approach for estimating (-). The key observation is
'The observation that history can serve as an instrumental variable in POMDPs is mentioned in [HDG15, VSH 16]. However, these works aim to learn the system dynamics instead of policy evaluation or learning. Hence, concepts like depereed value functions do not appear in these works.

---

that it satisfies L[ E)] = 0 for any :: + R where [g) is defined as
L(g. E = ([(,,,)(++(((()) - (H))
for q: F IR and { H R. Given some constrained function classes Q [F RJ and C - R and a hyperparameter À 2 0, the estimator is computed according to Line 1 of easily show that the population-level minimizers argmin maxęez [[L(g, - (H)) are all learnable future-dependent value functions. This is later formalized in Theorem 2.
Algorithm 1. When the realizability By n Q + 0 holds and E is unconstrained,
We can use any function classes such as neural networks, RKHS, and random forests to parameterize Q and E. Here, the function class E plays critical role in measuring how q deviates from the ground truth by. The hyperparameter À is introduced to obtain a fast convergence rate. We call it a stabilizer approaches infinity. Note that
instead of a regularizer since À does not need to shrink to zero regularizers are needed when we penalize the norms of q and &, i.e.,
by = argmin max Ep (p. - 0.5 (H) + 0.5a' 0.50'1141 - 0.5a 0
gEQ
EEE
for certain function norms || llee and || || and hyperparameters a', 0.
In the remainder of this section, we present three concrete examples using linear models, RKHSs and neural networks. Let || ele and
|| || denote no2-norms when we use linear models and RKHS
norms when using RKHSs.
Example 2 (Linear models). Suppose Q.E are linear, i.e.. G = (0T))()) I 1 E R
(o Φx(+) | 0 E Tedb) with features or : F + Rdy &H H - TR.n. Then,
(.) = ()) (M, {alaa + AMa] M2a + a' 1ay} } M (alax + AMa) 'MI,
M, = ED [00, A) M2 = (H) - ()OT,A))((F")) M3 = En)dx
When a' 0, a 0, \- = 0, the value estimators boil down to
bv()) = +.) MI, JvM = Es-us [
The above estimators are closety related to the LSTD estimators in MDPs [LP03]. Specifically, the off- off-policy LSTD estimator for state- aalue functions (DNP* 14, UHJ200 is given by
Egwug 106 (s)[ED (os (5)00 (S) 7H(S, (o))
(6)
Our new proposed estimator JvM is
Bi-uy (D)())))))))))))) - ~M)) AFOT((")) (H))
which is very similar to (6). The critical difference lies in that we use futures (including current observations) and histories as proxies infer the latent state S under partial observability.
Example 3 (RKHSs). Let Q, be RKHSs with kernels FxF - kH(,) )) H - RR Then,
by()) ks(+) {(K's] faIn + Ku) Tk'--'ss +a'nn KK2) 1 faIn +u ba.l-K'' 'K2/2x
where E RR, k(.) E R", KH E Ruxn K2 Runn such that
(K*)us) = Kx (H1), H()), (k>)o,)=>>(T()) (O)) = kk)((()) p(اT Example 4 (Neural Networks). We set Q to a class of neural networks and recommend to set E to a linear or RKHS class so that the minimax optimization is reduced to single-stag stage optimization. The resulting optimization problem can be solved by off the-thh-sheff stochastic gradient descent (SGD) methods. Specifically, when we set E to linear model, by is reduced to
= A
=
(5))->kyle (F((())))) p()), (k)())
by = argmin Z(q) [aal + (H))) 9EQ
Z(g)= == Eole(A, 7q(" q (F]]))x(H))
When we set E to be an RKHS, by is reduced to
{aln ]KH3 -K 1/2 2(4), {z'(4))=== == ) + [)( -(F(())
by argmin rEQ
{ Zz (q)) T K 1/2 H
7

---

Remark 4 (Comparison with minimax methods for MDPs). Our proposed methods are closely related to the minimax learning approach (a.k.a. Bellman residual minimization) for RL [ASM08]. More specifically, in MDPs where the evaluation policy is memory-less, [UIJ+ 21, TFL+ proposed minimax learning methods based on the following equations,
() (S") + R] V** (S) =0 vh S
These methods are no longer applicable in POMDPs since we are unable to directly observe the latent state. Although substituting the latent state with the entire history can still provide statistical guarantees, is susceptible to the curse of horizon.
Remark (Modeling of system dynamics). Our minimax estimators can be extended to learning system dynamics. In particular, for tabular POMDPs, these results are closely related to the literature on spectral learning HMMs and POMDPs (SBS 10, BSGII, BGGI3]. Refer to Section F.G.
Remark 6 (Finite horizon setting). The extension to the finite horizon setting is discussed Section
5 Finite Sample Results
We study the finite sample convergence rate of the proposed estimators in this section. To simplify the technical analysis, we impose three assumptions. First, we assume the function classes are bounded, i.e., [2] S Co | Oz for some Co. C= >> O. Second, we assume that the offline data are i.i.d. Third, we assume Q, E are finite hypothesis classes. Meanwhile, our results can be extended to infinite hypothesis classes using the global/local Rademacher complexity theory; see e.g., [UI]+21]. To simplify the presentation, following standard convention in OPE, we suppose the initial distribution is known, i.e., mu oc.
Accuracy of by. We first demonstrate that by consistently estimates the learnable future-dependent value bridge functions. To formalize this, we introduce the following Bellman operators.
Definition (Bellman operators). The Bellman residual operator onto the history is defined as
T 3 (()) + Bly(O, A) + FF)))) - -FFF H HH=1 = .
and the Bellman residual ervor onto the history is defined as (((Tg) Similarly, the Bellman residual operator onto the latent state, T is defined
T FF R] 2(-) Blu(O, A) + (F(F)) (F)
and the Bellman residual error onto the latent state is defined as (((TT(a)) The conditional expectations equal to zero when h and lie outside the support of H. and S, respectively.
The Bellman residual error onto the history is zero for any learnable future-dependent value function, ie.. by ) (H)) 0. Thus, this is suitable measure to assess how well value function-based estimators approximate the true learnable future-dependent value functions.
Theorem 2 (Finite sample property of by). Set X 0. Suppose (2a) By n Q o 0 (realizability) and (2b) TQ C E (Bellman completeness). With probability 1- we have
c(1/A+ }} max(1,CC Co, V
Int [lc//) where c is some universal constant.
Note (2a) and (2b) are commonly assumed in the literature on MDPs [CJ19, UII+21] as well. In particular, Bellman completeness means that the function class E is sufficiently rich to capture the Bellman update of functions in Q For instance, these assumptions are naturally met in HSE- POMDPs. We require À in the statement of Theorem 2 to obtain parametric convergence rate. When À 0, although we can obtain rate of On 1/1), it is unclear whether we can achieve
Accuracy of JvM- We derive the finite sample guarantee for JyM-
'Without the independence assumption, similar results can be similarly established by imposing certain mixing conditions; see e.g.. (SZLS20, LQM20, KU22].

---

Theorem 3 (Finite sample property of Jv2)). Ser À > O. Suppose (2a), (2b), (2c) any element
in q E Q that satisfies E[{ (q))() H] = also satisfies T (g) 0. (2d) the overlap
())
m(O, A) < co and any element in q E Q that satisfies T (1) = 0 also satisfies T (5)
where 50 (g)( With probabilityy 1 8, we have
c(1/+ A) max(1, CGT.C.. P [[(*)) Jvul -
In ([1
(7)
(1 (1-
n
where
E (1){)}
OV) = { (
sup
[[(T())(H))P]
(8)
E Bnwd+ : (g)
Dr Droldar, /d., Pa+] =
sup (vER I(T (+)0)))))) ESS P, (T)())
(9)
On top of (2a) and (2b) that are assumed in Theorem 2, when (V1 < 00, (2c) and (2d) hold, we have the non-vacuous PAC guarantee. The condition Dre P+t) oc and (2d) are the overlap conditions, which are adaptive to the function class and are weaker than (Ic). These are also used in MDPs [XCI+21]. Here, Dr : Pa+) is a refined version of the density ratio and satisfies Dr (d=s, P=*) S wn= (S). The condition IV1 ( (2) < oo and (2c) are characteristic conditions in POMDPs that quantify how much errors are properly translated from on H to on S. Similar assumptions are frequently imposed in IV literature [DLMS20, CP12].
sc.
The upper error bound in (7) does not have explicit exponential dependence on the effective horizon 1/(1- 7). In particular, as shown in Section D, for tabular POMDPs and HSE-POMDPs, the terms Dre(d==, Pr*)) and k( Q) can be reduced to certain condition numbers associated with covariance matrices spanned by feature vectors; see (15) and (16) in Appendix D. Hence, unlike SIS- methods, we are able to break the curse of horizon.
The numbers of future and history proxies included in F and H represents tradeoff. Specifically, if F contains enough observations, it is likely that (2a) will hold. Meanwhile, if H contains enough observations, it is more likely that (2b) will hold. These facts demonstrate the benefits of including sufficient number of observations in F and H. However, the statistical complexities In]] will increase with the number of observations in F and HI
Lastly, it's worth noting that while our methods effectively address the curse of horizon, they may incur exponential growth concerning the number of future proxies used. This also applies to history proxies, which should be longer than the length of short memory policies. Here, we focus on the explanation of future proxies. For instance, in the tabular case, log [S2] might scale with (M|M when considering Ω2 as the set of all functions on Mr However, this situation differs significantly from the curse of horizon, a challenge that naive methods like replacing states with the entire history encounter. These methods would necessitate the entire history to achieve Markovianity, whereas we only require a shorter length of future observations establish the conditions outlined in Theorem (existence), which can be much shorter. Specific examples are provided throughout the paper, including Example which discusses the tabular setting and demonstrates that we essentially need as many future proxies as states, as long as there is sufficient statistical dependence between them.
6 Experiment
This section empirically evaluates the performance of the proposed method on a synthetic dataset.?. 7.
We use the CartPole environment provided by OpenAl Gym [BCP+ 16), which is commonly employed in other OPE studies [SUH]22, FCG18). By default, this non-tabular environment consists of 4- dimensional states, which are fully observable. Following [SUHJ22], we create partial observability by adding independent Gaussian noises to each dimension of the state as O6i) = S(i) (1 + -V(1- + ),32)), 1 رj < 4. To define behavior and evaluation policies, we first train an expert policy using DDQN [VHGS 16] on latent states S. Subsequently, we apply Behavior Cloning (BC) on two datascts, one containing pairs of latent state and action (S, A) and the other containing pairs of observation respeeee respectively. Then, we use the base policy obtained by BC on the state-action
and action (0, A),
Our code is available at hutp://gihhbbcommiiiooolldeutlpp httpe--uuuureeeeeeeettooo

---

CartPole with
..10.0...3)
CartPole Obs A10.0 0.34)
De (Dbm)
POWCN 20 incurialls
Log of Bias (relative)
Log of (relative)
Choice of
Choice of
Figure 2: Logarithms of relative biases (left) and MSEs (right) of the proposed and the baseline estimators for various values of e, which specify the evaluation policy. The confidence intervals are obtained through 100 Monte Carlo simulations.
pairs (S, A) to define an <-greedy behavior policy, where we set e = 0.3. Similarly, the evaluation policy is also e-greedy policy, based the hase policy obtained by BC the observation-action pairs (O, A), with different values of E [0.1, 0.3, 0.5, 0.7]. We conduct the experiment with 100 random seeds, and for each simulation, we collect logged data consisting of 1000 trajectories, each containing 100 steps.
We compare our proposal with Sequential Importance Sampling (SIS) [Pre00] and the naive minimax OPE [UH/20]. which is designed for oully-observable MDPs and does not account for partial observability. The naive minimax estimator is defined if the environment replacing H and F in Algorithm with the current observation O. In contrast, our proposed method a 3-step history H and one-step future F address partial observability. Both proposed method and the naive approach use two-layer neural networks for the function Q and RKHSs for E, detailed in Example 4.
fully observable,
We present the results in Figure 2, which demonstrate the superior accuracy of our proposed estimator compared to the baselines (SIS and naive minimax estimator) in terms of mean square errors (MSEs). Additional experimental details and ablation results, including the variations in the length of H, F, and the choice of RKHSs, can be found in Appendix H.3.
7 Conclusion
We present a novel approach for OPE of short-memory policies in POMDPs. Our method involves in- troducing future-dependent value functions and the associated off-policy Bellman equations, followed by proposing a minimax estimator based on these equations. This is the first model-free method that allows for general function approximation and mitigates the curse of horizon. Our proposal is grounded three interpretable key assumptions: observability, which asserts the presence of (short) future observations retaining adequate information about latent states, invertibility, which posits the existence of (short) histories preserving ample information about latent states; and the overlap between evaluation policies and behavior policies.
We have several avenues for enhancing our proposals. Firstly, automatically determining the appropriate lengths of futures and histories holds practical significance. Additionally, explor- ing recent attention mechanisms that extend beyond selecting the most recent history proxies or the nearest future proxies shows promise. Secondly, while we establish Bellman equations for POMDPs and use a simple minimax approach akin to [DLMS20], we may benefit from leverag- ing more refined methods introduced in recent research for solving conditional moment equations 23c, BKM 23a, BKM+23b),
Acknowledgements
This material is based upon work supported by the National Science Foundation under Grant Nos. IIS 21 2471, IIS 2141781, IIS 1846210, IIS 2154711 and Engineering and Physical Sciences Research Council grant EP/W014971/1.
'When collecting offfine data from the behavior policy, the behavior policy takes the observation O as input, noting that the dimension of S and O is the same in our experimental setting.
10

---

References
[ALA16] Kamyar Azizzadenesheli, Alessandro Lazaric, and Animashree Anandkumar. Rein- forcement learning of pomdps using spectral methods. Conference on Learning Theory, pages 193-256. PMLR, 2016.
[ASM08] András Antos, Csaba Szepesvári, and Rémi Munos. Learning near-optimal policies with bellman-residual minimization based fitted policy iteration and single sample path. Machine Learning, 71(1):89-122 2008
[AYA18] Kamyar Azizzadenesheli, Yisong Yue, and Animashree Anandkumar, Policy gradi- ent in partially observable environments: Approximation and convergence. arXiv preprint arXiv: 1810.07900, 2018.
[BBC+19 19] Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemyslaw Debiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Chris Hesse, et al. Dota 2 with large scale deep reinforcement learning. arXiv preprint arXin:1912.06680 2019.
[BCP+16] Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym. arXiv preprint arXiv: 000v::66000000 01 540, 2016.
[BDRS96] Dima Burago, Michel De Rougemont, and Anatol Slissenko. On the complexity of partially observed markov decision processes. Theoretical Computer Science, 157(2):161-18,, 1996.
[Ber12] Dimitri Bertsekas. Dynamic programming and optimal control: Volume volume 1. Athena scientific, 2012.
[BGG13] Byron Boots, Geoffrey Gordon, and Arthur Gretton. Hilbert space embeddings of predictive state representations. arXiv preprint (rXiv:1309.68) 2013.
[BK21] Andrew Bennett and Nathan Kallus. Proximal reinforcement learning: Efficient off-policy evaluation in partially observed markov decision processes. 2021.
[BKLM21] Andrew Bennett, Nathan Kallus, Lihong Li, and Ali Mousavi. Off-policy evaluation in infinite-horizon reinforcement learning with latent confounders. In International Conference Artificial Intelligence and Statistics, pages
PMLR, 2021.
[BKM 1 23a] Andrew Bennett, Nathan Kallus, Xiaojie Mao, Whitney Newey, Vasilis Syrgkanis, and Masatoshi Uehara. Inference strongly identified functionals of weakly identified functions. In The Thirty Sixth Annual Conference on Learning Theory, pages
PMLR, 2023.
[BKM 23b] Andrew Bennett, Nathan Kallus, Xiaojie Mao, Whitney Newey, Vasilis Syrgkanis, and Masatoshi Uehara. Minimax instrumental variable regression and /2 convergence guarantees without identification or closedness. In Gergely Neu and Lorenzo Rosasco, editors, Proceedings of Thirty Sixth Conference Learning Theory, volume 195 of Proceedings of Machine Learning Research, pages 2291-2318, 2023.
[BKM+23c] Andrew Bennett, Nathan Kallus, Xiaojie Mao, Whitney Newey, Vasilis Syrgkanis, and Masatoshi Uchara. Source condition double robust inference on functionals of inverse problems. arXiv preprint arXivv2307.137993 2023.
[BKS19] Andrew Bennett, Nathan Kallus, and Tobias Schnabel. Deep generalized method of moments for instrumental variable analysis. In Advances in Neural Information Processing Systems 32, pages 3564-3574. 2019.
BMVVDL19] Aurelien Bibaut, Ivana Malenica, Nikos Vlassis, and Mark Van Der Laan. More efficient policy evaluation through regularized targeted learning. International Conference Machine Learning, pages 654-663. PMLR, 2019.
11

---

[BSG11] Byron Boots, Sajid M Siddiqi, and Geoffryy J Gordon. Closing the learning- planning loop with predictive state representations. The International Journal of Roboties Research, 30(7):554-966, 2011.
[BSZ23] David Bruns-Smith and Angela Zhou. Robust -evalu-g-valtttionn and iteration under sequentially exogenous unohserved confounders. arXiv preprint arXiv:2302.00662, 2023.
[Cas98] Anthony R Cassandra. survey of pomdp applications. In Working notes of AAAI 1998 fall symposium on planning with partially observable Markov decision processes, volume 1724, 1998.
[CBM22] Fan Chen, Yu Bai, and Song Mei. Partially observable rl with b-stability: Uni- fied structural condition and sharp sample-efficient algorithms. arXiv preprint htfi:2200.14990, 2022.
[CFR07] Marine Carrasco, Jean-Pierre Florens, and Eric Renault. Linear inverse problems in structural econometries estimation based on spectral decomposition and regulariza- tion. Handbook of econometrics, 6:5633-5751 -551,, 2007.
[CJ19] Jinglin Chen and Nan Jiang. Information-theoretie theoretic considerations in batch reinforce- ment learning. In International Conference Machine Learning, pages 1042-1051. PMLR, 2019.
[CKPW18] Zhiyong Cui, Ruimin Ke, Ziyuan Pu, and Yinhai Wang. Deep bidirectional and unidirectional Istm recurrent neural network for network -iide traffic speed prediction. arXiv preprint arXiv: 1801.02/444000 2018
[CNS18] Victor Chernozhukov, Whitney K Newey, and Rahul Singh. Learning 12 con- tinuous regression functionals via regularized riesz representers. arXiv preprins arXiv:1809.05224, 2018.
[CNSS20] Victor Chernozuukov, Whitney Newey, Rahul Singh, and Vasilis Syrgkanis. Adver- sarial estimation of riesz representers. arXiv preprint arXiv:2101.000: 000009, 2020.
[CO20] Sayak Ray Chowdhury and Rafael Oliveira. No-regret reinforcement learning with value function approximation: kernel embedding approach. arXiv preprint arXiv:2011.07881, 2020.
[CP12] Xiaohong Chen and Demian Pouzo. Estimation of nonparametric conditional moment models with possibly nonsmooth generalized residuals. Econometrica, 80(1):277- 321, 2012.
[CP Yifan Cui, Hongming Pu, Xu Shi, Wang Miao, and Eric Tchetgen Tchetgen. Semi- parametric proximal causal inference. arXiv preprint urXiv:2011.08411, 2020.
[CQ22] Xiaohong Chen and Zhengling Qi. On well-posedness and minimax optimal rates of nonparametric q-function estimation in off-policy evaluation. arXiv preprint arXiv:2201.066 2022.
[CWWY23) Siyu Chen, Yitan Wang. Zhaoran Wang, and Zhuoran Yang. unified framework of policy learning for contextual bandit with confounding bias and missing observations. arXiv preprint arXiv:2303.1 1171 2023.
[DHB+17] Carlton Downey, Ahmed Hefny, Byron Boots, Geoffrey Gordon, and Boyue Li. Predictive state recurrent neural networks. Advances in Neural Information Processing Systems, 30, 2017.
[DJW20] Yaqi Duan, Zeyu Jia, and Mengdi Wang. Minimax-optimal off off-policy evaluation with linear function approximation. In International Conference on Machine Learning, pages 2701-2709. PMLR, 2020.
12

---

[DLMS20]
Nishanth Dikkala, Greg Lewis. Lester Mackey, and Vasilis Syrgkanis. Minimax estimation of conditional moment models. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 12248-12262, 2020.
[DNP*14] Christoph Dann, Gerhard Neumann, Jan Peters, et al. Policy evaluation with temporal differences: A survey and comparison. Journal of Machine Learning Research, 15:809-8833 2014.
[EGW05] Damien Ernst, Pierre Geurts, and Louis Wehenkel. Tree-based batch mode reinforce- ment learning. Journal of Machine Learning Research, 6:503-50 556, 2005.
[FCG18] Mehrdad Farajtabar, Yinlam Chow, and Mohammad Ghavamzadeh. More robust dou- bly robust off-policy evaluation. In International Conference on Machine Learning. pages 1447-1456. PMLR, 2018.
[FLL19] Yihao Feng, Lihong Li, and Qiang Liu. A kernel loss for solving the bellman equation. Advances in Neural Information Processing Systems, 32, 2019.
[FS19] Dylan J Foster and Vasilis Syrgkanis. Orthogonal statistical learning. arXiv preprint 1wXv::191.000036 2019.
[2CZ*22] Hongyi Guo, Qi Cai, Yufeng Zhang. Zhuoran Yang, and Zhaoran Wang. Provably efficient offline reinforcement learning for partially observable markov decision processes. In International Conference on Machine Learning, pages 8016-8038. PMLR, 2022.
[GDB16] Zhaohan Daniel Guo, Shayan Doroudi, and Emma Brunskill. A pac rl algorithm for episodic pomdps. In Artificial Intelligence and Statistics, pages 510-518. PMLR, 2016.
[GMR22] Noah Golowich, Ankur Moitra, and Dhruv Rohatgi. Planning in observable pomdps quasipolynomial time. arXiv preprint arXiv:2201.04735 2022.
[HDG15] Ahmed Hefny, Carlton Downey, and Geoffrey J Gordon. Supervised learning for dynamical system learning. Advances in neural information processing systems, 18:19611 2015.
[2D Botao Hao. Yaqi Duan, Tor Lattimore, Csaba Szepesvári, and Mengdi Wang. Sparse feature selection makes batch reinforcement learning more sample efficient. In International Conference on Machine Learning, pages 4063-4073. PMLR, 2021.
[HKZ12] Daniel Hsu, Sham M Kakade, and Tong Zhang. A spectral algorithm for learning hidden markov models. Journal of Computer and System Sciences, 7865):1460-1488 2012.
[Horl1] Joel L Horowitz. Applied nonparametric instrumental variables estimation. Econo- metrica, 79(2):347-394, 2011.
[HW17] David A Hirshberg and Stefan Wager. Augmented minimax linear estimation. arXiv preprint arXiv: 1712.0771 2017.
[HW21] Yuchen Hu and Stefan Wager. Off Off-policy evaluation in partially observed markov decision processes. arXiv preprint arXiv:2 /2343, 2021.
[Jae00] Herbert Jaeger. Observable operator models for discrete stochastic time series. Neural computation, 12(6):1371-1399 2000.
[JKA+17] Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. Contextual decision processes with low bellman rank are pac-learnable. In International Conference on Machine Learning, pages 1704-1713, PMLR, 2017.
[JKKL20] Chi Jin, Sham M Kakade, Akshay Krishnamurthy, and Qinghua Liu. Sample-efficient reinforcement learning of undercomplete pomdps. arXiv preprint arXiv:2006. 12484, 2020.
13

---

[JL16] Nan Jiang and Lihong Li. Doubly robust off policy value evaluation for reinforcement learning. In International Conference on Machine Learning, pages 552-661. PMLR, 2016.
[SSLZ19] Binyan Jiang, Rui Song, Jialiang Li, and Donglin Zeng. Entropy learning for dynamic treatment regimes. Statistica Sinica, 29(4): 2019.
[KAL16] Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Pac reinforcement learning with rich observations. Advances in Neural Information Processing Systems, 29, 2016.
[KB14] Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 14/2v::4/2.6900 2014.
[KECM21] Jeongyeol Kwon, Yonathan Efroni, Constantine Caramanis, and Shie Mannor. RI for latent mdps: Regret guarantees and a lower bound. Advances in Neural Information Processing Systems, 34, 2021.
[KHS+15] Predrag Klasnja, Eric Hekler, Saul Shiffman, Audrey Boruvka, Daniel Almirall, Ambuj Tewari, and Susan A Murphy. Microrandomized trials: An experimen- tal design for developing just-in-time adaptive interventions. Health Psychology. 34(S):1220, 2015.
[KIS15] Alex Kulesza, Nan Jiang, and Satinder Singh. Spectral learning of predictive state representations with insufficient statistics. In Twenty-Ninth AAAI Conference on Artificial Intelligence, 2015.
[KL19] Michael Kosorok and Eric B Laber. Precision medicine. Annual review of statistics and its application, 6:263-286, 2019.
[KLC98] Leslie Pack Kaelbling, Michael I. Littman, and Anthony R Cassandra. Planning and acting in partially observable stochastic domains. Artificial intelligence, 101(1-2):99- 134, 1998.
[KMU2I] Nathan Kallus, Xiaojie Mao, and Masatoshi Uchara. Causal inference under un- measured confounding with negative controls: A minimax learning approach. arXiv preprint 20X. 14029, 2021.
[KU20] Nathan Kallus and Masatoshi Uchara. Double reinforcement learning for efficient off- policy evaluation in markov decision processes. J. Mach. Learn. Res., 21(167):1-63, 2020.
[KU22] Nathan Kallus and Masatoshi Uehara. Efficiently breaking the curse of horizon in off- off-policy evaluation with double reinforcement learning. Operations Research, 2022.
[KY22] Ali Devran Kara and Serdar Yuksel. Near optimality of finite memory feedback poli- cies in partially observed markov decision processes, Journal of Machine Learning Research, 23(1 13:114),4 2022.
[KZ20] Nathan Kallus and Angela Zhou. Confounding-robute policy evaluation in infinite- horizon reinforcement learning. arXiv preprint arXiv:2002.045116 2020.
[LAHA21] Sahin Lale, Kamyar Azizzadenesheli, Babak Hassibi, and Anima Anandkumar. Adaptive control and regret minimization in linear quadratic gaussian (Igg) setting. In 2021 American Control Conference (ACC), pages 2517-2522. IEEE, 2021.
[LCSJ22] Qinghua Liu, Alan Chung, Csaba Szepesvári, and Chi Jin. When is partially observ- able reinforcement learning not scary? arXiv preprint arXiv:2204.08967 2022.
[LFY+21] Luofeng Liao, Zuyue Fu, Zhuoran Yang, Yixin Wang, Mladen Kolar, and Zhaoran Wang. Instrumental variable value iteration for causal offline reinforcement learning. arXiv preprint 2021.
14

---

[LKTF20] Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. Offline reinforcement learning: Tutorial, review, and perspectives on open problems. arXiv preprint arXiv:000.006643, 2020.
[LLTZ18] Qiang Liu, Lihong Li, Ziyang Tang, and Dengyong Zhou. Breaking the curse of horizon: Infinite-horizon off-policy estimation. In Advances in Neural Information Processing Systems 31. pages 5356-5366. 2018.
[LMWY22] Miao Lu, Yifei Min, Zhaoran Wang, and Zhuoran Yang. Pessimism in the face of confounders: Provably efficient offline reinforcement learning in partially observable markov decision processes. arXiv preprint arXiv:2205. 2.N::2999.3389. 2022.
[LNSJ22] Qinghua Liu, Praneeth Netrapalli, Csaba Szepesvari, and Chi Jin. Optimistic mle-a generic model-based algorithm for partially observable sequential decision making. arXiv preprint arXiv:2209. 14997, 2022.
[LPO3] Michail G Lagoudakis and Ronald Parr. Least-squares policy iteration. The Journal of Machine Learning Research, 4:1 1077-114,, 2003.
[LQM20] Peng Liao, Zhengling Qi, and Susan Murphy. Batch policy learning in average reward markov decision processes. arXiv preprini arXi::2007. 2020.
[LSO1] Michael Littman and Richard S Sutton. Predictive representations of state. Advances in neural information processing systems, 14, 2001.
[LVY19] Hoang Le, Cameron Voloshin, and Yisong Yue. Batch policy learning under con- straints. In International Conference on Machine Learning, pages 3703-3712. PMLR, 2019.
[MGT18] Wang Miao, Zhi Geng, and Eric J Tchetgen Tchetgen. Identifying causal effects with proxy variables of an unmeasured confounder. Biometrika, 105(4):977-993, 2018.
[MKS+13] 13] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep re- inforcement learning. arXiv preprint arXiv: 2013.
[MS08] Rémi Munos and Csaba Szepesvári. Finite-time bounds for fitted value iteration. Journal of Machine Learning Research, 9(5), 2008
[MST18] Wang Miao, Xu Shi, and Eric Tchetgen Tchetgen. confounding bridge approach for double negative control inference on causal effects. arXiv preprint teXiv:/808.04900 2018.
[MdLRGG01] Susan A Murphy, Mark J van der Laan, James M Robins, and Conduct Problems Prevention Research Group. Marginal mean models for dynamic regimes. Journal of the American Statistical Association, 1410-142,,, 2001.
[MY20] Curtis McDonald and Serdar Yüksel. Exponential filter stability via dobrushin's coefficient. Electronic Communications in Probability, 25:1-13, 2020.
[NCDL19] Ofir Nachum, Yinlam Chow, Bo Dai, and Lihong Li. Dualdice: Behavior- agnostic estimation of discounted stationary distribution corrections. arXiv preprint 1906 2019.
[New13] Whitney K Newey. Nonparametric instrumental variables estimation. American Economic Review, 103(3):550-56, 2013.
[NJ21] Yash Nair and Nan Jiang. A spectral approach off-policy evaluation for pomdps. arXiv preprint arXiv: 109. 10502, 2021.
[NKYB20] Hongseok Namkoong, Ramtin Keramati, Steve Yadlowsky, and Emma Brunskill. Off-policy policy evaluation for sequential decisions under unobserved confounding. arXiv preprint arXiv:2003.0562. 2020.
15

---

[PGT06] Joelle Pineau, Geoffrey Gordon, and Sebastian Thrun. Anytime point-based approxi- mations for large pomdps. Journal of Artificial Intelligence Research, 27:335-380, 2006.
[Pre00] Doina Precup. Eligibility traces for off-policy policy evaluation. Computer Science Department Faculty Publication Series, page 80, 2000.
[PT87] Christos H Papadimitriou and John N Tsitsiklis. The complexity of markov decision processes, Mathematics of operations research, 12(3):441 450, 1987.
[RGT04] Matthew Rosencrantz, Geoff Gordon, and Sebastian Thrun. Learning low dimen- sional predictive representations. In Proceedings of the twenty-first international conference on Machine learning, page 88, 2004.
[RRS98] Andrea Rotnitzky, James M Robins, and Daniel O Scharfstein. Semiparametric regression for repeated outcomes with nonignorable nonresponse. Journal of the american statistical association, 93(444):1321-1339 1998.
10] Le Song, Byron Boots, Sajid M Siddiqi. Geoffrey Gordon, and Alex Smola. Hilbert space embeddings of hidden markov models. In Proceedings of the 27th International Conference on International Conference on Machine Learning, pages 991-998, 2010.
[SHSF09] Le Song, Jonathan Huang, Alex Smola, and Kenji Fukumizu. Hilbert space em- beddings of conditional distributions with applications to dynamical systems. In Proceedings of the 26th Annual International Conference on Machine Learning, pages 961-968, 2009.
[SJR04] Satinder Singh, Michael James, and Matthew Rudary. Predictive state representations: A new theory for modeling dynamical systems. In Proceedings of the 20th Conference on Uncertainty in Artificial Intelligence, 2004.
[SMNTT20] Xu Shi, Wang Miao, Jennifer C Nelson, and Eric Tchetgen Tchetgen. Multiply robust causal inference with double-negative control adjustment for categorical un- measured confounding. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 82(2):521-585 2020.
[SRRH21] Adish Singla, Anna N Rafferty, Goran Radanovic, and Neil Heffernan. Rein- forcement learning for education: Opportunities and challenges. arXiv preprint arXiv:2107.08828, 2021.
[SSH20] Max Simchowitz, Karan Singh, and Elad Hazan. Improper learning for non- non-stochastic control. In Conference on Learning Theory, pages 3320-3436. PMLR, 2020.
[SUHJ22] Chengehun Shi, Masatoshi Uehara, Jiawei Huang. and Nan Jiang. minimax learning approach to off-policy evaluation in confounded partially observable markov decision processes. In International Conference on Machine Learning, pages 20057- 20094. PMLR, 2022.
[SZLS20] Chengchun Shi, Sheng Zhang, Wenbin Lu, and Rui Song. Statistical inference of the value function for reinforcement learning in infinite horizon settings. arXiv preprint arXiv:2001.0451:1 2020.
[2ZY+22] Chengchun Shi, Jin Zhu, Shen Ye, Shikai Luo, Hongtu Zhu, and Rui Song. Off-policy confidence interval estimation with confounded markov decision process. Journal of the American Statistical Association, pages 1-12, 2022.
(TB16) Philip Thomas and Emma Brunskill. Data-efficient off-polic policy evaluation for reinforcement learning. In International Conference Machine Learning, pages 2139-2148. PMLR, 2016.
[TDHL19] Anastasios A Tsiatis, Marie Davidian, Shannon T Holloway, and Eric B Laber. Dynamic Treatment Regimes: Statistical Methods for Precision Medicine. CRC press, 2019.
16

---

[TF Ziyang Tang, Yihao Feng, Lihong Li, Dengyong Zhou, and Qiang Liu. Harnessing infnitehorizon off- pollcy evaluation; Double robustness via duality. ICLR 2020, 2020.
[TSM20] Guy Tennenholtz, Uri Shalit, and Shie Mannor. Off-policy evaluation in partially observable environments. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 10276- 10283, 2020.
[UHJ20) Masatoshi Uehara, Jiawei Huang, and Nan Jiang. Minimax weight and q-function learning for off- policy evaluation. In International Conference Machine Learning. pages 9659-9999669 PMLR, 2020.
[UI]+21] Masatoshi Uehara, Masaaki Imaizumi, Nan Jiang, Nathan Kallus, Wen Sun, and Tengyang Xie. Finite sample analysis of minimax offline reinforcement learning: Completeness, fast rates and first-order efficiency. arXiv preprint arXiv:2102.02981 2021.
[US21] Masatoshi Uehara and Wen Sun. Pessimistic model-based offline reinforcement learning under partial coverage. arXiv preprint arXiv:2107.06222 2021.
[USL+22] Masatoshi Uchara, Ayush Sekhari, Jason D Lee, Nathan Kallus, and Wen Sun. Provably efficient reinforcement learning in partially observable dynamical systems. arXiv preprint arXiv:2206. /2020, 2022.
[VHGS16] Hado Van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double q-learning. Proceedings of the AAAI conference on artificial intelligence, volume 30, 2016.
IVSH 16] Arun Venkatraman, Wen Sun, Martial Hebert, Bagnell, and Byron Boots. Online instrumental variable regression with applications to online linear system identifica- tion. In Proceedings of the AAAI Conference Artificial Intelligence, volume 30, 2016.
[WYW20] Lingxiao Wang, Zhuoran Yang. and Zhaoran Wang. Provably efficient causal reinforcement learning with confounded observational data. arXiv preprint arXiv:2006. 12311, 2020.
[XC Tengyang Xie, Ching-An Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal. Bellman-consistent pessimism for offline reinforcement learning. Advances in neural information processing systems, 34, 2021.
[XISSS20] Zekun Xu, Eric Laber, Ana-Maria Staicu, and Emanuel Severus. Latent-state models for precision medicine. arXiv preprint arXiv:2005. 13001, 2020.
[2] Yang Xu, Jin Zhu, Chengehun Shi, Shikai Luo, and Rui Song. An instrumental vari- able approach to confounded off- off-policy evaluation. arXiv preprint arXh::2212.14463 2022.
[ZB16] Junzhe Zhang and Elias Bareinboim. Markov decision processes with unobserved confounders: A causal approach. Technical report, Technical Report R-23, Purdue AI Lab, 2016.
[ZLKB20] Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Learning near optimal policies with low inherent bellman eтror. In International Conference on Machine Learning, pages 10978-10989. PMLR, 2020.
[ZUSL22] Wenhao Zhan, Masatoshi Uehara, Wen Sun, and Jason D Lee. Pac reinforcement learning for predictive state representations. arXiv preprinl arXiv:2207.057335 2022.
[ZW22] Andrea Zanette and Martin Wainwright. Bellman residual orthogonalization for offline reinforcement learning. arXiv preprint arXiv:2203.12786 2022.
[ZWB21] Andrea Zanette, Martin J Wainwright, and Emma Brunskill. Provable benefits of actor-critic methods for offline reinforcement learning. Advances in neural information processing systems, 34, 2021.
17

---

[2X Han Zhong, Wei Xiong. Sirui Zheng, Liwei Wang, Zhaoran Wang, Zhuoran Yang, and Tong Zhang. A posterior sampling framework for interactive decision making. arXiv preprint arXiv:22 1.001166,, 2022.
18


Reviews:
[{"review_id": "GDFKRTGfoG", "reviewer": "Reviewer_W56S", "summary": "The paper proposes a new OPE method for in POMDPs. The paper first introduces a new future-dependent value function and derive a new Bellman equation for the future-dependent value functions. Then, the paper proposes an estimator to learn such future-dependent value function. The paper provides theoretical results on the finite sample guarantee and a simple empirical demonstration that the estimator performs well in a partial observable Cartpole environment. ", "questions": "I would appreciate it if the authors can answer my questions listed in the weakness section, especially on the curse of horizon. ", "limitations": "The authors adequately addressed the limitations. They provide many extension of the proposed method in different settings in the appendix (e.g. for finite horizon). ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "The paper introduces a new estimator for POMDPs, which is claimed to be the first model-free method that enable general function approximation and does not suffer from the curse of horizon. I think the paper would have a significant contribution to the OPE community. \n(Note that I am not familiar with the literature on OPE for POMDPs, so my evaluation is sorely based on the related work section in the paper). \n\nThe future dependent idea is new, as far as I know. The paper also sufficiently discuss related works on OPE for POMDPs and the corresponding minimax estimator for fully observable MDPs. It is also good that the paper provides many examples on when the conditions hold in different settings such as tabular setting, and the connection between these conditions to conditions in existing works. \n\nI didn’t check the proof in the appendix carefully, but the theoretical results are reasonable. ", "weaknesses": "I think one weakness of the paper is the presentation clarity. It introduce many notation so it requires careful reading at first. I understand that these notations are necessary but I think some improvement can be made to make the paper easier to read.  Some steps/derivations are not very clear to me:\n- Are all expectation in the paper, when not explicitly specified, taken with respect to the offline data sampled from the data collection policy $\\pi_b$?\n- The expectation in definition 1 is taken w.r.t. the data from the data collection policy? What is the intuition behind the definition? If we can sample history from the data collection policy, there exists some function that can map the history to the true return? \n- In Line 218, “note that right hand side of Eq. 3 is a function of Z,S instead of H”. What is Z here?\n- The paper is about OPE for short-memory policies, but the main text only describes methods for memory-less policies (for simplicity). I think the paper can still  briefly summarizing what is different for short-memory policies. Does the length of the memory affect the finite sample bounds?\n- The paper mentions that it addresses the curse of horizon, however, isn't this because (1) we only consider short-memory policies and (2) assume future F contains sufficient information about S? \n\nIn the experiment, the base policy (I guess it is the data collection policy?) is defined on (S,A) but I think the method requires $\\pi_b(A|O)$. Did I misunderstand something here? \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your incisive comments. We will review the draft again, and improve the clariy. \n\n\n**Are all expectations in the paper, when not explicitly specified, taken with respect to the offline data sampled from the data collection policy?**\n\nYes. We will make it more explicit and reiterate relevant equations.\n\n\n**The expectation in definition 1 is taken w.r.t. the data from the data collection policy?** \n\nYes. \n\n**Intuition behind the definition 1? Why don't we use the histories?** \n\nThis is an excellent comment! We first explain the intuition. The intuition is to embed the original value functions, defined on the latent states, into ones that take multi-step futures as inputs. This allows us to derive a new Bellman equation for these future-dependent value functions. \n\nNext, we discuss why we chose to use multi-step futures instead of multi-step histories. The reason behind this choice is that if we were to use multi-step histories as inputs instead of multi-step futures, it remains unclear how to estimate such new value functions. Specifically, the Bellman equation might not hold if we replace the latent state with the multi-step histories. \n\n\n**In Line 218, “note that right hand side of Eq. 3 is a function of Z,S instead of H”. What is Z here?**\n\nThank you for catching the typo. It should just say \"of S\". We will fix it accordingly.\n\n\n**I think the paper can still briefly summarizing what is different for short-memory policies. Does the length of the memory affect the finite sample bounds?** \n\nThis is another excellent comment! To save space, we discussed the evaluation of short-memory policies in Section C. Following your suggestion, we will provide a summary in the main text if our paper gets accepted. In particular, The length of memory indeed affects the bound, and this would be reflected in $\\log |\\mathcal{Q}|$, as the input of the future-dependent value function depends on the length of the memory. Without inductive bias, in the worst case, this error could grow exponentially fast with respect to the length of memory. Notice that this differs from the curse of horizon suffered by naive methods such as SIS. The curse of horizon exists even when the evaluation policy is memoryless.\n\n**The paper mentions that it addresses the curse of horizon, however, isn't this because (1) we only consider short-memory policies and (2) assume future F contains sufficient information about S?**\n\nYes, you are right. Both are our primary assumptions. Indeed, without any assumption, it is unclear how to break the curse of horizon. Many papers formally proved that the curse of horizon is unavoidable without any assumptions in POMDPs [see e.g., JKKL20]. \n\nWe believe that our assumptions are reasonable for the purpose of overcoming the curse of horizon. Specifically, short-memory policies are widely used in practice to handle non-Markov environments, as mentioned in the introduction (E.g., in DQN in the Atari [MKS+ 13], the length is $4$). Additionally, similar assumptions regarding the future are widely imposed in the POMDP literature; see e.g., [JKKL20, NJ21, SUHJ22].\n\n\n**In the experiment, the base policy (I guess it is the data collection policy?) is defined on (S,A) but I think the method requires ... Did I misunderstand something here?**\n\nApologize for the confusion. This is a typo. In line 344, $(S,A)$ should be $(O,A)$. We will fix it accordingly. Thanks for catching it.\n"}, {"review_id": "TTdnST3AE2", "reviewer": "Reviewer_489Z", "summary": "The paper addresses the problem of off-policy evaluation in POMDPs. The main idea is to modify the Bellman equation by incorporating future and historical observations instead of relying on unobserved states. This new future-dependent value function allows for policy evaluation without the need for unobserved states. The paper explores the sufficient conditions and conducts finite sample analysis based on the modified Bellman equation. The proposed algorithm is demonstrated through a numerical experiment on CartPole, showing improved prediction error.", "questions": "Questions:\n1. The definition of $\\mathcal{F}$ for future observations is not consistent. In the equation after line 135 (also Figure 1), $F$ consists of $M_F$ observations and $M_F-1$ actions. However, in lines 142-147, $F$ consists of $M_F$ observations and $M_F$ actions. Which one is actually used in the experiment?\n2. (Question regarding the experiment, after reviewing Appendix H.3)\n\nSuggestions and Typos\n1. Typo: In the equation after line 135, $(O_{-M_H:t-1}, A_{-M_H:t-1})$ should be $(O_{t-M_H:t-1}, A_{t-M_H:t-1})$.\n2. Typo: In line 199, remove \"heir proposal.\"\n3. It would be interesting for practitioners to observe the prediction error as $M_F$ and $M_H$ vary. Exploring the trade-off between more accurate prediction through increased history/future observations and the complexity of the function space would be an intriguing avenue for future research.\n4. An extension to attention-based neural networks as the function space would be extremely interesting.", "limitations": "n/a", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Motivation and clarity:\n- The paper acknowledges the common occurrence of partial observability in real-world scenarios and the challenges it poses for off-policy evaluation, making it a relevant and long-standing research problem.\n- The paper is well-written and easy to follow.\n\nNovelty:\n- The proposed methods are clever and remarkably simple.\n- The discussion on the conditions for observability and invertibility provides theoretical insights into the occurrence of \"magic\" (evaluation without observing unobserved states). The entire reasoning process almost feels like a result from a standard RL textbook.", "weaknesses": "My only concern is the practicality of the proposed algorithm. The experimental results are not sufficiently convincing, and conducting more extensive studies, including (1) more baselines and (2) more complex environments, particularly real-world POMDP applications, would greatly enhance the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**My only concern is the practicality of the proposed algorithm. The experimental results are not sufficiently convincing, and conducting more extensive studies, including (1) more baselines and (2) more complex environments, particularly real-world POMDP applications, would greatly enhance the paper.** \n\n\nThank you for the suggestion. We will incorporate additional experiments to answer questions of practicality. Our primary contributions are theoretical-methodological, and we hope you agree the paper is acceptable in its current form given this focus. But we of course want to make the paper even stronger and can easily add more experiments to support our results. Regarding (1), we will add the standard baseline that simply tackles the problem as an MDP after augmenting states with short histories. Regarding (2), we will run our code the Mountain car and taxi environments. Both of these are straightforward to do using the code base that we submitted as supplementary materials.\n\n\n\n**The definition of F for future observations is not consistent**\n\nThank you for bringing this to our attention. Our proposal actually works in both cases: whether we have $M_F$ or $M_F-1$ actions. However, for consistency, we generally consider the case where future observations consist of $M_F$ observations and $M_F-1$ actions. We will fix lines 142-147 to be consistent with this choice, and we will mention explicitly in a remark that the alternative option of $M_F$ actions also works.\n\n**Possible extensions.**\n\nWe appreciate the reviewer's valuable suggestions. We agree that both extensions are indeed very interesting avenues for future research. We will certainly mention and explore these directions in the conclusion. Especially using attention mechanisms could potentially provide a very practical way to select relevant histories and future observations."}, {"review_id": "BtwkJiSw7W", "reviewer": "Reviewer_RwWH", "summary": "The paper considers off-policy evaluation for POMDPs, where the data is collected using a behavior policy that is only dependent on the observations available to the evaluation policy as well. The work defines a new \"future-dependent\" value function and its associated Bellman equations that are used to define a new set of conditional moment equations. While the existing estimators for this setting suffer from the curse of the horizon, the proposed method does not.  Overall, I think it is an interesting idea, though there are some points that can be clarified better.", "questions": "1. Staring at Definition 1, I am wondering if the importance-weighted return $\\rho G$ extracted from F, is a valid instance of $g_V(F)$? (I understand that propensity scores are not a part of $F$, but let's say data is augmented to make them part of $F$). \n\nComplimentarily, some discussion + examples around Definition 1 about the existence of $g_V(F)$ would also be fruitful. Line 211 kind of gets at it, but wraps it up in technical jargon.\n\n2. If yes, it is not intuitive to me why would the proposed method break the curse of the horizon. \n\nEven if the answer to the above is no, I am wondering if there is a price being paid in terms of the \"curse of the future\", i.e., the length of $F$? As mentioned in remark 4, if address the problem at hand can be addressed by substituting states with the history observed so far (although $\\mu$ would only depend on the current observation under the assumptions made earlier around Eqn 3 and 4.) and that is cursed by the length of the horizon, why wouldn't the proposed method be cursed by the length of the future?\n\n\n3. When multiple $g_V$ functions exist that satisfy the required condition, is there any reason to prefer one over the other? Can additional regularization be added to bias the solution towards one of them?\n\n4. Optional:  In my opinion, section 4 does not contribute much as once the conditional moment equations are obtained, the rest is a standard adaption of existing techniques.  I think it would be far more beneficial to a reader to have more discussion + positive/negative examples about the conditions for invertibility and existence, and what they imply in practice.\n", "limitations": "4. It would be beneficial to add another baseline, similar to naive minimax OPE, albeit with history as the state (with hyper-parameter tuning done similarly to the proposed method to choose the ideal history length).\n\nMinor:\n\n- Sentence phrasing in Line 129 suggests a model-based approach, whereas the main method is model-free\n- Eqn after Line 135 has a typo in subscripts.\n- Line 199: typo", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- Interesting idea of using future-dependent value functions. Though some prior works have touch upon similar ideas, the proposal is different enough.\n\n- OPE in POMDP is a common topic of interest and might be relevant to a lot of people.", "weaknesses": "- More discussions about Assumptions could be helpful\n\n- Experiments can be improved", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Staring at Definition 1, I am wondering if the importance-weighted return $\\rho G$ extracted from $F$, is a valid instance of $g_{V}(F)$?**\n\nYou are right: this would work if $F$ were the infinite future including _all_ future observations, actions, and rewards. Then, this choice of $g_{V}(F)$ essentially leads to sequential importance sampling (SIS), which suffers the curse of horizon due to the size of importance weights $\\rho$. To mitigate this, it becomes essential to use short futures with finite $M_F$ as we do. We will emphasize this point and the interesting connection to SIS.\n\n**Some discussion + examples around Definition 1 about the existence of $g_V(F)$ would also be fruitful. Line 211 kind of gets at it, but wraps it up in technical jargon.**\n\nThanks for the great suggestion. We will add discussion right after Definition 1, explaining existence is a question of existence of a solution to an integral equation and give the example of discrete variables where it can easily be stated as a solution to a system of linear equations (where we do not need Picard's theorem).\n\n**If yes, it is not intuitive to me why would the proposed method break the curse of the horizon... why wouldn't the proposed method be cursed by the length of the future?**\n \nYour observation is indeed astute. When employing multi-step futures, without a specific inductive bias (e.g., linear or smooth), the error could potentially grow exponentially in the number of future proxies used. For instance, in the tabular case, $\\log |\\Omega|$ might scale with $|O|^{M_F}$ when considering $\\Omega$ as the set of all functions on $|O|^{M_F}$. However, this scenario is notably different from the curse of horizon, which is a challenge that naive methods (such as replacing states with the entire history) face. Whereas such methods would suffer the length of the history that is needed to induce Markovianity (in general, the _whole_ history), we would only suffer the length $M_F$ of the future that is needed to establish the conditions of Theorem 1 (existence and invertibility) which can require much shorter length. We give specific examples throughout the paper. Example 1 in the main text discusses the tabular setting, showing we essentially need as many futures as the state, as long as there is sufficient statistical dependence between them. In Appendix D.2 we give the example of HSE-POMDPs and LQGs and show how they satisfy these conditions. We will add this discussion and make clearer in what ways do in fact break the curse of horizon.\n\nTo summarize:\n\n* The curse of horizon is unavoidable in naive methods, as you mentioned, where the state is replaced with the entire history in POMDPs. While using a short history instead of the whole history may be an option, it either requires a high-order Markov assumption or it may not provide any guarantees. In contrast, in our proposal, by choosing the length $M_F$ appropriately, we can ensure statistical guarantees for any horizon, provided the futures satisfy our proxy conditions.\n\n* The length of $M_F$ may indeed be relatively short in order to satisfy our conditions. For instance, in the tabular case, our assumption aligns with those made in several POMDP papers [ZUSL22, NJ21, SUHJ22], as mentioned in Line 234 and Line 235. Since these papers also encounter errors that grow exponentially with the length of future-proxies, they too implicitly assume a short length for future-proxies\n\n* The curse of horizon is inevitable without any assumptions, as demonstrated in [JKKL20]. To address this challenge, we propose new methods based on three assumptions: (a) (short) future observations serve as proxies for latent states, (b) histories serve as proxies for latent states, and (c) the length of the memory is short. We consider these assumptions to be interpretable and reasonable.\n\n**When multiple $g_V$ functions exist that satisfy the required condition, is there any reason to prefer one over the other? Can additional regularization be added to bias the solution towards one of them?**\n\nThank you for the excellent question. We will add a discussion of this. In the present paper, we focus on estimation with finite-sample bounds, for which any $b_V$ would do. (Note $b_V$ are the value functions we learn, while $g_V$ are fundamentally unlearnable.) Any $b_V$ satisfying $(\\mathcal Tb_V)(H)=0$ is sufficient for identification. And, in our estimation, we only establish guarantees on $\\mathbb E[(\\mathcal T\\hat b_V)^2(H)]$ in Theorem 2, which suffice to establish bounds for evaluation in Theorem 3. This can be interpreted as bounds on the projected distance $\\mathbb E[\\mathcal T(\\hat b_V-b_V)^2(H)]$, which is the _same_ no matter _which_ $b_V$ we choose.\n\nA future direction may be to consider inference based on asymptotic normality. To address that goal, it may be essential to include explicit regularization, such as Tikhonov regularization, as has been done in a different but related setting: \n\n*Bennett, Andrew, Nathan Kallus, Xiaojie Mao, Whitney Newey, Vasilis Syrgkanis, and Masatoshi Uehara. \"Source Condition Double Robust Inference on Functionals of Inverse Problems.\" arXiv preprint arXiv:2307.13793 (2023).*\n\n**Optional: In my opinion, section 4 does not contribute much as once the conditional moment equations are obtained, the rest is a standard adaption of existing techniques. I think it would be far more beneficial to a reader to have more discussion + positive/negative examples about the conditions for invertibility and existence, and what they imply in practice.**\n\nWe understand that an expert reader, such as yourself, may find it easy to derive the equations in Section 4 after reading Section 3. However, we also acknowledge that for many readers, this part may not be so trivial. Therefore, we think it best to retain it. Nevertheless, we agree with you that we should provide more discussion on invertibility and existence, and we will incorporate these discussions, as detailed above.\n"}, {"review_id": "WHVjktkEQ8", "reviewer": "Reviewer_MVwZ", "summary": "The paper introduces a novel model-free approach for off-policy evaluation (OPE) in partially observable Markov decision processes (POMDPs). The authors propose the use of future-dependent value functions (FDVFs) to capture the latent states by leveraging future observations. They provide a Bellman-like equation and a minimax algorithm for FDVFs, along with a PAC analysis.", "questions": "In Remark 3, \"heir proposal\" seems to be a typo; could you please clarify?\n\nInstead of SIS, could SIS with resampling (a.k.a. SIR, SIS/R, SMC, particle filtering) be utilized instead?", "limitations": "No", "rating": 3, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "+ The paper addresses a crucial challenge of handling real-world data that are partially observable and difficult to collect. \n\n+ The proofs seem to be correct. ", "weaknesses": "- The readability of the paper can be enhanced, particularly by providing a more intuitive motivation and explanation of FDVFs. The paper is densely written with numerous references to other sections and papers, which disrupts the flow. It is important to clearly state the main assumptions, problem, and overall approach in an intuitive manner.\n\n- The main weakness of the paper is the experiments section, which only considers a simple environment (CartPole) with partial observability achieved by adding Gaussian noise. \n\n- Additionally, the proposed method utilizes a limited history (3-step) and one-step future, which may not sufficiently demonstrate its effectiveness in mitigating the curse of horizon. \n\n- Furthermore, it is important to compare the proposed method with other OPE methods designed for POMDPs, as well as those using stacked observations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### Rebuttal for the Weakness \n\n**The readability of the paper can be enhanced, particularly by providing a more intuitive motivation and explanation of FDVFs.....** \n\nThank you for your suggestion. The primary motivation is FDVFs give embeddings of the latent states such that the expectation is the same as that of the latent-state value function, enabling OPE, as discussed in lines 172-174. To further help the reader we will move discussion of existence of FDVFs and examples from later in the text to be next to the definition.\n\n**The main weakness of the paper is the experiments section, which only considers a simple environment (CartPole) with partial observability achieved by adding Gaussian noise.**\n\nThe offline policy evaluation problem is notoriously challenging, even in MDPs. It can be even more difficult than offline policy learning in the sense that we can still learn good policies without precise policy value estimation. Due to this difficulty, many representative papers focusing on offline policy evaluation use simple environments such as Cartpole, as exemplified in [TB16] and the following papers:\n\nFarajtabar, Mehrdad, Yinlam Chow, and Mohammad Ghavamzadeh. \"More robust doubly robust off-policy evaluation.\" International Conference on Machine Learning. PMLR, 2018.\n\nShi, Chengchun, Runzhe Wan, Victor Chernozhukov, and Rui Song. \"Deeply-debiased off-policy interval estimation.\" In International conference on machine learning, pp. 9580-9591. PMLR, 2021.\n\nIn our setting, we even consider POMDPs, which are even more challenging than MDPs. Therefore, we believe that Cartpole is a reasonably challenging environment for our paper, and it is not considered a toy environment for our task of offline policy evaluation in POMDPs, especially as our primary contributions are theoretical-methodological. But we of course want to make the paper even stronger and can easily add more experiments to support our results. We will therefore run our code also the Mountain car and taxi environments. Both of these are straightforward to do using the code base that we submitted as supplementary materials.\n\n**Additionally, the proposed method utilizes a limited history (3-step) and one-step future, which may not sufficiently demonstrate its effectiveness in mitigating the curse of horizon.**\n\nOur methods are designed to be flexible, allowing for varying numbers of history and future steps. We have included ablation studies to demonstrate the effects of changing these parameters in Appendix. We are confident that our approach effectively addresses the curse of horizon under interpretable and reasonable assumptions. Notably, our work stands as the sole work in the realm of OPE in POMDPs with a theoretical guarantee, which can avoid the curse of horizon. \n\nYou might be interested in our choice of a 3-step history and a 1-step future. In the future, we plan to explore attention-based methods to determine which histories and futures we should select. If you require further clarification on specific concerns, we are more than willing to provide additional details.\n\n**Furthermore, it is important to compare the proposed method with other OPE methods designed for POMDPs, as well as those using stacked observations.**\n\nTo the best of our knowledge, existing OPE methods for POMDPs in the non-tabular setting with statistical guarantees are limited to SIS. Therefore, we believe our comparison is reasonable. But there are indeed some practical heuristics we can compare to. We will therefore add the standard baseline that simply tackles the problem as an MDP after augmenting states with short histories, which we believe is what you are referring to. Since this will necessarily be biased it will not converge. Nonetheless we agree that plotting it will provide an illustration of the importance of statistical convergence guarantees.\n\n### Rebuttal for the Questions \n\n**In Remark 3, \"heir proposal\" seems to be a typo; could you please clarify?**\n\nMany thanks for catching it! It will be corrected if our paper gets accepted. \n\n**Instead of SIS, could SIS with resampling (a.k.a. SIR, SIS/R, SMC, particle filtering) be utilized instead?**\n\nWe acknowledge that in the literature of importance sampling, resampling is commonly used. However, in OPE, we specifically focus on scenarios where data is generated by certain policies, and we do not have control over the data-generating process. Consequently, implementing resampling in such cases may not be feasible. Nevertheless, we agree that the idea of resampling may be useful in the online setting, where control over the data-generating process is available. We will point to this possible direction as an avenue for future work on online learning in POMDPs in our conclusion."}, {"review_id": "g0GD7DpzFX", "reviewer": "Reviewer_4aE2", "summary": "- This paper proposes a novel future-dependent value function to study the problem of OPE in POMDPs with function approximations. \n- A new Bellman-style conditional moment equation is derived for the future-dependent value function, based on which the value function can be learned via finite sample using minimax learning methods. \n- Under certain completeness, realizability, and overlapping assumptions, a finite sample theoretical bound is derived for the proposed minimax learning algorithm. The paper also provides experimental evidence to empirically evaluate the performance of the algorithm.\n", "questions": "- Regarding the completeness assumption (2b), how can it be justified in the examples provided in the paper, e.g., HSE-POMDPs? I would appreciate it if the authors could provide more detailed clarifications on that.\n- A novelty of the paper is using both history and future proxies in POMDP OPE. Is it possible to give a more quantitative trade-off between the usage of the history part and the future part (probably problem-dependent) towards optimal identifying and evaluating the policy value? \n- Another seemingly key assumption in the presentation of the paper is that the offline data from an infinite horizon POMDP has a stationary distribution. Even mentioned in the main texts, I still wondering if the algorithm and theory can be directly extended to the more general non-stationary settings.", "limitations": "The above points in Questions are potential limitations.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The paper first proposes using \"future-dependent value function\" to solve the problem of OPE in POMDPs, which is a critical problem in offline RL literature. The resulting method potentially overcomes the curse of horizon in learning POMDPs.\n- The presentation of the paper is clear, e.g., using memory-less policy to illustrate the idea in the main text. The connections with highly related works, e.g., OPE in MDPs, OPE in confounded POMDPs, system dynamics learning, spectral learning, are well-discussed.\n- The statistical theory regarding minimax learning and OPE is sound, and empirical evaluations are also provided.", "weaknesses": "- The idea of incorporating future information as parts of value functions for POMDPs is not new, e.g., [1], even though I still appreciate that this paper first attempts using such methods for OPE in POMDPs.\n- The main part of the statistical theory regarding minimax estimation and OPE is standard given that various customized assumptions (completeness, realizability, and certain overlapping conditions) hold.\n\n**References:**\n[1] Uehara M, Sekhari A, Lee J D, et al. Provably efficient reinforcement learning in partially observable dynamical systems[J]. Advances in Neural Information Processing Systems, 2022, 35: 578-592.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Regarding the completeness assumption (2b), how can it be justified in the examples provided in the paper, e.g., HSE-POMDPs? I would appreciate it if the authors could provide more detailed clarifications on that.**\n\nThank you for the question. Lemma 5 in Appendix D.2 establishes conditions for completeness under HSE-POMDPs. We will better advertise this result by remarking on it in the main text.\n\n**A novelty of the paper is using both history and future proxies in POMDP OPE. Is it possible to give a more quantitative trade-off between the usage of the history part and the future part (probably problem-dependent) towards optimal identifying and evaluating the policy value?**\n\nThank you for bringing up this important point. As mentioned at the end of Page 8, we acknowledge the existence of a tradeoff, but at this stage, we do not have a concrete method to quantitatively characterize it. We will mention this as an important avenue for future work in our conclusion.\n\n**Another seemingly key assumption in the presentation of the paper is that the offline data from an infinite horizon POMDP has a stationary distribution. Even mentioned in the main texts, I still wondering if the algorithm and theory can be directly extended to the more general non-stationary settings.**\n\nWe indeed assume that behavior policies are stationary, which is standard in the literature on POMDPs. However, the underlying distributions over latent states $S$ can be non-stationary. More specifically, from a methodological standpoint, it is possible to apply our methods even when the underlying state distributions are non-stationary. In such cases, adjustments to our current theoretical framework (Section 5) would be necessary. We believe that this could be achieved, for instance, by introducing mixing assumptions, as Shi et.al has done in the context of MDPs. We will mention this and explain the idea, but may not have the space to fully develop this direction in this paper.\n\n*Shi, C., Zhang, S., Lu, W., & Song, R. (2022). Statistical inference of the value function for reinforcement learning in infinite-horizon settings. Journal of the Royal Statistical Society Series B: Statistical Methodology, 84(3), 765-793.*\n\nAdditionally, we want to highlight that our proposed approach can be readily extended to the finite horizon setting, and the details of this extension are given in Appendix E.\n"}]

Author rebuttal:

Meta-review: The paper addresses off-policy evaluation in POMDPs and introduces a novel future-dependent value function. Instead of relying on unobserved states, this approach modifies the Bellman equation to incorporate both future and historical observations. The paper derives new Bellman and conditional moment equations and proposes an estimator that circumvents the curse of the horizon issue faced by existing methods. Theoretical results on the finite sample guarantee are presented. This paper is highly impactful for the community it is addressing. Overall a very solid submission, a clear accept.
Decision: Accept (spotlight)