\section{Introduction}
\label{sec:intro}


In practical scenarios where safety, reliability, or performance is a
concern, it is typically infeasible to directly deploy a reinforcement
learning (RL) algorithm, as it may compromise these desiderata. This
motivates research on \emph{off-policy evaluation}, where we use data
collected by a (presumably safe) logging policy to estimate the
performance of a given target policy, without ever deploying it. These
methods help determine if a policy is suitable for deployment at
minimal cost and, in addition, serve as the statistical foundations of
sample-efficient policy optimization algorithms. In light of the
fundamental role off-policy evaluation plays in RL, it has been the
subject of intense research over the last several
decades~\citep{horvitz1952generalization,dudik2014doubly,swaminathan2017off,kallus2018policy,sutton1988learning,bradtke1996linear,precup2000eligibility,jiang2015doubly,thomas2016data,farajtabar2018more,liu2018breaking,voloshin2019empirical}.


As many off-policy estimators have been developed, practitioners face
a new challenge of choosing the best estimator for their
application. This selection problem is critical to high quality
estimation as has been demonstrated in recent empirical
studies~\cite{voloshin2019empirical}. However, data-driven estimator
selection in these settings is fundamentally different from
hyperparameter optimization or model selection for supervised
learning. In particular, cross validation or bound minimization
approaches fail because there is no unbiased and low variance approach
to compare estimators. As such, the current best practice for
estimator selection is to leverage domain expertise or follow
guidelines from the literature~\citep{voloshin2019empirical}.


Domain knowledge can suggest a particular form of estimator, but a
second selection problem arises, as many estimators themselves have
hyperparameters that must be tuned. In most cases, these
hyperparameters modulate a bias-variance tradeoff, where at one
extreme the estimator is unbiased but has high variance, and at the
other extreme the estimator has low variance but potentially high
bias. Hyperparameter selection is critical to performance, but
high-level prescriptive guidelines are less informative for these
low-level selection problems. We seek a data-driven approach.


In this paper, we study the estimator-selection question for
off-policy evaluation. We provide a general technique, that we call
\textsc{Slope}\xspace, that applies to a broad family of estimators, across several
distinct problem settings. On the theoretical side, we prove that the
selection procedure is competitive with oracle tuning, establishing an
\emph{oracle inequality}. To demonstrate the generality of our
approach, we study two applications in detail: (1) bandwidth selection
in contextual bandits with continuous actions, and (2) horizon
selection for ``partial importance weighting estimators'' in RL. In
both examples, we prove that our theoretical results apply, and we
provide a comprehensive empirical evaluation. In the contextual
bandits application, our selection procedure is competitive with the
skyline oracle tuning (which is unimplementable in practice) and
outperforms any fixed parameter in aggregate across experimental
conditions.  In the RL application, our approach substantially
outperforms standard baselines including
\textsc{Magic}\xspace~\citep{thomas2016data}, the only comparable estimator selection
method.

\ifthenelse{\equal{arxiv}{arxiv}}{
\begin{wrapfigure}{R}{0.5\textwidth}
\vspace{-0.8cm}
\begin{center}
\includegraphics[width=0.47\textwidth]{bar_plots.pdf}
\end{center}
\vspace{-0.6cm}
\caption{Representative experiments with \textsc{Slope}\xspace. \textsc{Slope}\xspace is consistently one of the best
  approaches, regardless of whether model-based or importance-sampling
  based estimators are better.}
\label{fig:intro_exp}
\vspace{-0.3cm}
\end{wrapfigure}
}{
\begin{figure}
\begin{center}
\includegraphics[width=0.8\columnwidth]{bar_plots.pdf}
\end{center}
\vspace{-0.5cm}
\caption{Representative experiments with \textsc{Slope}\xspace. \textsc{Slope}\xspace is consistently one of the best
  approaches, regardless of whether model-based or importance-sampling
  based estimators are better.}
\label{fig:intro_exp}
\vspace{-0.4cm}
\end{figure}
}

A representative experimental result for the RL setting is displayed
in~\pref{fig:intro_exp}. Here we consider two different domains
from~\citet{voloshin2019empirical} and compare our new estimator,
\textsc{Slope}\xspace, with well-known baselines. Our method selects a false horizon
$\eta$, uses an unbiased importance sampling approach up to horizon
$\eta$, and then prematurely terminates the episode with a value
estimate from a parametric estimator (in this case trained via Fitted
Q iteration). Model selection focuses on choosing the false horizon
$\eta$, which yields parametric and trajectory-wise importance
sampling estimators as special cases (``Model'' and ``sampling'' in
the figure). Our experiments show that regardless of which of these
approaches dominates, \textsc{Slope}\xspace is competitive with the
best approach. Moreover, it outperforms \textsc{Magic}\xspace, the only other tuning
procedure for this setting.~\pref{sec:rl} contains more details and
experiments.

At a technical level, the fundamental challenge with estimator
selection is that there is no unbiased and low-variance approach for
comparing parameter choices. This precludes the use of cross
validation and related approaches, as estimating the error of a method
is itself an off-policy evaluation problem!
Instead, adapting ideas from nonparametric
statistics~\citep{lepski1997optimal,mathe2006lepskii}, our selection
procedure circumvents this error estimation problem by only using
variance estimates, which are easy to obtain. At a high level, we use
confidence bands for each estimator around their (biased) expectation
to find one that approximately balances bias and variance. This
balancing corresponds to the oracle choice, and so we obtain our
performance guarantee.

\paragraph{Related work.}
As mentioned, off-policy evaluation is a vibrant research area with
contributions from machine learning, econometrics, and statistics
communities.
Two settings of particular interest are contextual bandits and general
RL. For the former, recent and classical references
include~\cite{horvitz1952generalization,dudik2014doubly,hirano2003efficient,farajtabar2018more,su2019doubly}. For
the latter, please refer to~\citet{voloshin2019empirical}.

Parameter tuning is quite important for many off-policy evaluation
methods.~\citet{munos2016safe} observe that methods like
\textsc{Retrace} are fairly sensitive to the hyperparameter. Similarly
conclusions can be drawn from the experiments of~\citet{su2019cab} in
the contextual bandits context. Yet,
when tuning is required, most works resort to heuristics.  For
example, in~\citet{kallus2018policy}, a bandwidth hyperparameter is
selected by performing an auxiliary nonparametric estimation task,
while in~\citet{liu2018breaking}, it is selected as the median of the
distances between points. In both cases, no theoretical guarantees are
provided for such methods.

Indeed, despite the prevalence of hyperparameters in these methods, we
are only aware of two methods for estimator selection: the \textsc{Magic}\xspace
estimator~\citep{thomas2016data}, and the bound minimization approach
studied by~\citet{su2019doubly} (see also~\citet{wang2017optimal}).
Both approaches use MSE surrogates for estimator selection, where
\textsc{Magic}\xspace under-estimates the MSE and the latter uses an over-estimate.
The guarantees for both methods (asymptotic consistency, competitive
with unbiased approaches) are much weaker than our oracle inequality,
and \textsc{Slope}\xspace substantially outperforms \textsc{Magic}\xspace in experiments.



Our approach is based on Lepski's principle for bandwidth selection in
nonparametric
statistics~\citep{lepskii1992asymptotically,lepskii1991problem,lepskii1993asymptotically,lepski1997optimal}.
In this seminal work, Lepski studied nonparametric estimation problems
and developed a data-dependent bandwidth selection procedure that
achieves optimal adaptive guarantees, in settings where procedures
like cross validation do not apply (e.g., estimating a regression
function at a single given point). Since its introduction, Lepski's
methodology has been applied to other statistics
problems~\cite{birge2001alternative,mathe2006lepskii,goldenshluger2011bandwidth,kpotufe2013adaptivity,page2018goldenshluger},
but its use in machine learning has been limited. To our knowledge,
Lepski's principle has not been used for off-policy evaluation, which
is our focus.




\section{Setup}
\label{sec:setup}

We formulate the estimator selection problem generically, where there is an
abstract space $\Zcal$ and a distribution $\Dcal$ over $\Zcal$. We
would like to estimate some parameter $\theta^\star \defeq
\theta(\Dcal) \in \RR$, where $\theta$ is some known real-valued
functional, given access to $z_1,\ldots,z_n \iidsim \Dcal$. Let
$\hat{\Dcal}$ denote the empirical measure, that is the uniform
measure over the points $z_{1:n}$. 

To estimate $\theta^\star$ we use a finite set of $M$ estimators
$\{\theta_i\}_{i=1}^M$, where each $\theta_i: \Delta(\Zcal) \to
\RR$. Given the dataset, we form the estimates $\hat{\theta}_i \defeq
\theta_i(\hat{\Dcal})$. Ideally, we would choose the index that
minimizes the absolute error with $\theta^\star$, that is $\argmin_{i
  \in [M]} \abr{\hat{\theta}_i - \theta^\star}$. Of course this
\emph{oracle} index depends on the unknown parameter $\theta^\star$,
so it cannot be computed from the data.  Instead we seek a data-driven
approach for selecting an index $\hat{i}$ that approximately minimizes
the error.

To fix ideas, in the RL context, we may think of $\theta$ as the value
of a \emph{target policy} $\pi_{\mathrm{T}}$ and $z_{1:n}$ as $n$
trajectories collected by some \emph{logging policy} $\pi_{\mathrm{L}}$. The
estimators $\{\theta_i\}_{i=1}^M$ may be partial importance weighting
estimators~\cite{thomas2016data}, that account for policy mismatch on
trajectory prefixes of different length. 
These estimators modulate a bias variance tradeoff: importance
weighting short prefixes will have high bias but low variance, while
importance weighting the entire trajectory will be unbiased but have
high variance. We will develop this example in detail
in~\pref{sec:rl}.

For performance guarantees, we decompose the absolute error into two
terms: the bias and the deviation. For this decomposition, define
$\bar{\theta}_i \defeq \EE[\theta_i(\hat{D})]$ where the expectation
is over the random samples $z_{1:n}$. Then we have
\begin{align*}
\abr{\hat{\theta}_i - \theta^\star} \leq \abr{\bar{\theta}_i - \theta^\star} + \abr{\hat{\theta}_i - \bar{\theta}_i} \eqdef \textsc{bias}\xspace(i) + \textsc{dev}\xspace(i).
\end{align*}
As $\textsc{dev}\xspace(i)$ involves statistical fluctuations only, it is amenable to
concentration arguments, so we will assume access to a high
probability upper bound. Namely, our procedure uses a confidence
function $\textsc{cnf}\xspace$ that satisfies $\textsc{dev}\xspace(i) \leq \textsc{cnf}\xspace(i)$ for all $i \in
[M]$ with high probability. On the other hand, estimating the bias is
much more challenging, so we do not assume that the estimator has
access to $\textsc{bias}\xspace(i)$ or any sharp upper bound. Our goal is to select
an index $\hat{i}$ achieving an \emph{oracle inequality} of the form
\begin{align}
\label{eq:guarantee_form}
\abr{\hat{\theta}_{\hat{i}} - \theta^\star}
\leq \textsc{const}\xspace \times \min_{i}\cbr{\textsc{b}\xspace(i) + \textsc{cnf}\xspace(i)},
\end{align}
that holds with high probability where $\textsc{const}\xspace$ is a universal
constant and $\textsc{b}\xspace(i)$ is a sharp upper bound on
$\textsc{bias}\xspace(i)$.\footnote{Some assumptions prevent us from setting
  $\textsc{b}\xspace(i) = \textsc{bias}\xspace(i)$.}  
This guarantee certifies that the
selected estimator is competitive with the error bound for the best
estimator under consideration.

We remark that the above guarantee is qualitatively similar, but
weaker than the ideal guarantee of competing with the actual error of
the best estimator (as opposed to the error bound). In theory, this
difference is negligible as the two guarantees typically yield the
same statistical conclusions in terms of convergence
rates. Empirically we will see that ~\pref{eq:guarantee_form} does
yield strong practical performance.









\section{General Development}
\label{sec:general}

To obtain an oracle inequality of the form
in~\pref{eq:guarantee_form}, we require some benign assumptions. When
we turn to the case studies, we will verify that these assumptions
hold for our estimators.


  
\paragraph{Validity and Monotonicity.}
The first basic property on the bias and confidence functions is that
they are valid in the sense that they actually upper bound the
corresponding terms in the error decomposition. 
\begin{assum}[Validity]
\label{assum:concentration}
We assume
\ifthenelse{\equal{arxiv}{arxiv}}{}{\vspace{-3pt}}
\begin{packed_enum}
\item (Bias Validity) $\abr{\bar{\theta}_i - \theta^\star} \leq
  \textsc{b}\xspace(i)$ for all $i$.
\item (Confidence Validity) With probability at least $1-\delta$,
  $|\hat{\theta}_i - \bar{\theta}_i| \leq \textsc{cnf}\xspace(i)$  for all $i$.
\end{packed_enum}
\ifthenelse{\equal{arxiv}{arxiv}}{}{\vspace{-3pt}}
\end{assum}
Typically $\textsc{cnf}\xspace$ can be constructed using straightforward
concentration arguments such as Bernstein's inequality. Importantly,
$\textsc{cnf}\xspace$ does not have to account for the bias, so the term $\textsc{dev}\xspace$ that
we must control is centered. We also note that $\textsc{cnf}\xspace$ need not be
deterministic, for example it can be derived from empirical Bernstein
inequalities. We emphasize again that the estimator does not have
access to $\textsc{b}\xspace(i)$.



We also require a monotonicity property on these functions.
\begin{assum}[Monotonicity]
\label{assum:monotonicity}
We assume that there exists a constant $\kappa > 0$ such that for all
$i \in [M-1]$
\ifthenelse{\equal{arxiv}{arxiv}}{}{\vspace{-3pt}}
\begin{packed_enum}
\item $\textsc{b}\xspace(i) \leq \textsc{b}\xspace(i+1)$.
\item $\kappa\cdot\textsc{cnf}\xspace(i) \leq \textsc{cnf}\xspace(i+1) \leq \textsc{cnf}\xspace(i)$.
\end{packed_enum}
\ifthenelse{\equal{arxiv}{arxiv}}{}{\vspace{-3pt}}
\end{assum}

In words, the estimators should be ordered so that the bias is
monotonically increasing and the confidence is decreasing but not too
quickly, as parameterized by the constant $\kappa$.
This structure is quite natural when estimators navigate a
bias-variance tradeoff: when an estimator has low bias it typically
also has high variance and vice versa.
It is also straightforward to enforce a decay rate for $\textsc{cnf}\xspace$ by
selecting the parameter set appropriately. We will see how to do this
in our case studies.



\paragraph{The \textsc{Slope}\xspace procedure.}
\textsc{Slope}\xspace is an acronym for ``Selection by Lepski's principle for
Off-Policy Evaluation.'' As the name suggests, the approach is based
on Lepski's principle~\cite{lepski1997optimal} and is defined as
follows. We first define intervals
\begin{align*}
I(i) \defeq [\hat{\theta}_i - 2\textsc{cnf}\xspace(i), \hat{\theta}_i + 2\textsc{cnf}\xspace(i)],
\end{align*}
and we then use the intersection of these intervals to select an index
$\hat{i}$. Specifically, the index we select is
\begin{align*}
\hat{i} \defeq \max\cbr{i \in [M]: \cap_{j=1}^i I(j) \ne \emptyset}.
\end{align*}
In words, we select the largest index such that the intersection of
all previous intervals is non-empty. See~\pref{fig:illustration}
for an illustration.

\ifthenelse{\equal{arxiv}{arxiv}}{
\begin{wrapfigure}{R}{0.5\textwidth}
\begin{center}

\begin{tikzpicture}[scale=1.5]
\draw[|-|] (0,0) -- (0,2); \draw[|-|] (0,0.99) -- (0,1.01); \node at (-0.2,1) {$\hat{\theta}_1$};
\draw[|-|] (1,0.3) -- (1,1.3); \draw[|-|] (1,0.79) -- (1,0.81); \node at (0.8,0.8) {$\hat{\theta}_2$};
\draw[|-|] (2,1.0) -- (2,1.5);  \draw[|-|] (2,1.24) -- (2,1.26); \node at (1.8,1.25) {$\hat{\theta}_3$};
\draw[|-|] (3,0.4) -- (3,0.65); \draw[|-|] (3,0.515) -- (3,0.535); \node at (2.8,0.525) {$\hat{\theta}_4$};
\draw[|-|] (4,0.1) -- (4,0.225);  \draw[|-|] (4,0.1525) -- (4,0.1725); \node at (3.8,0.1625) {$\hat{\theta}_5$};
\node at (2,0) {$\hat{i} = 3$};
\draw[decoration={brace,mirror},decorate] (0.1,1) -- node[right=3pt] {$2\textsc{cnf}\xspace(1)$} (0.1,2);
\draw[decoration={brace,mirror},decorate] (1.1,0.3) -- node[right=3pt] {$I(2)$} (1.1,1.3);
\draw[decoration={brace,mirror},decorate] (2.1,1) -- node[right=3pt] {$I(3)$} (2.1,1.5);
\path [fill=blue,opacity=0.2] (0,1) rectangle (4,1.25);
\node[blue] at (3.5,1.125) {$\cap_{i=1}^3 I(i)$};
\end{tikzpicture}
 \end{center}
\vspace{-0.5cm}
\caption{Illustration of \textsc{Slope}\xspace with $M=5$. As $\cap_{i=1}^3 I(i)$ is
  non-empty but $I(4)$ does not intersect with $I(3)$, we select
  $\hat{i}=3$.}
\vspace{-0.5cm}
\label{fig:illustration}
\end{wrapfigure}
}{
\begin{figure}
\begin{center}

\begin{tikzpicture}[scale=1.5]
\draw[|-|] (0,0) -- (0,2); \draw[|-|] (0,0.99) -- (0,1.01); \node at (-0.2,1) {$\hat{\theta}_1$};
\draw[|-|] (1,0.3) -- (1,1.3); \draw[|-|] (1,0.79) -- (1,0.81); \node at (0.8,0.8) {$\hat{\theta}_2$};
\draw[|-|] (2,1.0) -- (2,1.5);  \draw[|-|] (2,1.24) -- (2,1.26); \node at (1.8,1.25) {$\hat{\theta}_3$};
\draw[|-|] (3,0.4) -- (3,0.65); \draw[|-|] (3,0.515) -- (3,0.535); \node at (2.8,0.525) {$\hat{\theta}_4$};
\draw[|-|] (4,0.1) -- (4,0.225);  \draw[|-|] (4,0.1525) -- (4,0.1725); \node at (3.8,0.1625) {$\hat{\theta}_5$};
\node at (2,0) {$\hat{i} = 3$};
\draw[decoration={brace,mirror},decorate] (0.1,1) -- node[right=3pt] {$2\textsc{cnf}\xspace(1)$} (0.1,2);
\draw[decoration={brace,mirror},decorate] (1.1,0.3) -- node[right=3pt] {$I(2)$} (1.1,1.3);
\draw[decoration={brace,mirror},decorate] (2.1,1) -- node[right=3pt] {$I(3)$} (2.1,1.5);
\path [fill=blue,opacity=0.2] (0,1) rectangle (4,1.25);
\node[blue] at (3.5,1.125) {$\cap_{i=1}^3 I(i)$};
\end{tikzpicture}
 \end{center}
\vspace{-0.4cm}
\caption{Illustration of \textsc{Slope}\xspace with $M=5$. As $\cap_{i=1}^3 I(i)$ is
  non-empty but $I(4)$ does not intersect with $I(3)$, we select
  $\hat{i}=3$.}
\vspace{-0.4cm}
\label{fig:illustration}
\end{figure}
}

The intuition is to adopt an optimistic view of the bias function
$\textsc{b}\xspace(i)$. First observe that if $\textsc{b}\xspace(i) = 0$ then,
by~\pref{assum:concentration}, we must have $\theta^\star \in
I(i)$. 
Reasoning optimistically, it is
possible that we have $\textsc{b}\xspace(i) = 0$ for all $i \leq \hat{i}$, since
by the definition of $\hat{i}$ there exists a choice of $\theta^\star$
that is consistent with all intervals. As $\textsc{cnf}\xspace(\hat{i})$ is the
smallest among these, index $\hat{i}$ intuitively has lower error than
all previous indices. On the other hand, it is not possible to have
$\textsc{b}\xspace(\hat{i}+1) = 0$, since there is no consistent choice for
$\theta^\star$ and the bias is monotonically increasing. In fact, if
$\theta^\star \in I_{\hat{i}}$, then we must actually have
$\textsc{b}\xspace(\hat{i}+1) \geq \textsc{cnf}\xspace(\hat{i}+1)$, since the intervals have
width $4\textsc{cnf}\xspace(\cdot)$. Finally, since $\textsc{cnf}\xspace(\cdot)$ does not shrink
too quickly, all subsequent indices cannot be much better than
$\hat{i}$, the index we select. Of course, we may not have
$\theta^\star \in I_{\hat{i}}$, so this argument does not constitute a
proof of correctness, which is deferred to~\pref{app:proofs}.



\paragraph{Theoretical analysis.}
We now state the main guarantee.
\begin{theorem}
\label{thm:main}
Under~\pref{assum:concentration} and~\pref{assum:monotonicity}, we have that with probability at least $1-\delta$:
\begin{align*}
\abr{\hat{\theta}_{\hat{i}} - \theta^\star} &\leq 6(1+\kappa^{-1})\min_i\cbr{\textsc{b}\xspace(i) + \textsc{cnf}\xspace(i)}.
\end{align*}
\end{theorem}
The theorem verifies that the index $\hat{i}$ satisfies an oracle
inequality as in~\pref{eq:guarantee_form}, with $\textsc{const}\xspace =
6(1+\kappa^{-1})$.  This is the best guarantee one could hope for, up
to the constant factor and the caveat that we are competing with the
error bound instead of the error, which we have already discussed.
For off-policy evaluation, we are not aware of any other approaches
that achieve any form of oracle inequality. The closest comparison is
the bound minimization approach of~\citet{su2019doubly}, which is
provably competitive only with unbiased indices (with $\textsc{b}\xspace(i) =
0$). However in finite sample, these indices could have high variance
and consequently worse performance than some biased estimator. In this
sense, the \textsc{Slope}\xspace guarantee is much stronger.

While our main result gives a high probability absolute error bound,
it is common in the off-policy evaluation literature to instead
provide bounds on the mean squared error. Via a simple translation
from the high-probability guarantee, we can obtain a MSE bound here as
well. For this result, we use the notation $\textsc{cnf}\xspace(i;\delta)$ to
highlight the fact that the confidence bounds hold with probability
$1-\delta$.

\begin{corollary}[MSE bound]
\label{corr:mse}
In addition to~\pref{assum:concentration}
and~\pref{assum:monotonicity}, assume that $\theta^\star,
\hat{\theta}_i\in [0,R]$ a.s., $\forall i$, and that $\textsc{cnf}\xspace$ is
deterministic.\footnote{The restriction to deterministic confidence functions can easily be removed with another concentration argument.}  Then for any $\delta > 0$,
\begin{align*}
\EE (\hat{\theta}_{\hat{i}} - \theta^\star)^2 \leq \nicefrac{C}{\kappa^2} \min_{i}\cbr{\textsc{b}\xspace(i)^2 + \textsc{cnf}\xspace(i;\delta)^2} +
R^2\delta,
\end{align*}
where $C > 0$ is a universal constant.\footnote{We have not attempted
  to optimize the constant, which can can be extracted from our proof
  in~\pref{app:proofs}.}
\end{corollary}
We state this bound for completeness but remark that it is typically
loose in constant factors because it is proven through a high
probability guarantee. In particular, we typically require $\textsc{cnf}\xspace(i) >
\sqrt{\textsc{var}\xspace(i)}$ to satisfy~\pref{assum:concentration}, 
which is already loose in comparison with a more direct MSE bound.
Unfortunately, Lepski's principle cannot provide direct MSE bounds
without estimating the MSE itself, which is precisely the problem we
would like to avoid. On the other hand, the high probability guarantee
provided by~\pref{thm:main} is typically more practically meaningful.



\section{Application 1: continuous contextual bandits}
\label{sec:ccb}
For our first application, we consider a contextual bandit setting
with continuous action space, following~\citet{kallus2018policy}. Let
$\Xcal$ be a context space and $\Acal = [0,1]$ be a univariate
real-valued action space. There is a distribution $\Pcal$ over
context-reward pairs, which is supported on $(\Xcal, \Acal \to
[0,1])$. We have a stochastic logging policy $\pi_{\mathrm{L}}: \Xcal \to
\Delta(\Acal)$ which induces the distribution $\Dcal$ by generating
tuples $\{(x_i,a_i,r_i(a_i),\pi_{\mathrm{L}}(a_i))\}_{i=1}^n$, where $(x_i,r_i)
\sim \Pcal$, $a_i \sim \pi_{\mathrm{L}}(x_i)$, only $r_i(a_i)$ is observed, and
$\pi_{\mathrm{L}}(a_i)$ denotes the density value. This is a bandit setting as
the distribution $\Pcal$ specifies rewards for all actions, but only
the reward for the chosen action is available for estimation.

For off-policy evaluation, we would like to estimate the value of some
target policy $\pi_{\mathrm{T}}$, which is given by $V(\pi_{\mathrm{T}}) \defeq
\EE_{(x,r) \sim \Pcal,a\sim\pi_{\mathrm{T}}(x)}\sbr{r(a)}$.
Of course, we do not have sample access to $\Pcal$ and must resort to
the logged tuples generated by $\pi_{\mathrm{L}}$. A standard off-policy
estimator in this setting is
\begin{align*}
\hat{V}_h(\pi_{\mathrm{T}}) := \frac{1}{nh}\sum_{i=1}^n \frac{K( |\pi_{\mathrm{T}}(x_i)- a_i|/h) r_i(a_i)}{\pi_{\mathrm{L}}(a_i)},
\end{align*}
where $K: \RR_+ \to \RR$ is a \emph{kernel function} (e.g., the boxcar
kernel $K(u) = \frac{1}{2} \one\{u \leq 1\}$).
This
estimator has appeared in recent
work~\citep{kallus2018policy,krishnamurthy2019contextual}.  The key
parameter is the bandwidth $h$, which modulates a bias-variance
tradeoff, where smaller bandwidths have lower bias but higher
variance.


\subsection{Theory}
For a simplified exposition, we instantiate our general framework 
when (1) $\pi_{\mathrm{L}}$ is the uniform logging
policy, (2) $K$ is the boxcar kernel, and (3) we assume that
$\pi_{\mathrm{T}}(x) \in [\gamma_0,1-\gamma_0]$ for all $x$. These
simplifying assumptions help clarify the results, but they are not
fundamentally limiting. 



Fix $\gamma \in (0,1)$ and let $\Hcal \defeq \{\gamma_0 \gamma^{M-i}:
1 \leq i \leq M\}$ denote a geometrically spaced grid of $M$ bandwidth
values. Let $\hat{\theta}_i \defeq \hat{V}_{h_i}(\pi_{\mathrm{T}})$. For the
confidence term,
in~\pref{app:proofs}, we show that we can set
\begin{align}
\textsc{cnf}\xspace(i) \defeq \sqrt{\frac{2 \log(2M/\delta)}{nh_i}} + \frac{2\log(2M/\delta)}{3nh_i} \label{eq:ccb_conf}
\end{align}
and this satisfies~\pref{assum:concentration}. With this form, it is not hard
to see that the second part of~\pref{assum:monotonicity} is also
satisfied, and so we obtain the following result.

\begin{theorem}
\label{thm:ccb}
Consider the setting above with uniform $\pi_{\mathrm{L}}$, boxcar kernel, and
$\Hcal$ as defined above. Let $\textsc{b}\xspace$ be any valid and monotone bias
function, and define \textsc{cnf}\xspace as
in~\pref{eq:ccb_conf}. Then~\pref{assum:concentration}
and~\pref{assum:monotonicity} are satisfied with $\kappa=\gamma$,
so the guarantee in~\pref{thm:main} applies.

In particular, if $\gamma,\gamma_0$ are constants and
rewards are $L$-Lipschitz, for $\omega(\sqrt{\log(\log(n))/n}) \leq L
\leq O(n)$, then \begin{align*}
\abr{\hat{\theta}_{\hat{i}} - \theta^\star} \leq O\rbr{\rbr{\frac{L\log(\log(n)/\delta)}{n}}^{1/3}}
\end{align*}
with probability at least $1-\delta$, \emph{without knowledge of the
  Lipschitz constant $L$.}
\end{theorem}

For the second statement, we remark that if the Lipschitz constant
were known, the best error rate achievable is $O(
(L\log(1/\delta)/n)^{1/3})$. 
Thus, \textsc{Slope}\xspace incurs almost no price for adaptation. We also note that
it is typically impossible to know this parameter in practice.

It is technical but not difficult to derive a more general result,
relaxing many of the simplifying assumptions we have made.
To this end, we provide a guarantee for non-uniform $\pi_{\mathrm{L}}$ in the
appendix. We do not pursue other extensions here, as the necessary
techniques are well-understood
(c.f.,~\citet{kallus2018policy,krishnamurthy2019contextual}).

\subsection{Experiments}
\label{sec:cb_exp}

We empirically evaluate using \textsc{Slope}\xspace for bandwidth selection in a
synthetic environment for continuous action contextual bandits. We
summarize the experiments and findings here with detailed description
in~\pref{app:ccb_exp}.\footnote{Code for this section is publicly
  available at
  \url{https://github.com/VowpalWabbit/slope-experiments}.}

\ifthenelse{\equal{arxiv}{arxiv}}{
\begin{wraptable}{R}{0.46\textwidth}
\begin{center}
\vspace{-0.85cm}
\begin{tabular}{| c |}
\hline
Reward fn $\in \{ \textrm{quadratic, absolute value} \}$\\
\hline
Lipschitz const $\in \{0.1,0.3,1,3,10\}$\\
\hline
Kernel $\in \{\textrm{boxcar, Epanechnikov}\}$\\
\hline
$\pi_{\mathrm{T}} \in \{\textrm{linear, tree}\}$\\
\hline
$\pi_{\mathrm{L}} \in \{\textrm{linear, tree}\}$\\
\hline
Randomization $\in \{\textrm{unif, friendly, adversarial}\}$\\
\hline
Samples $\in \{10^i : i \in \{1,2,3,4,5\}\}$\\
\hline
\end{tabular}
\vspace{-0.25cm}
\caption{Contextual Bandit experiment conditions.}
\vspace{-0.65cm}
\label{tab:cb_conds}
\end{center}
\end{wraptable}
}{
\begin{table}
\begin{center}
\begin{tabular}{| c |}
\hline
Reward fn $\in \{ \textrm{quadratic, absolute value} \}$\\
\hline
Lipschitz const $\in \{0.1,0.3,1,3,10\}$\\
\hline
Kernel $\in \{\textrm{boxcar, Epanechnikov}\}$\\
\hline
$\pi_{\mathrm{T}} \in \{\textrm{linear, tree}\}$\\
\hline
$\pi_{\mathrm{L}} \in \{\textrm{linear, tree}\}$\\
\hline
Randomization $\in \{\textrm{uniform, friendly, adversarial}\}$\\
\hline
Samples $\in \{10^i : i \in \{1,2,3,4,5\}\}$\\
\hline
\end{tabular}
\caption{Contextual Bandit experimental conditions.}
\vspace{-0.4cm}
\label{tab:cb_conds}
\end{center}
\end{table}
}
\vspace{-0.2em}
\paragraph{The environment.}
We use a highly configurable synthetic environment,
which
allows for action spaces of arbitrary dimension, varying reward
function, reward smoothness, kernel, target, and logging
policies. In our experiments, we focus on $\Acal = [0,1]$. We vary all
other parameters, as summarized in~\pref{tab:cb_conds}.

The simulator prespecifies a mapping $x \mapsto a^\star(x)$ which is
the global maxima for the reward function. We train deterministic
policies by regressing from the context to this global maxima.
For the logging policy, we use two ``softening'' approaches
for randomization,
following~\citet{farajtabar2018more}. We use two regression models
(linear, decision tree), and two softenings in addition to uniform
logging, for a total of 5 logging and 2 target policies.

\vspace{-0.2em}
\paragraph{Methods.}
We consider 7 different choices of geometrically spaced bandwidths
$\Hcal \defeq \{2^{-i}:i \in [7]\}$. We evaluate the performance of
these fixed bandwidths in comparison with \textsc{Slope}\xspace, which selects from
$\Hcal$. For \textsc{Slope}\xspace, we simplify the implementation by replacing the
confidence function in~\pref{eq:ccb_conf}, with twice the empirical
standard deviation of the corresponding estimate. This approximation
is a valid asymptotic confidence interval and is typically sharper
than~\pref{eq:ccb_conf}, so we expect it to yield better practical
performance. We also manually enforce monotonicity of this confidence
function.

We are not aware of other viable baselines for this setting. In
particular, the heuristic method of~\citet{kallus2018policy} is too
computationally intensive to use at our scale.


\vspace{-0.2em}
\paragraph{Experiment setup.}
We have 1000 conditions determined by: logging
policy, target policy, reward functional form, reward smoothness,
kernel, and number of samples $n$. For each condition, we first obtain a
Monte Carlo estimate of the ground truth $V(\pi_{\mathrm{T}})$ by collecting
100k samples from $\pi_{\mathrm{T}}$.  Then we collect $n$ trajectories from
$\pi_{\mathrm{L}}$ and evaluate the squared error of each method $(\hat{V} -
V(\pi_{\mathrm{T}}))^2$. We perform 30 replicates of each condition with
different random seeds and calculate the correspond mean squared error
(MSE) for each method: $\mathrm{MSE} := \frac{1}{30}\sum_{i=1}^{30}
(\hat{V}_i - V(\pi_{\mathrm{T}}))^2$ where $\hat{V}_i$ is the estimate on the
$i^{\textrm{th}}$ replicate.

\begin{figure*}
\includegraphics[width=\textwidth]{./cb_ecdf.pdf}
\ifthenelse{\equal{arxiv}{arxiv}}{\vspace{-0.5cm}}{\vspace{-0.75cm}}
\caption{Experimental results for contextual bandits with continuous
  actions. Left: CDF of normalized MSE across all 480
  conditions. Normalization is by the worst MSE for that
  condition. Middle: Pairwise comparison matrix, entry $P_{i,j}$
  counts the fraction of conditions where method $i$ is statistically
  significantly better than method $j$, so larger numbers in the rows
  (or smaller numbers in the columns) is better. Right: asymptotic
  behavior of \textsc{Slope}\xspace selecting between two bandwidths. }
\vspace{-0.25cm}
\label{fig:cb_exp}
\end{figure*}


\paragraph{Results.}
The left panel of~\pref{fig:cb_exp} aggregates results via the
empirical CDF of the normalized MSE, where we normalize by the worst
MSE in each condition. The point $(x,y)$ indicates that on
$y$-fraction of conditions the method has normalized MSE at most $x$,
so better methods lie in the top-left quadrant. We see that \textsc{Slope}\xspace is
the top performer in comparison with the fixed bandwidths.

In the center panel, we record the results of pairwise comparisons
between all methods. Entry $(i,j)$ of this array is the fraction of
conditions where method $i$ is significantly better than method $j$
(using a paired $t$-test with significance level $0.05$). Better
methods have smaller numbers in their column, which means they are
typically not significantly worse than other methods. The final
row summarizes the results by averaging each column. In this
aggregation, \textsc{Slope}\xspace also outperforms each individual fixed bandwidth,
demonstrating the advantage in data-dependent estimator selection.

Finally, in the right panel, we demonstrate the behavior of \textsc{Slope}\xspace in
a single condition as $n$ increases. Here \textsc{Slope}\xspace is only selecting
between two bandwidths $\Hcal\defeq\{1/4,1/32\}$. When $n$ is small,
the small bandwidth has high variance but as $n$ increases, the bias
of the larger bandwidth dominates. \textsc{Slope}\xspace effectively
navigates this tradeoff, tracking $h=1/4$ when $n$ is small, and
switching to $h=1/32$ as $n$ increases.

\paragraph{Summary.}
\textsc{Slope}\xspace is the top performer when compared with fixed bandwidths in
our experiments. This is intuitive as we do not expect a single
fixed bandwidth to perform well across all conditions. On the other
hand, we are not aware of other approaches for bandwidth selection in
this setting, and our experiments confirm that \textsc{Slope}\xspace is a viable and
practically effective approach.


\section{Application 2: reinforcement learning}
\label{sec:rl}

Our second application is multi-step reinforcement learning (RL). We
consider episodic RL where the agent interacts with the environment in
episodes of length $H$. Let $\Xcal$ be a state space and $\Acal$ a
finite action space. In each episode, a trajectory $\tau \defeq
(x_1,a_1,r_1,x_2,a_2,r_2,\ldots,x_H,a_H,r_H)$ is generated where (1)
$x_1\in\Xcal$ is drawn from a starting distribution $P_0$, (2) rewards
$r_h \in \RR$ and next state $x_{h+1}\in\Xcal$ are drawn from a system
descriptor $(r_h,x_{h+1})\sim P_+(x_h,a_h)$ for each $h$ (with the
obvious definition for time $H$), and (3) actions $a_1,\ldots,a_H \in
\Acal$ are chosen by the agent. A policy $\pi : \Xcal \mapsto
\Delta(\Acal)$ chooses a (possibly stochastic) action in each state
and has value $V(\pi) \defeq \EE\sbr{\sum_{h=1}^H \gamma^{h-1} r_h
  \mid a_{1:H}\sim\pi}$, where $\gamma \in (0,1)$ is a discount
factor.
For normalization, we assume that rewards are in $[0,1]$ almost
surely.

\ifthenelse{\equal{arxiv}{arxiv}}{
\begin{wraptable}{R}{0.55\textwidth}
  \begin{center}
    \vspace{-0.4cm}
    \begin{tabular}{|c|c|c|c|c|} 
      \hline
      \text{Environment} & \text{GW} & \text{MC}  & \text{Graph} & \text{PO-Graph}\\
      \hline
      \text{Horizon} & 25 & 250 & 16 & 16\\
      \text{MDP} & \text{Yes} & \text{Yes} & \text{Yes} & \text{No} \\
      \text{Sto Env} & \text{Both} & \text{No} & \text{Yes} & \text{Yes}\\
      \text{Sto Rew} & \text{No} & \text{No} & \text{Both} &\text{Both}\\
      \text{Sparse Rew} & \text{No} & \text{No} & \text{Both} &\text{Both} \\
      \text{Model class} & \text{Tabular} & \text{NN} &\text{Tabular} &\text{Tabular}\\
      \text{Samples} & $2^{7:9}$ & $2^{8:10}$ & $2^{7:10}$ & $2^{7:10}$\\
      \text{\# of policies} & 5 & 4 & 2 & 2\\
            \hline
    \end{tabular}
    \vspace{-0.25cm}
    \caption{RL Environment Details}
    \vspace{-0.6cm}
    \label{tab:envs}
  \end{center}
\end{wraptable}
}{
\begin{table}[t]
  \begin{center}
    \begin{tabular}{|c|c|c|c|c|} 
      \hline
      \text{Environment} & \text{GW} & \text{MC}  & \text{Graph} & \text{PO-Graph}\\
      \hline
      \text{Horizon} & 25 & 250 & 16 & 16\\
      \text{MDP} & \text{Yes} & \text{Yes} & \text{Yes} & \text{No} \\
      \text{Sto Env} & \text{Both} & \text{No} & \text{Yes} & \text{Yes}\\
      \text{Sto Rew} & \text{No} & \text{No} & \text{Both} &\text{Both}\\
      \text{Sparse Rew} & \text{No} & \text{No} & \text{Both} &\text{Both} \\
      \text{Model class} & \text{Tabular} & \text{NN} &\text{Tabular} &\text{Tabular}\\
      \text{Samples} & $2^{7:9}$ & $2^{8:10}$ & $2^{7:10}$ & $2^{7:10}$\\
      \text{\# of policies} & 5 & 4 & 2 & 2\\
            \hline
    \end{tabular}
    \vspace{-0.4cm}
    \caption{RL Environment Details}
    \vspace{-0.5cm}
    \label{tab:envs}
  \end{center}
\end{table}
}

For off-policy evaluation, we have a dataset of $n$
trajectories
$\{(x_{i,1},a_{i,1},r_{i,1},\ldots,x_{i,H},a_{i,H},r_{i,H})\}_{i=1}^n$
generated by following some logging policy $\pi_{\mathrm{L}}$, and we would like
to estimate $V(\pi_{\mathrm{T}})$ for some other target policy. 
The importance weighting approach is also standard here,
and perhaps the simplest estimator is
\begin{align}
\hat{V}_{\mathrm{IPS}}(\pi_{\mathrm{T}}) \defeq \frac{1}{n}\sum_{i=1}^n \sum_{h=1}^H \gamma^{h-1} \rho_{i,h} r_{i,h},\label{eq:rl_ips}
\end{align}
where $\rho_{i,h} \defeq \prod_{h'=1}^h\tfrac{\pi_{\mathrm{T}}(a_{i,h'} \mid
  x_{i,h'})}{\pi_{\mathrm{L}}(a_{i,h'} \mid x_{i,h'})}$ is the step-wise
importance weight.  This estimator is provably unbiased under very
general conditions, but it suffers from high variance due to the
$H$-step product of density ratios.\footnote{We note that there are
  variants with improved variance. As our estimator selection question
  is somewhat orthogonal, we focus on the simplest estimator.} An
alternative approach is to directly model the value function using
supervised learning, as in a regression based dynamic programming
algorithm like Fitted Q
Evaluation~\citep{riedmiller2005neural,szepesvari2005finite}.
While these ``direct modeling'' approaches have very low variance,
they are typically highly biased because they rely on supervised
learning models that cannot capture the complexity of the environment.
Thus they lie on the other extreme of the bias-variance spectrum.


To navigate this tradeoff,~\citet{thomas2016data} propose a family of
\emph{partial importance weighting estimators}. To instantiate this
family, we first train a direct model $\hat{V}_{\mathrm{DM}} : \Xcal
\times [H] \to \RR$ to approximate $(x,h) \mapsto
\EE_{\pi}\sbr{\sum_{h'=h}^H\gamma^{h'-h}r_{h'} \mid x_h=x}$, for
example via Fitted Q Evaluation.  Then, the estimator is
\ifthenelse{\equal{arxiv}{arxiv}}{
\begin{align}
\label{eq:partial_ips}
\hat{V}_{\eta}(\pi_{\mathrm{T}}) & \defeq \frac{1}{n}\sum_{i=1}^n
\sum_{h=1}^\eta \gamma^{h-1} \rho_{i,h} r_{i,h} +
\frac{1}{n}\sum_{i=1}^n 
\gamma^\eta\rho_{i,\eta}\hat{V}_{\mathrm{DM}}(x_{i,\eta+1},\eta+1),
\end{align}
}{
\begin{align}
\label{eq:partial_ips}
\hat{V}_{\eta}(\pi_{\mathrm{T}}) & \defeq \frac{1}{n}\sum_{i=1}^n
\sum_{h=1}^\eta \gamma^{h-1} \rho_{i,h} r_{i,h} \\
& ~~~~ +
\frac{1}{n}\sum_{i=1}^n 
\gamma^\eta\rho_{i,\eta}\hat{V}_{\mathrm{DM}}(x_{i,\eta+1},\eta+1),\notag
\end{align}
}
The estimator has a parameter $\eta$ that governs a \emph{false
  horizon} for the importance weighting component. Specifically, we
only importance weight the rewards up until time step $\eta$ and we
complete the trajectory with the predictions from a direct modeling
approach. 
The model selection question here centers around choosing the
false horizon $\eta$ at which point we truncate the unbiased
importance weighted estimator. 

\subsection{Theory}
We instantiate our general estimator selection framework in this
setting.  Let $\hat{\theta}_i \defeq \hat{V}_{H-i+1}(\pi_{\mathrm{T}})$ for
$i \in \{1,\ldots,H+1\}$. Intuitively, we expect that the variance of
$\hat{\theta}_i$ is large for small $i$, since the estimator involves
a product of many density ratios. Indeed, in the appendix, we derive a
confidence bound and prove that it verifies our assumptions. The bound
is quite complicated so we do not display it here, but we refer the
interested reader to~\pref{eq:rl_dev} in~\pref{app:proofs}. The bound
is a Bernstein-type bound which incorporates both variance and range
information. We bound these as
\ifthenelse{\equal{arxiv}{arxiv}}{
\begin{align*}
\textrm{Variance}(\hat{V}_\eta(\pi_{\mathrm{T}})) \leq 3V_{\mathrm{max}}^2(1 + \sum_{h=1}^\eta \gamma^{2(h-1)}p_{\mathrm{max}}^h), \qquad 
\textrm{Range}(\hat{V}_\eta(\pi_{\mathrm{T}})) \leq 3V_{\mathrm{max}} (1+\sum_{h=1}^\eta \gamma^{h-1}p_{\mathrm{max}}^h),
\end{align*}
}{
\begin{align*}
\textrm{Variance}(\hat{V}_\eta(\pi_{\mathrm{T}})) \leq 3V_{\mathrm{max}}^2(1 + \sum_{h=1}^\eta \gamma^{2(h-1)}p_{\mathrm{max}}^h)\\
\textrm{Range}(\hat{V}_\eta(\pi_{\mathrm{T}})) \leq 3V_{\mathrm{max}} (1+\sum_{h=1}^\eta \gamma^{h-1}p_{\mathrm{max}}^h),
\end{align*}
}
where $V_{\mathrm{max}}\defeq (1-\gamma)^{-1}$ is the range of the value function
and $p_{\mathrm{max}} \defeq \sup_{x,a}\tfrac{\pi_{\mathrm{T}}(a \mid x)}{\pi_{\mathrm{L}}(a \mid
  x)}$ is the maximum importance weight, which should be
finite. Equipped with these bounds, we can apply Bernstein's
inequality to obtain a valid confidence interval.\footnote{This yields
  a relatively concise deviation bound, but we note that it is not the
  sharpest possible.} Moreover, it is not hard to show that this
confidence interval is monotonic with $\kappa \defeq
(1 + \gamma p_{\mathrm{max}})^{-1}$. This yields the following theorem.
\begin{theorem}[Informal]
\label{thm:rl}
Consider the episodic RL setting with $\hat{\theta}_i \defeq
\hat{V}_{H-i+1}(\pi_{\mathrm{T}})$ defined in~\pref{eq:partial_ips}. Let
$\textsc{b}\xspace$ be any valid and monotone bias function. Then with $\textsc{cnf}\xspace(i)$
as in~\pref{eq:rl_dev} in the appendix,~\pref{assum:concentration} and 
~\pref{assum:monotonicity} with
$\kappa \defeq(1+\gammap_{\mathrm{max}})^{-1}$ hold, so~\pref{thm:main} applies.
\end{theorem}
A more precise statement is provided in~\pref{app:proofs}, and we
highlight some salient details here. First, our analysis actually
applies to a doubly-robust variant of the estimator $\hat{V}_\eta$, in
the spirit of~\citep{jiang2015doubly}.  Second, $\textsc{b}\xspace(i) \defeq
\tfrac{\gamma^{H-i+1}-\gamma^H}{1-\gamma}$ is valid and monotone, and
can be used to obtain a concrete error bound.
However, 
the oracle inequality yields a stronger conclusion, since it applies
for \emph{any} valid and monotone bias function. This universality is
particularly important when using the doubly robust variant, since it
is typically not possible to sharply bound the bias.

The closest comparison is \textsc{Magic}\xspace~\citep{thomas2016data}, which is
strongly consistent in our setting. However, it does not satisfy any
oracle inequality and is dominated by \textsc{Slope}\xspace in experiments.



\subsection{Experiments}
We evaluate \textsc{Slope}\xspace in RL environments spanning 106 different
experimental conditions.
We also compare with previously proposed estimators and assess robustness under various conditions.
Our experiments closely follow the setup
of~\citet{voloshin2019empirical}. Here we provide an overview of the
experimental setup and highlight the salient differences from
theirs. All experimental details are
in~\pref{app:rl_exp}.\footnote{Code for this section is available at \url{https://github.com/clvoloshin/OPE-tools}.}


\paragraph{The environments.}
We use four RL environments: Mountain Car, Gridworld, Graph, and
Graph-POMDP (abbreviated MC, GW, Graph, and PO-Graph). All four
environments are from~\citet{voloshin2019empirical}, and they provide
a broad array of environmental conditions, varying in terms of horizon
length, partial observability, stochasticity in dynamics,
stochasticity in reward, reward sparsity, whether function
approximation is required, and overlap between logging and target
policies. Logging and target policies are
from~\citet{voloshin2019empirical}. A summary of the environments and
their salient characteristics is displayed in~\pref{tab:envs}.



\begin{figure*}[tb]
\includegraphics[width=\textwidth]{combined_RL.pdf}
\vspace{-0.5cm}
\caption{Left: Cumulative distribution function of the normalized MSE for all conditions, Middle: Pairwise comparison matrix $P$ for the methods, over all conditions. Element $P_{ij}$ denotes the percentage of times that method $i$ outperforms method $j$. The last row shows the column average for each method, the lower the better. Right: Learning Curve for the Hybrid domain.}
\label{fig:rl_fig}
\vspace{-0.25cm}
\end{figure*}


\paragraph{Methods.}
We compare four estimators: the direct model (DM), a self-normalized
doubly robust estimator (WDR), (c) \textsc{Magic}\xspace, and (d) \textsc{Slope}\xspace. All four
methods use the same direct model, which we train either by Fitted Q
Evaluation or by $Q^\pi(\lambda)$~\citep{munos2016safe}, following the
guidelines in~\citet{voloshin2019empirical}. The doubly robust
estimator is the most competitive estimator in the family of
full-trajectory importance weighting. It is similar
to~\pref{eq:rl_ips}, except that the direct model is used as a control
variate and the normalizing constant $n$ is replaced with the sum of
importance weights. \textsc{Magic}\xspace, as we have alluded to, is the only other
estimator selection procedure we are aware of for this setting. It
aggregates partial importance weighting estimators to optimize a
surrogate for the MSE. For \textsc{Slope}\xspace, we use twice the empirical
standard deviation as the confidence function, which is asymptotically
valid and easier to compute.

We do not consider other baselines for two reasons. First, DM, WDR,
and \textsc{Magic}\xspace span the broad estimator categories (importance weighted,
direct, hybrid) within which essentially all estimators
fall. Secondly, many other estimators have hyperparameters that must
be tuned, and we believe \textsc{Slope}\xspace will also be beneficial when used in
these contexts.






\paragraph{Experiment Setup.}
We have 106 experimental conditions determined by
environment, stochasticity of dynamics and reward,
reward sparsity, logging policy, target policy, and number of
trajectories $n$.
For each condition, we calculate the MSE for each method by averaging over 100 replicates.




\paragraph{Results.}
In the left panel of~\pref{fig:rl_fig}, as in~\pref{sec:cb_exp}, we
first visualize the aggregate results via the cumulative distribution
function (CDF) of the normalized MSE in each condition (normalizing
by the worst performing method in each condition). As a reminder, the
figure reads as follows: for each $x$ value, the corresponding $y$
value is the fraction of conditions where the estimator has normalized
MSE at most $x$. In this aggregation, we see that WDR has the worst
performance, largely due to intolerably high variance. \textsc{Magic}\xspace and DM
are competitive with each other with \textsc{Magic}\xspace having a slight
edge. \textsc{Slope}\xspace appears to have the best aggregate performance; for the
most part its CDF dominates the others.



In the central panel, we display an array of statistical comparisons
between pairs of methods. As before, entry $(i,j)$ of this array is
computed by counting the fraction of conditions where method $i$ beats
$j$ in a statistically significant manner (we use paired $t$-test on
the MSE with significance level $0.05$). The column-wise averages are
also displayed.

In this aggregation, we see clearly that \textsc{Slope}\xspace dominates the three
other methods. First, \textsc{Slope}\xspace has column average that is smaller than
the other methods. More importantly, \textsc{Slope}\xspace is favorable when
compared with each other method individually. For example, \textsc{Slope}\xspace is
(statistically) significantly worse than \textsc{Magic}\xspace on 16\% of the
conditions, but it is significantly better on 25\%. Thus, this
visualization clearly demonstrates that \textsc{Slope}\xspace is the best performing
method in aggregate across our experimental conditions.

Before turning to the final panel of~\pref{fig:rl_fig}, we
recall~\pref{fig:intro_exp}, where we display results for two specific
conditions. Here, we see that \textsc{Slope}\xspace outperforms or is statistically
indistinguishable from the best baseline, regardless of whether direct
modeling is better than importance weighting! We are not aware of any
selection method that enjoys this property.

\paragraph{Learning curves.}
The final panel of~\pref{fig:rl_fig} visualizes the performance of the
four methods as the sample size increases. Here we consider the Hybrid
domain from~\citet{thomas2016data}, which is designed specifically to
study the performance of partial importance weighting estimators. The
domain has horizon 22, with partial observability in the first two
steps, but full observability afterwards. Thus a (tabular) direct
model is biased since it is not expressive enough for the first two
time steps, but $\hat{V}_2(\pi_{\mathrm{T}})$ is a great estimator since the
direct model is near-perfect afterwards.

The right panel of~\pref{fig:rl_fig} displays the MSE for each method
as we vary the number of trajectories, $n$ (we perform 128
replicates and plot bars at $\pm 2$ standard errors). We see that when $n$ is small, DM
dominates, but its performance does not improve as $n$ increases due
to bias. Both WDR and \textsc{Magic}\xspace catch up as $n$ increases, but \textsc{Slope}\xspace is
consistently competitive or better across all values of $n$,
outperforming the baselines by a large margin. Indeed, this is because
\textsc{Slope}\xspace almost always chooses the optimal false horizon index of
$\eta=2$ (e.g., 90\% of the replicates when $n=500$).

\paragraph{Summary.}
Our experiments show that \textsc{Slope}\xspace is competitive, if not the best,
off-policy evaluation procedure among \textsc{Slope}\xspace, \textsc{Magic}\xspace, DM, and WDR. We
emphasize that \textsc{Slope}\xspace is not an estimator, but a selection procedure
that in principle can select hyperparameters for many estimator
families. Our experiments with the partial importance weighting family
are quite convincing,
and we believe this demonstrates the potential for \textsc{Slope}\xspace when used
with other estimator families for off-policy evaluation in
RL.\footnote{In settings where straightforward empirical variance
  estimates are not available, the bootstrap may provide an
  alternative approach for constructing the $\textsc{cnf}\xspace$
  function. Experimenting with such estimators is a natural future direction.}




\section{Discussion}
\label{sec:discussion}
In summary, this paper presents a new approach for estimator selection
in off-policy evaluation, called \textsc{Slope}\xspace. The approach applies quite
broadly; in particular, by appropriately spacing hyperparameters, many
common estimator families can be shown to satisfy the assumptions for
\textsc{Slope}\xspace. To demonstrate this, we provide concrete instantiations in
two important applications.  Our theory yields, to our knowledge, the
first oracle-inequalities for off-policy evaluation in RL. Our
experiments demonstrate strong empirical performance, suggesting that
\textsc{Slope}\xspace may be useful in many off-policy evaluation contexts.
 
\section*{Acknowledgements}
We thank Mathias Lecuyer for comments on a preliminary version of this
paper.

\clearpage

