On the Curses of Future and History in Future-dependent Value Functions for Off-policy Evaluation

Authors: yuheng  zhang
nan  jiang
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 07:09:19

Abstract: We study off-policy evaluation (OPE) in partially observable environments with complex observations, with the goal of developing estimators whose guarantee avoids exponential dependence on the horizon. While such estimators exist for MDPs and POMDPs can be converted to history-based MDPs, their estimation errors depend on the state-density ratio for MDPs which becomes history ratios after  conversion, an exponential object. Recently, Uehara et al. [2022a] proposed future-dependent value functions as a promising framework to address this issue, where the guarantee for memoryless policies depends on the density ratio over the latent state space. However, it also depends on the boundedness of the future-dependent value function and other related quantities, which we show could be exponential-in-length and thus erasing the advantage of the method. In this paper, we discover novel coverage assumptions tailored to the structure of POMDPs, such as outcome coverage and belief coverage, which enable polynomial bounds on the aforementioned quantities. As a side product, our analyses also lead to the discovery of new algorithms with complementary properties.

Main paper: 
 introduction and related works: 
 Off-policy evaluation (OPE) is the problem of estimating the return of a new evaluation policy π e based on historical data, which is typically collected using a different policy π b (the behavior policy). OPE plays a central role in the pipeline of offline reinforcement learning (RL), but is also notoriously difficult. Among the major approaches, importance sampling (IS) and its variants Precup et al. [2000] , Jiang and Li [2016] provide unbiased and/or asymptotically correct estimation using the cumulative importance weights: given a trajectory of observations and actions o 1 , a 1 , o 2 , a 2 , . . . , o H , a H , the cumulative importance weight is H h=1 πe(a h |o h ) π b (a h |o h ) , whose variance grows exponentially with the horizon, unless π b and π e are very close in their action distributions. In the language of offline RL theory [Chen and Jiang, 2019 , Xie and Jiang, 2021 , Yin and Wang, 2021] , the boundedness of the cumulative importance weights is the coverage assumption required by IS, a very stringent one.Alternatively, algorithms such as Fitted-Q Evaluation [FQE; Ernst et al., 2005 , Munos and Szepesvári, 2008 , Le et al., 2019] and Marginalized Importance Sampling [MIS; Liu et al., 2018 , Xie et al., 2019 , Nachum et al., 2019 , Uehara et al., 2020] enjoy more favorable coverage assumptions, at the cost of function-approximation biases. Instead of requiring bounded cumulative importance weights, FQE and MIS only require that of the state-density ratios, which can be substantially smaller [Chen and Jiang, 2019, Xie and Jiang, 2021] . That is, when the environment satisfies the Markov assumption (namely o h is a state), the guarantees of FQE and MIS only depend on the range of d πe h (o h )/d π b h (o h ), where d πe h and d π b h is the marginal distribution of o h under π e and π b , respectively. In this paper, we study the non-Markov setting, which is ubiquitous in real-world applications. Such environments are typically modeled as Partially Observable Markov Decision Processes (POMDPs) Kaelbling et al. [1998] . Despite the more general formulation, one can reduce a POMDP to an MDP, making algorithms for MDPs applicable: we can simply define an equivalent MDP, with its state being the history of the original POMDP, (o 1 , a 1 , . . . , o h ). Unfortunately, a close inspection reveals the problem: the state-density ratio after conversion isd πe h (o 1 , a 1 , . . . , o h ) d π b h (o 1 , a 1 , . . . , o h ) = h-1 h ′ =1 π e (a h ′ |o h ′ ) π b (a h ′ |o h ′ ) ,which is exactly the cumulative importance weights in IS and thus also an exponential object!To address this issue, Uehara et al. [2022a] recently proposed a promising framework called futuredependent value functions (or FDVF for short). Notably, their coverage assumption is the boundedness of density ratios between π e and π b over the latent state for memoryless policies. This is as if we were dealing directly with the latent MDP underlying the POMDP, a perhaps best possible scenario.Nevertheless, have we achieved exponential-free OPE in POMDPs?The answer to this question turns out to be nontrivial. In addition to the latent-state coverage parameter, the guarantee in Uehara et al. [2022a] also depends on other quantities that are less interpretable. Among them, the boundedness of FDVF itself-a concept central to this framework-is unclear, and we show that a natural construction yields an upper bound that still scales with the cumulative importance weights, thus possibly erasing the superiority of the framework over IS or MDP-reduction.In this work, we address these caveats by proposing novel coverage assumptions tailored to the structure of POMDPs, under which fully polynomial estimation guarantees can be established. More concretely, our contributions are:1. For FDVFs, we show that a novel coverage concept called outcome coverage is sufficient for guaranteeing its boundedness (Section 4). Notably, outcome coverage concerns the overlap between π b and π e from the current time step onward, whereas all MDP coverage assumptions concern that before the current step. 2. With another novel concept called belief coverage (Section 5.1), we establish fully polynomial estimation guarantee for the algorithm in Uehara et al. [2022a] . The discovery of belief coverage also leads to a novel algorithm (Section 5.3) that is analogous to MIS for MDPs. 3. Despite the similarity to linear MDP coverage [Duan et al., 2020] due to the linear-algebraic structure, these POMDP coverage conditions also have their own unique properties due to the L 1 normalization of belief and outcome vectors. We present improved analyses that leverage such properties and avoid explicit dependence on the size of the latent state space (Section 4.2).2 Preliminaries POMDP Setup. We consider a finite-horizon POMDP H, S = is the initial latent state distribution. For mathematical convenience we assume all the spaces are finite and discrete, but the cardinality of O h , O, can be arbitrarily large. A trajectory (or episode) is sampled ass 1 ∼ d 1 , then o h ∼ O(•|s h ), r h = R(o h , a h ), s h+1 ∼ T(•|s h , a h ) for 1 ≤ h ≤ H,with a 1:H decided by the decision-making agent, and the episode terminates after a H . s 1:H are latent and not observable to the agent.History-future Split.Given an episode o 1 , a 1 , . . . , o H , a H and a time step h of interest, it will be convenient to rewrite the episode as(τ h , f h o h , a h , f h+1 ).Here τ h = (o 1 , a 1 , . . . o h-1 , a h-1 ) ∈ H h := h-1 h ′ =1 (O h × A) denotes the historical observationaction sequence (or simply history) prior to step h, and f h+1 = (o h+1 , a h+1 , . . . , o H , a H ) ∈ F h+1 := H h ′ =h+1 (O h ′ × A) denotes the future after step h. This format will be convenient for reasoning about the system dynamics at step h. We use H = H h=1 H h to denote the entire history domain and use F = H h=1 F h to denote the entire future domain. This way we can use stationary notation for functions over S, O, H, F, where the time step can be identified from the function input (e.g., R(o h , a h )), and functions with time-step subscripts refer to their restriction to the h-th step input space, often treated as a vector (e.g., R h ∈ R O h ×A ).Memoryless and History-dependent Policies. A policy π : H h=1 (H h × O h ) → ∆(A) specifies the action probability conditioned on the past observation-action sequence. 1 In the main text, we will restrict ourselves to memory-less (or reactive) policies that only depends on the current observation o h ; extension to general policies is similar to Uehara et al. [2022a] and discussed in Appendix B.6. For any π, we use Pr π and E π for the probabilities and expectations under episodes generated by π, and define J(π) as the expected cumulative return:J(π) := E π H h=1 R(o h , a h ) .For memoryless π, we also define V π S (s h ) as the latent state value function ats h : V π S (s h ) := E π H h ′ =h R(o h ′ , a h ′ ) | s h ∈ [0, H]. d π (s h ) denotes the marginal distribution of s h under π.Off-policy Evaluation. In OPE, the goal is to estimate J(π e ) using n data trajectories D = {(o(i) 1 , a (i) 1 , r (i) 1 , . . . , o (i) H , a (i) H , r (i) H ) : i ∈ [n]} collected using π b . We write E D [•]to denote empirical approximation of expectation using D. Define the one-step action probability ratio µ(o h , a h ) := πe(a h |o h ) π b (a h |o h ) . We make the following assumption throughout: Assumption 1 (Action coverage). We assumeπ b (a h |o h ) is known and max h,o h ,a h µ(o h , a h ) ≤ C µ .This is a standard assumption in the OPE literature, and is needed by IS and value-based estimators that model state value functions [Jiang and Li, 2016, Liu et al., 2018] .Belief and Outcome Matrices. We now introduce two matrices of central importance to our discussions. Given history τ h , we define b(τ h ) ∈ R S as its belief state vector where b i (τ h ) = Pr(s h = i|τ h ). Then the belief matrix M H,h ∈ R S×H h is one where the column indexed by τ h ∈ H h is b(τ h ). Similarly, for future f h , we define u(f h ) ∈ R S as its outcome vector where[u(f h )] i = Pr π b (f h |s h = i). The outcome matrix M F ,h ∈ R S×F h isone where the column indexed by f h is u(f h ). Unlike the belief matrix, the outcome matrix M F ,h is dependent on the behavior policy π b , which is omitted in the notation.For mathematical conveniences, we make the following assumptions throughout merely for simplifying presentations; they allow us to invert certain covariance matrices and avoid 0/0 situations, which can be easily handled with extra care when the assumptions do not hold.Assumption 2 (Invertibility). ∀h ∈ [H], (1) rank(M H,h ) = rank(M F ,h ) = S. (2) ∀f h , Pr π b (f h ) > 0; ∀o h , a h , R(o h , a h ) > 0.Other Notation. Given a vector a, ∥a∥ Σ := √ a ⊤ Σa, where Σ is a positive semi-definite (PSD) matrix. When Σ = diag(d) for a stochastic vector d, this is the d-weighted 2-norm of a, which we also write as ∥a∥ 2,d . For a positive integer m, we use [m] to denote the set {1, 2, • • • , m}. For a matrix M , we use (M ) ij to denote the ij entry of M . 
future-dependent value functions: 
 In this section, we provide a recap of FDVFs and translate the main result of Uehara et al. [2022a] into the finite-horizon setting, which is mathematically cleaner and more natural in many aspects; see Appendix B.2 for further discussion.To illustrate the main idea behind FDVFs, recall that the tool that avoids the exponential weights in MDPs is to model the value functions. While we would like to apply the same idea to POMDPs, history-dependent value functions lead to unfavorable coverage conditions (see Section 1). The only other known notion of value functions we are left with is that over the latent state space, V πe S (s h ), which unfortunately is not accessible to the learner since it operates on unobservable latent states.The central idea is to find observable proxies of V πe S (s h ), which takes future as inputs: Definition 3 (Future-dependent value functions [Uehara et al., 2022a] ). A future-dependent value function V F : F → R, where F := h F h , is any function that satisfies the following:EQUATIONRecall our convention, that V F ,h ∈ R |F h | is V F restricted to F h , and V πe S,h is defined similarly.A FDVF V F is a property of π e , but also depends on π b . As we will see later in Section 4, the boundedness of V F will depend on certain notion of coverage of π b over π e . As another important property, the FDVF V F is generally not unique even if we fix π e and π b , as Eq.( 1) is generally an underdetermined linear system (S ≪ |F h |) and can yield many solutions. As we see below, it suffices to model any one of the solutions. Thus, from now on, when we talk about the boundedness of V F , we always consider the V F with the smallest range among all solutions.Finite Sample Learning. Like in MDPs, to learn an approximate FDVF from data, we will minimize some form of estimated Bellman residuals (or errors). For that we need to first introduce the Bellman residual operators for FDVFs: Definition 4 (Bellman residual operators). ∀V : F → R, the Bellman residual on state s h is:2 (B S V )(s h ) := E a h ∼πe a h+1:H ∼π b [r h + V (f h+1 ) | s h ] -E π b [V (f h ) | s h ].Similarly, the Bellman residual onto the history τ h is:EQUATIONThe following lemma shows that, ideally, we would want to find V with small B S V :Lemma 1. For any π e , π b , andV : F → R, J(π e ) -E π b [V (f 1 )] = H h=1 E πe (B S V )(s h ) .See proof in Appendix C.1. As the lemma shows, any V with small B S V (such as V F , sinceB S V F ≡ 0) can be used to estimate J(π e ) via E π b [V (f 1 )].But again, B S operates on S which is unobserved, and we turn to its proxy B H , which are linear measures of B S (Eq.2). More concretely, Uehara et al. [2022a] proposed to estimate E π b [(B H V ) 2 ] using an additional helper class Ξ : H → R to handle the double-sampling issue [Antos et al., 2008 , Dai et al., 2018] :EQUATIONwhereL h (V, ξ) = E D [{µ(a h , o h )(r h + V (f h+1 )) -V (f h )}ξ(τ h ) -0.5ξ 2 (τ h )].Under the following assumptions, the estimator enjoys a finite-sample guarantee:Assumption 5 (Realizability). Let V ⊂ (F → R) be a finite function class. Assume V F ∈ V for some V F satisfying Definition 3. Assumption 6 (Bellman completeness). Let Ξ ⊂ (H → R) be a finite function class. Assume B H V ∈ Ξ, ∀V ∈ V.Theorem 2. Under Assumptions 5 and 6, w.p. ≥ 1 -δ,|J(π e )-E D [ V (f 1 )]| ≤ cH max{C V + 1, C Ξ } • IV(V)Dr V [d πe , d π b ] C µ log |V||Ξ| δ n ,where c is an absolute constant,3 and CV := max V ∈V ∥V ∥ ∞ , C Ξ := max ξ∈Ξ ∥ξ∥ ∞ , IV(V) := max h sup V ∈V E π b [(B S V ) (s h ) 2 ] E π b [(B H V ) (τ h ) 2 ] , Dr V [d πe , d π b ] := max h sup V ∈V E πe [(B S V ) (s h ) 2 ] E π b [(B S V ) (s h ) 2 ].See proof in Appendix C.2. Among the objects that appear in the bound, some are mundane and expected (e.g., horizon H, the complexities of function classes log |V||Ξ|, etc.). We now focus on the important ones, which reveals the open questions we shall investigate next:1. Dr V [d πe , d π b ] measures the coverage of π b over π e on the latent state space S, as the expression inside square-root can be bounded by max s h d πe (s h )/d π b (s h ).2. (Q1) C V is the range of the V class. Since V F ∈ V (Assumption 5), C V ≥ ∥V F ∥ ∞ . However, unlike the standard value functions in MDPs which have obviously bounded range [0, H] (this also applies to V πe S ), the range of V F is unclear. Similarly, since Ξ needs to capture B H V for V ∈ V, the boundedness of Ξ is also affected.3. (Q2) IV(V) appears because we use B H V as a proxy for B S V , which is only a linear measure of the latter, ) reflects the conversion ratio between them. Uehara et al. [2022a] pointed out that the value is finite if M H,h has full-row rank (S), but a quantitative understanding is missing.(B H V )(τ h ) = ⟨b(τ h ), B S h V ⟩. IV(VThe rest of the paper proposes new coverage assumptions, analyses, and algorithms to answer the above questions, providing deeper understanding on the mathematical structure of OPE in POMDPs. 
boundedness of fdvfs: 
 We start with Q1: when are FDVFs bounded? Recall from Definition 3 that a FDVF at level h, V F ,h , is any function satisfying M F ,h × V F ,h = V πe S,h , where M F ,h is the outcome matrix with(M F ,h ) i,j = Pr π b (f h = j | s h = i).Since the equation can have many solutions and we only need to find one of them, it suffices to provide an explicit construction of a V F ,h and show it is well bounded. Also note that the equations for different h are independent of each other, so we can construct V F ,h for each h separately.We first describe two natural constructions, both of which yield exponentially large upper bounds.Importance Sampling Solution. Uehara et al. [2022a] provided a cruel bound on ∥V F ∥ ∞ which scales with 1/σ min (M F ,h ), which we show shortly is an exponential-in-length quantity. However, it is not hard to notice that in certain benign cases, V F does not have to blow-up exponentially and has obviously bounded constructions.As a warm-up, consider the on-policy case of π b = π e , where a natural solution isV F (f h ) = R + (f h ) := H h ′ =h R(o h ′ , a h ′ ). Here R + (f h ) simply adds up the Monte-Carlo rewards in future f h , which is bounded in [0, H]. The construction trivially satisfies E π b [V F (f h ) | s h ] = V πe S (s h ) when π b = π e .In the more general setting of π b ̸ = π e , the hope is that V F can be still bounded up to some coverage condition that measures how π e deviates from π b .Unfortunately, generalizing the above equation to the off-policy case raises issues: consider the solutionV F (f h ) = R + (f h ) • H h ′ =h πe(a h ′ |o h ′ ) π b (a h ′ |o h ′ ), whose correctness can be verified by importance sampling. Despite its validity, the construction involves cumulative action importance weights, which erases the superiority of the framework over IS as discussed in the introduction.Pseudo-inverse Solution. Another direction is to simply treat Eq.(1) as a linear system. Given that the system is under-determined, we can use pseudo-inverse:4 V F ,h = M ⊤ F ,h M F ,h M ⊤ F ,h -1V πe S,h . In this case, ∥V F ∥ ∞ can be bounded using 1/σ min (M F ,h ), where σ min denotes the smallest singular value. In fact, closely related quantities have appeared in the recent POMDP literature; for example, in the online setting, Liu et al. [2022a] used σ min of an action-conditioned variant of M F ,h as a complexity parameter for online exploration in POMDPs. Unfortunately, these quantities suffer from scaling issues: 1/σ min (M F ,h ) is guaranteed to be misbehaved if the process is sufficiently stochastic.EQUATION.In this example, C stoch measures how the distribution of f h under π b deviates multiplicatively from a uniform distribution over F h , and an even moderately stochastic π b and emission process O will lead to small C stoch , which implies an exponentially large 1/σ min (M F ,h ).Pseudo-inverse finds the minimum L 2 norm solution. However, given that we are searching for solutions in R F h which has an exponential dimensionality, the standard L 2 norm-which treats all coordinates equally-is not a particularly informative metric. Instead, we propose to minimize the weighted L 2 norm with a particular weighting scheme, which has also been used in HMMs [Mahajan et al., 2023] and enjoys benign properties.We first define the diagonal weight matrixZ h := diag(1 ⊤ S M F ,h ), where 1 S ∈ R S = [1, • • • , 1] ⊤is the all-one vector. Then, the solution that minimizes ∥ • ∥ Z h is:EQUATIONΣ F ,h ∈ R S×S plays an important role in this construction. Recall that its counterpart in the pseudoinverse solution, namely M F ,h M ⊤ F ,h , has scaling issues (Example 1), that even its largest eigenvalue can decay exponentially with H -h + 1. In contrast, Σ F ,h is very well-behaved in its magnitude, as shown below. Furthermore, while M ⊤ F ,h on the left is now multiplied by Z -1 h which can be exponentially large, Z -1 h M ⊤ F ,h together is still well-behaved; see proof in Appendix D.2. Proposition 3 (Properties of Eq.( 4)). 1. Σ F ,h is doubly-stochastic: that is, each row/column of Σ F ,h is non-negative and sums up to 1. As a consequence,σ max (Σ F ,h ) = 1. 2. Rows of Z -1 h M ⊤ F ,h , i.e., {u(f h ) ⊤ /Z(f h ) : f h ∈ F h },are stochastic vectors, i.e., they are non-negative and the row sum is 1.Therefore, it is promising to make the assumption that σ min (Σ F ,h ) is bounded away from zero, which immediately leads to the boundedness of V F given that of Z -1 h M ⊤ F ,h ([0, 1]) and V πe S ([0, H]). However, we need to rule out the possibility that Σ F ,h is always near-singular, and find natural examples that admit large σ min (Σ F ,h ), as given below. Example 2. Suppose f h always reveals s h , in the sense that for any j ∈ F h , Pr π b (f h = j | s h = i) is only non-zero for a single i ∈ [S], and zero for all other latent states. Then, Σ F ,h = I, the identity matrix. Furthermore, V F from Eq.(4) satisfies ∥V F ∥ ∞ ≤ H. See Appendix D.3 for details.The example shows an ideal case where σ min (Σ F ,h ) = σ max (Σ F ,h ) = 1, when the future fully determines s h . This can happen when the last observation o H reveals the identity of an earlier latent state s h . Note that in this case, M F ,h M ⊤ F ,h can still have poor scaling if the actions and observations between step h and H are sufficiently stochastic, which shows how the weighted 2-norm solution and analysis improve over the pseudo-inverse one. More generally, Σ F ,h is the confusion matrix of making posterior predictions of s h from f h based on a uniform prior over S h (see Appendix B.8 for how to incorporate different priors) with u(f h ) ⊤ /Z(f h ) being the posterior, and σ min (Σ F ,h ) serves as a measure of how the distribution of future f h helps reveal the latent state s h .We now break down the boundedness of Eq.( 4) into more interpretable assumptions.Assumption 7 (L 2 outcome coverage). Assume for all h, ∥V πe S,h ∥ 2 Σ -1 F ,h ≤ C F ,V .Assumption 8 (Σ F ,h regularity). Assume for anyf h : ∥u(f h )/Z(f h )∥ 2 Σ -1 F ,h ≤ C F ,U .Proposition 4 (Boundedness of FDVF). Under Assumptions 7 and 8, V F in Eq.4 satisfies∥V F ∥ ∞ ≤ C F ,2 := C F ,V C F ,U . Furthermore, when only Assumption 7 holds, ∥V F ,h ∥ Z h ≤ C F ,V , ∀h.See proof in Appendix D.4. Assumption 7 requires that the weighted covariance matrix Σ F ,h covers the direction of V πe S,h well. As a sanity check, it is always bounded in the on-policy case:Example 3. When π b = π e , ∥V πe S,h ∥ Σ -1 F ,h ≤ H √ S.Notably, mathematically similar coverage assumptions are also found in the linear MDP literature. For example, with state-action feature ϕ h for time step h, a very tight coverage parameter for linear et al., 2021] . Despite the mathematically similarity, there are important high-level differences between these notions of coverage:MDPs is ∥E πe [ϕ h ]∥ 2 Eπ b [ϕ h ϕ ⊤ h ] -1 [Zanette1. As mentioned earlier, MDP coverage is concerned with the dynamics before step h, whereas our outcome coverage concerns that after h. Relatedly, MDP coverage depends on the initial distribution (which our outcome coverage does not depend on), and our coverage depends on the reward function through V F (which MDP coverage does not explicitly depend on). In Section 5, we will discuss our other coverage assumption (belief coverage), which is more similar to the MDP coverage in that they are both concerned with the past. 2. The linear MDP coverage assumption is a refinement of state-density ratio using the knowledge of the function class [Chen and Jiang, 2019, Song et al., 2022] . In comparison, the linear structure of our outcome-coverage assumption comes directly from the internal structure of POMDPs.S dependence via L 1 /L ∞ Hölder and L ∞ Outcome CoverageExample 3 shows that even in the on-policy case, C F ,V may depend on S which makes the assumption only meaningful for finite and small S. In fact, we showed earlier that V F = R + is a natural and obvious L ∞ -bounded solution for π b = π e , but this is not recovered by the construction in Eq. ( 4). We also need an additional regularity Assumption 8.As it turns out, these undesired properties arise because L 2 Hölder-which is natural for linear MDP settings mentioned above-fails to leverage theL 1 normalization of u(f h ) ⊤ /Z(f h ) (Proposition 4,Claim 2) and is loose for POMDPs; see Appendix B.5 for further details. A better choice is L 1 /L ∞ Hölder, motivating the L ∞ coverage assumption below, which requires a slightly different construction of V F . These definitions may seem mysterious or even counterintuitive; it will be easier to explain the intuitions when we get to their counterparts for belief coverage in Section 5.2.Construction of V F Define Z R (f h ) := Z(f h )/R + (f h ),and we use Z R to replace Z in Eq.( 4):V F ,h = (Z R h ) -1 M ⊤ F ,h (Σ R F ,h ) -1 V πe S,h , where Σ R F ,h := M F ,h (Z R h ) -1 M ⊤ F ,h . (5) Assumption 9 (L ∞ outcome coverage). Assume for all h, ∥(Σ R F ,h ) -1 V πe S ∥ ∞ ≤ C F ,∞ . Lemma 5. Under Assumption 9, ∥V F ∥ ∞ ≤ HC F ,∞ . See proof in Appendix E.7.In Appendix B.5 we show that the construction shares similar properties to Eq.( 4) in the scenario of Example 2. On the other hand, it has better scaling properties w.r.t. S and does not additionally require a regularity assumption like Assumption 8. In the on-policy case, Eq.( 5) exactly recovers V F = R + , a property that Eq.(4) does not enjoy; see Appendix E.8 for details. Example 3 ). Furthermore, the construction in Eq.( 5) is exactlyExample 4. When π e = π b , (Σ R F ,h ) -1 V πe S = 1, thus Assumption 9 holds with C F ,∞ = 1 (c.f. C F ,V ≤ H √ S inV F = R + . 
effective history weights and a new algorithm: 
 We now turn to Q2 in Section 3, which asks for a quantitative understanding of the IV(V) term. Note that IV(V) and Dr V [d πe , d π b ], taken together, are to address the conversion between:(We minimize:EQUATIONThe two terms differ both in the policy (π b → π e ) and the operator (B H → B S ). While we could directly define a parameter by taking the worst-case (over V ∈ V) ratio between the two expressions,5 the real question is to provide more intuitive understanding of when it can be bounded.Towards this goal, Uehara et al. [2022a] split the above ratio into two terms, IV(V) and DrV [d πe , d π b ],which take care of the B H → B S conversion (under π b ) and π b → π e conversion (under B S ), respectively. While this leads to an intuitive upper bound of the π b → π e conversion parameter in terms of latent state coverage, the nature of the B H → B S conversion, IV(V), remains mysterious.In this section, we take a different approach by directly providing an intuitive upper bound on both conversions altogether, under a novel belief coverage assumption. In Appendix E.4 we will also revisit the split into IV(V) and Dr V [d πe , d π b ]: in the absence of strong structures from V, the boundedness of IV(V) turns out to require an even stronger version of belief coverage, rendering the split unnecessary. Furthermore, our approach also leads to a novel algorithm for estimating J(π e ) that replaces Bellman-completeness (Assumption 6) with a weight-realizability assumption, similar to MIS estimators for MDPs [Liu et al., 2018 , Uehara et al., 2020] .The key idea in this section is the notion of effective history weights, that perform the π b → π e and B H → B S conversions jointly.Definition 10 (Effective history weights). An effective history weight functionEQUATIONWe first see that well-bounded w ⋆ immediately leads to a good conversion ratio for Eq.( 6):|E πe (B S V )(s h ) | = |E π b [w ⋆ (τ h )(B H V )(τ h )]| ≤ E π b [w ⋆ (τ h ) 2 ]E π b [(B H V )(τ ) 2 ],where the inequality follows from Cauchy-Schwartz for r.v.'s. Hence, all we need is ∥w⋆ ∥ 2,d π b h := E π b [w ⋆ (τ h ) 2 ],the π b -weighted 2-norm of w ⋆ , to be bounded, and we focus on this quantity next. Similar to Section 4, there may be multiple w ⋆ that satisfies the definition, and we only need to show the boundeness of any solution. Also similarly, the most obvious solution is w⋆ (τ h ) = Prπ e (τ h ) Prπ b (τ h ) = h-1 h ′ =1 πe(a h ′ |o h ′ ) π b (a h ′ |o h ′ ) , noting that E πe (B S V )(s h ) = E πe (B H V )(τ h) and importance weighting on τ h changes E π b to E πe . However, the use of cumulative importance weights is undesirable given its exponential nature, causing the history-version of "curse of horizon" Liu et al. [2018] .Construction by Belief Matching. We now show a better construction that is bounded under a natural belief coverage assumption. Note that Def 10 can be written as:E π b [w ⋆ (τ h )⟨b(τ h ), B S h V ⟩] = E πe ⟨b(τ h ), B S h V ⟩ , where B S h V ∈ R Sis the Bellman residual vector for V on S h . As a sufficient condition (which is also necessary when V lacks strong structures, i.e., {B S h V : V ∈ V} spans the entire R S ), we can find w ⋆ that satisfies:E π b [w ⋆ (τ h )b(τ h )] = E πe [b(τ h )] =: b πeh . This is related to the mean matching problem in the distribution shift literature [Gretton et al., 2009, Yu and Szepesvári, 2012] , and a standard solution is [Bruns-Smith et al., 2023] :EQUATIONwhere Σ H,h := τ h d π b (τ h )b(τ h )b(τ h ) ⊤ ,∥ 2 Σ -1 H,h ≤ C H,2 . Lemma 6. Under Assumption 11, w ⋆ in Eq. (8) satisfies ∀h, ∥w ⋆ ∥ 2 2,d π b h ≤ C H,2 . See Appendix E.1.Assumption 11 requires that the covariance matrix of belief states under π b covers b πe , the average belief state under π e . As before, we also check the on-policy case (see Appendix E.2):Example 5. In the on-policy case (π b = π e ), C H,2 ≤ 1.Algorithm Guarantee Now we have all the pieces to present a fully polynomial version of Theorem 2 under the proposed coverage assumptions. One subtlety is that the guarantee depends on C V := max V ∈V ∥V ∥ ∞ , which is closely related to ∥V F ∥ ∞ since we require V F ∈ V, but they are not equal since V can include other functions with higher range. To highlight the dependence of ∥V F ∥ ∞ on the proposed coverage assumptions, we follow Xie and Jiang [2020] to assume that the range of the function classes is not much larger than that of the function it needs to capture. A similar assumption applies for bounding C Ξ . The proof of the theorem is deferred to Appendix E.10.Theorem 7. Consider the same setting as Theorem 2, and let Assumptions 11 and 9 hold. For some absolute constant c, further assume C V ≤ c∥V F ∥ ∞ for V F in Eq.( 5) andC Ξ ≤ c(∥V F ∥ ∞ + 1). W.p. ≥ 1 -δ, |J(π e ) -E D [ V (f 1 )]| ≤ cH 2 (C F ,∞ + 1) C H,2 Cµ log(|V||Ξ|/δ) n .In addition to H and complexities of |V| and |Ξ|, the bound only depends on the intuitive coverage parameters: C µ (action coverage), C H,2 (L 2 belief coverage), and C F ,∞ (L ∞ outcome coverage).Assumption 11 enables bounded second moment of w ⋆ (Lemma 6) but does not control ∥w ⋆ ∥ ∞ , which we show will be useful for the new algorithm in Section 5.3. Here we present the L ∞ version of belief coverage that controls ∥w ⋆ ∥ ∞ , which also helps understand L ∞ outcome coverage given the symmetry between history and future. As alluded to in Section 4.2 and Appendix B.5, L 2 Hölder is inappropriate for controlling the infinity-norm since it does not leverage the L 1 normalization of vectors in POMDPs. Instead, we propose the following decomposition based on L 1 /L ∞ Hölder:|w ⋆ (τ h )| ≤ ∥b(τ h )∥ 1 ∥Σ -1 H,h b πe h ∥ ∞ = ∥Σ -1 H,h b πe h ∥ ∞ .This way, we can immediately bound ∥w ⋆ ∥ ∞ with the following assumption:Assumption 12 (L ∞ belief coverage). Assume ∀h, ∥Σ -1 H,h b πe h ∥ ∞ ≤ C H,∞ . Then ∥w ⋆ ∥ ∞ ≤ C H,∞ .Σ -1 H,h b πe h is the inverse of second moment (covariance) multiplying the first moment (expectation), raising the concern that the quantity may be poorly scaled: for example, given bounded (but otherwise arbitrary) random vector X, E[XX ⊤ ] -1 E[X] can go to infinity if we rescale X by a small constant. First note that such a pathology cannot happen here because the random vectors (b(τ h )) are L 1normalized and cannot be arbitrarily rescaled. Below we use a few examples to show that Σ -1 H,h b πe h is a very well-behaved quantity, and naturally generalize familiar concepts such as concentrability coefficient from MDPs [Munos, 2007 , Chen and Jiang, 2019 , Uehara et al., 2022a] .We start by checking the on-policy case. Perhaps surprisingly, Σ -1 H,h b πe h has an exact solution: Example 6. When π e = π b , Σ -1 H,h b πe h = 1, the all-one vector; see Appendix E.5 for the calculation. Consequently, Assumption 12 is satisfied with C H,∞ = 1.The next scenario considers when b(τ h ) is always one-hot, i.e., histories reveal the latent state (this is analogous to Example 2. L ∞ coverage reduces to the familiar concentrability coefficient, the infinity-norm of density ratio as a standard coverage parameter:Example 7. When b(τ h ) is always one-hot, ∥Σ -1 H,h b πe h ∥ ∞ = max s h d πe (s h )/d π b (s h ).We can also calculate Xie and Jiang [2020] show that this is tighter than max s h d πe (s h )/d π b (s h ), and this relation extends elegantly to general belief vectors in our setting:∥b πe h ∥ 2 Σ -1 H,h from Assumption 11, which equals E π b [(d πe (s h )/d π b (s h )) 2 ] in this "1-hot belief" scenario.Lemma 8. ∥b πe h ∥ 2 Σ -1 H,h ≤ ∥Σ -1 H,h b πe h ∥ ∞ .See proof in Appendix E.6.The discovery of effective history weights and its boundedness also lead to a new algorithm analogous to MIS methods for MDPs [Uehara et al., 2020] . The idea is that since Lemma 1 tells us to minimizeE πe [(B S V )(s h )], which equals E π b [w ⋆ (τ h )(B H V )(τ h )]from Def 10, we can then use another function class W ⊂ (H → R) to model w ⋆ , and approximately solve the following:EQUATIONwhich minimizes an upper bound ofE π b [w ⋆ (τ h )(B H V )(τ h )] as long as w ⋆ ∈ W ⊂ (H → R).Since there is no square inside the expectation, there is no double-sampling issue and we thus do not need the Ξ class and its Bellman-completeness assumption. The h-th term of the loss can be estimated straightforwardly asEQUATION)We now provide the sample-complexity analysis of the algorithm, using a more general analysis that allows for approximation errors in V and W.Assumption 13 (Approximate realizablity). Assumemin V ∈V max w∈W H h=1 E π b w h (τ h ) • (B H V )(τ h ) ≤ ϵ V , inf w∈sp(W) max V ∈V H h=1 E π b (w ⋆ h (τ h ) -w h (τ h )) • (B H V )(τ h ) ≤ ϵ W .Instead of measuring how W and V capture our specific constructions of V F and w ⋆ , the above approximation errors automatically allow all possible solutions by measuring the violation of the equations that define V F and w ⋆ .We present the sample complexity bound of our algorithm as follows. Similar to Theorem 7, we assume that C V := max V ∈V ∥V ∥ ∞ and C W := max h sup w∈W ∥w∥ ∞ are not much larger than the corresponding norms of V F and w ⋆ , respectively. See the proof in Appendix E.11.Theorem 9. Let V be the result of approximating Eq.9 with empirical estimation in Eq.( 10). Assume that C V ≤ c∥V F ∥ ∞ for V F in Eq.( 5), and C W ≤ c∥w ⋆ ∥ ∞ for w ⋆ in Eq.( 8). Under Assumptions 12, 9, and 13, w.p.≥ 1 -δ, J(π e ) -E D [ V (f 1 )] ≤ ϵ V + ϵ W + cH 2 C H,∞ (C F ,∞ + 1) Cµ log |V||W| δ n .As a remark, there is also a way to leverage the tighter L 2 belief coverage, despite that it does not guarantee bounded ∥w ⋆ ∥ ∞ and only∥w ⋆ ∥ 2 2,d π b h. In particular, if all functions in W have bounded∥ • ∥ 2 2,d π b h, the estimator in Eq.( 10) will have bounded 2nd moment on the data distribution. In this case, using Median-of-Means estimators [Lerasle, 2019 , Chen, 2020 ] instead of plain averages for Eq.( 10) will only pay for the 2nd moment and not the range. 
conclusion and future work: 
 The main text considers memoryless policies. Similar to Uehara et al. [2022a] , we can extend to policies that depend on recent observations and actions (or memory). In fact, we provide a more general result in Appendix B.6 that handles recurrent policies that are finite state machines, which allows the policy to depend on long histories. However, the coverage coefficient will be diluted quickly when the memory contains rich information, which we call the curse of memory. We suspect that structural policies are needed to avoid the curse of memory and leave this to future work. , 2016 , Namkoong et al., 2020 , Nair and Jiang, 2021 , Guo et al., 2022 , Lu et al., 2022 , Shi et al., 2022 , Hong et al., 2023] . However, all these methods require the behavior policy to solely depend on the latent state. This assumption is inapplicable for our unconfounded POMDP setting, where the behavior policy depends on the observations. Hu and Wager [2023] studied the same unconfounded setting as ours. Nonetheless, their method uses multi-step importance sampling, leading to an undesirable exponential dependence on the horizon. The closest related work to our paper is [Uehara et al., 2022a ], which we analyze in detail in Section 3. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [NA] Justification: No experiments.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes] Justification: We conform with the NeurIPS Code of Ethics.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA] Justification: This paper presents work whose goal is to advance the field of learning theory and has no societal impact.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: This paper poses no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [NA] Justification: This paper does not use existing assets.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. 
 
 Appendix: Online Learning in POMDPs. There are many prior works studying online learning algorithms for sub-classes of POMDPs, including decodable POMDPs [Krishnamurthy et al., 2016 , Jiang et al., 2017 , Du et al., 2019 , Efroni et al., 2022] , Latent MDPs [Kwon et al., 2021] and linear quadratic Gaussian setting (LQG) [Lale et al., 2021 , Simchowitz et al., 2020] . Recently, online learning algorithms with polynomial sample results have been proposed for both tabular POMDPs [Guo et al., 2016 , Azizzadenesheli et al., 2016 , Jin et al., 2020 , Liu et al., 2022a] and POMDPs with general function approximation [Zhan et al., 2022 , Liu et al., 2022b , Chen et al., 2022 , Huang et al., 2023] .All of these approaches are model-based and require certain model assumptions. Uehara et al. [2022b] proposed a model-free online learning algorithm based on future-dependent value functions (FDVFs). However, their algorithm requires the boundness of FDVFs for all policies in the policy class, as well as a low-rank property of the Bellman loss, which limits the generality of the results.There has been a long history of studying OPE in MDPs, including importance sampling (IS) approaches [Precup et al., 2000 , Li et al., 2011] and their doubly robust variants [Dudík et al., 2011 , Jiang and Li, 2016 , Thomas and Brunskill, 2016 , Farajtabar et al., 2018] , marginalized importance sampling (MIS) methods [Liu et al., 2018 , Xie et al., 2019 , Kallus and Uehara, 2020] and model-based estimators [Eysenbach et al., 2020 , Yin et al., 2021 , Voloshin et al., 2021] . As mentioned in Section 1, directly applying IS-based approaches for POMDPs will result in exponential variance. Meanwhile, MIS-based approaches do not apply to POMDPs since they require the environment to satisfy the Markov assumption.B.1 Connection between Future-dependent Value Functions and Learnable Future-dependent Value Functions Uehara et al. [2022a] proposed a learnable version of future dependent value functions and focused on the learning of learnable FDVFs instead of the original FDVFs defined in Definition 3. In this subsection, we first introduce the definition of learnable FDVFs and then show that it is equivalent to FDVFs under a full-rank assumption. Definition 14 (Learnable future-dependent value functions). A Learnable future-dependent value function V L F : F → R is any function that satisfies the following:∀τ h , (B H V L F )(τ h ) = 0. For any FDVF V F , since B S V F ≡ 0, we have ∀τ h , (B H V F )(τ h ) = E π b [µ(o h , a h ){r h + V F (f h+1 )} -V F (f h ) | τ h ] = ⟨b(τ h ), B S h V F ⟩ = 0.Therefore, all FDVFs are also learnbale FDVFs. On the other hand, for any learnbale FDVFV L F , let B H h V L F ∈ R |H h |be the Bellman residual vector for V L F on H h and B S h V L F ∈ R S be the Bellman residual vector on S h . With the help of M H,h , we have the following relation betweenB H h V L F and B S h V L F : B H h V L F = (M H,h ) ⊤ B S h V L F . When rank(M H,h ) = S, B H h V L F = 0 if and only if B S h V L F = 0. Therefore, V L F satisfies that ∀s h , (B S V L F )(s h ) = 0, implying that V LF is also a FDVF. Under the regular full rank assumption, the two definitions are actually equivalent.The original results of Uehara et al. [2022a] were given in the infinite-horizon discounted setting. To describe their data collection assumption in simple terms, consider an infinite trajectory that enters the stationary configuration of π b , and we pick a random time step and call it t = 0 (which corresponds to a time step h in our setting). Then, history (analogous to our τ h ) is (o (-M F ):(-1) , a (-M F ):(-1) ), and future is (o 0:M H , a 0:M F -1 ). M F and M H are hyperparameters that determines the lengths, and should not be confused with our M F ,h and M H,h matrices. Data points collected in this way form the "transition" dataset. Separately, there is an "initial" dataset of (o 0:M F -1 , a 0:M F ) tuples to represent the analogue of initial state distribution in MDPs.Besides the fact that finite-horizon formulation better fits real-world applications with episodic nature (e.g., a session in conversational system), there are mathematical reasons why the finite-horizon formulation is more natural:1. Unlike the infinite-horizon setting, we do not need separate "trainsition" and "initial" datasets. The natural H-step episode dataset plays both roles. We also do not need the stationarity assumption. 2. In the infinite-horizon, M F and M H are hyperparameters which do not have an obvious upper bound. The larger they are, it is easier to satisfy certain identification assumptions (such as full-rankness of the counterparts of our M H,h and M F ,h ). On the other hand, the "curses of future and horizon" we identified in this work corresponds to exponential dependence on M F and M H , so there is a potential trade-off in the choice of M F and M H . In contrast, the future and the history have maximum lengths (H -h and h -1 at time step h) in our setting. As we establish coverage assumptions that avoid potential exponential dependencies on these lengths, the trade-off in the choice of length is eliminated, so it is safe for us to always choose the maximum length, as we do in the paper.As alluded to at the beginning of Section 5, we can tighten the definition of L 2 belief coverage by directly using the ratio:sup V ∈V |E πe [(B S V )(s h )]| E π b [(B H V )(τ h ) 2 ],which automatically leverages the structure of V. For example, if {B S h V : V ∈ V} only occupies a low-dimensional subspace of R S h (that is, there exists ϕ : S h → R d such that (B S V )(s h ) = ϕ(s h ) ⊤ θ V ), then belief matching above Eq.( 8) can be done in R d instead of R S h . Other coverage definitions may be refined in similar manners.To interpret Assumption 8, let x = u(f h )/Z(f h ) ∈ ∆(S), and assign a distribution over x by sampling f h ∼ diag(Z h /S), then Assumption 8 becomes x ⊤ E Z h /S [xx ⊤ ] -1 x ≤ C F ,U S for any x with non-zero probability. This is a common regularity assumption [Duan et al., 2020 , Perdomo et al., 2023] , requiring that no x points to a direction in R S alone without being joined by others from the distribution. While 1/σ min (Σ F ,h ) can bound this quantity, the other way around is not true, implying that Assumption 8 is weaker. Example 8 (Bounded C F ,U without bounded 1/σ min (Σ F ,h )). Consider a distribution over x where with 0.5 probability, x = [1/2+ϵ, 1/2-ϵ] ⊤ , and with the other 0.5 probability,x = [1/2-ϵ, 1/2+ϵ] ⊤ . Then, as ϵ → 0, 1/σ min (Σ F ,h ) → ∞, but x ⊤ E[xx ⊤ ] -1 x ≤ 2.Here we provide more details about the L ∞ outcome coverage in Section 4.2, which are omitted in the main text due to space limit.Looseness of L 2 outcome coverage We start by examining the looseness of L 2 outcome coverage (Assumption 7), which will motivate the L ∞ version of outcome coverage. To develop intuitions, we first examine the boundedness of Eq.( 4) (the construction that leads to L 2 outcome coverage) in the setting of Example 2. In this example, Σ F ,h = I, and ∥V F ∥ ∞ ≤ H. According to the L 2 Hölder decomposition in Proposition 4, however,∥V F ∥ ∞ ≤ max f h ∥u(f h )/Z(f h )∥ 2 ∥V πe S ∥ 2 ≤ H √ S,where∥ • ∥ Σ -1 F ,his replaced by ∥ • ∥ 2 since Σ F ,h = I. In contrast, the tight analysis is∥V F ∥ ∞ ≤ max f h ∥u(f h )/Z(f h )∥ 1 ∥V πe S ∥ ∞ ≤ H.The comparison clearly highlights that the looseness in S comes from the fact that L 2 Hölder does not fully leverage the fact that ∥u(f h )/Z(f h )∥ 1 = 1 and loosely relaxing it to ∥u(f h )/Z(f h )∥ 2 ≤ 1.In contrast, our L ∞ coverage assumption allows for a more natural L 1 /L ∞ Hölder to leverage theL 1 normalization of u(f h )/Z(f h ). L ∞ Outcome Coverage Similar to L ∞ belief coverage, we could define L ∞ outcome coverage simply as ∥(Σ F ,h ) -1 V πe S ∥ ∞ .The small caveat and inelegance is that it does not recover V F = R + when π b = π e . To address this, we leverage the lesson from belief coverage (Section 5.2): to obtain C H,∞ = 1 when π b = π e , a key property is that Σ H,h (data covariance matrix) and b π b h (the vector to be covered) are the covariance matrix and the mean vector w.r.t. the same distribution of belief vectors. In contrast, for the outcome coverage case, V πe S depends on the reward function, but such information is missing in Σ F ,h , which prevents a perfect cancellation in the on-policy case.Therefore, we can adjust the definition of Σ F ,h to mimic the situation of belief coverage. The first step is to find the counterpart of belief state which is L 1 -normalized. This obviously corresponds toZ -1 h M ⊤ F ,h , whose rows sum up to 1. Let ū(f h ) := u(f h )/Z(f h ) ∈ ∆(S h ), then Σ F ,h = S • E Z h /S [ūū ⊤ ].Then, by incorporating reward information into Σ F ,h , we arrive at the solution in Eq.( 5).Finally, we examine the setting of Example 2 and show that V F in Eq.( 5) is similarly well-behaved as Eq.( 4) in this scenario.Example 9. In the same setting as Example 2, i.e., f h always reveals s h , we haveΣ R F ,h = diag(V π b S h ), and ∥(Σ R F ,h ) -1 V πe S ∥ ∞ = max s h V πe S (s h )/V π b S (s h ).This example also closely resembles Example 7 for belief coverage. While (Σ R F ,h ) -1 may behave poorly if V π b S (s h ) is small, an easy fix is to simply add a constant to the reward function and shift its range to e.g., [1, 2] , which ensures a small C F ,∞ .The main text assumes memoryless π b and π e . Similar to Uehara et al. [2022a] , we can extend the approach to handle history-dependent policies (the changes to the proof are sketched below). Instead of rewriting the proof with these changes, we will provide a "black-box" reduction that handles the extension more elegantly and allow for more general results than Uehara et al. [2022a] .Memory-based Policies and Changes in the Proofs Define memory m h as a function of τ h (i.e., m h = m h (τ h )), and a memory-based policy can depend on (m h , o h ). Uehara et al. [2022a] allows for m h = (o h-M :h-1 , a h-M :h-1 ) for some fixed window M in their analyses. If we let m h = (o 1:h-1 , a 1:h-1 ), we recover fully general history-dependent policies.If we direct modify the proofs to accommodate this generalization (as done in Uehara et al. [2022a] ), the required changes are:• V πe S and V F need to additionally depend on m h to be well defined. V ∈ V also generally depend on m h since we need realizability V F ∈ V. . This is generally exponential in the length of m h (e.g., if M = h -1, the ratio is exactly the cumulative importance weight), preventing us from handling π b and π e with long-range history dependencies.Reduction to Memoryless Case Instead of changing the proofs, we now describe an alternative approach that (1) produces results similar to Uehara et al. [2022a] , and (2) handles more general recurrent policies that are finite-state-machines (FSMs), which subsume fully history-dependent policies (or policies that depend on a fixed-length window) as special cases.Concretely, a policy with memory m h is said to be an FSM, if m h+1 can be computed solely based on m h , o h , a h , without using other information in τ h .m h = (o h-M :h-1 , a h-M :h-1) satisfies this definition, as computing m h+1 is simply dropping the oldest observation-action pair from m h and appending the newest one. 6 Another example is belief update, where b(τ h+1 ) can be computed from b(τ h ), o h , a h . We assume that both π b and π e have the same memory; if they differ, we can simply concatenate their memories together. Then, handling memories in our analyses takes two steps:1. We allow latent state transition to depend on o h , that is, s h+1 ∼ T(•|s h , a h , o h ). This model has been considered by Jiang et al. [2017] to unify POMDPs and low-rank MDPs. Our analyses hold as-is without any changes. To provide some intuition: the key property that enables the analyses of FDVF is that s h is a bottleneck that separates histories from futures, which enables 2). This property is intact with the additional dependence of s h on o h-1 .(B H V )(τ h ) = ⟨b(τ h ), B S h V ⟩ in Eq.(2. We provide a blackbox reduction from the memory-based case to the memoryless case. Define a new POMDP that is equivalent to the original one, where the latent state is sh = (s h , m h ). The observation is õh = (o h , m h ), which can be emitted from sh since sh contains m h . The latent state transition is sh+1 = (s h+1 , m h+1 ), where s h+1 ∼ T(•|s h , a h , o h ), and m h+1 is updated from m h (contained in sh ), a h , and o h ; this is why we need o h to participate in latent transitions. Now it suffices to perform OPE in the new POMDP. Data from the original POMDP can be converted to that of the new POMDP with õh = (o h , m h ). π b and π e only need to depend on õh and become memoryless.Given the reduction, if we design function classes that operate on the histories and futures of the new POMDP, the guarantees in the main text immediately hold. The final step is to translate the objects (e.g., futures and histories) and guarantees in the new POMDP back to the original POMDP for interpretability. Note that the history in the new POMDP is τh = (õ 1:h-1 , a 1:h-1 ), which contains the same information as τ h , so functions in Ξ and W can still operate on τ h . Similarly, V ∈ V now takes (m h , f h ) as input, which is consistent with Uehara et al. [2022a] .When translating the assumptions back to the original POMDP, we can see that now the results can be well-behaved when m h is "simple". For example, if m h takes values from a constant-sized space, d πe (s h , m h )/d π b (s h , m h ) (which lower-bounds belief coverage as discussed above) may not blow up exponentially, even though m h can hold information that is arbitrarily old (e.g., it remembers one bit of information from h = 1). This is a scenario that cannot be handled by the formulation of Uehara et al. [2022a] .However, the guarantee can still deteriorate when the policies maintain rich memories, even if these memories are highly structured, such as m h = b(τ h ). Under the mild assumption that all histories lead to distinct belief states b(τ h ) (they can be very close in R S and just need to be not exactly identical), the belief state in the new POMDP, b(τ h ), completely ignores the linear structure of m h and treats it in the same way as m h = τ h ,7 leading to an exponentially large belief coverage. How to handle policies that depend on rich but highly structured memories such as belief states is a major open problem.One somewhat undesirable property of our algorithms and analyses is that they do not subsume MDP algorithms/analyses as a special case. MDPs can be viewed as POMDPs with identity emission, i.e., o h = s h . In this case, algorithms considered in this paper are analogous to their MDP counterparts Uehara et al. [2020] , except that the MDP algorithms require that all functions V , w, ξ to operate on the current state s h . In contrast, our FDVF operates on f h = (o h , a h , . . . , o H , a H ) which includes o h (= s h ). To recover the MDP algorithm as a special case, we can choose V such that every V ∈ V only depends on f h through o h . However, w and ξ operate on τ h = (o 1 , a 1 , . . . , o h-1 , a h-1 ) which does not contain o h . This makes subsuming the MDP case difficult.Here we describe briefly how to overcome this issue by slightly modifying our analysis; the changes are somewhat similar to Appendix B.6. Instead of letting τ h = (o 1 , a 1 , . . . , o h-1 , a h-1 ), we can define an alternative notion of history τh = (o 1 , a 1 , . . . , o h ) and replace τ h in the main text with τh . Algorithmically, we can immediately recover MDP algorithms by also restricting functions in W and X to only operate on o h . However, our analyses (which apply to general POMDPs) need to change accordingly, as replacing τ with τh will break the key properties, such as B H V being linear in B S V . The problem is that in the definitions of V πe S and B S V we want to marginalize out the randomness of o h given s h , which is in conflict with conditioning on τh that includes all the information of o h . To address this, we simply replace s h with sh := (s h , o h ) in the definition of V πe S , B S V , M H,h , and M F ,h . That is, V πe S is now a function of sh and also depends on o h , b(τ h ) is the posterior distribution over sh , and the entries of the outcome matrix M F ,h is Pr π b (f h |s h , o h ). This retains the key property that B H V is linear in B S V with b(τ h ) as the coefficient.When we specialize the guarantees of this modified analysis to the MDP setting, outcome coverage is always satisfied and we can always use the MDP's standard value function as V F . For belief coverage, note that(B H V )(τ h ) = (B S V )(s h , o h ),which is simply the standard definition of Bellman error in MDPs (since s h = o h ), which we denote as (BV )(s h ). Plugging this into the refined coverage discussed in Appendix B.3, we recover the standard definition of coverage in the MDP setting, namelysup V ∈V |Eπ e [(B S V )(s h )]| √ Eπ b [(B S V )(s h ) 2 ] . B.8 Incorporating Different Latent-State Priors in V FIn Section 4 we showed that Σ F ,h , which is crucial to the construction in Eq.( 4), can be viewed as the confusion matrix of making posterior predictions of s h from f h , using a uniform prior. The uniform prior corresponds to the all-one vector 1 S in the definition of Z h := diag(1 ⊤ S M F ,h ), which naturally leads to the question of whether we can incorporate a different and perhaps more informative prior.Let p h ∈ ∆(S h ) be the prior we would like to use instead of the uniform prior. An immediate idea is to define Z p h h = diag(p ⊤ h M F ,h ) (possibly up to a S scaling factor, as the uniform prior is p unif = [1/S, • • • , 1/S] ⊤ and 1 S = Sp unif ) and directly plug it into the construction in Eq.( 4). However, this breaks some of the key properties of the current construction of Σ F ,h , such as L 1 normalization of rows of Z -1 h M ⊤ F ,h . To resolve this, the key is to realize that the rows of Z -1 h M ⊤ F ,h are L 1 normalized because they can be viewed as posteriors over S h . In comparison, if we examine the (f h , s h )-th entry of (Zp h h ) -1 M ⊤ F ,h , it is Pr π b [f h |s h ] s ′ ∈S h Pr π b [f h |s ′ ]p h (s ′ ), so clearly it is missing a p h (s h ) term on the numerator to be a proper posterior. Inspired by this observation, we can see how to fix the construction now: recall thatV F needs to satisfy M F ,h V F ,h = V πe S,h . If p h > 0, then this is equivalent to (diag(p h )M F ,h )V F ,h = diag(p h )V πe S,h . Then, the minimum Z p hh -weighted solution of this equation will provide the desired construction that preserves the L 1 normalization properties.Which prior p h to use? For the initial time step h = 1, the initial latent-state distribution d 1 is the most natural candidate for the prior. If d 1 (s 1 ) = 0 for some s 1 ∈ S 1 , incorporating d 1 as the prior will essentially treat s 1 as non-existent and ignore the outcome coverage of π b over π e from s 1 , which is reasonable because s 1 will not be activated by neither π e and π b . For h > 1, the answer is less clear, and natural candidates include p h = d π b h and d πe h , or perhaps their probability mixture. For the example scenarios examined in the main text, these choices (or even a uniform prior) do not make significant differences, and we leave the investigation of which prior is the best to future work.The RHS of the lemma statement isH h=1 E πe (B S V )(s h ) = H h=1 E s h ∼d πe h E a h ∼πe a h+1:H ∼π b [r h + V (f h+1 ) | s h ] -E π b [V (f h ) | s h ] .Now notice that the expected value of the V (f h+1 ) term for h is the same as that of the V (f h ) term for h + 1, since both can be written asE s h+1 ∼d πe h+1 [E π b [V (f h+1 )|s h+1 ]]. After telescoping cancellations, what remains on the RHS is H h=1 E s h ∼d πe h E a h ∼πe a h+1:H ∼π b [r h | s h ] -E s1 [E π b [V (f 1 )|s 1 ]] = J(π e ) -E π b [V (f 1 )].The proof follows similar idea from Uehara et al. [2022a] .Let G h V = µ(o h , a h )(r h + V (f h+1 )) - V (f h ), we have V = argmin V ∈V max ξ∈Ξ H h=1 E D (G h V ) 2 -(G h V -ξ(τ h )) 2 .For any fixed V , we defineξ V = argmax ξ∈Ξ - H h=1 E D (G h V -ξ(τ h )) 2 .Analysis of Inner Maximizer. We observe that for any h ∈ [H],E π b (ξ(τ h ) -G h V ) 2 -((B H V )(τ h ) -G h V ) 2 = E π b (ξ(τ h ) -(B H V )(τ h )) 2 . Let X h = (ξ(τ h )-G h V ) 2 -((B H V )(τ h )-G h V ) 2 and X = H h=1 X h . Let C = max{1+C V , C Ξ }, since C µ ≥ 1, we have |ξ(τ h )| ≤ C, |G h V | ≤ 3C µ C and B H V (τ h ) ≤ 3 C. Therefore, we have |X h | ≤ 40C µ C2 and |X| ≤ 40HC µ C2 . We observe that E π b [X 2 h ] ≤ E π b ((B H V )(τ h ) -ξ(τ h )) 2 (B H V )(τ h ) + ξ(τ h ) -2G h V 2 ≤ E π b (B H V )(τ h ) -ξ(τ h ) 2 30 C2 + 12(G h V ) 2 ≤ E π b (B H V )(τ h ) -ξ(τ h ) 2 54 C2 + 96 C2 µ(o h , a h ) 2 ≤ 150 C2 C µ E π b (B H V )(τ h ) -ξ(τ h ) 2 .Hence, for the variance of X, we haveVar π b [X] ≤ H H h=1 E π b X 2 h ≤ 150H C2 C µ H h=1 E π b (B H V )(τ h ) -ξ(τ h ) 2 .From Bernstein's inequality, with probability at least 1 -δ/2, ∀V ∈ V, ∀ξ ∈ Ξ, we haveEQUATIONFrom Bellman completeness assumption B H V ⊂ Ξ, we also haveEQUATIONTherefore, we obtain thatH h=1 E π b [((B H V )(τ h ) -ξ V (τ h )) 2 ] = H h=1 E π b [( ξ V (τ h ) -G h V ) 2 -((B H V )(τ h ) -G h V ) 2 ] ≤ H h=1 {E D -E π b }[( ξ V (τ h ) -G h V ) 2 -((B H V )(τ h ) -G h V ) 2 ] + H h=1 E D [( ξ V (τ h ) -G h V ) 2 -((B H V )(τ h ) -G h V ) 2 ] ≤ H h=1 {E D -E π b }[( ξ V (τ h ) -G h V ) 2 -((B H V )(τ h ) -G h V ) 2 ] ≤ 150H C2 C µ H h=1 E π b [((B H V )(τ h ) -ξ V (τ h )) 2 ] log(4|V||Ξ|/δ) n + 40H C2 C µ log(4|V||Ξ|/δ) n .The second inequality is from Equation ( 12) and the last inequality is from Equation (11). We then haveEQUATIONCombining Equation ( 11) and Equation ( 13), we haveEQUATIONHence,H h=1 E D [( ξ V (τ h ) -G h V ) 2 ] - H h=1 E D [((B H V )(τ h ) -G h V ) 2 ] ≤ H h=1 E π b [( ξ V (τ h ) -G h V ) 2 ] - H h=1 E π b [((B H V )(τ h ) -G h V ) 2 ] + 2ε stat = H h=1 E π b [((B H V )(τ h ) -ξ V (τ h )) 2 ] + 2ε stat ≤ 3ε stat .The first inequality is from Equation ( 14) and the last step is from Equation (13).Analysis of Outer Minimizer. For any future-dependent value function V F , from optimality of V and the convergence of inner maximizer, we haveEQUATIONThe last step is from that (B H V F )(τ h ) = 0. For any τ h , we observe that ∀V ∈ V and h ∈ [H],E π b [(G h V ) 2 -(G h V -(B H V )(τ h )) 2 ] = E π b [-(B H V )(τ h ) 2 + 2(B H V )(τ h )G h V ] = E π b [(B H V )(τ h ) 2 ]. For any fixed V ∈ V, let Y h = (G h V ) 2 -(G h V -(B H V )(τ h )) 2 and Y = H h=1 Y h , we have |Y h | ≤ 27 C2 C µ and |Y | ≤ 27H C2 C µ . We observe that E π b [Y 2 h ] = E π b [(2G h V -(B H V )(τ h )) 2 (B H V )(τ h ) 2 ] ≤ E π b [(18 C2 + 4(G h V ) 2 )(B H V )(τ h ) 2 ] ≤ E π b [(26 C2 + 32 C2 µ(o h , a h ) 2 )(B H V )(τ h ) 2 ] ≤ 58 C2 C µ E π b [(B H V )(τ h ) 2 ].Then, for the variance of Y , we haveVar π b [Y ] ≤ E π b [Y 2 ] ≤ H H h=1 E π b [Y 2 h ] = 58H C2 C µ H h=1 E π b [(B H V )(τ h ) 2 ].From Bernstein's inequality, with probability at least 1 -δ/2, ∀V ∈ V, we haveEQUATIONTherefore, we haveH h=1 E π b (B H V )(τ h ) 2 = H h=1 E π b [(G h V ) 2 -(G h V -(B H V )(τ h )) 2 ] ≤ H h=1 (E D -E π b )[(G h V ) 2 -(G h V -(B H V )(τ h )) 2 ] + H h=1 E D (G h V ) 2 -(G h V -(B H V )(τ h )) 2 ≤ 58H C2 C µ H h=1 E π b (B H V )(τ h ) 2 log(4|V|/δ) n + 27H C2 C µ log(4|V|/δ) n + 6ε stat .(From Equation ( 15) and Equation ( 16)) Solving it and we getH h=1 E π b (B H V )(τ h ) 2 ≤ 10ε stat .We then invoke Lemma 1 and obtain thatJ(π e ) -E π b [ V (f 1 )] ≤ H h=1 E s h ∼d h πe (B S V )(s h ) ≤ H H h=1 E s h ∼d h πe (B S V )(s h ) 2 ≤ H H h=1 E s h ∼d h πe (B S V )(s h ) 2 ≤ H H h=1 E π b (B H V )(τ h ) 2 • H h=1 E s h ∼d h πe (B S V )(s h ) 2 H h=1 E π b (B H V )(τ h ) 2 ≤ 10Hε stat • H h=1 E πe (B S V )(s h ) 2 H h=1 E π b (B S V )(s h ) 2 • H h=1 E π b (B S V )(s h ) 2 H h=1 E π b (B H V )(τ h ) 2 ≤ 50H max{C V + 1, C Ξ }IV(V)Dr V [d πe , d π b ] C µ log 4|V||Ξ| δ n .The proof is completed by using Hoeffding's inequality to bound|E D [ V (f 1 )] -E π b [ V (f 1 )]|.D Proofs for Section 4 (f h )∥ 2 ≤ C stoch √ S (OA) H-h+1 .Then, for any x ∈ R S such that ∥x∥ 2 = 1, we havex ⊤ (M F ,h M ⊤ F ,h )x ≤ f h ∥x∥ 2 2 ∥u(f h )∥ 2 2 = C 2 stoch S (OA) H-h+1 . Therefore, σ min (M F ,h ) ≤ σ max (M F ,h ) ≤ C stoch √ S/(OA) (H-h+1)/2 .For each entry in Σ F ,h , we can write it as(Σ F ,h ) ij = k Pr π b (f h = k | s h = i) Pr π b (f h = k | s h = j) i ′ Pr π b (f h = k | s h = i ′ )Since the probability is always non-negative, all the entries in Σ F ,h is non-negative. For each row i, we havej (Σ F ,h ) ij = k j Pr π b (f h = k | s h = i) Pr π b (f h = k | s h = j) i ′ Pr π b (f h = k | s h = i ′ ) = k Pr π b (f h = k | s h = i) = 1.Similarly, for each column j, we also have i (Σ F ,h ) ij = 1. Therefore, we prove that Σ F ,h is doubly-stochastic and we know for a stochastic matrix, the largest eigenvalue is 1.Due to the block structure of M F ,h , Σ F ,h is clearly diagonal, and the i-th diagonal entry is:j:Prπ b [f h =j|s h =i]>0 Pr π b [f h = j|s h = i] 2 i ′ Pr π b [f h = j|s h = i ′ ].Due to the revealing property, the denominator is just Pr π b [f h = j|s h = i], so the expression is just summing up Pr π b [f h = j|s h = i] over j, which is 1.According to Equation (4), we have for any f h ,V F (f h ) = Z(f h ) -1 u(f h ) ⊤ Σ -1 F ,h V πe S,h ≤ Z(f h ) -1 u(f h ) ⊤ Σ -1 F ,h Z(f h ) -1 u(f h ) (V πe S,h ) ⊤ Σ -1 F ,h V πe S,h ≤ C F ,U C F ,V .The last step is from Assumption 7 and Assumption 8. Therefore,∥V F ∥ ∞ ≤ C F ,U C F ,V = C F ,2. Moreover, we observe that∥V F ,h ∥ 2 Z h = f h Z(f h ) Z(f h ) -1 u(f h ) ⊤ Σ -1 F ,h V πe S 2 = f h Z(f h ) -1 (V πe S ) ⊤ Σ -1 F ,h u(f h )u(f h ) ⊤ Σ -1 F ,h V πe S = (V πe S ) ⊤ Σ -1 F ,h   f h Z(f h ) -1 u(f h )u(f h ) ⊤   Σ -1 F ,h V πe S = (V πe S ) ⊤ Σ -1 F ,h Σ F ,h Σ -1 F ,h V πe S ≤ C F ,V .The last step is from Assumption 7.We give the calculation for Example 3. Whenπ e = π b , V πe S,h = M F ,h R + h , so ∥V πe S,h ∥ 2 Σ -1 F ,h = (R + h ) ⊤ M ⊤ F ,h Σ -1 F ,h M F ,h R + h = (R + h ) ⊤ Z 1/2 h Z -1/2 h M ⊤ F ,h (M F ,h Z -1 h M ⊤ F ,h )M F ,h Z -1/2 h Z 1/2 h R + h ≤ (R + h ) ⊤ Z 1/2 h Z 1/2 h R + h, where the last step follows from the fact thatZ -1/2 h M ⊤ F ,h (M F ,h Z -1 h M ⊤ F ,h )M F ,h Z -1/2 his a projection matrix (P 2 = P ) and is dominated by identity in eigenvalues (P ⪯ I). Now, recall that Z h /S is a proper distribution, so(R + h ) ⊤ Z h R + h = S • E Z h /S [(R + h ) 2 ] ≤ SH 2 .E Proofs for Section 5E.1 Proof of Lemma 6We first verify that w ⋆ in Eq. ( 8) satisfies Eq. ( 7) as follows.E π b [w ⋆ (τ h )b(τ h )] = τ h d π b h (τ h )w ⋆ (τ h )b(τ h ) = τ h d π b h (τ h )b(τ h )b(τ h ) ⊤ Σ -1 H,h b πe h = τ h d π b h (τ h )b(τ h )b(τ h ) ⊤ Σ -1 H,h b πe h = b πe h . We then show that ∥w ⋆ ∥ 2 2,d π b h = τ h d π b h (τ h ) b(τ h ) ⊤ Σ -1 H,h (b πe h ) 2 = (b πe h ) ⊤ Σ -1 H,h τ h d π b h (τ h )b(τ h )b(τ h ) ⊤ Σ -1 H,h b πe h = (b πe h ) ⊤ Σ -1 H,h Σ H,h Σ -1 H,h b πe h = (b πe h ) ⊤ Σ -1 H,h b πe h ≤ C H,2. The last step follows from Assumption 11.Consider the lemma: given vector x and PD matrix Σ, if Σ ⪰ xx ⊤ , then x ⊤ Σ -1 x ≤ 1. The calculation in the example directly follows from letting x = b π b h , Σ = Σ H,h , and the condition Σ ⪰ xx ⊤ is satisfied due to Jensen's inequality.To prove the lemma, note that Σ -xx ⊤ is PSD, so(Σ -1 x) ⊤ (Σ -xx ⊤ )(Σ -1 x) ≥ 0. This implies x ⊤ Σ -1 x ≥ x ⊤ Σ -1 xx ⊤ Σ -1 x, so x ⊤ Σ -1 x ≤ 1.Here we show that belief coverage is stronger than latent state coverage. More concretely, consider a standard measure of latent state coverage, the 2nd moment of state density ratio (c.f. discussion below Example 7):E π b [(d πe (s h )/d π b (s h )) 2 ] = (b πe h ) ⊤ diag(E π b [b(τ h )]) -1 b πe h .In comparison, our belief coverage parameter from Assumption 11 is(b πe h ) ⊤ Σ -1 H,h b πe h = (b πe h ) ⊤ E π b [b(τ h )b(τ h ) ⊤ ] -1 b πe h .To show the former is smaller than the latter, it suffices to show thatdiag(E π b [b(τ h )]) -1 ⪯ (E π b [b(τ h )b(τ h ) ⊤ ]) -1 , which is implied by diag(E π b [b(τ h )]) ⪰ E π b [b(τ h )b(τ h ) ⊤ ]. It therefore suffices to show that diag(b(τ h )) ⪰ b(τ h )b(τ h ) ⊤holds in a pointwise manner for all τ h . To show this, we temporarily let b = b(τ h ) in the calculation: consider an arbitrary vector v ∈ R S , thenv ⊤ (diag(b) -bb ⊤ )v = E s∼b [v(s) 2 ] -(E s∼b [v(s)]) 2 ≥ 0.The last step is due to Jensen's inequality.We now compare to the IV(V) and Dr V terms in Theorem 2. Belief coverage is generally stronger than latent state coverage which corresponds to the Dr V term (see Appendix E.3). That said, perhaps surprisingly, the remaining IV(V) term must scale with 1 σmin(Σ H,h ) under moderate assumptions. Proposition 10. Suppose v min is the eigenvector corresponding to σ min (Σ H,h ), the smallest eigenvalue for some ΣH,h . Then, if c 0 v min ∈ B S h V := {B S h V : V ∈ V} for some non-zero c 0 , IV(V) ≥ mins h d π b (s h ) σmin(Σ H,h ) .The proposition states that as long as min s h d π b (s h ) is bounded away from 0 (which is benign and helps bound the Dr V [d πe , d π b ] term) and V is sufficiently rich that B S h V includes a certain vector in R S , then boundedness of IV(V) requires bounded 1/σ min (Σ H,h ), which is stronger than our belief coverage assumption. This renders the split between IV(V) and Dr V [d πe , d π b ] superficial and perhaps unnecessary.Proof of Proposition 10. Since c 0 v min ∈ {B S h V : V ∈ V}, there exists V such that B S h V = c 0 v min . For such V , we observe thatE π b B H V (τ h ) 2 = τ h d π b (τ h ) ⟨b(τ h ), c 0 v min ⟩ 2 = c 2 0 v ⊤ min Σ H,h v min = σ min (Σ H,h )c 2 0 .andE π b B S V (s h ) 2 ≥ min s h d π b (s h ) • ∥c 0 v min ∥ 2 2 = min s h d π b (s h ) • c 2 0 . Therefore E π b [(B S V ) (s h ) 2 ] E π b [(B H V ) (τ h ) 2 ] ≥ min s h d π b (s h ) • c 2 0 σ min (Σ H,h )c 2 0 = min s h d π b (s h ) σ min (Σ H,h) .It suffices to showΣ H,h 1 = E π b [b(τ h )b(τ h ) ⊤ ]1 = E π b [b(τ h )b(τ h ) ⊤ 1] = E π b [b(τ h )] = b π b h .The key is to notice that (b πe h ) ⊤ is non-negative, so(b πe h ) ⊤ Σ -1 H,h b πe h ≤ (b πe h ) ⊤ |Σ -1 H,h (b πe h )| (| • | is pointwise absolute value) ≤ (b πe h ) ⊤ 1 • ∥Σ -1 H,h (b πe h )∥ ∞ (using the non-negativity of (b πe h ) ⊤ again) = ∥Σ -1 H,h (b πe h )∥ ∞ .According to Eq. ( 5), we use L 1 /L ∞ Hölder's inequality and obtain that for any f h|V F (f h )| ≤ u(f h ) Z R (f h ) 1 (Σ R F ,h ) -1 V πe S ∞ = R + (f h ) u(f h ) Z(f h ) 1 (Σ R F ,h ) -1 V πe S ∞ ≤ R + (f h )C F ,∞ ≤ HC F ,∞ .The second inequality is from Assumption 9 and u(f h ) Z(f h ) is a stochastic vector. The last step is from the boundedness of the reward.We use diag(•) both for creating a diagonal matrix with an input vector and for taking the diagonal vector out of a matrix.Σ R F ,h 1 = M F ,h (Z R h ) -1 M ⊤ F ,h 1 = M F ,h (Z R h ) -1 diag(Z h ) ⊤ = M F ,h R + h = V πe S .The calculation is similar to that of Example 2 in Appendix D.3, except that the numerator has an extra R + (f h ). Therefore, when calculating the i-th diagonal entry of Σ R F ,h , the final sum is calculating the expectation of R + (f h ) conditioned on s h = i under policy π b , which is the definition of V π b S (i).In the proof of Theorem 2, we haveH h=1 E π b (B H V )(τ h ) 2 ≤ 10ε stat , ε stat := 225H C2 log(4|V||Ξ|/δ) n .We observe thatE πe (B S V )(s h ) = E τ h ∼d πe h E s h ∼b(τ h ) (B S V )(s h ) = E πe (B H V )(τ h ) = E π b w ⋆ (τ h )(B H V )(τ h ) ≤ ∥w ⋆ ∥ 2,d π b h E π b (B H V )(τ h ) 2 ≤ C H,2 E π b (B H V )(τ h ) 2The third equality is from Definition 10, the first inequality is from Cauchy-Schwarz inequality and the last inequality is from Lemma 6. Then, we haveH h=1 E πe (B S V )(s h ) ≤ H H h=1 E πe (B S V )(s h ) 2 ≤ 10HC H,2 ε stat ≤ 50H C C H,2 C µ log(4|V||Ξ|/δ) n ≤ cH 2 (C F ,∞ + 1) C H,2 C µ log(4|V||Ξ|/δ) n .The last step is from Lemma 5, C V ≤ c∥V F ∥ ∞ and C Ξ ≤ c(∥V F ∥ ∞ + 1). The proof is completed after invoking Lemma 1.Finally, we prove Theorem 9. The proof uses the similar idea from Xie and Jiang [2020] . For any V ∈ V and w ∈ W, we define the population loss estimator L d π b and the empirical loss estimator L D as followsL d π b (V, w) := H h=1 E π b w(τ h )(B H V )(τ h ) L D (V, w) := H h=1 E D [w(τ h ) (µ(o h , a h ) (r h + V (f h+1 )) -V (f h ))] .We then invoke Lemma 1 and obtain thatJ(π e ) -E π b [ V (f 1 )] = H h=1 E s h ∼d πe (B S V )(s h ) .We observe thatE s h ∼d πe (B S V )(s h ) = E τ h ∼d πe E s h ∼b(τ h ) (B S V )(s h ) = E τ h ∼d πe (B H V )(τ h ) = E π b w ⋆ (τ h )(B H V )(τ h ) ,where the last step is from Definition 10. Therefore, our goal is to boundH h=1 E π b w ⋆ (τ h )(B H V )(τ h ) = L d π b ( V , w ⋆ ) . Let w := argmin w∈sp(W) max V ∈V H h=1 E π b (w ⋆ (τ h ) -w(τ h )) • (B H V )(τ h ) , V := argmin V ∈V sup w∈sp(W) H h=1 E π b w(τ h ) • (B H V )(τ h ) .Then, we subtract the approximation error of w from our objective,H h=1 E π b w ⋆ (τ h )(B H V )(τ h ) = H h=1 E π b (w ⋆ (τ h ) -w(τ h )) • (B H V )(τ h ) + H h=1 E π b w(τ h ) • (B H V )(τ h ) ≤ H h=1 E π b (w ⋆ (τ h ) -w(τ h )) • (B H V )(τ h ) + H h=1 E π b w(τ h ) • (B H V )(τ h ) ≤ ϵ W + H h=1 E π b w(τ h ) • (B H V )(τ h ) .Next, we consider the approximation error of V and obtain thatH h=1 E π b w(τ h ) • (B H V )(τ h ) = ϵ V + H h=1 E π b w(τ h ) • (B H V )(τ h ) -sup w∈sp(W) H h=1 E π b w(τ h ) • (B H V )(τ h ) . We then connect L d π b (V, w) with L D (V, w) as follows, H h=1 E π b w(τ h ) • (B H V )(τ h ) -sup w∈sp(W) H h=1 E π b w(τ h ) • (B H V )(τ h ) ≤ sup w∈sp(W) H h=1 E π b w(τ h ) • (B H V )(τ h ) -sup w∈sp(W) H h=1 E π b w(τ h ) • (B H V )(τ h ) = max w∈W L d π b ( V , w) -max w∈W L d π b ( V , w) = max w∈W L d π b ( V , w) -max w∈W L D ( V , w) + max w∈W L D ( V , w) -max w∈W L d π b ( V , w) ≤ max w∈W L d π b ( V , w) -max w∈W L D ( V , w) + max w∈W L D ( V , w) -max w∈W L d π b ( V , w) ≤ max w∈W L d π b ( V , w) -L D ( V , w) + max w∈W L d π b ( V , w) -L D ( V , w) .The first equality is from that sup w∈sp(W) |f (•)| = max w∈W |f (•)| for any linear function f (•). The second inequality is from the optimality of V .For any fixed V, w, let random variableX = H h=1 w(τ h ) (µ(o h , a h )(r h + V (f h )) -V (f h+1 )), E π b [X] = L d π b (V, w). Recall that C V := max V ∈V ∥V ∥ ∞ and C W := max h sup w∈W ∥w∥ ∞ . For |X|, we have |X| ≤ 2HC µ (1 + C V )C W . For the variance, we have Var π b [X] ≤ H H h=1 E π b w(τ h ) 2 (µ(o h , a h )(r h + V (f h+1 )) -V (f h )) 2 ≤ H H h=1 E π b w(τ h ) 2 2C 2 V + 2(1 + C V ) 2 µ(o h , a h ) 2 ≤ 4H 2 (1 + C V ) 2 C µ C 2 W .From Bernstein's inequality, with probability at least 1 -δ, we have|L d π b (V, w) -L D (V, w)| ≤ 2H(1 + C V )C W C µ log 2 δ n + 2H(1 + C V )C W C µ log 2 δ n .Taking the union bound and we obtain ≤ 4H(1 + C V )C W C µ log 2|V||W| δ n + 4H(1 + C V )C W C µ log 2|V||W| δ n .According to Lemma 5, Assumption 12, C V ≤ c∥V F ∥ ∞ and C W ≤ c∥w ⋆ ∥ ∞ , we further haveJ(π e ) -E π b [ V (f 1 )] ≤ ϵ V + ϵ W + cH 2 C H,∞ (C F ,∞ + 1) C µ log 2|V||W| δ n + cH 2 C H,∞ (C F ,∞ + 1)C µ log 2|V||W| δ n .The proof is completed by using Hoeffding's inequality to bound|E D [ V (f 1 )] -E π b [ V (f 1 )]|.• It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.Here we do not allow the policy to depend on the latent state, which satisfies sequential ignorability and eliminates data confoundedness; seeNamkoong et al. [Section 3;2020] andUehara et al. [Appendix B; 2022a]. There is also a line of research on OPE in confounded POMDPs where the behavior policy only depends on the latent state[Tennenholtz et al., 2020, Shi et al., 2022]; see Appendix A.We let V (fH+1) ≡ 0 for all V to be considered, so that we do not need to handle the H-th step separately.The value of c can differ in each occurrence, and we reserve the symbol c for such absolute constants.All covariance-like matrices in the paper, such as M F ,h M ⊤ F ,h here, are invertible under Assumption 2.Recent offline RL theory indeed employed such definitions[Xie et al., 2021, Song et al., 2022], but that is after we developed mature understanding of their properties, such as being upper bounded by density ratios.When h ≤ M no dropping is needed. In fact, if we never drop, then m h = τ h is just the history.b(τ h ) has a "block one-hot" structure, where the block of size S indexed by m h (τ h ) is equal to b(τ h ), and all other entries are 0. 


Decision: This paper presents innovative coverage assumptions for Off-Policy Evaluation (OPE) in the Partially Observable Markov Decision Process (POMDP) setting. Unlike the naive coverage coefficient definition, these new coefficients do not exhibit a direct exponential dependence on the POMDP's horizon. Building upon these quantities, the authors develop sample-efficient OPE algorithms tailored to this setting.

Currently, the proposed algorithms are only sample efficient and their practical usefulness seems currently limited. Nevertheless, this work is a significant advancement in the OPE for POMDPs setting;  a challenging and highly relevant problem in real-world applications. The proposed approach has the potential to facilitate the design of practical OPE algorithms for POMDPs and offer researchers a fresh perspective on addressing existing challenges in POMDPs. Therefore, I am pleased to support the acceptance of this work.

Reviews: review: paper_summary: paper_summary: This paper studies off-policy evaluation in POMDPs and introduces two novel coverage concepts: outcome coverage and belief coverage. Outcome coverage uses a weighted norm to ignore unimportant futures in future-dependent value functions. Belief coverage is related to the covariance matrix of belief states under the behavior policy. The paper argues that these conditions are sufficient for the reward of the evaluation policy to be close to the estimated value function for the dataset generated by the behavior policy.
strength_weakness: strength_weakness: The paper's main weakness is that it targets a very limited audience of theoreticians only. There is extremely little text providing intuition or any sort of motivation for the research questions, approach or solution.

Despite significant familiarity with off-policy evaluation, importance sampling, POMDPs, etc., I was unfortunately unable to:
- follow most of the paper,
- understand the main questions being asked,
- see what this would be useful for,
- evaluate the reasonableness of the assumptions,
- check the proofs,
- appreciate the consequences of the results.

In short, if the paper is intended to be read by anyone outside of a very limited audience, it will need to be substantially rewritten so as to be much more accessible. I'm not even sure if my summary is correct.
questions: questions: Can the authors please provide a summary of the work that a non-theoretician might understand and appreciate if they have a strong background in the empirical side of the relevant concepts?
limitations: limitations: N/A
paper_summary: paper_summary: This paper studied the finite sample guarantee of future-dependent value function (FDVF) based method for policy evaluation problem in POMDPs. The existing guarantee depends on the boundedness of the FDVF which can be exponential in horizon. The authors studied this quantity and proposed new coverage assumptions with intuitive explanation under which FDVF can be well-bounded achieving polynomial guarantee on model parameters. Besides, they also quantified a conversion ratio between Bellman residual on states and history.
strength_weakness: strength_weakness: 1. For the boundedness of FDVF, there isn't a clear discussion on the strictness of the assumptions in all cases except in some intuitive examples. A claim that $C_{\mathcal{F}, V}$ is polynomially bounded in all cases is needed.
2. To claim a fully polynomial guarantee, the paper didn't discuss on $C_\Xi$, though it also appears in the sample guarantee and can dominate $C_{\mathcal{V}}+1$.
questions: questions: See weaknesses.
limitations: limitations: See weaknesses.
paper_summary: paper_summary: This paper addresses off-policy evaluation in the context of POMDP, aiming to develop estimators that avoid exponential dependence on the horizon. Paper introduces two novel coverage assumptions --- outcome coverage and belief coverage --- tailored to POMDPs to achieve polynomial bounds on estimation guarantees. Specifically, outcome coverage ensures boundedness of future-dependent value functions (FDVF) which targets the shift from $\pi_b\rightarrow\pi_e$, while belief coverage deals with IV ($\mathcal{B}^\mathcal{H}\rightarrow\mathcal{B}^\mathcal{S}$) and Dr ($\pi_b\rightarrow\pi_e$) jointly. The work leverages unique properties of POMDP coverage conditions, avoiding explicit dependence on the latent state space size. The MIS algorithm is proposed to provide interpretations concerning the sample complexity under theses new assumptions.
strength_weakness: strength_weakness: Minor:  I appreciate this work as a theoretical contribution. It would be even more promising if some preliminary experiments were conducted, as OPE using such a history weight function is a novel idea and its empirical performance cannot be anticipated.
questions: questions: - As pointed out in the title, FDVF is the key tool to deal with OPE for POMDPs. I wonder if the authors could comment more on why such "future-dependence" is necessary to deal with partial observation? 
- From my intepretation, it seems that $L_\infty$ assumptions should be looser ones and can better accomodates the PO. Why are the $L_2$ assumptions emphasized, or do they offer any unnoticed benefits?
- Minor: in line 312, should it be $d^{\pi_e}$?
limitations: limitations: The proposed method is limited to handling memoryless policies and history-dependent policies with structured constraints, but this limitation does not hurt the paper's contributions considering the hardness explained in the appendix.
paper_summary: paper_summary: This paper proposes new off-policy estimators for POMDPs without exponential variance with the horizon. Specifically, outcome coverage and belief coverage are assumed which capture the past and future information, respectively. This framework reduces the estimation guarantees from exponential to polynomial.
strength_weakness: strength_weakness: 1. The new algorithm in Section 5.3 has not been studied thoroughly with experiments.
questions: questions: 1. Is it possible to extend the analysis to infinite horizon?

2. Can you justify the full row rank assumption in Assumption 2?
limitations: limitations: The authors addressed the limitations in Section 6.

Comments: comment: I appreciate the authors' efforts on the rebuttal. The elaboration sounds reasonable to me and I would like to increase my score to 6.
Thank the authors for the response. I am maintaining my score.
Thanks for the response. I perhaps spoke too strongly about what I called the very limited audience. Let me amend my statement to simply say that this paper does not feel accessible to me, despite the fact that I am a practitioner with experience in many of the areas discussed here, and with plenty of theory knowledge as well (just not this kind of theory). This feels like a disadvantage for the paper, and it's unfortunately the only aspect I can comment on. There are theory papers I've read that don't feel this way, and I would encourage the authors to try their best to make this work as accessible as possible.
I thank the authors for the detailed response. I am maintaining my original score and remain in favor of acceptance.