# A Review of Off-Policy Evaluation in Reinforcement Learning

Masatoshi<EMAIL_ADDRESS>[ Chengchun
<EMAIL_ADDRESS>[ Nathan<EMAIL_ADDRESS>[
Masatoshi Uehara is a Ph.D. student in the Department of Computer Science at
Cornell University and Cornell Tech, NYC, USA, .  Chengchun Shi is an
Assistant Professor in the Department of Statistics at London School of
Economics and Political Science, London, UK, .  Nathan Kallus is an Associate
Professor of Operations Research and Information Engineering, Cornell Tech,
NYC, USA, .

###### Abstract

Reinforcement learning (RL) is one of the most vibrant research frontiers in
machine learning and has been recently applied to solve a number of
challenging problems. In this paper, we primarily focus on off-policy
evaluation (OPE), one of the most fundamental topics in RL. In recent years, a
number of OPE methods have been developed in the statistics and computer
science literature. We provide a discussion on the efficiency bound of OPE,
some of the existing state-of-the-art OPE methods, their statistical
properties and some other related research directions that are currently
actively explored.

Off-policy evaluation,

semiparametric methods,

causal inference,

dynamic treatment regime,

offline reinforcement learning,

contextual bandits,

###### keywords:

, ,

##  1 INTRODUCTION

Reinforcement learning (RL, Sutton and Barto, 2018) has been arguably one of
the most vibrant research frontiers in machine learning. It is concerned with
learning an optimal policy in sequential decision making problems to maximize
the long-term reward that the decision maker receives. In the recent few
years, RL has been successfully applied to solve a number of challenging
problems across various domains, including games (Silver et al., 2016),
robotics (Kober, Bagnell and Peters, 2013), ridesharing (Xu et al., 2018) and
autonomous driving (Sallab et al., 2017), to mention a few.

In this paper, we focus on off-policy evaluation (OPE), a fundamental problem
in RL. OPE is concerned with estimating the mean reward of a given decision
policy, known as the _evaluation policy_ , using historical data generated by
a potentially different policy, known as the _behavior policy_. While OPE may
be useful for _online RL_ , where we can experiment with novel policies, it is
most crucial for _offline RL_ , where we only have access to a historical
dataset and are not allowed to experiment. Thus, OPE is important in a number
of applications, where experimentation may be expensive, risky, and/or
unethical, including healthcare (Murphy et al., 2001), recommendation systems
(Chapelle and Li, 2011), education (Mandel et al., 2014), dialog systems
(Jiang et al., 2021) and robotics (Levine et al., 2020). In these settings,
any new policy must first be evaluated offline based on previously collected
historical data before it can be tried in practice. Moreover, reliable
quantification of the uncertainty in the evaluation can be crucial. OPE can
thus be phrased as a statistical estimation and inference problem.

In the statistics literature, OPE is closely related to a line of research on
evaluating the outcome of patients under a fixed or data-dependent decision
policy (Wang et al., 2012; Zhang et al., 2012, 2013; Chakraborty, Laber and
Zhao, 2014; Matsouaka, Li and Cai, 2014; Luedtke and Van Der Laan, 2016;
Luedtke and van der Laan, 2017; Wang et al., 2018; Zhu, Zeng and Song, 2019;
Shi, Lu and Song, 2020; Wu and Wang, 2021). There is in particular a growing
interest in developing statistical methods for precision medicine (see e.g.,
Tsiatis et al., 2019, for an overview), which is a medical paradigm that
focuses on identifying the most effective treatment based on individual
patient information. See also Murphy (2003); Robins (2004); Qian and Murphy
(2011); Zhao et al. (2012a); Lu, Zhang and Zeng (2013); Schulte et al. (2014);
Zhang et al. (2015); Fan et al. (2017); Jiang et al. (2017); Zhu et al.
(2017); Zhang et al. (2018); Shi et al. (2018); Ertefaie and Strawderman
(2018); Mo, Qi and Liu (2021) and the references therein. Formally speaking, a
decision policy (also known as a treatment regime), is a function that takes
as input a patient’s personal information such as their demographic
characteristics, genetic information, clinical measurements and outputs the
treatment that they shall receive from among the options available. For many
chronic diseases such as cancer and diabetes, treatment of patients involves a
series of decisions. Decision policies in these settings are often dynamic,
depending on patients’ responses measured over time. These are known as
dynamic treatment regimes (DTR). The objective of OPE in these settings is to
evaluate the expected outcome of a (dynamic) treatment policy based on
historical data collected from randomized clinical trials or observational
electronic health records.

We note that the statistics literature typically adopts a counterfactual or
potential-outcome framework (Rubin, 2005) to describe the estimand of interest
and impose assumptions such as unconfoundedness and consistency (see Section 2
for details) to guarantee that the estimand can be identified from the
observed data. To the contrary, researchers in the RL community generally do
not use this framework, starting instead from a structural assumption of
working in, for example, a Markov decision process (MDP). Since the objectives
are essentially the same, algorithms developed in the RL literature can be
easily adapted to evaluate the impact of a given DTR. Similarly, results
established in the statistics literature are applicable to more general OPE
problems as well. However, as far as we can tell, researchers that belong to
one community are often not aware of works published in the other community,
and vice versa. This motivates us to present an overview of the recent
literature on OPE from a unified perspective. We remark that in addition to
the statistics and computer science literature, OPE is widely studied in the
economics literature as well (see e.g., Kitagawa and Tetenov, 2018; Huber,
2019).

Recently, there have been a few reviews of existing statistical learning
methods for precision medicine (see e.g., Kosorok and Moodie, 2015; Kosorok
and Laber, 2019). However, these methods were primarily motivated by
applications in finite horizon settings with only a few treatment stages. In
this paper, we focus on settings where the horizon (number of treatment
stages) is very long and possibly infinite. These settings are natural for
formulating sequential decision making problems in robotics, ridesharing,
autonomous driving, and have been widely studied in the computer science
literature (Sutton and Barto, 2018). The long- and infinite-horizon setting
has more recently been adopted in the statistics literature on learning and
evaluating optimal DTRs in mobile health applications (Boruvka et al., 2018;
Liao, Klasnja and Murphy, 2020; Luckett et al., 2020; Hu et al., 2020; Liao et
al., 2022; Shi et al., 2022a). OPE is challenging in these settings. For
example, directly applying the stepwise (augmented) inverse propensity score
weighted ((A)IPW) estimator (Robins, Rotnitzky and Scharfstein, 1999; Zhang et
al., 2013) developed in the short finite horizon settings might be
inapplicable or sub-optimal due to the following reasons:

  * •

First, these stepwise methods are inconsistent with finitely many trajectories
(e.g., patients). Datasets of this type frequently occur in several mobile
health applications (see e.g., Marling and Bunescu, 2018) where the total
number of patients is small while the number of decision points can be very
large.

  * •

Second, these stepwise methods are known to suffer from the curse of horizon
in the sense that its mean squared error (MSE) grows exponentially fast with
respect to the horizon (Liu et al., 2018; Gottesman et al., 2019). As we will
explain, the exponential dependence on horizon is unavoidable when the
observed data are generated by a non-Markov decision process (NMDP), which is
typically the setting that the existing literature on DTR considers, but it
can be avoided if we assume additional structure.

Recent works from the computer science literature (see e.g., Liu et al., 2018;
Kallus and Uehara, 2019a) suggest that if we are willing to assume some
additional structures, _i.e._ , Markovianity and time-homogeneity, we can
alleviate these challenges. First, Markovianity makes it possible for us to
construct efficient estimators to break the curse of horizon. Second, time-
homogeneity enables us to construct efficient estimators even from a single
trajectory. We remark that most works in computer science consider settings
with these structures. These settings differ from those studied in the
classical statistics literature.

This article reviews the OPE problem from a statistical perspective and
focusing on the Markovian setting with long or infinite horizon. We review
what is the best-possible asymptotic MSE (also known as the efficiency bound)
that one can hope for in OPE and discuss ways to construct efficient
estimators that achieve this bound. Efficiency bounds have been recognized as
natural criteria to understand the statistical limits of parameter estimation
and to compare different estimators (van Der Laan and Robins, 2003). We will
also discuss some recent OPE methods developed in the computer science
literature, summarize their advantages and limitations, and propose possible
directions for future development.

The rest of the article is organized as follows. In Section 2, for pedagogic
purposes, we start with _non-dynamic_ setting (Dudik et al., 2014), a special
case of RL with independent transitions, where we present the efficiency bound
and introduce various estimators with different statistical properties.
Section 3 is concerned with OPE under an NMDP or time-varying MDP and Section
4 under a (time-homogeneous) MDP.We introduce the efficiency bounds for each
setting and present methodologies to construct efficient estimators that
achieve these bounds using two key functions, Q-functions and marginal density
ratios. We further briefly touch on model-based estimators and compare model-
free estimators that employ Q-functions and marginal ratios. In Section 5, we
summarize additional important statistical theories of OPE, such as
convergence rates of Q-functions and marginal density ratios, and what makes
OPE problems special, compared to standard conditional moment problems in
statistics. In Section 6, we give an overview of some other related research
directions that are currently beingactively explored.

##  2 NON-DYNAMIC SETTING

To begin with, we consider estimating a given evaluation policy’s expected
return (value) in the non-dynamic setting (sometimes referred to as the
contextual bandit setting, even if not studying adaptive experimentation). The
problem can be formulated as follows. The decision maker first observes some
contextual information (also called baseline covariates or state variables),
summarized into $S\in\mathcal{S}$ in some domain $\mathcal{S}$. An action
(also called treatment or intervention) $A$ is then selected out of a set of
candidates $\mathcal{A}$ according to some behavior policy $\pi^{\mathrm{b}}$
(also known as the propensity score, Rosenbaum, 1983) such that
$\pi^{\mathrm{b}}(\cdot\mid s)$ corresponds to the probability mass or density
function of $A$ conditional on $S=s$, depending on whether $A$ is discrete or
continuous. In return, the decision maker receives a numerical reward
$R\in\mathbb{R}$ for the chosen action. This process repeats for multiple
steps, yielding the following observed dataset:

$\displaystyle\\{\mathcal{J}^{(i)}\\}_{i=1}^{n}=\\{S^{(i)},A^{(i)},R^{(i)}\\}_{i=1}^{n}\overset{\text{i.i.d}}{\sim}P_{\pi^{\mathrm{b}}}(s,a,r)=p_{S}(s)\pi^{\mathrm{b}}(a|s)p_{R|S,A}(r|s,a),$
(1)

where $(S^{(i)},A^{(i)},R^{(i)})$ denotes the state-action-reward triplet
observed at time $i$ and the notation $P_{\pi^{\mathrm{b}}}$ is used to
indicate that the data are generated according to the behavior policy. In
addition to the observed reward, we use $R(a)$ to denote the potential
outcome, representing the reward that the decision maker would have received
if action $a$ is selected. We remark that the above setting is essentially the
same as in the statistics literature on causal inference (see e.g., Imbens and
Rubin, 2015; Hernan and Robins, 2019) and estimation of optimal individualized
treatment regimes in point exposure studies (see e.g., Zhang et al., 2012).

In OPE, our goal is to estimate the expected reward of a given evaluation
policy $\pi^{\mathrm{e}}$. Formally speaking, $\pi^{\mathrm{e}}$ is a function
that maps the space of contextual information $\mathcal{S}$ to a probability
distribution on $\mathcal{A}$. When the action space is discrete, the decision
maker will set $A=a$ with probability $\pi^{\mathrm{e}}(a|s)$ under
$\pi^{\mathrm{e}}$. In the causal inference literature, most papers consider
settings of binary treatment and state-agnostic evaluation policies, i.e.,
$\mathcal{A}=\\{0,1\\}$ and that $\pi^{\mathrm{e}}(a|s)=\mathrm{I}(a=1)$ or
$\pi^{\mathrm{e}}(a|s)=\mathrm{I}(a=0)$. They focus on estimating the average
treatment effect (ATE), defined as the value difference between the two state-
agnostic policies. When the action space is continuous, we require
$\pi^{\mathrm{e}}$ to be a stochastic policy, i.e.,
$\pi^{\mathrm{e}}(\cdot|s)$ corresponds to a non-degenerate probability
density function for any $s$. Some extra care is needed when
$\pi^{\mathrm{e}}$ is a deterministic policy, i.e., $A$ is a deterministic
function of $S$ under $\pi^{\mathrm{e}}$. We discuss this in detail in Section
6.5. Given $S$, let
$R(\pi^{\mathrm{e}})=\sum_{a\in\mathcal{A}}R(a)\pi^{\mathrm{e}}(a|S)$ denotes
the potential outcome that would have been observed under $\pi^{\mathrm{e}}$.
We aim to estimate the value $\mathbb{E}[R(\pi^{\mathrm{e}})]$ denoted by $J$
based on the dataset in (1). Toward that end, we need the following
assumptions.

######  Assumption 1 (Weak positivity).

The support of $\pi^{\mathrm{e}}(\cdot|s)$ is included in the support of
$\pi^{\mathrm{b}}(\cdot|s)$ for any $s\in\mathcal{S}$.

######  Assumption 2 (Consistency).

$R=R(A)$, almost surely.

######  Assumption 3 (Unconfoundeness).

For any $a\in\mathcal{A}$, $A$ and $R(a)$ are conditionally independent given
$S$.

Assumption 1 is slightly weaker than the standard positivity assumption
commonly imposed in the literature on learning optimal individualized
treatment regimes. The consistency assumption requires the reward at each time
to depend on their own action only. In other words, there is no interference
effect across time. Assumption 3 is commonly referred to as the no unmeasured
confounders assumption. It automatically holds when the datasets are collected
from randomized studies where the behavior policy is a constant function of
the contextual information.

For a given function $f(s,a,r)$ of the state-action-reward triplet, we use
$\mathbb{E}_{P_{\pi}}[f]$ to denote its expectation assuming the data follows
a given policy $\pi$, i.e.,

$\displaystyle\mathbb{E}_{P_{\pi}}[f]=\int
f(s,a,r)P_{\pi}(s,a,r)\mathrm{d}(s,a,r)=\int
f(s,a,r)p_{S}(s)\pi(a|s)p_{R|S,A}(r|s,a)\mathrm{d}(s,a,r).$

In addition, let $\mathbb{E}_{n}[f]$ denote $\mathbb{E}_{n}[f]\coloneqq
1/n\sum_{i=1}^{n}f(S^{(i)},A^{(i)},R^{(i)})$ and $\|f\|_{2}$ denote
$\\{\mathbb{E}_{P_{\pi^{\mathrm{b}}}}[f^{2}]\\}^{1/2}$. Under Assumptions 1, 2
and 3, we can identify the parameter of interest from the observed data.

######  Theorem 1.

Suppose Assumptions 1, 2 and 3 hold. Let $\eta(s,a)=\pi^{\mathrm{e}}(a\mid
s)/\pi^{\mathrm{b}}(a\mid s)$.

$\displaystyle\mathbb{E}[R(\pi^{\mathrm{e}})]=\mathbb{E}_{P_{\pi^{\mathrm{e}}}}[r]=\mathbb{E}_{P_{\pi^{\mathrm{b}}}}[\eta(s,a)r].$
(2)

We make a few remarks. First, the consistency and unconfoundedness assumptions
ensure that the first equation in (2) holds (see e.g., Tsiatis, 2006, Section
13.3). It implies that the target parameter can be written as a function of
the observed data. The second equation can be easily verified under the weak
positivity assumption. Second, as we have commented, most researchers in the
RL community do not adopt the potential outcome framework. However, the
developed theories and methods are applicable under Assumptions 2 and 3.

We next present three commonly-used estimators for policy evaluation. The
first one is the importance sampling (IS) estimator, defined by

$\displaystyle\mathbb{E}_{n}\left[\frac{\pi^{\mathrm{e}}(a|s)}{\hat{\pi}^{b}(a|s)}r\right],$

where $\hat{\pi}^{b}$ denotes some estimator for $\pi^{\mathrm{b}}$. The above
estimator is also referred to as an IPW or Horvitz-Thompson estimator (Hernan
and Robins, 2019). A potential limitation of such an estimator is that when
$\pi^{\mathrm{e}}$ differs greatly from $\pi^{\mathrm{b}}$, the ratio
$\pi^{\mathrm{e}}/\pi^{\mathrm{b}}$ can be very large for some sample values,
making the resulting estimator unstable. To overcome this limitation, we could
either use a self-normalized IS (NIS, Owen, 2013) estimator defined by

$\displaystyle\mathbb{E}_{n}\left[\frac{\pi^{\mathrm{e}}(a,s)}{\hat{\pi}^{b}(a|s)}r\right]/\mathbb{E}_{n}\left[\frac{\pi^{\mathrm{e}}(a|s)}{\hat{\pi}^{b}(a|s)}\right],$

or a truncated IS estimator (Heckman, Ichimura and Todd, 1998) by replacing
$\hat{\pi}^{b}$ with $\max(\epsilon,\hat{\pi}^{b})$ for some small constant
$\epsilon>0$.

The second estimator is the direct method (DM) estimator, defined by
$\mathbb{E}_{n}[\hat{q}(s,\pi^{\mathrm{e}})]$ where
$q(s,a)=\mathbb{E}[R|S=s,A=a]$, $\hat{q}$ denotes some estimator of $q$, and
$\hat{q}(s,\pi^{\mathrm{e}})$ is a shorthand for
$\mathbb{E}_{a\sim\pi^{\mathrm{e}}(a|s)}[\hat{q}(s,a)|s]$. Such an estimator
is also referred to as a regression-type estimator. Notice that DM is biased
when the regression model is misspecified. To the contrary, IS is unbiased
with known $\pi^{\mathrm{b}}$, as in randomized studies. However, IS might
have a much larger variance than DM when $\pi^{\mathrm{e}}$ differs
considerably from $\pi^{\mathrm{b}}$. This represents a bias-variance trade-
off. In addition, DM requires a weaker coverage assumption than IS. For
instance, suppose that we use a linear model, e.g.,
$q(s,a)=\langle\theta,\phi(s,a)\rangle$. Then DM requires
$\sup_{x}x^{\top}\mathbb{E}_{P_{\pi^{e}}}[\phi(s,a)\phi(s,a)^{\top}]x/x^{\top}\mathbb{E}_{P_{\pi^{b}}}[\phi(s,a)\phi(s,a)^{\top}]x<\infty$.
This is weaker than $\max_{(a,s)}\pi^{e}(a\mid s)/\pi^{b}(a\mid s)<\infty$,
the coverage condition required by IS.

The third estimator combines the first two for more robust policy evaluation.
It is referred to as the doubly robust estimator, defined as

$\displaystyle\hat{J}_{\mathrm{dr}}=\mathbb{E}_{n}\left[\frac{\pi^{\mathrm{e}}(a|s)}{\hat{\pi}^{b}(a|s)}\\{r-\hat{q}(s,a)\\}+\hat{q}(s,\pi^{\mathrm{e}})\right].$

Such an estimator has been extensively studied in the statistics literature
(see e.g., Robins, Rotnitzky and Zhao, 1994; Scharfstein, Rotnizky and Robins,
1999; Bang and Robins, 2005; Tsiatis, 2006; Zhang et al., 2012; Chernozhukov
et al., 2018; Foster and Syrgkanis, 2019; Chernozhukov, Newey and Singh,
2018). Dudik et al. (2014) introduced this estimator in the machine learning
literature.

We next briefly discuss some statistical properties of the doubly robust
estimator. First, it is doubly robust in that as long as either model for
$\hat{q}(s,a)$ or $\hat{\pi}^{b}(a|s)$ is well-specified, the final estimator
is consistent.

Second, it is semiparametrically efficient in that its MSE achieves the
efficiency bound under certain rate conditions specified below. Formally
speaking, given a model for the joint distribution function of the state-
action-reward triplet, the efficiency bound is defined as the lower bound of
the asymptotic MSEs among all regular $\sqrt{n}$-consistent estimators with
respect to the model (see e.g., van der Vaart, 1998, Chapters 7 and 25). More
specifically, regular estimators are those whose limiting distributions are
insensitive to small changes to the data generating process (DGP) within the
region of the model and the efficient estimator is the one whose MSE is
asymptotically equivalent to the efficiency bound. The efficient influence
function (EIF) plays a key role in constructing efficient estimators. One
popular approach to obtain the EIF is to represent the derivative of the
target with respect to (w.r.t.) the model parameters as the integral of a
product of a certain function and a score function (see e.g., Kennedy, 2022,
Section 3.4). When the model is nonparametric (as required in Theorem 2), this
function is unique and equals the EIF. Given the EIF, its empirical average
produces the efficient estimator.

Theorem 2 below summarizes the efficiency bound and the associated EIF of
policy value w.r.t. the nonparametric model. Its detailed proof can be found
in Robins, Rotnitzky and Zhao (1994); Narita, Yasui and Yata (2019).

######  Theorem 2.

The EIF of $J$ w.r.t. the nonparametric model $\mathcal{M}$ is

$\displaystyle\eta(s,a)\\{r-q(s,a)\\}+q(s,\pi^{\mathrm{e}})-\mathbb{E}[R(\pi^{\mathrm{e}})].$
(3)

The efficiency bound of $J$ w.r.t. $\mathcal{M}$ is

$\displaystyle
V(\mathcal{M})=\mathbb{E}_{P_{\pi^{\mathrm{b}}}}\left[\eta^{2}(s,a)\mathrm{var}_{P_{\pi^{\mathrm{b}}}}[r|s,a]\right]+\mathrm{var}_{P_{\pi^{\mathrm{b}}}}[q(s,\pi^{\mathrm{e}})]$

where $\mathrm{var}_{P_{\pi^{\mathrm{b}}}}[r|s,a]$ denotes the conditional
variance of $R$ given $(A,S)=(a,s)$.

Notice that the model $\mathcal{M}$ specifies the joint distribution of the
state-action-reward triplet. As such, the $q$-function, the behavior policy
(e.g., conditional distribution of the action given the state) and the density
ratio are determined by $\mathcal{M}$. In addition, as we have commented, an
empirical average of the EIF produces the efficient estimator
$\mathbb{E}_{n}[\eta(s,a)\\{r-q(s,a)\\}+q(s,\pi^{\mathrm{e}})]$. However,
since $q(s,a)$ and $\eta(s,a)$ are unknown, we need to plug-in their
estimators. The resulting value estimator equals $\hat{J}_{\mathrm{dr}}$.

Third, sample splitting allows us to use one part of the data to learn the
nuisance functions $q$ and $\pi^{b}$, and the remaining part to do the
estimation of the main parameter, i.e., the value. When coupled with sample
splitting, the scaled MSE
$n\mathbb{E}[|\hat{J}_{\mathrm{dr}}-\mathbb{E}[R(\pi^{\mathrm{e}})]|^{2}]$
achieves the efficiency bound under mild rate conditions on the estimated
nuisance functions $\hat{q}$ and $\hat{\pi}^{b}$ (Zheng and van Der Laan,
2011; Chernozhukov et al., 2018). Specifically, we only require
$\|\hat{\pi}^{b}-\pi^{b}\|_{2}=\mathrm{o}_{p}(n^{-1/4})$ and
$\|\hat{q}-q\|_{2}=\mathrm{o}_{p}(n^{-1/4})$, allowing these nuisance function
estimators to converge at rates that are slower than the usual parametric rate
$O_{p}(n^{-1/2})$ . It allows us to apply the highly adaptive Lasso (Benkeser
and van der Laan, 2016), random forest (Wager and Walther, 2016) and deep
learning (LeCun, Bengio and Hinton, 2015) 111The best possible minimax rate
that a nonparametric estimator of $q$ can achieve is given by
$n^{-\alpha/(d+2\alpha)}$ under the assumption that $q$ belongs to a Holder
ball with dimension $d$ and smoothness parameter $\alpha$ (Tsybakov, 2009). It
is immediate to see that the rate becomes slower when the state is high-
dimensional or the function is non-smooth, leading to the potential violation
of the rate condition. We also remark that when $q$ is estimated via state-of-
the-art deep learning methods, it is possible to obtain convergence rates that
depend on the intrinsic dimension instead of the original dimension (Schmidt-
Hieber, 2019; Nakada and Imaizumi, 2020; Suzuki, 2018). In addition, the
$o_{p}(n^{-1/4})$-rate requirement can be further relaxed using the theory of
higher-order influence functions (Robins et al., 2017; Mukherjee, Newey and
Robins, 2017).  . Without sample splitting, some additional metric entropy
conditions need to be imposed on these nuisance estimators and many machine
learning estimators might fail to satisfy these conditions (Díaz, 2019). The
purpose of imposing the metric entropy condition is to verify a stochastic
equicontinuity condition in the theoretical analysis. We remark that sample-
splitting is commonly used for statistical inference (see e.g., Romano and
DiCiccio, 2019).

Finally, we remark that there exist some specific DM and IS estimators that
satisfy the doubly-robustness property or achieve the efficiency bound. For
instance, Kang and Schafer (2007) developed a DM estimator, which utilizes a
weighted regression method to estimate $q$-functions by using weights
proportional to $\pi^{\mathrm{e}}/\pi^{\mathrm{b}}$. This estimator is doubly
robust. Similarly, a doubly robust IS estimator was proposed by Scharfstein,
Rotnizky and Robins (1999). Hahn (1998) developed a DM estimator that
estimates $q(s,a)$ nonparametrically. It achieves the efficiency bound under
certain smoothness conditions. Hirano, Imbens and Ridder (2003) proposed an
efficient nonparametric IS estimator under similar conditions.

Although $\hat{J}_{\mathrm{dr}}$ is widely used, it is known that the vanilla
doubly robust estimator $\hat{J}_{\mathrm{dr}}$ suffers from several
limitations, especially when the nuisance function models are misspecified. To
address these limitations, a number of estimators have been further developed.
First, Rubin and van Der Laan (2008) and Cao, Tsiatis and Davidian (2009)
proposed some alternative doubly robust estimators that achieve minimum
asymptotic variance among some class even when the model for $q$ is
misspecified. Tan (2010) developed a doubly-robust estimator that is bounded
and intrinsically efficient, e.g., guaranteed to be more efficient than IS and
NIS estimators asymptotically even when the model for $q$ is misspecified. All
the aforementioned estimators require the correct specification of
$\pi^{\mathrm{b}}$ to ensure certain optimality properties. Vermeulen and
Vansteelandt (2015) proposed a bias-reduced estimator to handle the case where
both models are misspecified. There are also some other estimators, including
the covariate balancing-type estimator (Wang and Zubizarreta, 2020; Imai and
Ratkovic, 2014; Ning, Sida and Imai, 2020), the minimax estimator (Hirshberg
and Wager, 2017; Chernozhukov et al., 2020), the switching estimator (Tsiatis
and Davidian, 2007; Wang, Agarwal and Dudik, 2017), the target maximum
likelihood estimator (TMLE, van der Laan and Rose, 2018), the high-order
influence function estimator (Robins et al., 2017; Mukherjee, Newey and
Robins, 2017) and the distributionally robust estimator (Si et al., 2020),
among many others (see e.g., Agarwal et al., 2017; Su et al., 2020; Sondhi,
Arbour and Dimmery, 2020; Singh, 2021).

##  3 OFF-POLICY EVALUATION ON NMDP, TMDP

This section is concerned with OPE in general sequential decision making
problems with dependent transitions. We focus on two particular data
generating processes, NMDP and time-varying Markov decision process (TMDP). As
commented in the introduction, estimators in NMDPs suffer from the curse of
horizon (Liu et al., 2018). Their MSEs grow exponentially fast with respect to
the number of horizon $H$ in general. On the contrary, in TMDPs, there exist
estimators whose MSEs grow polynomially in $H$. We will discuss this in
detail.

This section is organized as follows. We first introduce the data generating
process and formulate the problem. We next present the DM and IS estimators
under these settings and discuss their limitations. Finally, we present the
efficiency bounds in NMDP and TMDP, and introduce efficient estimators whose
MSEs achieve these lower bounds.

###  3.1 Data Generating Process and Problem Formulation

We choose not to use the potential outcome framework to simplify the
presentation. The data trajectory from NMDP or TMDP can be summarized as a
sequence of state-action-reward-next state quadruplets
$\mathcal{J}=\\{(S_{t},A_{t},R_{t},S_{t+1})\\}_{1\leq t\leq H}$ where $H$
denotes the horizon. Similar to the bandit setting, at time $t$, the decision
maker observes a state vector $S_{t}$ from the environment, based on which an
action $A_{t}$ is selected based on the observed data history. The environment
responds by providing the decision maker with an immediate reward
$R_{t}\in\mathbb{R}$ and moves to the next state $S_{t+1}$. Notice that
contextual bandits correspond to a special case of NMDPs/TMDPs with $H=1$.

Let $p_{S_{1}}$ denote the probability mass/density function of $S_{1}$. Let
$\\{(s_{t},a_{t},r_{t},s_{t+1})\\}_{1\leq t\leq H}$ denote a realization of
$\mathcal{J}$. In addition, let
$\mathcal{j}_{a_{t}}=(s_{1},a_{1},r_{1},\dots,s_{t},a_{t})$ and
$\mathcal{j}_{s_{t}}=(s_{1},a_{1},r_{1},\dots,a_{t-1},s_{t})$ denote the
state-action-reward history up to $a_{t}$ and $s_{t}$, respectively. In an
NMDP, we assume the actions are generated according to a history-dependent
behavior policy $\pi^{b}=\\{\pi_{t}^{b}\\}_{1\leq t\leq H}$ where each
$\pi_{t}^{b}$ maps $\mathcal{j}_{s_{t}}$ to a probability mass/density
function $\pi_{t}^{b}(\cdot|\mathcal{j}_{s_{t}})$ on the action space. In
addition, the state transition and the reward distribution are history
dependent as well. We use $p_{S_{t+1},R_{t}}(\cdot|\mathcal{j}_{a_{t}})$ to
denote the conditional probability mass/density function of $(S_{t+1},R_{t})$
given the past data history. We use $P_{\pi^{b}}$ to denote the joint
distribution function of the data trajectory. As commented in the
introduction, such a data generating process is commonly used in the
literature on learning dynamic treatment regimes.

A TMDP is a special case of the NMDP where the observed data satisfy the
Markov property. Informally speaking, future and past observations are
conditionally independent given the present. Specifically,
$p_{S_{t+1},R_{t}}(\cdot|\mathcal{j}_{a_{t}})$ depends on
$\mathcal{j}_{a_{t}}$ only through the current state-action pair
$(s_{t},a_{t})$. We use $p_{S_{t+1},R_{t}}(\cdot|s_{j},a_{j})$ to denote the
corresponding conditional distribution. In addition, we assume the behavior
policy is a Markov policy. In other words,
$\pi_{t}^{b}(a_{t}\mid\mathcal{j}_{s_{t}})=\pi_{t}^{b}(a_{t}\mid s_{t})$ for
any $t$.

To summarize, the joint distribution of the data from an NMDP can be
factorized as follows,

$\displaystyle
P_{\pi^{b}}=p_{S_{1}}(s_{1})\prod_{t=1}^{H}\pi_{t}^{b}(a_{t}\mid\mathcal{j}_{s_{t}})p_{S_{t+1},R_{t}}(s_{t+1},r_{t}\mid\mathcal{j}_{a_{t}}).$
(4)

In TMDP, the joint distribution becomes

$\displaystyle
P_{\pi^{b}}=p_{S_{1}}(s_{1})\prod_{t=1}^{H}\pi_{t}^{b}(a_{t}\mid
s_{t})p_{S_{t+1},R_{t}}(s_{t+1},r_{t}\mid s_{t},a_{t}).$ (5)

We use $\mathcal{M}_{\mathrm{NMDP}}$ and $\mathcal{M}_{\mathrm{TMDP}}$ to
denote the nonparametric models specified by (4) and (5), respectively,
without any other parametric assumptions. In practice, the underlying data
generating process is usually unknown to us. In that case, we can test the
Markov assumption based on the observed data to distinguish between NMDP and
TMDP (Shi et al., 2020)222 When the model selection results are uncertain,
e.g., the test sometimes inconsistently classifies a TMDP as an NMDP, the
subsequent inference for the off-policy value will be problematic. Problems of
this type have been known as “selective inference” (Taylor and Tibshirani,
2015). In that case, sample-splitting can be employed to account for model
selection uncertainty and to ensure valid inference. For instance, we may use
one half of the data for model selection and the remaining half for the
subsequent inference. Other data-splitting methods can be potentially used as
well (see e.g., Meinshausen, Meier and Bühlmann, 2009; Luedtke and Van Der
Laan, 2016; Shi, Lu and Song, 2020; Shi et al., 2021a). .

In OPE, our goal is to estimate the average cumulative reward of an evaluation
policy $\pi^{e}$,
$J^{(H)}=\mathrm{E}_{P_{\pi^{e}}}\left[\sum_{t=1}^{H}\gamma^{t-1}r_{t}\right],$
using $n$ data trajectories (e.g., plays of a game or patients in healthcare
applications) $\mathcal{D}=\\{\mathcal{J}^{(1)},\dots,\mathcal{J}^{(n)}\\}$
that are i.i.d. copies of $\mathcal{J}$. Here, a discount factor $\gamma$ (
$0\leq\gamma\leq 1$) balances the trade-off between immediate and future
rewards. We require $\pi^{e}$ to be a Markov policy in TMDP. This assumption
is reasonable as there exists an optimal Markov policy whose expected return
is no worse than any history-dependent policy under the memoryless assumption
(Bertsekas, 2012).

To conclude this section, we introduce some additional notations. First, the
state-action value functions (better known as the Q-function) and (state)
value functions are defined as the conditional expectation of the cumulative
reward given the past data history under $\pi^{e}$. Specifically, we define

$\displaystyle q_{t}(\mathcal{j}_{a_{t}})$
$\displaystyle=\mathrm{E}_{P_{\pi^{e}}}\left[\sum_{k=t}^{H}\gamma^{k-t-1}r_{k}\mid\mathcal{j}_{a_{t}}\right],\,v_{t}(\mathcal{j}_{s_{t}})=q_{t}(\mathcal{j}_{s_{t}},\pi_{t}^{e})=\mathrm{E}_{a_{t}\sim\pi_{t}^{e}(a_{t}\mid\mathcal{j}_{s_{t}})}[q_{t}\mid\mathcal{j}_{s_{t}}],$

for any $t$. For TMDPs, the data history before a time step $t$
($\mathcal{j}_{a_{t-1}}$) is conditionally independent of current and future
rewards (e.g., $r_{t},\cdots,r_{H}$) given $s_{t},a_{t}$. With some abuse of
notation, we use $q_{t}(s_{t},a_{t})$ and
$v_{t}(s_{t})=q_{t}(s_{t},\pi_{t}^{e})$ to represent the corresponding Q- and
state value functions under TDMPs.

Second, we denote the density ratio at time $t$ between the evaluation and
behavior policy by
$\eta_{t}(\mathcal{j}_{a_{t}})=\pi^{e}_{t}(a_{t}\mid\mathcal{j}_{s_{t}})/\pi^{b}_{t}(a_{t}\mid\mathcal{j}_{s_{t}})$.
We define the cumulative density ratio and the marginal density ratio up to
time $t$ as follows,

$\displaystyle\lambda_{t}(\mathcal{j}_{a_{t}})$
$\displaystyle=\prod_{k=1}^{t}\eta_{k}(\mathcal{j}_{a_{k}}),\qquad\mu_{t}(s_{t},a_{t})=\frac{p_{\pi^{e}_{t}}(s_{t},a_{t})}{p_{\pi^{b}_{t}}(s_{t},a_{t})},\quad
w_{t}(s_{t})=\frac{p_{\pi^{e}_{t}}(s_{t})}{p_{\pi^{b}_{t}}(s_{t})},$

where $p_{\pi_{t}}(\cdot,\cdot)$ and $p_{\pi_{t}}(\cdot)$ denotes the
_marginal_ distribution of $S_{t},A_{t}$ and $S_{t}$, assuming the system
follows a given policy $\pi$.

Finally, for a given function $g(\mathcal{j})$ where
$\mathcal{j}=(s_{1},a_{1},r_{1},s_{2},a_{2},r_{2},\dots,s_{T},a_{T},r_{H},s_{H+1})$
denotes the entire data trajectory, we use
$\|g\|_{2}=\mathrm{E}_{P_{\pi^{\mathrm{b}}}}[\left|g\right|^{2}]^{1/2}$ to
denote its $L^{2}$-norm under the behavior policy. Let
$\textstyle\mathrm{E}_{n}[g(\mathcal{j})]=n^{-1}\sum_{i=1}^{n}g(\mathcal{\mathcal{J}}^{(i)}).$

###  3.2 DM and IS Estimators

We introduce two popular OPE methods in this section. The first approach is
the _direct method_ (DM), where we estimate the Q-function based on the
observed data and directly use it to derive the value estimator. Q-functions
are typically estimated by a recursive way (Sutton and Barto, 2018; Clifton
and Laber, 2020). We will discuss the detailed estimating procedure in Section
5.1. Once we have an estimate $\hat{q}_{1}$ of $q_{1}$, the DM estimate is
given by

$\hat{J}^{(H)}_{\mathrm{DM}}=\mathrm{E}_{n}\left[\hat{q}_{1}(s_{1},\pi^{\mathrm{e}}_{1})\right].$

One potential limitation of DM is that the estimator might suffer from a large
bias due to the model misspecification of Q-function.

The second approach is the _importance sampling_ (IS) method, which averages
the data weighted by the density ratio of the evaluation and behavior
policies. The resulting estimator is also known as the stepwise IPW estimator
(Robins, Rotnitzky and Scharfstein, 1999). Given some estimator
$\hat{\lambda}_{t}$ of the cumulative density ratios $\lambda_{t}$, the IS
estimator is defined by

$\displaystyle{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\hat{J}^{(H)}_{\mathrm{IS}}=\mathrm{E}_{n}\left[\sum_{t=1}^{H}\gamma^{t-1}\hat{\lambda}_{t}r_{t}\right].}$

When the behavior policy is known and we set $\hat{\lambda}_{t}$ to its oracle
value, the IS estimator is unbiased. However, it might suffer from a large
variance due to that $\lambda_{t}$ can be very large for some sample values.
To alleviate this problem, we can consider a self-normalized version of the IS
estimator (Precup, Sutton and Singh, 2000; Robins et al., 2007; Kuzborskij et
al., 2021), given by

$\displaystyle\hat{J}^{(H)}_{\mathrm{NIS}}=\mathrm{E}_{n}\left[\sum_{t=1}^{H}\gamma^{t-1}\left\\{\hat{\lambda}_{t}r_{t}/\mathrm{E}_{n}\left[\hat{\lambda}_{t}\right]\right\\}\right].$

###  3.3 Efficiency Bounds in NMDP and TMDP

We first introduce the efficiency bound and the EIF for estimating $J^{(H)}$
under NMDP (Bibaut et al., 2019; Kallus and Uehara, 2020a) 333Special cases of
the EIF and efficiency bound have been considered in the literature. In the
statistics literature, Robins, Rotnitzky and Zhao (1995) studied the case
where the evaluation policy is state-agnostic in the context of missing data,
and Murphy et al. (2001) considered a deterministic evaluation policy in the
context of marginal structural models beyond policy evaluation. In the
computer science literature, Jiang and Li (2016) derived the efficiency bound
under NMDP with finite state and action spaces. However, they did not derive
the efficiency bound and the EIF when the state or action space is
continuous.. It extends the contextual bandits results in Theorem 2 to
sequential decision making.

######  Theorem 3 (Efficiency bound and EIF under $\mathrm{NMDP}$).

The efficient influence function of $J^{(H)}$ w.r.t.
$\mathcal{M}_{\mathrm{NMDP}}$ is

$\displaystyle\phi_{\mathrm{NMDP}}(\mathcal{j};\\{\lambda_{t}\\},\\{q_{t}\\})=-J^{(H)}+\sum_{t=1}^{H}\\{\gamma^{t}\lambda_{t}\left(r_{t}-q_{t}\right)+\gamma^{t-1}\lambda_{t-1}v_{t}\\},\quad
v_{t}=q_{t}(\mathcal{j}_{s_{t}},\pi_{t}),$ (6)

where $\lambda_{0}=\gamma$. The efficiency bound w.r.t.
$\mathcal{M}_{\mathrm{NMDP}}$ is

$\displaystyle
V(\mathcal{M}_{\mathrm{NMDP}})=\mathrm{var}_{P_{\pi^{\mathrm{b}}}}[v_{0}(s_{0})]+\sum_{t=1}^{H}\mathrm{E}_{P_{\pi^{\mathrm{b}}}}\left[\gamma^{2(t-1)}\lambda^{2}_{t}(\mathcal{j}_{a_{t}})\mathrm{var}\left(r_{t}+\gamma
v_{t+1}\mid\mathcal{j}_{a_{t}}\right)\right].$ (7)

We next introduce the efficiency bound and the EIF under TMDP (Kallus and
Uehara, 2020a) 444Jiang and Li (2016) derived the efficiency bound under TMDP
with finite state and action spaces. However, they did not derive the
efficiency bound and the EIF when the state or action space is continuous..

######  Theorem 4 (Efficiency bound and EIF under $\mathrm{TMDP}$).

The efficient influence function of $J^{(H)}$ w.r.t.
$\mathcal{M}_{\mathrm{TMDP}}$ is

$\displaystyle\phi_{\mathrm{TMDP}}(\mathcal{j};\\{\mu_{t}\\},\\{q_{t}\\})=-J^{(H)}+\sum_{t=1}^{H}\\{\gamma^{t}\mu_{t}\left(r_{t}-q_{t}\right)+\gamma^{t-1}\mu_{t-1}v_{t}\\},\quad
v_{t}=q_{t}(s_{t},\pi_{t}),$ (8)

where $\mu_{0}=\gamma$.  The efficiency bound w.r.t.
$\mathcal{M}_{\mathrm{TMDP}}$ is

$\displaystyle
V(\mathcal{M}_{\mathrm{TMDP}})=\mathrm{var}_{P_{\pi^{\mathrm{b}}}}[v_{0}(s_{0})]+\sum_{t=1}^{H}\mathrm{E}_{P_{\pi^{\mathrm{b}}}}\left[\gamma^{2(t-1)}\mu^{2}_{t}(s_{t},a_{t})\mathrm{var}\left(r_{t}+\gamma
v_{t+1}\mid s_{t},a_{t}\right)\right].$ (9)

We make some observations. First, the difference between
$\phi_{\mathrm{NMDP}}(\mathcal{j};\\{\lambda_{t}\\},\\{q_{t}\\})$ and
$\phi_{\mathrm{TMDP}}(\mathcal{j};\\{\mu_{t}\\},\\{q_{t}\\})$ is whether
$\lambda_{t}$ or $\mu_{t}$ is being utilized. Second, these EIFs and
efficiency bounds are derived with respect to semiparametric models.  They
remain unchanged even if we impose a more restricted model with a known
behavior policy. Third, the differences between the two bounds characterize
the effect of taking into consideration additional problem structures on the
feasibility of OPE. To elaborate, assume (1) $0\leq R_{t}\leq
R_{\mathrm{max}}$ for all $t=1,\dots,H$, (2)
$\mathrm{E}[\log(\eta_{t})]\geq\log(C)$ for all $t=1,\dots,H$ and
$\mathbb{E}[\log(\mathrm{var}[r_{t}+\gamma
v_{t+1}\mid\mathcal{j}_{a_{t}}])]\geq\log(V^{2}_{\min})$, (3)
$0\leq\mu_{t}\leq C^{\prime}$ for all $t=1,\dots,H$. The latter two conditions
essentially require that the behavior and evaluation policies do not differ
too much. Under these assumptions, we can show that

$\displaystyle V(\mathcal{M}_{\mathrm{TMDP}})\leq
C^{\prime}R^{2}_{\max}H^{2},\,\,\,\,V(\mathcal{M}_{\mathrm{NMDP}})\geq
C^{H}V^{2}_{\min}.$

By the definition of the density ratio, both $C$ and $C^{\prime}$ are strictly
larger than $1$ when the two policies differ from each other. This implies
that $V(\mathcal{M}_{\mathrm{TMDP}})$ grows polynomially fast w.r.t. $H$ if
$C^{\prime}=O(1)$. To the contrary, $V(\mathcal{M}_{\mathrm{NMDP}})$ grows
exponentially fast w.r.t. $H$.  Notice that $V(\mathcal{M}_{\mathrm{NMDP}})$
is the smallest possible asymptotic MSE that a regular and asymptotically
linear off-policy estimator can achieve in NMDPs, these observations imply
that the exponential dependence on horizon in the estimation error is
unavoidable in general without any further assumption.

Finally, it is worthwhile to note that the efficiency bound under NMDP can be
derived from that under TMDP by embedding NMDPs into TMDPs. More concretely,
given an NMDP, if we set the state $s^{\diamond}_{t}$ to the whole history
$\mathcal{j}_{s_{t}}=(s_{1},a_{1}\cdots,s_{t})$, it becomes a TMDP. The
resulting efficiency bound is given by

$\displaystyle\mathrm{var}_{P_{\pi^{\mathrm{b}}}}[v_{0}(s^{\diamond}_{0})]+\sum_{t=1}^{H}\mathrm{E}_{P_{\pi^{\mathrm{b}}}}\left[\gamma^{t-1}\mu^{2}_{t}(s^{\diamond}_{t},a_{t})\mathrm{var}\left(r_{t}+\gamma
v_{t+1}\mid s^{\diamond}_{t},a_{t}\right)\right].$ (10)

When the state is history-dependent, the density ratio of the marginal state-
action pair is reduced to the cumulative density ratio, i.e.,
$\mu_{t}(s^{\diamond}_{t},a_{t})=\lambda_{t}(\mathcal{j}_{a_{t}})$. As such,
(10) is consistent with the efficiency bound under NMDP displayed in Theorem
3.

Despite that the EIFs and efficiency bounds under the two models share similar
forms, the inputs of the Q-function and density ratio are different. In
particular, both the Q-function and density ratio under NMDP are history-
dependent. As such, the resulting EIF suffers from the curse of horizon,
yielding a large efficient bound.

###  3.4 Efficient Estimators in NMDP

As commented in Section 2, a natural idea to obtain an efficient estimator is
to take an empirical average of the EIF in Theorem 3 with plugging in
estimator for unknown nuisance functions $\lambda_{t},q_{t}$.  Given some
estimators $\hat{\lambda}_{t},\hat{q}_{t}$ for $\lambda_{t},q_{t}$, Jiang and
Li (2016); Thomas and Brunskill (2016) proposed the following estimator:

$\displaystyle\hat{J}^{(H)}_{\mathrm{DR}}=\mathrm{E}_{n}\left[\sum_{t=1}^{H}\left(\gamma^{t}\hat{\lambda}_{t}(\mathcal{j}_{a_{t}})\\{r_{t}-\hat{q}_{t}(\mathcal{j}_{a_{t}})\\}+\gamma^{t-1}\hat{\lambda}_{t-1}\hat{q}_{t}(\mathcal{j}_{s_{t}},\pi^{\mathrm{e}}_{t})\right)\right],$
(11)

which combines DM and IS for robust policy evaluation. When the evaluation
policy is state-agnostic or deterministic, similar estimators have been
proposed by Robins, Rotnitzky and Zhao (1995); Murphy et al. (2001); Zhang et
al. (2013). A split sample version of $\hat{J}^{(H)}_{\mathrm{DR}}$ was
developed by Kallus and Uehara (2020a).

We next discuss the statistical properties of $\hat{J}^{(H)}_{\mathrm{DR}}$
when coupled with data splitting. First, it is doubly robust in the sense that
the estimator is consistent as long as either the model for
$\hat{\lambda}_{t}$ or $\hat{q}_{t}$ is correctly specified. Specifically,
when $\\{\hat{\lambda}_{t}\\}_{t}$ are consistent to $\\{\lambda_{t}\\}_{t}$,
we have

$\displaystyle\hat{J}^{(H)}_{\mathrm{DR}}=\mathbb{E}_{n}\left[\sum_{t=1}^{H}\gamma^{t-1}\hat{\lambda}_{t-1}\hat{q}_{t}(\mathcal{j}_{s_{t}},\pi^{\mathrm{e}}_{t})-\gamma^{t}\hat{\lambda}_{t}\hat{q}_{t}(\mathcal{j}_{a_{t}})\right]+\mathbb{E}_{n}[\sum_{t=1}^{H}\gamma^{t}\hat{\lambda}_{t}r_{t}]\approx\mathbb{E}_{n}[\sum_{t=1}^{H}\gamma^{t}\hat{\lambda}_{t}r_{t}]\stackrel{{\scriptstyle
p}}{{\rightarrow}}J^{(H)}.$

On the other hand, when $\\{\hat{q}_{t}\\}_{t}$ are consistent to
$\\{q_{t}\\}_{t}$, we have

$\displaystyle\hat{J}^{(H)}_{\mathrm{DR}}=\mathrm{E}_{n}[\hat{q}_{1}(s_{1},\pi^{\mathrm{e}}_{1})]+\mathrm{E}_{n}\left[\sum_{t=1}^{H}\gamma^{t}\hat{\lambda}_{t}\\{r_{t}-\hat{q}_{t}(\mathcal{j}_{a_{t}})+\gamma\hat{q}_{t+1}(\mathcal{j}_{s_{t+1}},\pi^{\mathrm{e}}_{t+1})\\}\right]\approx\mathrm{E}_{n}[\hat{q}_{1}(s_{1},\pi^{\mathrm{e}}_{1})]\stackrel{{\scriptstyle
p}}{{\rightarrow}}J^{(H)}.$

Second, $\hat{J}^{(H)}_{\mathrm{DR}}$ is efficient under possibly mild rate
conditions on $\\{\hat{\lambda}_{t}\\}_{t}$ and $\\{\hat{q}_{t}\\}_{t}$.
Specifically, we only require
$\|\hat{\lambda}_{t}-\lambda_{t}\|_{2}=\mathrm{o}_{p}(n^{-1/4})$ and
$\|\hat{q}_{t}-q_{t}\|_{2}=\mathrm{o}_{p}(n^{-1/4})$ for any $1\leq t\leq H$
when coupled with sample splitting. These rates can be satisfied for many
flexible estimators as we will see in Section 5.  Furthermore, as commented in
Section 3.3, even if this estimator is efficient, the asymptotic MSE grows
exponentially fast with respect to $H$.

Many variants of the DR estimator have been proposed in the computer science
and statistics literature, including the self-normalized DR estimator (Thomas
and Brunskill, 2016), the more robust DR estimator (Farajtabar, Chow and
Ghavamzadeh, 2018; Tsiatis, Davidian and Cao, 2011), the TMLE version (Bibaut
et al., 2019), the intrinsically efficient estimator (Kallus and Uehara,
2019b). We remark that all these methods do not exploit the model structure of
TMDPs, i.e., Markovianity. As a result, they _fail_ to be efficient under
TMDP.

###  3.5 Efficient Estimators in TMDP

By taking an empirical average of the EIF in Theorem 4 , Kallus and Uehara
(2020a) proposed the following double reinforcement learning (DRL) estimator
for efficient evaluation under TMDP,

$\hat{J}^{(H)}_{\mathrm{DRL}}=\mathrm{E}_{n}\left[\sum_{t=1}^{H}\gamma^{t}\hat{\mu}_{t}\\{r_{t}-\hat{q}_{t}(s_{t},a_{t})\\}+\gamma^{t-1}\hat{\mu}_{t-1}\hat{q}_{t}(s_{t},\pi^{\mathrm{e}}_{t})\right],$

where $\hat{\mu}_{t}$ and $\hat{q}_{t}$ denote some estimators for $\mu_{t}$
and $q_{t}$, respectively. Similar to $\hat{J}^{(H)}_{\mathrm{DR}}$, this
estimator is consistent when either $\\{\hat{\mu}_{t}\\}_{t}$ or
$\\{\hat{q}_{t}\\}_{t}$ is consistent, and is efficient when these nuisance
function estimators converge at rates $\mathrm{o}_{p}(n^{-1/4})$. It differs
from those estimators outlined in Section 3.4 in that its asymptotic MSE grows
polynomially in $H$ and is thus much more efficient.

When $\hat{q}_{t}=0$ for any $t$, it is reduced to the marginal IS estimator
(Xie, Ma and Wang, 2019; Liu, Bacon and Brunskill, 2020):

$\displaystyle\hat{J}^{(H)}_{\mathrm{MIS}}=\mathrm{E}_{n}\left[\sum_{t=1}^{H}\gamma^{t}\hat{\mu}_{t}r_{t}\right].$

However, it is worth mentioning that this estimator is not generally efficient
even when $\|\hat{\mu}_{t}-\mu_{t}\|_{2}=\mathrm{o}_{p}(n^{-1/4})$.

Computing $\hat{J}^{(H)}_{\mathrm{DRL}}$ requires estimating the marginal
density ratios and Q-functions from the observed data. We will discuss the
estimating procedure of the Q-function in Section 5.1. To estimate the
marginal density ratio, it suffices to estimate $\eta_{t}$ (or $\pi_{t}^{b}$,
equivalently) and $w_{t}$ since
$\mu_{t}(s_{t},a_{t})=\eta_{t}(s_{t},a_{t})w_{t}(s_{t})$. We note that
$\pi_{t}^{b}$ can be estimated using existing supervised learning algorithms.
Kallus and Uehara (2020a) proposed two approaches to estimate $w_{t}(s_{t})$.
To motivate the first method, we notice that

$\displaystyle
w_{t}(s_{t})=\mathbb{E}_{P_{\pi_{b}}}[\lambda_{t-1}(\mathcal{j}_{a_{t-1}})\mid
s_{t}].$

Given some estimators for $\lambda_{t-1}$, estimation of $w_{t}$ can be
formulated into a regression problem. To illustrate the second method, we
observe that

$\displaystyle
w_{t}(s_{t})=\mathbb{E}_{P_{\pi_{b}}}[w_{t-1}(s_{t-1})\eta_{t}(s_{t},a_{t})|s_{t}].$

This allows us to sequentially estimate $w_{t}$ for $t=1,2,\cdots,H$ using
regression.

When parametric models are imposed to learn $w_{t}$ and $\eta_{t}$, one can
easily show that $\hat{\mu}_{t}$ converges at a rate of $O_{p}(n^{-1/2})$
under mild regularity conditions. Finally, we remark when behavior policies
are unknown, we had better use the following estimating equation:

$\displaystyle
0=\mathbb{E}_{P_{\pi_{b}}}[\mu_{t-1}(s_{t-1},a_{t-1})f(s_{t},\pi^{e})-\mu_{t}(s_{t},a_{t})f(s_{t},a_{t})],\forall
f(s,a).$

The above equation can be used to construct a minimax objective function for
estimating $\\{\mu_{t}\\}_{t}$, as discussed in Section 4.4.

##  4 OFF-POLICY EVALUATION ON MDP

This section is concerned with OPE using data generated from a standard Markov
decision process .

Similar to TMDP, observations in MDP satisfy the Markov property. However, it
differs from TMDP in that the system transitions are homogeneous over time. We
remark that most of the existing state-of-the-art RL algorithms rely on this
assumption. It ensures the existence of an optimal stationary (time-
homogeneous & Markov) policy that is no worse than any history-dependent
policies (Puterman, 2014). As such, we focus on evaluating a stationary policy
$\pi^{\mathrm{e}}$ throughout this section.

The rest of this section is organized as follows. We first detail the data
generating process and describe the parameter of interest. We next present the
efficiency bound and the EIF under MDP. Finally, we review various OPE
estimators developed in the literature.

###  4.1 Data Generating Process and Parameter of Interest

An MDP can be viewed as a special case of the TMDP with time-homogeneous
transition functions and infinitely many horizons. Specifically, we have
$p_{S_{t+1},R_{t}}(s_{t+1},r_{t}|s_{t},a_{t})=p(s_{t+1},r_{t}|s_{t},a_{t})$
for some probability mass/density function $p$ and any $t\geq 0$. Unless
otherwise noted, for simplicity, we also assume the behavior policy is
stationary, i.e., $\pi^{\mathrm{b}}_{t}=\pi^{\mathrm{b}}$ for any $t$. It
implies that the density ratio is stationary as well, i.e., $\eta_{t}=\eta$
for any $t$. This assumption can be relaxed. Please see e.g., Liao et al.
(2022) and for further details.

The offline dataset consists of $n$ trajectories, corresponding to $n$ i.i.d.
copies of a data trajectory. Let
$\\{(S_{t}^{(i)},A_{t}^{(i)},R_{t}^{(i)},S_{t+1}^{(i)})\\}_{1\leq t\leq H}$ be
the data collected from the $i$th trajectory where $H$ denotes the number of
decision points in the observed data trajectory. In addition, the stationarity
assumption on the behavior policy does not necessarily imply that
$\\{S_{t}\\}_{t}$ is stationary over time. As such, our discussion is
applicable to settings where the stationary distribution does not exist, which
is certainly the case with a fixed $H$.

The joint distribution of a single data trajectory is given by

$\displaystyle P_{\pi^{b}}=p_{S_{1}}(s_{1})\prod_{t=1}^{H}\pi^{b}(a_{t}\mid
s_{t})p(s_{t+1},r_{t}\mid a_{t},s_{t}).$

The offline dataset can be converted into state-action-reward-next-state
tuples $\\{S^{[i]},A^{[i]},R^{[i]},S^{\prime[i]}\\}_{i=1}^{N}$ where

$\displaystyle S^{[i]}\sim
p_{b}(\cdot),\,\,A^{[i]}\sim\pi^{\mathrm{b}}(\cdot|S^{[i]}),\,\,(R^{[i]},S^{\prime[i]})\sim
p(\cdot,\cdot|A^{[i]},S^{[i]}),$ (12)

where $N=nH$ and $p_{b}$ denotes the marginal distribution of the state in the
observed data. Hereafter, to simplify the theoretical analysis, we assume the
data tuples on the left-hand-side are i.i.d. and denote the density function
on the right-hand-side as $p_{b}(s,a,r,s^{\prime})$. This formulation is
standard in offline RL (Agarwal et al., 2019). For the time-dependent case, we
refer the readers to Bibaut et al. (2021); Shi et al. (2022a), which impose
certain mixing conditions for the DGPs. We use $\mathcal{M}_{\mathrm{MDP}}$ to
denote the nonparametric model specified by the above joint distribution (12)
without imposing any additional assumptions.

The parameter of interest we consider is the expected discounted cumulative
reward, given by

$\displaystyle
J(\gamma)=\mathbb{E}_{P_{\pi^{\mathrm{e}}}}\left[\sum_{t=1}^{+\infty}\gamma^{t-1}r_{t}\right].$
(13)

Throughout this section, we suppose $0\leq\gamma<1$. 555For mathematical and
computational convenience, most existing works in the computer science
literature adopt a discounted reward setting where $\gamma$ is strictly
smaller than $1$. In the statistics literature, there are some recent works
that study OPE under the average reward setting where $\gamma=1$ (see e.g.,
Liao, Klasnja and Murphy, 2021; Liao et al., 2022). RL in these settings
involves several technical subtleties arise. For instance, the Q-functions
need to be defined by subtracting the policy value at each time step to ensure
its finiteness. Please refer to Liao et al. (2022) for more details.  The
quantity $J(\gamma)$ can be interpreted as the evaluation of a functional
defined by $\pi^{\mathrm{e}}(a\mid s),p(s^{\prime},r\mid s,a)$ and
$p_{e}^{(1)}(s)$, where $p_{e}^{(1)}(\cdot)$ is an initial state distribution
for the target estimand. For simplicity, we assume $p_{e}^{(1)}(\cdot)$ is
pre-specified. When $p_{e}^{(1)}(\cdot)$ is unknown, we can plug in the
empirical distribution from the data $\\{S^{[i]}_{1}\\}_{i=1}^{N^{\prime}}\sim
p_{e}^{(1)}(\cdot)$.

As we will see below, there exist consistent OPE estimators even when the data
consist of a single trajectory, i.e., $n=1$. This is different from the
findings in Section 3 where consistent estimation in NMDPs or TMDPs requires
$n$ to diverge to infinity. Such a phenomenon is due to the time-homogeneity
assumption under MDP, which enables consistent estimation even with a limited
number of trajectories.

To conclude this section, we introduce the Q-function, the value function and
the marginal density ratio under MDP. The Q-function associated with $\pi^{e}$
is defined as the expected discounted cumulative reward under $\pi^{e}$
conditional on a given initial state-action pair. Specifically, we have

$\displaystyle
q(s,a)=\mathbb{E}_{P_{\pi_{e}}}\left[\sum_{t=1}^{\infty}\gamma^{t-1}r_{t}|s_{1}=s,a_{1}=a\right].$

The value function under $\pi^{e}$ is given by
$v(s)=q(s,\pi^{\mathrm{e}})=\int\pi^{\mathrm{e}}(a|s)q(s,a)\mathrm{d}a$.
Finally, we define the marginal density ratio

$\displaystyle\mu^{*}(s,a)=\frac{p^{(\infty)}_{e,\gamma}(s)\pi^{\mathrm{e}}(a\mid
s)}{{p_{b}(s)\pi^{\mathrm{b}}(a\mid s)}},$

where $p^{(\infty)}_{e,\gamma}$ is the $\gamma$-discounted average state
visitation distribution under $\pi^{\mathrm{e}}$, i.e.,
$p^{(\infty)}_{e,\gamma}(s)=(1-\gamma)\sum_{t\geq
1}\gamma^{t-1}p_{e}^{(t)}(s)$ where $p_{e}^{(t)}$ denotes the probability
mass/density function of $S_{t}$, assuming that the system follows $\pi^{e}$
and $S_{1}$ follows $p_{e}^{(1)}$. Here, we implicitly assume that the support
of $p^{(\infty)}_{e,\gamma}(s)\pi^{\mathrm{e}}(a\mid s)$ is included in the
support of $p_{b}(s)\pi^{\mathrm{b}}(a\mid s)$. This is a weak positivity
assumption in MDP. We also define
$w^{*}(s)=p^{(\infty)}_{e,\gamma}(s)/p_{b}(s)$ as the marginal density ratio
of the state.

###  4.2 Efficiency Bound and EIF

When $p_{e}^{(1)}$ is pre-specified 666When $p_{e}^{(1)}$ is not pre-
specified, the efficiency bound will have an additional variance term that is
proportional to $\mathrm{var}_{p^{(1)}_{e}}[v(s)]$. In addition, if we set
$\gamma=0$, then the results are reduced to those in Theorem 2.  , Kallus and
Uehara (2019a) derived the efficiency bound of $J(\gamma)$ w.r.t. a
nonparametric model $\mathcal{M}_{\mathrm{MDP}}$ and established the
corresponding EIF. We summarize their results in the following theorem.

######  Theorem 5.

Letting $v(s^{\prime})=q(s^{\prime},\pi^{\mathrm{e}})$, the EIF of $J(\gamma)$
w.r.t. $\mathcal{M}_{\mathrm{MDP}}$ is

$\displaystyle\phi_{\mathrm{MDP}}(s,a,r,s^{\prime};\mu^{*},q)=-J(\gamma)+\mathbb{E}_{s\sim
p_{e}^{(1)}}[q(s,\pi^{\mathrm{e}})]+(1-\gamma)^{-1}\mu^{*}(s,a)\\{r+\gamma
v(s^{\prime})-q(s,a)\\},$ (14)

and the efficiency bound $V(\mathcal{M}_{\mathrm{MDP}})$ is

$\displaystyle
V(\mathcal{M}_{\mathrm{MDP}})=(1-\gamma)^{-2}\mathbb{E}_{p_{b}}[\mu^{*}(s,a)^{2}\mathrm{var}[r+\gamma
v(s^{\prime})|s,a]].$

Theorem 5 implies that the lower bound of asymptotic MSE among all regular
estimators is $V(\mathcal{M}_{\mathrm{MDP}})/N$. Compared to the lower bound
$V(\mathcal{M}_{\mathrm{TMDP}})/n$ in the TMDP, this rate is faster by a
factor of $H=N/n$, which is the benefit we get by taking the time-homogeneity
property into consideration.

Interestingly, Theorem 5 enables us to recover the efficiency bound in TMDPs.
Notice that TMDPs can be embedded into MDPs by augmenting the state space with
a time index $t$. Let $\tilde{s}=(s,t)$ denote the augmented state. It follows
that $p_{b}(\tilde{s},a)=H^{-1}p_{\pi^{b}_{t}}(s,a)$ and
$p^{(\infty)}_{e,\gamma}(\tilde{s},a)=(1-\gamma)\gamma^{t-1}p^{(t)}_{e}(s)$.
When the initial state distribution under $\pi^{\mathrm{e}}$ is pre-specified,
the variance term $\mathrm{var}_{P_{\pi^{b}}}[v_{0}(s_{0})]$ does not appear
in the efficiency bound and the resulting efficiency bound under this MDP is
consistent with that in TMDPs. In addition, due to the inclusion of the time
index in the state, the variance of EIF under this MDP is larger than that
under a stationary MDP.

We also remark that Theorem 5 considers a discounted reward setting. In the
literature, Liao et al. (2022) derived the efficiency bound for the average-
reward setting where $\gamma=1$, and Bibaut et al. (2021) derived the
efficiency bound under settings where each unit is not independent.

###  4.3 Model-Free Estimators

We introduce three different types of OPE estimators in this section,
corresponding to the DM estimator, the marginal IS estimator and the doubly-
robust estimator. All these estimators are model-free in the sense that they
are derived without estimating the system transition function
$p(s^{\prime},r\mid s,a)$. In addition, the estimators introduced in Section 3
can be potentially applied to estimating $J(\gamma)$.  However, as commented
before, these estimators are not efficient as they do not take the additional
structure into consideration. They require the number of trajectories $n$ to
approach infinity to be consistent and converge slower than those estimators
we will introduce below.

First, we introduce the double reinforcement learning (DRL) estimator
developed by Kallus and Uehara (2019a),

$\hat{J}_{\mathrm{DRL}}=\mathbb{E}_{s\sim
p_{e}^{(1)}}[\hat{q}(s,\pi^{\mathrm{e}})]+\mathbb{E}_{N}[(1-\gamma)^{-1}\hat{\mu}^{*}(s,a)\\{r+\gamma\hat{q}(s^{\prime},\pi^{e})-\hat{q}(s,a)\\}],$

where the expectation $\mathbb{E}_{N}$ is taken with respect to the empirical
measure $N^{-1}\sum_{i}\delta_{(S^{[i]},A^{[i]},S^{{}^{\prime}[i]},R^{[i]})}$.
This DRL estimator is obtained by plugging in certain estimators
$\hat{\mu}^{*},\hat{q}$ for $\mu^{*},q$ in (14). We discuss how to construct
these estimators in Section 4.4.

Second, we introduce the marginal IS (MIS) and DM estimators. Both estimators
can be recovered by DRL with certain choice of nuisance functions. For
instance, when set $\hat{q}=0$, DRL is reduced to the MIS estimator proposed
by Liu et al. (2018),

$\displaystyle\hat{J}_{\text{MIS}}=(1-\gamma)^{-1}\mathbb{E}_{N}[\hat{\mu}^{*}(s,a)r].$

On the other hand, DRL is reduced to the DM estimator when $\hat{\mu}^{*}=0$.

$\hat{J}_{\text{DM}}=\mathbb{E}_{s\sim
p_{e}^{(1)}}[\hat{q}(s,\pi^{\mathrm{e}})].$

As we have mentioned in Section 2, the DM estimator is more robust to the
insufficient coverage of offline data when compared to MIS. More specifically,
when we use linear models to parametrize the Q-function, i.e.,
$q(s,a)=\langle\theta,\phi(s,a)\rangle$, the DM estimator only requires
$\sup_{x}x^{\top}\mathbb{E}_{p^{(\infty)}_{e,\gamma}}[\phi(s,a)\phi(s,a)^{\top}]x/x^{\top}\mathbb{E}_{p_{b}(s,a)}[\phi(s,a)\phi(s,a)^{\top}]x<\infty$,
which is weaker than the coverage assumption
$\|\mu^{\star}(\cdot)\|_{\infty}<\infty$ required by MIS. In addition, it
remains very challenging to consistently estimate the marginal density ratio
$\mu^{*}$. Notice that in contrast to the bandit setting, $\mu^{*}$ remains
unknown even if the behavior policy is known.

Third, when coupled with sample splitting, DRL is semiparametrically efficient
when both $\hat{\mu}^{*}$ and $\hat{q}$ converge at a rate of
$o_{p}(N^{-1/4})$. We also remark that when $\hat{q}$ is parametrized via
certain nonparametric estimators such as reproducing kernel Hilbert spaces
(RKHSs, Steinwart and Christmann, 2008) or linear sieves, the resulting DM
estimator is able to achieve the efficiency bound as well. See Theorem 2 of
Liao, Klasnja and Murphy (2021) and Appendix E.2.1 of Shi et al. (2022b),
respectively. Similarly, when linear sieves are used to parametrize $\mu^{*}$,
the resulting MIS estimator is semiparametrically efficient as well since it
equals DRL with both nuisance functions parametrized via linear sieves
(Uehara, Huang and Jiang, 2020). Nonetheless, different from DRL, all these
efficient estimators are nuisance-function-dependent.

Fourth, DRL estimator is doubly robust in that it is consistent when either
$\hat{\mu}^{*}$ or $\hat{q}$ is consistent. The doubly robust property is
confirmed as follows. When $\hat{q}$ is consistent to $q$, we have

$\displaystyle\hat{J}_{\mathrm{DRL}}\approx\mathbb{E}_{s\sim
p_{e}^{(1)}}[\hat{q}(s,\pi^{\mathrm{e}})]\stackrel{{\scriptstyle
p}}{{\rightarrow}}J(\gamma).$

When $\hat{\mu}^{\star}$ is consistent to $\mu$, we have

$\displaystyle\hat{J}_{\mathrm{DRL}}\approx(1-\gamma)^{-1}\mathbb{E}_{N}[\hat{\mu}^{*}(s,a)r]\stackrel{{\scriptstyle
p}}{{\rightarrow}}J(\gamma).$

Finally, it is worthwhile to mention two closely related estimators. First,
Tang et al. (2020) developed another doubly-robust estimator that breaks the
curse of horizon. When the behavior policy is known, the estimator requires
either the marginal state density ratio $w^{*}$ (see the definition in Section
4.4.2) or the state value function to be correctly specified. However, its
asymptotic variance is larger than DRL; hence, it is generally not efficient
(Kallus and Uehara, 2020b). Secondly, Shi et al. (2021b) developed a deeply-
debiased estimator for confidence interval construction and uncertainty
quantification. It shares similar spirits to the minimax optimal estimating
procedure that uses higher-order influence functions to learn the average
treatment effect in contextual bandits (see e.g., Mukherjee, Newey and Robins,
2017). Debiasing brings additional flexibility in that it allows the nuisance
functions to diverge at an arbitrary rate.

###  4.4 Estimation of Q-functions $q(s,a)$ and Marginal Ratios
$\mu^{\star}(s,a)$

####  4.4.1 Estimation of Q-functions $q(s,a)$

The first method is fitted Q-iteration (FQE, Ernst, Geurts and Wehenkel, 2005;
Munos and Szepesvári, 2008; Fan et al., 2020). This is essentially a value
iteration method that allows for flexible functional approximation. It
recursively updates the Q-estimator based on the Bellman equation

$\displaystyle\mathbb{E}_{(s^{\prime},r)\sim p(\cdot|s,a)}[r+\gamma
q(s^{\prime},\pi_{e})\mid s,a]=q(s,a),$ (15)

for any $(a,s)$. More specifically, at the $k$th iteration, it updates
$\hat{q}$ by solving

$\displaystyle\hat{q}_{(k+1)}\leftarrow\operatorname*{arg\,min}_{\tilde{q}\in\mathcal{Q}}\mathbb{E}_{N}[\\{r-\tilde{q}(s,a)+\gamma\hat{q}_{(k)}(s^{\prime},\pi^{\mathrm{e}})\\}^{2}],$

where $\mathcal{Q}$ denotes some flexible function class such as deep neural
networks or RKHSs. During each iteration, the above optimization can be cast
into a supervised learning problem with
$\\{R^{[i]}+\gamma\hat{q}_{(k)}(S^{{}^{\prime}[i]},\pi^{\mathrm{e}})\\}_{i}$
as the responses, and $\\{(A^{[i]},S^{[i]})\\}_{i}$ as the predictors.

The second method is minimax Q-learning (Uehara, Huang and Jiang, 2020). The
following observation forms the basis of the method: based on the Bellman
equation (15), we have for any discriminator function $f$ that

$\displaystyle\mathbb{E}_{p_{b}}[f(s,a)\\{r+\gamma
q(s^{\prime},\pi^{\mathrm{e}})-q(s,a)\\}]=0.$ (16)

As such, the Q-estimator can be computed by solving the following minimax
problem,

$\displaystyle\operatorname*{arg\,min}_{\tilde{q}\in\mathcal{Q}}\max_{f\in\mathcal{F}}\mathbb{E}_{N}[f(s,a)\\{r+\gamma\tilde{q}(s^{\prime},\pi^{\mathrm{e}})-\tilde{q}(s,a)\\}]-\lambda\mathbb{E}_{N}[f^{2}(s,a)],\,$
(17)

for some tuning parameter $\lambda\geq 0$ and function classes $\mathcal{Q}$,
$\mathcal{F}$. In view of (16), the discriminator class $\mathcal{F}$ is
introduced to measure the discrepancy between $q$ and $\tilde{q}$. When
$\lambda>0$, the objective function in (17) corresponds to the modified
Bellman residual minimization loss (BRM, Antos, Szepesvári and Munos, 2008;
Farahm et al., 2016; Liao et al., 2022). The above minimax optimization is
difficult to solve in general. To simplify the calculation, we can set
$\mathcal{F}$ to a ball of an RKHS, with which the inner maximization has a
closed-form solution, and then $\hat{q}$ can be learned by solving the outer
minimization via stochastic gradient descent (Liu et al., 2018). Similar to
FQE, we can take $\mathcal{Q}$ to be a rich function class (e.g., neural
networks). Alternatively, we can set both $\mathcal{Q}$ and $\mathcal{F}$ to
linear models, with which the q-estimator has a closed-form solution. In that
case, interestingly, the resulting DM estimator $\hat{J}_{\text{DM}}$ is
reduced to LSTDQ (short for Least-Squares Temporal-Difference learning for
Q-functions, see e.g., Lagoudakis and Parr, 2004, for details).

Next, we compare minimax Q-learning against FQE. First, from a theoretical
point of view, the Bellman closedness assumption required by FQE does not
satisfy the monotonic property. In other words,
$\mathcal{B}\mathcal{Q}\subset\mathcal{Q}$ holds does not necessarily imply
$\mathcal{B}\widetilde{\mathcal{Q}}\subset\widetilde{\mathcal{Q}}$ for any
$\mathcal{Q}\subset\widetilde{\mathcal{Q}}$ where $\mathcal{B}$ is a Bellman
operator that satisfies
$\mathcal{B}\tilde{q}(\cdot)\coloneqq\mathbb{E}_{p(s^{\prime},r|\cdot)}[r+\gamma\tilde{q}(s^{\prime},\pi^{\mathrm{e}})|\cdot]$
for any $\tilde{q}$. On the contrary, the Bellman closedness assumption
required by minimax Q-learning satisfies this property. See Section 5.1 for
details. Second, from an optimization point of view, minimax Q-learning (which
relies on minimax optimization) is much more challenging to implement compared
to FQE. Finally, it is generally difficult to select hyperparameters in both
minimax Q-learning and FQE. In contrast to supervised learning, there does not
exist a natural cross-validation criterion in Q-function estimation.
Specifically, whereas FQE is built upon supervised learning, the iterative use
of it makes cross-validation non-trivial 777 Recently, this problem has been
partially addressed by Miyaguchi (2022). . In minimax Q-learning, the minimax
objective function makes cross-validation very difficult to implement.

Finally, another closely related topic is the estimation of the state-value
function $v(s)$. Feng, Li and Liu (2019) proposed a minimax learning method to
learn $v$. They compute the value estimator by solving a minimax objective
function, based on the Bellman equation for the state-value function,

$\displaystyle\mathbb{E}_{p_{b}}[f(s)\eta(s,a)\\{r+\gamma
v(s^{\prime},\pi^{\mathrm{e}})-v(s)\\}]=0,$

for a certain class of discriminator functions $f\in\mathcal{F}$. In cases
where linear models are imposed to model $v$, the resulting method is reduced
to those discussed in Bertsekas and Yu (2009); Ueno et al. (2011); Dann,
Neumann and Peters (2014); Luckett et al. (2020).

####  4.4.2 Estimation of Marginal Ratios $\mu^{*}(s,a)$

We next discuss how to estimate $\mu^{*}(s,a)$.

Uehara, Huang and Jiang (2020) proposed a minimax weight-learning to estimate
$\mu^{*}$ without imposing the stationarity assumption. The method is based on
the following identity:

$\displaystyle
0=\mathbb{E}_{p_{b}}[\gamma\mu^{*}(s,a)f(s^{\prime},\pi^{\mathrm{e}})-\mu^{*}(s,a)f(s,a)]+(1-\gamma)\mathbb{E}_{p^{(1)}_{e}}[f(s,\pi^{\mathrm{e}})],\,\forall
f(s,a).$ (18)

Notice that this equation is agnostic to the behavior policy. Then, given
certain rich function classes $\mathcal{M}$ and $\mathcal{F}$, the minimax
estimator is defined by

$\displaystyle\textstyle\operatorname*{arg\,min}_{\tilde{\mu}^{*}\in\mathcal{M}}\max_{f\in\mathcal{F}}$
$\displaystyle\mathbb{E}_{N}[\gamma\tilde{\mu}^{*}(s,a)f(s^{\prime},\pi^{\mathrm{e}})-\tilde{\mu}^{*}(s,a)f(s,a)]+(1-\gamma)\mathbb{E}_{p^{(1)}_{e}}[f(s,\pi^{\mathrm{e}})]-\lambda\mathbb{E}_{N}[f(s,a)^{2}],\,$

for some tuning parameter $\lambda\geq 0$. Interestingly, when we set both
$\mathcal{M}$ and $\mathcal{F}$ to linear models, the resulting marginal IS
estimator $J_{\text{MIS}}$ is reduced to LSTDQ.

It is worthwhile to add two remarks. First, recalling
$\mu^{*}(s,a)=w^{*}(s)\pi^{\mathrm{e}}(a\mid s)/\pi^{\mathrm{b}}(a\mid s)$,
when we know $\pi^{\mathrm{b}}(a\mid s)$, it suffices to estimate $w^{*}$. Liu
et al. (2018) 888Notice that (19) is slightly different from the original
proposal in Liu et al. (2018, Lemma 3) since they take the expectation with
respect to the discounted occupancy distribution $p_{b,\gamma}(s)$. Later, the
modified version (19) is discussed in Kallus and Uehara (2019a, Lemma 16).
propose the following estimating equation:

$\displaystyle 0=\mathbb{E}_{p_{b}}[\gamma
w^{*}(s)\eta(s,a)f(s^{\prime})-w^{*}(s)f(s)]+(1-\gamma)\mathbb{E}_{p^{(1)}_{e}}[f(s)],\,\forall
f(s),$ (19)

where $\eta(s,a)=\pi^{\mathrm{e}}(a\mid s)/\pi^{\mathrm{b}}(a\mid s)$. Second,
several related minimax estimators have been proposed from a duality viewpoint
(Yang et al., 2020; Nachum and Dai, 2020; Dai et al., 2020). More
specifically, they cast an OPE problem into a linear programming problem.
Then, the objective function of minimax estimators is derived from the
corresponding Lagrange function.

###  4.5 Model-Based Estimators

So far we have discussed the model-free method. In this section, we focus on
the class of model-based estimators. A typical model-based estimator estimates
the transition density and reward density functions from the data and plugs in
these estimators in (13) to construct the value estimator. Note this estimator
is also known as g-formula in the literature on causal inference (Hernan and
Robins, 2019). When probabilistic neural networks are used to model the
transition function, the resulting model-based estimator has shown good
empirical performance in challenging continuous control domains (Zhang et al.,
2021).

Statistical properties of model-based estimators have been recently
established in the computer science literature. Yin and Wang (2020) proved
that the model-based estimator in discrete MDPs is asymptotically efficient.
This result extends the findings of Hahn (1998) to sequential decision making.
In continuous domains, Uehara and Sun (2021) studied model-based estimators
with maximum likelihood parameter estimation of transition density.

To conclude this section, we discuss the advantages and disadvantages of these
model-based estimators when compared against model-free estimators. On one
hand, hyperparameter selection is much easier in model-based methods since
existing state-of-the-art supervised learning algorithms are applicable to
learn the state transition and reward functions, and cross-validation can be
potentially employed for parameter tuning. On the contrary, as commented in
Section 4.4, hyperparameter tuning is more delicate in model-free methods. On
other hand, in settings with high-dimensional state information, model-based
estimators might not be preferable since it is more challenging to model the
state transition function than to model the value function.

###  4.6 OPE and Nonparametric Instrumental Variable Estimation

According to (15), Q-functions are characterized as solutions to certain
conditional moment equations. As such, Q-function estimation (and the
subsequent policy evaluation) can be cast into nonparametric instrumental
variable estimation, which has long been studied in statistics and
econometrics (see e.g., Chamberlain, 1992; Ai and Chen, 2003, 2012; Newey,
2013; Dikkala et al., 2020). This connection has been widely recognized among
RL researchers (Kallus and Uehara, 2019a; Chen and Qi, 2022; Zhang et al.,
2022).

In the rest of this section, we highlight two key features of OPE. First,
while Q-function estimation can be formulated into instrumental variable
estimation, the Bellman equation (15) has a unique structure where the
Q-function appears on both the left-hand-side and right-hand-side of the
estimating equation with different inputs. This special structure gives
license to use sequential regression, i.e., FQE for Q-function estimation.
However, to our knowledge, sequential regression has not been applied to
solving standard conditional moment equations. Second, in OPE, the ultimate
goal is to estimate the target policy’s value. There exist consistent OPE
estimators such as $\hat{J}_{\mathrm{MIS}}$ that can be constructed without
Q-function estimation.

##  5 OPE Theory

In Section 4, we mainly discuss the efficiency, assuming that we obtain
convergence rates of Q-functions and marginal ratios. In this section, we
mainly explain the convergence properties of these two functions and the
special characteristics of OPE problems. In this section, for simplicity,
while we focus on MDPs, every discussion is easily applicable to TMDPs.

###  5.1 Convergence Rates of Q-functions

We discuss the statistical properties of Q-functions. To establish the rate of
convergence properties of the aforementioned algorithms, we often require the
realizability and completeness assumptions. Both assumptions are commonly
imposed in the computer science literature (see e.g., Munos and Szepesvári,
2008; Chen and Jiang, 2019). The realizability assumption essentially requires
$q\in\mathcal{Q}$. In other words, the function class $\mathcal{Q}$ shall be
rich enough to contain $q$. The completeness assumption requires $\mathcal{Q}$
to be closed under the Bellman operator. For FQE, the completeness assumption
requires $\mathcal{B}\mathcal{Q}\subset\mathcal{Q}$ (recall that $\mathcal{B}$
is the Bellman operator). It is satisfied when the transition density $p$ is a
smooth function and $\mathcal{Q}$ contains the class of smooth functions
(Munos and Szepesvári, 2008; Fan et al., 2020). Compared to the realizability,
this $\mathcal{B}\mathcal{Q}\subset\mathcal{Q}$ does not have a monotonic
property in that the larger $\mathcal{Q}$ does not result in the weaker
assumption. For minimax Q-learning, the completeness assumption requires
$\mathcal{B}\mathcal{Q}\subset\mathcal{F}$. Similarly, with a smooth
transition density function, it holds when $\mathcal{F}$ contains the class of
smooth functions. Compared to $\mathcal{B}\mathcal{Q}\subset\mathcal{Q}$, this
$\mathcal{B}\mathcal{Q}\subset\mathcal{F}$ has a certain monotonic property in
that the larger $\mathcal{F}$ result in the weaker assumption.

Under these conditions $q\in\mathcal{Q}$ and Bellman completeness
($\mathcal{B}\mathcal{Q}\subset\mathcal{Q}$ in FQE and
$\mathcal{B}\mathcal{Q}\subset\mathcal{F}$ in minimax Q-learning), we can
derive the rate of convergence of the Bellman residual error
$\\{\mathbb{E}_{p_{b}}[\\{\mathcal{B}\hat{q}-\hat{q}\\}^{2}]\\}^{1/2}$ as a
function of the critical radii of the function class (Uehara et al., 2021;
Duan, Jin and Li, 2021). For example, when we use parametric models with
finite VC dimensions for $\mathcal{Q}$ and $\mathcal{F}$, the rate of
convergence is $O_{p}(N^{-1/2})$. When we use Hölder classes with an input
dimension $d$ and the smoothness parameter $\alpha$, the rate is
$O_{p}(N^{-\alpha/(2\alpha+d)})$. These results can be directly translated
into an error bound for $|\hat{J}_{\text{DM}}-J|$ using

$|\hat{J}_{\text{DM}}-J|\leq\\{\mathbb{E}_{p_{b}}[\mu^{\star}(s,a)^{2}]\\}^{1/2}\mathbb{E}_{p_{b}}[\\{\mathcal{B}\hat{q}-\hat{q}\\}^{2}(s,a)]\\}^{1/2}.$

For the derivation, please refer to Uehara et al. (2021). Finally, we remark
that Bellman residual errors can be further translated into $\ell_{2}$-errors
$\\{\mathbb{E}_{p_{b}}[(\hat{q}-q)^{2}(s,a)]\\}^{1/2}$ under certain mild
conditions (Chen and Qi, 2022). Furthermore, Huang and Jiang (2022) discuss
how to directly obtain $\\{\mathbb{E}_{p_{b}}[(\hat{q}-q)^{2}(s,a)]\\}^{1/2}$
under the realizability $q\in\mathcal{Q}$ and $q^{\prime}\in\mathcal{W}$ where
$q^{\prime}$ is a certain function without going through Bellman residual
errors.

###  5.2 Convergence Rates of Marginal Ratios $\mu^{*}(s,a)$

Finally, we discuss the statistical properties of the marginal IS estimator.
We need the realizability condition $\mu^{*}\in\mathcal{M}$ and the
completeness condition $\mathcal{B}^{\prime}\mathcal{M}\subset\mathcal{F}$
where $\mathcal{B}^{\prime}$ denotes the adjoint Bellman operator (see Uehara
et al., 2021, for the detailed definition). Similar to the Bellman operator
$\mathcal{B}$ that satisfies $\mathcal{B}q=q$, $\mathcal{B}^{\prime}$
satisfies the identity that $\mathcal{B}^{\prime}\mu^{*}=\mu^{*}$ and can be
understood as the analog of $\mathcal{B}$ for describing the marginal density
ratio. Under these conditions, we can characterize the Bellman residual error
$\\{\mathbb{E}_{p_{b}}[\\{\mathcal{B}^{\prime}\hat{\mu}^{*}-\hat{\mu}^{*}\\}^{2}]\\}^{1/2}$
using the critical radii of the function class. For instance, when we use
parametric models with finite VC dimensions for $\mathcal{M}$ and
$\mathcal{F}$, the Bellman residual error decays to zero at a rate of
$O_{p}(N^{-1/2})$. When we use Hölder classes with an input dimension $d$ and
the smoothness parameter $\alpha$, the rate is
$O_{p}(N^{-\alpha/(2\alpha+d)})$. Similarly, these results can be directly
translated into an error bound for $|\hat{J}_{\text{MIS}}-J|$. Please refer to
Uehara et al. (2021) for details. Furthermore, Huang and Jiang (2022) discuss
how to directly obtain
$\\{\mathbb{E}_{p_{b}}[(\hat{\mu}^{\star}-\mu^{\star})^{2}(s,a)]\\}^{1/2}$
under the realizability $\mu^{\star}\in\mathcal{M}$ and
${\mu^{\prime}}^{\star}\in\mathcal{F}$ where
${\mu^{\prime}}^{\star}\in\mathcal{F}$ is a certain function without going
through Bellman residual errors.

###  5.3 Do We Really Need Bellman Completeness?

We discuss the role of the completeness assumption in this section. Several
papers (see e.g., Du et al., 2019; Foster et al., 2021) proved that the
realizability condition alone is insufficient to obtain a non-asymptotic error
bound that is polynomial in the number of horizon in a variety of contexts.
These results suggest that some other conditions are needed in addition to the
realizability of Q-functions.

One example of these assumptions is given by the Bellman completeness
condition introduced in Section 5.1. Alternatively, we can impose certain
matrix invertibility conditions when specialized to linear models (Perdomo et
al., 2022). These conditions have also been introduced in the statistics
literature (see e.g., Ertefaie and Strawderman, 2018; Shi et al., 2022a) to
study the rate of convergence and asymptotic normality of the Q-function
estimator. However, it remains unclear how to extend this condition to general
function approximation that permits the use of deep neural networks and random
forests. Finally, Uehara et al. (2021) obtained a favorable non-asymptotic
result that allows general function approximation by assuming the
realizability of the marginal density ratios. Notably, they proved the
convergence of the policy value without the convergence of nuisance function
estimators.

##  6 Recent progress and Discussion

In this section, we present an overview of some other related research
directions that are currently being actively explored.

###  6.1 Non-asymptotic Lower bounds

In this paper, we present the efficiency bound (e.g., the best-possible
asymptotic MSE) for OPE under various DGPs. In the RL community, researchers
are particularly interested in non-asymptotic results. The non-asymptotic
minimax (or locally minimax) lower bounds characterize the best-possible
nonasymptotic MSE as a function of the sample size, the horizon as well as
some other quantities of interest. These non-asymptotic lower bounds for OPE
have been recently established under some specific settings (Duan, Jia and
Wang, 2020; Yin, Bai and Wang, 2021; Wang, Foster and Kakade, 2020; Pananjady
and Wainwright, 2021; Hao et al., 2021; Mou et al., 2021; Mou, Wainwright and
Bartlett, 2022).

###  6.2 Unmeasured confounding

In observational data, the sequential ignorability assumption could be
violated in some applications (see e.g., Namkoong et al., 2020). In that case,
the policy value is not identified without additional assumptions. To address
this problem, several approaches have been developed in the literature. The
first line of research proposes to develop partial identification bounds for
the policy value based on a sensitivity model (Kallus and Zhou, 2020; Namkoong
et al., 2020; Zhang and Bareinboim, 2021). These papers are inspired by works
in the causal inference literature on sensitivity analysis (Manski, 1995;
Rosenbaum, 2002). The second line of research focuses on the confounded MDP
model (Zhang and Bareinboim, 2016) under which the Markov assumption is
satisfied and relies on certain proxy variables for consistent OPE (see e.g.,
Bennett et al., 2021; Fu et al., 2022; Shi et al., 2022c). The third line of
research uses partially observable environments to formulate the OPE problem
under unmeasured confounding. For instance, in the discrete state-action space
setting, Tennenholtz, Shalit and Mannor (2020) uses an idea of negative
controls (Miao, Geng and Tchetgen Tchetgen, 2018) and establishes the point
identification strategy. Later, these results are extended to the continuous
state-action space setting (Bennett and Kallus, 2021; Miao, Qi and Zhang,
2022; Shi et al., 2022d).  However, they all rely on certain assumptions that
might be difficult to validate in practice. For instance, to derive the
partial identification bound, Namkoong et al. (2020) assumed that there is
only a single step of confounding at a known time step to sharpen the partial
identification bound. Tennenholtz, Shalit and Mannor (2020) imposed certain
matrix invertibility assumptions to guarantee the identifiability of the
policy value from the observed data.

###  6.3 Partially Observable MDPs

In partially observable MDPs (POMDPs), agents only have access to noisy
observations instead of the underlying states. Compared to MDPs, POMDPs are
more general. In addition, POMDPs might fit real datasets better than MDPs
since the Markovian assumption are often questionable in practice. Since
POMDPs are NMDPs, we can employ any off-the-shelf OPE methods for NMDPs
(Futoma, Hughes and Doshi-Velez, 2020; Hu and Wager, 2021). However, these
methods suffer from the curse of horizon and cannot consistently learn the
policy value from a single trajectory. To alleviate these issues, by fully
leveraging structures of POMDPs, Uehara et al. (2022) recently proposed a
model-free OPE method in POMDPs. However, it remains unclear whether there are
model-based methods that can circumvent the curse of horizon and learn from a
single trajectory.

###  6.4 Offline policy optimization

In offline policy optimization, we aim to identify an optimal policy based on
the observed data to maximize the expected return. A simple idea would be to
first construct some OPE estimator $\hat{J}(\pi)$ for any policy $\pi$ that
belongs to a policy class $\Pi$, and then compute the optimal policy by
$\hat{\pi}=\operatorname*{arg\,max}_{\pi\in\Pi}\hat{J}(\pi)$. Such an idea has
been adopted in the contextual bandit setting for offline policy optimization
(Zhang et al., 2012; Zhao et al., 2012b; Swaminathan and Joachims, 2015a, b;
Athey and Wager, 2017; Kitagawa and Tetenov, 2018). However, it is challenging
to extend these methods to the long horizon or infinite horizon settings in
RL. First, the nuisance functions such as the Q-function and the marginal
density ratio involved in the OPE estimator are policy-dependent. It remains
unknown how to learn the set of nuisance functions over a given policy class
in a computationally efficient manner. Second, a crucial challenge of applying
such a method lies in the existence of out-of-distribution actions due to the
mismatch between the behavior policy and the target policy. It results in
overestimation of the value evaluated at these out-of-distribution actions,
therefore worsening the performance of policy learning. To address this
limitation, we can employ the pessimism principle to prevent overestimation
and restrict the learned policies to stay close to the behavior policy
(Swaminathan and Joachims, 2015a, b; Yu et al., 2020; Kidambi et al., 2020).
Such a principle has been recently investigated from a theoretical perspective
(Jin, Yang and Wang, 2020; Rashidinejad et al., 2021; Uehara and Sun, 2021;
Xie et al., 2021).

###  6.5 General policies

So far we have focused on the setting where the evaluation policy is known to
us. There are applications where the evaluation policy is a deterministic
function of behavior policy, such as the tilting policy or the modified
treatment policy (Díaz, 2019; Young, Hernán and Robins, 2014). Since the
behavior policy is unknown, so is the evaluation policy. The resulting
efficiency bound for OPE and the EIF are different from what we have discussed
in the main text (Kennedy, 2019; Kallus and Uehara, 2020b).

In addition, as we have discussed in the main text, some extra care is needed
when the action space is continuous and the evaluation policy is
deterministic. In that case, the causal estimand is no longer pathwise
differentiable and $\sqrt{n}$-consistent estimation does not exist (Bibaut and
J. van der Laan, 2017; Kennedy et al., 2017). By imposing certain smoothness
conditions over the action space, the policy value can still be consistently
estimated if we replace the indicator function in the estimating function with
kernels (Kallus and Uehara, 2020c). However, such a method might suffer from
the curse of dimensionality and perform poorly in high-dimensional action
space.

###  6.6 General causal graphs

NMDP and TMDP are special cases of causal directed acyclic graphs (DAGs). For
general causal graphs, under the no unmeasured confounders assumption, it is
well-known that the policy value is identifiable and that the EIF exists (van
Der Laan and Robins, 2003; Rotnitzky and Smucler, 2020). When there are
unmeasured variables, although a general identification condition exists (Tian
and Pearl, 2002; Shpitser and Pearl, 2006), the estimating procedure is less
explored. In some special cases, several estimators have been proposed and are
proven to achieve efficiency bound (Fulcher et al., 2020; Bhattacharya, Nabi
and Shpitser, 2020; Jung, Tian and Bareinboim, 2020; Smucler, Sapienza and
Rotnitzky, 2022). However, it remains unknown whether nonparametrically
efficient estimators exist under more general settings.

## References

  * Agarwal et al. (2017) [author] Agarwal, AmanA., Basu, SoumyaS., Schnabel, TobiasT. and Joachims, ThorstenT. (2017). Effective evaluation using logged bandit feedback from multiple loggers. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining 687–696.
  * Agarwal et al. (2019) [author] Agarwal, AlekhA., Jiang, NanN., Kakade, Sham MS. M. and Sun, WenW. (2019). Reinforcement learning: Theory and algorithms. CS Dept., UW Seattle, Seattle, WA, USA, Tech. Rep.
  * Ai and Chen (2003) [author] Ai, ChunrongC. and Chen, XiaohongX. (2003). Efficient estimation of models with conditional moment restrictions containing unknown functions. Econometrica 71 1795–1843.
  * Ai and Chen (2012) [author] Ai, ChunrongC. and Chen, XiaohongX. (2012). The semiparametric efficiency bound for models of sequential moment restrictions containing unknown functions. Journal of Econometrics 170 442–457.
  * Antos, Szepesvári and Munos (2008) [author] Antos, AndrásA., Szepesvári, CsabaC. and Munos, RémiR. (2008). Learning near-optimal policies with Bellman-residual minimization based fitted policy iteration and a single sample path. Machine Learning 71 89–129.
  * Athey and Wager (2017) [author] Athey, SusanS. and Wager, StefanS. (2017). Efficient Policy Learning. arXiv preprint arXiv:1702.02896.
  * Bang and Robins (2005) [author] Bang, HeejungH. and Robins, James MJ. M. (2005). Doubly robust estimation in missing data and causal inference models. Biometrics 61 962–973.
  * Benkeser and van der Laan (2016) [author] Benkeser, DavidD. and van der Laan, MarkM. (2016). The Highly Adaptive Lasso Estimator. In 2016 IEEE International Conference on Data Science and Advanced Analytics (DSAA) 2016 689–696. IEEE.
  * Bennett and Kallus (2021) [author] Bennett, AndrewA. and Kallus, NathanN. (2021). Proximal Reinforcement Learning: Efficient Off-Policy Evaluation in Partially Observed Markov Decision Processes.
  * Bennett et al. (2021) [author] Bennett, AndrewA., Kallus, NathanN., Li, LihongL. and Mousavi, AliA. (2021). Off-policy evaluation in infinite-horizon reinforcement learning with latent confounders. In International Conference on Artificial Intelligence and Statistics 1999–2007. PMLR.
  * Bertsekas (2012) [author] Bertsekas, Dimitri PD. P. (2012). Dynamic programming and optimal control, 4th ed. ed. Athena Scientific optimization and computation series. Athena Scientific, Belmont, Mass.
  * Bertsekas and Yu (2009) [author] Bertsekas, Dimitri PD. P. and Yu, HuizhenH. (2009). Projected equation methods for approximate solution of large linear systems. Journal of computational and applied mathematics 227 27–50.
  * Bhattacharya, Nabi and Shpitser (2020) [author] Bhattacharya, RohitR., Nabi, RaziehR. and Shpitser, IlyaI. (2020). Semiparametric inference for causal effects in graphical models with hidden variables. arXiv preprint arXiv:2003.12659.
  * Bibaut and J. van der Laan (2017) [author] Bibaut, AurelienA. and J. van der Laan, MarkM. (2017). Data-adaptive smoothing for optimal-rate estimation of possibly non-regular parameters. arXiv preprint arxiv:1706.07408.
  * Bibaut et al. (2019) [author] Bibaut, AurelienA., Malenica, IvanaI., Vlassis, NikosN. and van der Laan, MarkM. (2019). More Efficient Off-Policy Evaluation through Regularized Targeted Learning. In Proceedings of the 36th International Conference on Machine Learning. Proceedings of Machine Learning Research 97 654–663.
  * Bibaut et al. (2021) [author] Bibaut, AurelienA., Petersen, MayaM., Vlassis, NikosN., Dimakopoulou, MariaM. and van der Laan, MarkM. (2021). Sequential causal inference in a single world of connected units. arXiv preprint arXiv:2101.07380.
  * Boruvka et al. (2018) [author] Boruvka, AudreyA., Almirall, DanielD., Witkiewitz, KatieK. and Murphy, Susan A.S. A. (2018). Assessing Time-Varying Causal Effect Moderation in Mobile Health. Journal of the American Statistical Association 113 1112 - 1121.
  * Cao, Tsiatis and Davidian (2009) [author] Cao, WeihuaW., Tsiatis, Anastasios A.A. A. and Davidian, MarieM. (2009). Improving efficiency and robustness of the doubly robust estimator for a population mean with incomplete data. Biometrika 96 723–734.
  * Chakraborty, Laber and Zhao (2014) [author] Chakraborty, BibhasB., Laber, Eric BE. B. and Zhao, Ying-QiY.-Q. (2014). Inference about the expected performance of a data-driven dynamic treatment regime. Clinical Trials 11 408–417.
  * Chamberlain (1992) [author] Chamberlain, GaryG. (1992). Comment: Sequential moment restrictions in panel data. Journal of Business & Economic Statistics 10 20–26.
  * Chapelle and Li (2011) [author] Chapelle, OlivierO. and Li, LihongL. (2011). An Empirical Evaluation of Thompson Sampling. In Advances in Neural Information Processing Systems 24 2249–2257.
  * Chen and Jiang (2019) [author] Chen, JinglinJ. and Jiang, NanN. (2019). Information-Theoretic Considerations in Batch Reinforcement Learning. In Proceedings of the 36th International Conference on Machine Learning 97 1042–1051.
  * Chen and Qi (2022) [author] Chen, XiaohongX. and Qi, ZhenglingZ. (2022). On Well-posedness and Minimax Optimal Rates of Nonparametric Q-function Estimation in Off-policy Evaluation. arXiv preprint arXiv:2201.06169.
  * Chernozhukov, Newey and Singh (2018) [author] Chernozhukov, VictorV., Newey, WhitneyW. and Singh, RahulR. (2018). De-biased machine learning of global and local parameters using regularized Riesz representers. arXiv preprint arXiv:1802.08667.
  * Chernozhukov et al. (2018) [author] Chernozhukov, VictorV., Chetverikov, DenisD., Demirer, MertM., Duflo, EstherE., Hansen, ChristianC., Newey, WhitneyW. and Robins, JamesJ. (2018). Double/debiased machine learning for treatment and structural parameters. Econometrics Journal 21 C1–C68.
  * Chernozhukov et al. (2020) [author] Chernozhukov, VictorV., Newey, WhitneyW., Singh, RahulR. and Syrgkanis, VasilisV. (2020). Adversarial estimation of riesz representers. arXiv preprint arXiv:2101.00009.
  * Clifton and Laber (2020) [author] Clifton, JesseJ. and Laber, EricE. (2020). Q-Learning: Theory and Applications. Annual review of statistics and its application 7 279–301.
  * Dai et al. (2020) [author] Dai, BoB., Nachum, OfirO., Chow, YinlamY., Li, LihongL., Szepesvári, CsabaC. and Schuurmans, DaleD. (2020). Coindice: Off-policy confidence interval estimation. arXiv preprint arXiv:2010.11652.
  * Dann, Neumann and Peters (2014) [author] Dann, ChristophC., Neumann, GerhardG. and Peters, JanJ. (2014). Policy Evaluation with Temporal Differences: A Survey and Comparison. Journal of Machine Learning Research 15 809-883.
  * Dikkala et al. (2020) [author] Dikkala, NishanthN., Lewis, GregG., Mackey, LesterL. and Syrgkanis, VasilisV. (2020). arXiv preprint arXiv: 2006.07201.
  * Du et al. (2019) [author] Du, Simon SS. S., Kakade, Sham MS. M., Wang, RuosongR. and Yang, Lin FL. F. (2019). Is a good representation sufficient for sample efficient reinforcement learning? arXiv preprint arXiv:1910.03016.
  * Duan, Jia and Wang (2020) [author] Duan, YaqiY., Jia, ZeyuZ. and Wang, MengdiM. (2020). Minimax-optimal off-policy evaluation with linear function approximation. In International Conference on Machine Learning 2701–2709. PMLR.
  * Duan, Jin and Li (2021) [author] Duan, YaqiY., Jin, ChiC. and Li, ZhiyuanZ. (2021). Risk Bounds and Rademacher Complexity in Batch Reinforcement Learning. arXiv preprint arXiv:2103.13883.
  * Dudik et al. (2014) [author] Dudik, MiroslavM., Erhan, DumitruD., Langford, JohnJ. and Li, LihongL. (2014). Doubly Robust Policy Evaluation and Optimization. Statistical Science 29 485–511.
  * Díaz (2019) [author] Díaz, IvánI. (2019). Machine learning in the estimation of causal effects: targeted minimum loss-based estimation and double/debiased machine learning. Biostatistics (Oxford, England).
  * Ernst, Geurts and Wehenkel (2005) [author] Ernst, DamienD., Geurts, PierreP. and Wehenkel, LouisL. (2005). Tree-based batch mode reinforcement learning. Journal of Machine Learning Research 6 503–556.
  * Ertefaie and Strawderman (2018) [author] Ertefaie, AshkanA. and Strawderman, Robert LR. L. (2018). Constructing dynamic treatment regimes over indefinite time horizons. Biometrika 105 963-977.
  * Fan et al. (2017) [author] Fan, CaiyunC., Lu, WenbinW., Song, RuiR. and Zhou, YongY. (2017). Concordance-assisted learning for estimating optimal individualized treatment regimes. Journal of the Royal Statistical Society. Series B, Statistical methodology 79 1565\.
  * Fan et al. (2020) [author] Fan, JianqingJ., Wang, ZhaoranZ., Xie, YuchenY. and Yang, ZhuoranZ. (2020). A Theoretical Analysis of Deep Q-Learning. In Proceedings of the 2nd Conference on Learning for Dynamics and Control. Proceedings of Machine Learning Research 120 486–489.
  * Farahm et al. (2016) [author] Farahm, AmirmassoudA., , Ghavamzadeh, MohammadM., Szepesvári, CsabaC. and Mannor, ShieS. (2016). Regularized Policy Iteration with Nonparametric Function Spaces. Journal of Machine Learning Research 17 1-66.
  * Farajtabar, Chow and Ghavamzadeh (2018) [author] Farajtabar, M.M., Chow, Y.Y. and Ghavamzadeh, M.M. (2018). More robust doubly robust off-policy evaluation. In Proceedings of the 35th International Conference on Machine Learning 1447–1456.
  * Feng, Li and Liu (2019) [author] Feng, YihaoY., Li, LihongL. and Liu, QiangQ. (2019). A Kernel Loss for Solving the Bellman Equation. In Advances in Neural Information Processing Systems 32 15430–15441.
  * Foster and Syrgkanis (2019) [author] Foster, Dylan J.D. J. and Syrgkanis, VasilisV. (2019). Orthogonal Statistical Learning. arXiv preprint arXiv:1901.09036.
  * Foster et al. (2021) [author] Foster, Dylan JD. J., Krishnamurthy, AkshayA., Simchi-Levi, DavidD. and Xu, YunzongY. (2021). Offline reinforcement learning: Fundamental barriers for value function approximation. arXiv preprint arXiv:2111.10919.
  * Fu et al. (2022) [author] Fu, ZuyueZ., Qi, ZhenglingZ., Wang, ZhaoranZ., Yang, ZhuoranZ., Xu, YanxunY. and Kosorok, Michael RM. R. (2022). Offline reinforcement learning with instrumental variables in confounded markov decision processes. arXiv preprint arXiv:2209.08666.
  * Fulcher et al. (2020) [author] Fulcher, Isabel RI. R., Shpitser, IlyaI., Marealle, StellaS. and Tchetgen Tchetgen, Eric JE. J. (2020). Robust inference on population indirect causal effects: the generalized front door criterion. Journal of the Royal Statistical Society. Series B, Statistical methodology 82 199–214.
  * Futoma, Hughes and Doshi-Velez (2020) [author] Futoma, JosephJ., Hughes, Michael CM. C. and Doshi-Velez, FinaleF. (2020). Popcorn: Partially observed prediction constrained reinforcement learning. arXiv preprint arXiv:2001.04032.
  * Gottesman et al. (2019) [author] Gottesman, OmerO., Johansson, FredrikF., Komorowski, MatthieuM., Faisal, AldoA., Sontag, DavidD., Doshi-Velez, FinaleF. and Celi, Leo AnthonyL. A. (2019). Guidelines for reinforcement learning in healthcare. Nat Med 25 16–18.
  * Hahn (1998) [author] Hahn, JinyongJ. (1998). On the Role of the Propensity Score in Efficient Semiparametric Estimation of Average Treatment Effects. Econometrica 66 315–331.
  * Hao et al. (2021) [author] Hao, BotaoB., Duan, YaqiY., Lattimore, TorT., Szepesvári, CsabaC. and Wang, MengdiM. (2021). Sparse feature selection makes batch reinforcement learning more sample efficient. In International Conference on Machine Learning 4063–4073. PMLR.
  * Heckman, Ichimura and Todd (1998) [author] Heckman, James J.J. J., Ichimura, HidehikoH. and Todd, PetraP. (1998). Matching as an econometric evaluation estimator. Review of Economic Studies 65\.
  * Hernan and Robins (2019) [author] Hernan, M. A.M. A. and Robins, J. M.J. M. (2019). Causal Inference. Boca Raton: Chapman & Hall/CRC.
  * Hirano, Imbens and Ridder (2003) [author] Hirano, K.K., Imbens, G.G. and Ridder, G.G. (2003). Efficient estimation of average treatment effects using the estimated propensity score. Econometrica 71 1161–1189.
  * Hirshberg and Wager (2017) [author] Hirshberg, David AD. A. and Wager, StefanS. (2017). Augmented minimax linear estimation. arXiv preprint arXiv:1712.00038.
  * Hu and Wager (2021) [author] Hu, YuchenY. and Wager, StefanS. (2021). Off-Policy Evaluation in Partially Observed Markov Decision Processes. arXiv preprint arXiv:2110.12343.
  * Hu et al. (2020) [author] Hu, XinyuX., Qian, MinM., Cheng, BinB. and Cheung, Ying KuenY. K. (2020). Personalized Policy Learning using Longitudinal Mobile Health Data. Journal of the American Statistical Association 1–11.
  * Huang and Jiang (2022) [author] Huang, AudreyA. and Jiang, NanN. (2022). Beyond the Return: Off-policy Function Estimation under User-specified Error-measuring Distributions. Neurips.
  * Huber (2019) [author] Huber, MartinM. (2019). An introduction to flexible methods for policy evaluation. arXiv preprint arXiv:1910.00641.
  * Imai and Ratkovic (2014) [author] Imai, KosukeK. and Ratkovic, MarcM. (2014). Covariate balancing propensity score. Journal of the Royal Statistical Society: Series B (Statistical Methodology) 76 243–263.
  * Imbens and Rubin (2015) [author] Imbens, Guido W.G. W. and Rubin, Donald B.D. B. (2015). Causal Inference for Statistics, Social, and Biomedical Sciences: An Introduction. Cambridge University Press. 10.1017/CBO9781139025751
  * Jiang and Li (2016) [author] Jiang, N.N. and Li, L.L. (2016). Doubly robust off-policy value evaluation for reinforcement learning. In Proceedings of the 33rd International Conference on International Conference on Machine Learning-Volume 652–661.
  * Jiang et al. (2017) [author] Jiang, RunchaoR., Lu, WenbinW., Song, RuiR. and Davidian, MarieM. (2017). On estimation of optimal treatment regimes for maximizing t-year survival probability. Journal of the Royal Statistical Society. Series B, Statistical methodology 79 1165\.
  * Jiang et al. (2021) [author] Jiang, HaomingH., Dai, BoB., Yang, MengjiaoM., Zhao, TuoT. and Wei, WeiW. (2021). Towards Automatic Evaluation of Dialog Systems: A Model-Free Off-Policy Evaluation Approach. arXiv preprint arXiv:2102.10242.
  * Jin, Yang and Wang (2020) [author] Jin, YingY., Yang, ZhuoranZ. and Wang, ZhaoranZ. (2020). Is Pessimism Provably Efficient for Offline RL? arXiv preprint arXiv:2012.15085.
  * Jung, Tian and Bareinboim (2020) [author] Jung, YonghanY., Tian, JinJ. and Bareinboim, EliasE. (2020). Learning Causal Effects via Weighted Empirical Risk Minimization. In Advances in Neural Information Processing Systems (H.H. Larochelle, M.M. Ranzato, R.R. Hadsell, M. F.M. F. Balcan and H.H. Lin, eds.) 33 12697–12709. Curran Associates, Inc.
  * Kallus and Uehara (2019a) [author] Kallus, NathanN. and Uehara, MasatoshiM. (2019a). Efficiently Breaking the Curse of Horizon: Double Reinforcement Learning in Infinite-Horizon Processes. arXiv preprint arXiv:1909.05850.
  * Kallus and Uehara (2019b) [author] Kallus, NathanN. and Uehara, MasatoshiM. (2019b). Intrinsically Efficient, Stable, and Bounded Off-Policy Evaluation for Reinforcement Learning. In Advances in Neural Information Processing Systems 32 3320–3329.
  * Kallus and Uehara (2020a) [author] Kallus, NathanN. and Uehara, MasatoshiM. (2020a). Double Reinforcement Learning for Efficient Off-Policy Evaluation in Markov Decision Processes. J. Mach. Learn. Res. 21 167–1.
  * Kallus and Uehara (2020b) [author] Kallus, NathanN. and Uehara, MasatoshiM. (2020b). Efficient Evaluation of Natural Stochastic Policies in Offline Reinforcement Learning. arXiv preprint arXiv:2006.03886.
  * Kallus and Uehara (2020c) [author] Kallus, NathanN. and Uehara, MasatoshiM. (2020c). Doubly robust off-policy value and gradient estimation for deterministic policies. arXiv preprint arXiv:2006.03900.
  * Kallus and Zhou (2020) [author] Kallus, NathanN. and Zhou, AngelaA. (2020). Confounding-Robust Policy Evaluation in Infinite-Horizon Reinforcement Learning. In Advances in Neural Information Processing Systems 33 22293–22304. Curran Associates, Inc.
  * Kang and Schafer (2007) [author] Kang, Joseph D. Y.J. D. Y. and Schafer, Joseph L.J. L. (2007). Demystifying Double Robustness: A Comparison of Alternative Strategies for Estimating a Population Mean from Incomplete Data. Statistical Science 22 523–539.
  * Kennedy (2019) [author] Kennedy, Edward HE. H. (2019). Nonparametric Causal Effects Based on Incremental Propensity Score Interventions. Journal of the American Statistical Association 114 645–656.
  * Kennedy (2022) [author] Kennedy, Edward HE. H. (2022). Semiparametric doubly robust targeted double machine learning: a review. arXiv preprint arXiv:2203.06469.
  * Kennedy et al. (2017) [author] Kennedy, Edward HE. H., Ma, ZongmingZ., McHugh, Matthew DM. D. and Small, Dylan SD. S. (2017). Non-parametric methods for doubly robust estimation of continuous treatment effects. Journal of the Royal Statistical Society: Series B (Statistical Methodology) 79 1229–1245.
  * Kidambi et al. (2020) [author] Kidambi, RahulR., Rajeswaran, AravindA., Netrapalli, PraneethP. and Joachims, ThorstenT. (2020). MOReL: Model-Based Offline Reinforcement Learning. In Advances in Neural Information Processing Systems 33 21810–21823. Curran Associates, Inc.
  * Kitagawa and Tetenov (2018) [author] Kitagawa, ToruT. and Tetenov, AlekseyA. (2018). Who Should Be Treated? Empirical Welfare Maximization Methods for Treatment Choice. Econometrica 86 591–616.
  * Kober, Bagnell and Peters (2013) [author] Kober, JensJ., Bagnell, J AndrewJ. A. and Peters, JanJ. (2013). Reinforcement learning in robotics: A survey. The International Journal of Robotics Research 32 1238–1274.
  * Kosorok and Laber (2019) [author] Kosorok, Michael RM. R. and Laber, Eric BE. B. (2019). Precision Medicine. Annual review of statistics and its application 6 263–286.
  * Kosorok and Moodie (2015) [author] Kosorok, Michael R.M. R. and Moodie, Erica E. M.E. E. M. (2015). Adaptive Treatment Strategies in Practice: Planning Trials and Analyzing Data for Personalized Medicine. Society for Industrial and Applied Mathematics, USA.
  * Kuzborskij et al. (2021) [author] Kuzborskij, IljaI., Vernade, ClaireC., Gyorgy, AndrasA. and Szepesvári, CsabaC. (2021). Confident off-policy evaluation and selection through self-normalized importance weighting. In International Conference on Artificial Intelligence and Statistics 640–648. PMLR.
  * Lagoudakis and Parr (2004) [author] Lagoudakis, MichailM. and Parr, RonaldR. (2004). Least-Squares Policy Iteration. Journal of Machine Learning Research 4 1107–1149.
  * LeCun, Bengio and Hinton (2015) [author] LeCun, YannY., Bengio, YoshuaY. and Hinton, GeoffreyG. (2015). Deep learning. nature 521 436–444.
  * Levine et al. (2020) [author] Levine, SergeyS., Kumar, AviralA., Tucker, GeorgeG. and Fu, JustinJ. (2020). Offline reinforcement learning: Tutorial, review, and perspectives on open problems. arXiv preprint arXiv:2005.01643.
  * Liao, Klasnja and Murphy (2020) [author] Liao, PengP., Klasnja, PredragP. and Murphy, SusanS. (2020). Off-Policy Estimation of Long-Term Average Outcomes with Applications to Mobile Health. Journal of the American Statistical Association (To appear).
  * Liao, Klasnja and Murphy (2021) [author] Liao, PengP., Klasnja, PredragP. and Murphy, SusanS. (2021). Off-policy estimation of long-term average outcomes with applications to mobile health. Journal of the American Statistical Association 116 382–391.
  * Liao et al. (2022) [author] Liao, PengP., Qi, ZhenglingZ., Wan, RunzheR., Klasnja, PredragP. and Murphy, SusanS. (2022). Batch policy learning in average reward Markov decision processes. Annals of Statistics accepted.
  * Liu, Bacon and Brunskill (2020) [author] Liu, YaoY., Bacon, Pierre-LucP.-L. and Brunskill, EmmaE. (2020). Understanding the Curse of Horizon in Off-Policy Evaluation via Conditional Importance Sampling. In Proceedings of the 37th International Conference on Machine Learning (Hal DauméH. D. III and AartiA. Singh, eds.). Proceedings of Machine Learning Research 119 6184–6193. PMLR.
  * Liu et al. (2018) [author] Liu, QiangQ., Li, LihongL., Tang, ZiyangZ. and Zhou, DengyongD. (2018). Breaking the Curse of Horizon: Infinite-Horizon Off-Policy Estimation. In Advances in Neural Information Processing Systems 31 5356–5366.
  * Lu, Zhang and Zeng (2013) [author] Lu, WenbinW., Zhang, Hao HelenH. H. and Zeng, DonglinD. (2013). Variable selection for optimal treatment decision. Statistical methods in medical research 22 493–504.
  * Luckett et al. (2020) [author] Luckett, Daniel J.D. J., Laber, Eric B.E. B., Kahkoska, Anna R.A. R., Maahs, David M.D. M., Mayer-Davis, ElizabethE. and Kosorok, Michael R.M. R. (2020). Estimating Dynamic Treatment Regimes in Mobile Health Using V-Learning. Journal of the American Statistical Association 115 692–706.
  * Luedtke and Van Der Laan (2016) [author] Luedtke, Alexander RA. R. and Van Der Laan, Mark JM. J. (2016). Statistical inference for the mean outcome under a possibly non-unique optimal treatment strategy. Annals of statistics 44 713\.
  * Luedtke and van der Laan (2017) [author] Luedtke, Alexander RA. R. and van der Laan, Mark JM. J. (2017). Evaluating the impact of treating the optimal subgroup. Statistical methods in medical research 26 1630–1640.
  * Mandel et al. (2014) [author] Mandel, T.T., Liu, Y.Y., Levine, S.S., Brunskill, E.E. and Popovic, ZZ. (2014). Off-policy evaluation across representations with applications to educational games. In Proceedings of the 13th International Conference on Autonomous Agentsand Multi-agent Systems 1077–1084.
  * Manski (1995) [author] Manski, Charles FC. F. (1995). Identification problems in the social sciences. Harvard University Press, Cambridge, Mass.
  * Marling and Bunescu (2018) [author] Marling, CindyC. and Bunescu, Razvan CR. C. (2018). The OhioT1DM dataset for blood glucose level prediction. In KHD@ IJCAI.
  * Matsouaka, Li and Cai (2014) [author] Matsouaka, Roland AR. A., Li, JunlongJ. and Cai, TianxiT. (2014). Evaluating marker-guided treatment selection strategies. Biometrics 70 489–499.
  * Meinshausen, Meier and Bühlmann (2009) [author] Meinshausen, NicolaiN., Meier, LukasL. and Bühlmann, PeterP. (2009). P-values for high-dimensional regression. Journal of the American Statistical Association 104 1671–1681.
  * Miao, Geng and Tchetgen Tchetgen (2018) [author] Miao, WangW., Geng, ZhiZ. and Tchetgen Tchetgen, Eric JE. J. (2018). Identifying causal effects with proxy variables of an unmeasured confounder. Biometrika 105 987–993.
  * Miao, Qi and Zhang (2022) [author] Miao, RuiR., Qi, ZhenglingZ. and Zhang, XiaokeX. (2022). Off-Policy Evaluation for Episodic Partially Observable Markov Decision Processes under Non-Parametric Models. arXiv preprint arXiv:2209.10064.
  * Miyaguchi (2022) [author] Miyaguchi, KoheiK. (2022). Almost Hyperparameter-Free Hyperparameter Selection Framework for Offline Policy Evaluation. In AAAI Conference on Artificial Intelligence.
  * Mo, Qi and Liu (2021) [author] Mo, WeibinW., Qi, ZhenglingZ. and Liu, YufengY. (2021). Learning optimal distributionally robust individualized treatment rules. Journal of the American Statistical Association 116 659–674.
  * Mou, Wainwright and Bartlett (2022) [author] Mou, WenlongW., Wainwright, Martin JM. J. and Bartlett, Peter LP. L. (2022). Off-policy estimation of linear functionals: Non-asymptotic theory for semi-parametric efficiency. arXiv preprint arXiv:2209.13075.
  * Mou et al. (2021) [author] Mou, WenlongW., Pananjady, AshwinA., Wainwright, Martin JM. J. and Bartlett, Peter LP. L. (2021). Optimal and instance-dependent guarantees for Markovian linear stochastic approximation. arXiv preprint arXiv:2112.12770.
  * Mukherjee, Newey and Robins (2017) [author] Mukherjee, RajarshiR., Newey, Whitney KW. K. and Robins, James MJ. M. (2017). Semiparametric efficient empirical higher order influence function estimators. arXiv preprint arXiv:1705.07577.
  * Munos and Szepesvári (2008) [author] Munos, RémiR. and Szepesvári, CsabaC. (2008). Finite-time bounds for fitted value iteration. Journal of Machine Learning Research 9 815–857.
  * Murphy (2003) [author] Murphy, S. A.S. A. (2003). Optimal dynamic treatment regimes. Journal of the Royal Statistical Society: Series B (Statistical Methodology) 65 331–355.
  * Murphy et al. (2001) [author] Murphy, S. A.S. A., van der Laan, M. J.M. J., Robins, J. M.J. M. and Group, Conduct Problems Prevention ResearchC. P. P. R. (2001). Marginal Mean Models for Dynamic Regimes. Journal of the American Statistical Association 96 1410–1423.
  * Nachum and Dai (2020) [author] Nachum, OfirO. and Dai, BoB. (2020). Reinforcement learning via fenchel-rockafellar duality. arXiv preprint arXiv:2001.01866.
  * Nakada and Imaizumi (2020) [author] Nakada, RyumeiR. and Imaizumi, MasaakiM. (2020). Adaptive Approximation and Generalization of Deep Neural Network with Intrinsic Dimensionality. J. Mach. Learn. Res. 21 1–38.
  * Namkoong et al. (2020) [author] Namkoong, HongseokH., Keramati, RamtinR., Yadlowsky, SteveS. and Brunskill, EmmaE. (2020). Off-policy policy evaluation for sequential decisions under unobserved confounding. arXiv preprint arXiv:2003.05623.
  * Narita, Yasui and Yata (2019) [author] Narita, YusukeY., Yasui, ShotaS. and Yata, KoheiK. (2019). Efficient Counterfactual Learning from Bandit Feedback. AAAI.
  * Newey (2013) [author] Newey, Whitney KW. K. (2013). Nonparametric instrumental variables estimation. American Economic Review 103 550–56.
  * Ning, Sida and Imai (2020) [author] Ning, YangY., Sida, PengP. and Imai, KosukeK. (2020). Robust estimation of causal effects via a high-dimensional covariate balancing propensity score. Biometrika 107 533–554.
  * Owen (2013) [author] Owen, Art B.A. B. (2013). Monte Carlo theory, methods and examples.
  * Pananjady and Wainwright (2021) [author] Pananjady, AshwinA. and Wainwright, Martin JM. J. (2021). Instance-Dependent $l_{\infty}$-Bounds for Policy Evaluation in Tabular Reinforcement Learning. IEEE transactions on information theory 67 566–585.
  * Perdomo et al. (2022) [author] Perdomo, Juan CJ. C., Krishnamurthy, AkshayA., Bartlett, PeterP. and Kakade, ShamS. (2022). A Sharp Characterization of Linear Estimators for Offline Policy Evaluation. arXiv preprint arXiv:2203.04236.
  * Precup, Sutton and Singh (2000) [author] Precup, D.D., Sutton, R.R. and Singh, SS. (2000). Eligibility traces for off-policy policy evaluation. In Proceedings of the 17th International Conference on Machine Learning 759–766.
  * Puterman (2014) [author] Puterman, Martin LM. L. (2014). Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons.
  * Qian and Murphy (2011) [author] Qian, MinM. and Murphy, Susan AS. A. (2011). Performance guarantees for individualized treatment rules. Annals of statistics 39 1180\.
  * Rashidinejad et al. (2021) [author] Rashidinejad, PariaP., Zhu, BanghuaB., Ma, CongC., Jiao, JiantaoJ. and Russell, StuartS. (2021). Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism. arXiv preprint arXiv:2103.12021.
  * Robins (2004) [author] Robins, J. M.J. M. (2004). Optimal structural nested models for optimal sequentialdecisions. In Proceedings of the Second Seattle Symposium in Biostatistics: Analysis of Correlated Data.
  * Robins, Rotnitzky and Zhao (1994) [author] Robins, James M.J. M., Rotnitzky, AndreaA. and Zhao, Lue PingL. P. (1994). Estimation of Regression Coefficients When Some Regressors are not Always Observed. Journal of the American Statistical Association 89 846–866.
  * Robins, Rotnitzky and Zhao (1995) [author] Robins, James MJ. M., Rotnitzky, AndreaA. and Zhao, Lue PingL. P. (1995). Analysis of Semiparametric Regression Models for Repeated Outcomes in the Presence of Missing Data. Journal of the American Statistical Association 90 106–121.
  * Robins, Rotnitzky and Scharfstein (1999) [author] Robins, J. M.J. M., Rotnitzky, A.A. and Scharfstein, D. O.D. O. (1999). Sensitivity Analysis for Selection Bias and Unmeasured Confounding in Missing Data and Causal Inference Models. Statistical Models in Epidemiology: The Environment and Clinical Trials. 116\. NY: Springer-Verlag.
  * Robins et al. (2007) [author] Robins, JamesJ., Sued, MarielaM., Lei-Gomez, QuanhongQ. and Rotnitzky, AndreaA. (2007). Comment: Performance of Double-Robust Estimators When "Inverse Probability" Weights Are Highly Variable. Statistical Science 22 544–559.
  * Robins et al. (2017) [author] Robins, James MJ. M., Li, LinglingL., Mukherjee, RajarshiR., Tchetgen, Eric TchetgenE. T. and van der Vaart, AadA. (2017). Minimax estimation of a functional on a structured high-dimensional model. The Annals of Statistics 45 1951–1987.
  * Romano and DiCiccio (2019) [author] Romano, Joseph PJ. P. and DiCiccio, CyrusC. (2019). Multiple data splitting for testing. Department of Statistics, Stanford University.
  * Rosenbaum (1983) [author] Rosenbaum, P. R.P. R. (1983). The central role of the propensity score in observational studies for causal effects. 70 41–55.
  * Rosenbaum (2002) [author] Rosenbaum, Paul R.P. R. (2002). Observational Studies, second edition. ed. Springer Series in Statistics. Springer New York : Imprint: Springer, New York, NY.
  * Rotnitzky and Smucler (2020) [author] Rotnitzky, AndreaA. and Smucler, EzequielE. (2020). Efficient Adjustment Sets for Population Average Causal Treatment Effect Estimation in Graphical Models. Journal of machine learning research 21\.
  * Rubin (2005) [author] Rubin, D. B.D. B. (2005). Causal inference using potential outcomes: design, modeling, decisions. Journal of the American Statistical Association 100 322-331.
  * Rubin and van Der Laan (2008) [author] Rubin, Daniel BD. B. and van Der Laan, Mark JM. J. (2008). Empirical efficiency maximization: improved locally efficient covariate adjustment in randomized experiments and survival analysis. The international journal of biostatistics 4\.
  * Sallab et al. (2017) [author] Sallab, Ahmad ELA. E., Abdou, MohammedM., Perot, EtienneE. and Yogamani, SenthilS. (2017). Deep reinforcement learning framework for autonomous driving. Electronic Imaging 2017 70–76.
  * Scharfstein, Rotnizky and Robins (1999) [author] Scharfstein, D.D., Rotnizky, A.A. and Robins, J. M.J. M. (1999). Adjusting for nonignorable dropout using semi-parametric models. Journal of the American Statistical Association 94 1096–1146.
  * Schmidt-Hieber (2019) [author] Schmidt-Hieber, JohannesJ. (2019). Deep ReLU network approximation of functions on a manifold. arXiv preprint arXiv:1908.00695.
  * Schulte et al. (2014) [author] Schulte, Phillip J.P. J., Tsiatis, Anastasios A.A. A., Laber, Eric B.E. B. and Davidian, MarieM. (2014). Q-and A-Learning Methods for Estimating Optimal Dynamic Treatment Regimes. Statistical science 29 640–661.
  * Shi, Lu and Song (2020) [author] Shi, ChengchunC., Lu, WenbinW. and Song, RuiR. (2020). Breaking the Curse of Nonregularity with Subagging - Inference of the Mean Outcome under Optimal Treatment Regimes. Journal of machine learning research 21\.
  * Shi et al. (2018) [author] Shi, ChengchunC., Song, RuiR., Lu, WenbinW. and Fu, BoB. (2018). Maximin projection learning for optimal treatment decision with heterogeneous individualized treatment effects. Journal of the Royal Statistical Society: Series B (Statistical Methodology) 80 681–702.
  * Shi et al. (2020) [author] Shi, ChengchunC., Wan, RunzheR., Song, RuiR., Lu, WenbinW. and Leng, LingL. (2020). Does the Markov decision process fit the data: testing for the Markov property in sequential decision making. In International Conference on Machine Learning 8807–8817. PMLR.
  * Shi et al. (2021a) [author] Shi, ChengchunC., Song, RuiR., Lu, WenbinW. and Li, RunzeR. (2021a). Statistical inference for high-dimensional models via recursive online-score estimation. Journal of the American Statistical Association 116 1307–1318.
  * Shi et al. (2021b) [author] Shi, ChengchunC., Wan, RunzheR., Chernozhukov, VictorV. and Song, RuiR. (2021b). Deeply-Debiased Off-Policy Interval Estimation. arXiv preprint arXiv:2105.04646.
  * Shi et al. (2022a) [author] Shi, ChengchunC., Zhang, ShengS., Lu, WenbinW. and Song, RuiR. (2022a). Statistical inference of the value function for reinforcement learning in infinite horizon settings. Journal of the Royal Statistical Society. Series B, Statistical methodology 84 765–793.
  * Shi et al. (2022b) [author] Shi, ChengchunC., Wang, XiaoyuX., Luo, ShikaiS., Zhu, HongtuH., Ye, JiepingJ. and Song, RuiR. (2022b). Dynamic causal effects evaluation in A/B testing with a reinforcement learning framework. Journal of the American Statistical Association.
  * Shi et al. (2022c) [author] Shi, ChengchunC., Zhu, JinJ., Ye, ShenS., Luo, ShikaiS., Zhu, HongtuH. and Song, RuiR. (2022c). Off-policy confidence interval estimation with confounded Markov decision process. Journal of the American Statistical Association 1–12.
  * Shi et al. (2022d) [author] Shi, ChengchunC., Uehara, MasatoshiM., Huang, JiaweiJ. and Jiang, NanN. (2022d). A minimax learning approach to off-policy evaluation in confounded partially observable markov decision processes. In International Conference on Machine Learning 20057–20094. PMLR.
  * Shpitser and Pearl (2006) [author] Shpitser, IlyaI. and Pearl, JudeaJ. (2006). Identification of Joint Interventional Distributions in Recursive Semi-Markovian Causal Models. In Proceedings of the 21st National Conference on Artificial Intelligence - Volume 2. AAAI’06 1219–1226. AAAI Press.
  * Si et al. (2020) [author] Si, NianN., Zhang, FanF., Zhou, ZhengyuanZ. and Blanchet, JoseJ. (2020). Distributionally Robust Policy Evaluation and Learning in Offline Contextual Bandits. In Proceedings of the 37th International Conference on Machine Learning (Hal DauméH. D. III and AartiA. Singh, eds.). Proceedings of Machine Learning Research 119 8884–8894. PMLR.
  * Silver et al. (2016) [author] Silver, DavidD., Huang, AjaA., Maddison, Chris JC. J., Guez, ArthurA., Sifre, LaurentL., Van Den Driessche, GeorgeG., Schrittwieser, JulianJ., Antonoglou, IoannisI., Panneershelvam, VedaV., Lanctot, MarcM. et al. (2016). Mastering the game of Go with deep neural networks and tree search. nature 529 484–489.
  * Singh (2021) [author] Singh, RahulR. (2021). Debiased kernel methods. arXiv preprint arXiv:2102.11076.
  * Smucler, Sapienza and Rotnitzky (2022) [author] Smucler, EzequielE., Sapienza, FacundoF. and Rotnitzky, AndreaA. (2022). Efficient adjustment sets in causal graphical models with hidden variables. Biometrika 109 49–65.
  * Sondhi, Arbour and Dimmery (2020) [author] Sondhi, ArjunA., Arbour, DavidD. and Dimmery, DrewD. (2020). Balanced off-policy evaluation in general action spaces. In International Conference on Artificial Intelligence and Statistics 2413–2423. PMLR.
  * Steinwart and Christmann (2008) [author] Steinwart, IngoI. and Christmann, AndreasA. (2008). Support vector machines. Springer Science & Business Media.
  * Su et al. (2020) [author] Su, YiY., Dimakopoulou, MariaM., Krishnamurthy, AkshayA. and Dudík, MiroslavM. (2020). Doubly robust off-policy evaluation with shrinkage. In International Conference on Machine Learning 9167–9176. PMLR.
  * Sutton and Barto (2018) [author] Sutton, Richard SR. S. and Barto, Andrew GA. G. (2018). Reinforcement learning: An introduction. MIT press, Cambridge.
  * Suzuki (2018) [author] Suzuki, TaijiT. (2018). Adaptivity of deep ReLU network for learning in Besov and mixed smooth Besov spaces: optimal rate and curse of dimensionality. arXiv preprint arXiv:1810.08033.
  * Swaminathan and Joachims (2015a) [author] Swaminathan, AdithA. and Joachims, ThorstenT. (2015a). The Self-Normalized Estimator for Counterfactual Learning. In Advances in Neural Information Processing Systems 28 3231–3239.
  * Swaminathan and Joachims (2015b) [author] Swaminathan, AdithA. and Joachims, ThorstenT. (2015b). Batch Learning from Logged Bandit Feedback through Counterfactual Risk Minimization. Journal of Machine Learning Research 16 1731-1755.
  * Tan (2010) [author] Tan, ZhiqiangZ. (2010). Bounded, efficient and doubly robust estimation with inverse weighting. Biometrika 97 661–682.
  * Tang et al. (2020) [author] Tang, ZiyangZ., Feng, YihaoY., Li, LihongL., Zhou, DengyongD. and Liu, QiangQ. (2020). Doubly Robust Bias Reduction in Infinite Horizon Off-Policy Estimation. ICLR 2020.
  * Taylor and Tibshirani (2015) [author] Taylor, JonathanJ. and Tibshirani, Robert JR. J. (2015). Statistical learning and selective inference. Proceedings of the National Academy of Sciences 112 7629–7634.
  * Tennenholtz, Shalit and Mannor (2020) [author] Tennenholtz, GuyG., Shalit, UriU. and Mannor, ShieS. (2020). Off-Policy Evaluation in Partially Observable Environments. Proceedings of the AAAI Conference on Artificial Intelligence 34 10276-10283.
  * Thomas and Brunskill (2016) [author] Thomas, P.P. and Brunskill, E.E. (2016). Data-efficient off-policy policy evaluation for reinforcement learning. In Proceedings of the 33rd International Conference on Machine Learning 2139–2148.
  * Tian and Pearl (2002) [author] Tian, JinJ. and Pearl, JudeaJ. (2002). A general identification condition for causal effects. In Eighteenth national conference on artificial intelligence 567–573. American Association for Artificial Intelligence.
  * Tsiatis (2006) [author] Tsiatis, Anastasios AA. A. (2006). Semiparametric Theory and Missing Data. Springer Series in Statistics. Springer New York, New York, NY.
  * Tsiatis and Davidian (2007) [author] Tsiatis, Anastasios AA. A. and Davidian, MarieM. (2007). Comment: Demystifying Double Robustness: A Comparison of Alternative Strategies for Estimating a Population Mean from Incomplete Data. Statistical science 22 569–573.
  * Tsiatis, Davidian and Cao (2011) [author] Tsiatis, Anastasios AA. A., Davidian, MarieM. and Cao, WeihuaW. (2011). Improved Doubly Robust Estimation When Data Are Monotonely Coarsened, with Application to Longitudinal Studies with Dropout. Biometrics 67 536–545.
  * Tsiatis et al. (2019) [author] Tsiatis, Anastasios AA. A., Davidian, MarieM., Holloway, Shannon TS. T. and Laber, Eric BE. B. (2019). Dynamic Treatment Regimes: Statistical Methods for Precision Medicine. CRC press.
  * Tsybakov (2009) [author] Tsybakov, Alexandre BA. B. (2009). Lower bounds on the minimax risk. In Introduction to Nonparametric Estimation 77–135. Springer.
  * Uehara, Huang and Jiang (2020) [author] Uehara, MasatoshiM., Huang, JiaweiJ. and Jiang, NanN. (2020). Minimax Weight and Q-Function Learning for Off-Policy Evaluation. ICML 2020.
  * Uehara and Sun (2021) [author] Uehara, MasatoshiM. and Sun, WenW. (2021). Pessimistic Model-based Offline RL: PAC Bounds and Posterior Sampling under Partial Coverage. arXiv preprint arXiv:2107.06226.
  * Uehara et al. (2021) [author] Uehara, MasatoshiM., Imaizumi, MasaakiM., Jiang, NanN., Kallus, NathanN., Sun, WenW. and Xie, TengyangT. (2021). Finite Sample Analysis of Minimax Offline Reinforcement Learning: Completeness, Fast Rates and First-Order Efficiency.
  * Uehara et al. (2022) [author] Uehara, MasatoshiM., Kiyohara, HarukaH., Bennett, AndrewA., Chernozhukov, VictorV., Jiang, NanN., Kallus, NathanN., Shi, ChengchunC. and Sun, WenW. (2022). Future-Dependent Value-Based Off-Policy Evaluation in POMDPs. arXiv preprint arXiv:2207.13081.
  * Ueno et al. (2011) [author] Ueno, TsuyoshiT., Kawanabe, MotoakiM., Mori, TakeshiT., Maeda, Shin-IchiS.-I. and Ishii, ShinS. (2011). Generalized TD learning. Journal of Machine Learning Research 12 1977–2020.
  * van Der Laan and Robins (2003) [author] van Der Laan, Mark J.M. J. and Robins, James MJ. M. (2003). Unified Methods for Censored Longitudinal Data and Causality. Springer Series in Statistics,. Springer New York, New York, NY.
  * van der Laan and Rose (2018) [author] van der Laan, Mark JM. J. and Rose, SherriS. (2018). Targeted Learning in Data Science: Causal Inference for Complex Longitudinal Studies. Springer Series in Statistics.
  * van der Vaart (1998) [author] van der Vaart, A. W.A. W. (1998). Asymptotic statistics. Cambridge University Press, Cambridge, UK.