# Proximal Reinforcement Learning: Efficient Off-Policy Evaluation in
Partially Observed Markov Decision Processes

Andrew Bennett
Cornell University
<EMAIL_ADDRESS>Nathan Kallus
Cornell University
<EMAIL_ADDRESS>
(October 28, 2021)

###### Abstract

In applications of offline reinforcement learning to observational data, such
as in healthcare or education, a general concern is that observed actions
might be affected by unobserved factors, inducing confounding and biasing
estimates derived under the assumption of a perfect Markov decision process
(MDP) model. Here we tackle this by considering off-policy evaluation in a
partially observed MDP (POMDP). Specifically, we consider estimating the value
of a given target policy in a POMDP given trajectories with only partial state
observations generated by a different and unknown policy that may depend on
the unobserved state. We tackle two questions: what conditions allow us to
identify the target policy value from the observed data and, given
identification, how to best estimate it. To answer these, we extend the
framework of proximal causal inference to our POMDP setting, providing a
variety of settings where identification is made possible by the existence of
so-called bridge functions. We then show how to construct semiparametrically
efficient estimators in these settings. We term the resulting framework
proximal reinforcement learning (PRL). We demonstrate the benefits of PRL in
an extensive simulation study.

##  1 Introduction

An important problem in reinforcement learning (RL) is off policy evaluation
(OPE), which is defined as estimating the average reward generated by a target
_evaluation_ policy, given observations of data generated by running some
different _behavior_ policy. This problem is particularly important in many
application areas such as healthcare, education, or robotics, where
experimenting with new policies may be expensive, impractical, or unethical.
In such applications OPE may be used in order to estimate the benefit of
proposed policy changes by decision makers, or as a building block for the
related problem of policy optimization. At the same time, in the same
applications, unobservables can make this task difficult due to the lack of
experimentation.

As an example, consider the problem of evaluating a newly proposed policy for
assigning personalized curricula to students semester by semester, where the
curriculum assignment each semester is decided based on observed student
covariates, such as course outcomes and aptitude tests, with the goal of
maximizing student outcomes as measured, _e.g._ , by standardized test scores.
Since it may be unethical to experiment with potentially detrimental
curriculum plans, we may wish to evaluate such policies based on passively
collected data where the targeted curriculum was decided by teachers. However,
there may be factors unobserved in the data that jointly influence the
observed student covariates, curriculum assignments, and student outcomes;
this may arise for example because the teacher can perceive subjective aspects
of the students’ personalities or aptitudes and take these into account in
their decisions. While such confounding breaks the usual Markovian assumptions
that underlie standard approaches to OPE, the process may well be modeled by a
partially observed Markov decision process (POMDP). Two key questions for OPE
in POMDPs are: when is policy value still identifiable despite confounding due
to partial observation and, when it is, how can we estimate it most
efficiently.

In this work we tackle these two questions, expanding the range of settings
that enable identification and providing efficient estimators in these
settings. First, we extend an existing identification result for OPE in
tabular POMDPs (Tennenholtz et al., 2020) to the continuous setting, which
provides some novel insight on this existing approach but also highlights its
limitations. To break these limitations, motivated by these insights, we
provide a new general identification result based on extending the proximal
causal inference framework (Miao et al., 2018a; Cui et al., 2020; Kallus et
al., 2021) to the dynamic, longitudinal setting. This permits identification
in more general settings. And, unlike the previous results, this one expresses
the value of the evaluation policy as the mean of some score function under
the distribution over trajectories induced by the logging policy, which allows
for natural estimators with good qualities. In particular, we prove
appropriate conditions under which the estimators arising from this result are
consistent, asymptotically normal, and semiparametrically efficient. In
addition, we provide a tractable algorithm for computing the nuisance
functions that allow such estimators to be computed, based on recent state-of-
the-art methods for solving conditional moment problems. We term this
framework proximal reinforcement learning (PRL), highlighting the connection
to proximal causal inference. We provide a series of synthetic experiments
that empirically validate our theoretical results and demonstrate the benefits
of PRL.

##  2 Related Work

First, there is a extensive line of recent work on OPE under unmeasured
confounding. This work considers many different forms of confounding,
including confounding that is iid at each time step (Wang et al., 2020;
Bennett et al., 2021; Liao et al., 2021), occurs only at a single time step
(Namkoong et al., 2020), satisfies a “memorylessness” property (Kallus and
Zhou, 2020), follows a POMDP structure (Tennenholtz et al., 2020; Nair and
Jiang, 2021; Oberst and Sontag, 2019; Killian et al., 2020), may take an
arbitrary form (Chen and Zhang, 2021; Chandak et al., 2021), or is in fact not
a confounder (Hu and Wager, 2021). These works have varying foci: Namkoong et
al. (2020); Kallus and Zhou (2020); Chen and Zhang (2021) focus on computing
intervals comprising the partial identification set of all hypothetical policy
values consistent with the data and their assumptions; Oberst and Sontag
(2019); Killian et al. (2020) focus on sampling counterfactual trajectories
under the evaluation policy given that the POMDP follows a particular Gumbel-
softmax structure; Wang et al. (2020); Gasse et al. (2021) focus on using the
offline data to warm start online reinforcement learning; Liao et al. (2021)
study OPE using instrumental variables; Chandak et al. (2021) show that OPE
can be performed under very general confounding if the behavior policy
probabilities of the logged actions are known; Hu and Wager (2021) consider
hidden states that do not affect the behavior policy and are therefore not
confounders but do make OPE harder by breaking Markovianity thereby inducing a
curse of horizon; and Tennenholtz et al. (2020); Nair and Jiang (2021) study
conditions under which the policy value under the POMDP model is identified.

Of the past work on OPE under unmeasured confounding, Tennenholtz et al.
(2020); Nair and Jiang (2021) are closest to ours, since they too consider a
general POMDP model of confounding, namely without restrictions that preserve
Markovianity via iid confounders, knowing the confounder-dependent
propensities, having unconfounded logged actions, or using a specific Gumbel-
softmax form. Tennenholtz et al. (2020) consider a particular class of tabular
POMDPs satisfying some rank constraints, and Nair and Jiang (2021) extend
these results and slightly relax its assumptions. However, both do not
consider how to actually construct OPE estimators based on their
identification results that satisfy desirable properties such as consistency
or asymptotic normality, and they can only be applied to tabular POMDPs. Our
work presents a novel and general identification result and proposes a class
of resulting OPE estimators that possesses such desirable properties.

Another area of relevant literature is on proximal causal inference (PCI). PCI
was first proposed by Miao et al. (2018a), showing that using two
conditionally independent proxies of the confounder (known as a negative
control outcome and a negative control action) we can learn an outcome bridge
function that generalizes the standard mean-outcome function and controls for
the confounding effects. Since then this work has been expanded, including by
alternatively using an action bridge function which instead generalizes the
inverse propensity score (Miao et al., 2018b), allowing for multiple
treatments over time (Tchetgen et al., 2020), performing multiply-robust
treatment effect estimation (Shi et al., 2020), combining outcome and action
bridge functions for semiparametrically efficient estimation (Cui et al.,
2020), using PCI to estimate the value of contextual-bandit policies (Xu et
al., 2021) or generalized treatment effects (Kallus et al., 2021), or
estimating bridge functions using adversarial machine learning (Kallus et al.,
2021; Ghassami et al., 2021). In addition, the OPE for POMDP methodologies of
Tennenholtz et al. (2020); Nair and Jiang (2021) discussed above were said to
be motivated by PCI. Our paper relates to this body of work as it proposes a
new way of performing OPE for POMDPs using PCI, and it also proposes a new
adversarial machine learning-based approach for estimating the bridge
functions.

Finally, there is an extensive body of work on learning policies for POMDPs
using online learning. For example, see Azizzadenesheli et al. (2016), Katt et
al. (2017), Bhattacharya et al. (2020),Yang et al. (2021), Singh et al.
(2021), and references therein. Our work is distinct in that we consider an
offline setting where identification is an issue. At the same time, our work
is related to the online setting in that it could potentially be used to
augment and warm start such approaches if there is also offline observed data
available.

##  3 Problem Setting

A POMDP is formally defined by a tuple
$(\mathcal{S},\mathcal{A},\mathcal{O},H,P_{O},P_{R},P_{T})$, where
$\mathcal{S}$ denotes a state space, $\mathcal{A}$ denotes a finite action
space, $\mathcal{O}$ denotes an observation space, $H\in\mathbb{N}$ denotes a
time horizon, $P_{O}$ is an observation kernel, with $P_{O}^{(t)}(\cdot\mid
s)$ denoting the density of the observation $O_{t}$ given the state $S_{t}=s$
at time $t$, $P_{R}$ is a reward kernel, with $P_{R}^{(t)}(\cdot\mid s,a)$
denoting the density of the (bounded) reward $R_{t}\in[-R_{\max},R_{\max}]$
given the state $S_{t}=s$ and action $A_{t}=a$ at time $t$, and $P_{T}$ is a
transition kernel, with $P_{T}^{(t)}(\cdot\mid s,a)$ denoting the density of
the next $S_{t+1}$ given the state $S_{t}=s$ and action $A_{t}=a$ at time $t$.
Note that we allow for the POMDP to be time inhomogeneous; that is, we allow
the outcome, reward, and transition kernels to potentially depend on the time
index. Finally, we let $O_{0}$ denote some prior observation of the state
before $t=1$ (which may be empty), and we let $\tau^{\textup{full}}_{t}$ and
$\tau_{t}$ denote the true and observed trajectories up to time $t$
respectively, which we define according to

$\displaystyle\tau_{0}$ $\displaystyle=\tau^{\textup{full}}_{0}=O_{0}$
$\displaystyle\tau_{t}$
$\displaystyle=(O_{0},(O_{1},A_{1},R_{1}),(O_{2},A_{2},R_{t}),\ldots,(O_{t},A_{t},R_{t}))$
$\displaystyle\tau^{\textup{full}}_{t}$
$\displaystyle=(O_{0},(S_{1},O_{1},A_{1},R_{1}),(S_{2},O_{2},A_{2},R_{t}),\ldots,(S_{t},O_{t},A_{t},R_{t}))\,.$

Let $\pi_{b}$ be some given randomized _logging policy_ , which is
characterized by a sequence of functions $\pi_{b}^{(1)},\ldots,\pi_{b}^{(H)}$,
where $\pi_{b}^{(t)}(a\mid S_{t})$ denotes the probability that the logging
policy takes action $a\in\mathcal{A}$ at time $t$ given state $S_{t}$. The
logging policy together with the POMDP define a joint distribution over the
(true) trajectory $\tau_{H}^{\textup{full}}$ given by acting according to
$\pi_{b}$; let $\mathcal{P}_{b}$ denote this distribution. All probabilities
and expectations in the ensuing will be with respect to $\mathcal{P}_{b}$
unless otherwise specified, _e.g._ , by a subscript.

Our data consists of observed trajectories generated by the logging policy:
$\mathcal{D}=\\{\tau_{H}^{(1)},\tau_{H}^{(2)},\ldots,\tau_{H}^{(n)}\\}$, where
each $\tau_{H}^{(i)}$ is an iid sample of $\tau_{H}$ (which does not contain
$S_{t}$), distributed according to $\mathcal{P}_{b}$. Importantly, we
emphasize that, although we assume that states are unobserved by the decision
maker and are not included in the logged data $\mathcal{D}$, the logging
policy still uses these hidden states, inducing confounding.

Implicit in our notation $\pi_{b}^{(t)}(a\mid S_{t})$ is that the logging
policy actions are independent of the past given current state $S_{t}$.
Similarly, the POMDP model is characterized by similar independence assumption
with respect to observation and reward emissions, and state transitions. This
means that $\mathcal{P}_{b}$ satisfies a Markovian assumption with respect to
$S_{t}$; however, as $S_{t}$ is unobserved we cannot condition on it and break
the past from the future. We visualize the directed acyclic graph (DAG)
representing $\mathcal{P}_{b}$ in in Fig. 1. In particular, we have the
following conditional independencies in $\mathcal{P}_{b}$: for every $t$,

$\displaystyle O_{t}\perp\\!\\!\\!\perp\tau^{\textup{full}}_{t-1}\mid
S_{t},~{}~{}~{}~{}R_{t}\perp\\!\\!\\!\perp\tau^{\textup{full}}_{t-1},O_{t}\mid
S_{t},A_{t},~{}~{}~{}~{}S_{t+1}\perp\\!\\!\\!\perp\tau^{\textup{full}}_{t-1},O_{t},R_{t}\mid
S_{t},A_{t},~{}~{}~{}~{}A_{t}\perp\\!\\!\\!\perp\tau^{\textup{full}}_{t-1}\mid
S_{t}\,.$

Now, let $\pi_{e}$ be some deterministic _target policy_ that we wish to
evaluate, which is characterized by a sequence of functions
$\pi_{e}^{(1)},\ldots,\pi_{e}^{(H)}$, where
$\pi_{e}^{(t)}(O_{t},\tau_{t-1})\in\mathcal{A}$ denotes the action taken by
policy $\pi_{e}$ at time $t$ given current observation $O_{t}$ and the past
observable trajectory $\tau_{t-1}$. We visualize the POMDP model under such a
policy that only depends on observable data in Fig. 2. Note that we allow
$\pi_{e}^{(t)}$ to potentially depend on all observable data up to time $t$;
this is because the Markovian assumption _does not_ hold with respect to the
observations $O_{t}$, so we may wish to consider policies that use all past
observable information to best account for the unobserved state. We let
$\mathcal{P}_{e}$ denote the distribution over trajectories that would be
obtained by following policy $\pi_{e}$ in the POMDP. Then, given some
discounting factor $\gamma\in(0,1]$, we define the _value_ of policy $\pi_{e}$
as111Unlike some definitions of policy value, we have omitted normalizing by
$\sum_{t=1}^{H}\gamma^{t-1}$ for the sake of brevity.

$v_{\gamma}(\pi_{e})=\sum_{t=1}^{H}\gamma^{t-1}\mathbb{E}_{\mathcal{P}_{e}}[R_{t}]\,,$

The task OPE under the POMDP model is to estimate $v_{\gamma}(\pi_{e})$ (a
function of $\mathcal{P}_{e}$) given $\mathcal{D}$ (drawn from
$\mathcal{P}_{b}$).

$S_{1}$$A_{1}$$R_{1}$$O_{1}$$S_{2}$$A_{2}$$R_{2}$$O_{2}$$S_{3}$$A_{3}$$R_{3}$$O_{3}$……
Figure 1: Graphical representation of the POMDP model under logging policy
$\pi_{b}$. The red arrows make explicit the dependence of $\pi_{b}$ on the
hidden state. Dashed circles denote variables unobserved in our data.
$S_{1}$$A_{1}$$R_{1}$$O_{1}$$S_{2}$$A_{2}$$R_{2}$$O_{2}$$S_{3}$$A_{3}$$R_{3}$$O_{3}$……$\tau_{0}$$\tau_{1}$$\tau_{2}$$\tau_{3}$
Figure 2: Graphical representation of the POMDP model under evaluation policy
$\pi_{e}$. The red arrows make explicit the dependence of $\pi_{e}$ on the
current observation and previous observable trajectory, and the blue nodes and
arrows make explicit the dependence of the observable trajectories on the
data.

##  4 Identification Theory

Before considering how to actually estimate $v_{s}(\pi_{e})$, we first
consider the simpler problem of _identification_ , which is the problem of
finding some function $\psi$ such that
$v_{\gamma}(\pi_{e})=\psi(\mathcal{P}_{b})$. This is the first stepping stone
because $\mathcal{P}_{b}$ is the most we could hope to ever learn from
observing $\mathcal{D}$. If such a $\psi$ exists, then we say that
$v_{\gamma}(\pi_{e})$ is _identified_ with respect to $\mathcal{P}_{b}$. In
general, such an identification result is impossible for the OPE problem given
unobserved confounding as introduced by our POMDP model. Therefore, we must
impose some assumptions on $\mathcal{P}_{b}$ for such identification to be
possible.

To the best of our knowledge, the only existing identification result of this
kind was presented by Tennenholtz et al. (2020), and is only valid in tabular
settings where states and observations are discrete. We will proceed first by
extending this approach to more general, non-tabular settings. However, we
will note that there are some restrictive limitations to estimation based on
this approach. So, motivated by the limitations, we develop a new and more
general identification theory which extends the PCI approach to the sequential
setting and easily enables efficient estimation.

###  4.1 Identification by Time-Independent Sampling and Its Limitations

For our generalization of Tennenholtz et al. (2020), we will consider
evaluating policies $\pi_{e}$ such that $\pi_{e}^{(t)}$ only depends on the
past observable data via $\\{O_{1},\ldots,O_{t}\\}$ and
$\\{A_{1},\ldots,A_{t-1}\\}$.222That is, $\pi_{e}$ disregards $O_{0}$ as well
as past rewards. First, for each $t\in\\{1,\ldots,H\\}$ let
$\Omega_{t}=(Z_{t},W_{t},X_{t},A_{t},R_{t})$, where $Z_{t}=O_{t-1}$,
$W_{t}=O_{t}$, and $X_{t}=O_{t+1}$, and let $\Omega_{0}=X_{0}$.333This
renaming of some of the variables will allow for a clearer connection to the
next section. In addition, define
$\Omega^{*}_{t}=\\{\Omega_{0},\Omega_{1},\ldots,\Omega_{t}\\}$, and let
$\mathcal{P}_{\text{ind}}$ denote the measure on $\Omega^{*}_{H}$ in which
each $\Omega_{t}$ is sampled _independently_ according to its marginal
distribution in $\mathcal{P}_{b}$. Next, we make the following completeness
assumption:

######  Assumption 1 (Completeness).

For each $t\in\\{1,\ldots,H\\}$ and $a\in\mathcal{A}$, if
$\mathbb{E}_{\mathcal{P}_{b}}[g(S_{t})\mid O_{t},A_{t}=a]=0$ almost surely for
some function $g$, then $g(S_{t})=0$ almost surely.

This assumption is fundamental to this identification approach, and
essentially requires that $O_{t}$ captures all degrees of variation in
$S_{t}$. In the case that states and observations are finite, it is necessary
that $O_{t}$ have at least as many categories as $S_{t}$ for this condition to
hold.

Finally, we let $E_{t}$ denote the random variable measurable with respect to
$A_{1:t-1}$ and $W_{1:t}$ that gives the action that would have been assigned
by $\pi_{e}^{(t)}$ given past observations $W_{1:t}$ and past actions
$A_{1:t-1}$. Given this, we are ready to present our first identification
result.

######  Theorem 1.

Let Assumption 1 hold, and suppose that for each $t\in\\{1,\ldots,H\\}$ there
exists a function
$\rho^{(t)}:\mathcal{S}\times\mathcal{A}\times\mathcal{S}\mapsto\mathbb{R}$,
such that for every measure $f$ on $W_{t}$ that is absolutely continuous with
respect to $\mathcal{P}_{b}$ and every $a\in\mathcal{A}$, we have almost
surely

$\mathbb{E}\left[\int\rho^{(t)}(Z_{t},A_{t},x)df(x)\ \middle|\
W_{t},A_{t}=a\right]=P(A_{t}=a\mid
W_{t})^{-1}\left(\frac{df}{d\mathcal{P}_{b}}\right)(W_{t})\,,$ (1)

where $df/d\mathcal{P}_{b}$ denotes the Radon-Nikodym derivative of $f$ with
respect to $\mathcal{P}_{b}$. Then, for each $s\in\\{1,\ldots,H\\}$ we have

$\mathbb{E}_{\mathcal{P}_{e}}[R_{s}]=\mathbb{E}_{\mathcal{P}_{\text{ind}}}\left[R_{s}\prod_{t=1}^{s}\mathds{1}\\{A_{t}=E_{t}\\}\rho^{(t)}(Z_{t},A_{t},X_{t-1})\right]$

We note that this result identifies $v_{\gamma}(\pi_{e})$ for any given
$\gamma$, since by construction $\mathcal{P}_{\text{ind}}$ is identified with
respect to $\mathcal{P}_{b}$, and this allows us to express
$v_{\gamma}(\pi_{e})$ as a function of $\mathcal{P}_{\text{ind}}$. Note that
implicit in the assumptions is that $P(A_{t}=a\mid W_{t})>0$.

We call this result a _time-independent sampling_ result, since it is written
as an expectation with respect to $\mathcal{P}_{\text{ind}}$, where data at
each time point is sampled independently. We note that the moment equations
given by Eq. 1 in general are very complicated, and it is not immediately
clear under what conditions this equation is even solvable. In the tabular
setting, we present the following lemma which provides an analytic solution to
Eq. 1 and makes clear the connection to Tennenholtz et al. (2020).

######  Lemma 1.

Suppose that $O_{t}$ is discrete with $k$ categories for every $t$, and
without loss of generality let the support of $O_{t}$ be denoted by
$\\{1,\ldots,k\\}$. In addition, for each $t\in\\{1,\ldots,s\\}$ and
$a\in\mathcal{A}$, let $Q^{(t,a)}$ denote the $k\times k$ matrix defined
according to

$Q^{(t,a)}_{x,y}=P_{\mathcal{P}_{b}}(O_{t}=x\mid A_{t}=a,O_{t-1}=y)\,.$

Then, assuming $Q^{(t,a)}$ is invertible for each $t$ and $a$, Eq. 1 is solved
by

$\rho^{(t)}(z,a,x)=\frac{((Q^{(t,a)})^{-1})_{z,x}}{P(O_{t-1}=z,A_{t}=a)}\,.$

Furthermore, plugging this solution into the identification result of Theorem
1 is identical to Theorem 1 of Tennenholtz et al. (2020).

We also note that in the case that the matrices $Q^{(t,a})$ defined above are
invertible, it easily follows that Assumption 1 holds as long as $U_{t}$ has
at most $k$ categories.

Unfortunately, this identification result has some major shortcomings. For
one, the nuisance function defined by Eq. 1 is generally very complex and is
difficult to estimate in general. Even in the tabular setting where this can
be solved analytically, the result still depends on a large number of matrices
being invertible, which is potentially dubious in practice.444Tennenholtz et
al. (2020) also consider a more flexible version of their result which makes
the invertibility assumption more flexible, but this requires a different
model than the POMDP in which we have multiple conditionally independent
observations at every time step. In addition, since this result is given by an
expectation under $\mathcal{P}_{\text{ind}}$ rather than $\mathcal{P}_{b}$, it
is difficult to analyze using standard efficiency theory given iid samples
from $\mathcal{P}_{b}$. Empirical approximations of this expectation given $n$
iid samples from $\mathcal{P}_{b}$ would require averaging over $n^{s}$ terms,
introducing a curse of dimension. Finally, this expectation clearly does not
have many of the desirable properties for OPE estimating equations held by
many OPE estimators in the simpler MDP setting, such as Neyman orthogonality
(Kallus and Uehara, 2019a, b).

###  4.2 Identification by Proximal Causal Inference

We now discuss an alternative way of obtaining identifiability, via a
reduction to a nested sequence of proximal causal inference (PCI) problems of
the kind described by Cui et al. (2020). These authors considered identifying
the average treatment effect (ATE), and other related causal estimands, for
binary decision making problems with unmeasured confounding given two
independent proxies for the confounders, one of which is conditionally
independent from treatments given confounders, and the other of which is
independent from outcomes given treatment and confounders. We will in fact
leverage the refinement of the PCI approach by Kallus et al. (2021), which has
strictly weaker assumptions than Cui et al. (2020).

Our reduction works by defining random variables $Z_{t}$ and $W_{t}$ for each
$t\in[H]$ that are measurable with respect to the observed trajectory
$\tau_{H}$. We respectively refer to these as _negative control actions_ and
_negative control outcomes_. All negative controls must be satisfy certain
independence properties outlined below. Any definition of such variables that
satisfy these independence properties is considered a valid PCI reduction, and
we will have various examples of valid PCI reductions for our POMDP model at
the end of this section.

To formalize these assumptions, we must first define some additional notation.
Let $\mathcal{P}^{*}_{t}$ denote the measure on trajectories induced by
running policy $\pi_{e}$ for the first $t-1$ actions, and running policy
$\pi_{b}$ henceforth. Note that according to this definition,
$\mathcal{P}_{b}=\mathcal{P}^{*}_{1}$, and
$\mathcal{P}_{e}=\mathcal{P}^{*}_{H+1}$. In addition, we use the notation
$\mathbb{E}^{*}_{t}$ for expectation under $\mathcal{P}^{*}_{t}$, and
$P^{*}_{t}$ for the probability mass or density of random variables under
$\mathcal{P}^{*}_{t}$. Next, for each $t\in\\{1,\ldots,H\\}$ we define
$E_{t}=\pi_{e}^{(t)}(O_{t},\tau_{t-1})$; that is, $E_{t}$ is shorthand for the
action that our deterministic target policy would take given the observable
information available at time $t$. Furthermore, analogous to Section 4.1, for
any choice of negative controls we will define the shorthand notation
$D_{t}=(Z_{t},W_{t},A_{t},E_{t},R_{t})$. Finally, for any random variable
$Y_{t}$ that is measurable with respect to $(R_{t},D_{t+1:H})$, which we refer
to as an _outcome variable at time $t$_, for ease of presentation. We will use
the potential outcome notation $Y_{t}(a)$ for any $a\in\mathcal{A}$ to denote
a random variable with the same distribution as $Y_{t}$ would have if,
possibly counter to fact, action $a$ were taken at time $t$ instead of $A_{t}$
(and subsequent actions were still taken according to the behavior policy). We
note that we will only consider such potential outcome variables under the
measure $\mathcal{P}^{*}_{t}$, in which case $Y_{t}(a)$ corresponds to the
outcome that would be obtained by applying $\pi_{e}$ for the first $t-1$
actions, the fixed action $a$ at time $t$, and then $\pi_{b}$ henceforth (as
opposed to the factual outcome $Y_{t}$ obtained by applying $\pi_{e}$ for the
first $t-1$ actions and $\pi_{b}$ henceforth). We note that according to this
notation we have $Y_{t}(A_{t})=Y_{t}$ always.

Given these definitions, the independence assumptions for a valid PCI
reduction are as follows.

######  Assumption 2 (Negative Controls).

For each $t\in[H]$ and $a\in\mathcal{A}$, and any outcome variable $Y_{t}$
that is measurable w.r.t. $(R_{t},D_{t+1:H})$, we have

$Z_{t},A_{t}\perp\\!\\!\\!\perp_{\mathcal{P}^{*}_{t}}W_{t},E_{t},Y_{t}(a)\mid
S_{t}\,.$

We note that these independence assumptions imply that the decision making
problem under $\mathcal{P}^{*}_{t}$ with confounder $S_{t}$, negative controls
$Z_{t}$ and $W_{t}$, action $A_{t}$, and outcome $(R_{t},D_{t+1:H})$ satisfy
the PCI problem structure as in Cui et al. (2020). We also note that we may
additionally include an observable context variable $X_{t}$, which may be
useful for defining more efficient reductions. In this case, the conditional
independence assumption in Assumption 2 should hold given both $S_{t}$ and
$X_{t}$, and in everything that follows $Z_{t}$, $W_{t}$, and $S_{t}$ should
be replaced with $(Z_{t},X_{t})$, $(W_{t},X_{t})$, and $(S_{t},X_{t})$
respectively, as in Cui et al. (2020). However, we omit $X_{t}$ from the
notation in the rest of the paper for brevity.

Next, our identification result below depends on the existence of some
_bridge_ functions. Specifically, we make the following assumption.

######  Assumption 3 (Bridge Functions Exist).

For each $t\in[H]$ and $a\in\mathcal{A}$, there exists a function $q^{(t)}$
satisfying

$\mathbb{E}^{*}_{t}[q^{(t)}(Z_{t},A_{t})\mid
S_{t},A_{t}=a]=P^{*}_{t}(A_{t}=a\mid S_{t})^{-1}\qquad\text{a.s.}$

Furthermore, for any given outcome variable $Y_{t}=\phi(R_{t},D_{t+1:H})$,
there exists a function $h^{(t,\phi)}$ satisfying

$\mathbb{E}^{*}_{t}[h^{(t,\phi)}(W_{t},A_{t})\mid
S_{t},A_{t}=a]=\mathbb{E}^{*}_{t}[\mathds{1}\\{E_{t}=A_{t}\\}Y_{t}\mid
S_{t},A_{t}=a]\qquad\text{a.s.}$

Note that implicit in the assumption is that $P^{*}_{t}(A_{t}=a\mid S_{t})>0$.
We refer to the functions $q^{(t)}$ as _action bridge functions_ , and
$h^{(t,\phi)}$ as _outcome bridge functions_. These may be seen as analogues
of inverse propensity scores and state-action quality functions respectively.
As argued previously by Kallus et al. (2021), assuming the existence of these
functions is more general than the approach taken by Cui et al. (2020), who
require complex completeness conditions. Existence of such functions functions
can be justified, _e.g._ , by conditions on the the singular values of certain
conditional expectation linear operators; we refer readers to Kallus et al.
(2021) for a detailed presentation of such conditions, as well as concrete
examples of bridge functions when the negative controls are discrete, or the
negative controls and $Y_{t}$ are defined by linear models.

Given this, we are now ready to present our main identifiability theorem.

######  Theorem 2.

Let Assumptions 2 and 3 hold. For each $s\in\\{1,\ldots,H\\}$ recursively
define $Y^{(s)}_{s}=R_{s}$, and
$Y^{(s)}_{t-1}=\phi^{(t,s)}(Z_{t},W_{t},A_{t},E_{t},Y_{t})$ for each $t\leq
s$, where the function $\phi^{(t,s)}$ is allowed to take one of the following
three forms:

$\displaystyle\phi^{(t,s)}_{\text{Reg}}(Z_{t},W_{t},A_{t},E_{t},Y_{t}^{(s)})$
$\displaystyle=\sum_{a\in\mathcal{A}}h^{(t,s)}(W_{t},a)$
$\displaystyle\phi^{(t,s)}_{\text{IS}}(Z_{t},W_{t},A_{t},E_{t},Y_{t}^{(s)})$
$\displaystyle=q^{(t)}(Z_{t},A_{t})\mathds{1}\\{A_{t}=E_{t}\\}Y_{t}^{(s)}$
$\displaystyle\phi^{(t,s)}_{\text{DR}}(Z_{t},W_{t},A_{t},E_{t},Y_{t}^{(s)})$
$\displaystyle=\sum_{a\in\mathcal{A}}h^{(t,s)}(W_{t},a)+q^{(t)}(Z_{t},A_{t})\left(\mathds{1}\\{A_{t}=E_{t}\\}Y_{t}^{(s)}-h^{(t,s)}(W_{t},A_{t})\right)\,,$

where $h^{(t,s)}$ and $q^{(t)}$ are solutions to, respectively,

$\displaystyle\mathbb{E}^{*}_{t}[q^{(t)}(Z_{t},A_{t})\mid W_{t},A_{t}=a]$
$\displaystyle=P^{*}_{t}(A_{t}=a\mid W_{t})^{-1}\quad\text{a.s.}\quad\forall
a\in\mathcal{A}\,,$ (2)
$\displaystyle\mathbb{E}^{*}_{t}[h^{(t,s)}(W_{t},A_{t})\mid Z_{t},A_{t}=a]$
$\displaystyle=\mathbb{E}^{*}_{t}[\mathds{1}\\{A_{t}=E_{t}\\}Y_{t}^{(s)}\mid
Z_{t},A_{t}=a]\quad\text{a.s.}\quad\forall a\in\mathcal{A}\,,$ (3)

which we show must exist.

Then, we have
$\mathbb{E}_{\mathcal{P}_{e}}[R_{s}]=\mathbb{E}_{\mathcal{P}_{b}}[Y_{0}^{(s)}]$
for each $s\in\\{1,\ldots,H\\}$.

We note that $Y_{0}^{(t)}$ is a function of $\tau_{H}$ for each $t$, so
therefore this is a valid identification result. Furthermore, given
Assumptions 2 and 3 it must be the case that there exist solutions to Eqs. 2
and 3; in particular, any functions $q^{(t)}$ and $h^{(t,s)}$ satisfying
Assumption 3 with $\phi(R_{t},D_{t+1:H})=Y_{t}^{(s)}$ must satisfy Eqs. 2 and
3. Importantly, our identification result holds using _any_ functions
$q^{(t)}$ and $h^{(t,s)}$ satisfying Eqs. 2 and 3, even if these functions do
not satisfy the equations in Assumption 3. However, the existence of functions
in Assumption 3 is still important for the proof of Theorem 2, even if
different functions $q^{(t)}$ and $h^{(t,s)}$ are used. We refer readers to
the proof in the appendix for more details.

Comparing with Theorem 1, this result has many immediate advantages. It is
written as an expectation over $\mathcal{P}_{b}$, and so may be analyzed
readily using standard semiparametric efficiency theory, and although Eqs. 3
and 2 may appear complex given that they are expressed in terms of the
intervention distributions $\mathcal{P}^{*}_{t}$, this can easily be dealt
with as discussed later.

Furthermore, in the case that we use $\phi^{(t,s)}_{\text{DR}}$ for each
$t,s$, we present the following corollary, which provides a simplified
equation for $v_{\gamma}(\pi_{e})$.

######  Corollary 1.

Let Assumptions 2 and 3 hold. For each $t\in[H]$ let $h^{(t)}$ be any solution
to

$\mathbb{E}^{*}_{t}[h^{(t)}(W_{t},A_{t})\mid
Z_{t},A_{t}=a]=\mathbb{E}^{*}_{t}[\mathds{1}\\{E_{t}=A_{t}\\}Y_{t}\mid
Z_{t},A_{t}=a]\quad\text{a.s.}\quad\forall a\in\mathcal{A}\,,$ (4)

where we recursively define $Y_{H}=R_{H}$, and

$Y_{t-1}=R_{t-1}+\gamma\left(\sum_{a\in\mathcal{A}}h^{(t)}(W_{t},a)+q^{(t)}(Z_{t},A_{t})\left(\mathds{1}\\{A_{t}=E_{t}\\}Y_{t}-h^{(t)}(W_{t},A_{t})\right)\right)\,,$
(5)

for $t>1$. In addition, let $\eta_{1}=1$, and for each $t>1$ define

$\eta_{t}=\prod_{s=1}^{t-1}q^{(s)}(Z_{s},A_{s})\mathds{1}\\{A_{s}=E_{s}\\}\,.$
(6)

Then, we have
$v_{\gamma}(\pi_{e})=\mathbb{E}_{\mathcal{P}_{b}}[\psi_{\text{IS}}(\tau_{H})]=\mathbb{E}_{\mathcal{P}_{b}}[\psi_{\text{Reg}}(\tau_{H})]=\mathbb{E}_{\mathcal{P}_{b}}[\psi_{\text{DR}}(\tau_{H})]$,
where

$\displaystyle\psi_{\text{IS}}(\tau_{H})$
$\displaystyle=\sum_{t=1}^{H}\gamma^{t-1}\eta_{t+1}R_{t}$ (7)
$\displaystyle\psi_{\text{Reg}}(\tau_{H})$
$\displaystyle=\sum_{a\in\mathcal{A}}h^{(1)}(W_{1},a)$ (8)
$\displaystyle\psi_{\text{DR}}(\tau_{H})$
$\displaystyle=\sum_{t=1}^{H}\gamma^{t-1}\left(\eta_{t+1}R_{t}+\eta_{t}\sum_{a\in\mathcal{A}}h^{(t)}(W_{t},a)-\eta_{t}q^{(t)}(Z_{t},A_{t})h^{(t)}(W_{t},A_{t})\right)\,.$
(9)

This corollary follows directly from Theorem 2, noting that
$Y_{t}=\sum_{s=t}^{H}\gamma^{s-t}Y_{t}^{(s)}$, and
$h^{(t)}=\sum_{s=t}^{H}\gamma^{s-t}h^{(t,s)}$. We note that Eq. 7 and Eq. 8
have very similar structures to importance sampling and direct method
estimators for the MDP setting, while Eq. 9 has a very similar structure to
the Double Reinforcement Learning (DRL) estimators for the MDP setting (Kallus
and Uehara, 2020), where the $h^{(t)}$ terms are similar to the quality
function terms, and the $\eta_{t}$ and $\nu_{t}$ terms are similar to the
importance sampling terms. In the case of Eq. 9 this is particularly
promising, since DRL estimators enjoy desirable properties such as
semiparametric efficiency in the MDP setting (Kallus and Uehara, 2020).
Indeed, in Section 5 we show that similar properties extend to estimators
defined based on Eq. 9.

###  4.3 Specific Proximal Causal Inference Reductions and Resulting
Identification

We conclude this section with some discussion of how to actually construct a
valid PCI reduction. We provide several options of how this reduction may be
performed, and discuss in each case the assumptions that would be required of
the POMDP and evaluation policy for identification based on our results. In
all cases, we would need to assume or justify the implicit completeness and
regularity assumptions given the corresponding choice of $Z_{t}$ and $W_{t}$.
Furthermore, we note that the practicality of any given reduction would depend
heavily on how well-correlated $W_{t}$ and $Z_{t}$ are for each $t$, which in
turn would impact how easily the required nuisance functions $q^{(t)}$ and
$h^{(t)}$ could be fit.

#### Current and past observation.

A simple choice would be to define $W_{t}=O_{t}$, and $Z_{t}=O_{t-1}$. Since
we require that $Z_{t}$ is conditionally independent of the actions taken by
$\pi_{e}$ at time $t$ onward (given $S_{t}$ and $A_{t}$), this choice would be
valid for instance if $\pi_{e}^{(t)}$ did not depend on the prior observations
$O_{0:t-1}$.

#### Current and $k$-previous observation.

A slight generalization of the previous reduction would be to use
$W_{t}=O_{t}$ and $Z_{t}=O_{\max(t-k,0)}$. This would be valid if
$\pi_{e}^{(t)}$ did not depend on observations $O_{0:\max(t-k,0)}$, _i.e._ ,
only the $k$-most recent observations are used for decision making.

#### Current and initial observation.

In the case that $\pi^{(t)}$ depended on all previous observations except for
$O_{0}$, we may use $W_{t}=O_{t}$ and $Z_{t}=O_{0}$.

#### Two views of current observation.

If each observation factored as $O_{t}=(O_{t}^{\prime},O_{t}^{\prime\prime})$,
where $O_{t}^{\prime}$ and $O_{t}^{\prime\prime}$ were conditionally
independent given $S_{t}$ and $A_{t}$, then we may justify choosing
$Z_{t}=O_{t}^{\prime\prime}$ and $W_{t}=O_{t}^{\prime}$. This would be valid
if $\pi_{e}^{(t)}$ did not depend on $O_{t^{\prime}}^{\prime\prime}$ for any
$t^{\prime}\leq t$. This may be an appealing approach if observations
contained certain view(s) of the state that we did not want to explicitly
consider in decision making, for example for fairness or interpretability
reasons.

#### Current observation and previous reward.

Finally, in the case that $\pi_{e}^{(t)}$ did not depend on past rewards, we
may choose $W_{t}=O_{t}$ and $Z_{t}=R_{t-1}$. Note that this implies a “prior
reward” $R_{0}$; in the case that $\pi_{e}^{(t)}$ did not depend on $O_{0}$
for any $t$, then we could avoid this issue by modifying the reduction,
instead defining $Z_{1}=O_{0}$.

##  5 Policy Value Estimators

Now we turn from the question of identification to estimation. We will focus
on estimation of $v_{s}(\pi_{e})$ based on the identification result given by
Corollary 1. A natural approach to estimating $v_{\gamma}(\pi_{e})$ based on
this would be to use an estimator of the kind

$\hat{v}^{(n)}_{\gamma}(\pi_{e})=\frac{1}{n}\sum_{i=1}^{n}\widehat{\psi}_{\text{DR}}(\tau_{H}^{(i)})\,,$
(10)

where $\widehat{\psi}_{\text{DR}}$ is an approximation of $\psi_{\text{DR}}$
using plug-in estimators for the nuisance functions $h^{(t)}$ and $q^{(t)}$
for each $t$. In the remainder of this section, we will discuss the properties
of estimators of this kind. We will assume in the remainder of this section
that we have fixed a valid PCI reduction that satisfies Assumptions 2 and 3.

###  5.1 Consistency and Asymptotic Normality

We first consider conditions under which the estimator
$\hat{v}^{(n)}_{\gamma}(\pi_{e})$ is consistent and asymptotically normal. For
this, we need to make some assumptions on the quality of our estimated
nuisance functions $\hat{q}^{(t)}$ and $\hat{h}^{(t)}$. Before we introduce
these assumption, we need to introduce some additional notation. Specifically,
for any quantity $\Psi$ that depends on the nuisance functions $q^{(t)}$
and/or $h^{(t)}$, let $\Delta\Psi=\hat{\Psi}-\Psi$ denote the difference
between the estimated quantity $\hat{\Psi}$ using the plugin estimated
nuisances, and the true quantity $\Psi$ using the true nuisances. Then, our
assumption on nuisance estimation quality is as follows.

######  Assumption 4.

For each $a\in\mathcal{A}$, and each
$\Psi,\Psi^{\prime}\in\\{h^{(t)}(W_{t},a),q^{(t)}(W_{t},A_{t}):t\in[H]\\}$
such that $\Psi\neq\Psi^{\prime}$, the following hold, where the randomness in
each bound is defined with respect to the sampling distribution defining the
estimated nuisances plugged into the $\Delta\Psi$ terms.

  1. 1.

$\|\Delta\Psi\|_{2,\mathcal{P}_{b}}=o_{p}(1)$

  2. 2.

$\|\Delta\Psi\|_{2,\mathcal{P}_{b}}\|\Delta\Psi^{\prime}\|_{2,\mathcal{P}_{b}}=o_{p}(n^{-1/2})$

  3. 3.

$\|\Delta\Psi\|_{\infty}=O_{p}(1)$

  4. 4.

$\|\Psi\|_{\infty}<\infty$

Essentially, Assumption 4 requires that the nuisances $q^{(t)}$ and $h^{(t)}$
are estimated consistently in terms of the $L_{2,\mathcal{P}_{b}}$ functional
norm for each $t$, and that the corresponding product-error terms converge at
the sub-parametric $o_{p}(n^{-1/2})$ rate. This could be achieved, for
example, if each nuisance were estimated at the $o_{p}(n^{-1/4})$ rate, which
is obtainable for many non-parametric machine learning-based methods
(Chernozhukov et al., 2016). In addition, we require a technical boundedness
condition on the uniform norm of the errors and of the true nuisances
themselves. Given this, we can now present our main consistency and asymptotic
normality theorem.

######  Theorem 3.

Let the conditions of Theorem 2 be given, and assume that the nuisance
functions plugged into $\hat{v}^{(n)}_{\gamma}(\pi_{e})$ are estimated using
cross fitting. Furthermore, suppose that the nuisance estimation for each
cross-fitting fold satisfies Assumption 4. Then, we have
$\sqrt{n}(\hat{v}^{(n)}_{\gamma}(\pi_{e})-v_{\gamma}(\pi_{e}))\to\mathcal{N}(0,\sigma^{2}_{\text{DR}})$
in distribution, where

$\sigma^{2}_{\text{DR}}=\mathbb{E}_{\mathcal{P}_{b}}[(\psi_{\text{DR}}(\tau_{H})-v_{\gamma}(\pi_{e}))^{2}]$

The proof of Theorem 3 relies on the fact that $\psi_{\text{DR}}$ satisfies a
Neyman orthogonality condition with respect to all nuisance functions, and by
applying Chernozhukov et al. (2016, Theorem 3.1). We refer the reader to the
appendix for the detailed proof. We also note that Theorem 3 depends on the
nuisances being fit using cross-fitting. Concretely, this means that we
randomly split the observed trajectories into $K$ folds for some fixed $K\geq
2$, for each fold we compute separate nuisances $\hat{q}^{(t)}$ and
$\hat{h}^{(t)}$ using only the data outside of that fold, and then we compute
$\hat{v}^{(n)}_{\gamma}(\pi_{e})$ with each term
$\widehat{\psi}_{\text{DR}}(\tau_{H}^{(i)})$ computed using the nuisances
estimated excluding $\tau_{H}^{(i)}$. We refer the reader to Chernozhukov et
al. (2016) for a more detailed description of cross-fitting.

One technical note about this theorem is that there may be multiple $q^{(t)}$
and $h^{(t)}$ that solve Eqs. 2 and 4, which creates some ambiguity in both
Assumption 4 and the definition of $\psi_{\text{DR}}(\tau_{H})$. This is
important, since the ambiguity in the definition of
$\psi_{\text{DR}}(\tau_{H})$ effects the value of the asymptotic variance
$\sigma^{2}_{\text{DR}}$. In this case, we implicitly assume that Assumption 4
holds for some arbitrarily given solutions $q^{(t)}$ and $h^{(t)}$ for each
$t\in[H]$, and that $\sigma^{2}_{\text{DR}}$ is defined using the same
$q^{(t)}$ and $h^{(t)}$ solutions.

###  5.2 Semiparametric Efficiency

We now consider the question of _semiparametric efficiency_ of our OPE
estimators. Semiparametrically efficiency is defined relative to a model
$\mathcal{M}$, which is a set of allowed distributions such that
$\mathcal{P}_{b}\in\mathcal{M}$. Roughly speaking, we say that an estimator is
semiparametrically efficient _w.r.t._ $\mathcal{M}$ if it is regular (meaning
invariant to $O_{p}(1/\sqrt{n})$ perturbations in the data generating process
that are allowed by $\mathcal{M}$), and achieves the minimum asymptotic
variance of all regular estimators. We provide a detailed overview of
semiparametric efficiency in Appendix A, but for the purposes of this section
it suffices to say that there exists a function $\psi_{\text{eff}}\in
L_{2,\mathcal{P}_{b}}(\tau_{H})$, called the “efficient influence function”
(EIF) _w.r.t._ $\mathcal{M}$, and that an estimator
$\hat{v}^{(n)}_{\gamma}(\pi_{e})$ is efficient _w.r.t._ $\mathcal{M}$ if and
only if
$\sqrt{n}(\hat{v}^{(n)}_{\gamma}(\pi_{e})-v_{\gamma}(\pi_{e}))=n^{-1/2}\sum_{i=1}^{n}\psi_{\text{eff}}(\tau_{H}^{(i)})+o_{p}(1)$.

One complication in considering models of distributions on $\tau_{H}$ is that
technically the definition of $v_{\gamma}(\pi_{e})$ depends on the full
distribution of $\tau_{H}^{\textup{full}}$. In the case that the distribution
of $\tau_{H}$ corresponds to the logging distribution induced by some behavior
policy and underlying POMDP that satisfies Assumption 3, it is clear from
Theorem 2 that using _any_ nuisances satisfying the required conditional
moment will result in the same policy value estimate $v_{\gamma}(\pi_{e})$.
However, if we allow for distributions on $\tau_{H}$ that do not necessarily
satisfy such conditions, as is standard in the literature on policy
evaluation, it may be the case that different solutions for $h^{(t)}$ and
$q^{(t)}$ result in different values of
$\mathbb{E}_{\mathcal{P}}[\psi_{\text{DR}}(\tau_{H})]$. To avoid such issues,
we consider a model of distributions where the nuisances and corresponding
policy value estimate are uniquely defined, as follows.

######  Definition 1 (Model and Target Parameter).

Define $\mathcal{M}_{e}^{(0)}$ as the set of all distributions on $\tau_{H}$,
and for each $t\geq 1$ recursively define:

  1. 1.

$\eta_{t,\mathcal{P}}=\prod_{s=1}^{t-1}q^{(s)}_{\mathcal{P}}(Z_{s},A_{s})\mathds{1}\\{A_{s}=E_{s}\\}$,
for $\mathcal{P}\in\mathcal{M}_{e}^{(t-1)}$

  2. 2.

$P^{*}_{t,\mathcal{P}}(A_{t}\mid
W_{t})=\mathbb{E}_{\mathcal{P}}[\eta_{t,\mathcal{P}}\mid
W_{t},A_{t}]P_{\mathcal{P}}(A_{t}\mid W_{t})$, for
$\mathcal{P}\in\mathcal{M}_{e}^{(t-1)}$

  3. 3.

$T_{t,\mathcal{P}}:L_{2,\mathcal{P}}(Z_{t},A_{t})\mapsto
L_{2,\mathcal{P}}(W_{t},A_{t})$ where
$(T_{t,\mathcal{P}}g)(W_{t},A_{t})=\mathbb{E}_{\mathcal{P}}[\eta_{t,\mathcal{P}}g(Z_{t},A_{t})\mid
W_{t},A_{t}]$, for $\mathcal{P}\in\mathcal{M}_{e}^{(t-1)}$

  4. 4.

$\mathcal{M}_{e}^{(t)}=\mathcal{M}_{e}^{(t-1)}\cap\\{\mathcal{P}:T_{t,\mathcal{P}}\text{
is invertible and }P^{*}_{t,\mathcal{P}}(A_{t}\mid W_{t})^{-1}\in
L_{2,\mathcal{P}}(W_{t},A_{t})\\}$

  5. 5.

$q^{(t)}_{\mathcal{P}}(Z_{t},A_{t})=T_{t,\mathcal{P}}^{-1}\left(P^{*}_{t,\mathcal{P}}(A_{t}\mid
W_{t})^{-1}\right)$, for $\mathcal{P}\in\mathcal{M}_{e}^{(t)}$

Furthermore, let $T^{*}_{t,\mathcal{P}}$ denote the adjoint of
$T_{t,\mathcal{P}}$, define $Y_{H}=R_{h}$, and for each $t\in[H]$ recursively
define

  1. 1.

$\mu_{t,\mathcal{P}}(Z_{t},A_{t})=\mathbb{E}_{\mathcal{P}}[\eta_{t,\mathcal{P}}\mathds{1}\\{A_{t}=E_{t}\\}Y_{t,\mathcal{P}}\mid
Z_{t},A_{t}]$, for $\mathcal{P}\in\mathcal{M}_{e}^{(t)}$

  2. 2.

$h^{(t)}_{\mathcal{P}}(W_{t},A_{t})=(T^{*}_{t,\mathcal{P}})^{-1}\left(\mu_{t,\mathcal{P}}(Z_{t},A_{t})\right)$,
for $\mathcal{P}\in\mathcal{M}_{e}^{(t)}$

  3. 3.

$Y_{t-1,\mathcal{P}}=R_{t-1}+\gamma\left(\sum_{a\in\mathcal{A}}h^{(t)}_{\mathcal{P}}(W_{t},a)+q^{(t)}_{\mathcal{P}}(Z_{t},A_{t})\left(\mathds{1}\\{A_{t}=E_{t}\\}Y_{t,\mathcal{P}}-h^{(t)}_{\mathcal{P}}(W_{t},A_{t})\right)\right)$,
for $\mathcal{P}\in\mathcal{M}_{e}^{(t)}$

where the latter is only defined for $t>1$. Finally, let
$\mathcal{M}_{\textup{PCI}}=\mathcal{M}_{e}^{(H)}$, and for each
$\mathcal{P}\in\mathcal{M}_{\textup{PCI}}$ define

$V(\mathcal{P})=\mathbb{E}_{\mathcal{P}}\left[\sum_{a\in\mathcal{A}}h^{(1)}_{\mathcal{P}}(W_{1},a)\right]\,.$

We note that this definition is not circular, since $\eta_{1,\mathcal{P}}=1$
for every $\mathcal{P}$, and so we can concretely define the first set of
quantities in the order they are listed above for each $t\in[H]$ in ascending
order, and the second set in descending order of $t$. We note that in the case
that $\mathcal{P}=\mathcal{P}_{b}$, it is straightforward to reason that
$\eta_{t,\mathcal{P}_{b}}$, $q_{\mathcal{P}_{b}}^{(t)}$,
$h_{\mathcal{P}_{b}}^{(t)}$, and $Y_{t,\mathcal{P}_{b}}$ agree with the
corresponding definitions in Theorems 2 and 1; $T_{t,\mathcal{P}_{b}}$ and
$T^{*}_{t,\mathcal{P}_{b}}$ correspond to standard conditional expectation
operators under $\mathcal{P}^{*}_{t}$; $P^{*}_{t,\mathcal{P}_{b}}(A_{t}\mid
W_{t})=P^{*}_{t}(A_{t}\mid W_{t})$; and
$V(\mathcal{P}_{b})=v_{\gamma}(\pi_{e})$. Therefore,
$\mathcal{M}_{\textup{PCI}}$ is a natural model of observational distributions
where the required nuisances are uniquely defined, and $V(\mathcal{P})$ is a
natural and uniquely defined generalization of $v_{\gamma}(\pi_{e})$ for
distributions $\mathcal{P}$ that cannot be defined as the logging distribution
for some POMDP and behavior policy satisfying Assumption 3.

Finally, we assume the following the following on the actual observed
distribution $\mathcal{P}_{b}$.

######  Assumption 5.

For every sequence of distributions $\mathcal{P}_{n}$ that converge in law to
$\mathcal{P}_{b}$, there exists some integer $N$ such that for all $n\geq N$
and $t\in[H]$ such that $T_{t,\mathcal{P}_{n}}$ and
$T^{*}_{t,\mathcal{P}_{n}}$ are invertible. Furthermore, for all such
sequences and $t\in[H]$ we also have

  1. 1.

$\liminf_{n\to\infty}\inf_{\|f(Z_{t},A_{t})\|_{1,\mathcal{P}_{n}}\geq
1}\|T_{t,\mathcal{P}_{n}}f(Z_{t},A_{t})\|_{1,\mathcal{P}_{n}}>0$

  2. 2.

$\liminf_{n\to\infty}\inf_{\|g(W_{t},A_{t})\|_{1,\mathcal{P}_{n}}\geq
1}\|T^{*}_{t,\mathcal{P}_{n}}g(W_{t},A_{t})\|_{1,\mathcal{P}_{n}}>0$

  3. 3.

$\limsup_{n\to\infty}\|P^{*}_{t,\mathcal{P}_{n}}(A_{t}\mid
W_{t})^{-1}\|_{\infty}<\infty$ .

In addition, for each $t\in[H]$ the distribution $\mathcal{P}_{b}$ satisfies

  1. 4.

$\inf_{\|f(Z_{t},A_{t})\|_{2,\mathcal{P}_{b}}\geq
1}\|T_{t,\mathcal{P}_{n}}f(Z_{t},A_{t})\|_{2,\mathcal{P}_{b}}>0$

  2. 5.

$\inf_{\|g(W_{t},A_{t})\|_{2,\mathcal{P}_{n}}\geq
1}\|T^{*}_{t,\mathcal{P}_{n}}g(W_{t},A_{t})\|_{2,\mathcal{P}_{b}}>0$ .

The condition that $T_{t,\mathcal{P}_{n}}$ and $T^{*}_{t,\mathcal{P}_{n}}$ are
invertible for large $n$ ensures that the model $\mathcal{M}_{\textup{PCI}}$
is locally saturated at $\mathcal{P}_{b}$, and the additional conditions
ensure that the nuisance functions can be uniformly bounded within parametric
submodels. These are very technical conditions used in our semiparametric
efficiency proof, and it may be possible to relax them. We note also that in
discrete settings, these conditions follow easily given
$\mathcal{P}_{b}\in\mathcal{M}_{\textup{PCI}}$, since in this setting the
conditions can be characterized in terms of the entries or eigenvalues of some
probability matrices being bounded away from zero, which by continuity must be
the case when $\mathcal{P}_{n}$ is sufficiently close to $\mathcal{P}_{b}$. In
continuous settings this kind of reasoning becomes more complicated, but it
might still be possible to derive Assumption 5 from simpler assumptions.

Importantly, the locally saturated condition on $\mathcal{M}_{\textup{PCI}}$
at $\mathcal{P}_{b}$ means that we do not have to explicitly consider the
tangent space of $\mathcal{M}_{\textup{PCI}}$. We chose to enforce this since
the correct tangent space under more general assumptions appears to be very
complex and difficult to define concretely. Furthermore, although more
specific tangent spaces have been proposed in past work on proximal causal
inference, their correctness has not been properly justified. We do not
explore these issues here in further detail as they are technically complex
and besides the point of this paper, but for completeness we provide details
in Appendix B.

Given this setup, we can now present our main efficiency result.

######  Theorem 4.

Suppose that $\mathcal{P}_{b}$ is the observational distribution given by a
POMDP and logging policy that satisfies the conditions of Theorem 2, and let
Assumption 5 be given. Then, $\psi_{\text{DR}}(\tau_{H})-v_{\gamma}(\pi_{e})$
is the efficient influence function for $V(\mathcal{P})$ locally at
$\mathcal{P}=\mathcal{P}_{b}$.

Finally, the following corollary combines this result with Theorem 3, which
shows that under the same conditions, if the nuisances are appropriately
estimated then the resulting estimator will achieve the semiparametric
efficiency bound relative to $\mathcal{M}_{\textup{PCI}}$.

######  Corollary 2.

Let the conditions of Theorems 3 and 4 be given. Then, the estimator
$\hat{v}^{(n)}_{\gamma}(\pi_{e})$ is semi-parametrically efficient relative to
the model $\mathcal{M}_{\textup{PCI}}$.

###  5.3 Nuisance Estimation

Finally, we conclude this section with a discussion of how we may actually
estimate $q^{(t)}$ and $h^{(t)}$. The conditional moment equations Eqs. 2 and
4 defining these nuisances are defined in terms of the intervention
distributions $\mathcal{P}^{*}_{t}$, which are not directly observable.
Therefore, we provide the following lemma, which re-frames these as a nested
series of conditional moment restrictions under $\mathcal{P}_{b}$.

######  Lemma 2.

Let the conditions of Theorem 2 be given. Then, for any collection of
functions $q^{(1)},\ldots,q^{(H)}$ and $h^{(1)},\ldots,h^{(H)}$, these
functions satisfy Eqs. 2 and 4 for every $t\in[H]$ if and only if for every
$t\in[H]$ we have

$\mathbb{E}_{\mathcal{P}_{b}}\left[\eta_{t}\left(g(W_{t},A_{t})q^{(t)}(Z_{t},A_{t})-\sum_{a\in\mathcal{A}}g(W_{t},a)\right)\right]=0\,,$

for all measurable $g(W_{t},A_{t})$, and

$\mathbb{E}_{\mathcal{P}_{b}}\left[\eta_{t}\left(h^{(t)}(W_{t},A_{t})-\mathds{1}\\{E_{t}=A_{t}\\}Y_{t}\right)\,\Big{|}\,Z_{t},A_{t}\right]=0\quad\text{a.s.}\,,$

where $\eta_{t}$ and $Y_{t}$ are defined as in Corollary 1.

We can observe that the moment restrictions defining $q^{(t)}$ for each $t$
depend only on $q^{(t^{\prime})}$ for $t^{\prime}<t$, and those defining
$h^{(t)}$ for each $t$ depend on $h^{(t^{\prime})}$ for $t^{\prime}>t$ and on
$q^{(t^{\prime\prime})}$ for every $t^{\prime\prime}\neq t$. This suggests a
natural order for estimating these nuisances, of $q^{(1)}$ through $q^{(H)}$
first, and then $h^{(H)}$ through $h^{(1)}$. Alternatively, we may jointly
solve for all these nuisances together as a set of $2H$ continua of moment
equations. In addition, the above moment restrictions defining $q^{(t)}$ have
the advantage that they do not explicitly depend on any additional nuisance
functions such as $P^{*}_{t}(A_{t}\mid W_{t})^{-1}$.

Next, we propose a specific meta-algorithm for estimating these nuisances
sequentially, based on the Kernel VMM algorithm of Bennett and Kallus (2021),
which was previously proposed for solving conditional moment problems. This
meta-algorithm assumes some function classes $\mathcal{Q}^{(t)}$ and
$\mathcal{H}^{(t)}$ from which our estimates $q^{(t)}$ and $h^{(t)}$ will be
chosen for each $t\in[H]$. In addition, it requires kernel functions
$K^{(q,t)}$ and $K^{(h,t)}$ for each $t\in[H]$, where the former is defined on
pairs of $(W_{t},A_{t})$ tuples, and the latter on pairs of $(Z_{t},A_{t})$
tuples, as well as hyperparameters $\alpha^{(q,t)}\geq 0$ and
$\alpha^{(h,t)}\geq 0$, and optional regularization functions
$\mathcal{R}^{(q,t)}$ on $q\in\mathcal{Q}^{(t)}$ and $\mathcal{R}^{(h,t)}$ on
$h\in\mathcal{H}^{(t)}$. We note that any or more of the above inputs may in
general be data-driven. Furthermore, for any random variable $X$ measurable
_w.r.t._ $\tau_{H}$ we let $\mathbb{S}(X)$ denote the set of unique values of
$X$ observed in our dataset, define $N(X)=|\mathbb{S}(X)|$, and denote the
elements of $\mathbb{S}(X)$ by
$\\{\mathbb{S}(X)_{1},\ldots,\mathbb{S}(X)_{N(X)}\\}$, where the ordering of
the elements is arbitrary but fixed. We note that for any $X$ it must be the
case that $N(X)\leq n$, since we only observe $n$ trajectories $\tau_{H}$.
Similarly, we define
$\mathbb{S}(X;\mathcal{A})=\\{(x,a):x\in\mathbb{S}(X),a\in\mathcal{A}\\}$,
$N(X;\mathcal{A})=|\mathcal{A}|N(X)$, and again assume an arbitrary but fixed
ordering of the elements in $\mathbb{S}(X;\mathcal{A})$. Finally, we assume
access to some prior estimates $\tilde{q}^{(t)}$ and $\tilde{h}^{(t)}$, which
may be defined arbitrarily and need not necessarily be consistent. Given this,
we present our algorithm in Algorithm 1.

Algorithm 1 Sequential VMM for PCI-POMDP Nuisance Estimation

1: Data $\mathcal{D}=(\tau_{H}^{(1)},\ldots,\tau_{H}^{(n)})$, nuisance
function classes $\mathcal{Q}^{(t)}$ and $\mathcal{H}^{(t)}$, kernel functions
$K^{(q,t)}$ and $K^{(h,t)}$, hyperparameters $\alpha^{(q,t)}$ and
$\alpha^{(h,t)}$, prior estimates $\tilde{q}^{(t)}$ and $\tilde{h}^{(t)}$, and
optional regularization functions $\mathcal{R}^{(q,t)}$ and
$\mathcal{R}^{(h,t)}$, for all $t\in[H]$

2:Nuisance estimates $\hat{q}^{(t)}$ and $\hat{h}^{(t)}$ for all $t\in[H]$

3:for $t\in\\{1,2,\ldots,H\\}$ do

4: if $t=1$ then

5: $\eta_{i}^{(t)}\leftarrow 1$ $\triangleright$ $i\in[n]$

6: else

7:
$\eta_{i}^{(t)}\leftarrow\eta_{i}^{(t-1)}\mathds{1}\\{A_{t-1}^{(i)}=E_{t-1}^{(i)}\\}\hat{q}^{(t-1)}(Z_{t-1}^{(i)},A_{t-1}^{(i)})$
$\triangleright$ $i\in[n]$

8: end if

9: $\hat{q}^{(t)}\leftarrow$ ComputeQ($\mathcal{D}$, $t$, $\mathcal{Q}^{(t)}$,
$\mathcal{R}^{(q,t)}$, $\alpha^{(q,t)}$, $\tilde{q}^{(t)}$, $K^{(q,t)}$,
$\eta^{(t)}$)

10:end for

11:for $t\in\\{H,H-1,\ldots,1\\}$ do

12: if t = H then

13: $\omega_{i}^{(t)}\leftarrow 0$ $\triangleright$ $i\in[n]$

14: else

15:
$\omega_{i}^{(t)}\leftarrow\sum_{a\in\mathcal{A}}\hat{h}^{(t+1)}(W^{(i)}_{t+1},a)+\hat{q}^{(t+1)}(Z^{(i)}_{t+1},A^{(i)}_{t+1})\left(\mu_{i}^{(t+1)}-\hat{h}^{(t+1)}(W^{(i)}_{t+1},A^{(i)}_{t+1})\right)$
$\triangleright$ $i\in[n]$

16: end if

17:
$\mu_{i}^{(t)}\leftarrow\mathds{1}\\{A_{t}^{(i)}=E_{t}^{(i)}\\}(R_{t}^{(i)}+\gamma\omega_{i}^{(t)})$
$\triangleright$ $i\in[n]$

18: $\hat{h}^{(t)}\leftarrow$ ComputeH($\mathcal{D}$, $t$,
$\mathcal{H}^{(t)}$, $\mathcal{R}^{(h,t)}$, $\alpha^{(h,t)}$,
$\tilde{h}^{(t)}$, $K^{(h,t)}$, $\eta^{(t)}$, $\mu^{(t)}$)

19:end for

20:return $\hat{q}^{(1)},\ldots,\hat{q}^{(H)}$,
$\hat{h}^{(1)},\ldots,\hat{h}^{(H)}$

21:function ComputeQ($\mathcal{D}$, $t$, $\mathcal{Q}$, $\mathcal{R}$,
$\alpha$, $\tilde{q}$, $K$, $\eta$)

22: $L_{i,j}\leftarrow
K((W_{t}^{(i)},A_{t}^{(i)}),\mathbb{S}(W_{t};\mathcal{A})_{j})$
$\triangleright$ $i\in[n],j\in[N(W_{t};\mathcal{A})]$

23:
$\tilde{L}_{i,j}\leftarrow\sum_{a\in\mathcal{A}}K((W_{t}^{(i)},a),\mathbb{S}(W_{t};\mathcal{A})_{j})$
$\triangleright$ $i\in[n],j\in[N(W_{t};\mathcal{A})]$

24:
$M_{i,j}\leftarrow\eta_{i}\left(\tilde{q}(Z_{t}^{(i)},A_{t}^{(i)})L_{k,j}-\tilde{L}_{k,j}\right)$
$\triangleright$ $i\in[n],j\in[N(W_{t};\mathcal{A})]$

25: $Q_{i,j}\leftarrow\frac{1}{n}\sum_{k=1}^{n}M_{k,i}M_{k,j}+\alpha
K(\mathbb{S}(W_{t};\mathcal{A})_{i},\mathbb{S}(W_{t};\mathcal{A})_{j})$
$\triangleright$ $i,j\in[N(W_{t};\mathcal{A})]$

26:
$B_{i,j}\leftarrow\frac{1}{n}\sum_{k=1}^{n}\eta_{k}L_{k,i}\mathds{1}\\{(Z_{t}^{(k)},A_{t}^{(k)})=\mathbb{S}(Z_{t},A_{t})_{j}\\}$
$\triangleright$ $i\in[N(W_{t};\mathcal{A})],j\in[N(Z_{t},A_{t})]$

27:
$\rho(q)_{i}\leftarrow\sum_{j\in[N(Z_{t},A_{t})]}B_{i,j}q(\mathbb{S}(Z_{t},A_{t})_{j})-\frac{1}{n}\sum_{k=1}^{n}\eta_{k}\tilde{L}_{k,i}$
$\triangleright$ $i\in[N(W_{t};\mathcal{A})],q\in\mathcal{Q}$

28: return
$\operatorname*{arg\,min}_{q\in\mathcal{Q}}\rho(q)^{T}Q^{-1}\rho(q)+\mathcal{R}(q)$

29:end function

30:function ComputeH($\mathcal{D}$, $t$, $\mathcal{H}$, $\mathcal{R}$,
$\alpha$, $\tilde{h}$, $K$, $\eta$, $\mu$)

31: $L_{i,j}\leftarrow
K((Z_{t}^{(i)},A_{t}^{(i)}),\mathbb{S}(Z_{t},A_{t})_{j})$ $\triangleright$
$i\in[n],j\in[N(Z_{t},A_{t})]$

32:
$M_{i,j}\leftarrow\eta_{i}L_{k,j}\left(\tilde{h}^{(t)}(W_{t}^{(i)},A_{t}^{(i)})-\mu_{i}\right)$
$\triangleright$ $i\in[n],j\in[N(Z_{t},A_{t})]$

33: $Q_{i,j}\leftarrow\frac{1}{n}\sum_{k=1}^{n}M_{k,i}M_{k,j}+\alpha
K(\mathbb{S}(Z_{t},A_{t})_{i},\mathbb{S}(Z_{t},A_{t})_{j})$ $\triangleright$
$i,j\in[N(Z_{t},A_{t})]$

34:
$B_{i,j}\leftarrow\frac{1}{n}\sum_{k=1}^{n}\eta_{k}L_{k,i}\mathds{1}\\{(W_{t}^{(k)},A_{t}^{(k)})=\mathbb{S}(W_{t},A_{t})_{j}\\}$
$\triangleright$ $i\in[N(Z_{t},A_{t})],j\in[N(W_{t},A_{t})]$

35:
$\rho(h)_{i}\leftarrow\sum_{j\in[N(W_{t},A_{t})]}B_{i,j}h(\mathbb{S}(W_{t},A_{t})_{j})-\frac{1}{n}\sum_{k=1}^{n}\eta_{k}\mu_{k}L_{k,i}$
$\triangleright$ $i\in[N(Z_{t},A_{t})],h\in\mathcal{H}$

36: return
$\operatorname*{arg\,min}_{h\in\mathcal{H}}\rho(h)^{T}Q^{-1}\rho(h)+\mathcal{R}(h)$

37:end function

We provide a derivation of this algorithm in Appendix D. We note that it is a
meta-algorithm, since it requires some additional procedures to solve the
respective minimization problems over $q\in\mathcal{Q}^{(t)}$ and
$h\in\mathcal{\mathcal{missing}}H^{(t)}$ at the end of ComputeQ and ComputeH
respectively. However, solving such problems is very standard and well
studied, so we do not consider it explicitly. In the case that the data is
discrete this algorithm is very efficient in terms of how it scales with $n$.
In this case the overall computational cost is $O(Hn)$, since
$N(Z_{t},A_{t})$, $N(W_{t},A_{t})$, and $N(W_{t};\mathcal{A})$ are bounded for
each $t\in[H]$. On the other hand, if the data is continuous, the algorithm is
still valid, although it may be expensive for large $n$ (in particular, in
this case both ComputeQ and ComputeH require computing the inverse of a
$n\times n$ matrix). In this case, it may be more computationally tractable to
consider alternative algorithms, such as an analogue of Algorithm 1 based on
Neural VMM instead of Kernel VMM (Bennett and Kallus, 2021). However, we leave
this problem to future work. Finally, we note that in practice, as in Bennett
and Kallus (2021), we may iterate Algorithm 1 multiple times, each time using
the previous iterate solution for the prior estimates $\tilde{q}^{(t)}$ and
$\tilde{h}^{(t)}$.

##  6 Experiments

###  6.1 Experimental Setup

$s_{1}$$s_{2}$$s_{3}$3.01.08.00.0-2.0-2.0 Figure 3: Graphical representation
of the NoisyObs POMDP scenario. Red dashed edges / blue solid edges represent
the transitions under actions $a_{1}$ / $a_{2}$ respectively, and the numeric
label for each edge indicates the corresponding reward. Note that all
transitions and rewards in NoisyObs are deterministic, and do not depend on
the time index. In each state $s_{i}$ we receive observation $o_{i}$ with
probability $1-\epsilon_{\textup{noise}}$, or observatoin $o_{j}$ with
probability $\epsilon_{\textup{noise}}/2$, for each $j\neq i$.

Finally, we present a series of experiments, which are intended as an
empirical “proof of concept” of the correctness of our theory and algorithms.
In these experiments, we consider a simple POMDP, which we refer to as
NoisyObs, which is a time-homogeneous POMDP with three states, two actions,
and three observation values. We denote these by
$\mathcal{S}=\\{s_{1},s_{2},s_{3}\\}$, $\mathcal{A}=\\{a_{1},a_{2}\\}$, and
$\mathcal{O}=\\{o_{1},o_{2},o_{3}\\}$. We summarize the state transition and
reward structure of the POMDP in Fig. 3. The observation emission process for
this POMDP is given by

$P_{O}^{(t)}(o_{i}\mid s_{j})=\begin{cases}1-\epsilon_{\textup{noise}}&i=j\\\
\epsilon_{\textup{noise}}/2&i\neq j\end{cases}$

for all $t\in[H]$, where $\epsilon_{\textup{noise}}$ is a parameter of the
POMDP. We note that these observations can be seen as a noisy measurement of
the state; _i.e._ , we observe the correct state with probability
$1-\epsilon_{\textup{noise}}$, or a randomly selected incorrect state with
probability $\epsilon_{\textup{noise}}$. In the case that
$\epsilon_{\textup{noise}}=0$ the problem becomes a MDP, and greater values of
$\epsilon_{\textup{noise}}$ indicate more noisy measurements. Thus, NoisyObs
provides a simple model for evaluating sequential decision making policies,
where the logged data may be corrupted.

| $a_{1}$ | $a_{2}$
---|---|---
$s_{1}$ | 0.8 | 0.2
$s_{2}$ | 0.8 | 0.2
$s_{3}$ | 0.2 | 0.8

| $a_{1}$ | $a_{2}$
---|---|---
$o_{1}$ | 1 | 0
$o_{2}$ | 1 | 0
$o_{3}$ | 0 | 1

| $a_{1}$ | $a_{2}$
---|---|---
$o_{1}$ | 0 | 1
$o_{2}$ | 0 | 1
$o_{3}$ | 1 | 0

| $a_{1}$ | $a_{2}$
---|---|---
$o_{1}$ | 1 | 0
$o_{2}$ | 0 | 1
$o_{3}$ | 1 | 0

Table 1: The first table summarizes the probability distribution of the
logging policy $\pi_{b}^{\textsc{NoisyObs}}$, where each row gives the
probability distribution over actions for the corresponding state. The next
three tables similarly summarize the three evaluation policies
$\pi_{e}^{\textup{easy}}$, $\pi_{e}^{\textup{hard}}$, and
$\pi_{e}^{\textup{optim}}$ respectively, which are all deterministic policies
that depend on the current observation only. Note that none of these policies
depend on the time index.

We collected logged data using a time-homogeneous behavioral policy
$\pi_{b}^{\textsc{NoisyObs}}$, with a horizon length $H=3$. For each logged
trajectory first sample a prior state $S_{0}$ by $s_{1}$, $s_{2}$, or $s_{3}$
with probabilities $0.5$, $0.3$, and $0.2$ respectively, a prior observation
$O_{0}\sim P_{O}(\cdot\mid S_{0})$, and a prior action
$A_{0}\sim\pi_{b}^{\textsc{NoisyObs}}(\cdot\mid S_{0})$, and the initial state
$S_{1}$ is given by transitioning from $S_{0}$ with $A_{0}$. In addition, we
considered evaluating three different evaluation policies
$\pi_{e}^{\textup{easy}}$, $\pi_{e}^{\textup{hard}}$, and
$\pi_{e}^{\textup{optim}}$, each of which is also time-homogeneous and depends
only on the current observation. The probability tables for all four policies
are summarized in Table 1. We note that $\pi_{e}^{\textup{easy}}$ and
$\pi_{e}^{\textup{hard}}$ are so because they are designed to have high and
low overlap with the logging policy respectively, and
$\pi_{e}^{\textup{optim}}$ is named so because it is the optimal policy when
$\epsilon_{\textup{noise}}$ is sufficiently small. Therefore these cover a
wide range of different kinds of policies; one with strong overlap, one with
poor overlap, and a high-performing policy with overlap somewhere in the
middle. In all cases, we consider estimating the value of the corresponding
policy with $\gamma=1$.

We performed policy evaluation with the following methods. First, we used our
method described in Section 5 with 5-fold cross-fitting, with nuisance
estimation following Algorithm 1, which we refer to as Ours. We used the PCI
reduction given by setting $Z_{t}=O_{t-1}$, and $W_{t}=O_{t}$, and did not
include an explicit $X_{t}$. For every $t\in[H]$ we set the inputs to the
algorithm as follows: $\mathcal{H}^{(t)}$ and $\mathcal{Q}^{(t)}$ were the set
of all tabular functions; all regularization functions were set as
$\mathcal{R}(f)=\lambda\|f\|_{2,n}$, for some fixed hyperparameter $\lambda$;
all values of $\alpha^{(q,t)}$ and $\alpha^{(h,t)}$ were set a to a common
hyperparameter $\alpha$; and the kernels $K^{(q,t)}$ and $K^{(h,t)}$ were set
as in Bennett and Kallus (2021), using the same process of combining three
Gaussian kernels with automatically calibrated bandwidths based on the
variance of the data. Furthermore, the inputs to the kernel functions were
given by concatenating one-hot embeddings of $Z_{t}$ and $A_{t}$ or $W_{t}$
and $A_{t}$. We describe the selection of hyperparameters $\alpha$ and
$\lambda$ in Appendix E. In addition, we implemented the following benchmark
methods:

  1. 1.

MeanR: This is a naive baseline given by
$\frac{1}{n}\sum_{i=1}^{n}\sum_{t=1}^{H}\gamma^{t}R_{t}^{(i)}$

  2. 2.

MDP: This is a model-based baseline given by fitting a tabular MDP to the
observed data based on the observed counts and treating the observations as
states, and computing the value of $\pi_{e}$ on this model using dynamic
programming

  3. 3.

TIS: This is given by estimating the time-independent sampling identification
quantity defined by Theorems 1 and 1, by estimating the required probability
matrices directly from the observed counts, and replacing the expectation over
$\mathcal{P}_{\text{ind}}$ with its empirical analogue, based on summing over
all $n^{H}$ combinations of separately sampling an observed trajectory at each
time step.

For full details of the implementation of each method, see our code at
https://github.com/CausalML/ProximalRL.

###  6.2 Results

|
---|---
|
|
Figure 4: Experiment results with $\epsilon_{\textup{noise}}=0$. In the top, middle, and bottom rows we display results for estimating the policy value of $\pi_{e}^{\textup{easy}}$, $\pi_{e}^{\textup{hard}}$, and $\pi_{e}^{\textup{optim}}$ respectively. On the left we display the mean policy value estimate for each method and each value of $n$, where the solid black line corresponds to the true policy value, and the shaded regions correspond to one standard deviations of the policy value estimates. On the right we display the corresponding mean squared error of these estimates, where the shaded regions correspond to 95% confidence intervals for these values. |
---|---
|
|
Figure 5: Experiment results with $\epsilon_{\textup{noise}}=0.2$. Results
displayed as in Fig. 4

We now present results policy evaluation for for the above scenario and
policies, using both our method and the above benchmarks. Specifically, for
each $n\in\\{200,500,1000,2000,5000,10000\\}$,
$\pi_{e}\in\\{\pi_{e}^{\textup{easy}},\pi_{e}^{\textup{hard}},\pi_{e}^{\textup{optim}}\\}$,
and $\epsilon\in\\{0,0.2\\}$ we repeated the following process $100$ times:
(1) we sampled $n$ trajectories with horizon length $H=3$, behavior policy
$\pi_{b}^{\textsc{NoisyObs}}$ and noise level
$\epsilon_{\textup{noise}}=\epsilon$; and (2) estimated $v_{1}(\pi_{e})$ using
these $n$ trajectories for each method.

First, in Fig. 4 we display results in the unconfounded case, where
$\epsilon_{\textup{noise}}=0$ (_i.e._ , MDP setting). We can observe that in
this case, both our method and the MDP baseline appear to be consistent, with
accurate estimates of the policy value as $n\to\infty$, as would be expected.
In this setting, the MDP method is generally more accurate than ours with
lower-variance estimates, which makes sense since ours is designed for much
more general conditions.

Next, in Fig. 5 we display results for the confounded case where
$\epsilon_{\textup{noise}}=0.2$ (_i.e._ , POMDP setting). Here, we see that
our method remains consistent, while the MDP method, which is only designed to
work in MDP settings, does not. The only exception is for estimating the value
of $\pi_{e}^{\textup{easy}}$, however this is only because MDP just happens to
have very small bias for estimating this policy, which is serendipitous and
not something that can be guaranteed in general. In general, our method has
much higher variance in this more challenging setting compared with the
previous one, especially for smaller values of $n$. That said, when $n$ is
large the method works very accurately.

Finally, we note that in general, as expected, the MeanR benchmark is
inconsistent in both scenarios, and only works when the target policy just
happens to be be close to the mean logged reward. Furthermore, despite our
identification theory in Section 4.1, the TIS method in general performs very
poorly. In some sense this is unsurprising, since as discussed in Section 4.1
the identification result is of an unusual form (as an expectation over
$\mathcal{P}_{\text{ind}}$), and we did not provide any theory of the
resulting plug-in algorithm’s convergence. Furthermore, in our pilot
experiments we experimented a similar method by instead directly computing the
identification result given by Tennenholtz et al. (2020, Theorem 1) by summing
over all possible trajectories, with empirical estimates of probability
matrices plugged in. However, this approach had similar problems, with errors
significantly greater even than TIS,555We speculate that this occurs because
unlike TIS the estimate is not normalized; it is computed as a sum over all
trajectories rather than as the mean of some empirical distribution, so the
resulting policy value estimates can take values well outside the range of
observed rewards. so we did not include these results. It is possible that,
_e.g._ , more sophisticated approaches to regularizing the nuisance estimation
for such approaches could make them work well, however even then they would
suffer from the theoretical limitations discussed in Section 4.1.

##  7 Conclusion

In this paper, we discussed the problem of OPE for POMDPs. First, we analyzed
the recently proposed approach for identifying the policy value for tabular
POMDPs (Tennenholtz et al., 2020). We showed that while it could be placed
within a more general framework and extended to continuous settings, it
suffers from some theoretical limitations due to the unusual form of the
identification quantity, which brings into question how useful it could be for
actually constructing estimators with good qualities, such as regularity,
$\sqrt{n}$-asymptotic normality, _etc_. Then, motivated by these limitations,
we proposed a new framework for identifying the policy value by sequentially
reducing the problem to a series of proximal causal inference problems. Then,
we extended this identification framework to a framework of estimators based
on double machine learning and cross-fitting (Chernozhukov et al., 2016), and
showed that under appropriate conditions such estimators are asymptotically
normal and semiparametrically efficient. Furthermore, we provided a concrete
algorithm for implementing such an estimator based on recent approaches to
solving conditional moment problems (Bennett and Kallus, 2021). Finally, we
performed an empirical investigation of our proposed estimators in synthetic
settings, and demonstrated that indeed our approach is consistent, even in
confounded settings where standard approaches to OPE fail.

Perhaps the most significant scope for future work on this topic is in the
development of more practical algorithms. Indeed, although our experiments
were only intended as a “proof of concept” of our theory, they also show that
our actual proposed estimators have very high variance with a moderate number
(_e.g._ , 1000) of trajectories, even in this extremely simple toy POMDP.
There are many approaches that may improve on this; for example it may be
beneficial to solve the conditional moment problems defining the $q^{(t)}$ and
$h^{(t)}$ functions simultaneously rather than sequentially as we proposed,
which may result in cascading errors. Related to this, our proposed approach
for solving the conditional moment problems under the intervention
distributions $\mathcal{P}^{*}_{t}$ is to use the functions $q^{(t^{\prime})}$
for $t^{\prime}<t$ (as in Lemma 2), which is akin to an importance sampling
approach. This could be inefficient, and alternative approaches akin to a
direct or doubly robust approach may be possible. Furthermore, although we
showed that our approach can work in toy settings, the hyperparameters needed
for good performance varied from setting to setting. Unfortunately, given
unobserved confounding it is inherently challenging to perform hyperparameter
optimization without actually performing experimentation. Therefore, another
important topic for future work is on more practical approaches to
hyperparameter optimization and algorithm selection for the nuisance
estimation. We note that this is an important and under-explored topic for
problems involving unmeasured confounding in general.

Another area where there is significant scope for future work is on the topic
of semiparametric efficiency. We provided efficiency theory under relatively
strong assumptions which ensure that all of the nuisances are uniquely
determined and that the model is locally saturated. However, this may be
unrealistic in general. Relaxing this assumption means that the tangent set
under consideration becomes more complex, and as previously discussed the
existing work on proximal causal inference does not address how to handle this
correctly. Therefore, working out what the tangent set looks like under more
general assumptions, what form the efficient influence function takes, and
under what conditions (if any) it takes a form similar to
$\psi_{\text{DR}}(\tau_{H})$ are important open questions. Furthermore, these
are also open question for proximal causal inference more generally, as they
are also unsolved in the case of $H=1$.

Finally, in terms of future work, there is the problem of how to actually
apply our theory, as well as policy value estimators as in Section 5, in a
useful way to real-world sequential decision making problems involving
unmeasured confounding. Ultimately, although our work is largely theoretical,
we hope that it will be impactful in motivating new approaches to solving such
challenging problems.

## References

  * Azizzadenesheli et al. (2016) K. Azizzadenesheli, A. Lazaric, and A. Anandkumar.  Reinforcement learning of pomdps using spectral methods.  In _Conference on Learning Theory_ , pages 193–256. PMLR, 2016.
  * Bennett and Kallus (2021) A. Bennett and N. Kallus.  The variational method of moments.  _arXiv preprint arXiv:2012.09422_ , 2021.
  * Bennett et al. (2021) A. Bennett, N. Kallus, L. Li, and A. Mousavi.  Off-policy evaluation in infinite-horizon reinforcement learning with latent confounders.  In _International Conference on Artificial Intelligence and Statistics_ , pages 1999–2007. PMLR, 2021.
  * Bhattacharya et al. (2020) S. Bhattacharya, S. Badyal, T. Wheeler, S. Gil, and D. Bertsekas.  Reinforcement learning for pomdp: Partitioned rollout and policy iteration with application to autonomous sequential repair problems.  _IEEE Robotics and Automation Letters_ , 5(3):3967–3974, 2020.
  * Chandak et al. (2021) Y. Chandak, S. Niekum, B. C. da Silva, E. Learned-Miller, E. Brunskill, and P. S. Thomas.  Universal off-policy evaluation.  _arXiv preprint arXiv:2104.12820_ , 2021.
  * Chen and Zhang (2021) S. Chen and B. Zhang.  Estimating and improving dynamic treatment regimes with a time-varying instrumental variable.  _arXiv preprint arXiv:2104.07822_ , 2021.
  * Chernozhukov et al. (2016) V. Chernozhukov, D. Chetverikov, M. Demirer, E. Duflo, C. Hansen, and W. K. Newey.  Double machine learning for treatment and causal parameters.  Technical report, cemmap working paper, 2016.
  * Cui et al. (2020) Y. Cui, H. Pu, X. Shi, W. Miao, and E. T. Tchetgen.  Semiparametric proximal causal inference.  _arXiv preprint arXiv:2011.08411_ , 2020.
  * Gasse et al. (2021) M. Gasse, D. Grasset, G. Gaudron, and P.-Y. Oudeyer.  Causal reinforcement learning using observational and interventional data.  _arXiv preprint arXiv:2106.14421_ , 2021.
  * Ghassami et al. (2021) A. Ghassami, A. Ying, I. Shpitser, and E. T. Tchetgen.  Minimax kernel machine learning for a class of doubly robust functionals.  _arXiv preprint arXiv:2104.02929_ , 2021.
  * Hu and Wager (2021) Y. Hu and S. Wager.  Off-policy evaluation in partially observed markov decision processes.  _arXiv preprint arXiv:2110.12343_ , 2021.
  * Kallus and Uehara (2019a) N. Kallus and M. Uehara.  Double reinforcement learning for efficient off-policy evaluation in Markov decision processes, 2019a.  arXiv:1908.08526.
  * Kallus and Uehara (2019b) N. Kallus and M. Uehara.  Efficiently breaking the curse of horizon in off-policy evaluation with double reinforcement learning, 2019b.  arXiv:1909.05850.
  * Kallus and Uehara (2020) N. Kallus and M. Uehara.  Double reinforcement learning for efficient off-policy evaluation in markov decision processes.  _Journal of Machine Learning Research_ , 21(167):1–63, 2020.
  * Kallus and Zhou (2020) N. Kallus and A. Zhou.  Confounding-robust policy evaluation in infinite-horizon reinforcement learning, 2020.  arXiv:2002.04518.
  * Kallus et al. (2021) N. Kallus, X. Mao, and M. Uehara.  Causal inference under unmeasured confounding with negative controls: A minimax learning approach.  _arXiv preprint arXiv:2103.14029_ , 2021.
  * Katt et al. (2017) S. Katt, F. A. Oliehoek, and C. Amato.  Learning in pomdps with monte carlo tree search.  In _International Conference on Machine Learning_ , pages 1819–1827. PMLR, 2017.
  * Killian et al. (2020) T. W. Killian, M. Ghassemi, and S. Joshi.  Counterfactually guided policy transfer in clinical settings.  _arXiv preprint arXiv:2006.11654_ , 2020.
  * Liao et al. (2021) L. Liao, Z. Fu, Z. Yang, M. Kolar, and Z. Wang.  Instrumental variable value iteration for causal offline reinforcement learning.  _arXiv preprint arXiv:2102.09907_ , 2021.
  * Miao et al. (2018a) W. Miao, Z. Geng, and E. J. Tchetgen Tchetgen.  Identifying causal effects with proxy variables of an unmeasured confounder.  _Biometrika_ , 105(4):987–993, 2018a.
  * Miao et al. (2018b) W. Miao, X. Shi, and E. T. Tchetgen.  A confounding bridge approach for double negative control inference on causal effects.  _arXiv preprint arXiv:1808.04945_ , 2018b.
  * Nair and Jiang (2021) Y. Nair and N. Jiang.  A spectral approach to off-policy evaluation for pomdps.  _arXiv preprint arXiv:2109.10502_ , 2021.
  * Namkoong et al. (2020) H. Namkoong, R. Keramati, S. Yadlowsky, and E. Brunskill.  Off-policy policy evaluation for sequential decisions under unobserved confounding.  _arXiv preprint arXiv:2003.05623_ , 2020.
  * Oberst and Sontag (2019) M. Oberst and D. Sontag.  Counterfactual off-policy evaluation with gumbel-max structural causal models.  In _International Conference on Machine Learning_ , pages 4881–4890. PMLR, 2019.
  * Shi et al. (2020) X. Shi, W. Miao, J. C. Nelson, and E. J. Tchetgen Tchetgen.  Multiply robust causal inference with double-negative control adjustment for categorical unmeasured confounding.  _Journal of the Royal Statistical Society: Series B (Statistical Methodology)_ , 82(2):521–540, 2020.
  * Singh et al. (2021) G. Singh, S. Peri, J. Kim, H. Kim, and S. Ahn.  Structured world belief for reinforcement learning in pomdp.  In _International Conference on Machine Learning_ , pages 9744–9755. PMLR, 2021.
  * Tchetgen et al. (2020) E. J. T. Tchetgen, A. Ying, Y. Cui, X. Shi, and W. Miao.  An introduction to proximal causal learning.  _arXiv preprint arXiv:2009.10982_ , 2020.
  * Tennenholtz et al. (2020) G. Tennenholtz, S. Mannor, and U. Shalit.  Off-policy evaluation in partially observable environments.  In _Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI)_ , 2020.
  * Van Der Vaart (1991) A. Van Der Vaart.  On differentiable functionals.  _The Annals of Statistics_ , pages 178–204, 1991.
  * Van der Vaart (2000) A. W. Van der Vaart.  _Asymptotic statistics_ , volume 3.  Cambridge university press, 2000.
  * Wang et al. (2020) L. Wang, Z. Yang, and Z. Wang.  Provably efficient causal reinforcement learning with confounded observational data.  _arXiv preprint arXiv:2006.12311_ , 2020.
  * Xu et al. (2021) L. Xu, H. Kanagawa, and A. Gretton.  Deep proxy causal learning and its application to confounded bandit policy evaluation.  _arXiv preprint arXiv:2106.03907_ , 2021.
  * Yang et al. (2021) C.-H. H. Yang, I. Hung, T. Danny, Y. Ouyang, and P.-Y. Chen.  Causal inference q-network: Toward resilient reinforcement learning.  _arXiv preprint arXiv:2102.09677_ , 2021.

##  Appendix A Semiparametric Efficiency Theory

In this appendix we provide a brief review of semiparametric efficiency
theory, as relevant for the theory in this paper. We will consider a random
variable $X\in\mathcal{X}$, a model (set of distributions) $\mathcal{M}$,
where each $P\in\mathcal{M}$ defines a distribution for $X$, and some scalar
parameter $v:\mathcal{M}\mapsto\mathbb{R}$. Also let $\mu$ denote some
dominating measure such that $P\ll\mu$ for every $P\in\mathcal{P}$, and denote
the corresponding density as $dP/d\mu$. Given iid observations
$X_{1},\ldots,X_{n}$ sampled from some $P_{0}\in\mathcal{M}$, semiparametric
efficiency theory concerns itself with the limits on the estimation of
$v(P_{0})$, given that the estimator is required to be consistent and “well
behaved” (defined concretely below) at all $P$ in a neighborhood of $P_{0}$ in
the model $\mathcal{M}$.

###  A.1 Definitions

######  Definition 2 (Influence function of estimators).

An estimator sequence $\hat{v}_{n}(X_{1:n})$ is asymptotically linear (AL)
with influence function (IF) $\psi_{P_{0}}(X)$ if

$\sqrt{n}(\hat{v}_{n}(X_{1:n})-v(P_{0}))=\frac{1}{\sqrt{n}}\sum_{i=1}^{n}\psi_{P_{0}}(X)+o_{p}(1)$

where $\mathbb{E}_{P_{0}}[\psi_{P_{0}}(X)]=0$.

######  Definition 3 (One-dimensional submodel and its score function).

A one-dimensional submodel of $\mathcal{M}$ passing through $P$ is a set of
distributions $\\{P_{\epsilon}:\epsilon\in U\\}\subseteq\mathcal{M}$, where:

  1. 1.

$P_{0}=P$

  2. 2.

The score function $s(X;\epsilon)=(d/d\epsilon)\log((dP_{\epsilon}/d\mu)(X))$
exists

  3. 3.

There exists $u>0$ _s.t._ $\int\sup_{|\epsilon|\leq
u}|s(X;\epsilon)|(dP_{\epsilon}/d\mu)(X)d\mu(X)<\infty$ and
$\mathbb{E}[\sup_{|\epsilon|\leq u}s(X;\epsilon)^{2}]<\infty$ .

Also, we define $s(X)=s(X;0)$, which we refer to as the score function of the
submodel at $P_{0}$, Note that by property (3) we have $s(X)\in L_{2,P}(X)$.
We also note that these conditions on the parametric sub-model are slightly
stronger than those in some related work; these are needed to prove our
semiparametric efficiency results with full rigor, and our definitions below
should be interpreted _w.r.t._ such well-behaved submodels.

######  Definition 4 (Tangent space).

The tangent space of $\mathcal{M}$ at $P_{0}$ is the linear closure of the
score function at $P_{0}$ of all one-dimensional submodels of $\mathcal{M}$
passing through $P_{0}$.

Note that the tangent space is always a cone, since we can always redefine any
one-dimensional parametric submodel replacing $\epsilon$ with any scalar
multiple of $\epsilon$.

######  Definition 5 (Pathwise differentiability).

A functional $v:\mathcal{M}\mapsto\mathbb{R}$ is pathwise differentiable at
$P_{0}$ wrt $\mathcal{M}$ if there exists a mean-zero function
$\psi_{P_{0}}(X)$, such that any one-dimensional submodel $\\{P_{\epsilon}\\}$
of $\mathcal{M}$ passing through $P_{0}$ with score function $s(X)$ satisfies

$\left.\frac{dv(P_{\epsilon})}{d\epsilon}\right|_{\epsilon=0}=\mathbb{E}[\psi_{P_{0}}(X)s(X)]\,.$

The function $\psi_{P_{0}}(X)$ is called a gradient of $v(P_{0})$ at $P_{0}$
wrt $\mathcal{M}$. The efficient IF (EIF, or canonical gradient) of $v(P_{0})$
wrt $\mathcal{M}$ is the unique gradient $\tilde{\psi}_{P_{0}}(X)$ of
$v(P_{0})$ at $P_{0}$ wrt $\mathcal{M}$ that belongs to the tangent space at
$P_{0}$ wrt $\mathcal{M}$.

Finally, we define regular estimators, which are those whose limiting
distribution is robust to local changes to the data generating process. This
is what we alluded to above by “well behaved” estimators. Note that
restricting attention to regular estimators excludes pathological behavior
such as that of the super-efficient Hodges estimator.

######  Definition 6 (Regular estimators).

An estimator sequence $\hat{v}_{n}$ is called regular at $P_{0}$ for
$v(P_{0})$ wrt $\mathcal{M}$ if there exists a limiting probability measure
$L$ such that, for any one-dimensional submodel $\\{P_{\epsilon}\\}$ of
$\mathcal{M}$ passing through $P_{0}$, we have

$\sqrt{n}(\hat{v}_{n}(X_{1:n})-v(P_{1/\sqrt{n}}))\to L$

in distribution as $n\to\infty$, where $X_{1:n}$ are distributed iid according
to $P_{1/\sqrt{n}}$.

Note that this property holds even if $\\{P_{\epsilon}\\}$ is chosen
adversarially in response to $\hat{v}_{n}$.

###  A.2 Characterizations

The following characterizes some important equivalences based on the above
definitions. The following are based on Van Der Vaart [1991, Theorm 3.1].

######  Theorem 5 (Influence functions are gradients).

Suppose that $\hat{v}_{n}(X_{1:n})$ is an AL estimator of $v(P_{0})$ with
influence function $\psi_{P_{0}}(X)$, and that $v(P_{0})$ is pathwise
differentiable at $P_{0}$ wrt $\mathcal{M}$. Then $\hat{v}_{n}(X_{1:n})$ is a
regular estimator of $v(P_{0})$ at $P_{0}$ wrt $\mathcal{M}$ if and only if
$\psi_{P_{0}}(X)$ is a gradient of $v(P_{0})$ at $P_{0}$ wrt $\mathcal{M}$.

######  Corollary 3 (Characterization of the EIF).

The EIF wrt $\mathcal{M}$ is the projection of any gradient wrt $\mathcal{M}$
onto the tangent space wrt $\mathcal{M}$.

###  A.3 Strategy to calculate the EIF

Given the above, the following is a natural strategy to calculate the EIF:

  1. 1.

Calculate a gradient $\psi_{P_{0}}(X)$ of the target parameter $v(P_{0})$ wrt
$\mathcal{M}$

  2. 2.

Calculate the gradient space wrt $\mathcal{M}$

  3. 3.

Either:

    1. (a)

Show that $\psi_{P_{0}}(X)$ already lies in the above tangent space, or

    2. (b)

Project $\psi_{P_{0}}(X)$ onto the tangent space

The first part of the above can often be done by explicitly computing the
derivative of $v(P_{\epsilon})$ wrt $\epsilon$, and re-arranging this into the
form $\mathbb{E}[\psi_{P_{0}}(X)s(X)]$ for some function $\psi_{P_{0}}(X)$.

###  A.4 Optimalities

Finally, we describe the optimal properties of the EIF
$\tilde{\psi}_{P_{0}}(X)$. We define the _efficiency bound_ as the variance of
the EIF, $\textup{var}_{P_{0}}[\tilde{\psi}_{P_{0}}(X)]$, which has the
following interpretations. First, the efficiency bound gives a lower-bound on
the risk of any estimator in a local asymptotic minimax sense [Van der Vaart,
2000, Theorem 25.20].

######  Theorem 6 (Local Asymptotic Minimax (LAM) theorem).

Let $v(P_{0})$ be pathwise differentiable at $P_{0}$ wrt $\mathcal{M}$, with
the EIF $\tilde{\psi}_{P_{0}}(X)$. Then, for any estimator sequence
$\hat{v}_{n}(X_{1:n})$, and any symmetric quasi-convex loss function
$l:\mathbb{R}\mapsto[0,\infty)$, we have

$\sup_{m\in\mathbb{N},\\{P_{\epsilon}^{(1)}\\},\ldots,\\{P_{\epsilon}^{(m)}\\}}\lim_{n\to\infty}\sup_{k\in[m]}\mathbb{E}_{P_{1/\sqrt{n}}^{(k)}}\left[l\left(\sqrt{n}\left\\{\hat{v}_{n}(X_{1:n})-v(P_{1/\sqrt{n}})\right\\}\right)\right]\geq\int
l(u)d\mathcal{N}(0,\textup{var}_{P_{0}}[\tilde{\psi}_{P_{0}}(X)])\,,$

where $\\{P_{\epsilon}^{(1)}\\},\ldots,\\{P_{\epsilon}^{(m)}\\}$ are one-
dimensional submodels of $\mathcal{M}$ passing through $P_{0}$.

In other words, if we allow for adversarial local perturbations to the data
generating process that are consistent with $\mathcal{M}$, then the worst-case
risk of _any_ estimator (not necessarily regular) is lower-bounded by that of
a regular and asymptotic estimator whose influence function is the EIF. This
interpretation follows because, given the above definition of regular
estimators and the central limit theorem, the limiting distribution of such a
regular and AL estimator is
$\mathcal{N}(0,\textup{var}_{P_{0}}[\tilde{\psi}_{P_{0}}(X)])$ under any such
local perturbations. Note that this theorem also implies the following,
possibly easier-to-interpret corollary.

######  Corollary 4.

Under the same assumptions as Theorem 6, we have

$\inf_{\delta>0}\liminf_{n\to\infty}\sup_{Q\in\mathcal{M},d_{\textup{TV}}(Q,P_{0})\leq\delta}\mathbb{E}_{Q}\left[l\left(\sqrt{n}\left\\{\hat{v}_{n}(X_{1:n})-v(Q)\right\\}\right)\right]\geq\int
l(u)d\mathcal{N}(0,\textup{var}_{P_{0}}[\tilde{\psi}_{P_{0}}(X)])\,,$

where $d_{\textup{TV}}(\cdot,\cdot)$ is the total variation distance, and
$\mathcal{N}(\mu,\sigma^{2})$ denotes a normal distribution with mean $\mu$
and variance $\sigma^{2}$.

Second, the efficiency bound gives a lower-bound on the risk of any regular
estimator, in a strict non-minimax sense [Van der Vaart, 2000, Theorem 25.21].

######  Theorem 7 (Convolution Theorem).

Let $l:\mathbb{R}\mapsto[0,\infty)$ be a symmetric quasi-convex loss function.
Let $v(P_{0})$ be pathwise differentiable at $P_{0}$ wrt $\mathcal{M}$ with
EIF $\tilde{\psi}_{P_{0}}(X)$, and let $\hat{v}_{n}(X_{1:n})$ be a regular
estimator sequence for $v(P_{0})$ at $P_{0}$ wrt $\mathcal{M}$, with limiting
distribution $L$. Then, we have

$\int l(u)dL(u)\geq\int
l(u)d\mathcal{N}(0,\textup{var}_{P_{0}}[\tilde{\psi}_{P_{0}}(X)])\,.$

Equality holds obviously when
$L=\mathcal{N}(0,\textup{var}_{P_{0}}[\tilde{\psi}_{P_{0}}(X)])$, which as
discussed above follows when $\hat{v}_{n}(X_{1:n})$ is regular and AL with
influence function given by the EIF.

We note that in our interpretations of both the LAM and Convolution Theorems,
we argued that if an estimator is regular and AL with influence function
$\tilde{\psi}_{P_{0}}(X)$ then it will achieve the corresponding bound. The
following final theorem shows that the latter property alone is both necessary
and sufficient [Van der Vaart, 2000, Theorem 25.23].

######  Theorem 8.

Let $v(P_{0})$ be pathwise differentiable at $P_{0}$ wrt $\mathcal{M}$, and
let $\tilde{\psi}_{P_{0}}(X)$ be the EIF. Then an estimator sequence is
efficient (regular wrt $\mathcal{M}$ and with limiting distribution
$\mathcal{N}(0,\textup{var}_{P_{0}}[\tilde{\psi}_{P_{0}}(X)])$) if and only if
it is AL with influence function $\tilde{\psi}_{P_{0}}(X)$.

##  Appendix B Discussion of Issues with Tangent Spaces in Past Work

Here we will discuss the problems with tagnent spaces proposed in past work on
proximal causal inference. Given that this past work has considered the
simpler setting where $H=1$, we will omit all suffixes and prefixes involving
$t$ in the discussion here. Let $T:L_{2}(Z,A)\mapsto L_{2}(W,A)$ be the
conditional operator defined according to

$Tf(Z,A)=\mathbb{E}[f(Z,A)\mid W,A]\quad\forall f\,,$

whose adjoint $T^{*}:L_{2}(W,A)\mapsto L_{2}(Z,A)$ satisfies

$T^{*}g(W,A)=\mathbb{E}[g(W,A)\mid Z,A]\quad\forall g\,.$

In Cui et al. [2020], the authors propose to use the tangent space, which, in
terms of our notation and definitions of $q$ and $h$, is defined by the
restrictions

$\displaystyle\mathbb{E}[q(Z,A))(s(A\mid W)+s(Z\mid W,A))\mid W,A]$
$\displaystyle\in\text{Range}(T)$
$\displaystyle\mathbb{E}[(\mathds{1}\\{E=A\\}R-h(W,A))s(W,R\mid Z,A)\mid Z,A]$
$\displaystyle\in\text{Range}(T^{*})\,.$

However, this choice of tangent space is never fully justified in terms of the
model under consideration. In Kallus et al. [2021], the authors do justify the
necessity of these restrictions by noting that if $q_{\epsilon}$ and
$h_{\epsilon}$ are differentiable with respect to $\epsilon$ within a given
submodel, then we must have

$\displaystyle\mathbb{E}\left[\left.\frac{\partial}{\partial\epsilon}\right|_{\epsilon=0}q_{\epsilon}(Z,A)\mid
W,A\right]$
$\displaystyle=\left.\frac{\partial}{\partial\epsilon}\right|_{\epsilon=0}P_{\epsilon}(A\mid
W)^{-1}-\mathbb{E}[s(Z\mid W,A)q(Z,A)\mid W,A]$ $\displaystyle=-P(A\mid
W)^{-1}s(A\mid W)-\mathbb{E}[s(Z\mid W,A)q(Z,A)\mid W,A]$
$\displaystyle=-\mathbb{E}[(s(A\mid W)+s(Z\mid W,A))q(Z,A)\mid W,A]$
$\displaystyle\mathbb{E}\left[\left.\frac{\partial}{\partial\epsilon}\right|_{\epsilon=0}h_{\epsilon}(W,A)\mid
Z,A\right]$ $\displaystyle=\mathbb{E}[s(W,R\mid
Z,A)(\mathds{1}\\{E=A\\}R-h(W,A))\mid Z,A]\,.$

Unfortunately, there are still some problems in this choice of tangent space.
Firstly, although they are clearly necessary conditions for differentiability
of the nuisances, it is not clear that they are _sufficient_ conditions; that
is, it is not clear that for a given score function satisfying these
conditions we can actually construct a parametric submodel for which the
nuisances are defined and differentiable. Note that this is contrast to many
other areas of work involving semiparametric efficiency theory, where the
tangent set restrictions simply correspond to some conditional independence
assumptions, in which case it is trivial to see that the tangent set
restrictions invoked are both necessary and sufficient, since the partitioning
of the score function immediately implies the independence structure of
corresponding parametric submodels.

Secondly, it is not clear that diferentiability of the nuisances is even
necessary – indeed we showed how to prove that $\psi_{\text{DR}}(\tau_{H})$ is
a gradient of the policy value without ever assuming or requiring that the
nuisance functions were differentiable – nor is it clear what impact if any
this requirement of nuisance differentiability would have on the actual model
of interest.

Thirdly, Kallus et al. [2021] consider a more general model in which $h$ and
$q$ are not necessarily uniquely determined, in which case the above
restrictions would actually have to hold for _all_ valid $h$ and $q$
functions, and it is not immediately clear that requiring this restriction for
a single chosen $h$ and $q$ is sufficient.

Finally, under a model in which the allowed distributions all actually
correspond to observational distributions for latent variable models with
hidden confounders satisfying the PCI, which the past work implies are the
only kinds of distributions under consideration, there are additional
necessary restrictions on the score functions. For example, let $L=(Z,A)$, and
$Q=(W,R)$, then from the PCI independence assumptions is clear that the
observed distribution must take the form

$P(L,Q)=\int P(S)P(L\mid S)P(Q\mid S)d\mu(S)\,,$

for some latent variable $S$. It is easy to show that this implies that for
any differentiable submodel on the full data $(L,Q,S)$ we have

$\displaystyle s(L,Q)$ $\displaystyle=\frac{\int\partial(s(S)+s(L\mid
S)+s(Q\mid S))P(S)P(L\mid S)P(Q\mid S)d\mu(S)}{\int P(S)P(L\mid S)P(Q\mid
S)d\mu(S)}$ $\displaystyle=\int\partial(s(S)+s(L\mid S)+s(Q\mid S))P(S\mid
L,Q)d\mu(S)$ $\displaystyle=\mathbb{E}[s(S)+s(L\mid S)+s(Q\mid S)\mid L,Q]\,.$

Therefore, there must exist functions $f_{1}$, $f_{2}$, and $f_{3}$ such that

$s(Z,A,W,R)=\mathbb{E}[f_{1}(S)+f_{2}(Z,A;S)+f_{3}(W,R;S)\mid Z,A,W,R]\,,$

which satisfy

$\mathbb{E}[f_{1}(S)]=\mathbb{E}[f_{2}(Z,A;S)\mid
S]=\mathbb{E}[f_{3}(W,R;S)\mid S]=0\,.$

It is not clear that the previously proposed tangent spaces ensure this
condition, for example.

Given these above issues, we took care to define assumptions to avoid such
issues, by ensuring that we consider a model that is locally saturated at
$\mathcal{P}_{b}$, which guarantees that the tangent set is all square
integrable functions. Achieving this involves ensuring that the nuisances are
uniquely determined locally near $\mathcal{P}_{b}$, and defining the parameter
of interest is not defined in terms of the actual policy value, and rather in
terms of the nuisances and the identification quantity; that is, we ensure
that the parameter of interest corresponds to the target policy value for
distributions that actually come from an underlying valid PCI model satisfying
our assumptions, and otherwise is still an unambiguous and well-defined
quantity as long as the nuisances are uniquely defined.

##  Appendix C Proofs of Main Theorems and Lemmas

###  C.1 Proof of Theorem 1

###### Proof.

We will prove this result for arbitrary fixed $s$. Define

$\displaystyle Y_{s}$ $\displaystyle=R_{s}$ $\displaystyle Y_{t}$
$\displaystyle=\phi^{(t+1)}(Z_{t+1},A_{t+1},W_{t+1},E_{t+1},X_{t},Y_{t+1})\qquad\forall
t\in[s-1]\,,$

where

$\phi^{(t)}(z,a,w,e,x,y)=\rho^{(t)}(z,a,x)\mathds{1}\\{a=e\\}y\,.$

Now, by these definitions we need to prove that

$\mathbb{E}_{\mathcal{P}_{e}}[R_{s}]=\mathbb{E}_{\mathcal{P}_{\text{ind}}}[Y_{0}]\,.$

where $Y_{0}=\phi^{(1)}(Z_{1},A_{1},W_{1},E_{1},X_{0},Y_{1})$.

We will proceed via a recursive argument. In order to set up our key
recursion, we first define some additional notation. First, let
$\mathcal{P}^{*}_{t}$ denote the intervention distribution introduced in
Section 4.2, and let $\mathcal{P}^{*}_{\text{ind},t}$ denote the measure on
$\Omega_{H}^{*}$ defined by a mixture between $\mathcal{P}^{*}_{t+1}$ and
$\mathcal{P}_{\text{ind}}$, where

  1. 1.

$\\{W_{1:t-1}\\}$, $\\{X_{1:t-1}\\}$ $\\{A_{1:t-1}\\}$, and $\\{R_{1:t-1}\\}$
are jointly sampled from $\mathcal{P}^{*}_{t}$

  2. 2.

$\\{Z_{1},\ldots,Z_{H}\\}$, $\\{W_{t},\ldots,W_{H}\\}$,
$\\{X_{t},\ldots,X_{H}\\}$ $\\{A_{t},\ldots,A_{H}\\}$, and
$\\{R_{t},\ldots,R_{H}\\}$ are jointly sampled from
$\mathcal{P}_{\text{ind}}$.

Given this setup, the inductive relation we would like to prove is

$\mathbb{E}_{\mathcal{P}^{*}_{\text{ind},t}}[\phi^{(t)}(Z_{t},A_{t},W_{t},E_{t},X_{t-1},Y_{t})]=\mathbb{E}_{\mathcal{P}^{*}_{\text{ind},t+1}}[Y_{t}]\qquad\forall
t\in[s]$ (11)

We note that if Eq. 11 holds, then via chaining this relation and the
recursive definitions of $Y_{t}$, we would instantly have our result, since
$\mathbb{E}_{\mathcal{P}^{*}_{\text{ind},1}}[\phi^{(1)}(Z_{1},A_{1},W_{1},E_{1},W_{0},Y_{1})]=\mathbb{E}_{\mathcal{P}^{*}_{\text{ind},1}}[Y_{0}]=\mathbb{E}_{\mathcal{P}_{\text{ind}}}[Y_{0}]$,
and
$\mathbb{E}_{\mathcal{P}^{*}_{\text{ind},s+1}}[R_{s}]=\mathbb{E}_{\mathcal{P}_{e}}[R_{s}]$.
Therefore, it only remains to prove that Eq. 11 holds.

Next, by the assumption on $\phi^{(t)}$ in the theorem statement, we have

$\displaystyle\mathbb{E}_{\mathcal{P}^{*}_{\text{ind},t}}\left[\rho^{(t)}(Z_{t},A_{t},X_{t-1})\left(\frac{d\mathcal{P}_{b}}{d\mathcal{P}^{*}_{\text{ind},t+1}}\right)(W_{t})\
\middle|\ W_{t},A_{t}=a\right]$
$\displaystyle=\left(\frac{d\mathcal{P}_{b}}{d\mathcal{P}^{*}_{\text{ind},t+1}}\right)(W_{t})\mathbb{E}_{\mathcal{P}^{*}_{\text{ind},t}}\left[\int_{x}f_{t-1}(x)\rho^{(t)}(Z_{t},A_{t},x)\
\middle|\ W_{t},A_{t}=a\right]$
$\displaystyle=\left(\frac{d\mathcal{P}_{b}}{d\mathcal{P}^{*}_{\text{ind},t+1}}\right)(W_{t})\left(\frac{d\mathcal{P}^{*}_{\text{ind},t+1}}{d\mathcal{P}_{b}}\right)(W_{t})P(A_{t}=a\mid
W_{t})^{-1}$ $\displaystyle=P(A_{t}=a\mid W_{t})^{-1}\,,$

where in this derivation $f_{t-1}$ denotes the density of $X_{t-1}$ under
$\mathcal{P}^{*}_{\text{ind},t}$, which we note is the same as the density of
$W_{t}$ under $\mathcal{P}^{*}_{\text{ind},t+1}$. Given this, applying the
independence assumptions of our POMDP framework we have

$\displaystyle\mathbb{E}_{\mathcal{P}^{*}_{\text{ind},t}}[P(A_{t}=a\mid
S_{t})^{-1}\mid W_{t},A_{t}=a]$
$\displaystyle=\mathbb{E}_{\mathcal{P}^{*}_{\text{ind},t}}[P(A_{t}=a\mid
S_{t},W_{t})^{-1}\mid W_{t},A_{t}=a]$
$\displaystyle=\int_{s}\frac{P(S_{t}=s\mid W_{t},A_{t}=a)}{P(A_{t}=a\mid
W_{t},S_{t}=s)}ds$ $\displaystyle=\int_{s}\frac{P(A_{t}=a\mid
W_{t},S_{t}=s)P(S_{t}=s\mid W_{t})}{P(A_{t}=a\mid W_{t},S_{t}=s)P(A_{t}=a\mid
W_{t})}ds$ $\displaystyle=P(A_{t}=a\mid W_{t})^{-1}$
$\displaystyle=\mathbb{E}_{\mathcal{P}^{*}_{\text{ind},t}}\left[\rho^{(t)}(Z_{t},A_{t},X_{t-1})\left(\frac{d\mathcal{P}_{b}}{d\mathcal{P}^{*}_{\text{ind},t+1}}\right)(W_{t})\
\middle|\ W_{t},A_{t}=a\right]$
$\displaystyle=\mathbb{E}_{\mathcal{P}^{*}_{\text{ind},t}}\left[\mathbb{E}_{\mathcal{P}^{*}_{\text{ind},t}}\left[\rho^{(t)}(Z_{t},A_{t},X_{t-1})\left(\frac{d\mathcal{P}_{b}}{d\mathcal{P}^{*}_{\text{ind},t+1}}\right)(W_{t})\
\middle|\ S_{t},W_{t},A_{t}=a\right]W_{t},A_{t}=a\right]$
$\displaystyle=\mathbb{E}_{\mathcal{P}^{*}_{\text{ind},t}}\left[\mathbb{E}_{\mathcal{P}^{*}_{\text{ind},t}}\left[\rho^{(t)}(Z_{t},A_{t},X_{t-1})\left(\frac{d\mathcal{P}_{b}}{d\mathcal{P}^{*}_{\text{ind},t+1}}\right)(W_{t})\
\middle|\ S_{t},A_{t}=a\right]W_{t},A_{t}=a\right]\,.$

Given this, it then follows from Assumption 1 that

$\mathbb{E}_{\mathcal{P}^{*}_{\text{ind},t}}\left[\rho^{(t)}(Z_{t},A_{t},X_{t-1})\left(\frac{d\mathcal{P}_{b}}{d\mathcal{P}^{*}_{\text{ind},t+1}}\right)(W_{t})\
\middle|\ S_{t},A_{t}=a\right]=P(A_{t}=a\mid S_{t})^{-1}\,,$

which holds almost surely for each $a\in\mathcal{A}$, and therefore also holds
replacing $a$ with $A_{t}$.

Finally, applying this previous equation, we have

$\displaystyle\mathbb{E}_{\mathcal{P}^{*}_{\text{ind},t}}[\phi^{(t)}(Z_{t},A_{t},W_{t},E_{t},X_{t-1},Y_{t}]$
$\displaystyle=\mathbb{E}_{\mathcal{P}^{*}_{\text{ind},t}}[\rho^{(t)}(Z_{t},A_{t},X_{t-1})\mathds{1}\\{A_{t}=E_{t}\\}Y_{t}]$
$\displaystyle=\mathbb{E}_{\mathcal{P}^{*}_{\text{ind},t}}\left[\mathbb{E}_{\mathcal{P}^{*}_{\text{ind},t}}\left[\rho^{(t)}(Z_{t},A_{t},X_{t-1})\left(\frac{d\mathcal{P}_{b}}{d\mathcal{P}^{*}_{\text{ind},t+1}}\right)(W_{t})\
\middle|\
S_{t},A_{t},W_{t},E_{t},Y_{t}\right]\left(\frac{d\mathcal{P}^{*}_{\text{ind},t+1}}{d\mathcal{P}_{b}}\right)(W_{t})\mathds{1}\\{A_{t}=E_{t}\\}Y_{t}\right]$
$\displaystyle=\mathbb{E}_{\mathcal{P}^{*}_{\text{ind},t}}\left[\mathbb{E}_{\mathcal{P}^{*}_{\text{ind},t}}\left[\rho^{(t)}(Z_{t},A_{t},X_{t-1})\left(\frac{d\mathcal{P}_{b}}{d\mathcal{P}^{*}_{\text{ind},t+1}}\right)(W_{t})\
\middle|\
S_{t},A_{t},\right]\left(\frac{d\mathcal{P}^{*}_{\text{ind},t+1}}{d\mathcal{P}_{b}}\right)(W_{t})\mathds{1}\\{A_{t}=E_{t}\\}Y_{t}\right]$
$\displaystyle=\mathbb{E}_{\mathcal{P}^{*}_{\text{ind},t}}\left[P(A_{t}\mid
S_{t})^{-1}\left(\frac{d\mathcal{P}^{*}_{\text{ind},t+1}}{d\mathcal{P}_{b}}\right)(W_{t})\mathds{1}\\{A_{t}=E_{t}\\}Y_{t}\right]$
$\displaystyle=\mathbb{E}_{\mathcal{P}^{*}_{\text{ind},t}}\left[\sum_{a}\
\frac{P(A_{t}\mid S_{t},W_{t},E_{t},Y_{t})}{P(A_{t}\mid
S_{t})}\left(\frac{d\mathcal{P}^{*}_{\text{ind},t+1}}{d\mathcal{P}_{b}}\right)(W_{t})\mathds{1}\\{E_{t}=a\\}Y_{t}(E_{t})\right]$
$\displaystyle=\mathbb{E}_{\mathcal{P}^{*}_{\text{ind},t}}\left[\left(\frac{d\mathcal{P}^{*}_{\text{ind},t+1}}{d\mathcal{P}_{b}}\right)(W_{t})Y_{t}(E_{t})\right]$
$\displaystyle=\mathbb{E}_{\mathcal{P}^{*}_{\text{ind},t+1}}[Y_{t}]\,,$

where the third and sixth equalities follow from the independence assumptions
of the POMDP given $S_{t}$. In this derivation we use the potential outcome
notation $Y_{t}(a)$ to denote the value $Y_{t}$ would have taken if we
intervened on the $t$’th action with value $a$ (and the subsequent values of
$X_{t}$ and $R_{t}$ are possibly changed accordingly; note that this
intevention does not change the values of $Z_{t}$ or $W_{t}$ since these
represent observations at time $t-1$ and $t$ respectively.) The final equality
follows because replacing $Y_{t}$ with $Y_{t}(E_{t})$ effectively updates the
mixture distribution $\mathcal{P}^{*}_{\text{ind},t}$ so that $A_{t}$,
$X_{t}$, and $R_{t}$ are included in the set variables sampled according to
$\mathcal{P}^{*}_{t+1}$, rather than in the set of those sampled according to
$\mathcal{P}_{\text{ind}}$. Furthermore, integrating over the Radon-Nikodym
derivative $(d\mathcal{P}^{*}_{\text{ind},t+1}/d\mathcal{P}_{b})(W_{t})$
effectively further updates the mixture distribution so that $W_{t}$ is also
included in the set sampled according to $\mathcal{P}^{*}_{t+1}$, since the
distribution of $W_{t}$ under $\mathcal{P}_{b}$ is the same as the
distribution of $W_{t}$ under $\mathcal{P}^{*}_{\text{ind},t}$. That is, these
two terms effectively replace integration under
$\mathcal{P}^{*}_{\text{ind},t}$ with integration under
$\mathcal{P}^{*}_{\text{ind},t+1}$. This establishes Eq. 11, and therefore as
discussed above the theorem follows by recursion.

∎

###  C.2 Proof of Lemma 1

###### Proof.

First we establish the required property of this definition of $\rho^{(t)}$.
Since observations are tabular, the required property is equivalent to

$\displaystyle\mathbb{E}\left[\sum_{x\in\mathcal{O}}f(x)\rho^{(t)}(Z_{t},A_{t},x)\
\middle|\ W_{t},A_{t}=a\right]$
$\displaystyle=\frac{f(W_{t})}{P(W_{t})}P(A_{t}\mid W_{t})^{-1}$
$\displaystyle=\frac{f(W_{t})}{P(A_{t}=a,O_{t}=W_{t})}\,,$

almost surely for every discrete probability distribution $f$ over the
observation space. Now, recalling that $Q^{(t,a)}_{x,y}=P(O_{t}=x\mid
A_{t}=a,O_{t-1}=y)$, plugging the definition of $\rho^{(t)}$ into the LHS
above, we have

$\displaystyle\mathbb{E}\left[\sum_{x\in\mathcal{O}}f(x)\rho^{(t)}(Z_{t},A_{t},x)\
\middle|\ W_{t},A_{t}=a\right]$
$\displaystyle=\mathbb{E}\left[\sum_{x\in\mathcal{O}}f(x)P(O_{t-1}=Z_{t},A_{t}=a)^{-1}(Q^{(t,a)})^{-1}_{Z_{t},x}\
\middle|\ W_{t},A_{t}=a\right]$
$\displaystyle=\sum_{x,z\in\mathcal{O}}f(x)P(O_{t-1}=z,A_{t}=a)^{-1}P(O_{t-1}=z\mid
O_{t}=W_{t},A_{t}=a)(Q^{(t,a)})^{-1}_{z,x}$
$\displaystyle=\sum_{x,z\in\mathcal{O}}f(x)P(O_{t-1}=z,A_{t}=a)^{-1}\frac{P(O_{t}=W_{t}\mid
O_{t-1}=z,A_{t}=a)P(O_{t-1}=z\mid A_{t}=a)}{P(O_{t}=W_{t}\mid
A_{t}=a)}(Q^{(t,a)})^{-1}_{z,x}$
$\displaystyle=\sum_{x,z\in\mathcal{O}}\frac{f(x)P(O_{t-1}=z\mid
A_{t}=a)}{P(O_{t-1}=z,A_{t}=a)P(O_{t}=W_{t}\mid
A_{t}=a)}Q^{(t,a)}_{W_{t},z}(Q^{(t,a)})^{-1}_{z,x}$
$\displaystyle=\sum_{x\in\mathcal{O}}\frac{f(x)}{P(A_{t}=a)P(O_{t}=W_{t}\mid
A_{t}=a)}\sum_{z\in\mathcal{O}}Q^{(t,a)}_{W_{t},z}(Q^{(t,a)})^{-1}_{z,x}$
$\displaystyle=\sum_{x\in\mathcal{O}}\frac{f(x)}{P(O_{t}=W_{t},A_{t}=a)}\mathds{1}\\{W_{t}=x\\}=\frac{f(W_{t})}{P(A_{t}=a,O_{t}=W_{t})}\,,$

which establishes the required property of $\rho^{(t)}$.

Now, for the second part of the theorem, we first note that in terms of our
notation and under our (w.l.o.g.) assumption that the target policy is
deterministic, Tennenholtz et al. [2020, Theorem 1] is equivalent to

$\displaystyle\mathbb{E}_{\mathcal{P}_{e}}[R_{s}]=\sum_{o_{1:s}\in\mathcal{O}^{s},a_{1:s}\in\mathcal{A}^{s}}$
$\displaystyle\left(\prod_{t=1}^{s}\mathds{1}\\{a_{t}=E_{t}(o_{1:t},a_{1:t-1})\\}\right)$
$\displaystyle\cdot\sum_{z\in\mathcal{O}}\mathbb{E}_{\mathcal{P}_{b}}[R_{s}\mid
O_{s}=o_{s},A_{s}=a_{s},O_{s-1}=z]$ $\displaystyle\qquad\cdot
P(O_{s}=o_{s}\mid A_{s}=a,O_{s-1}=z)\omega(o_{1:s},a_{1:s})_{z}\,,$

where $E_{t}(o_{1:t},a_{1:t-1})$ denotes the action taken by $\pi_{e}$ given
$O_{1:t}=o_{1:t}$, and $A_{1:t-1}=a_{1:t-1}$, and

$\displaystyle\omega(o_{1:s},a_{1:s})$
$\displaystyle=\prod_{t=1}^{s}\Xi_{s-t+1}(o_{1:s-t+1},a_{1:s-t+1})$
$\displaystyle\Xi_{t}(o_{1:t},a_{1:t})_{z,z^{\prime}}$
$\displaystyle=\sum_{x\in\mathcal{O}}(Q^{(t,a_{t})})^{-1}_{z,x}P(O_{t}=x,O_{t-1}=o_{t-1}\mid
A_{t-1}=a_{t-1},O_{t-2}=z^{\prime})\qquad\forall t\in\\{2,3,\ldots,s\\}$
$\displaystyle\Xi_{1}(o_{1:t},a_{1:t})_{z}$
$\displaystyle=\sum_{x\in\mathcal{O}}(Q^{(1,a_{1})})^{-1}_{z,x}P(O_{1}=x)\,.$

We note that the term we refer to as $\omega$ was called $\Omega$ in
Tennenholtz et al. [2020], and the terms we refer to as $\Xi$ were called $W$,
and we explicitly write out the matrix multiplication in the definitions of
the $\Xi$ terms. Next, plugging the definition of $\omega$ into the above
equation for $\mathbb{E}_{\mathcal{P}_{e}}[R_{s}]$, and explicitly writing out
the sums implied by the multiplication of the $\Xi_{t}$ terms, and re-
arranging terms, we obtain

$\displaystyle\mathbb{E}_{\mathcal{P}_{e}}[R_{s}]=\sum_{\begin{subarray}{c}o_{1:s}\in\mathcal{O}^{s},a_{1:s}\in\mathcal{A}^{s}\\\
z_{1:s}\in\mathcal{O}^{s},x_{0:s-1}\in\mathcal{O}^{s}\end{subarray}}$
$\displaystyle\left(\prod_{t=1}^{s}\mathds{1}\\{a_{t}=E_{t}(o_{1:t},a_{1:t-1})\\}\right)$
$\displaystyle\cdot\mathbb{E}_{\mathcal{P}_{b}}[R_{s}\mid
O_{s}=o_{s},A_{s}=a_{s},O_{s-1}=z_{s}]$
$\displaystyle\cdot\left(\prod_{t=1}^{s}(Q^{(t,a_{t})})^{-1}_{z_{t},x_{t-1}}P(A_{t}=a_{t},O_{t-1}=z_{t})^{-1}\right)$
$\displaystyle\cdot\left(\prod_{t=1}^{s-1}P(O_{t}=o_{t},A_{t}=a_{t},O_{t-1}=z_{t},O_{t+1}=x_{t})\right)$
$\displaystyle\cdot P(O_{s}=o_{s},A_{s}=a_{s},O_{s-1}=z_{s})P(O_{0}=x_{0})\,.$

Now, we note that
$(Q^{(t,a_{t})})^{-1}_{z_{t},x_{t-1}}P(A_{t}=a_{t},O_{t-1}=z_{t})^{-1}=\rho^{(t)}(z_{t},a_{t},x_{t-1})$,
and that summing over the product of terms
$\prod_{t=1}^{s-1}P(O_{t}=o_{t},A_{t}=a_{t},O_{t-1}=Z_{t},O_{t+1}=x_{t})$ and
$P(O_{s}=o_{s},A_{s}=a_{s},O_{s-1}=Z_{s})$ and $P(O_{0}=x_{0})$ is equivalent
to integrating over $\mathcal{P}_{\text{ind}}$, where $z_{t}$, $a_{t}$,
$x_{t}$, and $o_{t}$ correspond to $Z_{t}$, $A_{t}$, $X_{t}$, and $W_{t}$
respectively. Re-writing the previous equation as an expectation and
simplifying based on this gives us

$\displaystyle\mathbb{E}_{\mathcal{P}_{e}}[R_{s}]$
$\displaystyle=\mathbb{E}_{\mathcal{P}_{\text{ind}}}\left[\mathbb{E}_{\mathcal{P}_{b}}[R_{s}\mid
W_{s},A_{s},Z_{s}]\prod_{t=1}^{s}\mathds{1}\\{A_{t}=E_{t}\\}\rho^{(t)}(Z_{t},A_{t},X_{t-1})\right]$
$\displaystyle=\mathbb{E}_{\mathcal{P}_{\text{ind}}}\left[\mathbb{E}_{\mathcal{P}_{\text{ind}}}\left[R_{s}\prod_{t=1}^{s}\mathds{1}\\{A_{t}=E_{t}\\}\rho^{(t)}(Z_{t},A_{t},X_{t-1})\
\middle|\ W_{s},A_{s},Z_{s}\right]\right]$
$\displaystyle=\mathbb{E}_{\mathcal{P}_{\text{ind}}}\left[R_{s}\prod_{t=1}^{s}\mathds{1}\\{A_{t}=E_{t}\\}\rho^{(t)}(Z_{t},A_{t},X_{t-1})\right]\,,$

where the second equation follows since the distribution of $R_{s}$ given
$W_{s}$, $A_{s}$, and $Z_{s}$ is the same under $\mathcal{P}_{b}$ and
$\mathcal{P}_{\text{ind}}$, and because $R_{s}$ is independent of
$\prod_{t=1}^{s}\mathds{1}\\{A_{t}=E_{t}\\}\rho^{(t)}(Z_{t},A_{t},X_{t-1})$
given $(W_{s},A_{s},Z_{s})$ under $\mathcal{P}_{\text{ind}}$. We note that the
final equation is our identification result from Theorem 1, and so we
conclude. ∎

###  C.3 Proof of Theorem 2

Before we present the main proof, we establish some additional notation and
some helper lemmas. Using similar notation to Kallus et al. [2021], for any
$t\in[H]$ and $\phi\in L_{2,\mathcal{P}^{*}_{t}}(R_{t},D_{t+1:H})$ we define
the sets

$\displaystyle\mathbb{Q}^{(t)}$ $\displaystyle=\\{q\in
L_{2,\mathcal{P}^{*}_{t}}(Z_{t},A_{t}):\mathbb{E}^{*}_{t}[q(Z_{t},A_{t})-P^{*}_{t}(A_{t}\mid
S_{t})^{-1}\mid S_{t},A_{t}=a]=0\quad\text{a.s.}\quad\forall
a\in\mathcal{A}\\}$ $\displaystyle\mathbb{H}^{(t,\phi)}$
$\displaystyle=\\{h\in
L_{2,\mathcal{P}^{*}_{t}}(W_{t},A_{t}):\mathbb{E}^{*}_{t}[h(W_{t},A_{t})-\mathds{1}\\{A_{t}=E_{t}\\}Y_{t}\mid
S_{t},a_{t}=a]=0\quad\text{a.s.}\quad\forall a\in\mathcal{A}\\}$
$\displaystyle\mathbb{Q}^{(t)}_{\text{obs}}$ $\displaystyle=\\{q\in
L_{2,\mathcal{P}^{*}_{t}}(Z_{t},A_{t}):\mathbb{E}^{*}_{t}[q(Z_{t},A_{t})-P^{*}_{t}(A_{t}\mid
W_{t})^{-1}\mid W_{t},A_{t}=a]=0\quad\text{a.s.}\quad\forall
a\in\mathcal{A}\\}$ $\displaystyle\mathbb{H}^{(t,\phi)}_{\text{obs}}$
$\displaystyle=\\{h\in
L_{2,\mathcal{P}^{*}_{t}}(W_{t},A_{t}):\mathbb{E}^{*}_{t}[h(W_{t},A_{t})-\mathds{1}\\{A_{t}=E_{t}\\}Y_{t}\mid
W_{t},A_{t}=a]=0\quad\text{a.s.}\quad\forall a\in\mathcal{A}\\}\,,$

where $Y_{t}=\phi(R_{t},E_{t+1:H})$.

First, we will prove an important claim from Section 4.2, which is that
Assumption 3 implies that Eqs. 2 and 3 both have solutions. This claim is
formalized by the following lemma.

######  Lemma 3.

Under Assumption 2 and for each $t\in[H]$ and $\phi\in
L_{2,\mathcal{P}^{*}_{t}}(R_{t},D_{t+1:H})$ we have
$\mathbb{Q}^{(t)}\subseteq\mathbb{Q}^{(t)}_{\text{obs}}$ and
$\mathbb{H}^{(t,\phi)}\subseteq\mathbb{H}^{(t,\phi)}_{\text{obs}}$.

###### Proof of Lemma 3.

First, suppose that $q^{(t)}\in\mathbb{Q}^{(t)}$. Then we have

$\displaystyle\mathbb{E}^{*}_{t}[q^{(t)}(Z_{t},A_{t})\mid W_{t},A_{t}=a]$
$\displaystyle=\mathbb{E}^{*}_{t}[\mathbb{E}^{*}_{t}[q^{(t)}(Z_{t},A_{t})\mid
S_{t},W_{t},A_{t}=a]\mid W_{t},A_{t}=a]$
$\displaystyle=\mathbb{E}^{*}_{t}[\mathbb{E}^{*}_{t}[q^{(t)}(Z_{t},A_{t})\mid
S_{t},A_{t}=a]\mid W_{t},A_{t}=a]$
$\displaystyle=\mathbb{E}^{*}_{t}[P^{*}_{t}(A_{t}=a\mid S_{t})^{-1}\mid
W_{t},A_{t}=a]$ $\displaystyle=\int\frac{P^{*}_{t}(S_{t}=s\mid
W_{t},A_{t}=a)}{P^{*}_{t}(A_{t}=a\mid S_{t}=s)}d\mu(s)$
$\displaystyle=\int\frac{P^{*}_{t}(A_{t}=a\mid
W_{t},S_{t}=s)P^{*}_{t}(S_{t}=s\mid W_{t})}{P^{*}_{t}(A_{t}=a\mid
S_{t}=s)P^{*}_{t}(A_{t}=a\mid W_{t})}d\mu(s)$
$\displaystyle=P^{*}_{t}(A_{t}=a\mid W_{t})^{-1}\int P^{*}_{t}(S_{t}=s\mid
W_{t})d\mu(s)$ $\displaystyle=P^{*}_{t}(A_{t}=a\mid W_{t})^{-1}\,,$

where in the second and sixth equalities we apply the independence assumptions
from Assumption 2, in the third equality we apply the fact that
$q^{(t)}\in\mathbb{Q}^{(t)}$, and the fifth equality follows from Bayes’ rule.
Therefore, $q^{(t)}\in\mathbb{Q}^{(t)}_{\text{obs}}$.

Second, suppose that $h^{(t)}\in\mathbb{H}^{(t,\phi)}$. Then we have

$\displaystyle\mathbb{E}^{*}_{t}[h^{(t)}(W_{t},A_{t})\mid Z_{t},A_{t}=a]$
$\displaystyle=\mathbb{E}^{*}_{t}[\mathbb{E}^{*}_{t}[h^{(t)}(W_{t},A_{t})\mid
S_{t},Z_{t},A_{t}=a]\mid Z_{t},A_{t}=a]$
$\displaystyle=\mathbb{E}^{*}_{t}[\mathbb{E}^{*}_{t}[h^{(t)}(W_{t},A_{t})\mid
S_{t},A_{t}=a]\mid Z_{t},A_{t}=a]$
$\displaystyle=\mathbb{E}^{*}_{t}[\mathbb{E}^{*}_{t}[\phi(R_{t},D_{t+1:H})\mid
S_{t},A_{t}=a]\mid Z_{t},A_{t}=a]$
$\displaystyle=\mathbb{E}^{*}_{t}[\mathbb{E}^{*}_{t}[\phi(R_{t},D_{t+1:H})\mid
S_{t},Z_{t},A_{t}=a]\mid Z_{t},A_{t}=a]$
$\displaystyle=\mathbb{E}^{*}_{t}[\phi(R_{t},D_{t+1:H})\mid Z_{t},A_{t}=a]\,,$

where in the second and fourth equalities we apply the independence
assumptions from Assumption 2, and in the third equality we apply the fact
that $h^{(t)}\in\mathbb{H}^{(t)}$. Therefore,
$h^{(t)}\in\mathbb{H}^{(t,\phi)}_{\text{obs}}$. ∎

Next, we establish the following pair of lemmas, which allow us to establish
that $\phi^{(t,s)}_{\text{IS}}$ and $\phi^{(t,s)}_{\text{Reg}}$ satisfy an
important recursive property in the case that $q^{(t)}\in\mathbb{Q}^{(t)}$ or
$h^{(t)}\in\mathbb{H}^{(H)}$ respectively.

######  Lemma 4.

Suppose that $q^{(t)}\in\mathbb{Q}^{(t)}$, let $Y_{t}=\phi(R_{t},D_{t+1:H})$,
and let Assumption 2 be given. Then, we have

$\mathbb{E}^{*}_{t}[q^{(t)}(Z_{t},A_{t})\mathds{1}\\{A_{t}=E_{t}\\}Y_{t}]=\mathbb{E}^{*}_{t+1}[Y_{t}]\,.$

######  Lemma 5.

Suppose that $h^{(t)}\in\mathbb{H}^{(t,\phi)}$, let
$Y_{t}=\phi(R_{t},D_{t+1:H})$, and let Assumption 2 be given. Then, we have

$\mathbb{E}^{*}_{t}\left[\sum_{a\in\mathcal{A}}h^{(t)}(W_{t},a)\right]=\mathbb{E}^{*}_{t+1}[Y_{t}]\,.$

###### Proof of Lemma 4.

Given that $q^{(t)}\in\mathbb{Q}^{(t)}$, we have

$\displaystyle\mathbb{E}^{*}_{t}[q^{(t)}(Z_{t},A_{t})\mathds{1}\\{A_{t}=E_{t}\\}Y_{t}]$
$\displaystyle=\mathbb{E}^{*}_{t}[\mathbb{E}^{*}_{t}[q^{(t)}(Z_{t},A_{t})\mid
S_{t},A_{t},E_{t},Y_{t}(1),\ldots,Y_{t}(m)]\mathds{1}\\{A_{t}=E_{t}\\}Y_{t}]$
$\displaystyle=\mathbb{E}^{*}_{t}[\mathbb{E}^{*}_{t}[q^{(t)}(Z_{t},A_{t})\mid
S_{t},A_{t}]\mathds{1}\\{A_{t}=E_{t}\\}Y_{t}]$
$\displaystyle=\mathbb{E}^{*}_{t}[P^{*}_{t}(A_{t}\mid
S_{t})^{-1}\mathds{1}\\{A_{t}=E_{t}\\}Y_{t}]$
$\displaystyle=\mathbb{E}^{*}_{t}[P^{*}_{t}(A_{t}\mid
S_{t})^{-1}\mathds{1}\\{A_{t}=E_{t}\\}Y_{t}(E_{t})]$
$\displaystyle=\mathbb{E}^{*}_{t}\left[\sum_{a\in\mathcal{A}}\frac{P^{*}_{t}(A_{t}=a\mid
S_{t},E_{t},Y_{t}(1),\ldots,Y_{t}(m))}{P^{*}_{t}(A_{t}=a\mid
S_{t})}\mathds{1}\\{E_{t}=a\\}Y_{t}(E_{t})\right]$
$\displaystyle=\mathbb{E}^{*}_{t}\left[\sum_{a\in\mathcal{A}}\mathds{1}\\{E_{t}=a\\}Y_{t}(E_{t})\right]$
$\displaystyle=\mathbb{E}^{*}_{t}[Y_{t}(E_{t})]$
$\displaystyle=\mathbb{E}^{*}_{t+1}[Y_{t}]\,,$

where in the second and sixth equalities we apply the independence assumptions
from Assumption 2, in the third equality we apply the fact that
$q^{(t)}\in\mathbb{Q}^{(t)}$, in the fourth equality we apply the fact that
$Y_{t}=Y_{t}(A_{t})$, and in the final equality we apply the fact that by
definition intervening on the $t$’th action with $E_{t}$ under
$\mathcal{P}^{*}_{t}$ is by definition equivalent to $\mathcal{P}^{*}_{t+1}$.
∎

###### Proof of Lemma 5.

Given that $h^{(t,\phi)}\in\mathbb{Q}^{(t)}$, we have

$\displaystyle\mathbb{E}^{*}_{t}\left[\sum_{a\in\mathcal{A}}h^{(t)}(W_{t},a)\right]$
$\displaystyle=\mathbb{E}^{*}_{t}\left[\mathbb{E}^{*}_{t}\left[\sum_{a\in\mathcal{A}}h^{(t)}(W_{t},a)\
\middle|\ S_{t}\right]\right]$
$\displaystyle=\mathbb{E}^{*}_{t}\left[\mathbb{E}^{*}_{t}\left[\sum_{a\in\mathcal{A}}h^{(t)}(W_{t},A_{t})\
\middle|\ S_{t},A_{t}=a\right]\right]$
$\displaystyle=\mathbb{E}^{*}_{t}\left[\mathbb{E}^{*}_{t}\left[\sum_{a\in\mathcal{A}}\mathds{1}\\{E_{t}=A_{t}\\}Y_{t}\
\middle|\ S_{t},A_{t}=a\right]\right]$
$\displaystyle=\mathbb{E}^{*}_{t}\left[\mathbb{E}^{*}_{t}\left[\sum_{a\in\mathcal{A}}\mathds{1}\\{E_{t}=a\\}Y_{t}(E_{t})\
\middle|\ S_{t},A_{t}=a\right]\right]$
$\displaystyle=\mathbb{E}^{*}_{t}\left[\mathbb{E}^{*}_{t}\left[\sum_{a\in\mathcal{A}}\mathds{1}\\{E_{t}=a\\}Y_{t}(E_{t})\
\middle|\ S_{t}\right]\right]$
$\displaystyle=\mathbb{E}^{*}_{t}\left[\sum_{a\in\mathcal{A}}\mathds{1}\\{E_{t}=a\\}Y_{t}(E_{t})\right]$
$\displaystyle=\mathbb{E}^{*}_{t}[Y_{t}(E_{t})]$
$\displaystyle=\mathbb{E}^{*}_{t+1}[Y_{t}]$

where in the second and sixth equalities we apply the independence assumptions
from Assumption 2, in the third equality we apply the fact that
$h^{(t)}\in\mathbb{H}^{(t,\phi)}$, in the fourth equality we apply the fact
that $Y_{t}=Y_{t}(A_{t})$, and in the final equality we apply the fact that by
definition intervening on the $t$’th action with $E_{t}$ under
$\mathcal{P}^{*}_{t}$ is by definition equivalent to $\mathcal{P}^{*}_{t+1}$.
∎

Now, by the previous two lemmas, we would be able to establish identification
via backward induction, if it were the case that the functions $q^{(t)}$ and
$h^{(t,s)}$ used for identification were actually members of
$\mathbb{Q}^{(t)}$ and $\mathbb{H}^{(t,\phi)}$ (for $\phi$ such that
$\phi(R_{t},D_{t+1:H})=Y_{t}^{(s)}$). However, instead we assumed that
$q^{(t)}\in\mathbb{Q}^{(t)}_{\text{obs}}$ and
$h^{(t)}\in\mathbb{H}^{(t,\phi)}_{\text{obs}}$, so some additional care must
be taken. The next lemma and its corollaries allow us to remedy this issue.

######  Lemma 6.

Let $q^{(t)}\in\mathbb{Q}^{(t)}_{\text{obs}}$ and
$h^{(t)}\in\mathbb{H}^{(t,\phi)}_{\text{obs}}$ be chosen arbitrarily, for some
given $Y_{t}=\phi(R_{t},D_{t+1:H})$. Then we have

$\mathbb{E}^{*}_{t}[q^{(t)}(Z_{t},A_{t})\mathds{1}\\{A_{t}=E_{t}\\}Y_{t}]=\mathbb{E}^{*}_{t}\left[\sum_{a\in\mathcal{A}}h^{(t)}(W_{t},a)\right]\,.$

###### Proof of Lemma 6.

We have

$\displaystyle\mathbb{E}^{*}_{t}[q^{(t)}(Z_{t},A_{t})\mathds{1}\\{A_{t}=E_{t}\\}Y_{t}]$
$\displaystyle=\mathbb{E}^{*}_{t}[q^{(t)}(Z_{t},A_{t})\mathbb{E}^{*}_{t}[\mathds{1}\\{A_{t}=E_{t}\\}Y_{t}\mid
Z_{t},A_{t}]]$
$\displaystyle=\mathbb{E}^{*}_{t}[q^{(t)}(Z_{t},A_{t})\mathbb{E}^{*}_{t}[h^{(t)}(W_{t},A_{t})\mid
Z_{t},A_{t}]]$
$\displaystyle=\mathbb{E}^{*}_{t}[q^{(t)}(Z_{t},A_{t})h^{(t)}(W_{t},A_{t})]$
$\displaystyle=\mathbb{E}^{*}_{t}[\mathbb{E}^{*}_{t}[q^{(t)}(Z_{t},A_{t})\mid
W_{t},A_{t}]h^{(t)}(W_{t},A_{t})]$
$\displaystyle=\mathbb{E}^{*}_{t}[P^{*}_{t}(A_{t}\mid
W_{t})^{-1}h^{(t)}(W_{t},A_{t})]$
$\displaystyle=\mathbb{E}^{*}_{t}\left[\sum_{a\in\mathcal{A}}\frac{P^{*}_{t}(A_{t}=a\mid
W_{t})}{P^{*}_{t}(A_{t}=a\mid W_{t})}h^{(t)}(W_{t},a)\right]$
$\displaystyle=\mathbb{E}^{*}_{t}\left[\sum_{a\in\mathcal{A}}h^{(t)}(W_{t},a)\right]\,.$

∎

######  Corollary 5.

Suppose that $q^{(t)}\in\mathbb{Q}^{(t)}_{\text{obs}}$, let
$Y_{t}=\phi(R_{t},D_{t+1:H})$, and let Assumptions 2 and 3 be given. Then, we
have

$\mathbb{E}^{*}_{t}[q^{(t)}(Z_{t},A_{t})\mathds{1}\\{A_{t}=E_{t}\\}Y_{t}]=\mathbb{E}^{*}_{t+1}[Y_{t}]\,.$

######  Corollary 6.

Suppose that $h^{(t)}\in\mathbb{H}^{(t,\phi)}_{\text{obs}}$, let
$Y_{t}=\phi(R_{t},D_{t+1:H})$, and let Assumptions 2 and 3 be given. Then, we
have

$\mathbb{E}^{*}_{t}\left[\sum_{a\in\mathcal{A}}h^{(t)}(W_{t},a)\right]=\mathbb{E}^{*}_{t+1}[Y_{t}]\,.$

Corollary 5 follows because from Assumption 3 there must exist some
$h^{(t)}\in\mathbb{H}^{(t,\phi)}$, and by Lemma 3 we know that
$h^{(t)}\in\mathbb{H}^{(t,\phi)}_{\text{obs}}$, so therefore applying Lemma 6
and then Lemma 5 we have

$\mathbb{E}^{*}_{t}[q^{(t)}(Z_{t},A_{t})\mathds{1}\\{A_{t}=E_{t}\\}Y_{t}]=\mathbb{E}^{*}_{t}\left[\sum_{a\in\mathcal{A}}h^{(t)}(W_{t},a)\right]=\mathbb{E}^{*}_{t+1}[Y_{t}]\,.$

Corollary 6 follows by an almost identical logic, since by Assumption 3 there
must exist some $q^{(t)}\in\mathbb{Q}^{(t)}$, and by Lemma 3 we also know that
$q^{(t)}\in\mathbb{Q}^{(t)}_{\text{obs}}$. Therefore, applying Lemma 6 and
then Lemma 4 we have

$\mathbb{E}^{*}_{t}\left[\sum_{a\in\mathcal{A}}h^{(t)}(W_{t},a)\right]=\mathbb{E}^{*}_{t}[q^{(t)}(Z_{t},A_{t})\mathds{1}\\{A_{t}=E_{t}\\}Y_{t}]=\mathbb{E}^{*}_{t+1}[Y_{t}]\,.$

These corollaries are sufficient to construct our inductive proof for our main
identification result, in the case of $\phi^{(t,s)}_{\text{IS}}$ and
$\phi^{(t,s)}_{\text{Reg}}$. However, for the case of
$\phi^{(t,s)}_{\text{DR}}$ we need to establish one final lemma before
presenting our main proof.

######  Lemma 7.

Suppose that either $q^{(t)}\in\mathbb{Q}^{(t)}_{\text{obs}}$ and $h^{(t)}\in
L_{2,\mathcal{P}^{*}_{t}}(W_{t},A_{t})$ _or_
$h^{(t)}\in\mathbb{H}^{(t,\phi)}_{\text{obs}}$ and $q^{(t)}\in
L_{2,\mathcal{P}^{*}_{t}}(Z_{t},A_{t})$. In addition, let
$Y_{t}=\phi(R_{t},D_{t+1:H})$, and let Assumptions 2 and 3 be given. Then, we
have

$\mathbb{E}^{*}_{t}\left[q^{(t)}(Z_{t},A_{t})(\mathds{1}\\{A_{t}=E_{t}\\}Y_{t}-h^{(t)}(W_{t},A_{t}))+\sum_{a\in\mathcal{A}}h^{(t)}(W_{t},a)\right]=\mathbb{E}^{*}_{t+1}[Y_{t}]\,.$

###### Proof of Lemma 7.

First consider the case where $q^{(t)}\in\mathbb{Q}^{(t)}_{\text{obs}}$ and
$h^{(t)}\in L_{2,\mathcal{P}^{*}_{t}}(W_{t},A_{t})$. In this case, we have

$\displaystyle\mathbb{E}^{*}_{t}\left[q^{(t)}(Z_{t},A_{t})(\mathds{1}\\{A_{t}=E_{t}\\}Y_{t}-h^{(t)}(W_{t},A_{t}))+\sum_{a\in\mathcal{A}}h^{(t)}(W_{t},a)\right]$
$\displaystyle=\mathbb{E}^{*}_{t}t[q^{(t)}(Z_{t},A_{t})\mathds{1}\\{A_{t}=E_{t}\\}Y_{t}]+\mathbb{E}^{*}_{t}\left[\sum_{a\in\mathcal{A}}h^{(t)}(W_{t},a)\right]-\mathbb{E}^{*}_{t}[q^{(t)}(Z_{t},A_{t})h^{(t)}(W_{t},A_{t})]$
$\displaystyle=\mathbb{E}^{*}_{t+1}[Y_{t}]+\mathbb{E}^{*}_{t}\left[\sum_{a\in\mathcal{A}}h^{(t)}(W_{t},a)\right]-\mathbb{E}^{*}_{t}[q^{(t)}(Z_{t},A_{t})h^{(t)}(W_{t},A_{t})]\,,$

where in the second equality we apply Corollary 5. Now, given
$q^{(t)}\in\mathbb{Q}^{(t)}_{\text{obs}}$ we can further establish

$\displaystyle\mathbb{E}^{*}_{t}[q^{(t)}(Z_{t},A_{t})h^{(t)}(W_{t},A_{t})]$
$\displaystyle=\mathbb{E}^{*}_{t}\left[\mathbb{E}^{*}_{t}[q^{(t)}(Z_{t},A_{t})\mid
W_{t},A_{t}]h^{(t)}(W_{t},A_{t})\right]$
$\displaystyle=\mathbb{E}^{*}_{t}\left[P^{*}_{t}(A_{t}\mid
W_{t})^{-1}h^{(t)}(W_{t},A_{t})\right]$
$\displaystyle=\mathbb{E}^{*}_{t}\left[\sum_{a\in\mathcal{A}}h^{(t)}(W_{t},A_{t})\right]\,.$

Thus, plugging this into the previous equation we have

$\mathbb{E}^{*}_{t}\left[q^{(t)}(Z_{t},A_{t})(\mathds{1}\\{A_{t}=E_{t}\\}Y_{t}-h^{(t)}(W_{t},A_{t}))+\sum_{a\in\mathcal{A}}h^{(t)}(W_{t},a)\right]=\mathbb{E}^{*}_{t+1}[Y_{t}]\,.$

Next, instead consider the case where
$h^{(t)}\in\mathbb{H}^{(t,\phi)}_{\text{obs}}$ and $q^{(t)}\in
L_{2,\mathcal{P}^{*}_{t}}(Z_{t},A_{t})$. In this case, we have

$\displaystyle\mathbb{E}^{*}_{t}\left[q^{(t)}(Z_{t},A_{t})(\mathds{1}\\{A_{t}=E_{t}\\}Y_{t}-h^{(t)}(W_{t},A_{t}))+\sum_{a\in\mathcal{A}}h^{(t)}(W_{t},a)\right]$
$\displaystyle=\mathbb{E}^{*}_{t}\left[q^{(t)}(Z_{t},A_{t})\mathbb{E}^{*}_{t}[\mathds{1}\\{A_{t}=E_{t}\\}Y_{t}-h^{(t)}(W_{t},A_{t})\mid
Z_{t},A_{t}]\right]+\mathbb{E}^{*}_{t}\left[\sum_{a\in\mathcal{A}}h^{(t)}(W_{t},a)\right]$
$\displaystyle=0+\mathbb{E}^{*}_{t+1}[Y_{t}]\,,$

where the second equality follows from Corollary 6 and the fact that
$h^{(t)}\in\mathbb{H}^{(t,\phi)}_{\text{obs}}$. Therefore, under either
conditions we have our desired result.

∎

Now that we have established these preliminary lemmas, we are ready to present
the main proof.

###### Proof of Theorem 2.

First, we have assumed Assumptions 2 and 3, as well as the fact that
$q^{(t)}\in\mathbb{Q}^{(t)}_{\text{obs}}$ and
$h^{(t)}\in\mathbb{H}^{(t,\phi)}_{\text{obs}}$, so it follows from Corollaries
5, 6 and 7 that for any of the choices of $\phi^{(t+1,s)}_{\text{IS}}$,
$\phi^{(t+1,s)}_{\text{Reg}}$, or $\phi^{(t+1,s)}_{\text{DR}}$ for defining
each $Y_{t}^{(s)}$ term (for $t<s$) we have

$\mathbb{E}^{*}_{t}[\phi^{(t,s)}(Z_{t},W_{t},A_{t},E_{t},Y_{t}^{(s)})]=\mathbb{E}^{*}_{t+1}[Y_{t}^{(s)}]\,,$

which holds for every $t<s$. Furthermore, we have defined
$Y_{t}^{(s)}=\phi^{(t+1,s)}(Z_{t+1},W_{t+1},A_{t+1},E_{t+1},Y_{t+1}^{(s)})$
for each $t<s$, and $Y_{s}^{(s)}=R_{s}$, so the previous equation is
equivalent to

$\mathbb{E}^{*}_{t}[Y_{t-1}^{(s)}]=\mathbb{E}^{*}_{t+1}[Y_{t}^{(s)}]\,,$

which again holds for every $t<s$. Therefore, by backward induction we have

$\mathbb{E}^{*}_{1}[Y_{0}^{(s)}]=\mathbb{E}^{*}_{s+1}[R_{s}]\,.$

However, by construction $\mathcal{P}^{*}_{1}=\mathcal{P}_{b}$, and the
distribution of $R_{s}$ under $\mathcal{P}^{*}_{s+1}$ is the same as under
$\mathcal{P}_{e}$, so therefore we have
$\mathbb{E}_{\mathcal{P}_{b}}[Y_{0}^{(s)}]=\mathbb{E}_{\mathcal{P}_{e}}[R_{s}]$,
as required.

∎

###  C.4 Proof of Theorem 3

We will prove this theorem by appealing to Chernozhukov et al. [2016, Theorem
3.1]. Therefore, this proof will consist of establishing the conditions of
this theorem. We will first present a lemma establishing the Newman
orthogonality property of this influence function, which not only is a
condition of Chernozhukov et al. [2016, Theorem 3.1] but an important property
in its own right, before presenting the rest of the proof.

In what follows below, for any generic quantity $\Psi$ that depends on our
nuisance functions, we will use the notation $\hat{\Psi}$ to refer to the
value of $\Psi$ using the estimated nuisance functions $\hat{q}^{(t)}$ and
$\hat{h}^{(t)}$ in place of $q^{(t)}$ and $h^{(t)}$ respectively for each
$t\in[H]$, and define $\Delta\Psi=\hat{\Psi}-\Psi$. In addition, for any
$r\in[0,1]$ we let $\Psi|_{r}$ refer to the value of $\Psi$ using the
nuisances $q_{r}{(t)}=q^{(t)}+r\Delta q^{(t)}$ and
$h_{r}^{(t)}=h^{(t)}+r\Delta h^{(t)}$ in place of $q^{(t)}$ and $h^{(t)}$
respectively for each $t\in[H]$, and define $\Delta_{r}\Psi=\Psi|_{r}-\Psi$.
We note that according to these definitions, $\Psi=\Psi|_{0}$,
$\hat{\Psi}=\Psi|_{1}$, and $\Delta\Psi=\Delta_{1}\Psi$. In what follows below
we will treat $\Delta q^{(t)}$ and $\Delta h^{(t)}$ as non-random square
integrable functions with the same signature as $q^{(t)}$ and $h^{(t)}$
respectively for each $t\in[H]$, which may take arbitrary values. This is in
contrast to previous sections, where $\hat{\Psi}$ was treated as a random
quantity with respect to the sampling distribution of the $n$ iid behavior
trajectories. Finally, we note that it is trivial to verify that for any pair
of quantities $\Psi$ and $\Psi^{\prime}$ we have
$\Delta_{r}(\Psi+\Psi^{\prime})=\Delta_{r}\Psi+\Delta_{r}\Psi^{\prime}$, and
$\Delta_{r}(\Psi\Psi^{\prime})=(\Delta_{r}\Psi)\Psi^{\prime}+\Psi(\Delta_{r}\Psi^{\prime})+(\Delta_{r}\Psi)(\Delta_{r}\Psi^{\prime})$,
which we will frequently apply in the derivations below without further
explanation.

######  Lemma 8.

Under the conditions of Theorem 2, as well as the additional assumption that
$\|q^{(t)}(Z_{t},A_{t})\|<\infty$ and $\|h^{(t)}(W_{t},A_{t})\|<\infty$ for
each $t\in[H]$, $\psi_{\text{DR}}$ satisfies Neyman orthogonality with respect
to the nuisances $q^{(t)}$ and $h^{(t)}$ for all $t\in[H]$. More concretely,