Statistical Tractability of Off-policy Evaluation of History-dependent Policies in POMDPs
Authors: Yuheng Zhang
Nan Jiang
Venue: ICLR 2025 Poster (2025)
Keywords: Partially Observable Markov Decision Process; Offline Policy Evaluation; Reinforcement Learning Theory
Primary area: learning theory

Abstract: We investigate off-policy evaluation (OPE), a central and fundamental problem
in reinforcement learning (RL), in the challenging setting of Partially Observable
Markov Decision Processes (POMDPs) with large observation spaces. Recent
works of Uehara et al. (2023a); Zhang & Jiang (2024) developed a model-free
framework and identified important coverage assumptions (called belief and outcome coverage) that enable accurate OPE of memoryless policies with polynomial sample complexities, but handling more general target policies that depend on
the entire observable history remained an open problem. In this work, we prove
information-theoretic hardness for model-free OPE of history-dependent policies in
several settings, characterized by additional assumptions imposed on the behavior
policy (memoryless vs. history-dependent) and/or the state-revealing property of
the POMDP (single-step vs. multi-step revealing). We further show that some hardness can be circumvented by a natural model-based algorithm—whose analysis has surprisingly eluded the literature despite the algorithm’s simplicity—demonstrating
provable separation between model-free and model-based OPE in POMDPs.

Published as a conference paper at ICLR 2025
STATISTICAL TRACTABILITY OF OFF-POLICY EVALUA- TION OF HISTORY-DEPENDENT POLICIES IN POMDPS
Yuheng Zhang & Nan Jiang University of Illinois Urbana-Champaigee (yuhengz2, nanji nanjiang]] @cs. allinoii..... edu
ABSTRACT
We investigate off-policy evaluation (OPE), central and fundamental problem in reinforcement learning (RL). in the challenging setting of Partially Observable Markov Decision Processes (POMDPs) with large observation spaces. Recent works of Uehara et al. (2023a); Zhang & Jiang (2024) developed a model-free framework and identified important coverage assumptions (called belief and out- come coverage) that enable accurate OPE of memoryless policies with polynomial sample complexities, but handling more general target policies that depend on the entire observable history remained an open problem. In this work, we prove iiftommtiion-thorree hardness for model-free OPE of history-dependent policies several settings, characterized by additional assumptions imposed the behavior policy (memoryless vs. history-dependent) and/or the state-revealing property the POMDP (single-step multi-step revealing). We further show that some hard- ness can be circumvented by natural model--asee algorithm- whoose analysis has surprisingly eluded the literature despite the algorithm's simplicity- demonttrainn provable separation between model-free and model-basee OPE in POMDPs.
INTRODUCTION
Off-policy evaluation (OPE) aims to evaluate target policy л. using offline dataset collected by a different behavior policy тe. The problem plays a crucial role in reinforcement learning (RL),
and is particularly relevant real-world scenarios where policies need be properly evaluated
before online deployment (Murphy/ 2003 Hrnst et al. 2006 Mandel et al. 2014 Bottou et al. 2013
Chapelle et al. 2014 Theocharous al. 2015).
Efficient OPE requires the behavior policy n, to satisfy certain coverage assumptions with respect to the target policy we. In the setting of Markov Decision Processes (MDPs), is well established that a bounded state-action density ratio between म. and т.. suffices for polynomial sample-complexity bounds; see [eehara et al. (2022b); Jiang & Xie (2024) for surveys and tutorials on the topic. However, the Markov assumption, that the immediate observation is sufficient statistic of history, can be restrictive in scenarios where the state is latent and unobservable to the agent, as often the case in many real-world applications.
In this paper, we study OPE in non-Markov environments modelled as partially observable MDPs (POMDPs) where the observation space is large and demands the use of function approximation. In POMDPs, the agent only has access to observations rather than the latent state, and the next observation may depend the entire history of observation-action sequences (or simply, the history). common approach to apply MDP techniques is to treat the history as the state, thereby reducing POMDP to a history- based MDP. However, under this conversion, the atate-cction density ratio becomes the density ratio of the entire observation-action sequence, which grows exponentially with the horizon length.
'When we refer to OPE in POMDPs, we mean unconfounded POMDPs, where the behavior policy only depends on the observable variables and not the latent state. There is also research on OPE in confounded POMDPs, where the behavior policy n, depends on (only) the latent state (Shi et al. 2022 Bennett & Kallus 2024 see Zhang Jiang (2024) for further discussions the distinction hetween the two settings.

---

Published as a conference paper at ICLR 2025
Table Summary of whether poly(H, l e, CA. Ca,CO.CH (c.f. Theorem complexity is achievable in different settings, where Cp is either Co or C5 depending on whether single-step multi-step revealing is assumed. "MF" and "MB" stand for model-free (Definition 2 and model- based (Section()) respectively. "V" indicates positive results, and "x" indicates information-thhorett hardness. The setting is the easiest in the top-left corner, and becomes harder in the right or down direction. Therefore, the hardness of MF in Row 2 automatically implies those in Row 3. The bottom-right corner for MB is an open problem which we conjecture to be intractable.
Policy Types
Single-step Revealing
Multi-step Revealing
Memoryless Te & Te.
MF: / (Zhang & Jiang. 2024), MB: / (Theorem 55)
Memoryless na & History-dependent we History-dependent Te & Te
MF: x (Theorem
3p. MB: / [Theorem 55)
MF: X, MB: / (Theorem
MF: X MB:
To address this issue, recent line of research (Uehara ct al. 2023a Zhang & Jiang, 2024) has proposed model-free methods for OPE in POMDPs with large observation spaces. iZhang & Jiang (2024) identify two novel coverage assumptions for OPE in POMDPs, belief and outcome coverage, and demonstrate that their algorithm achieves polynomial sample complexity under these assumptions. However, they focus on evaluating memoryless target policies Te, which ignore history and depend only on the current observation. Extension to bistory-dependert ne exists, but the guarantees quickly deteriorate when the history window that me depends on has a nontrivial length (Uehara al., 2023a Appendix C). This motivates us to study the following question:
When can we achieve polynomial sample complexity for OPE of history-dependen target policies?
We investigate the question in a range of concrete settings, and the answer turns out to be more complex than a simple yes and no. These settings are defined by variations along several dimensions:
Model-free vs. model-based algorithms The algorithms in Uchara et al. (003a): Zhang & Jiang (2024) are model-free, in the sense that the algorithm only queries ne on histories in the off dataset. Under this rather broad definition (Definition 3 in Zhang & Jiang (2024), ) we show that no model-free algorithms can handle general history-dependent target policies, even if we impose additional assumptions to make the problem easier in other dimensions (see below). This motivates us to also consider model-based algorithms that a POMDP model from data, which circumvent the hardness they query π. model generated synthetic trajectories.
Single-step vs. multi-step (outcome) revealing The outcome coverage condition identified by Zhang & Jiang (002)) asserts that the future observation-action sequences can probabilistically decode the latent state (Assumption 9 in Zhang& & Jiang (2024)) A stronger version of the condition is that the immediate observation suffices, which corresponds to a standard (single-step) "revealing" assumption commonly made in online RL for POMDPs (Liu et al. 2022a).
Memoryless vs. history-dependent TT Another dimension is whether my is also history dependent. In the literature, it has been reported that history-dependent wa often makes it difficult to infer POMDP dynamics from data, and memoryless T6 makes it easier to do so (Kwon et al. 2024).
Our findings are summarized in Table [ With either relaxation (single-step revealing or memoryless Tb), a simple Maximum Likelihood Estimation (MLE)-based model-based algorithm achieves desired guarantees, where all model-free algorithms must suffer hardness. To our best knowledge, these results are the first polynomial sumple-complexity bound for evaluating iistrry-dependent target policies under coverage assumptions, and demonstrate a formal separation between moodll-based and model-free OPE in POMDPs.
PRELIMINARIES
Notation. For a vector a, we use diag(a) to denote the diagonal matrix with a as the diagonal and use |a]; to denote its i-th element. We use e, denote the basis vector with the i-th element being one. For a positive integer n, we use [n] to denote the set 21, ,n.. For a matrix M, we use miin (M) and MT denote its minimum singular value and pseudo-inverse respectively. The ij
2

---

Published as a conference paper at ICLR 2025
entry of matrix M is denoted [M]s and the i-th row of M is denoted as [M] The L1 norm of |
matrix M is || ||1 = supx#0
|x|1
POMDP Setup. We use tuple S - O,, T, Id, d1) to specify a finite-horizon POMDP. Here H is the length of horizon; Sn. is the state space at step h: A is the action space with |A| = A; O₂ is the observation space at step h with |O,, O; R O - [0. 1] is the reward function; T {Th [Th]ee[H-1] the collection of transition dynamics where TA Sh x A +
Sr,
Sp+1: O = {Ox )e( is the collection of emission dynamics where O₂, S. On; dj E A(S)) is the distribution of initial state 81. All state, action, and observation spaces are finite and discrete. However, since the observation space can be very rich, the cardinality O may be arbitrarily large. Therefore, we aim to obtain sample complexity bounds that avoid any explicit dependence on O.
At the beginning of each episode in the POMDP, an initial state $1 drawn from d1. At each step h, the decision-making agent observes On, ~ Da sh),, along with the reward r' (ox), and then takes an action aイ. After this, the environment transitions to the next state sh+1 (- Sh, an), ) and the episode terminates after agz Note that the states $1:H are latent and unobservable to the agent.
History and Belief State. We use Tn = (0), a, ... On: an) E Th := 1', x A) denote the historical observation-action sequence up to step h. Given history The we define (T(TT) E IR Sa41l as its belief state vector and [bs(TT)]; P i Tx.)
Policies. A (history-dependentt) policy x = { T h where TA Th-1 x On - A(A) specifies the action probability given the history Th-1 and the current observation On. A memoryless policy only depends the current observation (i.e., Tr O₂ - A(A)). We define J ((x) as the expected
cumulative return under policy π.: (Tx) = E Σ R(ox)). Here we use E, to denote the
expectations under policy т, IP* for the probability of an event under the same policy and (-) for the marginal distribution of 8h, Gg under π.
The Outcome Matrix. For any step h E [H], we use fn. (0h, "oh,ah,'. (H-1,
FA == TI== x A) x On to denote the future after step h. For future fh. we define u(fr) E RiSI as its outcome vector where [u(Sa)]; = p** 88 = i)). Then we define the outcome matrix UFA E [x.||(ss where the row indexed by fn is u(fa). Note that the outcome matrix UF, depends the behavior policy TT. which we omit in the notation.
Off-policy Evaluation (OPE). In OPE, we aim to use an offline dataset collected by behavior policy Tr to estimate the expected cumulative return of a target policy Te, which is J(xe). The
"'H .TH ) : [n]). Without loss dataset 'D consists of n data trajectories ((o))) (i) d1j :....0p "'
(8)
(x) (i) (0)
known and we need to learn the emission and transition dynamics. In this paper, we focus on evaluating history-depender
of generality, we assume the reward function
we, which is a more
general setting compared to the memoryless тe considered in previous works (Uchara et al. 2023a Zhang & Jiang 2024). Therefore, the action a₁ depends on both the history Th-1 and the observation on. Throughout the paper, we make the following assumption:
Assumption A. We assume TT (a Th-1, 0n) ) is known and maxh, 1. molan 1.9..) S CA.
The parameter CA will not always show up in our upper bounds due to its looseness but it is a useful relaxation for making meaningful comparisons across different settings of interest in Table T
Learning Goal. We consider rich and large observation spaces and want to avoid paying explicit dependence on in the sample complexity. One way of achieving so is to use importance sampling
"The belief state is determined by the environment dynamics and is independent of the policy. Our definition the same as in Uehara et al. (2023a) Zhhan & Jiang (2024); this slightly different from the usual definition that also includes ox+1 as a conditional variable.
See discussion of uniform vs. pppicc-specific coverage in Section 3.1 the policy-specific counterpart of Assumption A is hound Te (=(an Th-1: 7h o Th-1, o)).
3

---

Published as a conference paper at ICLR 2025
Precup 2000), which avoids O but pays pioonenniil-in-ooiiionn quantity O(CA instead. We follow the setting of Uehara et al. (2023a): Zhang & Jiang (2024) and use function approximation to avoid both O and exponential-in- H. by assuming that the learner has access to a realizable model class M 9 More formally, we make the following assumption throughout (except in Section 5)
Assumption (Realizability). We assume that the learner given M, a class of POMDPs with the same S, A. O H, R components as M Furthermore, M E.M
Our goal is to achieve sample complexity bounds polynomial in log [M], H as well as appropriate coverage parameters introduced in the next section.
INFORMATION-THEOREII HARDNESS OF MODEL-FREE ALGORITHMS
We start by introducing the key assumptions that enable efficient OPE of memoryless policies in prior works. Then, in Section 3.2 we demonstrate via a lower bound that evaluating history-dependent T. is information-theoreee theoreticalll hard for any model-free algorithm (Theorem B). motivating the investigation of model-based algorithms in Section
3.1 KEY ASSUMPTIONS AND EXISTING RESULTS FOR MEMORYLESS Te
The prior work of Zhang & Jiang (2024) identify two key assumptions for OPE of memoryless policies in POMDPs, as introduced below.
Assumption C (Uniform Belief Coverage). Define
Σg,h Exg (
Assume that 1/0min (EH,).= S Cz,, wh E [H - 1] for some CH < 0c.
Assumption D (Multi-step Outcome Revealing). Define
Σş = U3 UF where Z, = (ls.))
Here diag(-) is a diagonal matrix with its diagonal being the input vector, and 1s, is the all-1 vector with dimension [ We assume that |ال S Cr, vh E [H - 1] for some CF < co.
Intuitively, Assumption C states that the belief vector (s(T)-1) spans all directions of RISA when Th-1 is generated with Th. and similar "linear coverage" conditions also found in the linear MDP literature (Jin et al. [021]] Xiong et al. (0022)).A A.suaattsssstion Diss an analogous condition but stated for the future after step h, and be interpreted that the future fr. can nontrivially predict the latent state 8/2 (thus the term "revealing"). In fact, when ff. can deterministically predict sh, Assumption D holds with F I (the identity matrix) and Cf
Uniform vs. Policy-specific Coverage Both assumptions above are only properties of the behavior policy ne. whereas the original conditions of Zhang & Jiang 2024 are tighter versions that account for the properties of as well. For example, their belief coverage does not require covering all directions of RlSs|, but only the direction of [d (sh. = >)]+es,,- We call the former uniform coverage (since it works for all target policies) and the latter policy-specific coverage (since it is specific to the Te under consideration). Our positive results in Section 4|ass depend on policy-specific coverage parameters, but they are different from the ones in Zhang Jiang (2024) due the technical differences between model-free and model-based analyses. Moreover, some definitions (e.g.. outcome coverage in /Zhang & Jiang (2024), which is the policy-specific version of our Assumption D) do not extend to history-dependent me. Therefore, we introduce the uniform version of the assumptions here for a clean and fair comparison.
"The algorithms in Uehara et al. (2023a): Zhang & Jiang (2024) are model- free and require value function and Bellman error classes; in Appendix A we show how these classes can be constructed automatically from M. which is common practice when comparing across model-based and model free algorithms (Chen & Jiang
2019 Sun et al. 2019).
The definitions here are based on Un. calculated using the dynamcis of M Later we will also be interested in variant of this assumption, where all quantities are replaced by their counterparts calculated using the dynamics of some candidate model M M.
4

---

Published as a conference paper at ICLR 2025
We now state the result of Zhang & Jiang (2024) in our setup (see Footnote 4 for how we invoke their model-free algorithms and analyses in our model-based setup), with proof in Appendix A
Theorem 1 (Corollary of Theorem 7 of Zhang & Jiang (2024)). Under Assumptions
C and
D assume that Th and Te are memoryless, there exists an algorithm (see Appendix
such
that, with probability at least 1- - o ( - -TT))l I &with sample complexity n = poly(H, (ogg. Ca. Cz, Cn), where [(Te) is the algorithm's 's estimation of (
3.2 HARDNESS RESULTS FOR HISTORY-DEPENDENN Te.
We now show that Theorem | cannot hold we make Te and Te general history-dependen policies. In fact, the hardness is not specific the algorithms of Uchara al. (2023a); Zhang & Jiang (2024),
but applies generally to a broad range of model-free algorithms, as defined below.
Definition 2 (Model-free algorithm). We say that an algorithm for OPE POMDPs model-free, it only queries the action distribution of Te on trajectories observed in the offline dataset, i.e., the
only information known about Te Te T-loo ,a ....0% 0% for all [H] [n].
(6)
This definition is satisfied by the algorithms of Uehara et al. (023a); Zhang & Jiang 2024). When
it specialized to the MDP setting, it is also satisfied by most standard algorithms considered
model-free, such as importance sampling (Precup) 2000), Fitted-Q Evaluation (Ernst et al. 2005
Le et al., 2019 Voloshin et al. 2019). and marginalized importance sampling Liu al.] (2018);
Uehara et al. (2020). The spirit of focusing on how algorithms access and process information in
the input is consistent with prior works that show model-free and model-based separation from a
learning-theoretic perspective (Chen & Jiang 2019: Sun et al. (019)).
Moreover, the hardness still holds even we make the problem easier two aspects:
1. We keep memoryless (the more general setting is that is also history-dependent just as T.). Assumption D states that (multi-step) future can reveal the latent state 8n. The online POMDP literature has related and stronger assumption that the immediate observation on plays the same role (Liu et al. 2022a):
Assumption (Single-step Outcome Revealing). Define
Σo. = 0 WT 'h,, where Wr : diag(O,,s.,)
We assume |E s Co th E [ - 1] for some Co < co.
The interpretation of this assumption is similar to multi-step revealing Assumption D but requires that the immediate observation où (instead of the entire future as in multi-step revealing) is sufficient for making nontrivial predictions of 8). Therefore, the single-step outcome revealing assumption (Assumption E should be treated as generally stricter than its multi-step counterpart (Assumption DD. though a rigorous and quantitative comparison between Co and Cj is somewhat complicated and defer the discussion Appendix G Variants of this assumption have been proposed in online learning in POMDPs (Luu et al. 2022a). but the original version has poor scalability w.r.t. the number of observations, as pointed out by Chen al. (2022) and Zhang & Jiang (2024); see Example 1 of Zhang & Jiang (202)) for further discussions. Our Assumption 4 fixes the issue by using similar inverse- weighting scheme as Assumption | and enjoys better scaling with the size of the observation space. For example, when On can uniquely determine 8h, Σo, I and is independent of the number of observations.
Theorem 3 (Information -theoretttt hardness of model-free algorithms). In the same setup as Theo- rem 7 if we allow Te to be history-dependent (but ne is still memoryless), no model-free algorithm can achieve the polynomial sample complexity guarantee. This still holds even if we replace Cf with the single-step revealing parameter Co.
Proof. Consider the following POMDP: for 1 < h < transition before h = H 1 is trivial chain), and Cn 1. At the last step H, there are two states
there only one state 8h,1 (thus
'Here we assume that the algorithm has knowledge of the value of CJ and Cx. The analyses can be easily adapted to the case where the precise value of C5 (or Cx)) is unknown but a nontrivial upper bound (e.g.. constant multiple of the value) known.
5

---

Published as a conference paper at ICLR 2025
TH.L and HHRR- The emission is identity, i.e., On, Sh: meaning that the POMDP is also MDP and Co = C5 = 1. There are two actions, L and R. At step H 1, taking L and transitions to &H.L L and s, respectively. The agent only receives reward of 1 upon reaching state s.,L. The model is known so .M| = 1. The behavior policy тà is uniformly random, implying CA = 2. Consider two target policies, иh and 22. Both policies take action I. if historical actions do not include R for 1 S h < H -2 2. At step H - 1, J takes action L if all previous actions are L, while л2 takes action R if all previous actions are L. Under any history that includes least one I action, both policies yield the same action, and the concrete choice does not matter
((11) 1 and ((T2) = O, as running Ti produces an all-L sequence, and running T2 produces L..... L. R. However, since the two policies have identical action choices under all other action sequences, a model-free algorithm can only tell them apart if the sequence I.....: I. of length H - is observed in the offline data, which only happens with negligible O(1/2#) prohability. With overwhelming probability, J and Ty will look identical to the algorithm but their J(.) differs by a constant of 1. so algorithm can predict them well simultaneously up to 1/2 accuracy, unless it is given (2 samples to observe the L..., L sequence with nontrivial probability. However, in this problem, Co. Cy. Cn. CA. e, [M] are all constants, so the sample complexity in Theorem 1 is poly(H), which cannot explain away the exponential in 2) Thus we conclude that no model-free algorithm can achieve Theorem guarantee when We is allowed to be history dependent.
The counter-intuitive part of the construction is that the model is fully known (M = {M**), and the hardness comes merely from the fact that model-free algorithms have limited access to Te and cannot distinguish between two distory-dependent policies with very different returns from data. In fact, we remove the model-free restriction, the problem instance is trivial to solve as we can calculate JM- (Tx) by rolling out ne in M
4 POSITIVE RESULTS FOR MODEL-BASED ALGORITHMS
The negative result from the previous section naturally motivates the investigation of model-based algorithms, i.e., those that do not respect the restriction of Definition 2 Model-based algorithms fit the POMDP dynamics from data and use the learned model to evaluate тe: the latter step can often be achieved by rolling out trajectories in the learned model, where we need to query म. on synthetic trajectories generated by the learned model, thus violating Definition 2 and potentially cireumventing the hardness in Theorem 3
Concretely, we consider a very natural algorithm based on Maximum Likelihood Estimation (MLE). is, fact, quite surprising that such a simple algorithm has not been analyzed under relatively general assumptions for OPE in POMDPs. The algorithm is as follows:
Pre-filtering: We construct M' C M where all models that violate Assumption (for Section 4. where we assume single-step revealing in the guarantee) or (for Section 4.2 where we assume multi-step revealing) are excluded from MM' Such a filtering step is common in the POMDP learning literature (Liu et al. 2022a), and in Section 5 we show why MLE estimation requires this as a pre-processing step and will fail otherwise.
MLE: Let P7,, stands for the probabilities under policy i and model M. The model is learned
M MaXMEM Ei_ log 1i
Prediction: We use the expected return of xe in M, J J (Te), as estimation for ((Te)
4.1 GUARANTEE UNDER SINGLE-STEP OUTCOME REVEALING
We first show that the model-based algorithm enjoys a polynomial guarantee when we assume the stronger single-step outcome revealing (Assumption E instead of its multi-step version (Assump-
Rolling and ø2 leads deterministic outcomes, which characteristics of open-loop policies (i.e., action only depends h and independent of (7a-1, However, ni and T2 cannot be open-loop simultancously, otherwise they cannot have identical action choices on histories that include R.
*This requires the algorithm to have knowledge of the value or some nontrivial upper bound of Go (or Cr). Such knowledge is also required for Theorem

---

Published as a conference paper at ICLR 2025
tion D) Recall that even with this stronger revealing assumption the model-free algorithms still cannot provide polynomial guarantees.
Theorem 4. Given a realizable model class M, let model M be the MLE within M' using the dataset D. Under Assumption
E
with probability at least 1 5, we have
log M
[((Te) - (T)) 50
71
where
Donion ET,
Te (ap Th-1 (1)1110))|(BB (B, B,, (Th
Car = max
he [1]
Eon.an an
Ery
Th(an Th-1, On (B,. Bn))abs((T-1)))
Here B₁ (o, and the observable-operater parameterization of M under single-step revealing (see Appendix and Bn, is defined similarty for M. Furthermore, when Assumptions A hold, we have
Car.1 S CACH.
The proof deferred to Appendix D.I] To the best of our knowledge, this the first polynomial sample-complexity bound for model-based OPE of history-dependent target policies in POMDPs with large observation spaces. In addition to the quantities that have already been introduced, the bound depends on new coverage parameter, Cet,11, which we show can be upper bounded by CACH. With this relaxation, Theorem 4 limplies a formal poly H, log() CA. CF, Cx) sample complexity. setting where mrrel--free OPE provably cannot handle (Theorem B
However, as mentioned in Section 3.2 the CACH bound is relaxing Cen,1 to "uniform coverage" parameter, whereas Can, itself is policy-sepcific (note the dependence on T. on the numerator) and can be much tighter. For starters, when म. = To, it is obvious that Ceft. = 1. More generally, Ceff, captures the discrepancy between the model estimation error under the distributions induced by m. and mT. Unlike the commonly used L2 norm of Bellman error in offline MDPs (Xie et al. (021)), we use the L1 norm the estimation error, which better leverages the property of the belief state vector (| 1). The advantage of L1 over L2 is also discussed in Zhang & Jiang (2024), where they note that L1/ Tex Hölder's inequality can help reduce the dependence on S in the analysis. In the special case of the MDP setting (i.e., 8h, on and O2 I), we have (see Appendix B
d (sh, an)
Can,1 S max max h ag (s an)
This recovers a coverage coefficient in the form of state-action density ratio, which is commonly used in the offline MDP literature MMunos 2024
2007
Antos et 2008 Chen & Jiang 2019 Jiang & Xie
4.2 GUARANTEE UNDER MULTI-STEP OUTCOME REVEALING
Theorem 4 relies on Assumption which requires that the observation reveals sufficient information about the latent state. However, this assumption may not hold in more complex partially observable environments. We show that the model-based algorithm can also enjoy polynomial guarantees under the weaker multi-step revealing condition (Assumption D). if we impose that the behavior policy Te is memoryless (the target policy He is still history dependent).
Theorem 5. Given realizable model class M, let model M be the MLE within M' using dataset D. Suppose Ty is memoryless and Assumption D hold, with probability at least 5, we have
log
[M|
[(TT.) J.z(TT (Te)) 50
71
7

---

Published as a conference paper at ICLR 2025
where
Eos an Esg Te (as Th-1, (B B,) bs (Th-
Ceffion
max
(2)
he(H 1-1--111 Eon an Eer ma(an Th-1, on (B Bs) (Ta-1)ll
where B,, = (o an) is the observable-operate parameterization of M under multi-step revealing (Appendix C.. Furthermore, similar the single-step case, when Assumption AasumptionChhole Coold we can upper bound Ceffim as
Cetf.m S CACH.
The proof is deferred to Appendix D.2 Our theorem shows that when the behavior policy T6 is memoryless, only polynomial samples are required to evaluate the target policy Te under Assumption D The structure the bound is similar to that of Theorem except that replaces Co with its multi-step counterpart Cy.
Interestingly, our results reveal that a memoryless behavior policy can accurately evaluate history- dependent target policies when certain coverage conditions satisfied. This somewhat counter- intuitive, as one might expect that only history-dependan behavior policies could evaluate history- dependent target policies. However, this conclusion aligns with findings in latent MDPs (Kwon et al. 2024), which are a special case of POMDPs, This insight encourages the use of memoryless policies with good coverage for online exploration, consistent with many online algorithms that
employ uniform exploration policies (Efroni et al. 2022
Liu et al. 2022a Uehara et al. 2022a Guo
al. 2023b).
STATE-SPACE MISMATCH AND MODEL MISSPECIIFICTTION
So far we assume the agent is given realizable model class with the ground-truth latent-state space size (S). Although the knowledge of [S] is commonly assumed in both OPE in POMDPs (Uchara
al. 2023a Zhang & Jiang 2024) and online learning for POMDPs (Jin al., 2020 Liu al. 2022a obtaining this information in practice can be challenging, as the latent state space is an ungrounded object. A natural concern is that of state-space misspecification (Kulesza al., 2014, 2015): what if the state space of models in M (denoted as S in this section) is different from that of M This question has largely cluded the recent literature RL in POMDPs, and below we show that taking it seriously reveals interesting insights.
One immediate consequence of S A SS] is that the model realizability assumption M* E . no longer makes any sense. natural rescue is note that it is still possible to have models in M that induce the same observable process as M that is, they always generate the same distribution of observation-action sequences given any policy. For example, if S > [S], this weaker notion of realizability (based on observable equivalence) holds, since one can simply add dummy latent states to M to create equivalent model with larger latent-state spaces. More concretely:
still hope
Definition 6. We say that M satisfies observable-equivalene realizability, if there exists M E M, such that PM (on+1lo .i....,hh. an) is the same as Pa (ou+1l01, ........M "h, az) for all h and 01. 01 .0.............................. Oh-1-
We now show a somewhat counter-intuitive result: replacing M* E . with observable-equivalent realizability will break the previous guarantee (c.g., Theorem
Theorem 7. Take the same setting as Theorem|4 with model realizability (Assumption B replaced by the weaker observable observable-equivalen realizability (Defiiition 6). The model-basee algoritim, either with or without the pre-filtering step (Section cannot achieve the polynomial guarantee Theorem
Proof. The action space is {L, R} and rewards are only received at final step H. M = {M1, M2). ie., there are only two candidate models in M. All the models including M* share the same observation space, which contains only observation for h [ - 1] and two observations at step H. M, and M2 have the same state space as M at the final step H: 8 Sgood and Stads state Sgood always generates good with reward 1 and state Shad always generates Obad with reward 0. In M1,
8

---

Published as a conference paper at ICLR 2025
the state space at step h E [H- i (L For h [H 2], any state- pair (5h, an) deterministically transitions to the next state $h-1 = ($p, an). where an is appended to 8y. At step H - 1, all states transition to Sgodd when action L is taken; otherwise, they transition to Stad- M2 shares the same state space and dynamics as M1, except that at step H - 1, the all- R state will transition to Sgood if action R is taken. The ground-truth model M has only one state each step h E [H - 1]. At step H - 1. it transitions to 5good if action L is taken; otherwise, it transitions to Sbad- We can verify that Md produces the same observable process as M For M since there is only one state and one observation for h E [H 1]. we have Co Cu 1. The behavior policy To. is uniformly random with C^ = 2. while the target policy me always takes action R.
We first consider the case where the pre-fitterig step is skipped, so both M1 and M2 are considered for MLE. To estimate Te accurately, the algorithm needs to output M M1 (Mz's prediction is wrong by a constant), but the empirical MLE losses (T) of M1 and M2 are always identical unless the all-ß action sequence is contained in the dataset Since n, is uniformly random, (22"))
samples are needed to include this sequence with nontrivial probability. Therefore, with only poly samples, MLE cannot distinguish between M1 and M2, and hence cannot accurately estimate (
If the algorithm does perform the pre-filterngg step, note that Co = oo for both models as |Sa] > |O
for h > 1 and Σo., non-invertible, so both models will be climinated and the algorithm cannot be executed.
In the model-based algorithm in Section we assume revealing assumptions (Assumptions or D on M* and perform pre-filtering The negative result here sheds light on this and reveals the underlying reason: what we really need is not M*, but the learned model M satisfy revealing properties. In the proof of Theorem 7 no models in M satisfy single-step revealing (Assumption D which leads to poor sample efficiency. Inspired by this observation, we present the following result
that handles state-space mismatch properly. We assume |S| can be either smaller or greater than [S], and approximate version of observable
realizability.
Theorem 8. Given a model class M such that each M E M satisfies Assumption D Let model M
be the MLE within M using datasel DD Suppose Tb is memoryless, with probability at least -
(TTe) - (T(T) s o 11 1P
log
IMI
+ Eapprxx
where Cof.m is defined in Eq. (2) and Eapprox is the approximation error of M:
Eapprox
min MEM
[log [oggPrr PM, (T() -log177 (1)
17 (T
The proof is deferred to Appendix E Here we assume that all M E M satisfies Assumption D It actually fine if M itself does not satisfy the assumption, as long as one of models M E M is observable-equiivlent to M* up to approximation error Eapprox.
6 RELATED WORKS
OPE in POMDPs.
There are two main directions in the study of OPE in POMDPs: OPE in
confounded POMDPs and OPE in unconfounded POMDPs. OPE in confounded POMDPs (Zhang &
Bareinboim| 2016 Namkoong et al. 2020 Tennenholtz et al., 2020 Nair & Jiang 2021 Shi et al. 2022] Xu et al., 2023 Bennett & Kallus 2024) assume that the actions from the behavior policy depend only on the latent state. As result, these methods are inapplicable to our unconfounded setting, where the latent state is unobservable, and the behavior policy depends solely on the obser- vations and actions. A line of research (Hu & Wager 2023 Uehara et al. 2023a Zhang & Jiang 2024) investigates the same unconfounded setting as ours. Hu & Wager (2023) employ multi-step importance sampling, which leads to an exponential dependence on the horizon length. Uehara et al.) (2023a): Zhang & Jiang (2024) use model-free methods that estimate the future- -euundde value functions of the target policy, but their approaches focus memoryless target policies or policies with limited memory. In this paper, we leverage model- -ased methods and provide polynomial
sample complexity bounds for history-dependent target policies.

---

Published as a conference paper at ICLR 2025
OPE in MDPs. OPE is an important problem in MDPs and many works have studied it, including
importance sampling methods (Precup 2000; Li et al. 2011). 1.. marginalized importance sampling
approaches (Liu et al. 2018 Xie et al. 2019:] Kallus & Uchara, 2020 Katdare et al. (023). doubly
robust estimators (Dudik et al. 2011; Thomas & Brunskill, 2016, Jiang Li 2016 Farajtabar et al.
2018: Xu et al., 2021) and model-
methods (Eysenbach
al.) 2020 Voloshin et al. T
Yin et al.) 2021) D. However, most of these methods (except for importance sampling) require the Markovian property of the environment. Applying these techniques POMDPs either does not work or results in an exponential dependence on the horizon length. Xie et al. (219)) demonstrated that state-action coverage sufficient achieve polynomial sample complexity
MDPs. However, as shown by Kwon et al. (024), latent state coverage is insufficient in POMDPs due to their partial observability. In this paper, we consider coverage conditions for both histories and outcomes, a direction that is also explored in Zhang & Jiang (2024) for model-free methods.
Online Learning in POMDPs. Online learning algorithms in POMDPs have been extensively studied. Krishnamurthy et al. (2016) show that the lower bound on the sample complexity of learning general POMDPs is exponential in the horizon, and later works have focused on circumventing the hardness with additional assumptions. [eehara et al. (2023b) propose provably efficient algorithms for POMDPs with deterministic transition dynamics. Guo al. (vizzadeeiil et al. (2016); Xiong et al. (2022b) assume the environment satisfies the reachability assumption or that exploratory data is available. There are also many works studying sub-classes of POMDPs, including latent
MDPs (Kwon et al., |021 2024). decodable POMDPs (Krishnamurthy et al. 2016 Diang et al. 2017]
Du et al. 2019:
et al. 2002), weakly revealing POMDPs (Jin et al. [2200] Liu et al. 2022a b).
low-rank POMDPs Wang al.] 2022 Guo et al. 2023b), POMDPs with hindsight observability (Lee)
et al., 2023; Guo et al. 2023a) and observable POMDPs (Golowich et al.) 2022a b), except for
the model-free algorithm of Uchara et al. (2022a) based on the future-dependent value function
framework (Uchara et al. 2023a
CONCLUSION
We studied OPE of and showed provable separation between model-free and model-based methods in several settings. A major open problem is whether model-based algorithm can handle history-dependent na and multi-step revealing (the "?" mark in Table TT. and resolving this question will provide a more comprehensive picture of the landscape of OPE in POMDPs.
target policies in POMDPs with large observation spaces,
ACKNOWLEDGMENTS
Nan Jiang acknowledges funding support from NSF CNS-2112471, NSF CAREER IIS-2141781, Google Scholar Award, and Sloan Fellowship.
REFERENCES
András Antos, Csaba Szepesvári, and Rémi Munos. Learning ncar-optimal policies with bellman- residual minimization based fitted policy iteration and single sample path. Machine Learning, 71:89-129, 2008
Kamyar Azizzadenesheli, Alessandro Lazaric, and Animashree Anandkumar. Reinforcement learning of pomdps using spectral methods. In Conference on Learning Theory, pp. 193-256. PMLR, 2016.
Andrew Bennett and Nathan Kallus. Proximal reinforcement learning: Efficient off-policy evaluation in partially observed markov decision processes. Operations Research, 72(3):1011-1086, 2024.
Léon Bottou, Jonas Peters, Joaquin Quiñonero-Candela. Denis X Charles, D Max Chickering, Elon Portugaly, Dipankar Ray. Patrice Simard, and Ed Snelson. Counterfactual reasoning and learning systems: The example of computational advertising. Journal of Machine Learning Research, 14 (1),, 2013.
10

---

Published as a conference paper at ICLR 2025
Olivier Chapelle, Eren Manavoglu, and Romer Rosales. Simple and scalable response prediction for display advertising. ACM Transactions on Intelligent Systems and Technology (TIST), 5(4):1-34, 2014.
Fan Chen, Yu Bai, and Song Mei. Partially observable rl with b-stabilitty: Unified structural condition and sharp sample-efficient algorithms. arXiv preprint arXiv:2209. 2022.
Jinglin Chen and Nan Jiang. Information-theoreti considerations in batch reinforcement learning. In International Conference Machine Learning, pp- 1042-1051, PMLR, 2019.
Simon Du, Akshay Krishnamurthyy Nan Jiang, Alekh Agarwal, Miroslav Dudik, and John Langford. Provably efficient rl with rich observations via latent state decoding. In International Conference on Machine Learning, pp. 1665-1674. PMLR, 2019.
Miroslav Dudík, John Langford, and Lihong Li. Doubly robust policy evaluation and learning. arXiv preprint 1rXiv:1103.4600 2011.
Yonathan Efroni, Chi Jin, Akshay Krishnamurthy, and Sobhan Miryoosefi. Provable reinforcement learning with short-term memory. In International Conference Machine Learning, pp. 5832- 5850. PMLR, 2022.
Damien Ernst, Pierre Geurts, and Louis Wchenkel. Tree-based batch mode reinforcement learning. Journal of Machine Learning Research, 6, 2005.
Damien Ernst, Guy-Bart Stan, Jorge Goncalves. and Louis Wehenkel. Clinical data based optimal sti strategies for hiv: a reinforcement learning approach. In Proceedings of the 45th IEEE Conference Decision and Control, pp. 667-672. IEFE, 2006.
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. 13916, 2020.
Mehrdad Farajtabar, Yinlam Chow, and Mohammad Ghavamzadeh. More robust doubly robust off-policy evaluation. In International Conference on Machine Learning, pp. 1447-1456. PMLR, 2018.
Noah Golowich, Ankur Moitra, and Dhruv Rohatgi. Learning in observable pomdps, without computationally intractable oracles. Advances in neural information processing systems, 35: 1458-1473, 2022a.
Noah Golowich, Ankur Moitra, and Dhruv Rohatgi. Planning in observable pomdps in quasipolyno- mial time. arXiv preprint UrXiv:2201.04735, 2022b.
Jiacheng Guo, Minshuo Chen, Huan Wang, Caiming Xiong, Mengdi Wang, and Yu Bai. Sample-efficient learning of pomdps with multiple observations in hindsight. arXiv preprint arXiv:2307.02884, 2023a.
Jiacheng Guo, Zihao Li, Huazheng Wang, Mengdi Wang, Zhuoran Yang, and Xuezhou Zhang. Prov- ably efficient representation learning with tractable planning in low-rank pomdp. In International Conference on Machine Learning, pp. 19677119977. PMLR, 2023b.
Zhaohan Daniel Guo, Shayan Doroudi, and Emma Brunskill. A pac rl algorithm for episodic pomdps. In Artificial Intelligence and Statistics, pp. 510-518. PMLR, 2016.
Yuchen Hu and Stefan Wager. Off-policy evaluation in partially observed markov decision processes under sequential ignorability. The Annals of Statistics, 51
2023.
Herbert Jaeger. Observable operator models for discrete stochastic time series. Neural computation, 12(6):3311-1998 2000.
Nan Jiang and Lihong Li. Doubly robust off-policy value evaluation for reinforcement learning. In International conference on machine learning, pp. 652-661. PMLR, 2016.
Nan Jiang and Tengyang Xie. Offline reinforcement learning in large state spaces: Algorithms and guarantees. 2024.
11

---

Published as a conference paper at ICLR 2025
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. Contex- tual decision processes with low bellman rank are pac-learnabl.. In International Conference on Machine Learning, pp. 1704-1713, PMLR, 2017.
Chi Jin, Sham Kakade, Akshay Krishnamurthy, and Qinghua Liu. Sample-efficient reinforcement learning of undercomplete pomdps. Advances in Neural Information Processing Systems, 33: 15530-18539 2020.
Ying Jin, Zhuoran Yang, and Zhaoran Wang- Is pessimism provably efficient for offline ri? In International Conference on Machine Learning, pp. 5084-5096. PMLR, 2021.
Nathan Kallus and Masatoshi Uchara. Double reinforcement learning for efficient off-policy eval- uation in markov decision processes. Journal of Machine Learning Research, 21(167):1-63, 2020.
Pulkit Katdare, Nan Jiang, and Katherine Rose for off-environment policy evaluation. In Conference Robot Learning, pp. 3778-3788. PMLR, 2023.
Marginalized importance sampling
Akshay Krishnamurthy, Alekh Agarwal, and John Langford. PAC reinforcement learning with rich observations. In Advances in Neural Information Processing Systems, 2016.
Alex Kulesza, N Raj Rao, and Satinder Singh. Low-rank spectral learning. In Artificial Intelligence and Statistics, pp. 522-530. PMLR, 2014.
Alex Kulesza, Nan Jiang, and Satinder Singh. Low-rank spectral learning with weighted loss functions. In Artificial Intelligence and Statistics, pp. 517-525. PMLR, 2015.
Jeongyeol Kwon, Yonathan Efroni, Constantine Caramanis, and Shie Mannor. RI for latent mdps: Regret guarantees and a lower bound. Advances in Neural Information Processing Systems, 34: 24523-24534, 2021.
Jeongyeol Kwon, Shie Mannor, Constantine Caramanis, and Yonathan Efroni. RI in latent mdps is tractable: Online guarantees via off-policy evaluation. arXiv preprint arXiv:2406.01389 2024.
Hoang Le, Cameron Voloshin, and Yisong Yue. Batch policy learning under constraints. In Interna- fional Conference on Machine Learning, pp. 3703-3712, PMLR, 2019.
Jonathan Lee, Alekh Agarwal, Christoph Dann, and Tong Zhang. Learning in pomdps is sample- efficient with hindsight observability. In International Conference on Machine Learning, pp. 18733-18773. PMLR, 2023.
Lihong Li, Wei Chu, John Langford, and Xuanhui Wang. Unbiased offline evaluation of contextual- bandit-basee news article recommendation algorithms. In Proceedings of the fourth ACM interna- tional conference on Web search and data mining, pp. 297-306, 2011.
Qiang Liu, Lihong Li, Ziyang Tang, and Dengyong Zhou. Breaking the curse of horizon: Infinite- horizon off-policy estimation. Advances in neural information processing systems, 31, 2018.
Qinghua Liu, Alan Chung, Csaba Szepesvári, and Chi Jin. When is partially observable reinforcement learning not scary? In Conference on Learning Theory, pp- 5175-5220. PMLR, 2022a.
Qinghua Liu, Csaba Szepesvári, and Chi Jin. Sample-efficient reinforcement learning of partially observable markov games. Advances in Neural Information Processing Systems, 08:188966-8308 2022b.
Travis Mandel, Yun-En Liu, Sergey Levine, Emma Brunskill, and Zoran Popovic. Offline policy evaluation across representations with applications to educational games. In AAMAS, volume 1077, 2014.
Rémi Munos. Performance bounds in I p-norm for approximate value iteration. SIAM journal control and optimization, 46(2):541-561, 2007.
Susan A Murphy, Optimal dynamic treatment regimes. Journal of the Royal Statistical Society Series B: Statistical Methodology, 65(2):331-355, 2003.
12

---

Published as a conference paper at ICLR 2025
Yash Nair and Nan Jiang. A spectral approach to off-policy evaluation for pomdps. arXiv preprint arXiv:2109. 10502, 2021.
Hongseok Namkoong, Ramtin Keramati, Steve Yadlowsky, and Emma Brunskill. Off-policy policy evaluation for sequential decisions under unobserved confounding. Advances in Neural Information Processing Systems, 33: 185:18819-11 19-18831, 2020.
Doina Precup. Eligibility traces for off-policy policy evaluation. Computer Science Department Faculty Publication Series, pp. 80, 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, pp. 20057-20094. PMLR, 2022.
Wen Sun, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Model-based in contextual decision processes: Pac bounds and exponential improvements over model-free approaches. In Conference on learning theory, pp. 2898 -933.. PMLR, 2019.
Guy Tennenholtz, Uri Shalit, and Shie Mannor. Off-policy evaluation in partially observable en- vironments. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 10276-10283, 2020.
Georgios Theocharous, Philip S Thomas, and Mohammad Ghavamzadeh. Ad recommendation systems for life-time value optimization. In Proceedings of the 24th international conference on world wide web, pp. 1305-1310, 2015.
Philip Thomas and Emma Brunskill. Data-efficient off-policy policy evaluation for reinforcement learning. In International Conference on Machine Learning, pp. 2139-2148. PMLR, 2016.
Masatoshi Uehara, Jiawei Huang, and Nan Jiang. Minimax weight and q-function learning for off-policy evaluation. In International Conference on Machine Learning, pp. 9659-9668. PMLR, 2020.
Masatoshi Uchara, Ayush Sckhari, Jason D Lee, Nathan Kallus, and Wen Sun. Provably efficient reinforcement learning in partially observable dynamical systems. Advances in Neural Information Processing Systems, 35:578-599 2022a.
Masatoshi Uehara, Chengchun Shi, and Nathan Kallus. A review of off-policy evaluation in rein- forcement learning. arXiv preprint arXiv:2212.06355, 2022b.
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. Advances in Neural Information Processing Systems, 36, 2023a.
Masatoshi Uehara, Ayush Sekhari, Jason Lee, Nathan Kallus, and Wen Sun. Computationally efficient pac rl in pomdps with latent determinism and conditional embeddings. In International Conference on Machine Learning, pp. 34615-34641. PMLR, 2023b.
Cameron Voloshin, Hoang M Le, Nan Jiang, and Yisong Yue. Empirical study of off-policy policy evaluation for reinforcement learning. arXiv preprini arXiv: /91 106854, 2019.
Cameron Voloshin, Nan Jiang, and Yisong Yue. Minimax model learning. In International Conference on Artificial Intelligence and Statistics, pp. 1612-1620. PMLR, 2021.
Lingxiao Wang, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Embed control partially observed sys- tems: Representation learning with provable sample efficiency, arXiv preprint 2345, 2022.
Tengyang Xie, Yifei Ma, and Yu- Yu-Xiang Wang. Towards optimal off-policy evaluation for reinforce- ment learning with marginalized importance sampling. Advances in neural information processing systems, 32, 2019.
Tengyang Xie. Ching- An Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal. Bellman-ccosistern consistent pessimism for offline reinforcement learning. Advances in neural information processing systems, 34:6683-6694, 2021.
13

---

Published as a conference paper at ICLR 2025
Wei Xiong, Han Zhong, Chengshuai Shi, Cong Shen, Liwei Wang, and Tong Zhang. Nearly minimax optimal offline reinforcement learning with linear function approximation: Single-agent mdp and markov game. arXiv preprint arXiv:2205.15512, 2022a.
Yi Xiong, Ningyuan Chen, Xuefeng Gao, and Xiang Zhou. Sublinear regret for learning pomdps. Production and Operations Management, 3109):499-3304, 2022b.
Tengyu Xu, Zhuoran Yang. Zhaoran Wang, and Yingbin Liang. Doubly robust off- off-policy actor-critic: Convergence and optimality. In International Conference on Machine Learning, pp. PMLR, 2021.
Yang Xu, Jin Zhu, Chengehun Shi, Shikai Luo, and Rui Song. An instrumental variable approach to confounded off-policy evaluation. In International Conference on Machine Learning, pp- 38848 38880. PMLR, 2023.
Ming Yin, Yu Bai, and Yu-Xiang Wang. Near-optimal provable uniform convergence offline policy evaluation for reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pp. 1567-1575. PMLR, 2021.
Junzhe Zhang and Elias Bareinboim. Markov decision processes with unobserved confounders: causal approach. Purdue Al Lab, West Lafayette, IN, USA, Tech. Rep, 2016.
Yuheng Zhang and Nan Jiang. On the curses of future and history in future- deeundde value functions for off-policy evaluation. arXiv preprint arXiv:2402. 14703, 2024.
14

---

Published as a conference paper at ICLR 2025
A PROOF OF THEOREM
Proof. We use the algorithm described Section of Zhang & Jiang 2024). Given the model class M, we construct the function classes V and needed by their algorithm. First, apply the same pre-filtering as the model-based algorithm to obtain M'.. For each E _MM, we include the corresponding future- seture-dependent value function (FDVF) VF (their Definition 3) in V. For each model pair M1, M2 E MM, we include M,, Vr,M, (their Definition 4) in E, where Vy,M, is the FDVF in model M2 and M, is the Bellman residual operator under model M1. Hence, we have IV & LM| and E| S MM Meanwhile, their Assumptions 5 and 6 naturally satisfied. From Assumption their Assumption 11 also satisfied with C2.2 I C2+- According to their Lemma 5, have || 2o < HCr. Then, invoke their Theorem and obtain that w.p. 1 6,
| Calog([M]/0)
[J(me) (TT))
71
B CALCULATION OF THE MDP CASE
For MDP, we have on = Sn. and O2 = I. Hence, given Th-1- 8h, ah.
BB an)s))a)) By an) Og Oxbs(Tn-))) ||
Te(a; Th (h-11 sn)
Me(an
Th-1; shh
(Tnnnn Tnaa, )diag (sh I 1))sss( (T-
<e(aa
Th Th-1. 8h))
PM- (sh (h-1)) 1P an) PP (s' 8h, an)
-P (sh, an
Tb-1) ( shh an) Par. She an)a1l
Fix step h, the numerator in C becomes
8h, Σ (sh, an) || 8h, ax) PMM 1 an)
Similarly, the denominator is
Σ
dh (sn, an) (PT
Sh, shyan) PMM (.1sh, an)l
Then we have
Cef.11 S max max d (sh, an)
Sh on Th (8h, ap))
C OBSERVABLE OPERATOR MODELS
We introduce the observable operator models (OOMs) (Jaeger 2000). which (for our purposes) can be viewed as reparameterization of POMDPs. OOMs have seen wide use in recent POMDP literature (especially in the online setting (Liu al. 2022a ) and play crucial role in our model-based analyses.
Single-step Revealing. We first introduce the OOM used in environments satisfying single-step revealing condition. Given model parameters M (T, (,,i), we write the initial observation distribution by and observable operators as
bo 01d1 E O
B, a) 0/+1 ahangi ()) Roo
where Th, S. 1 || with (Thalis (n = st. =. a). Different from the pseudo-inverse in Liu et al. (2022a), we use the weighted version (Zhang & Jiang 2024) defined as follows:
of = =-- E.1, W
15

---

Published as a conference paper at ICLR 2025
where Lo,s and Wi. are defined in Assumption E
With the OOM representaion, for any trajectory Th = (01,, a1.01.1.. oh, an), , the probability of generating т) with policy л can written as
Pir. (Tr) (T)) (eo, B
...B........ (o1, ( a1)b)),
where <(T.) I a(ap oh Th-1) is the action probability of generating Th given policy Moreover, let b(Tr) (I (ow, an:) bo, have the following observation:
b(m)) IP M- (Th Ds(T))(TT)
where M- (m.) = c B (on-1, 1,--1,,4111 4h-1) B1 (01, Ybo is the environment probability of gener- ating Th- The relationship between b(Tx) and belief state vector (s(Tr) is crucial for developing coverage conditions the belief state.
Multi-step Revealing. Next, introduce the OOM in the multi-step revealing setting. Recall that fa denotes the future after step h, and Ur. is the outcome matrix, where the row indexed by fn represents its corresponding outcome vector. The observable operators are defined
bg = U E ER!F.
ao, UF A+1 Th )) FRAslx|Fal
Here U.. E Z is the weighted pseudo-inverse and Er Zn are defined in Assumption For any history Th-1 and future fh. the probability of generating (7h-1, fn) with policy т is written
PT ( /b) =(m--1) (e), Bn-1 (0h-1, ab-1) ... B1 (01. bbo)
Similar to the single-step step case, we also have the following relation between b(7)) and bs(T.):
b(Tx) IP (Tx) (=.)
D PROOFS FOR SECTION 4
We first provide a lemma showing that a model can have accurate probability estimation trajectories when it estimates the historical data well. The proof can be found in Appendix B of Liu al. (2022a).
Lemma (Restatement of Proposition 14 of of et al. (022a)). There exists a universal constant c such that for any 8 (0, 1]. with probability least 1 - ò, for all M E M, it holds that
2
Σ
log p 1 (T(9)
log [M
P (r(0)
Σ
(T) - P ()5-((T)
(T))
x
TEITH (O, X
Since the ground-truth M E M, for the MLE M, we further have
clog IM
Σ
p (7)
IPL (T) s
SMLE-
M
n
TEI
In addition, marginalizing two distributions will not increase the TV distance, for any h E [H - -1, the following inequalities hold,
Σ Th.0k+11
Too (Th 0h+1) P (Th, Oht1)
EMILE,
(3)
Σ Thefftt
p (m fh+1)
Pob (T Sn+2)
SEMEE
(4)
16

---

Published as a conference paper at ICLR 2025
D.1 PROOF OF THEOREM 4
To begin with, we first state the following lemma for our operators B, which is adapted from Lemma
32 of Liu et al. (2022a). We use Bra++1 to denote - B (a, (kw,
Lemma 10. For any index O S < h < H 1, trajectory Tj [Ow A), vector x E R policy n, and operator satisfying Assumption we have
Σ BBa++10l x (Th:s41 1ry) 5 Col1æ111.
Proof. From the definition of Bug++ have
Bas+i B1s+100110
Then, for any standard basis e, E R we obtain
Σ
Pho++0)f1e)) x T(Tns+1 | [T)
The
Σ
(on = 0, 83+1 i) т (Theft1 TT))
Thii-1
Σ
P (on+1 0.7--1 Ty. -)
Thii-1
Therefore,
Σ |Ba x (Trist1 IT,)
Thi3+1
B 01 a(rag+1 ITy)
The
|10
++ < Coll=]11
The last step is from Assumption D and |of:||| < |1 11 W S Co.
Then, prove Theorem When the context is clear, we omit the (on, on)) in B, az).
Proof. We first bound the single-step estimation error of Tp. For any E [ - 1], we have
Σ TT(TT) x
B (oh, an) - Bu(on, and b b(Th-1)
(T(
(a an (((n-)) - Balon, (n)
Bu an) (D(Th-1)= - b(7h-1)
TT(TH)
<2COÊMLE-
(5)
For the last step, the first term is bounded by ÉMLE due to Eq. B
The second term is from
Σ (b(T)) x By (on, an) (b(Th-1) - b( b(TT- ||;
7h
Σ Tb(Tu-1) Σ To(an 0h)1,0n)
an) (b)(on))) (6b7--1--((r-11)) b(TH-))) ||
7h-1
on
< 50 Σ (b(T~1)) 1(7m-1)- - b(Ta-1)
(a(n-)))((TT-1)))
(Lemma 10
COSMLE-
(Eq.
17

---

Published as a conference paper at ICLR 2025
Then consider the evaluation error of Te. We decompose the evaluation into single-step
J(Te) (NT(TT)
P (0h)
PP PM (on))ro)r(
h=1
PT ( PPr (on)
h=1
Oh
P (oh, Th-1) - PM (or: Th-
h=1
Th-1
B ... B,b BB-1 ... B,) x No ne(Th-1))
on
h=1
Th
B
Bi
... B ..,bbu) x Tee (e((n-1)
Am1
Fh
For the case h = 1, according to Eq. we have Σo; H, we use the telescoping and obtain the following equality for any Th-1-
F (01) - 1 (01) S EMLE. For 2 S h
B ..,b - -.. ...b B,bb-
Σ 1=1
B -B,)b(T,--))) + Bn-n.
(bo -bo). (6)
Therefore, for a fixed step 2 < S H, we have
Σ 7h-1
B
B,6 B .,,b))
Tee (T(Th-1)
h-1
Σ Te Te bu) Th-1
+
Σ
Te (T((T-1) Σ
B B (By-BB,B((TT)
Th-11
jml
For the first term, have
Σ ne Te(Th-1) bo)
B1-1n - bo)
x Tee (T(T))
7h-1
Th-1
Co bo bolli
(Lemma 10 (Eq.
< COêMLE.
For the second term, have
h-1
Σ Te (Th
B (B, - B,)b(T-1)
1=1
Tee (T()T) Σ
Tee (T TJ) x BR-18+1 (B, -B))((T-I))
Th 7h-1811
Σ Σ
Te (Tx Pr
t.
j+1 (B, B,)b(TT-1)
where
P Σ
ne(Th-1s5t1 (7)) B Bn-1941101
Th-19+1
18

---

Published as a conference paper at ICLR 2025
and observe that
[P (Paylik
Σ Te (Thh--1:j+1
( i, 0n-1:111 185+1 k. ab:j+1)
7h-11541
pi (on i 83+1 TT) M
Therefore |P 11 = 1. Since
111 S Co. we further upper bound Eq. as | J+1
4-1
Σ
(T P. 01:4 P (B, B,))((T-1))
j=1
h-11
[B - B,)b(T}-1) S Co Σ Σ ne(TT)
f=1
T
Taking summation over h from 1 to H, obtain
1-1 Σ ne(Ts) (B, (B, (B.-B))bbe B))
-( [xe(ee) S HCOEMLE HCo Σ
(8)
T3
From Eq. (5) we know that Σn, mo(T)) x (B, - B, b(T ||/ S 2C. Therefore, we
consider the ratio between estimation error of mT. and estimation error of my for step |H 1].
Σn, Te(m)) x (B, - B (T,)D(TT-I)
Σ. (T(TT)
(Bn, -B,) b(Th-1)
En Te(TT) PP (Th-1) x
(Br. b.s.)OOb((TT-)))
Σn, mb(Tn) IP Mr (Th-1) x
(B,. -B,,)O,sssT
Eon,as Ex
(e(an Th-1, on) (BB, - bs))0bs((Th)))
Eor.a Ex,
Tb(an
Th- on (B, bys
the first step, we use the relation b(Tn) PM- (T. 1 Combining with Eq. (8). we have
[(Te)) - (xc( S HCOOMII + 2H C2
where
Don.as Er, (e(aa Th-1; (B,
CoF.1
max kE(H- ((HH-)) 1] Eo, on Em, To(an Th-1, (l b,, 1)ll
We have proved the first part of the theorem. Next, we need to upper bound Cem,1 Let (rn RlSa be the 1-th row of (on, and - Bi, an then we have
E., [ (ap Th- oh) 17 b bs((T-1)]]
Cefr.1 < max max
We ( on.as.t
Ex,, (Tp Th o% (on, an) bs (T(-n)
max CA Ex, (0): an) (1-
hE
and Ex, ann (Or, an) bs (T)))
To lower bound the denominator, we have
Es, [or(o,, ax) bs(TT-1)) = E., (z,(on, an) bs 1))
[zi(on an) bs (s(
19

---

Published as a conference paper at ICLR 2025
(or(ons an) b 1))
Em
[ an ) 11 (
min (2x, 2 (on, aB)l
[on an (TT 1)ll2
min (EH.A) ( (0p, dn)ll2.
(9)
Here ΣnY Ex, (s(tn-1)bs( []- The first inequality is from Cauchy-Schward inequality and the last inequality is because [lbs (Th- 1)|| S 1. The numerator is upper bounded by
(on, an) (Ts(TT-))) ))] s ( (Ta
an
(10)
Combining Eq.
9 and Eq. (10
CaH S CACH.
The proof is completed.
D.2 PROOF OF THEOREM 5
As in Appendix D.I we first show lemma for the operators B in the multi-step outcome scenario.
Lemma 11. For any index 0 S < h S H trajectory Tj E [[r= A), vector R 55al, policy n, and operator B satisfying Assumption D
we have
Σ Tha+1
BBa+io|l x (Thost1 (Ty) S C>||æ|11.
Proof. From the definition of Bugj+1s we have
Bis+i = Bag+i 1n
Then, any standard basis e, E RRS, we obtain
Σ Thif+1
|But+1 x (Thsf+1 Tz)
= Σ
PM (fh+1, Oh:jt1 18411 = i, i,an)tt) (Thistz Tj)
Thife1 fu+1
Σ
Σ
pany + p (B (hiftt
Ty. 85-1 = 1.
Thi++1 fh+1
Therefore
Σ
[Baj+isll x (Thott1 TT)
This41
< [Baj+ BE x x Tr)
Thist1
< <>
The last step is from Assumption D and || & I1 CF.
Then, we prove Theorem
Proof. We first observe that for any h E [H 1).
Σ To(TT) [lb(TT) b(TT)lI = Σ
T (Th, fh+1) - PT (Th, Sh+1) S EMLEE
7h
TheJktt
20

---

Published as a conference paper at ICLR 2025
The inequality is from Eq. E [H - 1]. we have
Hence, using Lemma 11 for the estimation enror of Tb at step
Σ (T()
Bn (on; an) Bn(on, an)) b(Th-1)]|
Fh
$ Σ Tb(TT) x
(o an (((h-)) - Bn anle an)bb(n->)]
Th
Σ
(T()
Balon:an an) (D(Th-1)- b(7h-1))l
<2CFEMLE-
(11)
Next, we consider the reward of Te at each step. For step h, we construct policy μ4, which follows Te until step - and follows my from step h. It clear that μln has the same expected reward as m at step h. Let rh (fr) be the reward of fn. at step h, we have
H
((TT) (TT)
=
Σ
(IPMA (fh) - PM-- (fa))ra(FN)
1=1
fx
BB-1 ... -, BA-1 ... Bybo) x melta-)))
Σ
fh
h=1
fn
Th-1
Σ
B B .,b. B.. BBbb) x ne me(
Fk
Similar the derivation of Theorem for the case 1, according Eq. 44) we have
En p (fi) P (fi)
<
EMLE-
For 2 s h I H. we use the telescoping in Eq. (6) and
obtain
B B,b BB-1 ... Bybo) x Te(Tn-1)
76-1
h-1
Σ Te(Th-1)B bo) T6-1
+
Σ
Te Te(Th-1)
Σ
B 1h-11ti1B B,)b(Tz-1)
Th-1
j=1
For the first term, we have
Σ (T((Tn-))Ba-a bu)
B B bo)
x (T
Th-1
C= bo - bolli
(Lemma (Eq.
< Cy
For the second term, we have
h-1
Σ Te (Th1) 1)
B 11 B B,)b(Tz11)
B
f=1
(T(
Σ
TT T3) x 11-1i+1 (B, -B, -B))((TT1))
Te
7h-10j-1
(Tx P. fhe
F B,)
(12)
53
21

---

Published as a conference paper at ICLR 2025
where
P =
Σ
Te(Th-1s+1 (T)) x 13+
1811
and observe that
P Pr,llik
Σ
(Th-1:j+1
Ty) M
(fh 1.0h-1:1+1 1841 k. alsj+1)
Th-11--1
P 1 1it4
Me (fh = 8j+1 k. Ty).
M
Therefore PP,, |1 L. Since |10
[0+1ll CF. we further upper bound Eq. 12
h-1
a1. f (B, - -B,)b(Tz-1) Te(T,) P
j=1
CC Σ Σ Te (Tx)
(B, B,)b(Ts-1))
Taking summation over from 1 to H, we get
H
- - (xo)) S HCOSMLE + HCJ Σ
Σ me(T)) {e(l))((BB (B, - [BBj-B))bC BB))((r-))) (13)
7
According to Eq. [1], we have En, TT(T)) x (B,, - Bn) b(Th- S 2CFEML. Therefore,
the ratio between estimation error of n. and estimation error of ma for step h [H is written as:
En (T(TT)
(By, BB))(TT-
Σn mb(Th)
(Br. BB
b b(Tn-1)
En, Ne(Th) MM-
(Th-1)
(Br, - B.
En, TT(TT) (Th-1)
(Br, - BBBUUFFF bs
Eonas E
Telan Th- 0n) (lB -B,)Us
Eon Br, To(an Th-1, ol] BB,)U bs
In the first step, the relation b(Th) =P (T.) bsTh). Combining it with Eq. (3 we have
[J(x.) [x)(Ta) S HCF - 2f
where
Eon Ex. (ah Th-1, (B) - BB)UF bs bs
Coft.
hE 11]
Σ on Emp To(an Th-1, Oh. ( BB bs
Similar to Theorem
further have Cen.m I CACHy the proof is completed.
E PROOFS FOR SECTION 5
Proof of Theorem Recall that
(log pa (T(1))
1P (7(
Epppexx
min MEM
i=1
22

---

Published as a conference paper at ICLR 2025
By invoking Lemma with probability least 1 - 8, we have
(V log
IMI
Σ
P (T)
Pi- (r) 00
+ Eapprxx
= EMLB-
7
TEL A Therefore, for any HH 1], the following inequality holds,
(O,, x.A)
Σ P
(Th, fn+1) - PM. (Th, fi+t1)
- EMLE.
The remaining proof is similar to the proof of Theorem Finally, we get
[((xe) (x)( S HCFEMLE C
Substituting ÉMLE finishes the proof.
F TIGHER BOUND FOR MEMORYLESS πe
The paper mostly focuses on evaluation deeeedet target policies in the previous section. Here, we show that we can obtain tighter coverage coefficient for memoryless Te. present the results for multi-step outcome revealing, with the single-step case being similar.
Theorem 12. Under the same condition as Theorem and assuming Te is memoryless, with probability at least - 8. we have
log IMI
[J(Te) (Te) so
HHC
where
Eon sn E1=1
Fn111l
BiT. Te Ta
Th Th-1, 0n) [Br, Br)UUFA bs(Ta-1)
Ceff.m =
max
hE
Eon as
Er, Tb(an Th- 0n ( BA)Us bs (s(-111)ll
Note that the numerator of coverage coefficient Coft. in Theorem 5 can be written as:
Fi+tl
Σ
Σ
Ex.
Te(as
Th-1, on) [Br BA)UFA bs(Tn-1)
Compared to Cetf,m- the numerator in Catt. places the absolute operator outside of the expectation, resulting in a tighter coverage measurement. Mathematically similar tighter coverage coefficients have also been discovered in offline linear MDPs offline MDPs with general function approximation. We refer readers to Jiang & Xie 2024) for more details.
Proof Theorem 12
The proof is the same as for Theorem 5 up to bounding Eq. 12
For memo-
ryless Te, we observe that P,, is the same across different Tj. Therefore, we upper bound Eq. (2
as
Ofa (B, B,)D(TT-L))
h-1
Σ (B) - B,))((T-1))
$ Cr
Taking summation over from 1 to H, we get
#-1
(((.)) (x)( < HCF - HC₁
Σ
Σ
T (T, -
(14)
23

---

Published as a conference paper at ICLR 2025
As before, consider the ratio between estimation error of and estimation error of T. for step E
[ 1]:
En Te (Ta) x (B,, - (B))b(Th-1)
Σn, Tb(T)) BB, BB, b b(Th-1)
|| En., Te(TT) )P (7h-1) x (B, - BB)U B
En, TT(TT IP (Th-1) (B, - -Bn)UF, b.s (
En [
Exe Ta I on) [B. - BB)UURA bs(Tm-1))
Eon.an Br,
To(an Th-1,,;)](BB, BB)
Combining it with Eq.
(14). we have
[(Te) Jz((Te) S HCF
where
Enn ag
Ex
Te (a Th-1,
(Bn. (Bn- BA)UZAN bs(Tm-1)
Čoft.m == max hE[H-1
Eor,an EiTo
Tb(aa oh) B.))),,bs(TTh-)
The proof is completed.
G COMPARISON BETWEEN SINGLE-STEP AND MULTI-STEP OUTCOME REVEALING
In the main text, claim that multi-step outcome revealing (Assumption D is more lenient assumption than its single-step counterpart (Assumption E). and provide intuitions based on the confusion-matrix interpretation of Σy,t and Eo,t. However, rigorous quantitative argument is missing, which we discuss in this section. Ideally, what we want to show is that C' S Co (assuming both upper bounds are tight); if so, bounded Co (Assumption E) would immediately imply the same bound on Cy (Assumption D) showing that the latter is a weaker assumption.
Below we first show in Appendix G.1 that this memoryless; the additional factor is due to the use of matrix 1-norm. For the more general case where Ti can be distory-dependent the analysis for memoryless m. breaks down, which reveals some unnaturalness in the way we define Σ,,, and Σo.s (which are inherited from prior works). We argue in Appendix G.2 that we can re-define Ex.h and Σo, in a more natural manner that accounts for the latent state distribution under Th. which will allow for quantitative comparison between F and Σo,;; furthermore, all the results in the main paper hold up to minor changes under the new definitions.
be proved up to a factor of Sp when Ty is
G.1 MEMORYLESS We
We first compare CF and Co quantitatively assuming memoryless my We can express F as:
ΣFA = |Sa1 Σ =(f))a(()))((A)),, fr.
where 2(fx) x(fa) is the probability of observing fo when sn is uniformly distributed. Moreover, 15
define Pr', (-) as a joint distribution over 8n, and fh. where 8 is uniformly sampled, and fn is rolled out from 84, using Ty (note that this distribution is only well-defined for memoryless TT), and we have
(uff)); = iu(fi))s Pr',, (sh. = =i) f1).
2(h))
24

---

Published as a conference paper at ICLR 2025
Here, serves as inverse belief state vector, predicting the current state based future trajectory rather than the history. Similarly, Σo, can be written as:
Σo, = SSA Σ ((oo))())))(oo)'
where w(on) w(oa)
|S.. represents the probability of observing on when sh uniformly distributed
and (ū(on)), []: = Pr's (sh. on). (Note that ū(os) has dependence on mi since variables after
an are not involved, but the distribution of variables is consistent with Pr Next, we show that , 2 ||o, For any vector a E 12 we have
a L'Eon |S, Bo, [(a i(on))
S Ban (Eryloo (a ((Ja))))
|Sh [o, salonn (aT()))))
EF
The inequality is from Jensen's 's inequality. Therefore, we have:
1 & V|slllzZAl s vis S |s, ||
This implies whenever single-step outcome revealing assumption is satisfied with bound Co, the multi-step revealing assumption also holds with Cy maxx Co.
G.2 HISTORY-DEPENDER Th
Unfortunately, the above analysis only works for memoryless Tu. and breaks down if m is history- dependent: a key step was to interpret ū(fa) as (ū(f)))s = -Pr',, (s), = fi., which is only possible when na is memoryless. The root problem is that we want to take [u(fh)] = Ip* (Sh 8 = 1) and use Bayes rule to convert it to the posterior over 5h given fn. so that we can interpret FF, as the confusion matrix of predicting 84 from fn. Since the distribution is under MT. implicitly defines df the "label prior" for Sa. but previous definitions enforce unnatural and arbitrary uniform prior over Sy, (which stems from the 1s, in Zn, = diag(U> Is, )).
To fix this, show that we can re-define Σy., and Σo,, in way that is more natural and respects the de prior for latent states, and results in the main text hold up to minor changes, as will be explained. Concretely, let Рa d, for concision. We introduce Under this formulation, we have 7 (fx) = (rx,(fh), (fr), which corresponds to the marginal probability of fr under my. With this adjustment, we propose the following new assumption.
weight matrix 7 diag(U &.PP))).
Assumption F (Multi-Step Outcome Revealing with Memory-Basse -Baed Behavior Policies), Define
P diag (u UU,
We assume that || ) Cr vh E H - 1] for some ČF < oc.
Here, EP, can be interpreted the confusion matrix of latent states 8n with respect to the following process: first sample fn. according its marginal probability under Tp. (fr) Pr (fr). Then, conditioned on fn. we independently sample two latent states, and s/,, both from Pr., fi). Note that the joint distribution of (sh, fx) in this process consistent with that under To. so we abuse the notation Pr.. (.) to refer to this distribution (which is augmented with s variable). The (i. j-th entry of E corresponds the probability Pr (5%,
Sy. = j) since
EPA EA
Σ Pr (s), i fn k) Pr Pr.. (fr. Sh. j) Pr., (5/, = =)
This holds due to the conditional independence between 8n, and s/1 given fn. as defined by the sampling process. Similar to the properties of ΣyAh, when fú deterministically predicts Sh we have F I. This interpretation justifies the boundedness of ((PP))))1 as assumption. In fact, when pa uniform, we have A. Σx,ii when Pa is not uniform, EF,, is more natural as it does not artificially and arbitrarily inject the uniform prior into the definition.
25

---

Published as a conference paper at ICLR 2025
Comparison between Single-step and Multi-step Revealing For the single-step outcome revealing assumption, we can similarly replace Σo.1 with 20,, = (iag(P)))0 (W ) On, where WRt". (iag(O,,P)) The comparison between 1 "11 and ( follows similar analysis as Appendix G.1 where Pr (-) will be replaced with the more natural (r).
Changes to the Main Analyses We now show that the main results of our work are mostly unaffected if we switch to the new assumptions. Taking the upper-bound analysis (e-g.. Theorem ( example, Cj enters the analysis through bounding the norm of the OOM parameterization of the model (see c.g., Lemma
With the new definition of 2 all we need is to change the weighted pseudo-inverse used in the OOM representation accordingly; let
U = (E - (
which leads to the new operator:
(o = UF diagi 1))
Since
f.h 1 "
Cz.
one can verify that Lemma 11 still holds for B,, with Cf replaced by Cy. The rest of the analysis follows the same as in Appendix D
Future-dependent Value Function Construction Besides our analyses, changes in the definitions of CF will also affect the comparison with the model-free results from Zhang & Jiang (024) as cited in the first row of Table T. As it turns out, these results also hold under the new definition. In Uehara et al. (2023a); Zhang & Jiang (204). Cy is involved in their analysis when they Σx, to construct the future deture-dependent value function (FDVF) (Uchara et al. 2023a) and bound it range. Here show that we can also use the newly defined F construct FDVE, whose range depends on Cr, and the rest of their analyses still hold.
FDVF Vy satisfies that Vh,
UFA x VV Vi.h.
where V the latent-state value function of the memoryless evaluation policy Te. i..., the expected sum of rewards from step onwards conditioned on a latent state. Let R+ (J²) = Σ#= R(on)) be the Monte-Carlo return in fa. and 2, R.Pr. (fx) 2, (fr)/R* (fr). We construct the FDVF as:
VF, = (Z (2 -UA-P")~"U=,,ue Uuaadiiappps. (= - -V, where Rt.ps. = diag(p:)U .P. UF
We can then make a similar outcome coverage assumption as Assumption of Zhang & Jiang (2024), ensuring the boundedness of Vr For the on-policy case We, can verify that the constructed Vi exactly recovers Rt, which is naturally bounded by H.
26


Reviews:
[{"review_id": "SbPo5lAQi7", "reviewer": "Reviewer_TkqZ", "summary": "This paper explores the off-policy evaluation (OPE) of history-dependent policies within partially observable Markov decision processes (POMDPs) using large observation spaces. Traditional methods for OPE in POMDPs have relied on model-free approaches and simplified memoryless policies due to computational complexity. This paper address this by examining the statistical challenges of evaluating more complex, history-dependent policies and by proposing a model-based method to circumvent limitations in model-free approaches. Key theoretical contributions include identifying scenarios where model-free methods are insufficient, as well as demonstrating how a simple model-based approach can achieve polynomial sample complexity.", "questions": "See weaknesses", "limitations": "", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "It seems interesting to me that the model-based methods, which use synthetic data from learned models, bypass the limitations of model-free algorithms, especially in history-dependent scenarios.", "weaknesses": "1. What is the practical meaning of assumption D (multi-step outcome revealing) and how is it related to other revealing conditions in offline and online partially observable reinforcement learning, as well as the corresponding results?\n\n2. Although it is said that $M^*$ does not necessarily satisfy the realizability, would the observable-equivalent realizability actually similar to it, and the resulting dependency on the realizability error seems actually trivial? Since the only difference is the additional gap due to the error in estimation likelihood from the misspecification of $M$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "LL2jA4HAwz", "reviewer": "Reviewer_2cH2", "summary": "This paper explores the statistical tractability of off-policy evaluation (OPE) for history-dependent policies in unconfounded partially observable Markov decision processes (POMDPs) with large observation spaces. The authors first establish information-theoretic hardness results for model-free algorithms when evaluating history-dependent policies, highlighting the increased complexity compared to memoryless policies. To address these challenges, they then propose a model-based approach that enables efficient OPE for history-dependent policies.", "questions": "I have a concern regarding the MLE part. From my understanding, it seems that $\\epsilon_{MLE}$ may implicitly depend on the horizon length $H$. Could you please clarify and elaborate on this point? If so, how would this dependence impact the main results in the paper?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The findings in this paper are interesting. It demonstrates that no sample-efficient model-free OPE algorithm exists for POMDPs when evaluating history-dependent policies, whereas a model-based approach can achieve polynomial sample complexity. This highlights the effectiveness of model-based methods in POMDPs, and perhaps inspires future research on model-based RL for POMDPs. The theoretical analysis is solid and strong, and the writing is logically structured.", "weaknesses": "1. The writing could be improved to be more accessible to readers who may not be deeply familiar with this topic. For example, in the introduction, the authors could provide additional insights into belief and outcome coverage when these concepts are first introduced.\n\n2. Another area for improvement in the writing would be providing a broader perspective on the paper’s contributions. Since the main contribution is extending existing results from memoryless policies to history-dependent policies, it would be helpful to include a high-level discussion in the introduction on (1) why history-dependent policies are particularly important in POMDP settings, and (2) what major challenges arise when attempting to apply existing analysis techniques for memoryless policies to history-dependent policies.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "GHJDJ0jhqF", "reviewer": "Reviewer_CtM3", "summary": "This paper focus on OPE problems in unconfounded POMDPs with large observation spaces and history-dependent target policies. While previous work addressed the problem for memoryless target policies under certain coverage assumptions, the authors extended these results to history-dependent target policies and prove polynomial complexity.", "questions": "1. Can authors provide any empirical or simulation results by the proposed algorithm on the setting described in the paper?\n2. Are there any possibilities that can handle the state-space mismatch problem specified in Theorem 7?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper addresses an important gap in the literature by extending OPE to history-dependent target policies in POMDPs.\n2. The authors provide solid theoretical results, including both hardness proofs and positive guarantees for model-based algorithm.\n3. The paper is well-organized, with clear definitions, assumptions, and theorem statements that make the paper accessible.", "weaknesses": "1. The paper does not include experimental results to validate the theoretical findings or to demonstrate the practical effectiveness of the MLE-based algorithm.\n2. The model-based algorithm is not robust to state-space mismatch or model misspecification.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "KtCJS0KkhX", "reviewer": "Reviewer_8ySD", "summary": "This paper investigates off-policy evaluation in POMDPs. Compared to previous work, this paper considers more general target policies that depend on the entire observable history. The authors first provide hardness results showing that a model-free algorithm can not output a near-optimal evaluation with polynomial sample complexity. To handle this challenge, the authors adopt a model-based method based on MLE. The authors further prove that under certain assumptions, even considering more general target policies, the proposed model-based method can output near-optimal evaluation with polynomial sample complexity. Finally, the authors weaken the realization assumption under misspecification cases.", "questions": "Should the policy $\\pi$ in Eq. (1) be behavior policy $\\pi_b$?\n\n I wonder if assumption A can be relaxed, for example, estimated via the offline data set? And how would this relax affect the MLE in Algorithm?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "(1) The paper provides hardness results for model-free methods, which motivates the authors to adopt the model-based methods.\n\n(2) This paper weakens several previous assumptions on target policies and POMDPs, and proves the polynomial sample complexity upper bound for model-based methods.\n\n(3) The paper is well-organized and easy to follow.", "weaknesses": "It seems that the **Pre-filtering** and **MLE** parts of algorithms are not computationally efficient. **Pre-filtering** requires to verify each of the models in set $\\mathcal{M}$. Is there any efficient way to implement these two steps?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)