# Bibliography management: natbib package

Toru Kitagawa Department of Economics, Brown University and Department of
Economics, University College London. Email<EMAIL_ADDRESS>Hugo
Lopez Department of Economics, University of Chicago. Email:
<EMAIL_ADDRESS>Jeff Rowley Department of Economics, University College
London. Email<EMAIL_ADDRESS>
#  Stochastic Treatment Choice with Empirical Welfare Updating††thanks: The
authors thank participants at the Bristol Econometrics Study Group Conference
for beneficial comments. The authors also gratefully acknowledge financial
support from ERC grant (number 715940) and the ESRC Centre for Microdata
Methods and Practice (CeMMAP) (grant number RES-589-28-0001).

Toru Kitagawa Department of Economics, Brown University and Department of
Economics, University College London. Email<EMAIL_ADDRESS>Hugo
Lopez Department of Economics, University of Chicago. Email:
<EMAIL_ADDRESS>Jeff Rowley Department of Economics, University College
London. Email<EMAIL_ADDRESS>
###### Abstract

This paper proposes a novel method to estimate individualised treatment
assignment rules. The method is designed to find rules that are stochastic,
reflecting uncertainty in estimation of an assignment rule and about its
welfare performance. Our approach is to form a prior distribution over
assignment rules and to update this prior based upon an empirical welfare
criterion. The social planner then assigns treatment by drawing a policy from
the resulting posterior. We show analytically a welfare-optimal way of
updating the prior using empirical welfare. The posterior obtained by
implementing the optimal updating rule is not feasible to compute, so we
propose a variational Bayes approximation for the optimal posterior. We
characterise the welfare regret convergence of the assignment rule based upon
this variational Bayes approximation and show that it converges to zero at a
rate of $\ln(n)/\sqrt{n}$. We apply our methods to experimental data from the
Job Training Partnership Act Study and extensive numerical simulations to
illustrate the implementation of our methods.

Keywords: Empirical welfare maximisation, policy learning, PAC-Bayes learning,
variational Bayes.

##  1 Introduction

The principal goal of programme evaluation is to inform the social planner as
to which individuals within a target population should receive which
treatment. When treatment effects are heterogeneous in individuals’ observable
characteristics, the social planner can improve social welfare by implementing
an individualised treatment assignment rule based upon these characteristics.
The literature on statistical treatment choice initiated by Manski (2004)
studies how to estimate assignment rules based upon a finite sample and how to
assess their welfare performance. Given an experimental sample, existing
approaches – including those proposed in Manski (2004), Hirano and Porter
(2009), Kitagawa and Tetenov (2018), and Athey and Wager (2021) – yield non-
randomised assignment rules, which are deterministic functions mapping the
individual’s observable characteristics to a recommended treatment. That is,
individuals that share the same observable characteristics are all assigned
the same treatment. Such assignment rules are sharp and address the question
of who should be treated? We adopt a broader view of the treatment choice
problem by considering stochastic assignment rules that map individual
observable characteristics to a probability distribution over the different
treatment arms, instead addressing the question of with what probability
should an individual be treated?

In static treatment choice problems with outcome distributions that exhibit
the monotone likelihood ratio property, deterministic assignment rules form a
class of admissible policies (Karlin and Rubin, 1956; Tetenov, 2012), such
that restricting attention to this class is without loss (of welfare). Once we
allow the class of outcome distributions to be unconstrained though, there is
little theoretical justification for focusing on deterministic rules. In
comparison to stochastic assignment rules, deterministic assignment rules have
the following three potentially undesirable features. Firstly, deterministic
assignment rules cannot incorporate confidence or uncertainty about which
treatment is best for each individual. Stochastic assignment rules can
represent such uncertainty, which arises due to the (finite sample) nature of
experimental data or model misspecification, through their probability
weighting of treatments. Secondly, stochastic assignment rules facilitate
future evaluation, since implementing a stochastic assignment rule can
generate a new experimental sample in which treatment is randomised
conditional on individual observable characteristics. Thirdly, unlike
deterministic assignment rules for which the probability that a treatment is
assigned changes discontinuously at some threshold, stochastic assignment
rules feature assignment probabilities that smoothly change with respect to
individual characteristics. Such a feature is desirable if a fairness
criterion requiring that individuals with similar characteristics have similar
probabilities of treatment (Dwork et al., 2012) is enforced.

This paper proposes novel and general methods for obtaining stochastic
individualised assignment rules based on randomised control trial data.
Assuming that the social planner assigns individuals to a binary treatment,
with her goal being to maximise additive (utilitarian) social welfare as in
Manski (2004), we exploit an empirical analogue of the social welfare
criterion to generate individualised assignment probabilities. Specifically,
we start with a prior distribution over a collection of deterministic
assignment rules $\mathscr{G}$, each of which partitions the space of
individual observable characteristics $\mathscr{X}$ into a group of
characteristics $G$ and its complement $G^{c}$, which generates a
deterministic assignment rule $g(x)=1\\{x\in G\\}$. An individual with
characteristics $x\in\mathscr{X}$ is assigned treatment if $x\in G$, and is
not assigned treatment if $x\in G^{c}$. We then update the prior distribution
based upon an empirical analogue of the social welfare criterion to obtain a
posterior distribution over $\mathscr{G}$. To generate a stochastic
assignment, we draw a $g$ from $\mathscr{G}$ according to the posterior
distribution over this collection, and implement the policy prescribed by $g$.
In this way, the stochastic assignment rule that is applied to an individual
with characteristics $x$ is such that the probability of that individual being
treated is equal to the posterior probability that a $g$ is drawn such that
$G$ contains $x$.

One of the main contributions of this paper is that we derive an optimal
updating procedure for obtaining the posterior distribution over
$\mathscr{G}$. This procedure minimises an upper bound on welfare regret and
yields an exponential tilting of the prior over $\mathscr{G}$, where the
tilting depends upon the empirical welfare criterion. This novel updating
formula resembles the quasi-posterior distribution that appears in the
Laplace-type estimation studied by Chernozhukov and Hong (2003), but differs
in that the constant factor in the exponential tilting term is determined
endogenously by the Lagrange multiplier of the optimisation.

Despite our analytical characterisation of the optimal posterior distribution,
computation of this distribution or sampling of $g$ from it is not
straightforward. We therefore consider a variational approximation of the
optimal posterior distribution by a parametric distribution. In particular, we
consider the class of Linear Eligibility Score rules that assign treatment if
$x^{\prime}\gamma$ (the linear score) exceeds some threshold $c$
(eligibility). Building upon the LES class, we exploit the invariance of the
welfare criterion to the ratio of $\gamma$ to $c$ (scale invariance) and
approximate the optimal posterior distribution using a multivariate von Mises-
Fisher distribution.

To demonstrate how to implement our approach and what it delivers in practice,
we apply our methods to the JTPA Study sample that is studied by Bloom et al.
(1997). Given observations of prior earnings and years of education, we ask
with what probability should an individual be treated? Restricting attention
to linear assignment rules and a variational approximation of the optimal
posterior distribution by a multivariate von Mises-Fisher distribution, we
estimate a stochastic assignment rule that is more likely to allocate JTPA
assistance to individuals with high prior earnings and fewer years of
education. Kitagawa and Tetenov (2018), which similarly considers the JTPA
Study sample, and estimates a deterministic assignment rule, serves as a
useful benchmark for comparison. Aside from the obvious difference that we
estimate a stochastic rule (i.e., every individual has a non-trivial
probability to be allocated JTPA assistance under our rule), our estimated
rule allocates JTPA assistance with a lower probability across the sample than
the deterministic rule of Kitagawa and Tetenov (2018), which targets
individuals with low prior earnings and few years of education for treatmens.
This difference reflects the shape of the empirical welfare criterion which
can be captured by our approach but missed by the deterministic policy
obtained as a mode of the empirical welfare criterion.

###  1.1 Literature review

This paper contributes to the growing literature on statistical treatment
choice initiated by Manski (2004). Exact minimax regret assignment rules are
studied in Schlag (2006), Stoye (2009, 2012), Tetenov (2012), Ishihara and
Kitagawa (2021), and Yata (2021). Hirano and Porter (2009) analyses
asymptotically-optimal assignment rules in limit experiments, and Bhattacharya
and Dupas (2012) considers capacity constrained policies. Kitagawa and Tetenov
(2018) proposes Empirical Welfare Maximisation (EWM) methods for
individualised assignment, which maximise a sample analogue of the social
welfare function over a constrained class of policies. Similar approaches have
been studied in the literature on machine learning and personalised medicine,
as in Zadrozny (2003), Beygelzimer and Langford (2009), Zhang et al. (2012),
Zhao et al. (2012), and Swaminathan and Joachims (2015). Recent advances in
learning individualised assignment policies include Adjaho and Christensen
(2022), Athey and Wager (2021), D’Adamo (2021), Han (2022), Kido (2022),
Kitagawa and Tetenov (2021), Kitagawa et al. (2021), Liu (2022), Mbakop and
Tabord-Meehan (2021), Nie et al. (2021), Sakaguchi (2019), Sasaki and Ura
(2020), Sun (2021), and Viviano (2021), to list but a few works. The
assignment rules estimated in these works are all deterministic.

There are some earlier works that investigate the decision-theoretic
justification for randomising assignment and the welfare performance of these
rules, with Manski (2009) providing a detailed review of settings where
randomised rules are preferable. When the welfare criterion is only partially
identified, minimax regret-optimal rules are stochastic given knowledge of the
identified set (Manski, 2000a, 2005, 2007a, 2007b), which remains true even
after taking into account uncertainty of estimates of the bounds (Stoye, 2012;
Yata, 2021; Manski, 2022). As shown by Manski and Tetenov (2007) and Manski
(2009), randomised rules can also be justified by a nonlinear welfare
criterion in a point-identified setting. Kitagawa et al. (2022) shows that for
a wide class of nonlinear welfare regret criteria, admissible assignment rules
are stochastic. Kock et al. (2022) obtains a stochastic assignment rule in a
setting where the oracle optimal rule is fractional due to nonlinearity in the
social planner’s chosen welfare criterion. In contrast to the static treatment
assignment problem, dynamic treatment assignment problems analysed in the
multi-arm bandit literature often consider stochastic assignments that balance
the exploitation versus exploration trade-off, such as the posterior
probability matching algorithm of Thompson (1933) does.

Chamberlain (2011) and Dehejia (2005) approach the treatment choice problem
from a Bayesian perspective. In their framework, the potential outcome
distributions are parametric, and it is over the parameters of these
distributions that a prior is imposed. For the standard mean welfare
criterion, the Bayes optimal allocation rule is deterministic. Our approach
differs from these works in that we do not assume a prior distribution over
the data generating process. We instead impose few restrictions on the data
generating process, and form prior and posterior distributions over the
parameters that index assignment rules. Our approach can be advantageous when
compared to Chamberlain (2011) if the social planner is concerned about
potential misspecification of the likelihood. If the likelihood is
misspecified, the resulting Bayes-optimal assignment rule can be suboptimal
even for large samples. In contrast, our approach is guaranteed to yield a
welfare-optimal policy among the prespecified class of policies without
requiring a specification for the data generating process.

Our approach is also related to that of Bissiri et al. (2016) and Csaba and
Szoke (2020), where loss function-driven (quasi-Bayes) updating rules are
proposed. Rather than follow their approach by adopting exponentiated loss as
a quasi-likelihood and solving the quasi-Bayesian decision problem, we obtain
an optimal learning rule by minimising a high probability upper bound on
welfare regret. This way of establishing optimality is similar to the
structural risk minimisation approach of Vapnik (1998) and the _Probably
Approximately Correct_ (henceforth, PAC) analysis proposed by Valiant (1984),
which was extended to the study of randomised predictors in Shawe-Taylor and
Williamson (1997), and McAllester (1999), constituting the development of PAC-
Bayes theory. For classification and regression problems, various PAC-Bayes
bounds on prediction generalisation errors are obtained in Seeger (2002),
McAllester (2003), Germain et al. (2009), Catoni (2007), Bégin et al. (2014),
Bégin et al. (2016), Derbeko et al. (2004), and Pentina and Lampert (2015),
and can accommodate quasi-Bayesian procedures similar to ours. See Guedj
(2019) for a recent review of this literature. To our knowledge, the PAC-Bayes
bounds that we derive for treatment choice are new to the literature and offer
a contribution of independent interest.

Although the treatment choice problem is distinct from prediction problems –
as is discussed in Kitagawa and Tetenov (2018) – the EWM approach for
treatment choice is closely related to the cost-sensitive binary
_classification_ problem, as first pointed out by Zadrozny (2003). The PAC-
Bayes classification analysis with variational posterior approximation that is
proposed by Alquier et al. (2016) is, therefore, closely related to our
analysis. There are, however, important differences with Alquier et al.
(2016). Firstly, we make use of the approach proposed by Bégin et al. (2016),
which allows for the construction of a variety of different bounds via a
general convex function. This introduces the complication that classification
is not standard (i.e., cost is homogeneous) and is instead cost-sensitive.
Introducing heterogeneity in the cost of misclassification leads to a non-
trivial challenge in deriving the PAC bounds. To address these complications
we leverage results in Maurer (2004) for continuous loss functions over the
unit interval. Secondly, Alquier et al. (2016) considers approximating the
optimal posterior distribution by a Gaussian distribution. We exploit the
scale invariance property of the welfare criterion and approximate the optimal
posterior distribution by a multivariate von Mises-Fisher distribution over
the hypersphere.

##  2 Model and Setup

###  2.1  Notation and setting

We let $D\in\\{0,1\\}$ be a binary treatment, and $Y_{1}$ and $Y_{0}$ be the
potential outcomes associated with the treatments $D=1$ and $D=0$,
respectively. We let $X\in\mathscr{X}$ be a vector of observable
characteristics, which we refer to as covariates, where
$\mathscr{X}\subset\mathbb{R}^{m-1}$. Suppose that experimental data
comprising $n$ iid observations of $(Y_{i},D_{i},X_{i})$ are available, where
$Y_{i}=D_{i}\cdot Y_{1i}+(1-D_{i})\cdot Y_{0i}$ is the post-treatment observed
outcome of individual $i$. We denote the empirical distribution of the
experimental sample, which we reiterate is a probability distribution over
$(Y_{i},D_{i},X_{i})$, by $P^{n}$. We contrast this distribution with the
joint distribution of $(Y_{1},Y_{0},D,X)$ from which the experimental data is
drawn, which we refer to as the data generating process and denote by $P$. We
assume that the covariates consist only of those characteristics that the
planner can use to discriminate between individuals in the target population,
with budgetary, ethical or legal considerations precluding the use of other
characteristics.

Throughout our analysis, we maintain several assumptions. We follow Manski
(2004) and the subsequent literature in supposing that the social welfare
criterion is that of a utilitarian social planner who aims to maximise the
average level of individual outcomes. We note that other criteria could also
be implemented, such as inequality-averse social welfare and Gini social
welfare.111For example, Kasy (2016) and Kitagawa and Tetenov (2021) study a
setting where the social welfare function is a weighted average of the
outcomes with rank-dependent weights, which includes the Gini social welfare
function as a special case.

######  Assumption 1 (External validity).

The population to which policy is to be applied – the target population – has
the same distribution over $(Y_{1},Y_{0},X)$ as the marginal distribution of
$(Y_{1},Y_{0},X)$ in the data generating process.

######  Assumption 2 (Unconfoundedness).

The data generating process satisfies $(Y_{1},Y_{0})\perp\\!\\!\\!\perp D|X$.

Assumptions 1 and 2 are satisfied, for instance, if the experimental data is
extracted directly from the target population and the treatment is,
conditional on the covariates, randomly assigned,222Kitagawa and Tetenov
(2018) considers a setting where the marginal distribution of $X$ differs
between the population of interest and the data generating process. Adjaho and
Christensen (2022) and Kido (2022) study settings that differ also in terms of
the distribution of potential outcomes. independently of the potential
outcomes (Rosenbaum and Rubin, 1983).

######  Assumption 3 (Bounded outcomes).

There exists a constant $0<M<\infty$ such that the support of Y is contained
in $[0,M]$.

######  Assumption 4 (Strict overlap).

There exists a $\psi\in(0,1/2)$ such that the propensity score satisfies, for
all $x\in\mathscr{X}$, $e(x)\in[\psi,1-\psi]$, where $e(x)=E_{P}(D|X)$.

We normalise the outcome variable to the interval $[0,M]$. As discussed in
Kitagawa and Tetenov (2018) and Swaminathan and Joachims (2015), policies that
maximise an empirical welfare criterion are not invariant to positive affine
transformations of outcomes, which is the case for the empirical welfare
criterion that we consider in this paper. Given Assumptions 3 and 4, we can
define

$H\equiv\frac{Y\cdot\frac{\psi}{M}}{e(X)\cdot D+(1-e(X))\cdot(1-D)},$ (2.1)

which are confined to the unit interval, and which we interpret as weights and
that are motivated by an unbiased estimator of the (scaled) expected potential
outcomes. We solve the planner’s problem using these transformed outcomes.

Let $G\subset\mathscr{X}$ specify a set of individuals – identified by their
individual characteristics – to be treated deterministically. We refer to $G$
as a policy. Adopting an additive utilitarian perspective, the average level
of social welfare attained by $G$ is proportional to

$W(G)\equiv\mathrm{E}_{P}\left(Y_{1}\cdot 1\\{X\in G\\}+Y_{0}\cdot 1\\{X\notin
G\\}\right).$ (2.2)

Given Assumptions 1, 2 and 4 and that $Y=Y_{0}+D\cdot(Y_{1}-Y_{0})$, we can
re-write Equation 2.2 as

$\displaystyle W(G)$ $\displaystyle=\mathrm{E}_{P^{n}}\left(\frac{Y\cdot
D}{e(X)}\cdot 1\\{X\in G\\}+\frac{Y\cdot(1-D)}{1-e(X)}\cdot 1\\{X\notin
G\\}\right),$ (2.3)
$\displaystyle=\mathrm{E}_{P^{n}}\left(\frac{Y\cdot(1-D)}{1-e(X)}\right)+\mathrm{E}_{P^{n}}\left(\left(\frac{Y\cdot
D}{e(X)}-\frac{Y\cdot(1-D)}{1-e(X)}\right)\cdot 1\\{X\in G\\}\right).$ (2.4)

Accordingly, the sample analogue of Equation 2.2 can be written as

$\displaystyle W_{n}(G)$
$\displaystyle\equiv\frac{1}{n}\sum^{n}_{i=1}\left(\frac{y_{i}\cdot
d_{i}}{e(x_{i})}\cdot 1\\{x_{i}\in
G\\}+\frac{y_{i}\cdot(1-d_{i})}{1-e(x_{i})}\cdot 1\\{x_{i}\notin G\\}\right),$
(2.5)
$\displaystyle=\frac{1}{n}\sum^{n}_{i=1}\frac{y_{i}\cdot(1-d_{i})}{1-e(x_{i})}+\frac{1}{n}\sum^{n}_{i=1}\left(\frac{y_{i}\cdot
d_{i}}{e(x_{i})}-\frac{y_{i}\cdot(1-d_{i})}{1-e(x_{i})}\right)\cdot
1\\{x_{i}\in G\\},$ (2.6)

where $W_{n}(G)$ is an unbiased estimator for the true level of welfare that
arises from the implementation of a particular $G$. Given the additive social
welfare criterion, the maximal welfare level can be attained by a
deterministic policy. Hence, as far as the population welfare maximisation
problem is concerned, the social planner wants to select the $G$ that
maximises $W(G)$.

Each $G$ can be associated with a binary function $g$ that indicates
membership in $G$. We refer to $g$ as a deterministic asssignment rule, or
simply as an assignment rule, with $\mathscr{G}$ constituting the class of
admissible assignment rules. With this notation to hand, we can write Equation
2.6, with some abuse of notation, as

$\displaystyle W_{n}(g)$
$\displaystyle=\frac{1}{n}\sum^{n}_{i=1}\frac{y_{i}\cdot(1-d_{i})}{1-e(x_{i})}+\frac{1}{n}\sum^{n}_{i=1}\left(\frac{y_{i}\cdot
d_{i}}{e(x_{i})}-\frac{y_{i}\cdot(1-d_{i})}{1-e(x_{i})}\right)\cdot g(x_{i}),$
(2.7)
$\displaystyle=\frac{1}{n}\sum^{n}_{i=1}h_{i}\cdot\frac{M}{\psi}\cdot\left(e(x_{i})\cdot
d+(1-e(x_{i}))\cdot(1-d_{i})\right)\cdot\left(\frac{d_{i}}{e(x_{i})}\cdot
g(x_{i})+\frac{1-d_{i}}{1-e(x_{i})}\cdot(1-g(x_{i}))\right),$ (2.8)
$\displaystyle=\frac{1}{n}\sum^{n}_{i=1}h_{i}\cdot\frac{M}{\psi}\cdot\left(d_{i}\cdot
g(x_{i})+(1-d_{i})\cdot(1-g(x_{i}))\right),$ (2.9)
$\displaystyle=\frac{1}{n}\sum^{n}_{i=1}h_{i}\cdot\frac{M}{\psi}\cdot
1\\{g(x_{i})=d_{i}\\},$ (2.10)
$\displaystyle=\frac{1}{n}\sum^{n}_{i=1}h_{i}\cdot\frac{M}{\psi}-\frac{1}{n}\sum^{n}_{i=1}h_{i}\cdot\frac{M}{\psi}\cdot
1\\{g(x_{i})\neq d_{i}\\},$ (2.11)

where $h_{i}$ is the analogue of $H$, as defined in Equation 2.1, for some
observation $(y_{i},d_{i},x_{i})$. We observe from Equation 2.11 that
$W_{n}(G)$ depends upon $g$ only through its second term, such that

$\underset{g}{\operatorname{argmax}}\,W_{n}(g)=\underset{g}{\operatorname{argmin}}\,\frac{1}{n}\sum_{i=1}^{n}h_{i}\cdot
1\\{g(x_{i})\neq d_{i}\\}.$ (2.12)

Accordingly, we define

$R(g)\equiv\mathrm{E}_{P^{n}}\left(H\cdot 1\left\\{g(X)\neq
D\right\\}\right),$ (2.13)

which we term the welfare risk of $g$, and its empirical analogue

$R_{S}(g)\equiv\frac{1}{n}\sum_{i=1}^{n}h_{i}\cdot 1\left\\{g(x_{i})\neq
d_{i}\right\\},$ (2.14)

which we term the empirical welfare risk of $g$. Both are measures of average
welfare loss under repeated sampling of experimental data. In view of Equation
2.12, the social planner’s objective is to minimise Equation 2.13 via Equation
2.14, by appropriately choosing $g$.

One special set of policies that we draw particular attention to is the Linear
Eligibility Score (LES) class that is defined in Kitagawa and Tetenov (2018),
and that we denote by $\mathscr{F}$. Assignment rules in this class are
indexed by a finite-dimensional parameter vector $\gamma$ and a threshold $c$,
and are associated with a binary function $f_{\beta}$ that satisfies, for all
$x\in\mathscr{X}$,

$f_{\beta}(x)\equiv 1\\{x^{\prime}\gamma\geq c\\},$ (2.15)

where we take $\beta$ to include both $\gamma$ and $c$ (i.e., $\beta$ is an
$m$-dimensional vector). Each LES rule induces a partitioning of the covariate
space into two half-spaces, such that individuals in the upper contour set
receive treatment and individuals in the lower contour set do not. By
restricting $\beta$ to the unit hypersphere (i.e., the Euclidean length of
$\beta$ is one), we guarantee that each policy is associated with a unique
$\beta$. In what follows, we exploit the interchangeability of $\beta$ and the
LES rule that it indexes, adopting $\beta$ as the argument of the loss
functions that we consider. For instance, and again with some abuse of
notation, whenever we focus on the LES class of decision rules we write

$R(\beta)=\mathrm{E}_{P^{n}}\left(H\cdot 1\\{f_{\beta}(X)\neq D\\}\right),$
(2.16)

and

$R_{S}(\beta)=\frac{1}{n}\sum_{i=1}^{n}h_{i}\cdot
1\left\\{f_{\beta}(x_{i})\neq d_{i}\right\\},$ (2.17)

respectively, in place of Equations 2.13 and 2.14.

###  2.2 Posterior over policies as a stochastic assignment rule

We now adapt Equations 2.13 and 2.14 to handle stochastic assignment rules. We
let $\Pi$ denote a probability distribution over $\mathscr{G}$ that we
interpret as a posterior distribution, imposing some mild technical
requirements to ensure measurability.333$\mathscr{G}$ cannot be too rich.
Although we defer to Gunsilius (2019) for further discussion of this point, we
remark that $\mathscr{G}$ can be characterised by a collection of binary
functions, with the number of functions in this collection equal to the
cardinality of $\mathscr{G}$. We let $\mathscr{M}$ denote the collection of
all posterior distributions.

######  Definition 1 (Posterior assignment rule).

Let $\Pi$ be a probability distribution over $\mathscr{G}$ that is constructed
upon observing the sample. The posterior assignment rule under $\Pi$ is a
stochastic assignment rule that assigns individuals with $x\in\mathscr{X}$ to
treatment with probability
$Q^{\Pi}(x)\equiv\int_{\mathscr{G}}g(x)\cdot\mathrm{d}\Pi$.

To implement posterior assignment rules in practice, we suggest randomly
drawing a $g$ from $\mathscr{G}$ according to $\Pi$ for each individual in the
target population. In this way, similar individuals, who can have similar
assignment probabilities, can be assigned to different treatment arms.
Moreover, this approach does not require computation of the probability of
treatment, which can be expensive or infeasible.

######  Definition 2 (Expected welfare risk under $\Pi$).

We define the expected welfare risk under $\Pi$ as

$\displaystyle R^{\Pi}$
$\displaystyle\equiv\int_{\mathscr{G}}R(g)\cdot\mathrm{d}\Pi(g),$ (2.18)
$\displaystyle=\mathrm{E}_{P^{n}}\left(H\cdot\left(D\cdot\left(1-Q^{\Pi}(X)\right)+\left(1-D\right)\cdot
Q^{\Pi}(X)\right)\right),$

with its empirical analogue taking the form

$\displaystyle R_{S}^{\Pi}$
$\displaystyle\equiv\int_{\mathscr{G}}R_{S}(g)\cdot\mathrm{d}\Pi(g),$ (2.19)
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}h_{i}\cdot\left(d_{i}\cdot\left(1-Q^{\Pi}(x_{i})\right)+\left(1-d_{i}\right)\cdot
Q^{\Pi}(x_{i})\right).$

The interpretation of $R^{\Pi}$ is the average welfare loss that the social
planner expects from implementing each $g$ in $\mathscr{G}$ in the target
population when $g$ is distributed according to $\Pi$.

We reiterate that stochastic assignment is achieved by randomly drawing $g$
according to $\Pi$. This way of selecting assignment rules is reminiscent of
the Gibbs classifier in statistical learning theory (Germain et al., 2009) and
might offer a computational advantage over other methods if drawing $g$
according to $\Pi$ is easier than maximising empirical welfare or finding the
mode of $\Pi$, say. An advantage of stochastic assignment is the possibility
for sequential treatment evaluation: the induced assignment of treatment and
non-treatment to individuals in the target population by $\Pi$ is random
conditional on $X$, which allows for estimation of the causal effect of
treatment in future studies. In this sense, stochastic assignment is well
suited to balancing existing evidence about what constitutes the optimal
assignment for each individual against the benefit of further exploration of
the treatment effect (Manski, 2000b). We do not, however, study this channel
and focus on a purely static problem in this paper.

Our framework allows the social planner to hold some prior as to what
constitutes the best policy. We differentiate the subjective beliefs that the
social planner holds, which we encode using the prior distribution $\pi_{0}$,
and their updated beliefs following their observation of sample data, which we
encode using $\Pi$. In the analysis that follows, we provide finite sample
regret guarantees in the form of PAC-Bayes bounds for stochastic assignment.
The approach discussed here differs significantly from other Bayesian
treatment choice settings, such as those discussed in Chamberlain (2011),
because we do not impose any kind of prior belief on $P$. We instead choose to
model the beliefs that the social planner has regarding the optimal policy.
Using a decision procedure that is free from specification of the likelihood
comes with a desirable robustness property, as we discuss in due course.

Aside from its more conventional role as a means of expressing existing
information about what constitutes the best policy, $\pi_{0}$ can also play
several other roles within our framework. For instance, $\pi_{0}$ can also
embed any constraints that are imposed upon the set of policies through
truncation of its support. Such a zero density condition can be imposed in
lieu of an explicit restriction on $\mathscr{G}$ and is easy to implement in
practice via rejection sampling, with only those policies that satisfy any
budgetary, ethical or legal constraints being retained under the sampling
procedure. Moreover, $\pi_{0}$ can also be used to describe the status quo,
with restrictions on the shape of $\pi_{0}$ governing how much policy can
deviate. These interpretations of $\pi_{0}$ naturally extend to $\Pi$.

##  3 Optimal stochastic assignment and convergence of welfare

###  3.1 Bounding expected welfare risk

Seeing as experimental data provides only an insight into the welfare
performance of any policy in the target population, a very natural question to
ask is how much we can expect $R^{\Pi}_{S}$ to differ from $R^{\Pi}$ for any
given $\Pi$. We provide an answer to this question here.

######  Theorem 1.

Suppose that Assumptions 1, 2, 3 and 4 are satisfied, and $n\geq 8$. Then, for
any $0<\epsilon<1$ and $\Pi\in\mathscr{M}$ that is absolutely continuous with
respect to $\pi_{0}$, the following inequality holds with probability at least
$1-\epsilon$ in terms of $P^{n}$:

$R^{\Pi}\leq
R_{S}^{\Pi}+\sqrt{\frac{1}{2n}\cdot\left(\mathrm{KL}(\Pi\|\pi_{0})+\ln\left(\frac{2\sqrt{n}}{\epsilon}\right)\right)}.$
(3.1)

We present a proof of this theorem in Section A.1. The proof builds upon Bégin
et al. (2016, §Lemma 3), which offers a flexible approach that allows for the
recovery of many different PAC-Bayes bounds. The approach centres around a
convex function of $R^{\Pi}$ and $R^{\Pi}_{S}$, which we specify so as to
recover the form that is presented in McAllester (2003, see §(8) in , ). We
leverage results in Maurer (2004, §Lemma 3 and §Theorem 1), exploiting the
properties of Bernoulli random variables and convex functions, to adapt Bégin
et al. (2016) and the bound that is presented therein to allow for
heterogeneous cost (in lieu of the standard binary loss function that is
prevalent in the classification literature and that is studied in Bégin et
al., 2016).

We note that Theorem 1 holds for any rules that update $\pi_{0}$ and deliver
$\Pi$, and that we have not committed to any particular updating rule to
obtain Equation 3.1. A feature of Equation 3.1 is that the regularisation term
– that contains the Kullback-Leibler divergence of $\Pi$ from $\pi_{0}$ –
enters additively, which we find is a convenient feature for establishing
convergence of our variational approximation (regularisation can otherwise be
effected multiplicatively).444See Bégin et al. (2016) for the implications of
different convex functions. The regularisation term, by design, prevents
overfitting. To illustrate this point, suppose that $\pi_{0}$ is uniform over
$\mathscr{G}$: the best response of the social planner absent regularisation
is to concentrate probability mass on the optimal (in-sample) $g$ as suggested
by data, such that $\Pi$ is degenerate. In the presence of regularisation,
however, this is no longer a best response, since the Kullback-Leibler
divergence infinitely penalises degeneracy vis-à-vis uniformity. Rather, the
best response of the social planner is to allocate probability mass on all $g$
in $\mathscr{G}$, albeit concentrating more mass on those $g$ that are
associated with low empirical welfare risk. Put differently, the
regularisation term controls how far away from $\pi_{0}$ a stochastic
assignment rule can be, with this difference governed by the number of
observations in the sample.

The Vapnik-Chervonenkis (VC) dimension is the standard measure of complexity
in the statistical learning literature. We instead associate complexity with
the Kullback-Leibler divergence. If one is willing to impose distributional
constraints on a posterior assignment rule, an advantage of the PAC-Bayes
approach and of using the Kullback-Leibler divergence is that complexity is
then purely in terms of the selected (stochastic) assignment rule $\Pi$ rather
than in terms of the class of possible stochastic assignment rules
$\mathscr{M}$ or the class of underlying deterministic rules $\mathscr{G}$. As
such, Theorem 2 is free from any assumption about the VC dimension. The
influence of VC dimension for $\mathscr{G}$ is implicit in our setting: the
upper bound on the difference between $R_{S}^{\Pi}$ and $R^{\Pi}$ implied by
Equation 3.1 is governed by the Kullback-Leibler divergence, which is
increasing in the dimension of the support of $\Pi$ and $\pi_{0}$, and so is
non-decreasing in the complexity of $\mathscr{G}$; the lowest attainable
$R^{\Pi}$ is non-increasing in the complexity of $\mathscr{G}$.

###  3.2 Optimal updating rule

In a standard Bayesian setting, unknown parameters index the distribution of
data and inference on parameters is conducted with respect to the posterior
distribution for the,. Typically, the posterior distribution is constructed
from a well-defined likelihood function via Bayes’ theorem. We leverage
Theorem 1 to construct $\Pi$ from $\pi_{0}$ and $R^{\Pi}_{S}$. This approach
is valid since Theorem 1 holds for all $\Pi\in\mathscr{M}$. We emphasise that
the posterior distribution that we construct is over assignment rules rather
than over the data generating processes, which is distinct from Bissiri et al.
(2016) and Csaba and Szoke (2020).

Following McAllester (2003) and Germain et al. (2009), we define an optimal
posterior distribution, which we denote by $\Pi^{*}$, as a distribution over
$\mathscr{G}$ that minimises the right hand side of Equation 3.1. That is,
$\Pi^{*}$ minimises

$R_{S}^{\Pi}+\sqrt{\frac{1}{2n}\cdot\left(\mathrm{KL}(\Pi\|\pi_{0})\text{+}\ln\left(\frac{2\sqrt{n}}{\epsilon}\right)\right)}.$
(3.2)

######  Theorem 2.

The optimal posterior $\Pi^{\ast}$ over $\mathscr{G}$ satisfies

$\mathrm{d}\Pi^{*}(g)\equiv\frac{\exp\left(-\chi\cdot
R_{S}(g)\right)}{\int_{\mathscr{G}}\exp\left(-\chi\cdot
R_{S}(g)\right)\cdot\mathrm{d}\pi_{0}(g)}\cdot\mathrm{d}\pi_{0}(g),$ (3.3)

where

$\chi\equiv
4n\cdot\sqrt{\frac{1}{2n}\cdot\left(\mathrm{KL}(\Pi^{*}\|\pi_{0})+\ln\left(\frac{2\sqrt{n}}{\epsilon}\right)\right)}.$
(3.4)

We present a proof of this theorem in Section A.2.

The posterior distribution that we derive is analogous to the optimal
posterior in McAllester (2003) with the difference that our observations are
mapped to the unit interval rather than to $\\{-1,1\\}$, which is the standard
support in classification. This particular distribution is common in the
statistical mechanics literature and is a Boltzmann (or Gibbs) distribution,
and has the form of exponential tilting of the prior, where the exponential
tilting term involves the negative empirical welfare risk. The degree of
tilting depends upon the magnitude of $\chi>0$, which is the inverse of the
Lagrange multiplier of the associated minimisation problem and that
corresponds to the root of Equation 3.4. The Lagrange multiplier controls the
extent to which $\pi_{0}$ is updated by empirical welfare risk in minimising
the upper bound for $R^{\Pi}$.

Although Theorem 2 offers an analytical characterisation of the optimal
posterior, we are unable to obtain a closed-form expression for the optimal
posterior density. While Equation 3.4 does suggest a means to compute this
density, it is likely that, in practice, this computation is difficult to
perform with any precision. Given that we have, however, established that this
density exists, we can consider approximating it using the _variational
approximation_ method, as is considered in Alquier et al. (2016).

###  3.3 Variational approximation of the optimal stochastic assignment rule

We develop a variational approximation of the optimal posterior density.
Variational approximation is useful in situations where Gibbs distributions
are difficult to sample from directly, such as is the case for graphical
models where Markov Chain Monte Carlo (MCMC) sampling is costly (Wainwright
and Jordan, 2008). In variational approximation, we choose to approximate the
optimal posterior distribution via a family of distributions of our choice,
$\mathscr{V}\subset\mathscr{M}$. This allows us to develop an analytically
tractable upper bound for the welfare regret attained by the resulting
stochastic assignment rule.

Aside from guaranteeing tractability in estimation, variational approximation
can also be motivated as a convenient way to impose constraints on the set of
policies. For instance, a fairness criterion requiring that individuals with
similar characteristics have similar probabilities of treatment (Dwork et al.,
2012) can be enforced by specifying that $\mathscr{V}$ is a continuous family,
and by limiting the concentration of the density. A similar approach can be
used if $\mathscr{V}$ is a parametric family to limit how much policy can
deviate from the status quo, by fixing the parameters of the posterior
distribution or restricting them to some set, say.

We approximate $\Pi^{\ast}$ (implicitly defined in Theorem 2) by minimising
the right-hand side of Equation 3.1 with respect to posterior distributions in
$\mathscr{V}$, defining

$\tilde{\Pi}\equiv\underset{\Pi\in\mathscr{V}}{\operatorname{argmin}}\,\left\\{R_{S}^{\Pi}+\sqrt{\frac{1}{2n}\cdot\left(\mathrm{KL}(\Pi\|\pi_{0})+\ln\left(\frac{2\sqrt{n}}{\epsilon}\right)\right)}\right\\}.$
(3.5)

We then use this optimal variational posterior distribution to define a new
bound for welfare regret from which we can characterise its convergence rate.

######  Lemma 1.

With probability $1-\epsilon$ the expected welfare risk under the optimal
variational posterior satisfies

$R^{\tilde{\Pi}}\leq\inf_{\Pi\in\mathscr{V}}R^{\Pi}+\frac{a(\lambda,n)}{\lambda}+\frac{\mathrm{KL}(\Pi\|\pi_{0})}{\lambda}+\frac{\ln\left(\frac{2}{\epsilon}\right)}{\lambda}+\sqrt{\frac{1}{2n}\cdot\left(\mathrm{KL}(\Pi\|\pi_{0})+\ln\left(\frac{4\sqrt{n}}{\epsilon}\right)\right)},$
(3.6)

where $\epsilon\in(0,1)$ is a constant and where $a$ is a function that
depends upon a positive constant $\lambda$.

In what follows, we let $\mathscr{V}$ be a variational family of distributions
that assigns positive density to assignment rules in $\mathscr{F}$ only.
Equivalently, we let $\mathscr{V}$ be a directional family that assigns
positive density to unit vectors on the hypersphere, recalling that every
policy in the LES class can be uniquely associated with a unit vector (see
Equation 2.15 and surrounding discussion). A particularly tractable
directional family, and one that we use, is the von Mises-Fisher family of
distributions, which is characterised by a probability density function
satisfying, for all $\kappa>0$ and $m$-dimensional unit vectors $\mu$,

$\mathrm{d}\Pi(\beta;\kappa,\mu)\equiv\frac{\kappa^{m/2-1}\cdot\exp\left({\kappa\cdot\mu^{\prime}\beta}\right)}{(2\pi)^{m/2}\cdot
I_{m/2-1}(\kappa)}\cdot\mathrm{d}\beta,$ (3.7)

where $I_{\nu}$ is a modified Bessel function of the first kind and order
$\nu$. A von Mises-Fisher distribution is the analogue of a multivariate
Gaussian distribution on the unit hypersphere. We refer to $\kappa$ as the
concentration parameter and to $\mu$ as the mean direction (the location
parameter), noting that the distribution becomes degenerate as
$\kappa\rightarrow\infty$ and uniform as $\kappa\rightarrow 0$.

We now introduce some further notation that facilitates our analysis. Firstly,
we let $\overline{R}=\inf_{\Pi\in\mathscr{M}}R^{\Pi}$ denote the minimum
expected welfare risk amongst assignment rules in $\mathscr{F}$ and
$\overline{\beta}$ denote the vector that parametrises the assignment rule
that induces $\overline{R}$. We also add the following assumption that
restricts the marginal distribution of $X$.

######  Assumption 5 (Margin assumption).

There exists a constant $c>0$ such that, for any $m$-dimensional unit vectors
$\beta^{\dagger}$ and $\beta^{\ddagger}$, $P\left(\langle
X,\beta^{\dagger}\rangle\cdot\left\langle X,\beta^{\ddagger}\right\rangle\leq
0\right)\leq c\cdot\left\|\beta^{\dagger}-\beta^{\ddagger}\right\|_{2}$.

This assumption is satisfied whenever $X$ has bounded density on the unit
hypersphere and is also present in the analysis of Alquier et al. (2016). An
interpretation of this assumption is that the proportion of individuals whose
treatment status switches is continuous with respect to the linear eligibility
score coefficients, with an implication being that $R(\beta)-\overline{R}\leq
2c\cdot\|\beta-\overline{\beta}\|_{2}$. We now present a high-probability
uniform upper bound for the welfare regret of the stochastic assignment rule
obtained by variational approximation via the von Mises-Fisher family of
distributions.

######  Theorem 3.

Suppose that Assumptions 1, 2, 3, 4 and 5 are satisfied, that $\pi_{0}$ is a
uniform distribution over the unit hypersphere, and that $\Pi$ is a von Mises-
Fisher distribution. Then for $n\geq 8$, with probability at least
$1-\epsilon$,

$R^{\tilde{\Pi}}-\overline{R}\leq M\cdot\frac{\ln(n)}{\sqrt{n}},$ (3.8)

where $M$ is a universal constant.

We present proof of this theorem and provide an analytical expression for the
universal constant in Section A.4.

The uniform upper bound on welfare regret that is defined by Equation 3.8
decays at a rate of $\ln(n)/\sqrt{n}$. This rate is slightly slower than the
welfare regret convergence rate of the EWM (deterministic) assignment rule
studied in Kitagawa and Tetenov (2018). A simple comparison of these rates,
however, is not quite meaningful for the following reason: we do not know if
the convergence rate of $\ln(n)/\sqrt{n}$ that is obtained in Theorem 3 is
sharp or not. Theorem 3 requires Assumption 5, while Kitagawa and Tetenov
(2018) does not impose this assumption in showing that $1/\sqrt{n}$ is the
minimax optimal rate of welfare regret convergence. We do not know what the
minimax optimal rate of welfare regret convergence is when Assumption 5 is
additionally imposed and, hence, cannot rule out the possibility that the
convergence rate of Theorem 3 can be improved upon and made faster than
$1/\sqrt{n}$.555Kitagawa and Tetenov (2018, §Theorem 2.3 and §Theorem 2.4)
establishes that the minimax-optimal rate under a stronger condition than our
Assumption 5 is $1/n^{2/3}$. This stronger condition embeds a margin
assumption that implies our Assumption 5 but also embeds the requirement that
the first-best treatment rule is contained in the set of admissible decision
rules – that $\mathscr{F}$ contains the deterministic assignment rule that
minimises expected welfare risk amongst all assignment rules. We do not make
any assumption about whether $\mathscr{F}$ (or indeed $\mathscr{G}$ in earlier
parts of our analysis) contains the first-best assignment rule, or whether
this rule is deterministic or stochastic. We leave further investigation of
this matter for future research.

It is worth emphasising that the regret convergence result of Theorem 3
imposes weak restrictions on the distribution of data (Assumptions 3 \- 5) and
does not require the specification of a likelihood function or of regression
equations. This contrasts with other approaches such as a Bayesian approach,
where misspecification of likelihood can lead to non-convergence of the
welfare regret even when Bayes optimal policies are constrained to
deterministic ones in $\mathscr{F}$.

Our approach is similar to Alquier et al. (2016) in which the families of
distributions for variational approximation are multivariate Gaussian
distributions on Euclidean space with flexible covariance matrices. In our
approach, we stipulate a class of von Mises-Fisher distributions, which are
the hyperspherical analogues of multivariate Gaussian distribution with
diagonal covariance matrices featuring a constant variance element. Since the
empirical welfare criterion for LES rules is invariant to the scale of
$\beta$, it is natural to consider von Mises-Fisher distributions rather than
Gaussian ones.

##  4 Implementation

To implement our procedure, we restrict attention to $\mathscr{F}$ and let
$\mathscr{V}$ be the von Mises-Fisher family of distributions. Our goal is
then to minimise the objective function,

$R^{\Pi}_{S}(f)+\sqrt{\frac{1}{2n}\cdot\left(\text{KL}(\Pi|\pi_{0})+\ln\left(\frac{2\sqrt{n}}{\epsilon}\right)\right)},$
(4.1)

with respect to the concentration parameter $\kappa$ and mean direction $\mu$,
which are the parameters of our chosen variational family. Here, we reiterate
that $\epsilon$ relates to the probability with which our high probability
bounds hold. We assume that $\pi_{0}$ is the uniform distribution over the
sphere and set $\epsilon$ equal to the 5% level throughout. We propose
numerically minimising the objective function, computing $R^{\Pi}_{S}$ for a
given realisation of data and for fixed values of the parameters of the von
Mises-Fisher distribution.

We propose approximating $R^{\Pi}_{S}$ using Monte Carlo draws of $\beta$ from
the von Mises-Fisher distribution for each combination of $\kappa$ and $\mu$.
We let $\\{\beta^{j}:j=1,...,J\\}$ be the pseudo-random draws that we obtain,
and compute

$\hat{R}^{\Pi}_{S}\equiv\frac{1}{n}\sum_{i=1}^{n}h_{i}\cdot\left(D_{i}\cdot(1-\hat{\Pi}_{i})+(1-D_{i})\cdot\hat{\Pi}_{i}\right),$
(4.2)

where, for all $i=1,...,n$,

$\hat{\Pi}_{i}\equiv\frac{1}{J}\sum_{j=1}^{J}1\\{x_{i}^{\prime}\beta^{j}\geq
0\\}.$ (4.3)

Fast pseudo-random sampling from of a von Mises-Fisher random vector is
possible using the rejection sampling method of Wood (1994) or the inversion
method of Kurz and Hanebeck (2015).

As is shown in Kitagawa and Rowley (2022), the Kullback-Leibler divergence of
the von Mises-Fisher distribution from the uniform distribution over the
hypersphere does not depend upon $\mu$ and increases at the logarithmic rate
in $\kappa$. In contrast, although $R^{\Pi}_{S}$ is a function of $\mu$ and
$\kappa$, the nature of this relationship is not clear. That several
combinations of $\mu$ and $\kappa$ induce local minima of $R^{\Pi}_{S}$ cannot
be ruled out for instance. Moreover, since we construct $\hat{R}^{\Pi}_{S}$
based upon random draws of $\beta$ from $\Pi$, our objective function is not a
smooth function of $\mu$ and $\kappa$. Given this, we suggest that a grid-
based search for the minimum of the objective function is appropriate, with
this search limited to values of $\kappa$ between zero and some specified
upper limit. Further insight about the behaviour of the objective function is
provided in Sections 5, B and C.

##  5 Empirical illustration

Figure 1: Variation in treatment propensity across individuals in the JTPA
Study sample Each point represents the individual characteristics of an
individual or several individuals in the JTPA Study sample. The size of each
point is proportional to the sum of the post-programme earnings of all
individuals with those characteristics, which corresponds to the weight given
to those observations in the empirical implementation. The colour of each
point measures the propensity with which an individual with those
characteristics is assigned treatment under our estimate of the optimal
stochastic assignment rule. Under the optimal stochastic assignment rule, more
educated individuals with low pre-programme earnings are less likely to be
assigned treatment. For comparison, individuals to the left of the solid
diagonal line are assigned treatment under the optimal deterministic
assignment rule of Kitagawa and Tetenov (2018). Figure 2: Behaviour of the
objective function given variation in the concentration $\kappa$ Holding fixed
the mean direction at its value under our estimate of the optimal stochastic
assignment rule, we vary the value of the concentration parameter. We plot the
USD equivalent amount of both the criterion (the objective function) and
empirical welfare risk (the first part of the objective function) in the JTPA
Study sample, which we define in Equation 4.1. As the concentration increases,
the stochastic assignment rule places increasing probability on a small
neighborhood of assignment rules about the mean direction – i.e., it becomes
more like a deterministic rule. The criterion first decreases alongside regret
but then increases as the penalty term begins to dominate. Figure 3:
Deterministic assignment rules and regret We calculate the in-sample regret
associated with different deterministic assignment rules. We project the
three-dimensional sphere onto the plane using a spherical coordinate mapping,
where the azimuth and inclination can be loosely interpreted as longitude and
latitude, respectively. The sphere can be broadly divided into two hemispheres
of low and high regret, with the best and worst deterministic assignment rules
found on the boundary of these two hemispheres. We emphasise the number of
local minima on this boundary. The intersection of the two white lines is
located at the mean direction of the optimal stochastic assignment rule. The
intersection of the two black lines is located at the optimal deterministic
assignment rule of Kitagawa and Tetenov (2018), which attains the minimal
regret amongst all deterministic linear rules. Figure 4: Behaviour of the
objective function given variation in the mean direction $\mu$ Holding fixed
the concentration parameter at its value under our estimate of the optimal
stochastic assignment rule, we vary the mean direction. We project the three-
dimensional sphere onto the plane using a spherical coordinate mapping, where
the azimuth and inclination can be loosely interpreted as longitude and
latitude, respectively. Stochastic assignment rules that are close tend to
give similar estimates of regret.

We illustrate our procedure using data from the National Job Training
Partnership Act (JTPA) Study. Applicants to the Study were randomly allocated
to one of two groups. Applicants allocated to the treatment group were
extended training, job search assistance and other services provided by the
JTPA over a period of 18 months. Applicants allocated to the control group
were excluded from JTPA assistance. Along with information collected prior to
the commencement of the intervention, the Study also collected administrative
and survey data relating to applicants’ earnings in the 30 months following
its start. Further details about the data and the Study can be found elsewhere
(see, for instance, Bloom et al., 1997). We restrict attention to a sample of
9,223 observations for which data on years of education and pre-programme
earnings amongst the sample of adults (aged 22 years and older) used in the
original evaluation of the programme and in subsequent studies (Bloom et al.,
1997; Heckman et al., 1997; Abadie et al., 2002) is available. Applicants in
this sample were assigned to the treatment group with a probability of two
thirds. Like Kitagawa and Tetenov (2018), we define $D$ to be the initial
assignment of treatment, rather than the actual take-up due to the presence of
non-compliance in the experiment. We study stochastic assignment rules.

We follow Kitagawa and Tetenov (2018) in considering total individual earnings
in the 30 months after programme assignment as our principal welfare measure.
Moreover, we focus exclusively on the class of linear rules,

$\displaystyle\mathscr{F}$
$\displaystyle=\left\\{(x:\beta_{0}+\beta_{1}\cdot\text{prior
earnings}+\beta_{2}\cdot\text{education}\geq
0\left|\,\|(\beta_{0},\beta_{1},\beta_{2})\|_{2}=1\right.\right\\},$ (5.1)
$\displaystyle=\left\\{x:\beta_{0}+\beta_{1}\cdot x_{1}+\beta_{2}\cdot
x_{2}\geq 0\left|\,\|(\beta_{0},\beta_{1},\beta_{2})\|_{2}=1\right.\right\\},$

that are studied in that paper.

To implement our procedure, we map prior earnings and education to the unit
interval,666We map each variable to the unit interval by dividing through by
its maximum in the sample. Kitagawa and Tetenov (2018) also does this. Such a
change of units is useful when the domain of one variable is much larger than
the domain of another and the respective coefficients on the two variables
reflect this. For instance, in our sample, every individual has between seven
and 18 years of education, and no individual earned more than $63,000 prior to
the start of the intervention. and calculate $H$ as outlined in Equation 2.1.
We perform this calculation without adjusting post-programme earnings by the
average cost of JTPA assistance ($774 per individual) for treated
individuals.777We adjust post-programme earnings by the average cost of JTPA
assistance in Appendix B We then utilise a grid search approach over the
parameters of the von Mises-Fisher distribution, specifying a reasonably fine
grid over the unit sphere888We design our grid so as to place an upper limit
on the great-circle distance between any point on the sphere and its closest
point on the grid. Our grid comprises a total of 10,116 directional vectors
combined with a sequence of evenly-spaced concentrations on the $[0,5]$
interval. For reference, the surface area of the sphere is $4\pi$, which means
that our grid has a density of approximately $0.001$. and over a finite subset
of the reals.

For each point on our grid, we draw 1,000 values of $\beta$ from the
corresponding von Mises-Fisher distribution and approximate empirical welfare
risk as per Equation 4.2. We then substitute these values into Equation 4.1 to
provide an estimate of the objective function.

We find that the objective function is minimised (amongst the class of von
Mises-Fisher distributed linear assignment rules) by the stochastic assignment
rule with $\kappa^{*}=1.550$ and $\mu^{*}=(0.883,0.442,0.158)$.999This
directional vector can be represented by an azimuth of $27^{\circ}$ and an
inclination of $81^{\circ}$ using spherical coordinates.

The optimal stochastic assignment rule, on average, assigns treatment to
individuals in the JTPA Study sample around 83% of the time. This probability
is not, however, uniform, and there is some variation in the probability with
which distinct individuals are assigned treatment. This variation in
assignment propensity can be seen in Figure 1, which plots the individual
characteristics of all individuals in the sample. The propensity with which
individuals with distinct characteristics are assigned to treatment is
represented by the color of each point, and the weight given to individuals in
the sample with particular characteristics is represented by the size of each
point. The weight attached to a given point is proportional to the sum of
post-programme earnings over all individuals with those characteristics, and
so is loosely related to the number of individuals that inhabit that
point.101010To simplify Figure 1, we re-scale the weights to lie in the
$[0,10]$ interval. As such, we suggest that the only inference that should be
drawn from the size of the points in Figure 1 is that points with greater mass
reflect some combination of higher post-programme earnings amongst individuals
with those characteristics and the presence of relatively more individuals in
the sample with those characteristics. Figure 1 shows that the optimal
stochastic assignment rule is more likely to assign treatment to an individual
with few years of education and high prior earnings than an individual with
more years of education and lower prior earnings, with the assignment
probability ranging from 78% to 84%. The deterministic assignment rule of
Kitagawa and Tetenov (2018), in contrast, assigns only individuals with few
years of education and low prior earnings to treatment, with around 93% of
individuals assigned to treatment. We plot this deterministic rule as a useful
benchmark for comparison in Figure 1.

It is important to emphasise that it is the regularisation term and, in
particular, the Kullback-Leibler divergence that limits the value of $\kappa$
at the optimum, and leads to an interior probability of assignment for all
individuals. This can be seen in Figure 2, which plots the USD equivalent of
the objective function (left-hand axis, solid line) and of empirical welfare
risk (right-hand axis, dashed line) for a range of $\kappa$, holding fixed
$\mu$ at $\mu^{*}$. We observe that empirical welfare risk decreases as
$\kappa$ increases, remaining low and constant once its value is sufficiently
large. The intuition here is that large values of $\kappa$ lead to stochastic
assignment rules that mimic deterministic ones. As $\mu^{*}$ implies that all
individuals would be treated if $\mu^{*}$ were instead enacted as a
deterministic rule, empirical welfare risk is necessarily constant for large
values of $\kappa$. That empirical welfare risk decreases for small to
moderate values of $\kappa$ is specific to the data and chosen $\mu$, and is
arguably also attributable to the lack of consideration given to the cost of
treatment. We expect then that $\mu$ will eventually coincide with the
deterministic assignment rule of Kitagawa and Tetenov (2018) as the value of
the concentration parameter approaches infinity, since there does not exist a
(linear) deterministic rule that can improve upon this. Tempering this
preference towards large values of $\kappa$ is the Kullback-Leibler divergence
of the von Mises-Fisher distribution from the uniform distribution, which is
increasing at the logarithmic rate in $\kappa$ and generates the difference
between the objective function and empirical welfare risk in Figure 2. As
$\kappa$ increases, the regularisation term begins to dominate.

To better understand why $\mu^{*}$ does not coincide with the deterministic
assignment rule of Kitagawa and Tetenov (2018) given $\kappa^{*}$, we refer to
Figure 3, which plots empirical welfare risk for all vectors on the unit
sphere – i.e., the empirical welfare risk associated with all deterministic
assignment rules. Figure 3 utilises the spherical coordinate system

$(\beta_{0},\beta_{1},\beta_{2})=(\cos(\theta)\sin(\phi),\sin(\theta)\sin(\phi),\cos(\phi)),$
(5.2)

where $\theta\in[-180^{\circ},180^{\circ})$ is the azimuth and
$\phi\in[0,180^{\circ}]$ is the inclination. It is perhaps convenient to think
of the azimuth as related to longitude and the inclination as related to
latitude. For non-trivial $\kappa$, the von Mises-Fisher distribution
allocates probability mass to the sphere in such a way that its density
contours are concentric about $\kappa$, with points closer to $\mu$ more
likely to occur. The deterministic assignment rule of Kitagawa and Tetenov
(2018) can be seen from Figure 3 to be located on the boundary between a high
risk region (no-one treated) and a moderate risk region (everyone treated). As
such, a stochastic assignment rule with non-trivial $\kappa$ and $\mu$ located
at this point would approximately allocate probability mass to each of these
regions in equal amounts. By shifting $\mu$ towards the centre of the moderate
risk region, we allocate relatively more mass to rules that induce moderate
risk and less mass to rules that induce high risk, which reduces empirical
welfare risk overall.

This pattern underlies what we observe in Figure 4, which plots empirical
welfare risk for all $\mu$ on the sphere given $\kappa^{*}$. Despite the
apparent discontinuity of risk over deterministic assignment rules, empirical
welfare risk (and the objective function) appear to vary smoothly.

##  6 Conclusion

Central to our analysis of the treatment choice problem is the question of how
should the social planner allocate individuals to treatment with a given
probability rather than with certainty? To answer this question, we focus on
stochastic assignment rules that we formulate as posterior distributions
obtained from well-defined prior distributions via a PAC-Bayes approach. These
distributions are able to accommodate any initial belief that the social
planner holds about what constitutes the best treatment, as well as any
budgetary, ethical or legal constraints that are imposed and that can arise
due to concerns about fairness or about maintaining the status quo. We
establish that it is possible to obtain the minimum expected welfare risk
under a variational approximation of the optimal posterior distribution, which
we also characterise. In keeping with the notion that variational
approximation replaces a general class of assignment rules with a simpler set
of policies, we focus on stochastic assignment rules that can be expressed as
density functions over the LES class of (deterministic) assignment rules. We
exploit the scale invariance of the LES class to restrict attention to
distributional families on the unit hypersphere, selecting the von Mises-
Fisher family of distributions as our chosen variational family. We
demonstrate how our methods can be used in an empirical setting by estimating
which individuals should be entered onto a job training programme, using data
from the well-known JTPA Study.

Our research suggests several further questions that remain unanswered. How
does the choice of variational family affect the rate of convergence? The von
Mises-Fisher family of distributions is not the only directional family –
other families such as the Matrix Langevin and Kent families allow for richer
covariance structures. While more general distributions admit more complex
stochastic assignment rules, does this additional generality come at an
additional cost? Do other parametrisations of the class of assignment rules
exist that can achieve faster decay rates? We establish that the optimal
stochastic assignment rule in our chosen variational family yields a
convergence rate for welfare regret of $\ln(n)/\sqrt{n}$. Ignoring the
logarithm in the numerator, this rate coincides with the minimax optimal rate
for deterministic assignment rules in the absence of the margin assumption, as
shown in Kitagawa and Tetenov (2018). Our convergence rate result, however,
relies upon Assumption 5 that constrains the marginal distribution of $X$. We
do not know whether this assumption leads to the minimax optimal rate being
faster than $1/\sqrt{n}$ and whether the proposed method can attain a faster
convergence rate than $\ln(n)/\sqrt{n}$.

## References

  * Abadie et al. (2002) Abadie, A., J. Angrist, and G. Imbens (2002): “Instrumental variables estimates of the effect of subsidized training on the quantiles of trainee earnings,” _Econometrica_ , 70, 91–117.
  * Adjaho and Christensen (2022) Adjaho, C. and T. Christensen (2022): “Externally Valid Treatment Choice,” _arXiv preprint arXiv:2205.05561_.
  * Alquier et al. (2016) Alquier, P., J. Ridgway, and N. Chopin (2016): “On the properties of variational approximations of Gibbs posteriors,” _The Journal of Machine Learning Research_ , 17, 8374–8414.
  * Amos (1974) Amos, D. E. (1974): “Computation of modified Bessel functions and their ratios,” _Mathematics of computation_ , 28, 239–251.
  * Athey and Wager (2021) Athey, S. and S. Wager (2021): “Policy learning with observational data,” _Econometrica_ , 89, 133–161.
  * Bégin et al. (2014) Bégin, L., P. Germain, F. Laviolette, and J.-F. Roy (2014): “PAC-Bayesian theory for transductive learning,” in _Artificial Intelligence and Statistics_ , 105–113.
  * Bégin et al. (2016) ——— (2016): “PAC-Bayesian bounds based on the Rényi divergence,” in _Artificial Intelligence and Statistics_ , 435–444.
  * Beygelzimer and Langford (2009) Beygelzimer, A. and J. Langford (2009): “The offset tree for learning with partial labels,” in _Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining_ , ACM, 129–138.
  * Bhattacharya and Dupas (2012) Bhattacharya, D. and P. Dupas (2012): “Inferring welfare maximizing treatment assignment under budget constraints,” _Journal of Econometrics_ , 167, 168–196.
  * Bissiri et al. (2016) Bissiri, P. G., C. C. Holmes, and S. G. Walker (2016): “A general framework for updating belief distributions,” _Journal of the Royal Statistical Society: Series B (Statistical Methodology)_ , 78, 1103–1130.
  * Bloom et al. (1997) Bloom, H. S., L. L. Orr, S. H. Bell, G. Cave, F. Doolittle, W. Lin, and J. M. Bos (1997): “The benefits and costs of JTPA Title II-A programs: Key findings from the National Job Training Partnership Act study,” _Journal of human resources_ , 549–576.
  * Boucheron et al. (2013) Boucheron, S., G. Lugosi, and P. Massart (2013): _Concentration inequalities: A nonasymptotic theory of independence_ , Oxford university press.
  * Catoni (2007) Catoni, O. (2007): “PAC-Bayesian supervised classification: the thermodynamics of statistical learning,” _arXiv preprint arXiv:0712.0248_.
  * Chamberlain (2011) Chamberlain, G. (2011): “Bayesian aspects of treatment choice,” _The Oxford Handbook of Bayesian Econometrics_ , 11–39.
  * Chernozhukov and Hong (2003) Chernozhukov, V. and H. Hong (2003): “An MCMC approach to classical estimation,” _Journal of Econometrics_ , 115, 293–346.
  * Csaba and Szoke (2020) Csaba, D. and B. Szoke (2020): “Learning with misspecified models,” Tech. rep., mimeo.
  * D’Adamo (2021) D’Adamo, R. (2021): “Policy Learning Under Ambiguity,” _arXiv preprint arXiv:2111.10904_.
  * Dehejia (2005) Dehejia, R. H. (2005): “Program evaluation as a decision problem,” _Journal of Econometrics_ , 125, 141–173.
  * Derbeko et al. (2004) Derbeko, P., R. El-Yaniv, and R. Meir (2004): “Explicit learning curves for transduction and application to clustering and compression algorithms,” _Journal of Artificial Intelligence Research_ , 22, 117–142.
  * Dwork et al. (2012) Dwork, C., M. Hardt, T. Pitassi, O. Reingold, and R. Zemel (2012): “Fairness through awareness,” in _Proceedings of the 3rd innovations in theoretical computer science conference_ , 214–226.
  * Germain et al. (2009) Germain, P., A. Lacasse, F. Laviolette, and M. Marchand (2009): “PAC-Bayesian learning of linear classifiers,” in _Proceedings of the 26th Annual International Conference on Machine Learning_ , ACM, 353–360.
  * Guedj (2019) Guedj, B. (2019): “A primer on PAC-Bayesian learning,” _arXiv preprint arXiv:1901.05353_.
  * Gunsilius (2019) Gunsilius, F. (2019): “A path-sampling method to partially identify causal effects in instrumental variable models,” _arXiv preprint arXiv:1910.09502_.
  * Han (2022) Han, S. (2022): “Optimal dynamic treatment regimes and partial welfare ordering,” _unpublished manuscript_.
  * Heckman et al. (1997) Heckman, J. J., H. Ichimura, and P. E. Todd (1997): “Matching as an econometric evaluation estimator: Evidence from evaluating a job training programme,” _The review of economic studies_ , 64, 605–654.
  * Hirano and Porter (2009) Hirano, K. and J. R. Porter (2009): “Asymptotics for statistical treatment rules,” _Econometrica_ , 77, 1683–1701.
  * Ishihara and Kitagawa (2021) Ishihara, T. and T. Kitagawa (2021): “Evidence Aggregation for Treatment Choice,” _arXiv preprint arXiv:2108.06473_.
  * Karlin and Rubin (1956) Karlin, S. and H. Rubin (1956): “The theory of decision procedures for distributions with monotone likelihood ratio,” _The Annals of Mathematical Statistics_ , 272–299.
  * Kasy (2016) Kasy, M. (2016): “Partial identification, distributional preferences, and the welfare ranking of policies,” _Review of Economics and Statistics_ , 98, 111–131.
  * Kido (2022) Kido, D. (2022): “Distributionally Robust Policy Learning with Wasserstein Distance,” _arXiv preprint arXiv:2205.04637_.
  * Kitagawa et al. (2022) Kitagawa, T., S. Lee, and C. Qiu (2022): “Treatment Choice with Nonlinear Regret,” _arXiv preprint arXiv:2205.08586_.
  * Kitagawa and Rowley (2022) Kitagawa, T. and J. Rowley (2022): “Statistical divergences of von Mises-Fisher distributions,” _arXiv preprint arXiv:2202.05192_.
  * Kitagawa et al. (2021) Kitagawa, T., S. Sakaguchi, and A. Tetenov (2021): “Constrained classification and policy learning,” _arXiv preprint arXiv:2106.12886_.
  * Kitagawa and Tetenov (2018) Kitagawa, T. and A. Tetenov (2018): “Who should be treated? empirical welfare maximization methods for treatment choice,” _Econometrica_ , 86, 591–616.
  * Kitagawa and Tetenov (2021) ——— (2021): “Equality-Minded Treatment Choice,” _Journal of Business Economics and Statistics_ , 39, 561–574.
  * Kock et al. (2022) Kock, A. B., D. Preinerstorfer, and B. Veliyev (2022): “Treatment recommendation with distributional targets,” _Journal of Econometrics_.
  * Kurz and Hanebeck (2015) Kurz, G. and U. D. Hanebeck (2015): “Stochastic sampling of the hyperspherical von Mises–Fisher distribution without rejection methods,” in _2015 Sensor Data Fusion: Trends, Solutions, Applications (SDF)_ , IEEE, 1–6.
  * Liu (2022) Liu, Y. (2022): “Policy Learning under Endogeneity Using Instrumental Variables,” _arXiv preprint arXiv:2206.09883_.
  * Manski (2000a) Manski, C. F. (2000a): “Identification problems and decisions under ambiguity: empirical analysis of treatment response and normative analysis of treatment choice,” _Journal of Econometrics_ , 95, 415–442.
  * Manski (2000b) ——— (2000b): “Using Studies of Treatment Response to Inform Treatment Choice in Heterogeneous Populations,” .
  * Manski (2004) ——— (2004): “Statistical treatment rules for heterogeneous populations,” _Econometrica_ , 72, 1221–1246.
  * Manski (2005) ——— (2005): _Social choice with partial knowledge of treatment response_ , Princeton University Press.
  * Manski (2007a) ——— (2007a): _Identification for prediction and decision_ , Harvard University Press.
  * Manski (2007b) ——— (2007b): “Minimax-regret treatment choice with missing outcome data,” _Journal of Econometrics_ , 139, 105–115.
  * Manski (2009) ——— (2009): “The 2009 Lawrence R. Klein Lecture: Diversified treatment under ambiguity,” _International Economic Review_ , 50, 1013–1041.
  * Manski (2022) ——— (2022): “Identification and Statistical Decision Theory,” _arXiv preprint arXiv:2204.11318_.
  * Manski and Tetenov (2007) Manski, C. F. and A. Tetenov (2007): “Admissible treatment rules for a risk-averse planner with experimental data on an innovation,” _Journal of Statistical Planning and Inference_ , 137, 1998–2010.
  * Mardia and Jupp (2009) Mardia, K. V. and P. E. Jupp (2009): _Directional statistics_ , vol. 494, John Wiley & Sons.
  * Maurer (2004) Maurer, A. (2004): “A note on the PAC Bayesian theorem,” _arXiv preprint cs/0411099_.
  * Mbakop and Tabord-Meehan (2021) Mbakop, E. and M. Tabord-Meehan (2021): “Model selection for treatment choice: Penalized welfare maximization,” _Econometrica_ , 89, 825–848.
  * McAllester (1999) McAllester, D. A. (1999): “Some PAC-Bayesian Theorems,” _Machine Learning_ , 37, 355–363.
  * McAllester (2003) ——— (2003): “PAC-Bayesian stochastic model selection,” _Machine Learning_ , 51, 5–21.
  * Nie et al. (2021) Nie, X., E. Brunskill, and S. Wager (2021): “Learning When-to-Treat Policies,” _Journal of the American Statistical Association_ , 116, 392–409.
  * Pentina and Lampert (2015) Pentina, A. and C. H. Lampert (2015): “Lifelong learning with non-iid tasks,” in _Advances in Neural Information Processing Systems_ , 1540–1548.
  * Rosenbaum and Rubin (1983) Rosenbaum, P. R. and D. B. Rubin (1983): “The central role of the propensity score in observational studies for causal effects,” _Biometrika_ , 70, 41–55.
  * Sakaguchi (2019) Sakaguchi, S. (2019): “Estimating Optimal Dynamic Treatment Assignment Rules under Intertemporal Budget Constraints,” Tech. rep., cemmap working paper.
  * Sasaki and Ura (2020) Sasaki, Y. and T. Ura (2020): “Welfare analysis via marginal treatment effects,” _arXiv preprint arXiv:2012.07624_.
  * Schlag (2006) Schlag, K. H. (2006): “ELEVEN-Tests needed for a Recommendation,” _Economics Working Papers_ , ECO2006/2.
  * Seeger (2002) Seeger, M. (2002): “Pac-bayesian generalisation error bounds for gaussian process classification,” _Journal of machine learning research_ , 3, 233–269.
  * Shawe-Taylor and Williamson (1997) Shawe-Taylor, J. and R. C. Williamson (1997): “A PAC analysis of a Bayesian estimator,” in _Annual Workshop on Computational Learning Theory: Proceedings of the tenth annual conference on Computational learning theory_ , vol. 6, 2–9.
  * Stoye (2009) Stoye, J. (2009): “Minimax regret treatment choice with finite samples,” _Journal of Econometrics_ , 151, 70–81.
  * Stoye (2012) ——— (2012): “Minimax regret treatment choice with covariates or with limited validity of experiments,” _Journal of Econometrics_ , 166, 138–156.
  * Sun (2021) Sun, L. (2021): “Empirical welfare maximization with constraints,” _arXiv preprint_.
  * Swaminathan and Joachims (2015) Swaminathan, A. and T. Joachims (2015): “Counterfactual risk minimization: Learning from logged bandit feedback,” in _International Conference on Machine Learning_ , 814–823.
  * Tetenov (2012) Tetenov, A. (2012): “Statistical treatment choice based on asymmetric minimax regret criteria,” _Journal of Econometrics_ , 166, 157–165.
  * Thompson (1933) Thompson, W. R. (1933): “On the likelihood that one unknown probability exceeds another in view of the evidence of two samples,” _Biometrika_ , 25, 285–294.
  * Valiant (1984) Valiant, L. G. (1984): “A theory of the learnable,” in _Proceedings of the sixteenth annual ACM symposium on Theory of computing_ , ACM, 436–445.
  * Vapnik (1998) Vapnik, V. N. (1998): _Statistical Learning Theory_ , Wiley.
  * Viviano (2021) Viviano, D. (2021): “Policy targeting under network interference,” _arXiv preprint_.
  * Wainwright and Jordan (2008) Wainwright, M. J. and M. I. Jordan (2008): “Graphical Models, Exponential Families, and Variational Inference,” _Foundations and Trends in Machine Learning_ , 1, 1 – 305.
  * Wood (1994) Wood, A. T. (1994): “Simulation of the von Mises Fisher distribution,” _Communications in statistics-simulation and computation_ , 23, 157–164.
  * Yata (2021) Yata, K. (2021): “Optimal Decision Rules Under Partial Identification,” _arXiv preprint arXiv:2111.04926_.
  * Zadrozny (2003) Zadrozny, B. (2003): “Policy mining: Learning decision policies from fixed sets of data,” Ph.D. thesis, University of California, San Diego.
  * Zhang et al. (2012) Zhang, B., A. A. Tsiatis, M. Davidian, M. Zhang, and E. Laber (2012): “Estimating optimal treatment regimes from a classification perspective,” _Stat_ , 1, 103–114.
  * Zhao et al. (2012) Zhao, Y., D. Zeng, A. J. Rush, and M. R. Kosorok (2012): “Estimating individualized treatment rules using outcome weighted learning,” _Journal of the American Statistical Association_ , 107, 1106–1118.

##  Appendix A Proofs of theorems and associated lemmata

###  A.1 Proof of Theorem 1

We let $c$ denote a convex function mapping the unit square to the reals. Then

$\displaystyle n\cdot c\left(R^{\Pi}_{S},R^{\Pi}\right)$ $\displaystyle=n\cdot
c\left(\mathrm{E}_{\Pi}(R_{S}(g)),\mathrm{E}_{\Pi}(R(g))\right),$ (A.1)
$\displaystyle\leq\mathrm{E}_{\Pi}\left(n\cdot c(R_{S}(g),R(g))\right),$

by convexity.

######  Bégin et al. (2016, §Lemma 3) (Kullback-Leibler change of measure).

Let $\phi$ be any measurable function mapping $\mathscr{G}$ to the reals. For
any $g\in\mathscr{G}$ and any distributions $\Pi$ and $\pi_{0}$ on
$\mathscr{G}$ such that $\Pi$ is absolutely continuous with respect to
$\pi_{0}$,

$\mathrm{E}_{\Pi}\left(\phi(g)\right)\leq\mathrm{KL}(\Pi\|\pi_{0})+\ln\left(\,\mathrm{E}_{\Pi}\left(\exp\left({\phi(g)}\right)\right)\right).$
(A.2)

We let $\phi(g)=n\cdot c(R_{S}(g),R(g))$, and so

$\mathrm{E}_{\Pi}\left(n\cdot
c\left(R_{S}(g),R(f)\right)\right)\leq\mathrm{KL}(\Pi\|\pi_{0})+\ln\left(\mathrm{E}_{\Pi}\left(\exp\left({n\cdot
c(R_{S}(g),R(g))}\right)\right)\right).$ (A.3)

We then apply Markov’s inequality to $\mathrm{E}_{\Pi}\left(\exp\left({n\cdot
c(R_{S}(g),R(g))}\right)\right)$ to obtain

$P^{n}\left(\mathrm{E}_{\Pi}\left(\exp\left({n\cdot
c(R_{S}(g),R(g))}\right)\right)\geq\frac{1}{\epsilon}\cdot\mathrm{E}_{P^{n}}\left(\mathrm{E}_{\Pi}\left(\exp\left({n\cdot
c(R_{S}(g),R(g))}\right)\right)\right)\right)\leq\epsilon.$ (A.4)

Thus, with probability at least $1-\epsilon$ we have, for all
$\Pi\in\mathscr{M}$,

$\mathrm{E}_{\Pi}\left(\exp\left({n\cdot
c(R_{S}(g),R(g))}\right)\right)\leq\frac{1}{\epsilon}\cdot\mathrm{E}_{P^{n}}\left(\mathrm{E}_{\Pi}\left(\exp\left({n\cdot
c(R_{S}(g),R(g))}\right)\right)\right).$ (A.5)

Combining Equations A.1, A.3 and A.5, we obtain

$n\cdot
c\left(R_{S}^{\Pi},R^{\Pi}\right)\leq\mathrm{KL}(\Pi\|\pi_{0})+\ln\left(\frac{1}{\epsilon}\cdot\mathrm{E}_{P^{n}}\left(\mathrm{E}_{\pi_{0}}\left(\exp\left({n\cdot
c\left(R_{S}(g),R(g)\right)}\right)\right)\right)\right).$ (A.6)

We now look to simplify
$\mathrm{E}_{P^{n}}\left(\mathrm{E}_{\pi_{0}}\left(\exp\left({n\cdot
c\left(R_{S}(g),R(g)\right)}\right)\right)\right)$.

######  Maurer (2004, §Lemma 3).

Let $U$ denote a vector of $n$ independent and identically distributed random
variables, each with values in the unit interval and $\mathrm{E}(U)=\mu$. In
addition, let $U^{\dagger}$ be a Bernoulli random variable satisfying
$\mathrm{E}(U^{\dagger})=\mu$. Suppose that $b$ is a convex function that maps
an $n$-dimensional binary vector to the reals. Then

$\mathrm{E}\left(b(U)\right)\leq\mathrm{E}\left(b(U^{\dagger})\right).$ (A.7)

If $t$ is permutation-symmetric in its arguments and $\theta(k)$ denotes the
$n$-dimensional binary vector whose first $k$ coordinates are one and whose
remaining $n-k$ coordinates are zero, we also have

$\mathrm{E}\left(b(U^{\dagger})\right)=\sum_{k=0}^{n}{n\choose
k}\cdot(1-\mu)^{n-k}\cdot\mu^{k}\cdot b(\theta(k)).$ (A.8)

We then note that, by defining
$b(U^{\dagger})=\frac{1}{n}\sum_{i=1}^{n}U_{i}^{\dagger}$ such that
$\mathrm{E}_{P^{n}}\left(b(U^{\dagger})\right)=\mathrm{E}_{P^{n}}\left(R_{S}(g)\right)=R(g)$,
since $c(\cdot,R(g))$ is convex, and since the exponential function is convex
and non-decreasing, $\exp\left({c(\cdot,R(g))}\right)$ is convex. Applying
Equation A.7, we obtain

$\mathrm{E}_{P^{n}}\left(\mathrm{E}_{\pi_{0}}\left(\exp\left({n\cdot
c\left(R_{S}(g),R(g)\right)}\right)\right)\right)\leq\mathrm{E}_{P^{n}}\left(\mathrm{E}_{\pi_{0}}\left(\exp\left({n\cdot
c\left(b(U^{\dagger}),R(g)\right)}\right)\right)\right),$ (A.9)

into which we substitute the definition of the expectation to write

$\displaystyle\mathrm{E}_{P^{n}}\left(\mathrm{E}_{\pi_{0}}\left(\exp\left({n\cdot
c\left(R_{S}(g),R(g)\right)}\right)\right)\right)$
$\displaystyle\leq\mathrm{E}_{\pi_{0}}\left(\sum_{k}P^{n}\left(b(U^{\dagger})=\frac{k}{n}\right)\cdot\exp\left({n\cdot
c\left(\frac{k}{n},R(g)\right)}\right)\right),$ (A.10)

where we omit the limits of summation to avoid confusion. We then apply
Equation A.8 and the binomial theorem to obtain

$\displaystyle\mathrm{E}_{\pi_{0}}\left(\underset{k}{\overset{}{\sum}}P^{n}\left(b(U^{\dagger})=\frac{k}{n}\right)\cdot\exp\left({n\cdot
c\left(\frac{k}{n},R(g)\right)}\right)\right)$
$\displaystyle=\mathrm{E}_{\pi_{0}}\left(\underset{k=0}{\overset{n}{\sum}}{n\choose
k}\cdot R(g)^{k}\cdot(1-R(g))^{n-k}\cdot\exp\left({n\cdot
c\left(\frac{k}{n},R(g)\right)}\right)\right),$ (A.11)
$\displaystyle=\mathrm{E}_{\pi_{0}}\left(\sum_{k=0}^{n}\mathrm{Bin}_{k}^{n}(R(g))\cdot\exp\left({n\cdot
c\left(\frac{k}{n},R(g)\right)}\right)\right),$ (A.12)
$\displaystyle\leq\sup_{r\in[0,1]}\,\sum_{k=0}^{n}\mathrm{Bin}_{k}^{n}(r)\cdot\exp\left({n\cdot
c\left(\frac{k}{n},r\right)}\right).$ (A.13)

If

$\displaystyle c\left(q,p\right)$
$\displaystyle=\mathrm{KL}\left(q\|p\right),$ (A.14)
$\displaystyle=q\cdot\mathrm{ln}\left(\frac{q}{p}\right)+\left(1-q\right)\cdot\mathrm{ln}\left(\frac{1-q}{1-p}\right),$

then

$\displaystyle\sup_{r\in[0,1]}\sum_{k=0}^{n}\mathrm{Bin}_{k}^{n}(r)\cdot\exp\left({n\cdot
c\left(\frac{k}{n},r\right)}\right)$
$\displaystyle=\sup_{r\in[0,1]}\sum_{k=0}^{n}{n\choose
k}\cdot\left(\frac{k}{n}\right)^{k}\cdot\left(1-\frac{k}{n}\right)^{n-k},$
(A.15) $\displaystyle=\sum_{k=0}^{n}{n\choose
k}\cdot\left(\frac{k}{n}\right)^{k}\cdot\left(1-\frac{k}{n}\right)^{n-k},$
(A.16) $\displaystyle\equiv\mathscr{I}_{KL},$ (A.17)

which is a function of $n$ only.

######  Maurer (2004, §Theorem 1).

For all $n\geq 2$,

$\mathrm{E}\left(\exp\left({n\cdot\mathrm{KL}(R_{S}(g)\|R(g))}\right)\right)\leq\exp\left(\frac{1}{12n}\right)\cdot\sqrt{\frac{\pi
n}{2}}+2.$ (A.18)

We emphasise that, here, $\pi$ signifies the mathematical constant rather than
a probability distribution. As is discussed in Maurer (2004), for all $n\geq
8$,

$\exp\left(\frac{1}{12n}\right)\cdot\sqrt{\frac{\pi n}{2}}+2\leq 2\sqrt{n}.$
(A.19)

Hence, for all $n\geq 8$ we have $\mathscr{I}_{KL}\leq 2\sqrt{n}$. We are of
course interested in the maximum distance between the expected welfare risk
and its empirical analogue and so define $c_{V^{2}}(q,p)=2(q-p)^{2}$. Finally,
we substitute $c_{V^{2}}(q,p)$ into Equation A.6 and utilise Pinsker’s
Inequality, which states that $c_{V^{2}}(q,p)\leq\mathrm{KL}(q\|p)$, together
with Maurer (2004, §Theorem 1) to obtain

$\displaystyle R^{\Pi}-R^{\Pi}_{S}$
$\displaystyle\leq\sqrt{\frac{1}{2n}\cdot\mathrm{KL}(\Pi\|\pi_{0})+\frac{1}{2n}\cdot\ln\left(\frac{1}{\epsilon}\cdot\mathrm{E}_{P^{n}}\left(\mathrm{E}_{\pi_{0}}\left(\exp\left({n\cdot
c_{V^{2}}\left(R_{S}(g),R(g)\right)}\right)\right)\right)\right)},$ (A.20)
$\displaystyle\leq\sqrt{\frac{1}{2n}\cdot\mathrm{KL}(\Pi\|\pi_{0})+\frac{1}{2n}\cdot\ln\left(\frac{1}{\epsilon}\cdot\mathrm{E}_{P^{n}}\left(\mathrm{E}_{\pi_{0}}\left(\exp\left({n\cdot\mathrm{KL}\left(R_{S}(g)\|R(g)\right)}\right)\right)\right)\right)},$
(A.21)
$\displaystyle\leq\sqrt{\frac{1}{2n}\cdot\mathrm{KL}(\Pi\|\pi_{0})+\frac{1}{2n}\cdot\ln\left(\frac{1}{\epsilon}\cdot\mathscr{I}_{KL}\right)},$
(A.22)
$\displaystyle\leq\sqrt{\frac{1}{2n}\left(\mathrm{KL}(\Pi\|\pi_{0})+\ln\left(\frac{2\sqrt{n}}{\epsilon}\right)\right)}.$
(A.23)

The desired result follows by rearrangement.

###  A.2 Proof of Theorem 2

An optimal posterior minimises

$\displaystyle\mathrm{E}_{\Pi}\left(R_{S}(g)\right)+\sqrt{\frac{1}{2n}\cdot\left(\mathrm{E}_{\Pi}\left(\ln\left(\frac{\mathrm{d}\Pi(g)}{{\mathrm{d}\pi_{0}}(g)}\right)\right)+\ln\left(\frac{2\sqrt{n}}{\epsilon}\right)\right)}\text{
subject to }\int_{\mathscr{G}}\mathrm{d}\Pi(g)=1,$ (A.24)
$\displaystyle\inf_{g\in\mathscr{G}}\,\mathrm{d}\Pi(g)\geq 0.$

Provided that the solution satisfies the non-negativity constraints (the
second constraint of Equation A.24), this is equivalent to minimising

$\int_{\mathscr{G}}R_{S}(g)\cdot\mathrm{d}\Pi(g)+\sqrt{\frac{1}{2n}\cdot\left(\int_{\mathscr{G}}\ln\left(\frac{\mathrm{d}\Pi(g)}{{\mathrm{d}\pi_{0}}(g)}\right)\cdot\mathrm{d}\Pi(g)+\ln\left(\frac{2\sqrt{n}}{\epsilon}\right)\right)}+\xi\cdot\left(\int_{\mathscr{G}}\mathrm{d}\Pi(g)-1\right),$
(A.25)

where $\xi$ is the Lagrange multiplier. We separate this minimisation into two
parts, by minimising Equation A.25 over $\Pi$ subject to its Kullbuck-Leibler
divergence from $\pi_{0}$ being equal to $c\geq 0$ and, subsequently, by
searching for the $c$ that minimises the objective function.

We can write the constrained minimisation that forms the first part of the
problem as

$\int_{\mathscr{G}}R_{S}(g)\cdot\mathrm{d}\Pi(g)+\sqrt{\frac{1}{2n}\cdot\left(c+\ln\left(\frac{2\sqrt{n}}{\epsilon}\right)\right)}+\xi\cdot\left(\int_{\mathscr{G}}\mathrm{d}\Pi(g)-1\right)+\frac{1}{\chi}\cdot\left(\int_{\mathscr{G}}\ln\left(\frac{\mathrm{d}\Pi(g)}{{\mathrm{d}\pi_{0}}(g)}\right)\cdot\mathrm{d}\Pi(g)-c\right),$
(A.26)

where $\xi$ and $1/\chi$ are Lagrange multipliers, and where $c\geq 0$ is a
constant, provided that the omitted non-negativity constraints are satisfied
at the solution. The associated first order condition of the minimand with
respect to $\mathrm{d}\Pi(g)$ is

$R_{S}(g)+\xi+\frac{1}{\chi}\cdot\left(\ln\left(\frac{\mathrm{d}\Pi(g)}{\mathrm{d}\pi_{0}(g)}\right)+1\right)=0.$
(A.27)

Rearranging, we obtain

$\mathrm{d}\Pi^{*}(g)=\frac{\exp\left({-\chi\cdot
R_{S}(g)}\right)}{\exp\left({1+\xi\cdot\chi}\right)}\cdot\mathrm{d}{\pi_{0}}(g),$
(A.28)

where we emphasise that $\Pi^{*}$ is a function of $\chi$. In view of the
first constraint of Equation A.25,

$\exp\left({1+\xi\cdot\chi}\right)=\int_{\mathscr{G}}\exp\left({-\chi\cdot
R_{S}(g)}\right)\cdot\mathrm{d}\pi_{0}(g),$ (A.29)

and so, for all $g\in\mathscr{G}$,

$\mathrm{d}\Pi^{*}(g)=\frac{\exp\left(-\chi\cdot
R_{S}(g)\right)}{\int_{\mathscr{G}}\exp\left(-\chi\cdot
R_{S}(g)\right)\cdot\mathrm{d}{\pi_{0}}(g)}\cdot{\mathrm{d}\pi_{0}(g)},$
(A.30)

which integrates to one as is required. We reiterate that Equation A.30 is
derived for an arbitrary $c\geq 0$, and so holds for any feasible values of
$\chi$.

For $\Pi^{*}$ to satisfy $\mathrm{KL}(\Pi^{*}\|\pi_{0})=c$, we require that

$\displaystyle c$
$\displaystyle=\int_{\mathscr{G}}\ln\left(\frac{\mathrm{d}\Pi^{*}(g)}{\mathrm{d}\pi_{0}(g)}\right)\cdot\mathrm{d}\Pi^{*}(g),$
(A.31) $\displaystyle=-\int_{\mathscr{G}}\chi\cdot
R_{S}(g)\cdot\mathrm{d}\Pi^{*}(g)-\ln\left(\int_{\mathscr{G}}\exp\left(-\chi\cdot
R_{S}(g)\right)\cdot\mathrm{d}{\pi_{0}}(g)\right).$

This relationship between the radius of the Kullback-Leibler ball and the
inverse of the Lagrange multiplier shows that $c$ is strictly monotonically
increasing in $\chi>0$ provided that $R_{S}(g)$ is not constant over those $g$
supported by $\pi_{0}$, since

$\displaystyle\frac{\mathrm{d}c}{\mathrm{d}\chi}$
$\displaystyle=-\int_{\mathscr{G}}R_{S}(g)\cdot\mathrm{d}\Pi^{*}(g)-\int_{\mathscr{G}}\chi\cdot
R_{S}(g)\cdot\frac{\mathrm{d}}{\mathrm{d}\chi}\left(\frac{\mathrm{d}\Pi^{*}(g)}{\mathrm{d}\pi_{0}(g)}\right)\cdot\mathrm{d}\pi_{0}+\int_{\mathscr{G}}R_{S}(g)\cdot\mathrm{d}\Pi^{*}(g)$
(A.32)
$\displaystyle=\chi\cdot\int_{\mathscr{G}}\left(R_{S}(g)-R_{S}^{\Pi^{*}}\right)^{2}\cdot\mathrm{d}\Pi^{*}(g)$
(A.33) $\displaystyle\geq 0,$ (A.34)

where Equation A.34 is strict if $\chi>0$ and $R_{S}(g)\neq R_{S}^{\Pi^{*}}$
for at least some $g$ supported by $\pi_{0}$. Accordingly, in the second part
of the optimisation, we substitute $\Pi^{*}$ into Equation A.26 in place of
$\Pi$ and solve the unconstrained minimisation problem with respect to $\chi$.
That is, we solve

$\min_{\chi}\left\\{R_{S}^{\Pi^{*}}+\underbrace{\sqrt{\frac{1}{2n}\cdot\left(-\chi\cdot
R_{S}^{\Pi^{*}}-\ln\left(\int_{\mathscr{G}}\exp\left(-\chi\cdot
R_{S}(g)\right)\cdot\mathrm{d}\pi_{0}(g)\right)+\ln\left(\frac{2\sqrt{n}}{\epsilon}\right)\right)}}_{\textrm{Penalty}}\right\\}.$
(A.35)

We note that

$\displaystyle\frac{\mathrm{d}}{\mathrm{d}\chi}R^{\Pi^{*}}_{S}$
$\displaystyle=\frac{\mathrm{d}}{\mathrm{d}\chi}\int_{\mathscr{G}}R_{S}(g)\cdot\frac{\exp\left(-\chi\cdot
R_{S}(g)\right)}{\int_{\mathscr{G}}\exp\left(-\chi\cdot
R_{S}(g)\right)\cdot\mathrm{d}{\pi_{0}}(g)}\cdot{\mathrm{d}\pi_{0}(g)},$
(A.36)
$\displaystyle=\int_{\mathscr{G}}R_{S}(g)\cdot\frac{\mathrm{d}}{\mathrm{d}\chi}\frac{\exp\left(-\chi\cdot
R_{S}(g)\right)}{\int_{\mathscr{G}}\exp\left(-\chi\cdot
R_{S}(g)\right)\cdot\mathrm{d}{\pi_{0}}(g)}\cdot{\mathrm{d}\pi_{0}(g)},$
$\displaystyle=-\int_{\mathscr{G}}\left(R_{S}(g)-R_{S}^{\Pi^{*}}\right)^{2}\cdot\mathrm{d}\Pi^{*}(g),$

which we interpret as the variance of empirical welfare risk under $\Pi^{*}$.
Using this result, we further note that

$\displaystyle\frac{\mathrm{d}}{\mathrm{d}\chi}\textrm{Penalty}$
$\displaystyle=\frac{1}{4n\cdot\textrm{Penalty}}\cdot\left(-R_{S}^{\Pi^{*}}-\chi\cdot\frac{\mathrm{d}}{\mathrm{d}\chi}R^{\Pi^{*}}_{S}+\frac{\int_{\mathscr{G}}R_{S}(g)\cdot\exp\left(-\chi\cdot
R_{S}(g)\right)\cdot\mathrm{d}\pi_{0}(g)}{\int_{\mathscr{G}}\exp\left(-\chi\cdot
R_{S}(g)\right)\cdot\mathrm{d}\pi_{0}(g)}\right),$ (A.37)
$\displaystyle=\frac{1}{4n\cdot\textrm{Penalty}}\cdot-\chi\cdot\frac{\mathrm{d}}{\mathrm{d}\chi}R^{\Pi^{*}}_{S},$
$\displaystyle=\frac{1}{4n\cdot\textrm{Penalty}}\cdot\chi\cdot\int_{\mathscr{G}}\left(R_{S}(g)-R_{S}^{\Pi^{*}}\right)^{2}\cdot\mathrm{d}\Pi^{*}(g).$

Together Equations A.36 and A.37 imply that the associated first order
condition of Equation A.35 with respect to $\chi$ is

$\frac{1}{4n\cdot\textrm{Penalty}}\cdot\chi\cdot\int_{\mathscr{G}}\left(R_{S}(g)-R_{S}^{\Pi^{*}}\right)^{2}\cdot\mathrm{d}\Pi^{*}(g)=\int_{\mathscr{G}}\left(R_{S}(g)-R_{S}^{\Pi^{*}}\right)^{2}\cdot\mathrm{d}\Pi^{*}(g).$
(A.38)

Provided – trivially, we might add – that $\Pi^{*}$ is not degenerate and
there is variation in empirical welfare risk (the conditions under which
Equation A.34 is strict), then this condition reduces to

$\chi=4n\cdot\sqrt{\frac{1}{2n}\cdot\left(\mathrm{KL}(\Pi^{*}\|\pi_{0})+\ln\left(\frac{2\sqrt{n}}{\epsilon}\right)\right)},$
(A.39)

which is exactly the condition that appears in Theorem 2.

Although Equations A.39 and A.30 characterise a possible interior solution of
the optimisation, we have yet to guarantee that this proposed solution is a
global optimum. To address this, we show that the two possible corner
solutions are sub-optimal, such that the first order conditions from which
Equation A.39 are derived are applicable. Continuity and differentiability of
Equation A.26 are then sufficient111111It is possible to show that the
difference between the left- and right-hand sides of Equation A.39 is negative
at $\chi=0$ and positive if $\chi$ is sufficiently large, with existence then
established using extensions of the intermediate value theorem and its
corollary, Bolzano’s theorem. to guarantee that a fixed point satisfying
Equation A.39 exists.

Neither $\pi_{0}$ nor a degenerate distribution are optimal. To establish that
$\pi_{0}$ is not optimal, we note that $\Pi^{*}$ coincides with $\pi_{0}$ when
$\chi=0$. By marginally increasing $\chi$, such that we move in the direction
of $\Pi^{*}$, we obtain a probability distribution that is in the interior. It
suffices to show that such a probability distribution reduces the value of the
objective function relative to $\pi_{0}$. Evaluating Equations A.36 and A.37
at $\chi=0$, we obtain

$\displaystyle\frac{\mathrm{d}}{\mathrm{d}\chi}\left.\left(R^{\Pi^{*}}_{S}+\textrm{Penalty}\right)\right|_{\chi=0}$
$\displaystyle=\frac{\mathrm{d}}{\mathrm{d}\chi}R^{\pi_{0}}_{S},$ (A.40)
$\displaystyle<0,$

as we require, with any $\chi$ satisfying $0<\chi<2n\cdot R^{\pi_{0}}$
yielding a strictly lower value than $\chi=0$. To establish that a degenerate
distribution is not optimal, we note that such a distribution implies infinite
divergence from $\pi_{0}$ (if $\pi_{0}$ were itself degenerate then our
analysis would be meaningless since the prior and posterior distributions
would always coincide; and if $\pi_{0}$ is atomic then the discrete case would
apply). Given that $\pi_{0}$ attains a finite value of the objective function,
however, $\pi_{0}$ is always preferred to a degenerate distribution, and so a
degenerate distribution cannot be optimal.

###  A.3 Proof of Lemma 1

In the course of this proof, we rely on several results in Alquier et al.
(2016) and follow the standard PAC-Bayesian approach (see Catoni, 2007). We
define

$\mathrm{d}\Pi^{*}(g)=\frac{\exp\left(-\lambda\cdot(R(g)-R_{S}(g))\right)}{\int_{\mathscr{G}}\exp\left(-\lambda\cdot(R(g)-R_{S}(g))\right)\cdot\mathrm{d}{\pi_{0}}(g)}\cdot{\mathrm{d}\pi_{0}(g)},$
(A.41)

which differs from Equation A.30 in its use of the notation $\lambda$ rather
than $\chi$ and in terms of the measures of risk that it uses, such that

$\ln\left(\int_{\mathscr{G}}\exp(-\lambda\cdot(R(g)-R_{S}(g)))\cdot\mathrm{d}{\pi_{0}(g)}\right)=-\inf_{\Pi\in\mathscr{M}}\,\left\\{\int_{\mathscr{G}}\lambda\cdot(R(g)-R_{S}(g))\cdot\mathrm{d}\Pi(g)+\mathrm{KL}(\Pi\|{\pi_{0}})\right\\},$
(A.42)

by definition of the Kullback-Leibler divergence and of $\Pi^{*}$.

As in Alquier et al. (2016), we define a Hoeffding assumption as

$\mathrm{E}_{\pi_{0}}\left(\mathrm{E}_{P^{n}}\left(\exp\left({\lambda\cdot\left(R(g)-R_{S}(g)\right)}\right)\right)\right)\leq\exp\left({a(\lambda,n)}\right),$
(A.43)

where $a$ is a function that depends upon $\lambda>0$. This follows directly
from applying Hoeffding’s lemma (Boucheron et al., 2013) to the left-hand side
of Equation A.43 and then taking the expectation over $\mathscr{G}$ with
respect to $\pi_{0}$. As we have bounded the welfare criterion such that it is
contained in the unit interval, this assumption holds directly without any
further restrictions. Applying Fubini’s Theorem to Equation A.43, we obtain

$\mathrm{E}_{P^{n}}\left(\int\exp\left(\lambda\cdot(R_{S}(g)-R(g))-a(\lambda,n)\right)\cdot
d{\pi_{0}}\right)\leq 1.$ (A.44)

Given that (A.42) can be re-stated as

$\int_{\mathscr{G}}\exp\left(-\lambda\cdot\left(R(g)-R_{S}(g)\right)\right)\cdot\mathrm{d}{\pi_{0}(g)}=\exp\left(\sup_{\Pi\in\mathscr{M}}\,\int_{\mathscr{G}}\lambda\cdot\left(R_{S}(g)-R(g)\right)\cdot\mathrm{d}\Pi(g)-\mathrm{KL}(\Pi\|{\pi_{0}})\right),$
(A.45)

it follows from Equations A.42 and A.44 that

$\mathrm{E}_{P^{n}}\left(\exp\left(\sup_{\Pi\in\mathscr{M}}\,\lambda\cdot\int_{\mathscr{G}}(R_{S}(g)-R(g))\cdot\mathrm{d}\Pi(g)-\mathrm{KL}(\Pi\|\pi_{0})-a(\lambda,n)\right)\right)\leq
1.$ (A.46)

Multiplying both sides of Equation A.46 by $\epsilon/2$ and using the fact
that $\mathrm{E}\left(\exp(U)\right)\geq\Pr(U>0)$ for any random variable $U$,
we obtain

$P^{n}\left(\sup_{\Pi\in\mathscr{M}}\,\lambda\cdot\int_{\mathscr{G}}\left(R_{S}(g)-R(g)\right)\cdot\mathrm{d}\Pi(g)-\mathrm{KL}(\Pi||{\pi_{0}})-a(\lambda,n)+\ln\left(\frac{\epsilon}{2}\right)>0\right)\leq\frac{\epsilon}{2}.$
(A.47)

Keeping this bound in mind, we now turn to the problem of bounding expected
welfare regret.

We let $c$ denote a convex function that maps from the unit square to the
reals. Then, by Jensen’s Inequality,

$\displaystyle n\cdot c\left(R^{\Pi}_{S},R^{\Pi}\right)$ $\displaystyle=n\cdot
c\left(\mathrm{E}_{\Pi}\left(R_{S}(g)\right),\mathrm{E}_{\Pi}\left(R(g)\right)\right),$
(A.48) $\displaystyle\leq\mathrm{E}_{\Pi}\left(n\cdot
c\left(R_{S}(g),R(g)\right)\right).$

Letting $\phi(g)=n\cdot c(R_{S}(g),R(g))$, we apply Bégin et al. (2016, §Lemma
3) to obtain

$\mathrm{E}_{\Pi}\left(n\cdot
c(R_{S}(g),R(g))\right)\leq\mathrm{KL}(\Pi\|{\pi_{0}})+\ln\left(\mathrm{E}_{\pi_{0}}\left(\exp\left(n\cdot
c(R_{S}(g),R(g))\right)\right)\right),$ (A.49)

which, in conjunction with Equation A.48, yields

$n\cdot
c\left(R^{\Pi}_{S},R^{\Pi}\right)\leq\mathrm{KL}(\Pi\|{\pi_{0}})+\ln\left(\mathrm{E}_{\pi_{0}}\left(\exp\left(n\cdot
c(R_{S}(g),R(g))\right)\right)\right).$ (A.50)

We then apply Markov’s inequality to the term inside the logarithm, which
yields

$P^{n}\left(\mathrm{E}_{\pi_{0}}\left(\exp\left(n\cdot
c(R_{S}(g),R(g))\right)\right)\geq\frac{2}{\epsilon}\cdot\mathrm{E}_{P^{n}}\left(\mathrm{E}_{\pi_{0}}\left(\exp\left(n\cdot
c(R_{S}(g),R(g))\right)\right)\right)\right)\leq\frac{\epsilon}{2}.$ (A.51)

Combining Equations A.47 and A.51 by means of Bonferroni’s inequalities, we
determine that, for all $\Pi\in\mathscr{M}$,

$\mathrm{E}_{\pi_{0}}\left(\exp\left(n\cdot
c(R_{S}(g),R(g))\right)\right)\leq\frac{2}{\epsilon}\cdot\mathrm{E}_{P^{n}}\left(\mathrm{E}_{\pi_{0}}\left(\exp\left(n\cdot
c(R_{S}(g),R(g))\right)\right)\right),$ (A.52)

and

$\lambda\cdot\mathrm{E}_{\Pi}\left(R_{S}(g)\right)\leq\lambda\cdot\mathrm{E}_{\Pi}\left(R(g)\right)+\mathrm{KL}(\Pi||{\pi_{0}})+a(\lambda,n)+\ln\left(\frac{2}{\epsilon}\right),$
(A.53)

which both hold simultaneously with probability at least $1-\epsilon$. We then
take the exponential of both sides of Equation A.50 and rearrange, relating
the result to the left-hand side of Equation A.52 to obtain

$n\cdot
c\left(R_{S}^{\Pi},R^{\Pi}\right)\leq\mathrm{KL}(\Pi\|{\pi_{0}})+\ln\left(\frac{2}{\epsilon}\cdot\mathrm{E}_{P^{n}}\left(\mathrm{E}_{\pi_{0}}\left(\exp\left(n\cdot
c\left(R_{S}(g),R(g)\right)\right)\right)\right)\right).$ (A.54)

We note that Equation A.54 is identical to Equation A.6 except for the
logarithm on the right hand-side, the argument of which differs only in the
constant that multiplies the expectation. As such, and following the steps of
Section A.1 that follow Equation A.6, we are able to show that, for all
$\Pi\in\mathscr{M}$,

$R^{\Pi}\leq
R_{S}^{\Pi}+\sqrt{\frac{1}{2n}\cdot\left(\mathrm{KL}(\Pi||{\pi_{0}})+\ln\left(\frac{4\sqrt{n}}{\epsilon}\right)\right)},$
(A.55)

and

$\lambda R_{S}^{\Pi}\leq\lambda\cdot
R^{\Pi}+\mathrm{KL}(\Pi||{\pi_{0}})+a(\lambda,n)+\ln\left(\frac{2}{\epsilon}\right),$
(A.56)

which both hold simultaneously with probability at least $1-\epsilon$. We now
denote by $\mathscr{V}\subset\mathscr{M}$ a family of distributions over the
class of feasible assignment rules and restrict attention to this subset.
Since $\mathscr{V}\subset\mathscr{M}$, Equations A.55 and A.56 hold with
probability at least $1-\epsilon$ for all $\Pi\in\mathscr{V}$ and, in
particular, for the variational approximation of $\Pi^{*}$, which we define as

$\tilde{\Pi}=\operatorname*{argmin}_{\Pi\in\mathscr{G}}\,\mathrm{KL}(\Pi\|\Pi^{*}).$
(A.57)

Hence, from Equation A.55,

$R^{\tilde{\Pi}}\leq\inf_{\Pi\in\mathscr{V}}\,R_{S}^{\Pi}+\sqrt{\frac{1}{2n}\left(\mathrm{KL}(\Pi||{\pi_{0}})+\ln\left(\frac{4\sqrt{n}}{\epsilon}\right)\right)}.$
(A.58)

Finally, dividing both sides of Equation A.56 by $\lambda$ and replacing
$R^{\Pi}_{S}$ inside the infimum of Equation A.58 with the right-hand side of
Equation A.56, we obtain the required result, which we reiterate holds with
probability at least $1-\epsilon$.

###  A.4 Proof of Theorem 3

We rely on an intermediate result that we introduce now, in advance of the
proof.

######  Lemma 2.

The circular variance of a von Mises-Fisher random vector with concentration
parameter $\kappa\geq 0$ is bounded from above by

$\frac{\underline{c}_{\nu}+\sqrt{\kappa^{2}+\overline{c}_{\nu}^{2}}-\kappa}{\underline{c}_{\nu}+\sqrt{\kappa^{2}+\overline{c}_{\nu}^{2}}},$
(A.59)

where $\nu=m/2-1$ for convenience, with $\underline{c}_{\nu}=\nu+1/2$ and
$\overline{c}_{\nu}=\nu+3/2$.

As is shown in Kitagawa and Rowley (2022), the circular variance is an
$\mathrm{O}(\kappa^{-1})$ function. Proof of Lemma 2 is deferred until the end
of this proof.

######  Lemma 3.

The Kullback-Leibler divergence of a von Mises-Fisher random vector with
concentration parameter $\kappa\geq 0$ is bounded from above by

$\underline{c}_{\nu}\cdot\ln\left(\frac{\underline{c}_{\nu}+\sqrt{\kappa^{2}+\overline{c}_{\nu}^{2}}}{\underline{c}_{\nu}+\overline{c}_{\nu}}\right)+\sqrt{\vphantom{\overline{c}_{\nu}^{2}}\kappa^{2}+\underline{c}_{\nu}^{2}}-\sqrt{\kappa^{2}+\overline{c}_{\nu}^{2}}+1,$
(A.60)

where $\nu=m/2-1$ for convenience, with $\underline{c}_{\nu}=\nu+1/2$ and
$\overline{c}_{\nu}=\nu+3/2$.

As is shown in Kitagawa and Rowley (2022), the Kullback-Leibler divergence is
an $\mathrm{O}(\ln\left(\kappa\right))$ function. Proof of Lemma 3 is deferred
until the end of this proof.

With Lemmas 2 and 3 to hand, we begin by noting that, together, Assumptions 5
and 1 imply that

$R^{\tilde{\Pi}}\leq\bar{R}+\inf_{\mu,\kappa}a_{1}+a_{2}+\sqrt{a_{3}},$ (A.61)

where

$\displaystyle a_{1}$
$\displaystyle=\int_{\mathbb{S}^{m-1}}2c\cdot\|\beta-\overline{\beta}\|_{2}\cdot\mathrm{d}\Pi(\beta;\kappa,\mu)\vphantom{\left(\frac{1}{\lambda}\right)},$
(A.62) $\displaystyle a_{2}$
$\displaystyle=\frac{1}{\lambda}\cdot\left(a(\lambda,n)+\mathrm{KL}(\Pi||{\pi_{0}})+\ln\left(\frac{2}{\epsilon}\right)\right),$
$\displaystyle a_{3}$
$\displaystyle=\frac{1}{2n}\cdot\left(\mathrm{KL}(\Pi||{\pi_{0}})+\ln\left(\frac{4\sqrt{n}}{\epsilon}\right)\right),$

and where $\mathbb{S}^{m}$ is the $m$-sphere (i.e., the hypersphere in
$\mathbb{R}^{m+1})$.

Focusing on $a_{1}$, we use Jensen’s inequality to show that

$\displaystyle
2c\cdot\int_{\mathbb{S}^{m-1}}\|\beta-\overline{\beta}\|_{2}\cdot\mathrm{d}\Pi(\beta;\kappa,\mu)$
$\displaystyle\leq
2c\cdot\sqrt{\int_{\mathbb{S}^{m-1}}\sum_{l=0}^{m}(\beta_{l}-overline{\beta}_{l})^{2}\cdot\mathrm{d}\Pi(\beta;\kappa,\mu)}$
(A.63)
$\displaystyle=2c\cdot\sqrt{\mathrm{tr}\left(\mathrm{E}_{\Pi}\left((\beta-\overline{\beta})\cdot(\beta-\overline{\beta})^{\prime}\right)\right)}.$
(A.64)

Rearranging, we obtain

$\displaystyle\mathrm{E}_{\Pi}\left((\beta-\overline{\beta})\cdot(\beta-\overline{\beta})^{\prime}\right)$
$\displaystyle=\mathrm{E}_{\Pi}\left((\beta-\overline{\beta}+\mathrm{E}_{\Pi}\left(\beta\right)-\mathrm{E}_{\Pi}\left(\beta\right))\cdot(\beta-\overline{\beta}+\mathrm{E}_{\Pi}\left(\beta\right)-\mathrm{E}_{\Pi}\left(\beta\right))^{\prime}\right)$
(A.65)
$\displaystyle=\mathrm{E}_{\Pi}\left((\beta-\mathrm{E}_{\Pi}({\beta}))\cdot(\beta-\mathrm{E}_{\Pi}(\beta))^{\prime}\right)+(\mathrm{E}_{\Pi}(\beta)-\overline{\beta})\cdot(\mathrm{E}_{\Pi}(\beta)-\overline{\beta})^{\prime}$
(A.66)
$\displaystyle=\mathrm{Variance}_{\Pi}(\beta)+(A_{m}(\kappa)\cdot\mu-\overline{\beta})\cdot(A_{m}(\kappa)\cdot\mu-\overline{\beta})^{\prime},$
(A.67)

where

$A_{m}(\kappa)=\frac{I_{m/2}(\kappa)}{I_{m/2-1}(\kappa)},$ (A.68)

which relies on two results from Mardia and Jupp (2009) and Kitagawa and
Rowley (2022). These results relate to the first two moments of the von Mises-
Fisher distribution and are

$\displaystyle\mathrm{E}_{\Pi}(\beta)=A_{m}(\kappa)\cdot\mu,$ (A.69)
$\displaystyle\mathrm{Variance}_{\Pi}(\beta)=\frac{1}{\kappa}\cdot
A_{m}(\kappa)\cdot\mathbb{I}_{m}+\left(1-\frac{m}{\kappa}\cdot
A_{m}(\kappa)-A_{m}^{2}(\kappa)\right)\cdot\mu\cdot\mu^{\prime},$ (A.70)

where $\mathbb{I}_{m}$ is the m-dimensional identity matrix. Restricting the
set of von Mises-Fisher distributions to those satisfying
$\mu=\overline{\beta}$, $a_{1}$ is bounded by

$\displaystyle
2c\cdot\sqrt{\mathrm{tr}\left(\mathrm{E}\left((\beta-\overline{\beta})\cdot(\beta-\overline{\beta})^{\prime}\right)\right)}$
$\displaystyle=2c\cdot\sqrt{\mathrm{tr}\left(\mathrm{Variance}(\beta)+(A_{m}(\kappa)-1)^{2}\cdot\mu\cdot\mu^{\prime}\right)}$
(A.71) $\displaystyle=\sqrt{8c^{2}}\cdot\sqrt{1-A_{m}(\kappa)},$

which is proportional to the square root of the circular variance.121212Recall
that the right-hand side of Equation A.61 is preceded by an infimum over
$\mu$; it is not necessary for $\mu=\overline{\beta}$ to minimise Equation
A.71 for this choice to deliver a useful upper bound. Lemma 2 details the
behaviour of the circular variance. Using Lemma 2, Equation A.71 can be
bounded from above by

$\sqrt{8c^{2}\cdot\frac{\underline{c}_{\nu}+\sqrt{\kappa^{2}+\overline{c}_{\nu}^{2}}-\kappa}{\underline{c}_{\nu}+\sqrt{\kappa^{2}+\overline{c}_{\nu}^{2}}}}\leq
4c\cdot\sqrt{\frac{\nu+1}{\kappa}},$ (A.72)

where the right-hand side follows from the definitions of
$\underline{c}_{\nu}$ and $\overline{c}_{\nu}$ and concavity of the square
root, and by decreasing the denominator via elimination of
$\underline{c}_{\nu}$ and $\overline{c}_{\nu}$ (both are non-negative
constants). We substitute the right-hand side of Equation A.72 into Equation
A.61 in place of $a_{1}$.

We now focus on the Kullback-Leibler divergence, which appears in both $a_{2}$
and $a_{3}.$ We observe that the difference between the square roots in
Equation A.60 is increasing in $\kappa$ (i.e, the difference becomes less
negative as $\kappa$ increases and as $\kappa$ increases in importance
relative to $\nu$). As such, it suffices to omit the difference between the
square roots in Equation A.60 and to simply bound the Kullback-Leibler
divergence from above by

$\underline{c}_{\nu}\cdot\ln\left(\frac{\underline{c}_{\nu}+\sqrt{\kappa^{2}+\overline{c}_{\nu}^{2}}}{\underline{c}_{\nu}+\overline{c}_{\nu}}\right)+1\leq\underline{c}_{\nu}\cdot\ln\left(\kappa+1\right)+1,$
(A.73)

which is at least one due to the non-negativity of $\kappa$.

Substituting Equations A.72 and A.73 into the infimand of Equation A.61, we
obtain

$4c\cdot\sqrt{\frac{\nu+1}{\kappa}}+\frac{a(\lambda,n)}{\lambda}+\frac{\underline{c}_{\nu}}{\lambda}\cdot\ln(\kappa+1)+\frac{1}{\lambda}\cdot\ln\left(\frac{2e}{\epsilon}\right)+\sqrt{\frac{1}{2n}\cdot\left(\underline{c}_{\nu}\cdot\ln\left(\kappa+1\right)+\ln\left(\frac{4e\cdot\sqrt{n}}{\epsilon}\right)\right)},$
(A.74)

which we emhasise is an upper bound on the infimum. Our objective is to
minimise Equation A.74 by appropriately choosing $\kappa$ and $\lambda$
alongside the functional form of $a$. Accordingly, we let $\kappa=n$ and
$\lambda=\sqrt{n}$ alongside $a(\lambda,n)/\lambda=1/\lambda$. Given these
choices, it then follows that Equation A.74 is itself bounded from above by

$4c\cdot\sqrt{\frac{\nu+1}{n}\vphantom{\frac{1}{2n}\ln\left(\frac{4e\cdot\sqrt{n}}{\epsilon}\right)}}+\frac{1}{\sqrt{n}}+\frac{\underline{c}_{\nu}}{\sqrt{n}}\cdot\ln(n+1)+\frac{1}{\sqrt{n}}\cdot\ln\left(\frac{2e}{\epsilon}\right)+\sqrt{\frac{\underline{c}_{\nu}}{2n}\cdot\ln(n+1)\vphantom{\frac{1}{2n}\ln\left(\frac{4e\cdot\sqrt{n}}{\epsilon}\right)}}+\sqrt{\frac{1}{2n}\ln\left(\frac{4e\cdot\sqrt{n}}{\epsilon}\right)}$
(A.75)

which exploits the concavity of the square root. Defining

$M\equiv
4c\cdot\sqrt{\nu+1}+1+\underline{c}_{\nu}\cdot\frac{\ln(9)}{\ln(8)}+\ln\left(\frac{2e}{\epsilon}\right)+\sqrt{\frac{\underline{c}_{\nu}\cdot\ln(9)}{2\cdot\ln(8)}}+\sqrt{\frac{1}{2}\cdot\ln\left(\frac{4e}{\epsilon}\right)}+\frac{\sqrt{\ln(8)}}{\sqrt{2}\cdot\ln(8)},$
(A.76)

which relies on the maintained assumption of Theorem 3 that $n\geq 8$, we then
determine that

$R^{\tilde{\Pi}}\leq\bar{R}+M\cdot\frac{\ln(n)}{\sqrt{n}},$ (A.77)

such that $M$ is a universal constant.

###  A.5 Proof of Lemma 2

The circular variance of a von Mises-Fisher random vector is one minus the
ratio of consecutive modified Bessel functions of the first kind (i.e., one
minus the mean resultant length). Bounds on these ratios are derived in Amos
(1974; restated for immediate application to hyperspherical problems in
Kitagawa and Rowley, 2022). The result then immediately follows upon
subtraction of the lower bound from one.

###  A.6 Proof of Lemma 3

Kitagawa and Rowley (2022) shows that, when $\Pi$ is a von Mises-Fisher
distribution and $\pi_{0}$ is the uniform distribution over the hypersphere,

$\mathrm{KL}(\Pi\|\pi_{0})=\nu\cdot\ln\left(\frac{\kappa}{2}\right)-\underbrace{\ln\left(I_{\nu}(\kappa)\right)}_{\text{Bessel
fn.}}-\ln\left(\Gamma\left(\nu+1\right)\right)+\underbrace{A_{m}(\kappa)\cdot\kappa}_{\text{Ratio
fn.}},$ (A.78)

where we recall that $\nu=m/2-1$, with $\underline{c}_{\nu}=\nu+1/2$ and
$\overline{c}_{\nu}=\nu+3/2$. To derive an upper bound on the Kullback-Leibler
divergence that does not involve modified Bessel functions or their ratios, we
replace the terms labelled Bessel fn. and Ratio fn. in Equation A.78 with
appropriate lower and upper bounds, respectively. To do so, we rely on results
(and notation) in Kitagawa and Rowley (2022), which are themselves adapted and
restated from Amos (1974).

Firstly, the term labelled Bessel fn. is bounded from below (recall that the
term enters negatively) by

$\frac{1}{2}\cdot\ln\left(\frac{2}{\kappa}\right)-\ln\left(\Gamma\left(\nu+1\right)\right)+\underline{c}_{\nu}\cdot\ln\left(\frac{\kappa\cdot(\nu+1)}{\underline{c}_{\nu}+\sqrt{\kappa^{2}+\overline{c}_{\nu}^{2}}}\right)+\frac{\kappa^{2}}{\overline{c}_{\nu}+\sqrt{\kappa^{2}+\overline{c}_{\nu}^{2}}}.$
(A.79)

Secondly, the term labelled Ratio fn. is bounded from above by

$\frac{\kappa^{2}}{\underline{c}_{\nu}+\sqrt{\kappa^{2}+\underline{c}_{\nu}^{2}}}.$
(A.80)

Substituting Equations A.79 and A.80 into Equation A.78, cancelling terms and
noting that

$\nu\cdot\ln\left(\frac{\kappa}{2}\right)-\frac{1}{2}\cdot\ln\left(\frac{2}{\kappa}\right)=\left(\nu+\frac{1}{2}\right)\cdot\ln\left(\frac{\kappa}{2}\right),$
(A.81)

we obtain

$\underline{c}_{\nu}\cdot\ln\left(\frac{\kappa}{2}\right)-\underline{c}_{\nu}\cdot\ln\left(\frac{\kappa\cdot(\nu+1)}{\underline{c}_{\nu}+\sqrt{\kappa^{2}+\overline{c}_{\nu}^{2}}}\right)-\frac{\kappa^{2}}{\overline{c}_{\nu}+\sqrt{\kappa^{2}+\overline{c}_{\nu}^{2}}}+\frac{\kappa^{2}}{\underline{c}_{\nu}+\sqrt{\kappa^{2}+\underline{c}_{\nu}^{2}}}.$
(A.82)

To obtain the required result, we simplify the first two terms of Equation
A.82 and use the fact that, for any real $c$ (in this case, equal to either
$\underline{c}_{\nu}$ or $\overline{c}_{\nu}$, which are positive reals),

$\frac{\kappa^{2}}{c+\sqrt{\kappa^{2}+c^{2}}}=\sqrt{\kappa^{2}+c^{2}}-c,$
(A.83)

which makes use of the formula for the difference of two squares.

##  Appendix B Accounting for the cost of treatment in the JTPA Study sample

In what follows, we distinguish between the JTPA Study sample, which we
sometimes refer to as the raw data, and the cost-adjusted JTPA Study sample,
which we sometimes refer to as the adjusted data. The adjusted data subtracts
the cost of treatment from the outcome of interest (post-programme earnings)
of all treated individuals.131313We observe that this leads to those
individuals with zero post-programme earnings then having negative earnings.
This violates Assumption 1, which requires that all earnings be bounded and
non-negative. We, nonetheless, proceed with this adjustment of post-programme
earnings as is. An alternative would be to add $774 to all post-programme
earnings before subtracting the assumed cost of treatment. Following Kitagawa
& Tetenov (2018), we assume that the cost of treatment is $774. We then
proceed to search for the optimal stochastic assignment rule, applying the
same grid search approach as we outlined in the main text for the raw data,
using the adjusted data.

Figure 5: Variation in treatment propensity across individuals in the cost-
adjusted JTPA Study sample Each point represents the individual
characteristics of an individual or several individuals in the cost-adjusted
JTPA Study sample. The size of each point is proportional to the sum of the
post-programme earnings of all individuals with those characteristics, which
corresponds to the weight given to those observations in the empirical
implementation. The colour of each point measures the propensity with which an
individual with those characteristics is assigned treatment under our estimate
of the optimal stochastic assignment rule. Under the optimal stochastic
assignment rule, more educated individuals with low pre-programme earnings are
less likely to be assigned treatment. For comparison, individuals under the
solid line are assigned treatment under the optimal deterministic assignment
rule of Kitagawa & Tetenov (2018). Figure 6: Behaviour of the objective
function given variation in the concentration $\kappa$ Holding fixed the mean
direction at its value under our estimate of the optimal stochastic assignment
rule, we vary the value of the concentration parameter. We plot the USD
equivalent amount of both the criterion (the objective function) and empirical
welfare risk (the first part of the objective function) in the cost-adjusted
JTPA Study sample, which we define in the main text. As the concentration
increases, the stochastic assignment rule places increasing probability on a
small neighbourhood of assignment rules about the mean direction – i.e., it
becomes more like a deterministic rule. The criterion first decreases
alongside empirical welfare risk but then increases as the penalty term begins
to dominate. Figure 7: Deterministic assignment rules and empirical welfare
risk We calculate the in-sample empirical welfare risk associated with
different deterministic assignment rules. We project the three-dimensional
sphere onto the plane using a spherical coordinate mapping, where the azimuth
and inclination can be loosely interpreted as longitude and latitude,
respectively. The sphere can be broadly divided into two hemispheres of low
and high empirical welfare risk, with the best and worst deterministic
assignment rules found on the boundary of these two hemispheres. We emphasise
the number of local minima on this boundary. The intersection of the two white
lines is located at the mean direction of the optimal stochastic assignment
rule. The intersection of the two black lines is located at the optimal
deterministic assignment rule of Kitagawa & Tetenov (2018), which attains the
minimal empirical welfare risk amongst all deterministic linear rules. Figure
8: Behaviour of the objective function given variation in the mean direction
$\mu$ Holding fixed the concentration parameter at its value under our
estimate of the optimal stochastic assignment rule, we vary the mean
direction. We project the three-dimensional sphere onto the plane using a
spherical coordinate mapping, where the azimuth and inclination can be loosely
interpreted as longitude and latitude, respectively. Stochastic assignment
rules that are close tend to give similar estimates of empirical welfare risk.
Figure 9: Distribution of propensity of treatment across individuals (costed)
For a given instance of the von Mises-Fisher distribution, we draw 1,000
directional vectors and count how many of these vectors, implemented as
deterministic assignment rules, assign each individual in the cost-adjusted
JTPA Study sample to the treatment group. We call this the propensity of
treatment, and note that it varies across individuals with distinct individual
characteristics, with some individuals assigned to the treatment group more
frequently than others. This defines a distribution (over individuals) of the
propensity of treatment for a given instance. We summarise this distribution
by the range and the 10th and 90th quantiles of this distribution. We set the
mean direction equal to the mean direction of the optimal stochastic
assignment rule. As the directional vectors concentrate around the mean
direction, the propensity of assignment approaches one for all individuals,
which aligns with the fact that if the mean direction were a deterministic
assignment rule then it would assign treatment to all individuals. Figure 10:
Distribution of propensity of treatment across individuals (raw) For a given
instance of the von Mises-Fisher distribution, we draw 1,000 directional
vectors and count how many of these vectors, implemented as deterministic
assignment rules, assign each individual in the raw JTPA Study sample to the
treatment group. We call this the propensity of treatment, and note that it
varies across individuals with distinct individual characteristics, with some
individuals assigned to the treatment group more frequently than others. This
defines a distribution (over individuals) of the propensity of treatment for a
given instance. We summarise this distribution by the range and the 10th and
90th quantiles of this distribution. We set the mean direction equal to the
mean direction of the deterministic assignment rule estimated by Kitagawa &
Tetenov (2018), and extend the range of concentrations that we consider. As
the directional vectors concentrate around the mean direction, the propensity
of assignment diverges, which aligns with the fact that if the mean direction
were a deterministic assignment rule then it would assign some individuals to
the treatment group and some individuals to the control group, each with
certainty.

We find that the objective function is minimised by the stochastic assignment
rule with $\kappa^{*}=0.560$ and $\mu^{*}=(0.872,0.490,0.018)$. For
completeness, this directional vector can be represented by an azimuth of
$29^{\circ}$ and an inclination of $89^{\circ}$ using spherical coordinates.
The value of the objective function and the empirical welfare risk induced by
this assignment rule are equivalent to $9,302 and $5,155, respectively.

For comparison, Kitgagawa & Tetanov (2018) estimates that the deterministic
assignment rule defined by the vector $(0.117,-0.990,-0.086)$ minimises
empirical welfare risk. Relative to the raw analysis of the main text, this
assignment rule is much flatter, and essentially determines that all
individuals with low pre-programme earnings (earnings of around $5,000 or
less) should be treated, irrespective of education.

Figures 5, 2, 3 and 4 (Figure 5 through Figure 8) are intended to be
comparable to the figures in the main text. There are two differences of note
between the results of the raw and costed analyses. Firstly, in Figure 6, the
effect of $\kappa$ on empirical welfare risk is much more muted, with risk
only decreasing by around $50 as $\kappa$ increases (over the interval that we
study). In contrast, empirical welfare risk decreases by around $200 when the
cost of treatment is not accounted for. This reflects the second difference,
which is apparent in Figure 7. Specifically, that the difference in empirical
welfare risk between those assignment rules that assign everyone to treatment
versus those that assign no-one to treatment is much smaller. The benefit to
increased concentration, which is a reduction in the probability mass
allocated to those assignment rules that assign no-one to treatment is,
accordingly, smaller. The implication is that the penalty term starts to
dominate the objective function for smaller values of $\kappa$.

To supplement our analysis, we include two additional figures in Figures 9 and
10 (Figures 9 and 10). These figures are intended to give some idea about how
the concentration of the von Mises-Fisher distribution influences the
propensity with which individuals are assigned to the treatment group. For
example, given a particular instance of the von Mises-Fisher distribution, one
individual might have a high propensity of assignment whereas another might
have a low propensity. In other words, the number of directional vectors that
are drawn from the von Mises-Fisher distribution for which the first
individual is assigned to the treatment group is greater than for the second
individual. As the value of $\kappa$ increases, so these directional vectors
concentrate around the mean direction, and the propensity of assignment to the
treatment group approaches zero or one for each individual. We see from Figure
9 that, when the mean direction is $\mu^{*}$, the propensity of assignment in
the cost-adjusted JTPA Study sample tends towards one for all individuals. In
contrast, and to illustrate the possibility of complete dichotomy, for the raw
JTPA Study sample, we see from Figure 10 that the propensity of assignment
diverges as $\kappa$ increases. We observe in both datasets that much of the
variation in propensity is driven by a few individuals in the tail, who are
likely those individuals whose individual characteristics make them outliers.
In both cases, the median propensity of treatment (i.e., the probability with
which the average individual in the sample is assigned to the treatment group)
tends towards one.

##  Appendix C Numerical simulations

We propose several experiments that investigate how various aspects of the
sample data that is available to the social planner affect the posterior
distribution and its shape when the specified prior distribution is uniform
over the sphere. We conduct these experiments to better understand some of the
empirical results that we obtain for the main paper.

Aspects of the sample data that we vary include the number of observations,
the outcome of interest, and individual characteristics. We conduct these
experiments with simulated data and through manipulation of the existing
empirical application. Each experiment is comparable to the existing empirical
application in any case, in that observed individual characteristics are taken
to be education and pre-programme earnings alongside an intercept term, and
the outcome of interest is taken to be post-programme earnings. We investigate
how these aspects and our variation of them affect the objective function.

The specific questions that we ask, and that inform the design of our
experiments, are as follows.

  * –

How does the number of observations influence the shape of the objective
function?

  * –

How does the relative influence of education and pre-programme earnings on
post-programme earnings influence empirical welfare risk?

  * –

How does the distribution of individual characteristics influence the shape of
the objective function?

To address these questions we propose a series of linear specifications that
satisfy the bounded outcomes assumption (i.e., the outcome of interest can be
restricted to some subset $[0,M]$, where $M<\infty$) that we require. We
concede that these specifications are somewhat contrived, reflecting our need
to balance tractability with the requirements of the bounded outcomes
assumption. Denoting individual characteristics by ${X}$, we suppose that

${X}=(1,X_{\textrm{earn}},X_{\textrm{educ}})\in\\{1\\}\times[0,1]^{2},$ (C.1)

which can always be maintained via an appropriate affine map of the individual
characteristics (a step that we undertake in any case), and propose that

$\begin{array}[]{lclcl}Y_{0}&{}={}&{X}\cdot{\alpha}+\epsilon_{0},&{}{}\hfil&\epsilon_{0}\sim\mathrm{N}(0,\sigma_{0}^{2})\mathrm{\,truncated\,to\,}(0,m),\\\
Y_{1}&{}={}&{X}\cdot{\lambda}+\epsilon_{1},&{}{}\hfil&\epsilon_{1}\sim\mathrm{N}(0,\sigma_{1}^{2})\mathrm{\,truncated\,to\,}(0,m),\end{array}$
(C.2)

with

$\begin{array}[]{lcl}{\alpha}&{}\in{}&\\{v\in\mathbb{R}^{3}\,:\,v_{1}+v_{2}+v_{3}\geq
0\\},\\\ {\lambda}&{}\in{}&\\{v\in\mathbb{R}^{3}\,:\,v_{1}+v_{2}+v_{3}\geq
0\\},\end{array}$ (C.3)

where $Y_{0}$ and $Y_{1}$ denote the potential outcomes associated with the
control and intervention arms, respectively. The advantage of this
specification is that it provides a clear interpretation of the influence of
education and pre-programme earnings on post-programme earnings, and
facilitates addressing all of the questions that we pose. Moreover, the
potential outcomes are restricted to the lie in the union of the sets
$[0,\alpha+m]$ and $[0,\lambda+m]$. We note that the conditional expectations
of the potential outcomes are

$\begin{array}[]{lcl}\mathrm{E}(Y_{0}|{x})&{}={}&{x}\cdot{\alpha}+\frac{\phi(0)-\phi(m/\sigma_{0})}{\Phi(m/\sigma_{0})-\Phi(0)}\cdot\sigma_{0}={x}\cdot\tilde{{\alpha}},\\\
\mathrm{E}(Y_{1}|{x})&{}={}&{x}\cdot{\lambda}+\frac{\phi(0)-\phi(m/\sigma_{1})}{\Phi(m/\sigma_{1})-\Phi(0)}\cdot\sigma_{1}={x}\cdot\tilde{{\lambda}},\end{array}$
(C.4)

which are both affine functions of individual characteristics.141414Other
commonly invoked models fail to meet our test of tractability or the
requirements of the bounded outcomes assumption: the standard censored outcome
model generates a rectified normal distribution that is non-linear in
individual characteristics and is unbounded from above; logarithmic
transformation of the outcome implies a non-linear transformation of
individual characteristics. This is an attractive property that we exploit.

Knowledge of the data generating process (Equation C.2 in our framework) is
sufficient to determine the optimal assignment rule.151515We do not make any
claims about uniqueness in what follows and, indeed, presented with a finite
sample of individual characteristics, it is likely that several assignment
rules can attain the same partition of individuals as what we refer to as the
optimal assignment rule. Specifically, the optimal assignment rule delivers
the partition

$G=\left\\{{x}\,:\,\mathrm{E}(Y_{1}|{x})\geq\mathrm{E}(Y_{0}|{x})\right\\}.$
(C.5)

When the conditional expectation of the potential outcomes are affine
functions of individual characteristics (and assignment is at random, which is
an assumption that we implicitly maintain throughout) then the optimal
assignment rule belongs to the LES class. Hence, Equation C.4 guarantees that
the optimal policy has the specific form

$G=\\{{x}\,:\,{x}\cdot{\beta}\geq
0,{\beta}=(\tilde{{\lambda}}-\tilde{{\alpha}})/\|\tilde{{\lambda}}-\tilde{{\alpha}}\|_{2}\\},$
(C.6)

which is not only a member of the LES class but emphasises that the optimal
assignment rule can be summarised by a vector on the sphere (provided that the
potential outcomes have distinct process). This result provides motivation for
our reliance on spherical distributions and, in particular, the von Mises-
Fisher distribution. We observe that, abstracting from the issue of sampling
variation, empirical welfare risk is minimised when the mean direction of the
von Mises-Fisher distribution coincides with the policy defined in Equation
C.6. This insight allows us to focus exclusively on the influence of the
concentration parameter on empirical welfare risk and the objective function.

Throughout, we are careful to sample using inversion-based pseudo-random
sampling methods where possible. Compared to rejection sampling-based pseudo-
random sampling methods, inversion-based methods are able to guarantee
comparability across experiments despite differences in parameter values. We
also note that where we use data from the JTPA Study sample, this data is not
adjusted for the cost of treatment (i.e., we use the raw data).

###  C.1 Varying the number of observations

Figure 11: Behaviour of the objective function given variation in the
concentration $\kappa$

Holding fixed the mean direction at its value under our estimate of the
optimal stochastic assignment rule, we vary the value of the concentration
parameter. We plot the USD equivalent amount of both the criterion (the
objective function) and empirical welfare risk (the first part of the
objective function) in the cost-adjusted JTPA Study sample, which we define in
the main text. As the concentration increases, the stochastic assignment rule
places increasing probability on a small neighbourhood of assignment rules
about the mean direction – i.e., it becomes more like a deterministic rule.
The criterion first decreases alongside empirical welfare risk but then
increases as the penalty term begins to dominate. In each panel, we copy each
individual in the JTPA Study sample (once for the top panel, three times for
the bottom) such that we artificially inflate the number of observations.

To investigate the influence that the number of observations has on the
objective function and on empirical welfare risk, we copy each observation in
the JTPA Study sample either once or three times, thereby doubling and
quadrupling, respectively, the number of individuals in the sample. The
mechanical effect of this change is to mute the influence of the penalty term
in the objective function, without affecting empirical welfare risk. The
immediate implication is that larger values of the concentration parameter can
be sustained, since the penalty due to deviating from the uniform distribution
is relatively smaller for every such deviation.

We plot the objective function and empirical welfare risk for the doubled and
quadrupled JTPA Study samples in Figure 11 (Figure 11). We observe that
increasing the number of observations has the direct effect of decreasing the
magnitude of the objective function. Moreover, increasing the number of
observations also leads to an increase in the optimal value of the
concentration parameter, which increases from 1.550 to 1.890 and then to
2.490. We emphasise that the optimal mean direction is also not the same