On the Curses of Future and History in Future-dependent Value Functions for Off-policy Evaluation
Authors: Yuheng Zhang
Nan Jiang
Venue: NeurIPS 2024 poster (2024)
Keywords: Partially Observable Markov Decision Process; Offline Policy Evaluation; Reinforcement Learning Theory
Primary area: learning_theory

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.

On the Curses of Future and History in Future-dependent Value Functions for OPE
Yuheng Zhang University of Illinois Urhmna-Champaign yuhengz20111inois edu
Nan Jiang
University of Illinois Sibana-Champaigee nanjiang@illinet edu
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 -nn-gggthhh and thus erasing the advantage of the method. In this paper, we discover novel coverage assumptions tailored 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 the discovery of new algorithms with complementary properties.
Introduction and Related Works
Off-policy evaluation (OPE) is the problem of estimating the return of a new evaluation policy we based on historical data, which typically collected using a different policy Ty (the behavior policy). OPE plays 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 01, an 02, a2...., on, an, the cumulative importance weight is I x_ (o.)
Kalax ox."* whose variance grows exponentially with the horizon, unless Ta and n. very close in their action distributions. In the language of offline RL theory (Chen and Jiang 2019] Xie and Jiang, [202T] Yin and Wang 2021] the boundedness of the cumulative importance weights the coverage assumption required by IS, very stringent one.
Alternatively, algorithms such as Fitted-Q Evaluation [FQE; Erntt et al. 2005 Munos and Szepesvári 2019] and Marginalized Importance Sampling [MIS; Liu et al. 2018 Xie et al.) 2019
2008 Le et al.
2019 Uehara et al.) 2020] enjoy more favorable coverage assumptions, at the cost of (unction-approximatto biases. Instead of requiring bounded cumulative importance weights, FQE and MIS only require that of the -tate-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 on is a state), the guarantees of FQE and MIS only depend on the range of d', (o,)) (ow), where de and d is the marginal distribution of oz under ne and π, respectively.
Nachum et al.
In this paper, we study the non- Markov setting, which ubiquitous in real-world applications. Such environments are typically modeled as Partially Observable Markov Decision Processes (POMDPs)
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Kaelbling et al. [1988. 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, (01, .1..... 0h.). Unfortunately, close inspection reveals the problem: the state-density ratio after conversion is
(01, COl,,,...,,0
0
II A==1
h-1
Te (an low)
( (0) 01 0%)
Th (ow)
which is exactly the cumulative importance weights in IS and thus also an exponential object!
To address this issue. Uchara et al. [202aa] recently proposed a promising framework called future- dependent value functions (or FDVF for short). Notably, their coverage assumption is the boundedness of density ratios between Te and т. over the latent state for memoryless policies. This is as if we were dealing directly with the latent MDP underlying the POMDP, 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 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 novel coverage concept called outcome coverage is sufficient for guaranteeing its boundedness (Section 4). Notably, outcome coverage concerns the overlap between тT and from the current time step onward, whereas all MDP coverage assumptions concern that before the current step.
With another novel concept called belief coverage (Section 5.1) }. we establish fully polynomial estimation guarantee for the algorithm in Uehara et al. [202aa] 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 linear MDP coverage (Duan al.] 2020 due the linear-algebraa structure, these POMDP coverage conditions also have their own unique properties due to the L 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.2p.
2 Preliminaries
POMDP Setup. We consider a finite-horizon POMDP ( -H
On, O,, R,O,T, R, = - Sn, -
where H is the horizon, Sn is the latent state space at step h with S A. the action space with |A| A, On is the observation space step h with |O,1 0, R: x [0, 1] is the reward function, O : S + A(O) is the emission dynamics with O(-[s)) supported on O₂ for 8h Sp. T: S x - A(S) the dynamics (T(-Is), an) is supported Sa+1), and di A(S) is the initial latent state distribution. For mathematical convenience we assume all the spaces are finite and discrete, but the cardinality of Or, O, can be arbitrarily large. A trajectory (or episode) is sampled as
d1, then o ~ O(-[s)). = R(on, on). $h+1 T(-|sh, ax) for 1 < h < H, with f1sb decided by the decision makiing agent, and the episode terminates after ag. $1:H are latent and not observable to the agent.
History-future Split. Given an episode 01, 01,..., OH, az and time step h of interest, it will be convenient to rewrite the episode as
(Th, , Oh, an fn+1).
Here Tn (0), a.... Oh ap-1) E HA h-1 (On A) denotes the historical observation- action sequence (or simply history) prior to step h. and fr+1 (oh+1s 0h+1y 0H aH) E "1 - (On x A) denotes the future after step h. This format will be convenient for
-
Fa+1

---

reasoning about the system dynamics at step h. We use H. - - Hr to denote the entire history domain and use F = Fh to denote the entire future domain. This way can use stationary notation for functions over S. O H. F, where the time step can be identified from the function imput (e.g., R(o,, (n)), and functions with time-step subscripts refer to their restriction the h-th step input space, often treated as a vector (e.g,, R E BOxxAA.
Memoryless and History-dependent Policies. A policy U.- (H,, x O - A(A) specifies the action probability conditioned on the past observation-actio restrict ourselves to memory-less (or reactive) policies that only depends on the current observation oni extension to general policies is similar to Uchara et al. (2022a) and discussed in Appendix[B.8 For any π, we use Pr, and E, for the probabilities and expectations under episodes generated by म, and define For memoryless T, we also
sequence In the main text, we will
(IT) as the expected cumulative return: (TT := IE,,, Σ> h= Rion, aid)
define V (#k) as the latent state value function S4: Vg (8%) == E, [0, H). d' (s%) denotes the marginal distribution of 8n under и.
Ew== R(ow, awr) 8% E
Off-policy Evaluation. In OPE, the goal is to estimate ((Te) using n data trajectories D [n]] collected using mh. We write Ep|:] denote empirical approximation of expectation using D. Define the one-step action probability ratio plon, aq)
(6) (6) (lof)) aj .1(") HH aH .TH
(enlon) We make the following assumption throughout:
(a low)
Assumption 1 (Action coverage). We assume (a lox) is known and max plon, an) S Cp.
This is standard assumption the OPE literature, and is needed by IS and value-based estimators that model state value functions Diang and Li. 2016 Liu et al. 2018).
Belief and Outcome Matrices. We now introduce two matrices of central importance to our discussions. Given history The we define b(T.) E R$ as its belief state vector where b;(Tx) Pr(sn, = i|Tx). Then the belief matrix Ma.h E SxHa is one where the column indexed by Th E Hr b(Tr). Similarly, for future Sh. we define u(fa) RS as its outcome vector where [u(fi)]; = Prxs (fr i). The outcome matrix MF,a E RXJ%, is one where the column indexed by fa is u(fa). Unlike the belief matrix, the outcome matrix MF.1 is dependent on the behavior policy Te. which is omitted in the notation.
For mathematical conveniences, we make the following assumptions throughout merely for simplify- ing 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). vh [H], (1) rank(MH.N. rank (,,, S. (2) Vs. Prz, (fa) > 0; Von, On. R(or. an.) > O.
Other Notation. Given vector a, ||a||s: == Va VaTEa Ea, where Σ is positive semi-definite (PSD) matrix. When == diag(d) (d) for a stochastic vector d, this is the d-weighted 2-norm of a, which we also write as ||a||a.d- For positive integer m, use [m]] to denote the set {1,2, ... m]. For matrix M, we use (M) to denote the ij entry of M.
3 Future-dependent Value Functions
In this section, we provide recap of FDVFs and translate the main result of Uchara 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 would like apply the same idea to POMDPs,
Herre we do not allow the policy to depend on the latent state, which satisties sequential ignorability and eliminates data confoundedness; see Namkoong et al. (Section 3: 3:2220) and Uehara et al. (Appendix B; (:(202aa There is also line of research on OPE in confounded POMDPs where the behavior policy only depends on the latent state Tennenholtz al. 2020
Shi al. 2022 see Appendix
3

---

Mistory-dependen value functions lead to unfavorable coverage conditions (see Section T. The only other known notion of value functions we are left with is that over the latent state space, V (s)). which unfortunately is not accessible to the learner since it operates on unobservable latent states.
The central idea is to find observable proxies of - (8h). which takes future as inputs:
Definition 3 (Future-dependent value functions (Uchara et al. 2022aa): ). A future-depender value function VF= F 12, where F == Un Fh. any function that satisfies the following: Vsh. Em, (f.) sh V (sn). Equivalently, in matrix form, we have Vh,
MF VV, = S.k
Recall our convention, that Vy [RI is Vi restricted Fr. and S.h. is defined similarly.
A FDVF Vi is property of rT., but also depends on Th- As we will see later in Section the boundedness of Vy will depend on certain notion of coverage of my over we- As another important property, the FDVF V> is generally not unique even if we fix T.e and Tb. Eq. is generally an underdetermined linear system (S < [i D and can yield many solutions. As we see below, it suffices to model any one of the solutions. Thus, from now on, when talk about the boundedness of Vz, we always consider the V 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), VV : F R, the Bellman residual on state sn is
(B (ss)) == E Bi [In + v(f++1) sn] Em, (fh) sn).
Similarly, the Bellman residual onto the history Ty is: (8* (TT)) == EE anoTTe [ra + ((f++1) Th] (fhh) Tm] (b(T)),B) (2) 46-18-0
The following lemma shows that, ideally, we would want to find V with small B Lemma 1. For any Tes Th. and V F + J. (x)(V(()) Σ Er. VBs))
See proof in Appendix C.1 As the lemma shows, any V with small B (such as V7, since B+V; = 0) can be used to estimate J(Te) via Ez, [V()) But again, B operates on S which unobserved, and we turn to its proxy BHH which are linear measures of B (Eq More concretely, Uchara et al. (2022a) proposed to estimate IE,, (B%VV² using an additional helper class :: H + R to handle the double-sampling issue [Antos et al. 2008
Dai al. 2018:
V argmin max
> (V,
H
VEV EEE
where (V, = assumptions, the estimator enjoys a finite-sample guarantee:
on) -[VVE)==-((((a))) Epk(u(an,
-0.5) Under the following
Assumption 5 (Realizability). Let V c (F R) be finite function class. Assume Vy E V for some Vy satisfying Definition S
Assumption 6 (Bellman completeness). Let E (H -> R) be finite function class. Assume B E E, vV E
Theorem 2. Under Assumptions and w.p. 2 8
C. log [E
[( < cHf max +1 IV(V)DrvVV"" d
n where e is an absolute constant Hand Cy == maxvey loo, Cs == maxce= IKEl
Em (BSV) (sn)a] E., (B*V) (T.)2] Dry dd j max sup h Vev
Ex_ (BSV) (sN)a] E., (BSV) (sn)²
IV(V) max sup h VEV
We v(f++1) = for V to be considered, so that we do not need to handle the H-th step separately. 'The value of can differ in each occurrence, and reserve the symbol e for such absolute constants.

---

See proof in Appendix C expected (e.g., horizon H. the complexities function classes log EI. etc.). We now focus on the important ones, which reveals the open questions we shall investigate next:
Among the objects that appear in the bound, some are mundane and
1. Dryld d measures the coverage of TT over on the latent state space S, as the expression inside square-root can be bounded by maxs,, d= (sh)/ddo (sh).
(Q1) Cy is the range the V class. Since Vy E V (Assumption Cv 2 |V However, unlike the standard value functions in MDPs which have obviously bounded range [0, H (this also applies to ") the range of V is unclear. Similarly, since 3gr needs to capture B*V for V E V. the boundedness of also affected.
3. (Q2) IV(V) appears because we use B as a proxy for BSV, which is only a linear measure of the latter, (TT)) (b(T)), B,, (V()) reflects the conversion ratio between them. Uchara et al. 2022a| pointed out that the value is finite if Mx.h has full-row rank (S), but a quantitative understanding is missing.
The rest of the paper proposes coverage assumptions, analyses, and algorithms to answer the above questions, providing deeper understanding on the mathematical structure OPE POMDPs
4 Boundedness of FDVFs
We start with Q1: when are FDVFs bounded? Recall from Definition 3 that FDVF at level h, Vy is any function satisfying & x Vy.a = V where My is the outcome matrix with (Mr, = (fn,(fn = 8n = i). Since the equation can have many solutions and we only need to find one of them, suffices provide an explicit construction of VF, and show it is well bounded. Also note that the equations for different h are independent of each other, so we can construct VF. for each 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 | which scales with 1/amin (Mr,),, which we show shortly is exponential-in-lein quantity. However, it is not hard to notice that in certain benign cases, Vi does not have to blow-up exponentially and has obviously bounded constructions.
As a warm-up, consider the on-policy case of mh = ne, where a natural solution is V)((fi) = R (fr) == Ed=,, R(ops,aao a.)). Here R (fr) simply adds up the Monte-Carlo rewards in future fh- which is bounded in [0. H). The construction trivially satisfies E.,, [V>(f)) st] = V (s%) when Te Te- In the more general setting of N6 # we, the hope is that Vr can be still bounded up to some coverage condition that measures how Te deviates from Tb.
Unfortunately, generalizing the above equation to the off-policy case raises issues: consider the =e(eg)lo,))
solution V=(ff) = R+ (fr) II Ts(anrlow) [o whose correctness 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.
Another direction is to simply treat [ as a linear system. Given that the system is under-determined, we can use pseudo-inverse VF Mf, (MF,MMF.) V. In this case, <| can be bounded using 1/m (Mr,))) where amin denotes the smallest singular value. In fact, closely related quantities have appeared in the recent POMDP literature; for example, in the online setting, Liu al. [202aa] used amin of action-conditioned variant of My complexity parameter for online exploration in POMDPs. Unfortunaelly, these quantities suffer from scaling issues: mim (My,r. is guaranteed to be mishehaved if the process is sufficiently stochastic.
Pseudo-inverse Solution.
Example 1. Pr. (falsH) S
Cast (oA) KTY Vfn. Sh, then mmin ( (MF S Czoch V5/(OA)
H 8-641
'All covariance- matrices in the paper. such Mr MM.ME here, are invertible under Assumption 2
5

---

In this example, Cstoch measures how the distribution of fn under Tu deviates multiplicatiell from uniform distribution over Fr. and an even moderately stochastic Tu and emission process O will lead to small Cuuch. which implies an exponentially large 1/0min //minnM7,n MM,.).
4.1 Minimum Weighted 2-Norm Solution and Lg Outcome Coverage
Pseudo-inverse finds the minimum L2 norm solution. However, given that we are searching for solutions in I which has an exponential dimensionality, the standard L2 norm-which treats all coordinates equally-is not a particularly informative metric. Instead, we propose to minimize the weighted L2 norm with particular weighting scheme, which has also been used in HMMs al. 2023 and enjoys benign properties.
(Mabajan
We first define the diagonal weight matrix Zn == diag( (15 (Myr,.), where 1s E IR. = =1, 1,,.. _1] is the all-one vector. Then, the solution that minimizes
2| is:
V M ET S.h. where Σx,, M M
EF, E RSS plays an important role in this construction. Recall that its counterpart in the pseudo- inverse solution, namely MF.MM. A.- has scaling issues (Example 1 that even its largest eigenvalue can decay exponentially with H - h + 1. In contrast, Σy,,, is very well-behaved in its magnitude, as shown below. Furthermore, while MJ,, on the left is now multiplied by Z which can be exponentially large, Z MT together still well-behaved; see proof in Appendix D.2
Proposition (Properties of Eq.44), 1. Σy is doubly-stochase is non-negative and sums up to L. As consequence, mmax (E,,) =. 2. Rows of ZT Jo Le., {u(fx)] /Z(f)) fa. E Fr), are stochastic vectors, i.e., they are non-negative and the row sum is 1.
that is, each row/column EF
Therefore, it is promising to make the assumption that miin (Ex,) is bounded away from zero, which immediately leads to the boundedness of Vy given that of 2 MT, ((0, 1)) and V ((,, H). However, we need to rule out the possibility that Ei,,, is always near-singular, and find natural examples that admit large miin (SF,A), as given below.
Example 2. Suppose fn always reveals Sh, in the sense that for any j E Fh, Pr., (fn = = only nor-zero for a single E [S), and zero for all other latent states. Then, Σr,h = I, the identity matrix. Furthermore, Vy from Eq. 4 satisfies || floo S H. See Appendix D.3 details.
The example shows an ideal case where T (E) = maax (Ef,)) 1, when the future fully determines 8h. This can happen when the last observation on reveals the identity of an earlier latent state 8h. Note that in this case, a M,,n 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, Σx, is the confusion matrix of making posterior predictions of sh from fn based on uniform prior over St. (see Appendix B.8 for how to incorporate different priors) with u(fn) (f())) being the posterior, and 0 m (EF,,) serves as a measure of how the distribution of future fú. helps reveal the latent state 8).
We now break down the boundedness of Eq. 4p into more interpretable assumptions. Assumption 7 (L2 outcome coverage). Assume for all h. VIV 1 E2 S CC.V
Assumption 8 (EF,, regularity). Assume for any fu:
SFFUU.
Proposition 4 (Boundedness of FDVF). Under Assumptions 7 and 8 Vy in Eq satisfies || <
VCr.2 CC Furthermore, when only Assumption holds. | S /C,v, Vh.
See proof in Appendix D.4 Assumption requires that the weighted covariance matrix Σye, A covers the direction of S. well. As a sanity check, it is always bounded in the on-policy case:
Example 3. When Na = ne. V < HVS.
Notably, mathematically similar coverage assumptions are also found in the linear MDP literature. For example, with state-action feature O% for time step h, very tight coverage parameter for linear

---

o Zanette et al. 2021 Despite the mathematically similarity, there are important high-level differences between these notions of coverage:
MDPs is ||E [onll
1. 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 Vy (which MDP coverage does not explicitly depend on). In Section 5 will discuss other coverage assumption (belief coverage), which is more similar to the MDP coverage in that they are both concerned with the past.
The linear MDP coverage assumption is refinement of state-density ratio using the knowledge of the function class [Chen and Jiang 20199 [Song et al. [022]. In comparison, the linear structure of our outcome-coverage assumption comes directly from the internal structure of POMDPs.
4.2 Addressing S dependence via Li Loo Hölder and Los Outcome Coverage
Example shows that even in the on-policy case, CF may depend on S which makes the assumption only meaningful for finite and small S. In fact, showed earlier that VF R is a natural and
obvious -bounded solution for тh = Te. but this is not recovered by the construction in Eq. (4)
We also need an additional regularity Assumption 8
As turns out, these undesired properties arise because L2 which is natural for linear MDP
settings mentioned above-fails to leverage the L1 normalization of u(fx) /Z(fi) (Proposition 4
Claim 2) and is loose for POMDPs; see Appendix B.5 for further details. A better choice is
L Hölder, motivating the Lo coverage assumption below, which requires slightly different
construction of Vy. These definitions may seem mysterious or even counterintuitive; it will be easier explain the intuitions when get to their counterparts for belief coverage in Section 5.2
Construction of Vi= Define Z nd (fr))) == (fh)) (fr), and we use n to replace Z in Eq.
VF = (Z ( - VVS.. where E == (Z M7,
(5)
Assumption 9 (Lx outcome coverage). Assume for all h. (( 1lo0 S C7
Lemma 5. Under Assumption
|| S HCF,00. See proof in Appendix E.7
In Appendix B.5 we show that the construction shares similar properties to Eq. 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 Vy R. a property that Eq.(4) does not enjoy; see Appendix E.8 details.
1, thus Assumption holds with C7 1 (c.f. Cr.v S HVS in Example 3). Furthermore, the construction in Eq. is exactly Vy = R+.
Example 4. When Te Th, (E
5 Effective History Weights and A New Algorithm
We now turn Q2 in Section
which asks for a quantitative understanding of the IV(V) term. Note that IV(V) and Dry [dm d taken together, are to address the conversion between:
(We minimize:)
[B,
(We want to bound:) |E,, (B V)
(6)
The two terms differ both in the policy (Th - T.) and the operator (8 + BS). While we could directly define a parameter by taking the worst-case (over V E V) ratio between the expressions the real question is to provide more intuitive understanding of when it can be bounded.
Towards this goal. Uchara et al. which take care of the B respectively. While this leads to intuitive upper bound of the Te me conversion parameter in
2022a split the above ratio into two terms, IV(V) and Dry d B conversion (under Tτ) and π& >> Te conversion (under BS).
terms of latent state coverage, the nature of the B + BS conversion, IV(V), remains mysterious.
'Recent offline RL theory indeed employed such definitions Xie et al. 2021 Song et al. 2022 but that is after developed mature understanding of their properties, such being upper bounded by density ratios.
7

---

In this section, we take a different approach by directly providing an intuitive upper bound on both conversions altogether, under novel belief coverage assumption. In Appendix E.44 we will also revisit the split into (V()) and Dry[d d= in the absence of strong structures from V. the boundedness of IV()) turns out to require an even stronger version of belief coverage, rendering the split unnecessary. Furthermore, our approach also leads to novel algorithm for estimating J(xe)
that replaces Bellman- Bellman-completenn completeness (Assumption 6) with a weight-realizability assumption, similar to MIS estimators for MDPs [Lu et al. 2018 Uchara et al. 2020
5.1 Effective History Weights
The key idea in this section is the notion of effectivve history weights, that perform the Tb - ne and 8 - B conversions jointly.
Definition 10 (Effective history weights), An effective history weight function w" H - I is any function that satisfies: vV E V. h [H],
Em, [w" V())())))(T)) E.,. [ V))
We first see that well-bounded w² immediately leads to a good conversion ratio for Eq.(6):
Br [(B))
[w" (T,) S V /Er. [w- (T.)"))
where the inequality follows from Cauchy-Schwerr for r.v.'. Hence, all we need is ||=* ||="|l2,777 1l2.0,
v VE,, (Th) )), the m--eeighted 2-norm of w*, to be bounded, and we focus 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* (T.) = Pra, (7.)
(T..
I Na(aw noting that Er,,, [(B)] = E.,, [[T)] and importance weighting on xs(agglow)) low)
Th changes ET, to Ex... 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 better construction that bounded under a natural belief coverage assumption. Note that Def 10 can be written as:
Ex, [w" (bb))) 8 V) E.,, (MTT.).BB.))
where B V E RR$ is the Bellman residual vector for V on Sn. As sufficient condition (which is also necessary when V lacks strong structures, i.e., { V E V} spans the entire R$), we can find w" that satisfies: [ (Tx [TT))] = E,, (b(
b This is related to the mean matching
problem in the distribution shift literature [Gretton et al. 2009 Yu and Szepesvári] 2012). and standard solution is (Bruns-Smith et al. 2023
w" (Tr) b(T.) E
F b
(8)
where Σn, Er, d (bb(TTT))) (bT.)T and b," coincides with (sw))ss
The weighted 2-norm this solution is immediately bounded under the following assumption.
Assumption 11 (I2 belief coverage). Assume vh, |lb Il x.z CCH22
Lemma 6. Under Assumption 11 w" in Eq. { satisfies Yh, || S CH.2. See Appendix E.1
Assumption requires that the covariance matrix of belief states under ny covers be the average belief state under Te. As before, also check the on-policy case (see Appendix E.2
Example In the on-policy case (To Te). CH,2 S 1.
Algorithm Guarantee Now we have all the pieces to present a fully polynomial version of Theorem Sateemmm@mn Junder the proposed coverage assumptions. One subtlety is that the guarantee depends on Cy = maxvev [Vlloc, which is closely related to || since we require Vy E V, but they are not equal since can include other functions with higher range. To highlight the dependence of || on the proposed coverage assumptions, we follow Xie and Jiang [2020] to assume that the range the function classes is not much larger than that of the function needs capture. similar assumption applies for bounding Cz. The proof of the theorem is deferred to Appendix E.10
8

---

Theorem 7. Consider the same setting as Theorem 2 and let Assumptions 77 and hold. For some absolute constant e, further assume Cy I cllV for Vx in Eq. and C= S <llV + 1).
Wp. 2 1 1 5, (.())) EDIV & (C + 1)v Cr Cp log(v
In addition to H and complexities of [V] and |3], the bound only depends on the intuitive coverage
parameters: Cp (action coverage), Ch,2 (Lg belief coverage), and Cy (L outcome coverage).
5.2 Lo Belief Coverage
Assumption I1 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* |oo, which also helps understand Loe outcome coverage given
the symmetry between history and future. As alluded to Section 4.2 and Appendix [B.5] Ly Hölder is inappropriate for controlling the infinity-norm since it does not leverage the L, normalization of vectors in POMDPs. Instead, we propose the following decomposition based on L Lo Hölder:
|ww (T.)) S [[b(T.))l lla |>x,, by |loc || by co This way, we can immediately bound || ||
with the following assumption:
Assumption 12 (Lec belief coverage). Assume Yh, H 1 S CH.oo- Then 1lo S CHH
"H.h by 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,
D-1
go infinity if rescale X by small constant. First note that such a pathology cannot happen here because the random vectors (b(7+)) are L1- normalized and cannot be arbitrarily rescaled. Below we use a few examples to show that Σx, b% a very well-behaved quantity, and naturally generalize familiar concepts such as concentrability coefficient from MDPs [Munos] 2007, Chen and Jiang 2019 Uchara et al. 2022a].
We start by checking the on-policy case. Perhaps surprisingly, Si,h by has an exact solution:
Example When मे Tb. Ex,, bj 1. the all-one vector; see Appendix E.5 for the calculation. Consequently, Assumption 72 is satisfied with Ch,co = 1.
The next scenario considers when b(Tr) is always one-hot, i.e., histories reveal the latent state (this is analogous to Example 2 T. coverage reduces the familiar concentrability coefficient, the infinity-norm of density ratio as a standard coverage parameter:
Example 7. When b(TH) is always one-hot, | b
Il = max,, d= (8n)) (F
We can also calculate |b To ||= from Assumption 11, which equals E., (dd (sx) (d (sn)) (s in this h
"1-hot belief" scenario. Xie and Jiang 20200] show that this is tighter than max,, d (sn)/ d (sn). and this relation extends elegantly to general belief vectors in our setting:
Lemma 8.
11
$
|| bj Il.o See proof in Appendix E.6
5.3 New Algorithm
The discovery of effective history weights and boundedness also lead to new algorithm analogous
to MIS methods for MDPs [Uehara et al. 2020 The idea is that since Lemma D tellss us minimize
E,, [[B= () )]. which equals E., w (Th (B* V).))) from Def 10 we can then use another function class W C (H + IR) to model w*, and approximately solve the following:
argmin max -==1 Em, [B(T)
VEV WEW
which minimizes an upper bound of E.,, [w (B.) as long w* W C (H -). Since there is no square inside the expectation, there is no doublc-sampling issue and we thus do not need the = class and its Bellman-completenee assumption. The h-th term of the loss be estimated straightforwardly as
ED (w(Th) (p(on, an) (ra + -
(10)

---

We now provide the sumple-compledd analysis of the algorithm, using more general analysis that allows for approximation errors in and W.
Assumption 13 (Approximate realizablity). Assume
H
min max VEV
Σ
E. [T)(TT) (BH)] Srv:
H Emo (Tx) () ((B
inf max WEsp(W) VEV
S ew-
Instead of measuring how W and V capture specific constructions of Vy and w², the above approximation errors automatically allow all possible solutions by measuring the violation of the equations that define Vy and w*
We present the sample complexity bound of our algorithm as follows. Similar to Theorem 7 we assume that Cy= == maxvev ||V||> and Cw max, suPwew ||w]||> are not much larger than the corresponding norms of Vx 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 (Q. Assume 11 for w² in E.. Under Assumptions /2
that Cy cl for Vs Eq. (5). and Cw S cl w
and 13 w.p. 1 [mme) EDIV [V()]] sv + ew + cHH (CF,00 +1) Cj log Wi
As remark, there is also a way to leverage the tighter L2 belief coverage, despite that it does not guarantee bounded || and only || 2.47 In particular, if all functions W have bounded
II- -112.,. 2.4.. the estimator in Eq. (T)) will have bounded 2nd moment on the data distribution. this case, using Median-of-Me -feannsssss estimators [Lerasle 2019 Chen 2020 instead of plain averages for (0) 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 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 call the curse of memory. We suspect that structural policies are needed to avoid the curse of memory and leave this to future work.
Acknovledgements
Nan Jiang acknowledges funding support from NSF 11--1112471, NSF CAREER IIS-214178,, Google Scholar Award, and Sloan Fellowship.
References
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, 2008.
Kamyar Azizzadenesheli, Alessandro Lazaric, and Animashree Anandkumar. Reinforcement learning of pomdps using spectral methods. In Conference on Learning Theory, pages 193-256. PMLR, 2016.
David Bruns-Smith, Oliver Dukes, Avi Feller, and Elizabeth L Ogburn. Augmented balancing weights as linear regression. arXiv preprint arXiv:2304. 14545, 2023.
Fan Chen, Yu Bai, and Song Mei. Partially observable with b-stability: Unified structural condition and sharp sample-efficient algorithms. arXiv preprint arXiv:2209. 2022.
10

---

Jinglin Chen and Nan Jiang. cntomattiontthoreed considerations in batch reinforcement learning. In Proceedings of the 36th International Conference on Machine Learning, pages 1042-1051, 2019.
Yen-Chi Chen. A short note on the median-of-means estimator, 2020.
Bo Dai, Albert Shaw, Lihong Li, Lin Xiao, Niao He, Zhen Liu, Jianshu Chen, and Le Song. Sbeed: Convergent reinforcement learning with nonlinear function approximation. In International Conference on Machine Learning, pages 1133-1142, 2018.
Simon Du, Akshay Krishnamurthy, Nan Jiang, Alekh Agarwal, Miroslav Dudik, and John Lang- ford. Provably efficient RL with Rich Observations via Latent State Decoding. In International Conference Machine Learning, pages 1665-1674, 2019.
Yaqi Duan, Zeyu Jia, and Mengdi Wang. Minimax-optimall off pollpy evaluation with linear function approximation. In International Conference on Machine Learning, pages 2701-2709 PMLR, 2020.
Miroslav Dudík, John Langford, and Lihong Li. Doubly Robust Policy Evaluation and Learning. In Proceedings of the 28th International Conference on Machine Learning, pages 1097-1104, 2011.
Yonathan Efroni, Chi Jin, Akshay Krishnamurthy, and Sobhan Miryoosefi. Provable reinforcement learning with a short-term memory. In International Conference on Machine Learning, pages 5832-5850. PMLR, 2022.
Damien Ernst, Pierre Geurts, and Louis Wehenkel. Tree-based batch mode reinforcement learning. Journal of Machine Learning Research, 6:503-556, 2005.
Benjamin Eysenbach, Swapnil Asawa, Shreyas Chaudhari, Sergey Levine, and Ruslan Salakhutdinov. Off-dynamics reinforcement learning: Training for transfer with domain classifiers. arXiv preprint arXiv:2006. 139/6, 2020.
Mehrdad Farajtabar, Yinlam Chow, and Mohammad Ghavamzadeh. More robust doubly robust off- policy evaluation. In International Conference Machine Learning, pages 1447-1456. PMLR, 2018.
Arthur Gretton, Alex Smola, Jiayuan Huang, Marcel Schmittfull, Karsten Borgwardt, Bernhard Schölkopf, et al. Covariate shift by kernel mean matching. Dataset shift in machine learning, 3(4); 5, 2009.
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.
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.
Mao Hong, Zhengling Qi, and Yanxun Xu. A policy gradient method for confounded pomdps. arXiv preprint arXiv:2305. 17083, 2023.
Yuchen Hu and Stefan Wager. Off-policy evaluation in partially observed markov decision processes under sequential ignorability. The Annals of Statistics, 51(4):1561-1555 2023.
Ruiquan Huang, Yingbin Liang, and Jing Yang. Provably efficient ucb-type algorithms for learning predictive state representations. arXiv preprint arX 2023.
Nan Jiang and Lihong Li. Doubly Robust Off Offlpy Value Evaluation for Reinforcement Learning. In Proceedings of the 33rd International Conference on Machine Learning, volume 48, pages 652-661, 2016.
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E. Schapire. Con- textual Decision Processes with low Bellman rank are PAC-learnable. In Proceedings of the 34th International Conference Machine Learning, volume 70, pages 1704-1713, 2017.
11

---

Chi Jin, Sham Kakade, Akshay Krishnamurthy, and Qinghua Liu. Sample-efficient reinforcement learning of undercomplete pomdps. Advances in Neural Information Processing Systems, 33: 18530-185339 2020.
Leslie Pack Kaelbling, Michael L. Littman, and Anthony R Cassandra. Planning and acting in partially observable stochastic domains. Artificial intelligence, 101(1-2):99-334 1998.
Nathan Kallus and Masatoshi Uchara. Double reinforcement learning for efficient off- aff-policy eval- uation in markov decision processes. Journal of Machine Learning Research, 21(167):1-63, 2020.
Akshay Krishnamurthy, Alekh Agarwal, and John Langford. PAC reinforcement learning with rich observations. In Advances in Neural Information Processing Systems, 2016.
Jeongyeol Kwon, Yonathan Efroni, Constantine Caramanis, and Shie Mannor. RI for latent mdps: Regret guarantees and lower bound. Advances in Neural Information Processing Systems, 34: -4523-24534, 2021.
Sahin Lale, Kamyar Azizzadenesheli, Babak Hassibi, and Anima Anandkumar. Adaptive control and regret minimization in linear quadratic gaussian (lgg) setting. In 2021 American Control Conference (ACC), pages 2517-2522. IEEE, 2021.
Hoang Le, Cameron Voloshin, and Yisong Yue. Batch policy learning under constraints. In Interna- 2019.
tional Conference on Machine Learning, pages
Matthieu Lerasle. Lecture notes: Selected topics on robust statistical learning theory. arXiv preprint arXiv: 10761, 2019.
Lihong Li, Wei Chu, John Langford, and Xuanhui Wang. Unbiased Offline Evaluation of Contextual- bandit-based News Article Recommendation Algorithms. In Proceedings of the 4th International Conference on Web Search and Data Mining, pages 297-306, 2011.
Qiang Liu, Lihong Li, Ziyang Tang, and Dengyong Zhou. Breaking the curse of horizon: Infinite- horizon aff-policy estimation. In Advances in Neural Information Processing Systems, pages 1356-5366, 2018.
Qinghua Liu, Alan Chung, Csaba Szepesvári, and Chi Jin. When partially observable reinforcement learning not scary? In Conference on Learning Theory, pages 5175-5220. PMLR, 2022a.
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, 2022b.
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. 2tt.:22055333500 13589, 2022.
Gaurav Mahajan, Sham Kakade, Akshay Krishnamurthy, and Cyril Zhang. Learning hidden markov models using conditional samples. The Thirty Sixth Annual Conference on Learning Theory, PMLR, 2023.
pages
Rémi Munos. Performance bounds Lp-norm for approximate value iteration. SIAM journal on control and optimization, 46(2):541-56 2007.
Rémi Munos and Csaba Szepesvári. Finite-time bounds for fitted value iteration. Journal of Machine Learning Research, 91May))8558857, 2008
Ofir Nachum, Yinlam Chow, Bo Dai, and Lihong Li. Dualdice: Bchavior- estimation of discounted stationary distribution corrections. Advances in Neural Information Processing Systems, 32, 2019.
Yash Nair and Nan Jiang. A spectral approach to off off-policy evaluation for pomdps. arXiv preprint arXiv:2109.108 10502, 2021.
12

---

Hongseok Namkoong, Ramtin Keramati, Steve Yadlowsky, and Emma Brunskill. Off- Off-policy policy evaluation for sequential decisions under unobserved confounding, Advances in Neural Information Processing Systems, 53:188194 1883, 2020.
Juan C Perdomo, Akshay Krishnamurthy, Peter Bartlett, and Sham Kakade. A complete characteriza- tion of linear estimators for offline policy evaluation. Journal of Machine Learning Research, 24 (284):1-50, 2023.
Doina Precup, Richard S Sutton, and Satinder P Singh. Eligibility traces for off-policy policy evaluation. In Proceedings of the Seventeenth International Conference on Machine Learning. pages 759-766, 2000.
Chengchun Shi, Masatoshi Uehara, Jiawei Huang, and Nan Jiang. A minimax learning approach to off- policy evaluation confounded partially observable markov decision processes. In International Conference on Machine Learning, pages 20057-20094, PMLR, 2022.
Max Simchowitz, Karan Singh, and Elad Hazan. Improper learning for non-stochastic control. In Conference on Learning Theory, pages 3320-3436. PMLR, 2020.
Yuda Song, Yifei Zhou, Ayush Sekhari, Drew Bagnell, Akshay Krishnamurthy, and Wen Sun. Hybrid rl: Using both offline and online data can make rl efficient. In The Eleventh International Conference Learning Representations, 2022.
Guy Tennenholtz, Uri Shalit, and Shie Mannor. Off Off-po evaluation in partially observable envi- ronments. Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 10276-10288 2020.
Philip Thomas and Emma Brunskill. Dffi-Efficient Off-Policy Policy Evaluation for Reinforcement Learning. In Proceedings of the 33rd International Conference on Machine Learning, 2016.
Masatoshi Uehara, Jiawei Huang, and Nan Jiang. Minimax Weight and Q-Function Learning for Off-Policy Evaluation. In Proceedings of the 37th International Conference on Machine Learning, pages 1023-1032, 2020.
Masatoshi Uehara, Haruka Kiyohara, Andrew Bennett, Victor Chernozhukov, Nan Jiang, Nathan Kallus, Chengchun Shi, and Wen Sun. Future-dependent value-based off-policy evaluation in pomdps. arXiv preprint arXiv:2207. 2an.:2207733.1,,, 2022a.
Masatoshi Uchara, Ayush Sekhari, Jason Lee, Nathan Kallus, and Wen Sun. Provably efficient re- inforcement learning in partially observable dynamical systems. arXiv preprint arXiv:2206. /2020, 2022b.
Cameron Voloshin, Nan Jiang, and Yisong Yue. Minimax model learning. In International Conference on Artificial Intelligence and Statistics, pages 1612-1620. PMLR, 2021.
Tengyang Xie and Nan Jiang. Qa approximation schemes for batch reinforcement learning: A theoretical comparison. In Conference on Uncertainty in Artificial Intelligence, pages 550-559. PMLR, 2020.
Tengyang Xie and Nan Jiang. Batch value-function approximation with only realizability. In International Conference on Machine Learning, pages 11404-11413, PMLR, 2021.
Tengyang Xie, Yifei Ma, and Yu-Xiang Wang. Towards optimal off-policy evaluation for reinforce- ment learning with marginalized importance sampling. Advances in Newral Information Processing Systems, 32, 2019.
Tengyang Xie, Ching-An An Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal. Bellman-consister pessimism for offline reinforcement learning. arXiv preprint arXiv:2106.066 06926, 2021.
Ming Yin and Yu-Xiang Wang. Towards instance-optimal offline reinforcement learning with pessimism. Advances in neural information processing systems, 34:4065-4078. 2021.
Ming Yin, Yu Bai, and Yu-Xiang Wang. Near-optimal provable uniform convergence in offline policy evaluation for reinforcement learning. International Conference on Artificial Intelligence and Statistics, pages 1567-1575. PMLR, 2021.
13

---

YaonLiang Yu and Csaba Szepesvári. Analysis of kernel mean matching under covariate shift. In Proceedings of the 29th International Coference on International Conference on Machine Learning. pages 1147-1154, 2012.
Andrea Zanette, Martin Wainwright, and Emma Brunskill. Provable benefits of actor-critic methods for offline reinforcement learning. Advances neural information processing systems, 34:1364 34:13626 13640, 2021.
Wenhao Zhan, Masatoshi Uchara, Wen Sun, and Jason D Lee. Pac reinforcement learning for predictive state representations. arXiv preprint arXiv:2207.05786 2022.
Junzhe Zhang and Elias Bareinboim. Markov decision processes with unobserved confounders: A causal approach. Purdue Al Lab, West Lafayette, IN, USA, Tech. Rep, 2016.
14

---

A Related Literature
OPE in POMDPs. There is line of research OPE in confounded POMDPs Zhang and
Bareinboim. 2016 Namkoong et al. 2020 Nair and Jiang 2021 Guo et al. 2022 Lu ct al. 2022
Shi et al. 2022 Hong al. 2023]. However, all these methods require the behavior policy to solely depend on the latent state. This assumption inapplicable for our unconfounded POMDP setting, where the behavior policy depends on the observations. |uu and Wager (2023) studied the same unconfounded setting as ours. Nonetheless, their method uses multi-step importance sampling, leading an undesirable exponential dependence the horizon. The closest related work to our paper is (ehaaa et al. 2022a which we analyze in detail in Section
Online Learning in POMDPs. There are many prior works studying online learning algorithms for sub-classes POMDPs, including decodable POMDPs (Krishnamurthy al. 2016 Jiang et al.,
2017 Du et al., 2019 Efroni al., 2022]. Latent MDPs K Kwon et al. [202]] 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 Azizzaeneshh et al. 2016 Jin et al. 2020 Liu et al. 2022a] and POMDPs with general
function approximation IZhan al. 2022 Liu et al. 2002bb] Chen et al. 2022 Huang et al. 2023
All of these approaches are model-basee and require certain model assumptions. Uchara et al. 2022b
proposed model-free online learning algorithm based on future-depende
value functions (FDVFs).
However, their algorithm requires the boundness of FDVFs for all policies in the policy class, as well low-rank property of the Bellman loss, which limits the generality of the results.
OPE in MDPs. There has been a long history of studying OPE in MDPs, including importance sampling (IS) approaches [Precup et al., [2000] [i et al. [2011] and their doubly robust variants [Dudik]
jt al. 201 I Jiing and Li 2016 Thomas and Brunskill [2016] Farajtabar et al. 2018), marginalized
importance sampling (MIS) methods [Liu et al.
2018 Xie et al. [2199] Kallus and Uehara, 2020) and
model-based estimators [Eysenbach al. 2020 Yin et al. 2021, Voloshin et 2021J. As mentioned in Section I
directly applying IS-based approaches for POMDPs will result in exponential variance.
Meanwhile, MIS-based based approaches do not apply to POMDPs since they require the environment to satisfy the Markov assumption.
B Discussions and Extensions
B.1 Connection between Future-dependent Value Functions and Learnable Future-dependent Value Functions
Uehara et al. 2022a proposed 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, first introduce the definition of learnable FDVFs and then show that is equivalent to FDVFs under full-rank assumption.
Definition 14 (Learnable future-dependent value functions). A Learnable future-dependent value function V F + IR is any function that satisfies the following: VTE.
(B* (B))
For any FDVF Vv, since BSV; 0, we have VTL.
Vz) = Er, [u(O,, an) (r) + V=((n+1)) - V=(fh) TA (b(()),BB -
Therefore, all FDVFs are also learnbale FDVFs. On the other hand, for any learnbale FDVF V let B% E lal be the Bellman residual vector for V on Hd, and B& e R be the Bellman residual vector on Sn. With the help of MH. we have the following relation between B% V and B V
VK = (M..)) TRATTTBB BB
When rank (Mr,n) = S. V = 0 if and only if B = O. Therefore, V satisfies that Vsn. (BS (sL)) = 0. implying that V also FDVE Under the regular full rank assumption, the two definitions are actually equivalent.
15

---

B.2 Comparison between the Finite-horizon and the Discounted Formulations
The original results of Uehara al. 2022a] were given in the -hriiinn discounted setting. To describe their data collection assumption in simple terms, consider an infinite trajectory that enters the stationary configuration of TT. and we pick a random time step and call t (which corresponds to time step h in our setting). Then, history (analogous to our TH.) is (o(- (- (--))))()>)((-))) and future is (0n:M (0:Mp-1). Mr and Mи are hyperparameters that determines the lengths, and should not be confused with our MF.A.. and MH.A matrices. Data points collected in this way form the "transition" dataset. Separately, there is an "initial" dataset of (Ou:Mp-1, 4u:Ms) ) tuples to represent the analogue of initial state distribution in MDPs.
Besides the fact that horie-horizon formulation better fits real-world applications with episodic nature (e-g-, session in conversational system), there are mathematical reasons why the finite-horizon formulation more natural:
1. Unlike the infinite-horizon setting, 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. In the infinite-horizon, Mr and MH 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 MH,h h and M)..). On the other hand, the "curses of future and horizon" we identified in this work corresponds to exponential dependence so there is a potential trade-off in the choice Mr and MH contrast, the future and the history have maximum lengths (H h and h 1 at time step h)) in setting. As 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 to always choose the maximum length, do in the paper.
Mp and Mr.
B.3 Refined Coverage
As alluded to at the beginning of Section 5 we can tighten the definition of L2 belief coverage by directly using the ratio:
EE,, VV
sup VEW
VE,, (BHV))
which automatically leverages the structure of V. For example, if ( V V E V) only occupies a low-dimensional subspace of R& (that is, there exists Sh - Rd such that VB$V)ss)) ((s))
(o,)) 0y), then belief matching above (g. can be done in Rd instead of S. Other coverage definitions may be refined in similar manners.
B.4 Interpretation of Assumption
8
To interpret Assumption g let x = (((w)/Z((n) E ASS), and assign a distribution over x by sampling fn ~ (iag(Zn,/ SS). S). then Assumption 8 becomes x Ez, /s xx x < CF for any x with non-zero probability. This is a common regularity assumption DDaa al. 2020 Perdomo et al., 2023), requiring that no x points to a direction in R alone without being joined by others from the distribution. While 1 m/miii can bound this quantity, the other way around is not true, implying that Assumption iss weaker.
Example 8 (Bounded Cr.6 without bounded 1 1/amin (E),,)). Consider distribution over x where with 0.5 probability, x 11/2+c,1/2-0 and with the other 0.5 probability, x [1/2- T Then, as 1/0min (Ex,a) xo, but x: TT E[xxx ] 5 2.
B.5 Intuition for Lac Outcome Coverage
Here we provide more details about the Loo outcome coverage Section 4.2 which are omitted in the main text due to space limit.
Looseness of La2 outcome coverage We start by examining the looseness of 7.2 outcome coverage (Assumption 7 which will motivate the Loo version of outcome coverage. To develop intuitions,
16

---

first examine the boundedness of Eq. (the construction that leads to L2 outcome coverage) in the setting of Example 2 In this example, Σv and V H. According to the L2 Hölder
decomposition in Proposition 4 however,
Vollo S max |u(/a)//([W)ll)))) S HVS,
where || -1ls, is replaced by || lla since Σy = I. In contrast, the tight analysis is
V
max [| 1lo S H.
fv.
The comparison clearly highlights that the looseness in S comes from the fact that Lg Hölder does not fully leverage the fact that / = =1 and loosely relaxing it to (ff))) S 1. In contrast, our Loo coverage assumption allows for more natural L1/ Loo Hölder leverage the L1 normalization of (ffn)/Z(fh).
Lo Outcome Coverage Similar to Tox belief coverage, we could define Loo outcome coverage simply ((E,,,)\VV'"' To address this, we leverage the lesson from belief coverage (Section 5.2]: to obtain CH when TT Te. a key property is that An,. (data covariance matrix) and by (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 depends on the reward function, but such information is missing in Ey,K. No which prevents a perfect cancellation in the on poloicc case.
The small caveat and inelegance is that it does not recover Vy R+
when
adjust the definition of Σ to mimic the situation of belief coverage. The first step is to find the counterpart of belief state which In-normalized. This obviously corresponds to - S. E2z, jū Then, by incorporating reward information into Ey,h, we arrive at the solution in 55
Therefore,
'M
whose rows sum up to 1. Let ü(fx) == ((f))/Z(fh) E A(S)), then Σy, =
Finally, we examine the setting of Example 2 and show that Vz in Eq. is similarly well-behaved as (q.(4) in this scenario.
Example 9. In the same setting as Example 2 i.e., fa always reveals sh, we have Σ diag( (V ) and || (E - 11 = max.,
(sn).
This example also closely resembles Example 7 for belief coverage. While (E may behave poorly V/5h (s%. is small, an easy fix is to simply add a constant to the reward function and shift its range to c.g., [1, 2], which ensures small C7
B.6 Extension to History-dependent Policies
The main text assumes memoryless Ta and Fe- Similar to Uehara et al. [202aa] we can extend the approach to handle history- depeededd 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 Uchara et al. 2022a]]
Memory-based Policies and Changes in the Proofs Define memory m/ as function of T (i.e., my = m& ma(TT) )), and a memory-based policy can depend on (m,, 0z). Uehara et al. (202aa allows for my (On Mch-14 -4-A0:h- - for some fixed window M in their analyses. If we let
mA = (0 1.h-1)hh.... we recover fully general history-dependee policies.
If we direct modify the proof's to accommodate this generalization (as done in Uehara et al. 2022a
the required changes are:
v and Vy need to additionally depend on my to be well defined. V V also generally depend on since we need realizability V E V.
MF and MH.1 have rows indexed by (MK, ma) instead of just 8h. That is, we replace belief state with posterior over (sh, ma). Similarly, entries in My are now future probabilities conditioned on (sh, m
17

---

However, if we consider latent state coverage, which is weaker than belief coverage that is really needed (Appendix E.3 now require bounded d"' (=,.),,ma)" This is generally exponential in the length of my (e.g,, if M- h 1, the ratio is exactly the cumulative importance weight), preventing us from handling Te and Te 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 terre-state-maane policies (or policies that depend on a fixed-length window) as special cases.
(FSMs), which subsume fully distory-depender
Concretely, a policy with memory my is said to be an FSM, if mi+11 can be computed solely based on my, Oh "h, without using other information in тą- my (Oh-M:h-1s 1n A M---) satisfies this definition, as computing m2++1 is simply dropping the oldest observation-action pair from my and appending the newest one Another example is belief update, where b(Ta+1) can be computed from ((T)),, a/.
We assume that both Ta and Te 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 On, that is, $6+1 ~ T(1ssh, an ox). 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 8y, is bottleneck that separates histories from futures, which enables VV+ Sp. on Oh-1-
(B in 2). This property is intact with the additional dependence of
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 6n m)) The observation is on = (On, my), which can be emitted from 8). since &n contains my The latent state transition is 5 from my (contained in 5n), Ox. and on; this is why we need oμ 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 o₁ = (on, m.). TO and Te only need to depend on on
(5h+1; M+++1 1), where 1h++1 I T[- Gh 0n), and m 1 is updated
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 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 f.. (ō1:h-1, 01:h-1), which contains the same information as Tr. so functions in E and W can still operate on T₁-- Similarly, V E V now takes (mm,, (h) 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 my is "simple". For example, if m. takes values from constant-sizer sizedn space, d (s), m2)/ddm 1d (sh, my) (which lower-bounde belief coverage as discussed above) may not blow up exponentially, even though my 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 ma = b(Tx). Under the mild assumption that all histories lead to distinct belief states b(T)) (they can very close in RSS and just need to be not exactly identical), the belief state in the new POMDP, b(T.). completely ignores the linear structure of my and treats it in the same way m, Th I leading to 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.
'When h < M no dropping is needed. In fact, if we never drop, then mn is just the history. "(TT.) ) has "block one-hot" structure, where the block of size S indexed by my (7.) is equal to ( and all other entries are 0.
18

---

B.7 Recovering MDP Algorithms and Analyses
One somewhat undesirable property of our algorithms and analyses that they do not subsume MDP algorihhms/analyst as a special case. MDPs can be viewed as POMDPs with identity emission. i.c., Oh = S/. 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 84- contrast, our FDVF operates on fn (oh, .,.,....0 ,H ag) ) which includes on(= 8)). To recover the MDP algorithm as special case, we can choose V/ such that every V E V only depends on fn through o₁. However, w and & operate on 7/ = (0), - does not contain O%- This makes subsuming the MDP case difficult.
Oh-1; Oh-1:0h-1) which
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 тı = (01, ................................ -h-1, 04-1), we can define an alternative notion of history Th (01, 01 ................................ 0%, and replace тh in the main text with The Algorithmically, we can immediately recover MDP algorithms by also restricting functions in W and X' to only operate on O₁- However, our analyses (which apply to general POMDPs) need to change accordingly, linear in V The problem that in the definitions of V and B we want to marginalize out the randomness of on given 8n, which is in conflict with conditioning on 2n. that includes all the information on. To address this, we simply replace 8n with š.. == (5h, Op.) in the definition V BVV, MR.,. and MA That is, V is now a function of ön and also depends on Oh, b(T)) the posterior distribution over 8n, and the entries of the outcome matrix MF.. is Prx, (Ja [s 0n). This retains the key property that 8 V is linear in B with b(TT.) as the coefficient.
replacing with Fj will break the key properties, such as V² being
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 Vy. For belief coverage, note that VB*V) = (B$V)
on), which is simply the standard definition of Bellman error
in MDPs (since Sh o,). ). which denote as (s.) Plugging this into the refined coverage discussed in Appendix B.3 we recover the standard definition of coverage in the MDP setting, namely
1 [65 V (sx)
supvey
Emg (B+ (F
B.8 Incorporating Different Latent-State Priors in Vf
In Section 4
we showed that EA which crucial to the construction in Eq.44, 4). can be viewed the confusion matrix of making posterior predictions of 8n from fs. using a uniform prior. The uniform prior corresponds the all-one vector 1 in the definition of Zn diag(1} MM.n). which naturally leads to the question of whether we can incorporate different and perhaps more informative prior.
Let P E (SS) be the prior would like to use instead of the uniform prior. An immediate idea is to define h diag(P;, (P, MF,,) (possibly up to 5 scaling factor, as the uniform prior is Punif = [1/S.-.. 1/S]T and 1s Spmir) and directly plug it into the construction in Eq.44). However, this breaks some of the key properties of the current construction of Σy, such as L1 normalization rows of M
To resolve this, the key is to realize that the rows of ZT,1 MM are L1 normalized because they can be viewed as posteriors over Sh. In comparison, if we examine the (Jn, sth)-th entry of (2P.) (2p%)-1a -I it is
Pr., If|ss
Eves, Pr., [flls p')'''
so clearly it is missing a Pa (sk) term on the numerator to be a proper posterior. Inspired by this observation, we can see how to fix the construction now: recall that Vy needs to satisfy M Vr,a S.N. If Pa > O, then this is equivalent to
(diag(p=) a.) VF diag(p:)
Then, the minimum 2 weighted solution of this equation will provide the desired construction that preserves the L, normalization properties.
Which prior Pa. to use? For the initial time step h = 1, the initial latent-state distribution d, is the most natural candidate for the prior. If di (s1) 0 for some 81 E Sj, incorporating dj as the
19

---

prior will essentially treat as non oon-xxistent and ignore the outcome coverage of Tb over from S1. which is reasonable because $1 will not be activated by neither Ta and Tr, For h > the answer is less clear, and natural candidates include PA d and d, or perhaps their probability mixture. For the example scenarios examined in the main text, these choices (or even uniform prior) do not make significant differences, and we leave the investigation of which prior is the best to future work.
C Proofs for Section 3
C.1 Proof of Lemma
1
The RHS of the lemma statement is
ΣE,, Er. ((S)
= E
Beand
E
anott [nh V(f++1) sh) ET, (V(h)) sa]]
A=1
Now notice that the expected value of the V( term for is the same as that of the V(fh)
term for h + since both can be written as E Bestnngg ET, (ff((()))))s)e After telescoping cancellations, what remains on the RHS is
E Ex
anooTe [ra sn]] E., (EFT,V(([))s)]] = ((m.) - E., [V()]]
C.2 Proof of Theorem
The proof follows similar idea from V(fh), we have
Uehara et al.
2022a Let G.V ulon, an) + V(fnti))
H ED (G (G.V - =(T
argmin max VEV
EE
4=1
For any fixed V, we define
Ev
Σ
ED (G.V E(Tn))
argmax EE
Analysis of Inner Maximizer. We observe that for any h E [H],
- Let X₁, = (E(T)) (BB and
Em, (({(T)) - - = Er. [(E(T)) - (),)))
and = Σm= Xn. Let C max(1+Cu, Cz}. since Cp 2 1, we have |5(T))) - C, V < 3C, C and VTT)) $ 3C. Therefore, we have
|x1| S ,0 and X S 40HC, We observe that
Ez, [X]]
$ B.,.
()T)) {(Th))
2 V
(( {(TW)) (300 +12(GAV)9]
E.,
< Es, ((T) - {(T))) 2 (540² + +966 u(on, }2]
< 1,.
-
Hence, for the variance of X, we have
Var [X] H
Em. [X]]
h=1
H
< 150HH
Σ
En,
((B - -
h=1
20

---

From Bernstein's 's inequality, with probability at least 1 8/2, VA V, E, we have
D Ex ((((())) - VV ((B*)) -())))((("""))) - 1 A=1
150H Σ R., ((BB)) (( 40HC²Cp
(2
7
n
(11)
From Bellman completeness assumption V E, we also have
H
EollEv - 9vV)² - - so.
(12)
h=1
Therefore, we obtain that
E ((1)*))(m))
H
Exs ( ((( - -
-
h=1
Σ E - E,, -
- ((B* - 9n Vv
Σ Eol(E((T) - GVV - ((B -
H
Σ (ED - En, (L. - - ((B*))(TT) -
150HC2C, IH Em, ((B (og 40HCOC, log (1
The second inequality is from Equation 12 and the last inequality is from Equation have
We then
H
staat Stat := 225HC log( [0g(4
B. (BB(((()))TT))) -
(TW))
(13)
n
Combining Equation
and Equation
13 we have
H
Σ D E,, - - V) $ Estat
G.V
(14)
Hence,
H Σ Ep (
Σ
ED (
"7
"
Ex. (T) -9
Em, (m)
- Gr V)
+ 25 stat
1=1
En, (T))
+ 2E S 35 stat
The first inequality is from Equation
14 and the last step is from Equation
13
21

---

Analysis of Outer Minimizer. For any siture-dependent value function Vy, from optimality of V and the convergence of inner maximizer, have
H
Ep ED - (G.V ((B)))
Ep 2 -G, + 3Etatt
S
h
Ed (GnV>)² (9nV= -Evs) Stat
Ep s. -GG - (T)))) + Ga
6t
(15)
The last step is from that (B* = 0. For any The observe that VV E V and h [H].
Ex, - (B=)))
For any fixed V V, let Y. (9. (9, V (B))) and Y Eh= Yn. have
[Y s C7 and |Y| s 2T We observe that
Ex, [ = V (8
< Er, [180 + 4(G, (
E,, 1266 + 320
an) (())"((,,aa))))((()))))) (B))))))))))))))
< Cg V)
Then, for the variance of Y, we have
Var Y S ETy (Y2)
H < H
Em [2
h=1
58H0CC Cp
Σ Emg (B*
From Bernstein's inequality, with probability least 1 8/2, VV V. we have
H
Σ
ED - E..)) - (G,
- - VB
1m1
log( (gg(41)1/))
27 log (1)()))
<
58HC2C, Σ E., (B*
(16)
n
n
22

---

Therefore, we have
H
H =
(BN)))
Σ
Ex, (9 (/ - -9 - (Th)))
1=11
h=1
[ED - Br, (( - (9
(674))
h=1
ED [9 (9 (TN)))
H Σ
(1B7)))T))
log(4/V1/6)
27H Log(4/1//1/
58HC²CP
Bm
+ Stat
p
h=1
(From Equation
15
and Equation
(66
Solving it and we get
H
ET.
S (B*
10
A=1
We then invoke Lemma and obtain that
H
[(Te) E.G (
E en md
[189T)(aN]]
)) 2 (1B8))())))
Esnnat
[1808)
Ees di
> h=1 E Ssandi
[135))
Σ h=1 Eay
(B )2
== Br.
(BST)))))
=1= BiT,
(188))
V Estat
E Emo
(xx)))
Σ == Ero
(BHH
Cp log //1/331
50H max + 1, DVV))VV( (dTo, J
n The proof is completed by using Hoeffding's inequality to bound |Ep [(1)] - Ez,, (fi)]
D Proofs for Section
D.1 E
We provide a brief justification of Example have
Cue When (falo)) 5 T for any u(fi), we
Cuuch VS (OA)H-u+1*
(u(f))l2 <
Then, for any x E R such that ||x||2 1, we have
J(MrAMMWWe & Σ
(OA)
fn
23

---

Therefore, Tiiu (MF S (max( & Cstoch (M
D.2 Proof of Proposition 3
For each entry in E,, can write it as
Prm, (Sn = 8h =i) Pros (Jn = k 84 j)
(E
Ex PTa, (Jh 1: 8h 1')
Since the probability is always non-negative, all the entries in Ex,t f is non-negative. For each row i, we have
ΣEANNN ΣΣ Pras (fn = k 84 = 1) Pr., (fa = k. 8h2 5)
Ev Proso (fn 5% = 11)
= -E Pros (fn sn = =.
Similarly, for each column j. we also have (EE,,)) = Therefore, we prove that Σy,,, is doubly-stochastic and we know for a stochastic matrix, the largest eigenvalue is 1.
D.3 Example 2
Due to the block structure of My A. Σy.n a is clearly diagonal, and the i-th diagonal entry is:
Pr.. lfn = j/sa = z)²
Σ En Pr [sn = j|sh = i7]
Pr =
Due to the revealing property, the denominator is just Pr (fr 51sh, = =i.. so the expression is just summing up Pr (Ja = j/8h- = i) over j, which is 1.
D.4 Proof of Proposition
According to Equation
we have for any fh.
V*(()) = Z(N) Z(/N)''((W) u(()) T
$ (WW S CCF,CCFV
(VS,) TEE VTz. 21F
The last step is from Assumption VC Moreover, we observe that
7 and Assumption Therefore, || S VCFECFV=
1 = E((h) (Z(FN) T v ?
)²
fn z(fr) ((V3) T u(hhu(u T
fn.
= =VV3)) T Σニ
Σ Z(WN) HUNNWuN) V5
fn
(V
T F.
Ex
J.h V5 - CF.V
The last step is from Assumption
24

---

D.5 Example
We give the calculation for Example
When Te Tbe V.S. R so
|IV 13'1 R
M M 2iy, Mr,h Rij
(R;) T 7///2 T 1/ M (M F Z M T. 2n 7,, Ri
(R Z
_/2 Zn²²
1 R
where the last step follows from the fact that Z, /T, M (MF Zn M 1/2 is projec- tion matrix (P2 P) and is dominated by identity in eigenvalues (P 1). Now, recall that Zz/ 25/S is a proper distribution, so
RR T Zn R = R... (2. SH?
E
Proofs for Section 5
E.1 Proof of Lemma 6
We first verify that wi in Eq. (8) satisfies Eq. 7 as follows.
Bsg [w (T. (TT))
Σ de (m.) (T.)((T)
(T.)((7)b(T)) E
Σ (()D)(() b
b
We then show that
|| 112 12.0030
Σ dh (Th) (D(T)) T Exih )b
= -bbt.) Ejpl Σ
Dnin b
Th.
=bba') T Ex, 2.
Hi.h bya
= -b),') Ex, b CH.2.
The last step follows from Assumption
E.2
Example 5
Consider the lemma: given vector r and PD matrix Σ. if 2 xr. |thn x ---lI < 1. The calculation in the example directly follows from letting b E Σh and the condition Σ xx is satisfied due Jensen's inequality.
To prove the lemma, note that - xx PSD, so
( <x~ (0-1x)((5)) (I FF ()= 2.
This implies x: - r 2 x rr
TI-L 1,,00 so x. I 1.
E.3
Comparison between belief coverage and latent state coverage
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
Es, (dd (sn)/d") (bx*) diag(Em, (b(T)))) b
25

---

In comparison, our belief coverage parameter from Assumption 11 is
(b% HHh by = (bx) Ez, (( b(())) bb
To show the former smaller than the latter, suffices to show that
diag B,, (bTx))) = (Rm, (b(TT))((TT))))))
which is implied by dEa [b()))) = ((TT) It therefore suffices to show that (liag((T.)) -=2 ( (m())) holds in a pointwise manner for all The To show this, we temporarily let b b(Th) in the calculation: consider arbitrary vector E R then
v (diag(b) bb T ) EE- b[t())] (LE bu(s))
The last step due to Jensen's inequality.
E.4 Comparison IV(V)
We now compare to the IV(V) and Dry terms in Theorem 2 Belief coverage is generally stronger than latent state coverage which corresponds the Dry term (see Appendix E.3p. That said, perhaps surprisingly, the remaining IV()) term must scale with amin (2u,
under moderate assumptions.
Proposition 10. Suppose min the eigenvector corresponding J (EH,n). the smallest eigen- value for some Ez.h- Then, if Commin VV {B V V E V} for some non-zero co.
IV(V) min,, (as)
main (En.s)
The proposition states that as long as mins, (sn) is bounded away from (which is benign and helps bound the Dry (dT d' term) and V is sufficiently rich that B3 includes certain vector in R then boundedness of IV()) requires bounded 1/omin (Ex,n), which is stronger than our belief coverage assumption. This renders the split between IV(V) and Dry [d",, dd* superficial and perhaps unnecessary.
Proof of Proposition 10 Since Viin E {B V : E V}, there exists such that B V = Co miin- For such V. we observe that
Σ (T)) (b(r),, covini" chv min EH,A amia ) E., VV (Tn)a
and
Ex, (BSV) (sh)²1
min d (sn) 1/c0 V 8%
min d (sn) c/-
8i.
Therefore
Ex, (BSV) (sh)2] B. (BHV) (T
mins, d= (sn) c mmin (EH,))c
min., d (8h)
V
mmin (E.,h)
E.5 Example 6
It suffices to show
= (e(.)b(T))))))
E., (b(T)))TTTT) = Ex, [b(T)) = =b
E.6 Proof of Lemma g
The key is to notice that (b"r) is non-negative, so
(b%)) Σ H by < (b%. [xxl(bb < <bb) ) T E (b)-))l<
() is pointwise absolute value)
(using the non-negativity of (b ) agaain
| lloo.
26

---

E.7
Proof of Lemma 5
According to Eq. we use Lo/ Hölder's inequality and obtain that for any fi.
u(fn)
[V>(fi] -
(x
1l
(JN)
1
u(fi)
|| (
'V3 10
7(Fa)
- (Fn)Cooo
- HC0
The second inequality is from Assumption and 7(%) the boundedness of the reward.
u( (1)
is stochastic vector. The last step is from
E.8 Example 4
We use diag(-) both for creating diagonal matrix with an input vector and for taking the diagonal vector out of a matrix.
1= a (Z,) -MM 1 MM (Z, diag(ZN)
Mr = V
E.9 Example 9
The calculation is similar to that of Example in Appendix D33 R+ (fr). Therefore, when calculating the i-th diagonal entry of Σ . the final sum is calculating the expectation of R (fr) conditioned on sy = i under policy To. which is the definition of V (i).
except that the numerator has extra
E.10 Proof of Theorem
In the proof of Theorem we have
225H log (4
EmL
(BT))
I 10
Estat
We observe that
E.T (B3T)
B me E Reynb(Tn)
(18)))(sn)
Es.
Emn (Tx)
I|l" 112, V Bmn [1BH()
$ v Cr.L2Ee ((T
The third equality is from Definition the last inequality is from Lemma
10 the first inequality from Cauchy-Schward inequality and Then, we have
h
E..
()sn)
H
En
(BB8))
h=1
10H CH.2Estan
Cn.
- 50HŌ,
n
S cC + +1) C2.20 (og(41))336)
n
The last step is from Lemma after invoking Lemma
Cv S lo and Cs S /ll + 1). The proof is completed
27

---

E.11 Proof of Theorem 9
Finally, we prove Theorem The proof uses the similar idea from Xie and Jiang 2020] For any V E V and w E W, we define the population loss estimator La and the empirical loss estimator
LD as follows
H
Caro (V,w) ;=
Σ Ens (B h=1
(D(V.w)= :=
ED (w(TT) (p(on,an) (ra + ((f++1)) - ((fi))).
We then invoke Lemma
and obtain that
H
((Fe)- 1m.
Σ h=1
Esn ma (B88))(n)
We observe that
(188)
Brncedt (gnnb(Th) (sN))
Ees mame
Erannate [BT)
ETg 10 (BT)(
where the last step is from Definition
Therefore, our goal to bound
Σ Ers w= (Bx)
Care (V, w"
Let
T argmin max "Esp(W) VEV
Σ h=1
Ex, [w (Tx) - -w(r)) (8*)
11 >
Em [w(Th): V3H)
argmin Vev
sup WWs
Then, we subtract the approximation error of w from our objective,
H
E
(BT
Σ Ems
(w (w'()))((TT)) (B*
E w(Th): (B*
H
Emy
- (TT))) (B*))
+
Σ
Em,
(8(T)) (B*
h=1
H
< ew
Σ
Ems
i ((T))
(B*
h=1
Next, we consider the approximation error of V and obtain that
H
H
H
Ex,
(5(Th)(88*)))
= cv +
Er,
((Th) . (88 ()
sup (Ws
Er, (w(T)) ( -88*
A=1
h=1
A=
28

---

We then connect La (V, w) with CD(V, w) as follows,
Σ h=1
I
m
T(Th)
(B*
sup wesp(W)
E
w(Th) (7
1=11
H
H Σ Ews h=1
Emp w(Tn) (B* [
(T(TT))) (B [B
- sup WEsp(W)
sup wEs
1=1 Lazo (V, w)
Caro (V, (00
max WEW
max wEW
fax (V, w)
CD(V, w1)
+ LD w)
Lax (V,w) w)
max wEW
WEW
WEW
wEW
I max WEW
La (V, w)
max WEW
CD(V, w)
+ max WEW
CD(V, w)
max WEW
Lare (V, w)
max WEW
Lavo (V, w) CD w)
+ max wEW
Care (V, w) CD (V, w)
The first equality is from that sup (VV)) If(-)) = max [f(-)] for any linear function f(-). The
second inequality is from the optimality of V.
For any fixed V. w, let random variable = Σ w(Th) (n(on, an)(nn))r + +V(h)) - ((fn+1)) E [X] Lars (V, w)). Recall that Cy == maxvev [ and Cw == max, suPwew || For
[X], we have X < 2HC + Cv)Cw. For the variance, we have
Var [X]
H
H
Emo ((((n) an) + (([++1)) ((nn))
H
B., (w(TT)² (2C2 + 2(1 (v)) an)
<
From Bernstein's 's inequality, with probability at least 1 8, we have
C, Galog
2H + 2H(1+CV)CWCC log
Cara (V, - (V( < 2H CV)Cw CV)
Taking the union bound and we obtain
Caro (V, w)) - Lo w)
max NEW Lazo (V,w) w) - LD( w)
max NEW
Calog 21III
(E(1+CC) log 31
<
<4M(1+C>CCW
n
According to Lemma
Assumption 12 Cy S VllVV loo and Ow S Ill we further have
Iiin log
cH-CCH,0 C.CCH,OOCCCCO + I)C,, log 2|
J(mr)) - B., (v()))] s 6v + ew + cHf (Cr + +1
The proof is completed by using Hoeffding's inequality to bound EED [(1)) E., (V
29

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Our main claims made in the abstract and introduction accurately reflect the paper's contributions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitations in Section
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
30

---

Justification:
We provide the full set of assumptions in the main text and a complete proof in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proof' provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification: No experiments.
Guidelines:
The answer NA means that the paper does include experiments. If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
31

---

Answer:
[NA]
Justification: No experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ cppppi.ccppulli//uuuiu wwwiii/gguie///eeeeeeoecc CoodeSubeiiie ssi wswonnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification:
No experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification: No experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
32

---

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 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror 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.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
No experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well 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 failed experiments that didn't make into the paper).
9. Code Of Ethics
Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Question:
Answer: [Yes]
Justification:
We conform with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration 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 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.
33

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is 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 being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there 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 monitor how system learns from feedback over time, improving the efficiency and accessibility MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper poses such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have 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 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 best faith effort.
12. Lieenses for existing assets
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?
Question:
Answer: [NA]
Justification: This paper does not existing assets.
Guidelines:
The answer NA means that the paper does 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 URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.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, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of 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.
34

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
35


Reviews:
[{"review_id": "C03rb3Li1x", "reviewer": "Reviewer_Djpv", "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.", "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": "N/A", "rating": 5, "confidence": 1, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "To be honest, this paper is quite far beyond my abilities with RL theory. I was able to identify two positive aspects.\n\n1. The paper operates in the POMDP setting, and (as far as I can tell) does not assume the learning agent ever has access to the set of latent states S. If I'm incorrect about this, I ask the authors to let me know so I can fix my understanding.\n\n2. The paper starts by suggesting that we will be looking for solutions in $mathcal{F}_h$, but points out correctly that this will give us exponential dimensionality, and subsequently finds another approach with better properties.", "weaknesses": "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.\n\nDespite significant familiarity with off-policy evaluation, importance sampling, POMDPs, etc., I was unfortunately unable to:\n- follow most of the paper,\n- understand the main questions being asked,\n- see what this would be useful for,\n- evaluate the reasonableness of the assumptions,\n- check the proofs,\n- appreciate the consequences of the results.\n\nIn 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable comments.\n\n> **“the paper … does not assume the learning agent ever has access to the set of latent states S. If I'm incorrect about this, I ask the authors to let me know ...”**\n\nYou are right. As in the standard POMDP setting, the latent states $s\\_h$ are not included in the dataset received by the agent performing off-policy evaluation. This has also been made explicit in Lines 66 and 67. Both the behavior and the target policies also only operate on the observables, i.e., they cannot depend on the latent states (see Footnote 1). \n\n---\n\n> **“The paper's main weakness is that it targets a very limited audience of theoreticians. There is extremely little text providing intuition or any sort of motivation for the research questions, approach or solution.”**\n\nWe appreciate the comment about readability and will try our best to address it. But yes, this is a pure theory paper mainly aiming at the RL theory audience, a community with a strong presence at NeurIPS. We believe that the study of POMDPs, especially providing results in modern (offline) RL theory frameworks (i.e., providing sample complexity guarantees in terms of proper coverage parameters), is an important and understudied research direction. For MDPs, the research on understanding coverage assumptions (starting from early works of Munos and Szepesvari between 2000 and 2010) has led to growth of the offline RL theory community, and eventually practical offline algorithms that are both theoretically sound and empirically effective (see e.g., ICML 2022 Outstanding Paper Runner-up: “Adversarially trained actor critic for offline reinforcement learning”). What our paper does can be viewed as similar efforts that lay down the theoretical foundations for POMDPs, which may inspire practical algorithms later. We have articulated such a motivation in the context of (offline) RL theory research in the abstract, the introduction, and Section 3; see also our response below to your question on “summary for non-theoretician”. In the revised version, we will include additional text to further clarify the significance and rationale behind our research questions and proposed solutions. \n\nFurthermore, the POMDP theory literature have generally been known to be mathematically involved (e.g., the PSR literature, which the future-dependent value function framework draws inspiration from, has always been a niche yet important topic in RL), and distilling knowledge into an easy-to-understand form often takes multiple papers and years of efforts in such research directions. We believe we have already made progress on this: in Section 3, we rewrote and presented the work of Uehara et al. [2022a] in much simpler forms compared to the original paper, forming a clean basis for our later investigation as well as future work in this direction.\n\n---\n\n> **“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?”**\n\nIn OPE in MDPs, methods that learn value functions have the theoretical advantage of paying state density ratios as its coverage parameter, compared to importance sampling that incurs exponential dependence. However, naive extensions and analyses to POMDPs erase such advantages. We identify novel coverage definitions and further develop the future-dependent value function (FDVF) framework that reinstantiate such advantages in POMDPs.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "frj7OfQW5h", "reviewer": "Reviewer_zNfE", "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.", "questions": "See weaknesses.", "limitations": "See weaknesses.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper clearly pointed out the problem of the existing sample guarantee (Theorem 2) along with illustrating examples, such as the boundedness of $C_\\Xi$ can be exponential in horizon.\n2. The assumptions proposed are intuitively interpretable and successfully solve the problem.", "weaknesses": "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.\n2. 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$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable comments. \n\n> **“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\\_{F, V}$ is polynomially bounded in all cases is needed.”**\n\n$C\\_{F, V}$ is the (L2) outcome coverage. As its name suggests, it is a _coverage_ parameter, which describes the extent to which the data (sampled from the behavior policy) contains information about the target policy. Coverage parameters will **not** be bounded in all cases. For example, in the MDP literature, (the boundedness of) the state-density ratios are a standard form of coverage parameter, which can be easily infinite with a poor offline data distribution. Nevertheless, we view state-density ratio as a “polynomial quantity” because there are natural settings where the cumulative importance weights are exponential yet the state-density ratio remain small (see e.g., the example on page 3 of Liu et al. [2018]: “Breaking the Curse of Horizon: Infinite-Horizon Off-Policy Estimation”). Indeed, the wide acceptance of state-density ratio as an appropriate coverage parameter is precisely established by studying “intuitive examples”, just as we did in this paper.\n\nNote that this is a major difference between MDPs and POMDPs (and not realizing the difference might be why the reviewer made this comment in the first place): in MDPs, value functions are always bounded and they have nothing to do with the offline data distribution. In the future-dependent value function (FDVF) framework, however, these FDVFs are properties of both the behavior and the target policies (Line 131), and their existence and boundedness depend on a new form of coverage not seen in MDPs (Line 248), namely the outcome coverage. \n\n\n---\n\n> **“the paper didn't discuss on $C\\_{\\Xi}$”**\n\n$C\\_{\\Xi}$ is assumed to be bounded by  $c (\\\\\\|V\\_F\\\\\\|\\_\\infty+1)$ (Line 327), with $c$ being an absolute constant. The rationale is exactly the same as for $C\\_V$ (see below), so we omitted the explanation for $C\\_{\\Xi}$ due to space limit at submission time. That said, the reviewer is right that we should have discussed this explicitly, and we will add in revision.\n\nRecall that for $C\\_V$, we wrote in Line 322:\n\n> To highlight the dependence of $\\\\\\|V\\_F\\\\\\|\\_\\infty$ 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** [i.e., $C\\_V \\le c \\\\\\|V\\_F\\\\\\|\\_\\infty$ for absolute constant c, as in Line 327].\n\nWe made a similar assumption for $C\\_{\\Xi}$ in Line 327 for exactly the same reason: the functions that $\\Xi$ needs to capture are $\\\\\\{B^H V: V \\in \\mathcal{V}\\\\\\}$ (the Bellman completeness in Assumption 6, Line 152). From the definition of $B^H V$ (Eq.(2)), we know that its boundedness is immediately provided by the boundedness of $V \\in \\mathcal{V}$ (i.e., $2C\\_V + 1$). The final assumption on $C\\_{\\Xi}$ follows from combining this with the bound on $C\\_V$ above.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "XEkpdmr5xM", "reviewer": "Reviewer_jTik", "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.", "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? \n- 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?\n- Minor: in line 312, should it be $d^{\\pi_e}$?", "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.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "- The paper is well-structured and exceptionally clear, making it easy to read. The problem formulation, assumptions and subsequent results are presented with great clarity. The mathematical derivations appear sound.\n- The new coverage assumptions are novel and effectively solve the non-trivial problems (1) the counterpart of bounded density ratio, the widely adopted coverage assumption for offline MDP, in the context of POMDPs (2) avoid exponentials.\n- A information-theoretical algorithm, MIS, is provided for interpretation of sample complexity", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their appreciation of our work and the valuable comments.\n\n> **”Why such `future-dependence’ is necessary to deal with partial observation?”**\n\nAs we mentioned in the paper, the most obvious thing to try is to use history-dependent value functions by converting the POMDP into a history-based MDP. However, a straightforward extension incurs the curse of horizon, which shows that some new ideas are needed to overcome this difficulty. We did not claim that “future-dependence” is absolutely “necessary”,\njust that it is a promising idea for addressing this issue. Future-dependence may not be the only idea that works, and other plausible approaches remain to be explored in future works. \n\n---\n\n> **”From my interpretation, it seems that $L\\_\\infty$ assumptions should be looser ones and can better accommodate the PO. Why are the t $L\\_2$ assumptions emphasized, or do they offer any unnoticed benefits?”**\n\nAs the reviewer also noticed, $L\\_\\infty$ assumptions are looser than their $L\\_2$ counterparts (but the $L\\_2$ versions often require additional assumptions, e.g., Assumption 8). So whenever no additional assumption is needed, using $L\\_2$ assumptions lead to tighter bounds and better guarantees (e.g., Theorem 7 depends on the $L\\_2$ version of belief coverage, and no additional regularity assumption is needed).\n\nAnother reason we emphasized $L\\_2$ assumptions is its familiarity to the RL theory audience, that they look very similar to coverage coefficients in the linear MDP literature (Line 246). On the other hand, $L\\_\\infty$ assumptions are very … alien, which can look problematic at the first glance (Line 341) and its validity largely relies on the $L\\_1$ normalization of belief vectors, a property rarely found in other settings in RL theory. Therefore, we start with $L\\_2$ assumptions for a more gentle introduction, and describe $L\\_\\infty$ later as an improvement. \n\n---\n\n> Line 312\n\nIt is indeed a typo; thanks for pointing it out!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "jreXN3zYVF", "reviewer": "Reviewer_NgTY", "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.", "questions": "1. Is it possible to extend the analysis to infinite horizon?\n\n2. Can you justify the full row rank assumption in Assumption 2?", "limitations": "The authors addressed the limitations in Section 6.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. This paper gives comprehensive analysis in theory, which makes the proposed paradigm sound.\n\n2. The improvement from exponential to polynomial is impressive.", "weaknesses": "1. The new algorithm in Section 5.3 has not been studied thoroughly with experiments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their appreciation of our work and the valuable comments.\n\n> **”Is it possible to extend the analysis to infinite horizon?”**\n\nWe believe the answer is yes. In fact, the work of Uehara et al. [2022a] (which we build on) is in the infinite-horizon discounted setting. However, as we discussed in Appendix C.2 (page 17), working with POMDPs and performing the kind of analyses we do in the infinite-horizon setting is really messy. (Just to give a taste: in the infinite-horizon setting, computing belief state requires us to trace back history indefinitely, and in the finite-horizon setting we only need to trace back to the beginning of the episode; see more detailed discussion in C.2) In contrast, the finite-horizon formulation is much cleaner and we are able to re-express the ideas and analyses in Uehara et al. [2022a] in much more elegant forms, which is significant given the complexity of the POMDP formulation (i.e., we want to simplify all aspects as much as we can, as long as it does not lose the essence of the setting). If one is willing to put up with the messiness of the infinite-horizon setting, we believe it should be possible to translate our results into the infinite-horizon setting that Uehara et al. [2022a] took.\n\n---\n\n> **“Can you justify the full row rank assumption in Assumption 2?\"**\n\nThese assumptions are made for technical convenience, as mentioned in Line 108. Our main results still hold after some modifications even if they do not hold. Taking L2 belief coverage (Assumption 11) as an example: if $\\Sigma\\_{H, h}$ is not invertible, but $b\\_h^{\\pi\\_e}$ lies in the subspace of $\\Sigma\\_{H, h}$, we can still define L2 belief coverage by replacing inverse with pseudo-inverse, and the rest of the analyses and the main results still hold. (If $b\\_h^{\\pi\\_e}$ does not lie in the subspace, we can just define the coverage parameter to be infinite, i.e., no guarantee can be given.) Assuming full-rankness is just a convenient way to avoid dealing with these hassles. \n\nTo recap, what really matters is whether (and to what extent)  $b\\_h^{\\pi\\_e}$ lies in the subspace of $\\Sigma\\_{H, h}$; the binary notion of full row rank or not of $\\Sigma\\_{H, h}$ does not really matter and is made only for simplifying presentations. Moreover, these full-rank assumptions are intimately connected to the notion of “core histories” and “core tests (future events)” in the PSR literature, which the future-dependent value function framework draws inspiration from (see their connection in Uehara et al. [2022a]).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: 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.
Decision: Accept (poster)