# Learning treatment effects while treating those in need

Bryan Wilder
Machine Learning Department, Carnegie Mellon University
<EMAIL_ADDRESS>Pim Welle
Allegheny County Department of Human Services
Department of Engineering and Public Policy, Carnegie Mellon University
<EMAIL_ADDRESS>
#### Abstract:

Many social programs attempt to allocate scarce resources to people with the
greatest need. Indeed, public services increasingly use algorithmic risk
assessments motivated by this goal. However, targeting the highest-need
recipients often conflicts with attempting to evaluate the causal effect of
the program as a whole, as the best evaluations would be obtained by
randomizing the allocation. We propose a framework to design randomized
allocation rules which optimally balance targeting high-need individuals with
learning treatment effects, presenting policymakers with a Pareto frontier
between the two goals. We give sample complexity guarantees for the policy
learning problem and provide a computationally efficient strategy to implement
it. We then apply our framework to data from human services in Allegheny
County, Pennsylvania. Optimized policies can substantially mitigate the
tradeoff between learning and targeting. For example, it is often possible to
obtain 90% of the optimal utility in targeting high-need individuals while
ensuring that the average treatment effect can be estimated with less than 2
times the samples that a randomized controlled trial would require. Mechanisms
for targeting public services often focus on measuring need as accurately as
possible. However, our results suggest that algorithmic systems in public
services can be most impactful if they incorporate program evaluation as an
explicit goal alongside targeting.

#### Keywords:

Resource allocation, machine learning, experimental design, causal inference

##  1 Introduction

A recurring challenge across many policy settings is the allocation of a
limited resource under uncertainty about its benefit. Consider a policymaker
who wishes to focus a limited budget for the largest overall effect. On the
one hand, if the policymaker knew exactly how much each individual benefited
from a given intervention, they could scale the most effective programs and
target each towards the individuals who would benefit the most. On the other
hand, if there was complete uncertainty about benefits, decisions could be no
better than random. Most real settings exist somewhere in the middle:
policymakers believe that they can identify some individuals who are plausibly
better candidates for an intervention but have little formal evidence about
causal effects. Indeed, even the average treatment effect is often not
precisely known (much less heterogeneous effects), making it difficult to
identify and scale the best interventions. Without precise knowledge of causal
effects, resources in any given program are often allocated preferentially to
individuals whose observable characteristics are thought to indicate greater
need; see, e.g. the common use of vulnerability assessments in the allocation
of housing assistance [26, 29] or proxy means tests in development settings
[11, 3, 8]. It is increasingly common to measure need using predictions from
machine learning models [32, 2, 23, 31]. Unlike causal quantities, such models
can often be estimated using existing historical data because they predict the
“baseline” risk of an adverse outcome without treatment (while the treatment
effect is the difference in outcomes with and without treatment). This offers
the potential to target interventions towards more vulnerable individuals but
it also poses a dilemma: obtaining strongly credible evidence about treatment
effects would require randomized allocations that sometimes deny treatment to
individuals thought to have higher need. However, estimating even average
effects would provide an often-lacking chance to identify which programs are
truly effective at improving outcomes.

Here we study the question: how can policymakers optimally navigate such
tradeoffs, balancing the goal of offering interventions to people who need
them in the present while also gathering evidence to improve services over
time? Currently, policymakers largely choose between one of two extremes. In
regular practice, services are often given exclusively to those individuals
deemed at highest need, an allocation rule we refer to as need-based
targeting. At the opposite extreme, policymakers occasionally carve out
specific settings to run a randomized controlled trial (RCT), ignoring the
targeting goal entirely but enabling credible estimates of treatment effects.
One reason RCTs are uncommon is that policymakers may be justifiably averse to
denying a potentially beneficial intervention to high-risk individuals, even
if doing so provides evidence for the future.

We propose an optimal experimental design framework that traces out the entire
spectrum between these extremes. In the case where a policymaker prefers
either the pure randomization of an RCT or the pure needs assessment of a risk
model they can still pursue those strategies, but with this framework they can
operate anywhere in between. Our methods learn a class of of assignment rules
that map an individual’s observable features to their probability of receiving
an intervention. These rules are the solution to a family of optimization
problems that balance (1) the precision of the estimated average treatment
effect with (2) how well allocations align with a specified measure of
individual need. Our framework also allows the policymaker to easily impose
additional constraints, for example on equity in allocation across different
subgroups. The result is a Pareto frontier of experimental designs that
optimally span the tradeoff between such competing goals.

Our results connect to recent interest in the difference between targeting
interventions according to baseline risk (in potential outcome terms, an
estimate of $Y(0)$) versus treatment effects (an estimate of $Y(1)-Y(0)$) [4,
17]. Some have argued that targeting by risk is difficult to rationalize in
welfare terms because high-risk individuals may not realize the greatest
benefit [13], while others have illustrated settings where targeting based on
risk selects a population with a higher “ceiling” for potential impact [14].
Our goal in this paper is not to take a stance about what preferences
policymakers ought to have with respect to this question. There are a variety
of reasons policymakers may prefer either strategy, especially in the setting
we consider where high-quality estimates of causal effects are not available
at the outset. In some domains, beliefs about which individuals are likely to
benefit from a service may already be baked into eligibility criteria or risk
assessments. In others, policymakers may see intrinsic value in offering
assistance to individuals with high need, even if they do not benefit as much
as others. Our framework is agnostic as to the content of these preferences;
we take them as encapsulated in a fixed targeting utility function and our
goal is simply to enable treatment effect estimation while sacrificing as
little of this pre-specified utility as possible. While one empirical
motivation for our work is the widespread adoption of algorithmic risk
assessments, our methods can be equally well applied to preferences informed
by treatment effect estimates if these are available.

We can draw a similar distinction between our goals and those of the online
learning paradigm. For example, one line of work models the assignment of
individuals to interventions as a contextual bandit [1, 10, 9]. However, such
methods have seen relatively few uses in real-world policy settings. The
motivation for our problem formulation is that policymakers may have multiple
incommensurable goals, in which case the single long-term regret objective
optimized in online learning may fail to capture their preferences. Such
objectives can unfold on several levels. First, as discussed above, offering
assistance to individuals with high need is often considered worthwhile in
itself, even if those individuals do not benefit as much from treatment (and
hence contribute less to the standard objective for a contextual bandit).
Second, treatment effect estimates inform multiple kinds of decisions: both
who to offer a given intervention to, but also which programs to offer in the
first place. Indeed, identifying and scaling the best-performing interventions
(via an estimate of the ATE) may often be more impactful than improving the
targeting of individual interventions [25, 22]. Finally, policymakers may be
unwilling to tolerate the significant amount of randomized exploration that
online learning methods often require. For the small sample sizes common in
social service settings, such exploration may impose costs qualitatively
similar to a RCT. For all of these reasons, we formulate an explicitly multi-
objective problem which presents the policymaker with a Pareto frontier
between targeting individuals in need and estimating treatment effects (along
with any other goals such as fairness). It is best suited for the case where
policymakers wish to learn about treatment effects while always ensuring a
specific level of performance in targeting high-need individuals, instead of
minimizing asymptotic regret as in online learning. This presentation of a
Pareto curve between multiple objectives can be seen in the spirit of [27]’s
proposal for machine learning to explicitly balance objectives such as profit,
welfare, and fairness. Operationally, our method is non-adaptive and easily
implemented as a post-processing step to any existing risk model, which also
helps circumvent common challenges in implementing online learning such as
delayed outcomes [19] and inability to make frequent updates [24].

We start by formally introducing our optimal experimental design framework. We
provide a computationally lightweight approach to learn optimal assignment
policies and give statistical guarantees for its finite-sample performance.
Our policies can be implemented as a simple post-processing step on top of any
existing means of scoring individual need. Then, we conduct an empirical study
using data from two human service settings in Allegheny County, Pennsylvania.
We analyze the tradeoff between targeting and learning in this setting, and
find that, under optimized designs, the tradeoff between these two goals is
often quite favorable. For examples, designs at the Pareto frontier computed
by our method are often able to provide 90% of the best possible performance
in treating high-need individuals, while enabling randomization-based, gold-
standard estimates of the average treatment effect at sample sizes within a
factor of two of what a RCT would require. There is no way completely avoid
difficult choices between targeting and learning, and the right balance to
strike will inevitably be sensitive to context and the needs of particular
communities. However, our results show that carefully chosen allocation rules
can substantially mitigate such conflicts, offering one route towards
evidence-based improvement of critical services.

##  2 Optimal allocation policies

Consider the problem of a policymaker who would like to determine a scheme for
allocating a limited quantity of a treatment or intervention, while balancing
multiple different goals. Specifically, they would like to both reach
individuals who are greatest need according to some pre-specified metric while
simultaneously learning about the average treatment effect that the
intervention offers. The policymaker chooses a function
$p(X):\mathcal{X}\to[0,1]$ which gives the probability of assigning each
individual treatment based on their features $X\in\mathcal{X}$. Treatment is
assigned to each individual independently with this probability, after which
their corresponding outcomes are observed. Finally, the decision maker
estimates the average treatment effect on some target population.

###  2.1 Formulation

Let $Y(0),Y(1)$ denote potential outcomes absent and with treatment,
respectively. We assume that $X,Y(0),Y(1)\sim\mathbb{P}$ iid for some joint
distribution $\mathbb{P}$. Let $\tau=\mathbb{E}[Y(1)-Y(0)]$ denote the ATE and
$\tau(X)=\mathbb{E}[Y(1)-Y(0)|X]$ denote the conditional average treatment
effect (CATE). We start by assuming that the decision maker wishes to estimate
the ATE with respect to the distribution $\mathbb{P}$, and later consider the
case where they wish to estimate the ATE on specific subpopulation. Let $u(X)$
denote a targeting utility function chosen by the decision maker which maps an
individual’s observed covariates to the utility of offering treatment to that
individual. In our running example, $u$ may be an estimate of the probability
of an adverse outcome absent treatment (i.e., $u(X)=\widehat{E}[Y(0)|X]$), but
our methods are agnostic as to how $u$ is chosen. We assume that $u$ is
normalized so that $u(X)\in[0,1]$ with probability 1.

To formalize our objective, we start by recalling the efficiency bound for the
variance of the ATE estimate [12, 16], given by

$\displaystyle\mathbb{V}_{\text{ATE}}=\mathbb{E}\left[\frac{\text{Var}(Y(1)|X)}{p(X)}+\frac{\text{Var}(Y(0)|X)}{1-p(X)}-(\tau(X)-\tau)^{2}\right].$

The efficiency bound quantifies the lower possible variance for estimating the
ATE. Since in experimental settings we will be able to use unbiased
estimators, this is also equivalent to the best possible mean-squared error.
By focusing on the efficiency bound, our formulation is agnostic to the exact
choice of estimator. We seek assignment probabilities $p(X)$ that minimize
this estimation error subject to a constraint on utility. However, the outcome
variance terms in the numerator typically cannot be estimated without
observations of the potential outcomes, i.e., before running the trial.
Suppose that both variances are upper bounded by some constant $C$. Then, we
have

$\displaystyle\mathbb{V}_{\text{ATE}}\leq
C\cdot\left(\mathbb{E}\left[\frac{1}{p(X)}+\frac{1}{1-p(X)}\right]-\mathbb{E}\left[(\tau(X)-\tau)^{2}\right]\right)$

and dropping all terms that do not depend on $p(X)$ implies that minimizing
this upper bound is equivalent to minimizing

$\displaystyle\mathbb{E}\left[\frac{1}{p(X)}+\frac{1}{1-p(X)}\right]$

which will be our surrogate objective. However, we remark that if estimates of
$\text{Var}(Y(\cdot)|X)$ happen to be available, they can easily be
incorporated into our framework and the resulting optimization problem. Given
this objective, we aim to find allocation probabilities which solve an
optimization problem of the form:

$\displaystyle\min_{p}\mathbb{E}\left[\frac{1}{p(X)}+\frac{1}{1-p(X)}\right]$
$\displaystyle\mathbb{E}[p(X)u(X)]\geq c$ (1)
$\displaystyle\mathbb{E}[p(X)]\leq b$ $\displaystyle
p(X)\in[\gamma,1-\gamma]\quad\forall X\in\mathcal{X}.$

The objective is to minimize our proxy for the variance of the ATE estimate.
The first constraint imposes that the assignment rule has expected utility at
least $c$ with respect to $u$. The second constraint enforces budget
feasibility, that at most a fraction $b$ of individuals are offered treatment.
Finally, we restrict the assignment probabilities to the interval
$[\gamma,1-\gamma]$ for a small constant $\gamma$ chosen by the user (since
the objective becomes undefined at $p(X)=0$ or 1).

This core formulation can also be extended with additional user-specified
constraints. For example, we may wish to impose a constraint on equity in
resource allocation across different population groups. Suppose that we
specify two subgroups $\mathcal{G}_{0},\mathcal{G}_{1}\subseteq X$. Natural
constraints could be that the groups have similar expected utility,

$\displaystyle|\mathbb{E}[p(X)u(X)|X\in\mathcal{G}_{0}]-\mathbb{E}[p(X)u(X)|X\in\mathcal{G}_{1}]|\leq\epsilon$
(2)

or are offered similar treatment probabilities,

$\displaystyle|\mathbb{E}[p(X)|X\in\mathcal{G}_{0}]-\mathbb{E}[p(X)|X\in\mathcal{G}_{1}]|\leq\epsilon.$
(3)

In general, our technical framework can accommodate any such constraints so
long as the resulting feasible set is convex in $p$ (as is the case for these
two examples). In what follows, we let the optimization problem have
constraints of the form

$\displaystyle\mathbb{E}[g_{j}(p(X_{i}),X_{i})]\leq c_{j}\quad j=1...J$

where $J$ is the total number of constraints. We assume that each function is
normalized so that $g_{j}(p(X_{i}),X_{i})\in[0,1]$ with probability 1 and
$g_{j}(p(X_{i}),X_{i})$ is 1-Lipschitz with respect to $p(X_{i})$. Both
conditions are easily enforced for all of the example constraints above.

There are two main difficulties in solving the above optimization problem.
First, it is over a functional decision variable $p$ (a mapping from
covariates to assignment probabilities). Second, the objective and constraints
are in terms of expectations over the data generating distribution, while in
practice we will only have access to finite samples. We next introduce
efficient algorithms to compute near-optimal policies with finite-sample
guarantees.

###  2.2 Computing optimal policies

Our aim is to find an assignment probability function $p$ that solves the
above optimization problem, given a sample $X_{1}...X_{n}\sim\mathbb{P}$. We
emphasize that our approach only requires unlabeled data to inform the
covariate distribution. The high-level idea is to use this sample to estimate
the optimal value of the dual parameter for each constraint. As each
individual arrives, we can then solve a separate optimization problem to
compute their assignment probability, balancing between the need to adhere to
the constraints (as represented by the dual variables) versus the variance
that this individual would contribute to the ATE estimate. For example, an
individual for whom $u(X)$ is large would have a larger dual term encouraging
assignment to treatment (in order to boost utility), which can be weighed
against the variance contributed by large assignment probabilities. To
formalize this idea, we take the dual of the population optimization problem
to obtain

$\displaystyle\max_{\lambda\geq
0}\min_{p\in[\gamma,1-\gamma]^{\mathcal{X}}}\mathbb{E}\left[\frac{1}{p(X)}+\frac{1}{1-p(X)}+\sum_{j=1}^{J}\lambda_{j}(g(p(X),X)-c_{j})\right]$

where $\lambda_{j}$ is the dual variable associated constraint $j$. The dual
has the attractive property that the inner objective is separable across $X$,
allowing us to push the min inside the expectation:

$\displaystyle\max_{\lambda\geq
0}\mathbb{E}\left[\min_{p(X)\in[\gamma,1-\gamma]}\frac{1}{p(X)}+\frac{1}{1-p(X)}+\sum_{j=1}^{J}\lambda_{j}(g(p(X),X)-c_{j})\right].$

Our strategy will be to produce estimates $\widehat{\lambda}$ of the the
optimal dual parameters on the training set by solving the sample problem

$\displaystyle\max_{\lambda\geq
0}\frac{1}{n}\sum_{i=1}^{n}\left[\min_{p(X_{i})\in[\gamma,1-\gamma]}\frac{1}{p(X_{i})}+\frac{1}{1-p(X_{i})}+\sum_{j=1}^{J}\lambda_{j}(g(p(X_{i}),X_{i})-c_{j})\right].$
(4)

This is a strongly convex optimization problem in $n$ variables that can
easily be solved using standard methods. Then, at test time, we compute $p(X)$
for each incoming individual $X$ by solving the inner minimization problem at
the optimal dual parameters, i.e., we compute

$\displaystyle\widehat{p}(X)=\text{argmin}_{p(X)\in[\gamma,1-\gamma]}\frac{1}{p(X)}+\frac{1}{1-p(X)}+\sum_{j=1}^{J}\widehat{\lambda}_{j}(g(p(X),X)-c_{j})$
(5)

separately for each individual and randomize them to be treated with
probability $\widehat{p}(X)$. Effectively, the dual parameters tell the test-
time algorithm how much to weight the constraints (e.g., utility and budget
considerations) compared to variance. One potentially desirable property of
this approach is that it does not require any joint computations over the
entire cohort of individuals who are candidates for treatment; the allocations
can be computed and sampled entirely separately. This may be necessary in
settings where individuals arrive in a rolling fashion, as in e.g. most
operational social or health services.

###  2.3 Finite-sample guarantees

We now turn to establishing the number of samples of $X$ that are required to
ensure that we obtain a policy which is both close to satisfying the
constraints, and near-optimal in terms of variance, with high probability. Let
the population optimal assignment probabilities be $p^{*}$. We obtain the
following result:

######  Proposition 1.

Given $n$ iid samples of $X$ from $\mathbb{P}$, let the solution to the sample
dual optimization problem 4 be $\widehat{\lambda}$ and suppose that for some
$d>0$, $||\widehat{\lambda}||_{\infty}\leq d$ with probability at least
$1-\delta_{1}$. Let $\widehat{p}$ be the policy obtained by solving the
associated Lagrangian for any given $X$. Let $p^{*}$ denote the optimal
solution to the population problem. Fix any $\epsilon,\delta_{2}>0$. In order
to guarantee that with probability at least $1-\delta_{1}-\delta_{2}$,

$\displaystyle\mathbb{E}\left[\frac{1}{\widehat{p}(X)}+\frac{1}{1-\widehat{p}(X)}\right]\leq\mathbb{E}\left[\frac{1}{p^{*}(X)}+\frac{1}{1-p^{*}(X)}\right]+\epsilon$
$\displaystyle\mathbb{E}[g_{j}(\widehat{p}(X),X)]\leq c_{j}+\epsilon\quad
j=1...J$

it suffices to have
$n=O\left(\frac{J^{3}d^{2}}{\epsilon^{2}}\log\frac{Jd}{\epsilon\delta_{2}}\right)$
samples.

Rearranging the theorem statement, the loss in both the objective and the
constraints shrinks with high probability at a rate of $O(n^{-\frac{1}{2}})$
when $J$ and $d$ are fixed. A proof is given the appendix. The main idea is
that optimal policies for this problem are parameterized just by the values of
the dual parameters. Notably, this allows us to escape any dependence on
“dimension” terms for the policy class except the number of constraints $J$.
By contrast, sample complexity guarantees for policy learning from
observational data typically require imposing a bound on a complexity measure
such as the VC dimension or covering number [5, 6, 30], regardless of whether
the optimal policy actually belongs to a small-dimensional class. In our
setting, we obtain convergence to the optimum at the root-$n$ parametric rate
without the need for a separate realizability assumption.

We remark that the convergence rate does depend on
$||\widehat{\lambda}||_{\infty}$, the maximum value of the optimal dual
parameters for the sample problem. Intuitively, the magnitude of the dual
variables quantifies how sensitive the objective function is to solutions that
leave some slack in the constraints due to sampling noise, e.g., slightly
underutilize the budget. For well-behaved constraint structures, this term can
be controlled using the fact that the objective has bounded gradients. As an
example, consider the case where the constraints are linear in $p$ (as are all
the constraints discussed above), represented as $\mathbb{E}[g_{j}(X)p(X)]\leq
c_{j}$ for functions $g_{j}$ that depend only on $X$. Let
$g(X_{i})=[g_{1}(X_{i})...g_{J}(X_{i})]$ collect the coefficients for all of
the constraints with respect to individual $i$. Note that $g$ is a random
variable which depends on the iid draws of the $X_{i}$. Suppose that $g$
satisfies a standard small ball condition from random matrix theory [21, 35]
that

$\displaystyle\inf_{||v||_{2}\leq
1}\Pr\left(|g(X_{i})^{T}v|\geq\alpha\right)\geq\beta$

for some $\alpha,\beta>0$. Roughly, this says that the entries are $g$ are not
too small with very high probability; e.g., in Problem 1 it requires that the
utility function is not too concentrated on a low-probability set of
individuals. Under this condition, the KKT system defining $\widehat{\lambda}$
is well-conditioned with high probability and we obtain

######  Corollary 1.

Suppose that the constraints are linear in $p$ and that $g(X_{i})$ obeys the
small ball condition with parameters $\alpha,\beta>0$. Then
$||\widehat{\lambda}||_{\infty}\leq\frac{\sqrt{2}}{\alpha\sqrt{\beta}\gamma^{2}}$
with probability $1-\Theta(\exp(-\beta^{2}n))$ and so
$n=O(\frac{J^{3}}{\epsilon^{2}}\frac{1}{\alpha^{2}\beta\gamma^{4}}\log\frac{J}{\alpha\beta\gamma\delta_{2}\epsilon})$
samples suffice for the guarantees of Proposition 1 to hold with probability
$1-\Theta(\exp(-\beta^{2}n))-\delta_{2}$.

###  2.4 Alternate estimands

In some settings, policymakers may wish to identify effects other than the
ATE. For example, they may wish to identify the average treatment effect only
for the $\alpha$-fraction of the population greatest risk for an adverse
outcome (the beneficiaries under need-based targeting), or some other subgroup
of particular interest. Our framework can be naturally modified to accommodate
other estimands. In particular, let $\mathcal{S}\subseteq\mathcal{X}$ be the
target population for which we wish to estimate the group average treatment
effect. The objective function becomes

$\displaystyle\mathbb{E}\left[\left(\frac{1}{p(X)}+\frac{1}{1-p(X)}\right)\Big{|}X\in\mathcal{S}\right]=\frac{1}{\Pr[X\in\mathcal{S}]}\cdot\mathbb{E}\left[1\left[X\in\mathcal{S}\right]\left(\frac{1}{p(X)}+\frac{1}{1-p(X)}\right)\right]$

which counts individuals towards the variance only if they belong to the
target population. The modified optimization problem can then be solved
identically to as discussed above.

##  3 Results

We apply our methods to the design of evaluations for interventions in a human
services setting. We use data from the Allegheny County Department of Human
Services, which administers programs for mental and behavioral health,
substance use treatment, housing assistance, support for formerly incarcerated
people, aging, and more. The department serves a population of over 1.2
million people and allocates a total budget of more than $1 billion across
such programs. It regularly uses predictive risk models to prioritize
individuals with greater need for access to program with limited resources,
but also faces the overall challenge of determining which programs are working
in order to concentrate resources on more effective programs. We conduct
simulations using two datasets: one on individuals exiting jail who may be
eligible for programs aiming to prevent jail reentry, and a second on
individuals eligible for public housing assistance. For each dataset, the
utility function $u$ is set to be the risk of an adverse outcome absent
treatment, estimated via a random forest. For the first domain, the outcome is
one-year reentry and for the second the outcome is having at least four
emergency department visits in the following year. We then simulated a
hypothetical intervention with specified budget $b$ and a treatment effect
given by $\tau(X)=\beta\cdot\Pr(Y(0)=1|X)$, where $\beta$ is the relative
reduction in the frequency of adverse outcomes caused by the treatment and
$\Pr(Y(0)=1|X)$ is estimated via the random forest. Our main results are shown
for $\beta=0.1$. Results for other values are qualitatively similar and are
given in the appendix, along with details of the setup.

We evaluate our designs on two metrics. First, utility from targeting,
presented in terms of the fraction of individuals with an adverse baseline
outcome who would be allocated treatment (i.e., a measure of recall or
sensitivity). The second metric is the variance with which we can estimate the
ATE. To provide a concrete interpretation for the variance, we present it in
terms of the sample size needed to power an estimate. Specifically, we assume
standard Wald-type confidence intervals and find the sample size needed to
detect an effect of at least $\tau$ with 5% type-1 error and 80% power. We
benchmark our designs against two points. First, the sample size needed to
power a standard RCT that randomizes the same treatment budget uniformly
across individuals. Second, the sample size needed to power a regression
discontinuity (RD) estimate of the local average treatment effect around the
budget cutoff. While the RD is not directly comparable as it estimates a
different effect, it provides a reference point that is commonly used when
policies like need-based targeting create clear discontinuities. Sample size
calculations for the RD follow the approach of [28] and [7], which are based
on the optimal bandwidth calculation suggested by [15].

Figure 1: Utility vs sample size required to estimate the average treatment
effect. Top row: housing dataset. Bottom row: reentry dataset. Columns from
left to right: $b=0.15,0.3,0.45$. Each blue curve is produced by varying the
value of the utility constraint, solving for the corresponding optimal policy
at each point, and calculating the variance of the corresponding ATE estimate
(presented in terms of sample size required to power an estimate). The purple
dot shows the sample size and utility of running a RCT which randomizes
individuals uniformly with the same budget. The gray dashed line shows the
utility of need-based targeting (without randomization). The gold diamond
shows the sample size required to power a regression discontinuity estimate of
the local ATE after need-based targeting. The red triangle shows the point on
the curve at which the optimized policy obtains 90% of the best-possible
utility.

Figure 1 gives our primary simulation result: the Pareto frontier between
sample size and targeting utility as computed by our method. That is, every
point on the curve corresponds to a specific set of assignment probabilities
output as the solution to an instance of the optimization problem detailed
above. The curve is traced out by varying the value of the constraint on
utility. Shaded regions give 95% confidence bands computed using the
multiplier bootstrap [33, 20] with 10,000 replicates. We observe that the
tradeoff between these two objectives is relatively favorable, with a strongly
concave shape to the curve. That is, most of the gap in utility between the
RCT and need-based targeting can be made up with relatively small costs to
sample size. Intuitively, this behavior is expected because utility increases
linearly with $p(X)$ while variance increases much faster than linearly as
$p(X)$ approaches 1. Quantitatively, the optimized policy can achieve 90% of
the best possible utility using approximately 1.5-3 times the samples required
for a RCT. By comparison, we find that the RD requires 4-10 times the sample
size of a RCT, and often over 3 times that of the “90% utility” point for our
method. This is a consequence of the fact that the RD can only make use of
samples relatively close to the decision boundary. Accordingly, while a RD may
be attractive a policymaker who places a very high premium on targeting, it
imposes significant costs in terms of sample size requirements.

Figure 2: Visualization of the optimal policy at varying levels of the utility
constraint. Left: housing dataset. Right: reentry dataset. Each curve plots
the optimal treatment assignment probability $p(X)$ as a function of the
individual’s utility score $u(X)$ (for the specified value of the overall
utility constraint). The vertical dashed line gives the $(1-b)$-quantile of
$u$, where $b$ is the fraction of individuals treated. Both plots are for
$b=0.3$.

Figure 2 shows examples of the policies output by our method at varying levels
of the utility constraint, plotting the optimal $p(X)$ as a function of an
individual’s utility value $u(X)$. The optimal policies take an intuitive
S-shaped curve with steepness that depends on the utility constraint. At
larger values of the constraint, the optimal policy effectively redistribute
resources from individuals whose utility value lies just over the cutoff for
need-based targeting to individuals in the region below the cutoff.

Figure 3: Ability to estimate heterogeneous treatment effects for groups
defined by risk strata. Top: housing data. Bottom: reentry data. Left:
relative variance of ATE estimation at each level of $u$ compared to the
whole-population mean. Right: simulation of a setting where we aim to estimate
the ATE for the 30% highest-risk individuals. The blue curve gives the sample
size-utility tradeoff for the original policy which optimizes estimation of
the ATE for the whole population, while the orange curve gives the same
tradeoff for a policy optimized to estimate the ATE just on the high-risk
subgroup.

Our results so far have aimed at estimation of the ATE on the entire
population. We next turn to the ability to estimate effects for more specific
subpopulations. Figure 3 shows the pointwise value of the efficiency bound for
each of the same optimized policies as a function of the utility $u(X)$. The
variance of a group average treatment effect is obtained by integrating this
curve over the population of interest so that the whole-population ATE has
variance given by the integral over the entire population. We normalize the
curve so that the whole-population ATE has value 1, allowing us to interpret
the curve as the relative increase or decrease in sampling variance if we
tried to estimate the group average treatment effect (GATE) over a particular
subset of $\mathcal{X}$. We find that our designs have greatest power to
estimate GATEs for levels of the utility function near the budget cutoff,
while evidence regarding GATEs at one extreme or another would accrue at a
rate of up to 1.5 times slower than the mean. If a policymaker specifically
hopes to estimate a particular GATE, e.g. for higher-need individuals, they
can modify the objective function as described in Section 2.4. The right-hand
column of Figure 3 shows an example of this, where we simulate the goal of
estimating the GATE for the target population
$\mathcal{S}_{2}=\\{x:u(x)\geq\text{quantile}_{1-b}(u)\\}$, denoting the
$b$-highest need subgroup. We compare the utility-sample size tradeoff curve
for the policy optimized with respect to $\mathcal{S}_{2}$ compared to the
original policy, which optimizes for estimation of the whole-population ATE
($\mathcal{S}_{1}$). If the policymaker is willing to commit to the more
specific estimand, they are able to gain additional utility by forgoing
exploration on the remainder of the population.

Figure 4: Impact of fairness constraints. Top: housing dataset. Bottom:
reentry dataset. The left-hand plot of each row shows the utility of the
optimal policies for each group, i.e., the fraction of members of each group
with an adverse outcome who receive treatment. The $x$ axis varies the average
utility across the entire population (i.e., the value of the utility
constraint). Solid lines show policies without fairness constraints, while
dashed lines show policies with fairness constraints. The right-hand column
shows the percentage increase in variance (i.e., the objective function) that
results from imposing fairness constraints, again as a function of the value
of the utility constraint.

Finally, Figure 4 shows the consequences of adding fairness constraints (based
on Equation 2) to the optimization problem. We take the groups to consist of
White and Black individuals. We observe that the optimal policies without
fairness constraints imply slightly higher average utility for Black
individuals than White. Imposing fairness constraints narrows the difference,
at only a nominal cost in terms of estimation variance. The small cost of
imposing fairness constraints is attributable to the fact that the two groups
have relatively similar distributions of the utility function in our dataset.
In other settings, a larger “price of fairness” could arise if a decision
maker specifies a utility function which takes systematically larger values on
one of the groups.

##  4 Discussion

Designing effective interventions in socially critical domains often requires
policymakers to confront difficult tradeoffs between competing objectives.
Chief among these is the need to balance offering the highest-quality services
in the present against the potential to learn more and improve in the future.
This paper investigates a specific instantiation of this dilemma, in the form
of balancing between treating individuals who are judged to have higher need
against the ability to learn about the average treatment effect of the
program. We provide algorithms to minimize the error of ATE estimates subject
to a constraint on the expected utility of the policy in treating high-need
individuals. We find that by explicitly optimizing the tradeoff between these
competing goals, there is substantial room to navigate between the all-or-
nothing extremes of standard RCTs and targeting purely based on estimated
need.

In the future, such issues may grow in importance due to the increasing use of
predictive models in policy, healthcare, and social service settings. These
models are typically trained to classify baseline outcomes as accurately as
possible. The availability of such a model creates a strong impetus to
allocate treatment to the individuals deemed at highest risk. However, our
results can be seen as a caution that pure predictive accuracy is not the only
salient goal for such systems: giving up a marginal amount of alignment
between allocations and risk prediction can create large benefits in terms of
other objectives for program design (in our case, rigorous evaluation). In
this sense, our results dovetail with [18]’s normative argument that resource
allocations based on machine learning predictions should be randomized. Our
approach can be seen as giving the most effective way to implement such
randomization when the goal is to control the tradeoff between utility and
estimating treatment effects.

While risk prediction can help improve the efficiency with which limited
resources are used, prediction is ultimately only one component of successful
interventions. Evaluations of overall program effectiveness are highly
valuable to guide larger-scale strategic decisions about how to design program
offerings in the first place. Indeed, such higher-level decisions may be more
consequential for overall impact than refining individual-level targeting
decisions [25]. A broader conclusion from our work is that the design of
algorithmic systems for resource allocation should explicitly account for such
goals beyond predictive accuracy. Constrained optimization frameworks like
ours provide a means to build in additional objectives which reflect the role
that predictive models play in a larger system. Accounting for this larger
picture can help algorithm design play a more fruitful role in the provision
of public services.

## Acknowledgments

BW acknowledges support from the AI2050 program at Schmidt Sciences (Grant
#G-22-64474) and the AI Research Institutes Program funded by the National
Science Foundation under AI Institute for Societal Decision Making (AI-SDM),
Award No. 2229881. BW also thanks participants at the BIRS Workshop on
Bridging Prediction and Intervention Problems in Social Systems for fruitful
conversations.

## References

  * [1] Alekh Agarwal et al.  “Taming the monster: A fast and simple algorithm for contextual bandits”  In _International Conference on Machine Learning_ , 2014, pp. 1638–1646  PMLR
  * [2] Emily Aiken et al.  “Machine learning and phone data can improve targeting of humanitarian aid”  In _Nature_ 603.7903 Nature Publishing Group UK London, 2022, pp. 864–870
  * [3] Vivi Alatas et al.  “Targeting the poor: evidence from a field experiment in Indonesia”  In _American Economic Review_ 102.4 American Economic Association, 2012, pp. 1206–1240
  * [4] Susan Athey, Niall Keleher and Jann Spiess  “Machine learning who to nudge: causal vs predictive targeting in a field experiment on student financial aid renewal”  In _arXiv preprint arXiv:2310.08672_ , 2023
  * [5] Susan Athey and Stefan Wager  “Policy learning with observational data”  In _Econometrica_ 89.1 Wiley Online Library, 2021, pp. 133–161
  * [6] Victor Chernozhukov, Mert Demirer, Greg Lewis and Vasilis Syrgkanis  “Semi-parametric efficient policy learning with continuous actions”  In _Advances in Neural Information Processing Systems_ 32, 2019
  * [7] John Deke and Lisa Dragoset  “Statistical Power for Regression Discontinuity Designs in Education: Empirical Estimates of Design Effects Relative to Randomized Controlled Trials. Working Paper.”  In _Mathematica Policy Research, Inc._ ERIC, 2012
  * [8] Alexis Diamond et al.  “Estimating poverty rates in target populations: An assessment of the simple poverty scorecard and alternative approaches”  In _World Bank Policy Research Working Paper_ , 2016
  * [9] Maria Dimakopoulou, Zhengyuan Zhou, Susan Athey and Guido Imbens  “Balanced linear contextual bandits”  In _Proceedings of the AAAI Conference on Artificial Intelligence_ 33.01, 2019, pp. 3445–3453
  * [10] Dylan Foster and Alexander Rakhlin  “Beyond UCB: Optimal and efficient contextual bandits with regression oracles”  In _International Conference on Machine Learning_ , 2020, pp. 3199–3210  PMLR
  * [11] Margaret Grosh and Judy L Baker  “Proxy means tests for targeting social programs”  In _Living standards measurement study working paper_ 118, 1995, pp. 1–49
  * [12] Jinyong Hahn  “On the role of the propensity score in efficient semiparametric estimation of average treatment effects”  In _Econometrica_ JSTOR, 1998, pp. 315–331
  * [13] Johannes Haushofer et al.  “Targeting impact versus deprivation”, 2022
  * [14] Sara B Heller, Benjamin Jakubowski, Zubin Jelveh and Max Kapustin  “Machine learning can predict shooting victimization well enough to help prevent it”, 2022
  * [15] Guido Imbens and Karthik Kalyanaraman  “Optimal bandwidth choice for the regression discontinuity estimator”  In _The Review of economic studies_ 79.3 Oxford University Press, 2012, pp. 933–959
  * [16] Guido Imbens and Jeffrey M Wooldridge  “Recent developments in the econometrics of program evaluation”  In _Journal of economic literature_ 47.1 American Economic Association, 2009, pp. 5–86
  * [17] Kosuke Inoue, Susan Athey and Yusuke Tsugawa  “Machine-learning-based high-benefit approach versus conventional high-risk approach in blood pressure management”  In _International Journal of Epidemiology_ 52.4 Oxford University Press, 2023, pp. 1243–1256
  * [18] Shomik Jain, Kathleen Creel and Ashia Wilson  “Scarce Resource Allocations That Rely On Machine Learning Should Be Randomized”  In _International Conference on Machine Learning_ , 2024
  * [19] Pooria Joulani, Andras Gyorgy and Csaba Szepesvári  “Online learning under delayed feedback”  In _International conference on machine learning_ , 2013, pp. 1453–1461  PMLR
  * [20] Edward H Kennedy  “Nonparametric causal effects based on incremental propensity score interventions”  In _Journal of the American Statistical Association_ 114.526 Taylor & Francis, 2019, pp. 645–656
  * [21] Guillaume Lecué and Shahar Mendelson  “Sparse recovery under weak moment assumptions”  In _Journal of the European Mathematical Society_ 19.3, 2017, pp. 881–904
  * [22] Lydia T Liu, Serena Wang, Tolani Britton and Rediet Abebe  “Reimagining the machine learning life cycle to improve educational outcomes of students”  In _Proceedings of the National Academy of Sciences_ 120.9 National Acad Sciences, 2023, pp. e2204781120
  * [23] Ian Pan et al.  “Machine learning for social services: a study of prenatal case management in Illinois”  In _American journal of public health_ 107.6 American Public Health Association, 2017, pp. 938–944
  * [24] Vianney Perchet, Philippe Rigollet, Sylvain Chassang and Erik Snowberg  “Batched bandit problems”  In _Annals of Statistics_ , 2016
  * [25] Juan Carlos Perdomo  “The Relative Value of Prediction in Algorithmic Decision Making”  In _International Conference on Machine Learning_ , 2024
  * [26] Laura Petry et al.  “Associations between the Vulnerability Index-Service Prioritization Decision Assistance Tool and returns to homelessness among single adults in the United States”  In _Cityscape_ 23.2 JSTOR, 2021, pp. 293–324
  * [27] Esther Rolf et al.  “Balancing competing objectives with noisy data: Score-based classifiers for welfare-aware machine learning”  In _International Conference on Machine Learning_ , 2020, pp. 8158–8168  PMLR
  * [28] Peter Z Schochet  “Statistical power for regression discontinuity designs in education evaluations”  In _Journal of Educational and Behavioral Statistics_ 34.2 Sage Publications Sage CA: Los Angeles, CA, 2009, pp. 238–266
  * [29] Marybeth Shinn and Molly K Richard  “Allocating homeless services after the withdrawal of the vulnerability index–service prioritization decision assistance tool”  In _American Journal of Public Health_ 112.3 American Public Health Association, 2022, pp. 378–382
  * [30] Adith Swaminathan and Thorsten Joachims  “Batch learning from logged bandit feedback through counterfactual risk minimization”  In _The Journal of Machine Learning Research_ 16.1 JMLR. org, 2015, pp. 1731–1755
  * [31] Halil Toros and Daniel Flaming  “Prioritizing which homeless people get housing using predictive algorithms”  In _Available at SSRN 2960410_ , 2017
  * [32] Rhema Vaithianathan and Chamari I Kithulgoda  “Using predictive risk modeling to prioritize services for people experiencing homelessness in Allegheny County: Methodology update”  Auckland University of Technology, Centre for Social Data Analytics, 2020
  * [33] Aad W Van Der Vaart, Jon A Wellner, Aad W Vaart and Jon A Wellner  “Weak convergence”  Springer, 1996
  * [34] Martin J Wainwright  “High-dimensional statistics: A non-asymptotic viewpoint”  Cambridge university press, 2019
  * [35] Pavel Yaskov  “Controlling the least eigenvalue of a random Gram matrix”  In _Linear Algebra and its Applications_ 504 Elsevier, 2016, pp. 108–123

## Appendix

##  Appendix A Details of empirical study

We use two datasets provided by Allegheny County Department of Human Services.
The first covers 9213 individuals who were eligible in the past for public
housing assistance (prior to the creation of a new housing program). We use
40% of the data to train a random forest classifier to predict the probability
of having at least 4 emergency department visits in the next year. The base
rate of this outcome is approximately 54%. We then use the remaining 60% of
the data to estimate the performance of the optimal policy. The covariates $X$
are a set of 83 features collected by the county from administrative data
sources, including age, education level, previous appearances in the court
system, and past utilization of behavioral health, housing, or medicaid
services. We simulate a constant treatment effect on a binary outcome with
baseline frequency $\Pr(Y(0)=1)=0.54$ (matching the empirical frequency of
reentry in the data) and $\Pr(Y(1)=1)=0.54-\tau$.

The second dataset contains the outcomes of 76052 incarcerated people released
from jail. The probability of reentry within the next year in our data is
approximately 39%. We predict status-quo reentry risk using a random forest
classifier, and set the utility function $u$ to be the predicted reentry risk.
We use 60% of the data to train the predictive model and the remaining 40% to
estimate the performance of the optimal policy. We simulate a constant
treatment effect on a binary outcome with baseline frequency
$\Pr(Y(0)=1)=0.39$ (matching the empirical frequency of reentry in the data)
and $\Pr(Y(1)=1)=0.39-\tau$.

To calculate sample sizes for the regression discontinuity (RD) estimates, we
follow a procedure based on [28] and [7]. This requires two steps. First, we
use the distribution of $u(X)$ to estimate the design effect of a standard
OLS-based RD estimator compared to a RCT. Second, we estimate the optimal
bandwidth for a locally linear estimator using the method of [15] in order to
determine what fraction of the sample would be used. There are two important
caveats for this analysis. First, as discussed above, the RD targets a
different and incomparable estimand (the treatment effect for individuals at
the margin, versus the average effect). Second, the RD returns a potentially
biased estimate, as it uses a locally linear model with a bandwidth that
optimizes an empirical bias-variance tradeoff for the MSE. By contrast, our
estimates are guaranteed to be unbiased (as the propensity scores are known)
and so accrue error only due to variance. We ignore this bias in power
calculations, erring towards slightly more optimistic results for the RD.

##  Appendix B Additional simulation results

In Figure 5 we present versions of our main empirical results that vary the
hypothetical treatment effects. We fix the budget $b=0.3$ and present results
for $\beta=0.05$ and $\beta=0.15$ (compared to our main results for
$\beta=0.1$). The main conclusions are unchanged, though as expected all
designs require more samples in order to be powered to detect a smaller
effect.

Figure 5: Utility-sample size tradeoff curves for $\beta=0.05$ (left) and
$\beta=0.15$ (right). Top row: housing data. Bottom row: reentry data.

##  Appendix C Proofs

We first introduce some additional notation. Define
$f(p(X))=\frac{1}{p(X)}+\frac{1}{1-p(X)}$. Define $p(X,\lambda)$ to be the
optimal $p$ with fixed dual parameters $\lambda$, i.e., the solution to
Equation 5. Define $h_{j}(\lambda)=\mathbb{E}[g(p(X,\lambda),X)]$ and
$h_{j}^{n}(\lambda)=\frac{1}{n}\sum_{i=1}^{n}g(p(X_{i},\lambda),X_{i})$.

######  Lemma 1.

$\frac{1}{n}\sum_{i=1}^{n}f(p(X_{i}))$ is 32-strongly convex in
$p(X_{1})...p(X_{n})$.

###### Proof.

Taking second derivatives, we have that

$\displaystyle\frac{\partial^{2}f}{\partial
p(X_{i})^{2}}=\frac{2}{(1-p(X_{i}))^{3}}+\frac{2}{p(X_{i})^{3}}\geq 32.$

Since the summation is separable, its Hessian is a diagonal matrix with
entries lower bounded by 32, implying that $f$ must be strongly convex. ∎

######  Lemma 2.

For all $j$, $h_{j}$ and $h_{j}^{n}$ are both $\frac{1}{32}-$Lipschitz in the
$\ell_{1}$ norm.

###### Proof.

Within any range where the optimal $p(X,\lambda)$ is on the boundary of the
feasible set, $p(X,\lambda)$ does not depend on the dual variables. If the
optimal solution is not on the boundary, it is characterized equivalently by
the solution to the first-order condition

$\displaystyle
m(p(X),\lambda)\triangleq-\frac{1}{p(X)^{2}}+\frac{1}{(1-p(X))^{2}}+\sum_{j=1}^{J}\nabla
g_{j}(p(X),X)\lambda_{j}=0.$

We will bound the derivative $\frac{\partial
p(X,\lambda)}{\partial\lambda_{j}}$ for the set of $\lambda$ where
$p(X,\lambda)\in(\gamma,1-\gamma)$. When
$p(X,\lambda)\in\\{\gamma,1-\gamma\\}$, $\frac{\partial
p(X,\lambda)}{\partial\lambda_{j}}$ is either undefined (on the measure zero
set of boundary points where $p(X,\lambda)$ is not differentiable) or else
$\frac{\partial p(X,\lambda)}{\partial\lambda_{j}}=0$ (over regions where
$p(X,\lambda)$ is constant at either $\gamma$ or $1-\gamma$ and hence does not
depend on $\lambda$). Accordingly, to bound the Lipschitz constant, it
suffices to bound $\frac{\partial p(X,\lambda)}{\partial\lambda_{j}}$ just
over the region where $p(X,\lambda)$ is given by the solution to the first
order condition. Within this region, applying the implicit function theorem to
the first-order condition yields that

$\displaystyle\frac{\partial
p(X,\lambda)}{\partial\lambda_{j}}=-\frac{\partial m(p(X),\lambda)}{\partial
p(X)}^{-1}\frac{\partial m(p(X),\lambda)}{\partial\lambda_{j}}$

where we can bound $\frac{\partial m}{\partial p(X)}\geq 32$ (via Lemma 1) and
$\left\lvert\frac{\partial m}{\partial\lambda_{j}}\right\rvert=|\nabla
g_{j}(p(X),X)|\leq 1$ by assumption that $g_{j}$ is Lipschitz. Combining, we
obtain

$\displaystyle\left\lvert\frac{\partial
p(X,\lambda)}{\partial\lambda_{j}}\right\rvert\leq\frac{1}{32}\quad\forall
j=1...J.$

Using again the assumption that the $g_{j}$ are 1-Lipschitz in $p$, we have
that

$\displaystyle\left\lvert\frac{\partial
g_{j}(p(X,\lambda))}{\partial\lambda_{j}}\right\rvert\leq\left\lvert\frac{\partial
g_{j}(p(X,\lambda))}{\partial
p(X,\lambda)}\right\rvert\left\lvert\frac{\partial
p(X,\lambda)}{\partial\lambda_{j}}\right\rvert\leq\frac{1}{32}$

and so we have proved that for each $g_{j}$,
$||\nabla_{\lambda}g_{j}(p(X,\lambda))||_{\infty}\leq\frac{1}{32}$. Taking
expectations over $\mathbb{P}$ and the empirical distribution respectively
yields that $||\nabla_{\lambda}h_{j}(\lambda))||_{\infty}\leq\frac{1}{32}$ and
$||\nabla_{\lambda}h_{j}^{n}(\lambda))||_{\infty}\leq\frac{1}{32}$. Finally,
the conclusion in the lemma follows because the $\ell_{\infty}$ norm is dual
to the $\ell_{1}$. ∎

###### Proof of Proposition 1.

We start by proving that the expectations in the constraints are well-
approximated with high probability. The main idea is to discretize the range
of the dual variables, since by assumption $\widehat{\lambda}\in[0,d]^{J}$
with probability at least $1-\delta_{1}$. Let
$N([0,d]^{J},\epsilon,||\cdot||_{1})$ denote the $\ell_{1}$ covering number of
the set $[0,d]^{J}$. Let $B_{1}$ be the $\ell_{1}$ unit ball in $R^{J}$.
Standard bounds on covering numbers (e.g., [34], Lemma 5.7) imply that
$N([0,d]^{J},\epsilon,||\cdot||_{1})\leq\left(1+\frac{2}{\epsilon}\right)^{J}\frac{\text{vol}([0,d]^{J})}{\text{vol}(B_{1})}$.
Since $\text{vol}(B_{1})=\frac{2^{J}}{J!}$ and $\text{vol}([0,d]^{J})=d^{J}$,
we obtain that

$\displaystyle\log N([0,d]^{J},\epsilon,||\cdot||_{1})\leq
J\log\left(1+\frac{2}{\epsilon}\right)+\log
J!+J\log\frac{d}{2}=\Theta\left(J\left(\log\frac{1}{\epsilon}+\log J+\log
d\right)\right).$

We fix a $\epsilon$-covering $\Lambda$ of at most this size. We have that each
constraint function $h_{j}$ is $\frac{1}{32}-$Lipschitz in the $\ell_{1}$
norm. Accordingly, we condition on the event that

$\displaystyle|h_{j}^{n}(\lambda)-h_{j}(\lambda)|\leq\epsilon\quad\forall\lambda\in\Lambda,j=1...J$
(6)

which by a standard Hoeffding bound occurs with probability at least
$1-2\exp(-2n\epsilon^{2})$ for each $(\lambda,J)$ individually, and hence with
probability at least $1-2J|\Lambda|\exp(-2n\epsilon^{2})$ in total via union
bound. We also condition on the event that $||\widehat{\lambda}||_{\infty}\leq
d$, which occurs with probability at least $1-\delta_{1}$ by assumption. Since
$\widehat{\lambda}\geq 0$ by dual feasibility, there must be a point
$\lambda^{\prime}\in\Lambda$ with
$||\widehat{\lambda}-\lambda^{\prime}||_{1}\leq\epsilon$. We have via triangle
inequality that

$\displaystyle|h^{n}_{j}(\widehat{\lambda})-h_{j}(\widehat{\lambda})|\leq|h^{n}_{j}(\widehat{\lambda})-h^{n}_{j}(\lambda^{\prime})|+|h^{n}_{j}(\lambda^{\prime})-h_{j}(\lambda^{\prime})|+|h_{j}(\lambda^{\prime})-h_{j}(\widehat{\lambda})|.$

Since $||\widehat{\lambda}-\lambda^{\prime}||_{1}\leq\epsilon$, Lemma 2
implies that both the first and third terms are at most $\frac{\epsilon}{32}$.
Event 6 implies that the third term is at most $\epsilon$. Summing up, we have
that

$\displaystyle|h^{n}_{j}(\widehat{\lambda})-h_{j}(\widehat{\lambda})|\leq\frac{17}{16}\epsilon\quad\forall
j=1...J$ (7)

with probability at least $1-\delta_{1}-2J|\Lambda|\exp(-2n\epsilon^{2})$. On
this event,

$\displaystyle h_{j}(\widehat{\lambda})\leq
h^{n}_{j}(\widehat{\lambda})+\frac{17}{16}\epsilon\leq
c_{j}+\frac{17}{16}\epsilon$

where the last line uses primal feasibility for the sample problem.

Next, we turn to showing that the objective function value is near-optimal.
Essentially, the challenge is that if the sample dual variables cause errors
in the other direction, making the constraints overly conservative, this may
result in a worse value of the objective function. Writing out the population
dual objective function and using optimality of $\lambda^{*}$ for the
maximization, we have that

$\displaystyle\left(\mathbb{E}[f(\widehat{p}(X)]+\sum_{j}(\mathbb{E}[g_{j}(\widehat{p}(X),X)]-c_{j})\widehat{\lambda}_{j}\right)-\left(\mathbb{E}[f(p^{*}(X)]+\sum_{j}(\mathbb{E}[g_{j}(p^{*}(X),X)]-c_{j})\lambda^{*}_{j}\right)\leq
0.$

Complementary slackness for the population problem implies that
$\sum_{j}(\mathbb{E}[g_{j}(p^{*}(X),X)]-c_{j})\lambda^{*}_{j}=0$, so we have

$\displaystyle\mathbb{E}[f(\widehat{p}(X)]-\mathbb{E}[f(p^{*}(X)]\leq\sum_{j}-(\mathbb{E}[g_{j}(\widehat{p}(X),X)]-c_{j})\widehat{\lambda}_{j}.$

Now, for each constraint $j$, we consider two cases. Intuitively, these divide
whether there is a large or small amount of slack in the $j$th constraint. If
there is a small amount of slack, this cannot hurt the objective value too
much because the dual variables (and hence the “shadow price” for the
constraint) are bounded. If there is a large amount slack, then this implies
that there is also slack in the sample problem and so leaving slack must not
have hurt the objective value. More formally, the first case is that
$\mathbb{E}[g_{j}(\widehat{p}(X),X)]-c_{j}\geq-\frac{17}{16}\epsilon$. Since
$\widehat{\lambda}_{j}\geq 0$ this implies that

$\displaystyle-(\mathbb{E}[g_{j}(\widehat{p}(X),X)]-c_{j})\widehat{\lambda}_{j}\leq\frac{17}{16}\epsilon\cdot\widehat{\lambda}_{j}.$

The second case is that
$\mathbb{E}[g_{j}(\widehat{p}(X),X)]-c_{j}<-\frac{17}{16}\epsilon$. Using
Equation 7, we have that

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}g_{j}(\widehat{p}(X_{i}),X_{i})-c_{j}=h^{n}_{j}(\widehat{\lambda})-c_{j}<h_{j}(\widehat{\lambda})-c_{j}+\frac{17}{16}\epsilon<0.$

In this case, complementary slackness for the sample problem implies that
$\widehat{\lambda}_{j}=0$ and so
$(\mathbb{E}[g_{j}(\widehat{p}(X),X)]-c_{j})\widehat{\lambda}_{j}=0$.
Combining these cases and summing over the two constraints, we conclude that

$\displaystyle\mathbb{E}[f(\widehat{p}(X)]-\mathbb{E}[f(p^{*}(X)]\leq
J\frac{17}{16}\epsilon\cdot||\widehat{\lambda}_{j}||_{\infty}\leq\frac{17Jd}{16}\epsilon.$

Rescaling $\epsilon$ and setting the failure probability for event 6 in order
to obtain the guarantees in the theorem statement, we require

$\displaystyle
n=O\left(\frac{J^{2}d^{2}}{\epsilon^{2}}\left(\log\frac{J}{\delta_{2}}+J\log\frac{Jd}{\epsilon}\right)\right)=O\left(\frac{J^{3}d^{2}}{\epsilon^{2}}\log\frac{Jd}{\epsilon\delta_{2}}\right).$

∎

###### Proof of Corollary 1.

Strong convexity of the objective function implies that there are a unique set
of sample optimal dual parameters $\widehat{\lambda}$. The duals must solve
the stationarity condition

$\displaystyle\sum_{j=1}^{J}\lambda_{j}\nabla_{p(X_{i})}\left(\frac{1}{n}\sum_{k=1}^{n}g_{j}(p(X_{k}),X_{k})\right)=\nabla_{p(X_{i})}\left(\frac{1}{n}\sum_{k=1}^{n}f(p(X_{k}))\right)\quad\forall
i=1...n$

which, using separability of the objective and constraints, reduces to

$\displaystyle\sum_{j=1}^{J}\lambda_{j}\nabla_{p(X_{i})}g_{j}(p(X_{i}),X_{i})=\nabla_{p(X_{i})}f(p(X_{i}))\quad\forall
i=1...n.$

Let $G$ denote the matrix

$\displaystyle G=\begin{bmatrix}g(X_{1})\\\ g(X_{2})\\\ \vdots\\\
g(X_{n})\end{bmatrix}$

where $g(X_{i})$ was defined earlier to be the vector of coefficients for the
linear constraints $[g_{1}(X_{i})...g_{J}(X_{i})]$. Note that each row is a
iid random variable since we assume that the $X_{i}$ are iid. Finally, let $F$
denote the right-hand side vector

$\displaystyle F=\begin{bmatrix}\nabla_{p(X_{1})}f(p(X_{1}))\\\
\nabla_{p(X_{2})}f(p(X_{2}))\\\ \vdots\\\
\nabla_{p(X_{n})}f(p(X_{n}))\end{bmatrix}$

We can now characterize the duals as the solution of the linear system

$\displaystyle G\widehat{\lambda}=F.$

We start by noting that under the small-ball condition

$\displaystyle\inf_{||v||_{2}\leq 1}\Pr\left(|v^{T}\nabla
g(X_{i})|\geq\alpha\right)\geq\beta$

we have via [21] (using the statement of the result in [35])

$\displaystyle\Pr\left(\sigma_{\text{min}}(n^{-1}G^{T}G)\geq\frac{\alpha^{2}\beta}{2}\right)\geq
1-\Theta(\exp(-\beta^{2}n)).$

where $\sigma_{\text{min}}(\cdot)$ denotes the smallest singular value of a
matrix. We condition on this event in what follows. We apply the singular
value decomposition $G=U\Sigma V^{T}$. Let $\sigma_{1}...\sigma_{p}$ be the
singular values of $G$. The singular values of $G^{T}G$, which are controlled
under the small ball condition, are $\sigma_{1}^{2}...\sigma_{p}^{2}$. We have
that

$\displaystyle\min_{i=1...p}\sigma_{i}^{2}\geq n\frac{\alpha^{2}\beta}{2}.$

Since all of the singular values are bounded away from 0, $G$ has full column
rank and we can write the solution to the linear system defining
$\widehat{\lambda}$ as

$\displaystyle\widehat{\lambda}=(G^{T}G)^{-1}G^{T}F.$

Plugging in the SVD gives the usual form for the pseudoinverse

$\displaystyle(G^{T}G)^{-1}G^{T}=V\Sigma^{+}U^{T}$

where $\Sigma^{+}$ is the pseudoinverse of $\Sigma$. Accordingly, the singular
values of $(G^{T}G)^{-1}G^{T}$ are simply $\sigma_{1}^{-1}...\sigma_{p}^{-1}$.
Since we have that

$\displaystyle\max_{i=1...p}\sigma^{-1}_{i}\leq\frac{\sqrt{2}}{\alpha\sqrt{\beta
n}}.$

this in turn bounds the operator norm of $(G^{T}G)^{-1}G^{T}$ so that

$\displaystyle||\widehat{\lambda}||_{2}$
$\displaystyle\leq||(G^{T}G)^{-1}G^{T}||_{2}||F||_{2}$
$\displaystyle\leq\frac{\sqrt{2}}{\alpha\sqrt{\beta n}}||F||_{2}$
$\displaystyle\leq\frac{\sqrt{2}}{\alpha\sqrt{\beta}}||F||_{\infty}.$

Finally, a simple calculation shows that
$||F||_{\infty}\leq\max_{p(X)\in[\gamma,1-\gamma]}|\nabla
f(p(X))|\leq\frac{1}{\gamma^{2}}$. Putting it all together, we have that

$\displaystyle||\widehat{\lambda}||_{\infty}$
$\displaystyle\leq||\widehat{\lambda}||_{2}\leq\frac{\sqrt{2}}{\alpha\sqrt{\beta}\gamma^{2}}$

and the corollary follows by substituting this bound into Proposition 1. ∎