# Marginal Density Ratio for Off-Policy Evaluation in Contextual Bandits

Muhammad Faaiz Taufiq
Department of Statistics
University of Oxford
&Arnaud Doucet
Department of Statistics
University of Oxford
Rob Cornish
Department of Statistics
University of Oxford
&Jean-François Ton
ByteDance Research
ByteDance
Part of the work was done during an internship at ByteDance Research.
Correspondence to<EMAIL_ADDRESS>and
<EMAIL_ADDRESS>
###### Abstract

Off-Policy Evaluation (OPE) in contextual bandits is crucial for assessing new
policies using existing data without costly experimentation. However, current
OPE methods, such as Inverse Probability Weighting (IPW) and Doubly Robust
(DR) estimators, suffer from high variance, particularly in cases of low
overlap between target and behavior policies or large action and context
spaces. In this paper, we introduce a new OPE estimator for contextual
bandits, the Marginal Ratio (MR) estimator, which focuses on the shift in the
marginal distribution of outcomes $Y$ instead of the policies themselves.
Through rigorous theoretical analysis, we demonstrate the benefits of the MR
estimator compared to conventional methods like IPW and DR in terms of
variance reduction. Additionally, we establish a connection between the MR
estimator and the state-of-the-art Marginalized Inverse Propensity Score
(MIPS) estimator, proving that MR achieves lower variance among a generalized
family of MIPS estimators. We further illustrate the utility of the MR
estimator in causal inference settings, where it exhibits enhanced performance
in estimating Average Treatment Effects (ATE). Our experiments on synthetic
and real-world datasets corroborate our theoretical findings and highlight the
practical advantages of the MR estimator in OPE for contextual bandits.

##  1 Introduction

In contextual bandits, the objective is to select an action $A$, guided by
contextual information $X$, to maximize the resulting outcome $Y$. This
paradigm is prevalent in many real-world applications such as healthcare,
personalized recommendation systems, or online advertising [1, 2, 3]. The
objective is to perform actions, such as prescribing medication or
recommending items, which lead to desired outcomes like improved patient
health or higher click-through rates. Nonetheless, updating the policy
presents challenges, as naïvely implementing a new, untested policy may raise
ethical or financial concerns. For instance, prescribing a drug based on a new
policy poses risks, as it may result in unexpected side effects. As a result,
recent research [4, 5, 6, 7, 8, 9, 10, 11] has concentrated on evaluating the
performance of new policies (target policy) using only existing data that was
generated using the current policy (behaviour policy). This problem is known
as Off-Policy Evaluation (OPE).

Current OPE methods in contextual bandits, such as the Inverse Probability
Weighting (IPW) [12] and Doubly Robust (DR) [13] estimators primarily account
for the policy shift by re-weighting the data using the ratio of the target
and behaviour polices to estimate the target policy value. This can be
problematic as it may lead to high variance in the estimators in cases of
substantial policy shifts. The issue is further exacerbated in situations with
large action or context spaces [14], since in these cases the estimation of
policy ratios is even more difficult leading to extreme bias and variance.

In this work we show that this problem of high variance in OPE can be
alleviated by using methods which directly consider the shift in the marginal
distribution of the outcome $Y$ resulting from the policy shift, instead of
considering the policy shift itself (as in IPW and DR). To this end, we
propose a new OPE estimator for contextual bandits called the Marginal Ratio
(MR) estimator, which weights the data directly based on the shift in the
marginal distribution of outcomes $Y$ and consequently is much more robust to
increasing sizes of action and context spaces than existing methods like IPW
or DR. Our extensive theoretical analyses show that MR enjoys better variance
properties than the existing methods making it highly attractive for a variety
of applications in addition to OPE. One such application is the estimation of
Average Treatment Effect (ATE) in causal inference, for which we show that MR
provides greater sample efficiency than the most commonly used methods.

Our contributions in this paper are as follows:

  * •

Firstly, we introduce MR, an OPE estimator for contextual bandits, that
focuses on the shift in the marginal distribution of $Y$ rather than the joint
distribution of $(X,A,Y)$. We show that MR has favourable theoretical
properties compared to existing methods like IPW and DR. Our analysis also
encompasses theory on the approximation errors of our estimator.

  * •

Secondly, we explicitly lay out the connection between MR and Marginalized
Inverse Propensity Score (MIPS) [14], a recent state-of-the-art contextual
bandits OPE method, and prove that MR attains lowest variance among a
generalized family of MIPS estimators.

  * •

Thirdly, we show that the MR estimator can be applied in the setting of causal
inference to estimate average treatment effects (ATE), and theoretically prove
that the resulting estimator is more data-efficient with higher accuracy and
lower variance than commonly used methods.

  * •

Finally, we verify all our theoretical analyses through a variety of
experiments on synthetic and real-world datasets and empirically demonstrate
that the MR estimator achieves better overall performance compared to current
state-of-the-art methods.

##  2 Background

###  2.1 Setup and Notation

We consider the standard contextual bandit setting. Let $X\in{\mathcal{X}}$ be
a context vector (e.g., user features), $A\in\mathcal{A}$ denote an action
(e.g., recommended website to the user), and $Y\in\mathcal{Y}$ denote a scalar
reward or outcome (e.g., whether the user clicks on the website). The outcome
and context are sampled from unknown probability distributions $p(y\mid x,a)$
and $p(x)$ respectively. Let
$\mathcal{D}\coloneqq\\{(x_{i},a_{i},y_{i})\\}_{i=1}^{n}$ be a historically
logged dataset with $n$ observations, generated by a (possibly unknown)
_behaviour policy_ $\pi^{b}(a\mid x)$. Specifically, $\mathcal{D}$ consists of
i.i.d. samples from the joint density under behaviour policy,

$\displaystyle p_{\pi^{b}}(x,a,y)\coloneqq p(y\mid
x,a)\,{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\pi^{b}(a\mid
x)}\,p(x).$ (1)

We denote the joint density of $(X,A,Y)$ under the target policy as

$\displaystyle p_{\pi^{*}}(x,a,y)\coloneqq p(y\mid
x,a)\,{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\pi^{*}(a\mid
x)}\,p(x).$ (2)

Moreover, we use $p_{\pi^{b}}(y)$ to denote the marginal density of $Y$ under
the behaviour policy,

$\displaystyle p_{\pi^{b}}(y)$
$\displaystyle=\int_{\mathcal{A}\times{\mathcal{X}}}p_{\pi^{b}}(x,a,y)\,\mathrm{d}a\,\mathrm{d}x,$

and likewise for the target policy $\pi^{*}$. Similarly, we use
$\mathbb{E}_{\pi^{b}}$ and $\mathbb{E}_{\pi^{*}}$ to denote the expectations
under the joint densities $p_{\pi^{b}}(x,a,y)$ and $p_{\pi^{*}}(x,a,y)$
respectively.

##### Off-policy evaluation (OPE)

The main objective of OPE is to estimate the expectation of the outcome $Y$
under a given target policy $\pi^{*}$, i.e., $\mathbb{E}_{\pi^{*}}[Y]$, using
only the logged data $\mathcal{D}$.

Throughout this work, we assume that the support of the target policy
$\pi^{*}$ is included in the support of the behaviour policy $\pi^{b}$. This
is to ensure that importance sampling yields unbiased off-policy estimators,
and is satisfied for exploratory behaviour policies such as the
$\epsilon$-greedy policies.

######  Assumption 2.1 (Support).

For any $x\in{\mathcal{X}},a\in\mathcal{A}$, $\pi^{*}(a\mid
x)>0\implies\pi^{b}(a\mid x)>0$.

###  2.2 Existing off-policy evaluation methodologies

Next, we will present some of the most commonly used OPE estimators before
outlining the limitations of these methodologies. This motivates our proposal
of an alternative OPE estimator.

The value of the target policy can be expressed as the expectation of outcome
$Y$ under the target data distribution $p_{\pi^{*}}(x,a,y)$. However in most
cases, we do not have access to samples from this target distribution and
hence we have to resort to importance sampling methods.

##### Inverse Probability Weighting (IPW) estimator

One way to compute the target policy value, $\mathbb{E}_{\pi^{*}}[Y]$, when
only given data generated from $p_{\pi^{b}}(x,a,y)$ is to rewrite the policy
value as follows:

$\displaystyle\mathbb{E}_{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\pi^{*}}}[Y]=\int
y\,p_{\pi^{*}}(x,a,y)\,\mathrm{d}y\,\mathrm{d}a\,\mathrm{d}x=\int
y\,\underbrace{\frac{p_{\pi^{*}}(x,a,y)}{p_{\pi^{b}}(x,a,y)}}_{\rho(a,x)}\,p_{\pi^{b}}(x,a,y)\,\mathrm{d}y\,\mathrm{d}a\,\mathrm{d}x=\mathbb{E}_{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\pi^{b}}}\left[Y\,\rho(A,X)\right],$

where
$\rho(a,x)\coloneqq\frac{p_{\pi^{*}}(x,a,y)}{p_{\pi^{b}}(x,a,y)}=\frac{\pi^{*}(a|x)}{\pi^{b}(a|x)}$,
given the factorizations in Eqns. (1) and (2). This leads to the commonly used
_Inverse Probability Weighting (IPW)_ [12] estimator:

$\hat{\theta}_{\textup{IPW}}\coloneqq\frac{1}{n}\sum_{i=1}^{n}\rho(a_{i},x_{i})\,y_{i}.$

When the behaviour policy is known, IPW is an unbiased and consistent
estimator. However, it can suffer from high variance, especially as the
overlap between the behaviour and target policies decreases.

##### Doubly Robust (DR) estimator

To alleviate the high variance of IPW, [13] proposed a _Doubly Robust (DR)_
estimator for OPE. DR uses an estimate of the conditional mean
$\hat{\mu}(a,x)\approx\mathbb{E}[Y\mid X=x,A=a]$ (_outcome model_), as a
control variate to decrease the variance of IPW. It is also doubly robust in
that it yields accurate value estimates if either the importance weights
$\rho(a,x)$ or the outcome model $\hat{\mu}(a,x)$ is well estimated [13, 15].
The DR estimator for $\mathbb{E}_{\pi^{*}}[Y]$ can be written as follows:

$\hat{\theta}_{\textup{DR}}=\frac{1}{n}\sum_{i=1}^{n}\rho(a_{i},x_{i})\,(y_{i}-\hat{\mu}(a_{i},x_{i}))+\hat{\eta}(\pi^{*}),$

where
$\hat{\eta}(\pi^{*})=\frac{1}{n}\sum_{i=1}^{n}\sum_{a^{\prime}\in\mathcal{A}}\hat{\mu}(a^{\prime},x_{i})\pi^{*}(a^{\prime}\mid
x_{i})\approx\mathbb{E}_{\pi^{*}}[\hat{\mu}(A,X)]$. Here,
$\hat{\eta}(\pi^{*})$ is referred to as the Direct Method (DM) as it uses
$\hat{\mu}(a,x)$ directly to estimate target policy value.

###  2.3 Limitation of existing methodologies

To estimate the value of the target policy $\pi^{*}$, the existing
methodologies consider the shift in the joint distribution of $(X,A,Y)$ as a
result of the policy shift (by weighting samples by policy ratios). As we show
in Section 3.1, considering the joint shift can lead to inefficient policy
evaluation and high variance especially as the policy shift increases [16].
Since our goal is to estimate $\mathbb{E}_{\pi^{*}}[Y]$, we will show in the
next section that considering only the shift in the marginal distribution of
the outcomes $Y$ from $p_{\pi^{b}}(Y)$ to $p_{\pi^{*}}(Y)$, leads to a more
efficient OPE methodology compared to existing approaches.

To better comprehend why only considering the shift in the marginal
distribution is advantageous, let us examine an extreme example where we
assume that $Y\perp\\!\\!\\!\perp A\mid X$, i.e., the outcome $Y$ for a user
$X$ is independent of the action $A$ taken. In this specific instance,
$\mathbb{E}_{\pi^{*}}[Y]=\mathbb{E}_{\pi^{b}}[Y]\approx
1/n\sum_{i=1}^{n}y_{i},$ indicating that an unweighted empirical mean serves
as a suitable unbiased estimator of $\mathbb{E}_{\pi^{*}}[Y]$. However, IPW
and DR estimators use policy ratios $\rho(a,x)=\frac{\pi^{*}(a\mid
x)}{\pi^{b}(a\mid x)}$ as importance weights. In case of large policy shifts,
these ratios may vary significantly, leading to high variance in IPW and DR.

In this particular example, the shift in policies is inconsequential as it
does not impact the distribution of outcomes $Y$. Hence, IPW and DR estimators
introduce additional variance due to the policy ratios when they are not
actually required. This limitation is not exclusive to this special case; in
general, methodologies like IPW and DR exhibit high variance when there is low
overlap between target and behavior policies [16] even if the resulting shift
in marginals of the outcome $Y$ is not significant.

Therefore, we propose the _Marginal Ratio (MR)_ OPE estimator for contextual
bandits in the subsequent section, which circumvents these issues by focusing
on the shift in the marginal distribution of the outcomes $Y$. Additionally,
we provide extensive theoretical insights on the comparison of MR to existing
state-of-the-art methods, such as IPW and DR.

##  3 Marginal Ratio (MR) estimator

Our method’s key insight involves weighting outcomes by the marginal density
ratio of outcome $Y$:

$\displaystyle\mathbb{E}_{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\pi^{*}}}[Y]$
$\displaystyle=\int_{\mathcal{Y}}y\,p_{\pi^{*}}(y)\,\mathrm{d}y=\int_{\mathcal{Y}}y\,\frac{p_{\pi^{*}}(y)}{p_{\pi^{b}}(y)}\,p_{\pi^{b}}(y)\,\mathrm{d}y=\mathbb{E}_{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\pi^{b}}}\left[Y\,w(Y)\right],$

where $w(y)\coloneqq\frac{p_{\pi^{*}}(y)}{p_{\pi^{b}}(y)}.$ This leads to the
Marginal Ratio OPE estimator:

$\displaystyle\hat{\theta}_{\textup{MR}}\coloneqq\frac{1}{n}\sum_{i=1}^{n}w(y_{i})\,y_{i}.$

In Section 3.1 we prove that by only considering the shift in the marginal
distribution of outcomes, the MR estimator achieves a lower variance than the
standard OPE methods. In fact, this estimator does not depend on the shift
between target and behaviour policies directly. Instead, it depends on the
shift between the marginals $p_{\pi^{b}}(y)$ and $p_{\pi^{*}}(y)$.

##### Estimation of $w(y)$

When the weights $w(y)$ are known exactly, the MR estimator is unbiased and
consistent. However, in practice the weights $w(y)$ are often not known and
must be estimated using the logged data $\mathcal{D}$. Here, we outline an
efficient way to estimate $w(y)$ by first representing it as a conditional
expectation, which can subsequently be expressed as the solution to a
regression problem.

######  Lemma 3.1.

Let $w(y)=\frac{p_{\pi^{*}}(y)}{p_{\pi^{b}}(y)}$ and
$\rho(a,x)=\frac{\pi^{*}(a\mid x)}{\pi^{b}(a\mid x)}$, then
$w(y)=\mathbb{E}_{\pi^{b}}\left[\rho(A,X)\mid\,Y=y\right]$, and,

$\displaystyle
w=\arg\min_{f}\,\mathbb{E}_{\pi^{b}}\left[(\rho(A,X)-f(Y))^{2}\right].$ (3)

Lemma 3.1 allows us to approximate $w(y)$ using a parametric family
$\\{f_{\phi}:\mathbb{R}\rightarrow\mathbb{R}\mid\phi\in\Phi\\}$ (e.g. neural
networks) and defining $\hat{w}(y)\coloneqq f_{\phi^{*}}(y)$, where $\phi^{*}$
solves the regression problem in Eq. (3).

Note that MR can also be estimated alternatively by directly estimating
$h(y)\coloneqq w(y)\,y$ using a similar regression technique as above and
computing $\hat{\theta}_{\textup{MR}}=1/n\sum_{i=1}^{n}h(y_{i})$. We include
additional details along with empirical comparisons in Appendix F.1.1.

###  3.1 Theoretical analysis

Recall that the traditional OPE estimators like IPW and DR use importance
weights which account for the the shift in the joint distributions of
$(X,A,Y)$. In this section, we prove that by considering only the shift in the
marginal distribution of $Y$ instead, MR achieves better variance properties
than these estimators. Our analysis in this subsection assumes that the ratios
$\rho(a,x)$ and $w(y)$ are known exactly. Since the OPE estimators considered
are unbiased in this case, our analysis of variance is analogous to that of
the mean squared error (MSE) here. We address the case where the weights are
not known exactly in Section 3.1.2. First, we make precise our intuition that
the shift in the joint distribution of $(X,A,Y)$ is ‘greater’ than the shift
in the marginal distribution of outcomes $Y$. We formalise this using the
notion of $f$-divergences.

######  Proposition 3.2.

Let $f:[0,\infty)\rightarrow\mathbb{R}$ be a convex function with $f(1)=0$,
and $\textup{D}_{f}(P||Q)$ denotes the $f$-divergence between distributions
$P$ and $Q$. Then,

$\textup{D}_{f}\left(p_{\pi^{*}}(x,a,y)\,||\,p_{\pi^{b}}(x,a,y)\right)\geq\textup{D}_{f}\left(p_{\pi^{*}}(y)\,||\,p_{\pi^{b}}(y)\right).$

##### Intuition

Proposition 3.2 shows that the shift in the joint distributions is at least as
‘large’ as the shift in the marginals of the outcome $Y$. Traditional OPE
estimators, therefore take into consideration more of a distribution shift
than needed, and consequently lead to inefficient estimators. In contrast, the
MR estimator mitigates this problem by only considering the shift in the
marginal distributions of outcomes resulting from the policy shift. This
provides further intuition on why the MR estimator has lower variance compared
to existing methods.

######  Proposition 3.3 (Variance comparison with IPW estimator).

When the weights $\rho(a,x)$ and $w(y)$ are known exactly, we have that
$\textup{Var}_{\pi^{b}}[\hat{\theta}_{\textup{MR}}]\leq\textup{Var}_{\pi^{b}}[\hat{\theta}_{\textup{IPW}}]$.
In particular,

$\displaystyle\textup{Var}_{\pi^{b}}[\hat{\theta}_{\textup{IPW}}]-\textup{Var}_{\pi^{b}}[\hat{\theta}_{\textup{MR}}]=\frac{1}{n}\mathbb{E}_{\pi^{b}}\left[\textup{Var}_{\pi^{b}}\left[\rho(A,X)\mid
Y\right]\,Y^{2}\right]\geq 0.$

##### Intuition

Proposition 3.3 shows that the variance of MR estimator is smaller than that
of the IPW estimator when the weights are known exactly. Moreover, the
proposition also shows that the difference between the two variances will
increases as the variance $\textup{Var}_{\pi^{b}}\left[\rho(A,X)\mid Y\right]$
increases. This variance is likely to be large when the policy shift between
$\pi^{b}$ and $\pi^{*}$ is large, or when the dimensions of contexts $X$
and/or the actions $A$ is large, and therefore in these cases the MR estimator
will perform increasingly better than the IPW estimator. A similar phenomenon
occurs for DR as we show next, even though in this case the variance of MR is
not in general smaller than that of DR.

######  Proposition 3.4 (Variance comparison with DR estimator).

When the weights $\rho(a,x)$ and $w(y)$ are known exactly and
$\mu(A,X)\coloneqq\mathbb{E}[Y\mid X,A]$, we have that,

$\displaystyle\textup{Var}_{\pi^{b}}[\hat{\theta}_{\textup{DR}}]-\textup{Var}_{\pi^{b}}[\hat{\theta}_{\textup{MR}}]\geq\frac{1}{n}\mathbb{E}_{\pi^{b}}\left[\textup{Var}_{\pi^{b}}\left[\rho(A,X)\,Y\mid
Y\right]-\textup{Var}_{\pi^{b}}\left[\rho(A,X)\,\mu(A,X)\mid X\right]\right].$

##### Intuition

Proposition 3.4 shows that if $\textup{Var}_{\pi^{b}}\left[\rho(A,X)\,Y\mid
Y\right]$ is greater than $\textup{Var}_{\pi^{b}}\left[\rho(A,X)\,\mu(A,X)\mid
X\right]$ on average, the variance of the MR estimator will be less than that
of the DR estimator. Intuitively, this will occur when the dimension of
context space ${\mathcal{X}}$ is high because in this case the conditional
variance over $X$ and $A$, $\textup{Var}_{\pi^{b}}\left[\rho(A,X)\,Y\mid
Y\right]$ is likely to be greater than the conditional variance over $A$,
$\textup{Var}_{\pi^{b}}\left[\rho(A,X)\,\mu(A,X)\mid X\right]$. Our empirical
results in Appendix F.2 are consistent with this intuition. Additionally, we
also provide theoretical comparisons with other extensions of DR, such as
Switch-DR [5] and DR with Optimistic Shrinkage (DRos) [17] in Appendix B, and
show that a similar intuition applies for these results. We emphasise that the
well known results in [5] which show that IPW and DR estimators achieve the
optimal _worst case_ variance (where the worst case is taken over a class of
possible outcome distributions $Y\mid X,A$) are not at odds with our results
presented here (as the distribution of $Y\mid X,A$ is fixed in our setting).

####  3.1.1 Comparison with Marginalised Inverse Propensity Score (MIPS) [14]

In this section, we compare MR against the recently proposed Marginalised
Inverse Propensity Score (MIPS) estimator [14], which uses a marginalisation
technique to reduce variance and provides a robust OPE estimate specifically
in contextual bandits with large action spaces. We prove that the MR estimator
achieves lower variance than the MIPS estimator and doesn’t require new
assumptions.

##### MIPS estimator

As we mentioned earlier, the variance of the IPW estimator may be high when
the action $A$ is high dimensional. To mitigate this, the MIPS estimator
assumes the existence of a (potentially lower dimensional) action embedding
$E$, which summarises all ‘relevant’ information about the action $A$.
Formally, this assumption can be written as follows:

######  Assumption 3.5.

The action $A$ has no direct effect on the outcome $Y$, i.e.,
$Y\perp\\!\\!\\!\perp A\mid X,E$.

For example, in the setting of a recommendation system where $A$ corresponds
to the items recommended, $E$ may correspond to the item categories.
Assumption 3.5 then intuitively means that item category $E$ encodes all
relevant information about the item $A$ which determines the outcome $Y$.
Assuming that such action embedding $E$ exists, [14] prove that the MIPS
estimator $\hat{\theta}_{\textup{MIPS}}$, defined as

$\hat{\theta}_{\textup{MIPS}}\coloneqq\frac{1}{n}\sum_{i=1}^{n}\frac{p_{\pi^{*}}(e_{i},x_{i})}{p_{\pi^{b}}(e_{i},x_{i})}\,y_{i}=\frac{1}{n}\sum_{i=1}^{n}\frac{p_{\pi^{*}}(e_{i}\mid
x_{i})}{p_{\pi^{b}}(e_{i}\mid x_{i})}\,y_{i},$

provides an unbiased estimator of target policy value
$\mathbb{E}_{\pi^{*}}[Y]$. Moreover,
$\textup{Var}_{\pi^{b}}[\hat{\theta}_{\textup{MIPS}}]\leq\textup{Var}_{\pi^{b}}[\hat{\theta}_{\textup{IPW}}]$.

$(X,A)$ $(X,E)$$Y$ Figure 1: Bayesian network corresponding to Assumption 3.5.

##### Intuition

The context-embedding pair $(X,E)$ can be seen as a representation of the
context-action pair $(X,A)$ which contains less ‘redundant information’
regarding the outcome $Y$. Intuitively, the MIPS estimator, which only
considers the shift in the distribution of $(X,E)$ is therefore more efficient
than the IPW estimator (which considers the shift in the distribution of
$(X,A)$ instead).

##### MR achieves lower variance than MIPS

Given the intuition above, we should achieve greater variance reduction as the
amount of redundant information in the representation $(X,E)$ decreases. We
formalise this in Appendix D and show that the variance of MIPS estimator
decreases as the representation gets closer to $Y$ in terms of information
content. As a result, we achieve the greatest variance reduction by
considering the marginal shift in the outcome $Y$ itself (as in MR) rather
than the shift in the representation $(X,E)$ (as in MIPS). The following
result formalizes this finding.

######  Theorem 3.6.

When the weights $w(y)$, $\frac{p_{\pi^{*}}(e,x)}{p_{\pi^{b}}(e,x)}$ and
$\rho(a,x)$ are known exactly, then under Assumption 3.5,
$\mathbb{E}_{\pi^{b}}[\hat{\theta}_{\textup{MR}}]=\mathbb{E}_{\pi^{b}}[\hat{\theta}_{\textup{MIPS}}]=\mathbb{E}_{\pi^{*}}[Y]$,
and
$\textup{Var}_{\pi^{b}}[\hat{\theta}_{\textup{MR}}]\leq\textup{Var}_{\pi^{b}}[\hat{\theta}_{\textup{MIPS}}]\leq\textup{Var}_{\pi^{b}}[\hat{\theta}_{\textup{IPW}}].$

This analysis provides a link between the MR and MIPS estimators in the
framework of contextual bandits, and shows that the MR estimator achieves
lower variance than MIPS estimator while not requiring any additional
assumptions (e.g. Assumption 3.5 as in MIPS). We also verify this empirically
in Section 5.1 by reproducing the experimental setup in [14] along with the MR
baseline.

####  3.1.2 Weight estimation error

Our analysis so far assumes prior knowledge of the behavior policy $\pi^{b}$
and the marginal ratios $w(y)$. However, in practice, both quantities are
often unknown and must be estimated from data. To this end, we assume access
to an additional training dataset
$\mathcal{D}_{\textup{tr}}=\\{(x^{\textup{tr}}_{i},a^{\textup{tr}}_{i},y^{\textup{tr}}_{i})\\}_{i=1}^{m}$
(for weight estimation), in addition to the evaluation dataset
$\mathcal{D}=\\{(x_{i},a_{i},y_{i})\\}_{i=1}^{n}$ (for computing the OPE
estimate). The estimation of $\hat{w}(y)$ involves a two-step process that
exclusively utilizes data from $\mathcal{D}_{\textup{tr}}$:

  1. (i)

First, we estimate the policy ratio
$\hat{\rho}(a,x)\approx\frac{\pi^{*}(a|x)}{\pi^{b}(a|x)}$. This can be
achieved by estimating the behaviour policy $\widehat{\pi}^{b}$, and defining
$\hat{\rho}(a,x)\coloneqq\frac{\pi^{*}(a\mid x)}{\widehat{\pi}^{b}(a\mid x)}$.
Alternatively, $\hat{\rho}(a,x)$ can also be estimated directly by using
density ratio estimation techniques as in [18].

  2. (ii)

Secondly, we estimate the weights $\hat{w}(y)$ using Eq. (3) with $\hat{\rho}$
instead of $\rho$.

In practice, one may consider splitting $\mathcal{D}_{\textup{tr}}$ for each
estimation step outlined above. Moreover, each approximation step may
introduce bias and therefore, the MR estimator may have two sources of bias.
While classical OPE methods like IPW and DR also suffer from bias because of
$\hat{\rho}$ estimation, the estimation of $\hat{w}(y)$ is specific to MR.
However, we show below that given any policy ratio estimate $\hat{\rho}$, if
$\hat{w}(y)$ approximates $\mathbb{E}_{\pi^{b}}[\hat{\rho}(A,X)\mid Y=y]$
‘well enough’ (i.e., the estimation step (ii) shown above is ‘accurate
enough’), then MR achieves a lower variance than IPW and incurs little extra
bias.

######  Proposition 3.7.

Suppose that the IPW and MR estimators are defined as,

$\tilde{\theta}_{\textup{IPW}}\coloneqq\frac{1}{n}\sum_{i=1}^{n}\hat{\rho}(a_{i},x_{i})\,y_{i},\quad\textup{and
}\quad\tilde{\theta}_{\textup{MR}}\coloneqq\frac{1}{n}\sum_{i=1}^{n}\hat{w}(y_{i})\,y_{i},$

and define the approximation error as
$\epsilon\coloneqq\hat{w}(Y)-\tilde{w}(Y)$, where
$\tilde{w}(Y)\coloneqq\mathbb{E}_{\pi^{b}}[\hat{\rho}(A,X)\mid Y]$. Then we
have that,
$\textup{Bias}(\tilde{\theta}_{\textup{MR}})-\textup{Bias}(\tilde{\theta}_{\textup{IPW}})=\mathbb{E}_{\pi^{b}}[\epsilon\,Y]$.
Moreover,

$\displaystyle\textup{Var}_{\pi^{b}}[\tilde{\theta}_{\textup{IPW}}]-\textup{Var}_{\pi^{b}}[\tilde{\theta}_{\textup{MR}}]$
$\displaystyle=\frac{1}{n}(\underbrace{\mathbb{E}_{\pi^{b}}[\textup{Var}_{\pi^{b}}[\hat{\rho}(A,X)\,Y\mid
Y]]}_{\geq
0}-\textup{Var}_{\pi^{b}}[\epsilon\,Y]-2\,\textup{Cov}(\tilde{w}(Y)\,Y,\epsilon\,Y)).$
(4)

##### Intuition

The $\epsilon$ term defined in Proposition 3.7 denotes the error of the second
approximation step outlined above. As a direct consequence of this result, we
show in Appendix C that as the error $\epsilon$ becomes small (specifically as
$\mathbb{E}_{\pi^{b}}[\epsilon^{2}]\rightarrow 0$), the difference between
biases of MR and IPW estimator becomes negligible. Likewise, the terms
$\textup{Var}_{\pi^{b}}[\epsilon\,Y]$ and
$\textup{Cov}(\tilde{w}(Y)\,Y,\epsilon\,Y)$ in Eq. (4) will also be small and
as a result the variance of MR will be lower than that of IPW (as the first
term is positive).

In fact, using recent results regarding the generalisation error of neural
networks [19], we show that when using 2-layer wide neural networks to
approximate the weights $\hat{w}(y)$, the estimation error $\epsilon$ declines
with increasing training data size $m$. Specifically, under certain regularity
assumptions we obtain $\mathbb{E}_{\pi^{b}}[\epsilon^{2}]=O(m^{-2/3})$. Using
this we show that as the training data size $m$ increases, the biases of MR
and IPW estimators become roughly equal with a high probability, and

$\textup{Var}_{\pi^{b}}[\tilde{\theta}_{\textup{IPW}}]-\textup{Var}_{\pi^{b}}[\tilde{\theta}_{\textup{MR}}]=\frac{1}{n}\,\mathbb{E}_{\pi^{b}}[\textup{Var}_{\pi^{b}}[\hat{\rho}(A,X)\,Y\mid
Y]]+O(m^{-1/3}).$

Therefore the variance of MR estimator falls below that of IPW for large
enough $m$. The empirical results shown in Appendix F.2 are consistent with
this result. Due to space constraints, the main technical result has been
included in Appendix C.

###  3.2 Application to causal inference

Beyond contextual bandits, the variance reduction properties of the MR
estimator make it highly useful in a wide variety of other applications. Here,
we show one such application in the field of causal inference, where MR can be
used for the estimation of average treatment effect (ATE) [20] and leads to
some desirable properties in comparison to the conventional ATE estimation
approaches. Specifically, we illustrate that the MR estimator for ATE utilizes
the evaluation data $\mathcal{D}$ more efficiently and achieves lower variance
than state-of-the-art ATE estimators and consequently provides more accurate
ATE estimates. To be concrete, the goal in this setting is to estimate ATE,
defined as follows:

$\textup{ATE}\coloneqq\mathbb{E}[Y(1)-Y(0)].$

Here $Y(a)$ corresponds to the outcome under a deterministic policy
$\pi_{a}(a^{\prime}\mid x)\coloneqq{\mathbbm{1}}(a^{\prime}=a)$. Hence any OPE
estimator can be used to estimate $\mathbb{E}[Y(a)]$ (and therefore ATE) by
considering target policy $\pi^{*}=\pi_{a}$. An important distinction between
MR and existing approaches (like IPW or DR) is that, when estimating
$\mathbb{E}[Y(a)]$, the existing approaches only use datapoints in
$\mathcal{D}$ with $A=a$. To see why this is the case, we note that the policy
ratios
$\frac{\pi^{*}(A|X)}{\pi^{b}(A|X)}=\frac{{\mathbbm{1}}(A=a)}{\pi^{b}(A|X)}$
are zero when $A\neq a$. In contrast, the MR weights
$\frac{p_{\pi^{*}}(Y)}{p_{\pi^{b}}(Y)}$ are not necessarily zero for
datapoints with $A\neq a$, and therefore the MR estimator uses all evaluation
datapoints when estimating $\mathbb{E}[Y(a)]$.

As such we show that MR applied to ATE estimation leads to a smaller variance
than the existing approaches. Moreover, because MR is able to use all
datapoints when estimating $\mathbb{E}[Y(a)]$, MR will generally be more
accurate than the existing methods especially in the setting where the data is
imbalanced, i.e., the number of datapoints with $A=a$ is small for a specific
action $a$. In Appendix E, we formalise this variance reduction of the MR ATE
estimator compared to IPW and DR estimators, by deriving analogous results to
Propositions 3.3 and 3.4. In addition, we also show empirically in Section 5.3
that the MR ATE estimator outperforms the most commonly used ATE estimators.

##  4 Related Work

Off-Policy evaluation is a central problem both in contextual bandits [13, 5,
21, 6, 7, 17, 22, 8, 23] and in RL [24, 25, 26, 27]. Existing OPE
methodologies can be broadly categorised into Direct Method (DM), Inverse
Probability Weighting (IPW), and Doubly Robust (DR). While DM typically has a
low variance, it suffers from high bias when the reward model is misspecified
[28]. On the other hand, IPW [12] and DR [13, 5, 17] use policy ratios as
importance weights when estimating policy value and suffer from high variance
as overlap between behaviour and target policies increases or as the
action/context space gets larger [29, 14]. To circumvent this problem,
techniques like weight clipping or normalisation [4, 30, 31] are often
employed, however, these can often increase bias.

In contrast to these approaches, [14] propose MIPS, which considers the
marginal shift in the distribution of a lower dimensional embedding of the
action space. While this approach reduces the variance associated with IPW, we
show in Section 3.1.1 that the MR estimator achieves a lower variance than
MIPS while not requiring any additional assumptions (like Assumption 3.5).

In the context of Reinforcement Learning (RL), various marginalisation
techniques of importance weights have been used to propose OPE methodologies.
[21, 25, 26] use methods which considers the shift in the marginal
distribution of the states, and applies importance weighting with respect to
this marginal shift rather than the trajectory distribution. Similarly, [32]
use marginalisation for OPE in deep RL, where the goal is to consider the
shift in marginal distributions of state and action. Although marginalization
is a key trick of these estimators, these techniques do not consider the
marginal shift in reward as in MR and are aimed at resolving the curse of
horizon, a problem specific to RL. Apart from this, [33] propose a general
framework of OPE based on conditional expectations of importance ratios for
variance reduction. While their proposed framework includes reward conditioned
importance ratios, this is not the main focus and there is little theoretical
and empirical comparison of their proposed methodology with existing state-of-
the-art methods like DR.

Finally we note that the idea of approximating the ratio of intractable
marginal densities via leveraging the fact that this ratio can be reformulated
as the conditional expectation of a ratio of tractable densities is a standard
idea in computational statistics [34] and has been exploited more recently to
perform likelihood-free inference [35]. In particular, while [34] typically
approximates this expectation through Markov chain Monte Carlo, [35] uses
regression instead, however without any theory.

##  5 Empirical Evaluation

In this section, we provide empirical evidence to support our theoretical
results by investigating the performance of our MR estimator against the
current state-of-the-art OPE methods. The code to reproduce our experiments
has been made available at: github.com/faaizT/MR-OPE.

###  5.1 Experiments on synthetic data

For our synthetic data experiment, we reproduce the experimental setup for the
synthetic data experiment in [14] by reusing their code with minor
modifications. Specifically, ${\mathcal{X}}\subseteq\mathbb{R}^{d}$, for
various values of $d$ as described below. Likewise, the action space
$\mathcal{A}=\\{0,\dots,n_{a}-1\\}$, with $n_{a}$ taking a range of different
values. Additional details regarding the reward function, behaviour policy
$\pi^{b}$, and the estimation of weights $\hat{w}(y)$ have been included in
Appendix F.2 for completeness.

##### Target policies

To investigate the effect of increasing policy shift, we define a class of
policies,

$\pi^{\alpha^{\ast}}(a|x)=\alpha^{\ast}\,{\mathbbm{1}}(a=\arg\max_{a^{\prime}\in\mathcal{A}}q(x,a^{\prime}))+\frac{1-\alpha^{\ast}}{|\mathcal{A}|}\quad\textup{where}\quad
q(x,a)\coloneqq\mathbb{E}[Y\mid X=x,A=a],$

where $\alpha^{\ast}\in[0,1]$ allows us to control the shift between $\pi^{b}$
and $\pi^{*}$. In particular, as we show later, the shift between $\pi^{b}$
and $\pi^{*}$ increases as $\alpha^{\ast}\rightarrow 1$. Using the ground
truth behaviour policy $\pi^{b}$, we generate a dataset which is split into
training and evaluation datasets of sizes $m$ and $n$ respectively.

##### Baselines

We compare our estimator with DM, IPW, DR and MIPS estimators. Our setup
includes action embeddings $E$ satisfying Assumption 3.5, and so MIPS is
unbiased. Additional baselines have been considered in Appendix F.2. For MR,
we split the training data to estimate $\widehat{\pi}^{b}$ and $\hat{w}(y)$,
whereas for all other baselines we use the entire training data to estimate
$\widehat{\pi}^{b}$ for a fair comparison.

(a) Results with varying size of evaluation dataset $n$.

(b) Results with varying $\alpha^{\ast}$.

Figure 2: Results for synthetic data experiment. In 2(a) we have
$\alpha^{\ast}=0.8$ and in 2(b) we have $n=800$.

##### Results

We compute the target policy value using the $n$ evaluation datapoints. Here,
the MSE of the estimators is computed over 10 different sets of logged data
replicated with different seeds. The results presented have context dimension
$d=1000$, number of actions $n_{a}=100$ and training data size $m=5000$. More
experiments for a variety of parameter values are included in Appendix F.2.

##### Varying number of evaluation data $n$

In Figure 2(a) we plot the results with increasing size of evaluation data $n$
increases. MR achieves the smallest MSE among all the baselines considered
when $n$ is small, with the MSE of MR being at least an order of magnitude
smaller than every baseline for $n\leq 500$. This shows that MR is
significantly more accurate than the baselines when the size of the evaluation
data is small. As $n\rightarrow\infty$, the difference between the results for
MR and MIPS decreases. However, MR attains smaller variance and MSE than MIPS
generally, verifying our analysis in Section 3.1.1. Moreover, Figure 2(a)
shows that while the variance of MR is greater than that of DM, it still
achieves the lowest MSE overall, owing to the high bias of DM.

##### Varying $\alpha^{\ast}$

As $\alpha^{\ast}$ parameter of the target policy increases, so does the shift
between the policies $\pi^{b}$ and $\pi^{\alpha^{\ast}}$ as illustrated by the
figure on the right, which plots the KL-divergence
$D_{\textup{KL}}(\pi^{b}\,||\,\pi^{\alpha^{\ast}})$ as a function of $\alpha$.
Figure 2(b) plots the results for increasing policy shift. Overall, the MSE of
MR estimator is lowest among all the baselines. Moreover, while the MSE and
variance of all estimators increase with increasing $\alpha^{\ast}$ the
increase in these quantities is lower for the MR estimator than for the other
baselines. Therefore, the relative performance of MR estimator improves with
increasing policy shift and MR remains robust to increase in policy shift.

##### Additional ablation studies

In Appendix F.2, we investigate the effect of varying context dimensions $d$,
number of actions $n_{a}$ and number of training data $m$. In every case, we
observe that the MR estimator has a smaller MSE than all other baselines
considered. In particular, MR remains robust to increasing $n_{a}$ whereas the
MSE and variance of IPW and DR estimators degrade substantially when
$n_{a}\geq 2000$. Likewise, MR outperforms the baselines even when the
training data size $m$ is small.

Table 1: Mean squared error of target policy value with standard errors over 10 different seeds for different classification datasets. Here, number of evaluation data $n=1000$, and $\alpha^{\ast}=0.6$. Dataset | Digits | Letter | OptDigits | PenDigits | SatImage | Mnist | CIFAR-100
---|---|---|---|---|---|---|---
DM |  0.1508$\pm$0.0015 |  0.0886$\pm$0.0026 |  0.0485$\pm$0.0016 |  0.0520$\pm$0.0016 |  0.0208$\pm$0.0009 |  0.1109$\pm$0.0014 |  0.0020$\pm$0.0001
DR |  0.1334$\pm$0.0400 | 35.085$\pm$17.768 |  0.0464$\pm$0.0061 |  0.2343$\pm$0.1404 |  0.0560$\pm$0.0395 |  0.2617$\pm$0.0139 | 3823.9$\pm$2023.2
DRos |  0.0847$\pm$0.0025 |  0.2363$\pm$0.0586 |  0.0384$\pm$0.0025 |  0.0138$\pm$0.0029 |  0.0078$\pm$0.0008 |  0.2151$\pm$0.0061 |  0.2628$\pm$0.1087
IPW |  0.1632$\pm$0.0462 | 45.253$\pm$22.057 |  0.0844$\pm$0.0056 |  0.1342$\pm$0.0531 |  0.0900$\pm$0.0676 |  0.3359$\pm$0.0118 | 4116.9$\pm$2097.9
SwitchDR |  0.0982$\pm$0.0032 |  0.2387$\pm$0.0507 |  0.0557$\pm$0.0047 |  0.0342$\pm$0.0090 |  0.0136$\pm$0.0012 |  0.2750$\pm$0.0102 |  1.1644$\pm$0.8227
MR (Ours) | 0.0034$\pm$0.0001 | 0.0018$\pm$0.0004 | 0.0006$\pm$0.0002 | 0.0008$\pm$0.0002 | 0.0016$\pm$0.0003 | 0.0121$\pm$0.0009 | 0.0007$\pm$0.0002

###  5.2 Experiments on classification datasets

Following previous works on OPE in contextual bandits [13, 22, 36, 5], we
transform classification datasets into contextual bandit feedback data in this
experiment. We consider five UCI classification datasets [37] as well as Mnist
[38] and CIFAR-100 [39] datasets, each of which comprises
$\\{(x_{i},a^{\textup{gt}}_{i})\\}_{i}$, where $x_{i}\in{\mathcal{X}}$ are
feature vectors and $a^{\textup{gt}}_{i}\in\mathcal{A}$ are the ground-truth
labels. In the contextual bandits setup, the feature vectors $x_{i}$ are
considered to be the contexts, whereas the actions correspond to the possible
class of labels. For the context vector $x_{i}$ and the action $a_{i}$, the
reward $y_{i}$ is defined as
$y_{i}\coloneqq{\mathbbm{1}}(a_{i}=a^{\textup{gt}}_{i})$, i.e., the reward is
1 when the action is the same as the ground truth label and 0 otherwise. Here,
the baselines considered include the DM, IPW and DR estimators as well as
Switch-DR [5] and DR with Optimistic Shrinkage (DRos) [17]. We do not consider
a MIPS baseline here as there is no natural embedding $E$ of $A$. Additional
details are provided in Appendix F.3.

In Table 1, we present the results with number of evaluation data $n=1000$ and
number of training data $m=500$. The table shows that across all datasets, MR
achieves the lowest MSE among all methods. Moreover, for the Letter and
CIFAR-100 datasets the IPW and DR yield large bias and variance arising from
poor policy estimates $\widehat{\pi}^{b}$. Despite this, the MR estimator
which utilizes the _same_ $\widehat{\pi}^{b}$ for the estimation of
$\hat{w}(y)$ leads to much more accurate results. We also verify that MR
outperforms the baselines for increasing policy shift and evaluation data $n$
in Appendix F.3.

###  5.3 Application to ATE estimation

In this experiment, we investigate the empirical performance of the MR
estimator for ATE estimation.

##### Twins dataset

We use the Twins dataset studied in [40], which comprises data from twin
births in the USA between 1989-1991. The treatment $a=1$ corresponds to being
born the heavier twin and the outcome $Y$ corresponds to the mortality of each
of the twins in their first year of life. Specifically, $Y(1)$ corresponds to
the mortality of the heavier twin (and likewise for $Y(0)$). To simulate the
observational study, we follow a similar strategy as in [40] to selectively
hide one of the two twins as explained in Appendix F.4. We obtain a total of
11,984 datapoints, of which 5000 datapoints are used to train the behaviour
policy $\widehat{\pi}^{b}$ and outcome model $\hat{q}(x,a)$.

Table 2: Mean absolute ATE estimation error $\epsilon_{\textup{ATE}}$ with standard errors over 10 different seeds, for increasing number of evaluation data $n$. $n$ | 50 | 200 | 1600 | 3200
---|---|---|---|---
DM |  0.092$\pm$0.003 |  0.092$\pm$0.003 |  0.092$\pm$0.004 |  0.092$\pm$0.004
DR |  0.101$\pm$0.024 | 0.065$\pm$0.009 |  0.071$\pm$0.005 |  0.069$\pm$0.004
DRos |  0.100$\pm$0.017 |  0.089$\pm$0.006 |  0.093$\pm$0.004 |  0.087$\pm$0.004
IPW |  0.092$\pm$0.024 |  0.088$\pm$0.014 |  0.067$\pm$0.007 |  0.067$\pm$0.007
SwitchDR |  0.101$\pm$0.024 | 0.065$\pm$0.009 |  0.071$\pm$0.005 |  0.069$\pm$0.004
MR (Ours) | 0.062$\pm$0.007 | 0.065$\pm$0.007 | 0.061$\pm$0.005 | 0.061$\pm$0.006

Here, we consider the same baselines as the classification data experiments in
previous section. For our evaluation, we consider the absolute error in ATE
estimation, $\epsilon_{\textup{ATE}}$, defined as:
$\epsilon_{\textup{ATE}}\coloneqq|\hat{\theta}^{(n)}_{\textup{ATE}}-\theta_{\textup{ATE}}|.$
Here, $\hat{\theta}^{(n)}_{\textup{ATE}}$ denotes the value of the ATE
estimated using $n$ evaluation datapoints. We compute the ATE value using the
$n$ evaluation datapoints, over 10 different sets of observational data (using
different seeds). Table 2 shows that MR achieves the lowest estimation error
$\epsilon_{\textup{ATE}}$ for all values of $n$ considered here. While the
performance of other baselines improves with increasing $n$, MR outperforms
them all.

##  6 Discussion

In this paper, we proposed an OPE method for contextual bandits called
marginal ratio (MR) estimator, which considers only the shift in the marginal
distribution of the outcomes resulting from the policy shift. Our theoretical
and empirical analysis showed that MR achieves better variance and MSE
compared to the current state-of-the-art methods and is more data efficient
overall. Additionally, we demonstrated that MR applied to ATE estimation
provides more accurate results than most commonly used methods. Next, we
discuss limitations of our methodology and possible avenues for future work.

##### Limitations

The MR estimator requires the additional step of estimating $\hat{w}(y)$ which
may introduce an additional source of bias in the value estimation. However,
$\hat{w}(y)$ can be estimated by solving a simple 1d regression problem, and
as we show empirically in Appendix F, MR achieves the smallest bias among all
baselines considered in most cases. Most notably, our ablation study in
Appendix F.2 shows that even when the training data is reasonably small, MR
outperforms the baselines considered.

##### Future work

The MR estimator can also be applied to policy optimisation problems, where
the data collected using an ‘old’ policy is used to learn a new policy. This
approach has been used in Proximal Policy Optimisation (PPO) [41] for example,
which has gained immense popularity and has been applied to reinforcement
learning with human feedback (RLHF) [42]. We believe that the MR estimator
applied to these methodologies could lead to improvements in the stability and
convergence of these optimisation schemes, given its favourable variance
properties.

## Acknowledgements

We would like to thank Jake Fawkes, Siu Lun Chau, Shahine Bouabid and Robert
Hu for their useful feedback. We also appreciate the insights and constructive
criticisms provided by the anonymous reviewers. MFT acknowledges his PhD
funding from Google DeepMind.

## References

  * Li et al. [2010] Lihong Li, Wei Chu, John Langford, and Robert E. Schapire.  A contextual-bandit approach to personalized news article recommendation.  In _Proceedings of the 19th International Conference on World Wide Web_ , WWW ’10, page 661–670, New York, NY, USA, 2010. Association for Computing Machinery.  ISBN 9781605587998.  doi: 10.1145/1772690.1772758.  URL https://doi.org/10.1145/1772690.1772758.
  * Bastani and Bayati [2019] Hamsa Bastani and Mohsen Bayati.  Online decision making with high-dimensional covariates.  _Operations Research_ , 68, 11 2019.  doi: 10.1287/opre.2019.1902.
  * Xu et al. [2020] Xiao Xu, Fang Dong, Yanghua Li, Shaojian He, and Xin Li.  Contextual-bandit based personalized recommendation with time-varying user interests.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 34:6518–6525, 04 2020.  doi: 10.1609/aaai.v34i04.6125.
  * Swaminathan and Joachims [2015a] Adith Swaminathan and Thorsten Joachims.  Counterfactual risk minimization: Learning from logged bandit feedback.  In _Proceedings of the 32nd International Conference on International Conference on Machine Learning - Volume 37_ , ICML’15, page 814–823. JMLR.org, 2015a.
  * Wang et al. [2017] Yu-Xiang Wang, Alekh Agarwal, and Miroslav Dudík.  Optimal and adaptive off-policy evaluation in contextual bandits.  In _Proceedings of the 34th International Conference on Machine Learning - Volume 70_ , ICML’17, page 3589–3597. JMLR.org, 2017.
  * Farajtabar et al. [2018a] Mehrdad Farajtabar, Yinlam Chow, and Mohammad Ghavamzadeh.  More robust doubly robust off-policy evaluation.  In Jennifer Dy and Andreas Krause, editors, _Proceedings of the 35th International Conference on Machine Learning_ , volume 80 of _Proceedings of Machine Learning Research_ , pages 1447–1456. PMLR, 10–15 Jul 2018a.  URL https://proceedings.mlr.press/v80/farajtabar18a.html.
  * Su et al. [2019] Yi Su, Lequn Wang, Michele Santacatterina, and Thorsten Joachims.  CAB: Continuous adaptive blending for policy evaluation and learning.  In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, _Proceedings of the 36th International Conference on Machine Learning_ , volume 97 of _Proceedings of Machine Learning Research_ , pages 6005–6014. PMLR, 09–15 Jun 2019.  URL https://proceedings.mlr.press/v97/su19a.html.
  * Metelli et al. [2021] Alberto Maria Metelli, Alessio Russo, and Marcello Restelli.  Subgaussian and differentiable importance sampling for off-policy evaluation and learning.  In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, _Advances in Neural Information Processing Systems_ , volume 34, pages 8119–8132. Curran Associates, Inc., 2021.  URL https://proceedings.neurips.cc/paper_files/paper/2021/file/4476b929e30dd0c4e8bdbcc82c6ba23a-Paper.pdf.
  * Liu et al. [2019] Anqi Liu, Hao Liu, Anima Anandkumar, and Yisong Yue.  Triply robust off-policy evaluation, 2019.  URL https://arxiv.org/abs/1911.05811.
  * Sugiyama and Kawanabe [2012] Masashi Sugiyama and Motoaki Kawanabe.  _Machine Learning in Non-Stationary Environments: Introduction to Covariate Shift Adaptation_.  The MIT Press, 2012.  ISBN 9780262017091.  URL http://www.jstor.org/stable/j.ctt5hhbtm.
  * Swaminathan et al. [2017] Adith Swaminathan, Akshay Krishnamurthy, Alekh Agarwal, Miroslav Dudík, John Langford, Damien Jose, and Imed Zitouni.  Off-policy evaluation for slate recommendation.  In _Proceedings of the 31st International Conference on Neural Information Processing Systems_ , NIPS’17, page 3635–3645, Red Hook, NY, USA, 2017. Curran Associates Inc.  ISBN 9781510860964.
  * Horvitz and Thompson [1952] D. G. Horvitz and D. J. Thompson.  A generalization of sampling without replacement from a finite universe.  _Journal of the American Statistical Association_ , 47(260):663–685, 1952.  ISSN 01621459.  URL http://www.jstor.org/stable/2280784.
  * Dudík et al. [2014] Miroslav Dudík, Dumitru Erhan, John Langford, and Lihong Li.  Doubly robust policy evaluation and optimization.  _Statistical Science_ , 29(4):485–511, 2014.  ISSN 08834237, 21688745.  URL http://www.jstor.org/stable/43288496.
  * Saito and Joachims [2022] Yuta Saito and Thorsten Joachims.  Off-policy evaluation for large action spaces via embeddings.  In _Proceedings of the 39th International Conference on Machine Learning_ , pages 19089–19122. PMLR, 2022.
  * Jiang and Li [2016] Nan Jiang and Lihong Li.  Doubly robust off-policy value evaluation for reinforcement learning.  In Maria Florina Balcan and Kilian Q. Weinberger, editors, _Proceedings of The 33rd International Conference on Machine Learning_ , volume 48 of _Proceedings of Machine Learning Research_ , pages 652–661, New York, New York, USA, 20–22 Jun 2016. PMLR.  URL https://proceedings.mlr.press/v48/jiang16.html.
  * Li et al. [2018] Fan Li, Laine E Thomas, and Fan Li.  Addressing Extreme Propensity Scores via the Overlap Weights.  _American Journal of Epidemiology_ , 188(1):250–257, 09 2018.  ISSN 0002-9262.  doi: 10.1093/aje/kwy201.  URL https://doi.org/10.1093/aje/kwy201.
  * Su et al. [2020] Yi Su, Maria Dimakopoulou, Akshay Krishnamurthy, and Miroslav Dudík.  Doubly robust off-policy evaluation with shrinkage.  In _Proceedings of the 37th International Conference on Machine Learning_ , ICML’20. JMLR.org, 2020.
  * Sondhi et al. [2020] Arjun Sondhi, David Arbour, and Drew Dimmery.  Balanced off-policy evaluation in general action spaces.  In Silvia Chiappa and Roberto Calandra, editors, _Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics_ , volume 108 of _Proceedings of Machine Learning Research_ , pages 2413–2423. PMLR, 26–28 Aug 2020.  URL https://proceedings.mlr.press/v108/sondhi20a.html.
  * Lai et al. [2023] Jianfa Lai, Manyun Xu, Rui Chen, and Qian Lin.  Generalization ability of wide neural networks on $\mathbb{R}$, 2023.  URL https://arxiv.org/abs/2302.05933.
  * Pearl [2009] Judea Pearl.  _Causality_.  Cambridge University Press, 2 edition, 2009.  doi: 10.1017/CBO9780511803161.
  * Liu et al. [2018] Qiang Liu, Lihong Li, Ziyang Tang, and Dengyong Zhou.  Breaking the curse of horizon: Infinite-horizon off-policy estimation.  In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 31. Curran Associates, Inc., 2018.  URL https://proceedings.neurips.cc/paper/2018/file/dda04f9d634145a9c68d5dfe53b21272-Paper.pdf.
  * Kallus et al. [2021] Nathan Kallus, Yuta Saito, and Masatoshi Uehara.  Optimal off-policy evaluation from multiple logging policies.  In _International Conference on Machine Learning_ , pages 5247–5256. PMLR, 2021.
  * Saito et al. [2020] Yuta Saito, Aihara Shunsuke, Matsutani Megumi, and Narita Yusuke.  Open bandit dataset and pipeline: Towards realistic and reproducible off-policy evaluation.  _arXiv preprint arXiv:2008.07146_ , 2020.
  * Thomas and Brunskill [2016] Philip S. Thomas and Emma Brunskill.  Data-efficient off-policy policy evaluation for reinforcement learning.  In _Proceedings of the 33rd International Conference on International Conference on Machine Learning - Volume 48_ , ICML’16, page 2139–2148. JMLR.org, 2016.
  * Xie et al. [2019] Tengyang Xie, Yifei Ma, and Yu-Xiang Wang.  Towards optimal off-policy evaluation for reinforcement learning with marginalized importance sampling.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 32. Curran Associates, Inc., 2019.  URL https://proceedings.neurips.cc/paper/2019/file/4ffb0d2ba92f664c2281970110a2e071-Paper.pdf.
  * Kallus and Uehara [2022] Nathan Kallus and Masatoshi Uehara.  Double reinforcement learning for efficient off-policy evaluation in markov decision processes.  _J. Mach. Learn. Res._ , 21(1), jun 2022.  ISSN 1532-4435.
  * Liu et al. [2020] Yao Liu, Pierre-Luc Bacon, and Emma Brunskill.  Understanding the curse of horizon in off-policy evaluation via conditional importance sampling.  In _Proceedings of the 37th International Conference on Machine Learning_ , ICML’20. JMLR.org, 2020.
  * Voloshin et al. [2021] Cameron Voloshin, Hoang Minh Le, Nan Jiang, and Yisong Yue.  Empirical study of off-policy policy evaluation for reinforcement learning.  In _Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 1)_ , 2021.  URL https://openreview.net/forum?id=IsK8iKbL-I.
  * Sachdeva et al. [2020] Noveen Sachdeva, Yi Su, and Thorsten Joachims.  Off-policy bandits with deficient support.  In _Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, KDD ’20, page 965–975, New York, NY, USA, 2020. Association for Computing Machinery.  ISBN 9781450379984.  doi: 10.1145/3394486.3403139.  URL https://doi.org/10.1145/3394486.3403139.
  * Swaminathan and Joachims [2015b] Adith Swaminathan and Thorsten Joachims.  The self-normalized estimator for counterfactual learning.  In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 28. Curran Associates, Inc., 2015b.  URL https://proceedings.neurips.cc/paper_files/paper/2015/file/39027dfad5138c9ca0c474d71db915c3-Paper.pdf.
  * London and Sandler [2019] Ben London and Ted Sandler.  Bayesian counterfactual risk minimization.  In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, _Proceedings of the 36th International Conference on Machine Learning_ , volume 97 of _Proceedings of Machine Learning Research_ , pages 4125–4133. PMLR, 09–15 Jun 2019.  URL https://proceedings.mlr.press/v97/london19a.html.
  * Fujimoto et al. [2021] Scott Fujimoto, David Meger, and Doina Precup.  A deep reinforcement learning approach to marginalized importance sampling with the successor representation.  In Marina Meila and Tong Zhang, editors, _Proceedings of the 38th International Conference on Machine Learning_ , volume 139 of _Proceedings of Machine Learning Research_ , pages 3518–3529. PMLR, 18–24 Jul 2021.  URL https://proceedings.mlr.press/v139/fujimoto21a.html.
  * Rowland et al. [2020] Mark Rowland, Anna Harutyunyan, Hado Hasselt, Diana Borsa, Tom Schaul, Rémi Munos, and Will Dabney.  Conditional importance sampling for off-policy learning.  In _International Conference on Artificial Intelligence and Statistics_ , pages 45–55. PMLR, 2020.
  * Meng and Wong [1996] Xiao-Li Meng and Wing Hung Wong.  Simulating ratios of normalizing constants via a simple identity: a theoretical exploration.  _Statistica Sinica_ , pages 831–860, 1996.
  * Brehmer et al. [2020] Johann Brehmer, Gilles Louppe, Juan Pavez, and Kyle Cranmer.  Mining gold from implicit models to improve likelihood-free inference.  _Proceedings of the National Academy of Sciences_ , 117(10):5242–5249, 2020.
  * Farajtabar et al. [2018b] Mehrdad Farajtabar, Mohammad Ghavamzadeh, and Yinlam Chow.  More robust doubly robust off-policy evaluation.  2018b.
  * Dua and Graff [2017] Dheeru Dua and Casey Graff.  UCI machine learning repository, 2017.  URL http://archive.ics.uci.edu/ml.
  * Deng [2012] Li Deng.  The mnist database of handwritten digit images for machine learning research.  _IEEE Signal Processing Magazine_ , 29(6):141–142, 2012.
  * Krizhevsky [2009] Alex Krizhevsky.  Learning multiple layers of features from tiny images.  Technical report, 2009.
  * Louizos et al. [2017] Christos Louizos, Uri Shalit, Joris Mooij, David Sontag, Richard Zemel, and Max Welling.  Causal effect inference with deep latent-variable models.  In _Proceedings of the 31st International Conference on Neural Information Processing Systems_ , NIPS’17, page 6449–6459, Red Hook, NY, USA, 2017. Curran Associates Inc.  ISBN 9781510860964.
  * Schulman et al. [2017] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov.  Proximal policy optimization algorithms, 2017.
  * Lambert et al. [2022] Nathan Lambert, Louis Castricato, Leandro von Werra, and Alex Havrilla.  Illustrating reinforcement learning from human feedback (rlhf).  _Hugging Face Blog_ , 2022.  https://huggingface.co/blog/rlhf.
  * Lin et al. [2020] Junhong Lin, Alessandro Rudi, Lorenzo Rosasco, and Volkan Cevher.  Optimal rates for spectral algorithms with least-squares regression over hilbert spaces.  _Applied and Computational Harmonic Analysis_ , 48(3):868–890, 2020.  ISSN 1063-5203.  doi: https://doi.org/10.1016/j.acha.2018.09.009.  URL https://www.sciencedirect.com/science/article/pii/S1063520318300174.
  * Robins [1986] James Robins.  A new approach to causal inference in mortality studies with a sustained exposure period—application to control of the healthy worker survivor effect.  _Mathematical Modelling_ , 7(9):1393–1512, 1986\.  ISSN 0270-0255.  doi: https://doi.org/10.1016/0270-0255(86)90088-6.  URL https://www.sciencedirect.com/science/article/pii/0270025586900886.
  * Breiman [2001] Leo Breiman.  Random forests.  _Machine Learning_ , 45(1):5–32, 2001.  doi: 10.1023/A:1010933404324.  URL https://doi.org/10.1023/A:1010933404324.
  * Newey and Robins [2018] Whitney K. Newey and James R. Robins.  Cross-fitting and fast remainder rates for semiparametric estimation, 2018\.  URL https://arxiv.org/abs/1801.09138.

##  Appendix A Proofs

###### Proof of Lemma 3.1.

First, we express the weights $w(y)$ as the conditional expectation as
follows:

$\displaystyle w(y)$ $\displaystyle=\frac{p_{\pi^{*}}(y)}{p_{\pi^{b}}(y)}$
$\displaystyle=\int_{{\mathcal{X}},\mathcal{A}}\frac{p_{\pi^{*}}(x,a,y)}{p_{\pi^{b}}(y)}\,\mathrm{d}a\,\mathrm{d}x$
$\displaystyle=\int_{{\mathcal{X}},\mathcal{A}}\frac{p_{\pi^{*}}(x,a,y)}{p_{\pi^{b}}(y)}\,\frac{p_{\pi^{b}}(x,a\mid
y)}{p_{\pi^{b}}(x,a\mid y)}\,\mathrm{d}a\,\mathrm{d}x$
$\displaystyle=\int_{{\mathcal{X}},\mathcal{A}}\frac{p_{\pi^{*}}(x,a,y)}{p_{\pi^{b}}(x,a,y)}\,p_{\pi^{b}}(x,a\mid
y)\,\mathrm{d}a\,\mathrm{d}x$
$\displaystyle=\int_{{\mathcal{X}},\mathcal{A}}\rho(a,x)\,p_{\pi^{b}}(x,a\mid
y)\,\mathrm{d}a\,\mathrm{d}x$
$\displaystyle=\mathbb{E}_{\pi^{b}}[\rho(A,X)\mid Y=y],$

where
$\rho(a,x)=\frac{p_{\pi^{*}}(x,a,y)}{p_{\pi^{b}}(x,a,y)}=\frac{\pi^{*}(a\mid
x)}{\pi^{b}(a\mid x)}$. Since conditional expectations can be defined as the
solution of regression problem, the result follows. ∎

###### Proof of Proposition 3.2.

We have

$\displaystyle\textup{D}_{f}\left(p_{\pi^{*}}(x,a,y)\,||\,p_{\pi^{b}}(x,a,y)\right)$
$\displaystyle=\mathbb{E}_{\pi^{b}}\left[f\left(\frac{p_{\pi^{*}}(X,A,Y)}{p_{\pi^{b}}(X,A,Y)}\right)\right]$
$\displaystyle=\mathbb{E}_{\pi^{b}}\left[f\left(\frac{\pi^{*}(A\mid
X)}{\pi^{b}(A\mid X)}\right)\right]$
$\displaystyle=\mathbb{E}_{\pi^{b}}\left[\mathbb{E}_{\pi^{b}}\left[f\left(\frac{\pi^{*}(A\mid
X)}{\pi^{b}(A\mid X)}\right)\Bigg{|}Y\right]\right]$
$\displaystyle\geq\mathbb{E}_{\pi^{b}}\left[f\left(\mathbb{E}_{\pi^{b}}\left[\frac{\pi^{*}(A\mid
X)}{\pi^{b}(A\mid X)}\Bigg{|}Y\right]\right)\right]\quad\text{(Jensen's
inequality)}$
$\displaystyle=\mathbb{E}_{\pi^{b}}\left[f\left(\frac{p_{\pi^{*}}(Y)}{p_{\pi^{b}}(Y)}\right)\right]$
$\displaystyle=\textup{D}_{f}\left(p_{\pi^{*}}(y)\,||\,p_{\pi^{b}}(y)\right).$

∎

###### Proof of Proposition 3.3.

Since
$\mathbb{E}_{\pi^{b}}[\hat{\theta}_{\textup{IPW}}]=\mathbb{E}_{\pi^{b}}[\hat{\theta}_{\textup{MR}}]=\mathbb{E}_{\pi^{*}}[Y]$,
we have that,

$\displaystyle\textup{Var}_{\pi^{b}}[\hat{\theta}_{\textup{IPW}}]-\textup{Var}_{\pi^{b}}[\hat{\theta}_{\textup{MR}}]$
$\displaystyle=\mathbb{E}_{\pi^{b}}[\hat{\theta}_{\textup{IPW}}]^{2}-\mathbb{E}_{\pi^{b}}[\hat{\theta}_{\textup{MR}}]^{2}$
$\displaystyle=\frac{1}{n}\left(\mathbb{E}_{\pi^{b}}\left[\rho(A,X)^{2}\,Y^{2}\right]-\mathbb{E}_{\pi^{b}}\left[w(Y)^{2}\,Y^{2}\right]\right)$
$\displaystyle=\frac{1}{n}\left(\mathbb{E}_{\pi^{b}}\left[\mathbb{E}_{\pi^{b}}[\rho(A,X)^{2}\mid
Y]\,Y^{2}\right]-\mathbb{E}_{\pi^{b}}\left[w(Y)^{2}\,Y^{2}\right]\right)$
$\displaystyle=\frac{1}{n}\left(\mathbb{E}_{\pi^{b}}\left[\mathbb{E}_{\pi^{b}}[\rho(A,X)^{2}\mid
Y]\,Y^{2}\right]-\mathbb{E}_{\pi^{b}}\left[\mathbb{E}_{\pi^{b}}[\rho(A,X)\mid
Y]^{2}\,Y^{2}\right]\right)$
$\displaystyle=\frac{1}{n}\mathbb{E}_{\pi^{b}}\left[\textup{Var}_{\pi^{b}}\left[\rho(A,X)\mid
Y\right]\,Y^{2}\right].$

In the second last step above, we use the fact that
$w(y)=\mathbb{E}_{\pi^{b}}[\rho(A,X)\mid Y=y]$. ∎

###### Proof of Proposition 3.4.

Let $\hat{\mu}(a,x)\approx\mathbb{E}[Y\mid X=x,A=a]$ denote the outcome model
in DR estimator. Then, using multiple applications of the law of total
variance we get that

$\displaystyle n\,\textup{Var}_{\pi^{b}}[\hat{\theta}_{\textup{DR}}]$
$\displaystyle=\textup{Var}_{\pi^{b}}\left[\rho(A,X)\,(Y-\hat{\mu}(A,X))+\sum_{a^{\prime}\in\mathcal{A}}\hat{\mu}(a^{\prime},X)\,\pi^{*}(a^{\prime}\mid
X)\right]$
$\displaystyle=\textup{Var}_{\pi^{b}}\left[\rho(A,X)\,(Y-\hat{\mu}(A,X))+\mathbb{E}_{\pi^{*}}[\hat{\mu}(A,X)\mid
X]\right]$
$\displaystyle=\mathbb{E}_{\pi^{b}}[\textup{Var}_{\pi^{b}}[\rho(A,X)\,(Y-\hat{\mu}(A,X))+\mathbb{E}_{\pi^{*}}[\hat{\mu}(A,X)\mid
X]\mid X,A]]$
$\displaystyle\quad+\textup{Var}_{\pi^{b}}[\mathbb{E}_{\pi^{b}}[\rho(A,X)\,(Y-\hat{\mu}(A,X))+\mathbb{E}_{\pi^{*}}[\hat{\mu}(A,X)\mid
X]\mid X,A]]$
$\displaystyle=\mathbb{E}_{\pi^{b}}[\rho(A,X)^{2}\textup{Var}[Y\mid X,A]]$
$\displaystyle\quad+\textup{Var}_{\pi^{b}}[\mathbb{E}_{\pi^{b}}[\rho(A,X)\,(Y-\hat{\mu}(A,X))+\mathbb{E}_{\pi^{b}}[\rho(A,X)\,\hat{\mu}(A,X)\mid
X]\mid X,A]]$
$\displaystyle=\mathbb{E}_{\pi^{b}}[\rho(A,X)^{2}\textup{Var}[Y\mid X,A]]$
$\displaystyle\quad+\textup{Var}_{\pi^{b}}[\rho(A,X)\,(\mu(A,X)-\hat{\mu}(A,X))+\mathbb{E}_{\pi^{b}}[\rho(A,X)\,\hat{\mu}(A,X)\mid
X]]$ $\displaystyle=\mathbb{E}_{\pi^{b}}[\rho(A,X)^{2}\textup{Var}[Y\mid
X,A]]$
$\displaystyle\quad+\textup{Var}_{\pi^{b}}[\mathbb{E}_{\pi^{b}}[\rho(A,X)\,(\mu(A,X)-\hat{\mu}(A,X))+\mathbb{E}_{\pi^{b}}[\rho(A,X)\,\hat{\mu}(A,X)\mid
X]\mid X]]$
$\displaystyle\quad+\mathbb{E}_{\pi^{b}}[\textup{Var}_{\pi^{b}}[\rho(A,X)\,(\mu(A,X)-\hat{\mu}(A,X))+\mathbb{E}_{\pi^{b}}[\rho(A,X)\,\hat{\mu}(A,X)\mid
X]\mid X]]$
$\displaystyle=\mathbb{E}_{\pi^{b}}[\rho(A,X)^{2}\textup{Var}[Y\mid
X,A]]+\textup{Var}_{\pi^{b}}[\mathbb{E}_{\pi^{b}}[\rho(A,X)\,\mu(A,X)\mid X]]$
$\displaystyle\quad+\mathbb{E}_{\pi^{b}}[\textup{Var}_{\pi^{b}}[\rho(A,X)\,(\mu(A,X)-\hat{\mu}(A,X))\mid
X]]$ $\displaystyle\geq\mathbb{E}_{\pi^{b}}[\rho(A,X)^{2}\textup{Var}[Y\mid
X,A]]+\textup{Var}_{\pi^{b}}[\mathbb{E}_{\pi^{b}}[\rho(A,X)\,\mu(A,X)\mid
X]].$

Using this, we get that

$\displaystyle
n(\textup{Var}_{\pi^{b}}[\hat{\theta}_{\textup{DR}}]-\textup{Var}_{\pi^{b}}[\hat{\theta}_{\textup{MR}}])$
$\displaystyle\quad\geq\mathbb{E}_{\pi^{b}}[\rho(A,X)^{2}\textup{Var}[Y\mid
X,A]]+\textup{Var}_{\pi^{b}}\left[\mathbb{E}_{\pi^{b}}[\rho(A,X)\,\mu(A,X)\mid
X]\right]-\textup{Var}_{\pi^{b}}[w(Y)\,Y].$

Again, using the law of total variance,

$\displaystyle\textup{Var}_{\pi^{b}}[\rho(A,X)\,Y]$
$\displaystyle=\mathbb{E}_{\pi^{b}}[\textup{Var}_{\pi^{b}}[\rho(A,X)\,Y\mid
X,A]]+\textup{Var}_{\pi^{b}}[\mathbb{E}_{\pi^{b}}[\rho(A,X)\,Y\mid X,A]]$
$\displaystyle=\mathbb{E}_{\pi^{b}}[\rho(A,X)^{2}\textup{Var}[Y\mid
X,A]]+\textup{Var}_{\pi^{b}}[\rho(A,X)\,\mu(A,X)]$
$\displaystyle=\mathbb{E}_{\pi^{b}}[\rho(A,X)^{2}\textup{Var}[Y\mid
X,A]]+\textup{Var}_{\pi^{b}}\left[\mathbb{E}_{\pi^{b}}[\rho(A,X)\,\mu(A,X)\mid
X]\right]$
$\displaystyle\quad+\mathbb{E}_{\pi^{b}}\left[\textup{Var}_{\pi^{b}}[\rho(A,X)\,\mu(A,X)\mid
X]\right].$

Rearranging and substituting back into the expression earlier, we get that

$\displaystyle
n(\textup{Var}_{\pi^{b}}[\hat{\theta}_{\textup{DR}}]-\textup{Var}_{\pi^{b}}[\hat{\theta}_{\textup{MR}}])$
$\displaystyle\quad\geq\textup{Var}_{\pi^{b}}[\rho(A,X)\,Y]-\mathbb{E}_{\pi^{b}}\left[\textup{Var}_{\pi^{b}}[\rho(A,X)\,\mu(A,X)\mid
X]\right]-\textup{Var}_{\pi^{b}}[w(Y)\,Y].$

Now, from Proposition 3.3 we know that

$\displaystyle
n(\textup{Var}_{\pi^{b}}[\hat{\theta}_{\textup{IPW}}]-\textup{Var}_{\pi^{b}}[\hat{\theta}_{\textup{MR}}])=\textup{Var}_{\pi^{b}}[\rho(A,X)\,Y]-\textup{Var}_{\pi^{b}}[w(Y)\,Y]=\mathbb{E}_{\pi^{b}}\left[\textup{Var}_{\pi^{b}}\left[\rho(A,X)\mid
Y\right]\,Y^{2}\right].$

Therefore,

$\displaystyle
n(\textup{Var}_{\pi^{b}}[\hat{\theta}_{\textup{DR}}]-\textup{Var}_{\pi^{b}}[\hat{\theta}_{\textup{MR}}])$
$\displaystyle\quad\geq\mathbb{E}_{\pi^{b}}\left[\textup{Var}_{\pi^{b}}\left[\rho(A,X)\mid
Y\right]\,Y^{2}\right]-\mathbb{E}_{\pi^{b}}\left[\textup{Var}_{\pi^{b}}[\rho(A,X)\,\mu(A,X)\mid
X]\right]$
$\displaystyle\quad=\mathbb{E}_{\pi^{b}}\left[\textup{Var}_{\pi^{b}}\left[\rho(A,X)\,Y\mid
Y\right]-\textup{Var}_{\pi^{b}}[\rho(A,X)\,\mu(A,X)\mid X]\right].$

∎

###### Proof of Theorem 3.6.

This result follows straightforwardly from Proposition D.4 in Appendix D. ∎

###### Proof of Proposition 3.7.

$\displaystyle\textup{Bias}(\hat{\theta}_{\textup{IPW}})$
$\displaystyle=\mathbb{E}_{\pi^{b}}[\hat{\rho}(A,X)\,Y]-\mathbb{E}_{\pi^{*}}[Y]$
$\displaystyle=\mathbb{E}_{\pi^{b}}\left[\mathbb{E}_{\pi^{b}}[\hat{\rho}(A,X)\mid
Y]\,Y\right]-\mathbb{E}_{\pi^{*}}[Y]$
$\displaystyle=\mathbb{E}_{\pi^{b}}[\hat{w}(Y)\,Y]-\mathbb{E}_{\pi^{b}}[\epsilon\,Y]-\mathbb{E}_{\pi^{*}}[Y]$
$\displaystyle=\textup{Bias}(\hat{\theta}_{\textup{MR}})-\mathbb{E}_{\pi^{b}}[\epsilon\,Y].$

Next, to prove the variance result, we first use the law of total variance to
obtain

$\displaystyle\textup{Var}_{\pi^{b}}[\hat{\theta}_{\textup{IPW}}]$
$\displaystyle=\frac{1}{n}\textup{Var}_{\pi^{b}}[\hat{\rho}(A,X)\,Y]$
$\displaystyle=\frac{1}{n}\left(\textup{Var}_{\pi^{b}}[\mathbb{E}_{\pi^{b}}[\hat{\rho}(A,X)\,Y\mid
Y]]+\mathbb{E}_{\pi^{b}}[\textup{Var}_{\pi^{b}}[\hat{\rho}(A,X)\,Y\mid
Y]]\right)$
$\displaystyle=\frac{1}{n}\left(\textup{Var}_{\pi^{b}}[\tilde{w}(Y)\,Y]+\mathbb{E}_{\pi^{b}}[\textup{Var}_{\pi^{b}}[\hat{\rho}(A,X)\,Y\mid
Y]]\right).$

Moreover, using the fact that $\hat{w}(Y)=\tilde{w}(Y)+\epsilon$ we get that,

$\displaystyle\textup{Var}_{\pi^{b}}[\hat{\theta}_{\textup{MR}}]$
$\displaystyle=\frac{1}{n}\textup{Var}_{\pi^{b}}[\hat{w}(Y)\,Y]$
$\displaystyle=\frac{1}{n}\textup{Var}_{\pi^{b}}[\left(\tilde{w}(Y)+\epsilon\right)\,Y]$
$\displaystyle=\frac{1}{n}\left(\textup{Var}_{\pi^{b}}[\tilde{w}(Y)\,Y]+\textup{Var}_{\pi^{b}}[\epsilon\,Y]+2\,\textup{Cov}(\tilde{w}(Y)\,Y,\epsilon\,Y)\right).$

Putting together the two variance expressions derived above, we get that

$\displaystyle\textup{Var}_{\pi^{b}}[\hat{\theta}_{\textup{IPW}}]-\textup{Var}_{\pi^{b}}[\hat{\theta}_{\textup{MR}}]$
$\displaystyle\quad=\frac{1}{n}\left(\mathbb{E}_{\pi^{b}}[\textup{Var}_{\pi^{b}}[\hat{\rho}(A,X)\mid
Y]\,Y^{2}]-\textup{Var}_{\pi^{b}}[\epsilon\,Y]-2\,\textup{Cov}(\tilde{w}(Y)\,Y,\epsilon\,Y)\right).$

∎

##  Appendix B Comparison with extensions of the doubly robust estimator

In this section, we theoretically investigate the variance of MR against the
commonly used extensions of the DR estimator, namely Switch-DR [5] and DR with
Optimistic Shrinkage (DRos) [17]. At a high level, these estimators seek to
reduce the variance of the vanilla DR estimator by considering modified
importance weights, thereby trading off the variance for additional bias.
Below, we provide the explicit definitions of these estimators for
completeness.

##### Switch-DR estimator

The original DR estimator can still have a high variance when the importance
weights are large due to a large policy shift. Switch-DR [5] aims to
circumvent this problem by switching to DM when the importance weights are
large:

$\hat{\theta}_{\textup{SwitchDR}}\coloneqq\frac{1}{n}\sum_{i=1}^{n}\rho(a_{i},x_{i})\,(y_{i}-\hat{\mu}(a_{i},x_{i})){\mathbbm{1}}(\rho(a_{i},x_{i})\leq\tau)+\hat{\eta}(\pi^{*}),$

where $\tau\geq 0$ is a hyperparameter, $\hat{\mu}(a,x)\approx\mathbb{E}[Y\mid
X=x,A=a]$ is the outcome model, and

$\hat{\eta}(\pi^{*})=\frac{1}{n}\sum_{i=1}^{n}\sum_{a^{\prime}\in\mathcal{A}}\hat{\mu}(a^{\prime},x_{i})\pi^{*}(a^{\prime}\mid
x_{i})\approx\mathbb{E}_{\pi^{*}}[\hat{\mu}(A,X)]$

where $a_{i}^{*}\sim\pi^{*}(\cdot\mid x_{i})$.

##### Doubly Robust with Optimal Shrinkage (DRos)

DRos proposed by [17] uses new weights $\hat{\rho}_{\lambda}(a_{i},x_{i})$
which directly minimises sharp bounds on the MSE of the resulting estimator,

$\hat{\theta}_{\textup{DRos}}\coloneqq\frac{1}{n}\sum_{i=1}^{n}\hat{\rho}_{\lambda}(a_{i},x_{i})\,(y_{i}-\hat{\mu}(a_{i},x_{i}))+\hat{\eta}(\pi^{*}),$

where $\lambda\geq 0$ is a pre-defined hyperparameter and
$\hat{\rho}_{\lambda}$ is defined as

$\hat{\rho}_{\lambda}(a,x)\coloneqq\frac{\lambda}{\rho^{2}(a,x)+\lambda}\,\rho(a,x).$

When $\lambda=0$, $\hat{\rho}_{\lambda}(a,x)=0$ leads to DM, whereas as
$\lambda\rightarrow\infty$, $\hat{\rho}_{\lambda}(a,x)\rightarrow\rho(a,x)$
leading to DR.

More generally, both of these estimators can be written as follows:

$\hat{\theta}_{\textup{DR}}^{\tilde{\rho}}\coloneqq\frac{1}{n}\sum_{i=1}^{n}\tilde{\rho}(a_{i},x_{i})\,(y_{i}-\hat{\mu}(a_{i},x_{i}))+\hat{\eta}(\pi^{*}).$

Here, when
$\tilde{\rho}(a,x)=\rho(a,x){\mathbbm{1}}(\rho(a_{i},x_{i})\leq\tau)$, we
recover the Switch-DR estimator and likewise when
$\tilde{\rho}(a,x)=\hat{\rho}_{\lambda}(a,x)$, we recover DRos.

###  B.1 Variance comparison with the DR extensions

Next, we provide a theoretical result comparing the variance of the MR
estimator with these DR extension methods.

######  Proposition B.1.

When the weights $w(y)$ are known exactly and the outcome model is exact,
i.e., $\hat{\mu}(a,x)=\mu(a,x)=\mathbb{E}[Y\mid X=x,A=a]$ in the DR estimator
$\hat{\theta}_{\textup{DR}}^{\tilde{\rho}}$ defined above,

$\displaystyle\textup{Var}_{\pi^{b}}[\hat{\theta}_{\textup{DR}}^{\tilde{\rho}}]-\textup{Var}_{\pi^{b}}[\hat{\theta}_{\textup{MR}}]\geq\frac{1}{n}\mathbb{E}_{\pi^{b}}\left[\textup{Var}_{\pi^{b}}\left[\rho(A,X)\mid
Y\right]\,Y^{2}-\textup{Var}_{\pi^{b}}\left[\rho(A,X)\mu(A,X)\mid
X\right]\right]-\Delta,$

where
$\Delta\coloneqq\frac{1}{n}\mathbb{E}_{\pi^{b}}\left[(\rho^{2}(A,X)-\tilde{\rho}^{2}(A,X))\,\textup{Var}[Y\mid
X,A]\right]$.

###### Proof of Proposition B.1.

Using the fact that $\hat{\mu}(a,x)=\mu(a,x)$ and the law of total variance,
we get that

$\displaystyle
n\,\textup{Var}_{\pi^{b}}[\hat{\theta}_{\textup{DR}}^{\tilde{\rho}}]$
$\displaystyle=\textup{Var}_{\pi^{b}}[\tilde{\rho}(A,X)\,(Y-\hat{\mu}(A,X))+\sum_{a^{\prime}\in\mathcal{A}}\hat{\mu}(a^{\prime},X)\pi^{*}(a^{\prime}\mid
X)]$
$\displaystyle=\textup{Var}_{\pi^{b}}[\tilde{\rho}(A,X)\,(Y-\hat{\mu}(A,X))+\mathbb{E}_{\pi^{*}}[\hat{\mu}(A,X)\mid
X]]$
$\displaystyle=\textup{Var}_{\pi^{b}}[\tilde{\rho}(A,X)\,(Y-\mu(A,X))+\mathbb{E}_{\pi^{*}}[\mu(A,X)\mid
X]]$
$\displaystyle=\textup{Var}_{\pi^{b}}[\mathbb{E}_{\pi^{b}}[\tilde{\rho}(A,X)\,(Y-\mu(A,X))+\mathbb{E}_{\pi^{*}}[\mu(A,X)\mid
X]\mid X,A]]$
$\displaystyle\qquad+\mathbb{E}_{\pi^{b}}[\textup{Var}_{\pi^{b}}[\tilde{\rho}(A,X)\,(Y-\mu(A,X))+\mathbb{E}_{\pi^{*}}[\mu(A,X)\mid
X]\mid X,A]]$
$\displaystyle=\textup{Var}_{\pi^{b}}[\mathbb{E}_{\pi^{*}}[\mu(A,X)\mid
X]]+\mathbb{E}_{\pi^{b}}[\tilde{\rho}^{2}(A,X)\textup{Var}[Y\mid X,A]]$
$\displaystyle=\textup{Var}_{\pi^{b}}[\mathbb{E}_{\pi^{*}}[\mu(A,X)\mid
X]]+\mathbb{E}_{\pi^{b}}[\rho^{2}(A,X)\,\textup{Var}[Y\mid X,A]]$
$\displaystyle\qquad+\underbrace{\mathbb{E}_{\pi^{b}}[(\tilde{\rho}^{2}(A,X)-\rho^{2}(A,X))\,\textup{Var}[Y\mid
X,A]]}_{-n\,\Delta}$
$\displaystyle=\textup{Var}_{\pi^{b}}[\mathbb{E}_{\pi^{b}}[\rho(A,X)\,\mu(A,X)\mid
X]]+\mathbb{E}_{\pi^{b}}[\rho^{2}(A,X)\,\textup{Var}[Y\mid X,A]]-n\,\Delta.$

Again, using the law of total variance we can rewrite the second term on the
RHS above as,

$\displaystyle\mathbb{E}_{\pi^{b}}[\rho^{2}(A,X)\,\textup{Var}[Y\mid X,A]]$
$\displaystyle\quad=\textup{Var}_{\pi^{b}}[\rho(A,X)\,Y]-\textup{Var}_{\pi^{b}}[\rho(A,X)\,\mu(A,X)]$
$\displaystyle\quad=\textup{Var}_{\pi^{b}}[\mathbb{E}_{\pi^{b}}[\rho(A,X)\mid
Y]\,Y]+\mathbb{E}_{\pi^{b}}[\textup{Var}_{\pi^{b}}[\rho(A,X)\mid Y]\,Y^{2}]$
$\displaystyle\qquad-\textup{Var}_{\pi^{b}}[\rho(A,X)\,\mu(A,X)]$
$\displaystyle\quad=\textup{Var}_{\pi^{b}}[w(Y)\,Y]+\mathbb{E}_{\pi^{b}}[\textup{Var}_{\pi^{b}}[\rho(A,X)\mid
Y]\,Y^{2}]-\textup{Var}_{\pi^{b}}[\rho(A,X)\,\mu(A,X)]$
$\displaystyle\quad=n\,\textup{Var}_{\pi^{b}}[\hat{\theta}_{\textup{MR}}]+\mathbb{E}_{\pi^{b}}[\textup{Var}_{\pi^{b}}[\rho(A,X)\mid
Y]\,Y^{2}]-\textup{Var}_{\pi^{b}}[\rho(A,X)\,\mu(A,X)].$

Putting this together, we get that

$\displaystyle
n\,\textup{Var}_{\pi^{b}}[\hat{\theta}_{\textup{DR}}^{\tilde{\rho}}]$
$\displaystyle\quad=n\,\textup{Var}_{\pi^{b}}[\hat{\theta}_{\textup{MR}}]+\mathbb{E}_{\pi^{b}}[\textup{Var}_{\pi^{b}}[\rho(A,X)\mid
Y]\,Y^{2}]-\textup{Var}_{\pi^{b}}[\rho(A,X)\,\mu(A,X)]$
$\displaystyle\qquad+\textup{Var}_{\pi^{b}}[\mathbb{E}_{\pi^{b}}[\rho(A,X)\,\mu(A,X)\mid
X]]-n\,\Delta$
$\displaystyle\quad=n\,\textup{Var}_{\pi^{b}}[\hat{\theta}_{\textup{MR}}]+\mathbb{E}_{\pi^{b}}[\textup{Var}_{\pi^{b}}[\rho(A,X)\mid
Y]\,Y^{2}]-\mathbb{E}_{\pi^{b}}[\textup{Var}_{\pi^{b}}[\rho(A,X)\,\mu(A,X)\mid
X]]-n\,\Delta,$

where in the last step above, we again use the law of total variance.
Rearranging the above leads us to the result. ∎

##### Intuition

Note that for both of the DR extensions under consideration, the modified
ratios $\tilde{\rho}(a,x)$ satisfy $0\leq\tilde{\rho}(a,x)\leq\rho(a,x)$ and
hence $\Delta\geq 0$ (using the definition of $\Delta$ in Proposition B.1).
When the modified ratios $\tilde{\rho}(a,x)$ are ‘close’ to the true policy
ratios $\rho(a,x)$, then using the definition of $\Delta$, we have that
$\Delta\approx 0$. In this case, the result above provides a similar intuition
to Proposition 3.4 in the main text. Specifically, in this case we have that
if $\textup{Var}_{\pi^{b}}\left[\rho(A,X)\,Y\mid Y\right]$ is greater than
$\textup{Var}_{\pi^{b}}\left[\rho(A,X)\,\mu(A,X)\mid X\right]$ on average, the
variance of the MR estimator will be less than that of the DR extension under
consideration. Intuitively, this will occur when the dimension of context
space ${\mathcal{X}}$ is high because in this case the conditional variance
over $X$ and $A$, $\textup{Var}_{\pi^{b}}\left[\rho(A,X)\,Y\mid Y\right]$ is
likely to be greater than the conditional variance over $A$,
$\textup{Var}_{\pi^{b}}\left[\rho(A,X)\,\mu(A,X)\mid X\right]$.

In contrast if the modified ratios $\tilde{\rho}(a,x)$ differ substantially
from $\rho(a,x)$, then $\Delta$ will be large and the variance of MR may be
higher than that of the resulting DR extension. However, this comes at the
cost of significantly higher bias in the DR extension and consequently MSE of
the DR extension will be high in this case.

##  Appendix C Weight estimation error

In this section, we theoretically investigate the effects of using the
estimated importance weights $\hat{w}(y)$ rather than $\hat{\rho}(a,x)$ on the
bias and variance of the resulting OPE estimator. Further to our discussion in
Section 3.1.2, we focus in this section on the approximation error when using
a wide neural network to estimate the weights $\hat{w}(y)$. To this end, we
use recent results regarding the generalization of wide neural networks [19]
to show that the estimation error of the approximation step (ii) in the
Section 3.1.2 declines with increasing number of training data when
$\hat{w}(y)$ is estimated using wide neural networks. Before providing the
main result, we explicitly lay out the assumptions needed.

###  C.1 Using wide neural networks to approximate the weights $\hat{w}(y)$

######  Assumption C.1.

Let $\tilde{w}(y)\coloneqq\mathbb{E}_{\pi^{b}}[\hat{\rho}(A,X)\mid Y=y].$
Suppose $\tilde{w}\in\mathcal{H}_{1}$ and $||\tilde{w}||_{\mathcal{H}_{1}}\leq
R$ for some constant $R$, where $\mathcal{H}_{1}$ is the reproducing kernel
Hilbert space (RKHS) associated with the Neural Tangent Kernel $K_{1}$
associated with 2 layer neural network defined on $\mathbb{R}$.

######  Assumption C.2.

There exists an $M\in[0,\infty)$ such that $\mathbb{P}_{\pi^{b}}(|Y|\leq
M)=1$.

######  Assumption C.3.

$\hat{\rho}(a_{i},x_{i})$ satisfies

$\displaystyle\hat{\rho}(a_{i},x_{i})=\tilde{w}(y_{i})+\eta_{i},$

where $\eta_{i}\overset{\textup{iid}}{\sim}\mathcal{N}(0,\sigma^{2})$ for some
$\sigma>0$.

######  Theorem C.4.

Suppose that the IPW and MR estimators are defined as,

$\tilde{\theta}_{\textup{IPW}}\coloneqq\frac{1}{n}\sum_{i=1}^{n}\hat{\rho}(a_{i},x_{i})\,y_{i},\quad\text{and
}\quad\tilde{\theta}_{\textup{MR}}\coloneqq\frac{1}{n}\sum_{i=1}^{n}\hat{w}_{m}(y_{i})\,y_{i},$

where $\hat{w}_{m}(y)$ is obtained by regressing to the estimated policy
ratios $\hat{\rho}(a,x)$ using $m$ i.i.d. training samples
$\mathcal{D}_{\textup{tr}}\coloneqq\\{(x^{\textup{tr}}_{i},a^{\textup{tr}}_{i},y^{\textup{tr}}_{i})\\}_{i=1}^{m}$,
i.e., by minimising the loss

$\displaystyle\mathcal{L}(\phi)=\mathbb{E}_{(X,A,Y)\sim\mathcal{D}_{\textup{tr}}}\left[\left(\hat{\rho}(A,X)-f_{\phi}(Y)\right)^{2}\right].$

Suppose Assumptions C.1-C.3 hold, then for any given $\delta\in(0,1)$, if
$f_{\phi}$ is a two-layer neural network with width $k$ that is sufficiently
large and stops the gradient flow at time $t_{*}\propto m^{2/3}$, then for
sufficiently large $m$, there exists a constant $C_{1}$ independent of
$\delta$ and $m$, such that

$|\textup{Bias}(\tilde{\theta}_{\textup{MR}})-\textup{Bias}(\tilde{\theta}_{\textup{IPW}})|\leq
C_{1}\,m^{-1/3}\log{\frac{6}{\delta}}$

holds with probability at least $(1-\delta)(1-o_{k}(1))$. Moreover, there
exist constants $C_{2},C_{3}$ independent of $\delta$ and $m$ such that

$\displaystyle
n(\textup{Var}_{\pi^{b}}[\tilde{\theta}_{\textup{IPW}}]-\textup{Var}_{\pi^{b}}[\tilde{\theta}_{\textup{MR}}])\geq\underbrace{\mathbb{E}_{\pi^{b}}[\textup{Var}_{\pi^{b}}[\hat{\rho}(A,X)\,Y\mid
Y]]}_{\geq
0}-C_{2}\,m^{-2/3}\,\log^{2}{\frac{6}{\delta}}-C_{3}\,m^{-1/3}\,\log{\frac{6}{\delta}}$

holds with probability at least $(1-\delta)(1-o_{k}(1))$. Here, the randomness
comes from the joint distribution of training samples and random
initialization of parameters in the neural network $f_{\phi}$.

###### Proof of Theorem C.4.

The proof of this theorem relies on [19, Theorem 4.1]. Recall the definition
$\tilde{w}(Y)\coloneqq\mathbb{E}_{\pi^{b}}[\hat{\rho}(A,X)\mid Y]$. We can
rewrite our setup in the setting of [19, Theorem 4.1], by relabelling
$\hat{\rho}(a,x)$ in our setup as $y$ in their setup and relabelling $y$ in
our setup as $x$ in their setup. Then, given $\delta\in(0,1)$, from [19,
Theorem 4.1], it follows that under Assumptions C.1-C.3 that there exists a
constant $C$ independent of $\delta$ and $m$, such that

$\displaystyle\mathbb{E}_{\pi^{b}}[\epsilon^{2}]\leq
C\,m^{-2/3}\,\log^{2}{\frac{6}{\delta}}$ (5)

holds with probability at least $(1-\delta)(1-o_{k}(1))$, where
$\epsilon\coloneqq\hat{w}_{m}(Y)-\tilde{w}(Y)$. Recall from Proposition 3.7
that

$|\textup{Bias}(\tilde{\theta}_{\textup{MR}})-\textup{Bias}(\tilde{\theta}_{\textup{IPW}})|=|\mathbb{E}_{\pi^{b}}[\epsilon\,Y]|.$

From this it follows using Cauchy-Schwarz inequality that,

$\displaystyle|\textup{Bias}(\tilde{\theta}_{\textup{MR}})-\textup{Bias}(\tilde{\theta}_{\textup{IPW}})|$
$\displaystyle=|\mathbb{E}_{\pi^{b}}[\epsilon\,Y]|\leq\left(\mathbb{E}_{\pi^{b}}[\epsilon^{2}]\mathbb{E}_{\pi^{b}}[Y^{2}]\right)^{1/2}.$

Combining the above with Eqn. (5), it follows that,

$\displaystyle|\textup{Bias}(\tilde{\theta}_{\textup{MR}})-\textup{Bias}(\tilde{\theta}_{\textup{IPW}})|\leq
C^{1/2}\,m^{-1/3}\,\log{\frac{6}{\delta}}(\mathbb{E}_{\pi^{b}}[Y^{2}])^{1/2}=C_{1}\,m^{-1/3}\,\log{\frac{6}{\delta}}$

holds with probability at least $(1-\delta)(1-o_{k}(1))$, where
$C_{1}=C^{1/2}\,(\mathbb{E}_{\pi^{b}}[Y^{2}])^{1/2}$.

Next, to prove the variance result, we recall from Proposition 3.7 that

$\displaystyle
n(\textup{Var}_{\pi^{b}}[\tilde{\theta}_{\textup{IPW}}]-\textup{Var}_{\pi^{b}}[\tilde{\theta}_{\textup{MR}}])$
$\displaystyle=\mathbb{E}_{\pi^{b}}[\textup{Var}_{\pi^{b}}[\hat{\rho}(A,X)\mid
Y]\,Y^{2}]-\textup{Var}_{\pi^{b}}[\epsilon\,Y]-2\,\textup{Cov}(\epsilon\,Y,\tilde{w}(Y)\,Y)$

Now note that, under Assumption C.2,

$\displaystyle\textup{Var}_{\pi^{b}}[\epsilon\,Y]\leq\mathbb{E}_{\pi^{b}}[(\epsilon\,Y)^{2}]\leq
M^{2}\mathbb{E}_{\pi^{b}}[\epsilon^{2}]\leq
C\,M^{2}\,m^{-2/3}\,\log^{2}{\frac{6}{\delta}}=C_{2}\,m^{-2/3}\,\log^{2}{\frac{6}{\delta}},$

holds with probability at least $(1-\delta)(1-o_{k}(1))$, where
$C_{2}=C\,M^{2}$. Similarly, we have that with probability at least
$(1-\delta)(1-o_{k}(1))$,

$\displaystyle|\textup{Cov}(\epsilon\,Y,\tilde{w}(Y)\,Y)|$
$\displaystyle=|\mathbb{E}_{\pi^{b}}[\epsilon\,\tilde{w}(Y)\,Y^{2}]-\mathbb{E}_{\pi^{b}}[\epsilon\,Y]\mathbb{E}_{\pi^{b}}[\tilde{w}(Y)\,Y]|$
$\displaystyle\leq|\mathbb{E}_{\pi^{b}}[\epsilon\,\tilde{w}(Y)\,Y^{2}]|+|\mathbb{E}_{\pi^{b}}[\epsilon\,Y]\mathbb{E}_{\pi^{b}}[\tilde{w}(Y)\,Y]|$
$\displaystyle\leq\left(\mathbb{E}_{\pi^{b}}[\epsilon^{2}]\mathbb{E}_{\pi^{b}}[\tilde{w}(Y)^{2}\,Y^{4}]\right)^{1/2}+(\mathbb{E}_{\pi^{b}}[\epsilon^{2}]\mathbb{E}_{\pi^{b}}[Y^{2}])^{1/2}|\mathbb{E}_{\pi^{b}}[\tilde{w}(Y)\,Y]|$
$\displaystyle=(\mathbb{E}_{\pi^{b}}[\epsilon^{2}])^{1/2}\,\left((\mathbb{E}_{\pi^{b}}[\tilde{w}(Y)^{2}\,Y^{4}])^{1/2}+(\mathbb{E}_{\pi^{b}}[Y^{2}])^{1/2}\,|\mathbb{E}_{\pi^{b}}[\tilde{w}(Y)\,Y]|\right)$
$\displaystyle\leq C_{3}\,m^{-1/3}\,\log{\frac{6}{\delta}},$

where
$C_{3}=C\,(\mathbb{E}_{\pi^{b}}[\tilde{w}(Y)^{2}\,Y^{4}])^{1/2}+(\mathbb{E}_{\pi^{b}}[Y^{2}])^{1/2}\,|\mathbb{E}_{\pi^{b}}[\tilde{w}(Y)\,Y]|$,
and we use Cauchy-Schwarz inequality in the third step above. Putting this
together, we obtain the required result. ∎

##### Intuition

This theorem shows that as the number of training samples $m$ increases, the
biases of MR and IPW estimators become roughly equal, whereas the variance of
MR estimator falls below that of the IPW estimator. The empirical results
shown in Appendix F.2 are consistent with this result. Moreover, in Theorem
C.4, the estimated policy ratio $\hat{\rho}(a,x)$ is fixed for increasing $m$,
i.e., we do not update $\hat{\rho}(a,x)$ as more training data becomes
available. While this may seem as a disadvantage for the IPW estimator, we
point out that the result also holds when the policy ratio is exact (i.e.,
$\hat{\rho}(a,x)=\rho(a,x)$) and hence the IPW estimator is unbiased.

##### Relaxing Assumption C.3

[19][Theorem 4.1] suppose that the data has the relationship shown in
Assumption C.3. However, the theorem relies on Corollary 4.4 in [43], which
requires a strictly weaker assumption (Assumption 1 in [43]). Therefore, we
can relax Assumption C.3 to the following assumption.

######  Assumption C.5.

There exists positive constants $Q$ and $M$ such that for all $l\geq 2$ with
$l\in\mathbb{N}$

$\mathbb{E}_{\pi^{b}}[\hat{\rho}(A,X)^{l}\mid
Y]\leq\frac{1}{2}\,l!\,M^{l-2}\,Q^{2}$

$p_{\pi^{b}}$-almost surely.

It is easy to check that Assumption C.5 is strictly weaker than Assumption
C.3, and is also satisfied if the policy ratio $\hat{\rho}(A,X)$ is almost
surely bounded. For simplicity, we use the stronger assumption in our
Proposition C.4.

##  Appendix D Generalised formulation of the MIPS estimator [14]

As described in Section 3.1.1, the MIPS estimator proposed by [14] assumes the
existence of _action embeddings_ $E$ which summarise all relevant information
about the action $A$, and achieves a lower variance than the IPW estimator. To
achieve this, the MIPS estimator only considers the shift in the distribution
of $(X,E)$ as a result of policy shift, instead of considering the shift in
$(X,A)$ (as in IPW estimator). In this section, we show that this idea can be
generalised to instead consider general representations $R$ of the context-
action pair $(X,A)$, which encapsulate all relevant information about the
outcome $Y$. The MIPS estimator is a special case of this generalised setting
where the representation $R$ is of the form $(X,E)$.

##### Generalised MIPS (G-MIPS) estimator

Suppose that there exists an embedding $R$ of the context-action pair $(X,A)$,
with the Bayesian network shown in Figure 3. Here, $R$ may be a lower-
dimensional representation of the $(X,A)$ pair which contains all the
information necessary to predict the outcome $Y$. This corresponds to the
following conditional independence assumption:

######  Assumption D.1.

The context-action pair $(X,A)$ has no direct effect on the outcome $Y$ given
$R$, i.e., $Y\perp\\!\\!\\!\perp(X,A)\mid R$.

$(X,A)$ $R$$Y$ Figure 3: Bayesian network corresponding to Assumption D.1.

As illustrated in Figure 3, Assumption D.1 means that the embedding $R$ fully
mediates every possible effect of $(X,A)$ on $Y$. The generalised MIPS
estimator $\hat{\theta}_{\textup{G-MIPS}}$ of target policy value,
$\mathbb{E}_{\pi^{*}}[Y]$, is defined as

$\hat{\theta}_{\textup{G-MIPS}}\coloneqq\frac{1}{n}\sum_{i=1}^{n}\frac{p_{\pi^{*}}(r_{i})}{p_{\pi^{b}}(r_{i})}\,y_{i},$

where $p_{\pi^{b}}(r)$ denote the density of $R$ under the behaviour policy
(likewise for $p_{\pi^{*}}(r)$). Under assumption D.1,
$\hat{\theta}_{\textup{G-MIPS}}$ provides an unbiased estimator of target
policy value. Similar to Lemma 3.1, the density ratio
$\frac{p_{\pi^{*}}(r)}{p_{\pi^{b}}(r)}$ can be estimated by solving the
regression problem

$\displaystyle\arg\min_{f}\mathbb{E}_{\pi^{b}}\left(\frac{\pi^{*}(A\mid
X)}{\pi^{b}(A\mid X)}-f\left(R\right)\right)^{2}.$ (6)

###  D.1 Variance reduction of G-MIPS estimator

By only considering the shift in the embedding $R$, the G-MIPS estimator
achieves a lower variance relative to the vanilla IPW estimator. The following
result, which is a straightforward extension of [14, Theorem 3.6], formalises
this.

######  Proposition D.2 (Variance reduction of G-MIPS).

When the ratios $\rho(a,x)$ and $\frac{p_{\pi^{*}}(r)}{p_{\pi^{b}}(r)}$ are
known exactly then under Assumption D.1, we have that
$\mathbb{E}_{\pi^{b}}[\hat{\theta}_{\textup{IPW}}]=\mathbb{E}_{\pi^{b}}[\hat{\theta}_{\textup{G-MIPS}}]=\mathbb{E}_{\pi^{*}}[Y]$.
Moreover,

$\displaystyle\textup{Var}_{\pi^{b}}[\hat{\theta}_{\textup{IPW}}]-\textup{Var}_{\pi^{b}}[\hat{\theta}_{\textup{G-MIPS}}]\geq\frac{1}{n}\mathbb{E}_{\pi^{b}}\left[\mathbb{E}[Y^{2}\mid
R]\textup{Var}_{\pi^{b}}[\rho(A,X)\mid R]\right]\geq 0.$

###### Proof of Proposition D.2.

The following proof, which is included for completeness, is a straightforward
extension of [14, Theorem 3.6].

$\displaystyle
n(\textup{Var}_{\pi^{b}}[\hat{\theta}_{\textup{IPW}}]-\textup{Var}_{\pi^{b}}[\hat{\theta}_{\textup{MIPS}}])$
$\displaystyle\quad=\textup{Var}_{\pi^{b}}\left[\frac{\pi^{*}(A|X)}{\pi^{b}(A|X)}\,Y\right]-\textup{Var}_{\pi^{b}}\left[\frac{p_{\pi^{*}}(R)}{p_{\pi^{b}}(R)}\,Y\right]$
$\displaystyle\quad=\textup{Var}_{\pi^{b}}\left[\mathbb{E}_{\pi^{b}}\left[\frac{\pi^{*}(A|X)}{\pi^{b}(A|X)}\,Y\Bigg{|}R\right]\right]+\mathbb{E}_{\pi^{b}}\left[\textup{Var}_{\pi^{b}}\left[\frac{\pi^{*}(A|X)}{\pi^{b}(A|X)}\,Y\Bigg{|}R\right]\right]-\textup{Var}_{\pi^{b}}\left[\mathbb{E}_{\pi^{b}}\left[\frac{p_{\pi^{*}}(R)}{p_{\pi^{b}}(R)}\,Y\Bigg{|}R\right]\right]$
$\displaystyle\qquad-\mathbb{E}_{\pi^{b}}\left[\textup{Var}_{\pi^{b}}\left[\frac{p_{\pi^{*}}(R)}{p_{\pi^{b}}(R)}\,Y\Bigg{|}R\right]\right]$

Now using the conditional independence Assumption D.1, the first term on the
RHS above becomes,

$\displaystyle\textup{Var}_{\pi^{b}}\left[\mathbb{E}_{\pi^{b}}\left[\frac{\pi^{*}(A|X)}{\pi^{b}(A|X)}\,Y\Bigg{|}R\right]\right]$
$\displaystyle=\textup{Var}_{\pi^{b}}\left[\mathbb{E}_{\pi^{b}}\left[\frac{\pi^{*}(A|X)}{\pi^{b}(A|X)}\Bigg{|}R\right]\,\mathbb{E}_{\pi^{b}}\left[Y|R\right]\right]$
$\displaystyle=\textup{Var}_{\pi^{b}}\left[\frac{p_{\pi^{*}}(R)}{p_{\pi^{b}}(R)}\,\mathbb{E}_{\pi^{b}}\left[Y|R\right]\right],$

where in the last step above we use the fact that

$\displaystyle\mathbb{E}_{\pi^{b}}\left[\frac{\pi^{*}(A|X)}{\pi^{b}(A|X)}\Bigg{|}R\right]=\frac{p_{\pi^{*}}(R)}{p_{\pi^{b}}(R)}.$

Putting this together, we get that

$\displaystyle
n(\textup{Var}_{\pi^{b}}[\hat{\theta}_{\textup{IPW}}]-\textup{Var}_{\pi^{b}}[\hat{\theta}_{\textup{MIPS}}])$
$\displaystyle\quad=\mathbb{E}_{\pi^{b}}\left[\textup{Var}_{\pi^{b}}\left[\frac{\pi^{*}(A|X)}{\pi^{b}(A|X)}\,Y\Bigg{|}R\right]\right]-\mathbb{E}_{\pi^{b}}\left[\textup{Var}_{\pi^{b}}\left[\frac{p_{\pi^{*}}(R)}{p_{\pi^{b}}(R)}\,Y\Bigg{|}R\right]\right].$
(7)

Since we have that

$\displaystyle\mathbb{E}_{\pi^{b}}\left[\frac{\pi^{*}(A|X)}{\pi^{b}(A|X)}\,Y\Bigg{|}R\right]=\mathbb{E}_{\pi^{b}}\left[\frac{\pi^{*}(A|X)}{\pi^{b}(A|X)}\Bigg{|}R\right]\,\mathbb{E}_{\pi^{b}}\left[Y|R\right]=\frac{p_{\pi^{*}}(R)}{p_{\pi^{b}}(R)}\,\mathbb{E}_{\pi^{b}}\left[Y|R\right],$

Eq. (7) becomes,

$\displaystyle\mathbb{E}_{\pi^{b}}\left[\textup{Var}_{\pi^{b}}\left[\frac{\pi^{*}(A|X)}{\pi^{b}(A|X)}\,Y\Bigg{|}R\right]\right]-\mathbb{E}_{\pi^{b}}\left[\textup{Var}_{\pi^{b}}\left[\frac{p_{\pi^{*}}(R)}{p_{\pi^{b}}(R)}\,Y\Bigg{|}R\right]\right]$
$\displaystyle\quad=\mathbb{E}_{\pi^{b}}\left[\mathbb{E}_{\pi^{b}}\left[\left(\frac{\pi^{*}(A|X)}{\pi^{b}(A|X)}\,Y\right)^{2}\Bigg{|}R\right]-\mathbb{E}_{\pi^{b}}\left[\left(\frac{p_{\pi^{*}}(R)}{p_{\pi^{b}}(R)}\,Y\right)^{2}\Bigg{|}R\right]\right]$
$\displaystyle\quad=\mathbb{E}_{\pi^{b}}\left[\mathbb{E}_{\pi^{b}}\left[\left(\frac{\pi^{*}(A|X)}{\pi^{b}(A|X)}\right)^{2}\Bigg{|}R\right]\,\mathbb{E}_{\pi^{b}}\left[Y^{2}|R\right]-\left(\frac{p_{\pi^{*}}(R)}{p_{\pi^{b}}(R)}\right)^{2}\,\mathbb{E}_{\pi^{b}}\left[Y^{2}|R\right]\right]$
$\displaystyle\quad=\mathbb{E}_{\pi^{b}}\left[\mathbb{E}_{\pi^{b}}\left[Y^{2}|R\right]\,\left(\mathbb{E}_{\pi^{b}}\left[\left(\frac{\pi^{*}(A|X)}{\pi^{b}(A|X)}\right)^{2}\Bigg{|}R\right]-\left(\mathbb{E}_{\pi^{b}}\left[\frac{\pi^{*}(A|X)}{\pi^{b}(A|X)}\Bigg{|}R\right]\right)^{2}\,\right)\right]$
$\displaystyle\quad=\mathbb{E}_{\pi^{b}}\left[\mathbb{E}_{\pi^{b}}\left[Y^{2}|R\right]\,\textup{Var}_{\pi^{b}}\left[\frac{\pi^{*}(A|X)}{\pi^{b}(A|X)}\Bigg{|}R\right]\right].$

∎

##### Intuition

Here, $R$ contains all relevant information regarding the outcome $Y$.
Moreover, intuitively $R$ can be thought of as the state obtained by
‘filtering out’ relevant information about $Y$ from $(X,A)$. Therefore, $R$
contains less ‘redundant’ information regarding the outcome $Y$ as compared to
the covariate-action pair $(X,A)$. As a result, the G-MIPS estimator which
only considers the shift in the marginal distribution of $R$ due to the policy
shift is more efficient than the IPW estimator, which considers the shift in
the joint distribution of $(X,A)$ instead. In fact, as the amount of
‘redundant’ information regarding $Y$ decreases in the embedding $R$, the
G-MIPS estimator becomes increasingly efficient with decreasing variance. We
formalise this as follows:

######  Assumption D.3.

Assume there exist embeddings $R^{(1)},R^{(2)}$ of the covariate-action pair
$(X,A)$, with Bayesian network shown in Figure 4. This corresponds to the
following conditional independence assumptions:

$R^{(2)}\perp\\!\\!\\!\perp(X,A)\mid R^{(1)},\qquad\textup{and}\qquad
Y\perp\\!\\!\\!\perp(R^{(1)},X,A)\mid R^{(2)}.$

$(X,A)$$R^{(1)}$$R^{(2)}$$Y$ Figure 4: Bayesian network corresponding to
Assumption D.3.

We can define G-MIPS estimators for these embeddings to obtain unbiased OPE
estimators under Assumption D.3 as follows:

$\hat{\theta}^{(j)}_{\textup{G-MIPS}}\coloneqq\frac{1}{n}\sum_{i=1}^{n}\frac{p_{\pi^{*}}(r_{i}^{(j)})}{p_{\pi^{b}}(r_{i}^{(j)})}\,y_{i},$

for $j\in\\{1,2\\}$. Here, $\frac{p_{\pi^{*}}(r^{(j)})}{p_{\pi^{b}}(r^{(j)})}$
is the ratio of marginal densities of $R^{(j)}$ under target and behaviour
policies. We next show that the variance of
$\hat{\theta}^{(j)}_{\textup{G-MIPS}}$ decreases with increasing $j$.

######  Proposition D.4.

When the ratios $\rho(a,x)$, $w(y)$ and
$\frac{p_{\pi^{*}}(r^{(j)})}{p_{\pi^{b}}(r^{(j)})}$ are known exactly for
$j\in\\{1,2\\}$, then under Assumption D.3 we get that

$\mathbb{E}_{\pi^{b}}[\hat{\theta}_{\textup{IPW}}]=\mathbb{E}_{\pi^{b}}[\hat{\theta}^{(1)}_{\textup{G-MIPS}}]=\mathbb{E}_{\pi^{b}}[\hat{\theta}^{(2)}_{\textup{G-MIPS}}]=\mathbb{E}_{\pi^{b}}[\hat{\theta}_{\textup{MR}}]=\mathbb{E}_{\pi^{*}}[Y].$

Moreover,

$\textup{Var}_{\pi^{b}}[\hat{\theta}_{\textup{IPW}}]\geq\textup{Var}_{\pi^{b}}[\hat{\theta}^{(1)}_{\textup{G-MIPS}}]\geq\textup{Var}_{\pi^{b}}[\hat{\theta}^{(2)}_{\textup{G-MIPS}}]\geq\textup{Var}_{\pi^{b}}[\hat{\theta}_{\textup{MR}}].$

###### Proof of Proposition D.4.

First, we prove that the G-MIPS estimators are unbiased using induction on
$j$. We define $R^{(0)}\coloneqq(X,A)$ and
$\hat{\theta}^{(0)}_{\textup{G-MIPS}}$ defined as

$\hat{\theta}^{(0)}_{\textup{G-MIPS}}\coloneqq\frac{1}{n}\sum_{i=1}^{n}\frac{p_{\pi^{*}}(r_{i}^{(0)})}{p_{\pi^{b}}(r_{i}^{(0)})}\,y_{i},$

recovers the IPW estimator $\hat{\theta}_{\textup{IPW}}$. When $j=0$, we know
that $\hat{\theta}^{(0)}_{\textup{G-MIPS}}=\hat{\theta}_{\textup{IPW}}$ is
unbiased. Now, assume that
$\mathbb{E}_{\pi^{b}}[\hat{\theta}^{(j)}_{\textup{G-MIPS}}]=\mathbb{E}_{\pi^{*}}[Y]$.

Conditional on $R^{(j)}$, $R^{(j+1)}$ does not depend on the policy.
Therefore,

$\displaystyle\frac{p_{\pi^{*}}(r^{(j)})}{p_{\pi^{b}}(r^{(j)})}=\frac{p_{\pi^{*}}(r^{(j)})\,p(r^{(j+1)}\mid
r^{(j)})}{p_{\pi^{b}}(r^{(j)})\,p(r^{(j+1)}\mid
r^{(j)})}=\frac{p_{\pi^{*}}(r^{(j)},r^{(j+1)})}{p_{\pi^{b}}(r^{(j)},r^{(j+1)})}.$

And therefore,

$\displaystyle\frac{p_{\pi^{*}}(r^{(j+1)})}{p_{\pi^{b}}(r^{(j+1)})}$
$\displaystyle=\int_{r^{(j)}}\frac{p_{\pi^{*}}(r^{(j)},r^{(j+1)})}{p_{\pi^{b}}(r^{(j)},r^{(j+1)})}\,p_{\pi^{b}}(r^{(j)}\mid
r^{(j+1)})\,\mathrm{d}r^{(j)}$
$\displaystyle=\int_{r^{(j)}}\frac{p_{\pi^{*}}(r^{(j)})}{p_{\pi^{b}}(r^{(j)})}\,p_{\pi^{b}}(r^{(j)}\mid
r^{(j+1)})\,\mathrm{d}r^{(j)}$
$\displaystyle=\mathbb{E}_{\pi^{b}}\left[\frac{p_{\pi^{*}}(R^{(j)})}{p_{\pi^{b}}(R^{(j)})}\Bigg{|}R^{(j+1)}=r^{(j+1)}\right].$

Using this and the fact that $R^{(j)}\perp\\!\\!\\!\perp Y\mid R^{(j+1)}$, we
get that

$\displaystyle\mathbb{E}_{\pi^{b}}\left[\hat{\theta}^{(j+1)}_{\textup{G-MIPS}}\right]$
$\displaystyle=\mathbb{E}_{\pi^{b}}\left[\frac{p_{\pi^{*}}(R^{(j+1)})}{p_{\pi^{b}}(R^{(j+1)})}\,Y\right]$
$\displaystyle=\mathbb{E}_{\pi^{b}}\left[\frac{p_{\pi^{*}}(R^{(j+1)})}{p_{\pi^{b}}(R^{(j+1)})}\,\mathbb{E}_{\pi^{b}}[Y|R^{(j+1)}]\right]$
$\displaystyle=\mathbb{E}_{\pi^{b}}\left[\mathbb{E}_{\pi^{b}}\left[\frac{p_{\pi^{*}}(R^{(j)})}{p_{\pi^{b}}(R^{(j)})}\Bigg{|}R^{(j+1)}\right]\,\mathbb{E}_{\pi^{b}}[Y|R^{(j+1)}]\right]$
$\displaystyle=\mathbb{E}_{\pi^{b}}\left[\mathbb{E}_{\pi^{b}}\left[\frac{p_{\pi^{*}}(R^{(j)})}{p_{\pi^{b}}(R^{(j)})}\,Y\Bigg{|}R^{(j+1)}\right]\right]$
$\displaystyle=\mathbb{E}_{\pi^{b}}\left[\frac{p_{\pi^{*}}(R^{(j)})}{p_{\pi^{b}}(R^{(j)})}\,Y\right]$
$\displaystyle=\mathbb{E}_{\pi^{b}}\left[\hat{\theta}^{(j)}_{\textup{G-MIPS}}\right]=\mathbb{E}_{\pi^{*}}[Y].$

Next, to prove the variance result we consider the difference

$\displaystyle\textup{Var}_{\pi^{b}}[\hat{\theta}^{(j)}_{\textup{G-MIPS}}]-\textup{Var}_{\pi^{b}}[\hat{\theta}^{(j+1)}_{\textup{G-MIPS}}]$
$\displaystyle=\frac{1}{n}\left(\textup{Var}_{\pi^{b}}\left[\frac{p_{\pi^{*}}(R^{(j)})}{p_{\pi^{b}}(R^{(j)})}\,Y\right]-\textup{Var}_{\pi^{b}}\left[\frac{p_{\pi^{*}}(R^{(j+1)})}{p_{\pi^{b}}(R^{(j+1)})}\,Y\right]\right)$
$\displaystyle=\frac{1}{n}\Bigg{(}\textup{Var}_{\pi^{b}}\left[\mathbb{E}_{\pi^{b}}\left[\frac{p_{\pi^{*}}(R^{(j)})}{p_{\pi^{b}}(R^{(j)})}\,Y\Bigg{|}R^{(j+1)}\right]\right]+\mathbb{E}_{\pi^{b}}\left[\textup{Var}_{\pi^{b}}\left[\frac{p_{\pi^{*}}(R^{(j)})}{p_{\pi^{b}}(R^{(j)})}\,Y\Bigg{|}R^{(j+1)}\right]\right]$
$\displaystyle\qquad-\textup{Var}_{\pi^{b}}\left[\frac{p_{\pi^{*}}(R^{(j+1)})}{p_{\pi^{b}}(R^{(j+1)})}\,\mathbb{E}_{\pi^{b}}[Y\mid
R^{(j+1)}]\right]-\mathbb{E}_{\pi^{b}}\left[\left(\frac{p_{\pi^{*}}(R^{(j+1)})}{p_{\pi^{b}}(R^{(j+1)})}\right)^{2}\,\textup{Var}_{\pi^{b}}[Y\mid
R^{(j+1)}]\right]\Bigg{)}$

where in the last step we use the law of total variance. Now, using the fact
that $R^{(j)}\perp\\!\\!\\!\perp Y\mid R^{(j+1)}$, we can rewrite the
expression above as

$\displaystyle=\frac{1}{n}\Bigg{(}\textup{Var}_{\pi^{b}}\left[\mathbb{E}_{\pi^{b}}\left[\frac{p_{\pi^{*}}(R^{(j)})}{p_{\pi^{b}}(R^{(j)})}\Bigg{|}R^{(j+1)}\right]\,\mathbb{E}_{\pi^{b}}[Y|R^{(j+1)}]\right]+\mathbb{E}_{\pi^{b}}\left[\textup{Var}_{\pi^{b}}\left[\frac{p_{\pi^{*}}(R^{(j)})}{p_{\pi^{b}}(R^{(j)})}\,Y\Bigg{|}R^{(j+1)}\right]\right]$
$\displaystyle\qquad-\textup{Var}_{\pi^{b}}\left[\frac{p_{\pi^{*}}(R^{(j+1)})}{p_{\pi^{b}}(R^{(j+1)})}\,\mathbb{E}_{\pi^{b}}[Y\mid
R^{(j+1)}]\right]-\mathbb{E}_{\pi^{b}}\left[\left(\frac{p_{\pi^{*}}(R^{(j+1)})}{p_{\pi^{b}}(R^{(j+1)})}\right)^{2}\,\textup{Var}_{\pi^{b}}[Y\mid
R^{(j+1)}]\right]\Bigg{)}$
$\displaystyle=\frac{1}{n}\Bigg{(}\mathbb{E}_{\pi^{b}}\left[\textup{Var}_{\pi^{b}}\left[\frac{p_{\pi^{*}}(R^{(j)})}{p_{\pi^{b}}(R^{(j)})}\,Y\Bigg{|}R^{(j+1)}\right]\right]-\mathbb{E}_{\pi^{b}}\left[\left(\frac{p_{\pi^{*}}(R^{(j+1)})}{p_{\pi^{b}}(R^{(j+1)})}\right)^{2}\,\textup{Var}_{\pi^{b}}[Y\mid
R^{(j+1)}]\right]\Bigg{)}.$

Moreover, again using the conditional independence $R^{(j)}\perp\\!\\!\\!\perp
Y\mid R^{(j+1)}$, we can expand the first term in the expression above as
follows:

$\displaystyle\mathbb{E}_{\pi^{b}}\left[\textup{Var}_{\pi^{b}}\left[\frac{p_{\pi^{*}}(R^{(j)})}{p_{\pi^{b}}(R^{(j)})}\,Y\Bigg{|}R^{(j+1)}\right]\right]$
$\displaystyle=\mathbb{E}_{\pi^{b}}\Bigg{[}\mathbb{E}_{\pi^{b}}\left[\frac{p_{\pi^{*}}^{2}(R^{(j)})}{p_{\pi^{b}}^{2}(R^{(j)})}\Bigg{|}R^{(j+1)}\right]\,\mathbb{E}_{\pi^{b}}[Y^{2}|R^{(j+1)}]$
$\displaystyle\qquad-\left(\mathbb{E}_{\pi^{b}}\left[\frac{p_{\pi^{*}}(R^{(j)})}{p_{\pi^{b}}(R^{(j)})}\Bigg{|}R^{(j+1)}\right]\mathbb{E}_{\pi^{b}}[Y|R^{(j+1)}]\right)^{2}\Bigg{]}$
$\displaystyle\geq\mathbb{E}_{\pi^{b}}\Bigg{[}\left(\mathbb{E}_{\pi^{b}}\left[\frac{p_{\pi^{*}}(R^{(j)})}{p_{\pi^{b}}(R^{(j)})}\Bigg{|}R^{(j+1)}\right]\right)^{2}\,\mathbb{E}_{\pi^{b}}[Y^{2}|R^{(j+1)}]$
$\displaystyle\qquad-\left(\frac{p_{\pi^{*}}(R^{(j+1)})}{p_{\pi^{b}}(R^{(j+1)})}\mathbb{E}_{\pi^{b}}[Y|R^{(j+1)}]\right)^{2}\Bigg{]}$
$\displaystyle=\mathbb{E}_{\pi^{b}}\Bigg{[}\left(\frac{p_{\pi^{*}}(R^{(j+1)})}{p_{\pi^{b}}(R^{(j+1)})}\right)^{2}\,\textup{Var}_{\pi^{b}}[Y\mid
R^{(j+1)}]\Bigg{]}.$

Here, to get the inequality above, we use the fact that
$\mathbb{E}[X^{2}]\geq(\mathbb{E}[X])^{2}$. Putting this together, we get that
$\textup{Var}_{\pi^{b}}[\hat{\theta}^{(j)}_{\textup{G-MIPS}}]-\textup{Var}_{\pi^{b}}[\hat{\theta}^{(j+1)}_{\textup{G-MIPS}}]\geq
0$.

Moreover, the result
$\textup{Var}_{\pi^{b}}[\hat{\theta}^{(2)}_{\textup{G-MIPS}}]\geq\textup{Var}_{\pi^{b}}[\hat{\theta}_{\textup{MR}}]$
follows straightforwardly from above by defining $R^{(3)}\coloneqq Y$. Then,
the embeddings satisfy the causal structure

$R^{(0)}\rightarrow R^{(1)}\rightarrow R^{(2)}\rightarrow R^{(3)}\rightarrow
Y.$

Using the result above, we know that
$\textup{Var}_{\pi^{b}}[\hat{\theta}^{(2)}_{\textup{G-MIPS}}]\geq\textup{Var}_{\pi^{b}}[\hat{\theta}^{(3)}_{\textup{G-MIPS}}]$.
But now it is straightforward to see that
$\hat{\theta}^{(3)}_{\textup{G-MIPS}}=\hat{\theta}_{\textup{MR}}$, and the
result follows. ∎

##### Intuition

Here, $R^{(j+1)}$ can be thought of as the embedding obtained by ‘filtering
out’ relevant information about $Y$ from $R^{(j)}$. As such, the amount of
‘redundant’ information regarding the outcome $Y$ decreases successively along
the sequence $R^{(0)}(\coloneqq(X,A)),R^{(1)},R^{(2)}$. As a result, the
G-MIPS estimators which only consider the shift in the marginal distributions
of $R^{(j)}$ due to policy shift become increasingly efficient with decreasing
variance as $j$ increases. Define the representation $R^{(3)}\coloneqq Y$,
then the corresponding G-MIPS estimator reduces to the MR estimator, i.e.,
$\hat{\theta}^{(3)}_{\textup{G-MIPS}}=\hat{\theta}_{\textup{MR}}$. Moreover,
this estimator has minimum variance among all the G-MIPS estimators
$\\{\hat{\theta}^{(j)}_{\textup{G-MIPS}}\\}_{0\leq j\leq k}$, as the
representation $R^{(3)}$ contains precisely the least amount of information
necessary to obtain the outcome $Y$. In other words, $Y$ itself serves as the
‘best embedding’ of covariate-action pair $R^{(0)}$ which contains all
relevant information regarding $Y$. We verify this empirically in Appendix F.2
by reproducing the experimental setup in [14] along with the MR baseline.
Additionally, the MR estimator does not rely on assumptions like D.1 for
unbiasedness.

In addition to this, solving the regression problem in Eq. (6) will typically
be more difficult when $R$ is higher dimensional (as is likely to be the case
for many choices of embeddings $R$), leading to high bias. In contrast, for MR
the embedding $R=Y$ is one dimensional and therefore the regression problem is
significantly easier to solve and yields lower bias. Our empirical results in
Appendix F confirm this.

###  D.2 Doubly robust G-MIPS estimators

Consider the setup for the G-MIPS estimator shown in Figure 3. In this case,
we can derive a doubly robust extension of the G-MIPS estimator, denoted as
GM-DR, which uses an estimate of the conditional mean
$\tilde{\mu}(r)\approx\mathbb{E}[Y\mid R=r]$ as a control variate to decrease
the variance of G-MIPS estimator. This can be explicitly written as follows:

$\displaystyle\tilde{\theta}_{\textup{DM-
DR}}\coloneqq\frac{1}{n}\sum_{i=1}^{n}\frac{p_{\pi^{*}}(r_{i})}{p_{\pi^{b}}(r_{i})}\,(y_{i}-\tilde{\mu}(r_{i}))+\tilde{\eta}(\pi^{*}).$
(8)

where
$\tilde{\eta}(\pi^{*})=\frac{1}{n}\sum_{i=1}^{n}\sum_{r^{\prime}\in\mathcal{R}}\tilde{\mu}(r^{\prime})\,p_{\pi^{*}}(r^{\prime}\mid
x_{i})$ is the analogue of the direct method. Here, $\mathcal{R}$ denotes the
space of the possible of the representations $R$111the
$\sum_{r^{\prime}\in\mathcal{R}}$ can be replaced with
$\int_{r^{\prime}\in\mathcal{R}}\mathrm{d}r^{\prime}$ when $\mathcal{R}$ is
continuous. Moreover, given the density $p(r\mid x,a)$, we can compute
$p_{\pi^{*}}(r\mid x)$ using

$p_{\pi^{*}}(r\mid x)=\sum_{a^{\prime}\in\mathcal{A}}p(r\mid
x,a^{\prime})\,\pi^{*}(a^{\prime}\mid x).$

It is straightforward to extend ideas from [13] to show that estimator
$\tilde{\theta}_{\textup{DM-DR}}$ is doubly robust in that it will yield
accurate value estimates if either the importance weights
$\frac{p_{\pi^{*}}(r)}{p_{\pi^{b}}(r)}$ or the outcome model $\tilde{\mu}(r)$
is well estimated.

##### There is no analogous DR extension of the MR estimator

A consequence of considering the embedding $R=Y$ (as in MR) is that in this
case we do not have an analogous doubly robust extension as above. To see why
this is the case, note that when $R=Y$, we get that
$\tilde{\mu}(r)=\mathbb{E}[Y\mid R=r]=\mathbb{E}[Y\mid Y=y]=y$. If we
substitute this $\tilde{\mu}(r)$ in (8), we are simply left with
$\tilde{\eta}(\pi^{*})$ on the right hand side (as the first term cancels
out). This means that the resulting estimator does not retain the doubly
robust nature as we no longer obtain an accurate estimate if either the
outcome model or the importance ratios are well estimated.

##  Appendix E Application to causal inference

In this section, we investigate the application of the MR estimator for the
estimation of average treatment effect (ATE). In this setting, we suppose that
$\mathcal{A}=\\{0,1\\}$, and the goal is to estimate ATE defined as follows:

$\textup{ATE}\coloneqq\mathbb{E}[Y(1)-Y(0)]$

Here, we use the potential outcomes notation [44] to denote the outcome under
a deterministic policy $\pi^{*}(a^{\prime}\mid x)=\mathbbm{1}(a^{\prime}=a)$
as $Y(a)$.

Specifically, the IPW estimator applied to ATE estimation yields:

$\widehat{\textup{ATE}}_{\textup{IPW}}=\frac{1}{n}\sum_{i=1}^{n}\rho_{\textup{ATE}}(a_{i},x_{i})\times
y_{i},$

where

$\rho_{\textup{ATE}}(a,x)\coloneqq\frac{\mathbbm{1}(a=1)-\mathbbm{1}(a=0)}{\pi^{b}(a|x)}.$

Similarly, the MR estimator can be written as

$\widehat{\textup{ATE}}_{\textup{MR}}=\frac{1}{n}\sum_{i=1}^{n}w_{\textup{ATE}}(y_{i})\times
y_{i},$

where

$w_{\textup{ATE}}(y)=\frac{p_{\pi^{(1)}}(y)-p_{\pi^{(0)}}(y)}{p_{\pi^{b}}(y)},$

and $\pi^{(a)}(a^{\prime}\mid x)\coloneqq\mathbbm{1}(a^{\prime}=a)$ for
$a\in\\{0,1\\}$.

Again, using the fact that
$w_{\textup{ATE}}(Y)\overset{\textup{a.s.}}{=}\mathbb{E}[\rho_{\textup{ATE}}(A,X)\mid
Y]$, we can obtain $w_{\textup{ATE}}$ by minimising a simple mean-squared
loss:

$\displaystyle
w_{\textup{ATE}}=\arg\min_{f}\mathbb{E}_{\pi^{b}}\Big{[}\frac{\mathbbm{1}(A=1)-\mathbbm{1}(A=0)}{\pi^{b}(A|X)}-f(Y)\Big{]}^{2}.$

######  Proposition E.1 (Variance comparison with IPW ATE estimator).

When the weights $\rho_{\textup{ATE}}(a,x)$ and $w_{\textup{ATE}}(y)$ are
known exactly, we have that
$\textup{Var}[\widehat{\textup{ATE}}_{\textup{MR}}]\leq\textup{Var}[\widehat{\textup{ATE}}_{\textup{IPW}}]$.
Specifically,

$\displaystyle\textup{Var}[\widehat{\textup{ATE}}_{\textup{IPW}}]-\textup{Var}[\widehat{\textup{ATE}}_{\textup{MR}}]=\frac{1}{n}\mathbb{E}\left[\textup{Var}\left[\rho_{\textup{ATE}}(A,X)|Y\right]\,Y^{2}\right]\geq
0.$

###### Proof of Proposition E.1.

We have

$\displaystyle\textup{Var}[\widehat{\textup{ATE}}_{\textup{IPW}}]-\textup{Var}[\widehat{\textup{ATE}}_{\textup{MR}}]$
$\displaystyle=\frac{1}{n}\left(\textup{Var}[\rho_{\textup{ATE}}(A,X)\,Y]-\textup{Var}[w_{\textup{ATE}}(Y)\,Y]\right).$
(9)

Using the tower law of variance, we get that

$\displaystyle\textup{Var}[\rho_{\textup{ATE}}(A,X)\,Y]$
$\displaystyle=\textup{Var}[\mathbb{E}[\rho_{\textup{ATE}}(A,X)\,Y\mid
Y]]+\mathbb{E}[\textup{Var}[\rho_{\textup{ATE}}(A,X)\,Y\mid Y]]$
$\displaystyle=\textup{Var}[\mathbb{E}[\rho_{\textup{ATE}}(A,X)\mid
Y]\,Y]+\mathbb{E}[\textup{Var}[\rho_{\textup{ATE}}(A,X)\mid Y]\,Y^{2}]$
$\displaystyle=\textup{Var}[w_{\textup{ATE}}(Y)\,Y]+\mathbb{E}[\textup{Var}[\rho_{\textup{ATE}}(A,X)\mid
Y]\,Y^{2}].$

Putting this together with (9) we obtain,

$\displaystyle\textup{Var}[\widehat{\textup{ATE}}_{\textup{IPW}}]-\textup{Var}[\widehat{\textup{ATE}}_{\textup{MR}}]$
$\displaystyle=\frac{1}{n}\mathbb{E}[\textup{Var}[\rho_{\textup{ATE}}(A,X)\mid
Y]\,Y^{2}],$

which straightforwardly leads to the result. ∎

Given the above definitions, the IPW estimator for $\mathbb{E}[Y(a)]$ would
only consider datapoints with $A=a$, as it weights the samples using the
policy ratios $\mathbbm{1}(A=a)/\pi^{b}(A|X)$ which are only non-zero when
$A=a$. This is however not the case with the MR estimator, as it uses the
weights $p_{\pi^{*}}(Y)/p_{\pi^{b}}(Y)$ which are not necessarily zero for
$A\neq a$. Therefore, MR uses all evaluation datapoints $\mathcal{D}$ when
estimating $\mathbb{E}[Y(a)]$. The MR estimator therefore leads to a more
efficient use of evaluation data in this example.

Likewise, the doubly robust (DR) estimator applied to ATE estimation yields,

$\displaystyle\widehat{\textup{ATE}}_{\textup{DR}}\coloneqq\frac{1}{n}\sum_{i=1}^{n}\rho_{\textup{ATE}}(a_{i},x_{i})\,\left(y_{i}-\hat{\mu}(a_{i},x_{i})\right)+\frac{1}{n}\sum_{i=1}^{n}\left(\hat{\mu}(1,x_{i})-\hat{\mu}(0,x_{i})\right),$

where $\hat{\mu}(a,x)\approx\mathbb{E}[Y\mid X=x,A=a]$. Like in classical off-
policy evaluation, DR yields an accurate estimator of ATE when either the
weights $\rho_{\textup{ATE}}(a,x)$ or the outcome model i.e.,
$\hat{\mu}(a,x)=\mathbb{E}[Y\mid X=x,A=a]$, are well estimated. However,
despite this doubly robust nature of the estimator, we can show that the
variance of the DR estimator may be higher than that of the MR estimator in
many cases. The following result formalises this variance comparison between
the DR and MR estimators, and is analogous to the result in Proposition 3.4
derived for classical off-policy evaluation.

######  Proposition E.2 (Variance comparison with DR ATE estimator).

When the weights $\rho_{\textup{ATE}}(a,x)$ and $w_{\textup{ATE}}(y)$ are
known exactly,

$\displaystyle\textup{Var}[\widehat{\textup{ATE}}_{\textup{DR}}]-\textup{Var}[\widehat{\textup{ATE}}_{\textup{MR}}]\geq\frac{1}{n}\mathbb{E}\left[\textup{Var}\left[\rho_{\textup{ATE}}(A,X)\,Y\mid
Y\right]-\textup{Var}\left[\rho_{\textup{ATE}}(A,X)\mu(A,X)\mid
X\right]\right],$

where $\mu(A,X)\coloneqq\mathbb{E}[Y\mid X,A]$.

###### Proof of Proposition E.2.

Using the law of total variance, we get that

$\displaystyle n\,\textup{Var}[\widehat{\textup{ATE}}_{\textup{DR}}]$
$\displaystyle=\textup{Var}[\rho_{\textup{ATE}}(A,X)\,(Y-\hat{\mu}(A,X))+(\hat{\mu}(1,X)-\hat{\mu}(0,X))]$
$\displaystyle=\textup{Var}[\mathbb{E}[\rho_{\textup{ATE}}(A,X)\,(Y-\hat{\mu}(A,X))+(\hat{\mu}(1,X)-\hat{\mu}(0,X))\mid
X,A]]$
$\displaystyle\qquad+\mathbb{E}[\textup{Var}[\rho_{\textup{ATE}}(A,X)\,(Y-\hat{\mu}(A,X))+(\hat{\mu}(1,X)-\hat{\mu}(0,X))\mid
X,A]]$
$\displaystyle=\textup{Var}[\rho_{\textup{ATE}}(A,X)\,(\mu(A,X)-\hat{\mu}(A,X))+(\hat{\mu}(1,X)-\hat{\mu}(0,X))]$
$\displaystyle\qquad+\mathbb{E}[\rho^{2}_{\textup{ATE}}(A,X)\textup{Var}[Y\mid
X,A]].$

Again, using the law of total variance we can rewrite the first term on the
RHS above as,

$\displaystyle\textup{Var}[\rho_{\textup{ATE}}(A,X)\,(\mu(A,X)-\hat{\mu}(A,X))+(\hat{\mu}(1,X)-\hat{\mu}(0,X))]$
$\displaystyle\quad=\textup{Var}[\mathbb{E}[\rho_{\textup{ATE}}(A,X)\,(\mu(A,X)-\hat{\mu}(A,X))+(\hat{\mu}(1,X)-\hat{\mu}(0,X))\mid
X]]$
$\displaystyle\qquad+\mathbb{E}[\textup{Var}[\rho_{\textup{ATE}}(A,X)\,(\mu(A,X)-\hat{\mu}(A,X))+(\hat{\mu}(1,X)-\hat{\mu}(0,X))\mid
X]]$
$\displaystyle\quad\geq\textup{Var}[\mathbb{E}[\rho_{\textup{ATE}}(A,X)\,(\mu(A,X)-\hat{\mu}(A,X))+(\hat{\mu}(1,X)-\hat{\mu}(0,X))\mid
X]]$
$\displaystyle\quad=\textup{Var}[\mathbb{E}[\rho_{\textup{ATE}}(A,X)\,(\mu(A,X)-\hat{\mu}(A,X))+\rho_{\textup{ATE}}(A,X)\,\hat{\mu}(A,X)\mid
X]]$
$\displaystyle\quad=\textup{Var}[\mathbb{E}[\rho_{\textup{ATE}}(A,X)\,\mu(A,X)\mid
X]],$

where, in the second last step above we use the fact that

$\mathbb{E}[\rho_{\textup{ATE}}(A,X)\,\hat{\mu}(A,X)\mid
X]=\hat{\mu}(1,X)-\hat{\mu}(0,X).$

Putting this together, we get that

$\displaystyle
n\,\textup{Var}[\widehat{\textup{ATE}}_{\textup{DR}}]\geq\textup{Var}[\mathbb{E}[\rho_{\textup{ATE}}(A,X)\,\mu(A,X)\mid
X]]+\mathbb{E}[\rho^{2}_{\textup{ATE}}(A,X)\textup{Var}[Y\mid X,A]].$

Therefore,

$\displaystyle
n\,(\textup{Var}[\widehat{\textup{ATE}}_{\textup{DR}}]-\textup{Var}[\widehat{\textup{ATE}}_{\textup{MR}}])$
$\displaystyle\quad\geq\textup{Var}[\mathbb{E}[\rho_{\textup{ATE}}(A,X)\,\mu(A,X)\mid
X]]+\mathbb{E}[\rho^{2}_{\textup{ATE}}(A,X)\textup{Var}[Y\mid
X,A]]-\textup{Var}[w_{\textup{ATE}}(Y)\,Y]$
$\displaystyle\quad=\textup{Var}[\mathbb{E}[\rho_{\textup{ATE}}(A,X)\,\mu(A,X)\mid
X]]+\mathbb{E}[\textup{Var}[\rho_{\textup{ATE}}(A,X)\,Y\mid
X,A]]-\textup{Var}[w_{\textup{ATE}}(Y)\,Y]$
$\displaystyle\quad=\textup{Var}[\mathbb{E}[\rho_{\textup{ATE}}(A,X)\,\mu(A,X)\mid
X]]+\textup{Var}[\rho_{\textup{ATE}}(A,X)\,Y]-\textup{Var}[\mathbb{E}[\rho_{\textup{ATE}}(A,X)\,Y\mid
X,A]]$ $\displaystyle\qquad-\textup{Var}[w_{\textup{ATE}}(Y)\,Y]$
$\displaystyle\quad=\textup{Var}[\mathbb{E}[\rho_{\textup{ATE}}(A,X)\,\mu(A,X)\mid
X]]+\textup{Var}[\mathbb{E}[\rho_{\textup{ATE}}(A,X)\mid
Y]\,Y]+\mathbb{E}[\textup{Var}[\rho_{\textup{ATE}}(A,X)\mid Y]\,Y^{2}]$
$\displaystyle\qquad-\textup{Var}[\mathbb{E}[\rho_{\textup{ATE}}(A,X)\,Y\mid
X,A]]-\textup{Var}[w_{\textup{ATE}}(Y)\,Y]$
$\displaystyle\quad=\textup{Var}[\mathbb{E}[\rho_{\textup{ATE}}(A,X)\,\mu(A,X)\mid
X]]+\textup{Var}[w_{\textup{ATE}}(Y)\,Y]+\mathbb{E}[\textup{Var}[\rho_{\textup{ATE}}(A,X)\mid
Y]\,Y^{2}]$
$\displaystyle\qquad-\textup{Var}[\mathbb{E}[\rho_{\textup{ATE}}(A,X)\,Y\mid
X,A]]-\textup{Var}[w_{\textup{ATE}}(Y)\,Y]$
$\displaystyle\quad=\textup{Var}[\mathbb{E}[\rho_{\textup{ATE}}(A,X)\,\mu(A,X)\mid
X]]-\textup{Var}[\mathbb{E}[\rho_{\textup{ATE}}(A,X)\,Y\mid
X,A]]+\mathbb{E}[\textup{Var}[\rho_{\textup{ATE}}(A,X)\mid Y]\,Y^{2}]$
$\displaystyle\quad=\textup{Var}[\rho_{\textup{ATE}}(A,X)\,\mu(A,X)]-\mathbb{E}[\textup{Var}[\rho_{\textup{ATE}}(A,X)\,\mu(A,X)\mid
X]]-\textup{Var}[\rho_{\textup{ATE}}(A,X)\,\mu(A,X)]$
$\displaystyle\qquad+\mathbb{E}[\textup{Var}[\rho_{\textup{ATE}}(A,X)\mid
Y]\,Y^{2}]$
$\displaystyle\quad=\mathbb{E}\left[\textup{Var}\left[\rho_{\textup{ATE}}(A,X)\mid
Y\right]\,Y^{2}-\textup{Var}\left[\rho_{\textup{ATE}}(A,X)\mu(A,X)\mid
X\right]\right].$

∎

Proposition E.2 shows that if
$\textup{Var}\left[Y\,\rho_{\textup{ATE}}(A,X)\mid Y\right]$ is greater than
$\textup{Var}\left[\rho_{\textup{ATE}}(A,X)\mu(A,X)\mid X\right]$ on average,
the variance of the MR estimator will be less than that of the DR estimator.
Intuitively, this is likely to happen when the dimension of context space
${\mathcal{X}}$ is high because in this case, the conditional variance over
$X$ and $A$, $\textup{Var}\left[Y\,\rho_{\textup{ATE}}(A,X)\mid Y\right]$ is
likely to be greater than the conditional variance over $A$,
$\textup{Var}\left[\rho_{\textup{ATE}}(A,X)\mu(A,X)\mid X\right]$.

##  Appendix F Experimental Results

In this section, we provide additional experimental details for the results
presented in the main text. We also include extensive experimental results to
provide further empirical evidence in favour of the MR estimator.

##### Computational details

We ran our experiments on Intel(R) Xeon(R) CPU E5-2690 v4 @ 2.60GHz with 8GB
RAM per core. We were able to use 150 CPUs in parallel to iterate over
different configurations and seeds. However, we would like to note that for
each run our algorithms only requires 1 CPU and at most 30 minutes to run as
our neural networks are relatively small. Throughout our experiments, whenever
the outcome $Y$ was continuous, we used a fully connected neural network with
three hidden layers with 512, 256 and 32 nodes respectively (and ReLU
activation function) to estimate the weights $\hat{w}(y)$. On the other hand,
when the outcome is discrete we can directly estimate
$\hat{w}(y)\approx\mathbb{E}[\hat{\rho}(A,X)\mid Y=y]$ by calculating the
sample mean of $\hat{\rho}(A,X)$ on samples with $Y=y$. Additionally, for each
configuration of parameters in our experiments, we ran experiments for 10
different seeds (in {0, 1, …, 9}).

###  F.1 Alternative methodology of estimating MR

In addition to the OPE baselines like IPW, DM and DR estimators considered in
the main text, we also include empirically investigate an alternative
methodology of estimating MR. Below we describe this methodology, denoted as
‘MR (alt)’, in greater detail:

####  F.1.1 MR (alt)

Recall our definition of MR estimator:

$\hat{\theta}_{\textup{MR}}\coloneqq\frac{1}{n}\sum_{i=1}^{n}w(y_{i})\,y_{i}.$

In the main text, we propose estimating the weights $w(y)$ first and using
this to estimate $\hat{\theta}_{\textup{MR}}$ using the above expression.
Alternatively, we can estimate $h(y)\coloneqq y\,w(y)$ using

$\displaystyle
h=\arg\min_{f}\,\mathbb{E}_{\pi^{b}}\left[\Bigg{(}Y\,\frac{\pi^{*}(A|X)}{\pi^{b}(A|X)}-f(Y)\Bigg{)}^{2}\right].$

Subsequently, the MR estimator can be written as:

$\hat{\theta}_{\textup{MR}}=\frac{1}{n}\sum_{i=1}^{n}h(y_{i}).$

We refer to this alternative methodology as ‘MR-alt’ and compare it
empirically against the original methodology (which we simply refer to as
‘MR’). In general, it is difficult to say which of the two methods will
perform better. Intuitively speaking, in cases where the behaviour of the
quantity $Y\,\frac{\pi^{*}(A|X)}{\pi^{b}(A|X)}$ with varying $Y$ is ‘smoother’
than that of $\frac{\pi^{*}(A|X)}{\pi^{b}(A|X)}$, the alternative method is
expected to perform better. Our empirical results in the next sections show
that the relative performance of the two methods varies for different data
generating mechanisms.

###  F.2 Synthetic data experiments

Here, we include additional experimental details for the synthetic data
experiments presented in Section 5.1 for completeness. For this experiment, we
use the same setup as the synthetic data experiment in [14], reproduced by
reusing their code with minor modifications.

##### Setup

Here, we sample the $d$-dimensional context vectors $x$ from a standard normal
distribution. The setup used also includes $3$-dimensional categorical action
embeddings $E\in\mathcal{E}$, which are sampled from the following conditional
distribution given action $A=a$,

$p(e\mid
a)=\prod_{k=1}^{3}\frac{\exp{(\alpha_{a,e_{k}})}}{\sum_{e^{\prime}\in\mathcal{E}_{k}}\exp{(\alpha_{a,e^{\prime}})}},$

which is independent of the context $X$. $\\{\alpha_{a,e_{k}}\\}$ is a set of
parameters sampled independently from the standard normal distribution. Each
dimension of $\mathcal{E}$ has a cardinality of $10$, i.e.,
$\mathcal{E}_{k}=\\{1,2,\dots,10\\}$.

##### Reward function

The expected reward is then defined as:

$q(x,e)=\sum_{k=1}^{3}\eta_{k}\cdot(x^{T}\,M\,x_{e_{k}}+\theta_{x}^{T}\,x+\theta_{e}^{T}\,x_{e_{k}}),$

where $M$, $\theta_{x}$ and $\theta_{e}$ are parameter matrices or vectors
sampled from a uniform distribution with range $[-1,1]$. $x_{e_{k}}$ is a
context vector corresponding to the $k$-th dimension of the action embedding,
which is unobserved to the estimators. $\eta_{k}$ specifies the importance of
the $k$-th dimension of the action embedding, sampled from Dirichlet
distribution so that $\sum_{k=1}^{3}\eta_{k}=1$.

##### Behaviour and target policies

The behaviour policy $\pi^{b}$ is defined by applying the softmax function to
$q(x,a)=\mathbb{E}[q(X,E)\mid A=a,X=x]$ as

$\pi^{b}(a\mid
x)=\frac{\exp{(-q(x,a))}}{\sum_{a^{\prime}\in\mathcal{A}}\exp{(-q(x,a^{\prime}))}}.$

For the target policy, we define the class of parametric policies,

$\pi^{\alpha^{\ast}}(a|x)=\alpha^{\ast}\,{\mathbbm{1}}(a=\arg\max_{a^{\prime}\in\mathcal{A}}q(x,a^{\prime}))+\frac{1-\alpha^{\ast}}{|\mathcal{A}|},$

where $\alpha^{\ast}\in[0,1]$ controls the shift between the behaviour and
target policies. As shown in the main text, as $\alpha^{\ast}\rightarrow 1$,
the shift between behaviour and target policies increases.

##### Baselines

In the main text, we compare MR with DM, IPW, DR and MIPS estimators. In
addition to these baselines, here we also consider Switch-DR [5] and DR with
Optimistic Shrinkage (DRos) [17]. Following [14], we use the random forest
[45] along with 2-fold cross-fitting [46] to obtain $\hat{q}(x,e)$ for DR and
DM methods. To estimate $p_{\pi^{b}}(a\mid x,e)$ for MIPS estimator, we use
logistic regression. We also include the results for MR estimated using the
alternative methodology described in Section F.1.1. We refer to this as ‘MR
(alt)’.

##### Estimation of behaviour policy $\widehat{\pi}^{b}$ and marginal ratio
$\hat{w}(y)$

We do not assume that the true behaviour policy $\pi^{b}$ is known, and
therefore estimate $\widehat{\pi}^{b}$ using the available training data. For
the MR estimator, we estimate the behaviour policy using a random forest
classifier trained on 50% of the training data and use the rest of the
training data to estimate the marginal ratios $\hat{w}(y)$ using multi-layer
perceptrons (MLP). Moreover, for a fair comparison we use a different
behaviour policy estimate $\widehat{\pi}^{b}$ for all other baselines which is
trained on the entire training data.

(a) $d=1000$, $n_{a}=100$, $\alpha^{\ast}=0.8$

(b) $d=5000$, $n_{a}=250$, $\alpha^{\ast}=0.8$

(c) $d=5000$, $n_{a}=250$, $\alpha^{\ast}=1.0$

Figure 5: MSE with varying size of evaluation dataset $n$ for different
choices of parameters.

(a) $d=100$, $n_{a}=100$, $n=100$

(b) $d=100$, $n_{a}=250$, $n=100$

(c) $d=1000$, $n_{a}=250$, $n=100$

Figure 6: MSE with varying $\alpha^{\ast}$ for different choices of
parameters.

####  F.2.1 Results

For this experiment, the results are computed over 10 different sets of logged
data replicated with different seeds, and in Figures 5 \- 8 we use a total of
$m=5000$ training data.

##### Varying size of evaluation data $n$

Figure 5 shows that MR outperforms the other baselines, in terms of MSE and
squared bias, when the number of evaluation data $n\leq 1000$. Additionally,
we observe that in this experiment, MR estimated using our original methods
(‘MR’), yields better results than the alternative method of estimating MR
(‘MR (alt)’). Moreover, while the variance of DM is lower than that of MR, the
DM method has a high bias and consequently a high MSE. We note that while the
difference between MSE and variance of MIPS and MR estimators decreases with
increasing evaluation data size, MR still outperforms MIPS in terms of both
MSE and variance.

##### Varying $\alpha^{\ast}$

Figure 6 shows the results with increasing policy shift. It can be seen that
overall MR methods achieve the smallest MSE with increasing policy shift.
Moreover, the difference between MSE and variance of MR and IPW/DR methods
increases with increasing policy shift, showing that MR performs especially
better than these baselines when the difference between behaviour and target
policies is large. Similarly, we observe in Figure 6 that as the shift between
the behaviour and target policy increases with increasing $\alpha^{\ast}$, so
does the difference between the MSE and variance of MR and the MIPS
estimators. This shows that generally MR outperforms MIPS estimator in terms
of variance and MSE, and that MR performs especially better than MIPS as the
difference between behaviour and target policies increases.

##### Varying $d$ and $n_{a}$

Figures 7 and 8 show that MR outperforms the other baselines as the context
dimensions and/or number of actions increase. In fact, these figures show that
MR is significantly robust to increasing dimensions of action and context
spaces, whereas baselines like IPW and DR perform poorly in large action
spaces.

##### Varying $m$

Figure 10 shows the results with increasing number of training data $m$. We
again observe that the MR methods ‘MR’ and ‘MR (alt)’ outperforms the other
baselines in terms of the MSE and squared bias even when the number of
training data is low. Moreover, the variance of both the MR estimators
continues to improve with increasing number of training data.

In this experiment, we observe that overall ‘MR (alt)’ performs worse than the
original MR estimator (‘MR’ in the figures). However, as we observe in
Appendix F.5, this does not happen consistently across all experiments, which
suggests that the comparative performance of the two MR methods depends on the
data generating mechanism.

(a) $n_{a}=20$, $n=200$, $\alpha^{\ast}=0.8$

(b) $n_{a}=100$, $n=200$, $\alpha^{\ast}=0.8$

(c) $n_{a}=250$, $n=200$, $\alpha^{\ast}=0.8$

Figure 7: MSE with varying context dimensions $d$ for different choices of
parameters.

(a) $d=1000$, $n=100$, $\alpha^{\ast}=0.4$

(b) $d=1000$, $n=100$, $\alpha^{\ast}=0.8$

(c) $d=1000$, $n=100$, $\alpha^{\ast}=1.0$

Figure 8: MSE with varying number of actions $n_{a}$ for different choices of
parameters.

####  F.2.2 Known policy ratios $\rho(a,x)$

Table 3: Mean-squared error results with 2 standard errors for synthetic data setup considered in Section 5.1 with $d=5000$, $n_{a}=50$, $\alpha^{\ast}=0.8$. We use a fixed budget of datapoints (denoted by $N$) for each baseline and in the case of MR we use $m=2000$ of the available datapoints to estimate $\hat{w}(y)$ and the rest of data to evaluate the MR estimator (i.e. $n=N-2000$ for MR). In contrast, for IPW and MIPS since the importance ratios are already known, we use all of the $N$ datapoints for evaluation of the off-policy value (i.e. $n=N$ for IPW and MIPS). | $N$ | 2800 | 3200 | 6400 | 10000 | 12000
---|---|---|---|---|---|---
GT weights $\rho(a,x)$ and estimated reward model $\hat{\mu}(a,x)$ | DM |  0.137$\pm$0.028 |  0.099$\pm$0.012 |  0.103$\pm$0.012 |  0.093$\pm$0.010 |  0.089$\pm$0.010
($m=2000$ used for training $\hat{\mu}(a,x)$ and $n=N-2000$ | DR |  0.227$\pm$0.065 |  0.068$\pm$0.035 |  0.068$\pm$0.022 | 0.024$\pm$0.011 |  0.045$\pm$0.015
used for evaluation) | DRos |  0.128$\pm$0.027 |  0.072$\pm$0.011 |  0.049$\pm$0.014 |  0.063$\pm$0.014 |  0.051$\pm$0.016
SwitchDR |  0.128$\pm$0.027 |  0.059$\pm$0.014 |  0.052$\pm$0.013 |  0.061$\pm$0.015 |  0.056$\pm$0.016
GT weights (all of $N$ datapoints are used for evaluation) | IPW |  0.237$\pm$0.062 |  0.066$\pm$0.036 |  0.067$\pm$0.021 |  0.025$\pm$0.011 | 0.044$\pm$0.014
MIPS |  0.236$\pm$0.062 |  0.065$\pm$0.035 |  0.067$\pm$0.021 |  0.025$\pm$0.011 | 0.044$\pm$0.014
Estimated weights $\hat{w}(y)$ ($m=2000$ used for training |  |  |  |  |  |
and $n=N-2000$ used for evaluation) | MR (Ours) | 0.045$\pm$0.015 | 0.042$\pm$0.014 | 0.048$\pm$0.020 |  0.049$\pm$0.020 |  0.047$\pm$0.016

Our previous setting of unknown importance policy ratios $\rho(a,x)$ captures
a wide variety of real-world applications, ranging from health care to
autonomous driving. In addition, to demonstrate the utility of MR in settings
with known $\rho(a,x),p(e\mid a,x)$ and unknown $w(y)$ (for our proposed
method, MR), we have conducted additional experiments. Here, we use a fixed
budget of datapoints (denoted by $N$) for each baseline and for MR we allocate
$m=2000$ of the available datapoints to estimate $\hat{w}(y)$ and use the
remaining for evaluating the MR estimator (i.e., $n=N-2000$ for MR). In
contrast, for IPW and MIPS (since the importance ratios are already known), we
use all of the $N$ datapoints to evaluate the off-policy value (i.e. $n=N$ for
IPW and MIPS).

The results included in Table 3 show that MR achieves the smallest MSE among
the baselines for $N\leq 6400$. However, we observe that the MSE of IPW, DR
and MIPS (with true importance weights) falls below that of MR (with estimated
weights $\hat{w}$) when the data size $N$ is large enough (i.e., $N\geq
10,000$). This is to be expected since IPW, DR and MIPS are unbiased (i.e.,
use ground truth importance ratios $\rho(a,x)$) whereas MR uses estimated
weights $\hat{w}(y)$ (and hence may be biased). MR still performs the best
when $N\leq 6400$.

###  F.3 Experiments on classification datasets

Here, we conduct experiments on four classification datasets, OptDigits,
PenDigits, SatImage and Letter datasets from the UCI repository [37], the
Digits dataset from scikit-learn library, as well as the Mnist [38] and
CIFAR-100 datasets [39].

##### Setup

Following previous works [13, 22, 36, 5], the classification datasets are
transformed to contextual bandit feedback data. The classification dataset
comprises $\\{x_{i},a^{\textup{gt}}_{i}\\}_{i=1}^{n_{0}}$, where
$x_{i}\in{\mathcal{X}}$ are feature vectors and
$a^{\textup{gt}}_{i}\in\mathcal{A}$ are the ground-truth labels. In the
contextual bandits setup, the feature vectors $x_{i}$ are considered to be the
contexts, whereas the actions correspond to the possible class of labels. We
split the dataset into training and testing datasets of sizes $m$ and $n$
respectively. We present the results for a range of different values of $m$
and $n$.

##### Reward function

Let $X$ be a context with ground truth label $A^{\textup{gt}}$, we define the
reward for action $A$ as:

$Y\coloneqq{\mathbbm{1}}(A=A^{\textup{gt}}).$

##### Behaviour and target policies

Using the $m$ training datapoints, we first train a classifier