# The Cram Method for Efficient Simultaneous Learning and Evaluation††thanks:
The proposed methodology will be implemented through an open-source Python
package, CRAM.

Zeyang Jia Kosuke Imai Michael Lingzhi Li PhD Student, Department of
Statistics, Harvard University, Cambridge, MA, 02138. Email:
<EMAIL_ADDRESS>Department of Government and Department of
Statistics, Harvard University, Cambridge, MA 02138\. Phone: 617–384–6778,
Email<EMAIL_ADDRESS>URL: https://imai.fas.harvard.eduAssistant Professor,
Technology and Operations Management, Harvard Business School, Boston, MA
02163. Email<EMAIL_ADDRESS>URL: https://www.michaellz.com

###### Abstract

We introduce the ‘cram’ method, a general and efficient approach to
simultaneous learning and evaluation using a generic machine learning (ML)
algorithm. In a single pass of batched data, the proposed method repeatedly
trains an ML algorithm and tests its empirical performance. Because it
utilizes the entire sample for both learning and evaluation, cramming is
significantly more data-efficient than sample-splitting. The cram method also
naturally accommodates online learning algorithms, making its implementation
computationally efficient. To demonstrate the power of the cram method, we
consider the standard policy learning setting where cramming is applied to the
same data to both develop an individualized treatment rule (ITR) and estimate
the average outcome that would result if the learned ITR were to be deployed.
We show that under a minimal set of assumptions, the resulting crammed
evaluation estimator is consistent and asymptotically normal. While our
asymptotic results require a relatively weak stabilization condition of ML
algorithm, we develop a simple, generic method that can be used with any
policy learning algorithm to satisfy this condition. Our extensive simulation
studies show that, when compared to sample-splitting, cramming reduces the
evaluation standard error by more than 40% while improving the performance of
learned policy. We also apply the cram method to a randomized clinical trial
to demonstrate its applicability to real-world problems. Finally, we briefly
discuss future extensions of the cram method to other learning and evaluation
settings.

Key Words: causal inference, policy learning, policy evaluation, machine
learning, sample splitting

##  1 Introduction

In recent years, with the growing availability of granular data, there has
been an explosion of interest in developing and utilizing data-driven
algorithms. Applications range from the use of classical machine learning (ML)
algorithms for prediction and decision-making to the deployment of generative
artificial intelligence (AI) tools for creation of high-quality text and image
outputs. Although much of scholarly efforts have focused upon the development
of such data-driven algorithms, it is essential to empirically evaluate the
performance of learned prediction and decision rules before implementing them
in the real world.

This paper presents the ‘cram’ method, a general and efficient approach that
enables analysts to simultaneously learn a prediction or decision rule and
assess its effectiveness. The name cram is inspired by an intensive learning
approach often used by cram schools, where students iterate a process of
learning new materials and taking practice tests to prepare for a final exam.
The proposed method uses the same idea by repeatedly training an ML algorithm
and testing its performance in a single pass of batched data. Because cramming
uses the entire sample, it leads to more data-efficient learning and
evaluation than traditional sample-splitting methods.

The sequential nature of cramming naturally accommodates an online learning
setting, as algorithms are trained by using an additional batch of data at
each step. This feature also enables the use of online algorithms in offline
settings, leading to a substantial gain in computational efficiency.
Importantly, the cram method evaluates the performance of a specific rule
learned during a training process while taking into account statistical
uncertainty due to both training and evaluation. This contrasts with cross-
validation and other resampling techniques that are used to evaluate the
average performance of an ML algorithm across training data sets rather than
that of a learned rule based on the single training data set at hand.

Figure 1: A schematic Illustration of the cram method. We begin a cramming
process by randomly dividing a dataset into $T$ batches, and defining a
baseline rule, Rule 0. The method then learns an updated rule, Rule 1, using
the first batch of data, Batch 1, and evaluates the difference in performance
between these two consecutive rules, $\Delta$(Rule 1, Rule 0), using the
remaining $T-1$ batches. Repeating this train-and-test process leads to the
final learned rule, Rule $T$, and the evaluation of performance improvement
$\Delta$(Rule $T$, Rule $T-1$). Finally, aggregating these performance
differences yields the evaluation of the final rule.

Figure 1 presents a schematic illustration of the cram method while we provide
its formal definition in Section 2. A cramming process begins by randomly
dividing a dataset into a total of $T$ batches, and defining a baseline rule,
which is denoted by Rule 0 in the figure. We first train an ML algorithm using
the first batch of data, yielding an updated rule Rule 1. We then evaluate the
performance difference between these two rules, i.e.,
$\Delta(\text{Rule~{}1},\text{Rule~{}0})$, using the remaining $T-1$ batches.
We repeat this train-and-test process at each iteration $t$; using the first
$t$ batches to generate Rule $t$, and evaluating the performance improvement
over Rule $t-1$, i.e., $\Delta(\text{Rule~{}$t$},\text{Rule~{}$t-1$})$, based
on the remaining $T-t$ batches. Repeating this process $T-1$ times yields the
final learned rule, Rule $T$. Finally, we assess the performance of Rule $T$
by simply summing all the performance improvements, i.e.,
$\sum_{t=1}^{T-1}\Delta(\text{Rule~{}$t$},\text{Rule~{}$t-1$})$, with the
exception of the last improvement
$\Delta(\text{Rule~{}$T$},\text{Rule~{}$T-1$})$, which has no available
samples for evaluation.

Cramming has clear advantages over sample-splitting. First, the cram method
utilizes the entire sample for learning while sample-splitting must set aside
a test set of sufficiently large size for evaluation, which cannot be used for
learning. Second, cramming method also uses the entire sample for evaluation.
In particular, a greater subset of data is used for performance evaluation at
early stages of learning when learned rules are likely to be substantially
changing. Cramming, therefore, is much more data-efficient than sample-
splitting. Finally, as mentioned earlier, the cram method can accommodate
online learning algorithms, which are available for many popular ML methods.
This means that in many cases, cramming does not lead to a substantial
increase in computational cost relative to relative to sample-splitting even
though it repeatedly trains ML algorithms.

We demonstrate the power of cramming by applying it to the standard offline
policy learning setting where researchers use an ML algorithm to learn an
individualized treatment rule (ITR) and evaluate its empirical performance by
estimating the average outcome that would result if the learned ITR were to be
deployed. In Section 3, we show that our crammed evaluation estimator is
$L_{1}$ consistent and asymptotically normal under a minimal set of
assumptions. While our asymptotic results require learned ITRs to stabilize at
a relatively slow rate as more batches of data are used, we also provide a
simple and general method, which can be used with any ML algorithm to ensure
that this stabilization condition is satisfied.

In Section 4, we conduct extensive simulations by utilizing a wide array of 77
different data generating processes taken from the 2016 Atlantic Causal
Inference Conference (ACIC) data challenge (Dorie et al.,, 2019). We find
that, in comparison to sample-splitting, cramming leads to the improved
performance of learned ITRs across these diverse settings. Importantly,
cramming reduces the evaluation standard error by more than 40% across all
data generating processes and a broad spectrum of policy learning algorithms —
regression, tree-based methods, and neural networks. The magnitude of this
precision improvement is similar to the one obtained by tripling the test size
under sample-splitting. Finally, we find that the bias of the cram method is
negligible and its confidence intervals have a good empirical coverage even
when the sample size is relatively small.

In Section 5, we demonstrate the applicability of the cram method using a
well-known randomized clinical trial described by Byar and Green, (1980). This
trial examines the effect of administering diethylstilbestrol, a type of
synthetic estrogen, to prolong total survival in late-stage prostate cancer
patients. We compare the learning and evaluation results from cramming with
those based on sample-splitting. We find that the cram method produces a
performance estimate similar to sample-splitting, but with a much smaller
estimated standard error.

In this paper, we focus on the application of cramming to _offline_ and _off-
policy_ learning and evaluation, where data acquisition is not affected by
changing learned policies. The cram method can also be applied to _online_ and
_on-policy_ learning and evaluation, where data are adaptively collected
according to learned policies. In Section 6, we briefly discuss this and other
potential extensions of the cram method.

#### Related literature.

The existing evaluation methods can largely be categorized into two groups:
sample-splitting and resampling methods (see e.g., Raschka,, 2018, for a
detailed review). Sample-splitting involves training an ML algorithm on a
randomly selected subset of dataset to learn a prediction or decision rule
while evaluating the performance of this learned rule on the remaining held-
out data. This strategy, while intuitive and easy to implement, does not
utilize data efficiently. The proposed cram method overcomes this limitation.

In contrast, resampling methods, which include bootstrap (e.g., Efron,, 1992;
Efron and Tibshirani,, 1997) and cross-validation (e.g., Stone,, 1974; Blum et
al.,, 1999), make more efficient use of data. These methods, however, estimate
the average algorithmic performance over multiple training data sets, thus
assessing the efficacy of an ML algorithm rather than that of a specific
learned rule (e.g., Zhang,, 1993; Austern and Zhou,, 2020; Bayle et al.,,
2020; Imai and Li, 2023a, ; Bates et al.,, 2023). In contrast, the cram method
is designed to yield a single learned rule and evaluate its empirical
performance using the same data set. Moreover, these resampling methods may
not be applicable to computationally intensive learning algorithms, such as
large-scale neural networks, because it requires repeated model fitting. The
cram method addresses this computational challenge by admitting online
learning algorithms.

There exists a growing body of work that estimates a fixed population-level
parameter based on sequentially collected data. This includes the use of
reinforcement learning to estimate model parameters (e.g., Hadad et al.,,
2021; Dimakopoulou et al.,, 2021; Zhan et al.,, 2021; Zhang et al.,, 2021;
Chen et al.,, 2021) and the analysis of online experimentation to ascertain
average treatment effects over time (e.g., Johari et al.,, 2015; Howard et
al.,, 2021; Ham et al.,, 2023). Our problem is fundamentally different from
the one studied in this literature. Using sequentially ordered data, the cram
method simultaneously learns a prediction or decision rule and evaluates the
performance of a learned rule itself rather than estimating a fixed parameter
of interest. Because the learned rule and hence its performance change as a
function of data in a cramming process, our theoretical results require
different technical tools than those used in this literature.

In this paper, we consider a specific application of the cram method, the use
of cramming for simultaneous policy learning and evaluation. In the relevant
literature, a number of scholars have proposed evaluation estimators that are
consistent for the value of a fixed policy (e.g., Dudík et al.,, 2011; Jiang
and Li,, 2016; Kallus,, 2018; Yadlowsky et al.,, 2021; Li and Imai,, 2023).
Most of these methods assume that a policy to be evaluated is given, and does
not allow for it to be learned using the same data. One exception is Imai and
Li, 2023a  who use cross-validation to simultaneously learn multiple ITRs and
evaluate their performance (see also Chernozhukov et al.,, 2019; Imai and Li,
2023b, , for a similar approach to the evaluation of estimated heterogeneous
effects). As discussed above, however, their method assesses the average
performance of learning algorithm over multiple training data sets rather than
that of one specific rule learned from the entire data.

##  2 Cramming for simultaneous policy learning and evaluation

In this section, we formally introduce the cram method in the specific context
of simultaneous policy learning and evaluation. We begin by describing the
goal of cramming and then provide a formal definition of the cram method.

###  2.1 Setup

Our goal is to efficiently learn a data-driven policy and evaluate the
performance of learned policy at the same time. Suppose we have a dataset of
$n$ independent and identically distributed samples, denoted by
$\mathcal{D}_{n}=\\{(\bm{X}_{i},D_{i},Y_{i})\\}_{i=1}^{n}$ where for each
observation $i$, $\bm{X}_{i}\in\mathcal{X}$ represent a vector of $p$ pre-
treatment covariates whose support is $\mathcal{X}\subset\mathbb{R}^{p}$, and
$D_{i}\in\\{0,1\\}$ is the observed binary treatment, and
$Y_{i}\in\mathcal{Y}$ is the observed outcome where
$\mathcal{Y}\subset\mathbb{R}$ is the support of the outcome variable. We use
$Y_{i}(d)\in\mathcal{Y}$ to denote a potential outcome under the treatment
condition $d\in\\{0,1\\}$ where the observed outcome is given by
$Y_{i}=Y_{i}(D_{i})$.

The above potential outcome notation implicitly assumes no interference
between units and consistency (Rubin,, 1990). In addition, we assume that the
treatment assignment is unconfounded and satisfies the overlap condition. We
formally state this strong ignorability assumption (Rosenbaum and Rubin,,
1983).

######  Assumption 1 (Strong ignorability of treatment assignment)

The treatment assignment mechanism satisfies the following conditions:

  1. 1.

(Unconfoundedness) The treatment assignment is conditionally independent of
potential outcomes given the observed pre-treatment covariates:

$\\{Y(0),Y(1)\\}\mbox{$\perp\\!\\!\\!\perp$}D\mid\bm{X}$

  2. 2.

(Overlap) The propensity score
$e(\bm{x}):=\mathbb{P}\left(D=1\mid\bm{X}=\bm{x}\right)$ is bounded away from
0 and 1. That is, there exists a constant $c>0$ such that

$c\leq e(\bm{x})\leq 1-c,$

holds for all $x\in\mathcal{X}$.

We define a policy or an individualized treatment rule (ITR) as a function
that maps an individual’s covariates $\bm{x}\in\mathcal{X}$ to the probability
of receiving the treatment: $\pi:\mathcal{X}\to[0,1]$. That is, under this
policy, we have,

$\pi(\bm{x})\ =\ \mathbb{P}\left(D=1\mid\bm{X}=\bm{x}\right).$

Thus, the cram method allows for both deterministic and stochastic treatment
policies.

In the standard policy learning settings, the most commonly used evaluation
metric is the value of policy $\pi$ defined as the expected outcome that would
be realized if the treatment is assigned according to the policy (e.g.,
Kitagawa and Tetenov,, 2018; Athey and Wager,, 2021):

$\displaystyle V(\pi)\ :=\ \mathbb{E}_{D\sim\pi}\left[Y(D)\right]\ =\
\mathbb{E}\left[Y(1)\pi(\bm{X})+Y(0)(1-\pi(\bm{X}))\right].$ (1)

For notational simplicity, we will instead consider the value difference
between a specific policy of interest $\pi$ and a baseline policy $\pi_{0}$,
which can be any fixed and known policy:

$\Delta(\pi;\pi_{0})\ :=\ V(\pi)-V(\pi_{0})\ =\
\mathbb{E}\left[(Y(1)-Y(0))(\pi(\bm{X})-\pi_{0}(\bm{X}))\right].$

We emphasize that we use this alternative evaluation metric solely for the
purpose of simplifying our exposition. In Appendix S1, we explain why it is
sufficient to consider this policy value difference even when the evaluation
metric of interest is the value of a learned policy defined in Equation (1).
We also note that in some cases, the policy value difference with respect to
some baseline policy (e.g., a status-quo policy) is of interest in itself
(e.g., Ben-Michael et al.,, 2021; Zhang et al.,, 2022; Kallus,, 2022; Jia et
al.,, 2023).

Given the above setup, we consider the problem of how to simultaneously learn
a policy and evaluate the performance of a final learned policy. Our goal is
two-fold. First, we wish to use the observed data to learn a desirable policy,
according to some criteria, that maps an individual’s covariates to treatment
probability. To ensure that the cram method is widely applicable, we remain
agnostic about a specific criteria and ML algorithm used to obtain a learned
policy. For example, we neither require the use of any specific ML algorithms,
nor assume that a learned policy is optimal according to some criteria (even
theoretically). We also accommodate any policy class, to which learned
policies belong, thereby allowing for a wide range of stochastic and
deterministic policies.

Our second goal is to estimate the value of a learned policy based on the same
observed data used for policy learning. Specifically, we wish to obtain a
valid point estimate and confidence interval for the value difference between
a final learned policy and a baseline policy (or the value of the learned
policy itself). The cram method achieves these two goals in a data-efficient
manner, utilizing the entire data to learn a policy and evaluate its
performance at the same time. We now formally introduce this proposed
methodology.

###  2.2 The cram method

Data: $\mathcal{D}_{n}=\\{\bm{X}_{i},D_{i},Y_{i}\\}_{i=1}^{n}$

Input: policy learning algorithm $\mathcal{A}$, baseline policy $\pi_{0}$,
number of batches $T$

Output: estimated value difference between the learned and baseline policies
$\widehat{\Delta}(\mathcal{A}(\mathcal{D});\pi_{0})$

1 Randomly partition the dataset $\mathcal{D}_{n}$ into $T$ batches
$\mathcal{B}_{1},\mathcal{B}_{2},...,\mathcal{B}_{T}$;

2 Set $\hat{\pi}_{0}=\pi_{0}$;

3 for  _$t=1$ to $T-1$_ do

4

  1. 1.

Learn a policy using the first $t$ batches
$\hat{\pi}_{t}:=\mathcal{A}(\bigcup_{j=1}^{t}\mathcal{B}_{j})$;

  2. 2.

Evaluate the policy value difference between $\hat{\pi}_{t}$ and
$\hat{\pi}_{t-1}$ using the remaining batches
$\bigcup_{j=t+1}^{T}\mathcal{B}_{j}$ and store the resulting estimate as
$\widehat{\Delta}(\hat{\pi}_{t};\hat{\pi}_{t-1})$;

Evaluate the value difference between the final learned policy
$\hat{\pi}_{T}:=\mathcal{A}(\mathcal{D}_{n})$ and the baseline policy
$\pi_{0}$ as:
$\displaystyle\widehat{\Delta}(\hat{\pi}_{T};\pi_{0}):=\sum_{t=1}^{T-1}\widehat{\Delta}(\hat{\pi}_{t};\hat{\pi}_{t-1}).$

Algorithm 1 Cramming for simultaneous policy learning and evaluation Figure 2:
A schematic illustration of cramming for simultaneous policy learning and
evaluation as defined in Algorithm 1. At the $t$-th iteration, we use the
first $t$ batches (blue boxes) to learn a policy $\hat{\pi}_{t}$ and use the
remaining $T-t$ batches (red boxes) to estimate the policy value difference
between $\hat{\pi}_{t}$ and $\hat{\pi}_{t-1}$, i.e.,
$\widehat{\Delta}(\hat{\pi}_{t},\hat{\pi}_{0})$. After repeating this train-
and-test process $T-1$ times, the estimated policy value differences from all
iterations are summed together to obtain an estimate of the value difference
between the final learned policy and the baseline policy, i.e.,
$\widehat{\Delta}(\hat{\pi}_{T};\pi_{0})$.

Algorithm 1 outlines a cramming process for simultaneous policy learning and
evaluation while Figure 2 provides its schematic illustration. Cramming begins
by randomly splitting the data into $T$ batches and defining a baseline policy
$\pi_{0}$. Although, for notational simplicity, we consider batches of equal
size, cramming works with unequally sized batches as well. The key idea of
cramming in this offline policy learning setting is to create a sequential
structure to the i.i.d. dataset so that one can repeat train-and-test steps.

Specifically, for each iteration $t=1,2,\dots,T-1$, we apply a policy learning
algorithm, $\mathcal{A}:\bm{\mathcal{D}}\to\Pi$ (a function that maps the
space of a training data set $\bm{\mathcal{D}}$ to any deterministic or
stochastic policy class $\Pi$), to the first $t$ batches to learn a policy
$\hat{\pi}_{t}:=\mathcal{A}(\bigcup_{j=1}^{t}\mathcal{B}_{j})$. We use the
“hat” notation to emphasize that $\hat{\pi}_{t}$ is a function of the observed
data and hence is a random variable. We then evaluate the performance of the
learned policy using the remaining $T-t$ batches and estimate the policy value
difference between the updated policy and the previously learned policy
$\widehat{\Delta}(\hat{\pi}_{t};\hat{\pi}_{t-1})$ where
$\hat{\pi}_{0}=\pi_{0}$.

After $T-1$ iterations, we estimate the policy value difference between the
final learned policy $\hat{\pi}_{T}:=\mathcal{A}(\mathcal{D}_{n})$ and the
baseline policy $\pi_{0}$ using the following decomposition:

$\displaystyle\Delta(\hat{\pi}_{T};\pi_{0})\ =\
\sum_{t=1}^{T}\Delta(\hat{\pi}_{t};\hat{\pi}_{t-1})\ \approx\
\sum_{t=1}^{T-1}\Delta(\hat{\pi}_{t};\hat{\pi}_{t-1}),$ (2)

where we omit the final policy difference, i.e.,
$\Delta(\hat{\pi}_{t};\hat{\pi}_{t-1})$ as there are no available samples to
estimate the final policy change. In the next section, we impose a relatively
weak stability condition on the learning algorithm so that this final
difference term is indeed theoretically negligible. In Section 3, we provide a
a simple and general algorithm that can be combined with any learning
algorithm to provably satisfy this weak stability condition in practice.
Finally, in Section 4, we demonstrate that many common learning algorithms
empirically satisfy the stability condition without modification.

In practical implementation, we recommend requiring the first and last batches
of the data, i.e., $\mathcal{B}_{1}$ and $\mathcal{B}_{T}$, which we refer to
as ‘burn-in’ and ‘burn-out’ sets, respectively, to be not too small ($\gtrsim
10$). The goal of the burn-in set is to properly train policy learning
algorithms without numerical issues. The burn-out set is used to ensure that
we have enough treated and control samples for stable evaluation.

We emphasize that sample-splitting is a special case of cramming with only two
batches and hence has no iterative train-and-test process. Intuitively,
cramming can significantly improve sample-splitting if a learning algorithm
$\mathcal{A}$ stabilizes earlier in the process. The reason is that the cram
method uses more data for evaluation at an earlier stage when learned policies
are changing substantially and the policy value difference is relatively
large. Cramming allocates less data to evaluation at a later stage when the
learning algorithm is more stable and the policy value difference is smaller.
This adaptive sample allocation leads to efficiency gain in policy evaluation.

Finally, although cramming requires learning of $T$ policies, its sequential
nature enables the use of efficient online learning algorithms so that
additional computational costs are minimized. For example, we can use popular
online algorithms such as (kernel) recursive least squares (Engel et al.,,
2004) and stochastic gradient descent (Amari,, 1993). These online algorithms
are widely used to train a variety of ML algorithms including neural networks
and gradient boosted trees. This represents a major advantage over resampling
methods such as bootstrap and cross-validation where it may be difficult to
apply such online learning algorithms.

##  3 Statistical inference after cramming

In this section, we show how to conduct statistical inference after cramming.
Specifically, we formally introduce the policy value difference estimator
$\widehat{\Delta}(\hat{\pi}_{T};\pi_{0})$ under cramming and derive its
asymptotic properties. We show that under a minimal set of regularity
conditions, the proposed estimator is $L_{1}$ consistent and asymptotically
normal so long as the policy learning algorithm $\mathcal{A}$ satisfies a
stabilization condition. While our stabilization condition is relatively weak,
it may be difficult to verify that any given learning algorithm satisfies this
condition. To address this practical challenge, we also propose a simple,
generic algorithm that can ensure any learning algorithm satisfies the
required stabilization condition.

###  3.1 A crammed policy evaluation estimator

We now introduce a crammed policy evaluation estimator where, for simplicity,
we assume the propensity score $e(\bm{x})$ is known. An extension to
observational studies, where the propensity score is unknown and estimated, is
also possible but is not considered in this paper.

The proposed estimator applies the inverse probability weighting (IPW)
estimator $\widehat{\Gamma}_{tj}$ to each batch $\mathcal{B}_{j}$, yielding a
batch-specific estimate of the policy value difference between two consecutive
policies, i.e., $\Delta(\hat{\pi}_{t},\hat{\pi}_{t-1})$. The formal definition
of this estimator is given here.

######  Definition 1 (The crammed IPW policy evaluation estimator)

The crammed policy evaluation estimator of $\Delta(\hat{\pi}_{T};\pi_{0})$ is
given by,

$\widehat{\Delta}(\hat{\pi}_{T};\pi_{0})\ :=\
\sum_{t=1}^{T-1}\widehat{\Delta}(\hat{\pi}_{t};\hat{\pi}_{t-1})$

where $\hat{\pi}_{0}=\pi_{0}$,

$\widehat{\Delta}(\hat{\pi}_{t};\hat{\pi}_{t-1})\ :=\
\frac{1}{T-t}\sum_{j=t+1}^{T}\widehat{\Gamma}_{tj},\
\text{and}\quad\widehat{\Gamma}_{tj}\ :=\
\frac{1}{B}\sum_{i\in\mathcal{B}_{j}}\left\\{\frac{Y_{i}D_{i}}{e(\bm{X}_{i})}-\frac{Y_{i}(1-D_{i})}{1-e(\bm{X}_{i})}\right\\}(\hat{\pi}_{t}(\bm{X}_{i})-\hat{\pi}_{t-1}(\bm{X}_{i})),$

for $t=1,2,\ldots,T-1$ and $j=t+1,t+2,\ldots,T$.

We emphasize that all of our results in this paper hold if this IPW estimator
is replaced with another unbiased estimator such as a doubly robust estimator.
The proposed crammed IPW estimator, however, is attractive due to its
simplicity and computational efficiency.

Definition 1 formalizes an intuitive interpretation of the cram method given
earlier. That is, at each iteration $t$ of a cramming process, we learn policy
$\hat{\pi}_{t}$ using the first $t$ batches. We then estimate the policy value
difference between $\hat{\pi}_{t}$ and $\hat{\pi}_{t-1}$ in each of the
remaining $T-t$ batches by averaging this IPW estimator,
$\widehat{\Gamma}_{tj}$, over the remaining batches
$\bigcup\mathcal{B}_{j=t+1}^{T}$. We add these estimated policy value
differences to arrive at the final crammed estimator,
$\widehat{\Delta}(\hat{\pi}_{T};\pi_{0})$.

Despite its interpretability, Definition 1 does not directly exploit the
sequential structure of cramming. This makes it difficult to analyze the
asymptotic behavior of the proposed crammed policy evaluation estimator. Thus,
we consider the following alternative but equivalent formulation of the
estimator:

$\widehat{\Delta}(\hat{\pi}_{T};\pi_{0})\ =\
\sum_{j=2}^{T}\widehat{\Gamma}_{j}(T)\quad\text{where}\quad\widehat{\Gamma}_{j}(T)\
:=\ \sum_{t=1}^{j-1}\frac{1}{T-t}\widehat{\Gamma}_{tj}.$

This expression show that, for each batch $j$, we estimate all the policy
value differences based on the policies learned up to the previous batch,
i.e.,
$\Delta(\hat{\pi}_{1};\pi_{0}),\Delta(\hat{\pi}_{2};\hat{\pi}_{1}),\ldots,\Delta(\hat{\pi}_{j-1};\hat{\pi}_{j-2})$,
and sum these estimates, i.e.,
$\widehat{\Gamma}_{1j},\widehat{\Gamma}_{2j},\ldots,\widehat{\Gamma}_{j-1,j}$,
up while giving greater weights to those obtained earlier in the cramming
process. Since the remaining batches are not used at each step, this
representation of the crammed policy evaluation estimator preserves the
sequential nature of cramming. We will use this alternative expression in
proving our theoretical results.

###  3.2 Assumptions on policy learning algorithm

To derive the asymptotic properties of the crammed policy evaluation estimator
introduced in Definition 1, we impose two assumptions on policy learning
algorithm. The first is the key assumption of the cram method that requires a
policy learning algorithm to stabilize at a certain rate as more data are used
for learning.

######  Assumption 2 (Stabilization condition)

Define the $L_{1}$ distance between two consecutive learned policies at
iteration $t$ of a cramming process as follows:

$Q_{t}\ :=\
\mathbb{E}_{\bm{X}}\left[|\hat{\pi}_{t}(\bm{X})-\hat{\pi}_{t-1}(\bm{X})|\right]=\int_{\bm{x}\in\mathcal{X}}|\hat{\pi}_{t}(\bm{x})-\hat{\pi}_{t-1}(\bm{x})|dF_{\bm{X}}(\bm{x})$

where $t=1,2,\ldots,T$, $\hat{\pi}_{0}=\pi_{0}$, and $F_{\bm{X}}$ denotes the
cumulative distribution function of the pre-treatment covariates $\bm{X}$. The
learning algorithm must satisfy the following stabilization rate condition;
$\exists\delta>0,R_{1}>0,K_{0}>0,$ such that for all $t\geq R_{1}$,

$t^{1+\delta}Q_{t}\leq K_{0}\ \text{holds almost surely}.$

We emphasize that $Q_{t}$ defined above is a random variable because the
learned policies, $\hat{\pi}_{t}$ and $\hat{\pi}_{t-1}$, depend on the data
and the expectation is taken only with respect to the distribution of $\bm{X}$
(i.e., a new sample of $\bm{X}$ rather than the sample used for learning and
evaluation).

This $t^{1+\delta}$ stabilization condition arises naturally from the fact
that for every iteration in the cram method, we are losing $B$ evaluation
samples, and thus the policy differences must decrease faster than linearly to
allow the estimator to converge asymptotically. In particular, if a learning
algorithm satisfies the stabilization condition given in Assumption 2, it
yields a learned policy sequence $\\{\hat{\pi}_{t}\\}_{t=1}^{\infty}$ that has
a limit in the $L_{1}$ metric almost surely. We call this a limit policy of
the learned policy sequence and denote it by $\hat{\pi}_{\infty}$. The next
proposition establishes the existence and uniqueness of limit policy.

######  Proposition 1 (Limit policy)

Under Assumption 2, for any learned policy sequence
$\\{\hat{\pi}_{t}\\}_{t=1}^{\infty}$, there exists a unique limit policy
$\hat{\pi}_{\infty}:\mathcal{X}\to[0,1]$ such that with probability 1 the
following equality holds,

$\lim_{t\to\infty}\mathbb{E}_{\bm{X}}[|\hat{\pi}_{\infty}(\bm{X})-\hat{\pi}_{t}(\bm{X})|]\
=\ 0.$

Proof of the proposition is given in Appendix S4. Proposition 1 shows that
Assumption 2 is the weakest possible in the sense that if $\delta=0$, the
learned policy sequence $\\{\hat{\pi}_{t}\\}_{t=1}^{\infty}$ may not have a
limit in the $L_{1}$ metric, making meaningful asymptotic analysis difficult.
We stress that $\hat{\pi}_{\infty}$ is almost surely defined for every
realization of learned policy sequence $\\{\hat{\pi}_{t}\\}_{t=1}^{\infty}$,
which _depends on the data_ and is not a population-level fixed quantity.
Furthermore, we do not assume that the learned policy sequence
$\\{\hat{\pi}_{t}\\}_{t=1}^{\infty}$ converges to an optimal oracle policy or
any policy that is constant across data sets.

Finally, we require that the limit policy differs from the baseline policy. In
other words, if a learning algorithm cannot learn anything, then cramming will
not be helpful.

######  Assumption 3 (Limit policy differs from the baseline policy)

The limit policy $\hat{\pi}_{\infty}$ of a learned policy sequence
$\\{\hat{\pi}_{t}\\}_{t=1}^{\infty}$ differs from the baseline policy
$\pi_{0}$ in the $L_{1}$ distance almost surely. That is, there exists
$M_{1}>0$ such that,

$\mathbb{E}_{\bm{X}}\left[|\pi_{0}(\bm{X})-\hat{\pi}_{\infty}(\bm{X})|\right]>M_{1}\
\ \text{almost surely}.$

This assumption is necessary to avoid the degenerate case where there is no
policy value difference to evaluate at the end of cramming process.

###  3.3 Guaranteed stable cramming with a generic policy learning algorithm

Given the trivial nature of Assumption 3, the only substantial restriction the
cram method imposes on learning algorithms is the stability condition given in
Assumption 2. Although many learning algorithms appear to satisfy this
condition in practice (see Section 4), in general it is difficult to
theoretically verify this stabilization condition for a given learning
algorithm.

Data: a sequence of batches from cramming,
$\mathcal{B}_{1},\mathcal{B}_{2},\ldots,\mathcal{B}_{t},\ldots$

Input: a policy learning algorithm $\mathcal{A}$, a baseline policy $\pi_{0}$,
constants $\delta>0$ and $C>0$

Result: a sequence of learned policies $\hat{\pi}_{1},\hat{\pi}_{2},\ldots$
satisfying the stabilization condition of Assumption 2.

1 Set $\hat{\pi}_{0}=\pi_{0}$;

2 for  _$t\geq 1$_ do

3 Obtain a candidate policy $\tilde{\pi}_{t}\ :=\
\mathcal{A}(\bigcup_{j=1}^{t}\mathcal{B}_{j})$ by applying the algorithm
$\mathcal{A}$ to the first $t$ batches

4 Compute the acceptance probability $p_{t}:=\min\\{Ct^{-1-\delta},1\\}$

5 Generate a learned policy as
$\hat{\pi}_{t}(x):=p_{t}\tilde{\pi}_{t}(x)+(1-p_{t})\hat{\pi}_{t-1}(x)$

Algorithm 2 Stable cramming with a generic policy learning algorithm

We develop a simple, generic algorithm (Algorithm 2) that converts any policy
learning algorithm to the one which satisfies Assumption 2. The key idea is to
control the stability of learned policies over iterations in a cramming
process by using an accept-and-reject algorithm where the acceptance
probability matches the required stabilization rate. In particular, so long as
one choose a sufficiently large value of $C$ and a sufficiently small value of
$\delta$, the algorithm will be able to learn well at an early stage of
cramming process.

Algorithm 2 is conservative in a sense that it can make any policy learning
algorithm satisfy Assumption 2. This means that there are likely to exist a
better algorithm applicable to specific cases. In practice, most commonly used
policy learning algorithms are already quite stable. Therefore, for
practitioners, we recommend choosing a $C$ and $\delta$ such that the policy
learning algorithm can learn, without modification, for at least $80\%$ of the
data.

The following proposition formally establishes that this approach yields a
sequence of learned policies that satisfy the stabilization condition.

######  Proposition 2 (Stabilization guarantee)

The output sequence of learned policies $\\{\hat{\pi}_{t}\\}_{t=1}^{\infty}$
from Algorithm 2 satisfies the stabilization condition of Assumption 2.

This result immediately follows from the definition of Algorithm 2:

$\displaystyle\mathbb{E}_{\bm{X}}\left[|\hat{\pi}_{t}(\bm{X})-\hat{\pi}_{t-1}(\bm{X})|\right]$
$\displaystyle\ =\
p_{t}\mathbb{E}_{\bm{X}}\left[|\tilde{\pi}_{t}(\bm{X})-\hat{\pi}_{t-1}(\bm{X})|\right]\
\leq\ p_{t}\ \leq\ Ct^{-1-\delta}.$

###  3.4 Consistency and asymptotic normality

We now establish the $L_{1}$ consistency and asymptotic normality of the
crammed policy evaluation estimator introduced in Definition 1. We require the
following two mild regularity conditions about potential outcomes.

######  Assumption 4 (Bounded conditional expectation and conditional
variance)

Both the conditional expectation and conditional variance of the potential
outcome, i.e., $\mu_{d}(\bm{x}):=\mathbb{E}[Y(d)\mid\bm{X}=\bm{x}]$ and
$\sigma_{d}^{2}(\bm{x}):=\mathbb{V}(Y(d)\mid\bm{X}=\bm{x})$ for $d=0,1$,
respectively, are uniformly bounded on the covariate space $\mathcal{X}$:

$\sup_{\bm{x}\in\mathcal{X}}\mu_{d}(\bm{x})<\infty,\quad
0<\inf_{\bm{x}\in\mathcal{X}}\sigma_{d}^{2}(\bm{x})\leq\sup_{\bm{x}\in\mathcal{X}}\sigma_{d}^{2}(\bm{x})<\infty,\quad\text{for}\
d=0,1.$

######  Assumption 5 (Moment condition)

The potential outcomes have finite fourth moments:

$\exists K_{4}>0,s.t.\ \ \mathbb{E}[Y(d)^{4}]\leq K_{4},\quad\text{for}\
d=0,1.$

We emphasize that these regularity conditions are quite weak and are expected
to be satisfied in most settings.

We now present the theorems that establish our asymptotic results as the
sample size $n$ goes to infinity or equivalently the number of batches $T$
tends to infinity with a fixed batch size of $B$. First, we show that the
proposed crammed estimator is consistent.

######  Theorem 1 ($L_{1}$ consistency)

Suppose that a sequence of learned policies $\\{\hat{\pi}_{t}\\}_{t=1}^{T}$
satisfies Assumption 2. Then, under Assumptions 1, 4, and 5, we have,

$\mathbb{E}\left[\bigr{|}\widehat{\Delta}(\hat{\pi}_{T};\pi_{0})-\Delta(\hat{\pi}_{T};\pi_{0})\bigr{|}\right]\rightarrow
0\ \ \text{as}\ \ T\rightarrow\infty.$

Proof is given in Appendix S2. The theorem implies that the bias of our
estimator goes to 0 as $T\to\infty$, despite the fact that we are not able to
estimate the final policy value difference
$\hat{\Delta}(\hat{\pi}_{T},\hat{\pi}_{T-1})$. This is because Assumption 2
guarantees that $\hat{\Delta}(\hat{\pi}_{T},\hat{\pi}_{T-1})$ is negligible as
$T\to\infty$.

The next theorem further establishes the asymptotic normality.

######  Theorem 2 (Asymptotic normality)

Suppose that a sequence of learned policies $\\{\hat{\pi}_{t}\\}_{t=1}^{T}$
satisfies Assumptions 2 and 3 . Then, under Assumptions 1, 4, and 5, we have,

$\sqrt{T}\cdot\frac{\widehat{\Delta}(\hat{\pi}_{T};\pi_{0})-\Delta(\hat{\pi}_{T};\pi_{0})}{v_{T}}\stackrel{{\scriptstyle
d}}{{\longrightarrow}}N(0,1).$

The asymptotic variance is given by,

$v_{T}^{2}\ :=\
T\sum_{j=2}^{T}\mathbb{V}(\widehat{\Gamma}_{j}(T)\mid\mathcal{H}_{j-1}),$

where $\mathcal{H}_{j}:=\bigcup_{t=1}^{j}\mathcal{B}_{t}$.

Proof is given in Appendix S3. Unlike the standard central limit theorem, both
the estimand $\Delta(\hat{\pi}_{T};\pi_{0})$ and the asymptotic variance
$v_{T}$ are random variables that are functions of the observed data. Since a
primary goal of cramming is to evaluate a specific learned policy obtained
from the data, the difficulty of evaluation, which is represented by the
asymptotic variance, also depends on this learned policy. Proving Theorem 2,
therefore, requires a careful control of all data generating sequences.

We further note that we are able to prove asymptotic normality with only an
$L_{1}$ assumption on the stability of policy learning algorithm. This is
surprising because the asymptotic variance $v_{T}^{2}$ naturally contains
$L_{2}$ expressions of the policy differences. This is mainly due to the
cancellation of the policy differences that occur in cramming as we sum over
the $T-1$ iterations to arrive at the final crammed evaluation estimator.

Next, we introduce the crammed variance estimator, which is consistent for the
asymptotic variance $v_{T}^{2}$ of the crammed policy evaluation estimator. We
begin by defining the following IPW estimator for the $j$th batch:

$\displaystyle\hat{g}_{Tj}(\bm{Z})\ :=\
\left\\{\frac{YD}{e(\bm{X})}-\frac{Y(1-D)}{1-e(\bm{X})}\right\\}\sum_{t=1}^{j-1}\frac{\hat{\pi}_{t}(\bm{X})-\hat{\pi}_{t-1}(\bm{X})}{T-t},$

where $\bm{Z}=\\{\bm{X},D,Y\\}$. Using this estimator, we can construct the
crammed variance estimator.

######  Definition 2 (The crammed variance estimator)

The crammed variance estimator is defined as:

$\hat{v}^{2}_{T}\ :=\
\frac{T}{B}\sum_{j=2}^{T}\widehat{\mathbb{V}}(\hat{g}_{Tj}),$

where $B$ is the batch size and

$\widehat{\mathbb{V}}(\hat{g}_{Tj})\ :=\
\frac{1}{B(T-j+1)-1}\sum_{k=j}^{T}\sum_{i\in\mathcal{B}_{k}}\left(\hat{g}_{Tj}(\bm{Z}_{i})-\bar{g}_{Tj}\right)^{2},\quad\bar{g}_{Tj}\
:=\
\frac{1}{B(T-j+1)}\sum_{k=j}^{T}\sum_{i\in\mathcal{B}_{k}}\hat{g}_{Tj}(\bm{Z}_{i}).$

If $B=1$ and $j=T$, we define $\widehat{\mathbb{V}}(\hat{g}_{TT})=0$.

Note that if the batch size is one, then we cannot compute the variance for
the evaluation of the final policy value difference. In that case, we set the
variance to zero.

Finally, the next theorem shows that this crammed variance estimator is
consistent.

######  Theorem 3 (Consistency of the crammed variance estimator.)

Suppose that the conditions of Theorem 2 hold. Then, as $T\rightarrow\infty$,
we have:

$|\hat{v}_{T}^{2}-v_{T}^{2}|\stackrel{{\scriptstyle p}}{{\longrightarrow}}0.$

Proof is given in Appendix S5. Theorem 3 permits the construction of an
asymptotically valid confidence interval. This result is stated as the
following corollary.

######  Corollary 1 (Asymptotic confidence intervals)

Suppose that the conditions of Theorem 2 hold. Then, as $T\rightarrow\infty$,
we have:

$\sqrt{T}\cdot\frac{\widehat{\Delta}(\hat{\pi}_{T};\pi_{0})-\Delta(\hat{\pi}_{T};\pi_{0})}{\hat{v}_{T}}\
\stackrel{{\scriptstyle d}}{{\longrightarrow}}\ \mathcal{N}\left(0,1\right).$

Proof is given in Appendix S6.

##  4 Simulation studies

In this section, we illustrate the power of cramming through an extensive set
of simulations. We find that across a total of 77 settings, the cram method
outperforms sample-splitting for both policy learning and evaluation.

###  4.1 Setup

We utilize the ACIC 2016 dataset (Dorie et al.,, 2019) that consists of 77
different data generating processes (DGPs) for the conditional average
treatment effect (CATE) estimation. These DGPs include a wide range of
simulation scenarios in terms of functional form and signal-noise ratio. In
all the setups, there are 58 numerical and categorical covariates, one binary
treatment, and one continuous outcome (Dorie et al.,, 2019).

Under each simulation setup, we synthetically create randomized experiments by
randomly assigning each observation to the treatment condition with
probability $1/2$. We then compute the potential outcomes based on a known
data generating process and generate the observed outcome according to the
realized treatment variable. Appendix S8.1 provides additional details of the
simulation setups.

We consider several policy learning algorithms, which first estimate the CATE
and assign the treatment if the estimated CATE is positive. The following
policy learning algorithms differ in the ways in which they estimate the CATE.

  * •

S-learner (Lipkovich et al.,, 2011; Qian and Murphy,, 2011) estimates the CATE
by modeling the conditional expectation of the outcome given the treatment,
covariates, and their interactions.

  * •

M-learner (Tian et al.,, 2014; Athey and Imbens,, 2016; Powers et al.,, 2018)
estimates the CATE by directly modeling the following transformed outcome
whose conditional expectation equals the CATE:
$Y^{*}:=YD/e(\bm{X})-Y(1-D)/(1-e(\bm{X}))$.

  * •

Causal Forest (Wager and Athey,, 2018; Athey and Wager,, 2019) uses a random-
forest type algorithm to estimate the CATE.

For S-learner and M-learner, we employ Linear Regression (LR) with a ridge
penalty and Feedforward Neural Networks (FNN). This yields a total of five
policy learning algorithms. Appendix S8.1 provides the implementation details
of these algorithms.

For cramming, we use the policy evaluation estimator given in Definition 1 and
the asymptotic confidence interval presented in Corollary 1. For sample-
splitting, we consider two scenarios. The first scenario uses 80% of the data
to learn a policy and the remaining 20% to evaluate the learned policy. These
results are shown in Section 4.2 below. The second scenario uses 60% of the
data to learn a policy and the remaining 40% to evaluate the learned policy.
The results of this 60-40% case are presented in Appendix S8.3.

We assess the performance of cramming and sample-splitting in terms of both
policy learning and evaluation. When evaluating learned policies, we directly
compare the value of a learned policy. When assessing the performance of
policy evaluation, we estimate the policy value difference
$\Delta(\hat{\pi}_{T};\pi_{0})$ and compute the bias, standard error, and
empirical coverage of confidence intervals.

Finally, under each simulation setting, we generate a dataset of sample size
varying from 300 to 1500. We fix the batch-size of cramming to 5% of the
sample size, resulting in 20 batches. We repeat the data generation 3,000
times to summarize the average value of the learned policy, and the bias,
standard error, and empirical coverage of the confidence intervals.

###  4.2 Results

We first summarize the results of all the 77 simulation settings based on the
S-learner with a ridge regression and sample size of 1,000, and then present
the specific results of particular settings using all five learning
algorithms.

(a) Percentage improvement in the policy value

(b) Percent improvement in standard error

(c) Standardized bias

(d) Coverage of 95% confidence intervals

Figure 3: Summary Results for Evaluation on 77 DGPs, where the CATE is
estimated with an S-learner using ridge regression.

Figures 3(a) and 3(b) demonstrate that when compared to the 80–20 sample-
splitting, cramming improves policy learning by increasing the value of
learned policies. The cram method also yields more accurate policy evaluation
by lowering the standard error of estimated policy values. Like sample-
splitting, the bias of cramming is small and the empirical coverage of
confidence intervals is accurate (see Figures 3(c) and 3(d)).

In these cases, cramming does have a small negative bias (see Figure 3(c)). As
briefly mentioned in Section 2.2, this is because there is no samples to be
used for evaluating the value difference between $\hat{\pi}_{T}$ and
$\hat{\pi}_{T-1}$. In many of these simulation settings with the moderate
sample size of 1000, the learned policy is still changing slightly at the
final step. Appendix S8.2 shows that this bias is eliminated once we use
$\hat{\pi}_{T-1}$ (rather than $\hat{\pi}_{T}$) as the final learned policy.
Then, we can use the final batch to evaluate the policy value difference
between $\hat{\pi}_{T-1}$ and $\hat{\pi}_{T-2}$.

To further understand the performance difference between CRAM and sample-
splitting, we focus on one DGP (DGP#4 of the ACIC 2016 dataset) as an example.
Specifically, this DGP utilizes a polynomial CATE function with strong
treatment effect heterogeneity. We compare the performance of the cram method
with that of the sample-splitting method under different sample sizes.

(a) Percentage improvement in policy value

(b) Percent improvement in standard error

Figure 4: Percent improvement of cramming over sample-splitting in terms of
policy value and standard error under DGP#4 across varying sample sizes. The
batch size is set to 5% of the sample size, which ranges from $300$ to $1500$
with an increment of $100$. The plots show the percent improvement of cramming
over sample-splitting in terms of policy value (left) and standard error
(right). “LR” stands for linear regression with a ridge penalty while “NN”
represents neural networks.

Figure 4 demonstrates the performance improvement of cramming relative to
80–20% sample-splitting. Appendix S8.3 presents the results compared to 60–40%
sample-splitting. We find that cramming is able to consistently achieve a
higher policy value and yield substantially smaller standard error than
sample-splitting, across sample sizes and different policy learning methods.
When compared to linear regression (LR), the relative advantage of cramming
over sample-splitting is reduced for neural networks (NN) and Causal Forest.
This is because it is easier to learn with more expressive ML models. While
not shown here, we find that the bias and coverage of confidence intervals are
comparable between cramming and sample-splitting across methods and sample
sizes. Finally, these findings are not sensitive to the choice of batch size.

##  5 Empirical application

We now apply the cram method to an empirical example to illustrate the use of
cramming in a real-world application setting.

###  5.1 Setup

We analyze the data from a randomized clinical trial that examines the
treatment effect of diethylstibestrol (a type of estrogen) on the survival of
cancer patients (Byar and Green,, 1980). The original dataset contains 502
patients who have a stage 3 or 4 prostate cancer. These patients are
randomized into four different treatment conditions: placebo and three
estrogen dose levels (0.2 mg, 1 mg, and 5 mg). For each patient, the trial
recorded their baseline health characteristics, common laboratory
measurements, prior disease history, and detailed information about the
current prostate cancer. The primary outcome $Y$ is the number of months of
survival at the end of follow-up, which may have occurred at either death or
the trial completion.

In our analysis, given a limited sample size of this study, we will combine
the three treatment groups together and compare them with the placebo group.
Therefore, the binary treatment variable $D\in\\{0,1\\}$ indicates whether or
not a patient receives any amount of estrogen (375 patients) or a placebo (127
patients). The average treatment effect is estimated to be $1.1$ months, but
this estimate was not statistically significant. That is, on average, the
estrogen treatment may not improve the survival outcome.

The goal of our analysis is, therefore, to learn a policy that identifies a
subgroup of patients who significantly benefit from the treatment despite the
statistically insignificant average treatment effect. We utilize a total of 13
pre-treatment covariates $\bm{X}$, including age, weight, blood pressure,
tumor size and stage, ECG diagnosis, and blood measurements.

We apply the cram method as well as sample-splitting. For cramming, we use a
batch size equal to 5% of the sample size. For sample-splitting, we use $80\%$
of the sample for policy learning, and the remaining $20\%$ for policy
evaluation.

To estimate CATE, we fit a ridge regression using the 13 pre-treatment
covariates and their interactions with the binary treatment. A learned policy
is obtained by giving the treatment to those whose CATE is estimated to be
positive. For policy evaluation, we use the standard IPW estimator introduced
in this paper, and compare the value of the learned policy with the baseline
policy of always giving the placebo.

###  5.2 Results

| cramming | sample-splitting
---|---|---
Estimated proportion treated | 57.76% | 56.94%
Estimated value | 7.77 | 3.90
Estimated standard error | 4.42 | 6.65
90% confidence interval | [0.50, 15.04] | [$-$7.03, 14.84]
Table 1: Policy evaluation under cramming and sample-splitting based on the
estrogen randomized controlled trial data. The estimated policy value under
cramming is greater than that under sample-splitting. In addition, cramming
yields a much smaller standard error than sample-splitting.

Table 1 presents the policy evaluation results for cramming and sample-
splitting. Although they treat a similar proportion of patients, the estimated
value is greater for the crammed policy. Consistent with our simulation
results, the cram method also has a smaller estimated standard error and
therefore a shorter confidence interval. With the 90% confidence level, the
crammed policy has a significant positive policy value while the sample-
splitting policy does not.

(a) Continuous covariates

(b) Binary covariates

Figure 5: Covariate distributions of individuals for whom the learned policies
under cramming and sample-splitting disagree. The left plot shows the
distributions of standardized continuous covariates while the right plot
represents those of binary covariates. The blue boxplots / bars indicate the
covariate distributs for those who would receive the treatment under the
crammed policy but not under the sample-split policy. The red boxplots / bars
represent the opposite disagreement cases.

Figure 5 shows the difference in the covariate distribution of patients for
whom the crammed and sample-split policies give the opposite treatment. The
blue boxplots and bars represent the covariate distributions for those whom
the crammed policy gives the treatment but the sample-split policy gives the
placebo. The red boxes and bars represent the opposite disagreement cases
where the sample-split policy gives the treatment but the crammed policy does
not.

We use boxplots to show the distributions of eight continuous pre-treatment
covariates after standardization (Figure 5(a)): Systolic blood pressure, age,
weight, diastolic blood pressure, Serum Hemoglobin, size of the primary tumor,
index of stage and history grade, and Serum Prostatic Acid Phosphatase. For
the five binary variables (a patient has stage 4 cancer, has cardiovascular
disease history, has bone metastases, is in bed, and has normal
electrocardiogram), we use the barplot to show their distributions (Figure
5(b)).

Compared to the sample-split policy, the crammed policy tends to give more
treatments to individuals who have the stage four cancer and a normal
electrocardiogram and give more placebos to those with a cardiovascular
disease history and relatively high diastolic blood pressure. Taken together,
the significant treatment effect under the crammed policy suggests that
ethylstibestrol might be more effective for patients with severe conditions.

##  6 Future extensions

The use of algorithmic decisions and recommendations is rapidly becoming
ubiquitous in today’s society. Safe deployment of such algorithms, however,
requires rigorous statistical evaluation of their empirical performance by
properly incorporating statistical uncertainty that arises from both learning
and evaluation. In this paper, we introduced the cram method, a general and
efficient approach to simultaneous learning and evaluation. The proposed
methodology enables analysts to use the same data for learning data-driven
prediction or decision rules and for evaluating the performance of learned
rules. We illustrated the potential power of cramming by applying it to the
standard offline policy learning and evaluation settings.

Given that the cram method provides a general framework for simultaneous
learning and evaluation, a number of future extensions are possible. Although
we have studied off-policy learning and evaluation in this paper, the
sequential nature of cramming is well suited for online and on-policy learning
and evaluation of bandit and other related algorithms. Furthermore, it is of
interest to extend cramming to active learning where data-efficient algorithms
play an important role. Finally, we also plan to investigate the application
of cramming to general prediction and regression problems.

## References

  * Amari, (1993) Amari, S.-i. (1993).  Backpropagation and stochastic gradient descent method.  Neurocomputing, 5(4-5):185–196.
  * Athey and Imbens, (2016) Athey, S. and Imbens, G. (2016).  Recursive partitioning for heterogeneous causal effects.  Proceedings of the National Academy of Sciences, 113(27):7353–7360.
  * Athey and Wager, (2019) Athey, S. and Wager, S. (2019).  Estimating treatment effects with causal forests: An application.  Observational studies, 5(2):37–51.
  * Athey and Wager, (2021) Athey, S. and Wager, S. (2021).  Policy learning with observational data.  Econometrica, 89(1):133–161.
  * Austern and Zhou, (2020) Austern, M. and Zhou, W. (2020).  Asymptotics of cross-validation.  arXiv preprint arXiv:2001.11111.
  * Bates et al., (2023) Bates, S., Hastie, T., and Tibshirani, R. (2023).  Cross-validation: What does it estimate and how well does it do it?  Journal of the American Statistical Association.
  * Bayle et al., (2020) Bayle, P., Bayle, A., Janson, L., and Mackey, L. (2020).  Cross-validation confidence intervals for test error.  In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H., editors, Advances in Neural Information Processing Systems, volume 33, pages 16339–16350. Curran Associates, Inc.
  * Ben-Michael et al., (2021) Ben-Michael, E., Greiner, D. J., Imai, K., and Jiang, Z. (2021).  Safe policy learning through extrapolation: Application to pre-trial risk assessment.  arXiv preprint arXiv:2109.11679.
  * Blum et al., (1999) Blum, A., Kalai, A., and Langford, J. (1999).  Beating the hold-out: bounds for k-fold and progressive cross-validation.  In Proceedings of the Twelfth Annual Conference on Computational Learning Theory, COLT ’99, page 203–208, New York, NY, USA. Association for Computing Machinery.
  * Byar and Green, (1980) Byar, D. P. and Green, S. B. (1980).  The choice of treatment for cancer patients based on covariate information.  Bulletin du cancer, 67(4):477–490.
  * Chen et al., (2021) Chen, H., Lu, W., and Song, R. (2021).  Statistical inference for online decision making via stochastic gradient descent.  Journal of the American Statistical Association, 116(534):708–719.
  * Chernozhukov et al., (2019) Chernozhukov, V., Demirer, M., Duflo, E., and Fernandez-Val, I. (2019).  Generic machine learning inference on heterogeneous treatment effects in randomized experiments.  Technical report, arXiv:1712.04802.
  * Dimakopoulou et al., (2021) Dimakopoulou, M., Ren, Z., and Zhou, Z. (2021).  Online multi-armed bandits with adaptive inference.  Advances in Neural Information Processing Systems, 34:1939–1951.
  * Dorie et al., (2019) Dorie, V., Hill, J., Shalit, U., Scott, M., and Cervone, D. (2019).  Automated versus do-it-yourself methods for causal inference: Lessons learned from a data analysis competition.  Statistical Science, 34(1):43–68.
  * Dudík et al., (2011) Dudík, M., Langford, J., and Li, L. (2011).  Doubly robust policy evaluation and learning.  arXiv preprint arXiv:1103.4601.
  * Efron, (1992) Efron, B. (1992).  Bootstrap methods: another look at the jackknife.  In Breakthroughs in statistics: Methodology and distribution, pages 569–593. Springer.
  * Efron and Tibshirani, (1997) Efron, B. and Tibshirani, R. (1997).  Improvements on cross-validation: the 632+ bootstrap method.  Journal of the American Statistical Association, 92(438):548–560.
  * Engel et al., (2004) Engel, Y., Mannor, S., and Meir, R. (2004).  The kernel recursive least-squares algorithm.  IEEE Transactions on signal processing, 52(8):2275–2285.
  * Hadad et al., (2021) Hadad, V., Hirshberg, D. A., Zhan, R., Wager, S., and Athey, S. (2021).  Confidence intervals for policy evaluation in adaptive experiments.  Proceedings of the national academy of sciences, 118(15):e2014602118.
  * Ham et al., (2023) Ham, D. W., Lindon, M., Tingley, M., and Bojinov, I. (2023).  Design-based confidence sequences: A general approach to risk mitigation in online experimentation.  Harvard Business School Technology & Operations Mgt. Unit Working Paper, (23-070).
  * Howard et al., (2021) Howard, S. R., Ramdas, A., McAuliffe, J., and Sekhon, J. (2021).  Time-uniform, nonparametric, nonasymptotic confidence sequences.  Annals of Statistics, 49(2):1050–1080.
  * (22) Imai, K. and Li, M. L. (2023a).  Experimental evaluation of individualized treatment rules.  Journal of the American Statistical Association, 118(541):242–256.
  * (23) Imai, K. and Li, M. L. (2023b).  Statistical inference for heterogeneous treatment effects discovered by generic machine learning in randomized experiments.
  * Jia et al., (2023) Jia, Z., Ben-Michael, E., and Imai, K. (2023).  Bayesian safe policy learning with chance constrained optimization: Application to military security assessment during the vietnam war.  arXiv preprint arXiv:2307.08840.
  * Jiang and Li, (2016) Jiang, N. and Li, L. (2016).  Doubly robust off-policy value evaluation for reinforcement learning.  In International Conference on Machine Learning, pages 652–661. PMLR.
  * Johari et al., (2015) Johari, R., Pekelis, L., and Walsh, D. J. (2015).  Always valid inference: Bringing sequential analysis to a/b testing.  arXiv preprint arXiv:1512.04922.
  * Kallus, (2018) Kallus, N. (2018).  Balanced policy evaluation and learning.  Advances in neural information processing systems, 31.
  * Kallus, (2022) Kallus, N. (2022).  What’s the harm? sharp bounds on the fraction negatively affected by treatment.  arXiv preprint arXiv:2205.10327.
  * Kitagawa and Tetenov, (2018) Kitagawa, T. and Tetenov, A. (2018).  Who should be treated? empirical welfare maximization methods for treatment choice.  Econometrica, 86(2):591–616.
  * Li and Imai, (2023) Li, M. L. and Imai, K. (2023).  Statistical performance guarantee for subgroup identification with generic machine learning.
  * Lipkovich et al., (2011) Lipkovich, I., Dmitrienko, A., Denne, J., and Enas, G. (2011).  Subgroup identification based on differential effect search—a recursive partitioning method for establishing response to treatment in patient subpopulations.  Statistics in medicine, 30(21):2601–2621.
  * Powers et al., (2018) Powers, S., Qian, J., Jung, K., Schuler, A., Shah, N. H., Hastie, T., and Tibshirani, R. (2018).  Some methods for heterogeneous treatment effect estimation in high dimensions.  Statistics in medicine, 37(11):1767–1787.
  * Qian and Murphy, (2011) Qian, M. and Murphy, S. A. (2011).  Performance guarantees for individualized treatment rules.  Annals of statistics, 39(2):1180.
  * Raschka, (2018) Raschka, S. (2018).  Model evaluation, model selection, and algorithm selection in machine learning.  arXiv preprint arXiv:1811.12808.
  * Rosenbaum and Rubin, (1983) Rosenbaum, P. R. and Rubin, D. B. (1983).  The central role of the propensity score in observational studies for causal effects.  Biometrika, 70(1):41–55.
  * Rubin, (1990) Rubin, D. B. (1990).  Comments on “On the application of probability theory to agricultural experiments. Essay on principles. Section 9” by J. Splawa-Neyman translated from the Polish and edited by D. M. Dabrowska and T. P. Speed.  Statistical Science, 5:472–480.
  * Stone, (1974) Stone, M. (1974).  Cross-validatory choice and assessment of statistical predictions.  Journal of the Royal Statistical Society. Series B (Methodological), 36(2):111–147.
  * Tian et al., (2014) Tian, L., Alizadeh, A. A., Gentles, A. J., and Tibshirani, R. (2014).  A simple method for estimating interactions between a treatment and a large number of covariates.  Journal of the American Statistical Association, 109(508):1517–1532.
  * Wager and Athey, (2018) Wager, S. and Athey, S. (2018).  Estimation and inference of heterogeneous treatment effects using random forests.  Journal of the American Statistical Association, 113(523):1228–1242.
  * Yadlowsky et al., (2021) Yadlowsky, S., Fleming, S., Shah, N., Brunskill, E., and Wager, S. (2021).  Evaluating treatment prioritization rules via rank-weighted average treatment effects.  arXiv preprint 2111.07966.
  * Zhan et al., (2021) Zhan, R., Hadad, V., Hirshberg, D. A., and Athey, S. (2021).  Off-policy evaluation via adaptive weighting with data from contextual bandits.  In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 2125–2135.
  * Zhang et al., (2021) Zhang, K., Janson, L., and Murphy, S. (2021).  Statistical inference with m-estimators on adaptively collected data.  Advances in neural information processing systems, 34:7460–7471.
  * Zhang, (1993) Zhang, P. (1993).  Model Selection Via Multifold Cross Validation.  The Annals of Statistics, 21(1):299 – 313.
  * Zhang et al., (2022) Zhang, Y., Ben-Michael, E., and Imai, K. (2022).  Safe policy learning under regression discontinuity designs.  arXiv 2208.13323.

Supplementary Appendix

##  Appendix S1 Estimating the policy value under cramming

In the main text, we focus on estimating the policy value difference between a
learned policy and a baseline policy,
$\Delta(\hat{\pi}_{T};\pi_{0}):=V(\hat{\pi}_{T})-V(\pi_{0})$. Here, we show
that it is also possible to estimate the value of a learned policy,
$V(\hat{\pi}_{T})$. To do this, for a given baseline policy, define the
following IPW estimator of its policy value using batch $j$:

$\hat{\eta}_{j}\ :=\
\frac{1}{B}\sum_{i\in\mathcal{B}_{j}}\left\\{\frac{Y_{i}D_{i}}{e(\mathbf{X}_{i})}\pi_{0}(\mathbf{X}_{i})+\frac{Y_{i}(1-D_{i})}{1-e(\mathbf{X}_{i})}(1-\pi_{0}(\mathbf{X}_{i}))\right\\}.$

Next, define the sample average of $\hat{\eta}_{j}$ over all batches:

$\hat{\eta}(T)=\frac{1}{T}\sum_{j=1}^{T}\hat{\eta}_{j}.$

It is easy to see that this converges to the value of the baseline policy
$V(\pi_{0})$ as $T\rightarrow\infty$, i.e.,

$\mathbb{E}\left[|\hat{\eta}(T)-V(\pi_{0})|\right]\rightarrow 0.$

Thus, we can adjust the crammed policy evaluation estimator introduced in
Definition 1 as follows:

$\widehat{\Psi}(T)\ :=\
\sum_{j=1}^{t}\widehat{\Psi}_{j}(T)\quad\text{where}\quad\widehat{\Psi}_{j}(T)\
:=\ \begin{cases}\widehat{\Gamma}_{j}(T)+\frac{1}{T}\hat{\eta}_{j},\ \ \ j\geq
2\\\ \frac{1}{T}\hat{\eta}_{j},\ \ \ j=1\end{cases}$

To establish the consistency of this crammed policy evaluation estimator, we
apply the triangle inequality and Theorem 1:

$\lim_{T\rightarrow\infty}\mathbb{E}\left[\bigr{|}\widehat{\Psi}(T)-V(\hat{\pi}_{T})\bigr{|}\right]\
\leq\
\lim_{T\rightarrow\infty}\left(\mathbb{E}\left[\left|\widehat{\Delta}(\hat{\pi}_{T};\pi_{0})-\Delta(\hat{\pi}_{T};\pi_{0})\right|\right]+\mathbb{E}\left[\left|\widehat{\Psi}(T)-V(\pi_{0})\right|\right]\right)\
=\ 0.$

To prove the asymptotic normality, notice that for $j\geq 2$, we have:

$\mathbb{V}(\widehat{\Psi}_{j}(T)\mid\mathcal{H}_{j-1})\ =\
\mathbb{V}(\widehat{\Gamma}_{j}(T)\mid\mathcal{H}_{j-1})+\frac{1}{T^{2}}\mathbb{V}(\hat{\eta}_{j}\mid\mathcal{H}_{j-1})+\frac{2}{T}\mathrm{Cov}(\widehat{\Gamma}_{j}(T),\hat{\eta}_{j}\mid\mathcal{H}_{j-1}).$

It is easy to see that the conditional variance of $\hat{\eta}_{j}$ does not
depend on the data:

$\displaystyle\mathbb{V}(\hat{\eta}_{j}\mid\mathcal{H}_{j-1})$ $\displaystyle\
=\
\frac{1}{B}\mathbb{E}\left[\frac{\mu_{1}(\bm{X})^{2}+\sigma_{1}^{2}(\bm{X})}{e(\bm{X})}\cdot\pi_{0}(\bm{X})^{2}+\frac{\mu_{0}(\bm{X})^{2}+\sigma_{0}^{2}(\bm{X})}{1-e(\bm{X})}\cdot(1-\pi_{0}(\bm{X}))^{2}\right]$
$\displaystyle\quad-\frac{1}{B}\mathbb{E}\left[\mu_{0}(\bm{X})+\pi_{0}(\bm{X})\tau(\bm{X})\right]^{2}$
$\displaystyle\ =\ \mathbb{V}(\hat{\eta}).$

For the covariance term, notice:

$\displaystyle\mathrm{Cov}(\widehat{\Gamma}_{j}(T),\hat{\eta}_{j}\mid\mathcal{H}_{j-1})$
$\displaystyle=$
$\displaystyle\frac{1}{B}\mathbb{E}_{\bm{X}}\left[\left(\sum_{t=1}^{j-1}\frac{\hat{\pi}_{t}(\bm{X})-\hat{\pi}_{t-1}(\bm{X})}{T-t}\right)\left\\{\frac{\mu_{1}(\bm{X})^{2}+\sigma_{1}^{2}(\bm{X})}{e(\bm{X})}\cdot\pi_{0}(\bm{X})+\frac{\mu_{0}(\bm{X})^{2}+\sigma_{0}^{2}(\bm{X})}{1-e(\bm{X})}\cdot(1-\pi_{0}(\bm{X}))\right\\}\right]$
$\displaystyle-\frac{1}{B}\mathbb{E}_{\bm{X}}\left[\tau(\bm{X})\sum_{t=1}^{j-1}\frac{\hat{\pi}_{t}(\bm{X})-\hat{\pi}_{t-1}(\bm{X})}{T-t}\right]\mathbb{E}\left[\mu_{0}(\bm{X})+\pi_{0}(\bm{X})\tau(\bm{X})\right]$
$\displaystyle=$
$\displaystyle\sum_{t=1}^{j-1}\frac{C_{t}}{T-t}-V(\pi_{0})\sum_{t=1}^{j-1}\frac{B_{t}}{T-t},$

where the definition of $B_{t}$ is given in Lemma 5 of Appendix S7.5 and
$C_{t}$ is defined:

$C_{t}\ :=\
\frac{1}{B}\mathbb{E}_{\bm{X}}\left[\left(\hat{\pi}_{t}(\bm{X})-\hat{\pi}_{t-1}(\bm{X})\right)\left\\{\frac{\mu_{1}(\bm{X})^{2}+\sigma_{1}^{2}(\bm{X})}{e(\bm{X})}\cdot\pi_{0}(\bm{X})+\frac{\mu_{0}(\bm{X})^{2}+\sigma_{0}^{2}(\bm{X})}{1-e(\bm{X})}\cdot(1-\pi_{0}(\bm{X}))\right\\}\right].$

Thus, the variance of the crammed policy evaluation estimator for the policy
value can be written as:

$\displaystyle\mathbb{V}(\widehat{\Psi}_{j}(T)\mid\mathcal{H}_{j-1})$
$\displaystyle=$
$\displaystyle\mathbb{V}(\widehat{\Gamma}_{j}(T)\mid\mathcal{H}_{j-1})+\frac{\mathbb{V}(\hat{\eta})}{T^{2}}+\frac{2}{T}\sum_{t=1}^{j-1}\frac{C_{t}}{T-t}-\frac{V(\pi_{0})}{T}\sum_{t=1}^{j-1}\frac{B_{t}}{T-t}$
$\displaystyle=$
$\displaystyle\frac{1}{B}\sum_{t_{1}=1}^{j-1}\sum_{t_{2}=1}^{j-1}\frac{1}{(T-t_{1})(T-t_{2})}A_{t_{1}t_{2}}-\frac{1}{B}\left(\sum_{t=1}^{j-1}\frac{B_{t}}{T-t}\right)^{2}+\frac{\mathbb{V}(\hat{\eta})}{T^{2}}+\frac{2}{T}\sum_{t=1}^{j-1}\frac{C_{t}}{T-t}-\frac{V(\pi_{0})}{T}\sum_{t=1}^{j-1}\frac{B_{t}}{T-t},$

where the second equality follows from Lemma 5 where $A_{t_{1}t_{2}}$ is also
defined.

Finally, define the following quantity:

$w_{T}^{2}\ :=\
T\cdot\sum_{j=1}^{T}\mathbb{V}(\widehat{\Psi}_{j}(T)\mid\mathcal{H}_{j-1})\ =\
v_{T}^{2}+\mathbb{V}(\hat{\eta})+{2}\sum_{j=2}^{T}\sum_{t=1}^{j-1}\frac{C_{t}}{T-t}.$

Then, following the proof of Theorem 2, we can show:

$\sqrt{T}\frac{\widehat{\Psi}(T)-V(\pi)}{w_{T}}\ \stackrel{{\scriptstyle
d}}{{\longrightarrow}}\ \mathcal{N}(0,1).$

##  Appendix S2 Proof of Theorem 1

###### Proof.

First, the triangle inequality and the Jensen’s inequality imply:

$\displaystyle\mathbb{E}\left[\Bigr{|}\widehat{\Delta}(\hat{\pi}_{T};\pi_{0})-\Delta(\hat{\pi}_{T};\pi_{0})\Bigr{|}\right]$
$\displaystyle\leq\mathbb{E}\left[\Bigr{|}\Delta(\hat{\pi}_{T};\hat{\pi}_{T-1})\Bigr{|}\right]+\mathbb{E}\left[\Bigr{|}\widehat{\Delta}(\hat{\pi}_{T};\pi_{0})-\Delta(\hat{\pi}_{T-1};\pi_{0})\Bigr{|}\right]$
$\displaystyle\leq\mathbb{E}\left[\Bigr{|}\Delta(\hat{\pi}_{T};\hat{\pi}_{T-1})\Bigr{|}\right]+\sqrt{\mathbb{E}\left[\left(\widehat{\Delta}(\hat{\pi}_{T};\pi_{0})-\Delta(\hat{\pi}_{T-1};\pi_{0})\right)^{2}\right]}$

Therefore, to prove
$\lim_{B\rightarrow\infty}\mathbb{E}\left[\Bigr{|}\widehat{\Delta}(\hat{\pi}_{T};\pi_{0})-\Delta(\hat{\pi}_{T};\pi_{0})\Bigr{|}\right]=0$,
it is suffice to show:

$\lim_{T\rightarrow\infty}\mathbb{E}\left[\Bigr{|}\Delta(\hat{\pi}_{T};\hat{\pi}_{T-1})\Bigr{|}\right]=0,\quad\text{and}\quad\lim_{T\rightarrow\infty}\mathbb{E}\left[\left(\widehat{\Delta}(\hat{\pi}_{T};\pi_{0})-\Delta(\hat{\pi}_{T-1};\pi_{0})\right)^{2}\right]=0.$

We will show a stronger result:

$\lim_{T\rightarrow\infty}T^{1+\delta/2}\mathbb{E}\left[\Bigr{|}\Delta(\hat{\pi}_{T};\hat{\pi}_{T-1})\Bigr{|}\right]=0.$

By the definition of the policy value difference, we have:
$\Delta(\hat{\pi}_{T};\hat{\pi}_{T-1})=\mathbb{E}_{\bm{X}}\left[(\hat{\pi}_{T}(\bm{X})-\hat{\pi}_{T-1}(\bm{X}))\tau(\bm{X})\right]$.
Because of the bounded conditional expectation (Assumption 4), the CATE is
also bounded, i.e.,

$\displaystyle\sup_{\bm{x}\in\mathcal{X}}|\tau(\bm{x})|=\sup_{\bm{x}\in\mathcal{X}}|\mu_{1}(\bm{x})-\mu_{0}(\bm{x})|\leq\sup_{\bm{x}\in\mathcal{X}}\mu_{1}(\bm{x})+\sup_{\bm{x}\in\mathcal{X}}\mu_{0}(\bm{x})<\infty.$

Therefore,

$\displaystyle\bigr{|}\mathbb{E}_{\bm{X}}\left[(\hat{\pi}_{T}(\bm{X})-\hat{\pi}_{T-1}(\bm{X}))\tau(\bm{X})\right]\bigr{|}$
$\displaystyle\leq\sup_{\bm{x}\in\mathcal{X}}|\tau(\bm{x})|\cdot\mathbb{E}_{\bm{X}}\left[|\hat{\pi}_{T}(\bm{X})-\hat{\pi}_{T-1}(\bm{X})|\right].$

Applying Lemma 1, we obtain:

$0\ \leq\
\lim_{T\rightarrow\infty}T^{1+\delta/2}\mathbb{E}\left[\Bigr{|}\Delta(\hat{\pi}_{T};\hat{\pi}_{T-1})\Bigr{|}\right]\
\leq\
\sup_{\bm{x}\in\mathcal{X}}|\tau(\bm{x})|\cdot\lim_{T\rightarrow\infty}\mathbb{E}\left[T^{1+\delta/2}\mathbb{E}_{\bm{X}}\left[|\hat{\pi}_{T}(\bm{X})-\hat{\pi}_{T-1}(\bm{X})|\right]\right]=0,$

implying the desired result, i.e.,
$\lim_{T\rightarrow\infty}T^{1+\delta/2}\mathbb{E}\left[\Bigr{|}\Delta(\hat{\pi}_{T};\hat{\pi}_{T-1})\Bigr{|}\right]=0$.

Next, we use Lemma 5 to show:

$\sum_{j=2}^{T}\mathbb{E}\left[\widehat{\Gamma}_{j}(T)\mid\mathcal{H}_{j-1}\right]\
=\
\sum_{j=2}^{T}\sum_{t=1}^{j-1}\frac{\Delta(\hat{\pi}_{t};\hat{\pi}_{t-1})}{T-t}\
=\ \Delta(\hat{\pi}_{T-1};\pi_{0}).$

Therefore,

$\displaystyle\mathbb{E}\left[\left(\widehat{\Delta}(\hat{\pi}_{T};\pi_{0})-\Delta(\hat{\pi}_{T-1};\pi_{0})\right)^{2}\right]\
=$
$\displaystyle\mathbb{E}\left[\left(\sum_{j=2}^{T}\left\\{\widehat{\Gamma}_{j}(T)-\mathbb{E}\left[\widehat{\Gamma}_{j}(T)\mid\mathcal{H}_{j-1}\right]\right\\}\right)^{2}\right]$
$\displaystyle\ =$
$\displaystyle\sum_{j=2}^{T}\mathbb{E}\left[\left(\widehat{\Gamma}_{j}(T)-\mathbb{E}\left[\widehat{\Gamma}_{j}(T)\mid\mathcal{H}_{j-1}\right]\right)^{2}\right]$
$\displaystyle\ =$
$\displaystyle\sum_{j=2}^{T}\mathbb{E}\left[\mathbb{E}\left[\left(\widehat{\Gamma}_{j}(T)-\mathbb{E}\left[\widehat{\Gamma}_{j}(T)\mid\mathcal{H}_{j-1}\right]\right)^{2}\
\Bigr{|}\ \mathcal{H}_{j-1}\right]\right]$ $\displaystyle\ =$
$\displaystyle\sum_{j=2}^{T}\mathbb{E}\left[\mathbb{V}\left(\widehat{\Gamma}_{j}(T)\mid\mathcal{H}_{j-1}\right)\right].$

Again, Lemma 5 implies:

$\displaystyle\mathbb{V}\left(\widehat{\Gamma}_{j}(T)\mid\mathcal{H}_{j-1}\right)$
$\displaystyle=\frac{1}{B}\sum_{t_{1}=1}^{j-1}\sum_{t_{2}=1}^{j-1}\frac{A_{t_{1}t_{2}}}{(T-t_{1})(T-t_{2})}-\frac{1}{B}\left(\sum_{t=1}^{j-1}\frac{B_{t}}{T-t}\right)^{2}$
$\displaystyle=\frac{1}{B}\sum_{t_{1}=1}^{j-1}\sum_{t_{2}=1}^{j-1}\frac{A_{t_{1}t_{2}}-B_{t_{1}}B_{t_{2}}}{(T-t_{1})(T-t_{2})}$

Therefore,

$\displaystyle\sum_{j=2}^{T}\mathbb{V}\left(\widehat{\Gamma}_{j}(T)\mid\mathcal{H}_{j-1}\right)$
$\displaystyle\ =\
\frac{1}{B}\sum_{j=2}^{T}\sum_{t_{1}=1}^{j-1}\sum_{t_{2}=1}^{j-1}\frac{A_{t_{1}t_{2}}-B_{t_{1}}B_{t_{2}}}{(T-t_{1})(T-t_{2})}$
$\displaystyle\ =\
\frac{1}{B}\sum_{j=2}^{T}\sum_{t=1}^{j-1}\frac{A_{tt}-B_{t}^{2}}{(T-t)^{2}}+\frac{2}{B}\sum_{j=2}^{T}\sum_{1\leq
t_{1}<t_{2}\leq
j-1}\frac{A_{t_{1}t_{2}}-B_{t_{1}}B_{t_{2}}}{(T-t_{1})(T-t_{2})}$
$\displaystyle\ =\
\frac{1}{B}\sum_{t=1}^{T-1}\frac{A_{tt}-B_{t}^{2}}{T-t}+\frac{2}{B}\sum_{1\leq
t_{1}<t_{2}\leq T-1}\frac{A_{t_{1}t_{2}}-B_{t_{1}}B_{t_{2}}}{T-t_{1}}$
$\displaystyle\ =\
\frac{1}{B}\sum_{t=1}^{T-1}\frac{A_{tt}-B_{t}^{2}}{T-t}+\frac{2}{B}\sum_{1\leq
t_{1}\leq
T-2}\frac{1}{T-t_{1}}\sum_{t_{2}=t_{1}+1}^{T-1}A_{t_{1}t_{2}}-B_{t_{1}}B_{t_{2}}.$

We will use the following two inequalities:

$\displaystyle|A_{tt}-B_{t}^{2}|$ $\displaystyle\ \leq\ |A_{tt}|+|B_{t}|^{2},$
$\displaystyle\left|\sum_{t_{2}=t_{1}+1}^{T-1}A_{t_{1}t_{2}}-B_{t_{1}}B_{t_{2}}\right|$
$\displaystyle\ \leq\
\sup_{t_{1}<T}\left|\sum_{t_{2}=t_{1}+1}^{T-1}A_{t_{1}t_{2}}\right|+|B_{t_{1}}|\sum_{t_{2}=t_{1}+1}^{T-1}|B_{t_{2}}|.$

Applying Lemma 6, we have, almost surely:

$\displaystyle|A_{tt}|+|B_{t}|^{2}$ $\displaystyle\ \leq\
K_{A}t^{-1-\delta}+K_{B}^{2}t^{-2-2\delta}\leq(K_{A}+K_{B}^{2})t^{-1-\delta}$
$\displaystyle\sup_{t_{1}<T}\left|\sum_{t_{2}=t_{1}+1}^{T-1}A_{t_{1}t_{2}}\right|+|B_{t_{1}}|\sum_{t_{2}=t_{1}+1}^{T-1}|B_{t_{2}}|$
$\displaystyle\ \leq\
K_{A}t_{1}^{-1-\delta}+K_{B}^{2}t_{1}^{-1-\delta}\sum_{t_{2}=t_{1}+1}^{T-1}t_{2}^{-1-\delta}$
$\displaystyle\ \leq\
\left(K_{A}+K_{B}^{2}\sum_{k=0}^{\infty}k^{-1-\delta}\right)t_{1}^{-1-\delta}$

Therefore,

$\displaystyle\sum_{j=2}^{T}\mathbb{E}\left[\mathbb{V}\left(\widehat{\Gamma}_{j}(T)\mid\mathcal{H}_{j-1}\right)\right]$
$\displaystyle=\ $
$\displaystyle\frac{1}{B}\sum_{t=1}^{T-1}\frac{\mathbb{E}\left[t^{1+\delta}\left(A_{tt}-B_{t}^{2}\right)\right]}{(T-t)t^{1+\delta}}+\frac{2}{B}\sum_{1\leq
t_{1}\leq
T-2}\frac{1}{(T-t_{1})t_{1}^{1+\delta}}\mathbb{E}\left[t_{1}^{1+\delta}\sum_{t_{2}=t_{1}+1}^{T-1}A_{t_{1}t_{2}}-B_{t_{1}}B_{t_{2}}\right]$
$\displaystyle\leq\ $
$\displaystyle\text{Constant}\cdot\sum_{t=1}^{T-1}\frac{1}{(T-t)t^{1+\delta}}+\text{Constant}\cdot\sum_{1\leq
t_{1}\leq T-2}\frac{1}{(T-t_{1})t_{1}^{1+\delta}}\ \ \text{almost surely}$
$\displaystyle\leq\ $
$\displaystyle\text{Constant}\cdot\sum_{t=1}^{T-1}\frac{1}{(T-t)t^{1+\delta}}\
\ \text{almost surely},$ (S1)

where the constant does not involve $T$. Because of Lemma 3,

$\lim_{T\rightarrow\infty}\sum_{t=1}^{T-1}\frac{1}{(T-t)t^{1+\delta}}=0$

implying,
$\lim_{T\rightarrow\infty}\sum_{j=2}^{T}\mathbb{E}\left[\mathbb{V}\left(\widehat{\Gamma}_{j}(T)\mid\mathcal{H}_{j-1}\right)\right]=0$.
Finally, combining the above results, we have shown the desired $L_{1}$
convergence. ∎

##  Appendix S3 Proof of Theorem 2

In this section, we prove the asymptotic normality of the crammed policy
evaluation estimator introduced in Definition 1. We first explain our overall
proof strategy and then formalize the argument.

To prove this theorem, we consider the conditional distribution of
$\widehat{\Delta}(\hat{\pi}_{T};\pi_{0})$ given the first $f(T)$ observations.
Here, we choose $f(T):=\lfloor T^{1/5}\rfloor$, which is equal to the greatest
integer that is no greater than $T^{1/5}$. The choice of this specific rate is
not important so long as $\lfloor T^{1/5}\rfloor$ goes to infinity (as
$T\rightarrow\infty$) at a slower rate than $T$. We will bound the distance
between this conditional distribution and the normal distribution, and then
show that the marginal distribution of
$\widehat{\Delta}(\hat{\pi}_{T};\pi_{0})$ converge to normal after appropriate
scaling.

We begin by decomposing the crammed policy evaluation estimator as follows:

$\displaystyle\widehat{\Delta}(\hat{\pi}_{T};\pi_{0})$
$\displaystyle=\sum_{t=1}^{T-1}\sum_{j=t+1}^{T}\frac{1}{T-t}\widehat{\Gamma}_{t,j}$
$\displaystyle=\underbrace{\sum_{t=1}^{f(T)}\sum_{j=t+1}^{f(T)}\frac{1}{T-t}\widehat{\Gamma}_{t,j}}_{=\zeta^{(1)}_{T}}+\underbrace{\sum_{t=f(T)+1}^{T-1}\sum_{j=t+1}^{T}\frac{1}{T-t}\widehat{\Gamma}_{t,j}}_{=\zeta^{(2)}_{T}}+\underbrace{\sum_{t=1}^{f(T)}\sum_{j=f(T)+1}^{T}\frac{1}{T-t}\widehat{\Gamma}_{t,j}}_{=\zeta^{(3)}_{T}}.$
(S2)

$\left.\begin{array}[]{c|ccccc:ccccc}\text{Policy
difference}&1&2&3&\cdots&f(T)&f(T)+1&f(T)+2&\cdots&T-1&T\\\
\hline\cr\hat{\pi}_{1}-\pi_{0}&$\checkmark$&\frac{\widehat{\Gamma}_{1,2}}{T-1}&\frac{\widehat{\Gamma}_{1,3}}{T-1}&\cdots&\frac{\widehat{\Gamma}_{1,f(T)}}{T-1}&\frac{\widehat{\Gamma}_{1,f(T)+1}}{T-1}&\frac{\widehat{\Gamma}_{1,f(T)+2}}{T-1}&\cdots&\frac{\widehat{\Gamma}_{1,T-1}}{T-1}&\frac{\widehat{\Gamma}_{1,T}}{T-1}\\\
\hat{\pi}_{2}-\hat{\pi}_{1}&\ $\checkmark$&\
$\checkmark$&\frac{\widehat{\Gamma}_{2,3}}{T-2}&\cdots&\frac{\widehat{\Gamma}_{2,f(T)}}{T-2}&\frac{\widehat{\Gamma}_{2,f(T)+1}}{T-2}&\frac{\widehat{\Gamma}_{2,f(T)+2}}{T-2}&\cdots&\frac{\widehat{\Gamma}_{2,T-1}}{T-2}&\frac{\widehat{\Gamma}_{2,T}}{T-2}\\\
\hat{\pi}_{3}-\hat{\pi}_{2}&\ $\checkmark$&\ $\checkmark$&\
$\checkmark$&\cdots&\frac{\widehat{\Gamma}_{3,f(T)}}{T-3}&\frac{\widehat{\Gamma}_{3,f(T)+1}}{T-3}&\frac{\widehat{\Gamma}_{3,f(T)+2}}{T-3}&\cdots&\frac{\widehat{\Gamma}_{3,T-1}}{T-3}&\frac{\widehat{\Gamma}_{3,T}}{T-3}\\\
\vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\\
\hat{\pi}_{f(T)}-\hat{\pi}_{f(T)-1}&\ $\checkmark$&\ $\checkmark$&\
$\checkmark$&\cdots&\
$\checkmark$&\frac{\widehat{\Gamma}_{f(T),f(T)+1}}{T-f(T)}&\frac{\widehat{\Gamma}_{f(T),f(T)+2}}{T-f(T)}&\cdots&\frac{\widehat{\Gamma}_{f(T),T-1}}{T-f(T)}&\frac{\widehat{\Gamma}_{f(T),T}}{T-f(T)}\\\
\hdashline\hat{\pi}_{f(T)+1}-\hat{\pi}_{f(T)}&\ $\checkmark$&\ $\checkmark$&\
$\checkmark$&\cdots&\ $\checkmark$&\
$\checkmark$&\frac{\widehat{\Gamma}_{f(T)+1,f(T)+2}}{T-f(T)-1}&\cdots&\frac{\widehat{\Gamma}_{f(T)+1,T-1}}{T-f(T)-1}&\frac{\widehat{\Gamma}_{f(T)+1,T}}{T-f(T)-1}\\\
\hat{\pi}_{f(T)+2}-\hat{\pi}_{f(T)+1}&\ $\checkmark$&\ $\checkmark$&\
$\checkmark$&\cdots&\ $\checkmark$&\ $\checkmark$&\
$\checkmark$&\cdots&\frac{\widehat{\Gamma}_{f(T)+2,T-1}}{T-f(T)-2}&\frac{\widehat{\Gamma}_{f(T)+2,T}}{T-f(T)-2}\\\
\vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\\
\hat{\pi}_{T-1}-\hat{\pi}_{T-2}&\ $\checkmark$&\ $\checkmark$&\
$\checkmark$&\cdots&\ $\checkmark$&\ $\checkmark$&\ $\checkmark$&\cdots&\
$\checkmark$&\frac{\widehat{\Gamma}_{T-1,T}}{T-T+1}\\\
\hat{\pi}_{T}-\hat{\pi}_{T-1}&\ $\checkmark$&\ $\checkmark$&\
$\checkmark$&\cdots&\ $\checkmark$&\ $\checkmark$&\ $\checkmark$&\cdots&\
$\checkmark$&\ $\checkmark$\\\ \hline\cr\end{array}\right.$

Table S1: Illustration of the proof strategy for Theorem 2. The $(t,j)$-th
cell of this matrix represents the estimator of the policy value difference
between $\hat{\pi}_{t}$ and $\hat{\pi}_{t-1}$ using the $j$th batch for $j>t$.
Summing these cells leads to the crammed policy evaluation estimator. The
cells with $\checkmark$ are used to denote the fact that these batches (i.e.,
$t\geq j$) are not used to evaluate the policy value difference between
$\hat{\pi}_{t}$ and $\hat{\pi}_{t-1}$. Our proof strategy is to show that the
upper-left and lower-right blocks are small, while the upper-right block is
asymptotically normal.

Table S1 illustrates this decomposition where $\zeta^{(1)}_{T}$,
$\zeta^{(1)}_{T}$, and $\zeta^{(1)}_{T}$ correspond to the upper-left block,
lower-right block, and upper-right block, respectively. Our proof strategy is
to show that $\zeta^{(1)}_{T}$ and $\zeta^{(2)}_{T}$ are negligible while
$\zeta^{(3)}_{T}$ is asymptotically normal after proper centering and scaling.
In particular, we first define the following conditional standard deviation:

$\xi(T):=\sqrt{\mathbb{V}\left(\sum_{t=1}^{f(T)}\widehat{\Gamma}_{t,f(T)+1}\
\Bigr{|}\ \mathcal{H}_{f(T)}\right)}.$

We then prove a total of five conditions, which together establish the
asymptotic normality result. We state these conditions here:

  1. 1.

$\xi(T)$ is lower bounded by a constant as $T\to\infty$. That is, there exists
a constant $c_{0}$, and $R_{3}>0$, such that $\forall T>R_{3}$ the following
inequality holds almost surely:

$\xi(T)\geq c_{0}$ (C1)

  2. 2.

$\xi(T)$ converges to $v_{T}$ with probability 1:

$\frac{\xi(T)}{v_{T}}\stackrel{{\scriptstyle p}}{{\longrightarrow}}1.$ (C2)

  3. 3.

$\zeta^{(1)}_{T}$ is negligibly small:

$\sqrt{T}\cdot\zeta^{(1)}_{T}\stackrel{{\scriptstyle p}}{{\longrightarrow}}0.$
(C3)

  4. 4.

$\zeta^{(2)}_{T}$ is negligibly small:

$\sqrt{T}\left(\zeta^{(2)}_{T}-\Delta(\hat{\pi}_{T};\hat{\pi}_{f(T)})\right)\stackrel{{\scriptstyle
p}}{{\longrightarrow}}0.$ (C4)

  5. 5.

Appropriately normalized $\zeta^{(3)}_{T}$ converges to the standard normal
distribution:

$\sqrt{T}\cdot\frac{\zeta^{(3)}_{T}-\Delta(\hat{\pi}_{f(T)};\pi_{0})}{\xi(T)}\stackrel{{\scriptstyle
d}}{{\longrightarrow}}N(0,1).$ (C5)

Under these conditions, we can prove the following proposition:

###### Proposition 3

Assume that Conditions (C1))–(C5) are satisfied. Then:

$\sqrt{T}\cdot\frac{\widehat{\Delta}(\hat{\pi}_{T};\pi_{0})-\Delta(\hat{\pi}_{T};\pi_{0})}{v_{T}}\xrightarrow{d}N(0,1)$

###### Proof.

$\displaystyle\sqrt{T}\cdot\frac{\widehat{\Delta}(\hat{\pi}_{T};\pi_{0})-\Delta(\hat{\pi}_{T};\pi_{0})}{v_{T}}$
$\displaystyle=$
$\displaystyle\sqrt{T}\cdot\frac{\zeta^{(1)}_{T}+\left(\zeta^{(2)}_{T}-\Delta(\hat{\pi}_{T};\hat{\pi}_{f(T)})\right)+\left(\zeta^{(3)}_{T}-\Delta(\hat{\pi}_{f(T)};\pi_{0})\right)}{v_{T}}$
$\displaystyle=$
$\displaystyle\sqrt{T}\cdot\frac{\zeta^{(1)}_{T}}{v_{T}}+\sqrt{T}\cdot\frac{\zeta^{(2)}_{T}-\Delta(\hat{\pi}_{T};\hat{\pi}_{f(T)})}{v_{T}}+\sqrt{T}\cdot\frac{\zeta^{(3)}_{T}-\Delta(\hat{\pi}_{f(T)};\pi_{0})}{v_{T}}$
$\displaystyle=$
$\displaystyle\underbrace{\frac{\xi(T)}{v_{T}}}_{\xrightarrow{p}1,\;(\ref{cond:xiconv})}\left(\underbrace{\frac{\sqrt{T}\zeta^{(1)}_{T}}{\xi(T)}}_{\xrightarrow{p}0,\;(\ref{cond:term1})\;\&\;(\ref{cond:xibound})}+\underbrace{\frac{\sqrt{T}\left(\zeta^{(2)}_{T}-\Delta(\hat{\pi}_{T};\hat{\pi}_{f(T)})\right)}{\xi(T)}}_{\xrightarrow{p}0,\;(\ref{cond:term2})\;\&\;(\ref{cond:xibound})}+\underbrace{\frac{\sqrt{T}\left(\zeta^{(3)}_{T}-\Delta(\hat{\pi}_{f(T)};\pi_{0})\right)}{\xi(T)}}_{\xrightarrow{d}N(0,1),\;(\ref{cond:term3})}\right)$
$\displaystyle\stackrel{{\scriptstyle d}}{{\longrightarrow}}$ $\displaystyle
N(0,1).$

∎

Theorem 2C3C2C1C4C5Lemma 2Lemma 3Lemma 4Lemma 5Lemma 6 Figure S1: A directed
acyclic graph of the proof structure for Theorem 2.

We now present a formal proof of Theorem 2. Figure S1 presents the proof
structure as a directed acyclic graph. Given this structure, we prove the five
conditions in the order of their numbering (i.e., from C1 to C5).

###  S3.1 Proof of Condition C1

###### Proof.

We can further rewrite $\xi(T)$ using the definition of
$\widehat{\Gamma}_{tj}$ as follows:

$\displaystyle\xi(T)^{2}=$
$\displaystyle\mathbb{V}\left(\sum_{t=1}^{f(T)}\widehat{\Gamma}_{t,f(T)+1}\
\Biggr{|}\ \mathcal{H}_{f(T)}\right)$ $\displaystyle=$
$\displaystyle\frac{1}{B}\mathbb{V}_{\bm{Z}}\left(\left\\{\frac{YD}{e(\bm{X})}-\frac{Y(1-D)}{1-e(\bm{X})}\right\\}\left(\hat{\pi}_{f(T)}(\bm{X})-\pi_{0}(\bm{X})\right)\right)$
$\displaystyle=$
$\displaystyle\frac{1}{B}\mathbb{V}_{\bm{X}}\left(\tau(\bm{X})\left(\hat{\pi}_{f(T)}(\bm{X})-\pi_{0}(\bm{X})\right)\right)$
$\displaystyle+\frac{1}{B}\mathbb{E}_{\bm{X}}\left[\left(\frac{\mu_{1}(\bm{X})^{2}+\sigma_{1}^{2}(\bm{X})}{e(\bm{X})}+\frac{\mu_{0}(\bm{X})^{2}+\sigma_{0}^{2}(\bm{X})}{1-e(\bm{X})}-\tau(\bm{X})^{2}\right)\left(\hat{\pi}_{f(T)}(\bm{X})-\pi_{0}(\bm{X})\right)^{2}\right]$
$\displaystyle\geq$
$\displaystyle\frac{1}{B}\mathbb{E}_{\bm{X}}\left[\left(\frac{\mu_{1}(\bm{X})^{2}+\sigma_{1}^{2}(\bm{X})}{e(\bm{X})}+\frac{\mu_{0}(\bm{X})^{2}+\sigma_{0}^{2}(\bm{X})}{1-e(\bm{X})}-\tau(\bm{X})^{2}\right)\left(\hat{\pi}_{f(T)}(\bm{X})-\pi_{0}(\bm{X})\right)^{2}\right],$

where $\bm{Z}=\\{\bm{X},D,Y\\}$. We next bound
$\tau(\bm{X})^{2}=\left(\mu_{1}(\bm{X})-\mu_{0}(\bm{X})\right)^{2}$.

$\displaystyle\tau(\bm{X})^{2}$
$\displaystyle\leq\left(|\mu_{1}(\bm{X})|+|\mu_{0}(\bm{X})|\right)^{2}$
$\displaystyle=\left(\frac{|\mu_{1}(\bm{X})|}{\sqrt{e(\bm{X})}}\cdot\sqrt{e(\bm{X})}+\frac{|\mu_{0}(\bm{X})|}{\sqrt{1-e(\bm{X})}}\cdot\sqrt{1-e(\bm{X})}\right)^{2}$
$\displaystyle\leq\left(\frac{\mu_{1}(\bm{X})^{2}}{e(\bm{X})}+\frac{\mu_{0}(\bm{X})^{2}}{1-e(\bm{X})}\right)\left({e(\bm{X})}+{1-e(\bm{X})}\right)$
$\displaystyle\leq\frac{\mu_{1}(\bm{X})^{2}}{e(\bm{X})}+\frac{\mu_{0}(\bm{X})^{2}}{1-e(\bm{X})},$

where the second inequality follows from the Cauchy-Schwarz’s inequality.
Putting these results together, we have:

$\xi(T)^{2}\geq\frac{1}{B}\mathbb{E}_{\bm{X}}\left[\left(\frac{\sigma_{1}^{2}(\bm{X})}{e(\bm{X})}+\frac{\sigma_{0}^{2}(\bm{X})}{1-e(\bm{X})}\right)\left(\hat{\pi}_{f(T)}(\bm{X})-\pi_{0}(\bm{X})\right)^{2}\right].$

Assumption 4 implies the existence of a uniform lower bound $\sigma^{2}_{L}$
such that
$\inf_{\mathbf{x}\in\mathcal{X}}\sigma_{d}^{2}(\mathbf{x})\geq\sigma^{2}_{L}$
for $d=0,1$. Combining this fact with the overlap assumption (Assumption 1),
we apply Jensen’s inequality and obtain:

$\displaystyle\xi(T)^{2}$
$\displaystyle\geq\frac{2\sigma^{2}_{L}}{Bc}\mathbb{E}_{\bm{X}}\left[\left(\hat{\pi}_{f(T)}(\bm{X})-\pi_{0}(\bm{X})\right)^{2}\right]$
$\displaystyle\geq\frac{2\sigma^{2}_{L}}{Bc}\mathbb{E}_{\bm{X}}\left[|\hat{\pi}_{f(T)}(\bm{X})-\pi_{0}(\bm{X})|\right]^{2}.$

Because of Lemma 2, there exists a constant $R_{2}>0$ such that for all $t\geq
R_{2}$,

$\mathbb{E}_{\bm{X}}\left[|\hat{\pi}_{t}(\bm{X})-\pi_{0}(\bm{X})|\right]\geq\frac{M_{1}}{2}\
\ \text{almost surely}.$

Therefore, let $R_{3}=(R_{2}+1)^{5}$, then $T>R_{3}$ implies $f(T)=\lfloor
T^{1/5}\rfloor\geq R_{2}$. For any $T>R_{3}$,

$\displaystyle\xi(T)^{2}\geq\frac{2\sigma^{2}_{L}}{Bc}\mathbb{E}_{\bm{X}}\left[|\hat{\pi}_{f(T)}(\bm{X})-\pi_{0}(\bm{X})|\right]^{2}\geq\frac{\sigma^{2}_{L}M_{1}^{2}}{2Bc}\
\ \text{almost surely.}$

∎

###  S3.2 Proof of Condition C2

###### Proof.

To prove this condition, it suffices to show:

$\frac{\xi(T)^{2}}{v_{T}^{2}}\xrightarrow{p}1,$

because both $\xi(T)$ and $v_{T}$ are non-negative. First, we show that
$v_{T}^{2}$ and $\xi(T)^{2}$ have a vanishing difference as $T\to\infty$. By
definition of $v_{T}^{2}$ given in Theorem 2 and utilizing Lemma 5, we have:

$\displaystyle v_{T}^{2}$
$\displaystyle=T\sum_{j=2}^{T}\mathbb{V}\left(\widehat{\Gamma}_{j}(T)\mid\mathcal{H}_{j-1}\right)$
$\displaystyle=\frac{T}{B}\sum_{j=2}^{T}\left[\sum_{t_{1}=1}^{j-1}\sum_{t_{2}=1}^{j-1}\frac{A_{t_{1}t_{2}}}{(T-t_{1})(T-t_{2})}-\left(\sum_{t=1}^{j-1}\frac{B_{t}}{T-t}\right)^{2}\right]$
$\displaystyle=\frac{T}{B}\sum_{j=2}^{T}\left[\sum_{t=1}^{j-1}\frac{A_{tt}-B_{t}^{2}}{(T-t)^{2}}+\sum_{1\leq
t_{1}<t_{2}\leq
j-1}\frac{2A_{t_{1}t_{2}}-2B_{t_{1}}B_{t_{2}}}{(T-t_{1})(T-t_{2})}\right]$
$\displaystyle=\frac{T}{B}\sum_{t=1}^{T-1}\frac{A_{tt}-B_{t}^{2}}{T-t}+\frac{2T}{B}\sum_{1\leq
t_{1}<t_{2}\leq T-1}\frac{A_{t_{1}t_{2}}-B_{t_{1}}B_{t_{2}}}{T-t_{1}}$
$\displaystyle=\frac{T}{B}\sum_{t=1}^{T-1}\frac{A_{tt}-B_{t}^{2}}{T-t}+\frac{2T}{B}\sum_{1\leq
t_{1}\leq
T-2}\frac{1}{T-t_{1}}\sum_{t_{2}=t_{1}+1}^{T-1}\left(A_{t_{1}t_{2}}-B_{t_{1}}B_{t_{2}}\right),$

where $A_{t_{1},t_{2}}$ and $B_{t}$ are defined in Lemma 5.

Similarly, we obtain:

$\displaystyle\xi(T)^{2}$
$\displaystyle=\mathbb{V}\left(\sum_{t=1}^{f(T)}\widehat{\Gamma}_{t,f(T)+1}\
\Bigr{|}\ \mathcal{H}_{f(T)}\right)$
$\displaystyle=\frac{1}{B}\mathbb{V}_{\bm{Z}}\left(\left(\frac{YD}{e(\bm{X})}-\frac{Y(1-D)}{1-e(\bm{X})}\right)\left(\hat{\pi}_{f(T)}(\bm{X})-\pi_{0}(\bm{X})\right)\right)$
$\displaystyle=\frac{1}{B}\mathbb{V}_{\bm{X}}\left(\tau(\bm{X})(\hat{\pi}_{f(T)}(\bm{X})-\pi_{0}(\bm{X})\right)$
$\displaystyle\ \
+\frac{1}{B}\mathbb{E}_{\bm{X}}\left[\left(\frac{\mu_{1}(\bm{X})^{2}+\sigma_{1}^{2}(\bm{X})}{e(\bm{X})}+\frac{\mu_{0}(\bm{X})^{2}+\sigma_{0}^{2}(\bm{X})}{1-e(\bm{X})}-\tau(\bm{X})^{2}\right)\left(\hat{\pi}_{f(T)}(\bm{X})-\pi_{0}(\bm{X})\right)^{2}\right]$
$\displaystyle=\frac{1}{B}\mathbb{E}_{\bm{X}}\left[\left(\frac{\mu_{1}(\bm{X})^{2}+\sigma_{1}^{2}(\bm{X})}{e(\bm{X})}+\frac{\mu_{0}(\bm{X})^{2}+\sigma_{0}^{2}(\bm{X})}{1-e(\bm{X})}\right)\left(\hat{\pi}_{f(T)}(\bm{X})-\pi_{0}(\bm{X})\right)^{2}\right]$
$\displaystyle\ \
-\frac{1}{B}\mathbb{E}_{\bm{X}}\left[\tau(\bm{X})(\hat{\pi}_{f(T)}(\bm{X})-\pi_{0}(\bm{X}))\right]^{2}$
$\displaystyle=\frac{1}{B}\sum_{t_{1}=1}^{f(T)}\sum_{t_{2}=1}^{f(T)}\left(A_{t_{1}t_{2}}-B_{t_{1}}B_{t_{2}}\right)$
$\displaystyle=\frac{1}{B}\sum_{t=1}^{f(T)}\left(A_{tt}-B_{t}^{2}\right)+\frac{2}{B}\sum_{1\leq
t_{1}<t_{2}\leq f(T)}\left(A_{t_{1}t_{2}}-B_{t_{1}}B_{t_{2}}\right).$

Therefore, we have:

$\displaystyle v_{T}^{2}-\xi(T)^{2}$
$\displaystyle=\frac{T}{B}\sum_{t=1}^{T-1}\frac{A_{tt}-B_{t}^{2}}{T-t}+\frac{2T}{B}\sum_{t_{1}=1}^{T-2}\frac{1}{T-t_{1}}\sum_{t_{2}=t_{1}+1}^{T-1}\left(A_{t_{1}t_{2}}-B_{t_{1}}B_{t_{2}}\right)$
$\displaystyle\ \ \
-\frac{1}{B}\sum_{t=1}^{f(T)}\left(A_{tt}-B_{t}^{2}\right)-\frac{2}{B}\sum_{1\leq
t_{1}<t_{2}\leq f(T)}\left(A_{t_{1}t_{2}}-B_{t_{1}}B_{t_{2}}\right)$
$\displaystyle=\frac{1}{B}\sum_{t=1}^{f(T)}\frac{t(A_{tt}-B_{t}^{2})}{T-t}+\frac{T}{B}\sum_{t=f(T)+1}^{T-1}\frac{A_{tt}-B_{t}^{2}}{T-t}$
$\displaystyle\ \ \ +\frac{2}{B}\sum_{1\leq t_{1}\leq
f(T)-1}\frac{t_{1}}{T-t_{1}}\sum_{t_{2}=t_{1}+1}^{f(T)}\left(A_{t_{1}t_{2}}-B_{t_{1}}B_{t_{2}}\right)$
$\displaystyle\ \ \
+\frac{2T}{B}\sum_{t_{1}=1}^{T-2}\frac{1}{T-t_{1}}\sum_{t_{2}=\max\\{f(T),t_{1}\\}+1}^{T-1}\left(A_{t_{1}t_{2}}-B_{t_{1}}B_{t_{2}}\right).$
(S3)

Now, we analyze each term of the above expression of $v_{T}^{2}-\xi(T)^{2}$
and show that it goes to zero in probability as $T\to\infty$. We begin with
the first term, which can be bounded as follows:

$\frac{1}{B}\left|\sum_{t=1}^{f(T)}\frac{t(A_{tt}-B_{t}^{2})}{T-t}\right|\leq\frac{f(T)}{B(T-f(T))}\sum_{t=1}^{f(T)}|A_{tt}-B_{t}^{2}|\leq\frac{f(T)^{2}}{T-f(T)}\cdot\frac{K_{A}+K_{B}^{2}}{B},$

where the second inequality follows from Lemma 6 and $K_{A}$ and $K_{B}$ are
the constants defined in the same lemma as well. Since $f(T)=\lfloor
T^{1/5}\rfloor$ and $\lim_{T\rightarrow\infty}f(T)^{2}/(T-f(T))=0$, the first
term of Equation (S3) goes to zero as $T\rightarrow\infty$, i.e.,

$\frac{1}{B}\left|\sum_{t=1}^{f(T)}\frac{t(A_{tt}-B_{t}^{2})}{T-t}\right|\stackrel{{\scriptstyle
p}}{{\longrightarrow}}0.$

For the second term of Equation (S3), Lemma 6 implies,
$|A_{tt}-B_{t}^{2}|\leq|A_{tt}|+|B_{t}|^{2}\leq(K_{A}+K_{B}^{2})t^{-1-\delta}$
almost surely. Therefore, we have:

$\left|\frac{T}{B}\sum_{t=f(T)+1}^{T-1}\frac{A_{tt}-B_{t}^{2}}{T-t}\right|\leq\frac{K_{A}+K_{B}^{2}}{B}\sum_{t=f(T)+1}^{T-1}\frac{T}{(T-t)t^{1+\delta}}\
\ \text{almost surely}.$

By Lemma 3,

$0\leq\lim_{T\rightarrow\infty}\sum_{t=f(T)+1}^{T-1}\frac{T}{(T-t)t^{1+\delta}}=\lim_{T\rightarrow\infty}\sum_{t=f(T)+1}^{T-1}\frac{1}{t^{\delta}(T-t)}+\frac{1}{t^{1+\delta}}\leq\lim_{T\rightarrow\infty}\sum_{t=1}^{T-1}\frac{1}{t^{\delta}(T-t)}+\frac{1}{t^{1+\delta}}\
=\ 0.$

Thus,

$\left|\frac{T}{B}\sum_{t=f(T)+1}^{T-1}\frac{A_{tt}-B_{t}^{2}}{T-t}\right|\rightarrow
0\ \ \text{almost surely}.$

To show that the third term of Equation (S3) goes to zero, we take a similar
strategy and show:

$\displaystyle\left|\frac{2}{B}\sum_{1\leq t_{1}\leq
f(T)-1}\frac{t_{1}}{T-t_{1}}\sum_{t_{2}=t_{1}+1}^{f(T)}\left(A_{t_{1}t_{2}}-B_{t_{1}}B_{t_{2}}\right)\right|$
$\displaystyle\leq\frac{2(K_{A}+K_{B}^{2})}{B}\sum_{1\leq t_{1}\leq
f(T)-1}\frac{t_{1}(f(T)-t_{1})}{T-t_{1}}$
$\displaystyle\leq\frac{2(K_{A}+K_{B}^{2})}{B}\cdot\frac{f(T)^{3}}{T-f(T)}\ \
\text{almost surely}.$

Because $\lim_{T\rightarrow\infty}f(T)^{3}/(T-f(T))=0$ when $f(T)=\lfloor
T^{1/5}\rfloor$, the third term of Equation (S3) also goes to zero almost
surely.

Finally, we consider the fourth term of of Equation (S3), which can be
rewritten as:

$\frac{2T}{B}\sum_{t_{1}=1}^{T-2}\frac{1}{T-t_{1}}\sum_{t_{2}=\max\\{f(T),t_{1}\\}+1}^{T-1}\left(A_{t_{1}t_{2}}-B_{t_{1}}B_{t_{2}}\right)\
=\
\frac{2T}{B}\sum_{t_{2}=f(T)+1}^{T-1}\sum_{t_{1}=1}^{t_{2}-1}\frac{A_{t_{1}t_{2}}-B_{t_{1}}B_{t_{2}}}{T-t_{1}}.$

To bound this quantity, we can show:

$\displaystyle\sum_{t_{1}=1}^{t_{2}-1}\frac{A_{t_{1}t_{2}}}{T-t_{1}}$
$\displaystyle=$
$\displaystyle\mathbb{E}_{\bm{X}}\left[\left(\frac{\mu_{1}(\bm{X})^{2}+\sigma_{1}^{2}(\bm{X})}{e(\bm{X})}+\frac{\mu_{0}(\bm{X})^{2}+\sigma_{0}^{2}(\bm{X})}{1-e(\bm{X})}\right)\left(\hat{\pi}_{t_{2}}(\bm{X})-\hat{\pi}_{t_{2}-1}(\bm{X})\right)\sum_{t_{1}=1}^{t_{2}-1}\frac{\hat{\pi}_{t_{1}}(\bm{X})-\hat{\pi}_{t_{1}-1}(\bm{X})}{T-t_{1}}\right]$
$\displaystyle\leq$
$\displaystyle\left|\sum_{t_{1}=1}^{t_{2}-1}\frac{\hat{\pi}_{t_{1}}(\bm{X})-\hat{\pi}_{t_{1}-1}(\bm{X})}{T-t_{1}}\right|\cdot\mathbb{E}_{\bm{X}}\left[\left(\frac{\mu_{1}(\bm{X})^{2}+\sigma_{1}^{2}(\bm{X})}{e(\bm{X})}+\frac{\mu_{0}(\bm{X})^{2}+\sigma_{0}^{2}(\bm{X})}{1-e(\bm{X})}\right)\left|\hat{\pi}_{t_{2}}(\bm{X})-\hat{\pi}_{t_{2}-1}(\bm{X})\right|\right]$
$\displaystyle\leq$
$\displaystyle\left|\sum_{t_{1}=1}^{t_{2}-1}\frac{\hat{\pi}_{t_{1}}(\bm{X})-\hat{\pi}_{t_{1}-1}(\bm{X})}{T-t_{1}}\right|\cdot\sup_{\bm{x}\in\mathcal{X}}\left(\frac{\mu_{1}(\bm{x})^{2}+\sigma_{1}^{2}(\bm{x})}{e(\bm{x})}+\frac{\mu_{0}(\bm{x})^{2}+\sigma_{0}^{2}(\bm{x})}{1-e(\bm{x})}\right)\cdot\mathbb{E}_{\bm{X}}\left[\left|\hat{\pi}_{t_{2}}(\bm{X})-\hat{\pi}_{t_{2}-1}(\bm{X})\right|\right].$

Lemma 4 implies:

$\left|\sum_{t_{1}=1}^{t_{2}-1}\frac{\hat{\pi}_{t_{1}}(\bm{X})-\hat{\pi}_{t_{1}-1}(\bm{X})}{T-t_{1}}\right|\leq\frac{1}{T-t_{2}+1}.$

In addition, Assumptions 1 and 4 imply:

$\displaystyle\sup_{\bm{x}\in\mathcal{X}}\left(\frac{\mu_{1}(\bm{x})^{2}+\sigma_{1}^{2}(\bm{x})}{e(\bm{x})}+\frac{\mu_{0}(\bm{x})^{2}+\sigma_{0}^{2}(\bm{x})}{1-e(\bm{x})}\right)\leq
K_{A}<\infty,$

where $K_{A}$ is a constant defined in Lemma 5. Furthermore, Assumption 2
implies that there exist $K_{0},R_{1},\delta>0$ such that for all
$t_{2}>R_{1}$,

$\left|\sum_{t_{1}=1}^{t_{2}-1}\frac{A_{t_{1}t_{2}}}{T-t_{1}}\right|\leq\frac{K_{A}K_{0}}{T-t_{2}+1}t_{2}^{-1-\delta}.$

Similarly, it is also straightforward to show:

$\left|\sum_{t_{1}=1}^{t_{2}-1}\frac{B_{t_{1}}}{T-t_{1}}\right|\leq\sup_{\bm{x}\in\mathcal{X}}|\tau(\bm{x})|\cdot\frac{1}{T-t_{2}+1}.$

By Lemma 6, we have:

$|B_{t_{2}}|\sum_{t_{1}=1}^{t_{2}-1}\frac{|B_{t_{1}}|}{T-t_{1}}\leq\sup_{\bm{x}\in\mathcal{X}}|\tau(\bm{x})|\cdot\frac{1}{T-t_{2}+1}|B_{t_{1}}|\leq\frac{K_{B}\sup_{\bm{x}\in\mathcal{X}}|\tau(\bm{x})|}{(T-t_{2}+1)t_{2}^{1+\delta}}\
\ \text{almost surely}.$

Therefore, for $t_{2}>R_{1}$,

$\displaystyle\left|\sum_{t_{1}=1}^{t_{2}-1}\frac{A_{t_{1}t_{2}}-B_{t_{1}}B_{t_{2}}}{T-t_{1}}\right|\leq\frac{K_{B}\sup_{\bm{x}\in\mathcal{X}}|\tau(\bm{x})|+K_{A}K_{0}}{(T-t_{2}+1)t_{2}^{1+\delta}}\
\ \text{almost surely},$ (S4)

and

$\left|\frac{2T}{B}\sum_{t_{2}=f(T)+1}^{T-1}\sum_{t_{1}=1}^{t_{2}-1}\frac{A_{t_{1}t_{2}}-B_{t_{1}}B_{t_{2}}}{T-t_{1}}\right|\leq\frac{2T}{B}\sum_{t_{2}=f(T)+1}^{T-1}\frac{K_{B}\sup_{\bm{x}\in\mathcal{X}}|\tau(\bm{x})|+K_{A}K_{0}}{(T-t_{2}+1)t_{2}^{1+\delta}}\
\ \text{almost surely}.$

Utilizing Lemma 3, we can show:

$\displaystyle\lim_{T\rightarrow\infty}\sum_{t_{2}=f(T)+1}^{T-1}\frac{T}{(T-t_{2}+1)t_{2}^{1+\delta}}=0.$

We therefore have the fourth term of Equation (S3) converges to zero almost
surely as $T$ goes to infinity.

$\displaystyle\frac{2T}{B}\sum_{t_{1}=1}^{T-2}\frac{1}{T-t_{1}}\sum_{t_{2}=\max\\{f(T),t_{1}\\}+1}^{T-1}\left(A_{t_{1}t_{2}}-B_{t_{1}}B_{t_{2}}\right)\rightarrow
0\ \ \text{almost surely}.$

Combining the above results yields:

$|v_{T}^{2}-\xi(T)^{2}|\stackrel{{\scriptstyle p}}{{\longrightarrow}}0.$

Using Condition C1, we can show:

$\displaystyle\lim_{T\rightarrow\infty}\mathbb{P}\left(v_{T}^{2}<\frac{c_{0}}{2}\right)$
$\displaystyle\leq\lim_{T\rightarrow\infty}\mathbb{P}\left(|\xi(T)^{2}-v_{T}^{2}|>\frac{c_{0}}{2}\right)+\mathbb{P}\left(\xi(T)^{2}<c_{0}\right)=0$
(S5)

So for all $\epsilon>0$, we have:

$\displaystyle\lim_{T\rightarrow\infty}\mathbb{P}\left(\left|\frac{\xi(T)^{2}}{v_{T}^{2}}-1\right|>\epsilon\right)$
$\displaystyle\leq\lim_{T\rightarrow\infty}\mathbb{P}\left(v_{T}^{2}<\frac{c_{0}}{2}\right)+\mathbb{P}\left(\left|\frac{\xi(T)^{2}}{v_{T}^{2}}-1\right|>\epsilon,v_{T}^{2}\geq\frac{c_{0}}{2}\right)$
$\displaystyle\leq\lim_{T\rightarrow\infty}\mathbb{P}\left(v_{T}^{2}<\frac{c_{0}}{2}\right)+\mathbb{P}\left(|\xi(T)^{2}-v_{T}^{2}|>\frac{c_{0}\epsilon}{2}\right)=0$

∎

###  S3.3 Proof of Condition C3

###### Proof.

For the first term $\zeta^{(1)}_{T}$ of Equation (S2), recall:

$\sum_{t=1}^{j-1}\frac{1}{T-t}\widehat{\Gamma}_{t,j}=\left[\frac{1}{B}\sum_{i\in\mathcal{B}_{j}}\frac{Y_{i}D_{i}}{e(\bm{X}_{i})}-\frac{Y_{i}(1-D_{i})}{1-e(\bm{X}_{i})}\right]\cdot\sum_{t=1}^{j-1}\frac{\hat{\pi}_{t}(\bm{X}_{i})-\hat{\pi}_{t-1}(\bm{X}_{i})}{T-t}.$

Applying Lemma 4 to the second term in this equation yields:

$\left|\sum_{t=1}^{j-1}\frac{1}{T-t}\widehat{\Gamma}_{t,j}\right|\leq\left|\frac{1}{B}\sum_{i\in\mathcal{B}_{j}}\frac{Y_{i}D_{i}}{e(\bm{X}_{i})}-\frac{Y_{i}(1-D_{i})}{1-e(\bm{X}_{i})}\right|\cdot\frac{1}{T-j+1}.$

Therefore,

$\displaystyle|\zeta^{(1)}_{T}|$ $\displaystyle\ =\
\left|\sum_{j=2}^{f(T)}\sum_{t=1}^{j-1}\frac{1}{T-t}\widehat{\Gamma}_{t,j}\right|$
$\displaystyle\ \leq\
\sum_{j=2}^{f(T)}\frac{1}{T-j+1}\left|\frac{1}{B}\sum_{i\in\mathcal{B}_{j}}\frac{Y_{i}D_{i}}{e(\bm{X}_{i})}-\frac{Y_{i}(1-D_{i})}{1-e(\bm{X}_{i})}\right|$
$\displaystyle\ \leq\
\frac{1}{T-f(T)}\sum_{j=2}^{f(T)}\left|\frac{1}{B}\sum_{i\in\mathcal{B}_{j}}\frac{Y_{i}D_{i}}{e(\bm{X}_{i})}-\frac{Y_{i}(1-D_{i})}{1-e(\bm{X}_{i})}\right|.$

By the positivity assumption (Assumption 1), $c\leq e(\bm{x})\leq 1-c$ for any
$\bm{x}\in\mathcal{X}$. Therefore,

$\displaystyle\left|\sqrt{T}\zeta^{(1)}_{T}\right|$
$\displaystyle\leq\frac{\sqrt{T}}{T-f(T)}\sum_{j=2}^{f(T)}\left|\frac{1}{B}\sum_{i\in\mathcal{B}_{j}}\frac{Y_{i}D_{i}}{e(\bm{X}_{i})}-\frac{Y_{i}(1-D_{i})}{1-e(\bm{X}_{i})}\right|$
$\displaystyle\leq\frac{\sqrt{T}}{(T-f(T))B}\sum_{j=2}^{f(T)}\sum_{i\in\mathcal{B}_{j}}\frac{2}{c}\bigr{|}Y_{i}\bigr{|}.$

By Chebyshev’s inequality, we have

$\displaystyle\mathbb{P}\left(\left|\sqrt{T}\zeta^{(1)}_{T}\right|>\epsilon\right)$
$\displaystyle\leq\frac{1}{\epsilon}\mathbb{E}\left[\left|\sqrt{T}\zeta^{(1)}_{T}\right|\right]\leq\frac{2\sqrt{T}}{\epsilon
Bc(T-f(T))}\mathbb{E}\left[\sum_{j=2}^{f(T)}\sum_{i\in\mathcal{B}_{j}}\bigr{|}Y_{i}\bigr{|}\right]\leq\frac{2\sqrt{T}f(T)}{\epsilon
c(T-f(T))}\mathbb{E}\left[|Y|\right].$

Assumption 5 and Jensen’s inequality imply,
$\mathbb{E}\left[|Y|\right]\leq\left(\mathbb{E}\left[|Y|^{4}\right]\right)^{1/4}\leq
K_{4}^{1/4}.$ Therefore, $\forall\epsilon>0$,

$0\leq\lim_{T\rightarrow\infty}\mathbb{P}\left(\left|\sqrt{T}\zeta^{(1)}_{T}\right|>\epsilon\right)\leq\lim_{T\rightarrow\infty}\frac{2\sqrt{T}f(T)K_{4}^{\frac{1}{4}}}{\epsilon
c(T-f(T))}=\lim_{T\rightarrow\infty}\frac{2T^{7/10}K_{4}^{1/4}}{\epsilon
c(T-T^{1/5})}=0.$

Then, as $T\rightarrow\infty$, we have
$\sqrt{T}\zeta^{(1)}_{T}\stackrel{{\scriptstyle p}}{{\longrightarrow}}0$ as
desired. ∎

###  S3.4 Proof of Condition C4

###### Proof.

To show that $\zeta^{(2)}_{T}$ of Equation (S2) is negligibly small, notice

$\displaystyle\zeta^{(2)}_{T}-\Delta(\hat{\pi}_{T};\hat{\pi}_{f(T)})$
$\displaystyle=\sum_{t=f(T)+1}^{T-1}\sum_{j=t+1}^{T}\left(\frac{1}{T-t}\widehat{\Gamma}_{tj}-\Delta(\hat{\pi}_{t};\hat{\pi}_{t-1})\right)-\Delta(\hat{\pi}_{T};\hat{\pi}_{T-1})$
$\displaystyle=\sum_{t=f(T)+1}^{T-1}\left(\sum_{j=t+1}^{T}\frac{1}{T-t}\left(\widehat{\Gamma}_{tj}-\mathbb{E}\left[\widehat{\Gamma}_{tj}\mid\mathcal{H}_{t}\right]\right)\right)-\Delta(\hat{\pi}_{T};\hat{\pi}_{T-1})$
(S6)

where the second equality follows from Lemma 5. In the first step of the proof
of Theorem 1, we have shown
$\lim_{T\rightarrow\infty}T^{1+\delta/2}\mathbb{E}\left[|\Delta(\hat{\pi}_{T};\hat{\pi}_{T-1})|\right]=0$.
This directly implies as $T\rightarrow\infty$,
$\sqrt{T}\Delta(\hat{\pi}_{T};\hat{\pi}_{T-1})\xrightarrow{p}0$.

Therefore, we only need to deal with the first term of Equation (S6). Applying
Chebyshev’s inequality yields:

$\displaystyle\mathbb{P}\left(\sqrt{T}\left|\sum_{t=f(T)+1}^{T-1}\left(\sum_{j=t+1}^{T}\frac{1}{T-t}\left(\widehat{\Gamma}_{tj}-\mathbb{E}\left[\widehat{\Gamma}_{tj}\mid\mathcal{H}_{t}\right]\right)\right)\right|\geq\epsilon\right)$
$\displaystyle\leq\ $
$\displaystyle\frac{{T}}{\epsilon^{2}}\mathbb{E}\left[\left\\{\sum_{t=f(T)+1}^{T-1}\left(\sum_{j=t+1}^{T}\frac{1}{T-t}\left(\widehat{\Gamma}_{tj}-\mathbb{E}\left[\widehat{\Gamma}_{tj}\mid\mathcal{H}_{t}\right]\right)\right)\right\\}^{2}\right],$
(S7)

for any $\epsilon>0$. We can rewrite the expectation of Equation (S7) as:

$\mathbb{E}\left[\left\\{\sum_{t=f(T)+1}^{T-1}\sum_{j=t+1}^{T}M_{tj}(T)\right\\}^{2}\right]\quad\text{where}\quad
M_{tj}(T)=\frac{1}{T-t}\left(\widehat{\Gamma}_{tj}-\mathbb{E}\left[\widehat{\Gamma}_{tj}\mid\mathcal{H}_{t}\right]\right).$

Arrange these terms first by $t$ and then by $j$, (e.g.,
$M_{f(T)+1,f(T)+2}(T),M_{f(T)+1,f(T)+3}(T),$
$\cdots,M_{f(T)+1,T}(T),M_{f(T)+2,f(T)+3}(T),\cdots,M_{f(T)+2,T}(T),\cdots,M_{T-1,T}(T)$),
where the filtration of $M_{tj}(T)$ is $\mathcal{H}_{t}$. By construction, we
obtain a martingale difference sequence:

$\displaystyle\mathbb{E}\left[\left\\{\sum_{t=f(T)+1}^{T-1}\sum_{j=t+1}^{T}M_{tj}(T)\right\\}^{2}\right]$
$\displaystyle=\mathbb{E}\left[\sum_{t=f(T)+1}^{T-1}\sum_{j=t+1}^{T}\mathbb{E}\left[M_{tj}(T)^{2}\mid\mathcal{H}_{t}\right]\right]$
$\displaystyle=\mathbb{E}\left[\sum_{t=f(T)+1}^{T-1}\sum_{j=t+1}^{T}\frac{\mathbb{V}(\widehat{\Gamma}_{tj}\mid\mathcal{H}_{t})}{(T-t)^{2}}\right].$

The application of Lemma 5 yields:

$\sum_{t=f(T)+1}^{T-1}\sum_{j=t+1}^{T}\mathbb{E}\left[M_{tj}(T)^{2}\mid\mathcal{H}_{t}\right]\
=\ \sum_{t=f(T)+1}^{T-1}\frac{A_{tt}-B_{t}^{2}}{B(T-t)}.$

Using Lemma 6, we can obtain a upper bound:

$\displaystyle\left|\mathbb{E}\left[\left\\{\sum_{t=f(T)+1}^{T-1}\sum_{j=t+1}^{T}M_{tj}(T)\right\\}^{2}\right]\right|$
$\displaystyle=\left|\sum_{t=f(T)+1}^{T-1}\frac{\mathbb{E}\left[A_{tt}-B_{t}^{2}\right]}{B(T-t)}\right|$
$\displaystyle\leq\sum_{t=f(T)+1}^{T-1}\frac{\mathbb{E}\left[|A_{tt}|+|B_{t}|^{2}\right]}{B(T-t)}$
$\displaystyle\leq\sum_{t=f(T)+1}^{T-1}\frac{K_{A}+K_{B}^{2}}{B(T-t)t^{1+\delta}}\
\ \text{almost surely}.$

Therefore, $\forall\epsilon>0$,

$\displaystyle\lim_{T\rightarrow\infty}\frac{T}{\epsilon^{2}}\mathbb{E}\left[\left\\{\sum_{t=f(T)+1}^{T-1}\sum_{j=t+1}^{T}M_{t,j}(T)\right\\}^{2}\right]$
$\displaystyle\leq\ $
$\displaystyle\lim_{T\rightarrow\infty}\frac{T}{\epsilon^{2}}\cdot\frac{K_{A}+K_{B}^{2}}{B}\cdot\frac{1}{T}\left(\sum_{t=f(T)+1}^{T-1}\frac{1}{t^{1+\delta}}+\sum_{t=f(T)+1}^{T-1}\frac{1}{t^{\delta}(T-t)}\right)$
$\displaystyle\leq\ $
$\displaystyle\frac{K_{A}+K_{B}^{2}}{\epsilon^{2}B}\lim_{T\rightarrow\infty}\left(\sum_{t=f(T)+1}^{T-1}\frac{1}{t^{1+\delta}}+\sum_{t=f(T)+1}^{T-1}\frac{1}{t^{\delta}(T-t)}\right).$
(S8)

Since $f(T)=\lfloor T^{1/5}\rfloor$, we have
$\lim_{T\rightarrow\infty}\sum_{t=f(T)+1}^{T-1}t^{-1-\delta}=0.$ Applying
Lemma 3, we have

$0\leq\lim_{T\rightarrow\infty}\sum_{t=f(T)+1}^{T-1}\frac{1}{t^{\delta}(T-t)}\leq\lim_{T\rightarrow\infty}\sum_{t=1}^{T-1}\frac{1}{t^{\delta}(T-t)}=0.$

Therefore, as $T\rightarrow\infty$, the right-hand-side of Equation (S8) goes
to 0. Proof is complete. ∎

###  S3.5 Proof of Condition C5

###### Proof.

We will show that the final term $\zeta^{(3)}_{T}$ of Equation (S2) is
asymptotically normal. We first decompose the error of this term into two
parts:

$\displaystyle\zeta^{(3)}_{T}-\Delta(\hat{\pi}_{f(T)};\pi_{0})$
$\displaystyle=$
$\displaystyle\left(\sum_{t=1}^{f(T)}\sum_{j=f(T)+1}^{T}\frac{\widehat{\Gamma}_{tj}}{T-t}\right)-\Delta(\hat{\pi}_{f(T)};\pi_{0})$
$\displaystyle=$
$\displaystyle\sum_{j=f(T)+1}^{T}\left(\sum_{t=1}^{f(T)}\frac{\widehat{\Gamma}_{tj}}{T-t}\right)-\Delta(\hat{\pi}_{f(T)};\pi_{0})$
$\displaystyle=$
$\displaystyle\underbrace{\frac{1}{T-f(T)}\sum_{j=f(T)+1}^{T}\left[\left(\sum_{t=1}^{f(T)}\widehat{\Gamma}_{tj}\right)-\Delta(\hat{\pi}_{f(T)};\pi_{0})\right]}_{major\
part}+\underbrace{\sum_{j=f(T)+1}^{T}\sum_{t=1}^{f(T)}\left(\frac{1}{T-t}-\frac{1}{T-f(T)}\right)\widehat{\Gamma}_{tj}}_{minor\
part}$ (S9)

We will show that the major part in Equation (S9) is asymptotically normal
while the minor part is negligible after proper scaling. More concretely, we
will show:

$\displaystyle\sqrt{T}\cdot\frac{\frac{1}{T-f(T)}\sum_{j=f(T)+1}^{T}\left[\sum_{t=1}^{f(T)}\widehat{\Gamma}_{tj}-\Delta(\hat{\pi}_{f(T)};\pi_{0})\right]}{\xi(T)}$
$\displaystyle\stackrel{{\scriptstyle d}}{{\longrightarrow}}N(0,1).$ (S10)
$\displaystyle\sqrt{T}\cdot\frac{\sum_{j=f(T)+1}^{T}\sum_{t=1}^{f(T)}\left(\frac{1}{T-t}-\frac{1}{T-f(T)}\right)\widehat{\Gamma}_{tj}}{{\xi(T)}}$
$\displaystyle\stackrel{{\scriptstyle p}}{{\longrightarrow}}0$ (S11)

#### Proof of Equation (S10).

Notice that
$\left\\{\sum_{t=1}^{f(T)}\widehat{\Gamma}_{tj}\right\\}_{j=f(T)+1}^{T}$ are
i.i.d. random variables, conditional on $\mathcal{H}_{f(T)}$. We derive the
mean and variance of this conditional distribution:

$\displaystyle\mu(T)\ :=$
$\displaystyle\mathbb{E}\left[\sum_{t=1}^{f(T)}\widehat{\Gamma}_{tj}\mid\mathcal{H}_{f(T)}\right]$
$\displaystyle\ =$
$\displaystyle\mathbb{E}\left[\frac{1}{B}\sum_{i\in\mathcal{B}_{j}}\left(\frac{Y_{i}D_{i}}{e(\bm{X}_{i})}-\frac{Y_{i}(1-D_{i})}{1-e(\bm{X}_{i})}\right)\left(\hat{\pi}_{f(T)}(\bm{X}_{i})-\pi_{0}(\bm{X}_{i})\right)\
\biggr{|}\ \mathcal{H}_{f(T)}\right]$ $\displaystyle\ =$
$\displaystyle\mathbb{E}_{\bm{X}}\left[\tau(\bm{X})(\hat{\pi}_{f(T)}(\bm{X})-\pi_{0}(\bm{X}))\right]=\Delta(\hat{\pi}_{f(T)};\pi_{0}),$
$\displaystyle\mathbb{V}\left(\sum_{t=1}^{f(T)}\widehat{\Gamma}_{tj}\
\biggr{|}\ \mathcal{H}_{f(T)}\right)\ =$ $\displaystyle\xi(T)^{2}.$

Furthermore, we define $\rho(T)$ as:

$\rho(T):=\mathbb{E}\left[\left|\sum_{t=1}^{f(T)}\widehat{\Gamma}_{tj}-\mu(T)\right|^{3}\
\biggr{|}\ \mathcal{H}_{f(T)}\right],$

For any $T$, we can uniformly bound $\rho(T)$ as follows:

$\displaystyle\rho(T)\ =\ $
$\displaystyle\mathbb{E}\left[\left|\frac{1}{B}\sum_{i\in\mathcal{B}_{j}}\left(\frac{Y_{i}D_{i}}{e(\bm{X}_{i})}-\frac{Y_{i}(1-D_{i})}{1-e(\bm{X}_{i})}\right)\left(\hat{\pi}_{f(T)}(\bm{X}_{i})-\pi_{0}(\bm{X}_{i})\right)-\mu(T)\right|^{3}\
\biggr{|}\ \mathcal{H}_{f(T)}\right]$ $\displaystyle\leq\ $ $\displaystyle
8\mathbb{E}\left[\left|\frac{1}{B}\sum_{i\in\mathcal{B}_{j}}\left(\frac{Y_{i}D_{i}}{e(\bm{X}_{i})}-\frac{Y_{i}(1-D_{i})}{1-e(\bm{X}_{i})}\right)\left(\hat{\pi}_{f(T)}(\bm{X}_{i})-\pi_{0}(\bm{X}_{i})\right)\right|^{3}\
\biggr{|}\ \mathcal{H}_{f(T)}\right]$ (S12) $\displaystyle\leq\ $
$\displaystyle
8\mathbb{E}_{\bm{Z}}\left[\left|\left(\frac{YD}{e(\bm{X})}-\frac{Y(1-D)}{1-e(\bm{X})}\right)\left(\hat{\pi}_{f(T)}(\bm{X})-\pi_{0}(\bm{X})\right)\right|^{3}\right]$
$\displaystyle\leq\ $ $\displaystyle
8\mathbb{E}_{\mathbf{Z}}\left[\left|\frac{YD}{e(\bm{X})}-\frac{Y(1-D)}{1-e(\bm{X})}\right|^{3}\right]$
$\displaystyle\leq\ $ $\displaystyle
8\mathbb{E}\left[\left|\frac{1}{c}\\{|Y(0)^{\prime}|+|Y(1)^{\prime}|\\}\right|^{3}\right]$
(S13) $\displaystyle\leq\ $
$\displaystyle\frac{64}{c^{3}}\left(\mathbb{E}\left[|Y(0)^{\prime}|^{4}\right]^{3/4}+\mathbb{E}\left[|Y(1)^{\prime}|^{4}\right]^{3/4}\right)<\infty.$
(S14)

where Equation (S12) follows from the fact that for any random variable $X$,
we have:

$\mathbb{E}[|X-\mathbb{E}[X]|^{3}]=\mathbb{E}[(|X|+|\mathbb{E}[X]|)^{3}]\leq\mathbb{E}[(2|X|)^{3}]=\mathbb{E}[8|X|^{3}]$

Equation (S13) follows from the overlap assumption (Assumption 1), and
Equation (S14) utilizes the Norm inequality and the moment condition
(Assumption 5).

We characterize the behavior of the sample mean of
$\left\\{\sum_{t=1}^{f(T)}\widehat{\Gamma}_{tj}\right\\}_{j=f(T)+1}^{T}$,
conditional on the first ${f(T)}$ observations, i.e., $\mathcal{H}_{f(T)}$.
Specifically, denote $F_{T,\mathcal{H}_{f(T)}}$ as the conditional CDF of the
following random variable:

$\sqrt{T-f(T)}\cdot\frac{\frac{1}{T-f(T)}\sum_{j=f(T)+1}^{T}\left(\sum_{t=1}^{f(T)}\widehat{\Gamma}_{tj}-\mu(T)\right)}{\xi(T)},$
(S15)

given $\mathcal{H}_{f(T)}$. Then, by the Berry-Esseen Theorem, there exists a
positive constant $C$ such that the following inequality holds:

$\sup_{w}\left|F_{T,\mathcal{H}_{f(T)}}(w)-\Phi(w)\right|\leq\frac{C\cdot\rho(T)}{\xi(T)^{3}\cdot\sqrt{T-f(T)}}.$

where $\Phi(\cdot)$ is the CDF of the standard normal random variable. Since
by Condition C1, there exists $R_{3}>0$ such that for any $T\geq R_{3}$,
$\xi(T)^{2}\geq c_{0}^{2}$ almost surely. Also as $\rho(T)$ is uniformly
bounded, we have $\forall T\geq R_{3}$, there exists a positive constant
$c_{1}$ such that

$\sup_{w}\left|F_{T,\mathcal{H}_{f(T)}}(w)-\Phi(w)\right|\leq\frac{C\cdot\rho(T)}{\xi(T)^{3}\cdot\sqrt{T-f(T)}}\leq\frac{c_{1}}{\sqrt{T-f(T)}}\
\text{almost surely}.$

Denote $F_{T}$ as the (unconditional) CDF of the random variable given in
Equation (S15). Then, when $T\geq R_{3}$, we have:

$\displaystyle\sup_{w}|F_{T}(w)-\Phi(q)|$ $\displaystyle=\sup_{w}\left|\int
F_{T,\mathcal{H}_{f(T)}}(w)d\mathbb{P}(\mathcal{H}_{f(T)})-\Phi(w)\right|$
$\displaystyle\leq\sup_{w}\int\left|F_{T,\mathcal{H}_{f(T)}}(w)-\Phi(w)\right|d\mathbb{P}(\mathcal{H}_{f(T)})$
$\displaystyle\leq\frac{c_{1}}{\sqrt{T-f(T)}}\ \text{almost surely}.$

Since $f(T)=\lfloor T^{1/5}\rfloor$ implies
$\lim_{T\rightarrow\infty}T-f(T)=\infty$, we have,
$\lim_{T\rightarrow\infty}\sup_{w}|F_{T}(w)-\Phi(w)|=0$. Therefore,

$\sqrt{T-f(T)}\cdot\frac{\frac{1}{T-f(T)}\sum_{j=f(T)+1}^{T}\left(\sum_{t=1}^{f(T)}\widehat{\Gamma}_{tj}-\mu(T)\right)}{\xi(T)}\stackrel{{\scriptstyle
d}}{{\longrightarrow}}N(0,1).$

Since

$\lim_{T\rightarrow\infty}\frac{\sqrt{T}}{\sqrt{T-f(T)}}=\lim_{T\rightarrow\infty}\sqrt{\frac{T}{T-\lfloor
T^{1/5}\rfloor}}=1,$

we have proven Equation (S10).

#### Proof of Equation (S11).

By Condition C1, $\xi(T)$ is bounded from below. Therefore, it suffices to
show as $T\rightarrow\infty$,

$\displaystyle\sqrt{T}{\sum_{j=f(T)+1}^{T}\sum_{t=1}^{f(T)}\left(\frac{1}{T-t}-\frac{1}{T-f(T)}\right)\widehat{\Gamma}_{tj}}$
$\displaystyle\stackrel{{\scriptstyle p}}{{\longrightarrow}}0.$ (S16)

To show this, notice

$\displaystyle\left|\sum_{j=f(T)+1}^{T}\sum_{t=1}^{f(T)}\left(\frac{1}{T-t}-\frac{1}{T-f(T)}\right)\widehat{\Gamma}_{tj}\right|\
=$
$\displaystyle\left|\sum_{j=f(T)+1}^{T}\sum_{t=1}^{f(T)}\left(\frac{t-f(T)}{\\{T-f(T)\\}(T-t)}\right)\widehat{\Gamma}_{t,j}\right|$
$\displaystyle\ \leq$
$\displaystyle\sum_{j=f(T)+1}^{T}\sum_{t=1}^{f(T)}\left|\frac{t-f(T)}{\\{T-f(T)\\}(T-t)}\right|\cdot\left|\widehat{\Gamma}_{tj}\right|$
$\displaystyle\ \leq$
$\displaystyle\frac{f(T)}{\\{T-f(T)\\}^{2}}\sum_{j=f(T)+1}^{T}\sum_{t=1}^{f(T)}\biggr{|}\widehat{\Gamma}_{tj}\biggr{|}.$

By the definition of $\widehat{\Gamma}_{t,j}$ and the overlap assumption
(Assumption 1), we have:

$\displaystyle\biggr{|}\widehat{\Gamma}_{tj}\biggr{|}$
$\displaystyle=\frac{1}{B}\biggr{|}\sum_{i\in\mathcal{B}_{j}}\left(\frac{Y_{i}D_{i}}{e(\bm{X}_{i})}-\frac{Y_{i}(1-D_{i})}{1-e(\bm{X}_{i})}\right)\left(\hat{\pi}_{t}(\bm{X}_{i})-\hat{\pi}_{t-1}(\bm{X}_{i})\right)\biggr{|}$
$\displaystyle\leq\frac{1}{B}\biggr{|}\sum_{i\in\mathcal{B}_{j}}\left(\frac{Y_{i}D_{i}}{e(\bm{X}_{i})}-\frac{Y_{i}(1-D_{i})}{1-e(\bm{X}_{i})}\right)\biggr{|}$
$\displaystyle\leq\frac{2}{Bc}\sum_{i\in\mathcal{B}_{j}}|Y_{i}|,$

where $c$ is defined in Assumption 1. Putting all together:

$\left|\sum_{j=f(T)+1}^{T}\sum_{t=1}^{f(T)}\left(\frac{1}{T-t}-\frac{1}{T-f(T)}\right)\widehat{\Gamma}_{tj}\right|\leq\frac{2}{Bc}\cdot\frac{f(T)}{\\{T-f(T)\\}^{2}}\cdot
f(T)\sum_{j=f(T)+1}^{T}\sum_{i\in\mathcal{B}_{j}}|Y_{i}|.$

By Chebyshev’s inequality, for any $\epsilon>0$,

$\displaystyle\mathbb{P}\left(\sqrt{T}\left|\sum_{j=f(T)+1}^{T}\sum_{t=1}^{f(T)}\left(\frac{1}{T-t}-\frac{1}{T-f(T)}\right)\widehat{\Gamma}_{tj}\right|>\epsilon\right)$
$\displaystyle\leq$
$\displaystyle\frac{\sqrt{T}}{\epsilon}\mathbb{E}\left[\left|\sum_{j=f(T)+1}^{T}\sum_{t=1}^{f(T)}\left(\frac{1}{T-t}-\frac{1}{T-f(T)}\right)\widehat{\Gamma}_{tj}\right|\right]$
$\displaystyle\leq$
$\displaystyle\frac{2}{Bc\epsilon}\cdot\frac{\sqrt{T}f(T)^{2}}{\\{T-f(T)\\}^{2}}\mathbb{E}\left[\sum_{j=f(T)+1}^{T}\sum_{i\in\mathcal{B}_{j}}|Y_{i}|\right]$
$\displaystyle\leq$
$\displaystyle\frac{2}{c\epsilon}\cdot\frac{\sqrt{T}f(T)^{2}}{T-f(T)}\mathbb{E}\left[|Y|\right].$

Assumption 5 and Jensen’s inequality imply that there exists $K_{4}>0$ such
that
$\mathbb{E}\left[|Y|\right]\leq\sqrt[4]{\mathbb{E}\left[|Y|^{4}\right]}\leq
K_{4}^{1/4}<\infty$. Therefore, utilizing $f(T)=\lfloor T^{1/5}\rfloor$, we
have:

$\lim_{T\rightarrow\infty}\mathbb{P}\left(\sqrt{T}\left|\sum_{j=f(T)+1}^{T}\sum_{t=1}^{f(T)}\left(\frac{1}{T-t}-\frac{1}{T-f(T)}\right)\widehat{\Gamma}_{tj}\right|>\epsilon\right)\leq\frac{2B}{c\epsilon}\cdot\lim_{T\rightarrow\infty}\frac{T^{9/10}}{T-\lfloor
T^{1/5}\rfloor}=0.$

This completes proof.

∎

##  Appendix S4 Proof of Proposition 1

###### Proof.

Under Assumption 2, $\forall t\geq R_{1},j>0$, we have:

$\mathbb{E}_{\bm{X}}\left[|\hat{\pi}_{t+j}(\bm{X})-\hat{\pi}_{t}(\bm{X})|\right]\leq\sum_{k=1}^{j}\mathbb{E}_{\bm{X}}\left[|\hat{\pi}_{t+k}(\bm{X})-\hat{\pi}_{t+k-1}(\bm{X})|\right]\leq\sum_{k=1}^{j}\frac{K_{0}}{(t+k)^{1+\delta}}\
\ \text{almost surely}.$

Since

$\sum_{k=1}^{j}\frac{K_{0}}{(t+k)^{1+\delta}}\leq\sum_{k=1}^{\infty}\frac{K_{0}}{(t+k)^{1+\delta}},\quad\text{and}\quad\lim_{t\rightarrow\infty}\sum_{k=1}^{\infty}\frac{K_{0}}{(t+k)^{1+\delta}}=0,$

we have

$\displaystyle\lim_{t\rightarrow\infty}\sup_{j>0}\mathbb{E}_{\bm{X}}\left[|\hat{\pi}_{t+j}(\bm{X})-\hat{\pi}_{t}(\bm{X})|\right]=0\
\ \text{almost surely}.$

Therefore, with probability 1, the policy sequence
$\\{\hat{\pi}_{t}\\}_{t=1}^{\infty}$ is a Cauchy sequence in $L_{1}$ and has
an $L_{1}$ limit. ∎

##  Appendix S5 Proof of Theorem 3

###### Proof.

We first consider the case for any $0<h<1$,

$\displaystyle\left|\frac{T}{B}\sum_{j=2}^{T}\widehat{\mathbb{V}}(\hat{g}_{Tj})-v_{T}^{2}\right|$
$\displaystyle\ =$
$\displaystyle\left|\frac{T}{B}\sum_{j=2}^{T}\widehat{\mathbb{V}}(\hat{g}_{Tj})-\frac{T}{B}\sum_{j=2}^{T}\mathbb{V}_{\bm{Z}}(\hat{g}_{Tj}(\bm{Z}))\right|$
$\displaystyle\ \leq$ $\displaystyle\left|\frac{T}{B}\sum_{j=2}^{\lfloor
hT\rfloor}\widehat{\mathbb{V}}(\hat{g}_{Tj})-\frac{T}{B}\sum_{j=2}^{\lfloor
hT\rfloor}\mathbb{V}_{\bm{Z}}(\hat{g}_{Tj}(\bm{Z}))\right|+\frac{T}{B}\sum_{j=\lfloor
hT\rfloor+1}^{T}\mathbb{V}_{\bm{Z}}(\hat{g}_{Tj}(\bm{Z}))+\frac{T}{B}\sum_{j=\lfloor
hT\rfloor+1}^{T}\widehat{\mathbb{V}}(\hat{g}_{Tj}).$

Applying Lemma 7, we have:

$\frac{1}{B}\left|T\sum_{j=2}^{\lfloor
hT\rfloor}\widehat{\mathbb{V}}(\hat{g}_{Tj})-T\sum_{j=2}^{\lfloor
hT\rfloor}\mathbb{V}_{\bm{Z}}(\hat{g}_{Tj}(\bm{Z}))\right|\stackrel{{\scriptstyle
p}}{{\longrightarrow}}0.$

Moreover, Lemma 8 implies:

$\frac{T}{B}\sum_{j=\lfloor
hT\rfloor+1}^{T}{\mathbb{V}}_{\bm{Z}}(\hat{g}_{Tj}(\bm{Z}))\stackrel{{\scriptstyle
p}}{{\longrightarrow}}0,\quad\text{and}\quad\frac{T}{B}\sum_{j=\lfloor
hT\rfloor+1}^{T}\widehat{\mathbb{V}}(\hat{g}_{Tj})\stackrel{{\scriptstyle
p}}{{\longrightarrow}}0.$

Therefore, as $T\rightarrow\infty$, we have:

$\left|\frac{T}{B}\sum_{j=2}^{T}\widehat{\mathbb{V}}(\hat{g}_{Tj})-v_{T}^{2}\right|\stackrel{{\scriptstyle
p}}{{\longrightarrow}}0$

This completes proof. ∎

##  Appendix S6 Proof of Corollary 1

###### Proof.

Given Theorem 2, it suffices to show:

$\left|\frac{v_{T}}{\hat{v}_{T}}-1\right|\stackrel{{\scriptstyle
p}}{{\longrightarrow}}0.$

We begin by noting that $\forall\epsilon>0$,

$\mathbb{P}\left(\left|\frac{v_{T}}{\hat{v}_{T}}-1\right|>\epsilon\right)\ =\
\mathbb{P}\left(\left|{v_{T}}-{\hat{v}_{T}}\right|>\epsilon\hat{v}_{T}\right).$

Equation (S5) of the proof of Theorem 2 implies that there exists a constant
$c_{0}>0$ such that
$\lim_{T\rightarrow\infty}\mathbb{P}\left(v_{T}^{2}<c_{0}/2\right)=0$.
Therefore, we have:
$\lim_{T\rightarrow\infty}\mathbb{P}\left(|v_{T}|<\sqrt{c_{0}/2}\right)=0$.
Theorem 3, together with the Continuous Mapping Theorem, yields
$\left|\hat{v}_{T}-v_{T}\right|\stackrel{{\scriptstyle
p}}{{\longrightarrow}}0$. Therefore,

$\lim_{T\rightarrow\infty}\mathbb{P}\left(|\hat{v}_{T}|<\frac{1}{2}\sqrt{\frac{c_{0}}{2}}\right)\leq\lim_{T\rightarrow\infty}\mathbb{P}\left(|\hat{v}_{T}-v_{T}|>\frac{1}{2}\sqrt{\frac{c_{0}}{2}}\right)+\lim_{T\rightarrow\infty}\mathbb{P}\left(|v_{T}|<\sqrt{\frac{c_{0}}{2}}\right)=0.$

Finally, for all $\epsilon>0$,

$\displaystyle\mathbb{P}\left(\Bigr{|}{v_{T}}-{\hat{v}_{T}}\Bigr{|}>\epsilon\hat{v}_{T}\right)$
$\displaystyle\leq\mathbb{P}\left(|\hat{v}_{T}|\geq\frac{1}{2}\sqrt{\frac{c_{0}}{2}},\Bigr{|}{v_{T}}-{\hat{v}_{T}}\Bigr{|}>\frac{\epsilon}{2}\sqrt{\frac{c_{0}}{2}}\right)+\mathbb{P}\left(|v_{T}|<\frac{1}{2}\sqrt{\frac{c_{0}}{2}}\right)$
$\displaystyle\leq\mathbb{P}\left(\Bigr{|}{v_{T}}-{\hat{v}_{T}}\Bigr{|}>\frac{\epsilon}{2}\sqrt{\frac{c_{0}}{2}}\right)+\mathbb{P}\left(|v_{T}|<\frac{1}{2}\sqrt{\frac{c_{0}}{2}}\right),$

and the right-hand-side goes to 0 as $T\rightarrow\infty$. Therefore,

$\displaystyle\Bigr{|}\frac{v_{T}}{\hat{v}_{T}}-1\Bigr{|}\xrightarrow{p}0.$

∎

##  Appendix S7 Lemmas

###  S7.1 Lemma 1

###### Lemma 1

Under Assumption 2, as $t\rightarrow\infty$, we have, almost surely:

$\displaystyle\lim_{t\to\infty}t^{1+\delta/2}\mathbb{E}_{\bm{X}}\left[|\hat{\pi}_{t}(\bm{X})-\hat{\pi}_{t-1}(\bm{X})|\right]$
$\displaystyle\ =\ 0,$
$\displaystyle\lim_{t\to\infty}\mathbb{E}\left[t^{1+\delta/2}\mathbb{E}_{\bm{X}}\left[|\hat{\pi}_{t}(\bm{X})-\hat{\pi}_{t-1}(\bm{X})|\right]\right]$
$\displaystyle\ =\ 0,$

where $\delta$ is the same constant as the one given in Assumption 2.

###### Proof.

Assumption 2 implies that $\forall t\geq R_{1}$, $0\leq
t^{1+\delta/2}Q_{t}\leq K_{0}t^{-\delta/2}$ almost surely where
$Q_{t}=\mathbb{E}_{\bm{X}}\left[|\hat{\pi}_{t}(\bm{X})-\hat{\pi}_{t-1}(\bm{X})|\right]$.
Therefore, $\lim_{t\to\infty}t^{1+\delta/2}Q_{t}=0$ almost surely.
Furthermore, $\forall t>R_{1}$, $t^{1+\delta/2}Q_{t}\leq
K_{0}t^{-\delta/2}\leq K_{0}$ almost surely. Finally, the application of the
dominated convergence theorem implies
$\lim_{t\rightarrow\infty}\mathbb{E}\left[t^{1+\delta/2}Q_{t}\right]=0$ almost
surely.

∎

###  S7.2 Lemma 2

###### Lemma 2

Suppose Assumptions 2 and 3 hold. Then, there exists a constant $R_{2}$ such
that $\forall t\geq R_{2}$,

$\mathbb{E}_{\bm{X}}\left[|\hat{\pi}_{t}(\bm{X})-\pi_{0}(\bm{X})|\right]\geq\frac{M_{1}}{2}\
\ \text{almost surely},$

where $M_{1}$ is defined in Assumption 3.

###### Proof.

For any $t>0$, by the triangle inequality, we have:

$\mathbb{E}_{\bm{X}}\left[|\hat{\pi}_{t}(\bm{X})-\pi_{0}(\bm{X})|\right]\geq\mathbb{E}_{\bm{X}}\left[|\pi_{0}(\bm{X})-\hat{\pi}_{\infty}(\bm{X})|\right]-\mathbb{E}_{\bm{X}}\left[|\hat{\pi}_{t}(\bm{X})-\hat{\pi}_{\infty}(\bm{X})|\right].$

Then, Assumption 3 implies:

$\mathbb{E}_{\bm{X}}\left[|\hat{\pi}_{t}(\bm{X})-\pi_{0}(\bm{X})|\right]\geq
M_{1}-\mathbb{E}_{\bm{X}}\left[|\hat{\pi}_{t}(\bm{X})-\hat{\pi}_{\infty}(\bm{X})|\right]\
\ \text{almost surely}.$

Since $\hat{\pi}_{\infty}$ is defined as the $L_{1}$ limit of
$\\{\hat{\pi}_{t}\\}_{t=1}^{\infty}$,

$\mathbb{E}_{\bm{X}}\left[|\hat{\pi}_{t}(\bm{X})-\hat{\pi}_{\infty}(\bm{X})|\right]=\lim_{j\rightarrow\infty}\mathbb{E}_{\bm{X}}\left[|\hat{\pi}_{t}(\bm{X})-\hat{\pi}_{j}(\bm{X})|\right].$

Now, $\forall j\geq t$, we have:

$\mathbb{E}_{\bm{X}}\left[|\hat{\pi}_{t}(\bm{X})-\hat{\pi}_{j}(\bm{X})|\right]\
\leq\sum_{j=t+1}^{\infty}\mathbb{E}_{\bm{X}}\left[|\hat{\pi}_{j}(\bm{X})-\pi_{j-1}(\bm{X})|\right],$

which implies:

$\mathbb{E}_{\bm{X}}\left[|\hat{\pi}_{t}(\bm{X})-\hat{\pi}_{\infty}(\bm{X})|\right]\leq\sum_{j=t+1}^{\infty}\mathbb{E}_{\bm{X}}\left[|\hat{\pi}_{j}(\bm{X})-\pi_{j-1}(\bm{X})|\right].$

Therefore, for $t\geq R_{1}$, utilizing Assumption 2,

$\mathbb{E}_{\bm{X}}\left[|\hat{\pi}_{t}(\bm{X})-\hat{\pi}_{\infty}(\bm{X})|\right]\leq\sum_{j=t+1}^{\infty}\frac{K_{0}}{j^{1+\delta}}\
\ \text{almost surely}.$

Since the right-hand-side above monotonically goes to 0 as
$t\rightarrow\infty$, there must exist a constant $R_{2}$ such that
$R_{2}>R_{1}$ and when $t>R_{2}$,

$\sum_{j=t+1}^{\infty}\frac{K_{0}}{j^{1+\delta}}<\frac{M_{1}}{2}.$

Therefore, when $t>R_{2}$,

$\displaystyle\mathbb{E}_{\bm{X}}\left[|\hat{\pi}_{t}(\bm{X})-\pi_{0}(\bm{X})|\right]$
$\displaystyle\geq
M_{1}-\mathbb{E}_{\bm{X}}\left[|\hat{\pi}_{t}(\bm{X})-\hat{\pi}_{\infty}(\bm{X})|\right]\
\ \text{almost surely}$ $\displaystyle\geq
M_{1}-\frac{M_{1}}{2}=\frac{M_{1}}{2}\ \ \text{almost surely}$

∎

###  S7.3 Lemma 3

###### Lemma 3

Suppose that $\alpha$ is a positive constant. Then, we have:

$\displaystyle\lim_{T\rightarrow\infty}T\sum_{t=1}^{T-1}\frac{1}{t^{\alpha}(T-t)}$
$\displaystyle\ =\ \begin{cases}\sum_{t=1}^{\infty}t^{-\alpha},&\alpha>1\\\
\infty,&0<\alpha\leq 1.\end{cases}$
$\displaystyle\lim_{T\rightarrow\infty}\sum_{t=1}^{T-1}\frac{1}{t^{\alpha}(T-t)}$
$\displaystyle\ =\ 0,\ \ \forall\alpha>0$

###### Proof.

We consider three different scenarios; $\alpha=1$, $0<\alpha<1$, and
$1<\alpha$.

#### Case 1:

When $\alpha=1$, we have:

$\sum_{t=1}^{T-1}\frac{1}{t^{\alpha}(T-t)}=\sum_{t=1}^{T-1}\frac{1}{t(T-t)}=\frac{1}{T}\left(\sum_{t=1}^{T-1}\frac{1}{t}+\sum_{t=1}^{T-1}\frac{1}{T-t}\right)=\frac{1}{T}\sum_{t=1}^{T-1}\frac{2}{t}.$

This implies:

$\displaystyle\lim_{T\rightarrow\infty}T\sum_{t=1}^{T-1}\frac{1}{t^{\alpha}(T-t)}$
$\displaystyle=\lim_{T\rightarrow\infty}2\sum_{t=1}^{T-1}\frac{1}{t}=\infty,$
$\displaystyle\lim_{T\rightarrow\infty}\sum_{t=1}^{T-1}\frac{1}{t^{\alpha}(T-t)}$
$\displaystyle=\lim_{T\rightarrow\infty}\frac{2}{T}\sum_{t=1}^{T-1}\frac{1}{t}=0.$

#### Case 2:

When $0<\alpha<1$, we have:

$\sum_{t=1}^{T-1}\frac{1}{t^{\alpha}(T-t)}\geq\sum_{t=1}^{T-1}\frac{1}{t(T-t)}.$

This implies:

$\lim_{T\rightarrow\infty}T\sum_{t=1}^{T-1}\frac{1}{t^{\alpha}(T-t)}\geq\lim_{T\rightarrow\infty}T\sum_{t=1}^{T-1}\frac{1}{t(T-t)}=\infty.$

Next, using Hölder’s inequality, we obtain:

$\displaystyle\sum_{t=1}^{T-1}\frac{1}{t^{\alpha}(T-t)}$
$\displaystyle=\sum_{t=1}^{T-1}\frac{1}{t^{\alpha}(T-t)^{\alpha}}\cdot\frac{1}{(T-t)^{1-\alpha}}$
$\displaystyle\leq\left[\sum_{t=1}^{T-1}\left\\{t^{-\alpha}(T-t)^{-\alpha}\right\\}^{1/\alpha}\right]^{\alpha}\left[\sum_{t=1}^{T-1}\left((T-t)^{-1+\alpha}\right)^{1/(1-\alpha)}\right]^{1-\alpha}$
$\displaystyle\leq\left(\sum_{t=1}^{T-1}\frac{1}{t(T-t)}\right)^{\alpha}\left(\sum_{t=1}^{T-1}\frac{1}{T-t}\right)^{1-\alpha}$
$\displaystyle\leq\left(\frac{1}{T}\sum_{t=1}^{T-1}\frac{2}{t}\right)^{\alpha}\left(\sum_{t=1}^{T-1}\frac{1}{t}\right)^{1-\alpha}$
$\displaystyle=\frac{2^{\alpha}}{T^{\alpha}}\sum_{t=1}^{T-1}\frac{1}{t}.$

Therefore,

$0\leq\lim_{T\rightarrow\infty}\sum_{t=1}^{T-1}\frac{1}{t^{\alpha}(T-t)}\leq\lim_{T\rightarrow\infty}\frac{2^{\alpha}}{T^{\alpha}}\sum_{t=1}^{T-1}\frac{1}{t}=0.$

#### Case 3:

When $\alpha>1$, we have:

$\frac{1}{(T-t)t^{\alpha}}\ =\
\frac{1}{Tt^{\alpha}}+\frac{1}{T^{2}t^{\alpha-1}}+\cdots+\frac{1}{T^{\lfloor\alpha\rfloor}t^{1+\alpha-\lfloor\alpha\rfloor}}+\frac{1}{(T-t)T^{\lfloor\alpha\rfloor}t^{\alpha-\lfloor\alpha\rfloor}},$

where $\lfloor x\rfloor$ denotes the greatest integer that is no greater than
$x$. Therefore,

$\sum_{t=1}^{T-1}\frac{1}{(T-t)t^{\alpha}}=\frac{1}{T}\sum_{t=1}^{T-1}\frac{1}{t^{\alpha}}+\sum_{k=1}^{\lfloor\alpha\rfloor-1}\sum_{t=1}^{T-1}\frac{1}{T^{k+1}t^{\alpha-k}}+\frac{1}{T^{\lfloor\alpha\rfloor}}\sum_{t=1}^{T-1}\frac{1}{(T-t)t^{\alpha-\lfloor\alpha\rfloor}}.$

This implies:

$T\sum_{t=1}^{T-1}\frac{1}{(T-t)t^{\alpha}}=\sum_{t=1}^{T-1}t^{-\alpha}+\sum_{k=1}^{[\alpha]-1}\sum_{t=1}^{T-1}\frac{t^{-\alpha+k}}{T^{k}}+\frac{1}{T^{[\alpha]-1}}\sum_{t=1}^{T-1}\frac{1}{(T-t)t^{\alpha-[\alpha]}}.$

For the first term, since $\alpha>0$, we have:

$\lim_{T\rightarrow\infty}\sum_{t=1}^{T-1}\frac{1}{t^{\alpha}}\ =\
\sum_{t=1}^{\infty}\frac{1}{t^{\alpha}}.$

For the second term, $1\leq k\leq[\alpha]-1$ implies $0\leq t^{-\alpha+k}\leq\
t^{-\alpha+[\alpha]-1}\leq t^{-1}$. Using this inequality, we obtain:

$0\leq\frac{t^{-\alpha+k}}{T^{k}}\leq\ \frac{1}{tT^{k}}\leq\frac{1}{tT}.$

Therefore,

$0\leq\sum_{k=1}^{[\alpha]-1}\sum_{t=1}^{T-1}\frac{t^{-\alpha+k}}{T^{k}}\leq([\alpha]-1)\sum_{t=1}^{T-1}\frac{1}{tT},$

which implies:

$0\leq\lim_{T\rightarrow\infty}\sum_{k=1}^{[\alpha]-1}\sum_{t=1}^{T-1}\frac{t^{-\alpha+k}}{T^{k}}\leq([\alpha]-1)\lim_{T\rightarrow\infty}\sum_{t=1}^{T-1}\frac{1}{tT}=0.$

For the last term, if $\alpha$ is an integer, we must have $\alpha\geq 2$
because $\alpha>1$. Therefore,

$\lim_{T\rightarrow\infty}\frac{1}{T^{[\alpha]-1}}\sum_{t=1}^{T-1}\frac{1}{(T-t)t^{\alpha-[\alpha]}}=\lim_{T\rightarrow\infty}\frac{1}{T^{\alpha-1}}\sum_{t=1}^{T-1}\frac{1}{(T-t)}=0.$

If $\alpha$ is not an integer, then $0<\alpha-[\alpha]<1$. Applying the result
from Case 2 above, we have:

$0\leq\lim_{T\rightarrow\infty}\frac{1}{T^{[\alpha]-1}}\sum_{t=1}^{T-1}\frac{1}{(T-t)t^{\alpha-[\alpha]}}\leq\lim_{T\rightarrow\infty}\sum_{t=1}^{T-1}\frac{1}{(T-t)t^{\alpha-[\alpha]}}=0.$

Putting all together, when $\alpha>1$, we have:

$\displaystyle\lim_{T\rightarrow\infty}T\sum_{t=1}^{T-1}\frac{1}{(T-t)t^{\alpha}}$
$\displaystyle=\lim_{T\rightarrow\infty}\left(\sum_{t=1}^{T-1}\frac{1}{t^{\alpha}}+\sum_{k=1}^{[\alpha]-1}\sum_{t=1}^{T-1}\frac{t^{-\alpha+k}}{T^{k}}+\frac{1}{T^{[\alpha]-1}}\sum_{t=1}^{T-1}\frac{1}{(T-t)t^{\alpha-[\alpha]}}\right)$
$\displaystyle=\sum_{t=1}^{\infty}\frac{1}{t^{\alpha}}+0+0$
$\displaystyle=\sum_{t=1}^{\infty}\frac{1}{t^{\alpha}}\ <\ \infty$

This directly implies:

$\lim_{T\rightarrow\infty}\sum_{t=1}^{T-1}\frac{1}{(T-t)t^{\alpha}}=0.$

∎

###  S7.4 Lemma 4

###### Lemma 4

Suppose $a_{0},a_{1},...,a_{T}$ is a sequence of real numbers in $[0,1]$, then
$\forall 1\leq t_{1}\leq t_{2}\leq T-1$,

$-\frac{1}{T-t_{2}}\leq\sum_{t=t_{1}}^{t_{2}}\frac{a_{t}-a_{t-1}}{T-t}\leq\frac{1}{T-t_{2}}.$

As a special case, if we have a sequence of policies
$\pi_{0},\hat{\pi}_{1},...,\hat{\pi}_{T}$, then $\forall 1\leq t_{1}\leq
t_{2}\leq T-1,\forall\bm{x}\in\mathcal{X}$,

$-\frac{1}{T-t_{2}}\leq\sum_{t=t_{1}}^{t_{2}}\frac{\hat{\pi}_{t}(\bm{x})-\hat{\pi}_{t-1}(\bm{x})}{T-t}\leq\frac{1}{T-t_{2}}.$

###### Proof.

We begin by noting:

$\displaystyle\sum_{t=t_{1}}^{t_{2}}\frac{a_{t}-a_{t-1}}{T-t}$
$\displaystyle=\sum_{t=t_{1}}^{t_{2}}\frac{a_{t}}{T-t}-\sum_{t=t_{1}}^{t_{2}}\frac{a_{t-1}}{T-t}$
$\displaystyle=\sum_{t=t_{1}}^{t_{2}}\frac{a_{t}}{T-t}-\sum_{t=t_{1}-1}^{t_{2}-1}\frac{a_{t}}{T-t-1}$
$\displaystyle=\frac{a_{t_{2}}}{T-t_{2}}+\sum_{t=t_{1}}^{t_{2}-1}\left(\frac{a_{t}}{T-t}-\frac{a_{t}}{T-t-1}\right)-\frac{a_{t_{1}-1}}{T-t_{1}}$
$\displaystyle=\frac{a_{t_{2}}}{T-t_{2}}-\sum_{t=t_{1}}^{t_{2}-1}\frac{a_{t}}{(T-t)(T-t-1)}-\frac{a_{t_{1}-1}}{T-t_{1}}.$

Since $a_{t}\in[0,1]$ for all $t\geq 0$, and all the denominators in the above
expression are positive,

$\frac{a_{t_{2}}}{T-t_{2}}-\sum_{t=t_{1}}^{t_{2}-1}\frac{a_{t}}{(T-t)(T-t-1)}-\frac{a_{t_{1}-1}}{T-t_{1}}\leq\frac{1}{T-t_{2}},$

where the equality holds when $a_{t_{2}}=1$ and all others are 0\. Similarly,

$\frac{a_{t_{2}}}{T-t_{2}}-\sum_{t=t_{1}}^{t_{2}-1}\frac{a_{t}}{(T-t)(T-t-1)}-\frac{a_{t_{1}-1}}{T-t_{1}}\geq-\sum_{t=t_{1}}^{t_{2}-1}\frac{1}{(T-t)(T-t-1)}-\frac{1}{T-t_{1}}\geq-\frac{1}{T-t_{2}},$

where the equality holds when $a_{t_{1}-1}=0$ and all others are 1\.
Therefore, we obtain the desired result.

∎

###  S7.5 Lemma 5

###### Lemma 5

Suppose that Assumptions 1, 2, 4 and 5 hold. Define:

$\displaystyle A_{t_{1}t_{2}}$