# Sample size planning for conditional counterfactual mean estimation with a
K-armed randomized experiment

Gabriel Ruiz
Adobe Inc.
San Jose, CA, U.S.A.
garuiz<EMAIL_ADDRESS>

###### Abstract

We cover how to determine a sufficiently large sample size for a $K$-armed
randomized experiment in order to estimate conditional counterfactual
expectations in data-driven subgroups. The sub-groups can be output by any
feature space partitioning algorithm, including as defined by binning users
having similar predictive scores or as defined by a learned policy tree. After
carefully specifying the inference target, a minimum confidence level, and a
maximum margin of error, the key is to turn the original goal into a
simultaneous inference problem where the recommended sample size to offset an
increased possibility of estimation error is directly related to the number of
inferences to be conducted. Given a fixed sample size budget, our result
allows us to invert the question to one about the feasible number of treatment
arms or partition complexity (e.g. number of decision tree leaves). Using
policy trees to learn sub-groups, we evaluate our nominal guarantees on a
large publicly-available randomized experiment test data set.

###### Contents

  1. 1 Introduction
    1. 1.1 Feature space partitioning model for conditional counterfactual means
      1. 1.1.1 A manageable inference target in practice
  2. 2 Main result
    1. 2.1 Some regularity conditions
    2. 2.2 The main result
      1. 2.2.1 Applying Propositions 2.1, A.1, and A.2 with a standardized scale
    3. 2.3 Learning a feature space partition
    4. 2.4 Given a fixed sample size
    5. 2.5 Bounding the Outcome’s conditional variance
  3. 3 Emprical Evaluation
  4. 4 Discussion and Limitations
  5. 5 Acknowledgements
  6. A Extended Main Results
  7. B Proofs
    1. B.1 Proof of Lemma 2.1
    2. B.2 Proof of Propositions 2.1, A.1, and A.2
    3. B.3 Proof of Equation ()
    4. B.4 Additional Lemmas

##  1 Introduction

Figure 1: Example power analysis showing a sufficient sample size needed for
jointly inferring the expected potential outcome in 3 treatment arms for a new
randomly sampled individual. Here, individuals can fall into one of the sub-
groups defined by a partition of the feature space given by an arbitrary
decision tree. In addition to the number of sub-groups, the sample size is
determined by a desired confidence level, margin of error, and unexplained
outcome variation (or standard deviation).

Randomized experiments (REs) are, in some sense, the gold standard for
establishing causality. Although external validity is not guaranteed (Lei et
al.,, 2023), REs are a good starting point when they can be conducted. To this
end, we consider the problem of sample size planning when we would like to
contrast $K$ treatment groups. Noting the realistic possibility that the
potential outcomes across possible treatments for one individual need not be
similar to the potential outcomes of another individual, we consider sample
size planning in the context of conditional counterfactual means, where the
conditioning is with respect to baseline features.

We note that reasoning about treatment effects at an individual-level is
difficult, if not impossible (Vegetabile,, 2021), even with an infinitely
sized sample. For example, see Ruiz and Padilla, (2022) for the limited
statistical inference that is possible on the distribution of individual
treatment effects. For a goal that is more immediately within reach, we turn
our sample size planning problem into one that attempts to study
counterfactuals based on their average at the sub-group-level, such as defined
by, but not limited to, a causal regression tree (Athey and Imbens,, 2016) or
a policy tree (Athey and Wager,, 2021; Sverdrup et al.,, 2020). We work under
the flexibility that the sub-groups can be learned by any machine learning
model that partitions the space of baseline co-variates, or features, into
disjoint subsets. We illustrate an example partition of the feature space
using a policy tree (Athey and Wager,, 2021; Sverdrup et al.,, 2020) in
Section 3.

In determining a sufficient sample size, we require a desired margin of error,
frequentist confidence-level, model complexity–the number of subsets in the
partition, and plausible bounds on outcome variation. In practice, this can be
tuned to comply with realistic sample size constraints. Once these parameters
are specified, the sufficient sample size needed requires that we enforce a
minimum sample size constraint in each subset for each treatment group. To
attain nominal guarantees with such a partition, we require honest prediction
(Athey and Imbens,, 2016; Athey et al.,, 2019) wherein outcomes for a holdout
set in the training data are omitted from the partition splitting rules to be
learned.

The key in our sample size planning is that in reasoning about the effect of
$K$ treatments across such a partition, we are conducting a simultaneous
inference of means. Given that mistakes are more likely with an increased
number of simultaneous inferences, a sufficient sample size is needed to
ensure a desired accuracy. We formalize the amount that is sufficient in
Propositions 2.1, A.1, and A.2.

In the remainder of this section, we introduce our estimator and its super-
population analogue. In section 2, we discuss the ”high confidence” inference
guarantee we are after, assumptions, and the main result that allows us to
determine sample size as in the example shown in Figure 1. Given a fixed
sample size budget, we discuss in § 2.4 how our result allows us to invert the
question to one about the feasible number of treatment arms or partition
complexity (e.g. number of decision tree leaves). Next, Section 3 empirically
evaluates whether our main result holds using a semi-synthetic simulation from
a large publicly available a/b test. Finally, Section 4 concludes with a
discussion of limitations and possible extensions.

###  1.1 Feature space partitioning model for conditional counterfactual means

Suppose we have treatments $w=1,\dots,K$ we would like to contrast. We have
data of baseline covariates, treatment exposure, and outcome tuples
$\\{(X_{i},W_{i},Y_{i})\\}_{i=1}^{n}$ with which we would like to approximate
the non-trivial conditional counterfactual mean function,

$\mu^{*}(x,w)\ =\ \mathbb{E}\left[Y_{i}(w)\middle|X_{i}=x\right].$

Additionally, it can be of interest to study the pair-wise differences of
these means, known as the conditional average treatment effect (CATE)
function:

$\tau^{*}(x,w,w^{\prime})\ =\
\mathbb{E}\left[Y_{i}(w)-Y_{i}(w^{\prime})\middle|X_{i}=x\right];\
w,w^{\prime}\in\\{1,\dots,K\\}.$

Here, $\left\\{Y_{i}(w),Y_{i}(w^{\prime})\right\\}$ are known as potential
outcomes (Rosenbaum and Rubin,, 1983; Imbens and Rubin,, 2015), and
equivalently as counterfactuals (Pearl,, 2000; Hernan and Robins,, 2023).
These represent individual $i$’s hypothetical outcomes when we force,
typically in a randomized experiment, the exposure variable $W_{i}$ to be $w$
or $w^{\prime}$.

Suppose we partition the feature space into $L\geq 1$ subsets

$\mathcal{X}_{1},\dots,\mathcal{X}_{L}\ \subset\ \mathcal{X}.$

Denote:

$\ell:\ \mathcal{X}\to\\{1,\dots,L\\}$

as the mapping that assigns $\ell(x)=l$ if $x\in\mathcal{X}_{l}$. We will call
$l=1,\dots,L$ a leaf, as it is helpful to think of the partition of
$\mathcal{X}$ as arising from a decision tree (Breiman et al.,, 2017). Denote
the prediction indices in group $w=1,\dots,K$ in leaf $l=1,\dots,L$ as

$\mathcal{I}(w,l)=\left\\{i\in\mathcal{S}:\
W_{i}=w,\ell(X_{i})=l\right\\}\subset\\{1,\dots,n\\},$

and let its sample size be denoted by

$n_{wl}=\left|\mathcal{I}(w,l)\right|.$

Here, $\mathcal{S}\subset\\{1,\dots,n\\}$ denotes the holdouts for honest
prediction (Athey and Imbens,, 2016; Athey et al.,, 2019).

Making use of the partition of the feature space, suppose our approximation of
$\mu^{*}(x,w)$ is given by

$\hat{\mu}(x,w)\mapsto\frac{1}{n_{w\ell(x)}}\sum_{i\in\mathcal{I}(w,\ell(x))}Y_{i},$

the sample mean outcome in treatment group $w$ and leaf $\ell(x)$. Meanwhile,
the approximation to $\tau^{*}(x,w,w^{\prime})$, denoted as
$\hat{\tau}(x,w,w^{\prime})$, is given by:

$(x,w,w^{\prime})\mapsto\hat{\mu}(x,w)-\hat{\mu}(x,w^{\prime}),$

an estimator that is in strong analogy to, but which the partition mapping
$\ell(x)$ need not be limited to, the causal decision trees of Athey and
Imbens, (2016).

####  1.1.1 A manageable inference target in practice

Let $(X_{n+1},W_{n+1},Y_{n+1})$ be a new independent draw such that

$\displaystyle Y_{n+1}\mid W_{n+1}=w,\ell(X_{n+1})=\ell(x)$
$\displaystyle\overset{i.i.d.}{\sim}$ $\displaystyle\ Y_{i}\mid
W_{i}=w,\ell(X_{i})=\ell(x);\ i=1,\dots,n.$

While we mean to approximate the population-level quantity $\mu^{*}(x,w)$, the
population-analogue of $\hat{\mu}(x,w)$ is actually

$\mu(x,w)=\mathbb{E}\left[Y_{n+1}\middle|W_{n+1}=w,\ell(X_{n+1})=\ell(x)\right].$

This will be the target of our inference.

Note that $\mathcal{I}(w,l)$ is random because the tuples $(X_{i},W_{i})$ it
is based on are random. Conditional on $\mathcal{I}(w,\ell(x))$, we have that
$\hat{\mu}(x,w)$ is unbiased for $\mu(x,w)$ by its construction:

$\displaystyle\mathbb{E}\left[\hat{\mu}(x,w)\middle|\mathcal{I}(w,\ell(x))\right]$
$\displaystyle=$
$\displaystyle\frac{1}{n_{w\ell(x)}}\sum_{i\in\mathcal{I}(x,w)}\mathbb{E}\left[Y_{i}\middle|W_{i}=w,\ell(X_{i})=\ell(x),\mathcal{I}(w,\ell(x))\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}\left[Y_{n+1}\middle|W_{n+1}=w,\ell(X_{n+1})=\ell(x)\right].$

The estimator $\hat{\mu}(x,w)$ is also unbiased for the conditional mean of an
individual’s counterfactual outcome

$\mathbb{E}\left[Y_{n+1}(w)\middle|\ell(X_{n+1})=\ell(x)\right],$

provided the balancing score condition

$\\{Y_{n+1}(w),Y_{n+1}(w^{\prime})\\}\perp\\!\\!\\!\perp
W_{n+1}|\ell(X_{n+1})=\ell(x)$

holds (Rosenbaum and Rubin,, 1983; Imbens,, 2004; Imbens and Rubin,, 2015;
D’Amour et al.,, 2021; Hernan and Robins,, 2023). This condition holds in a
randomized experiment setting when $X_{i}$ are pre-treatment features that are
independent of treatment assignment. Importantly, this balancing condition
with respect to the discrete partition mapping $\ell(x)$ need not hold outside
of the experimental setting.

We similarly have that conditional on $\mathcal{I}(w,\ell(x))$ and
$\mathcal{I}(w^{\prime},\ell(x))$, $\hat{\tau}(x,w,w^{\prime})$ is unbiased
for

$\tau(x,w,w^{\prime})\ :=\ \mu(x,w)-\mu(x,w^{\prime}).$

The goal of our work will be to ensure the sets $\mathcal{I}(w,l)$ across
$(w,l)\in\left\\{1,\dots,K\right\\}\times\left\\{1,\dots,L\right\\}$ have
sufficient indices to provide a desired high-confidence accuracy guarantee on
$\mu(x,w)$. In addition to accurate inference on $\tau(x,w,w^{\prime})$, we
show such a guarantee also implies accurate inference on the best outcome
across treatment arms, on average, in leaf $\ell(x)$: $\max_{w}\mu(x,w)$. We
infer the latter quantity using its empirical analogue:
$\max_{w}\hat{\mu}(x,w)$.

##  2 Main result

We have the following key lemma before stating our main result. In it, denote

$\mathcal{I}=\left\\{\mathcal{I}(w,l):\
(w,l)\in\left\\{1,\dots,K\right\\}\times\left\\{1,\dots,L\right\\}\right\\}$

as the partition of the honest set indices $\mathcal{S}$ into the mutually
disjoint subsets.

######  Lemma 2.1 (Implications of accurate conditional counterfactual mean
estimation).

Let $\alpha\in(0,1)$ and $\epsilon>0$. Consider a new random test point
$X_{n+1}$.
If

$\text{Pr}\left(\max_{w}\left|\hat{\mu}(X_{n+1},w)-\mu(X_{n+1},w)\right|<\epsilon\
\middle|\ \mathcal{I}\right)\\\ \geq\ 1-\alpha,$ (1)

then

$\displaystyle\text{Pr}\left(\left|\max_{w}\hat{\mu}(X_{n+1},w)-\max_{w}\mu(X_{n+1},w)\right|<\epsilon\
\middle|\ \mathcal{I}\right)$ $\displaystyle\geq$ $\displaystyle 1-\alpha$ (2)

along with

$\displaystyle\text{Pr}\left(\max_{w\neq
w^{\prime}}\left|\hat{\tau}(X_{n+1},w,w^{\prime})-\tau(X_{n+1},w,w^{\prime})\right|<2\epsilon\
\middle|\ \mathcal{I}\right)$ $\displaystyle\geq$ $\displaystyle 1-\alpha.$
(3)

Moreover, if

$\text{Pr}\left(\sup_{x}\max_{w}\left|\hat{\mu}(x,w)-\mu(x,w)\right|<\epsilon\
\middle|\ \mathcal{I}\right)\\\ \geq\ 1-\alpha,$ (4)

then

$\displaystyle\text{Pr}\left(\sup_{x}\left|\max_{w}\hat{\mu}(x,w)-\max_{w}\mu(x,w)\right|<\epsilon\
\middle|\ \mathcal{I}\right)$ $\displaystyle\geq$ $\displaystyle 1-\alpha$ (5)

along with

$\displaystyle\text{Pr}\left(\sup_{x}\max_{w\neq
w^{\prime}}\left|\hat{\tau}(x,w,w^{\prime})-\tau(x,w,w^{\prime})\right|<2\epsilon\
\middle|\ \mathcal{I}\right)$ $\displaystyle\geq$ $\displaystyle 1-\alpha.$
(6)

Lemma 2.1 is saying that an $(\epsilon,\alpha)$ estimation guarantee for each
conditional counterfactual mean $\mu(w,\cdot)$, whether at a random point
$X_{n+1}$ or uniformly across $x$, implies an $(\epsilon,\alpha)$ estimation
guarantee on the best (largest) conditional counterfactual treatment mean.
Similarly, accurate estimation of the conditional counterfactual mean
$\mu(w,\cdot)$ implies a $(2\epsilon,\alpha)$ guarantee for our estimation of
the treatment effect function $\tau(\cdot,w,w^{\prime})$.

The proof of Lemma 2.1 is contained in Appendix B. The general idea in the
proof is to use a law of total probability decomposition for the probabilities
in (2) and (3) involving the maximal deviation

$\max_{w}\left|\hat{\mu}(X_{n+1},w)-\mu(X_{n+1},w)\right|.$

We follow similar steps for the inequalities in (5) and (6).

Given Lemma 2.1, the goal is now to understand the sufficient sample size
required per treatment group, per subset of the partition that grants us the
premise in either Equation (1) or (4). Propositions 2.1, A.1, and A.2 give us
this understanding.

###  2.1 Some regularity conditions

The required sample size depends on our assumption about the data generating
mechanism. Some representative assumptions include the following.

######  Assumption 2.1 (Bounded Outcome).

For known constants $a<b$, suppose that $\text{Pr}\left(a\leq Y_{i}\leq
b\right)=1$.

######  Assumption 2.2 (Known bound on the conditional variance).

Let $\sigma^{2}>0$ be a known constant. Across $w=1,\dots,K$ and
$l=1,\dots,L$, suppose that

$\sigma^{2}_{wl}:={\rm Var}\left[Y_{n+1}\mid
W_{n+1}=w,\ell(X_{n+1})=l\right]\leq\sigma^{2}.$

######  Assumption 2.3 (Central Limit Theorem).

Across $w=1,\dots,K$ and $x\in\mathcal{X}$, suppose that

$\hat{\mu}(x,w)\sim{\rm
Normal}\left(\mu(x,w),\sigma^{2}_{w\ell(x)}/n_{wl}\right).$

Section 2.5 discusses strategies for obtaining a bound on the conditional
variance. When bounds on the conditional variance are unknown, Remark 2.1
below discusses how one can proceed with inference on a standardized scale.

###  2.2 The main result

######  Proposition 2.1 (Main Result: Central Limit Theorem).

Suppose Assumptions 2.2 and 2.3 hold.

  * •

Then for the guarantee in (1) to hold, it is sufficient that

$\min_{w,l}n_{wl}\ \geq\
\left(\frac{\Phi^{-1}\left((1-\alpha)^{\frac{1}{K}}\right)\times\sigma}{\epsilon}\right)^{2}$
(7)

with $\Phi^{-1}$ the inverse Cumulative Distrubiton Function (CDF) of the
standard Normal distribution.

  * •

Then for the guarantee in (4) to hold, it is sufficient that

$\min_{w,l}n_{wl}\ \geq\
\left(\frac{\Phi^{-1}\left((1-\alpha)^{\frac{1}{KL}}\right)\times\sigma}{\epsilon}\right)^{2}.$
(8)

Using Proposition 2.1, Figure 1 plots the sufficient sample size as

$n\ =\ K\times
L\times\frac{\left(\frac{\Phi^{-1}\left((1-\alpha)^{\frac{1}{K}}\right)\times\sigma}{\epsilon}\right)^{2}}{\left|\mathcal{S}\right|/n}$

with the constraint that we use half the sample for honest prediction, i.e.
$\left|\mathcal{S}\right|/n=0.5$. We include the example choices
$\sigma\in\left\\{0.5,1\right\\}$, $\epsilon\in\left\\{0.01,0.1\right\\}$,
$L\in\left\\{16,512\right\\}$, and varying confidence levels $(1-\alpha)\times
100\%$.

In the appendix, we include Propositions A.1 and A.2. The former works under
Assumption A.1, while the latter works under Assumptions A.1 and A.2. These
correspond to a more conservative alternative to Assumption 2.3 (Rosenblum and
van der Laan,, 2009).

The proof of Propositions 2.1, A.1, and A.2 is found in Appendix B.2. It is an
application of Lemma B.2, which estimates the means of $K$ groups based on
independent data, across $L$ disjoint clusters. Conditional on the partition
$\mathcal{I}$, the setting of Propositions 2.1, A.1, and A.2 fits this mould.
The exact sufficient sample size per tree per treatment group in each
guarantee is given by the normality assumption, Hoeffding’s inequality, and
Bennett’s inequality, respectively (Wainwright,, 2019; Bennett,, 1962;
Rosenblum and van der Laan,, 2009).

Moreover, the statements in Propositions 2.1, A.1, and A.2 with respect to a
random new input $X_{n+1}$ do not assume anything about the discrete
distribution of the random variable $\ell(X_{n+1})$. This discrete
distribution can be spiked, slabbed, skewed, or anything else111Inserting
prior knowledge on, and constraining the posterior distribution of, this
distribution could be an interesting future direction.. The minimum sample
size guarantees the nominal coverage, regardless. At the stage of sample size
planning, this guard seems ideal as we may not have a good intuition for how a
learned partition will distribute the Multinoulli label $\ell(X_{n+1})$.

####  2.2.1 Applying Propositions 2.1, A.1, and A.2 with a standardized scale

In Section 2.5, we discuss how to obtain the bound on the conditional
variance, $\sigma^{2}$ to satisfy Assumption 2.2. In case we do not have
enough domain knowledge to obtain $\sigma^{2}$, we now discuss the consequence
of applying Propositions 2.1, A.1, and A.2 and Lemma 2.1 with the
specification $\sigma^{2}=1$. Remark 2.1 explains that this specification
turns our inference into one with a margin of error defined by a factor
$\epsilon$ times an amount relating to the true conditional standard
deviations.

Consider the outcome standardization

$Z_{iwl}\ :=\ \frac{Y_{i}}{\sigma_{wl}};\ i=1,\dots,n+1.$

With $Z_{iwl}$, we have the following standardized oracle estimator

$\hat{\mu}_{*}(x,w)\ =\
\frac{1}{n_{w\ell(x)}}\sum_{i\in\mathcal{I}(w,\ell(x))}Z_{iw\ell(x)}\ =\
\frac{\hat{\mu}(x,w)}{\sigma_{w\ell(x)}}$

for

$\mu_{*}(x,w)\ =\
\mathbb{E}\left[Z_{(n+1)wl}\middle|W_{n+1}=w,\ell(X_{n+1})=\ell(x)\right]\ =\
\frac{\mu(x,w)}{\sigma_{w\ell(x)}}.$

Noting that ${\rm Var}\left[Z_{iwl}\mid
W_{i}=w,\ell(X_{i})=l,\mathcal{I}\right]=1$, we have the following result with
respect to our actual quantity of interest.

######  Remark 2.1 (Working on a standardized scale).

To determine the sufficient sample size, we can apply Propositions 2.1, A.1,
and A.2 with respect to $\hat{\mu}_{*}(w,\cdot)$ and $\sigma\ \dot{=}\ 1$. The
practical interpretation thanks to Lemma 2.1 turns into:

  1. 1.

$\left|\hat{\mu}(X_{n+1},w)-\mu(X_{n+1},w)\right|<\epsilon\sigma_{w\ell(X_{n+1})}$
jointly for $w=1,\dots,K$ with probability $1-\alpha$;

  2. 2.

$\left|\max_{w}\hat{\mu}(X_{n+1},w)-\max_{w}\mu(X_{n+1},w)\right|<\epsilon\max_{w}\sigma_{w\ell(X_{n+1})}$
with probability $1-\alpha$;

  3. 3.

$\left|\hat{\tau}(X_{n+1},w,w^{\prime})-\tau(X_{n+1},w,w^{\prime})\right|<\epsilon\left(\sigma_{w\ell(X_{n+1})}+\sigma_{w^{\prime}\ell(X_{n+1})}\right)$
for each $w,w^{\prime}$ with probability $1-\alpha$

provided that the pertinent sample size constraint in Propositions 2.1, A.1,
and A.2 holds with $\sigma=1$. We have the analogous statements with respect
to the guarantees uniformly across $x$ .

Figure 1 with $\sigma=1$ depicts the sufficient sample sizes for Remark 2.1
with the choice $\epsilon\in\left\\{0.01,0.1\right\\}$.

###  2.3 Learning a feature space partition

The partition

$\mathcal{X}_{1},\dots,\mathcal{X}_{L}\ \subset\ \mathcal{X}.$

can be given by a decision tree (Breiman et al.,, 2017; Athey et al.,, 2019;
Athey and Wager,, 2021; Sverdrup et al.,, 2020), uniform mass binning
(Zadrozny and Elkan,, 2002; Gupta and Ramdas,, 2021), or other space
partitioning approach of interest. So long as the outcomes for prediction,
$(Y_{i};\ i\in\mathcal{S})$, stay independent of the learned partition split
points conditionally on their treatment designation and co-variates,
$((W_{i},X_{i});\ i\in\mathcal{S})$, our result is technically “model-free”
among possible approaches to discretize $\mathcal{X}$. We illustrate an
example partition of the feature space using a policy tree (Athey and Wager,,
2021; Sverdrup et al.,, 2020) in Section 3.

Of course, the exact partitioning approach will contribute to whether the
treatment effect parameters are informative or not. Compared to a partition of
the feature space that results from a least squares criterion for a single
tree in a regression forest that predicts $Y_{i}$ with $X_{i}$, it may be more
ideal to understand treatment effects with the feature space partition given
by a decision tree in a causal forest (Athey et al.,, 2019) that uses the more
relevant Robinson-Learner objective (Nie and Wager,, 2020).

###  2.4 Given a fixed sample size

Let

$n_{\mathcal{S}}=\left|\mathcal{S}\right|$

be the fixed sample size corresponding to the honest prediction set
$\mathcal{S}$. Recall that

$\sum_{w,l}n_{wl}=n_{\mathcal{S}}.$

For the sake of solving for tolerable values of $K,L,\alpha,$ and $\epsilon$,
let us set:

$\min_{w,l}n_{wl}\dot{=}\frac{n_{\mathcal{S}}}{K\times L}.$

To apply Propositions 2.1, A.1, and A.2 to the case with a fixed sample size
budget $n_{\mathcal{S}}$, we can enforce an inequality of the form

$\frac{n_{\mathcal{S}}}{K\times L}\ \geq\
g(K,L,\alpha,\epsilon,\sigma^{2},\dots),$

where $g$ corresponds to the concentration inequality that is used to
determine the sufficient sample size, such as the right hand side of the
inequality in (7). In order to solve for a tolerable value for one of $K$,
$L$, $\alpha$, and $\epsilon$, we can fix the other terms. That is:

  * •

The maximum allowable number of treatment arms:

$\arg\max\left\\{K:\ \frac{n_{\mathcal{S}}}{K\times L}\ \geq\
g(K,L,\alpha,\epsilon,\sigma^{2},\dots)\right\\}.$

  * •

The maximum allowable number of feature space subsets:

$\arg\max\left\\{L:\ \frac{n_{\mathcal{S}}}{K\times L}\ \geq\
g(K,L,\alpha,\epsilon,\sigma^{2},\dots)\right\\}.$

  * •

The supremum allowable confidence:

$\arg\sup\left\\{1-\alpha:\ \frac{n_{\mathcal{S}}}{K\times L}\ \geq\
g(K,L,\alpha,\epsilon,\sigma^{2},\dots)\right\\}.$

  * •

The infimum allowable margin of error:

$\arg\inf\left\\{\epsilon:\ \frac{n_{\mathcal{S}}}{K\times L}\ \geq\
g(K,L,\alpha,\epsilon,\sigma^{2},\dots)\right\\}.$

If the solutions to these are not analytically derivable, such as $\epsilon$
when $g$ is given by Bennet’s inequality in Proposition A.2, bisection or some
other root-finding method can be used (Rosenblum and van der Laan,, 2009).

###  2.5 Bounding the Outcome’s conditional variance

Some warnings are in order, especially when attempting to understand the
maximum allowable feature space subsets or maximum allowable number of
treatment arms. In particular, special care must be taken with respect to the
outcome variation bound

$\sigma^{2}\geq\max_{w,l}{\rm Var}\left[Y_{n+1}\mid
W_{n+1}=w,\ell(X_{n+1})=l\right].$

Due to the possibility of heteroscedasticty, ${\rm Var}\left[Y_{n+1}\mid
W_{n+1}=w,\ell(X_{n+1})=l\right]$ may change non-trivially as $L$ and $K$
change. When the outcome is bounded almost surely–Assumption 2.1, it can be
shown:

$\max_{w,l}{\rm Var}\left[Y_{n+1}\mid
W_{n+1}=w,\ell(X_{n+1})=l\right]\leq\frac{(b-a)^{2}}{4}.$

The upper bound is attained if $Y_{n+1}$ in treatment group $w$ in leaf $l$ is
discrete at two unique values $a$ and $b$ with equal probability.

A scenario to tighten the conservative conditional variance bound of
$(b-a)^{2}/4$ can be if we have knowledge that, for some fixed outcome value
$y^{*}$ and some small $p^{*}\in\left[0,1/2\right]$, we have:

$\max_{w,l}\text{Pr}\left(Y_{n+1}\neq y^{*}\ \middle|\
W_{n+1}=w,\ell(X_{n+1})=l\right)\ \leq p^{*}.$

The rate $p^{*}$ can be approximated from domain knowledge in the case that an
outcome rarely exhibits a change from a fixed value. For example, the best
click-through rate among marketing ad interventions may realistically remain
capped by a small value. In this case, we show in Appendix B that:

$\displaystyle\max_{w,l}{\rm Var}\left[Y_{n+1}\mid
W_{n+1}=w,\ell(X_{n+1})=l\right]$ (9) $\displaystyle\leq$ $\displaystyle
p^{*}\frac{(b-a)^{2}}{4}+p^{*}(1-p^{*})\max\left\\{(a-y^{*})^{2},(b-y^{*})^{2}\right\\}.$

If $Y_{n+1}\in\\{0,1\\}$, the conditional variance upper bound can instead be
tightened by noting:

$\displaystyle\max_{w,l}{\rm Var}\left[Y_{n+1}\mid
W_{n+1}=w,\ell(X_{n+1})=l\right]$ $\displaystyle=$
$\displaystyle\max_{w,l}\\{\text{Pr}\left(Y_{n+1}=y^{*}\ \middle|\
W_{n+1}=w,\ell(X_{n+1})=l\right)$ $\displaystyle\ \ \ \
\times\left[1-\text{Pr}\left(Y_{n+1}=y^{*}\ \middle|\
W_{n+1}=w,\ell(X_{n+1})=l\right)\right]\\}$ $\displaystyle\leq$ $\displaystyle
p^{*}(1-p^{*}),$

since $g(t)=t(1-t)$ is monotone increasing for $t\in[0,1/2]$. Figure 1 depicts
the binary outcome case with the most conservative standard deviation,
$\sigma=0.5$, corresponding to $p^{*}=0.5$.

Should we instead wish to specify the parameter $\sigma=1$, the sufficient
sample size in Propositions 2.1, A.1, and A.2 guarantees a deviation that is
within a factor $\epsilon$ of the conditional standard deviation, as we
explain in Remark 2.1.

##  3 Emprical Evaluation

Figure 2: Coverage across 500 replicates.

Figure 3: Across 500 replicates, the realized decision tree parameters.

We now present an application to Criteo AI Lab’s uplift prediction benchmark
dataset (Diemert et al.,, 2018). According to the web page that hosts the
data:

> This dataset is constructed by assembling data resulting from several
> incrementality tests, a particular randomized trial procedure where a random
> part of the population is prevented from being targeted by advertising. It
> consists of 25M rows, each one representing a user with [12] features, a
> treatment indicator and 2 labels (visits and conversions).

The available down sampled data consists of 13,979,592 observations. The
outcome we focus on is the $0/1$ indicator for a website visit.

In our semi-synthetic simulations, we use the Central Limit Theorem approach
to designate a sample size that guarantees

$\displaystyle\text{Pr}\left(\max_{w}\left|\frac{\hat{\mu}(X_{n+1},w)-\mu(X_{n+1},w)}{\sigma_{w\ell(X_{n+1})}}\right|<\frac{1}{25}\right)$
(10)

be at least $0.9$. For this to hold, it is sufficient that

$\min_{w,l}n_{wl}\geq 2374.$

We implement the sub-group counterfactual mean estimation using a PolicyTree
(Athey and Wager,, 2021) from the econml.policy module in Python (Battocchi et
al.,, 2019), which learns a decision tree-based mapping, also known as a
treatment policy,

$\hat{e}:\
\mathcal{X}\to\left\\{1,\dots,L\right\\}\to\left\\{1,\dots,K\right\\}$

maximizing the total rewards (website visits):

$\mathcal{L}(e)\ \dot{=}\
\sum_{i\in\mathcal{S}}\sum_{w}\mathbf{1}\left\\{{e}(X_{i})=w\right\\}R_{iw}.$

For our case, we constrain the minimum number of samples in each leaf to be
min_samples_leaf=2374. Here, $R_{iw}$ is the reward that can be obtained from
record $i$ should we assign them to treatment group $w$. In practice, the
various potential rewards (potential outcomes) are unknown, so we can impute
each of these with our estimate of

$\mathbb{E}\left[Y_{i}\middle|W_{i}=w,X_{i}\right].$

Using the training set indices
$\left\\{1,\dots,n\right\\}\backslash\mathcal{S}$, we fit a single regression
function, or Single-learner as it has been referred to in the causal inference
literature (Künzel et al.,, 2019; Nie and Wager,, 2020), using the histogram
gradient boosting classifier in the sklearn.ensemble module by setting
min_samples_leaf=2374 (Pedregosa et al.,, 2011). After imputing the honest set
values of $R_{iw}$ using this S-learner, we set the argument honest to be
False in PolicyTree since our honest splitting was done manually; we leave the
rest of the arguments to their default. Because the PolicyTree module does not
allow us to constrain the treatment-group sample size per leaf, we enforce our
required leaf constraint per treatment group by learning one PolicyTree
separately for each treatment group.

Given a specified maximum number of leaves ($L=5,10,50$) in a PolicyTree, and
given the minimum sample size per treatment group per leaf of 2374, along with
an honest set fraction of $\left|\mathcal{S}\right|/{n}=0.5$, we sample (with
replacement)

$n=2\times L\times 2374/0.5$

of the 13,979,592 records (half for the control group and half for treatment
group). We train our model with this sample. We replicate this process 500
times.

To approximate the true parameters in (LABEL:eqn:guaranteeNeeded), we sample
in each of the 500 replicates an additional $n_{\rm test}=2\times L\times
20,000$ records with which we calculate

$\hat{\mu}^{\rm test}(x,w):=\frac{1}{\left|\mathcal{I}^{\rm
test}(w,\ell(x)\right|}\sum_{j\in\mathcal{I}^{\rm test}(w,\ell(x)}Y_{n+j}$

and

$\hat{\sigma}^{\rm test}_{w\ell(x)}:=\sqrt{\frac{1}{\left|\mathcal{I}^{\rm
test}(w,\ell(x))\right|}\sum_{j\in\mathcal{I}^{\rm
test}(w,\ell(x))}\left(Y_{n+j}-\hat{\mu}^{\rm test}(x,w)\right)^{2}}.$

Here,

$\mathcal{I}^{\rm test}(w,l):=\left\\{j\in\left\\{1,\dots,n_{\rm
test}\right\\}:\ W_{n+j}=w,\ell(X_{n+j})=l\right\\}.$

To test whether (LABEL:eqn:guaranteeNeeded) holds, we take the average across
the 500 replicates of the one-replicate empirical coverage at the $n_{test}$
test points:

$\frac{1}{n_{\rm test}}\sum_{j=1}^{n_{\rm
test}}\mathbf{1}\left\\{\max_{w}\left|\frac{\hat{\mu}(X_{n+j},w)-\hat{\mu}^{\rm
test}(X_{n+j},w)}{\hat{\sigma}^{\rm
test}_{w\ell(X_{n+j})}}\right|<\frac{1}{25}\right\\}.$

Figure 3 shows the results: we achieve greater than 90% coverage across the
replicates. Besides the minimum sample size per leaf and treatment group we
specify, Figure 3 explains our good performance by demonstrating the
distribution of realized decision tree parameters: number of leaves, minimum
sample size per leaf and treatment group, and the max and median standard
deviations per leaf and treatment group in the test set. For example, the
number of leaves in a decision tree was not always the maximum of $L$ allowed
by the sample size $n$ and lower bound on $\min_{w,l}n_{wl}$. Intuitively,
this is because better splits were possible at the top of the decision trees
compared to a split that evenly divided the records in $\mathcal{S}$ to the
left and right child nodes.

##  4 Discussion and Limitations

With regard to recent advances in online experimentation and their anytime
valid inference (Maharaj et al.,, 2023; Kuchibhotla and Zheng,, 2021), we
think our results are helpful despite their application to fitting a model
”offline” after data collection. Online experiments typically run until
statistically significant differences across pair-wise mean comparisons are
reached, or until some time budget is reached if no statistical significance.
For the first case, at the time point where statistical significance is
reached, we can see how complex a model can be learned using the discussion in
Section 2.4. If the complexity is not satisfactory, more data can be
collected. On the other hand, despite the possibility that pair-wise mean
comparisons are not marginally significantly different when a time budget is
reached, some pair-wise comparisons in learnable sub-groups may be significant
if a large enough signal can be denoised by dilineating sub-groups with pre-
treatment features. For this second case, we may similarly entertain plausible
model complexities and even attempt to collect further data until a desired
complexity is possible.

Regarding the determination of a statistically significant difference between
two treatment groups in a sub-group, the value $\epsilon$ in our sample size
calculation gives an understanding that an absolute difference in means of
$2\epsilon$ or larger, whether at the original scale or a standardized scale,
is sufficiently large to rule out random chance at the $\alpha$-significance
level. However, we note that our use of an upper bound on the conditional
variances opens up the possiblity that smaller differences than $2\epsilon$
can be deemed statistically significant in practice. This is because the
standard error for the mean comparison,

$\sqrt{{\rm
Var}\left[\hat{\mu}_{wl}-\hat{\mu}_{w^{\prime}l}\mid\mathcal{I}\right]}=\sqrt{\sigma_{wl}^{2}/n_{wl}+\sigma_{w^{\prime}l}^{2}/n_{w^{\prime}l}},$

can be much smaller when using the true conditional variances compared to the
maximum bound $\sigma^{2}$. Related to this, each treatment group need not
have the same number of units either. That is, an imbalanced design where
there are more units in some treatment groups compared to others could help
make smaller differences in a pair-wise comparison of means detectable,
espcially if a greater sample is directed toward the treatment group(s) with
more outcome variation. This is simply because the standard error for a
pairwise mean comparison also decreases with an increase in the sample size
used to calculate one of the two sample means, $\hat{\mu}_{wl}$ or
$\hat{\mu}_{w^{\prime}l}$, in question.

While the empirical counterfactual mean in a sub-group may be close, in a
frequentist sense, to its population analogue with a sufficient sample size,
special care must be taken with respect to this parameter. Firstly, the sub-
group counterfactual average may not be the best summary value for a
treatment’s performance: a random variable (e.g. difference in potential
outcomes) need not be close to its (sub-group) average (Ruiz and Padilla,,
2022). Relatedly, special care must be taken with respect to hyper-parameter
tuning and goodness of fit. Empirics when choosing a regression model, such as
$R^{2}$ and AUC, are still important. Moreover, an ensemble of trees may more
robustly summarize an experiment compared to one tree (Athey et al.,, 2019).

In this paper, we address only internal validity of our inference (recall the
stationarity condition of the new test point in Section 1.1.1). In practice,
sensitivity analysis is important when reasoning about external validity of
inference with an experimental sample. For example, see Lei et al., (2023) for
a discussion of this phenomenon along with a reformulation of the policy
learning objective to account for it. Moreover, with respect to designing
randomized trials with the aim of understanding treatment effect
heterogeneity, Tipton and Mamakos, (2023) study the mean squared prediction
error (MSPE) of the random individual treatment effect of an out of sample
subject in a target population. Heterogeneity in Tipton and Mamakos, (2023) is
with respect to a linear specification and a low-dimensional reweighted least
squares estimator accounting for how relatively likely we are to observe a
unit in the sample’s origin population compared to the target inference
population. It would be interesting to join our and this approach for external
validity under a nonlinear model specification including, but not limited to,
a learnable feature space partition.

##  5 Acknowledgements

Gabriel would like to acknowledge Binjie Lai, Julia Viladomat, Vasco Yasenov,
Oscar Madrid-Padilla, Alan Vasquez, David Arbour, Ritwik Sinha, and Avi Feller
for their insightful conversations related to this manuscript. Gabriel would
also like to acknowledge the financial support of Adobe Inc. during the
realization of this work.

## References

  * 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 et al., (2019) Athey, S., Tibshirani, J., and Wager, S. (2019).  Generalized random forests.  The Annals of Statistics, 47(2):1148 – 1178.
  * Athey and Wager, (2021) Athey, S. and Wager, S. (2021).  Policy Learning With Observational Data.  Econometrica, 89(1):133–161.
  * Battocchi et al., (2019) Battocchi, K., Dillon, E., Hei, M., Lewis, G., Oka, P., Oprescu, M., and Syrgkanis, V. (2019).  EconML: A Python Package for ML-Based Heterogeneous Treatment Effects Estimation.  https://github.com/py-why/EconML.  Version 0.14.0.
  * Bennett, (1962) Bennett, G. (1962).  Probability inequalities for the sum of independent random variables.  Journal of the American Statistical Association, 57(297):33–45.
  * Breiman et al., (2017) Breiman, L., Friedman, J. H., Olshen, R. A., and Stone, C. J. (2017).  Classification And Regression Trees.  Routledge.
  * Diemert et al., (2018) Diemert, E., Betlei, A., Renaudin, C., and Amini, M.-R. (2018).  A Large Scale Benchmark for Uplift Modeling.  In KDD, London, United Kingdom.
  * D’Amour et al., (2021) D’Amour, A., Ding, P., Feller, A., Lei, L., and Sekhon, J. (2021).  Overlap in observational studies with high-dimensional covariates.  Journal of Econometrics, 221(2):644–654.
  * Gupta and Ramdas, (2021) Gupta, C. and Ramdas, A. (2021).  Distribution-Free Calibration Guarantees for Histogram Binning without Sample Splitting.  In Meila, M. and Zhang, T., editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 3942–3952. PMLR.
  * Hernan and Robins, (2023) Hernan, M. and Robins, J. (2023).  Causal Inference.  Chapman & Hall/CRC Monographs on Statistics & Applied Probab. CRC Press.
  * Imbens, (2004) Imbens, G. W. (2004).  Nonparametric Estimation of Average Treatment Effects Under Exogeneity: A Review.  The Review of Economics and Statistics, 86(1):4–29.
  * Imbens and Rubin, (2015) Imbens, G. W. and Rubin, D. B. (2015).  Causal Inference for Statistics, Social, and Biomedical Sciences: An Introduction.  Cambridge University Press.
  * Kuchibhotla and Zheng, (2021) Kuchibhotla, A. K. and Zheng, Q. (2021).  Near-optimal confidence sequences for bounded random variables.
  * Künzel et al., (2019) Künzel, S. R., Sekhon, J. S., Bickel, P. J., and Yu, B. (2019).  Metalearners for estimating heterogeneous treatment effects using machine learning.  Proceedings of the National Academy of Sciences, 116(10):4156–4165.
  * Lei et al., (2023) Lei, L., Sahoo, R., and Wager, S. (2023).  Policy learning under biased sample selection.  arXiv, 2304.11735.
  * Maharaj et al., (2023) Maharaj, A., Sinha, R., Arbour, D., Waudby-Smith, I., Liu, S. Z., Sinha, M., Addanki, R., Ramdas, A., Garg, M., and Swaminathan, V. (2023).  Anytime-valid confidence sequences in an enterprise a/b testing platform.  In Companion Proceedings of the ACM Web Conference 2023. ACM.
  * Nie and Wager, (2020) Nie, X. and Wager, S. (2020).  Quasi-oracle estimation of heterogeneous treatment effects.  Biometrika, 108(2):299–319.
  * Pearl, (2000) Pearl, J. (2000).  Causality: Models, reasoning, and inference 47cambridge university presscambridge, united kingdom. pearl, j. 2000.  Causality: models, reasoning, and inference, 47.
  * Pedregosa et al., (2011) Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., Vanderplas, J., Passos, A., Cournapeau, D., Brucher, M., Perrot, M., and Duchesnay, E. (2011).  Scikit-learn: Machine learning in Python.  Journal of Machine Learning Research, 12:2825–2830.
  * 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.
  * Rosenblum and van der Laan, (2009) Rosenblum, M. A. and van der Laan, M. J. (2009).  Confidence intervals for the population mean tailored to small sample sizes, with applications to survey sampling.  Int. J. Biostat., 5(1):Article 4.
  * Ruiz and Padilla, (2022) Ruiz, G. and Padilla, O. H. M. (2022).  Non-asymptotic confidence bands on the probability an individual benefits from treatment (PIBT).  arXiv, 2205.09094.
  * Sverdrup et al., (2020) Sverdrup, E., Kanodia, A., Zhou, Z., Athey, S., and Wager, S. (2020).  policytree: Policy learning via doubly robust empirical welfare maximization over trees.  Journal of Open Source Software, 5(50):2232.
  * Tipton and Mamakos, (2023) Tipton, E. and Mamakos, M. (2023).  Designing randomized experiments to predict unit-specific treatment effects.  arXiv, 2310.18500.
  * Vegetabile, (2021) Vegetabile, B. G. (2021).  On the Distinction Between ”Conditional Average Treatment Effects” (CATE) and ”Individual Treatment Effects” (ITE) Under Ignorability Assumptions.  arXiv, 2108.04939.
  * Wainwright, (2019) Wainwright, M. J. (2019).  High-Dimensional Statistics: A Non-Asymptotic Viewpoint.  Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press.
  * Zadrozny and Elkan, (2002) Zadrozny, B. and Elkan, C. (2002).  Transforming Classifier Scores into Accurate Multiclass Probability Estimates.  In Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’02, page 694–699, New York, NY, USA. Association for Computing Machinery.

##  Appendix A Extended Main Results

######  Proposition A.1 (Main Result: Bounded Outcome).

Suppose Assumption 2.1 holds. Let $\alpha\in(0,1)$ and $\epsilon>0$.

  * •

Then for (1) to hold, it is sufficient that

$\min_{w,l}n_{wl}\geq\frac{\log\left(\frac{2}{1-\left(1-\alpha\right)^{\frac{1}{K}}}\right)\left|b-a\right|^{2}}{2\epsilon^{2}}.$

  * •

Then for (4) to hold, it is sufficient that

$\min_{w,l}n_{wl}\geq\frac{\log\left(\frac{2}{1-\left(1-\alpha\right)^{\frac{1}{KL}}}\right)\left|b-a\right|^{2}}{2\epsilon^{2}}.$

######  Proposition A.2 (Main Result: Bounded Outcome and Bound on its
Conditional Variance).

Suppose Assumptions 2.1 and 2.2 hold.

  * •

Then for the guarantee in (1) to hold, it is sufficient that

$\displaystyle\min_{w,l}n_{wl}$ $\displaystyle\geq$
$\displaystyle\frac{\log\left(\frac{2}{1-(1-\alpha)^{\frac{1}{K}}}\right)\max\\{a^{2},b^{2}\\}}{\sigma^{2}\left\\{\left(1+s\right)\log\left(1+s\right)-s\right\\}}.$

  * •

Then for the guarantee in (4) to hold, it is sufficient that

$\displaystyle\min_{w,l}n_{wl}$ $\displaystyle\geq$
$\displaystyle\frac{\log\left(\frac{2}{1-(1-\alpha)^{\frac{1}{KL}}}\right)\max\\{a^{2},b^{2}\\}}{\sigma^{2}\left\\{\left(1+s\right)\log\left(1+s\right)-s\right\\}}.$

Here,

$s:=\frac{\epsilon\max\\{|a|,|b|\\}}{\sigma^{2}}.$

##  Appendix B Proofs

###  B.1 Proof of Lemma 2.1

###### Proof of Lemma 2.1.

Guarantees For a Random
$X_{n+1}\perp\\!\\!\\!\perp\left\\{X_{1},\dots,X_{n}\right\\}$:
With respect to the part of Lemma 2.1 that provides a guarantee for random
$X_{n+1}$, consider the event:

$\displaystyle\mathcal{E}(X_{n+1})$ $\displaystyle=$
$\displaystyle\left\\{\max_{w}\left|\hat{\mu}(X_{n+1},w)-\mu(X_{n+1},w)\right|<\epsilon\right\\}.$

Recall our assumption that $\text{Pr}\left(\mathcal{E}(X_{n+1})\ \middle|\
\mathcal{I}\right)\geq 1-\alpha$.

  * •

Best Conditional Counterfactual Mean:
Consider that:

$\displaystyle\text{Pr}\left(\left|\max_{w}\hat{\mu}(X_{n+1},w)-\max_{w}\mu(X_{n+1},w)\right|\geq\epsilon\
\middle|\ \mathcal{I}\right)$ $\displaystyle=$
$\displaystyle\text{Pr}\left(\left|\max_{w}\hat{\mu}(X_{n+1},w)-\max_{w}\mu(X_{n+1},w)\right|\geq\epsilon\
\middle|\
\mathcal{E}(X_{n+1}),\mathcal{I}\right)\text{Pr}\left(\mathcal{E}(X_{n+1})\
\middle|\ \mathcal{I}\right)$
$\displaystyle+\text{Pr}\left(\left|\max_{w}\hat{\mu}(X_{n+1},w)-\max_{w}\mu(X_{n+1},w)\right|\geq\epsilon\
\middle|\
\mathcal{E}(X_{n+1})^{C},\mathcal{I}\right)\text{Pr}\left(\mathcal{E}(X_{n+1})^{C}\
\middle|\ \mathcal{I}\right)$ $\displaystyle\leq$
$\displaystyle\text{Pr}\left(\mathcal{E}(X_{n+1})^{C}\ \middle|\
\mathcal{I}\right)$ $\displaystyle\leq$ $\displaystyle\alpha.$

From this, it follows that

$\text{Pr}\left(\left|\max_{w}\hat{\mu}(X_{n+1},w)-\max_{w}\mu(X_{n+1},w)\right|<\epsilon\
\middle|\ \mathcal{I}\right)\geq 1-\alpha$

as desired.

We used that

$\text{Pr}\left(\left|\max_{w}\hat{\mu}(X_{n+1},w)-\max_{w}\mu(X_{n+1},w)\right|\geq\epsilon\
\middle|\ \mathcal{E}(X_{n+1}),\mathcal{I}\right)=0.$

This is because $\mathcal{E}(X_{n+1})$ and triangle inequality imply that with
probability $1$,

$\displaystyle\left|\max_{w}\hat{\mu}(X_{n+1},w)-\max_{w}\mu(X_{n+1},w)\right|$
$\displaystyle=$
$\displaystyle\max\left\\{\max_{w}\hat{\mu}(X_{n+1},w)-\max_{w}\mu(X_{n+1},w),\
\max_{w}\mu(X_{n+1},w)-\max_{w}\hat{\mu}(X_{n+1},w)\right\\}$ $\displaystyle<$
$\displaystyle\max\left\\{\max_{w}\left[\mu(X_{n+1},w)+\epsilon\right]-\max_{w}\mu(X_{n+1},w),\
\max_{w}\left[\hat{\mu}(X_{n+1},w)+\epsilon\right]-\max_{w}\hat{\mu}(X_{n+1},w)\right\\}$
$\displaystyle=$ $\displaystyle\epsilon.$

Moreover, we used that

$\text{Pr}\left(\left|\max_{w}\hat{\mu}(X_{n+1},w)-\max_{w}\mu(X_{n+1},w)\right|\geq\epsilon\
\middle|\ \mathcal{E}(X_{n+1})^{C},\mathcal{I}\right)\leq 1.$

  * •

Treatment Effect Function:
Consider next that:

$\displaystyle\text{Pr}\left(\max_{w\neq
w^{\prime}}\left|\hat{\tau}(X_{n+1},w,w^{\prime})-\tau(X_{n+1},w,w^{\prime})\right|\geq
2\epsilon\ \middle|\ \mathcal{I}\right)$ $\displaystyle=$
$\displaystyle\text{Pr}\left(\max_{w\neq
w^{\prime}}\left|\hat{\tau}(X_{n+1},w,w^{\prime})-\tau(X_{n+1},w,w^{\prime})\right|\geq
2\epsilon\ \middle|\
\mathcal{E}(X_{n+1}),\mathcal{I}\right)\text{Pr}\left(\mathcal{E}(X_{n+1})\
\middle|\ \mathcal{I}\right)$ $\displaystyle+\text{Pr}\left(\max_{w\neq
w^{\prime}}\left|\hat{\tau}(X_{n+1},w,w^{\prime})-\tau(X_{n+1},w,w^{\prime})\right|\geq
2\epsilon\ \middle|\
\mathcal{E}(X_{n+1})^{C},\mathcal{I}\right)\text{Pr}\left(\mathcal{E}(X_{n+1})^{C}\
\middle|\ \mathcal{I}\right)$ $\displaystyle\leq$
$\displaystyle\text{Pr}\left(\mathcal{E}(X_{n+1})^{C}\ \middle|\
\mathcal{I}\right)$ $\displaystyle\leq$ $\displaystyle\alpha.$

From this, it follows that

$\text{Pr}\left(\max_{w\neq
w^{\prime}}\left|\hat{\tau}(X_{n+1},w,w^{\prime})-\tau(X_{n+1},w,w^{\prime})\right|<2\epsilon\
\middle|\ \mathcal{I}\right)\geq 1-\alpha$

as desired.

We used that

$\text{Pr}\left(\max_{w\neq
w^{\prime}}\left|\hat{\tau}(X_{n+1},w,w^{\prime})-\tau(X_{n+1},w,w^{\prime})\right|\geq
2\epsilon\ \middle|\ \mathcal{E}(X_{n+1}),\mathcal{I}\right)=0.$

This is because $\mathcal{E}(X_{n+1})$ and triangle inequality imply that with
probability $1$,

$\max_{w\neq
w^{\prime}}\left|\hat{\tau}(X_{n+1},w,w^{\prime})-\tau(X_{n+1},w,w^{\prime})\right|\leq
2\max_{w}\left|\hat{\mu}(X_{n+1},w)-\mu(X_{n+1},w)\right|<2\epsilon.$

Moreover, we used that

$\text{Pr}\left(\max_{w\neq
w^{\prime}}\left|\hat{\tau}(X_{n+1},w,w^{\prime})-\tau(X_{n+1},w,w^{\prime})\right|\geq
2\epsilon\ \middle|\ \mathcal{E}(X_{n+1})^{C},\mathcal{I}\right)\leq 1.$

Guarantees Uniformly Across $x\in\mathcal{X}$:
With respect to the part of Lemma 2.1 that provides a guarantee uniformly
across $x$, consider the event:

$\displaystyle\mathcal{E}$ $\displaystyle=$
$\displaystyle\left\\{\sup_{x}\max_{w}\left|\hat{\mu}(x,w)-\mu(x,w)\right|<\epsilon\right\\}.$

Recall our assumption that $\text{Pr}\left(\mathcal{E}\ \middle|\
\mathcal{I}\right)\geq 1-\alpha$.

  * •

Best Conditional Counterfactual Mean:
Consider that:

$\displaystyle\text{Pr}\left(\sup_{x}\left|\max_{w}\hat{\mu}(x,w)-\max_{w}\mu(x,w)\right|\geq\epsilon\
\middle|\ \mathcal{I}\right)$ $\displaystyle=$
$\displaystyle\text{Pr}\left(\sup_{x}\left|\max_{w}\hat{\mu}(x,w)-\max_{w}\mu(x,w)\right|\geq\epsilon\
\middle|\ \mathcal{E},\mathcal{I}\right)\text{Pr}\left(\mathcal{E}\ \middle|\
\mathcal{I}\right)$
$\displaystyle+\text{Pr}\left(\sup_{x}\left|\max_{w}\hat{\mu}(x,w)-\max_{w}\mu(x,w)\right|\geq\epsilon\
\middle|\ \mathcal{E}^{C},\mathcal{I}\right)\text{Pr}\left(\mathcal{E}^{C}\
\middle|\ \mathcal{I}\right)$ $\displaystyle\leq$
$\displaystyle\text{Pr}\left(\mathcal{E}^{C}\ \middle|\ \mathcal{I}\right)$
$\displaystyle\leq$ $\displaystyle\alpha.$

From this, it follows that

$\text{Pr}\left(\sup_{x}\left|\max_{w}\hat{\mu}(x,w)-\max_{w}\mu(x,w)\right|<\epsilon\
\middle|\ \mathcal{I}\right)\geq 1-\alpha$

as desired.

We used that

$\text{Pr}\left(\sup_{x}\left|\max_{w}\hat{\mu}(x,w)-\max_{w}\mu(x,w)\right|\geq\epsilon\
\middle|\ \mathcal{E},\mathcal{I}\right)=0.$

This is because $\mathcal{E}$ and triangle inequality imply that with
probability $1$,

$\displaystyle\sup_{x}\left|\max_{w}\hat{\mu}(x,w)-\max_{w}\mu(x,w)\right|$
$\displaystyle=$
$\displaystyle\sup_{x}\max\left\\{\max_{w}\hat{\mu}(x,w)-\max_{w}\mu(x,w),\
\max_{w}\mu(x,w)-\max_{w}\hat{\mu}(x,w)\right\\}$ $\displaystyle<$
$\displaystyle\sup_{x}\max\left\\{\max_{w}\left[\mu(x,w)+\epsilon\right]-\max_{w}\mu(x,w),\
\max_{w}\left[\hat{\mu}(x,w)+\epsilon\right]-\max_{w}\hat{\mu}(x,w)\right\\}$
$\displaystyle=$ $\displaystyle\epsilon.$

Moreover, we used that

$\text{Pr}\left(\sup_{x}\left|\max_{w}\hat{\mu}(x,w)-\max_{w}\mu(x,w)\right|\geq\epsilon\
\middle|\ \mathcal{E}^{C},\mathcal{I}\right)\leq 1.$

  * •

Treatment Effect Function:
Consider next that:

$\displaystyle\text{Pr}\left(\sup_{x}\max_{w\neq
w^{\prime}}\left|\hat{\tau}(x,w,w^{\prime})-\tau(x,w,w^{\prime})\right|\geq
2\epsilon\ \middle|\ \mathcal{I}\right)$ $\displaystyle=$
$\displaystyle\text{Pr}\left(\sup_{x}\max_{w\neq
w^{\prime}}\left|\hat{\tau}(x,w,w^{\prime})-\tau(x,w,w^{\prime})\right|\geq
2\epsilon\ \middle|\ \mathcal{E},\mathcal{I}\right)\text{Pr}\left(\mathcal{E}\
\middle|\ \mathcal{I}\right)$
$\displaystyle+\text{Pr}\left(\sup_{x}\max_{w\neq
w^{\prime}}\left|\hat{\tau}(x,w,w^{\prime})-\tau(x,w,w^{\prime})\right|\geq
2\epsilon\ \middle|\
\mathcal{E}^{C},\mathcal{I}\right)\text{Pr}\left(\mathcal{E}^{C}\ \middle|\
\mathcal{I}\right)$ $\displaystyle\leq$
$\displaystyle\text{Pr}\left(\mathcal{E}^{C}\ \middle|\ \mathcal{I}\right)$
$\displaystyle\leq$ $\displaystyle\alpha.$

From this, it follows that

$\text{Pr}\left(\sup_{x}\max_{w\neq
w^{\prime}}\left|\hat{\tau}(x,w,w^{\prime})-\tau(x,w,w^{\prime})\right|<2\epsilon\
\middle|\ \mathcal{I}\right)\geq 1-\alpha$

as desired. We used that

$\text{Pr}\left(\sup_{x}\max_{w\neq
w^{\prime}}\left|\hat{\tau}(x,w,w^{\prime})-\tau(x,w,w^{\prime})\right|\geq
2\epsilon\ \middle|\ \mathcal{E},\mathcal{I}\right)=0.$

This is because $\mathcal{E}$ and triangle inequality imply that with
probability $1$,

$\sup_{x}\max_{w\neq
w^{\prime}}\left|\hat{\tau}(x,w,w^{\prime})-\tau(x,w,w^{\prime})\right|\leq
2\sup_{x}\max_{w}\left|\hat{\mu}(x,w)-\mu(x,w)\right|<2\epsilon.$

Moreover, we used that

$\text{Pr}\left(\sup_{x}\max_{w\neq
w^{\prime}}\left|\hat{\tau}(x,w,w^{\prime})-\tau(x,w,w^{\prime})\right|\geq
2\epsilon\ \middle|\ \mathcal{E}^{C},\mathcal{I}\right)\leq 1.$

∎

###  B.2 Proof of Propositions 2.1, A.1, and A.2

Consider first that we have $M=K\times L$ groups we are taking the mean of.
Each observation is independent of any others, and within each group defined
by the treatment group and feature space subset, they are iid according to

$Y_{i}|\ell(X_{i})=l,W_{i}=w;l=1,\dots,L,\ w=1,\dots,K.$

Thus, we can apply the pertinent result in Lemma B.2.

###  B.3 Proof of Equation (LABEL:eqn:nonZeroVarBound)

###### Proof of Equation (LABEL:eqn:nonZeroVarBound).

We have:

$\displaystyle{\rm Var}\left[Y_{n+1}\mid W_{n+1}=w,\ell(X_{n+1})=l\right]$
$\displaystyle=$ $\displaystyle{\rm Var}\left[Y_{n+1}-y^{*}\mid
W_{n+1}=w,\ell(X_{n+1})=l\right]$ $\displaystyle=$
$\displaystyle\text{Pr}\left(Y_{n+1}\neq y^{*}\ \middle|\
W_{n+1}=w,\ell(X_{n+1})=l\right)\mathbb{E}\left[(Y_{n+1}-y^{*})^{2}\middle|W_{n+1}=w,\ell(X_{n+1})=l,Y_{n+1}\neq
y^{*}\right]$ $\displaystyle-\left(\text{Pr}\left(Y_{n+1}\neq y^{*}\ \middle|\
W_{n+1}=w,\ell(X_{n+1})=l\right)\mathbb{E}\left[Y_{n+1}-y^{*}\middle|W_{n+1}=w,\ell(X_{n+1})=l,Y_{n+1}\neq
y^{*}\right]\right)^{2}$ $\displaystyle=$
$\displaystyle\text{Pr}\left(Y_{n+1}\neq y^{*}\ \middle|\
W_{n+1}=w,\ell(X_{n+1})=l\right){\rm Var}\left[Y_{n+1}-y^{*}\mid
W_{n+1}=w,\ell(X_{n+1})=l,Y_{n+1}\neq y^{*}\right]$
$\displaystyle+\text{Pr}\left(Y_{n+1}\neq y^{*}\ \middle|\
W_{n+1}=w,\ell(X_{n+1})=l\right)\left[1-\text{Pr}\left(Y_{n+1}\neq y^{*}\
\middle|\ W_{n+1}=w,\ell(X_{n+1})=l\right)\right]$
$\displaystyle\times\left(\mathbb{E}\left[Y_{n+1}-y^{*}\middle|W_{n+1}=w,\ell(X_{n+1})=l,Y_{n+1}\neq
y^{*}\right]\right)^{2}$ $\displaystyle\leq$ $\displaystyle
p^{*}\frac{(b-a)^{2}}{4}+p^{*}(1-p^{*})\max\left\\{(a-y^{*})^{2},(b-y^{*})^{2}\right\\}$

In the first equality, we use that variance does not change when adding a
constant. In the second equality, we use that ${\rm
Var}\left[U\right]=\mathbb{E}\left[U^{2}\right]-(\mathbb{E}\left[U\right])^{2}$,
along with law of total expectation for these two terms. The third equality
uses that $\mathbb{E}\left[U^{2}\right]={\rm
Var}\left[U\right]+(\mathbb{E}\left[U\right])^{2}$ and combines terms. The
inequality at the end uses that the function $g(t)=t(1-t)$ is monotone
increasing on the interval $t\in[0,1/2]$. We also use the assumption that

$\max_{w,l}\text{Pr}\left(Y_{n+1}\neq y^{*}\ \middle|\
W_{n+1}=w,\ell(X_{n+1})=l\right)\leq p^{*}\leq\frac{1}{2},$

along with the fact that $Y_{n+1}-y^{*}\in[a-y^{*},b-y^{*}]$.

∎

###  B.4 Additional Lemmas

######  Lemma B.1 (Joint estimation of independent means).

Consider a sample of $n_{j}$ iid random variables $Y_{1j},\dots,Y_{n_{j}j}$,
across $j=1,\dots,K$.

Let $\epsilon\in(0,1)$ and $\alpha\in(0,1)$. Denote

$\mu_{j}=\mathbb{E}\left[Y_{ij}\right].$

  * •

Suppose that

$\text{Pr}\left(a\leq Y_{ij}\leq b\right)=1.$

Then for

$\text{Pr}\left(\max_{j}\left|\frac{1}{n_{j}}\sum_{i=1}^{n_{j}}Y_{ij}-\mu_{j}\right|<\epsilon\right)\geq
1-\alpha,$ (11)

it is sufficient that

$\min_{j}n_{j}\geq\frac{\log\left(\frac{2}{1-(1-\alpha)^{\frac{1}{K}}}\right)\left|b-a\right|^{2}}{2\epsilon^{2}}.$

  * •

In addition to

$\text{Pr}\left(a\leq Y_{ij}\leq b\right)=1,$

suppose further that

${\rm Var}\left[Y_{ij}\right]\leq\sigma^{2}\ \text{for each }j=1,\dots,K.$

Then for Equation (11), it is sufficient that

$\displaystyle\min_{j}n_{j}$ $\displaystyle\geq$
$\displaystyle\frac{\log\left(\frac{2}{1-(1-\alpha)^{\frac{1}{K}}}\right)\max\\{a^{2},b^{2}\\}}{\sigma^{2}\left\\{\left(1+s\right)\log\left(1+s\right)-s\right\\}},$

where

$s=\frac{\epsilon\max\\{|a|,|b|\\}}{\sigma^{2}}.$

  * •

Suppose instead that the Central Limit Theorem (CLT) holds:

$\hat{\mu}_{j}\sim\mathcal{N}\left(\mu_{j},\frac{{\rm
Var}\left[Y_{ij}\right]}{n_{j}}\right);\ j=1,\dots,K.$

Then for Equation (11), it is sufficient that

$\min_{j}n_{j}\ \geq\
\left(\frac{z_{\alpha_{0}/2}\times\max_{j}\sigma_{j}}{\epsilon}\right)^{2}.$

Here, $\Phi$ denotes the standard Normal CDF, while $z_{\alpha_{0}/2}$ is the
$(1-\alpha_{0}/2)^{\rm th}$ quantile of the standard Normal distribution.
Meanwhile,

$\alpha_{0}\ \dot{=}\ 1-(1-\alpha)^{\frac{1}{K}},$

###### Proof.

  * •

For the first case, we have

$\displaystyle\text{Pr}\left(\max_{j}\left|\frac{1}{n_{j}}\sum_{i=1}^{n_{j}}Y_{ij}-\mu_{j}\right|<\epsilon\right)$
$\displaystyle=$
$\displaystyle\prod_{j=1}^{K}\text{Pr}\left(\left|\frac{1}{n_{j}}\sum_{i=1}^{n_{j}}Y_{ij}-\mu_{j}\right|<\epsilon\right)$
$\displaystyle\geq$
$\displaystyle\prod_{j=1}^{K}\left(1-\exp\left\\{-\frac{2n_{j}\epsilon^{2}}{\left|b-a\right|^{2}}\right\\}\right)$
$\displaystyle\geq$ $\displaystyle 1-\alpha.$

The first equality is due to independence. The next inequality is due to
Hoeffding’s inequality (Wainwright,, 2019). For the last inequality, it is
sufficient that

$\min_{j}n_{j}\geq\frac{\log\left(\frac{2}{1-(1-\alpha)^{\frac{1}{K}}}\right)\left|b-a\right|^{2}}{2\epsilon^{2}}.$

  * •

For the second case, we use Bennett’s inequality (Bennett,, 1962; Rosenblum
and van der Laan,, 2009) with the premise that $\max_{j}{\rm
Var}\left[Y_{ij}\right]\leq\sigma^{2}$. We get:

$\displaystyle\text{Pr}\left(\max_{j}\left|\frac{1}{n_{j}}\sum_{i=1}^{n_{j}}Y_{ij}-\mu_{j}\right|<\epsilon\right)$
$\displaystyle=$
$\displaystyle\prod_{j=1}^{K}\text{Pr}\left(\left|\frac{1}{n_{j}}\sum_{i=1}^{n_{j}}Y_{ij}-\mu_{j}\right|<\epsilon\right)$
$\displaystyle\geq$
$\displaystyle\prod_{j=1}^{K}\left(1-\exp\left\\{-\frac{n_{j}\sigma^{2}}{\max\\{a^{2},b^{2}\\}}\left\\{\left(1+\frac{\epsilon\max\\{|a|,|b|\\}}{\sigma^{2}}\right)\log\left(1+\frac{\epsilon\max\\{|a|,|b|\\}}{\sigma^{2}}\right)-\frac{\epsilon\max\\{|a|,|b|\\}}{\sigma^{2}}\right\\}\right\\}\right)$
$\displaystyle\geq$ $\displaystyle 1-\alpha.$

For the last inequality it is sufficient that,

$\displaystyle\min_{j}n_{j}$ $\displaystyle\geq$
$\displaystyle\frac{\log\left(\frac{2}{1-(1-\alpha)^{\frac{1}{K}}}\right)\max\\{a^{2},b^{2}\\}}{\sigma^{2}\left\\{\left(1+\frac{\epsilon\max\\{|a|,|b|\\}}{\sigma^{2}}\right)\log\left(1+\frac{\epsilon\max\\{|a|,|b|\\}}{\sigma^{2}}\right)-\frac{\epsilon\max\\{|a|,|b|\\}}{\sigma^{2}}\right\\}}$
$\displaystyle=$
$\displaystyle\frac{\log\left(\frac{2}{1-(1-\alpha)^{\frac{1}{K}}}\right)\max\\{a^{2},b^{2}\\}}{\sigma^{2}\left\\{\left(1+s\right)\log\left(1+s\right)-s\right\\}},$

where

$s=\frac{\epsilon\max\\{|a|,|b|\\}}{\sigma^{2}}.$

  * •

In the third case, we have:

$\displaystyle\text{Pr}\left(\max_{j}\left|\hat{\mu}_{j}-\mu_{j}\right|<\epsilon\right)$
$\displaystyle\overset{(i)}{=}$
$\displaystyle\prod_{j=1}^{K}\text{Pr}\left(\left|\hat{\mu}_{j}-\mu_{j}\right|<\epsilon\right)$
$\displaystyle\overset{(ii)}{=}$
$\displaystyle\prod_{j=1}^{K}\left\\{1-2\times\Phi\left(-\frac{\epsilon\sqrt{n_{j}}}{\sigma_{j}}\right)\right\\}$
$\displaystyle\overset{(iii)}{\geq}$
$\displaystyle\left\\{1-2\times\Phi\left(-\frac{\epsilon\sqrt{\min_{j}n_{j}}}{\max_{j}\sigma_{j}}\right)\right\\}^{K}$
$\displaystyle\overset{(iv)}{=}$ $\displaystyle 1-\alpha.$

Equality in (i) holds if the sample means are independent of each other.

Equality in (ii) holds if we standardize $\hat{\mu}_{j}-\mu_{j}$. There,
$\Phi$ denotes the standard Normal CDF.

Moreover, the inequality in (iii) follows because

$\Phi\left(-\frac{\epsilon\sqrt{n_{j}}}{\sigma_{j}}\right)\ \leq\
\Phi\left(-\frac{\epsilon\sqrt{\min_{j}n_{j}}}{\max_{j}\sigma_{j}}\right),$

by the monotonic increasing property of CDFs.

Next, the equality in (iv) holds if we choose

$\epsilon\ \dot{=}\
z_{\alpha_{0}/2}\times\frac{\max_{j}\sigma_{j}}{\sqrt{\min_{j}n_{j}}}.$ (12)

There, $z_{\alpha_{0}/2}$ is the $(1-\alpha_{0}/2)^{\rm th}$ quantile of the
standard Normal distribution. Meanwhile,

$\alpha_{0}\ \dot{=}\ 1-(1-\alpha)^{\frac{1}{K}},$

which is a simple algebraic trick to allow the desired $(1-\alpha)\times\%100$
confidence in the joint inference of the means.

For a desired margin of error $\epsilon>0$, we can simply solve for
$\min_{j}n_{j}$ in Equation (12) to see that the minimum sample size must be
at least:

$\min_{j}n_{j}\ \geq\
\left(\frac{z_{\alpha_{0}/2}\times\max_{j}\sigma_{j}}{\epsilon}\right)^{2}.$

∎

######  Lemma B.2 (Joint estimation of independent group means nested within
clusters).

Consider a sample of $n_{jl}$ iid random variables
$Y_{1jl},\dots,Y_{n_{j}jl}$, across $j=1,\dots,K$ and $l=1,\dots,L$.

Let $\epsilon\in(0,1)$ and $\alpha\in(0,1)$. Denote

$\mu_{jl}=\mathbb{E}\left[Y_{ijl}\right].$

Group Means in Randomly Selected Cluster:

Suppose that $C\sim\text{Multinoulli}(\pi_{1},\dots,\pi_{L})$ with unknown

$\pi_{l}=\text{Pr}\left(C=l\right)>0;\ l=1,\dots,L.$

  * •

Suppose that

$\text{Pr}\left(a\leq Y_{ijl}\leq b\right)=1.$

Then for

$\text{Pr}\left(\max_{j}\left|\frac{1}{n_{jC}}\sum_{i=1}^{n_{j}}Y_{ijC}-\mu_{jC}\right|<\epsilon\right)\geq
1-\alpha,$ (13)

it is sufficient that

$\min_{j,l}n_{jl}\geq\frac{\log\left(\frac{2}{1-(1-\alpha)^{\frac{1}{K}}}\right)\left|b-a\right|^{2}}{2\epsilon^{2}}.$

  * •

In addition to

$\text{Pr}\left(a\leq Y_{ijl}\leq b\right)=1,$

suppose further that

${\rm Var}\left[Y_{ijl}\right]\leq\sigma^{2}\ \text{for each }j=1,\dots,K,\
l=1,\dots,L.$

Then for Equation (13), it is sufficient that

$\displaystyle\min_{j,l}n_{jl}$ $\displaystyle\geq$
$\displaystyle\frac{\log\left(\frac{2}{1-(1-\alpha)^{\frac{1}{K}}}\right)\max\\{a^{2},b^{2}\\}}{\sigma^{2}\left\\{\left(1+s\right)\log\left(1+s\right)-s\right\\}},$

where

$s=\frac{\epsilon\max\\{|a|,|b|\\}}{\sigma^{2}}.$

  * •

Suppose instead that the Central Limit Theorem (CLT) holds:

$\hat{\mu}_{jl}\sim\mathcal{N}\left(\mu_{jl},\frac{{\rm
Var}\left[Y_{ijl}\right]}{n_{jl}}\right)\ \text{for each }j=1,\dots,K,\
l=1,\dots,L.$

Then for Equation (13), it is sufficient that

$\min_{j,l}n_{jl}\ \geq\
\left(\frac{z_{\alpha_{0}/2}\times\max_{j,l}\sigma_{j,l}}{\epsilon}\right)^{2}$

with

$\alpha_{0}\ \dot{=}\ 1-(1-\alpha)^{\frac{1}{K}}.$

Group Means Across All Clusters:

  * •

Suppose that

$\text{Pr}\left(a\leq Y_{ijl}\leq b\right)=1.$

Then for

$\text{Pr}\left(\max_{j,l}\left|\frac{1}{n_{jl}}\sum_{i=1}^{n_{j}}Y_{ijl}-\mu_{jl}\right|<\epsilon\right)\geq
1-\alpha,$ (14)

it is sufficient that

$\min_{j,l}n_{jl}\geq\frac{\log\left(\frac{2}{1-(1-\alpha)^{\frac{1}{KL}}}\right)\left|b-a\right|^{2}}{2\epsilon^{2}}.$

  * •

In addition to

$\text{Pr}\left(a\leq Y_{ijl}\leq b\right)=1,$

suppose further that

${\rm Var}\left[Y_{ijl}\right]\leq\sigma^{2}\ \text{for each }j=1,\dots,K,\
l=1,\dots,L.$

Then for Equation (14), it is sufficient that

$\displaystyle\min_{j,l}n_{jl}$ $\displaystyle\geq$
$\displaystyle\frac{\log\left(\frac{2}{1-(1-\alpha)^{\frac{1}{KL}}}\right)\max\\{a^{2},b^{2}\\}}{\sigma^{2}\left\\{\left(1+s\right)\log\left(1+s\right)-s\right\\}},$

where

$s=\frac{\epsilon\max\\{|a|,|b|\\}}{\sigma^{2}}.$

  * •

Suppose instead that the Central Limit Theorem (CLT) holds:

$\hat{\mu}_{jl}\sim\mathcal{N}\left(\mu_{jl},\frac{{\rm
Var}\left[Y_{ijl}\right]}{n_{jl}}\right)\ \text{for each }j=1,\dots,K,\
l=1,\dots,L.$

Then for Equation (14), it is sufficient that

$\min_{j,l}n_{jl}\ \geq\
\left(\frac{z_{\alpha_{0}/2}\times\max_{j,l}\sigma_{j,l}}{\epsilon}\right)^{2}$

with

$\alpha_{0}\ \dot{=}\ 1-(1-\alpha)^{\frac{1}{KL}}.$

###### Proof.

Group Means in Randomly Selected Cluster:

In all cases, we have:

$\displaystyle\text{Pr}\left(\max_{j}\left|\frac{1}{n_{jC}}\sum_{i=1}^{n_{j}}Y_{ijC}-\mu_{jC}\right|<\epsilon\right)$
$\displaystyle=$
$\displaystyle\sum_{l=1}^{L}\text{Pr}\left(\max_{j}\left|\frac{1}{n_{jl}}\sum_{i=1}^{n_{j}}Y_{ijl}-\mu_{jl}\right|<\epsilon\
\middle|\ C=l\right)\text{Pr}\left(C=l\right)$ $\displaystyle=$
$\displaystyle\sum_{l=1}^{L}\text{Pr}\left(\max_{j}\left|\frac{1}{n_{jl}}\sum_{i=1}^{n_{j}}Y_{ijl}-\mu_{jl}\right|<\epsilon\right)\text{Pr}\left(C=l\right)$
$\displaystyle\geq$
$\displaystyle\sum_{l=1}^{L}\left(1-\alpha\right)\text{Pr}\left(C=l\right)$
$\displaystyle=$ $\displaystyle 1-\alpha.$

With the pertinent minimum sufficient sample size constraint, the inequality
is due to an invocation of Lemma B.1 for the term

$\text{Pr}\left(\max_{j}\left|\frac{1}{n_{jl}}\sum_{i=1}^{n_{j}}Y_{ijl}-\mu_{jl}\right|<\epsilon\right);\
l=1,\dots,L$

in the law of total probability decomposition of the initial statement.

Group Means Across All Clusters:

Based on the independence assumption, we have a total of $K\times L$
independent sample means

$\hat{\mu}_{jl};\ j=1,\dots,K,\ l=1,\dots,L.$

So we invoke Lemma B.1 with the pertinent minimum sufficient sample size
constraint and the substitution $K\mapsto K\times L$ for the total number of
groups.

∎