Breaking the Order Barrier: Off-Policy Evaluation for Confounded POMDPs
Authors: Qi Kuang
Jiayi Wang
Fan Zhou
Zhengling Qi
Venue: NeurIPS 2025 poster ()
Keywords: off-policy evaluation
confounded POMDPs
identification
Primary area: theory

Abstract: We consider off-policy evaluation (OPE) in Partially Observable Markov Decision Processes (POMDPs)  with unobserved confounding.  Recent advances have introduced bridge-function to circumvent unmeasured confounding and develop estimators for the policy value, yet the statistical error bounds of them related to the length of horizon $T$ and the size of the state-action space $|\mathcal{O}||\mathcal{A}|$ remain largely unexplored. In this paper, we systematically investigate the finite-sample error bounds of OPE estimators in finite-horizon tabular confounded POMDPs.  Specifically, we show that under certain rank conditions, the estimation error for policy value can achieve a rate of $\mathcal{O}(T^{1.5}/\sqrt{n})$, excluding the cardinality of the observation space $|\mathcal{O}|$ and the action space $|\mathcal{A}|$. With an additional mild condition on the concentrability coefficients in confounded POMDPs, the rate of estimation error can be improved to $\mathcal{O}(T/\sqrt{n})$. We also show that for a fully history-dependent policy, the estimation error scales as $\mathcal{O}\big(T/\sqrt{n}(|\mathcal{O}| |\mathcal{A}|)^{\frac{T}{2}}\big)$, highlighting the exponential error dependence introduced by history-based proxies to infer hidden states. Furthermore, when the target policy is memoryless policy, the error bound improves to $\mathcal{O}\big(T/\sqrt{n}\sqrt{|\mathcal{O}| |\mathcal{A}|}\big)$, which matches the optimal rate known for tabular MDPs. To the best of our knowledge, this is the first work to provide a comprehensive finite-sample analysis of OPE in confounded POMDPs.

Breaking the Order Barrier: Off-Policy Evaluation for Confounded POMDPs
Qi Kuang School of Statistics and Data Science Jiangxi University of Finance and Economics
Jiayi Wang
Department of Mathematical Sciences University of Texas at Dallas
Fan Zhou
School of Statistics and Data Science MoE Key Laboratory Interdisciplinary Research Computation and Economics Shanghai University of Finance and Economics
Zhengling Qi School of Business
George Washington University
Abstract
We consider off off-policy evaluation (OPE) in Partially Observable Markov Deci- sion Processes (POMDPs) with unobserved confounding. Recent advances have introduced bridge-function circumvent unmeasured confounding and develop estimators for the policy value, yet the statistical error bounds of them related the length of horizon T and the size of the state-action space |O] |A remain largely unexplored. In this paper, we systematically investigate the finite-sample error bounds of OPE estimators in finite-horizon tabular confounded POMDPs. Specifically, we show that under certain rank conditions, the estimation error for policy value achieve rate of O /n). excluding the cardinality of the ob- servation space |O] and the action space AA,. With an additional mild condition on the concentrability coefficients confounded POMDPs, the rate of estimation error can be improved to O(T/ We also show that for a fully distory-depender policy, the estimation error scales OTT (| F). highlighting the expo- nential error dependence introduced by cestory-based proxies to infer hidden states. Furthermore, when the target policy is memoryless policy, the error bound improves which matches the optimal rate known for tabular MDPs. To the best of our knowledge, this the first work to provide a comprehensive finite-sample analysis of OPE in confounded POMDPs.
Introduction
Partially Observable Markov Decision Processes (POMDPs) (Monahan 1982) have become a practi- cal framework for modeling decision-making under uncertainty across wide range of applications (Albright 1979 Monahan 1982, Singh et 1994 Cassandra] 1998 Young et al., 2013) [Bravo et
2019). In POMDPs, the agent must make decisions based on partial observations rather than full access to the underlying system state. Such partial observability often arises real-world settings, making standard Markov Decision Processes (MDPs) inadequate for modeling the underlying data- generating processes. For example, in healtheare, clinical decision-making frequently based on
"Corresponding authors: zhoufan@mail www..sshfe.........e...ee edu. cn; gizhengling@emait wwr.iiigggueeee. guu edu
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

partial information, while important latent factors like disease progression or genetic predispositions remain hidden or difficult quantify.
A recent line of research has focused on off-policy evaluation (OPE) within the framework of confounded POMDPS (Tennenholtz et al.] 2020; Nair and Jiang, 202T Shh et al.) 2022] Miao
iet al. 2022 Bennett and Kallus 2024). Since confounded POMDPs inherently violate the Markov assumption and mean encounter unmeasured confounders, existing approaches draw inspiration from proximal causal inference (Miao et al. 2018: Kallus et al. 2021 Cui et al. (024). leveraging partial observations as a proxy to infer the hidden state, which enables the identification of the policy value. However, treating histories as proxy states poses fundamental hardness for POMDPs, as these histories can entail an exponentially large number of possibilities, thereby demanding a potentially exponential number of samples for accurate evaluation (Liu and Jin (022).
To avoid an explicit exponential dependence of the error on the cardinality of the observation space, recent work (Tennenholtz et al. 22000; Nair and Jiang, 2021) uses importance sampling (IS) but
introduces an exponential-in-hoorize
quantity due using the cumulative importance weights. To
address the history-inducee "curse of horizon "Liuu et al. 2018), recent work (Shi et al. 2022 Uehara
et al. 2023 Zhang and Jiang, (022a) employ function approximation under realizability assumptions
and specific coverage assumptions. However, in tabular confounded POMDPs, despite the inevitable dependence on the observation and action sizes, the explicit dependence on the cardinality |O||A|| for
history-dependent policies remains unspecified.
On the other hand, excluding the influence of cardinality, the optimal error rate achievable by OPE estimators in confounded POMDPs remains unclear. Recent work (Zhang and Jiang/ [2025 (b) demonstrate an error rate of OT2 / /v).. yet these pertain to unconfounded POMDPs, where the behavior policy is solely dependent on observed variables. In contrast, it has been shown that OPE estimators can achieve an eгror rate of ((TV/n) in MDPs, which is known be minimax optimal in both sample size and horizon length. For instance, Yin and Wang (2020) shows that marginal importance sampling (MIS) estimator can attain such error bounds for tabular setting, while Wang et al. (2024) further proves that nonparametric Fitted-Q Evaluation (FQE) estimators can achieve similar sharp dependence under the realizability assumption on the ratio functions. Given these insights, one naturally wonders if the successful analysis can be leveraged to better understand the horizon dependence for the convergence rate of the OPE estimator in the presence of unobserved confounding.
Specifically, drawing from the aforementioned literature, we seek to address three questions:
QI: How does the history-dependent policy explicitly influence the dependency of error bounds in confounded POMDPs? Q2: How does the error bound depend on the horizon T Can the sharp linear rate, known for fully observable settings, be achieved in confounded POMDPs? Q3: What is
the role of the concentrability coefficients (the ratio functions defined in Assumption 3 in improving the convergence rate of OPE estimators in confounded POMDPs?
In this paper, we investigate the problem of off-policy evaluation under the confounded POMDPs, with focus on addressing the three key questions. Compared to existing work on OPE in confounded POMDPs, our contributions are as follows: Firstly, we establish a two-step model-based approach to estimate the policy value, which relies on certain matrix invertibility conditions. We demonstrate the estimation error for fully -eetoddd policy scale as O / / 3) ). while the higher-order terms of error bound exhibit a stronger dependence on the size of observation-action space, scaling as (IOI|-A) 5 Secondly, excluding the influence of cardinality, as T grows, the first- order term of the error bound demonstrates a 1 dependence, while the higher-order terms show a stronger 8 dependence. Thirdly, by assuming the boundedness of certain concentrability coefficients in confounded POMDPs, without additionally estimating these probability ratio functions, we show that the first-order term of the error bound can be improved to O(T) (n(1o]1AA))) Lastly, when the target policy is reduced to memoryless policy, the error bound improves to O(T) OOT/v////OlA) matching the sharpest rate of convergence known in the tabular MDPs setting.
2 Related Work
OPE in confounded POMDPs. A growing line of work has studied OPE in confounded POMDPs by leveraging proxy variables to identify policy value in the presence of unobserved confounders
2

---

(Zhang and Bareinboim 2016 Shi et al. 2022 Lu et al., 2023 Hong et al. 2024b a.. While these methods have primarily focused on settings involving function approximation, theoretical analysis in tabular settings remains relatively limited. Besides, line of research investigates the unconfounded setting (Uehara et al. 2023; Hu and Wager, 2023 Zhang and Jiang 2025a b). Among these, /Zhang] and Jiang (2025b) demonstrates that mistory-depender policies can achieve polynomial sample complexity for OPE under certain coverage assumptions and further highlights the necessity of model- approaches in this context. However, the unconfounded setting is less challenging than ours, as it fails to capture the complexities introduced by unobserved confounding. Crucially, none of the above works investigate whether optimal convergence rates can be achieved in confounded POMDPs.
OPE in MDPs. OPE in MDPs has been extensively studied, including importance sampling (IS)
approaches (Precup 2000) and their doubly robust variants (Dudík et al. [2011] [[aan and Li 2016
Thomas and Brunskill| 2016), well marginalized importance sampling (MIS) methods (Xie ct al. 2019 Kallus and Uehara 2020; Yin and Wang 2020). While IS-based estimators are broadly applicable, they suffer from high variance, leading to exponential dependence the horizon length. Additionally, MIS-based estimators rely on the Markov property, which limits their direct application to confounded POMDPs. Yin and Wang (2020) demonstrate that MIS methods can achieve rate of OTT/ However, there has been no work investigating the potential for improving the dependence on horizon length for OPE in confounded POMDPs.
3 Preliminaries
POMDP Sctup. We consider a finite-horizon episodic POMDP denoted by M = A,,,,A,T,M, {P.)T= ( where S, O and A denote the state space, the observa- tion space, and the action space respectively. In this paper, all S, O and A are finite. The integer T is the total length of the horizon. We use 11 E A(S) to denote the distribution of the initial state, where AS2) is a class of all probability distributions over the space ΩZ Denote {P:)T= to be the collection of state transition kernels over S x A to S, and (Te) to be the collection of observation emission kernels over S to O. We use (re)T= denote the collection of reward functions, i.., r. : S A [-1, 1] at each time step L. Finally, we let Og denote the prior observation, which provides prior information about the initial state Si.
In a standard POMDP, at each time step 4, given the current (hidden) state S., observation O₂ ~ Te(- S)) is observed. The agent then selects an action A, according to a certain policy, receives reward R2 with E,R, St $t, A, ae] (s az) for every (st, az), and the environment transitions to the next state S according to P. | Ar).
Off-policy Evaluation (OPE) under Unmeasured Confounding, This paper aims to estimate the value of potentially history policy for POMDPs using offline data. Define the observed history by H, == (O,,A1,..., Ot, A.) E Hr, where H, := I[= (O x A) is the space of observable history up to time t. The target policy to be evaluated is denoted by {m²) f-- 1. where Te : O x H4-1 + A(A)
History-dependent illustrated by the green arrows Figure Given the target policy æ = [ J 1= the policy value is defined as
1
T s:
V(T) = Es
E
Σ
R.
where ET is taken with respect to the distribution induced by the policy x.
In the offline setting, an agent cannot interact with the environment but only has access to a pre- collected dataset generated by some behavior policy {x]]{=1- We assume that the behavior policy depends on the unobserved state S., i.c., = SS A(A) for each t. Unlike previous work (Uchara) et al. 2023) Zhang and Jiang 2025alb). which restricts the behavior policy to be memoryless and dependent only on the current observation (i.e., a ~ (-lo)))) our approach allows the behavior policy to depend on the latent state, making it more aligned with real-world scenarios and thus introducing additional complexity in the analysis. We use P to denote the offline data distribution under the behavior policy and summarize the data as D == (ob: (of, at. r which consists of n i.i.d. samples drawn from P. The full data generating process so-called confounded POMDPs is depicted in Figure]] I
3

---

Notations. Throughout this paper, we assume that E is taken with respect to the offline distribution. We use uppercase letters such as (S,, O,, A,, R2, H,) to denote random variables and lowercase letters such as (st, ot, "t,"t, h₂) to denote their realizations, unless stated otherwise. We use the notation X 11 Y Z when X and Y are conditionally independent given Z under the offline distribution. For random variables X, Y and Z taking values on (f1,....,TTT {VI.-.., .nn and {21, 2gg respectively, P(X) denotes a n length vector with entries P,; = p(X = z;) and P(X Y denotes X matrix with entries (X YY) ;= p(X zj Y = 14). Similarly, P(X
Y)
x Y = yi), and P(X, Z = Y) denotes n matrix with entries (x, 2 2 = Ij Z = Y 14). For brevity, we sometimes abbreviate these as P( Y) and P(X, Y). For any two sequences {n {b,, 1= an 2 6n denotes On Cb, for some C, 0 and every > N. For matrix A, we denote its Moore-Penrose inverse by A and its smallest singular value by min (A).
denotes the n length vector with entries (X Y) p=
(X,
R1
Ry
S2
A
A2
Ar
Q
O+
Figure I: The directed acyclic graph of the data-generating process in confounded POMDPs, where states S, are not observed. Red arrows indicate the generation of actions via the behavior policy, while green arrows indicate the generation through a target history-dependent policy. Under the offline distribution P, we have the conditional independency Oo TL (Os, Oc-1, Sc, Ar, Hi-1 for any & E [T]]
4 Methods
In this section, we introduce the proposed off-policy evaluation method for confounded POMDPs. Before considering how to estimate VT)T), we first consider the problem of identification.
4.1 Identification
In general, identification is not possible for OPE in the presence of unobserved confounders. The fundamental challenge arises from two sources: (i) partial observability, which breaks the condi- tional independence (Markov property) essential for classical OPE estimators; and (ii) unmeasured confounding, which renders direct estimation of the policy value V(TT) intractable. Crucially, failure to account for such confounding leads to biased estimates of the policy value (Shi al. 2022). as the hidden state simultaneously influences both the action and future rewards and transitions.
To address these issues, natural strategy is to use the observed history to infer information about the
hidden state (Shi et al. 2022; Hong et al. 2024a b). This approach is motivated by the insight that the entire history contains rich information that can help reconstruct a proxy for the unobserved state. To enable the observed history for identifying the policy value, we impose rank conditions.
Assumption 1 (Invertibilityy. For each t E [T] and E A, assume P(O A, a,, S;) E R||Sx|o| has full row rank and IO, | A, = az Ou, H4-1) E [2(0114.-11(0)) has full column rank.
necessary condition for the rank condition is that |0] > (S]. Invertibility of IP, | A, = ar S)) guaranties that sufficient information about the hidden states is encoded in the observations across time steps. The invertibility of ((; A ===00 at Oo. H(-1) further ensures the recovery of information about the hidden states S, from the observable history {Oo, H,-1). }. Notably, leveraging the entire
history as a proxy relaxes the standard rank condition that requires P(O, A, = dr. 0, ) using one-step observation as proxy, to be invertible (Tennenholtz et al.) 2020 Shi et al., 2022). This is partieularly beneficial real-world applications where the observation space is often larger than the hidden state space.

---

Theorem 1. Under Assumptions
V(T) is identified as
T V(x) ΣEΣ
(a or, 1 A1 a1,
he
I1 P(O = A = a, Op H,,1) Art1 = ast1, Oo. Hi)
P - 0, o A oe. Ou H1-1).
Theorem states that the policy value can be expressed entirely in terms of observable variables. This expression is derived by decomposing the marginal distribution p" (r²) using the transition dynamics, reward, and target policy, based on the identity V(T) = E
R. = ='= rep" (re)- Similar results were initially introduced by Tennenholiz et al. 2020). Specifically, the invertibility of the action-condition reconstruct the distribution of observations and rewards under the target policy using offline data collected by the behavior policy. Intuitively, conditioning on the action blocks the confounding path through the unobserved states, isolating the confounding effect of the action. Consequently, these conion--ondiioneed probabilities, as proxy functions, can effectively correct the confounding identify the policy value. In addition, extend the identification results
probability matrices P(O,+1 AA = a,, Oo He) allows us to algebraically
influence, thus enabling beyond the tabular setting (see Theorem 5 in the Appendix), showing that the completeness condition (Assumption in the Appendix), which a generalization of the rank conditions in Assumption T is sufficient for the identification theorem to hold in more general settings.
4.2 Estimation via Value Functions
According Theorem 1 can directly perform OPE by estimating those conditional matrices relying solely on the offime data. However, the presence of multiple matrix inverses the product is computationally expensive and may lead to instability in the estimation. To address this, motivated by the structure of the identification in Theorem [ and propose to solve a Bellman-tyy tampt equation estimate the policy value
stable and computationally efficient approach.
Bellman-like recursions in confounded POMDPs. Under the invertibility assumptions stated in Assumption 1 the proxy {Ou, 1 is sufficient to construct Bellman-like recursion based entirely on observable variables (see Appendix I for further details). Specifically, we can formulate system of linear integral equations (I) whose solution defines sequence of proxy value functions (b%, A x x H + R
by (Ae, Or, H, H1-1) Oo, AG, Hi-1 E RiTI Oz, H
Oet, H.)T O₁, H.-1) Ou A,, H1-1. (1)
Σ a'EA
where b7:441 O. Note that the invertibility of IP(O A, ar Oo, H,-1) ensures that the value functions [T are uniquely defined solutions to this system. In the context of confounded POMDPs, these proxy functions play an analogous role to the value functions in MDPs, enabling the estimation of policy value through these functions. This naturally suggests a two-step procedure for OPE in confounded POMDPs: (i) estimate the conditional probabilities, and (ii) compute the value function from I using the estimated probabilities.
To illustrate the model-based estimation in the tabular setting, we first define two key conditional probability matrices for any given ag E A, rt, and 01+1 O,
P :PP(O, Oo. A = a,, H,-1) E 1
P Poetresoets ::P(O++1 0,+1, R, Tú, Or Oo, at, H(-1) e ol H
Then, we can rewrite the value recursion from equation T in matrix form as:
P a. B.
Σ Pastoores [Te Te(a, or h1-1) +
Σ
bu 0141, he-1, a,, oz) oz) o mm], (2)
01.00+1
d'EA
5

---

where B, := (at, or, h2-1) E ROO), Pa.: Pa., E R 1|x|0 are conditional prob- ability matrices defined earlier, O denotes the element-wise product, and re (0z) h4-1) Te Te 14-1) @ Ln v1,41 (1',,,, 0041, 1,,,, (t E R unique solution of B,, the matrix Pa, must be full column rank, i.e. rank(Pa.) a.) = |0) This is mild and typically reasonable assumption in practice, since [O] |O||H as t increases. Then, the solution to the linear system (2
Ol is a |O] length vector. To ensure
is given by
B: = Pt Σ
Pa Par.riou ( Te(ael 1 + E bV. ,441, h4-1,,,1,,,, o1) @ mm)
01,01:1
d'EA
where Pl us (P. PPT,
PT. 1 is the Moore-Penrose inverse of Pa. Given WiT++ = 0, the value functions (D can be solved iteratively, starting from t = 7 and
proceeding backward. Specifically, for any a E A. E 10, E He, the update rule gives
(ac, or, h(-1) (a oc. 1
Pa...re De (r + Σ
(3)
T1:00
a'EAA
where (or) E || a one-hot encoding vector for the observation oz.
Two-stage estimation. To enable the estimation of value functions, we estimate the conditional probability matrices P Papy Pa from the dataset 'D at time step /. Each matrix is constructed entry-wise as follows:
00, E 1( 1 ob. a;) = (ox, 00,, ac)
por 00. Ur, h1-1)
plo141, on 00. ar, hx-1) Eis 1f(o/ o¹ ri, ob. h at) = (o1-1, Or, re, 0D, h4-1 0z)
Ei= H(,, h;-1.a] = (on, h2-1, at)} denotes the number of the triplet (oo, h1-1, a,) being visited among n independent episodes.
where Noo 1..1
Then, the sequence of estimated value functions
(ōv, can be solved iteratively by
by.aaa, oz, 1) = Te lot, 1o
Σ r2,0'
p Pan.
We
Σ
od (5)
a'EAA
where ōv.T+1 0. P a. estimators unbiased, i.e. Elp(o: Ob, az, h4-1) p(o: Ou, at, he-1), which implies that E[P,,]= Pat Consequently, the recursion (5) ultimately yields asymptotically unbiased estimates of the true value functions. Moreover, the P., must be invertible for the recursion to proceed, which implicitly requires that each tuple (oo, 1 0r) must be observed sufficiently many times. To ensure numerical stability and avoid division by zero, we assume each (on, /4-1, 4z) in the data is sufficiently sampled. If the triple (oo, h)-1,ag)
(P. PT. 10 184-11, By Lemma 12 these empirical
collected in the offline data, we p(-loo, ae, ht-1) = 0.
Policy value estimation. After computing the value functions via 5 for T iterations, we plug the estimated value function by.1 into V(TT) to obtain the empirical estimator as
1 Σ Σ (a oi)
(T))
aEA
Algorithm
1 summarizes the proposed algorithm for OPE in confounded POMDPs.
5 Theoretical Results
In this section, we study the theoretical properties of our method under certain technical assumptions. Our primary goal is to establish a finite-sample error upper bound for V7(m) D()).. Specifically, this upper bound will depend on several factors, including the sample size n,, the horizon length T, and
the size of the observation space [O] and action space |.]. begin with, we impose the following key assumptions that are used in the thcoretical analysis.

---

Algorithm 1 Tabular Off-Policy Evaluation for Confounded POMDPs
Input: Dataset D, the target policy { ] and initialize bv,r+1 O. for t = T..... ., 1 do
Estimation of conditional probability: obtain Pa, and P Pa by Estimation of value functiion: obtain δv; by (5)
end for
Output: obtain estimated policy value (TT) by by.1.
Assumption 2.
The following conditions hold.
(a) (Coverage) For each t E [T', IE ITe= [ur(Ap (.. 2 S Crp < 00;
(3((A115))
(b) (Invertibility) For each E [T], as E A. rank( a.) = rank((a.) = 10), and the smallest
Cp
where < Cp < co is a constant; [T) the samples used to construct each entry of P as. satisfy bon.b.-1.a: 2 np," (oo, h)-1, a1) Or.35), where 0 0r.i5 < 1 with Eng B1,5 = 1, and we denote 8" == mine,i. Br.z5.
singular value man (P..) satisfies Jmin (P.)) VIoIi
(c)SSfficieet visitation of observations) For each E
Assumption a) imposes a bounded second moment condition on the cumulative importance ratio (concentrability coefficients), which is milder compared to directly bounding the importance weight Te(ag]o, m/// (ag (1)) a common assumption in the OPE literature. The invertibility condition (b) requires P., and P.. to be well-conditioned matrices, which is necessary for the uniqueness of the solution to the iteration equations (3) and (5) Furthermore, we require the lower bound of the This is informed by random matrix theory, where for an M x N random matrix (M fixed, N + oo), the smallest singular value decays at rate of O (/1//NT /N) (Rudelson and Vershynin, 2009). Assumption (2c) requires sufficient number of samples for each triple (ov. h4-1, )z), ensuring consistent estimation of the conditional palylog(io]".. F,T)
smallest singular value of Pa, to decay in proportion to 1/ 1/V|O|||,
probability matrices. Specifically, this requires the sample size mins,on." PF (0..))-1.9.))
and further details can be found in Appendix C and can be relaxed using a truncation argument, similar to the approach Yin and Wang 2222))
Assumption [e) is introduced to simplify the proof
We now present the main theorem that provides the upper bound for (V(T) (T))
Theorem 2. Under Assumptions 7 [ Then, with probability at least 6, it holds that
[(+)) - [m(] x T (1 - 8*) - Crl0 1
Vn
T1.5
(1 -1-00 -1-00'-'0
I V VIog(T210FPAA///)
(6)
T3
(1 - 0*) - n
0
A log 1O 1A)
In Theorem the first term in (6) scales as O(T15/VT)) which we refer to as the first-order term. The remaining terms, which are higher-order terms, exhibit stronger dependence on T but converge more quickly due to the faster rates of the sample size n. These results respond to Q2. For clarity, we omit the detailed form of the higher-order terms here, and the full specifications are discussed in Appendix
A Compared to the order of ( / /T) obtained in both unconfounded POMDPs (Uehara et al.
2023 Zhang and Jiang 2025a and confounded POMDPs (Bennett and Kallus 2024), we achieve sharper dependence on the horizon by leveraging the fact that the variance of the first-order term can be decomposed into a sum of T individual expectations of the conditional variance. Moreover, the first-order term in the upper bound (6) exhibits an exponential dependence order (|O]|A)) on the observation and action space, while the higher-order term shows strong dependence of order ([O][A]) or with 2 3. These results respond to Q1. The increased complexity arises from the fully history-dependent policy, leading to challenges in evaluating policies as the effective policy domain expands over time with the growth of the history space [He]]. This complexity highlights the inherent statistical challenges of evaluating fully -istery-dependent policies in confounded POMDPs.
7

---

Corollary 1. Under the conditions in Theorem 2 for the memoryless policy dependent on the current observation, i.e. π O + [(A), with high probability, it holds that
[V=)) (()) ( (1 (0)-00)-222 -
As shown in Corollary 11 when the target policy reduces to a memoryless policy, the exponential dependence on the observation and action spaces is no longer present. The upper bound 7 instead exhibits polynomial dependence on the horizon T, as well as on the cardinalities of the observation-action space. We now turn to a refined analysis of the upper bound (6. Before proceeding, we assume the existence of the following sequence of ratio functions.
Assumption 3. We assume the existence of real-valued functions {b A O that satisfy the following conditional moment restrictions,
H - RJ
(r H1-1) Ti( Si)
Sz Ar, H Ho-1] (W,,(Ar (A H,-1,
(8)
where we(Se, Hi-1) ( (St, H1-1). We denote Pe(or, St, ae h(-1) oi, (r, St, at, he- he-1]. We further assume there exists constant
E. (at, h (a; Cw < 00 such that
sup Se,
Pe Sts at hx11) S Cw.
These types of weight functions (br 17 are also utilized in OPE for confounded POMDPs Shi et al. 2022 Bennett and Kallus 2024). which allows for the adjustment of the observed dat distribution to account for the influence of unobserved confounders. The ratio P: plays the role of a concentrability coefficient in confounded POMDPs. Specifically, the following identity holds:
Pi (ot, St, at 12-1) Pd (st, h IH (ax ot, h2 )p(or 88)
PelOr, St: 0t, 01,h4-1)
pJ¹ (o,, St. Ge, h1-1) pf (s,, h1 1) ( s,)p(o; ss)
In the MDPs, Pt reduces to the ratio of the vate-action marginal density. which quantifies the mismatch between the marginal state-action distributions of the target and behavior policies. Analogous to the fully observable case, we impose the bounded ratio in (9), which ensures that the offline data distribution P can calibrate the distribution induced by the target policy n.
Lemma 1. For the target policy क : O x He-1 - A(A), we have
Σ E
Var
Rd
+
Ebu44a (a, H.) Sc, Ar, H4-
Var
Σ
R
aEA
where Var is taken with respect to the distribution induced by n.
Lemma establishes variance decomposition bound that is analogous to Lemma 3.4 in Yin and Wang 2020), which focuses on the OPE in MDPs. Notably, it shows that the sum of the conditional variances across time steps is upper bounded by the variance of the cumulative reward, which is on R, S T This result can be derived by iteratively applying the
the order of T since Var |>==1 law of total variance. The complete derivation is provided in Appendix C.1.2
Theorem 3. Under Assumptions
2 and we have the following results:
(a) for history-dependent policy, i.e. me : O H - (AA), with high probability holds that
T /= - cr
[(T)) -
(10)
(b) for memoryless policy, iee. Te : (AA), with high probability it holds that
[(T) - (()))((>))-=) = o T (1 0r) 0 + LA
(11)
vn
8

---

Based on Lemma we derive Theorem We omit the higher-order terms here, as they remain identical to those Theorem 2 Notably, the constant of the coverage condition Cg. is replaced by the constant of the bounded ratio Cw. Compared to the results in Theorem 2 the upper bound in (TO) demonstrates an improvement in the dependence on the horizon length 7 in the first-order term, reducing it from 7 to T. which is the sharpest known dependence of the horizon for tabular POMDPs. The bounded ratio function in Assumption 3 here provides an enhanced method for deriving the bound the first-order term, thereby achieving faster convergence. These results answer the question Q3. In the memoryless case, the upper bound in (IT) matches the optimal order of V /OIAA established for tabular MDPs Yin and Wang 2020). This finding highlights that linear sample complexity in T" is sufficient for evaluating the memoryless policy in confounded POMDPs under these conditions. In addition, it is crucial to emphasize that our approach does not require the estimation of weight functions {D focusing solely on the estimation of value functions 1 This distinguishes our approach from prior work such as Shi et al. (222)) which necessitates the estimation of both components.
6 Simulation Results
We conduct a simulation study to examine the behavior of the error (V(TT) - ((T) with respect to sample size n and horizon T. The primary objective to provide empirical validation for our theoretical results. To this end, we use a relatively simple simulation setup that ensures clarity in demonstration. Specifically, we evaluate our approach in a simulated POMDP environment characterized by one-dimensional discrete state/observation space, a discrete reward space, and binary actions. Concretely, we set AA = =000 13. O = {0, 1,2] for all t. The initial observation is given by Og Unif( (0, 1,2)) and S Unif 1,2]), and the transition dynamic is given by O2 (.S..) where SS) = 1,0, = (1) 3e/2) + c/2.. The immediate reward is set to be R2 2/(1- + (S,A-- - 3) 13. We collected offline data using time- -omogenoggs behavioral policy =²(1 = 1/(1 exp(e0.ppx)) + 1)] = (O)S)) For experimental details, we set e = 0.2, initialize bv,T+1 0, estimate conditional probability matrices as described in 4 and iteratively compute the value function by, over T steps according to (5)
We evaluate two target policies. (1) For the memoryless target policy T. (1)0.) 1/11 exp(-0.80, + 1)} = (O)O), the conditional probability P., and Pa..r,.... are condi- tioned on Og- We evaluate its value using sample sizes 200, 400,.... .... 1000, and horizon lengths T= = 20, 60, 100, 140. The results, shown in Figure 2 a), reveal a nearly linear relationship between (M)) - (T) and T, which aligns with our theoretical results as shown in Theorem 3 (2) For the fully history-dependent target policy setting, to simplify computation, we fix the action space to single action, A = {1}. In this case, Te (1 0,, = 1 and the historical information /1, is only used estimate the conditional probability matrices. We evaluate the policy value using sample sizes n = 1000, 4000, 7000, 10000, and horizon lengths T = 2, 4, 6. Figure bb) presents the logarithm of [>))) ((Tr) | versus T. For n 1000 setting, we observe noticeable fluctuations due to the increased size of the conditional probability matrices as T grows, which requires more samples to estimate each entry accurately. Nonetheless, across different n, observe an approximately linear relationship between the logarithmic error and the horizon T. These experimental results are consistent with the theoretical findings presented in Theorem
7 Conclusion
In this paper, study the problem of OPE in confounded POMDPs, where both partial observability and unobserved confounding pose significant challenges to policy evaluation. To address these challenges, we propose model-based framework that leverages observable history as proxy for hidden states. Under suitable invertibility conditions, we establish identification results for history- dependent policies. Our theoretical analysis demonstrates that the proposed method achieves convergence rate of O O) [A| An important direction for future research is investigate the minimax-optimal rate for off- policy evaluation confounded POMDPs and extend the framework to continuous state and action spaces.
O

---

11
1.0
0.300
EiTor
760
100
13
600
3335
900
7000
1.
1000
100
Horizon
(b)
Figure 2: (a) Results for [V())
(TT) when the target policy is memoryless. (b) Results for (og((V(z) (m)) when the target policy fully history-dependent
Acknowledgment
The authors would like to thank the anonymous reviewers for their valuable comments and construc- tive suggestions, which have significantly improved the quality of this paper. Qi Kuang acknowledges funding from the Early-Career Young Scientists and Technologists Project of Jiangxi Province (No. 20252BEJ730166) and the National Natural Science Foundation of China (No. 12571286), Fan Zhou acknowledges support from the Shanghai Research Center Data Science and Decision Technology.
References
Albright, S. C. (1979). Structural results for partially observable markov decision processes. Opera- lions Research, 2715)1044-11033
Bennett, A. and Kallus, N. (2024). Proximal reinforcement learning: Efficient off-policy evaluation in partially observed markov decision processes. Operations Research, 12(3):1011-1086.
Bravo, R. Z. B., Leiras, A., and Cyrino Oliveira, L. (2019). The of uavs humanitarian relief: an application of pomdp-based methodology for finding victims. Production and Operations Management, 28(2):421 440.
Cassandra, A. (1998). A survey of pomdp applications. In Working notes of AAAI 1998 fall symposium planning with partially observable Markov decision processes, volume 1724.
Cui, Y., Pu, H., Shi, X., Miao, W., and Tchetgen Tchetgen, F.. (2024). Semiparametric proximal causal inference. Journal of the American Statistical Association, 1194546)
Dudík, M., Langford, J., and Li, L. 1).11). Doubly robust policy evaluation and learning. arXiv preprint arXiv: (60.4
Hong, M., Qi, Z., and Xu, Y. (2024a). Model-based reinforcement learning for confounded pomdps. In Forty-first International Conference Machine Learning.
Hong, M., Qi. Z., and Xu, Y. (2024b). A policy gradient method for confounded POMDPs. In The International Conference Learning Representations.
Hu, Y. and Shiu, J.-L. (2018). Nonparametric identification using instrumental variables: sufficient conditions for completeness. Econometric Theory, 34(3)6559-693.
Hu, Y. and Wager, S. (2023). Off-policy evaluation in partially observed markov decision processes under sequential ignorability. The Annals of Statistics, 1145:1161-11585
Jiang, N. and Li, L. (2016). Doubly robust off-policy value evaluation for reinforcement learning. In
Balcan, M. F. and Weinberger, K. Q., editors, Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pages 652-661, New York, New York, USA. PMLR.
10

---

Kallus, N., Mao, X., and Uehara, M. (2021). Causal inference under unmeasured confounding with negative controls: minimax learning approach. arXiv preprint arXiv:2103.14029,
Kallus, N. and Uehara, M. (2020). Double reinforcement learning for efficient off-policy evaluation in markov decision processes. Journal of Machine Learning Research, 21(167):1-65
Kress, R., Maz'ya ya, V., and Kozlov, V. (1989). Linear integral equations, volume 82. Springer.
Liu, Q. and Jin, C. (2022). Partially observable rl: Benign structures and simple generic algorithms. https://qinghual2222.00 github.io.
Liu, Q. Li. L.. Tang, Z., and Zhou, D. (2018). Breaking the curse of horizon: Infinite-horizon off-policy estimation. Advances in neural information processing systems, 31.
Lu, M., Min, Y., Wang. Z., and Yang, Z. (2023). Pessimism in the face of confounders: Provably efficient offline reinforcement learning in partially observable markov decision processes. The International Conference Learning Representations.
Miao, R., Qi, Z., and Zhang, X. (2022). Off Off-policy evaluation for episodic partially observable markov decision processes under non- non- parametric models. arXiv preprint arXiv:2209, 10064.
Miao, W., Shi, X., and Tchetgen, E. T. (2018). confounding bridge approach for double negative control inference on causal effects. arXiv preprint arXiv: 04945.
Monahan, G. E. (1982). State of the art-a survey of partially observable markov decision processes: theory, models, and algorithms. Management science, 28(1):1-16.
Nair, Y. and Jiang, N. (2021). A spectral approach off-policy evaluation for pomdps. arXiv preprint (0t::2/09./0022
Newey, W. K. and Powell, J. L. (2003). Instrumental variable estimation of nonparametric models. Econometrica, 5165)11565-1578
Precup, D. (2000). Eligibility traces for off off-policy policy evaluation. Computer Science Department Faculty Publication Series, page 80.
Rudelson, M. and Vershynin, R. (2009). Smallest singular value of random rectangular matrix. Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences, 62(11))
Shi, C., Uchara, M., Huang, J., and Jiang, N. (2022). A minimax learning approach off-policy eval- uation in confounded partially observable markov decision processes. In International Conference on Machine Learning, pages 20057-20094 PMLR.
Singh, S. P., Jaakkola. T., and Jordan, M. I. (1994). Learning without state-estimation in partially observable markovian decision processes. In Machine Learning Proceedings 1994, pages 284-292. Elsevier.
Stewart, G. W. and Sun, J.-g. (1990). Matrix Perturbation Theory. Computer Science and Scientific Computing. Academic.
Tchetgen, F. J. Ying, A., Cui, Y., Shi, X., and Miao, W. (2020). An introduction proximal causal learning. arXiv preprint arXiv:2009. 10982.
Tennenholtz, G., Shalit, U., and Mannor, S. (2020). Off Off-policy evaluation in partially observable environments. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 10276-10283.
Thomas, P. and Brunskill, E. (2016). Data-efficient off-policy policy evaluation for reinforcement learning, In International conference machine learning, pages 2139-2148. PMLR
Tropp, (2012). User-friendly tail bounds for sums of random matrices. Foundations of
computational mathematics, 12:389-434.

---

Uchara, M., Kiyobara, H., Bennett, A., Cheroozhukov, V., Jiang, N., Kallus, N., Shi, C., and Sun, W. (2023), Future-dependent aalue-based off policy evaluation pomdps. Advances in neural information processing systems, 36: 19911-60088.
Wang. J., Qi Z., and Wong, R. K. (2024). A fine-grained analysis of fitted q-evaluation: Beyond parametric models. In International Conference on Machine Learning.
Xie, T., Ma, Y., and Wang, Y.-.. (2019). Towards optimal off-policy evaluation for reinforcement learning with marginalized importance sampling. Advances in neural information processing systems, 32.
Yin, M. and Wang, Y.-.. (2020). Asymptotically efficient off-policy evaluation for tabular rein- forcement learning. In International Conference on Artificial Intelligence and Statistics, pages 3948-3958. PMLR.
Young, S., Gasic, M., Thomson, B., and Williams, J. D. (2013). Pomdp-based statistical spoken dialog systems: review. Proceedings of the IEEE, 160-6711
Zhang, J. and Bareinboim, E. (2016). Markov decision processes with unobserved confounders: A causal approach. Technical report. Technical report, Technical Report R-23, Purdue Al Lab.
Zhang, Y. and Jiang, N. (2025a). On the curses of future and history in future-dependent value func- tions for off-policy evaluation. Advances in Neural Information Processing Systems, 37:124756- 124790.
Zhang, and Jiang, N. (2025b). Statistical tractability of off oof-policy evaluation of history-dependerr policies in pomdps. arXiv preprint arXiv:2503.01134
12

---

The Appendix is organized as follows:
Section A presents the detailed statements for Theorem 2 Section B
presents the detailed proof outlines the technical lemmas essential for the proofs. The code implement the simulation is available wtw.o...t.ooooo.oo.e..ooooooooot wwt.eoooo//aaaeeeee kuangqi927 /top/////o/ooonndnnnooooo
of Theorem [
Section C presents the detailed proof of Theorem Section D
A Detailed Statements of Theorem 2
We begin by presenting the detailed statements for Theorem 2 which differs from Theorem only in the first-order term.
We omit the full proof for Theorem 3
Theorem 4. Under Assumptions and 2 suppose the sample size n is sufficiently large, then, with probability least 6. it holds that
1.
((T) (T))
(1 0-)
- Cp A
T1.5
+
(1 0*) 0-- - 03 T A ST
1og(T)(0P(A1T/5)
73
+
- (1 0*) 0 0 57
| 87
/og(T>101F/A/7//))
(12)
n
T
+
-
(1 0*)
c 0 57
A log(T9101714//// /8)
n1
T
+ vn
log(1
The first four terms are related sub-optimality terms. The proof of the first-order term is provided in Appendix [CI.I and the proof of the higher-order terms is given in Appendix C.1.5 The proof of the last term related to the empirical process is presented Appendix C.2
B Proof of Theorem 1
For convenience, we omit the uppercase letters and abbreviate P(X, Z = 2 Y) as P(X, Y).
Proof. By the definition of policy value, we have
V(T)=
Txp" "rr)
t=1
Σ
p(re 00,81, a1 ,1.....,4. ae 0r)p(00, 81, A1, 01,..., a,, 0c)
t=1
00.81:01:00 10.11: 100000
-ΣΣn Σ
p(ra 8t, ())ppp 81, an 01,..... 8t, St, 0z)-
t=1
00.81.01.0H 0r
We now recursively decompose the joint probability p(on, 81, a1 01,.. . p(on, $1, OI......... 8t, a, or)
Sz, Sn, 0:) as follows,
p(a: Ou, $1, 01, 01,
8t, Ot (p(()) $1, 01, 81,
(a; oc, (4.h4-1)p(p
On, 81, 41,
)))o 81, a1 01, 01,..,,,
(a;
or, 1)
st)p(ou. $1, 01............
ne aa ot, 11/hh1)ppppp)
st)p(s 00, a1 o1, o ))p(ou $1, a1 01, .1,..,,0 o(-1)
ne (a, or, 1))
st)p(( | 3 $1 01 .I...,, 0)-1).
Hence, by induction, we obtain that
1.
plon, 81 U1 01,.. ..................... St, az 0t) =
II
(a os, 14-1:11pp )p(( 8i)
I p(sc41 si) p(silo0)p(oo).
13

---

Note that O2 1T A., A1-1 St, we can rewrite as
p(r: St, ae)p(ou, $1, a1, ....... St. az, 0z)
I
=p(,,, 0z st,ad) as)
n:(a; oz hi-)))))
I p(0441,0 |ss, (s))
p(si p(s1)oo))(on)
i=1
We now rewrite the policy value in the vector form as
Σ v(a)
Σ G1.0eemeei
[Im(a on ho-1))
T2
(13)
P(O,)P(S1100)
II [P az Si)
P(re, at, St).
Thus, the summation uses only observable variables.
We aim to eliminate the hidden states in (3) We invoke Lemma 2 of Tcheeeee et al. (2020). and the difference lies in that we use the full history (Oo. H as a proxy to infer hidden state S instead of one-step observation 0--1. This yields the following key causal structure.
P(S,, P O S,_ | (T
St)
=P(O,-1 a S, O,-1 a,-1, 0.. H 2 , 0,-1 a. Oo: H.
(14)
('(O, a,, Oo. H1 0r ar Oo, H,-1),
and
P(S,, 0-1 at 1, St 0: az, St)
-P(O,-1 a- S, 1)P (0, 0t-1, On, 21.-2))PP((0-111111 01-1, H2-2)
(15)
(O, de, Oo, H [P (r. Oo, H+-1),,
and
P(S:, 9-1 1 Oo H2,2) 02 S2) = IP(O,, 0 a. 14-1,0p: Oo. H₂-2)-
(16)
Combining these three equations yield
[4]. 15 and 16 we eliminate the latent states from 13 and
1-1
P(O.)P(()
II
P(S (i) P(ri, ar at. St)
=P(00))(O,100))
Pi(O) (n, On)OP, on an, On) 02, Oo. Hi)P 02 42, Oo. Hi) Pi(O3 (32 Oo (O), 03 Ou H2) Pt (0, a1, Oo. Hz) as Oo, Hz)
(i 0z On, H, (O or-1, Oo, Hz-2)PP at On, H, P(rr or a, Oo. H.-1)
-(O00)F(.100) (0, a1 Ou)
II P(0 a, Ou, HP (0 0 Oo, H,)
P(r,, or) ar, Oo, H;-1).
Here, we require P(O, at. St) St) to be invertible.
Putting all together gives the conclusion, which expresses the policy value entirely in terms of observable variables.
B.1 Identification via value function
In this section, we present complete proof of the identification results beyond the tabular setting. Theorem 5 (Identification). Under Assumptions 5 the policy value for can be identified as
V(T)
E
(a
(17)
14

---

Proof.
T
V(T) =E"
Re
(by definition of policy value)
1=1
T
= Bss m-
E
Re
Si
(by the law of total expectation)
1=1
=Es m21
E
Rs
S1, Ho.
(by Ho 0)
=Es, ~M
E
Σ by; (a, 02, Ho)
S1, Hu
(by Lemma
-Esyvss mis
E
ba 01) 81
(by Ho 0)
=E
Σ bū (a,(a,00)
Consequently, we complete the proof.
Assumption 1 Assumption 4 In tabular settings, the rank conditions are sufficient conditions for the completeness condition to hold. P(O; a,, St) being invertible means different states map to distinguishable observation distributions. Similarly, invertibility of P(O, at Ou. H,-1) ensures the history can span the full observation space. These together imply that the observable history {Oo, Hi-1) } contains enough information to separate functions of the hidden state S,, which is exactly what completeness requires. Besides, the invertibility of P(OO, 0e. On, H₁-1) ensures the existence of value functions in Assumption 4
Assumption 4. There exist real-valued functions (b% Ax O x He-1 R) that satisfy the following conditional moment restrictions:
E bV O,, Oo, Ar, H,-1
(, Or, H,-1)+ Diee+ (a', Od',0 H.) (((e)) O,, H.-1) Oo. A,, H--I
Beyond the tabular setting, the existence of these value functions is justified by some mild regularity conditions utilizing tools from singular value decomposition in functional analysis (Kress al.) 1989).
Assumption 5 (Completeness). For any measurable function ge S A He-1 R and any T.
Elg (Sc, Ar, H.-1) Ar, II,-1, Oo] 0 almost surely if and only if ge (S, A,, 11,1)) almost surely.
The completeness assumption is widely used in statistics and econometries. For example, it plays crucial role in instrumental variable estimation, where the identification of structural functions often depends on the completeness (Newey and Powell 2003 Hu and Shiu 2018).
Under Assumptions 4 and 5 obtain another sequence of conditional moment restrictions 18 that
are projected onto (St, Ar, 11:
(7,, H,-1, O.) Ar, HI-1, St E (ATT(A. Oz, H--1)
(18)
1 He, Oct1) Oi, Hr-1) | Ar, Hi-1, st).
a'EA land all all 1, 1,... T, holds that
Lemma 2. Under Assumptions
E
bV. (a, O,, 11--1)11) St H:-1
Σ 1
R2 St, H 1--1
(19)
15

---

B.2
Proof of Lemma 2
Proof. We prove it by induction. At the step & = T, we have
E"
RT
ST, -T-1
=E
1
RT
ST, OT, Ar]
ST, H, Or
Sr, Hr-
(by law of total expectation)
E
E
E
Rr
ST, 1r, Ar = πτ(aa Or, HT-
ST, HT 0+ ST, HT-
ST, Hr,,, a| ar(al Or, Hr-1) Sr, Hr-1
E
E
Rr
E
Σ E
RT ST. Hr = o) aT(a| Or, HT-1) ST,HT-
(by Rr
IL Or
ST, Ar, HT-
Σ E
RT ST, ST. Ar al kτ(a Or, HTT-))
ST, HT-
Σ E Rr
Sr, HT Ar
क Or. Hr-1)
Sr,Hr-1. Ar =
(by
Or Ar
Sr, HT-1)
E (a Or, H1-1)
ST, HT-1, Ar = a]
(by Or Ry ST, Ar, HT-1)
Σ
HT, Ar = =a)
(by Equation 18]
E (Or, HT-1.
Sr, Hr-
(by Or 11 Ar Sr, HT-1)
E
ba Or, HT-1)
HT-1
According to the above derivation, we have shown E. b7, (a, H1,1) S,. H, ET Σi R Sj. H when = T. We proceed with the derivation by induction. Assume that [.E, by, (a, O, H S,, H = E= [_' Rg SJ, H holds for j = k + 1, we will show that it also holds for j = k.
For j k, we first notice that
1
Σ Re
Sk.
Ha-1
Rs
Sby Hx-1
+ E
Σ 1=k+1
Rs
Sk. Hx-1
16

---

Next, we analyze these two terms separately. Analyzing the first term is the same as E" [r Sr, Hr-1] by replacing T with k.
T
RR
Su. H
Ex
R
Sk, Ha-1, A&
Sk, HK-1, Ozl
Sks Ha-1
(by law of total expectation)
Sk, Ox Onl
Rs
Sy, Hk- = a ak(a Ox, Hx-1)
Sk, H
E3
R
Sk. H Ok A4 = (a Ok: HK-1)
Sk, Hx-1
E
Rv:
Sk. H 1, A
ax(a| Ok, Ha-1)
Sk, HK-1
(by
Rs
1l. Os Sk, Ag, Hk-1)
Σ
E.
R# Sk. H 1 1, A₁
E T On, Ha-1)
Sky HK-1
E.
RR
Sk. H As
B MT(a| Ok, Ha-1)
Sky H A
(by
On Il. Av
1kp Hk-1)
Σ E RaTT(aa H,,H) H4-1, A
(by OF Tl Rs Sk, A Hk-1)
E. Ramz(a O₂, Hb-1) S5, Hx-1, Ag =
(20)

---

For the second term, we have
T
E"
R
Sk. Hk-1
-= +=+++
Sk+1, Hss Sk
Sk. Hi--
(by law of total expectation)
1==++
17
Rs
Sk+1, H&
Sk. Hx-1
(by (Re 11 Sk Sk+1, H&)
1==++1
E8
by OK+1, (k',t,,',,,,,,11 Hx)
1
Sky Ha-1
E
Σ b 0 Hx)
Sk-1, Hk. Sk
Sky Hx-1
(Ok+1 TT Sy. Sk+1, H₃.)
bi:+i Okt1, Ha)
Sk, 11
(by law of total expectation)
Wa'tildd, Odt,0
Sk: Hk-1, Ok: As
Sk. Hx-1
(by law of total expectation)
Σ b (a', Ok+1, Ha) Sk, H Ok, As = a 1
E
Tx(a Ok, Hx-2)
Sk, Ha-1
E
Σ
E
bū (d', Ok+1. Ha) On, Hx H(-1) Sb, 1 Ou,Ar Ax =
Sk, H4-1
E
E
b7.4ti Ox',0 ,d, Ha) Oz, Hk-1)
Hb,
Sk, H
E
E
1 (a', Ok+1, Ha)aa Oz, Ha-1)
St, H4,
Sk, 1k-1,A8
a
(by O₂
IL Ap Sk))
E
b Okt1, Ha)mo(a On, Ha-1)
Se, H As (by law of total expectation)
(21)
Combining Equations
20 and 21
we have
ET
Rg
Sk.
Ha-1
t=
= E
R
Sk. Ha -1
F
Σ
Rr
Sk, Ha-1
lI-++
(a Ok, Hx-1)
Sk, HK-1, = a)
Σ b7 (a 0k+1, Ha) On, Hb-1) Se, Hx- A =
(by Equations and (1)
E Rati(a Ok. Hk-1) + Σ (a', Oc+1, (a) Oz, Ha-1)
St, H As =
18

---

Vi Ok: 11)
Ski 1 A& al (by Equation 18
(a, Oz. Hk-1)
Sk. Hk-1
(by OK TT As
Sk: Hk-1)
E
b Oks Hk-1)
Hk-1
Therefore, E= Et= Re Sk, [k-11 E (O Ha-1) Sk, H also holds for j = k. if holds for By the induction argument, the proof is completed.
B.3 Identification via weight functions
We provide an alternative identification formula with weight functions {b |
Theorem 6 (Identification with weight functions). Under Assumptions and the policy value can be identified by weight functions as
T Σ t=1
V(T) E Bem Or, Hy- Ho-1)) H,-1, Oni
Proof.
T Σ
((TT)
E² (S.,
Er
Re(SS,, A.) Or, St, H(-1]]
E
a)((S Oz, He-1)
Σ
EE
ETT
Σ Re(S B1(5s,))7T(al0 Se, H
Σ
E
wi (St. H(-1) F=" Σ Rel On,
1 H.-1) St. He-1
Σ
E
Wr (Sr, H(-1)
Σ
Re(S,, (d, Hr,1)
aEd
Tr, Ha-1) (a(())
Σ
E
wr (Se, Hr-1)
Σ
Re (a))
Σ
E
E
wh(S 14 Re Ar)
Te,A:(Or Hc-1)
Sr, Ho.1o1 0.1
(by Ar ~ xb((S.))
*,( |S))
(A) Or, (1 He-1)
E
(A, Si)
E
[Re Oc, bwv Hc-1, St, H,
(by Equation 18
Σ E
[ A.) (A, Hr-1, (A,
S., 11,1,11)
19

---

(Oo 1T (0,, Ri) St. Ac. H(-1)
Σ E [R
H4- AA HA-1,
C Proof of Theorem 2 and 3
In this section, we provide the proof for Theorems and 3 in the main text. We only show the proof for the fully history-dependent policy, as the memoryless case can be derived straightforwardyy by excluding the history H from the conditional probabilities Pa. and aa. Before proceeding with the analysis, we first recall and introduce some notations.
Additional Notations. For t = L..... let D; represent the collection of historical data up to time step 1, i.e., D, = (ob, (op- , =1>=)=>> with Do = {ob 1i=1- For simplicity, we omit the su- perseript n² when referring to the expectation, variance, or probability under the distribution induced by T². To distinguish between different sources of randomness,
& to denote expectations over random variables (capital letters) and E to represent expectations over offline data, when both & and appear simultaneously. We use to represent the identity matrix, with its dimension being clear from the context. If a non-negative random variable X satisfies P(X < (E,, T)) + 0 as + 0 for any n, T, we write X Op(=(n, T)) with high probability.
Note that we assume sufficiently large n in Assumption c),, where we require a sufficient number of samples for each triple (oo, ac), ensuring consistent estimation of the conditional probability matrices. Specifically, we require ho 2 ripp" (on, a;) (1 - 0r.i5): where Rog. represents the count of the triple (ou, h4-1, at) in the data, and p. (ou, he-1, az) is the probability density under the behavior policy n². Define the event E == (3 I, on, h4-1,,1 s.t. Rlg 1 Z npp (ov, h ae) (1 9r.is)}. Then, combining the multiplicative Chernoff bound and a union bound over each ou, he-1, and ae, we have
P[E
Dop < nptt" (oo, he-1, (1 (l,is))
2 mine heg wi heiihe)))))))
AIOT
To ensure the number of samples is sufficiently large, the P[ET should be sufficiently small. This requires the sample size satisfying n
polylog(1O) _AA
mine, 1.- 1 P? (0u.he-1,a.)
Then, we consider the following decomposition of the error
((T) - ((T)) =
bi (4, 01) R.
Σ (vi
bv. (a, 01)] - Σ (v.
8 (a, 01)] - - Σ bw, (a. 0.)
+
E
We begin by analyzing the sub-optimality term E. 17..b4,10 (a, 01)) E. Ty. 01)). The second
term E, by. O1)] - E bv. (a, 01)] can be upper bounded by the uniform law of large numbers according to the empirical processes.
C.1 Bounding E bi (a, 01)) E. (a 01)]
We first decompose the sub-optimality term into three parts. Note that
E
Σ by, (a, - 12)--bbvaae 01)
a
20

---

3
b (11,01) 01) -
Σ
P
P vi (01) (ri 02
21
12
D7.1 (1)) Σ (1
Σ
P
og
21 (01)
(O:) (n+ Σ (01,
01
a
a
r2,02
02
Σ
(O:)Pt Σ Pa
Σ
02 (01, 02
by
bv. (az, - (0
3
Σ byg 01)
ni (a)
Σ
P Parm 11 (01)
Σ (0,,
12,02
02
+
([0=00))0T00011 Σ
Pan
Σ
bi: (2g. 02, (01,
Σ (01,
11,02
1/ (0 (
Σ
t2 (r2 Ebr
03, (0,, a1, 02, 02
12:03
ag
( (((B))+
We replace the data dependent terms P a, and PL ar, with their population counterparts P/. and Pi "e.41.0111 respectively. This error decomposition is then the sum of E(Ei), E(E2) and (Es). where
F1
Pt
E
1/1 Pa
by (a1,0)) Σ
(F1 +
Σ (iz o2, (O1,
11,02
a2
pt
P Pai
Σ
T2ts Pt
Σ
P 02
02
Q1
P1:02
82
P2/03
Σ
67 02, (01,
(r2 Σ
by (23, 0z, (0,, 02, 02))
u1,
+...
Σ
1 Pt Σ P
Panroos 11
Σ
T2th pl Σ
P
Pos Σ
T TT Por
01
11,02
12,03
av
bV.T
DV.T(ar
(ar,or, or, 01,, , 0rr
PT
E2
Σ
Pl a1
Σ P
Po - Σ Ti pl Σ
P
Pai
01
Q1
21:02
a1
11.0g
by (a),
-ri+
Σ
by (az, oz (O,, (2,,, (01,a))))
Σ T
pt
Σ
P
1
Σ
T2t22
pt
Σ
P
Pa2.72.0g1/2
01
02
11:03
a2
12.08
Σ
pt
Σ
P
Pas
1i Σ
T2th
pt
Σ 12.0g
P
U2
02
41
21,02
02
bi (ag, 02, (1),
12 + Σ
Wis 03, (01, (1,,01,02002))
Σ niS Pi
Pa
Pa 1 Σ
n2 Pl Σ
Pa
Σ
T P). or
Pa WP
T1.02
13,03
ay
21

---

IiVI Pi,
1/1
Σ
T2pyy
Σ
Pan Σ
T
Panr VT
r1:02
a2
12.03
Σ (ar, (aT,, or, (1,,0 ,0T .(T-
rT
B3
1 (41, 01)
Σ T142
P a1
Σ
P Poirioot 11
Σ
[v,1(a,,01
12,02
1b
P
Σ
P
01.01,0214 11
Σ
Σ
T2 P
Σ
P
Pa 22
Σ
DV:2 23
11,02
12:09
+...
Σ
Ti
P
Σ
P
Pa
TT P ay-1
E
Por-
P
71,02
rT-1,07
Σ
DVT
Σ
Tr TT
Σ
Permy te
Σ DUT
2T
Note that these terms ultimately decompose into a sum over all possible observable history trajectories. Simplifying these terms, have
E
Σ
P
Σ
P Partiennll
{
Eb
bv
(rc+
Σ
7GPE11
ai
P1l1
Eg
1
P
Σ
P
Σ
M pt Σ
Porrooy1
P
1=1
71
11
Σ
by.t
(re +
Σ byst2)
R4+1
di Ioirs ))
E3
Σ
T
pt
Σ P Pam
Vi-1
bi Σ Σ
Pt
Paston
ae
Tt-1,00
at
de
Tt,0c+1
is straightforward to show Eg = 0 by noticing that
Σ (arlor, 1e (o.)
Σ P Pasr dr(or) Σ
Te.00+1
Σ Telaalos,, 1--1 (t P Pa.bb(())) Σ bi 14-1)
wi (or)velor)
Σ (ar Oe, hz-1)
Diyzlar Oc, I1-1).
ai Throughout the proof we use the trick that
Σ ba, h--1) Σ (eloooo,
Pt.
Σ P Par
Velrr + Σ (at 00-1
a11l
Σ h
Pt aq
Σ P
Pa
Σ (ar oc, h(-1) - -rre Σ
bi (a o141, hct))
de
Te.0x41
Bx+1
Thus, it suffices to bound ((E)) and E(Eg) separately.
C.1.1 Bounding {(F))
Note that E(Fi) Σ E(T,) as the sum of T terms where
E(h) =8
Σ Ti (i(a100) क (as Si P!. Σ Paj th
Σ (an - -12 Σ bizlaz. (00. a.))
-1)-
(a Si))
P1.02
22

---

Ti (Ai
Vi PA PAA. $1
Σ (i, 01) (11 Σ
by. (02, 02, Hil)
* (
11.02
42
Ti(01 (11)
T2 02, 01, (222(())
8(12) -
(allaii)) yos Pl
Σ P Paim th Σ
(51)
mi( (22)
12n0g
1/2
P
Σ
P
Pag.rzoo
U2
Σ biza oz,
(01,))))))
((22 (r2
bi, (3, Σ
0z, (O1, a1 O2, az))
22.03
11
P
PA
PALKI
1
U2
P
Σ P
Σ b (2, - -r22
Σ
bi (as og, H2)
r2.03
82
92
AI (2 O2,
Hi)
4/2
Pl,,
Σ
P2 452
O2, Σ bi (2, H2,Hi)
(ra Σ
biza(as 03, Ha)
12:03
E(Ir) =
Pt WT
PA thr PT
Ay
Here, we simplify the expression by rewriting the summation over de, Ot as the expectation of At, Oz, and use the fact that A, 11 O₂ S..
First, we need to verify that the expectation B[E(E,)]=
= 0.
For E( it suffices to show E P.Pa ar og = P Par. 11.71.02 01..- Note that for each entry of P as .og- the empirical transition probability is an unbiased estimator its population transition probability (Lemma 12
Σ ( of. rí, og at) = (02,
(0,,01, 01, r1, Ou a1)}
E
E 1 (0), at)
a1)]
Ele (02, of, ri, ob, at) (o2, 01, a1)
, o |
E 1 (op at) (0o, a1)}
Boo.ay pl (02, 01,71 | 10,001) 01)
foo aj
(4) p
110.a1
p(oz, 01.71 (0.
Thus, E.P o1.
P Parorioo which yields
[[E(1,)
E
E
T1
P
Σ
PA
Σ (v,, 00---(1 (r+ Σ
by. (a2, (a2, 02,
r1,02
03
E
1
A
Σ
P
P 11
Σ (a, (n Σ
b2 (az, 02, H1
21.02
82
E
Ti
(z)
(a.
pf
Σ
P Pa
Σ bb bi (1) - (r1
- - Σ (22 02, 01, 01)
11.02
E
(a,, 0,)
For ETT), > 1, we can show the similar results that E am = P P. Thus, R(((F1)) =
0.
Then, it suffices to derive the bound for the variance of E(E,). By applying the law of total variance (Lemma we have
Var (EE))
23

---

T
Var
P
Σ
P U
Σ
b/.+ - (r+ + Σ
A Pe 1
p==1
"
ae
ac+1
Σ bi22 (ra E D |
E
Var
Σ
P 1
Pe.0++1
act1
Next we consider bounding Var(E(Ei), under different conditions.
(1) Bounding Var (EF)) without considering weight function Note that
Var
{(Ea)
T
D. [.]]
E
Var
E
Pt A
Σ
P
P 2/
Σbb
bi. - (rx Σ
"
1=1
1e.00+1
Re
a0+1
PASTiOA t/ ) Te,0c-1
E
Var
TT
P
Σ
|D4
b
N/ D: }}
E
3
Te'
Var
P
Σ
PA
P
b
1=1
T2,00+1
T
D. (PI) (PW) }
2
E
3
P
Σ
Cov
P
P 1/e
1=1
P=1
Tr,0t+1
T
Dr (PhoTTo )
2
E
Te
Σ
diag(1(Eoo,A) C)v
P PAlmooy We
P=1
1e,0++1
(1
$
2
T
TP
1
diag [ Eo 1/tooh/-////ooooo.. diagg(P (Aag(PPA th) (P%)) } pt
1=11
T2
T
(1
0)
E
2 A. diag( P PA (P')))) ) T
pt
1=1
==1
T2
(1
CC, Σ
|||l dh 1|2
| 11: diag (a, 1hx ll2
(6
T
(1 0¹) -C,, C3 Σ
n
T2
T
(1 0-) 10000"1'-000 CCC Σ
101 14
T < (1 - LAPT.
The inequality (i) follows from the independence each P P...r.. 0...1 since {r?" (1) 0+1 partitions the n episodes into disjoint sets according to all combinations of r' and o141- We define Eo
A, nppp' (1 Or,is)}, and 1 (Eao.h, }} is a vector of length |O]| H.-1l, where each element corresponds to Eng.i The inequality (fi) utilizes the fact that for any ag E
Cov Par 1/e D.]]
< diag (Par.rioo /// aoo P Parsrioon the P
(22)
< diag(P (aarinee vsl ooneer)e
24

---

The inequality (iii) follows from that diag (Pa, lla s 1, and | m (Po.) I Crv/Ol17-11
1
Therefore, obtain the upper bound of E(Ei)
T
E(EI) = Op
(1 (1-00)10(0((100
nn
(2) Bounding E(E)) with the weight function
Var
E(Ei)
P 1/2 Σb7 b7. (rx > E [D. |
Σ t=1
E
Var
3
II
TV
P
E
P
1=1
"
ac+1
Cw CWCC(1
--)
T
t=1
by lar, O₁, Hi-1) - RR. + E (atti Oc+1, Hi) Or, Ar, Ac, He-1) }
E
Var
(by Equation (24
C2 0-)-1
T 101 LA Σ
E
Var
Re + Σ
by (a, Oc+1, Hi) Or. S. Ar, He-1
11
1=1
Cw - -0)
IA
Var
R₂
(by Lemma
T -
For the first inequality, we examine the cases for = 1, separately in the following. The result for t follows by similar argument. Thus, incorporating the ratio function, obtain
E(E,) = OP ( Vn
||
For t = 1, we have
(A,10))
Σ bb - (ri Σ ( (waa)l |D| |oa}}
Var
18 TPt
PA
(i(()))))
11:02
a2
E Var E ((( Oo) A1, (1(11))
(11+Ebzzlasn) o2, [, |oa}}
pt, PA 11
Σ (a,, -1))-1r Σ b2
r1.02
=B
Var
(Ai, (n), (Ai101)
mi))] |oo}}
1 Pi PA 1/1
Σ (a,,0) 10)-(p
-(11 Σ 2 02, H1)
03.03
25

---

(by
Oo 11 10 00(11.A))
<B
3
Pi] Σ 0;) > 22 02 02, Hi)) } (P)))) }}}
pt
Σ
Ecov
Cov
A1
22:02
(1)
3
(ir (A1, 00) (0)
1/ Pl E diag
1oEo diag
(P (AA,))))) (P
(1) ++ 22 O2, O2.Hi) }
A2
0²)-
1A TE
LA
(4)):(41,0))((110)))
n
1 Pl 01
Σ (a, - diag (P az 41) (Pt)))
bb O2. H2)H
42
-2(1-8") - --)-1 [O|IA|]
n
Σ bū (21, - -(R1 + Σ
by (,2 O2, [5)
E
bi.1 (A1, (
C7 8 O111A|
n
Var bir (A1. (o). (o)
Σ b% (a 01) ())- (R. Ebrlla2 O2,
The inequality (i) holds by applying the same argument in the previous part that bounding Var (Fi)) without using the weight function. The inequality (ii) holds since that, for any 1 E (T).
15. Pl. diag (Pa,th) thr) (Pt, T de
< || w/ | pt, diag((a,
(23)
S 1810014-111
The last equality follows from the zero mean property that
E
O0. H,
Σ (a, O,,H, - (R, RR,+ > De.erlaatt Oct1, H.),
E
Oo. Hr-1BBB Te (Ar He-1)
Σ de
by (at Ot, Hc-1)
RR + Σ (a O411, Hi)]
Oo, 0o,, Ar, H
a++1
Ui (Ar, Oo. Oo, HB-1)BB Te Te(ArOOr He-1) Σ (ar, O,, H. by (A,, On, He-1) Oo, Ac, m
R
(by Assumption
T.(A. Or, H: > (ar, O,, H.-1) ( Or, Or |...)))
E
(Ar, Oo. H.-1)
(e(Se, H1-1)
E
Σ (A00
St Ar. Or, Hom1
(A(
26

---

(by Assumption 3
=E Σ (a]()) wi(Se, He-1)
E
Σ by. 10r O,
Hr-1) - ba, Oz, H(-1)
(al(s)
St, At a. Oc: Hi-1 s]
=B
wi (St: H1-1)BB
bynla, On, H(-1) Sr, a, Oz 0. Ho-1 Σ bir O2, H1-1)
=0.
For the last equation, we further have
(
Σ O1) -R) Eb 02. |r..s.
E
Var
b b (A1,
E (AN, (1,,
Var
S1, Ai AI}
Σ bia(ai, (Ri + Σ bb22 O2, H
O1, Si,
(by O₂ 11 O, Ai)
11
S Cw E E
01,
2az O2, Hi) |0,, A. An} (by Assumption 3
(R1 Var Σ (ai, (RI + Σ
a2
pi (A, (A
}
(an 01) - [Ri . + Σ 2 Oz, Hi) 0r, Si. A
-Ow
Var
PT (8 Yom A (1 (S))((11SSS))
02
p (at, Ot, 8t, h4-1)
p. (st, he- 1e oc, h 1))o)p((
by E
pi (as, Oc, St, 11-1))
pi (st, h4- (arls)
=Ow E"
Var Σ (a1, 01) - (R1 Σ
2a O2. O2HH1) H1))
O1, St,
where the inequality (i) follows from the Assumption 3 which states the ratio function satisfies
E Viv:(ar h (o) or, h2-11) | oe, az ho-1] S Cw.
sup aL
Thus. we have
v1 Σ O1) ( - D0 H1) Dj bo}}}
O1) (1)
E
Var
E
P Σ PA.
(A(A
Ow
Ow (1(1-00)
E
Var Σ b
-
by b2z O2, 02. O₂ 02, S1, A1 Σ
n
82
For / = 2, by applying the similar arguments, we have
Σ (2, - (r2 -(12 Σ b7 0z. Hz) ())) (2)
E
Var
3
n2
P
Σ
PA
P
4/2
n2
72.03
27

---

(
11
Var
T2 H1) pt, Σ
Posrniess
P7 (5.)
02
M2,03
bis( 03 (O2, 02, Hn)) Hh)))]
Σ 2 O2, H1) - r2 +
Σ
D2
a2
43
(S2, H1 HT) O2, H1)
E
Var &
122 JP
Σ P P2 42
ps (S2. H1 (A2(55)
A2
r2,03
Σ
2 (az, O2. H1) - (r2 Σ
biz 0g, (02, A2, H1)
D2
(by Lemma
a2
ag
(br: Oo, H2) H1) P P/, Σ
Var
12:09
(03 03. Hz)) (1a)]
Vy (a2, 02, H1) - (r2 Σ
D2
( C3 )-) 101
n
Var b (12, Oo. H2) O2, Hi) Σ (22, H1) - RR2 + Σ 173 Oz, Hz)
ag
(1(1--))
10 E Var E biv Oo, Hi (o Hi) S2, A2, H2
}
Σ 122 (az, H1) - R2 Σ
b4 Oz. Ha))
Oz S2, A2, Hi H1
(0)) Cw 0-)-1
1011AA1 E. E
1iv:2(22 On, (2) H4) O2, S2, A2, H1
n
Var
by (a2, O2, H1)
1'2 Σ b 0z, H2)
O2 S2, A2, Hi
C. 0-)-1
1d (S2, H1 2 A2 O2, Hh)
1011A112 E
n
Dh (S2, H1 m AA S2)
R2 + Σ (as, (as, Oz. H2)) ) Oz S2, A2. H1 }
Var
(022 O2, H1)
Q2
C2 --
}
101 |AA2 Ex
Var Σ
(az O2, H1) - Rz + Σ
by. Oz, OsHHo)
O2, S2, A2, H1
n
02
63
The inequality (i) is derived using the same arguments as in the proof for the case /. and equation 23 The incquality (it) is consequence of Assumption 3 as utilized in the proof for the case t 1.
28

---

Therefore, for any t E [T], by the same reasoning, we have
:
bi, - (rr _ E |0. Ebvs
B Var &
II T
P
Σ
PALmen
P
21
211l
Ow
Cw
C
0-)
1012
Var Σ lar On, Hi-1) Ra Σ bev 0411 Ho) Or, Sc. Ao, Hi-1
E
(24)
C.1.2 Proof of Lemma 1
Proof. let's suppress the target policy for simplicity. Denote D. = {O1a, Sia, Ala, R1a-1] First, note that
E"
R4 Σ bo. Od'1,, Hi)
A4,
E
Σ i Oct, Hi) Or, A. a, He-1 Tr Or, He-l)
E
Re + Σ biutzld', Oct, Hi) te(a Or, H1-1) Oc. Ar a, Hi-1
E
E
E
+ Σ b Oct1 Hi) mi O₁, Hr S₁, A. H,
Sr. A. = H
Re + Σ (d', Ho) To (a Or, Hr-1) Sc, A: = a, Hz-l
(by the law of total expectation)
]
E
E ba, On, H(-1)
Se, A: a, He-1
(by Equation (88)
by. (a, O,, H1-1)
(25)
Then, by iteratively applying the law of total variance, we have
Var
R +
Σ bi (a, Opt1, Hn)
t=1
E
Var
Σ R₁ Σ bV,441 (a, Oht1, Dr
+ Var
E
R₁ +
Σ
by (a, Ont1, Hi) Dr
1=1
1=1
E
Var
Rh. +
Σ (a Ont2,
On. Sh, Ane H
h-1 Σ
+ Var
Ri
Rn bbu4ta Oh+1, Han
On Sn, An Hh-1
E
Var
R
Σ (a, On42, Hn)
Sh, An, Hi-1
h-1
+ Var
Σ
bbnnaa On, On,
(by Equation 25
1=1
29

---

10
Var
Rh Σ by Oh41,, On. Sh. An, Hn-1
h-1
+
E
Var
R₂ + Σ (a, Hn-1)
Dh-1
1=1
h-1
+
Var
E
Rs + Σ (a, Hn-1)
Dn-1
1
Var
Rh +
Σ ba, Ont1,
On Sh. Ans Hn
+
E
Var
RB-
Sn-1, An-1, Hh-2 + Σ ba On, Hn- Sn-1,
h-2
+ Var
Σ Rr + E RA-1 + E (a,
On, Ha-1) On-1, Sa-1 An- Hn-2
t=1
E
Var
Rh + Σ
b7n44 (a, Out1, Hn) On. Sh, An; H
+
E
Var RR-1 + Σ b On, H Hn-1) Sn Hn-2
h-2
+ Var
Σ
Re
1a.
(by Equation 25
1=1
_...
E Var Re Σ Dbvenia Oc+1; Ho) Or, St, Ad, H=]]]
Then, letting h T and noting that b 04:4+1 get the desired result.
C.1.3 Proof of Lemma 3
Lemma 3. The variance of EEi) can be decomposed follows,
P
Σ
P
the
Σ Di.e (ra Σ
1=1
1
act1
+ Σ (iccel)) D. |..}}
E
Var
II
P
Σ
P Paroreoee the
Σ Di: (ra
[=1
Ts,04+1
apt1
Proof. By iteratively upplying the law of total variance, we have
Var
Σ PA
1' bv. (re+ + Σ (Ratte)
ac
1111
Dr }
-E
Var
PA Uy re:0+t1
Σ
Σ Di. - (r+ + Σ ((sti)]
91-1
Var
Te
Σ
P PA 1/
Σ bn (rr + Σ (iree)))
Dr
act7
EE Var
Σ 3
Pl
Σ
P Uv
bi.e Ebie
(rr Σ (ieti)]
Dr
b
P=1
30

---

T-1
Var
ME
P
Σ
1/
Eb., by: (r+ Σ
r1,0++1
a1
Gc+l
E
Var
P A
Σ
Σ bi. - (rr + Σ D(ctt)))
Dr
ac-1
|DT-1 }
Var
3
Σ
P
P We
Σ bb. - (re +
Σ Birttl))
A
12.0111
a1
41l1
Var
Σ r2:04+1
P
1/
bi, - (re +
Σ b(at)))
|
9c
ac+1
Σ
E
Var
3
II
Re'
th
P
E
PA
PA
Ebve - (rr + Σ
|D.]
D.
1m
(==1
C.1.4 Proof of Lemma 4
Lemma 4, For any function ft A H4-1 - Rd, the following holds:
p. (S,, H 1)
[e(A,, O., H1-1)]
E
pf (St, 11, 1 (Ar 5t)
pl pT (S
Hi- Te (Ac-1 O2-1, Σ Sela, Or, Hr-1)
=F
p (St-1, 1 H, / (Ac-1 Sc-1)
Proof. For the left-hand side of the equation, we have
Di (St, H(-1)
E
Se (A,, O,, H.-1)
PF (St, 11-1) nt (Ai Si)
Ps (st, h(-1)
Si (ar, or, h2-1)
pt Sn, 1.
st,
do,
pe (st, 11-11) m (at 84)
De (81,11911)
a (at st) st) T he,) dahhor Se (at, oc, (e,
LPt" (st, (st,he-1) 1) (at 84))
by O, 11 A St
Pf h1-1)
Joc Σ Dt" (St, hy- Teb (a se)
Se (a, or, h2-1) मं (a se) p (or s5 dordssdhhh
Σ fe (a, or, h+-1) p7 (st, ha-1) doids:
Jor
The third equality holds by taking expectation with respect to A,,
31

---

Now we analyze the right-hand side term.
pī-1 (S 2 T (A--1 1.-1.
Σ fo (a, Oz, He-))
E
Pi-1 (S1-1, (( 2) - (Al-1 S(-1)
Pi- (8--1, و πリ- (0c- 11-1, 22)
fc 00,
pf-1 (51-1 2 ग| (a=-1 81-1)
p²
(0r, at-1: O 81-1 -ي -op -00-----
/
Př h2-2) - (ac-1 1 he-2)
Σ Se (a, 0r, (1,
Pi-1 (8c-1, ف| (a=-1 81-1)
/ pxd - 3 ds idor i
(marginalization over S.)
/ Pi- (81-1, T-- (a--1 o 00-1. hl-2)
Σ Se (,,
pf-1 (8t-1, 11- - (d-1 82-1)
p= (0t, 8t, a: 0z 81 h4 2) ds 1
= / pī_1 (8011, n (at-1 0t-1, h2-2) Σ (a,,,,,i-))
p 8e) (se 10-11,8-- 11-1, (0. 86-1) dords,dar- ioor ,ds-- 1 dhu-2
=| Jongre Ae-i
(a, he 1 (ox 8e) Pt h-,, donds;dhh-1-
The last equality is by noticing that P. (st, he-1) = p(s; $t-1, ( (1 8t-1)p (SL-1, M1-2). Then the proof is completed by comparing these two terms.
C.1.5 Bounding (E2)
Similar as before, we treat E(E2) ΣT= E(1) as the sum of T terms where
(i E(h) = Σ (a Σ Pm
mlalO:)N Σ
Σ
Pm ((.)))
11:0
a1
11,99
Σ (a 01) - (n+ Σ (1
0z, (Q.,
E(12) =
क. (a10)) (O1) 01 Σ o2
Σ
nW (as (01, 0z Pt
Σ
P
11:02
42
12:03
(a Σ P
Pa
no (0) oz (01)
Pt. Σ
P
11:02
r2.03
Σ Wel 02, 02, (O1,a))) - (r2 + Σ
by (as oz, (O,, an (O.,
ag
E(Tr) =
Σ
T
pt Σ
Par
T2 P Σ
Σ
Pagrziog t/2 ...
Σ
TTUTT ay
Payrrn
r1.0g
12.03
ar.
Σ T pt. Σ P
Parmoot Σ Teth pt
Σ
P
t2 Σ
P
$1.92
r2.0g
Σ 07
by. (or,or, (0,, (0,,,0 ... ar-1)) - rr
32

---

Next, we aim to derive the bound of Var(E(E2)]. We first split E(22) into two parts:
E(B2)
3
Σ
TiVl
Plj
Σ
P
-
Emiil P!
Σ
P
81
1e.0111
re,0111
Σ bas, Oc,
ne Σ
by ( 0441, (Oz, A.....,
Oc, ai))
#et1
PA
E
PAL 82
ne (II
11
Pt
E
P P 1/
M= "
Σ bas ac, ou, (r+ Σ
01+1, (O1, , oz,
art1
=
P
Σ
PA io 1ochh-1
v/ P. -V,
Σ P P
7t-1.%
12.0441
Σ
bazelas, ot, (O1, AI,...,,. Ac-1)) - (rt Σ
by bi 0c+1, (O1, AI,... or, A
de
act1
8
P A1
Σ
PAL
Tel
vi
P A1
Σ
PA 1ote 1,0
..
T2-1106
Te-1:05
4. Pl Σ
P P
Eviilan (I - (n. Σ
bietilaen, (0..A........................... (0
a111
E2,1 + E2,2
(1) Bounding E(2,))
We first verify that ([x) O. For each E [T], holds that
T
E
E
Pt
Σ P PA--IM-10
1/ TP w TP!,
Σ P Purrooce 1/2
r.-1.0
res00t1
Σ baie ot, (O,, A A Ar1)) (ro+ Σ C 0c11, (01, ... on Aml)]] (p. !
T
E
Σ 15-1.0
P PA
2/ P. -6, P/
Σ
P P V
Pe.0541
bi Ot, (O,, Ap
o-1 Ac-1)) (ro Σ (0te4 00411, (O1, oc
0e+1
T
=B
3
Σ P (. (TPP),
- ( - oT P\,)
Σ
P P Vh
P=1
Te.0042
Σ
bV Ot, (O1, A1,..., 2-1, Ar-1)) - (n+ Σ 10tt1 (O1, A1, Ot, Ax))
ai
0e+1
=0.
33

---

With probability at least 1 - T|A we have the upper bound such that
Var {(2.))
E
Var E
Pl
Σ
PA
c - -6, -U,
E
P P 1/t
M=1
1.-1.0z
re.0+t1
or, An1)]]
byg (ar: O2, AI, o-- Ap-1, (r.+
0411 AI....
Dj
ar+1
7
(1
-00) 007-~1111
Σ
n
E
3
Te'
1
P
E
P v/ P/ -v,
Σ
diag P Partroonsst) (ie
T
1=1
1.0t
re,0011
T
1-0000111 |IA)
Σ
3
TV
P
U
(P), -h',, diag (As 14.
n
T
(1 ||4)
Σ
E
3
P - -P',
( diag (PA (1.2%)
1=1
#=1
T
(1 07) -|AI Σ
T b
max
1/
| pt
Pt a,
1 diag P Po, 1/2 )12
71
"F
a.EA
T3
T
S (1 -AACC Σ
max a.EA
|P
a: 2
Pa. - P Pal121111 1
(by Assumption aa)
(66)
T
- (1 0)) - C C
2
max a.eA
P -Parll 11
(by Equation 26
T2
(1((01144-1/0)) 10117T
(1 -+
(by Lemma 5
n(1 ((1-8*) 8*)
73
n² (1 8-)-~22
10
The equality (i) holds by recursively applying the law of total variance (same as Lemma 3 and
E Di] The inequality (ti) uses the fact that --1-B B-
A (B A)B-A)B-1, 1| 2
and diag P A,, v 1l2 1. For inequality (iii). by Lemma for any or E A, we have
miin (P 2 mmnn (Pa.) ||P., P ll2-
Thus, for any a E A, we have
1
|P ue
o Mmin ac))
0 min (Pai) -||Pa, Pa,
(26)
min (Pa.
<Cp <Cp 1O1l4111 (by Assumption 2
Here, we assume a sufficiently large sample size n, ensuring
|P - -Pa, llz converge to 0.
Therefore, with probability least T 6, obtain
E(E,1) S 1.. 11--1-0-11
|
27
3T-1
(27)
34

---

(2) Bounding (B2,2)
Next, we derive the bound for (E2,))
For of expression, denote
P.:=v P A
Σ
P P Vi
11,0441
Σ
P PAorooitt the
11
Notice that, for each & [T], with probability at least |A16, lP. pol can be bounded by
P P.
1. T.P. Pl P...PA 0/ v. (TPP, P. 1h
Pt. P
Ar PA, 2. 1/ T.P P PA, vhe
P. PA,. - w/ TP P. PA 1/
v (P), P/ PA. th + v1 PX
PA. - -PA.)
v 12
pt 1 1/ P A. 11, + ||
11 p PPA,11, 1.l1 |l -PAil1
A. - -PA 2 + | AA 12 PA. PA. 11
A.
(28)
22 max a.EA
||Pt
R. I -P -Paill
-
<CrlAlv H.
1og
Vn
(by Equation
26 and Lemma
(1 8*)
CF10"//A111oss(00/111111 Vn
St,n,8
35

---

Notice that, for each t E [T], with probability at least - |A|ō, we have
1
PAP A
Σ
P
bv. Eoee - (re+) Σ b7,011)
11.0++1
or
B++1
v P. Ar
P.P.P
PA
P
Σ
P PA 1/
Σ Ebr
(re
Σ
T1,00-1
act1
S max a'AA
V. Pt pt
Σ
P
Parreant the
Σ
Dbys rre Σ
Matti)
ai
ac
1e,0
ae
Gct1
max a.EA
4/ P1
P
pl
Σ
P
E
liyy (ra
Tr:04+1
T (1 0-)
pt P ac
(PD))CCP/10HHH111 A
max a,EA
n1
(41)
max a,EA
I+Pr ae
P Po.) >b11
T
(1 0*) -CC///0
vn
(|/71/2 + +||1t, 1 Pa: - -Poll l2l
T (1 0*) :CPV 1011
s max EA
Vn
+ Cp (1-8")+
T
Vn 101
vn (1 0*) 111-00)-cpp//1000001 11p//100/HH
(by Equation (26) and Lemma 5
=(1+ (1 - -1)-)
CrIoriAl1 01000/411100(000141-111110 Va (1- (1-0)
Vn
=T + temb)) Sem.
(29)
Here, we denote
(1-0')
S,,
1r
/n
For (i). by using the similar argument in the proof of bounding E(E)), we have
Σb by. (r+ rrst Σ b7 )}
T
max a.EA
Pt R1
Σ Par Por.roos
<Op
(1-0))
vn
Ts.0c-1
ar
Bx+1
The inequality (ii) uses the fact that A A = / + A (B
Then, for E(E,2)), we have
2(222))
T
=
Te
PL M
Σ
PA, 1re 1h
Tee
Pl
Σ Fe-1.0t
PA ao Br-1)
(=1
1t-1.00
P
Σ
P
P th
A.
T1,04+1
(as, oc, (O1, 01,...,,--1,,A--11 - (re Σ
Al,..,,, De (a141, (01, AI,... ,1 A ...)))
a2
a+t1
II
T1
Ph Σ
P P
T1,00
Σ birlar or, A0.,,,...,,,
9-,, A(-1)) - (re Σ
bT 0641
0c11, (0,, A A (0......... A
a+41
36

---

T
1-1
P..
Pe
P
E
P
P Vt.
#=1
Pr:0441
Σ
bi,elar, or, (01, A91,A...,011111111 A - (ree
a++1
(-1
t-1
<0
3
Pr. - Pe Pr +PP
II
Pe
P A
Σ
P PA
1=1
F=l
F==
Te,0441
Σ
by (ar,, Ot, (O1, , Ar-1)) - (r++ -(re
Σ
by 1 04:1, (O1, AIs..., 01, A
di
2112
(by Assumption 2 a) and Schwarz inequality)
3
Pv Pe Pr)
II
Pe
TPP A.
E PA 21
M=1
1r.0
Σ
be, Or, (01, -1,, Ar-1)) - (re Σ
1 (0,, AI,, Ail)
ax+]
Σ (PI) 61 (pi P1)
1-6;
6,-1 (P--1- -Pr-1) 1 1-61-1
3
(Pc-))
Pt
Σ
P
P 1/4
Σ 1%.0. (re Σ (
Ae
F2,0+1
de
a++1
pi 1111 pi PPP
1 1-61
8--1
1-51-1
<03 7
Σ
Σ
Pc-1
P P Pr-1
T (1+ + Cerm Sam
5 (E(0.1)--1(119))
(by Equation (29
sc
| 01 + P -Pil-1)1- ... (1P-11 56 1 -Po---p-1(--0-11 -1p11 101 P 81
T(
Scires)) Gr.m
(11+ p.: (PI-PI) ... (11+|p--1 1P-1--P-11 P.- - -1] I I(1+ + Lemo) )emo)Sen
<03 Σ
7'
T
t-1
(1 (1+ (1+Ev mv.m) (1 + (mmmm))) Se.
STC 4
(by Equation 28
#=1
(1 (1+ -1 (1+ ((ttam))een
STC
STC
Σ
t Eem,o (1 + (tmo)) Sem
ST (1+ EmnSII
37

---

The inequality (i) holds since (1 + Stmm,s I 1se, with E,,,, < 1, which is ensured by assuming sufficiently large sample size n. Therefore, with the probability at least |A[T obtain
2 ST c (1 Er.n, ET,,,
T (1 0²)
O
A
1og((0)1//)=-10))
(30)
T
+
n nh (1 03) 01-
A
ST log(
Combining with (7 and 330 with the probability least |A| TT) the upper bound of E(F2) is
T.5
E(E2) x
(1 - 07) 0
27
A S7-1
/og(10)F1A/7-1100
T
- (1 0*) -1,000)
1og(10)F14/7~116)
+ 7 (1-
| 1 log( 0
73
0%
n
C.1.6 Proof of Lemma
Lemma 5. Let be the d1 d2 matrix whose rows each sum to one. Let P denote entry-wise estimated counterpart, where euch entry Pij E (0, is unbiased estimator of Pij E (0, 1) based on naj independent samples satisfying Σ/=1 nij N for each 1....,dy dy. With probability at least 1 8, the spectral norm bound holds that
di (8)(d1)))
| - P
2
N
Proof. Without loss of generality, we assume dj > d2.
We begin by expressing P P as sum of independent random matrices
(1)
P-P P
Ek.
Eg
E
xx(0) P..
(E (T(
Here, P. N ER= ( is an empirical average of N independent multinomial trials, P; denotes
the i-th row of P, and x IRd2 is one-hot vector drawn independently from multinomial distribution with mean P..
Then, we apply the matrix Bernstein inequality to the sum Σ Ex/N.
Note that E[
||&l|l < 2/d thus it easy to check that d, By applying Lemma 6 for any t > 0, we have
N
-t/2
P( - p01|= 2) = =P(
Σ
Ex N
21) s (di + d2) exp
2 N
t/3
k=1
N
Setting t == /
(8) N
for constant, with probability least 1 5, the spectral norm of the
deviation
di log (d1/5)
p Pl2 S V
N
38

---

C.2 Bounding . (a, 01)1 - -E), (a, 01)]
We first introduce the concept of Rademacher complexity. which used to measure the size of function classes. Given any real-valued function class & defined over random variable X and any radius 6 O, the population Rademacher complexity defined as
" Σ 1=1
R(g) = 1x,,x
sup .eE
eag(Xi))
n
where {X,]== are i.i.d. copies X and {e:}==1 are i.i.d. Rademacher random variables taking values in (-1,+1] with equal probability. The empirical Rademacher complexity is given by
(G)
E.
sup DEG
If the function class G is bounded by T, by applying Lemma I0 can be bounded by
the empirical Rademacher complexity
(g) = 2 log |
(31)
Note that we can separate EE by; (a, 01)] - -EI By. (a, Oi)] into two parts,
(a, 0z) - E Σ (v
E
(v. 02) - 11- ba, 01)] -E 3 -E(E
- (a, -
E
by. (a, 0ii] - Σ by.
-E|_oEEEee (a.
+
E
E
bva 0z) - Dab--bn
bi 0i) - E Ov,i(a,0)) -x)
E Σ (a, 01) - Σ by (a,a
+
(a)) + (b).
For (a), note that Eg tv.1 Ea by, (-T.T)) By applying Lemma 8 with probability least
1 8, we have
(a) = E
Bv. (a, 01) - De (a, (a,)1a - Σ (v, O1) (1)
10, 0n]]
Σ b(a, O1) - - (a, (.) - Σ b(a, 01) Σ by. ba,
< sup BeB
E
(32)
(2g(2/8)
<Rn(Bi) + T
2n
log(c1/5)
<2coT
(by Equation (31)
where and are constants independent of T.
For (b), note that E, by E [0, T). By using Hoeffding's inequality, with probability at least we have
8,
87.1 (a. 0.)] - - Σ by (a, 0.)]
log(e//8)
(b) =
< ET
(33)
n
39

---

where and are constants independent of n, T.
Combining 32 and 33
with probability at least 28, it holds that
bv.i(a, 01) - Σ ( 0.1] s T
log 1/6
D
Additional Lemmas
Lemma (Matrix Bernstein inequality, Tropp 2012)). Suppose XI,... Xn are mean-zero, di d2
n... random matrices such that ||Xs|l I C almost surely for all E m....., Then for any 2 0,
-12/2
Σ
X;
2
S (di d2) exp
02 + Ct/3
where o² max {1) Σ I II E|
Lemma (McDiarmid's inequality). Suppose XI, Xn, E X independent random variables
and the function f x - R is a mapping. For all i E (1....,1 , and for all x1. ... In Ty E X, the function satisfies
If (IIS 24, 21411"" ,,,) xx) (x1, " ;;-1, T141:" , S ci.
then, have
IP (11(1)... X.)) - Ef(x, .x,) 2t) S 2 exp
21
Σ c
Lemma 8. Suppose a finite function class with |I S M, with probability at least 1 8, we have
log(2/8)
s(.)) - < 2R) + M sup
JEF 1=1
2n
Proof. Using the symmetrization technique and McDiarmid's inequality (Lemma 7.. for any 5 > we have
P
sup JEF
Σ 1=1
- ( E[f(X)) > (R,(F) +
< 2xexp(
2nc
M
Setting 2 exp
2nc
8 and solving completes this probability inequality.
Lemma 9 (Hoeffding's s inequality). Suppose X1, X2,..., Xa are independent random variables where a < X, S b almost surely. For any > O, we have
x. - >1 S2 52
{
2nt²
[b a)
1=1
Lemma 10 (Massart's finite class lemma). Let G be a finite set fanctions. Suppose that all functions in G are bounded, i.e., supyeg || S B. Then, the empirical Rademacher complexity is bounded by
2 log 9
(9) = B
Lemma 11 (Theorem 4.11 Stewart and Sun (1990). Let A, I mxx be the came-dimensional matrix with singular value
(1 2 (2(A) (A).
(1 2 (2( 2 (B).
Then for any unitarily invariant norm ||
diag(a, (A) a. (BB) s I|A - Bl.
40

---

Lemma 12 (Unbiased empirical transition probability). The empirical transition probability es- timator P(s'(s,a) Nis,a.82) is unbiased, that [ a)] p(s'|s,)) a), where (s,,,ss) N(s.a)
Σn 1[; = =, - a, 8:41 = s'} and ((, - " 1s; - a,
a}. aa.
Proof.
Given (s, a), (s, 5') is binomial variable such that N(s,, a. (s. a) Binomial (N(s.),))
Thus, the expectation of this binomial variable is
N(s, a, s') a(s,a)
((s.aa = P(s
E
By applying the law of total expectation, we have
a(s,
[(s,,,,5) a(s,a)
N(s,a) = p))
= E E
(s)
41

---

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: We explicitly introduce our contributions in both the abstract and introduction. The introduction raises existing unexplored questions that we aim to address in this work.
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 are 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 the Section 7
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]
42

---

We provide complete proof for each theoretical result, and the assumptions and detailed proof are provided in the Appendix.
Justification:
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 the statement of any theorems.
The proofs 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 short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be 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 it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We provide a detailed description experimental details the simulation section and explain the results to substantiate our claims.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to 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 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 a specific model and empirical evaluation, it may be necessary either make it 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 appropriate to the research performed.
While NeurlPS 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) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a 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., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
43

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification: Our work primarily focuses theoretical analysis. Therefore, only conduct simulation study.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nnis.cc
Soblic//guides/Coeeeubbbis
www.sssinoooiiillo for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is 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 NeurlPS code and data submission guidelines (https
/ wwtps/cccppplggggiiieeeeee
Ceaeee/CCoSSuSbissS..S.. wsw.ssooiccgyyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. 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 as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is 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: [Yes]
Justification: We provide detailed simulation settings the main text, including the structure of confounded POMDPs, the behavior policy used to collect data, and the two target policies to be evaluated.
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, 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:
[Yes]
Justification:
Our simulation studies justify our theoretical results.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
44

---

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, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
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 errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπτог 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 text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: All simulations were performed on an Intel(R) (eon(R) Gold 6240 CPU @ 2.60GHz.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs 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 or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer:
[Yes]
Justification:
We conform with the NeurIPS Code of Ethics in every respect.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS 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).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: We discuss the potential of confounded POMDPs to accurately model real- world decision-making tasks, such precise medical applications.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
45

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that 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 generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
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:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no 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 to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
46

---

If assets are released, the license, copyright information, and terms of use in the thcode. has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssi
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.
If this information 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: [Yes]
Justification:
We will release our code if this manuscript is acceptable.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent 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. Crowdsoureing 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:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information 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 to the NeurIPS Code of Ethics, 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 equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending 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.
47

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS 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.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: This research does not involve LLMs any important, original, or non- standard components
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM for what should or should not be described.
48


Reviews:
[{"review_id": "tESgMHR42m", "reviewer": "Reviewer_4S6u", "summary": "This paper investigates the problem of OPE in finite-horizon, tabular POMDPs with unmeasured confounding, focusing on the explicit statistical dependencies on trajectory length and the sizes of the observation and action spaces. The authors address the challenging scenario where the behavior policy depends on unobserved states. The core contribution is a two-step, model-based estimator for policy value, which relies on observable histories as proxies for hidden states and uses invertibility conditions on conditional probability matrices for identification. The paper systematically analyzes the finite-sample error bounds of this estimator, showing that for fully history-dependent policies, the error scales exponentially with the horizon and observation/action space, while for memoryless policies, the bound improves and matches the best-known result for tabular MDPs. Furthermore, under bounded concentrability conditions, the dependence on the horizon can be improved. Simulation studies confirm that empirical trends align with the theoretical analysis.", "questions": "1. How reasonable are Assumptions 1 (invertibility) and 2 (coverage) in practical offline RL datasets? Can the authors propose computationally feasible diagnostics or practical criteria for practitioners to check these conditions before applying the method?\n2. How sensitive is the estimator to violations of invertibility or coverage? Could the authors numerically or empirically investigate near-rank-deficient matrices or scarce data for certain histories to characterize when estimation breaks down?\n3. Can the authors provide empirical comparisons with alternative OPE methods in the tabular regime? How do the variance and robustness properties compare in practice?\n4. How do the proposed error bounds and empirical results compare to those from spectral methods or recent future-dependent estimators for confounded POMDPs?\n5. How does the computational cost of the two-step estimator scale with horizon and observation/action space sizes?\n6. Does the analysis accommodate time-varying or nonstationary behavior policies, or policies depending on longer histories? What is the rationale for the data assumptions made (e.g., as in line 121 differing from prior works), and how does this choice affect practical applicability?\n7. The simulation experiments lack sensitivity analysis with respect to key parameters, such as $\\epsilon$.\n8. In Figure 2(b), performance shows a sharp drop at $n=1000, T=4$. Is this due to randomness from a single trial, or does it indicate a more systematic issue?", "limitations": "Not sufficient.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**: The paper makes a significant theoretical advancement by providing the first explicit finite-sample error bounds for OPE in confounded POMDPs, clarifying how sample size, horizon length, observation/action space cardinalities, and policy type jointly influence statistical difficulty. The results directly address three open questions regarding horizon dependence, the effect of history-based policies, and the role of concentrability coefficients. For memoryless policies, the bounds match the sharpest known results from tabular MDPs, effectively bridging the gap between POMDP and MDP settings even in the presence of confounding. The analysis transparently distinguishes between history-dependent and memoryless policies, making clear when exponential versus polynomial sample complexity arises. The technical development is mathematically transparent, with well-stated assumptions and constructive derivations, and simulation results empirically confirm the predicted scaling relationships between estimation error, horizon, and sample size.\n\n**Weaknesses**\n1. The main results hinge on invertibility and full-rank conditions of certain conditional probability matrices, as well as sufficient coverage/visitation, which may be difficult to satisfy or verify in practice, especially in high-dimensional, sparse, or continuous settings. \n2. For history-dependent policies, the sample complexity and estimator scale exponentially with the horizon and observation/action space sizes, making the method impractical for long horizons or large tabular problems. The computational burden of estimating and inverting large matrices may be significant even for $T$.\n3. Experiments are restricted to a single, simple synthetic setup. There are no tests of robustness to key assumption violations (e.g., low rank, reduced coverage, mis-specified proxies), and no empirical evaluation on more realistic, high-dimensional, or classic POMDP benchmarks.\n4. The empirical results only showcase the proposed estimator; there is no direct comparison to other OPE approaches.\n5. Some technical sections, particularly around estimation and recursion in Section 4.2, use terse or overloaded notation that may hinder accessibility for a broader audience. Definitions and notation for distributions are sometimes implicit or scattered.\n6. Important details for replication (e.g., code, random seeds, parameter sweeps) are missing.", "was_revised": true, "final_justification": "This work combines algorithms, theory, and simulation, and I believe it has the potential to be accepted.", "rebuttal": "We appreciate the reviewer for their valuable comments! Below, we respond to the weaknesses and questions.\n\n**1. Clarification of assumption:**\n\nThe invertibility and coverage conditions are standard and widely used in POMDP literature [1, 2, 3]. \n\n- **invertibility:** The invertibility condition is essential for identifying policy value in tabular OPE  for POMDPs [1]. Checking the invertibility of $\\mathbb{P}(O_t | a_t, S_t)$ is straightforward when both $S_t$ and $O_t$ are binary. In this case, invertibility is ensured if $\\mathbb{P}(O_t = 1 | a_t, S_t = 0) \\neq \\mathbb{P}(O_t = 1 | a_t, S_t = 1)$ for all $a_t$. For larger $S_t$ and $O_t$, if $|\\mathcal{O}|>|\\mathcal{S}|$, the conditional probability matrix $\\mathbb{P}(O_t | a_t, S_t)$ is more likely to satisfy full row rank,  as it is rare to encounter linearly dependent columns in real-world tasks.  This scenario is reasonable and common in practice. For instance, in an autonomous vehicle scenario, the true state may include position and velocity, while the observation could come from multiple sensors, such as camera images,  GPS data, accelerometer readings, and LIDAR scans. Additionally, $\\mathbb{P}(O_t|a_t, O_0,H_{t-1})$  is more likely to have full row rank, as $|\\mathcal{O}||\\mathcal{H}_{t-1}|\\gg|\\mathcal{O}|$  over time. This shows the advantage of using the full history as a proxy for the hidden state. \n\n- **coverage:**  The coverage condition is a standard assumption for RL theory. We adopt a **more relaxed condition** that imposes a bounded second moment condition on the cumulative importance ratio in Assumption 2, compared to directly bounding the importance weight used in literature [1,4].\n\n- **violations of assumption**:  The key to avoiding violations of invertibility lies in estimating the empirical probability matrix. Two main factors influence this estimation:  sample size $n$ and Horizon $T$. A longer horizon introduces more action-observation-history combinations that increase zero entries, while a larger sample size helps reduce these zero entries.  In the tabular setting, it is feasible to check the invertibility condition using singular value decomposition (SVD). If the smallest eigenvalue of $\\widehat{\\mathbf{P}}_{a_t}$ is close to 0 (or the condition number is very large),  the matrix is nearly singular and almost non-invertible, which can be checked using `np.linalg.svd()` in NumPy. The coverage requires a bounded second moment condition on the importance ratio, and a sufficient condition to ensure this is to check the behavior policy $\\pi^b(a_t | s_t) > 0$ for all $a_t$ and $s_t$.\n- **check violation:** Due to time constraints, we do not conduct a comprehensive experiment to illustrate these points, but we outline an experimental plan to examine invertibility. By fixing the sample size $n$ and varying the horizon $T$, we will compute the smallest eigenvalue of $\\widehat{\\mathbf{P}}_{a_t}$ to observe when invertibility is violated, or fix $T$ and vary $n$.  However, the numerical stability (`np.linalg.pinv()`) may degrade with matrices having large or small singular values, and computing the pseudoinverse for large matrices can be expensive. Future work will explore using low-rank approximations to improve computational efficiency.\n- **computational cost scales with $T,|\\mathcal{O}|,|\\mathcal{A}|$:** The computational cost increases with  $T,|\\mathcal{O}|,|\\mathcal{A}|$.  As mentioned previously, computing the pseudoinverse using `np.linalg.pinv()` can be computationally expensive with large matrices. For empirical matrix $\\widehat{\\mathbf{P}}_ {a_t}$, which has dimension $|\\mathcal{O}||\\mathcal{H}_ {t-1}|\\times|\\mathcal{O}|$, the size of $\\widehat{\\mathbf{P}}_{a_t}$ increases as the horizon and the observation space size grow, thereby escalating the computational cost.\n\n\n\n**2 Experiments:**\n\n> a single synthetic setup; check assumption violations; consider more complex settings\n\nOur primary focus is on deriving statistical error bounds for tabular confounded POMDPs, so the experiments are designed to validate the theoretical results in a simple synthetic setup. To evaluate the violation of the coverage assumption, we add the experiments to investigate their impact on error performance under the memoryless policy case ($T=6$). We compare 4 different data generation strategies, where the ratio indicates the proportion of data collected from a random policy. The results show that the error increases as the distribution shift grows, which validates the error bounds.\n\n|        | without mixture policy | mixture(0.2) | mixture (0.5) | mixture(0.6) |\n| ------ | ---------------------- | ------------ | ------------- | ------------ |\n| n=500  | 1.65                   | 2.59         | 3.62          | 4.31         |\n| n=1000 | 1.45                   | 2.05         | 2.93          | 3.65         |\n| n=2000 | 1.21                   | 1.94         | 3.16          | 3.37         |\n\nTo extend the evaluation to high-dimensional and more complex settings, function approximation is necessary (such as neural networks, kernel methods). However, since our theoretical results are specifically derived in tabular settings, this is beyond the scope of our main focus, and we leave it as future work.\n\n> empirical comparisons with alternative methods.\n\nAppreciate the suggestion. Since the simulation studies are primarily focused on verifying the proposed error bound and there is no publicly available code for other confounded POMDP methods, we did not include the comparison. But we will include other tabular OPE methods in the future.\n\n> lack sensitivity analysis for key parameters, such as $\\epsilon$.\n\n Thanks for this nice suggestion. We compare 3 settings with $\\epsilon=0,0.4, 0.8$ for memoryless case. When $\\epsilon=0$, $P_t(O_t|S_t)=\\mathbb{1}\\\\{O_t=S_t\\\\}$, meaning no confounding exists, and larger $\\epsilon$ indicates more noise within the emission probability. The results show that error increases as $\\epsilon$ grows, which further illustrates that the less information the observation contains about the latent state, the more challenging learning confounded POMDPs become.\n\n|               | $\\epsilon=0$ | $\\epsilon=0.4 $ | $\\epsilon= 0.8$ |\n| ------------- | ------------ | --------------- | --------------- |\n| $n=1000, T=6$ | 1.41         | 3.41            | 4.60            |\n| $n=2000, T=6$ | 1.38         | 3.36            | 4.59            |\n| $n=1000, T=8$ | 1.73         | 4.34            | 5.01            |\n| $n=2000, T=8$ | 1.69         | 4.16            | 4.88            |\n\n> the sharp drop in Fig 2(b).\n\nThis drop is due to the unreliable pseudoinverse solution of empirical matrices in certain repeated runs,  caused by the relatively small sample size leading to sparse empirical matrices. In future work, we may consider better methods to address these practical challenges.\n\n\n\n**3. Other questions:**\n\n> Does the analysis accommodate time-varying behavior policies,...?\n\nIn our analysis, the behavior policy, defined as $\\pi^{b}_t:\\mathcal{S}\\to\\Delta(\\mathcal{A})$, is time-varying, and we consider both fully history-dependent and memoryless policy. Unlike previous work where the behavior policy depends only on the one-step observation, i.e., $\\pi^{b}_t:\\mathcal{O}\\to\\Delta(\\mathcal{A})$, our setting is more challenging due to unobserved states acting as unmeasured confounders,  affecting actions, rewards, and transitions simultaneously. This is more aligned with real-world scenarios, as in autonomous driving,  where the behavior policy of the vehicle’s control may depend on the unobserved driver’s mental state, with observed variables (e.g., position, speed, traffic conditions) used for OPE.\n\n> compare to other methods\n\n- **compared to spectral methods [4]:**  The key difference is that the paper [4] aims to relax the invertibility condition using spectral method, and establish the identification results for confounded POMDPs. However, their work does not provide finite-sample error bounds. In contrast, our focus is on establishing the finite-sample error bounds of a model-based OPE estimator for confounded POMDPs, and we provide the first explicit statistical dependencies on horizon and the sizes of the observation and action spaces. \n\n- **compared to future-dependent methods [2,3]:** Recent work [2, 3] use the future proxy to infer the hidden state,  implicitly assuming that the future proxy contains sufficient information about hidden states. However, they focus on **unconfounded POMDPs**, which restricts the behavior policy to be memoryless and dependent only on the current observation. In contrast, our work focus on more complex and realistic confounded POMDPs, where the behavior policy depends on the latent state. Our error bounds, scale as  $\\mathcal{O}(\\frac{T}{\\sqrt{n}})$, are sharper than  $\\mathcal{O}(\\frac{T^2}{\\sqrt{n}})$ in [2,3] in terms of horizon $T$, omitting dependencies on the sizes of the observation and action spaces, as work [2, 3] focuses on general function approximation.\n\n> Important details for replication are missing\n\nAll simulations are performed using a single NVIDIA GeForce RTX 3090 GPU, and each data point in the figure is average of the results from 5 random seeds. Due to the prohibition on using any links this year, we will release the code if this manuscript is accepted.\n\n> overloaded notation used in Section 4.2\n\nWe will remove the overloaded notations $\\mathbf{B}^{\\pi}$ and $\\mathbf{C}_{r,o}$ and clarify the hidden symbols to improve readability.\n\nRef:\n\n[1] Off-policy evaluation in partially observable environments. AAAI.\n\n[2] Future-dependent value-based off-policy evaluation in pomdps. NIPS\n\n[3] On the curses of future and history in future-dependent value functions for off-policy evaluation. NIPS.\n\n[4] A spectral approach to off-policy evaluation for pomdps. ICML.\n\n[5] A minimax learning approach to off-policy evaluation in confounded partially observable markov decision processes. ICML."}, {"review_id": "oMakpzxhUU", "reviewer": "Reviewer_mBzT", "summary": "This paper studies off-policy evaluation (OPE) in tabular Partially Observable Markov Decision Processes (POMDPs) with unobserved confounding. The main result is finite-sample statistical error bounds of a model-based OPE estimator. For history-dependent target policies, the error scales exponentially with the horizon $T$, while for memoryless target policies, the error bound improves to polynomial horizon dependency. Under further conditions on the concentrability coefficients, the rates are improved, especially for the memoryless target policy case the rate matches the optimal rate for OPE in tabular MDPs.", "questions": "1. In Line 153, why is it a *sufficient* condition that $|\\mathcal{O}|>|\\mathcal{S}|$ to ensure the rank condition (Assumption 1)? It seems that it is only a necessary condition.\n2. The statement of Theorem 1 is confusing. Are the random variables (in capital letters) taken expectation? What's their relationship with the realizations (in lowercase)?", "limitations": "Please see the Questions part.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths:**\n1. This paper is the first to study the explicit dependencies of tabular confounded POMDP OPE error bounds on the key variables including horizon $T$ and observation-action space sizes $|\\mathcal{O}|$ and $|\\mathcal{A}|$.\n2. The improved error bounds under further concentrability conditions using variance decomposition are interesting.\n\n**Weaknesses:**\n1. The lower bound of this exact problem (OPE in tabular confounded POMDP) is not provided.\n2. From the reviewer's perspective, the motivation of showing the exponential dependency on the time horizon $T$ is not convincing. On the one hand, it is conceivable that the exponential dependency does exist. On the other, real world problems of practical interests may exhibit certain structures that allow reasonable efficiency to learn a good policy, without falling into such a worst-case paradigm. \n3. The techniques to obtain the identification result and the error bounds are relatively standard given existing literature on (i) OPE in confounded POMDPs; (ii) OPE in tabular MDPs.\n4. Some unclear statements, please see the Questions part.", "was_revised": true, "final_justification": "The author’s response partially resolved my concerns, including clarity issues and the exponential dependency on the horizon parameter. However, I am still concerned with the technical significance of the paper, as well as the lacking of the fundamental limit of the problem, i.e., the lower bounds. Given that the paper stands as an initial step towards studying the explicit dependencies of the sample complexity on all problem parameters for tabular confounded POMDPs, I appreciate the main contributions of the paper. Overall, I am willing to raise my score to 4.", "rebuttal": "We thank the reviewer for their valuable comments and will improve the quality accordingly! Below we respond to the weaknesses and questions.\n\n\n\n **1. Lower bound is not provided.**\n\nThe error bound scale as $\\mathcal{O}(\\frac{T}{\\sqrt{n}})$ in Theorem 3, omitting the dependencies on the size of observation and action spaces, which matches the lower bound for tabular MDPs [1].  While no existing work has established the minimax lower bound for confounded POMDPs, due to the added complexity introduced by confounders, the lower bound for confounded POMDPs should at least be $\\mathcal{O}(\\frac{T}{\\sqrt{n}}|\\mathcal{O}|^{\\alpha_1}|\\mathcal{A}|^{\\alpha_2})$, where $\\alpha_1$ and $\\alpha_2$ remain unclear and require more sophisticated methods to determine. We acknowledge that deriving a lower bound in confounded POMDPs is difficult due to the challenges of partial observability, confounders, and complex statistical dependencies. We leave this challenging direction as future work.\n\n\n\n**2. Concerns about the exponential dependency on horizon $T$** \n\nThank you for raising this important question. In general, for POMDPs, an exponential dependence on the horizon in sample complexity is unavoidable without specific information about POMDPs.  However, as you mentioned, real-world problems may exhibit certain structures that allow the algorithm to learn efficiently without the exponential dependency on $T$. **However, achieving this requires additional structural conditions of the POMDPs.** \n\nIn paper [2], under the conditions where the *latent transitions are deterministic* (i.e. $P_t(\\cdot|S_t,A_t)$ is a Dirac) and the existence of a gap in optimal action values, the algorithm shows that the algorithm achieves polynomial rather than exponential growth in $T$;  Paper [3] assumes the *latent low-rank transition* where the transition dynamics of the hidden state space have a low-dimensional structure,  and consider *M-step decodable POMDPs* [4] assuming the existence of a decoder that can perfectly decode the latent state by looking at the latest $M$-memory. The approach allows learning a representation of latent states that captures only the most relevant features based on the history, showing that the sample complexity can avoid exponential dependence on $T$, reducing to $(|\\mathcal{O}||\\mathcal{A}|)^{M}$ , where $M$ is a fixed length that can be determined theoretically.\n\nIn summary, these works show that, under additional assumptions about the structure of the POMDPs (e.g., low-rank transitions or deterministic latent dynamics), polynomial scaling on $T$ is achievable.  We believe our work can naturally incorporate these structures and derive the corresponding bounds. However, given the already lack of a comprehensive finite-sample analysis of confounded POMDPs, our focus has primarily been on deriving a fine-grained error bound. In future work, we will explore incorporating these structural conditions to extend the current results.\n\n\n\n**3. The techniques to obtain the identification result and the error bounds are relatively standard** \n\nWe would like to clarify that this paper is the first to systematically analyze the finite-sample error bounds in confounded POMDPs.\n\n Specifically, we use two main techniques to derive fine-grained error bounds in the context of confounded POMDPs. First, we are the first to explicitly account for dependencies on the horizon  $T$ , sample size $n$, the sizes of the observation space $|\\mathcal{O}|$,  and the sizes of action spaces $|\\mathcal{A}|$.  The key technique is the error decomposition shown in Section C.1, where we carefully separate the policy value error into a first-order term and other higher-order terms.  Second, under bounded concentrability conditions, the dependence in the memoryless case can be improved to $\\mathcal{O}(\\frac{T}{\\sqrt{n}}\\sqrt{|\\mathcal{O}||\\mathcal{A}|})$, which matches the optimal rate for OPE in MDPs. **This improvement is achieved through Lemma 1, which first establishes a novel variance decomposition specific to confounded POMDPs.**\n\n\n\n**4. Condition $|\\mathcal{O}|>|\\mathcal{S}|$ in Assumption 1**\n\n We apologize for the problematic expression.  $|\\mathcal{O}|\\ge|\\mathcal{S}|$ is the necessary condition. Assumption 1 implies that the observation contains sufficient information about the state.\n\n\n\n**5. Some confusing notations in Theorem 1**\n\nThe random variables in capital letters do not take expectation, since the notation $\\mathbb{P}(X)$ represents a $n$-length vector with $\\mathbb{P}_ {i}(X):=p(X=x_i)$ and $\\mathbb{P}(X | Y)$ denotes a $n \\times m$ matrix with $\\mathbb{P}_ {i, j}(X | Y):=p(X=x_j | Y=y_i)$. The lowercase letters denote realizations of a random variable, such as $X = x_i$. For clarity,  we will write $\\mathbb{P}(O_{t+1}, O_t = o_t \\mid A_t = a_t, O_0,H_{t-1})$ consistently, rather than $\\mathbb{P}(O_{i+1}, o_i \\mid a_i, O_0,H_{i-1})$ for simplicity.\n\n\n\n\n\n**ref:**\n\n[1] Doubly Robust Off-policy Value Evaluation for Reinforcement Learning. ICML, 2016.\n\n[2] Computationally Efficient PAC RL in POMDPs with Latent Determinism and Conditional Embeddings. ICML, 2023.\n\n[3] Provably Efficient Reinforcement Learning in Partially Observable Dynamical Systems. NIPS, 2022\n\n[4] Provable reinforcement learning with a short-term memory. ICML, 2022."}, {"review_id": "8gLLmFOdIX", "reviewer": "Reviewer_6MWe", "summary": "This paper studies the off-policy evaluation for confounded POMDPs, which is argulably the most complicated dynamic decision-making paradigm. It designs an estimator that is based on a proxy value function, which satisfies a Bellman-type recursive equation. It also provides the finite-sample bound for the value function of the behavioral policy.", "questions": "- The paper explores two extremes of behavioral policies: memoryless policies that only depend on the observation; and confounded policies that can depend on the whole history. Usually there may be something in the middle. For example, in the Bayesian formulation of POMDP, one can formulate a belief state of the hidden state and then use the belief state to devide an MDP-like policy. For such policies, it can be seen that the history is first transformed to a low-dimensional representation (alhtough unobserved) and then the action depends on this reprentation. I believe the unobserved state $S_t$ can be used to model this. But because $S_t$ is not observed, it is not used in the estimator. My question is, if we know a functional form of $S_t$ (such as Bayesian updating), with some unknown parameters, is it possible to design more efficient estimators?", "limitations": "NA", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength:\n- The paper is very clearly written. Although the topic is highly technical and the notation is heavy, I find it easy to navigate through the contents. The results are also explained well without getting into the technical details. \n- The comparison to the literature, including the assumptions and the estimators, is thorough.\n\nI don't find any major weaknesses of the work.", "was_revised": true, "final_justification": "My score remains.", "rebuttal": "We appreciate the reviewer for their thoughtful comments and will improve the quality accordingly!\n\nIn our approach, the latent state $S_t$ is unobservable, so we do not directly include it in the estimator. However, when we have access to a functional form of $S_t$,  e.g. $S_t = f(O_{t-1},A_{t-1},\\dots,)$, this can be viewed as a belief state. The form represents the history of observations and actions, allowing us to use a low-dimensional representation to substitute the latent state to model the system's dynamics. In this case, the problem reduces to an MDP-like setting, where the complexity no longer grows exponentially with the horizon.\n\n In essence, we can leverage additional structural conditions of the POMDPs to improve the efficiency of the estimator.  Recent work [1] assumes **latent low-rank transitions** where the transition dynamics of the hidden state space have a low-dimensional structure, and assumes *M-step decodable POMDPs* [2] where there is a decoder that can perfectly decode the latent state using the latest M-step memory. The approach first learn a predictive state representation of latent states that captures only the most relevant features based on the history, and then use this representation to learn a $M$-length memory-based policy. They demonstrate that the sample complexity can avoid exponential dependence on $T$ with respect to the sizes of the observation and action spaces, reducing to $(|\\mathcal{O}||\\mathcal{A}|)^{M}$ , where $M$ is a fixed length that can be determined theoretically. We believe our work can naturally incorporate these structures and derive the corresponding bounds. So in future work, we will explore incorporating additional structural conditions into our confounded POMDPs. \n\n\n\n\n\n**Ref:**\n\n[1] Provably Efficient Reinforcement Learning in Partially Observable Dynamical Systems. NIPS, 2022\n\n[2] Provable reinforcement learning with a short-term memory. ICML, 2022."}, {"review_id": "izYZIjE0Ua", "reviewer": "Reviewer_o3rs", "summary": "The paper addresses off‐policy evaluation in finite‐horizon tabular POMDPs with unobserved states by using invertibility assumptions to treat observable histories as proxies. They propose a two‐step estimator—learning conditional probabilities from data and solving a Bellman‐like recursion over proxy value functions—and derive finite‐sample error bounds showing an $O(T^{1.5}/\\sqrt{n})$ rate (improving to $O(T/\\sqrt{n})$ under a concentrability condition).", "questions": "- I would suggest the authors to provide a more detiailed comparison with previous work in terms of assumptions and complexity, e.g., [1][2]. The current is not clear how th newly proposed method improves the previous results, and whether these better results come from algorithm improvement or benefits from stronger assumption, i.e., full-rank of $P,\\hat P$, history-dependent full coverage.\n- The claim ``sufficent large $n$\" in Theorem 2  is not rigorous, what's the required scale?\n- Since avoiding exponential dependence on the horizon is a crucial challenge in POMDPs—and prior work has sought the right complexity measures—can the proposed method leverage low-rank or lower-noise structure to improve its dependence?\n\n[1] Shi, C., Uehara, M., Huang, J., & Jiang, N. (2022, June). A minimax learning approach to off-policy evaluation in confounded partially observable markov decision processes. In International Conference on Machine Learning (pp. 20057-20094). PMLR.\n\n[2] Uehara, M., Kiyohara, H., Bennett, A., Chernozhukov, V., Jiang, N., Kallus, N., ... & Sun, W. (2023). Future-dependent value-based off-policy evaluation in pomdps. Advances in neural information processing systems, 36, 15991-16008.\n\n[3] Zhang, Y., & Jiang, N. (2024). On the curses of future and history in future-dependent value functions for off-policy evaluation. arXiv preprint arXiv:2402.14703.", "limitations": "- Minor: The expression in Theorem 1 is confusing because it mixes uppercase and lowercase characters. It would be clearer to write \\$O\\_i = o\\_i\\$ consistently rather than using \\$O\\_i\\$ directly.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "- This proposed a new mothod for OPE in the context of confounded POMDP for tabular case, which is novel.\n- The method is clearly motivated and well-presented, and the avoidance of minimax learning approach makes it more computationally efficient\n- The exponential dependence $(|O||A|)^{T/2}$ can be high since this paper considers the ``worst\" case where the underlying information structure is full-rank such that the estimation can not benefit from any low-rank architecture.\n- The method closely parallels standard OPE in tabular MDPs by treating the entire history as an aggregated state for value estimation and using empirical distributions for that estimation.", "was_revised": true, "final_justification": "Author's response have solved my main concerns, and thus I increase my score accordingly.", "rebuttal": "We thank the reviewer for the suggestive feedback. Our one-to-one response to the reviewer’s questions and concerns is given below.\n\n\n\n> Suggest the authors provide a more detailed comparison with previous work in terms of assumptions and complexity, e.g., [1, 2]. ...  whether these better results come from algorithm improvement or benefits from stronger assumptions.\n\nWe appreciate the suggestion to provide a more detailed comparison with previous work. We would like to first clarify the differences in the settings compared to the relevant literature. Paper [1] considers a confounded POMDP setting similar to ours, while papers [2] and [3] focus on unconfounded POMDPs, where the behavior policy depends on the one-step observation. All three relevant papers [1,2,3] consider general function approximation, while we focus on the tabular setting. \n\n- **Assumptions:**  The comparison is primarily centered around the coverage assumption. [2] assumes the bounded importance sampling weight of  $\\frac{\\pi(A_t|O_t)}{\\pi^b(A_t|O_t)}\\leq \\infty$, which is a standard assumption in the OPE literature. [3]  introduces a novel coverage assumption, belief coverage, which is tailored to the structure of POMDPs. This coverage assumption ensures that the data collected under the behavior policy provides sufficient information about the belief states encountered under the evaluation policy, ultimately enabling polynomial bounds on the horizon. [1] assumes the existence of weight bridge functions $b_W:\\mathcal{O}\\times\\mathcal{A}\\to\\mathbb{R}$, which is similar to the weight function we define in Assumption 3. However, we do not require the estimation of the weight function.\n- **Complexity:**  Omitting the terms related to the size of the observation space, action space, and function class, the error bound in [3] and our work scale with $\\mathcal{O}(\\frac{T}{\\sqrt{n}})$, while the results in [2] scale with  $\\mathcal{O}(\\frac{T^2}{\\sqrt{n}})$ and [1] focuses on the discounted setting and there is no finite-sample results for finite-horizon in [1]. However, [3] focuses on the unconfounded POMDP setting, which is easier than ours.\n\n- **Source of improvement:**  The improved results stem from a fine-grained finite-sample analysis in the context of confounded POMDPs. First, we are the first to explicitly account for dependencies on the horizon $T$ , sample size $n$, the sizes of the observation space $|\\mathcal{O}|$,  and the sizes of action spaces $|\\mathcal{A}|$.  We carefully separate the policy value error into first-order term and higher-order terms.  Second, under bounded concentrability conditions (i.e. the weight function in assumption 3 is bounded), the dependence in Theorem 3  can be improved to $\\mathcal{O}(\\frac{T}{\\sqrt{n}}\\sqrt{|\\mathcal{O}||\\mathcal{A}|})$ for the memoryless case, which matches the optimal rate for OPE in MDPs. **This improvement is achieved through Lemma 1, which first establishes a novel variance decomposition specific to confounded POMDPs.**\n\n\n\n> The claim \"sufficiently large $n$\" in Theorem 2 is not rigorous\n\nWe apologize for this confusion and will remove this claim from Theorem 2. We have assumed a sufficiently large $n$ in Assumption 2(c), where we require a sufficient number of samples for each triple $(o_0,h_{t−1},a_t)$, ensuring consistent estimation of the conditional probability matrices.  Specifically, we require $n_{o_0,h_{t-1},a_t}\\ge n p_t^{\\pi^b}\\left(o_0, h_{t-1},a_t\\right)(1-\\theta_{t,ij})$, where $n_{o_0,h_{t−1},a_t}$ represents the count of the triple $(o_0, h_{t-1}, a_t)$ in the data, and $p_t^{\\pi^b}(o_0, h_{t-1},a_t)$ is the probability density under the behavior policy $\\pi^b$. Define the event $E :=\\\\{\\exists ~t,o_0, h_{t-1},a_t ~ \\text{s.t.} n_{o_0,h_{t-1},a_t}\\ge n p_t^{\\pi^b}\\left(o_0, h_{t-1},a_t\\right)(1-\\theta_{t,ij})\\\\}$. Then, combining the multiplicative Chernoff bound and a union bound over each $t, o_0, h_{t-1}$, and $a_t$, we have\n$$\n\\mathbb{P}[E^c] \\leq \\sum_t \\sum_{o_0}\\sum_{h_{t-1}} \\sum_{a_t} \\mathbb{P}\\left[n_{o_0,h_{t-1},a_t}<n p_t^{\\pi^b}\\left(o_0, h_{t-1},a_t\\right)(1-\\theta_{t,ij})\\right] \\\\\n\\leq T |\\mathcal{O}|^T  |\\mathcal{A}|^T e^{-\\frac{{\\theta^*}^2 n \\min_{t, o_0,h_{t-1},a_t} p_t^{\\pi^b}(o_0, h_{t-1},a_t)}{2}}.\n$$\nTo ensure the number of samples is sufficiently large, the $\\mathbb{P}[E^c]$ should be sufficiently small. This requires $n \\geq \\frac{\\operatorname{polylog}(|\\mathcal{O}|^T, |\\mathcal{A}|^T, T)}{\\min_{t, o_0,h_{t-1},a_t} p_t^{\\pi^b}(o_0, h_{t-1},a_t)}$.\n\n> Since avoiding exponential dependence on the horizon is a crucial challenge in POMDPs—and prior work has sought the right complexity measures—can the proposed method leverage low-rank or lower-noise structure to improve its dependence?\n\n\n\nThank you for raising this important point.  We completely agree that avoiding exponential dependence on the horizon is a critical challenge in POMDPs. Our proposed method could indeed benefit from leveraging low-rank structures, as motivated by recent efforts.  \n\nRecent work [4] assumes **latent low-rank transitions**, where the transition dynamics of the hidden state space have a low-dimensional structure. Additionally, they consider *M-step decodable POMDPs* [5], where an unknown decoder can perfectly decode the latent state from the latest $M$-step memory. The approach first learn a representation of latent states that captures only the most relevant features based on the history, and then uses the representation to learn an $M$-length memory-based policy. They demonstrate that the sample complexity can avoid exponential dependence on $T$ with respect to the sizes of the observation and action spaces, reducing to $(|\\mathcal{O}||\\mathcal{A}|)^{M}$, where $M$ is a fixed length that can be determined theoretically.  The paper [6] also assumes the latent low-rank transition and structure of M-step decodable POMDPs, enabling a more computationally efficient algorithm and avoiding the exponential dependence on horizon. \n\n**Incorporating these assumptions into our tabular confounded POMDP setting could potentially improve the current results**. For example, we could approximate the belief state with a lower-dimensional representation that captures the most important information. In a tabular setting, the belief state can be formulated as a matrix, where each entry is a probability over hidden states based on the history of observations and actions, such as $\\mathbb{P}(S_t=s|O_o=o,H_{t-1}=h_{t-1},A_{t}=a)$. We can approximate the matrix using low-rank approximations such as SVD and PCA to reduce dimensionality, which can help keep the matrix size manageable, even for long horizons.\n\nWe believe our work can naturally incorporate these structures and derive the corresponding bounds. However, given the lack of a comprehensive finite-sample analysis of confounded POMDPs, our focus has primarily been on deriving a fine-grained error bound. In future work, we will explore incorporating additional structural conditions to extend the current results.\n\n\n\n>notations in Theorem 1\n\nThanks for this suggestion. The notation $\\mathbb{P}(X)$ represents a $n$-length vector with $\\mathbb{P}_ {i}(X):=p(X=x_i)$ and $\\mathbb{P}(X | Y)$ denotes a $n \\times m$ matrix with $\\mathbb{P}_ {i, j}(X | Y):=p(X=x_j | Y=y_i)$. The lowercase letters denote realizations of a random variable, such as $X = x_i$. For clarity,  we will write $\\mathbb{P}(O_{t+1}, O_t = o_t \\mid A_t = a_t, O_0,H_{t-1})$ consistently, rather than $\\mathbb{P}(O_{i+1}, o_i \\mid a_i, O_0,H_{i-1})$ for simplicity.\n\n\n\n**Ref:**\n\n[1]  A minimax learning approach to off-policy evaluation in confounded partially observable markov decision processes. ICML, 2022.\n\n[2] Future-dependent value-based off-policy evaluation in pomdps. NIPS, 2022\n\n[3] On the curses of future and history in future-dependent value functions for off-policy evaluation. NIPS, 2024.\n\n[4] Provably Efficient Reinforcement Learning in Partially Observable Dynamical Systems. NIPS, 2022\n\n[5] Provable reinforcement learning with a short-term memory. ICML, 2022."}]

Author rebuttal:

Meta-review: **(a) Summary of Scientific Claims and Findings**

The paper addresses of off-policy evaluation (OPE) in finite-horizon, tabular POMDPs with unmeasured confounding, where the behavior policy may depend on hidden states. The authors propose a two-step model-based estimator that leverages observable histories as proxies for hidden states under invertibility assumptions on conditional probability matrices. They establish finite-sample error bounds that reveal exponential scaling with horizon and observation/action space size for history-dependent policies, and improved (polynomial) bounds for memoryless policies. With additional concentrability assumptions, the horizon dependence is further reduced, achieving rates comparable to tabular MDPs. Synthetic simulations corroborate the theoretical scaling trends.

**(b) Strengths**

- Novelty: Provides the first explicit finite-sample error bounds for OPE in confounded POMDPs.

- Theoretical contribution: Results characterize the statistical difficulty as a function of horizon, policy type, and problem dimensions.

- Bridging gap to MDPs: Shows that for memoryless policies, the bounds match the stricter known MDP results

- Empirical alignment: Simulation experiments, while limited, validate the theoretical findings

**(c) Weaknesses**

- Strong assumptions: Relies on invertibility and full-rank conditions of conditional probability matrices, as well as broad coverage, which may be unrealistic or unverifiable in practical scenarios

- Limited experiments: Evaluation is restricted to simple synthetic settings, lacks robustness checks on violating assumptions, comparative baselines, or tests on more realistic benchmarks.

- No lower bounds are provided, leaving unclear whether the derived upper bounds are tight

**(d) Reasons for Decision**

After the discussion, the paper remains with some weaknesses, especially related to the technical significance since no lower bounds are provided. On the other side, this represents an initial work on this topic. For this reason, along with the soundness of the paper, I am recommending acceptance.

**(e) Rebuttal and Discussion**

The authors' rebuttal and discussion have clarified some issues. Although, as mentioned above, some issues regarding significance remain open.
Decision: Accept (poster)