{'fraction_non_alphanumeric': 0.047816173377902726, 'fraction_numerical': 0.01830739601089146, 'mean_word_length': 4.17279285468911, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 19, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Off-Policy Evaluation in Partially Observed Markov Decision Processes

We consider off-policy evaluation of dynamic treatment rules under the assumption that the underlying system can be modeled as a partially observed Markov decision process (POMDP). We propose an estimator, partial history importance weighting, and show that it can consistently estimate the stationary mean rewards of a target policy given long enough draws from the behavior policy. Furthermore, we establish an upper bound on its error that decays polynomially in the number of observations (i.e., the number of trajectories times their length), with an exponent that depends on the overlap of the target and behavior policies, and on the mixing time of the underlying system. We also establish a polynomial minimax lower bound for off-policy evaluation under the POMDP assumption, and show that its exponent has the same qualitative dependence on overlap and mixing time as obtained in our upper bound. Together, our upper and lower bounds imply that off-policy evaluation in POMDPs is strictly harder than off-policy evaluation in (fully observed) Markov decision processes, but strictly easier than model-free off-policy evaluation.


Introduction
Dynamic, data-driven treatment rules show considerable promise in a number of domains. In the area of mobile health, the increased use of smartphone health apps presents a number of opportunities to develop personalized and adaptive interventions [Nahum-Shani et al., 2018]: Examples involve apps that support patients recovering from alcohol use disorders by sending notifications when the patients are detected to be in situations with a high risk of relapse [Gustafson et al., 2014], and apps that help office workers maintain healthy levels of physical activity during the workday [Van Dantzig et al., 2013, Klasnja et al., 2019. In marketing, there is increased emphasis on taking a unified view of promotional campaigns that considers both long-and short-term effects of a sequence of actions [Ataman et al., 2010]. In education, there is interest in developing AI-based tutoring systems that learn how to design a personalized curriculum for each student [Koedinger et al., 2013].
One central difficulty in evaluating and designing adaptive treatment strategies is that any specific action can have both an immediate effect and also a longer-term (lag) effect on the targeted unit; and furthermore the long-term effects of different actions may interact with each other. Accurate evaluation of the total impact of any candidate intervention requires specifying a statistical model that captures the short-and long-term effects of relevant actions and lets us reason about treatment dynamics. Then, the statistical complexity of working with adaptive treatment strategies depends on the specified model.
The two predominant approaches to linking actions with future observed states and outcomes are to either assume Markov dynamics, or to work in a model-free specification. Under Markov dynamics, we posit that the observed system forms a (stationary) Markov decision process governed by our actions, i.e., that conditional on our present observations, the future behavior of the system is independent of past observations. This Markov assumption imposes considerable structure on the problem, and enables tractable approaches to policy evaluation and learning using simple experimental designs [e.g., Antos et al., 2008, Kallus and Uehara, 2020, Liao et al., 2021, Luckett et al., 2019. However, the assumption that the system is Markovian in terms of the observed state can be hard to justify in a number of application settings, including mobile health. For example, if a person's mood exhibits temporal dependence and affects their response to the intervention, but mood is not explicitly measured by the health app, then the Markov assumption will generally not hold.
In contrast, the model-free approach allows the state of the system at a given time to have an arbitrary dependence on all earlier actions [e.g., Jiang and Li, 2016, Murphy, 2003, Nie et al., 2021, Robins, 1986, 2004, Thomas and Brunskill, 2016, Zhang et al., 2013. This approach is fully flexible, but suffers from a curse of dimensionality: The set of possible action sequences grows exponentially in the number of time periods, and the statistical performance of model-free approaches will reflect this fact as the number of time periods gets large [Guo et al., 2017, Kallus andUehara, 2020].
In this paper, we propose partially observed Markov decision processes (POMDPs) as a promising best-of-both-worlds intermediate solution for modeling treatment dynamics in mobile health and other related applications. This model is considerably more flexible than the basic Markovian specification, because it allows for the existence of quantities (e.g., in our earlier example, mood) that play a key role in a unit's behavior yet remain hidden from the policy maker. At the same time, we find that it retains sufficient structure to avoid the curse of dimensionality in horizon length experienced by model-free methods. POMDPs are widely used in the engineering literature on planning under uncertainty [Kaelbling et al., 1998, Smallwood andSondik, 1973]. However, to the best of our knowledge, this paper is the first to consider POMDPs as a modeling framework enabling more precise off-policy evaluation of dynamic treatment rules under sequential ignorability. We discuss related work further in Section 1.2.

Modeling Treatment Dynamics
Suppose that, for units i = 1, . . . , n and epochs t = 1, . . . , T , we observe a state variable X i,t ∈ X , an outcome Y i,t ∈ R and an action W i,t ∈ {1, . . . , A}. For example, in the study of Klasnja et al. [2019] on smartphone apps that encourage healthy physical behavior, W i,t is a tailored prompt delivered via the app, Y i,t is a measurement of anti-sedentary behavior (e.g., walking), and X i,t measures a number of factors including availability of the subject (e.g., the app cannot send prompts when the subject is detected to be driving or already exercising). We assume that units are sampled i.i.d., but there may be complex temporal dependence for observations collected from the same unit.
A policy π is a (potentially random) mapping from currently observed state X i,t to an . Kallus and Uehara [2020] refer to Models 1 and 2 as models M 1 and M 2 respectively, and compare the difficulty of off-policy evaluation in these settings. In the model-free specification (Model 1), evaluating dynamic treatment rules over a target horizon T requires observing length-T trajectories under the behavior policy; furthermore, the difficulty of offpolicy evaluation over a horizon of length T scales exponentially in T [Guo et al., 2017, Kallus andUehara, 2020]. In contrast, under the Markovian specification (Model 2), we can define the stationary long-term value of a target policy in a way that converges as T gets large, and it is possible to estimate this long-term value with a parametric error rate, i.e., with mean squared error on the order of O(1/(nT )) given n trajectories of length T [Liao et al., 2021]. Thus, the gap between Models 1 and 2 becomes more and more acute as we consider longer trajectories. In a model-free setting, long trajectories simply increase the difficulty of the problem; whereas in the Markov specification, long trajectories give us more information that can be used to improve the precision with which we can estimate the stationary value of our target policy.
The goal of this paper is to map out the promise and challenges of off-policy evaluation under the POMDP model. At a high level, we find that-like in the Markovian Model 2-the POMDP assumption gives rise to stationarity and enables us to use long trajectories for improved precision. However, unlike in Model 2, we find that O(1/ √ nT ) errors are no longer possible. Instead, optimal errors scale as O(1/poly(nT )) with exponents that reflect both the mixing time of the POMDP and the overlap between the behavior and target policies. 2 Throughout this paper, we identify causal effects on a sequential ignorability (or unconfoundedness) assumption [Hernán and Robins, 2020]. Qualitatively, this assumption requires that the realized treatment assignment W i,t cannot depend on the unobserved state variables H i,t . One notable setting where our exogeneity assumption holds is in micro-randomized trials, which are a flexible class of experimental designs used to study adaptive treatment rules [Klasnja et al., 2015]. Such trials are a flexible and increasingly popular approach to experimental design in mobile health; recent examples of micro-randomized studies in this context include Battalio et al. [2021] and Klasnja et al. [2019]. We note that a key flexibility of micro-randomized trials is that, because treatment randomization probabilities can depend on X i,t , they can seamlessly integrate availability constraints. Such availability constraints are ubiquitous in mobile healthcare, e.g., a fitness app should not send notifications while the subject is detected to be driving.
Assumption 1. Under the behavior policy, the treatment W i,t is randomly assigned according to probabilities e(·) that may depend on the observed state X i,t (but nothing else), (1)

Related Work
The problem of off-policy evaluation of dynamic treatment rules goes back to early work from Robins [1986], who considered the problem in the model-free specification (Model 1).
2 The rates of convergence discussed in this paragraph should be seen as bounds for estimating the average in-sample long-term off-policy value for a model with fundamental heterogeneity across units, or alternatively as a bound for population off-policy value in a model without fundamental heterogeneity. When estimating population value in a model with fundamental heterogeneity across units, there is an additional O(1/ √ n) error term arising from random sampling of units; see Remark 1 for a further discussion.
Markov decision processes have long been used as a model for actions taken by an agent (e.g., a robot) [Russell and Norvig, 2010]. More recently, this modeling assumption has also been used to power various estimators for off-policy evaluation of dynamic treatment rules; see, e.g., Antos et al. [2008] and Luckett et al. [2019]. Kallus and Uehara [2020] emphasize that assuming Model 2 considerably improves available performance guarantees for off-policy evaluation, thus showing that working under Model 2 is desirable whenever the assumption is credible. Liao et al. [2021] provide an estimator of the long-term value of a policy under Model 2 with errors that converge as O(1/ √ nT ), and prove a central limit theorem for it. However, there remain many settings-including in mobile health-where it is not realistic to assume that we observe the full relevant state, thus making methods justified by Model 2 inapplicable.
The POMDP assumption is a weaker alternative to assuming Markovian structure, in that POMDPs allow for some relevant state variables to remain unobserved by the agent. Like Markov decision processes, POMDPs were originally introduced as a model for decisions taken by an agent, but in a situation where the agent needs to operate under uncertainty [Russell and Norvig, 2010]. The earliest investigations of POMDPs were focused on optimal control under uncertainty [Monahan, 1982, Smallwood and Sondik, 1973, Sondik, 1978; later, these models were also used for planning-based artificial intelligence [Kaelbling et al., 1998].
There have also been a handful of recent papers that discuss POMDPs in the context of causal inference and off-policy evaluation but, unlike us, they did not study how assuming Model 3 enables more precise evaluation under sequential ignorability relative to the modelfree specification. Mandel et al. [2014] consider POMDPs as a possible data-generative model in the context of off-policy evaluation; however, they do not exploit properties of the model for variance reduction, and instead used standard non-parametric methods (in particular importance sampling) for evaluation. Meanwhile, Bennett and Kallus [2021], Nair and Jiang [2021] and Tennenholtz et al. [2020] study confounding bias in the context of a POMDP model. Their main interest is in settings where the unobserved state H it is a source of unobserved confounding, and then build on the literature on causal identification with proxy variables [e.g., Miao et al., 2018] to correct for this confounding; and doing so requires making strong assumptions on the relationship between the observed and unobserved state variables. In contrast, we work in a setting where there are no confounding problems (Assumption 1) and so standard model-free methods like importance sampling would be unbiased but high variance; we then use (minimally structured) POMDP assumptions to enable improved precision.
We also note work by Thomas and Brunskill [2016] and Su et al. [2020] who consider offpolicy evaluation under sequential ignorability in the non-parametric model via a method that first takes k steps of importance weighting and then uses an outcome regression to estimate remaining rewards. The motivation for doing so is that importance weighting weighting is unbiased but, as discussed above, has a high variance when the evaluation horizon gets large; in contrast, outcome regression is often considered to be more stable but potentially biased. Thomas and Brunskill [2016] argue that combining both approaches to estimation can achieve a more desirable bias-variance trade-off than either method alone. While the modeling setup used in Thomas and Brunskill [2016] and Su et al. [2020] is completely different than ours, the main algorithmic idea-i.e., applying importance weighting only up to a finite horizon chosen by the analyst-is closely related to the partial history importance weighting algorithm we use to derive our upper bounds.
Finally, although in this paper we only consider off-policy evaluation under a POMDP assumption, this problem is closely related to the problem of policy learning from batched data. There is a large literature showing how, in the static case (i.e., with T = 1 and no long-term treatment effects) we can use off-policy evaluation as a means for policy learning [Athey and Wager, 2021, Kitagawa and Tetenov, 2018, Swaminathan and Joachims, 2015, Qian and Murphy, 2011, Zhao et al., 2012. Recently, Nie et al. [2021] extended some of these ideas to a dynamic problem related to optimal stopping under Model 1. Applying our results to the setting of dynamic policy learning from batch data under a POMDP assumption would be a natural direction for future investigations.

Off-Policy Evaluation via Partial History Weighting
It is well known that the state distribution of an irreducible and aperiodic Markov chain converges to a stationary distribution over time, and its rate of convergence to this stationary distribution is captured by its mixing time. One of the main findings of our paper is that the difficulty of off-policy evaluation in POMDPs depends on mixing properties of relevant Markov chains, and the associated mixing times play a central role in our analysis. We formalize the notion of mixing time as follows; see Even-Dar et al. [2005] and [Van Roy, 1998, Chapter 7] for further discussion of this definition.
Assumption 2. Let π be any policy that maps current observed state to action probabilties such that, under Model 3, Let P π i denote the state transition operator on (X i,t , H i,t ) associated with π. We assume that, for all considered policies π, there is a mixing time t π i such that for any pair of distributions f and f on (X i,t , H i,t ).
Our statistical estimand, i.e., the average long-term rewards of a policy, matches the one used in Liao et al. [2021], and we refer the reader to that paper for a longer discussion of (and motivation for) this estimand.
Definition 1. Under Model 3 and given a policy π satisfying Assumption 2, let L π i denote the stationary distribution of (X i,t , H i,t , W i,t , Y i,t ) under π. For simplicity, we restrict the state space X × H to be finite. We define V i (π), the long term reward for unit i under π, as the expectation of Y i,t under L π i . If furthermore the units i = 1, . . . , n are randomly sampled from the same population, we define V (π) = E [V i (π)] as the expected long-term reward of π.
Our proposed method for policy evaluation, partial-history importance weighting, directly exploits mixing properties of our model. The method starts by choosing a historylength k, chunking all available data into (overlapping) segments of length k+1, and applying importance weighting (or inverse-propensity weighting) to these segments: The qualitative insight motivating the method is as follows: If the system under policy π mixes in (on the order of) t π i steps, then once the treatment assignments W i,t of our observed trajectory match those assigned by π for (on the order of) t π i steps, it will yield outcomes that resemble those from the stationary distribution of the policy π.
In order to prove consistency of partial-history importance weighting, we need to further assume overlap of the behavior and target policies, i.e., we need an assumption guaranteeing that the behavior policy cannot systematically take different actions than the target policy.
Assumption 3. Under the setting of Assumption 1 and using notation from (2) to describe action probabilities under policy π, we assume that there is an overlap constant ζ π with π a (x) ≤ exp (ζ π ) e a (x) for all x ∈ X and a = 1, . . . , A.
Given bounds on mixing and overlap as above, the following result establishes a performance guarantee for partial history importance weighting. Merging notations from Assumptions 1 and 2, we write L e i for the stationary distribution of the i-th unit under the behavior policy, and t e i for the associated mixing time. Throughout this paper, all equalities and inequalities pertaining to random variables should be taken to hold almost surely.
Theorem 2.1. Given a target policy π and under Model 3, suppose we have a sequence of problems with units i = 1, . . . , n observed for T (n) time periods. Suppose additionally that the state transition distributions for each unit are all independently and identically sampled from a fixed population, P i ∼ D, that the initial states (X i,1 , H i,1 , W i,1 , Y i,1 ) for each unit are sampled from the corresponding stationary distribution L e i , that Assumptions 1 and 3 hold, and that for all X i,t ∈ X , H i,t ∈ H, W i,t = 1, . . . , A. Finally, suppose that both the target policy π(·) and the behavior policy e(·) satisfy Assumption 2, and that there is a constant t 0 for which t π i , t e i ≤ t 0 almost surely. Then, as n gets large and given any sequence satisfying the partial history importance-weighted estimator V (π; k(n)) from (4) is consistent for the long-term policy value V (π) as given in Definition 1. Furthermore, the mean-squared error of V (π; k(n)) as an estimator for the average long-term in-sample value is bounded as and its mean-squared error as an estimator for V (π) is bounded as where . . . stands in for the right-hand side expression in (8).
The following corollary is immediate, and provides a concrete upper bound for the difficulty of off-policy evaluation of dynamic treatment rules under a POMDP assumption.
Corollary 2.2. There exist a universal constant C 0 , and a constant C 1 (t 0 , ζ π , M 1 , M 2 ) depending on the problem specification such that, under the conditions of Theorem 2.1, the choice yields the error bounds Remark 1. The population mean-squared error bounds (9) and (12) reflect two sources of error: The error from estimating the average long-term off-policy rewards V i (π) for the i = 1, . . . , n units in the study, and the error from generalizing from the n study units to the full population. The former error is captured by (8) and (11) respectively and gets smaller as the horizon length T grows, whereas the latter is simply due to sampling variation in V i (π) and does not depend on the horizon length T (recall that, following Definition 1, the heterogeneity in V i (π) results from fundamental heterogeneity in the state evolution of different units under the same policy). We view the error terms in (8) and (11) as the most relevant in understanding the difficulty of off-policy evaluation in POMDPs, as the excess factor M 2 1 /n in (9) and (12) has nothing to do with dynamics; see (19). The bounds (8) and (11) can also be interpreted as error bounds in a model where there is no essential heterogeneity across units, i.e., P ‡ i (x, h, w) and thus also V i (π) = V (π) are equal across units, in which case it would be possible to learn the population value V (π) from observing a long enough trajectory from a single unit.

Proof of Theorem 2.1
To keep everything concise, we start by studying the behavior of the following component of the proposed estimator for V i (π), the stationary reward for the i-th unit (see Definition 1): with the shorthand Experimental units may behave differently from each other as they may have different state transition operators P i ; for this reason, we will sometimes informally refer to P i as a unit's "type". All proofs of technical lemmas are given in the supplementary material. We start by bounding the bias of V i (π; k) as an estimator for V i (π) conditionally on a unit's type P i by exploiting mixing properties of our model. In a slight abuse of notation, we drop the dependence of k(n) and T (n) on n for notation simplicity.
Lemma 2.3. Under the assumptions in Theorem 2.1, where L e,π k i denotes the joint distribution of (X i,t , H i,t , W i,t , Y i,t ) after k-step transition under P π i when starting from L e i , the stationary distribution of the quadruplet associated with the state transition operator P e i . Furthermore, By exploiting the correlation structure of the underlying process, we can also bound the variance of V i (π; k) with the mixing time of the two policies and the overlap between them.
Lemma 2.4. Under the assumptions stated in Theorem 2.1, Now that we have established the bias and variance of the partial estimator V i (π; k) in estimating V i (π), we can connect them to the task of estimating Under the assumptions stated in Theorem 2.1, Combining the bias and the variance we obtained from Lemma 2.5, we find that the mean-squared error of the estimator V (π; k) can be bounded as claimed in (8). Furthermore, (9) follows from (8) by noting that Furthermore, for any sequence k(n) satisfying (6), the bound in (9) converges to 0, and thus V (π; k(n)) is a consistent estimator of V (π).

Lower Bounds for Policy Evaluation in POMDPs
Above, we found that partial-history importance weighting enables consistent policy evaluation under bounds on the overlap and the mixing time. However, the achieved rate on mean-squared error is slower than the parametric 1/(nT (n)) rate. This raises a natural question: Does this slower-than-parametric rate of convergence reflect the difficulty of the statistical problem, or could we do better using a different algorithm? To elucidate this question, in this section we provide lower bounds for the minimax risk for off-policy evaluation in POMDPs under the same assumptions on mixing and overlap as used above. For simplicity, we here focus on the case where we only observe data from a single trajectory (i.e., we have n = 1 with T → ∞), and seek lower bounds for estimating the longterm reward V i (π) for that trajectory; in other words, we give lower bounds corresponding to the setting of (11) with n = 1. Throughout the rest of this section, we suppress the dependence of all values on i and n to avoid clutter.
Writing I(t 0 , ζ π , M 1 , M 2 ) for the class of all possible instances of POMDPs satisfying the conditions of Theorem 2.1, we seek a lower bound on the worst-case risk among all measurable estimatorsV : Here, the expectation is taken over the data generating distribution of the problem instance I, and V (I) denotes the ground truth of the estimand V under I. When there is no risk of confusion, we use shorthand I := I(t 0 , ζ π , M 1 , M 2 ) below.
Theorem 3.1. Define M 1 , M 2 , t 0 , ζ π as in Theorem 2.1 and fix any T ≥ 1. Let I be the set of problems as described in Section 2 such that following conditions are satisfied: (C1) π a (x)/e a (x) ≤ exp (ζ π ), ∀a = 1, . . . , A, x ∈ X ; (C2) f P π − f P π 1 ≤ 2 exp(−1/t 0 ), ∀f, f ; Then there is a constants C 2 (t 0 , ζ π , M 1 , M 2 ) such that the minimax risk of I(t 0 , ζ π , M 1 , M 2 ) is lower-bounded as The exponent on T in the lower bound (21) for the minimax risk gives us a number of valuable insights into the difficulty of policy evaluation in our POMDP model. First, it establishes that the optimal rate of convergence for off-policy evaluation is in fact subparametric, i.e., we cannot in general get 1/T rates of convergence, whenever t 0 ζ π > 1. Thus, off-policy evaluation in POMDPs is in fact strictly harder than in MDPs, where parametric rates rates would have been available under similar assumptions on mixing and overlap [Liao et al., 2021].
More broadly, Theorem 3.1 highlights the role of the mixing time t 0 and the overlap ζ π (in the form of t 0 ζ π , specifically) as a key measure of the difficulty of the problem. Our upper bound from Corollary 2.2 also depends on these quantities via the product t 0 ζ π ; and furthermore, the exponent in both the upper and lower bounds scales as 2/(t 0 ζ π ) when the mixing time t 0 is large. Thus, although our upper and lower bounds don't match exactly and we have a gap in rates of convergence for "easy" problems (i.e., where t 0 ζ π is small), Corollary 2.2 and Theorem 3.1 together give a sharp characterization of the minimax risk of off-policy evaluation in POMDPs for "hard" problems when t 0 ζ π is large.
One interesting question left open by Theorem 3.1 is whether or not parametric rates for for off-policy evaluation in POMDP are possible when the system mixes extremely fast, i.e., when t 0 ζ π ≤ 1. Shedding light on this question-and also closing the gap between the provided upper and lower bounds-would help deepen our understanding of this problem setting.

Proof of Theorem 3.1
Our proof follows Le Cam's two point method, where we reduce the problem of lowerbounding minimax estimation error to a hypothesis testing problem, and ask the question of how large the sample size needs to be in order for us to distinguish between two specific instances. Since the minimax risk is the worst-case risk of all estimators among the entire class I, R minimax is always lower bounded by the worst-case risk of all estimators among two specific instances I 1 , I 2 ∈ I, i.e., One can then make this lower bound large by identifying two instances that are similar in terms of the empirical distribution characterized by e (so they are hard to tell apart), but different in terms of V (·) characterized by π (so we pay a large price for incorrectly identifying the instance). For simplicity, we consider a setting where there is only a binary treatment with no covariates, i.e., W ∈ {0, 1}, X = ∅, and the probability of being assigned to treatment is the same across all units for every π ∈ Π. In addition, we consider a hidden variable over H, with |H| = Q and states labeled as h 1 , h 2 , . . . , h Q . We consider two instances that share the same underlying transition rule as follow (see Figure 2 for a graphical representation): We further define the target policy π to be always-treat, and the behavior policy to be treat-with-probability-exp (−ζ π ). It is immediate that under π, it is much easier for the chain to get to h Q than under e. We set the data generating distributions of Y (h, w) under I 1 and I 2 as ] is the only difference between I 1 and I 2 . To ease the notation, we drop the dependence on w and denote them as µ 1 (h Q ) and µ 2 (h Q ), respectively. Under this setting, we can calculate the closed-form solution of the stationary distribution d e and d π , where Lemma 3.2. The above two instances, with the choices of 0 ≤ ∆ ≤ M 1 and δ = 1 − exp(−1/t 0 ), satisfy (C1)-(C3) outlined in Theorem 3.1, i.e., I 1 , I 2 ∈ I. As a result, we obtain a family of pairs of instances {I 1 , I 2 }, indexed by Q ∈ Z + and ∆ ∈ [0, M 1 ]. Now that we have constructed a family of hard instances, we can follow the standard minimax framework and reduce it to a hypothesis testing problem asking whether the data is generated from I 1 or I 2 . We first apply Le Cam's lemma [Yu, 1997] where γ KL I1,I2 (Y 1:T , W 1:T ) denotes the KL divergence between the distribution of (Y 1:T , W 1:T ) under I 1 and I 2 , respectively, and n = 1 in the setting we consider. It remains to calculate the KL divergence between the observed data generated from the two instances.
Lemma 3.3. The KL divergence between the observed data generated by I 1 and I 2 is upper bounded as Motivated by the form of (24), we consider the instance with Then, plugging the result from Lemma 3.3 into (23), It now remains to turn this result into a bound on the mean-squared error ofV . To this end, we note that, in our model, +V (I 1 ) = −V (I 2 ) = ∆P π [H t = h Q ] (where the probability that H t = h Q does not depend on the instance and follows from (22)). Thus, Combining this with (22) and (26) and using the function φ( We then choose Q that maximizes the lower bound in (27). With we obtain that Finally, combining the two bounds in (29) yields the claimed bound (21).

Adaptive Estimation via Lepski's Method
In order to make use of the results from Theorem 2.1 and Corollary 2.2 in practice, we need a way to choose the window length k such that the resulting estimator compromises between the bias and the variance. One possible method for choosing between V (π; k) is to rely on domain knowledge [Clouse and Utgoff, 1992, Tenorio-Gonzalez et al., 2010, Gimelfarb et al., 2018, but in our setting getting access to bounds on the mixing time may be difficult, and Corollary 2.2 only gives guidance on the scaling of k(n) up to constants. Here, we explore a candidate data-driven method based on Lepski's method [Lepskii, 1992, Birgé, 2001, a popular approach for adaptively choosing regularization parameters in nonparametric statistical problems. Particularly relevant to us, Lepski's method was recently used by Su et al. [2020] to control a bias-variance tradeoff in a dynamic off-policy evaluation setting following Thomas and Brunskill [2016]. Algorithmically, Lepski's method relies on a method for generating confidence intervals I(π; k) for V (π) given any choice of k. Then given I(π; k) for k = −1, 0, . . . , K,k * is chosen ask * := min{k : ∩ K j=k I(π; j) = ∅}, i.e., we scan backwards from the the largest k and choosesk * to be the last k such that I(π; k) still overlaps with ∩ K j=k+1 I(π; j). In order to use Lepski's method, we need to choose a construction for confidence intervals. Here, we proceed based on the following central limit theorem.
Given this result, we proceed by running Lepski's method (30) based on the induced Gaussian intervalŝ where υ is the threshold parameter (in our experiments, we use υ = 1 as a default choice). This choice of confidence function coincides with the intervals considered in Intersection Confidence Intervals (ICI) rule [Goldenshluger and Nemirovski, 1997, Katkovnik, 1999, Katkovnik and Spokoiny, 2008, Zhang et al., 2008, Katkovnik et al., 2010, a special version of Lepski's method that is commonly implemented in signal processing applications.

Proof of Theorem 4.1
We start by proving a concentration inequality on the partial estimator V i (π; k) via the Martingale method. The following lemma is a consequence of the Azuma-Hoeffding inequality [Azuma, 1967, Hoeffding, 1963.
Lemma 4.3. Under the assumptions in Theorem 4.1, there exists a constant C 3 (t 0 , ζ π , M 1 ) such that, for all r ≥ 0, We now define truncated residuals and note that, under the condition (31), by Lemma 4.3 applied with r = n 0.49 . Now, recall that conditional expected rewards are almost surely bounded and thus E V i (π; k) P i = E L e,π k i Y i,t P i is also, meaning that Z i + E V i (π; k) P i is almost surely bounded to order n 0.49 . Furthermore, Z i and E V i (π; k) P i are asymptotically uncorrelated, and so lim inf n→∞ ψ 2 n /n ≥ σ 2 0 , ψ 2 n = Var where σ 2 0 is the assumed lower bound on Var [V i (π )] for any policy π . Thus, we immediately see that Lindeberg's condition holds, i.e., for any > 0, and so the result (32) follows from Lindeberg's central limit theorem together with Slutsky's lemma [van der Vaart, 2000].

Numerical Experiments
In this section, we examine the performance of the partial-history importance weighted estimator and compare it to the benchmark methods in both a set of simple synthetic data and a simplified version of data obtained from a mobile health study. Throughout, we will focus on the case where we fix the horizon T , and vary the sample size n from 100 to 900. The threshold parameter υ in (34) is set to 1. To obtain a stationary chain, we discard data generated during a burn-in period of 50 time steps.

A Simple Example
As prelude, we consider a simple example with binary observed and hidden covariate. Let X i,t , H i,t ∈ {0, 1} be the observed and hidden covariate of unit i at time t respectively. Denote S i,t = (X i,t , H i,t ). At each time point, each unit is randomly assigned the treatment so that W i,t = 1 with probability 0.5. Instead of this behavior policy, we are interested in a deterministic policy π that assigns the unit to treatment if X i,t = 1, and to control if X i,t = 0. In particular, we aim at estimating the expected value of the outcome at stationary had the target policy been in place from the beginning. We assume that there are two types of units in this population, determined by an unobserved U i ∼ Bernoulli(0.5), each equipped with a pair of transition matrices. Given S i,t−1 , if the unit is in control, S t will be generated from the stochastic matrix where the entry P 0 j,l denotes the probability of transiting from state j to state l. Similarly, if the unit is treated, S i,t will be generated from the stochastic matrix  N (0, 1). We set T = 150, and carry out the simulation 10, 000 times. We calculate the MSE of estimating V (π) according to equation (4), varying k from 1 to 8. In addition, we compare it with two benchmark methods, where V (π) is estimated naively as the sample mean of Y i,t , or estimated according to equation (4) with k = 0. Figure 3 displays how MSE changes with different choices of k and n. Here k = −1 refers to estimating with sample mean, and k = 0 refers to the method adjusting for the distribution of the current treatment only. As can be seen from the plot, all MSE curves  The lightest orange corresponds to the case with n = 100, with a gradient to dark red representing n increases from n = 100 to n = 900 gradually.
follow the pattern of first decreasing as k increases, reaching a low point, and rising again as k continues to increase. In the descending phase, errors are mostly due to bias and so using a larger n doesn't help; whereas in the increasing phase, errors are dominated by variance. As n grows, the relative importance of variance decreases and so the optimal choice of k grows (here, we see it shift from k = 3 to 4 as sample size increases). To verify that the central limit theorem holds for the optimal choice of k, we calculate the Kolmogorov-Smirnov statistic that measures the distance between the standardized empirical distribution of V (π; k) and a standard Gaussian distribution, and plot it versus different choices of k in Figure 4. We see that the empirical distribution of V (π; k) is approximately normal for the optimal choices of k (k = 3 or 4); however, for larger choices of k (i.e., cases with more extreme importance weights) the Gaussian approximation is less accurate-especially when n is small.
Finally, to test the performance of Lepski's method in selecting appropriate window size, we apply it to the simulated dataset, with K = {−1, 0, . . . , 8}. Figure 5 shows the MSE achieved using Lepski's method as a function of n. As hoped, we see that Lepski's method achieves a risk that is close to the MSE we could get by choosing the oracle k. Figure 6 provides further insight on the mechanics of Lepski's method, by showing the distribution of the value of k chosen for different n. For small n, the choice k = 2 is the most common; however, the choices k = 3 and k = 4 become more common instead as n gets larger.

A Mobile Health Study
In order to test the performance of the partial history weighted estimator in a more realistic environment, we apply the method to synthetic datasets simulated to mimic data collected from a mobile health app that monitors the blood glucose level of type 1 diabetic patients. We follow the generative model in Luckett et al. [2019], where they design the model and estimate the parameters according to data collected from the mobile health study of Maahs et al. [2012]. In this study, each day is divided into 24 intervals of 60-minutes each. The patient is asked to upload their physical activities and blood glucose level every hour, and a treatment decision is assigned to the patient at the end of each time interval. The dataset contains the observations of a ten-day period (i.e., T = 240). The data generating process Figure 6: Percentages of each k ∈ K selected by Lepski's method under different sample sizes n. The lightest red area corresponds to choosing k = −1, with a gradient to dark red representing choosing k = 8.
can be described as follows.
At each time point, each patient is randomly chosen to receive an insulin injection with P (In i,t = 1) = 0.3. With a probability of 0.4, the patient will partake in mild physical activity, with the total counts of physical activity Ex i,t ∼ T N (31, 5 2 , 0, ∞), where T N (31, 5 2 , 0, ∞) denotes a normal distribution N (31, 5 2 ) left-truncated at 0; otherwise, with a probability of 0.2, the patient will partake in moderate physical activity, with Ex i,t ∼ T N (819, 10 2 , 0, ∞) + T N (31, 5 2 , 0, ∞). In addition, with a probability of 0.2, the patient will consume food, with the unobserved total dietary intake Di i,t ∼ T N (78, 10 2 , 0, ∞). The average blood glucose level is then generated according to the formula with the individual-level offset ν i ∼ N (0, 10 2 ), and the random noise ε i,t ∼ N (0, 5 2 ). The patient's utility at time t is represented by the category Gl i,t falls in, with (39) Given this sequentially randomized data collection policy, our goal is to evaluate the deterministic policy that assigns the patient an insulin injection if Gl i,t ≥ 125, and does nothing otherwise. 4 Figure 7: MSE as a function of k under different sample sizes n. The lightest orange corresponds to the case with n = 100, with a gradient to dark red representing n increases from n = 100 to n = 900 gradually.
We employ partial-history importance weighted estimator, as defined in (4), with k varying from 1 to 12. Simulations result are aggregated across 100, 000 replications. As in the first experiment, we compare our method to the two benchmark methods denoted as k = −1 and k = 0 (i.e., no re-weighting and myopic re-weighting). To calculate the MSE, we compute the ground truth expected outcome under the target policy using a Monte Carlo approximation. The behavior of the estimates is represented in Figure 7 and 8.
In Figure 7, we observe a similar pattern as before, with a U-shape curve exhibiting a bias-variance trade-off in choosing k under all n. Moreover, as n grows, the optimal k moves gradually from k * = 8 to k * = 11. However, in contrast to the first setting, we need to weight a relatively long history to obtain the optimal estimator, which appears to reflect a longer mixing time induced by the data generating mechanism of the blood glucose level. Finally, as seen in Figure 8 we again see that that the k selected by Lepski's method still achieves a reasonable performance in practice across all sample sizes.

Discussion
In this paper, we considered POMDPs as a model for treatment dynamics in off-policy evaluation under sequential ignorability. We motivated the POMDP model as a way to avoid instability problems inherent with fully non-parametric off-policy evaluation without having to commit to an (often unrealistic) MDP specification. Our main results provide upper and lower bounds that validate this tradeoff, and establish off-policy evaluation in POMDPs as a statistical task whose difficulty falls strictly between that of off-policy evaluation in the non-parametric and MDP models. Our upper bounds are achieved via a simple and practical algorithm, partial history importance weighting, that performs will in numerical experiments and can be tuned via Lepski's method. On a conceptual level, one interesting finding is that the key problem primitives that govern rates of convergence in both our upper and lower bounds are the mixing time t 0 and the overlap parameter ζ π . Furthermore, rates of convergence in both bounds only depend on these quantities via their product t 0 ζ π . Thus, our results suggest that a practitioner interested in off-policy evaluation in a POMDP model should pay close attention to these quantities.
In this paper, we have taken a largely agnostic approach to modeling POMDPs, and make essentially no assumptions on the unobserved states beyond mixing. One interesting question left open is whether making further structural assumptions about the hidden states could enable faster rates of convergence. For example, if we were to assume the variable H i,t to take values in a finite space with a bounded number of unique elements, would this affect minimax lower bounds for off-policy evaluation? Given the growing number of application areas in need of sample-efficient methods for evaluating dynamic treatment rules, it is likely that any results of this type would be of considerable interest. To ease the notation, we denote (X i,t , H i,t ) =: S i,t ∈ S, and use the shorthand F i,t to denote all the information observed for unit i up to time t, Z i,t:s to denote the set {Z i,t , ..., Z i,s } for any random variable and indexes t ≤ s. We use the notation P i (s |s, a) to denote the probability of transiting from state s to state s under action a. Throughout, we will use the notation d π i to denote the stationary distribution of S i,t under any policy π.

A.1 Proof of Lemma 2.3
To prove the first part of the lemma, note that where for any t = 1, . . . , T − k, Now it suffices to show that Without loss of generality, consider the case where t = 1, then which, after iteratively applying the importance weight, is the sum of the probability d e i (s i,1 )π wi,1 (s i,1 )P i (s i,2 |s i,1 , w i,1 ) · · · π w i,k (s i,k )P i (s i,k+1 |s i,k , w i,k )E π Y i,k+1 s i,k+1 (S4) over all possible observations of trajectory (s i,1 , w i,1 , s i,2 , w i,2 , . . . , w i,k , s i,k+1 ). Thus, where d e i (P π i ) k (s) denotes the probability of sampling s when starting from d e i and transiting k times under P π i . The proof of the second part of the Lemma follows directly from the assumptions on mixing time, where we have and d π i = d π i (P π i ) k follows from the fact that d π i is the stationary distribution of transition under P π i .
A.2 Proof of Lemma 2.4 To start with, we denote the centered weighted outcome as for t = k + 1, . . . , T . Using basic properties of the variance operator, Now it remains to upper bound E Ỹ i,tỸi,t+j P i . We first consider the case where j ≥ k + 1, i.e., there is no overlapping weights inỸ i,t andỸ i,t+j . Without loss of generality, we take t = k + 1 for simplicity. It follows that E ω i,k+1 (π; k)Y i,k+1 P i E ω i,k+1+j (π; k)Y i,k+1+j P i .
To show (C3) is satisfied, from the data generating distributions of Y (h, w), we have Therefore, if 0 ≤ ∆ ≤ M 1 , we will always have E Y t W t , H t ≤ M 1 , E Y 2 t W t , H t ≤ M 2 , for all t = 1, . . . , T , W t ∈ {0, 1}, and H t ∈ H.
A.5 Proof of Lemma 3.3 To obtain the KL divergence between the observed data generated from the two instances, it is necessary to calculate a KL divergence between two mixture models, for which there exists no closed-form expression. Therefore, we employ instead an upper bound of it: Since the only difference between the data generating distributions of (Y 1 , W 1 , H 1 ) under the two instances is the conditional distribution Y 1 |W 1 , H 1 = h Q , by (22) As a result, A.6 Proof of Proposition 4.2 Since Var [V i (π )] ≥ σ 2 0 for any policy π , σ 2 (π; k) = Var V (π; k) Thus, we will be able prove Proposition 4.2 if we can show n σ 2 (π; k) − σ 2 (π; k) → 0 in probability. Indeed, since V (π; k) P → V (π), nσ 2 (π; k) = 1 n n i=1 V i (π; k) − V (π; k) V i (π; k) − E V i (π; k) P i E V i (π; k) P i − V (π; k) P → E Var V i (π; k) P i + Var E V i (π; k) P i + 0 = nσ 2 (π; k).