betaFeedback

WorksMathematics

Reinforcement Learning Under Runtime Confounding: Policy Learning and Off-Policy Evaluation

Abstract

Reinforcement learning (RL) is increasingly used to train robust, adaptable systems across healthcare, e-commerce, and robotics. In these settings, legal, ethical, or logistical concerns may preclude certain key variables that drive decisions from being collected during deployment time. This gives rise to a setting known as runtime confounding: the logged data hold full observability, but deployment time lacks knowledge of certain variables, known as runtime confounders. Unlike single timepoint and non-adaptive settings, runtime confounding under reinforcement learning has the potential to propagate over time, as earlier decisions affect future states, observations, and action assignments, leading to biased learning. We address these problems with three contributions: we (1) develop policy learning algorithms under runtime-confounding, (2) develop semi-parametric efficient off-policy estimation procedures, and (3) provide diagnostics for understanding the price of runtime confounding.

Introduction

Sequential decision-making rules are often deployed in settings with less information than was available during training. For example, a clinical decision-support tool may be trained on records that include laboratory results, clinician notes, or socioeconomic variables, but some of these variables that relate to sensitive subgroup classification, such as socioeconomics, may not be allowed as inputs when the tool is deployed to protect against discriminative profiling. This problem can occur in other settings with high-stakes decision-making, such as adjusting credit limits or child welfare screening. Despite having knowledge of all variables that influence outcomes in historical logs, during deployment time, one may not have access to an individual’s protected attributes for ethical, legal, or logistical reasons. More formally, these variables observed in historical data but are unavailable at deployment are known as runtime confounders, and the setting of misaligned logging data and deployment data is referred to as runtime confounding [6].

While a large part of reinforcement learning (RL) literature studies a related problem of unobserved confounding, to the best of our knowledge, no work studies runtime confounding precisely. More precisely, past work assume both logging and deployment lack confounders, and handle the non-identifiability with a range of approaches including causal bounds and online identification [2] (Zhang and Bareinboim 2019), sensitivity analysis [9, 14], and proximal or partially observable formulations [16, 4, 18]. In runtime confounding, the difficulty lies in the fact that the deployed policy can only condition on a variable set that does not include the runtime confounders, leading to a different policy class than that used in the historical data and violations to sequential randomization during deployment. Coston et al. [6] address runtime confounding in single-period counterfactual prediction, and recent work studies a conformal prediction approach in the same setting [3].

We address this gap by proposing a semiparametric-efficient framework for policy learning and off-policy evaluation under runtime confounding. The key observation is that the runtime restriction enters only through the numerator of an importance ratio. Hence, one may take a reweighting approach to recover the value of any policy in the runtime-confounding policy class, with all nuisances estimated from the full data. As a result, reinforcement learning under runtime confounding can fit within the ideas of doubly robust off-policy evaluation [7, 17, 8, 19] with cross-fitted nuisances [5], as well as the literature on dynamic treatment regimes for restricted policies [12, 15] and the broader literature on policy learning with observational data [1].

Our contributions are as follows.

  1. Policy learning. We propose a doubly robust policy learning algorithm for reinforcement learning under runtime confounding over a class of runtime deployable policies (Algorithm 1). Its regret relative to the full-information optimum is an irreducible runtime regret gap and efficient rates (Theorem 3).

  1. Semiparametric-Efficient Off-Policy Evaluation. For a fixed runtime policy, we propose a doubly-robust estimator that is asymptotically normal and attains the semiparametric efficiency bound, yielding valid confidence intervals and testing procedures (Theorem 2).

  1. Diagnosing and Characterizing the Price of Runtime Confounding. Because the runtime confounders are logged, we can test the price of runtime confounding. We propose a test for the irreducible runtime regret gap, giving a decision-relevant quantity for having to accept or choosing these runtime confounders.

Problem Setting

Notation

We consider a setting where we have complete observation logging data available over i∈[n]i \in[n] sample trajectories and t∈[T]t \in[T] timepoints. Trajectories are denoted by

O=(S1,A1,R1,…,ST,AT,RT),St=(Xt,Ut)∈SO = (S_1, A_1, R_1, \ldots, S_T, A_T, R_T), \qquad S_t = (X_t, U_t) \in\mathcal{S}

where StS_t is the full-state consisting of XtX_t (available at deployment) and UtU_t (recorded in the logs, but unavailable at runtime), At∈AA_t \in\mathcal{A} is the action, and Rt∈RR_t \in\mathbb{R} is the reward, bounded by Rmax⁡R_{\max}. Define the histories

Ht=(S1,A1,R1,…,St−1,At−1,Rt−1,St),HtX=(X1,A1,R1,…,Xt−1,At−1,Rt−1,Xt)H_t = (S_1, A_1, R_1, \ldots, S_{t-1}, A_{t-1}, R_{t-1}, S_t), \qquad H_t^X = (X_1, A_1, R_1, \ldots, X_{t-1}, A_{t-1}, R_{t-1}, X_t)

so that HtXH_t^X is the runtime version of the history, or HtH_t with each full state SsS_s replaced by its runtime component XsX_s. The observed data are generated by a logging policy πb(⋅∣Ht)\pi_b(\cdot\mid H_t) which we allow to be known or unknown by the researcher, where rewards and states are generated according to Rt∼pt(⋅∣Ht,At)R_t \sim p_t(\cdot\mid H_t, A_t) and St+1∼pt(⋅∣Ht,At,Rt)S_{t+1} \sim p_t(\cdot\mid H_t, A_t, R_t), respectively. Importantly, during deployment UtU_t is unavailable so that newer target policies which depend on UtU_t are infeasible. Figure 1 outlines our problem setting.

Problem setting diagram showing historical data and deployment

Figure 1. Problem setting. UtU_t is observed in the historical data, but unmeasured during deployment and in turn unavailable to the target policy.

We occasionally write AtπA_t^\pi to make dependence on the policy π\pi explicit, though we often omit this notation for brevity. Letting aˉs=a1,…,as\bar{a}_s = a_1, \ldots, a_s denote a fixed sequence of actions, we let Rt(aˉt)R_t(\bar{a}_t) denote the counterfactual reward under action sequence aˉt\bar{a}_t, and similarly let St(aˉt−1)S_t(\bar{a}_{t-1}) denote the counterfactual state at time tt that would be observed under action sequence aˉt−1\bar{a}_{t-1}.

Target Parameters and Identification

Our target is the γ\gamma-discounted objective function under a fixed policy π\pi:

J(π)=Eπ[∑t=1Tγt−1Rt](1)J(\pi) = \mathbb{E}_{\pi}\left[\sum_{t=1}^{T} \gamma^{t-1} R_t\right] \tag*{(1)}

In RL, one typically seeks to learn an optimal policy, and evaluate fixed policies, which act on the full history HtH_t, or current contexts StS_t and any relevant past information. What makes runtime confounding unique compared to standard RL settings is that we do not observe UtU_t at runtime, so policies that require UtU_t are infeasible. In turn, we instead aim to perform inference and learning over the policy class which acts only over the variables available at runtime:

ΠX={π=(πt)t≤T:πt(⋅∣HtX), σ(HtX)-measurable}\Pi_{\mathrm{X}} = \left\{ \pi= (\pi_t)_{t \le T} : \pi_t(\cdot\mid H_t^{\mathrm{X}}),\ \sigma(H_t^{\mathrm{X}})\text{-measurable} \right\}

Importantly, J(π)J(\pi) is not immediately identified for policies π\pi other than the logging policy πb\pi_b that generated the observed data. We assume the following identification conditions to identify J(π)J(\pi) for any π∈ΠX\pi\in\Pi_{\mathrm{X}}.

(Id1) Sequential ignorability. For all t∈[T]t \in[T], and for any generic action sequence aˉT=(a1,…,aT)\bar{a}_T = (a_1,\ldots,a_T),

Rt(aˉt),…,RT(aˉT),St+1(aˉt),…,ST(aˉT−1)⊥ ⁣ ⁣ ⁣⊥At∣HtR_t(\bar{a}_t),\ldots,R_T(\bar{a}_T),S_{t+1}(\bar{a}_t),\ldots,S_T(\bar{a}_{T-1}) \perp\!\!\!\perp A_t \mid H_t

(Id2) Consistency: St=St(Aˉt−1)S_t = S_t(\bar{A}_{t-1}) and Rt=Rt(Aˉt)R_t = R_t(\bar{A}_t) for all tt.

(Id3) Overlap. πb(a∣Ht)≥ηg>0\pi_b(a \mid H_t) \ge\eta_g > 0 for all a∈Aa \in\mathcal{A} and t∈[T]t \in[T].

(Id1) – (Id3) are standard identification assumptions in policy learning [13, 20] and reinforcement learning [8].

With these identification assumptions, one can identify J(π)J(\pi) from the observed data. Let the superscript RC denote the runtime version of any fixed object. Then define the runtime importance ratio as:

ρ1:tRC=∏s=1tλsRC,for λsRC=πs(As∣HsX)πb(As∣Hs)(2)\rho_{1:t}^{\mathrm{RC}} = \prod_{s=1}^{t} \lambda_s^{\mathrm{RC}}, \qquad\text{for } \lambda_s^{\mathrm{RC}} = \frac{\pi_s(A_s \mid H_s^{\mathrm{X}})}{\pi_b(A_s \mid H_s)} \tag*{(2)}

Here, the importance weight takes a particular form: In contrast to the non RC setting which uses ρ1:t=∏s=1tπs(As∣Ss)πb(As∣Hs)\rho_{1:t} = \prod_{s=1}^{t} \frac{\pi_s(A_s \mid S_s)}{\pi_b(A_s \mid H_s)}, the RC importance weight has the numerator correspond to runtime-confounded quantities while the denominator is the full information policy. For t=T,…,1t = T,\ldots,1, we then recursively define the Q- and Value function.

Qtπ(Ht,a)=Eπb[Rt+γVt+1π(Ht+1)∣Ht,At=a]Q_t^\pi(H_t,a) = \mathbb{E}_{\pi_b}\left[R_t + \gamma V_{t+1}^\pi(H_{t+1}) \mid H_t,A_t=a\right]
Vtπ(Ht)=∑aπt(a∣HtX)Qtπ(Ht,a)V_t^\pi(H_t) = \sum_a \pi_t(a \mid H_t^{\mathrm{X}})Q_t^\pi(H_t,a)

where VT+1π=0V_{T+1}^\pi= 0. Again, the primary difference is the action density that we marginalize over—a runtime policy.

Under Assumptions (Id1)-(Id3), J(π)J(\pi) is identified by the observed data functionals:

J(π)=Eπb[V1π(H1)]=Eπb[∑t=1Tγt−1ρ1:tRCRt](3)J(\pi) = \mathbb{E}_{\pi_b}[V_1^\pi(H_1)] = \mathbb{E}_{\pi_b}\left[\sum_{t=1}^{T}\gamma^{t-1}\rho_{1:t}^{\mathrm{RC}}R_t\right] \tag*{(3)}

Importantly, the identifying functional in (3) does not discard the historical UtU_t. Discarding variables that unavailable at runtime is a common practice in data science and machine learning ([6]), but will tend to yield invalid identifying functionals when the discarded variables are truly confounders. Specifically, focusing on the importance-weighted identifying functional in (3), if we were to to instead use the importance weights

ρ1:tX=∏s=1tλsX,whereλsX=πs(As∣HsX)πb(As∣HsX)\rho^X_{1:t} = \prod_{s=1}^{t} \lambda^X_s, \qquad\text{where} \qquad\lambda^X_s = \frac{\pi_s(A_s \mid H^X_s)}{\pi_b(A_s \mid H^X_s)}

the resulting identifying functional would generally not equal J(π)J(\pi). In turn, standard methods for both policy learning and inference ([8]) that naively estimate this functional would target the wrong parameter inducing unintended bias.

Efficient Estimation and Policy Learning

Both policy-learning and off-policy estimation will build on the efficient influence function (EIF) for the identifying functional (3) of the target parameter J(π)J(\pi). EIFs are crucial ingredients for constructing estimators of statistical parameters, and enable valid n\sqrt{n} asymptotic inference even when estimators of underlying nuisance functions themselves converge at slower rates ([10]). Throughout, we will estimate the EIF of J(π)J(\pi) using nuisance models for the propensity and the conditional outcome model, denoted by η=(πb(⋅∣Ht),{Qtπ(Ht,⋅)})\eta= (\pi_b(\cdot\mid H_t), \{Q^\pi_t(H_t,\cdot)\}). Writing δtπ=Rt+γVt+1π(Ht+1)−Qtπ(Ht,At)\delta^\pi_t = R_t + \gamma V^\pi_{t+1}(H_{t+1}) - Q^\pi_t(H_t,A_t) for the Bellman residual, the efficient influence function of JJ at fixed π∈ΠX\pi\in\Pi_X is given by the following Theorem:

Theorem 1 (Efficient Influence Function under Runtime-Confounding) Fix π∈ΠX\pi\in\Pi_X. Under our assumptions ((Id1)-(Id3)), the efficient influence function of J(π)J(\pi) is

φ(O;π,η)=V1π(H1)−J(π)+∑t=1Tγt−1ρ1:tRCδtπ(4)\varphi(O;\pi,\eta) = V^\pi_1(H_1) - J(\pi) + \sum_{t=1}^{T} \gamma^{t-1}\rho^{\mathrm{RC}}_{1:t}\delta^\pi_t \tag*{(4)}

where E[φ(O;π,η)]=0\mathbb{E}[\varphi(O;\pi,\eta)] = 0. The proof is found in Section A.1.

The EIF in (4) is analogous to the EIF considered by Kallus and Uehara [8] for non-Markov decision processes, where here the importance weights are restricted to accommodate policies π∈ΠX\pi\in\Pi_X.

Theorem 1 motivates an estimator based on the EIF φ(O;π,η)\varphi(O;\pi,\eta), where we use cross-fitting ([5]) to ensure the resulting asymptotic distribution remains tractable. Specifically, letting η^=(g^,{q^t})\hat{\eta} = (\hat{g}, \{\hat{q}_t\}) denote nuisances cross-fitted on folds not containing unit ii, estimate the objective by

J^(π)=1n∑i=1n[V^1π(H1(i))+∑t=1Tγt−1ρ^1:tRC,(i)δ^tπ,(i)](5)\hat{J}(\pi) = \frac{1}{n}\sum_{i=1}^{n}\left[\hat{V}^{\pi}_1(H^{(i)}_1) + \sum_{t=1}^{T}\gamma^{t-1}\hat{\rho}^{\mathrm{RC},(i)}_{1:t}\hat{\delta}^{\pi,(i)}_t\right] \tag*{(5)}

The full estimation procedure is outlined in Algorithm 1.

Algorithm 1: Doubly robust policy learning and inference under runtime confounding

Input: Logged trajectories $\{O_i\}_{i=1}^n$ with $S_{it}=(X_{it},U_{it})$; policy class $\Pi\subseteq\Pi_X$; folds $K$; overlap constant $\eta_g$; $C_Q=R_{\max}\sum_t\gamma^{t-1}$
Output: $\hat{\pi}$, $\hat{J}(\cdot)$, confidence intervals
Split $[n]$ into folds $\mathcal{I}_1,\ldots,\mathcal{I}_K$
// Propensities (full information), fitted on $\mathcal{I}_{-k}$
for $k=1,\ldots,K$ do
  for $t=1,\ldots,T$ do
    Fit $\hat{g}^{(-k)}_t(a\mid H_t)$ by regressing $A_t$ on $H_t$
  end
end
// Cross-fitted value estimate for $\pi\in\Pi_X$
Function Value$(\pi)$:
  for $k=1,\ldots,K$ do
    Set $\hat{V}^{(-k)}_{T+1}\equiv 0$
// Fitted-$Q$ evaluation on $\mathcal{I}_{-k}$
    for $t=T,\ldots,1$ do
      Fit $\hat{q}^{\pi,(-k)}_t(H_t,a)$ by regressing $R_t+\gamma\hat{V}^{(-k)}_{t+1}(H_{t+1})$ on $(H_t,A_t)$
      $\hat{V}^{(-k)}_t(H_t)\leftarrow\sum_a\pi_t(a\mid H_t^X)\hat{q}^{\pi,(-k)}_t(H_t,a)$
    end
// Evaluation on the held-out fold $\mathcal{I}_k$
    for $i\in\mathcal{I}_k$ do
      $\hat{\rho}^{\mathrm{RC}}_{i,1:t}\leftarrow\prod_{s\leq t}\frac{\pi_s(A_{is}\mid H^X_{is})}{\hat{g}^{(-k)}_s(A_{is}\mid H_{is})}$ for $t\in[T]$
      $\hat{\delta}^{\pi}_{it}\leftarrow R_{it}+\gamma\hat{V}^{(-k)}_{t+1}(H_{i,t+1})-\hat{q}^{\pi,(-k)}_t(H_{it},A_{it})$
      $\psi_i(\pi)\leftarrow\hat{V}^{(-k)}_1(H_{i1})+\sum_{t=1}^T\gamma^{t-1}\hat{\rho}^{\mathrm{RC}}_{i,1:t}\hat{\delta}^{\pi}_{it}$
    end
  end
  return $\hat{J}(\pi)=\frac{1}{n}\sum_{i=1}^n\psi_i(\pi)$ and $\hat{\sigma}^2(\pi)=\frac{1}{n}\sum_{i=1}^n(\psi_i(\pi)-\hat{J}(\pi))^2$
// Learning and inference
Policy learning: $\hat{\pi}\leftarrow\operatorname*{arg\,max}_{\pi\in\Pi}\operatorname{Value}(\pi)$
Inference for a fixed $\pi$: report $\hat{J}(\pi)\pm z_{1-\alpha/2}\hat{\sigma}(\pi)/\sqrt{n}$

Error Decomposition with the EIF

We now describe the high-level decomposition used to produce our policy learning and off-policy evaluation guarantees. Let Pnf=n−1∑i=1nf(Oi)\mathbb{P}_n f=n^{-1}\sum_{i=1}^n f(O_i) denote the empirical measure, φ^π\hat{\varphi}^{\pi} denote φπ\varphi^{\pi} with cross-fitted nuisance estimates, and Δgt=g^t−πb\Delta g_t=\hat{g}_t-\pi_b and Δqtπ=q^tπ−Qtπ\Delta q_t^{\pi}=\hat{q}_t^{\pi}-Q_t^{\pi} denote estimation error of each respective nuisance function. To analyze J^(π)\hat{J}(\pi), we decompose our error into the following terms:

J^(π)−J(π)=(Pn−E)φπ⏟(E)+Rem⁡(η^;π)⏟(R)+(Pn−E)(φ^π−φπ)⏟(C)(6)\widehat{J}(\pi)-J(\pi)=\underbrace{(\mathbb{P}_n-\mathbb{E})\varphi^\pi}_{\mathrm{(E)}}+\underbrace{\operatorname{Rem}(\widehat{\eta};\pi)}_{\mathrm{(R)}}+\underbrace{(\mathbb{P}_n-\mathbb{E})(\widehat{\varphi}^\pi-\varphi^\pi)}_{\mathrm{(C)}} \tag*{(6)}

where the remainder is given by:

Rem⁡(η^;π)=∑t=1Tγt−1E[ρ^1:t−1RC∑aπt(a∣HtX)Δgt(a∣Ht)g^t(a∣Ht)Δqtπ(Ht,a)](7)\operatorname{Rem}(\widehat{\eta};\pi)=\sum_{t=1}^{T}\gamma^{t-1}\mathbb{E}\left[\widehat{\rho}_{1:t-1}^{\mathrm{RC}}\sum_{a}\pi_t(a\mid H_t^X)\frac{\Delta g_t(a\mid H_t)}{\widehat{g}_t(a\mid H_t)}\Delta q_t^\pi(H_t,a)\right] \tag*{(7)}

This is a standard decomposition in the semiparametric literature [10], where term (E) is sampling error, term (R) denotes nuisance bias, and term (C) is controlled by cross-fitting. This decomposition to establish regret bounds and conditions under which J^(π)\widehat{J}(\pi) attains asymptotic normality.

Before introducing our results, we introduce the following estimation assumptions, which are sufficient to control the remainder term in (7).

(Est1) Product rate at π\pi. ∑t=1T∥Δgt∥2∥Δqtπ∥2=oP(n−1/2)\sum_{t=1}^{T}\|\Delta g_t\|_2\|\Delta q_t^\pi\|_2=o_P(n^{-1/2}).

(Est2) Consistency at π\pi. ∥Δgt∥2+∥Δqtπ∥2=oP(1)\|\Delta g_t\|_2+\|\Delta q_t^\pi\|_2=o_P(1) for each t∈[T]t\in[T].

(Est3) Complexity. ΠX\Pi_X has finite uniform entropy integral bounded by J<∞\mathcal{J}<\infty.

(Est1)-(Est2) are standard rate assumptions in semiparametric inference supporting the use of non-Donsker function classes in estimation. (Est3) is an entropy condition on the runtime policy class, rather than the nuisance function estimator, used for regret analysis. In the coming sections, we establish off-policy evaluation (3.1) and policy learning (3.2) results based on these assumptions.

Efficient Off-Policy Evaluation

We now fix π∈ΠX\pi\in\Pi_X and give conditions under which J^(π)\widehat{J}(\pi) in (5) is asymptotically normal and efficient based on Theorem 1.

Theorem 2 (Asymptotic normality and efficiency). Under our identification assumptions (Id1)-(Id3), and estimation assumptions (Est1)-(Est2),

n(J^(π)−J(π))⇝N(0,σRC2)\sqrt{n}\left(\widehat{J}(\pi)-J(\pi)\right)\rightsquigarrow\mathcal{N}(0,\sigma_{\mathrm{RC}}^2)

where

σRC2=V[ν1π(H1)]+∑t=1Tγ2(t−1)E[(ρ1:t−1RC)2V[δtπ∣Ht,At]]\sigma_{\mathrm{RC}}^2=\mathbb{V}\left[\nu_1^\pi(H_1)\right]+\sum_{t=1}^{T}\gamma^{2(t-1)}\mathbb{E}\left[(\rho_{1:t-1}^{\mathrm{RC}})^2\mathbb{V}\left[\delta_t^\pi\mid H_t,A_t\right]\right]

is the semiparametric efficiency bound. Moreover σ^RC2=Pn(φ^π)2\widehat{\sigma}_{\mathrm{RC}}^2=\mathbb{P}_n(\widehat{\varphi}^{\pi})^2 is consistent, so J^(π)±z1−α2σ^RCn\widehat{J}(\pi)\pm z_{1-\frac{\alpha}{2}}\frac{\widehat{\sigma}_{\mathrm{RC}}}{\sqrt{n}} is an asymptotically valid (1−α)(1-\alpha) confidence interval. The proof is found in Section A.3.

This result gives us a way to characterize uncertainty for runtime-confounded policies, and do valid testing procedures. The finding is analogous to the results from Kallus and Uehara [8], but RC adjusted.

Policy Learning under Runtime-Confounding

Let π⋆=arg max⁡πJ(π)\pi^\star= \operatorname*{arg\,max}_{\pi} J(\pi) over the unrestricted (full-information) policies, and πX⋆=arg max⁡π∈ΠXJ(π)\pi_X^\star= \operatorname*{arg\,max}_{\pi\in\Pi_X} J(\pi). The learned policy maximizes the cross-fitted estimator (5) over runtime policies,

π^=arg max⁡π∈ΠXJ^(π)\widehat{\pi} = \operatorname*{arg\,max}_{\pi\in\Pi_X} \widehat{J}(\pi)

so that π^\widehat{\pi} takes only HtXH_t^X as input and is deployable.

Theorem 3 (Regret under runtime confounding). Under the identification assumptions (Id1)–(Id3), (Est1) at π^\widehat{\pi} and πX⋆\pi_X^\star, and (Est3),

J(π⋆)−J(π^)≤ΔRC+OP(CρJn)+oP(n−1/2)(8)J(\pi^\star) - J(\widehat{\pi}) \leq\Delta_{\mathrm{RC}} + O_P\left(\frac{C_\rho J}{\sqrt{n}}\right) + o_P\left(n^{-1/2}\right) \tag*{(8)}

where ΔRC=J(π⋆)−J(πX⋆)\Delta_{\mathrm{RC}} = J(\pi^\star) - J(\pi_X^\star) and Cρ≲(Rmax⁡+CQ)∑t=1Tγt−1ηg−tC_\rho\lesssim(R_{\max} + C_Q) \sum_{t=1}^{T} \gamma^{t-1}\eta_g^{-t} where we recall that ηg\eta_g is our positivity constraint for the logger. The proof is found in Section A.2.

The result states that our learned policy, under sufficient regularity conditions, follows the same finding of n\sqrt{n} rates with an irreducible runtime gap ΔRC\Delta_{\mathrm{RC}}.

Diagnosing and Testing Runtime Confounding

One may ask the gap we are losing in the decision-making process by using variables available only at runtime. This can inform future experimentation or provide an interpretable gap when it is unavoidable for domain experts. We lower-bound and test the irreducible runtime gap ΔRC=J(π⋆)−J(πX⋆)≥0\Delta_{\mathrm{RC}} = J(\pi^\star) - J(\pi_X^\star) \geq0, which is the value lost by withholding Uˉt\bar{U}_t at deployment. Because ΔRC\Delta_{\mathrm{RC}} is a difference of maxima, inference on this parameter can be non-regular [11]. To address this difficult, we employ a sample-splitting approach. Specifically, we split the sample into parts AA and BB. On AA, we learn a full-information policy π^S\widehat{\pi}_S on HtH_t and a runtime policy π^X∈ΠX\widehat{\pi}_X \in\Pi_X by Algorithm 1. On BB, estimate the runtime gap by

Δ^RC=J^B(π^S)−J^B(π^X)\widehat{\Delta}_{\mathrm{RC}} = \widehat{J}_B(\widehat{\pi}_S) - \widehat{J}_B(\widehat{\pi}_X)

By Theorem 2, nB(Δ^RC−[J(π^S)−J(π^X)])\sqrt{n_B}\left(\widehat{\Delta}_{\mathrm{RC}} - [J(\widehat{\pi}_S) - J(\widehat{\pi}_X)]\right) is asymptotically normal. Assuming J(π⋆)−J(π^S)=oP(n−1/2)J(\pi^\star) - J(\widehat{\pi}_S) = o_P(n^{-1/2}) and J(πX⋆)−J(π^X)=oP(n−1/2)J(\pi_X^\star) - J(\widehat{\pi}_X) = o_P(n^{-1/2}),

Δ^RC±z1−α/2σ^/nB\widehat{\Delta}_{\mathrm{RC}} \pm z_{1-\alpha/2}\widehat{\sigma}/\sqrt{n_B}

is an asymptotically valid (1−α)(1-\alpha) confidence interval for ΔRC\Delta_{\mathrm{RC}}, and we can test H0:ΔRC=0H_0 : \Delta_{\mathrm{RC}} = 0, by p=2(1−Φ(nB∣Δ^RC∣/σ^))p = 2(1 - \Phi(\sqrt{n_B}|\widehat{\Delta}_{\mathrm{RC}}|/\widehat{\sigma})). Under H0H_0 this can fail if the two policies coincide so their scores are equal, so we impose V[φπ^S−φπ^X]≥c>0\mathop{\mathrm{V}}[\varphi_{\widehat{\pi}_S} - \varphi_{\widehat{\pi}_X}] \geq c > 0.

Discussion

Under high-stakes or high-latency decision-making, deployment of standard methods can be biased due to variables present in training logs not being present during implementation. We introduce policy learning and efficient off-policy evaluation methods for reinforcement learning under runtime confounding to overcome this gap. We additionally provide diagnostics to understand bias from using a runtime confounded policy, informing future design of experiments and the price of runtime confounding. Extensions to online settings and decaying overlap are left for future work.

Acknowledgments

This work was supported by National Institutes of Health (NIH) grant T32HL139426. We thank Rachel Nethery for helping birth this research.

References

Proofs

Proof of Theorem 1

Proof. In general, note the factorization given by

P(hT)=P(s1)∏tπb(at∣ht)Pt(rt∣ht,at)Pt(st+1∣rt,ht,at)\mathbb{P}(h_T) = \mathbb{P}(s_1) \prod_t \pi_b(a_t \mid h_t)\mathbb{P}_t(r_t \mid h_t,a_t)\mathbb{P}_t(s_{t+1} \mid r_t,h_t,a_t)

The EIF will be derived using the point mass contamination method, by perturbations on each of these densities, except πb\pi_b, which is assumed to be logged. Let Z=(S,A,R)Z=(S,A,R), S=(X,U)S=(X,U), we consider perturbations of the form Pϵ=(1−ϵ)P+ϵδz~\mathbb{P}_{\epsilon}=(1-\epsilon)\mathbb{P}+\epsilon\delta_{\widetilde{z}}

T=1 We start with the case when T=1T=1. Define m(S)=∑aπ(a∣X)Q(S,a)m(S)=\sum_a\pi(a\mid X)Q(S,a), Q(s,a)=E[R∣s,a]Q(s,a)=\mathbb{E}[R\mid s,a].

Our target parameter is

J(P)=∫∑aπ(a∣x)Q(s,a)f(s) dsJ(\mathbb{P}) = \int\sum_a \pi(a \mid x)Q(s,a)f(s)\,ds

Perturb along each population object: Q(s,a)Q(s,a), f(s)f(s). Then, by the chain rule, we have

ddϵJ(Pϵ)∣0=∑aπ(a∣x~)Q(s~,a)−J+∫∑aπ(a∣x)(ddϵQ(s,a)∣ϵ=0)f(s) ds\left.\frac{\mathrm{d}}{\mathrm{d}\epsilon}J(\mathbb{P}_{\epsilon})\right|_0 = \sum_a \pi(a\mid\widetilde{x})Q(\widetilde{s},a)-J + \int\sum_a\pi(a\mid x)\left(\left.\frac{\mathrm{d}}{\mathrm{d}\epsilon}Q(s,a)\right|_{\epsilon=0}\right)f(s)\,ds

Noting the usual calculation,

ddϵEPϵ[Y∣Z=z]∣ϵ=0=I[z=z~]/f(z)(y~−E[Y∣Z=z])\left.\frac{\mathrm{d}}{\mathrm{d}\epsilon}\mathbb{E}_{\mathbb{P}_{\epsilon}}[Y\mid Z=z]\right|_{\epsilon=0} = \mathbb{I}[z=\widetilde{z}]/f(z)(\widetilde{y}-\mathbb{E}[Y\mid Z=z])

This reduces to

ddϵJ(Pϵ)∣0=(∑aπ(a∣x~)Q(s~,a)−J)+π(a~∣x~)/f(s~,a~)(r~−Q(s~,a~))f(s~)=(∑aπ(a∣x~)Q(s~,a)−J)+π(a~∣x~)/πb(a~∣s~)(r~−Q(s~,a~))\begin{aligned} \left.\frac{\mathrm{d}}{\mathrm{d}\epsilon}J(\mathbb{P}_{\epsilon})\right|_0 = \left(\sum_a\pi(a\mid\widetilde{x})Q(\widetilde{s},a)-J\right) + \pi(\widetilde{a}\mid\widetilde{x})/f(\widetilde{s},\widetilde{a})(\widetilde{r}-Q(\widetilde{s},\widetilde{a}))f(\widetilde{s}) \\ &= \left(\sum_a\pi(a\mid\widetilde{x})Q(\widetilde{s},a)-J\right) + \pi(\widetilde{a}\mid\widetilde{x})/\pi_b(\widetilde{a}\mid\widetilde{s})(\widetilde{r}-Q(\widetilde{s},\widetilde{a})) \end{aligned}

Hence, the EIF at T=1T=1 reduces to φ=m(S)−J+λ1RC(R−Q(S,A))\varphi=m(S)-J+\lambda_1^{\mathrm{RC}}(R-Q(S,A)), for importance weight at one timepoint given by λ1RC=π1(A1∣X1)/πb(A1∣H1)\lambda_1^{\mathrm{RC}}=\pi_1(A_1\mid X_1)/\pi_b(A_1\mid H_1).

General T Now, we wish to extend this logic to general TT. The difference is that VtV_t is a recursive object:

Vtπ(Ht)=∑aπt(a∣HtX)Qtπ(Ht,a)=∑aπt(a∣HtX)E[Rt+γVt+1π(Ht+1)∣Ht,At=a]V_t^\pi(H_t)=\sum_a\pi_t(a\mid H_t^X)Q_t^\pi(H_t,a)=\sum_a\pi_t(a\mid H_t^X)\mathbb{E}[R_t+\gamma V_{t+1}^\pi(H_{t+1})\mid H_t,A_t=a]

In the same manner as above, we have

ddϵJ(Pϵ)∣0=V1π(H~1)−J+E[ddϵV1π(H1)∣ϵ=0]\left.\frac{\mathrm{d}}{\mathrm{d}\epsilon}J(\mathbb{P}_{\epsilon})\right|_0 = V_1^\pi(\widetilde{H}_1)-J+\mathbb{E}\left[\left.\frac{\mathrm{d}}{\mathrm{d}\epsilon}V_1^\pi(H_1)\right|_{\epsilon=0}\right]

where we have used that E[V1π(H1)]=Eπ[∑tγt−1Rt]=J(π)\mathbb{E}[V_1^\pi(H_1)] = \mathbb{E}_\pi[\sum_{t} \gamma^{t-1}R_t] = J(\pi)

For convenience, define the following time tt IS-weighted EIF of VV as

Γt=E[ρ1:t−1RCddϵVtπ(Ht)|ϵ=0]\Gamma_t = \mathbb{E}\left[\rho^{\mathrm{RC}}_{1:t-1}\frac{\mathrm{d}}{\mathrm{d}\epsilon}V_t^\pi(H_t)\middle|_{\epsilon=0}\right]

Setting the base case for our weights to 1, ρ1:0RC=1\rho^{\mathrm{RC}}_{1:0}=1, gives Γ1=E[ddϵV1π(H1)∣ϵ=0]\Gamma_1 = \mathbb{E}\left[\left.\frac{\mathrm{d}}{\mathrm{d}\epsilon}V_1^\pi(H_1)\right|_{\epsilon=0}\right] as our object as interest.

Since the value function is a function of the future timepoints (e.g. Γ1=E[ddϵV1π(H1)∣ϵ=0]\Gamma_1 = \mathbb{E}\left[\left.\frac{\mathrm{d}}{\mathrm{d}\epsilon}V_1^\pi(H_1)\right|_{\epsilon=0}\right] for V1V_1 being a function of V2V_2), we require unrolling this sum and understanding Γt\Gamma_t.

Borrowing the key calculation from above on QQ, we perturb the distributions, and calculate the EIF on QtQ_t:

ddϵQtπ(Ht,a)∣ϵ=0=I[Ht=h~t,a=a~t]/f(Ht,a)(r~t+γVt+1π(H~t+1)−Qtπ(Ht,a))+γE[ddϵVt+1π(Ht+1)∣ϵ=0|Ht,At=a]\left.\frac{\mathrm{d}}{\mathrm{d}\epsilon}Q_t^\pi(H_t,a)\right|_{\epsilon=0} = \mathbb{I}[H_t=\tilde{h}_t,a=\tilde{a}_t]/f(H_t,a)(\tilde{r}_t+\gamma V_{t+1}^\pi(\widetilde{H}_{t+1})-Q_t^\pi(H_t,a)) + \gamma\mathbb{E}\left[\left.\frac{\mathrm{d}}{\mathrm{d}\epsilon}V_{t+1}^\pi(H_{t+1})\right|_{\epsilon=0}\middle|H_t,A_t=a\right]

Plugging this into Γt\Gamma_t (the directional derivative for VtπV_t^\pi along Pϵ\mathbb{P}_\epsilon), using f(h~t,a~t)=f(h~t)πb(a~t∣h~t)f(\tilde{h}_t,\tilde{a}_t)=f(\tilde{h}_t)\pi_b(\tilde{a}_t\mid\tilde{h}_t) in the first term and E[∑aπt(a∣HtX)g(Ht,a)]=E[λtRCg(Ht,At)]\mathbb{E}[\sum_a\pi_t(a\mid H_t^X)g(H_t,a)]=\mathbb{E}[\lambda_t^{\mathrm{RC}}g(H_t,A_t)] in the second, gives

Γt=ρ1:t−1RCπt(a~t∣h~tX)πb(a~t∣h~t)(r~t+γVt+1π(H~t+1)−Qtπ(h~t,a~t))+γE[ρ1:t−1RCλtRCddϵVt+1π(Ht+1)∣ϵ=0]=ρ1:tRC(r~t+γVt+1π(H~t+1)−Qtπ(h~t,a~t))+γΓt+1\begin{aligned} \Gamma_t = \rho^{\mathrm{RC}}_{1:t-1}\frac{\pi_t(\tilde{a}_t\mid\tilde{h}_t^X)}{\pi_b(\tilde{a}_t\mid\tilde{h}_t)}(\tilde{r}_t+\gamma V_{t+1}^\pi(\widetilde{H}_{t+1})-Q_t^\pi(\tilde{h}_t,\tilde{a}_t))+\gamma\mathbb{E}\left[\left.\rho^{\mathrm{RC}}_{1:t-1}\lambda_t^{\mathrm{RC}}\frac{\mathrm{d}}{\mathrm{d}\epsilon}V_{t+1}^\pi(H_{t+1})\right|_{\epsilon=0}\right] \\ &= \rho^{\mathrm{RC}}_{1:t}(\tilde{r}_t+\gamma V_{t+1}^\pi(\widetilde{H}_{t+1})-Q_t^\pi(\tilde{h}_t,\tilde{a}_t))+\gamma\Gamma_{t+1} \end{aligned}

where ρ1:tRC\rho^{\mathrm{RC}}_{1:t} in the last line is evaluated at the point mass.

Unroll this from t=1t=1, with ΓT+1=0\Gamma_{T+1}=0,

Γ1=∑t=1Tγt−1ρ1:tRC(r~t+γVt+1π(H~t+1)−Qtπ(h~t,a~t))\Gamma_1 = \sum_{t=1}^{T}\gamma^{t-1}\rho^{\mathrm{RC}}_{1:t}(\tilde{r}_t+\gamma V_{t+1}^\pi(\widetilde{H}_{t+1})-Q_t^\pi(\tilde{h}_t,\tilde{a}_t))

Hence, the EIF form follows.

Note, if πb\pi_b is unknown and we need to account for local perturbations in the derivation, just as in the iid case, our score is orthogonal yielding the same EIF as above.

Proof of Theorem 3

Step 1: Regret decomposition. Adding and subtracting J(πX∗)J(\pi_X^*), the value at the optimal runtime-confounded policy, we can decompose the regret as

J(π∗)−J(π^)=J(π∗)−J(πX∗)+J(πX∗)−J(π^)(9)J(\pi^*)-J(\hat{\pi}) = J(\pi^*)-J(\pi_X^*)+J(\pi_X^*)-J(\hat{\pi}) \tag*{(9)}

ΔRC\Delta_{\mathrm{RC}} is irreducible, representing the gap between the optimal policy and optimal runtime policy. It remains to bound the estimation term, which is the only term depending on the data.

Step 1: Value-error decomposition. We can bound the estimation term as follows:

J(πΠ⋆)−J(π^)=[J(πΠ⋆)−J^(πΠ⋆)]+[J^(πΠ⋆)−J^(π^)]+[J^(π^)−J(π^)]≤[J^−J](π^)−[J^−J](πΠ⋆)=(Pn−E)(φπ^−φπΠ⋆)+Rem⁡(η^;π^)−Rem⁡(η^;πΠ⋆)+(Pn−E)[(φ^−φ)π^−(φ^−φ)πΠ⋆]≤2sup⁡π∈Π∣(Pn−E)φπ∣+2sup⁡π∈Π∣(Pn−E)(φ^−φ)π∣+∣Rem⁡(η^;π^)∣+∣Rem⁡(η^;πΠ⋆)∣(10)\begin{aligned} J(\pi^\star_{\Pi})-J(\widehat{\pi}) &= [J(\pi^\star_{\Pi})-\widehat{J}(\pi^\star_{\Pi})]+[\widehat{J}(\pi^\star_{\Pi})-\widehat{J}(\widehat{\pi})]+[\widehat{J}(\widehat{\pi})-J(\widehat{\pi})]\\ &\leq[\widehat{J}-J](\widehat{\pi})-[\widehat{J}-J](\pi^\star_{\Pi})\\ &=(\mathbb{P}_n-\mathbb{E})(\varphi^{\widehat{\pi}}-\varphi^{\pi^\star_{\Pi}})+\operatorname{Rem}(\widehat{\eta};\widehat{\pi})-\operatorname{Rem}(\widehat{\eta};\pi^\star_{\Pi})\\ &\quad+(\mathbb{P}_n-\mathbb{E})[(\widehat{\varphi}-\varphi)^{\widehat{\pi}}-(\widehat{\varphi}-\varphi)^{\pi^\star_{\Pi}}]\\ &\leq2\sup_{\pi\in\Pi}|(\mathbb{P}_n-\mathbb{E})\varphi^\pi|+2\sup_{\pi\in\Pi}|(\mathbb{P}_n-\mathbb{E})(\widehat{\varphi}-\varphi)^\pi|+|\operatorname{Rem}(\widehat{\eta};\widehat{\pi})|+|\operatorname{Rem}(\widehat{\eta};\pi^\star_{\Pi})| \tag*{(10)} \end{aligned}

The first inequality follows by adding and subtracting J^(πΠ⋆)\widehat{J}(\pi^\star_{\Pi}) and J^(π^)\widehat{J}(\widehat{\pi}), and applying the basic inequality. The second equality follows plugging in (6) and expanding. The final inequality follows from the triangle inequality and realizability.

Step 2: Empirical process control, on supremum terms.

Term 2 sup⁡π∈Π∣(Pn−E)φπ∣\sup_{\pi\in\Pi}|(\mathbb{P}_n-\mathbb{E})\varphi^\pi|: By (Id3), ∣V1π∣,∣J(π)∣≤CQ|V_1^\pi|,|J(\pi)|\leq C_Q, ρ1:tRC≤ηg−t\rho_{1:t}^{\mathrm{RC}}\leq\eta_g^{-t} and ∣δtπ∣≤Rmax⁡+(1+γ)CQ|\delta_t^\pi|\leq R_{\max}+(1+\gamma)C_Q, and the same bounds hold for the estimated versions. Hence ΦΠ\Phi_\Pi and Φ^Π(k)\widehat{\Phi}_\Pi^{(k)} admit an envelope Cρ=2CQ+(Rmax⁡+2CQ)∑t=1Tγt−1ηg−tC_\rho=2C_Q+(R_{\max}+2C_Q)\sum_{t=1}^{T}\gamma^{t-1}\eta_g^{-t}. Then, by symmetrization and Dudley’s entropy bound under (Est3),

Esup⁡π∈Π∣(Pn−E)φπ∣≲CρJn\mathbb{E}\sup_{\pi\in\Pi}|(\mathbb{P}_n-\mathbb{E})\varphi^\pi|\lesssim\frac{C_\rho\mathcal{J}}{\sqrt{n}}

Term 2 sup⁡π∈Π∣(Pn−E)(φ^−φ)π∣\sup_{\pi\in\Pi}|(\mathbb{P}_n-\mathbb{E})(\widehat{\varphi}-\varphi)^\pi|: Cross-fitting splits the term over folds of size nk=n/Kn_k=n/K. Let the function class implied by this process be given by Gk={φπ(⋅;η^(−k))−φπ(⋅;η):π∈Π}\mathcal{G}_k=\{\varphi^\pi(\cdot;\widehat{\eta}^{(-k)})-\varphi^\pi(\cdot;\eta):\pi\in\Pi\}. Then,

sup⁡π∈Π∣(Pn−E)(φ^−φ)π∣≤∑k=1Knknsup⁡g∈Gk∣(Pnk−E)g∣\sup_{\pi\in\Pi}|(\mathbb{P}_n-\mathbb{E})(\widehat{\varphi}-\varphi)^\pi|\leq\sum_{k=1}^{K}\frac{n_k}{n}\sup_{g\in\mathcal{G}_k}|(\mathbb{P}_{n_k}-\mathbb{E})g|

Conditional on the training folds I−k\mathcal{I}_{-k}, the nuisance estimates are fixed, so Gk\mathcal{G}_k is a fixed class of differences between elements of Φ^Π(k)\widehat{\Phi}_\Pi^{(k)} and ΦΠ\Phi_\Pi, with envelope 2Cρ2C_\rho. Its entropy is at most the sum of the entropies of these two classes, so J(Gk)≤2J\mathcal{J}(\mathcal{G}_k)\leq2\mathcal{J} by (Est3). Dudley’s integral on the evaluation fold gives E[sup⁡g∈Gk∣(Pnk−E)g∣∣I−k]≲CρJ/nk\mathbb{E}[\sup_{g\in\mathcal{G}_k}|(\mathbb{P}_{n_k}-\mathbb{E})g|\mid\mathcal{I}_{-k}]\lesssim C_\rho\mathcal{J}/\sqrt{n_k}. Since KK is fixed, Markov’s inequality gives 2sup⁡π∈Π∣(Pn−E)(φ^−φ)π∣=OP(CρJ/n)2\sup_{\pi\in\Pi}|(\mathbb{P}_n-\mathbb{E})(\widehat{\varphi}-\varphi)^\pi|=O_P(C_\rho\mathcal{J}/\sqrt{n}).

Step 3: Second-order remainder (R) By (7), applied fold by fold with η^=η^(−k)\hat{\eta} = \hat{\eta}^{(-k)}, for any π∈ΠX\pi\in\Pi_X,

∣Rem⁡(η^;π)∣≤∑t=1Tγt−1E[ρ^1:t−1RC1min⁡ag^t(a∣Ht)∑aπt(a∣HtX)∣Δgt(a∣Ht)∣⋅∣Δqtπ(Ht,a)∣]≤∑t=1Tγt−1ηg−tE[max⁡a∣Δgt(a∣Ht)∣⋅max⁡a∣Δqtπ(Ht,a)∣]≤∑t=1Tγt−1ηg−t∥max⁡a∣Δgt(a∣⋅)∣∥2∥max⁡a∣Δqtπ(⋅,a)∣∥2\begin{aligned} |\operatorname{Rem}(\hat{\eta};\pi)| &\le\sum_{t=1}^{T} \gamma^{t-1}\mathbb{E}\left[\hat{\rho}^{\mathrm{RC}}_{1:t-1}\frac{1}{\min_a \hat{g}_t(a \mid H_t)}\sum_a \pi_t(a \mid H_t^X)|\Delta g_t(a \mid H_t)|\cdot|\Delta q_t^\pi(H_t,a)|\right] \\ &\le\sum_{t=1}^{T}\gamma^{t-1}\eta_g^{-t}\mathbb{E}\left[\max_a|\Delta g_t(a \mid H_t)|\cdot\max_a|\Delta q_t^\pi(H_t,a)|\right] \\ &\le\sum_{t=1}^{T}\gamma^{t-1}\eta_g^{-t}\left\|\max_a|\Delta g_t(a \mid\cdot)|\right\|_2\left\|\max_a|\Delta q_t^\pi(\cdot,a)|\right\|_2 \end{aligned}

where the second inequality uses ρ^1:t−1RC≤ηg−(t−1)\hat{\rho}^{\mathrm{RC}}_{1:t-1} \le\eta_g^{-(t-1)} from (Id3), and the third follows from Cauchy–Schwarz. (Est1) then shows ∣Rem⁡(η^;π^)∣+∣Rem⁡(η^;πX)∣=oP(n−1/2)|\operatorname{Rem}(\hat{\eta};\hat{\pi})|+|\operatorname{Rem}(\hat{\eta};\pi_X)|=o_P(n^{-1/2}).

Proof of Theorem 2

Proof

Decomposition. Our decomposition yielded

J^(π)−J(π)=(Pn−E)φπ⏟(E)+Rem⁡(η^;π)⏟(R)+(Pn−E)(φ^π−φπ)⏟(C)\hat{J}(\pi)-J(\pi)=\underbrace{(\mathbb{P}_n-\mathbb{E})\varphi^\pi}_{\mathrm{(E)}}+\underbrace{\operatorname{Rem}(\hat{\eta};\pi)}_{\mathrm{(R)}}+\underbrace{(\mathbb{P}_n-\mathbb{E})(\hat{\varphi}^\pi-\varphi^\pi)}_{\mathrm{(C)}}

We show the result by demonstrating n(Pn−E)φπ⇝N(0,σRC2)\sqrt{n}(\mathbb{P}_n-\mathbb{E})\varphi^\pi\rightsquigarrow\mathcal{N}(0,\sigma_{\mathrm{RC}}^2) and that (R) and (C) are oP(n−1/2)o_P(n^{-1/2}).

Term (E) and the variance. By (Id3), φπ\varphi^\pi is bounded by CρC_\rho, and E[φπ]=0\mathbb{E}[\varphi^\pi]=0. Since trajectories are i.i.d., the central limit theorem gives n(Pn−E)φπ⇝N(0,V[φπ])\sqrt{n}(\mathbb{P}_n-\mathbb{E})\varphi^\pi\rightsquigarrow\mathcal{N}(0,\mathbb{V}[\varphi^\pi]). We are explicit about the form of V[φπ]\mathbb{V}[\varphi^\pi]. Write φπ=ξ0+∑t=1Tξt\varphi^\pi=\xi_0+\sum_{t=1}^{T}\xi_t, where

ξ0=V1π(H1)−J(π),ξt=γt−1ρ1:tRCδtπ\xi_0=V_1^\pi(H_1)-J(\pi),\qquad\xi_t=\gamma^{t-1}\rho_{1:t}^{\mathrm{RC}}\delta_t^\pi

for Bellman residual δtπ=Rt+γVt+1π(Ht+1)−Qtπ(Ht,At)\delta_t^\pi=R_t+\gamma V_{t+1}^\pi(H_{t+1})-Q_t^\pi(H_t,A_t). Expanding the variance of the sum,

V[φπ]=V[ξ0]+∑t=1TV[ξt]+2∑t=1TCov⁡(ξ0,ξt)+2∑1≤s<t≤TCov⁡(ξs,ξt)(11)\mathbb{V}[\varphi^\pi]=\mathbb{V}[\xi_0]+\sum_{t=1}^{T}\mathbb{V}[\xi_t]+2\sum_{t=1}^{T}\operatorname{Cov}(\xi_0,\xi_t)+2\sum_{1\le s<t\le T}\operatorname{Cov}(\xi_s,\xi_t) \tag*{(11)}

Mean Zero. By the tower property and the Bellman equation E[δtπ∣Ht,At]=E[Rt+γVt+1π(Ht+1)∣Ht,At]−Qtπ(Ht,At)=0\mathbb{E}[\delta_t^\pi\mid H_t,A_t]=\mathbb{E}[R_t+\gamma V_{t+1}^\pi(H_{t+1})\mid H_t,A_t]-Q_t^\pi(H_t,A_t)=0,

E[ξt]=E[γt−1ρ1:tRCE[δtπ∣Ht,At]]=0,E[ξ0]=E[V1π(H1)]−J(π)=0\mathbb{E}[\xi_t]=\mathbb{E}\left[\gamma^{t-1}\rho_{1:t}^{\mathrm{RC}}\mathbb{E}[\delta_t^\pi\mid H_t,A_t]\right]=0,\qquad\mathbb{E}[\xi_0]=\mathbb{E}[V_1^\pi(H_1)]-J(\pi)=0

Covariances with ξ0\xi_0. Conditioning on (Ht,At)(H_t,A_t) and pulling out the measurable factors ξ0\xi_0 and γt−1ρ1:tRC\gamma^{t-1}\rho^{\mathrm{RC}}_{1:t}

Cov⁡(ξ0,ξt)=E[ξ0ξt]=E[ξ0γt−1ρ1:tRCE[δtπ∣Ht,At]]=0\operatorname{Cov}(\xi_0,\xi_t)=\mathbb{E}[\xi_0\xi_t]=\mathbb{E}\left[\xi_0\gamma^{t-1}\rho^{\mathrm{RC}}_{1:t}\mathbb{E}[\delta_t^\pi\mid H_t,A_t]\right]=0

Covariances across periods. For s<ts<t, ξs\xi_s is σ(Ht,At)\sigma(H_t,A_t)-measurable, so

Cov⁡(ξs,ξt)=E[ξsξt]=E[ξsγt−1ρ1:tRCE[δtπ∣Ht,At]]=0\operatorname{Cov}(\xi_s,\xi_t)=\mathbb{E}[\xi_s\xi_t]=\mathbb{E}\left[\xi_s\gamma^{t-1}\rho^{\mathrm{RC}}_{1:t}\mathbb{E}[\delta_t^\pi\mid H_t,A_t]\right]=0

Variances. E[(δtπ)2∣Ht,At]=V[δtπ∣Ht,At]\mathbb{E}[(\delta_t^\pi)^2\mid H_t,A_t]=\mathbb{V}[\delta_t^\pi\mid H_t,A_t], so

V[ξt]=E[ξt2]=γ2(t−1)E[(ρ1:tRC)2E[(δtπ)2∣Ht,At]]=γ2(t−1)E[(ρ1:tRC)2V[δtπ∣Ht,At]]\mathbb{V}[\xi_t]=\mathbb{E}[\xi_t^2]=\gamma^{2(t-1)}\mathbb{E}\left[(\rho^{\mathrm{RC}}_{1:t})^2\mathbb{E}[(\delta_t^\pi)^2\mid H_t,A_t]\right]=\gamma^{2(t-1)}\mathbb{E}\left[(\rho^{\mathrm{RC}}_{1:t})^2\mathbb{V}[\delta_t^\pi\mid H_t,A_t]\right]

and V[ξ0]=V[V1π(H1)]\mathbb{V}[\xi_0]=\mathbb{V}[V_1^\pi(H_1)].

Combining. Substituting into (11), we find

V[φπ]=V[V1π(H1)]+∑t=1Tγ2(t−1)E[(ρ1:tRC)2V[δtπ∣Ht,At]]=σRC2\mathbb{V}[\varphi^\pi]=\mathbb{V}[V_1^\pi(H_1)]+\sum_{t=1}^{T}\gamma^{2(t-1)}\mathbb{E}\left[(\rho^{\mathrm{RC}}_{1:t})^2\mathbb{V}[\delta_t^\pi\mid H_t,A_t]\right]=\sigma_{\mathrm{RC}}^2

Hence

V[φπ]=V[V1π(H1)]+∑t=1TE[ξt2]=σRC2\mathbb{V}[\varphi^\pi]=\mathbb{V}[V_1^\pi(H_1)]+\sum_{t=1}^{T}\mathbb{E}[\xi_t^2]=\sigma_{\mathrm{RC}}^2

which is the efficiency bound since φπ\varphi^\pi is the EIF (Theorem 1).

Term (R). See Theorem 2 for the proof. By the bound on the remainder in the proof of Theorem 3, at the fixed π\pi,

∣Rem⁡(η^;π)∣≤∑t=1Tγt−1ηg−t∥Δgt∥2∥Δqt∥2=oP(n−1/2)\left|\operatorname{Rem}(\hat{\eta};\pi)\right|\leq\sum_{t=1}^{T}\gamma^{t-1}\eta_g^{-t}\lVert\Delta_{gt}\rVert_2\lVert\Delta_{q_t}\rVert_2=o_P(n^{-1/2})

by (Est1).

Term (C). Fix a fold kk with nk=n/Kn_k=n/K units. Conditional on the training folds I−k\mathcal{I}_{-k}, φ^π,(−k)−φπ\hat{\varphi}^{\pi,(-k)}-\varphi^\pi is a fixed function so

E[(Pnk−E)(φ^π,(−k)−φπ)∣I−k]=0,V[(Pnk−E)(φ^π,(−k)−φπ)∣I−k]≤∥φ^π,(−k)−φπ∥22nk\mathbb{E}\left[(\mathbb{P}_{n_k}-\mathbb{E})(\hat{\varphi}^{\pi,(-k)}-\varphi^\pi)\mid\mathcal{I}_{-k}\right]=0,\qquad\mathbb{V}\left[(\mathbb{P}_{n_k}-\mathbb{E})(\hat{\varphi}^{\pi,(-k)}-\varphi^\pi)\mid\mathcal{I}_{-k}\right]\leq\frac{\lVert\hat{\varphi}^{\pi,(-k)}-\varphi^\pi\rVert_2^2}{n_k}

By Chebyshev’s inequality, this term is OP(∥φ^π,(−k)−φπ∥2/n)O_P(\lVert\hat{\varphi}^{\pi,(-k)}-\varphi^\pi\rVert_2/\sqrt{n}). The difference can be decomposed as

φ^π−φπ=(V^1π−V1π)+∑t=1Tγt−1[(ρ^1:tRC−ρ1:tRC)δ^tπ+ρ1:tRC(δ^tπ−δtπ)]\hat{\varphi}^\pi-\varphi^\pi=(\hat{V}_1^\pi-V_1^\pi)+\sum_{t=1}^{T}\gamma^{t-1}\left[(\hat{\rho}^{\mathrm{RC}}_{1:t}-\rho^{\mathrm{RC}}_{1:t})\hat{\delta}_t^\pi+\rho^{\mathrm{RC}}_{1:t}(\hat{\delta}_t^\pi-\delta_t^\pi)\right]

By (Id3), ∣V^nπ−Vnπ∣≤max⁡a∣Δqn1π∣|\widehat{V}^{\pi}_{n}-V^{\pi}_{n}| \le\max_{a}|\Delta q^{\pi}_{n1}|, ∣δ^tπ∣≤Rmax⁡+(1+γ)CQ|\widehat{\delta}^{\pi}_{t}| \le R_{\max}+(1+\gamma)C_{Q}. Also, ∣δ^tπ−δtπ∣≤max⁡a∣Δqtπ∣+γmax⁡a∣Δqt+1π∣|\widehat{\delta}^{\pi}_{t}-\delta^{\pi}_{t}| \le\max_{a}|\Delta q^{\pi}_{t}|+\gamma\max_{a}|\Delta q^{\pi}_{t+1}|, and ρ1:tRC\rho^{\mathrm{RC}}_{1:t} is at most ηg−1\eta_{g}^{-1}. Combining, we can bound the ρ\rho difference by

∣ρ^1:tRC−ρ1:tRC∣≤ηg−(t−1)∑s≤t∣πsg^s−πsπb∣≤ηg−(t+1)∑s≤tmax⁡a∣Δgs∣|\widehat{\rho}^{\mathrm{RC}}_{1:t}-\rho^{\mathrm{RC}}_{1:t}| \le\eta_{g}^{-(t-1)}\sum_{s\le t}\left|\frac{\pi_{s}}{\widehat{g}_{s}}-\frac{\pi_{s}}{\pi_{b}}\right| \le\eta_{g}^{-(t+1)}\sum_{s\le t}\max_{a}|\Delta g_{s}|

Hence by (Est2), ∥φ^π,(−k)−φπ∥2≲∑t=1T(∥Δgt∥2+∥Δqtπ∥2)=oP(1)\|\widehat{\varphi}^{\pi,(-k)}-\varphi^{\pi}\|_{2} \lesssim\sum_{t=1}^{T}(\|\Delta g_{t}\|_{2}+\|\Delta q^{\pi}_{t}\|_{2})=o_{P}(1).

Consistency of our Variance Estimator. Since ∣φ^π∣,∣φπ∣≤Cρ|\widehat{\varphi}^{\pi}|,|\varphi^{\pi}|\le C_{\rho},

∣Pn(φ^π)2−Pn(φπ)2∣=∣Pn[(φ^π−φπ)(φ^π+φπ)]∣≤2CρPn∣φ^π−φπ∣\left|\mathbb{P}_{n}(\widehat{\varphi}^{\pi})^{2}-\mathbb{P}_{n}(\varphi^{\pi})^{2}\right|=\left|\mathbb{P}_{n}\left[(\widehat{\varphi}^{\pi}-\varphi^{\pi})(\widehat{\varphi}^{\pi}+\varphi^{\pi})\right]\right|\le2C_{\rho}\mathbb{P}_{n}|\widehat{\varphi}^{\pi}-\varphi^{\pi}|

With cross-fitting, Pn∣φ^π−φπ∣=∑k=1KnknPnk∣φ^π,(−k)−φπ∣\mathbb{P}_{n}|\widehat{\varphi}^{\pi}-\varphi^{\pi}|=\sum_{k=1}^{K}\frac{n_{k}}{n}\mathbb{P}_{n_{k}}|\widehat{\varphi}^{\pi,(-k)}-\varphi^{\pi}|. Conditional on I−k\mathcal{I}_{-k}, φ^π,(−k)−φπ\widehat{\varphi}^{\pi,(-k)}-\varphi^{\pi} is a fixed function evaluated on the independent fold kk, so by Cauchy--Schwarz

E[Pnk∣φ^π,(−k)−φπ∣∣I−k]=E[∣φ^π,(−k)−φπ∣∣I−k]≤∥φ^π,(−k)−φπ∥2\mathbb{E}\left[\mathbb{P}_{n_{k}}|\widehat{\varphi}^{\pi,(-k)}-\varphi^{\pi}|\mid\mathcal{I}_{-k}\right]=\mathbb{E}\left[|\widehat{\varphi}^{\pi,(-k)}-\varphi^{\pi}|\mid\mathcal{I}_{-k}\right]\le\|\widehat{\varphi}^{\pi,(-k)}-\varphi^{\pi}\|_{2}

The right side is oP(1)o_{P}(1) by our analysis on Term (C), so by Markov’s inequality applied conditionally on I−k\mathcal{I}_{-k}, Pnk∣φ^π,(−k)−φπ∣=oP(1)\mathbb{P}_{n_{k}}|\widehat{\varphi}^{\pi,(-k)}-\varphi^{\pi}|=o_{P}(1) for each kk.

It remains to show Pn(φπ)2→σRC2\mathbb{P}_{n}(\varphi^{\pi})^{2}\to\sigma^{2}_{\mathrm{RC}}. The terms (φπ(Oi))2(\varphi^{\pi}(O_{i}))^{2} are i.i.d. and bounded by Cρ2C_{\rho}^{2}, so by the law of large numbers Pn(φπ)2→E[(φπ)2]\mathbb{P}_{n}(\varphi^{\pi})^{2}\to\mathbb{E}[(\varphi^{\pi})^{2}] in probability. Therefore σ^RC2=Pn(φ^π)2→σRC2\widehat{\sigma}^{2}_{\mathrm{RC}}=\mathbb{P}_{n}(\widehat{\varphi}^{\pi})^{2}\to\sigma^{2}_{\mathrm{RC}} in probability.

References

  1. [1]Susan Athey and Stefan Wager. Policy learning with observational data. Econometrica, 89 (1):133–161, 2021.arxiv.org/abs/1702.02896
  2. [2]Elias Bareinboim, Andrew Forney, and Judea Pearl. Bandits with unobserved confounders: A causal approach. In Advances in Neural Information Processing Systems, volume 28, 2015.
  3. [3]Keith Barnatchez, Kevin P. Josey, Rachel C. Nethery, and Giovanni Parmigiani. Debiased machine learning for conformal prediction of counterfactual outcomes under runtime confounding. In Proceedings of the Fifth Conference on Causal Learning and Reasoning, volume 323 of Proceedings of Machine Learning Research, pages 1345–1379, 2026.arxiv.org/abs/2604.03772
  4. [4]Andrew Bennett and Nathan Kallus. Proximal reinforcement learning: Efficient off-policy evaluation in partially observed Markov decision processes. Operations Research, 72 (3):1071–1086, 2024.arxiv.org/abs/2110.15332
  5. [5]Victor Chernozhukov, Denis Chetverikov, Mert Demirer, Esther Duflo, Christian Hansen, Whitney Newey, and James Robins. Double/debiased machine learning for treatment and structural parameters. The Econometrics Journal, 21(1):C1–C68, 2018.
  6. [6]Amanda Coston, Edward Kennedy, and Alexandra Chouldechova. Counterfactual predictions under runtime confounding. Advances in neural information processing systems, 33:4150–4162, 2020.arxiv.org/abs/2006.16916
  7. [7]Nan Jiang and Lihong Li. Doubly robust off-policy value evaluation for reinforcement learning. In Proceedings of the 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pages 652–661, 2016.arxiv.org/abs/1511.03722
  8. [8]Nathan Kallus and Masatoshi Uehara. Double reinforcement learning for efficient off-policy evaluation in markov decision processes. Journal of Machine Learning Research, 21(167):1–63, 2020. URL https://jmlr.org/papers/v21/19-827.html.arxiv.org/abs/1908.08526
  9. [9]Nathan Kallus and Angela Zhou. Confounding-robust policy improvement. In Advances in Neural Information Processing Systems, volume 31, 2018.arxiv.org/abs/1805.08593
  10. [10]Edward H Kennedy. Semiparametric doubly robust targeted double machine learning: a review. Handbook of statistical methods for precision medicine, pages 207–236, 2024.arxiv.org/abs/2203.06469
  11. [11]Alexander R. Luedtke and Mark J. van der Laan. Statistical inference for the mean outcome under a possibly non-unique optimal treatment strategy. The Annals of Statistics, 44(2):713–742, 2016a.DOI
  12. [12]Alexander R. Luedtke and Mark J. van der Laan. Super-learning of an optimal dynamic treatment rule. The International Journal of Biostatistics, 12(1):305–332, 2016b. doi: 10.1515/ijb-2015-0052.DOI
  13. [13]Susan A. Murphy, Mark J. van der Laan, James M. Robins, and Conduct Problems Prevention Research Group. Marginal mean models for dynamic regimes. Journal of the American Statistical Association, 96(456):1410–1423, 2001. doi: 10.1198/016214501753383227.
  14. [14]Hongseok Namkoong, Ramtin Keramati, Steve Yadlowsky, and Emma Brunskill. Off-policy policy evaluation for sequential decisions under unobserved confounding. In Advances in Neural Information Processing Systems, volume 33, 2020.arxiv.org/abs/2003.05623
  15. [15]Shosei Sakaguchi. Estimation of optimal dynamic treatment assignment rules under policy constraints. Quantitative Economics, 16(3):981–1022, 2025. doi: 10.3982/QE22288.arxiv.org/abs/2106.05031
  16. [16]Guy Tennenholtz, Uri Shalit, and Shie Mannor. Off-policy evaluation in partially observable environments. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 10276–10283, 2020.arxiv.org/abs/1909.03739
  17. [17]Philip Thomas and Emma Brunskill. Data-efficient off-policy policy evaluation for reinforcement learning. In Proceedings of the 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pages 2139–2148, 2016.arxiv.org/abs/1604.00923
  18. [18]Masatoshi Uehara, Haruka Kiyohara, Andrew Bennett, Victor Chernozhukov, Nan Jiang, Nathan Kallus, Chengchun Shi, and Wen Sun. Future-dependent value-based off-policy evaluation in POMDPs. In Advances in Neural Information Processing Systems, volume 36, 2023.arxiv.org/abs/2207.13081
  19. [19]Mark J. van der Laan and Alexander R. Luedtke. Targeted learning of the mean outcome under an optimal dynamic treatment rule. Journal of causal inference, 3(1):61–95, 2015.
  20. [20]Baqun Zhang, Anastasios A. Tsiatis, Eric B. Laber, and Marie Davidian. Robust estimation of optimal dynamic treatment regimes for sequential treatment decisions. Biometrika, 100(3):681–694, 2013.DOI

Paper details

vlnc:W_3yweg98k
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 2

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents