Off-Policy Evaluation for Missingness-Aware Policies in MDPs with Rewards Missing Not at Random

Unknown

Conceptio › Archive › arXiv CS

arXiv CSopen access

Off-Policy Evaluation for Missingness-Aware Policies in MDPs with Rewards Missing Not at Random

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

machine learning, deep learning, neural networks

Off-Policy Evaluation for Missingness-Aware Policies in MDPs with Rewards Missing Not at Random

Ziheng Wei 1 Annie Qu 2 Rui Miao 3

arXiv:2606.20206v1 [stat.ML] 18 Jun 2026

Abstract

models and AI agents (Ouyang et al., 2022; Rafailov et al., 2023; Achiam et al., 2023). However, learning optimal policies often requires vast amounts of interaction with the environment, which can be costly, risky, and even unethical in high-stakes real-world applications such as healthcare and education (Tsiatis et al., 2019; Murphy, 2003; Mandel et al., 2014). In these applications, we often have interaction data collected according to some behavior policy, e.g., standard care or usual strategy. Estimating the value of a target policy using historical datasets collected under a different behavior policy, a problem known as Off-Policy Evaluation (OPE), is essential in offline RL (Levine et al., 2020; Uehara et al., 2022; Voloshin et al., 2019; Wang et al., 2024). Accurate OPE is critical for deploying safe and effective policies without the need for dangerous online exploration.

In offline Reinforcement Learning, immediate rewards in logged batch data are often unobserved due to sparse or irregular record-keeping, or censored beyond certain reward values. This issue arises in practical settings, including health care and marketing. We investigate off-policy evaluation (OPE) in finite-horizon Markov decision processes when rewards are missing not at random (MNAR), which breaks ignorability and induces selection bias even after conditioning on states and actions. To address this, we formalize a reward-dependent propensity model and use future states as shadow variables to identify the full-data conditional mean reward. We further introduce a bridge function that recovers the conditional mean reward without explicitly modeling the MNAR mechanism, and estimate it via a min-max procedure to avoid double sampling. Building upon these identification results, we propose an Fitted-Q-Evaluation-style estimator that propagates the recovered rewards while allowing target policies to depend on past missingness indicators. Finally, we establish consistency and finite-sample error bounds for our OPE estimator, and show through experiments the strong performance of our method compared to existing methods on simulated and MIMIC-III Sepsis data.

However, in many practical scenarios, such as medical treatment or digital advertising, the data is plagued by unobserved factors or missing values (Little & Rubin, 2019; Kallus & Zhou, 2020). A particularly pervasive challenge arises when rewards are missing not at random (MNAR), under which the probability of observing a reward depends on the latent value of the reward itself. For instance, in health care with scheduled chronic-disease management, patient outcomes such as patient-reported quality-of-life scores may be missing due to incomplete questionnaires or skipped follow-ups, while subsequent clinical states (lab results, vital signs, encounter records) are still recorded in the electronic health record (EHR). The recording of the outcome may itself depend on its value: patients with worsening symptoms are more likely to skip self-reported assessments, while those feeling well may also under-report. Similarly, in multi-touch digital marketing, attribution is frequently disrupted by privacy limitations. While non-conversions (zero rewards) are trivially observable, high-value purchases often involve cross-device journeys, such as a user clicking on mobile but converting on a desktop, or trigger manual review flows that break attribution links. Consequently, high-value conversions go missing while low-value or null outcomes remain fully observed, creating a dataset that systematically biases the learning process against the most desirable outcomes. Similar MNAR feedback has been systematically studied in recommender systems, where popularity and exposure biases make logged interactions MNAR and

1. Introduction Reinforcement Learning (RL) has achieved remarkable successes in sequential decision-making domains ranging from robotics to healthcare, and most recently in large language 1

Department of Statistics, University of Michigan at Ann Arbor Department of Statistics and Applied Probability, University of California at Santa Barbara 3 Department of Mathematical Sciences, University of Texas at Dallas. Correspondence to: Rui Miao <[email protected]>. 2

OPE for Missingness-Aware Policies in MDPs with Rewards Missing Not at Random

consequently distort offline evaluations (Yang et al., 2018).

optimization to estimate the bridge function and the value function, which avoids the double sampling issue.

Standard OPE methods, such as Fitted Q-evaluation (FQE) and Importance Sampling (IS), rely on fully observed trajectories. Failing to account for the missingness could lead to biased OPE and hence sub-optimal decision-making. In the OPE literature, scheme of missingness has been studied in various aspects. Partially Observable Markov Decision Processes (POMDPs, Kaelbling et al., 1998; Jaakkola et al., 1995) consider the case where the state is partially observed, which can be viewed as a special case of missingness. However, most existing POMDP methods assume that certain state variables are totally unobserved. In general, off-policy value in POMDPs are often unidentifiable without strong assumptions (Tennenholtz et al., 2020; Bennett et al., 2021; Shi et al., 2022; Uehara et al., 2023). Some works define the missingness of certain status (e.g., hitting wall in Gridworld environment (Sutton et al., 1998)) in the reward function by assigning it to be some large negative values to discourage certain actions, which lead to certain states with voided rewards (Ng et al., 1999; Devlin & Kudenko, 2012). However, this approach may not accurately reflect the true reward structure and can introduce bias. Chu et al. (2023); Park et al. (2025) study the OPE problem with truncated trajectories, where they treat missingness as certain constraints. However, by penalizing on the missingness, these methods may shift the policy evaluation away from the true potential reward without missingness. Wang et al. (2025) propose an inverse probability weighting method for OPE with nonignorable truncation, but their method relies on an extra shadow variable, or requires expert knowledge to select such a variable from observed states.

Building on these identification results, we further develop an FQE-style estimator that integrates the bridge function and allows target policies to depend on the previous missingness indicators. The procedure propagates the recovered rewards through the Bellman recursion of the target policy, yielding stable value estimates. We further establish the consistency and finite-sample error bounds of the proposed estimator in nonparametric settings. Extensive experiments on simulated data and a MIMIC-III dataset demonstrate the effectiveness of our method compared to existing benchmarks.

2. Preliminaries We consider an episodic Markov Decision Process (MDP) M = {S, A, P, r, T }, where S and A denote the state and action spaces, respectively. The horizon length T is finite, and we assume the terminal state ST +1 is observed. The transition kernels P = {Pt }Tt=1 govern the state dynamics, where Pt : S × A → ∆(S) maps state-action pairs to distributions over next states. The reward functions r = {rt }Tt=1 are defined as conditional expectations given the next state: rt (s, a, s′ ) = E[Rt | St = s, At = a, St+1 = s′ ] for any (s, a, s′ ) ∈ S × A × S. We assume bounded rewards Rt ∈ R ⊆ [−1, 1]. We introduce an observation indicator Ot ∈ {0, 1}, where Ot = 1 indicates that the reward Rt is observed at time t, and Ot = 0 otherwise. Importantly, we allow the rewards to be missing not at random (MNAR), that is, even after conditioning on current states and actions, the missingness probability may depend on the possibly unobserved reward itself. We formalize this through the propensity score et (s, a, r) = P (Ot = 1 | St = s, At = a, Rt = r) for t = 1, . . . , T .

In this paper, we study the OPE problem in MDPs with MNAR rewards to estimate values of target policies accounting for the past missingness. MNAR rewards break standard ignorability assumptions as the reward-dependent missingness induces selection bias and confounds state-action returns. The challenge is to recover the value of a target policy when the observed trajectories systematically underreport high or low rewards and when the missingness itself can depend on the past action and state, all without online data to re-collect or intervene.

Assumption 2.1 (No Future Dependence). For all t = 1, . . . , T − 1, Ot ⊥ (St+1:T , Rt+1:T ) | St , At , Rt .

We address these issues by formalizing the reward MNAR mechanism via a reward-dependent propensity score model and leveraging future states as shadow variables. Under mild completeness conditions, the shadow variables allow us to identify the full-data conditional mean reward even when the reward is MNAR. In addition, we introduce a bridge function bt (St , At , St+1 ) satisfying E {bt (St , At , St+1 ) | Rt , St , At } = Rt , enabling recovery of the conditional mean reward without explicitly estimating the MNAR mechanism. This avoids the variance blow-up in inverse propensity weighting. We propose the min-max

This assumption states that the current missingness indicator Ot , given the current state, action, and reward, is independent of all future states and rewards. For example, in healthcare, whether a patient’s health outcome is recorded typically depends on their current condition, not on future events that have not yet occurred. Our goal is to evaluate the performance of a target policy π = {πt }Tt=1 . We allow πt to depend on the previous reward missingness, which is practically relevant when decisions adapt based on whether prior outcomes were observed. For example, in healthcare, a clinician may choose 2

OPE for Missingness-Aware Policies in MDPs with Rewards Missing Not at Random

a more conservative treatment when the previous lab result is missing, whereas the historical standard-care behavior policy acts only on the current clinical state. The two policies thus share the same underlying causal structure but differ in which variables they condition on at decision time. Formally, πt : S × {0, 1} → ∆(A) with πt (a | s, o− ) = P (At = a | St = s, Ot−1 = o− ). To accommodate this dependence, we define an augmented state Set = (St , Ot−1 ) ∈ Se = S × {0, 1}, so that the target policy can be written as πt (a | Set ). The augmented process must satisfy the Markov property below.

Rt+1

Ot+1

St+1

At+1

St+2

Equivalently, for all (s, o− , a) with πtb (a | s) > 0, πt (a | s, o− ) ≤ κt πtb (a | s). Assumption 2.4. Assume there exist constants a > 0 and αt ≥ α > 1 such that for all t ∈ {1, . . . , T },

t = 1, . . . , T.

This assumption ensures that augmenting the state with the previous missingness indicator preserves the Markov property, and allows the value function recursion to hold with augmented state. The augmented transition kernel is P (Set+1 | Set , At ) = P ((St+1 , Ot ) | St , At ). We set O0 = 0 and let S1 ∼ ρ1 denote the initial state distribution. The Q-function and value function satisfy the Bellman equation π Qπt (s, a) =E rt (s, a, St+1 ) + Vt+1 (St+1 , Ot ) | St = s, At = a , X π Vt (s, o− ) = πt (a | s, o− )Qπt (s, a), VTπ+1 ≡ 0.

κt ≤ 1 +

a . tαt

Assumption 2.4 is an enhanced version for Assumption 2.3, which controls the cumulative growth of the concentrability coefficients so that the action mismatch does not compound over time. A structurally similar decay condition appears in Assumption 2 of Miao et al. (2022) in a POMDP setting. Corollary 2.5 (Bounded cumulative concentrability). Under Assumptions 2.3 and 2.4, for t = 1, . . . , T , (

(1) π e The policy value is defined as V (π) ≡ ESe1 ∼ρ̃1 V1 (S1 ) = ES1 ∼ρ1 V1π (S1 , 0) .

t Y

j=1

κj )

1/2

t 1 X a a ≤ exp ζ(α) := K, ≤ exp 2 j=1 j αj 2

where ζ(·) is the Riemann zeta function.

3. Identification

In OPE, data are collected under a behavior policy π b = {πtb }Tt=1 , where πtb : S → ∆(A) does not depend on the missingness indicators. The observed dataset D consists of obs n i.i.d. trajectories τi = {St,i , At,i , Ot,i , Rt,i , St+1,i }Tt=1 obs for i = 1, . . . , n, where Rt,i = Ot,i · Rt,i denotes the observed reward (zero when missing). See Figure 1 for a directed acyclic graph (DAG) illustrating the data-generating process.

In this section, we establish identification results for the policy value, and formalize the conditions required for our approach. To address the challenges posed by MNAR data in causal inference, Miao et al. (2015); Miao & Tchetgen Tchetgen (2016) propose identification methods with the help of auxiliary variables called shadow variables. Inspired by this line of research, we establish a nonparametric value-based approach for policy value identification. Our key insight is to adopt the next state St+1 as the shadow variable, which serves as a proxy that helps recover information about the unobserved rewards. The shadow variable must satisfy two conditions that govern its relationship with the reward and missingness indicator.

To deal with distribution shift in OPE, concentrability coefficients are often introduced (Munos, 2003; 2007; Chen & Jiang, 2019; Le et al., 2019; Duan et al., 2021). We define concentrability coefficient κt at time t in the following assumption. Assumption 2.3 (Concentrability). Given target policy π and behavior policy π b , for each t = 1, . . . , T , assume there exist finite constants {κt }Tt=1 such that ∥

Figure 1. DAG for the data-generating process. Black arrows represent the standard MDP dynamics and the MNAR reward mechanism, shared by both policies. The blue arrow Ot → At+1 is specific to the target policy, which is allowed to depend on the previous missingness indicator at decision time; the behavior policy depends only on the current state.

Assumption 2.2 (Markov Property for Augmented Process). The augmented process {(Set , At )}Tt=1 with Set = (St , Ot−1 ) is an MDP P (Set+1 | Se1:t , A1:t ) = P (Set+1 | Set , At ),

Assumption 3.1 (Exclusion Restriction). Suppose for all t = 1, . . . , T , St+1 satisfies

πt (a | s, o− ) ∥∞ ≤ κt . πtb (a | s)

St+1 ⊥ Ot | Rt , St , At . 3

OPE for Missingness-Aware Policies in MDPs with Rewards Missing Not at Random

Taking conditional expectation of (2) given (St , At ) yields

Assumption 3.2 (Relevance Condition). Suppose for all t = 1, . . . , T , St+1 satisfies

E[bt (s, a, St+1 ) | St = s, At = a]

St+1 ̸⊥ Rt | St , At , Ot = 1. The two assumptions above are basic conditions for St+1 to be a valid shadow variable at time t. Assumption 3.1 is a direct consequence of Assumption 2.1, which shows that conditional on the current state-action pair and the (possibly unobserved) reward, St+1 provides no additional information about whether the reward is observed. Assumption 3.2 ensures that on the observed subset, St+1 remains informative about Rt beyond what is already captured by (St , At ). This condition guarantees that the shadow variable carries useful information about the reward. In the causal graph in Figure 1, Assumption 3.1 is consistent with d-separation: conditioning on (Rt , St , At ) blocks all paths from St+1 to Ot . For subsequent analysis, we define the extended propensity score of non-missingness et (s, a, r, s′ ) = P (Ot = 1 | St = s, At = a, Rt = r, St+1 = s′ ). The choice of St+1 aligns with the recurring idea in POMDPs, i.e., leveraging future states or observations to serve as proxy latent state information (Singh et al., 2003; Uehara et al., 2023; Xu et al., 2023; Zhang & Jiang, 2024). Moreover, St+1 is endogenous to the MDP and already recorded in the logged transitions, so it requires no auxiliary measurement beyond the standard offline data, in contrast to approaches that specify an extra shadow variable (Wang et al., 2025).

Thus, the bridge function reproduces the correct one-step conditional mean reward required by the Bellman recursion. Moreover, a crucial observation which enables practical estimation is that P (St+1 | Rt , St , At , Ot = 1) = P (St+1 | Rt , St , At ), by Assumption 2.1. This implies that the bridge moment condition in Equation (2) can be identified from the observed subset {Ot = 1}. This means we can estimate the bridge function bt using only samples where rewards are observed, and then evaluate it at samples with Ot = 0 to impute the missing rewards. We further introduce the following assumptions for the identification of the policy value. Assumption 3.3 (Positivity). For all t = 1, . . . , T , and for all (s, a, r) ∈ S × A × R, 0 < et (s, a, r) < 1. The positivity assumption ensures that every state-actionreward triple has a positive probability of being both observed and unobserved, which is commonly used in causal inference literature. Assumption 3.4 (Completeness). For all (s, a) ∈ S × A, t = 1, . . . , T ,

For identification, rather than explicitly modeling the missingness mechanism under MNAR, our goal is to recover the full-data conditional mean reward E[Rt | St , At ] using only observable quantities. Under MNAR, the observed reward conditional expectation E Rt | St = s, At = a, Ot = 1 generally differs from the target E Rt | St = s, At = a , and directly using observed rewards would lead to a biased policy evaluation.

(1) For any square-integrable function h, E[h(Rt ) | St = s, At = a, St+1 ] Z = h(Rt )p(Rt | s, a, St+1 )dRt = 0, if and only if h(Rt ) = 0,

We adopt a bridge-based imputation strategy for missing rewards motivated by proximal causal inference (Tchetgen Tchetgen et al., 2020; Cui et al., 2024). Related bridge constructions also appear in the literature on confounded POMDPs (Miao et al., 2022; Shi et al., 2022; Hong et al., 2023; Li et al., 2025). The core idea is to construct functions that can learn the missing rewards in an unbiased manner by exploiting the relationship between rewards and next states.

a.s.

a.s.;

(2) For any square-integrable function g, E[g(St+1 ) | Rt , St = s, At = a] Z = g(St+1 )p(St+1 | Rt , s, a)dSt+1 = 0, if and only if g(St+1 ) = 0,

Specifically, we introduce a sequence of bridge functions {bt : S × A × S → R}Tt=1 satisfying the moment condition that E[bt (St , At , St+1 ) | Rt , St , At ] = Rt ,

(3)

=E(Rt | St = s, At = a) := r̄t (s, a).

a.s.

Assumption 3.4 guarantees the existence and uniqueness of the bridge functions bt , for t = 1, . . . , T . Completeness assumptions are standard in the proximal causal inference (Tchetgen Tchetgen et al., 2020; Cui et al., 2024), where they ensure that the conditional expectations are sufficiently rich to identify the target functional.

(2)

Equation (2) links the target quantity of interest to the observable offline distribution, and converts the recovery of E[Rt | St , At ] into an estimable conditional moment problem.

To provide concrete intuition, we characterize completeness in the tabular setting. 4

OPE for Missingness-Aware Policies in MDPs with Rewards Missing Not at Random

4. Estimation

Example 3.5 (Completeness in tabular setting). Assume S, R are tabular. Let matrix Mt,s,a ∈ R|S|×|R| where Mt,s,a (s′ , r) := P (St+1 = s′ | Rt = r, St = s, At = a) , s′ ∈ S, r ∈ R. Then

In this section, we discuss estimation of policy value and propose a FQE-style estimation method. To estimate the policy value, it suffices to estimate the bridge functions {bt } from conditional moment models

1. If for all (t, s, a), rank(Mt,s,a ) = |R|, then Assumption 3.4 (1) holds, and hence the bridge exists;

E[bt (St , At , St+1 ) − Rt | Rt , St , At , Ot = 1] = 0,

2. If for all (t, s, a), rank(Mt,s,a ) = |S|, then Assumption 3.4 (2) holds, and hence the bridge is unique;

which can be viewed as nonparametric instrumental variable (NPIV) problems. A natural approach would be to directly minimize the squared conditional moment

3. If |S| = |R|, then Mt,s,a is invertible for all (t, s, a) if and only if both Assumption 3.4 (1) and Assumption 3.4 (2) hold.

h 2 i min E E[bt (St , At , St+1 )−Rt | Rt , St , At , Ot = 1] .

bt ∈B(t)

Then we give the identification results for policy value as follows: Theorem 3.6 (Policy value identification). For an augmented MDP satisfying Assumptions 2.1, 2.2 and 3.2 to 3.4 and some regularity conditions, there always exist bridges {bt }Tt=1 that satisfy Equation (2), and the policy value then can be identified using {bt }Tt=1 .

However, this is not implementable for a single batch of trajectories because the squared conditional moments can lead to the double-sampling issue (Baird et al., 1995; Sutton et al., 1998). To circumvent the double-sampling problem, we adopt a min-max estimator for bt (Dikkala et al., 2020). The key insight is to replace the squared conditional moment with a saddle-point formulation that can be estimated from a single batch of samples.

See Appendix D for other regularity conditions and proof. Based on Theorem 3.6, we develop a value-based approach for policy value identification, which circumvents modeling the missing mechanism explicitly, in contrast to approaches such as Miao & Tchetgen Tchetgen (2016); Miao & Tchetgen (2018); Wang et al. (2025). This is practically significant as it can avoid the high variance induced from IPW methods or requires strong parametric assumptions about the missingness. Our identification procedure consists of three steps.

For each time step t, we solve 1 X (bt (St,i , At,i , St+1,i ) − Rt,i )gt (Rt,i , bt ∈B(t) g∈G (t) nt obs min

i∈It

U ∥gt ∥22 ) + λµ∥bt ∥2B(t) , δ2 (7) where Itobs = {i ∈ {1, . . . , n} : Ot,i = 1} denotes the observed dataset at time t, and nt = |Itobs |. We denote the function classes of gt and bt by G (t) , B (t) , which can be chosen as finite dimensional linear spaces, and infinite dimensional spaces like RKHSs, neural networks, etc. We focus on RKHSs in this paper. Let Q(t) be the RKHS containing function Qt . The term λ δU2 ∥gt ∥22 is the L2 penalty on the critic function gt . The norms ∥ · ∥2G (t) , ∥ · ∥2B(t) , ∥ · ∥2Q(t) denote the functional norm associated with G (t) , B (t) , Q(t) . λ, U, δ, µ > 0 are tuning parameters for the penalties. St,i , At,i ) − λ(∥gt ∥2G (t) +

using the observed subset with Ot = 1. This step leverages the shadow variable structure to extract reward information from state transitions. Step 2 (Identify Qπ and V π ). Define the imputed reward (4)

Then, we can substitute the estimates into fitted-Qevaluation (FQE) algorithm and obtain the estimate of policy value Vb (π). See Algorithm 1 for the point-estimated policy value estimation algorithm, where we use penalized nonparametric least squares to learn Qt :

and solve the Bellman recursion π et + Vt+1 Qπt (s, a) =E[R (St+1 , Ot ) | St = s, At = a], X Vtπ (s, o− ) = πt (a | s, o− )Qπt (s, a), VTπ+1 ≡ 0. a

It is trivial to verify that et | Rt , St , At ] = Rt , E[R

sup

Step 1 (Learn bt ). For each t = 1, . . . , T , learn bt from E bt (s, a, St+1 ) | Rt = r, St = s, At = a = r,

et := Ot Rt + (1 − Ot )bt (St , At , St+1 ), R

a.s.

a.s., (6)

X 2 b t = arg min 1 Q f (St,i , At,i )−yt,i +λQ,t ∥f ∥2Q(t) , (t) n i=1 f ∈Q (8) where yt,i is defined in Algorithm 1.

(5)

Step 3 (Identify the policy value). Compute V (π) = ESe1 ∼eρ1 [V1π (Se1 )] by backward induction. 5

OPE for Missingness-Aware Policies in MDPs with Rewards Missing Not at Random

Algorithm 1 Proximal FQE algorithm

5.2. Bridge function estimation error bound

{τi }ni=1 ,

Input: Offline dataset D = where τi = obs {(St,i , At,i , Ot,i , Rt,i , St+1,i )}Tt=1 , target policy π = {πt }Tt=1 , horizon T , function classes {B (t) , G (t) , Q(t) }. Initialize: VbTπ+1 (·, ·) ← 0. for t = T down to 1 do Bridge fitting: Obtain b̂t by solving Equation (7) on Itobs . be obs Imputation: for all i = 1, . . . , n set R + t,i ← R

For notational simplicity, define the projection operator Tt : L2 {S × A × S} → L2 {R × S × A}, which satisfies Tt bt = E[bt (St , At , St+1 )|Rt , St , At ]. Assumption 5.2 (Boundedness of Tt ). For any bt ∈ B (t) , Tt bt ∈ G (t) , and there exists L > 0 such that ∥Tt bt ∥G (t) ≤ L∥bt ∥B(t) .

t,i

Assumption 5.3 (Realizability). Suppose the true bridge function b∗t lies in function class B (t) . Similarly, we also assume Qπt ∈ Q(t) .

(1 − Ot,i )b̂t (St,i , At,i , St+1,i ). Targets for Bellman regression: if t < T then be bπ yt,i ← R t,i + Vt+1 (St+1,i , Ot,i ), i = 1, . . . , n. else be yt,i ← R t,i , i = 1, . . . , n. end if Fit Qt : regress yt,i on (St,i , At,i ) by Equation (8) to bt . obtain Q P b t (s, a). Define Vtπ : Vbtπ (s, o− ) ← a πt (a | s, o− )Q end for Pn Output: Vb (π) ← n1 i=1 Vb1π (S1,i , 0).

In practice, the boundedness assumption often holds when the conditional distribution of St+1 given (Rt , St , At ) is sufficiently smooth. Also, Realizability is a standard assumption in nonparametric estimation, requiring that the function classes are rich enough to contain the true targets. Next, we define the Bt -bounded norm subset of B (t) as (t) BB := {bt ∈ B (t) : ∥bt ∥B(t) ≤ Bt } and Ut -bounded norm (t) subset of G (t) as GU := {gt ∈ G (t) : ∥gt ∥G (t) ≤ Ut }. Assumption 5.4 (Richness of test function class). We suppose the test function approximation error within subset (t) GL2 ∥(b−b∗ )∥2 is bounded by

5. Theoretical results

sup

In this section, we establish consistency and finite-sample estimation error bounds for bridges b̂t and the policy value.

∥gt − Tt (b − b∗t )∥2 ≤ ηt < ∞.

This shows that function class G (t) is rich enough so that Tt (b − b∗t ) admits an L2 -approximation within (t) (t) GL2 ∥(b−b∗ )∥2 uniformly over b ∈ BB .

Definition 5.1 (Local Rademacher Complexity (Bartlett et al., 2005)). For any function class G defined over random variable X and radius δ > 0, the local Rademacher complexity is h

inf

(t) (t) b∈BB gt ∈GL2 ∥b−b∗ ∥2 t B(t)

5.1. Preliminaries

Rn (G, δ) = Eε,X

B(t)

Now we are ready to analyze min-max estimator b̂t estimated by Equation (7). Theorem 5.5 (Projected bridge estimation error bound (Dikkala et al., 2020; Miao et al., 2022)). For any t = 1, . . . , T , suppose function class G (t) is star-shaped and symmetric. Suppose G (t) and B (t) are 1-uniformly bounded. Define product class n (t) JB,U := ((s, a, s′ ), (r, s, a)) 7→ α(bt (s, a, s′ ) − b∗t (s, a, o (t) U s′ ))gb,t (r, s, a) | bt − b∗t ∈ BB , α ∈ [0, 1] ,

i 1X εi g(Xi ) , g∈G:∥g∥2 ≤δ n i=1 sup

where {Xi } are i.i.d. samples of X and {εi } are Rademacher random variables. ∥g∥22 := E[g(X)2 ] is the L2 norm of function g. Suppose the function class G satisfies

U where gb,t = arg mingt ∈G (t) ∥gt − Tt (b − b∗t )∥2 . De-

1. symmetric, if g ∈ G then −g ∈ G;

(t)

fine the two critical radii for function class G3U and (t) JB,L2 B , namely δtG and δtJ , and their maximum δnt := q 1 /ζ) . Assume max{δtG , δtJ }. Let δt = δnt + c0 log(c nt

2. star-shaped, if g ∈ G then rg ∈ G for all r ∈ [0, 1]; 3. b-uniformly bounded, ∥g∥∞ := supx∈X |g(x)| ≤ b for all g ∈ G.

δ2

ηt ≲ δt , then if λ ≍ Ut and µ ≥ 34 L2 + B36t λ δt2 , we have with probability 1 − 3ζ, the following bound holds Tt b̂t − b∗t 2 ≲ δt max{1, ∥b∗t ∥2B(t) }.

Then, the critical radius of such function class G, denoted by 2 δn , is the smallest solution to the inequality Rn (G, δ) ≤ δb . 6

OPE for Missingness-Aware Policies in MDPs with Rewards Missing Not at Random

Corollary 5.6 (RKHS cases with polynomial eigen decay). We further suppose B (t) and G (t) are RKHSs for all t = 1, . . . , T . KB,t and KG,t are the kernels of B (t) and G (t) G ∞ ∞ with non-increasing eigenvalues {µB t,j }j=1 and {µt,j }j=1 . We assume polynomial decay on eigenvalues, i.e., for some −2αB , µGt,j ≲ j −2αG , j → ∞. αB , αG > 12 , µB t,j ≲ j Let αmin := min{αB , αG }. Then the critical radius in Theα √ − 2α min+1 orem 5.5 satisfy δnt ≲ max{ Ut , LBt }nt min log nt . Consequently, under the conditions of Theorem 5.5, for all t = 1, . . . , T , with probability at least 1 − 3ζ,

Theorem 5.8 (Bridge estimation error bound). For any t = 1, . . . , T , suppose function class G (t) is star-shaped and symmetric. Suppose G (t) and B (t) are 1-uniformly bounded. Consider min-max estimator b̂t estimated by Equation (7). Define function classes star B (t) − b∗t = (t) {r(b−b∗t ) : b−b∗t ∈ BB , r ∈ [0, 1]}, and star Tt (B (t) − (t) U b∗t ) = {r gb,t : b − b∗t ∈ BB , r ∈ [0, 1]}, where U gb,t = arg mingt ∈G (t) ∥gt − Tt (b − b∗t )∥2 . Define the δnt U

(t)

as the upper bound on the critical radii qof G3U and the two function classes. Let δt = δnt + c0

∥Tt (b̂t − b∗t )∥2 ≲

− 2α min+1 log(c1 /ζ)nt min log nt .

log(c1 /ζ) . nt

Assume

δ2 ηt ≲ δt , then if λ ≍ Ut and µ ≥ 34 L2 + B36t λ δt2 , then with

probability 1 − 3ζ, the following bound holds Theorem 5.5 provides a finite-sample bound for the projected error ∥Tt (b̂t − b∗t )∥2 , where linear operator Tt maps a bridge function to a conditional expectation given (Rt , St , At ). However, for downstream analysis we also need control of the rooted mean-squared error (RMSE) ∥b̂t − b∗t ∥2 .

b̂t − b∗t 2 ≲ τt δt max{1, ∥b∗t ∥2B(t) }. 5.3. Policy value estimation error bound Based on Theorem 5.8, we can further bound the OPE error of the policy value Vb (π) estimated from Algorithm 1.

In general, converting projected error bounds into L2 error bounds is nontrivial because conditional moment problems are typically ill-posed inverse problems: the operator Tt is often compact and hence may not admit a stable inverse on an unrestricted function class. This phenomenon and the role of regularization in such conditional moment models are well-studied in the semi-/nonparametric literature; see, e.g., (Chen & Reiss, 2011; Chen & Pouzo, 2012). We introduce an ill-posedness measure for the conditional expectation operator Tt , following the definition in Dikkala et al. (2020). Since the true bridge b∗t is not assumed to lie (t) in BB , we define the best approximation within the ball bt,∗ := arg min ∥b − b∗t ∥2 , (t) b∈BB

Theorem 5.9 (Policy value estimation error bound). Suppose RKHSs Q(t) , B (t) , G (t) have polynomial eigen-decay rate −2αQ −2αB µQ , µB , µGt,j ≲ j −2αG , t,j ≲ j t,j ≲ j

where αQ , αB , αG > 1/2. Define αmin = min{αQ , αB , αG } > 12 . Denote δt,∗ = δ̄t,∗ + q c0 log(cn1 T /ζ) for some c0 , c1 > 0 where δ̄t,∗ is the upper bound of the critical radii of difference classes ∆Q(t) , (t) ∆Q(t+1) , ∆B (t) and GU defined in Appendix G. Suppose λQ,t ≍ (δ∆(t) )2 and let τmax = maxt≤T τt . Under AsQ sumptions 2.3, 2.4, 5.2 and 5.3 and assumptions for Theorem 3.6, with probability at least 1 − ζ, the policy value estimation error is bounded by

εt (Bt ) := inf ∥b − b∗t ∥2 . (t)

b∈BB

Definition 5.7 (Measure of ill-posedness). Define the ill∥b−b ∥2 posedness coefficient τt (Bt ) := supb∈B(t) ∥Tt (b−bt,∗t,∗ )∥ , 2 B and assume τt (Bt ) < ∞.

Vb (π) − V (π) ≲ Kτmax T 2

By combining Theorem 5.5 with Definition 5.7, we obtain an L2 error bound for the bridge estimator:

The choice of Bt trades off the approximation bias εt (Bt ) and the ill-posedness factor τt (Bt ). Consider the whole function class B (t) , where bt,∗ = b∗t and εt (Bt ) = 0 under Assumption 5.3, this gives the global ill-posedness

b∈B(t)

log(c1 T /ζ)n

− 2α min+1 min

log n.

Without considering the ill-posedness, our OPE error bound achieves the optimal rate in n in the classical nonparametric regression (Stone, 1982). Our error bound exhibits a T 2 dependence on the horizon, which arises from error propagation through the Bellman recursion and the additional complexity introduced by estimating bridge functions under the MNAR setting. For comparison, Wang et al. (2024) provide a fine-grained analysis of FQE under fully observed rewards. Under the completeness assumption for Q-functions p alone, they establish an error bound of order O(T 1.5 1/n) for both parametric p and nonparametric settings, improving upon the O(T 2 κ/n) bounds in prior work (Duan et al., 2020; Zhang et al., 2022). With an additional realizability assumption on the probability ratio functions wtπ , the rate further

∥b̂t − b∗t ∥2 ≤ τt (Bt )δt + (τt (Bt ) + 1)εt (Bt ).

τt := sup

∥b − bt,∗ ∥2 , ∥Tt (b − bt,∗ )∥2

where we assume τt < ∞. The RMSE is given by ∥b̂t − b∗t ∥2 ≲ τt δt . 7

OPE for Missingness-Aware Policies in MDPs with Rewards Missing Not at Random

p improves to O(T κ̃ 1/n), matching the sharpest known bound under the tabular setting (Yin & Wang, 2020). The additional T factor in our bound compared to the T 1.5 rate in Wang et al. (2024) partially reflects the cost of correcting for MNAR rewards through the bridge function mechanism.

n ∈ {64, 128, 256, 512, 1024, 2048} with T = 8, and T ∈ {2, 4, 8, 16, 32} with n = 512. More simulation details can be found in Appendix C.1. Figure 2 shows the MSE of prox (our method), and four baselines naive (naive FQE), ipw (IPW-FQE), impute (Impute-FQE), and scope (SCOPE) under three MNAR missingness levels, approximately 20%, 40%, and 80%. Across all three panels, prox achieves the fastest error decay in n and consistently the smallest MSE, with its advantage growing under heavier missingness. The baselines plateau at non-vanishing bias floors (naive, ipw), amplify selection bias (impute), or degrade under high missingness (scope), consistent with our theoretical analysis. Overall, the results demonstrate that prox is the most accurate and stable estimator in this setting.

6. Experiments In this section, we evaluate the performance of the proposed OPE estimator with rewards MNAR on both simulated and real-world data. We compare our method with four baselines: an IPW-based OPE method (Wang et al., 2025), a naive FQE baseline, an imputation-based OPE method and a reward-shaping-based OPE method (Parbhoo et al., 2020). The naive FQE estimator ignores the MNAR mechanism and applies FQE directly to the observed rewards. The IPW baseline adapts the weighting scheme of Wang et al. (2025), which was originally developed for a trajectory dropout model. The imputation-based baseline learns the reward function by regression and imputes the unobserved reward using the fitted model. The reward-shaping baseline, named SCOPE, uses per-step importance sampling with potentialbased reward shaping.

Additional simulation results for varying horizon lengths and different reward generation mechanisms are reported in Appendix C in the Supplemental Materials. 6.2. Application: MIMIC-III Sepsis data We evaluate our method on a real-world clinical dataset from the MIMIC-III database (Johnson et al., 2016), using the sepsis cohort and pre-processing pipeline of Raghu et al. (2017). The dataset consists of ICU patients meeting the Sepsis-3 criteria, where physiological measurements, lab values, and treatment records are aggregated into 4-hour windows. Each patient’s state at time t is represented by a 48-dimensional feature vector comprising demographics and static indices (e.g., age, SOFA score, SIRS), laboratory values, vital sign, and intake/output variables. The action space consists of 25 discrete treatment options formed by 5 vasopressor dose levels × 5 IV fluid dose levels, where non-zero dosages are discretized into quartiles.

We present results on simulation studies and a real-data application below. Our code is available at https:// github.com/NAIVlab/ShadOPE. 6.1. Simulation studies We conduct simulation studies in finite-horizon episodic MDPs to evaluate the proposed method under varying missingness levels and reward generation mechanisms. We compare ProxFQE against four baselines, naive FQE, IPW-FQE, Impute-FQE, and SCOPE, over 50 random seeds. We set state St = (St,1 , St,2 )⊤ ∈ S = R2 as a twodimensional vector. The action space is binary, A = {−1, 1}. Let O = {0, 1} and R = R. The propensity score is set as et (St , At , Rt ) = expit c0 −0.1At +0.2(1, −2)⊤ St +2.5Rt

where c0 is calibrated to attain target missing rates ranging from 20% to 80%. The target policy we want to evaluate is given by Pπ (At = 1 | St , Ot−1 ) = expit 3[(1, 0.3)⊤ St + 0.5

We retain patients with at least 10 recorded time steps and truncate to the first 10, yielding a horizon of T = 10 with 13,943 patients. The reward at each step is defined as Rt = −(SOF At+1 − SOF At ). Since the MIMIC-III rewards are fully observed, we introduce synthetic MNAR missingness to evaluate our method. The target policy is constructed by training a Double DQN on the fully-observed data and then applying a conservative dose reduction, yielding a missingness-aware policy π(a | st , ot−1 ). Additional setups are provided in Appendix C.4. We compare prox against oracle (oracle FQE), which uses fully observed rewards as a reference), naive, impute, ipw, and scope.

− 0.8(2Ot−1 − 1)] See Figure 4 in Appendix C for visualization of the generated data.

Figure 3 presents the results (full numerical results are provided in Table 1 in Appendix C.4). prox attains the lowest bias across all missing rates and remains close to oracle even under severe missingness, while all baselines exhibit substantially larger and growing bias as the missing rate

For function classes, we choose Gaussian kernels for G (t) and B (t) . We report MSE under three settings: varying the sample size, varying the horizon length, and varying the reward generation mechanism. Specifically, we consider 8

MSE vs n (missingness ~20%)

28 26 24 22 20 22 24 26 28

MSE vs n (missingness ~40%)

MSE vs n (missingness ~80%)

MSE (log2 scale)

OPE for Missingness-Aware Policies in MDPs with Rewards Missing Not at Random

20 22 24 26

211

210

21 23 25

28 26

naive

prox

n method

ipw

210 impute

211

210

211

scope

Figure 2. MSE vs. sample size (n) under three MNAR missingness percentages (∼20%, ∼40%, ∼80%). prox consistently achieves the lowest MSE across all sample sizes and missingness levels, with MSE decreasing steadily as n grows. (a) Estimated Policy Value V( )

20.0

15.0

12.5

|V( ) VOracle|

17.5

V( )

12.5 10.0 7.5 5.0

10.0 7.5 5.0 2.5

2.5 0.0

(b) Absolute Bias vs Oracle

17.5

20%

40%

60%

MNAR Missing Rate

oracle

0.0

80% prox

ipw

20%

40%

naive

impute

60%

MNAR Missing Rate

80%

Figure 3. OPE results on MIMIC-III sepsis data under MNAR missing rates from 20% to 80%. (a) Estimated policy value V̂ (π) with standard error bars. oracle FQE (gray) uses fully observed rewards as a reference. (b) Absolute bias relative to oracle FQE. SCOPE is excluded due to degenerate estimates.

increases. scope produces degenerate estimates due to near-zero importance weight overlap and is excluded from the figure.

moment conditions or the completeness assumptions, one can assess the robustness of policy value estimates to potential unobserved confounding in the missingness mechanism. Such sensitivity analyses have been studied in proximal causal inference and POMDPs, and adapting their frameworks from proximal causal inference and POMDPs to the reward-missingness mechanism in MDPs is an important direction for future work.

7. Conclusion and Discussion We study OPE in MDPs with MNAR rewards, proposing a bridge function approach that recovers the conditional mean reward without explicitly modeling the missingness mechanism. Unlike IPW-based methods (Wang et al., 2025) that require external auxiliary variables, our method uses the next state as an endogenous shadow variable, avoiding additional data requirements and IPW variance inflation.

Acknowledgement Qu’s research is partially supported by NSF Grant DMS 2515275, NCI grant 1R01CA297869, NSF Grant CDS&EMSS 2401271. Miao’s research is partially supported by Texas Artificial Intelligence Institute at University of Texas at Dallas.

A limitation of our framework is that the reward missingness process may still be influenced by unobserved confounding factors that are not fully captured by the observed trajectories. While our identification relies on assumptions through the bridge function, violations of these assumptions may lead to biased policy value estimates in practice.

Impact Statement This paper presents work whose goal is to advance the field of machine learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.

To address this concern, an important future direction is to incorporate sensitivity analysis into the proposed OPE framework. By parameterizing deviations from the bridge 9

OPE for Missingness-Aware Policies in MDPs with Rewards Missing Not at Random

References

Duan, Y., Jia, Z., and Wang, M. Minimax-optimal offpolicy evaluation with linear function approximation. In International Conference on Machine Learning, pp. 2701– 2709. PMLR, 2020.

Achiam, J., Adler, S., Agarwal, S., Ahmad, L., Akkaya, I., Aleman, F. L., Almeida, D., Altenschmidt, J., Altman, S., Anadkat, S., et al. Gpt-4 technical report. arXiv preprint arXiv:2303.08774, 2023.

Duan, Y., Jin, C., and Li, Z. Risk bounds and rademacher complexity in batch reinforcement learning. In International Conference on Machine Learning, pp. 2892–2902. PMLR, 2021.

Baird, L. et al. Residual algorithms: Reinforcement learning with function approximation. In Proceedings of the twelfth international conference on machine learning, pp. 30–37, 1995.

Enders, C. K. Applied missing data analysis. Guilford Publications, 2022.

Bartlett, P. L., Bousquet, O., and Mendelson, S. Local rademacher complexities. 2005.

Finn, C., Yu, T., Fu, J., Abbeel, P., and Levine, S. Generalizing skills with semi-supervised reinforcement learning. arXiv preprint arXiv:1612.00429, 2016.

Bennett, A. and Kallus, N. Proximal reinforcement learning: Efficient off-policy evaluation in partially observed markov decision processes. arXiv preprint arXiv:2110.15332, 2021.

Fischer, S. and Steinwart, I. Sobolev norm learning rates for regularized least-squares algorithms. Journal of Machine Learning Research, 21(205):1–38, 2020.

Bennett, A., Kallus, N., Li, L., and Mousavi, A. Off-policy evaluation in infinite-horizon reinforcement learning with latent confounders. In International Conference on Artificial Intelligence and Statistics, pp. 1999–2007. PMLR, 2021.

Foster, D. J. and Syrgkanis, V. Orthogonal statistical learning. The Annals of Statistics, 51(3):879–908, 2023.

Chen, J. and Jiang, N. Information-theoretic considerations in batch reinforcement learning. In International conference on machine learning, pp. 1042–1051. PMLR, 2019.

Fukumizu, K., Gretton, A., Lanckriet, G., Schölkopf, B., and Sriperumbudur, B. K. Kernel choice and classifiability for rkhs embeddings of probability distributions. Advances in neural information processing systems, 22, 2009.

Chen, X. and Pouzo, D. Estimation of nonparametric conditional moment models with possibly nonsmooth generalized residuals. Econometrica, 80(1):277–321, 2012.

Harutyunyan, A., Brys, T., Vrancx, P., and Nowé, A. Offpolicy reward shaping with ensembles. arXiv preprint arXiv:1502.03248, 2015.

Chen, X. and Reiss, M. On rate optimality for ill-posed inverse problems in econometrics. Econometric Theory, 27(3):497–521, 2011.

Hong, M., Qi, Z., and Xu, Y. A policy gradient method for confounded pomdps. arXiv preprint arXiv:2305.17083, 2023.

Chu, J., Yang, S., and Lu, W. Multiply robust off-policy evaluation and learning under truncation by death. In International Conference on Machine Learning, pp. 6195– 6227. PMLR, 2023.

Jaakkola, T., Singh, S. P., and Jordan, M. I. Reinforcement learning algorithm for partially observable markov decision problems. Advances in Neural Information Processing Systems, pp. 345–352, 1995.

Cui, Y., Pu, H., Shi, X., Miao, W., and Tchetgen Tchetgen, E. Semiparametric proximal causal inference. Journal of the American Statistical Association, 119(546):1348–1359, 2024.

Johnson, A. E., Pollard, T. J., Shen, L., Lehman, L.-w. H., Feng, M., Ghassemi, M., Moody, B., Szolovits, P., Anthony Celi, L., and Mark, R. G. Mimic-iii, a freely accessible critical care database. Scientific data, 3(1):1–9, 2016.

Devlin, S. and Kudenko, D. Dynamic potential-based reward shaping. Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems, pp. 433–440, 2012.

Kaelbling, L. P., Littman, M. L., and Cassandra, A. R. Planning and acting in partially observable stochastic domains, volume 101. Elsevier, 1998.

Dikkala, N., Lewis, G., Mackey, L., and Syrgkanis, V. Minimax estimation of conditional moment models. Advances in Neural Information Processing Systems, 33:12248– 12262, 2020.

Kallus, N. and Uehara, M. Double reinforcement learning for efficient off-policy evaluation in markov decision processes. In International Conference on Machine Learning, pp. 5078–5088. PMLR, 2020. 10

OPE for Missingness-Aware Policies in MDPs with Rewards Missing Not at Random

Kallus, N. and Zhou, A. Confounding-robust policy evaluation in infinite-horizon reinforcement learning. Advances in Neural Information Processing Systems, 33:22293– 22304, 2020.

Miao, W. and Tchetgen, E. T. Identification and inference with nonignorable missing covariate data. Statistica Sinica, 28(4):2049, 2018. Miao, W. and Tchetgen Tchetgen, E. J. On varieties of doubly robust estimators under missingness not at random with a shadow variable. Biometrika, 103(2):475–482, 2016.

Kress, R. Linear integral equations, volume 82. Springer, 1989. Krieg, D. Tensor power sequences and the approximation of tensor product operators. Journal of Complexity, 44: 30–51, 2018.

Miao, W., Tchetgen Tchetgen, E., and Geng, Z. Identification and doubly robust estimation of data missing not at random with an ancillary variable. 2015.

Kuang, Q., Wang, J., Zhou, F., and Qi, Z. Breaking the order barrier: Off-policy evaluation for confounded pomdps. Advances in Neural Information Processing Systems, 38: 49491–49538, 2026.

Miao, W., Geng, Z., and Tchetgen Tchetgen, E. J. Identifying causal effects with proxy variables of an unmeasured confounder. Biometrika, 105(4):987–993, 2018.

Le, H. M., Voloshin, C., and Yue, Y. Batch policy learning under constraints. International Conference on Machine Learning, pp. 3703–3712, 2019.

Mohan, K. and Pearl, J. Graphical models for processing missing data. Journal of the American Statistical Association, 116(534):1023–1037, 2021.

Levine, S., Kumar, A., Tucker, G., and Fu, J. Offline reinforcement learning: Tutorial, review, and perspectives on open problems. arXiv preprint arXiv:2005.01643, 2020.

Munos, R. Error bounds for approximate policy iteration. In Proceedings of the Twentieth International Conference on International Conference on Machine Learning, pp. 560–567, 2003.

Li, A., Boots, B., and Cheng, C.-A. Mahalo: Unifying offline reinforcement learning and imitation learning from observations. In International Conference on Machine Learning, pp. 19360–19384. PMLR, 2023.

Munos, R. Performance bounds in l p-norm for approximate value iteration. SIAM journal on control and optimization, 46(2):541–561, 2007. Murphy, S. A. Optimal dynamic treatment regimes. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 65(2):331–355, 2003.

Li, Y., Han, E., Hu, Y., Zhou, W., Qi, Z., Cui, Y., and Zhu, R. Reinforcement learning with continuous actions under unmeasured confounding. Journal of the American Statistical Association, (just-accepted):1–26, 2025.

Ng, A. Y., Harada, D., and Russell, S. Policy invariance under reward transformations: Theory and application to reward shaping. In International Conference on Machine Learning, pp. 278–287, 1999.

Little, R. J. and Rubin, D. B. Statistical analysis with missing data. John Wiley & Sons, 2019. Littman, M. and Sutton, R. S. Predictive representations of state. Advances in neural information processing systems, 14, 2001.

Ouyang, L., Wu, J., Jiang, X., Almeida, D., Wainwright, C., Mishkin, P., Zhang, C., Agarwal, S., Slama, K., Ray, A., et al. Training language models to follow instructions with human feedback. Advances in Neural Information Processing Systems, 35:27730–27744, 2022.

Liu, Q., Li, L., Tang, Z., and Zhou, D. Breaking the curse of horizon: Infinite-horizon off-policy estimation. Advances in Neural Information Processing Systems, 31, 2018.

Parbhoo, S., Gottesman, O., and Doshi-Velez, F. Shaping control variates for off-policy evaluation. In Offline Reinforcement Learning Workshop at Neural Information Processing Systems (NeurIPS), pp. 93, 2020.

Majumdar, R., Teversham, J., and Parbhoo, S. Conceptbased off-policy evaluation. In Reinforcement Learning Conference, 2025. Mandel, T., Liu, Y.-E., Levine, S., Brunskill, E., and Popovic, Z. Offline policy evaluation across representations with applications to educational games. Proceedings of AAMAS, 2014.

Park, S., Lu, W., and Yang, S. Evaluating and learning optimal dynamic treatment regimes under truncation by death. arXiv preprint arXiv:2510.07501, 2025. Rafailov, R., Sharma, A., Mitchell, E., Manning, C. D., Ermon, S., and Finn, C. Direct preference optimization: Your language model is secretly a reward model. Advances in neural information processing systems, 36: 53728–53741, 2023.

Miao, R., Qi, Z., and Zhang, X. Off-policy evaluation for episodic partially observable markov decision processes under non-parametric models. Advances in Neural Information Processing Systems, 35:593–606, 2022. 11

OPE for Missingness-Aware Policies in MDPs with Rewards Missing Not at Random

Raghu, A., Komorowski, M., Ahmed, I., Celi, L., Szolovits, P., and Ghassemi, M. Deep reinforcement learning for sepsis treatment. arXiv preprint arXiv:1711.09602, 2017.

Uehara, M., Kiyohara, H., Bennett, A., Chernozhukov, V., Jiang, N., Kallus, N., Shi, C., and Sun, W. Futuredependent value-based off-policy evaluation in pomdps. Advances in neural information processing systems, 36: 15991–16008, 2023.

Rashidinejad, P., Zhu, B., Ma, C., Jiao, J., and Russell, S. Bridging offline reinforcement learning and imitation learning: A tale of pessimism. In Advances in Neural Information Processing Systems, volume 34, pp. 11702– 11716, 2021.

Voloshin, C., Le, H. M., Jiang, N., and Yue, Y. Empirical study of off-policy policy evaluation for reinforcement learning. arXiv preprint arXiv:1911.06854, 2019. Wainwright, M. J. High-dimensional statistics: A nonasymptotic viewpoint, volume 48. Cambridge university press, 2019.

Shao, J. and Wang, L. Semiparametric inverse propensity weighting for nonignorable missing data. Biometrika, 103(1):175–187, 2016.

Wang, H., Xu, Y., Lu, W., and Song, R. Off-policy evaluation under nonignorable missing data. arXiv preprint arXiv:2507.06961, 2025.

Shi, C., Uehara, M., Huang, J., and Jiang, N. 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, 2022.

Wang, J., Qi, Z., and Wong, R. K. A fine-grained analysis of fitted q-evaluation: beyond parametric models. arXiv preprint arXiv:2406.10438, 2024.

Shi, L., Li, G., Wei, Y., Chen, Y., and Chi, Y. Pessimistic q-learning for offline reinforcement learning: Towards optimal sample complexity. In International Conference on Machine Learning, pp. 31335–31385. PMLR, 2023.

Xie, T., Cheng, C.-A., Jiang, N., Mineiro, P., and Agarwal, A. Bellman-consistent pessimism for offline reinforcement learning. In Advances in Neural Information Processing Systems, volume 34, pp. 6683–6694, 2021.

Singh, S. P., Littman, M. L., Jong, N. K., Pardoe, D., and Stone, P. Learning predictive state representations. In Proceedings of the 20th International Conference on Machine Learning (ICML-03), pp. 712–719, 2003.

Xu, Y., Zhu, J., Shi, C., Luo, S., and Song, R. An instrumental variable approach to confounded off-policy evaluation. In International Conference on Machine Learning, pp. 38848–38880. PMLR, 2023.

Stone, C. J. Optimal global rates of convergence for nonparametric regression. The annals of statistics, pp. 1040–1053, 1982.

Yang, L., Cui, Y., Xuan, Y., Wang, C., Belongie, S., and Estrin, D. Unbiased offline recommender evaluation for missing-not-at-random implicit feedback. In Proceedings of the 12th ACM conference on recommender systems, pp. 279–287, 2018.

Sun, B. and Tchetgen Tchetgen, E. J. Semiparametric estimation with data missing not at random using an instrumental variable. Statistica Sinica, 28(4):1965, 2018.

Yin, M. and Wang, Y.-X. Asymptotically efficient off-policy evaluation for tabular reinforcement learning. In International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pp. 3948–3958. PMLR, 2020.

Sutton, R. S., Barto, A. G., et al. Reinforcement learning: An introduction, volume 1. MIT press Cambridge, 1998. Tchetgen Tchetgen, E. J., Ying, A., Cui, Y., Shi, X., and Miao, W. An introduction to proximal causal learning. arXiv preprint arXiv:2009.10982, 2020.

Zhan, W., Huang, B., Huang, A., Jiang, N., and Lee, J. D. Offline reinforcement learning with realizability and singlepolicy concentrability. In Conference on Learning Theory, pp. 2730–2775. PMLR, 2022.

Tennenholtz, G., Shalit, U., and Mannor, S. Off-policy evaluation in partially observable environments. Proceedings of the AAAI Conference on Artificial Intelligence, 34(06): 10276–10283, 2020.

Zhang, R., Zhang, X., Ni, C., and Wang, M. Off-policy fitted q-evaluation with differentiable function approximators: Z-estimation and inference theory. In International Conference on Machine Learning, pp. 26713–26749. PMLR, 2022.

Tsiatis, A. A., Davidian, M., Holloway, S. T., and Laber, E. B. Dynamic Treatment Regimes: Statistical Methods for Precision Medicine. CRC press, 2019.

Zhang, Y. and Jiang, N. On the curses of future and history in future-dependent value functions for off-policy evaluation. Advances in Neural Information Processing Systems, 37:124756–124790, 2024.

Uehara, M., Shi, C., and Kallus, N. A review of off-policy evaluation in reinforcement learning. arXiv preprint arXiv:2212.06355, 2022. 12

OPE for Missingness-Aware Policies in MDPs with Rewards Missing Not at Random

Zhang, Y. and Jiang, N. Statistical tractability of off-policy evaluation of history-dependent policies in pomdps. arXiv preprint arXiv:2503.01134, 2025. Zheng, Q., Henaff, M., Amos, B., and Grover, A. Semisupervised offline reinforcement learning with actionfree trajectories. In International conference on machine learning, pp. 42339–42362. PMLR, 2023.

OPE for Missingness-Aware Policies in MDPs with Rewards Missing Not at Random

A. Related Work OPE. Off-policy evaluation has been extensively studied in the RL literature. Classical methods include IS and its variants (Liu et al., 2018), FQE (Le et al., 2019), and doubly robust estimators that combine both (Kallus & Uehara, 2020). Recent advances in offline RL have developed pessimistic approaches (Xie et al., 2021; Rashidinejad et al., 2021; Shi et al., 2023; Zhan et al., 2022) that achieve near-optimal sample complexity. For comprehensive reviews, see Uehara et al. (2022) and Levine et al. (2020). OPE in POMDPs has received growing attention, with works addressing latent confounding (Bennett et al., 2021; Kallus & Zhou, 2020), partial observability (Tennenholtz et al., 2020; Shi et al., 2022; Miao et al., 2022), and future-dependent estimation (Uehara et al., 2023; Zhang & Jiang, 2024). More recent extensions study OPE of history-dependent policies through model-based methods (Zhang & Jiang, 2025), confounded POMDPs (Kuang et al., 2026), and concept-based representations (Majumdar et al., 2025). These works tackle partial observability in the state process, while our work addresses a complementary challenge: MNAR missingness in the reward process under a fully observed MDP. Missing Data. Missing data problems have been extensively studied in statistics (Little & Rubin, 2019; Enders, 2022). Under missing at random (MAR) assumptions, inverse probability weighting and doubly robust methods are well-established. For MNAR, identification typically requires additional structure such as instrumental variables (Sun & Tchetgen Tchetgen, 2018), shadow variables (Shao & Wang, 2016; Miao & Tchetgen Tchetgen, 2016; Miao et al., 2018), or graphical constraints (Mohan & Pearl, 2021). Proximal causal inference (Tchetgen Tchetgen et al., 2020; Bennett & Kallus, 2021; Cui et al., 2024) has emerged as a powerful framework for handling unmeasured confounding using proxy variables. Our work extends these ideas to the OPE setting with MNAR rewards, leveraging future states as shadow variables for identification. Reward Shaping. Potential-based reward shaping augments rewards with a potential difference to densify sparse feedback while preserving the optimal policy (Ng et al., 1999), with later extensions to dynamic shaping and off-policy settings (Devlin & Kudenko, 2012; Harutyunyan et al., 2015; Parbhoo et al., 2020). These methods are designed to accelerate policy learning or reduce variance under fully observed rewards, whereas our work targets identification under MNAR rewards via a bridge function. Semi-supervised RL. Our setting also relates to semi-supervised RL and partially reward-labeled sequential decisionmaking, including semi-supervised RL with rewards available only in labeled MDPs (Finn et al., 2016), semi-supervised offline RL with mixed labeled and unlabeled trajectories (Zheng et al., 2023), and offline policy learning with partially reward-labeled trajectories (Li et al., 2023). These works focus on policy learning or reward modeling under label scarcity, whereas we target off-policy evaluation under an MNAR missingness mechanism that depends on the latent reward.

B. Discussion on shadow variables In the causal inference literature on missing data, identification typically requires additional assumptions, most commonly instantiated through either instrumental variables or shadow variables. Shadow-variable approaches (Miao et al., 2015; Miao & Tchetgen Tchetgen, 2016) leverage a fully observed variable that is informative about the outcome while being conditionally independent of the missingness mechanism given covariates and the (possibly unobserved) outcome. In contrast, instrumental-variable approaches (Sun & Tchetgen Tchetgen, 2018) posit a variable that shifts the missingness mechanism but has no direct effect on the outcome. In sequential decision making, Wang et al. (2025) develop an approach that requires specifying a stage-wise shadow variable Zt that satisfies conditional independence with dropout given (St , At , Rt+1 , St+1 ) while remaining informative about (Rt+1 , St+1 ) on the observed subset, effectively providing the identifying leverage needed to learn the dropout model. While such a choice can be plausible, it may rely on additional measurements or domain knowledge to select a valid Zt . In contrast, we adopt an endogenous choice of shadow variable, which is the next state St+1 . Under the exclusion restriction and relevance condition in Assumptions 3.1 and 3.2, St+1 provides a readily available proxy for the MNAR reward without introducing an extra auxiliary variable. Moreover, a natural extension of St+1 is a multi-step future variable, or a low-dimensional summary thereof. This aligns with a broader predictive-state perspective in POMDPs, where future observations are used to encode information about the latent state (Littman & Sutton, 2001; Singh et al., 2003). More recently, Xu et al. (2023); Uehara et al. (2023) use multi-step 14

OPE for Missingness-Aware Policies in MDPs with Rewards Missing Not at Random

futures to stand in for the unobserved state: instead of conditioning on the latent state, they condition on a future window and learn quantities from it, using the future window as a proxy that carries latent-state information. In missing data problems in MDPs, using longer futures can carry richer information about the missing rewards, and may make relevance and completeness-type conditions more plausible, but it also increases the statistical and computational burden as the future window grows. In practice, these tradeoffs motivate using compact summaries of multi-step futures.

C. Additional Experiment Details C.1. Additional simulation setups We set the behavior policy that generates the offline trajectories as Pπb (At = 1 | St ) = expit 0.3 + (0.8, −0.3)⊤ St . The next state St+1 is generated by transition kernel St+1 = 0.9St + 0.2At 12 + N (0, 0.12 I2 ) where 12 = (1, 1)⊤ and initial state S1 ∼ N (0, I2 ). We consider two reward generation mechanisms. The first is the sigmoid reward model used in other simulations: Rt = expit([0.9 − 0.6At , −0.7]⊤ St + [1.3, 2]⊤ St+1 − 0.4At ) + Ut ,

Ut ∼ Unif[−0.1, 0.1],

and the second is a linear reward model: Rt = clip([0.5, −0.3]⊤ St + [0.8, 0.6]⊤ St+1 − 0.3At + ϵt , −1, 1),

ϵt ∼ N (0, 0.01).

The true policy value is estimated by Monte Carlo using 5000 independent trajectories generated under the target policy. We visualize the generated data for the setting n = 1000, T = 10, and random seed 44; see Figure 4 for an overview. For all the RKHSs, the bandwidths are selected by median heuristic trick (Fukumizu et al., 2009); parameter δ is set to δt = 5nt−0.4 according to (Dikkala et al., 2020). The penalty parameter λrkhs is chosen by cross-validation.

Figure 4. Data overview. Left: histogram of the true reward rtrue with three overlays: overall (blue), observed O=1 (orange), and missing O=0 (red). The total missing rate is 11.60%. Missing mass is relatively larger in the low–reward region. Middle: state value St = (s1 , s2 ) colored by action (blue: a= − 1, red: a= + 1) according to target policy, showing both actions across the state space without obvious coverage gaps. Right: state value St = (s1 , s2 ) colored by missingness (yellow: O=1, purple: O=0); the non-uniform placement of missing points indicates observation probability varies with state.

C.2. Baseline methods for simulation C.2.1. NAIVE FQE In naive FQE baseline, we ignore the missingness mechanism, and perform FQE only on observed samples: 2 X naive b naive = arg min 1 Q Q(St,i , At,i ) − yt,i + λrkhs ∥Q∥2Q(t) , t Q∈Q(t) nt obs i∈It

OPE for Missingness-Aware Policies in MDPs with Rewards Missing Not at Random

where

( Rt,i , t = T, naive yt,i = P naive b Rt,i + a∈A π(a | St+1,i , Ot,i ) Qt+1 (St+1,i , a), t < T.

As discussed in Section 3, under reward MNAR we generally have E[Rt | St = s, At = a, Ot = 1] ̸= E[Rt | St = s, At = a] for some (s, a), so naive FQE, which regresses on observed rewards, can be biased. C.2.2. IPW-FQE We adapt the IPW-based FQE method of Wang et al. (2025) to our reward MNAR setting. Since the true reward Rt is unobserved when Ot = 0, we cannot directly condition the propensity score on Rt . Instead, we first fit an RKHS bridge et , and then estimate the extended propensity score via logistic function b̂t on observed samples (Ot = 1) to obtain R regression on features (St , At , b̂t ): êt (St , At , b̂t ) = P̂ (Ot = 1 | St , At , b̂t ). At each stage t, IPW-FQE solves a weighted kernel ridge regression on the observed subset Itobs : 2 1 X ipw wt,i Q(St,i , At,i ) − yt,i + λrkhs ∥Q∥2Q(t) , Q∈Q(t) nt obs

b ipw Q = arg min t

i∈It

1 where wt,i = êt,i and

ipw yt,i =

( Rt,i , P b ipw (St+1,i , a), Rt,i + a∈A π(a | St+1,i , Ot,i ) Q t+1

t = T, t < T.

C.2.3. I MPUTE -FQE At each step t, we fit a kernel ridge regression on the observed subset to learn the conditional mean of the reward function mt (St , At ). The imputed rewards are then constructed as eimp = Ot,i · Rt,i + (1 − Ot,i ) · m̂t (St,i , At,i ), R t,i eimp in place of Rt,i : and FQE proceeds on all nt samples using R t,i n

2 1 X imp b imp Q(S , A ) − y + λrkhs ∥Q∥2Q(t) , Q = arg min t,i t,i t t,i Q∈Q(t) n i=1 where

( imp yt,i =

eimp , R t = T, t,i P imp imp e b Rt,i + a∈A π(a | St+1,i , Ot,i ) Qt+1 (St+1,i , a), t < T.

Since m̂t is trained only on the observed subset {i : Ot,i = 1}, it estimates E[Rt | St , At , Ot = 1] rather than E[Rt | St , At ]. Under MNAR, the imputed values inherit the selection bias from the observed subsample, leading to biased Q-function estimates. C.2.4. SCOPE SCOPE (Parbhoo et al., 2020) is a per-step importance sampling estimator designed for sparse reward settings, which incorporates potential-based reward shaping (Ng et al., 1999) as a control variate to reduce variance. To apply SCOPE in our MNAR setting, we replace unobserved rewards with zero. This introduces bias because under MNAR, missingness is informative and zero-imputation does not recover the true expected reward. 16

OPE for Missingness-Aware Policies in MDPs with Rewards Missing Not at Random

C.3. Other simulation results

MSE vs T (missingness ~20%)

MSE vs T (missingness ~40%)

MSE vs T (missingness ~80%)

215

217

211

213

MSE (log2 scale)

232 227 222 217 212 27 22 23 28

MSE (log2 scale)

Figure 5 reports MSE as the horizon T varies from 2 to 32. Error compounding in backward induction affects all methods, but the growth rate differs markedly. prox remains below MSE ≈ 1 for T ≤ 16 across all missingness levels, whereas ipw already exceeds 102 at T = 16 under ∼40% missingness. impute is the worst-performing method at longer horizons, with MSE exceeding 108 at T = 32 under ∼20% missingness, because imputation errors at each step feed into subsequent Q-function fits and amplify exponentially. scope is the most competitive baseline for short horizons (T ≤ 4) but its per-step IS weights accumulate variance as T grows. These results highlight that the bridge-function approach in prox is particularly advantageous in long-horizon problems.

27 23 21 25

25 21 23 27

29 21

naive

prox

ipw

impute

scope

T method

Figure 5. MSE vs. horizon length (T ) under three MNAR missingness percentages (∼20%, ∼40%, ∼80%). prox scales most gracefully as T grows, maintaining orders-of-magnitude lower MSE than all baselines. ipw and impute explode at large T due to variance blow-up and compounding imputation errors, respectively. naive grows steadily as MNAR bias compounds at each backward step. scope remains more stable than ipw but degrades sharply under high missingness.

For the reward type comparison, we fix n = 512 and T = 8 and evaluate under the two reward generation mechanisms: a bounded sigmoid reward and a clipped linear reward. Figure 6 compares MSE across the two reward generation mechanisms. Under the sigmoid reward, prox achieves MSE on the order of 10−2 , while the best baseline (naive) is above 10−1 even at ∼20% missingness. The nonlinearity of the sigmoid function makes regression-based imputation particularly difficult, explaining the poor performance of impute on this reward type. Under the linear reward, all methods improve and the gap between prox and baselines narrows. Notably, impute and scope become competitive with prox at ∼80% missingness for the linear reward, suggesting that simpler reward structures are more amenable to naive correction strategies.

MSE by Reward Type (missingness ~40%)

20 22

26 sigmoid

Reward Type

linear

sigmoid naive

21 23

MSE by Reward Type (missingness ~80%)

MSE

MSE by Reward Type (missingness ~20%) 27

prox

Reward Type method ipw

linear impute

sigmoid

Reward Type

linear

scope

Figure 6. MSE by reward type (sigmoid vs. linear) under three MNAR missingness percentages (∼20%, ∼40%, ∼80%). For the sigmoid reward, prox achieves MSE orders of magnitude lower than all baselines. For the linear reward, the gap narrows but prox still leads. impute performs comparably on the linear reward but poorly on sigmoid. scope degrades sharply under high missingness for sigmoid.

OPE for Missingness-Aware Policies in MDPs with Rewards Missing Not at Random

C.4. Additional real data experiment setups The propensity score is set as et (St , At , Rt ) = expit(c0 + 2.0 · Rtstd + 0.3 · Stsignal − 0.1 · Anorm ), t where Rtstd = (Rt − R̄)/sd(R) is the standardized reward, Anorm is the standardized total treatment intensity (sum of t signal vasopressor and IV fluid dose levels, then z-scored), and St is a clinical severity signal defined as the normalized arterial lactate minus half the normalized mean blood pressure. The positive coefficient on the reward (cr = 2.0) ensures that higher rewards are more likely to be observed while lower rewards tend to be missing, reflecting a clinically plausible scenario where SOFA-based outcomes depend on lab measurements that may be ordered less frequently for deteriorating patients. The intercept c0 is calibrated via bisection to achieve target missing rates of 20%, 40%, 60%, and 80%. The target policy is constructed in two stages. First, we train a Double DQN with two hidden layers of size 128 on the original fully-observed data using the 48-dimensional state and γ = 1.0. This produces a greedy base policy πDQN (st ) over the 25 actions. Second, we construct a missingness-aware policy π(a | st , ot−1 ) by applying a conservative dose reduction when the previous reward is unobserved: if Ot−1 = 0, both the vasopressor and IV fluid dose levels recommended by the DQN are reduced by one (clipped at zero). This adjustment reflects a clinically natural response—reducing treatment intensity when the previous outcome is unknown—and produces a target policy whose action distribution depends on Ot−1 , consistent with the policy class in our framework. We split patients 60/40 by ID for model fitting and evaluation, respectively. On the fitting set, we train all OPE models including bridge functions, Q-networks, and auxiliary models for the baselines. Due to the high-dimensional state space and large action space, all methods use neural network function approximation, with architectures of (512, 512, 256) for Q-networks and bridge networks and (256, 256) for auxiliary networks (imputation regressor, propensity classifier). On the held-out 40% test set, we compute the per-patient estimated value V̂i (π) and report the mean and standard error. See detailed experiment results in Table 1. Table 1. OPE results on MIMIC-III sepsis data. We report the estimated policy value V̂ (π) with standard errors and absolute bias relative to oracle FQE. 20% MNAR Method oracle Prox IPW naive impute scope

V̂ (π)

40% MNAR Bias

V̂ (π)

60% MNAR Bias

V̂ (π)

80% MNAR Bias

V̂ (π)

Bias

2.94 ± 0.03 — 2.81 ± 0.03 — 2.46 ± 0.03 — 2.32 ± 0.03 — 2.99 ± 0.03 0.05 3.39 ± 0.03 0.58 3.81 ± 0.03 1.35 4.98 ± 0.03 2.66 4.15 ± 0.03 1.20 5.58 ± 0.03 2.77 7.10 ± 0.03 4.64 11.91 ± 0.04 9.59 4.54 ± 0.03 1.59 5.81 ± 0.03 3.00 7.33 ± 0.03 4.87 11.76 ± 0.03 9.44 6.22 ± 0.03 3.27 9.55 ± 0.04 6.74 13.17 ± 0.04 10.71 20.02 ± 0.06 17.70 10408.2 ± 1991.0 10405.3 −4089.2 ± 786.8 4092.0 10667.9 ± 2037.3 10665.4 −7096.6 ± 1373.6 7099.0

D. Proof of Theorem 3.6 In this section we provide the proof of identification result in Theorem 3.6. Part A: Identification by bridge functions We first show that the policy value can be identified by the bridge functions {bt }Tt=1 if the bridges exist. Fix t ∈ {1, . . . , T } and suppose there exists a measurable function bt : S × A × S → R satisfying the Equation (2). By Assumptions 2.1 and 3.3, conditioning on the event Ot = 1 is well-defined and E[bt (St , At , St+1 ) | Rt , St , At , Ot = 1] = E[bt (St , At , St+1 ) | Rt , St , At ]. So Equation (2) holds if and only if Equation (6) holds. et defined by Equation (4), Equation (5) implies that it has the same conditional mean reward as Rt For the imputed reward R given (St , At ): et | St = s, At = a] = E[bt (s, a, St+1 ) | St = s, At = a] = E[Rt | St = s, At = a] := r̄t (s, a). E[R 18

OPE for Missingness-Aware Policies in MDPs with Rewards Missing Not at Random

Now consider the augmented process. By Assumption 2.2, the augmented process is Markov, and the Bellman recursion holds with one-step reward r̄t (St , At ): π Qπt (s, a) = E r̄t (s, a) + Vt+1 (St+1 , Ot ) | St = s, At = a , X Vtπ (s, o− ) = πt (a | s, o− )Qπt (s, a), VTπ+1 ≡ 0, a

which is equivalent to Equation (1). Therefore, the policy value V (π) = E[V1π (Se1 )] is identified. Part B: Existence of bridge functions We now establish existence of the bridges. For a probability measure µ, let L2 (µ) denote the space of all squared integrable functions of x with respect to measure µ(x), which is a Hilbert space endowed with the inner product ⟨g1 , g2 ⟩ = R g1 (x)g2 (x)dµ(x). For any s, a, t, we define operator Tt|(s,a) : L2 PSt+1 |s,a → L2 PRt |s,a , where (Tt|(s,a) h)(r) := E h(St+1 ) | Rt = r, St = s, At = a . Its adjoint operator is defined by ∗ Tt|(s,a) : L2 PRt |s,a → L2 PSt+1 |s,a , ∗ where (Tt|(s,a) g)(s′ ) = E g(Rt ) | St+1 = s′ , St = s, At = a . Then, the bridge equation (2) can be written as a first-kind Fredholm integral equation (Tt|(s,a) h)(r) = g(r), where the unknown functions are h(·) = bt (s, a, ·) ∈ L2 PSt+1 |s,a and the right hand side is g(r) = r ∈ L2 (PRt |s,a ). Assumption D.1 (Hilbert-Schmidt property). For any (s, a) ∈ S × A, for all t = 1, . . . , T , denote conditional densities pSt+1 |Rt (s′ | r, s, a), pRt |St+1 (r | s′ , s, a). We have Z Z pSt+1 |Rt (s′ | r, s, a)pRt |St+1 (r | s′ , s, a)ds′ dr < ∞. R

This ensures that the operator Tt|(s,a) is Hilbert–Schmidt and thus admits a singular system {(σs,a,t,ν , φs,a,t,ν , ψs,a,t,ν )}ν≥1 ∗ satisfying Tt|(s,a) φs,a,t,ν = σs,a,t,ν ψs,a,t,ν and Tt|(s,a) ψs,a,t,ν = σs,a,t,ν φs,a,t,ν . Assumption D.2. Suppose {(σs,a,t,ν , φs,a,t,ν , ψs,a,t,ν )}ν≥1 is a singular system of Tt|(s,a) . Then for all (s, a) ∈ S × A and t = 1, . . . , T , 2 X g, ψs,a,t,ν L2 (PR |s,a ) t < ∞, 2 σs,a,t,ν ν≥1 R where g, ψs,a,t,ν L2 (P = R g(r) · ψs,a,t,ν (r)pRt |s,a (r)dr. ) Rt |s,a

Lemma D.3 (Picard’s Theorem (Kress, 1989)). Let H1 , H2 be real Hilbert spaces and K : H1 → H2 a compact linear operator with adjoint K ∗ : H2 → H1 . Then, there exists a singular system {(λν , ϕν , ψν )}∞ ν=1 of K, with singular values λν > 0 and orthonormal sequences {ϕν } ⊂ H1 , {ψν } ⊂ H2 satisfying Kϕν = λν ψν ,

K ∗ ψν = λν ϕν .

Given g ∈ H2 , the first–kind Fredholm equation Kh = g has a solution h ∈ H1 if and only if (a) g ∈ ker(K ∗ )⊥ ; P∞ −2 2 (b) ν=1 λν |⟨g, ψν ⟩H2 | < ∞, where ker(K ∗ ) = {h : K ∗ h = 0} is the null space of K ∗ , and ⊥ denotes the orthogonal complement to a set. 19

OPE for Missingness-Aware Policies in MDPs with Rewards Missing Not at Random

Proposition D.4 (Existence of bridges). Under Assumption 3.4 (1), Assumptions D.1 and D.2, for all (s, a) ∈ S × A and t = 1, . . . , T , there exists a solution h to equation Tt|(s,a) h = g, where h := bt (s, a; ·) ∈ L2 PSt+1 |s,a and g(r) = r ∈ L2 (PRt |s,a ). Equivalently, for any fixed (s, a) and t, there exists a function bt (s, a, ·) satisfying Equation (2). Proof. By Assumption D.1, for all (s, a) ∈ S × A and t = 1, . . . , T , the operator Tt|(s,a) is Hilbert–Schmidt and thus ∗ ∗ compact. Suppose there exists function f ∈ ker(Tt|(s,a) ), then by definition, Tt|(s,a) f = 0. By Assumption 3.4 (1), we have ∗ ∗ ⊥ 2 f (Rt ) = 0, a.s. Therefore, ker(Tt|(s,a) ) = {0}, and hence ker(Tt|(s,a) ) = L PRt |s,a . Because reward Rt is bounded, then g ∈ L2 PRt |s,a . So the condition (a) in Lemma D.3 is satisfied. Additionally, condition (b) is also satisfied by Assumption D.2. By Lemma D.3, there exists a solution h ∈ L2 (PSt+1 |s,a ) to Tt|(s,a) h = g where g(r) = r, i.e., there exists function bt (s, a, ·) such that: E bt (s, a, St+1 ) | Rt = r, St = s, At = a = r.

Part C: Uniqueness of bridge functions Next we study the uniqueness of the bridge functions. Proposition D.5 (Uniqueness of bridges). Under Assumption 3.4 (2), any bridge function bt satisfying E[bt (St , At , St+1 ) | Rt , St , At ] = Rt ,

a.s.

is unique. Proof. Suppose there exist different bridge functions b1,t and b2,t satisfying the equation above for any t. Then, E[b1,t (St , At , St+1 ) − b2,t (St , At , St+1 ) | Rt , St , At ] = 0,

a.s.

By Assumption 3.4 (2), we have b1,t − b2,t = 0,

a.s., ∀t = 1, . . . , T,

which contradicts b1,t ̸= b2,t . Thus uniqueness holds.

E. Proof of Theorem 5.5 For a function class G and radius δ > 0, given sample {Xi }, the local empirical Rademacher complexity is defined by b n (G, δ) = Eε R

i 1X εi g(Xi ) {Xi } g∈G:∥g∥2,n ≤δ n i=1 sup

Pn b n (G, δ) ≤ δ2 . where ∥g∥22,n = n1 i=1 g(Xi )2 . The empirical critical radius δ̂n is the smallest solution to the inequality R b Wainwright (2019) gives the relationship of critical radius and empirical critical radius: with probability at least 1 − ζ, r log(1/ζ) δn ≤ O(δ̂n + ), n which enables us to study on empirical critical radius δ̂n . Define Ψtn (b, g) =

1 X obs obs (bt (St,i , At,i , St+1,i ) − Rt,i )gt (Rt,i , St,i , At,i ), nt obs i∈It

OPE for Missingness-Aware Policies in MDPs with Rewards Missing Not at Random

and population level version h i Ψt (b, g) = E (bt (St , At , St+1 ) − Rt )gt (Rt , St , At ) Ot = 1 . Moreover, Let U t 2 2 Ψt,λ (b, g) = Ψ (b, g) − λ ∥g ∥ + ∥g ∥ t G (t) t 2,nt , n n δ2 2 U t,λ t 2 2 Ψ (b, g) = Ψ (b, g) − λ ∥gt ∥G (t) + 2 ∥gt ∥2 . 3 2δ So the minimizer b̂t can be written as b̂t = arg min

2 sup Ψt,λ n (b, g) + λµ∥bt ∥B(t) .

bt ∈B(t) gt ∈G (t)

(t)

By Lemma H.2, with probability at least 1 − ζ, for any function gt ∈ G3U , 1 ∥gt ∥22 + (δtG )2 , 2

∥gt ∥22,nt − ∥gt ∥22 ≤ q

(t) log(c1 /ζ) , and δnGt is the upper bound of the empirical critical radii of function class G3U . For any nt √ (t) ∥gt ∥2G (t) ≥ 3U , consider rescaling gt by ∥gt ∥3U(t) gt ∈ G3U , and we have G

where δtG = δnGt + c0

∥gt ∥22,nt − ∥gt ∥22 ≤

∥gt ∥G (t) 1 ∥gt ∥22 + (δtG )2 . 2 3U

Combine the above inequalities, ∥gt ∥22,nt − ∥gt ∥22

( ) ∥gt ∥2G (t) 1 2 G 2 ≤ ∥gt ∥2 + (δt ) max 1, . 2 3U

(9)

Thus, U ∥gt ∥2G (t) + 2 ∥gt ∥22,nt ≥ ∥gt ∥2G (t) + δ

U (δtG )2

( )# ∥gt ∥2G (t) 1 2 G 2 ∥gt ∥2 − (δt ) max 1, 2 3U

(10)

2 U ∥gt ∥22 − U. ≥ ∥gt ∥2G (t) + 3 2(δtG )2 Next, we study the upper and lower bounds of the centered empirical sup-loss U t t ∗ 2 2 sup Ψn (b̂t , g) − Ψn (bt , g) − 2λ ∥gt ∥G (t) + G 2 ∥gt ∥2,nt . (δt ) gt ∈G (t) For simplicity we omit t and write it as U sup Ψn (b̂, g) − Ψn (b∗ , g) − 2λ ∥g∥2G + 2 ∥g∥22,n . δ g∈G

(11)

E.1. Upper bounding the centered empirical sup-loss We first decompose Ψλn (b, g) by Ψλn (b, g) = Ψn (b, g) − Ψn (b∗ , g) + Ψn (b∗ , g) − λ

≥ Ψn (b, g) − Ψn (b∗ , g) − 2λ ∥g∥2G +

U ∥g∥2G + 2 ∥g∥22,n

U ∥g∥22,n δ2

− sup Ψλn (b∗ , g), g∈G

OPE for Missingness-Aware Policies in MDPs with Rewards Missing Not at Random

where the last inequality holds by symmetry of G. Then we have U 2 ∗ 2 sup Ψn (b̂, g) − Ψn (b , g) − 2λ ∥g∥G + 2 ∥g∥2,n ≤ sup Ψλn (b∗ , g) + Ψλn (b̂, g) δ g∈G g∈G ≤ sup Ψλn (b∗ , g) + sup Ψλn (b∗ , g) + λµ ∥b∗ ∥2B − ∥b̂∥2B g∈G

(12)

g∈G

≤ 2 sup Ψλn (b∗ , g) + λµ ∥b∗ ∥2B − ∥b̂∥2B . g∈G

By Lemma H.3, for all g ∈ G, similarly, with probability at least 1 − ζ we have ∥g∥G ∗ ∗ √ Ψn (b , g) − Ψ(b , g) ≤ 36δ ∥g∥2 + δ max 1, 3U ∥g∥G ≤ 36δ ∥g∥2 + δ(1 + √ ) . 3U

(13)

Combine Equation (10) and Equation (13), we have with probability at least 1 − 2ζ, for all b ∈ B and g ∈ G, U λ ∗ 2 ∗ 2 Ψn (b , g) = Ψn (b , g) − λ ∥g∥G + 2 ∥g∥2,n δ U 2 ∗ ∗ ∗ 2 ≤ Ψ(b , g) + |Ψn (b , g) − Ψ(b , g)| − λ ∥g∥G + 2 ∥g∥2,n δ U ∥g∥ G 2 ∗ 2 ≤ Ψ(b , g) + 36δ ∥g∥2 + δ(1 + √ ) − λ ∥g∥G + 2 ∥g∥2,n δ 3U 2 ∥g∥ U G ∗ 2 2 ≤ Ψ(b , g) + 36δ ∥g∥2 + δ(1 + √ ) − λ ∥g∥G + 2 ∥g∥2,n + λU 3 2δ 3U U λ ∥g∥G U 1 ∥g∥2G + 2 ∥g∥22,n + 36δ 2 + λU + 36δ∥g∥2 + 36δ 2 √ − λ 2 ∥g∥22,n − ∥g∥2G ≤ Ψ(b∗ , g) − λ 3 4δ 4δ 3 3U U λ ∥g∥G = Ψλ/2 (b∗ , g) + 36δ 2 + λU + 36δ∥g∥2 − λ 2 ∥g∥22,n + 36δ 2 √ − ∥g∥2G . 4δ 3 3U

1δ Using the fact that for any a, b > 0 and any norm, supg∈G (a∥g∥ − b∥g∥2 ) ≤ a4b , suppose λ ≥ CU , and then

362 δ 4 362 δ 2 U 2 ∥g∥ ≤ ; ≤ 2,n 4δ 2 λU C1 g∈G 182 δ 4 ∥g∥G λ 182 δ 2 sup 36δ 2 √ − ∥g∥2G ≤ ≤ . 3 λU C1 3U g∈G

sup 36δ∥g∥2 − λ

Therefore, Ψλn (b∗ , g) ≤ Ψλ/2 (b∗ , g) + 36δ 2 + λU +

5 × 182 δ 2 C1

Combine this with Equation (12) we get U sup Ψn (b̂, g) − Ψn (b∗ , g) − 2λ ∥g∥2G + 2 ∥g∥22,n ≤ 2 sup Ψλn (b∗ , g) + λµ ∥b∗ ∥2B − ∥b̂∥2B δ g∈G g∈G 10 × 182 2 )δ + λµ ∥b∗ ∥2B − ∥b̂∥2B C1 g∈G 2 10 × 18 2 = 2λU + (72 + )δ + λµ ∥b∗ ∥2B − ∥b̂∥2B . C1 (14) ≤ 2 sup Ψλ/2 (b∗ , g) + 2λU + (72 +

OPE for Missingness-Aware Policies in MDPs with Rewards Missing Not at Random

E.2. Lower bounding the centered empirical sup-loss By Assumption 5.4, we write gb = arg inf g∈GL2 ∥b−b∗ ∥2 ∥g − T (b − b∗ )∥2 where B

sup

inf

b∈B g∈GL2 ∥b−b∗ ∥2B

∥g − T (b − b∗ )∥2 ≤ η < ∞.

Also, let gb̂ = arg inf g∈GL2 ∥b̂−b∗ ∥2 ∥g − T (b̂ − b∗ )∥2 . B

When ∥gb̂ ∥2 ≤ δ, then ∥T (b̂ − b∗ )∥2 ≤ ∥gb̂ ∥ + ∥g − T (b − b∗ )∥2 ≤ δ + η; if ∥gb̂ ∥2 ≥ δ, let r = 2∥gδ ∥2 ∈ [0, 12 ], and rgb̂ ∈ GL2 ∥b̂−b∗ ∥2 since G is star-shaped. Hence, B

b̂

∗

sup Ψn (b̂, g) − Ψn (b , g) − 2λ

U ∥g∥2G + 2 ∥g∥22,n δ

g∈G

∗

≥ Ψn (b̂, rgb̂ ) − Ψn (b , rgb̂ ) − 2λ

U ∥rgb̂ ∥2G + 2 ∥rgb̂ ∥22,n

δ U = r Ψn (b̂, gb̂ ) − Ψn (b∗ , gb̂ ) −2λ r2 ∥gb̂ ∥2G + 2 ∥gb̂ ∥22,n . δ | {z } | {z }

(i)

(ii)

For (ii), r

U ∥gb̂ ∥2G + 2 ∥gb̂ ∥22,n δ

≤

1 r2 U ∥gb̂ ∥2G + 2 ∥gb̂ ∥22,n . 4 δ

(15)

By Equation (9), with probability at least 1 − ζ, i r2 U 3 ∥g ∥2 r2 U h r2 U 2 2 2 2 ∥g ∥ ≤ ∥g ∥ + ∥g ∥ − ∥g ∥ ∥gb̂ ∥22 + δ 2 (1 + b̂ G ) . ≤ 2 b̂ 2,n b̂ 2 b̂ 2,n b̂ 2 2 2 δ δ δ 2 3U Substitute this into Equation (15) and we get ∥g ∥2 U 1 r2 U 3 r2 ∥gb̂ ∥2G + 2 ∥gb̂ ∥22,n ≤ ∥gb̂ ∥2G + 2 ∥gb̂ ∥22 + δ 2 (1 + b̂ G ) δ 4 δ 2 3U 2 1 1 3U r 1 ≤ ( ∥gb̂ ∥2G + ∥gb̂ ∥2G ) + ∥gb̂ ∥22 + U 2 4 12 2δ 4 1 3 1 2 = ∥gb̂ ∥G + ( + )U 3 8 4 1 2 5 ∗ 2 ≤ L ∥b̂ − b ∥B + U. 3 8

(16)

For (i), we consider function class n o 2 JB,L2 B = ((s, a, s′ ), (r, s, a)) 7→ α(b(s, a, s′ ) − b∗ (s, a, s′ ))gbL B (r, s, a) | b − b∗ ∈ BB , α ∈ [0, 1] , q 2 where gbL B (r, s, a) = arg inf g∈GL2 B ∥g − T (b − b∗ )∥2 . Choose δ = δnJ + c0 log(cn1 /ζ) , where δnJ is the upper bound of the empirical critical radii of function class JB,L2 B . Choose loss function L = (b − b∗ )f , then by Lemma H.3, we have with probability at least 1 − ζ, for all b ∈ B and g ∈ G, |(Ψn (b, gb ) − Ψn (b∗ , gb )) − (Ψ(b, gb ) − Ψ(b∗ , gb ))| ≤ 18δ(∥(b∗ − b)gb ∥2 + δ) ≤ 18δ(∥gb ∥2 + δ), since b − b∗ ∈ BB , which is 1-uniformly bounded. 23

OPE for Missingness-Aware Policies in MDPs with Rewards Missing Not at Random √

When ∥b − b∗ ∥2B > B, we rescale the function by ∥b−bB∗ ∥B (b − b∗ ), and similarly, we obtain that with probability at least 1 − ζ, n ∥b − b∗ ∥2 o B |(Ψn (b, gb ) − Ψn (b∗ , gb )) − (Ψ(b, gb ) − Ψ(b∗ , gb ))| ≤ 18δ(∥gb ∥2 + δ) max 1, . B Therefore, with probability at least 1 − ζ, for any g ∈ G, r Ψn (b̂, gb̂ ) − Ψn (b∗ , gb̂ ) ≥ r Ψ(b̂, gb̂ ) − Ψ(b∗ , gb̂ ) − r|(Ψn (b, gb̂ ) − Ψn (b∗ , gb̂ )) − (Ψ(b, gb̂ ) − Ψ(b∗ , gb̂ ))| n ∥b̂ − b∗ ∥2 o B ≥ r Ψ(b̂, gb̂ ) − Ψ(b∗ , gb̂ ) − 18δr(∥gb̂ ∥2 + δ) max 1, . B {z } | | {z } (A)

(B)

For (A), h i δ E (b̂(S, A, S ′ ) − b∗ (S, A, S ′ ))gb̂ (R, S, A) Ot = 1 2∥gb̂ ∥2 i h δ E gb̂ (R, S, A)E b̂(S, A, S ′ ) − b∗ (S, A, S ′ ) | R, S, A, Ot = 1 Ot = 1 = 2∥gb̂ ∥2 n o δ = E gb̂ (R, S, A) T (b̂ − b∗ )(R, S, A) 2∥gb̂ ∥2 δ E (gb̂ (R, S, A))2 − gb̂ (R, S, A)[gb̂ (R, S, A) − T (b̂ − b∗ )(R, S, A)] = 2∥gb̂ ∥2 o δ n = ∥gb̂ ∥22 − Egb̂ (R, S, A)[gb̂ (R, S, A) − T (b̂ − b∗ )(R, S, A)] 2∥gb̂ ∥2 o δ n ∥gb̂ ∥22 − ∥gb̂ ∥2 ∥gb̂ − T (b̂ − b∗ ))∥2 ≥ 2∥gb̂ ∥2 o δn = ∥gb̂ ∥2 − ∥gb̂ − T (b̂ − b∗ ))∥2 2 o δn ∥T (b̂ − b∗ )∥2 − 2∥gb̂ − T (b̂ − b∗ ))∥2 ≥ 2 o δn ∥T (b̂ − b∗ )∥2 − 2η . ≥ 2

r Ψ(b̂, gb̂ ) − Ψ(b∗ , gb̂ ) =

For (B), n ∥b̂ − b∗ ∥2 o n ∥b̂ − b∗ ∥2 o δ B B 18δr(∥gb̂ ∥2 + δ) max 1, = 18δr( + δ) max 1, B 2r B n ∥b̂ − b∗ ∥2 o B = (9δ 2 + 18rδ 2 ) max 1, B 18δ 2 ∥b̂ − b∗ ∥2B ≤ 18δ 2 + . B So when ∥gb̂ ∥2 ≥ δ, with probability at least 1 − 2ζ, (i) = r Ψn (b̂, gb̂ ) − Ψn (b∗ , gb̂ ) ≥ (A) − (B) ≥

o δn 18δ 2 ∥b̂ − b∗ ∥2B ∥T (b̂ − b∗ )∥2 − 2η − 18δ 2 − . 2 B 24

OPE for Missingness-Aware Policies in MDPs with Rewards Missing Not at Random

Therefore the lower bound of supg∈G Ψn (b̂, g) − Ψn (b∗ , g) − 2λ ∥g∥2G + δU2 ∥g∥22,n is given by U ∗ 2 2 sup Ψn (b̂, g) − Ψn (b , g) − 2λ ∥g∥G + 2 ∥g∥2,n δ g∈G ≥(i) − 2λ(ii) o 18δ 2 ∥b̂ − b∗ ∥2B 1 5 δn − 2λ L2 ∥b̂ − b∗ ∥2B + U ≥ ∥T (b̂ − b∗ )∥2 − 2η − 18δ 2 − 2 B 3 8 2 2 δ 18δ 2λL 5 ≥ ∥T (b̂ − b∗ )∥2 − ηδ − 18δ 2 − ( + )∥b̂ − b∗ ∥2B − λU. 2 B 3 4 E.3. Combining the upper and lower bounds Combine the upper bound and lower bound, and then we have either ∥gb̂ ∥2 ≤ δ, or with probability at least 1 − 3ζ, for all b ∈ B, δ 18δ 2 2λL2 5 10 × 182 2 ∥T (b̂ − b∗ )∥2 − ηδ − 18δ 2 − ( + )∥b̂ − b∗ ∥2B − λU ≤ 2λU + (72 + )δ + λµ ∥b∗ ∥2B − ∥b̂∥2B . 2 B 3 4 C1 So 13 10 × 182 2 2λL2 δ 18δ 2 ∥T (b̂ − b∗ )∥2 ≤ λU + ηδ + λµ ∥b∗ ∥2B − ∥b̂∥2B + (90 + + )∥b̂ − b∗ ∥2B )δ + ( 2 4 C1 B 3 10 × 182 2 2L2 13 18δ 2 ≤ λU + ηδ + λµ ∥b∗ ∥2B − ∥b̂∥2B + (90 + )δ + 2λ( + ) ∥b∗ ∥2B + ∥b̂∥2B . 4 C1 λB 3 2

4L If µ ≥ 36δ λB + 3 , then

10 × 182 2 2 13 λU + ηδ + λµ ∥b∗ ∥2B − ∥b̂∥2B + (90 + )δ + λµ ∥b∗ ∥2B + ∥b̂∥2B δ 4 C1 2 10 × 18 2 13 λU + ηδ + 2λµ∥b∗ ∥2B + (90 + )δ 2 = δ 4 C1 13 λU λµ 20 × 182 ≤ + 2η + 4 ∥b∗ ∥2B + (180 + )δ. 2 δ δ C1

∥T (b̂ − b∗ )∥2 ≤

2δ , then with probability at least 1 − 4ζ, Suppose λ ≤ CU

13 λU λµ 20 × 182 + 2η + 4 ∥b∗ ∥2B + (180 + )δ 2 δ δ C1 13 20 × 182 ≤ C2 δ + 2η + 4C2 µδ∥b∗ ∥2B + (180 + )δ 2 C1 13 20 × 182 ≤ 4C2 µδ∥b∗ ∥2B + C2 + 180 + δ + 2η 2 C1 n o ≲ δ max 1, ∥b∗ ∥2B .

∥T (b̂ − b∗ )∥2 ≤

F. Proof of Corollary 5.6 Recall that the product class is denoted by n o (t) (t) L2 B JB,L2 B := ((s, a, s′ ), (r, s, a)) 7→ α(bt (s, a, s′ ) − b∗t (s, a, s′ ))gb,t (r, s, a) | bt − b∗t ∈ BB , α ∈ [0, 1] . (t) Define the tensor product of two RKHSs B (t) and G (t) as H⊗ endowed with kernel K⊗,t (x, y), (x′ , y ′ ) := (t) KB,t (x, x′ ) KG,t (y, y ′ ). Then, one can verify that JB,L2 B satisfies n o p p (t) (t) (t) JB,L2 B ⊆ f ∈ H⊗ : ∥f ∥H(t) ≤ Bt L2 Bt =: H⊗,LB . ⊗

OPE for Missingness-Aware Policies in MDPs with Rewards Missing Not at Random

By Lemma H.5, we have that r

(t)

Rnt (JB,L2 B , δ) ≤ LB

v uX ∞ X ∞ 2u G 2 . t min µB t,i µt,j , δ nt i=1 j=1

(17)

−2αB Under the polynomial eigen decay assumptions µB and µGt,j ≲ j −2αG with αmin := min{αB , αG }, by t,i ≲ i Lemma H.6, the tensor-product spectrum admits the bound ∞ X ∞ X

G 2 min{µB t,i µt,j , δ } ≲ δ

2− α 1

min

i=1 j=1

plugging this into Equation (17) yields

1 log . δ

− 2α min+1

δnJt ≲ LB nt

min

Similarly, we have

log nt .

δnGt ≲

− 2α G+1

Ut nt

log nt .

Therefore, δnt = max{δnGt , δnJt } satisfies δnt ≲ max{

α p − 2α min+1 Ut , LB} nt min log nt ,

and the claim follows by Theorem 5.5. The min-max estimation problem of bt has a closed-form solution, which is discussed in Dikkala et al. (2020) Appendix E.3.

G. Proof of Theorem 5.9 G.1. Error Decomposition The estimation error bound can be decomposed as |E[V1π ] − Vb (π)| ≤ |E[V1π ] − En [V1π ]| + |E[V1π ] − E[Vb1π ]| + |E(V1π − Vb1π ) − En (V1π − Vb1π )|, | {z } | {z } | {z } (I)

(II)

(III)

Pn 1

where En [V1π ] := n

π i=1 V1 (S1,i , 0).

G.2. Bound of (I) For (I), since rewards are bounded in [−1, 1], by Hoeffding inequality, with probability at least 1 − ζ, r r log(c1 /ζ) log(c1 /ζ) π π π |E[V1 ] − En [V1 ]| ≲ ∥V1 ∥∞ ≤T , n n where constant c1 > 0. G.3. Bound of (II) For (II), |E[V1π ] − E[Vb1π ]| ≤ ∥V1π − Vb1π ∥2 X b 1 (S1 , a))∥2 =∥ π1 (a | S1 , O0 )(Qπ1 (S1 , a) − Q a

X 1/2 b 1 (S1 , a)) 2 = E π1 (a | S1 , O0 = 0)(Qπ1 (S1 , a) − Q a

X 1/2 b 1 (S1 , a))2 ≤ E π1 (a | S1 , O0 = 0)(Qπ1 (S1 , a) − Q a

b 1 ∥2,π , := ∥Qπ1 − Q 26

OPE for Missingness-Aware Policies in MDPs with Rewards Missing Not at Random π where Qπt (s, a) = E(Rt + Vt+1 | s, a). Since there is no shift on marginal distributions of states d˜πt and d˜bt when t = 1, by Assumption 2.3,

b 1 ∥22,π = E ∥Qπ1 − Q (S1 ,O0 )∼d˜π

= E(S1 ,O0 )∼d˜b

b 1 (S1 , a))2 π1 (a | S1 , O0 = 0)(Qπ1 (S1 , a) − Q

a 1

b 1 (S1 , a))2 π1 (a | S1 , O0 = 0)(Qπ1 (S1 , a) − Q

≤ κ1 E(S1 ,O0 )∼d˜b

b 1 (S1 , a))2 π1b (a | S1 )(Qπ1 (S1 , a) − Q

b 1 ∥2 b , := κ1 ∥Qπ1 − Q 2,π b 1 ∥2 instead of ∥Qπ − Q b 1 ∥2 b . Q b t is estimated from penalized nonparametric least and for simplicity we write ∥Qπ1 − Q 2 1 2,π square problem Equation (8). b t − Qπ ∥2 involves the estimation error of the fitted Q-functions produced by FQE. Unlike standard supervised regression, ∥Q t the regression targets in FQE are pseudo-labels that depend on nuisance estimates and on future-stage fitted values. Concretely, at stage t < T , the target takes the form be bπ yt,i = R t,i + Vt+1 (St+1,i , Ot,i ), be bπ b where R t,i depends on the estimated bridge b̂t and Vt+1 depends on Qt+1 . Therefore, the regression noise and the b t − Qπt ∥2 typically leads regression function are statistically coupled through the common data, and a direct analysis of ∥Q to non-negligible cross terms that are difficult to control without additional device such as sample splitting or cross-fitting. b∗ , To decouple the effect of nuisance estimation from the intrinsic regression error, we introduce an oracle comparator Q t ∗ b defined as the solution of the same penalized regression problem as Qt but trained on an oracle pseudo-label yt , in which the nuisance components are replaced by their population counterparts. n

X ∗ 2 b ∗t = arg min 1 f (St,i , At,i ) − yt,i + λQ,t ∥f ∥2Q(t) , Q (t) n i=1 f ∈Q where ( ∗ yt,i =

et,i , R et,i + V π (St+1,i , Ot,i ), R t+1

π and Vt+1 (St+1,i , Ot,i ) =

t = T, t < T,

π a πt+1 (a | St+1 , Ot )Qt+1 (St+1 , a).

Then we have b t − Qπ ∥2 = ∥(Q bt − Q b ∗ ) + (Q b ∗ − Qπ )∥2 ∥Q t t t t b ∗ − Qπ ∥2 . bt − Q b ∗t ∥2 + ∥Q ≤ ∥Q | {z } | t {z t } (a)

(b)

bt , Q b ∗t are estimated from Equation (8) and Equation (18), it can be verified that For (a), since Q bt − Q b ∗t ∥2,n ≤ ∥yt − yt∗ ∥2,n ≤ ∥Q

√

√ be π π e 2∥R 2∥Vbt+1 − Vt+1 ∥2,n . t − Rt ∥2,n +

Since be ∗ ∗ e ∥R t − Rt ∥2,n = ∥(1 − Ot )(b̂t − bt )∥2,n ≤ ∥b̂t − bt ∥2,n , 27

(18)

OPE for Missingness-Aware Policies in MDPs with Rewards Missing Not at Random

and π π ∥Vbt+1 − Vt+1 ∥2,n :=

b t+1 (St+1 , a) − Qπ (St+1 , a) πt+1 (a | St+1 , Ot ) Q t+1

= ≤

n 1 X X

n i=1

1/2 b t+1 (St+1,i , a) − Qπt+1 (St+1,i , a) 2 πt+1 (a | St+1,i , Ot,i ) Q

n X 1 X

n i=1

2,n

1/2 b t+1 (St+1,i , a) − Qπt+1 (St+1,i , a) 2 πt+1 (a | St+1,i , Ot,i ) Q

b t+1 − Qπ ∥2,n,π , :=∥Q t+1 then bt − Q b ∗ ∥2,n ≤ ∥Q t

√

2∥b̂t − b∗t ∥2,n +

√

b t+1 − Qπ ∥2,n,π . 2∥Q t+1

(19)

Since Q(t) is (T − t + 1)-uniformly bounded, we consider scaling Q(t) by (T − t + 1) for convenience. According to Fischer & Steinwart (2020), under mild conditions, the RKHS norm of kernel ridge regression estimators (t) is bounded with high probability. and construct RKHS ball QRQ = {Q ∈ Q(t) : ∥Q∥Q(t) ≤ RQ } for all t = 1, . . . , T . (t)

Denote difference class ∆Q(t) := {∆Q | ∆Q = Q1 − Q2 , Q1 , Q2 ∈ QRQ }. Let δ̄∆(t) ,n be the upper bound of the Q

empirical critical radii of scaled function class ∆Q(t) . For RKHS B (t) , Proposition 9 in Dikkala et al. (2020) gives the closed form of the inner maximization, which implies (t) that ∥b̂t ∥B(t) can be bounded by a constant RB . Thus, consider RKHS ball BRB = {bt ∈ B (t) , ∥bt ∥B(t) ≤ RB }. Define (t)

difference class ∆B (t) = {∆b = b1 − b2 , b1 , b2 ∈ BRB } and let δ̄∆(t) ,n be the upper bound of the empirical critical radii b q of ∆B (t) . Then, we define δ̄∆t = max{δ̄∆(t) ,n , δ̄∆(t+1) ,n , δ̄∆(t) ,n } where δ∆t = δ̄∆t + c0 log(cn1 /ζ) for some c0 , c1 > 0. Qh Q b i P b t+1 − Qπ ∥2 b t+1 (St+1 , a) − Qπ (St+1 , a) 2 . π (a | S , O ) Q Let ∥Q := E b ˜ t+1 t+1 t t+1 2,b,π t+1 a∈A (St+1 ,Ot )∼d t+1

Applying Lemma H.2 on both sides of Equation (19), we have with probability at least 1 − ζ, bt − Q b ∗t ∥2 ≲∥b̂t − b∗t ∥2 + ∥Q b t+1 − Qπt+1 ∥2,b,π + (T − t + 1)δ∆ ∥Q t √ ∗ π b (Assumption 2.3 (2)) ≲∥b̂t − bt ∥2 + κt+1 ∥Qt+1 − Q ∥2 + (T − t + 1)δ∆ . t+1

(20)

(b) corresponds to a standard penalized least square estimation error. Since ∥Q∗t ∥Q(t) is bounded, by Lemma H.7, with probability at least 1 − ζ, (b) is bounded by b ∗ − Qπ ∥2 ≲ (δ (t) + ∥Q t t ∆

p λQ,t )(T − t + 1),

where δ∆(t) = δ∆(t) ,n + c0 Q

log(c1 T /ζ) for some c0 , c1 > 0. n

Therefore, with probability at least 1 − ζ/T ,

b t − Qπt ∥2 ≤ ∥Q bt − Q b ∗t ∥2 + ∥Q b ∗t − Qπt ∥2 ∥Q p √ b t+1 − Qπ ∥2 + (T − t + 1)δ∆ + (δ (t) + λQ,t )(T − t + 1). ≲ ∥b̂t − b∗t ∥2 + κt+1 ∥Q t+1 t ∆ Q

OPE for Missingness-Aware Policies in MDPs with Rewards Missing Not at Random

Applying backward induction from t = T down to t = 1 yields the bound for (II) with probability at least 1 − ζ: |E[V1π ] − E[Vb1π ]| ≤∥V1π − Vb1π ∥2 √ b 1 − Qπ ∥2 ≤ κ1 ∥Q 1

T Y T i X p √ h ≲ κj ∥b̂t − b∗t ∥2 + (T − t + 1)δ∆t + (δ∆(t) + λQ,t )(T − t + 1) t=1

≲K

j=1

T h X

τt δt (1 + ∥b∗t ∥2B(t) ) + (δ∆t + δ∆(t) +

i p λQ,t )(T − t + 1) .

t=1

G.4. Bound of (III) (t) (t) For (III), we first define function class ∆V (t) = ∆ = V1 − V2 | V1 , V2 ∈ VRV , where VRV is a (T − t + 1)-uniformly (t)

(t)

bounded function class of value functions at time t, induced from Q(t) under operator Πt : VRV = {Πt Q : Q ∈ QRQ }. Here P linear operator Πt is defined as (Πt Q)(s, o−) = πt (a | s, o− )Q(s, a). We choose the cost function as L(f (X), Y ) = (t) f (X) and apply Lemma H.1. We here also scale VRV by (T − t + 1). Then, with probability at least 1 − ζ, |E(V1π − Vb1π ) − En (V1π − Vb1π )| ≲ δ∆(1) (∥V1π − Vb1π ∥2 + T δ∆(1) ), V

where δ∆(1) = δ̄∆(1) ,n + c0 V

log(c1 /ζ) , and δ̄∆(1) ,n is the upper bound of the empirical critical radii of scaled function class n V

∆V (1) . Moreover, δ∆(1) ≤ δ∆(1) . V

G.5. Policy value error bound Combine the above inequalities, we obtain the policy value estimation error bound with probability at least 1 − ζ: Vb (π) − V (π) ≤(I) + (II) + (III) r log(c1 T /ζ) + (δ∆(1) + 1)∥V1π − Vb1π ∥2 + T (δ∆(1) )2 ≲T V V n r h log(c1 T /ζ) ≲T + T (δ∆(1) )2 + K(δ∆(1) + 1) τt δt (1 + ∥b∗t ∥2B(t) )+ V V n i p (δ∆t + δ∆(t) + λQ,t )(T − t + 1) Q r h log(c1 T /ζ) ≲T + T (δ∆(1) )2 + K(δ∆(1) + 1) τt δt (1 + ∥b∗t ∥2B(t) )+ V V n i (T − t + 1)δt,∗ r T X log(c1 T /ζ) ≲T + Kτmax T δt,∗ , n t=1

(t)

where δt,∗ as the maximum of the critical radii of difference classes ∆Q(t) , ∆Q(t+1) , ∆B (t) , and GU for t = 1, . . . , T , namely δ∆(t) , δ∆(t+1) , δ∆(t) and δG(t) . Q

With polynomial decay −2αQ µQ , t,j ≲ j

−2αB µB , t,j ≲ j

µGt,j ≲ j −2αG , 29

αQ , αB , αG > 1/2,

OPE for Missingness-Aware Policies in MDPs with Rewards Missing Not at Random

the corresponding critical radii satisfy 1 2α

δ∆(t) , δ∆(t+1) ≲ RQ Q Q

− 2α Q+1 Q

log n,

1 2α

δ∆(t) ≲ RB B

− 2α B+1 B

log n,

1 2αG +1

δG(t) ≲ Ut

− 2α G+1 G

log n.

Thus, the critical radius δt,∗ satisfies p p αmin p − δt,∗ ≲ max{ RQ , RB , Ut }n 2αmin +1 log n, where αmin = min{αQ , αB , αG }. Therefore, with probability at least 1 − ζ, the policy value is bound by αmin p − Vb (π) − V (π) ≲ Kτmax T 2 log(c1 T /ζ)n 2αmin +1 log n.

H. Auxiliary lemmas Lemma H.1 (Wainwright (2019), Theorem 14.20). Suppose function class F is symmetric, 1-uniformly bounded, and star-shaped around f ∗ . Let δn2 ≥ nc be any solution to the inequality Rn (F ∗ , δ) ≤ δ 2 , where F ∗ = {f − f ∗ | f ∈ F}. Suppose the cost function L(f (X), Y ) is L-Lipschitz in its first argument f (X). Then for all f ∈ F, with probability at 2 least 1 − c1 e−c2 nδn , we have |En L(f (x), y) − L(f ∗ (x), y) − E L(f (x), y) − L(f ∗ (x), y) | ≤ 10Lδn ∥f − f ∗ ∥2 + δn . Lemma H.2 (Wainwright (2019), Theorem 14.1). Given a star-shaped and b-uniformly bounded function class F, set 2 2 δn > 0 be any solution to R(F, δ) ≤ δb . Then for any t ≥ δn , with probability at least 1 − c1 exp(−c2 nt b2 ), we have ∥f ∥22,n − ∥f ∥22 ≤

1 1 ∥f ∥22 + t2 2 2

for all f ∈ F. Lemma H.3 (Foster & Syrgkanis (2023), Lemma 14). Consider a 1-uniformly bounded and star-shaped function class n) F, and pick any f ∗ ∈ F. Let δn2 ≥ c1 log(log be any solution to the inequalities Rn (Ft∗ , δ) ≤ δ 2 for all t ∈ {1, . . . , d}, n ∗ ∗ where Ft = {ft − ft | ft ∈ F|t }. Assume Lf is L-Lipschitz in its first argument f with respect to its ℓ2 norm. Then for all 2 f ∈ F, for some universal constants c2 , c3 > 0, with probability at least 1 − c2 e−c3 nδn , we have |En Lf − Lf ∗ ) − E Lf − Lf ∗ | ≤ 18Ldδn ∥f − f ∗ ∥2 + δn . The outcome fˆ of constrained ERM satisfies that with the same probability, En Lfˆ − Lf ∗ ) ≤ 18Ldδn ∥fˆ − f ∗ ∥2 + δn . Lemma H.4 (Wainwright (2019), Example 3.5). Let ε = (ε1 , . . . , εn ) be i.i.d. Rademacher variables taking values in {−1, +1} with equal probability. Let A ⊂ Rn be any (possibly infinite) bounded set, and define Z(A) := sup ⟨a, ε⟩ = sup a∈A

a∈A

n X

ak εk .

k=1

Let W (A) := supa∈A ∥a∥2 . Then for all t > 0, P Z(A) ≥ E[Z(A)] + t ≤ exp −

t2 . 16 W (A)2

Moreover, since −Z(A) = inf a∈A ⟨a, ε⟩ and the same argument applies, P |Z(A) − E[Z(A)]| ≥ t ≤ 2 exp − 30

t2 . 16 W (A)2

OPE for Missingness-Aware Policies in MDPs with Rewards Missing Not at Random

Lemma H.5 (Wainwright (2019), Corollary 14.5). Let H be an RKHS with reproducing kernel K and let F := {f ∈ H : ∥f ∥H ≤ 1} be the unit ball. Let {µj }∞ j=1 denote the non-increasing eigenvalues. Then the local Rademacher complexity satisfies, for any δ > 0, 1/2 r ∞ X 2 min{µj , δ 2 } . Rn (F, δ) ≤ n j=1 Moreover, let {µ̂j }nj=1 denote the eigenvalues of the renormalized kernel matrix K ∈ Rn×n with entries Kij = K(xi , xj )/n. Then the local empirical Rademacher complexity satisfies, for any δ > 0, r b n (F, δ) ≤ R

 1/2 n 2 X min{b µj , δ 2 } . n j=1

Lemma H.6 (Krieg (2018), Theorem 1(i)). Let σ : N → R+ be a non-increasing sequence with σ(n) → 0. For d ∈ N, define its d-th tensor power d Y σd (n1 , . . . , nd ) = σ(nk ), (n1 , . . . , nd ) ∈ Nd , k=1

and let τ : N → R+ be the non-increasing rearrangement of {σd (n1 , . . . , nd )}(n1 ,...,nd )∈Nd . If for some s > 0 one has σ(n) ≲ n−s , then τ (n) ≲ n−s (log n)s(d−1) . Lemma H.7 (Rademacher analogue of Wainwright (2019), Theorem 13.17). Let (xi , yi )ni=1 be i.i.d. with yi = f ∗ (xi ) + ξi , where E[ξi | xi ] = 0 and ξi is conditionally σ-sub-Gaussian. Let F be a symmetric, star-shaped class equipped with a Hilbert norm ∥ · ∥F . Consider the penalized least squares estimator ) ( n X 1 (yi − f (xi ))2 + λn ∥f ∥2F . fˆ ∈ arg min f ∈F 2n i=1 Suppose f ∗ ∈ F and ∥f ∗ ∥F ≤ R. Define the localized difference class G := {∆ = f − f ∗ : f ∈ F, ∥f ∥F ≤ R}. and the local empirical Rademacher complexity " b n (G, δ) := Eε R

1X sup εi ∆(xi ) ∆∈G:∥∆∥2,n ≤δ n i=1

# x1:n .

q 2 b n (G, δ̄n ) ≤ δ̄n , and define δn = δ̄n + c0 σ log(c1 /ζ) for some Let δ̄n be the upper bound of the critical radii satisfying R 32σ n numerical constants c0 , c1 > 0. Assume that λn ≥ 34 δn2 , then there exist constant C1 > 0 such that, with probability at least 1 − ζ, ∥fˆ − f ∗ ∥22 ≤ C1 R2 δn2 + λn .

Record · ID 290604 · SHA-256 c0ee4b2218bed0ca
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.