PAC-Bayesian Treatment Allocation Under Budget Constraints

PAC-Bayesian Treatment Allocation Under Budget Constraints

Introduction

This paper proposes new statistical decision rules for treatment assignments under a general budget or resource constraint. A key objective in the empirical analysis of treatment data is identifying policies that result in the most beneficial outcomes. There is a large literature (e.g. Manski2004 and hirano2009asymptotics) that examines how to determine which policies are optimal to implement in the absence of constraints such as one on policy cost. In practice, however, policy makers are rarely free from constraints when it comes to the policies they may enact. Several recent papers in the econometrics literature, including KT2018, athey2021policy, and mbakop2021model, consider the treatment estimation problem from an empirical welfare maximization (EWM) perspective that allows for arbitrary constraints on the functional form of the decision rule. However, these papers do not address general budget constraints nor cost uncertainty that varies with the characteristics of individual agents. For example, while KT2018 consider quantity constraints via random rationing, this treats costs as fixed and hence cannot identify which policies most efficiently balance cost vs. outcome trade-offs when costs vary with individual characteristics.

Here we focus on the setting where costs may be uncertain, current resource limitations may preclude treating all that can benefit, and where individual characteristics can influence treatment responses and costs. Compared to the unconstrained setting, the theoretically optimal treatment rule involves population objects that are more difficult to estimate and analyze in concert. For example, BHATTACHARYA2012168 show that under a quantity constraint, which is simpler than the setting with variable costs, the optimal rule is to assign treatment when the conditional average treatment effect exceeds its $(1-c)$th quantile. Here $c$ is the maximal proportion of treatments assignable under the constraint. As a result, it can be difficult to evaluate properties of interest for proposed approaches and each existing approach has limitations.

The contributions of the paper are as follows. First, we propose new treatment rules that expand the tool set available to policy makers in the budget constrained setting. Second, we show they possess several potential benefits in terms of theoretical guarantees, the variety of settings in which they can be applied, and ease of estimation. Third, we show expert knowledge can be incorporated when the policy maker has non-data-dependent insights into the problem. However, the ability to integrate expert knowledge is a secondary feature of the approach. In our primary implementation we assume no such knowledge.

PAC-Bayesian analysis applies the probably approximately correct learning framework to objects of interest that involve probability distributions over model or parameter families. These objects can include, for example, treatment rules formed by aggregating over a family of potential rules. Our work can be seen as extending the PAC-Bayesian learning approach to the treatment setting in a way that incorporates a secondary cost objective. This motivates the proposed rules and allows us to derive generalization bounds for the costs and oracle-type inequalities for the welfare regret of proposed rules. Here, the welfare regret associated with a treatment rule is the loss in expected welfare of the decision rule relative to the theoretically optimal decision rule (cf. Manski2004). To work within the regret framework, we also derive the form of a theoretically optimal treatment policy if the data generating process (DGP) were known under a general budget constraint.

Individualized treatment policies under budget restrictions are of interest in a variety of settings. Often policy makers with limited resources face uncertainty regarding the costs and benefits of potential policies where this uncertainty is driven due to the fact that costs and benefits vary with the individual characteristics of those who decide to participate in a program. For example, FinkelsteinEtAl2012OHI examine outcomes such as health care utilization and self-reported health measures following a randomized expansion of household access to Medicaid in Oregon. A policy maker may be interested in identifying policies to maximize a well-defined weighted average of such outcomes given a binding expenditure constraint. The government has control over eligibility rules defined on characteristics such as age, income, and the number of children in a household that directly influence expected cost and cost uncertainty.

Insecticide-treated nets (ITNs) for protection against malaria in regions of Africa represent another common example. lengeler1998insecticide, for instance, documents reductions in child mortality while kuecken2014does document returns to education related to ITN provisions. Teklehaimanot2007 estimate the cost of providing an ITN to every at-risk individual in sub-Saharan Africa to be 2.5 billion dollars. However, government and aid funding was below that level at the time of the study. BHATTACHARYA2012168 look at a treatment policy estimator under quantity constraints derived from data from a randomized experiment assigning ITNs to rural households in Kenya. They use fixed costs to estimate rules that satisfy quantity constraints. Our approach makes it possible to target policies in such a way as to account for cost heterogeneity (e.g. different distribution channels) and hence improve efficiency and achieve a higher overall outcome level.

Beyond aid and social safety net policies, the budget constrained treatment assignment problem can also arise in a commercial context for firms considering potentially costly promotions aimed at obtaining new customers. For instance, sun2021treatment recently proposed a budget constrained treatment estimator aimed at determining which customers should be offered trial access to a premium service. They seek to use customers' individual characteristics to discriminate against making offers to customers likely to heavily utilize the service in the trial (high cost) while being unlikely to use the service after the trial period expires. Rather than the simple notion of not wanting to implement a policy that leads to long-term losses, many companies will also face a short-term constraint on how much they can “lose" in the trial phase to gain market share. For other firms, like Uber which is considered in sun2021treatment, a deeper issue may arise. Increasing sales or trial offers may fundamentally alter the firm's cost structure (e.g., increasing driver compensation to induce enough new drivers to work to handle the increased number of trips).

The rules we develop start from a user-specified family of (non-stochastic) treatment models $\mathcal{F}$ that map an individual's covariates that are observable pre-treatment to the $\{0,1\}$ treatment indicator space. Rather than choosing the model that maximizes the empirical welfare in $\mathcal{F}$, for example, we instead consider stochastic treatment rules derived from $\mathcal{F}$ and a measure of budget penalized empirical welfare. Given an individual's pre-treatment covariates, their treatment probability is calculated as an exponentially weighted average over the treatments specified by members of $\mathcal{F}$. The treatment probability is similar to a weighted majority vote taken over $\mathcal{F}$. The exponential weighting received by members of the model family is greatest for models with a large budget-penalized empirical welfare. The magnitude of the penalization term related to cost is determined by a parameter $u$ that modulates the trade-off between maximizing welfare and reducing costs. Any choice for $u$ will correspond to a different maximal empirical budget, with $u=0$ corresponding to an unlimited budget (no constraint). Typically, for larger sample sizes, the rule is unlikely to assign identical covariates to different treatments unless there are subsets of the model family with similarly high values of penalized welfare that prescribe different treatments. We also consider closely related, non-stochastic, model aggregation treatment rules that aggregate over $\mathcal{F}$ to make treatment decisions.

Utilizing a PAC-Bayesian framework, under reasonable conditions we show that for a set of $u$ values, in large samples, with high probability we obtain increasingly accurate estimates of the target population costs associated with corresponding stochastic treatment rules. We can use these estimates to select $u$ or, alternatively, $u$ can be chosen via cross-validation. At the same time, with $u$ chosen in either manner, with high probability the resulting rule achieves a welfare regret comparable to that of the best models in the model family that have a similar target population cost. Starting from a set of budget penalty parameters, the policy maker can trace out good estimates of the feasible target population budgets, select the parameter associated with one of these estimates, and obtain a treatment rule with desirable regret properties. Regarding the non-stochastic, model aggregation treatment rules, we show that they inherit desirable properties from the stochastic rules. We also consider the setting where $u$ is chosen to meet a predetermined target population budget level. The procedure in this case is still reasonably motivated, as the rule minimizes an upper bound on the target population regret among rules that satisfy an empirical budget constraint. However, the generalization bounds for the target population cost and the oracle-type inequalities in this case become more complex to interpret.

The remainder of the paper is organized as follows. Section (ref) discusses related literature and papers with alternative budget constrained treatment estimators. Section (ref) details the statistical setting, treatment model formulation, and initial properties useful for later results. Section (ref) provides theoretical motivation for the proposed treatment rules, utilizing the PAC-Bayesian analysis framework to examine (frequentist) properties of the proposed rules. Section (ref) conducts a simulation experiment and discusses implementation and estimation. Lastly, Section (ref) conducts a short empirical illustration utilizing data from the Job Training Partnership Act Study and Section (ref) concludes.

Related Literature

The topic of budget constrained treatment allocation is the subject of a small but growing literature. sun2021treatment and wang2018learning empirically implement treatment rules starting from the notion of a theoretically optimal rule. They estimate unknown population level objects that appear in the optimal rules and then plug in the empirical counterparts to the corresponding theoretical formulas to obtain rules. The standard drawback of this sort of approach is that the estimation technique doesn't directly target policies that maximize the welfare problem of interest. For example, the regressions utilized to fit the conditional average treatment and cost functions in wang2018learning might yield parameters that are most accurate in regions of the covariate space that are less important for distinguishing individuals with a high outcome-to-cost ratios in the population. wang2018learning also consider a second method that shares similarities with the approach taken by huang2020estimating. These approaches add the budget constraint to the outcome-weighted treatment learning approach considered, for example, in zhao2012estimating. These approaches work from optimization problems that directly target an empirical version of the problem of interest.

One drawback of the aforementioned techniques is a lack of theoretical insight regarding the true target population cost and risk attributes of the proposed rules. sun2021empirical adapts the EWM setting of KT2018 to account for a general budget constraint. She considers a conservative rule that will satisfy the budget constraint asymptotically. She also considers a modified rule where a Lagrange multiplier parameter is capped during estimation. This will, asymptotically, approach the welfare of the budget constrained welfare maximizing policy among the user-specified model class. This methodology extends the arbitrary form features of EWM to the budget constraint setting. However, the rules involve a non-convex estimation procedure that may become difficult if the model class includes more flexible functional forms. While our methodology sacrifices some ability to satisfy functional form constraints due to its stochastic nature, one benefit is that we can take advantage of Bayesian estimation machinery as discussed in Section (ref). Lastly, although the modified rules of sun2021empirical will approach the optimal rule within the original budget constraint, it is worth noting that the modified rule may violate that budget constraint. One benefit of our approach is we can compare our rules to those with the highest welfare among rules with the same target population cost as the proposed rules.

In a broader context, this paper contributes to a growing literature on statistical treatment rules in econometrics, including Manski2004, dehejia2005program, hirano2009asymptotics, BHATTACHARYA2012168, KT2018, viviano2019policy, and athey2021policy. This literature has overlap with additional fields including statistics and machine learning. For examples, see qian2011performance and beygelzimer2009offset, respectively. Additional references and a discussion of the links between these fields can be found in athey2021policy. In the machine learning literature, london2019bayesian utilize a PAC-Bayesian approach to policy estimation for the logged bandit feedback problem which is closely related to treatment policy estimation. We also note that kitagawa2023stochastic examine stochastic treatment assignment rules from a PAC-Bayesian perspective. Their paper's approach has overlap with ours, however the papers diverge in a number of dimensions stemming from our focus on the setting with a general budget constraint which is not considered there.

Lastly, our analysis and proposed treatment rules are heavily influenced by the PAC-Bayesian machine learning literature. Seminal works in this area include shawe1997pac, mcallester1999some, mcallester1999pac, seeger2002pac, and mcallester2003pac. In particular, we utilize techniques stemming from catoni2007pac, lever2010distribution, maurer2004note, germain15aJMLR, and alquier2016properties. The theoretical contribution of our paper is, first, to modify and adapt relevant tools and generalization bounds to the treatment choice setting. We also develop the incorporation of a secondary objective or loss function (the treatment cost cost) into the analysis that yields informative oracle-type inequalities and generalization bounds relevant to the constrained budget setting.

Setup and Assumptions

Statistical Setting and Policy Maker's Problem

We consider the setting where a policy maker has data consisting of observations \[Z_{i}=(Y_{i}, C_{i}, D_{i}, X_{i}), \ i=1,\dots, n.\] Here, $X_{i}\in\mathcal{X}\subset\mathbb{R}^{d_{x}}$, where $d_{x}\in\mathbb{N}$, denotes a vector of covariates for individual or unit $i$ observed prior to treatment assignment, $Y_{i}\in\mathbb{R}$ is unit $i$'s outcome that is observed after treatment assignment, $C_{i}\in\mathbb{R}$ is the cost incurred and $D_{i}\in\{0,1\}$ is a treatment assignment indicator that is $1$ if unit $i$ was assigned the treatment and is zero otherwise. $C_{i}$ may be uncertain at the time of treatment assignment and is allowed to be observed after treatment assignment.

To account for heterogeneous treatment responses and costs, we work from a potential outcomes and costs framework. For unit $i$ and for $j\in\{0,1\}$, let $Y_{i,j}$ and $C_{i,j}$ denote the outcome and cost, respectively, that would have been observed if unit $i$ had been assigned $D_{i}=j$. Ignoring the index $i$, we can relate the observed outcome and cost to their potential outcomes and costs by writing

The following assumption formalizes this setting. It also includes conditions needed to identify properties related to potential outcomes and costs when they are not observed directly in sample data.

Assumption (ref) mirrors treatment assumptions in KT2018 and mbakop2021model and also includes similarly-formulated conditions for cost-related variables. Unconfoundedness states that, conditional on the covariates, the potential outcomes and costs are independent of the treatments assigned to the observed data. This and strict overlap will hold in randomized controlled trials (RCTs) which is our primary setting of interest. As such, we assume $e(x)$ is known. It is possible to adjust our procedures to a setting where $e(x)$ is estimated similarly to the e-hybrid rules utilized in KT2018 and mbakop2021model while maintaining some of the theoretical motivations considered in Section (ref). We leave a complete exploration of this topic to future research and work under the presumption that $e(x)$ is known.

Define the conditional average treatment effect (CATE) and the conditional average treatment cost (CATC), respectively, by

Assumption (ref) (iii) implies that $|\delta_{y}(X)|$ and $|\delta_{c}(X)|$ are bounded almost surely by $M_{y}$ and $M_{c}$, respectively. Our procedures can be implemented without knowledge of $M_{y}$ or $M_{c}$ and several of the motivating regret bounds in Section (ref) could be derived in slightly altered forms if instead we required that objects related to $|\delta_{y}(X)|$ and $|\delta_{c}(X)|$ are sub-Guassian or even sub-exponential with additional constraints on a hyper-parameter. Assumption (ref) (iii) is typically a mild requirement that is often adopted in the treatment and classification literature; here it simplifies our exposition and path to generalization bounds. Note that $Y$ and $C$ may belong to any interval. The upper and lower bounds are taken to be symmetric around zero for convenience and without loss of generality.

In section (ref) we propose treatment assignment rules that aim to balance two prevailing objectives. We seek rules that will maximize the expected outcome $Y$ while also accounting for a potential budget constraint when we anticipate that resource, policy, or other limitations may preclude treating everyone with a positive CATE. Our proposed rules contain a parameter $u$, which can be chosen in a data-dependent manner, that modulates how much the second (budgetary) objective is prioritized. In particular, any choice of $u$ corresponds to a different maximum expected cost in a budget-constrained welfare optimization problem. Before describing the treatment model and empirical approach, we first state the policy maker's problem at the population level under a given maximum budget $B$ if the distribution $Q$ were known.

The policy maker's goal is to obtain a treatment rule that maximizes welfare subject to a budget or quantity constraint. The treatment rule is intended for application to a target population wherein the joint distribution of $(Y_{0}, Y_{1}, C_{0}, C_{1},X)$ follows that associated with $Q$. We will consider stochastic treatment assignment rules, defining such a rule as a measurable map $f:\mathcal{X}\rightarrow [0,1]$ from the covariate space to a treatment assignment probability. If $f(x)\in\{0,1\}$, the treatment assignment for $x$ is non-random. If $0<f(x)<1$, treatment is assigned randomly with treatment probability $f(x)$.

The utilitarian welfare associated with $f$ is given by

This is the expected value of $Y$ when treatment is administered according to $f(X)$. Dropping terms that do not vary with $f$, the policy maker's objective function evaluated at $f$ is defined by

Choosing $f$ that maximizes $W(f)$ is equivalent to choosing $f$ that maximizes utilitarian welfare. Thus we will refer to $W(f)$ as the welfare associated with $f$. Note that by the law of iterated expectations, $W(f)=E_{Q}[\delta_{y}(X)f(X)]$. Next, define the expected cost of $f$ by

which can similarly be written $K(f)=E_{Q}[\delta_{c}(X)f(X)]$. Given a budget constraint $B$, the policy maker's problem is to identify

where the maximization is taken over all measurable functions from $\mathcal{X}$ to $[0,1]$.

Note that $K(f)=E_{Q}[C_{1}f(X)+C_{0}(1-f(X))]- E_{Q}[C_{0}].$ The budget constraint states that the expected additional cost due to implementing treatment policy $f$, that beyond what would be expected if treatment were never assigned, cannot exceed $B$. This is flexible, as it allows for cost savings (i.e. when $C_{1}<C_{0}$ with positive probability) to be factored into the budget. Provided such savings are possible, a policy maker could be interested in, for example, $B = 0$. In this scenario the policy maker is looking for treatment policies that may improve welfare without increasing the expected cost beyond the setting were no treatments are administered. On the other hand, if the policy maker has a fixed budget allocated to treatments and cost savings do not feed back into the budget, one can simply define $C_{0}=0$, so that the observed $C$ is equal to the cost of treatment when treatment is provided and is zero otherwise. If there is a a fixed quantity constraint consisting of a set number of treatments and no other budgetary concerns, one can set $C_{0}=0$ and $C_{1}=1$ so that the observed $C$ is the treatment indicator. In this case $B$ denotes the maximum proportion of the target population for which treatments are available.

If there is no budget constraint and the policy maker is able to choose any measurable $f:\mathcal{X}\rightarrow [0,1]$, it is straightforward to verify that an optimal treatment allocation rule is given by

$f^{*}$ assigns treatment to any unit with a positive CATE. Here, and throughout the paper, the indicator function $1\{A\}$ takes the value $1$ if event $A$ occurs and is zero otherwise. Given a particular budget constraint $B$, a solution to the policy maker's problem is characterized in the following theorem.

The choice of $\eta_{B}$ in Theorem (ref) is unique, however in general there may be different choices of $a_{1}, a_{2}$ that produce optimal rules when $E_{Q}[1\{\delta_{y}(X)=\eta_{B} \delta_{c}(X)\}]\neq 0$. Apart from this difference, Theorem (ref) is a generalization of a result in sun2021treatment which restricts itself to the setting where $C_{1}\geq C_{0}$ almost surely. In practice, of course, $Q$ is unknown to the researcher who must estimate a suitable model $f$ empirically. Section (ref) introduces the PAC-Bayesian setting for the empirical strategy we employ.

When $E_{Q}[1\{\delta_{y}(X)=\eta_{B}\delta_{c}(X)\}]=0$, for example when $\delta_{y}(X)$ and $\delta_{c}(X)$ have bounded densities, Theorem (ref) says the optimal treatment rule is deterministic and unique in terms of the resulting treatment decisions. However, the function $\delta_{y}(x)-\eta_{B}\delta_{c}(x)$ in the optimal rule in this setting, given by \[f^{*}_{B}(x)= 1\{\delta_{y}(x)-\eta_{B}\delta_{c}(x)>0\},\] is not unique. Any measurable function $m(x):\mathcal{X}\rightarrow\mathbb{R}$ that satisfies \[\mathrm{sign}\left [ m(x) \right ] = \mathrm{sign}\left [ \delta_{y}(x)-\eta_{B}\delta_{c}(x) \right ],\] yields an optimal treatment rule via $f_{m}(x)=1\{ m(x)>0\}$. This situation is similar to that in the binary forecasting problem (cf. elliott2013predicting) and is illustrated in Figure (ref).

In Section (ref), we propose treatment rules that aggregate over a user-specified family of treatment rules in a way that is weighted towards models with high empirical budget-penalized welfare. There, we introduce Gibbs treatment rules, which aggregate over the rule family to derive a treatment probability, and related majority vote rules which aggregate over the rule family to assign treatment directly. Aside from the desirable theoretical properties derived in Section (ref), some intuition behind such an approach is as follows. Two functions $\hat{m}(x)$ and $\hat{m}^{*}(x)$, with corresponding treatment rules $1\{\hat{m}(x)>0\}$ and $1\{\hat{m}^{*}(x)>0\}$, respectively, could yield identical or very similar treatment decisions over the sample covariate values. In a setting where different rules may have the same or very similar observable properties, it is reasonable to aggregate or average over rules with high empirical welfare. Rather than trying to select a single solution, we take the identification issue above as motivation for an ensemble approach.

Empirical Approach and PAC-Bayesian Setting

Underpinning the treatment rules we will consider is a family of non-stochastic treatment rules, indexed by $\theta\in\Theta$, denoted

For a concrete example, we could let $\{\phi_{1}(x),\dots, \phi_{q}(x)\}$ be a set of feature transformations where $\phi_{j}(x):\mathcal{X}\rightarrow \mathbb{R}$ for $j=1,\dots, q$. Denoting $\phi(x)=(\phi_{1}(x),\dots,\phi_{q}(x))^{\intercal}$, we could then have

where $q\in \mathbb{N}$ need not be equal to $d_{x}$, the dimension of $\mathcal{X}$.

For any treatment assignment rule $f$, we define the welfare regret relative to the first-best prediction rule $f^{*}$ in (ref) by \[R(f) \equiv W\left ( f^{*} \right ) - W\left (f \right ). \] Note that $R(f)$ is defined relative to the first-best treatment assignment without a budget constraint. We can also define

the welfare-regret under a maximum expected budget of $B$ where $f_{B}^{*}$ is defined in Theorem (ref). With simple manipulations, the oracle-type inequalities involving $R(f)$ in Sections (ref) and (ref) apply to $R_{B}(f)$ rather than $R(f)$. For simplicity, we will mostly work with $R(f)$ which is non-negative. Note that $R_{B}(f)$ is only non-negative when attention is constrained to treatment rules with a maximal budget $B$. For particular models $f_{\theta}\in\mathcal{F}_{\Theta}$, with a slight abuse of notation, we will write \[R(\theta) \equiv R\left ( f_{\theta} \right ), \ W(\theta) \equiv W\left ( f_{\theta} \right ), \ \mathrm{and} \ K(\theta)\equiv K\left ( f_{\theta} \right ). \]

Under the unconfoundedness and strict overlap conditions of Assumption (ref), it holds that \[W(f) = E_{Q} \left [ \left ( Y_{1}-Y_{0} \right ) f(X) \right ] = E_{P} \left [ \left ( \frac{YD}{e(X)}-\frac{Y(1-D)}{1-e(X)} \right )f(X) \right ]. \] A similar statement can be written for $K(f)$, now with $C$ in place of $Y$. Defining \[\delta_{y,i}= \left ( \frac{Y_{i}D_{i}}{e(X_{i})}-\frac{Y_{i}(1-D_{i})}{1-e(X_{i})} \right ) \ \mathrm{and} \ \delta_{c,i} = \left ( \frac{C_{i}D_{i}}{e(X_{i})}-\frac{C_{i}(1-D_{i})}{1-e(X_{i})} \right ), \] the (unbiased) empirical counterparts of $W(f)$, $R(f)$, and $K(f)$, along with their notation for $f_{\theta}\in\mathcal{F}_{\Theta}$, are given by

As $f^{*}$ is unknown, the empirical regret $R_{n}(f)=W_{n}(f^{*})-W_{n}(f)$ or $R_{n}(\theta)$ for $\theta\in\Theta$ cannot be evaluated in practice. $R_{n}(\theta)$ will arise in our analysis only as a theoretical object in relation to $R(\theta)$. We stress that the treatment assignment rules we consider can be expressed solely in terms of $W_{n}(\theta)$.

$\mathcal{F}_{\Theta}$ consisting of treatment rules of the form in (ref) will be considered in Sections (ref) and (ref). In general, to accommodate broader treatment rule model families, we make the following technical assumptions.

We now introduce the stochastic treatment rules of interest. Let $\mathcal{P}(\Theta)$ be the set of probability measures on $(\Theta,\mathcal{B}_{\theta})$ and, for any $\pi\in\mathcal{P}(\Theta)$, let $\mathcal{P}_{\pi}(\Theta)= \{\rho\in\mathcal{P}(\Theta): \rho \ll \pi \}$. That is, $\mathcal{P}_{\pi}(\Theta)$ is the set of probability measures on $(\Theta,\mathcal{B}_{\theta})$ that are absolutely continuous with respect to $\pi$. Rather than selecting a single value $\hat{\theta}\in\Theta$, for example that which maximizes $W_{n}(\theta)$, and then assigning treatment via $f_{\hat{\theta}}$, we seek probability measures $\rho\in \mathcal{P}(\Theta)$ from which we form stochastic treatment rules. Borrowing nomenclature from the classification literature, we work with Gibbs treatment rules. For $\rho\in\mathcal{P}(\Theta)$, the Gibbs treatment rule or method associated $\rho$, denoted $f_{G,\rho}:\mathcal{X}\rightarrow [0,1]$, is defined by \[f_{G,\rho}(x) = \int_{\Theta}f_{\theta}(x) d\rho(\theta), \ x\in\mathcal{X}.\]

Assigning treatments via the Gibbs method is equivalent to assigning treatments as follows. For an individual with covariates $X$, a parameter value $\theta_{\circ}$ is drawn randomly according to $\rho$, i.e. $\theta_{\circ}\sim\rho$. Then, $f_{\theta_{\circ}}(X)\in\{0,1\}$ determines the treatment assignment. This process, with an independent draw from $\rho$, is repeated each time treatment is to be assigned. Note that, exchanging the order of integration, we can write \[R(f_{G,\rho})= \int_{\Theta} R(\theta) d\rho(\theta) \ \ \mathrm{and} \ \ R_{n}(f_{G,\rho})= \int_{\Theta} R_{n} (\theta) d\rho(\theta),\] which is called the Gibbs risk associated with $\rho$. Similarly, the expected cost of $f_{G,\rho}$ and its empirical counterpart can be written \[K(f_{G,\rho})= \int_{\Theta} K(\theta) d\rho(\theta) \ \ \mathrm{and} \ \ K_{n}(f_{G,\rho})= \int_{\Theta} K_{n} (\theta) d\rho(\theta). \] We will frequently be concerned with the cost or empirical cost associated with a Gibbs treatment rule utilizing some $\rho\in\mathcal{P}_{\pi}(\Theta)$. To simplify the exposition, we denote

A non-stochastic treatment rule that is closely related to the Gibbs rule is the so-called majority vote or Bayes method associated with $\rho\in\mathcal{P}(\Theta)$. This is given by

In practice, majority vote rules can deliver treatment rules that are numerically more stable than their Gibbs counterpart. If $\rho=\alpha\rho_{1}+(1-\alpha)\rho_{2}$ for some $\rho_{1},\rho_{2}\in\mathcal{P}(\Theta)$ and constant $\alpha$, then $R(f_{G,\rho})=\alpha R(f_{G,\rho_{1}})+(1-\alpha)R(f_{G,\rho_{2}})$. That is, the Gibbs risk is a linear functional of $\rho$. This linearity makes the Gibbs risk and Gibbs treatment rules more amenable to theoretical analysis. Our analysis will therefore focus on a family of Gibbs treatment rules. However, in Section (ref), we show that the majority vote treatment rule associated with our Gibbs rules of interest inherit desirable properties from their Gibbs counterparts. In practice, either method is an acceptable choice and we consider both in our simulation study in Section (ref).

In particular, we propose to utilize Gibbs treatment rules constructed from data-dependent\footnote{In general, by data-dependent probability measures on $(\Theta,\mathcal{B}_{\theta})$ we mean regular conditional probability measures (RCPMs): letting $\mathcal{B}_{s}$ denote the $\sigma$-algebra associated with the sample space $\mathcal{S}$, $\rho(S,\cdot)$ is an RCPM on $(\Theta,\mathcal{B}_{\theta})$ if (i) for any fixed $A\in\mathcal{B}_{\theta}$, the map $S\mapsto \rho(S,A): (\mathcal{S},\mathcal{B}_{s}) \rightarrow \mathbb{R}_{+}$ is measurable; and (ii) for any $S\in\mathcal{S}$, the map $A\mapsto \rho(S,A):\mathcal{B}_{\theta}\rightarrow [0,1]$ is a probability measure. For additional measure-theoretic details, for example the decomposition and measurability of the Kullback-Leibler divergence (utilized throughout the paper) between RCPMs, we refer the reader to catoni2004statistical, in particular Proposition 1.7.1 and its proof on pages 50-54.} probability measures of the form $\hat{\rho}_{\lambda, u}$ defined below.

$\hat{\rho}_{\lambda, u}$ is sometimes called a Gibbs posterior distribution or a Boltzmann distribution. As $\lambda\rightarrow\infty$, $\hat{\rho}_{\lambda, u}$ concentrates around the value of $\theta$ such that $f_{\theta}$ minimizes the budget-penalized empirical regret criterion $R_{n}(f_{\theta})+ uK_{n}(f_{\theta})$. Equivalently, it concentrates around the value of $\theta$ the maximizes $W_{n}(\theta) -uK_{n}(\theta)$ over $\Theta$. This reduces to the empirical welfare maximizer when $u=0$. In general, $\hat{\rho}_{\lambda, u}$ assigns higher probability to regions of the parameter or model space with low budget-penalized empirical regret. $u$ modulates the trade off between emphasis on low regret vs expected cost. As subsequent analysis will show, different choices of $u$ correspond in a one-to-one manner with different budget constraints. We will consider the setting where $u$ is cross-validated and the setting where it is determined by a particular choice of a budget constraint parameter $B$. $\rho^{*}_{\lambda, u}$ is a theoretical counterpart to $\hat{\rho}_{\lambda, u}$ that will be useful when we analyze statistical properties related to $\hat{\rho}_{\lambda, u}$. $\lambda$ is typically chosen via cross-validation while choices where $\lambda = \mathcal{O}(\sqrt{n})$ will yield optimal or near-optimal rates of convergence in Section (ref).

In the PAC-Bayesian literature, probability measures over the model or parameter space that are traditionally chosen independently of the sample are often called prior probability measures. In our setting, the choice of $\pi$ utilized in Definition (ref) will fall into this category. Probability measures utilized for treatment or prediction, such as $\hat{\rho}_{\lambda, u}$, are called posterior distributions. However, this nomenclature does not have the same connotation as in traditional Bayesian methodology. While knowledge of the DGP could allow for a prior to be chosen that improves the performance of rules suggested from PAC-Bayesian analysis, often the prior is taken to be uniform or normal centered at the origin. Additionally, the posterior, for example, does not need to be proportional to a likeilihood function. The statistical analysis itself is frequentist in nature. The role and choice of $\pi$ will be discussed further later in the paper. For now we make the following assumption.

Initial Properties of the Gibbs Posterior

Here we derive initial properties of $\hat{\rho}_{\lambda, u}$ that link the choice of $u$ to a particular budget constraint. These provide intuition behind Definition (ref) and are utilized in proving the results of Section (ref).

Let $D_{\mathrm{KL}}(\rho,\pi)$ denote the Kullback–Leibler (KL) divergence between $\rho,\pi \in\mathcal{P}(\Theta)$,

Suppose the policy maker has a maximum expected budget of $B\in\mathbb{R}\cup \{\infty\}$, where $B=\infty$ is the unconstrained setting. If the data generating process were known, among Gibbs treatment rules we would be interested in a solution to

In practice, we will instead focus on a subset $\mathcal{P}_{\pi}(\Theta) \subset \mathcal{P}(\Theta)$ and solve the following empirical problem:

(ref) includes a regularization term in the form of $D_{\mathrm{KL}}(\rho,\pi)$, discouraging any choice for $\rho$ that has a large KL divergence from the reference measure $\pi$. In practice, $\mathcal{P}_{\pi}(\Theta)$ is flexible and optimal choices for $\lambda$ will entail $\lambda\rightarrow\infty$ as $n\rightarrow \infty$. When adapted to our setting, Lemma (ref) below shows that, provided a feasibility or Slater condition holds, for some value $\hat{u}\geq 0$, $\hat{\rho}_{\lambda,\hat{u}}$ is the solution to (ref). Of course, appearing to be a reasonable empirical counterpart of (ref) is not, in and of itself, justification for $f_{G,\hat{\rho}_{\lambda, u}}$. In Section (ref) we provide additional theoretical motivation for $f_{G,\hat{\rho}_{\lambda, u}}$, comparing it to alternative Gibbs rules and optimal (non-stochastic) models in $\mathcal{F}_{\theta}$.

The following lemma yields solutions to (ref) and a theoretical counterpart when $R_{n}(\theta)$ and $K_{n}(\theta)$ are replaced by $R(\theta)$ and $K(\theta)$, respectively.

When $B=\infty$, so that $\overline{u}_{B}=0$, the result in Lemma (ref) is a well known property that is commonly utilized in the PAC-Bayesian literature with $A(\theta)$ taken as some loss or regret function; see catoni2007pac and alquier2016properties among many possible examples. Lemma (ref) extends this setting to accommodate a secondary constraint objective associated with $H(\theta)$. When, for example $H(\theta)=R(\theta)$, $\Lambda(u)$ is the cost associated with the Gibbs treatment rule utilizing $\tilde{\rho}_{A,H,\lambda, u}$. $\Lambda(u)$ is decreasing in $u$. Intuitively, as the exponential re-weighting of $\pi$ depends more heavily on $H(\theta)$ for larger values of $u$, regions of the parameter or model space with greater cost receive a relatively lower weighting and the overall cost is reduced as $u$ increases. Convex optimization problems where the objective or constraint set involves the Kullback-Liebler divergence have been considered in earlier work, for example in csiszar1975divergence. Rather than establishing Lemma (ref) from the more abstract setting there, the proof in the Appendix utilizes well known properties of the KL divergence, stated as Lemma (ref) and Corollary (ref) in the Appendix. We note that Corollary (ref) (b) is a well known change-of-measure inequality (c.f. csiszar1975divergence and DonskerVaradhan1975) that is widely utilized in deriving PAC-Bayesian generalization bounds.

The property in (ref) is used in deriving the oracle-type inequalities in Section (ref). The result states that the duality gap between the primal and dual of the minimization problem in (ref) is zero. That is,

Note that the left-hand side of the above equality, the primal problem, is equivalent to the optimization problem in (ref). The right-hand side is the dual of this problem. That the right-hand side above is equivalent to the expression on the right-hand side of (ref) can be seen from a careful examination of (ref) or from Corollary (ref) (a) in the Appendix. The condition in (ref) constitutes a constraint qualification.

We will apply Lemma (ref) with $A(\theta) = R_{n}(\theta)$ or $R(\theta)$ and $H(\theta)=K_{n}(\theta)$ or $K(\theta)$. We consider two scenarios or perspectives. In the first, we have a (nonrandom) predetermined budget $B$ and utilize a corresponding, sample dependent, choice of $\hat{u}$. In the second scenario, we start from a predetermined, non-random choice of $u$ (or multiple values of $u$), which then corresponds to a sample dependent budget (or budgets) associated with $f_{G,\hat{\rho}_{\lambda, u}}$. We will require the following assumptions in order to satisfy (ref) in our analysis. The first will correspond to the case with a predetermined $B$ while the second condition will be utilized when we start from predetermined $u$.

Assumption (ref) involves $\mathcal{F}_{\Theta}$, $\pi$ and the sampling distribution $P$. Condition (i) requires that the budget of interest is not ruled out under the prior or reference measure $\pi$ and is not exactly at the boundary of theoretical or empirical feasibility. With additional exposition, the condition that $\pi\left ( \theta\in\Theta : K_{n}(\theta) < B \right ) >0$ holds $P^{n}$ a.s. could be replaced by the condition that $\pi\left ( \theta\in\Theta : K_{n}(\theta) < B \right ) >0$ holds with high probability. For example, with probability at least $1-\xi$, for some $\xi\in [0,1)$. In this case the theorems in Section (ref) will remain valid except that the high probability bounds there, that hold with probability at least $1-\epsilon$ for $\epsilon \in (0,1]$, will now hold with probability at least $1-\epsilon -\xi$. Condition (ii) requires that there is always variation in actual and empirical costs within models in $\mathcal{F}_{\Theta}$ drawn by $\pi$.

Given Lemma (ref) and the assumption above, the following definition will be relevant when the analysis starts with a predetermined budget $B$ for which we must find an appropriate value of $u$.

To conclude the section, we point out corollaries of Lemma (ref) and Assumption (ref) relevant to our setting. Define the sets

and

In the scenario where we start from a pre-selected $B$, $\mathcal{E}_{B}$ is the (non-random) subset of $\mathcal{P}_{\pi}(\Theta)$ corresponding to Gibbs treatment rules with expected cost within the budget. $\widehat{\mathcal{E}}_{B}$ a random set that serves as an empirical counterpart, denoting the $\rho\in\mathcal{P}_{\pi}(\Theta)$ with Gibbs rules that meet the budget constraint empirically.

When analysis begins with a pre-determined value of $u$, $B ( \hat{\rho}_{\lambda, u} )$ as in Assumption (ref) and its empirical counterpart $\widehat{B}( \hat{\rho}_{\lambda, u})$ both defined in (ref), are both random. $B ( \hat{\rho}_{\lambda, u} )$ is the expected cost of $f_{G,\hat{\rho}_{\lambda,u}}$ in the target population given the sample-dependent $\hat{\rho}_{\lambda, u}$. This is not observed. However, it is a key object of interest, as it tells the researcher the expected cost of the estimated policy $f_{G,\hat{\rho}_{\lambda, u}}$ associated with $u$. Similarly, for a predetermined $u$, both $\mathcal{E}_{B(\hat{\rho}_{\lambda, u})}$ and $\widehat{\mathcal{E}}_{\widehat{B}(\hat{\rho}_{\lambda, u})}$ are random sets. The former corresponds to all Gibbs treatment policies with an expected budget in the target population that is less than or equal to that of $f_{G,\hat{\rho}_{\lambda, u}}$. The latter serves as an empirical counterpart for which membership can be evaluated from the sample.

Given Lemma (ref) and Assumption (ref), the following lemma pertains to the empirical problem in (ref) and is mostly a corollary to (ref). It says that, for a pre-specified $B$, $\hat{\rho}_{\lambda, \hat{u}(B,\lambda)}$ solves (ref). Conversely, if we start with a predetermined value of $u$, $\hat{\rho}_{\lambda, u}$ solves an analogous problem where the budget is given by $\widehat{B}(\hat{\rho}_{\lambda, u})$.

PAC-Bayesian Analysis

Here we provide theoretical motivation for decision rules utilizing $\hat{\rho}_{\lambda, u}$ or $\hat{\rho}_{\lambda, \hat{u}(B,\lambda )}$. In Section (ref), we first construct PAC-Bayesian generalization bounds that are similar to counterparts in earlier literature. Then we derive oracle-type inequalities that compare the proposed treatment rules to alternatives in terms of regret in the target population for a given budget. The results in Section (ref) allow for a general choice of the prior or reference measure $\pi$ utilized in the definition of $\hat{\rho}_{\lambda, u}$ and $\hat{\rho}_{\lambda, \hat{u}(B,\lambda )}$. As a result, several bounds there contain KL divergence terms related to the complexity of the learning problem and the model class $\mathcal{F}_{\Theta}$. In Section (ref), we specify $\mathcal{F}_{\Theta}$ to consist of rules of the form in (ref) and take $\pi$ to be an uninformative multivariate normal distribution. In this setting, we obtain oracle-type inequalities that compare the regret of our proposed treatment assignment rules directly to that of the rules in $\mathcal{F}_{\Theta}$ with the lowest welfare regret that are in budget. In section (ref), we show that desirable properties for the majority vote rules associated with $\hat{\rho}_{\lambda, u}$ can be inherited by their majority vote counterparts.

Our analysis builds from results and techniques in the PAC-Bayesian literature that are not always stated in ways that are directly applicable to our setting. Results from earlier literature are adapted to our setting in Appendix Section (ref), which also contains additional properties of interest. For the most part, proofs are included there for completeness even when the adjustments are fairly minor. This spares the reader from visiting multiple references requiring concerted adjustments at certain steps of our analysis. Proofs specific to Section (ref) are contained in Appendix Section (ref).

Regret Bounds and Oracle-Type Inequalities

The first step in our analysis, Theorem (ref), obtains alterations of earlier PAC-Bayesian generalization bounds for the treatment assignment setting. A variant of part (a) appears in catoni2007pac which considers classification in the 0/1-loss setting. In our setting, it can be derived as a special case of a bound appearing in alquier2016properties or via a general approach to PAC-Bayesian bounds outlined, for example, in germain15aJMLR. We utilize the latter approach which is useful during additional steps of our analysis. The proofs of parts (b) and (c) utilize the approach of lever2010distribution, with part (b) being an alteration of Theorem 3 in that work.

Theorem (ref) contains high probability bounds for notions of the generalization error between the target population regret (or alternatively, expected cost) and its empirical counterpart for Gibbs treatment rules. For example, one notion of generalization error for the cost of policy $f_{G, \hat{\rho}_{\lambda, u}}$ could be the absolute difference, \[ \left \lvert K \left ( f_{G, \hat{\rho}_{\lambda, u}} \right )-K_{n} \left ( f_{G, \hat{\rho}_{\lambda, u}} \right ) \right \rvert .\] Suppose we take $\lambda = a\kappa \sqrt{n}/(M_{y}+uM_{c})$ for some constant $a>0$. Then Part (b) says that with probability at least $1-\epsilon$, this absolute difference is less than or equal to \[\frac{M_{c}}{\kappa \sqrt{2n}} \left [ a\sqrt{\log\left ( 4n \right ) + 2\log\frac{2}{\epsilon}}+ \frac{a^{2}}{2} + \log(2\sqrt{n})+\log\frac{2}{\epsilon} \right ]^{1/2} = \mathcal{O}\left ( \frac{\log{n}}{\sqrt{n}} \right ).\] When $M_{c}$ and $M_{y}$ are known, this upper bound can be evaluated for a given choice of $a$. We say that $K_{n}(f_{G,\hat{\rho}_{\lambda, u}})$ is Probably (with probability at least $1-\epsilon$) and Approximately (the $\mathcal{O}( \sqrt{ \log(n)/n} )$ upper bound on the absolute difference) Correct for $K(f_{G,\hat{\rho}_{\lambda, u}})$. This suggests that for a predetermined choice of $u$, $K_{n}(f_{G,\hat{\rho}_{\lambda, u}})$ will give a reasonable estimate of the expected cost in the target population, $K(f_{G,\hat{\rho}_{\lambda, u}})$, provided that $\lambda$ is not too large. Part (c) is a variation of the style of bound in (b) that is useful in deriving subsequent results. We note that the above choice for $\lambda$ may not be best in practice, or even feasible if the upper bound $M_{c}$ is not known. In practice $\lambda$ is chosen via cross-validation, which can be accommodated by Theorem (ref) similarly to the choice of $u$ as discussed below.

The bounds in Theorem (ref) can be adjusted to accommodate the setting where $\lambda$, $u$, or pairs $(\lambda, u)$ are selected from a finite set of values $\mathcal{W}$. With $\lvert \mathcal{W} \rvert$ denoting the number of elements in $\mathcal{W}$, one can apply a union bound argument similar to that in the proof of part (b). The theorem is applied once for each element of $\mathcal{W}$ with size $\epsilon/\lvert \mathcal{W} \rvert$ for each repetition. Then, applying the union bound argument, the bounds as stated in Theorem (ref) remain valid for any element of $\mathcal{W}$ with the alteration that the term $\log\frac{1}{\epsilon}$ in part (a) is replaced by $(\log\frac{1}{\epsilon} + \log \lvert \mathcal{W} \rvert )$ and the terms $\log \frac{2}{\epsilon}$ in parts (b) and (c) are replaced by $(\log\frac{2}{\epsilon} + \log \lvert \mathcal{W} \rvert )$. For example, when $\lambda = \mathcal{O}(\sqrt{n})$, this adds a term that is $\mathcal{O}( \log \lvert \mathcal{W} \rvert / \sqrt{n})$ to the right hand side of the high probability bound in part (a). This observation is applicable to the remaining theorems in the paper, with minor adjustments. Therefore, it is not unreasonable to start with multiple values for $u$. Then one may choose $u$ in $\hat{\rho}_{\lambda, u}$ for the final policy based on the empirical estimates of the associated budgets, $K_{n}(f_{G,\hat{\rho}_{\lambda, u}})$ for $u\in \mathcal{W}$, or via cross-validation.

Before comparing our suggested treatment policies to alternative choices, we discuss a final insight from Theorem (ref). Part (a) yields that, with probability at least $1-\epsilon$,

for all $\rho\in\mathcal{P}_{\pi}$ simultaneously. Given a budget $B$ such that Assumption (ref) (i) holds, Lemma (ref) (a) states that $\hat{\rho}_{\lambda, \hat{u}(B,\lambda)}$ produces the smallest upper bound for the target population regret in (ref) among all $\rho\in\mathcal{P}_{\pi}(\Theta)$ such that $K_{n}(f_{G,\rho})\leq B$. Similarly, starting from a given value of $u$, under Assumption (ref) (ii), Lemma (ref) (b) shows that $\hat{\rho}_{\lambda , u}$ results in the smallest upper bound for the target population regret among Gibbs rules with an empirical budget less than or equal to $\widehat{B}(\hat{\rho}_{\lambda, u})$.

Although Theorem (ref) (a) is most useful for our subsequent analysis, in the PAC-Bayesian literature there are alternative generalization bounds to (ref) that apply for all $\rho\in\mathcal{P}_{\pi}(\Theta)$ and could be adapted to our setting. Most notably, variants of the bounds in seeger2002pac and catoni2007pac are fairly ubiquitous in the literature. Either directly or via a slight relaxation, these bounds also suggest choosing $\rho$ to minimize

for some $\lambda >0$. Hence, if we impose an empirical budget constraint these would again lead back to $\hat{\rho}_{\lambda,\hat{u}(B,\lambda)}$ and $\hat{\rho}_{\lambda, u}$. We note that Seeger's bound is utilized in our analysis to derive parts (b) and (c) of Theorem (ref) and appears as Theorem (ref) in Appendix Section (ref). While this bound does not yield a closed form solution $\tilde{\rho}$ that minimizes an upper bound on the regret, we refer to the discussion in pmlr-v76-thiemann17a regarding a relaxation that suggests minimizing (ref) with $\lambda$ replaced by $\lambda n$, which will yield the an equivalent minimization problem when $\lambda$ is cross-validated. The style of bound in catoni2007pac, in particular Theorem 1.2.6 there, can be adapted to our setting via the approach in germain15aJMLR and again suggests choosing $\rho$ to minimize (ref).

Next we derive oracle-type inequalities that compare the target population regret associated with $\hat{\rho}_{\lambda, u}$ or $\hat{\rho}_{\lambda, \hat{u}(B,\lambda )}$ to that of alternative choices of $\rho$ among Gibbs treatment rules within a relevant budget. It may be helpful to recall the definitions of $\mathcal{E}_{B}$ and $\mathcal{E}_{B(\hat{\rho}_{\lambda ,u})}$ from (ref) and (ref), \[\mathcal{E}_{B} = \left \{ \rho\in\mathcal{P}_{\pi}(\Theta): K\left ( f_{G,\rho} \right ) \leq B \right \} \ \mathrm{and} \ \mathcal{E}_{B(\hat{\rho}_{\lambda, u})} = \left \{ \rho\in\mathcal{P}_{\pi}(\Theta): K\left ( f_{G,\rho} \right ) \leq K\left ( f_{G,\hat{\rho}_{\lambda, u}} \right ) \right \}.\] We have the following result.

Note that if $\lambda =\mathcal{O}(n^{1/2})$ , then for any $u\geq 0$ and $\epsilon\in (0,1]$, \[U_{1}\left ( \epsilon ; \lambda, u , n \right ) = \mathcal{O} \left ( \sqrt{\frac{\log(n)}{n}} \right ) \ \mathrm{and} \ U_{2}\left ( \epsilon ; \lambda, u , n \right ) =\mathcal{O} \left ( \frac{1}{\sqrt{n}} \right ). \] Theorem (ref) contains sharp oracle-type inequalities that hold with high probability. They differ slightly from traditional oracle inequalities in that the right-hand sides contain objects that are random.

Consider part (b) first. In this case, the randomness on the right-hand side of the inequality stems from $\mathcal{E}_{B ( \hat{\rho}_{\lambda, u} )}$ which depends on the sample through $B ( \hat{\rho}_{\lambda, u} )=K (f_{G,\hat{\rho}_{\lambda, u}})$, the un-observable expected target population cost of $\hat{\rho}_{\lambda, u}$. For a predetermined $u$, it is natural to ask if there are alternatives in $\mathcal{P}_{\pi}(\Theta)$ that would yield lower regret for the same or lower expected cost. $\mathcal{E}_{B ( \hat{\rho}_{\lambda, u} )}$ is therefore the natural set of interest for comparison with $\hat{\rho}_{\lambda, u}$ as it is the subset of $\mathcal{P}_{\pi}(\Theta)$ with Gibbs rules that have target population costs no greater than $B ( \hat{\rho}_{\lambda, u} )$. Given a budget $B ( \hat{\rho}_{\lambda, u} )$, an oracle with knowledge of $R(\theta)$ could solve for $ \arg\min_{\rho\in\mathcal{E}_{B ( \hat{\rho}_{\lambda, u} )}} R(f_{G,\rho})$. For $\lambda \rightarrow \infty$, we may consider $\arg\min_{\rho \in \mathcal{E}_{B ( \hat{\rho}_{\lambda, u} )}} R(f_{G,\rho}) +\lambda^{-1}D_{\mathrm{KL}}(\rho,\pi) $ as a second-best oracle solution. When $\lambda = \mathcal{O}(n^{1/2})$, for example, part (b) indicates that with high probability $\hat{\rho}_{\lambda, u}$ is close to the second best oracle solution. In Section (ref) we consider oracle-type inequalities without the KL penalty term appearing.

In part (a), the interpretation is similar to that in part (b), except that now the set of alternative Gibbs estimators for comparison are those that satisfy the predetermined budget $B$. This set is non-random, however now the right-hand side contains a term involving the random $\hat{u}=\hat{u}(B,\lambda)$. Note that $\hat{u}$ is the value taken by the Lagrange multiplier $u$ in the problem \[\min_{\rho\in\mathcal{E}_{B}} \sup_{u\geq 0} \left \{ \int_{\Theta}R_{n}(\theta) d\rho(\theta)+\frac{1}{\lambda }D_{\mathrm{KL}}(\rho,\pi) + u\left ( \int_{\Theta}K_{n}(\theta)d\rho(\theta) -B \right ) \right \}. \] It measures the marginal decrease in empirical penalized regret (alternatively, the increase in empirical penalized welfare) resulting from a marginal relaxation of the budget. Recall the welfare and budget are measured per treatment. For example, when benefits and costs are measured in dollars, how many dollars of penalized welfare are obtained (empirically) by increasing the maximum empirical cost by a dollar. In more extreme scenarios where a small increase in the budget produces a large increase in empirical welfare, the bound becomes less meaningful as the right-hand side approaches the maximum possible regret (if this level is exceeded, the bound becomes trivial). An example of an extreme setting would be when $\hat{u}=\mathcal{O}_{p}(n^{\alpha})$ for some $\alpha \geq 1/2$. When $\hat{u}n^{-1/2}$ is large relative to typical or maximal values of the regret (which ranges from zero to twice the maximal welfare), this situation is visible to the analyst. For a fixed $\lambda$, a statement similar to part (a) can be obtained where $\hat{u}$ is replaced by a non-random constant if we make additional assumptions on the data generating distribution $P$. For example, if we instead assume the marginal increase in population penalized regret associated with a small relaxation of the empirical budget is $\mathcal{O}_{p}(1)$. As it stands, the bound produces a robustness check for the method’s motivation. Intuitively, if it is easy to dramatically change the empirical welfare by relatively small budget changes, so that $\hat{u}n^{-1/2}$ is large, we may be in a situation where it is difficult to learn policies well for the given $B$ and the proposed rules should be treated cautiously.

If regions of the model space with desirable regret and budget are assigned lower probability by $\pi$, the distributions $\rho\in\mathcal{P}_{\pi}(\Theta)$ with the best trade-off between $R(f_{G,\rho})$ and $D_{\mathrm{KL}}(\rho,\pi)$ in Theorem (ref) will tend to have larger $D_{\mathrm{KL}}(\rho,\pi)$ terms. As a result, the upper bounds will be larger and less informative. Similarly, applying Theorem (ref) part (a) with $\rho=\hat{\rho}_{\lambda, c}$ for either $c=u\geq 0$ or $c=\hat{u}(B,\lambda)$, and noting Lemma (ref), the regret and budget bounds there are influenced by the trade-off between empirical regret (or cost) and $D_{\mathrm{KL}}(\hat{\rho}_{\lambda, c}, \pi)$. $D_{\mathrm{KL}}(\hat{\rho}_{\lambda, c}, \pi)$ increases when $\hat{\rho}_{\lambda, c}$ involves a greater re-weighting of $\pi$ in definition (ref). The impact of the KL terms in the bounds of this subsection are therefore related to the learning problem and model space complexity. It is influenced by how large the model space is, how narrow the subset of the model space with low regret/budget is, the relative difference in between lower and higher regret regions and the noisiness of the data. In parts (b) and (c) of Theorem (ref), where the KL term is absent, this role falls more to the $\lambda$ parameter: if the problem is more complex, larger (relative to $n$) values of $\lambda$ are needed to achieve lower regret or cost. If $\lambda$ is too large, remainder terms in the generalization error bounds increase. See lever2010distribution for further discussion of complexity in the setting of bounds of the form in (b) and (c).

Conversely, when the policy maker has (sample independent) knowledge of the data generating process, they may be able to select or alter a given choice of $\pi$ to focus on the regions of the model space that best balance regret and cost. Then $D_{\mathrm{KL}}(\rho, \pi)$ can be smaller for $\rho$ that put the greatest weight on the most desirable regions of the parameter space. The result is smaller upper bounds in Theorem (ref) and Theorem (ref) (a). A benefit of the Gibbs rules associated with $\hat{\rho}_{\lambda, u}$ and $\hat{\rho}_{\lambda, \hat{u}(B,\lambda)}$ is that economic theory or situation-specific knowledge can be factored into the treatment rule via $\pi$. Compatibility with expert knowledge may be a valuable advantage in settings where resource limitations imply that some individuals with a positive CATE will not be treated. As we will see in Section (ref), such knowledge is not required for the procedures to have desirable properties.

Normal Prior

As noted at the end of Section (ref), perhaps unsurprisingly, knowledge about the data generating process can confer estimation benefits through the choice of $\pi$. While it is a positive attribute that the proposed treatment rules can utilize this information when available, it is important to emphasize that such knowledge is not a requirement. Learning procedures based on PAC-Bayesian analysis often utilize uninformative or less informative choices for $\pi$, such as normal distributions, uniform distributions when $\Theta$ is compatible, or sparsity inducing distributions.

Here we take $\pi$ to be a multivariate normal distribution centered at the origin and utilize the models of the form in (ref). We show that the proposed treatment rules maintain desirable properties. In doing so, the KL divergence term is removed from the oracle inequalities, resulting in a clearer comparison to alternative treatment rules. We leave an exploration of alternative prior choices and the settings where they may be desirable to future research.

We satisfy Assumptions (ref) and (ref) with the following, more specific, condition. Note that in the assumption below we are treating $q$ as fixed; it does not grow with the sample size.

Next, we define

and denote

Note that $\Theta_{B ( \hat{\rho}_{\lambda, u} )}$ and $\overline{\theta}_{u}$ are random as they vary with $B ( \hat{\rho}_{\lambda, u} )$. $\Theta_{B ( \hat{\rho}_{\lambda, u} )}$ is the set of parameters such that the corresponding models in $\mathcal{F}_{\Theta}$ have lower expected target population cost than $f_{G,\hat{\rho}_{\lambda, u}}$. $\overline{\theta}_{u}$ is the minimizer of the population regret among this set. With regard to $\overline{\theta}$ and $\overline{\theta}_{u}$, we assume the following condition.

This type of condition is implicitly assumed in, for example, KT2018 and in sun2021empirical. It simplifies the exposition rather than allowing that the models associated with these parameters have regret that is arbitrarily close to an infimum. The requirement that $\overline{\theta}$ and $\overline{\theta}_{u}$ are nonzero simply specifies that the covariates are relevant to the budget constrained welfare problem. Lastly, our analysis will also require the following technical condition.

Assumption (ref) or a direct analog is applied in several classification and bipartite ranking applications utilizing PAC-Bayesian approaches. For examples, see ridgway2014pac, alquier2016properties, and guedj2018pac. It is a fairly mild requirement and, as is shown in alquier2016properties (c.f. p. 10 there), it is satisfied whenever $\phi(X)/\lVert \phi(X) \rVert$ has a bounded density on the unit sphere.

We have the following result.

Note that the values for $\lambda$ in parts (a) and (b) are chosen to produce the nearly optimal rate of convergence in part (b). In practice there may be better choices and we will typically choose $\lambda$ via cross-validation. As noted in the discussion following Theorem (ref), we may choose $\lambda$, $u$, or pairs $(\lambda, u)$ from a finite set of values $\mathcal{W}$. In this case the theorem above can be adjusted to hold simultaneously for all elements of $\mathcal{W}$ by replacing the terms $\log ( \epsilon/3)$ on the right-hand side of the inequality in (a) by $\log(\epsilon/3)+\log|\mathcal{W}|$ and the terms on the right-hand side of (b) that involve $\log ( \epsilon/4)$, which appear in the $\overline{U}_{j}$ terms defined in the proof, are replaced by $\log(\epsilon/4)+\log|\mathcal{W}|$. For example, for fixed $\epsilon\in (0,1]$ and $u\geq 0$, this adds a term that is $\mathcal{O}(\log |\mathcal{W}| n^{-1/2})$ to the right hand side of (b).

In Theorem (ref), $f_{G,\hat{\rho}_{\lambda, \hat{u}(B,\lambda) }}$ and $f_{G,\hat{\rho}_{\lambda, u }}$ are compared to the best (non-stochastic) models in $\mathcal{F}_{\Theta}$ with an expected cost no greater than $B$ or $B ( \hat{\rho}_{\lambda, u} )$, respectively. Additionally, the absence of KL terms in the inequalities allows for a more salient comparison to relevant alternatives. In part (b), for any $u\geq 0$ and $\epsilon\in(0,1]$, the terms beside $R(\overline{\theta}_{u})$ on the right hand-side are collectively $\mathcal{O}(\log(n)n^{-1/2})$. With high probability, the regret of $f_{G,\hat{\rho}_{\lambda,u}}$ gets close to the regret an oracle would obtain choosing the best rule from the subset of $\mathcal{F}_{\Theta}$ with a target population budget no greater than that of $f_{G,\hat{\rho}_{\lambda,u}}$. The rate $\log(n)n^{-1/2}$ is nearly optimal. For example, in the unconstrained case with $B=\infty$, which corresponds to $u=0$ or $\hat{u}=u^{*}=0$, KT2018 show that $n^{-1/2}$ is the optimal rate for bounds on the expected regret of the empirical welfare maximizer over $\mathcal{F}_{\Theta}$, provided $\mathcal{F}_{\Theta}$ has a finite VC-dimension (see the discussion there for more details).

Part (a) has the complication of involving $\hat{u}=\hat{u}(B,\lambda)$ and $u^{*} = u^{*}(B,\lambda/2)$ as $\lambda$ grows with $n$. The effect of $\hat{u}$ is related to the marginal decrease in $R_{n}(f_{G,\hat{\rho}_{\lambda, \hat{u}(B,\lambda)}}) +\lambda^{-1}D_{\mathrm{KL}}(\hat{\rho}_{\lambda, \hat{u}(B,\lambda)}, \pi )$ associated with marginal increases in $B$ as the penalty diminishes ($\lambda$ increases). The behavior of $u^{*}$ is related to the marginal decrease in the penalized regret of $f_{G,\rho^{*}_{\lambda,u^{*}(B,\lambda/2)}}$ associated with marginal increases in $B$. Suppose we are unlikely to have large marginal gains in empirical or theoretical penalized regret associated with a marginal increase in $B$ at all or small penalty levels (i.e. as $\lambda\rightarrow \infty$). Then (a) implies that, with high probability and for large enough sample sizes, the regret of $f_{G,\hat{\rho}_{\lambda, \hat{u} }}$ is close to the regret that would be obtained by an oracle choosing the best policy from the subset of $\mathcal{F}_{\Theta}$ with an expected cost in the target population that is less than or equal to $B$. For example, if $u^{*}=\mathcal{O}(1)$ and $\hat{u}=\mathcal{O}_{p}(1)$ as $n$ and $\lambda $ increase, then the terms on the right-hand side of the inequality in (a) other than $R(\overline{\theta})$ are $\mathcal{O}_{p}(\log(n)n^{-1/2})$.

We conclude this subsection with remarks regarding implications for the proposed treatment assignment rules. One drawback of starting from a fixed $B$ and utilizing $\hat{u}=\hat{u}(B,\lambda)$ is the absence of a counterpart to Theorem (ref) (b) for the cost $K(f_{G,\hat{\rho}_{\lambda, \hat{u}}})$ when $\hat{u}$ is random. Even when $\hat{u}$ and $u^{*}$ are well behaved so that Theorem (ref) (a) implies it is likely that $f_{G,\hat{\rho}_{\lambda, \hat{u}}}$ will have regret comparable to the best rules in $\mathcal{F}_{\Theta}$ with expected cost less than $B$, this may be achieved with an expected cost greater than $B$. On the other hand Theorem (ref) (a) with $\rho = \hat{\rho}_{\lambda, \hat{u}}$ yields that with probability at least $1-\epsilon$, \[K\left ( f_{G,\hat{\rho}_{\lambda, \hat{u}}} \right ) \leq B + \frac{1}{\lambda}D_{\mathrm{KL}}\left ( \hat{\rho}_{\lambda, \hat{u}}, \pi \right ) + \frac{1}{\lambda}\left [ \frac{\lambda^{2}M^{2}_{c}}{8n\kappa^{2}}+\log\frac{1}{\epsilon} \right ], \] where we have used the fact that $K_{n}(f_{G,\hat{\rho}_{\lambda, \hat{u}}})\leq B$ a.s. under the assumptions of the theorem. When $\lambda =\mathcal{O}(n^{1/2})$, for example, whether or not we have an upper bound that approaches $B$ depends on the behavior of this KL term. Unfortunately, $\hat{u}$ and the KL term above are difficult to analyze in this scenario as $\hat{u}$ is essentially defined implicitly to ensure $K_{n}(f_{G,\hat{\rho}_{\lambda, \hat{u}}})\leq B$. It is possible to cross-validate $B$, for example examining values less than $B$ to try and ensure the expected budget is not violated. The comments regarding extending the high probability bounds to apply simultaneously for multiple values of $u$ can be applied to choices for $B$ as well.

On the whole, the procedure starting with a set of values for $u$ may be more compelling. By Theorem (ref) (b) and the surrounding discussion, for values $u$ in a reasonably sized set $\mathcal{W}$, the values of $K_{n}(f_{G,\hat{\rho}_{\lambda, u}})$ provide reasonable estimates of $K(f_{G,\hat{\rho}_{\lambda, u}})$, the expected costs of these policies conditional on the rules estimated from the sample. These can be utilized to select $u$. Alternatively, $u$ can be chosen from $\mathcal{W}$ via cross-validation or by some other method. For example, in the case of pure quantity constraints, it may be possible use data from the target population to select $u$ to achieve the correct (or nearly correct) proportion of treatments assigned in the target population. Theorem (ref) (b) and its extension to hold for all $u\in\mathcal{W}$ simultaneously, then indicate it is likely $ R(f_{G,\hat{\rho}_{\lambda, u}})$ for the selected $u$ will be comparable to the best treatment rules in $\mathcal{F}_{\Theta}$ among those whose target population cost does not exceed that of $f_{G,\hat{\rho}_{\lambda, u}}$. Hence by starting from a set of $u$ values, the policy maker can trace out reasonable estimates of the target population budget horizon. At the same time, the policy selected according to these budget estimates is likely to be the best bang for the buck in that the associated regret gets close to that which an oracle would choose for the same target population cost.

The Majority Vote Treatment Rule

Let $\rho\in\mathcal{P}_{\pi}(\Theta)$. As mentioned in Section (ref), the non-stochastic majority vote treatment rule $f_{\mathrm{mv},\rho}$ in (ref) is a close relative of the Gibbs rule $f_{G,\rho}$ that can prove numerically more stable in practice. In the classification literature, it is well known that the risk associated with the majority vote rule, where risk is defined for a zero-one loss function, is upper bounded by twice the risk associated with the Gibbs classification method (e.g., langford2003pac, mcallester2003simplified). Hence analysis of the Gibbs treatment rule is often used to justify use of the majority vote. Additionally, the “$2 \times$" upper bound can be loose and it is not uncommon for majority vote rules to outperform Gibbs rules. We refer to germain15aJMLR for further discussion regarding the majority vote versus the Gibbs method for classification settings. Here, we show that, as in the classification setting, the majority vote treatment rule can inherit desirable qualities from the Gibbs treatment rule in the budget constrained treatment rule setting.

While the majority vote rule $f_{\mathrm{mv},\rho}$ is not guaranteed to satisfy the same budget as its Gibbs counterpart $f_{G,\rho}(x)$, we can still show that when $f_{G,\rho}(x)$ is close to $f^{*}_{B(\rho)}(x)$, the optimal rule for its budget, \[B(\rho) = K(f_{G,\rho}),\] then $f_{\mathrm{mv},\rho}$ will also be close to $f^{*}_{B(\rho)}$. The measurement of closeness, defined shortly, depends on both the welfare achieved and deviations from the budget $B(\rho)$. We will suppose that

That is, $f_{G,\rho}$ does not achieve the exact cost of the cost-minimizing rule $1\{\delta_{c}(x)<0\}$ for $x\in\mathcal{X}$. If (ref) were an equality, the budget of $f_{G,\rho}$ would be such that a policy maker faced with this budget would need to ignore welfare and seek the lowest cost rule. Hence, when we are interested in maximizing welfare with a budget constraint, it is reasonable to rule out the case where the solution to the policy maker's problem is to ignore welfare and seek the lowest cost. In addition to (ref), we will assume that $\delta_{y}(X)$ and $\delta_{c}(X)$ have bounded densities so that optimal solution to the decision makers in Theorem (ref) is deterministic.

Under (ref), Assumption (ref), and the condition that $\delta_{y}(X)$ and $\delta_{c}(X)$ have bounded densities, Theorem (ref) yields that the optimal budget-constrained policy for the budget $B(\rho)$ of the Gibbs rule $f_{G,\rho}$ is of the form

for a constant $\eta_{B(\rho)}$. It also follows from Theorem (ref) that either $\eta_{B(\rho)}=0$ and $K(f^{*}_{B(\rho)})<B(\rho)$ or else $\eta_{B(\rho)}>0$ and $K(f^{*}_{B(\rho)})=B(\rho).$ Recalling the definition of the welfare-regret under a budget constraint in (ref), \[R_{B(\rho)}(f) \equiv W\left ( f^{*}_{B(\rho)} \right )- W\left ( f \right ),\] it is clear that $R_{B(\rho)}(f_{G,\rho})$ is non-negative. It is small only when $f_{G,\rho}$ attains a welfare that is close to the budget optimal rule in its own budget class. We will show that when $R_{B(\rho)}(f_{G,\rho})$ is small, $f_{\mathrm{mv},\rho}$ has similar welfare to the optimal policy $f^{*}_{B(\rho)}$ and is unlikely to violate the budget $B(\rho)$ by a large amount.

First note that if a decision maker faced a budget of $B(\rho)$, it would be reasonable to seek a rule $f:\mathcal{X}\rightarrow[0,1]$ that minimizes \[L_{B(\rho)}(f) \equiv E_{Q}\left [ \left ( \delta_{y}(X)-\eta_{B(\rho)} \delta_{c}(X) \right ) \left (f^{*}_{B(\rho)}(X)-f(X) \right ) \right ],\] with the associated loss function

By the form of $f^{*}_{B(\rho)}$ in (ref), $L_{B(\rho)}(f)$ is non-negative and attains the value zero only when $f(X)=f^{*}_{B(\rho)}(X)$ almost surely. Of course, such a loss function cannot yield an estimation strategy directly because $\delta_{y}$, $\delta_{x}$, and $\eta_{B(\rho)}$ are unknown. However, when $L_{B(\rho)}(f)$ is small, this means we are unlikely to encounter a set of co-variates $X$ for which $f$ assigns treatment and $\eta_{B(\rho)}\delta_{c}(X)$ exceeds $\delta_{y}(X)$ by a large amount. We have the following result

We note that the expectation in the definition of $L_{B(\rho)}(f)$ is taken with respect to a draw from the target population. When $\rho$ is dependent on the sample data, the result and proof still hold, conditional on the estimated rule or sample, provided that (ref) can be assumed to hold almost surely for $\rho$ or with high probability if considering probabilistic bounds such as those in Sections (ref) and (ref). This is reasonable to assume for $\hat{\rho}_{\lambda, u}$, particularly when $u$ is not so large that no treatments will be assigned. The notion that, for appropriately chosen values of $\lambda$, $R_{B(\hat{\rho}_{\lambda, u})}(f_{G,\hat{\rho}_{\lambda, u}})$ is small is exactly the implication of Theorems (ref) (b) and (ref) (b).

For example, assume that the conditions of Theorem (ref) hold, take $\lambda = \kappa \sqrt{nq}/(M_{y}+uM_{c})$ (although we continue to write $\lambda$ to reduce clutter in the notation), and suppose that (ref) holds almost surely for $\rho = \hat{\rho}_{\lambda, u}$ and that $\delta_{c}(X)$ and $\delta_{y}(X)$ have bounded densities. Then by Theorem (ref) (b), with probability at least $1-\epsilon$ it holds that

where we have done some simple algebra on the inequality of part (b) of Theorem (ref) utilizing the definitions of regret and regret under a budget constraint. The above also uses the notation \[ R_{ B ( f_{G,\hat{\rho}_{\lambda, u}} )}(\theta) = W\left ( f^{*}_{B ( f_{G,\hat{\rho}_{\lambda, u}} )} \right ) - W \left ( f_{\theta} \right ). \] Recall that the terms outside of the $\arg\min$ on the right-hand side of the above inequality are at most $\mathcal{O}(\log(n)n^{-1/2})$ for fixed $u\geq 0 $, $q\in\mathbb{N}$ and $\epsilon\in (0,1]$. If, for example, \[\delta_{y}(X) = \phi(X)^{\intercal}\theta_{y}, \ \ \mathrm{and} \ \ \delta_{c}(X) = \phi(X)^{\intercal}\theta_{c}, \] for some $\theta_{y},\theta_{c}\in\mathbb{R}^{q}$, then we would have \[\underset{\theta\in \Theta_{B(\hat{\rho}_{\lambda, u})}}{\arg\min} \left [ R_{ B ( f_{G,\hat{\rho}_{\lambda, u}} )}(\theta) \right ]=0.\] In this case, the above combined with Theorem (ref) produce that, with probability at least $1-\epsilon$, $L_{B(\hat{\rho}_{\lambda, u})}(f_{\mathrm{mv},\hat{\rho}_{\lambda, u}})$ is bounded above by terms that are $\mathcal{O}(\log(n)n^{-1/2})$.

Simulation Study and Implementation Details

In this section we evaluate the proposed treatment assignment methodology in a simulation environment. We also discuss model estimation and implementation. Section (ref) describes the simulation environment and findings. Section (ref) describes a model estimation strategy using the Sequential Monte Carlo (SMC) approach and discusses the implementation choices utilized in the simulation.

Simulation Study

We assign treatments utilizing $\hat{\rho}_{\lambda, u}$ in the following simulation environments. We take $X= ( X_{1}, X_{2}, X_{3} )$ where $X_{j}\sim \mathrm{Unif}(-1,1)$ for $j=1,2,3$ are i.i.d. uniform random variables. Letting $\Lambda(v)=(1+\exp(-v))^{-1}$ denote the logistic function, potential outcomes are determined via \[Y_{d}=\max\{X_{1}+X_{2}, 0\}+\max\{ X_{3},0 \} + 4 d \Lambda\left ( 2 \left ( X_{1}+X_{1}X_{2}+X_{2} \right ) \right )+\epsilon, \ \ d\in\{0,1\}, \] where $\epsilon$ is taken to be a standard normal random variable that is truncated to take values in $[-2,2]$ and is independent of all other variables considered. Potential costs are determined via \[C_{0}=0, \ \ C_{1}\sim \mathrm{Binom}\left ( 6, \frac{ 4\Lambda\left (a(3 X_{2} + 1.5 X_{3} ) \right )}{6} \right ),\] where $a$ is a constant. Lastly, $e(x)=1/2$ for all $x\in\mathcal{X}$ so that $D\sim \mathrm{Bern}(1/2)$ and is independent of the other variables. We consider $a\in\{1,2,4\}$.

Each choice of $a$ corresponds to a different data generating process (DGP) and for each we perform the following simulation study separately. We simulate training sets each with sample size $n=1,000$. A testing sample of size $n_{\mathrm{test}}=10,000$, which is re-used across training sample iterations, yields approximately the true costs and benefits from of any considered treatment rule. We consider 100 training simulation replicates. Using knowledge of the DGP, we can calculate $E_{Q}[Y_{1,i}-Y_{0,i}|X_{i}]$ and $E_{Q}[C_{1,i}|X_{i}]$ for each testing set observation. Then, for a rule $f(x):\mathcal{X}\rightarrow [0,1]$, we use the testing set to obtain the (approximate) gain and cost associated with $f$, \[\mathrm{Gain \ of \ } f = E_{Q}\left [ \left ( Y_{1}- Y_{0} \right ) f(X) \right ],\] and \[\mathrm{Cost \ of \ } f = E_{Q}\left [ C_{1} f(X) \right ].\] The Gain of $f$ is the expected increase in welfare, relative to no treatments, associated with the treatment rule policy while the Cost of $f$ is its cost.

Section (ref) describes the Sequential Monte Carlo procedure used to sample from $\hat{\rho}_{\lambda, u}$ to implement the associated Gibbs or majority vote rule. We consider values of $u$ increasing from $0$ to $2$ in increments of $0.05$. For each choice of $u$, $\lambda$ is chosen by $4$-fold cross-validation to maximize $W_{n}(f)-uK_{n}(f)$ across hold-out folds, where $f=f_{G,\hat{\rho}_{\lambda, u}}$ for the Gibbs rules and $f=f_{\mathrm{mv},\hat{\rho}_{\lambda, u}}$ for the majority vote rules. We thus obtain treatment rules with varying gain-cost pairs for different choices of $u$ and can obtain cross-validation-based estimates of these pairs during the estimation stage.

To make estimation from a training sample operational, we must specify a treatment rule space $\mathcal{F}_{\Theta}$ and prior $\pi$. With $d_{x}$ denoting the dimension of $\mathcal{X}$ ($d_{x}=3$ in the simulation setting), for $k\in\mathbb{N}$ and $q_{k}={d_{x} + k \choose k}$, the polynomial transformation on $\mathcal{X}$ of order at most $k$ is defined as

where the summation is over all monomials $\phi_{j}(x)=\prod^{d}_{\ell=1}x_{\ell}^{p_{j\ell}}$ with $\sum_{\ell=1}^{d}p_{j\ell}\leq q$, $p_{j\ell}\in \mathbb{N}\cup\{0\}$. We take $\mathcal{F}_{\Theta}$ to be the family of rules described in (ref) and (ref) where the transformations $\phi_{j}(x)$ are the monomials used in the construction of the polynomial transformations on $\mathbb{R}^{3}$ of order at most $2$ with the monomials normalized by their sample mean and standard deviation calculated from training data. We set $\pi $ to be the standard multivariate normal distribution over $\mathbb{R}^{10}$.

As an alternative treatment rule, we consider the approach of sun2021treatment. Under our simulation setting, where for example $C_{0}\leq C_{1}$ almost surely, $f^{*}_{B}$ in Theorem (ref) takes the form \[f^{*}_{B}(x) = 1\left \{ \frac{\delta_{y}(x)}{\delta_{c}(x)} > \eta_{B} \right \},\] for some constant $\eta_{B}$. sun2021treatment show that $\delta_{y}(x)/\delta_{c}(x)$ can be estimated nonparametrically by re-purposing the so-called generalized random forest methodology of athey2019generalized. When costs can be observed at the time of treatment assignment, their approach first estimates $\delta_{y}(x)/\delta_{c}(x)$ for $x\in\mathcal{X}$. This produces an estimate of the conditional welfare to conditional cost ratio $\delta_{y}(X_{i})/\delta_{c}(X_{i})$ for each observation in the target group\footnote{By target group we mean individuals or units for whom treatment assignment must be determined, typically this is the wider population from which the sample comes from that consists of individuals or units not used in fitting treatment rules.}. These ratio estimates are ranked according in descending order and treatments are allotted according to this order until the budget is exhausted. We call such a method of assignment, where a ranking is derived for members of the target group who are then treated in that order until the budget is reached, a “batch implementation" method. Additionally, as a baseline rule, we estimate the CATE $\delta_{y}(x)=E_{Q}[Y_{1}-Y_{0}|X=x]$ using the generalized random forest of athey2019generalized and then use the resulting scores in the target group for a batch implementation. This baseline approach does not factor costs into the treatment decisions. In our simulations, these methods are implemented using R 4.2.2 (R_key) with the grf package (grf_r_key) following the described adaptation in sun2021treatment for their approach. The default package settings were except that the known treatment probabilities supplied to the algorithm.

The approach of sun2021treatment and the baseline that ignores cost utilize batch implementations while the Gibbs and majority vote methods do not. To compare like-for-like, the majority vote models associated with $\hat{\rho}_{\lambda, u}$ for a range of $u$ values (with $\lambda$ chosen via cross-validation for each $u$) are amenable to a batch implementation method. An algorithm for implementing a batch treatment rule utilizing the majority vote rules is described below.

\hrulefill

\noindentBatch treatment implementation utilizing majority vote rules

\hrulefill

\noindentInput Target group observations indexed by $\mathcal{I}_{\mathrm{target}} = \{ 1, 2,\dots, n_{\mathrm{target}} \} $ with $n_{\mathrm{target}}$ total observations and covariates $\{X_{j}: j\in\mathcal{I}_{\mathrm{target}}\}$, minimum cost $B_{\mathrm{min}}$, number of bins used denoted $n_{\mathrm{bin}}$, budget $B$, set of $u$ values denoted $\mathcal{W}_{u}$, majority vote rules $f_{\mathrm{mv}, \hat{\rho}_{\tilde{\lambda}_{u},u} }$ for each $u\in\mathcal{W}_{u}$ along with cost estimates $\hat{\mathrm{cost}}(f_{\mathrm{mv},\hat{\rho}_{\tilde{\lambda}_{u}, u}})$. If treatment is assigned to $X_{j}$, we then observe the cost of treating individual $j$, $C_{1,j}.$

\noindentOutput $\mathcal{I}_{\mathrm{treat}} \subseteq \mathcal{I}_{\mathrm{target}}$, a subset of individuals in the target group assigned treatment.

Step 1: Initialization

Set $B_{0} \leftarrow B_{\mathrm{min}}$ and $\mathcal{I}_{\mathrm{treat}} \leftarrow \emptyset$.

Step 2: Treatment determinations

For $i=1:n_{\mathrm{bin}}$

End For

\hrulefill

The algorithm above divides the cost space below the budget into bins and then performs a batch implementation at each bin using the majority vote scores of the model with an estimated cost nearest to that bin's endpoint. Note that we are using the notation $\tilde{\lambda}_{u}$ in $f_{\mathrm{mv}, \hat{\rho}_{\tilde{\lambda}_{u},u} }$ to reflect that $\lambda$ varies with $u$ and is data dependent. For $\hat{\mathrm{cost}}(f_{\mathrm{mv}, \hat{\rho}_{\tilde{\lambda}_{u},u} }),$ one could use $K_{n}(f_{\mathrm{mv}, \hat{\rho}_{\tilde{\lambda}_{u},u} })$, an estimate of the cost arising during the cross-validation of $\lambda$, or some other estimate such as one arising from an auxiliary testing dataset if one is available. Minor modifications may improve the performance, for example dropping any values of $u$ from consideration in Step $2$ if there exists another $u'$ with a corresponding estimated majority vote model that has lower estimated cost but higher estimated welfare. However, in our simulations we use the simpler version presented above. We take $\hat{\mathrm{cost}}(f_{\mathrm{mv}, \hat{\rho}_{\tilde{\lambda}_{u},u} })$ to be the average cost associated with $f_{\mathrm{mv}, \hat{\rho}_{\tilde{\lambda}_{u},u} }$ across the hold-out fold samples during the cross-validation of $\lambda$ when estimating $\hat{\rho}_{\lambda, u}$ for the majority vote model.

The batch implementation utilizing the majority vote rules is noteworthy because, when batch implementation is feasible, it controls costs accurately. In our simulations, we created $20$ equally spaced cost bins, starting at $0$ and with endpoints increasing from $0.1$ to $2$ by increments of $0.1$. We treated each end point as a desired budget level and applied the batch implementation that utilizes the majority vote models. For example, the first desired budget level is $B=0.1$ and utilizes $n_{\mathrm{bin}}=1$ in the algorithm above, while the last desired budget is $B=2$ and we set $n_{\mathrm{bin}}=20$. Throughout, we take $B_{\mathrm{min}}=0$. For each budget level we also applied the alternative batch implementation methods. The gains associated with models fit to each training sample iteration were calculated using the test set. Then these gains were averaged over all training sample iterations to produce Figures (ref), (ref) and (ref) for $a=1, 2, 4$, respectively. We denote the batch implementation method utilizing the majority vote models by “PB-B", we denote the non-parametric method of sun2021treatment centered around the conditional welfare to conditional cost ratio by “R-NP", and we denote the baseline that ignores cost by “Ignore Cost" or IC in subsequent discussion.

We will refer to the non-batch-implemented stochastic Gibbs and non-stochastic majority vote methods by “PB-G" and “PB-MV", respectively. To assess these methods, we utilize “cost curves" to compare the gain-cost trade-off of the considered rules at different budget levels. These are constructed as follows. For a single training sample iteration, for each $u$ we estimate a Gibbs rule and a majority vote rule. We then evaluate the true cost and gain associated with these treatment rules (for different choices of $u$) using the test data. Once we have the true costs associated with these rules, we estimate the R-NP ratios and IC CATE scores from the training sample and implement these rules via batch implementation in the testing data. For each $u$ choice and for each PB-MV and PB-G rule, the R-NP and IC rules are implemented to stop assigning treatment when they reach the same cost as the PB-MV or PB-G rule of interest. In this way we are comparing models with the same true costs.

For each training sample, the various (approximately) true gain-cost points associated with different $u$ choices for the PB-MV and PB-G methods are plotted in gain-cost space along with the associated points for the R-NP and IC models. The gain-cost curve for the iteration is then estimated by interpolating between these points. For a single training sample iteration, this process is illustrated in Figures (ref) and (ref) for the DGP with $a=1$. Then, the gain-cost curves for all training sample iterations are averaged (vertically) to produce the final (approximately) true gain-cost curves. This procedure for the DGP with $a=1$ then produces Figure (ref). The black lines in these figures give the gain-cost pairs that would result from randomly assigning treatment in the target population until the particular cost level is achieved. The cost curves for the DGPs with $a=2$ and $a=4$ are presented in Figures (ref) and (ref), respectively.

We can now discuss the main takeaways and results from the simulation study. Figures (ref)-(ref) present the cost curves from the simulation study while Table (ref) collects select data points from these graphs for a more precise snapshot. For $a=1$, the PAC-Bayesian methods PB-G, PB-MV, and PB-B perform quite closely to the R-NP method. In this setting, the R-NP slightly outperforms the PB-G and PB-MV methods across most cost levels, with the gap in out-performance slightly increasing at greater cost levels. The PB-B models, on the other hand, perform quite similarly to the R-NP method across the cost levels in this setting, with $\pm0.01$ differences in welfare at a few cost levels.

As $a$ increases to $2$ and $4$, all of the PAC-Bayesian-based rules improve their performance relative to the R-NP approach. PB-B rules yield higher welfare gains than the R-NP rules at lower to middle cost levels while slightly lagging the welfare of the R-NP models at higher cost levels for $a=2$ and slightly out-performing them at $a=4$. The out-performance of PB-B models increases slightly at lower cost levels as $a$ increases from $2$ from $4$. For $a\in\{2,4\}$, relative to the R-NP models, the PB-MV and PB-G models now yield higher welfare gains at lower cost levels, perform similarly at middling cost levels, and are slightly beaten at the highest budgets. As the cost/budget level increases, the optimal rules in these simulation environments involve treating a higher proportion of the target population, eventually treating everyone as cost levels are allowed to rise enough. The optimization problem that the Gibbs posterior solves is penalized towards allowing a degree of randomness in the resulting Gibbs rule (see, for example, the $D_{\mathrm{KL}}(\rho,\pi)$ term in (ref)). This could help to explain why the PB-G and closely related PB-MV models lag slightly at the highest cost levels whereas the PB-B implementation that treats until the budget is met performs well at these levels.

Note that \[\delta_{y}(x) = 4 \Lambda\left ( 2 \left ( x_{1}+x_{1}x_{2}+x_{2} \right ) \right ), \ \delta_{c}(x) = 4\Lambda\left (a(3 x_{2} + 1.5 x_{3} ) \right ).\] For values of $v$ near zero, $\Lambda(v)$ is approximately linear in $v$ and so the above compositions are also approximately linear in $x_{1}, x_{1}x_{2},$ $x_{2}$ and $x_{3}$ near the origin. For values further from the origin, which are encountered with increasing probability as $a$ increases, this linear approximation worsens. When we are likely to observe combinations of $X_{1}$, $X_{2}$, $X_{1}X_{2}$ and $X_{3}$ that are further from the origin, the conditional welfare to cost ratio in the optimal rules is a more complex object in these regions that is less well approximated by individual rules in $\mathcal{F}_{\Theta}$ and has increasing variance as $a$ increases. This simulation study could suggest the PAC-Bayesian approaches may have benefits over the R-NP method when conditional expected costs are noisier.

In practice it is desirable to compare alternative methods prior to implementation. For example, via evaluation using an auxialry testing data set separate from that which the models are trained on. One drawback of the approach of sun2021treatment and other batch implementation methods is they cannot be evaluated in a traditional way using test data withheld from model estimation. For example, test sample data points that a batch implementation method may rank highly for treatment may not have received the treatment and thus we do not observe the costs accruing properly to know when a batch implementation method would stop assigning treatments. We note that sun2021treatment is a working paper and since this paper was started the authors have added material aimed at addressing this issue.

It also is important to note that there are a number of settings where the forest-based R-NP method is not viable whereas the PAC-Bayesian approaches considered here remain applicable. Batch implementations are not always viable. The cost of a treatment may not be realized until sometime after treatment assignment and one may not always have the full target group available when the rule must be set. Batch implementations, where treatment is assigned until the budget is hit, could also be unacceptable to policy makers in settings where the “budget" is something with a negative connotation like a complication rate in a medical setting.

Additionally, the R-NP rule can only be applied when $C_{0}\leq C_{1}$ a.s., which rules out certain circumstances relevant to policy makers. For example, as noted in sun2021empirical, hendren2020unified identify fourteen welfare programs out of 133 considered that are estimated to have negative or zero net cost to the government. The EWM based approach of sun2021empirical can accommodate the setting where $C_{0}> C_{1}$ with positive probability, as can the PB-G and PB-MV methods considered here. However, the approach of sun2021empirical may be difficult to implement when allowing for more flexible decision rule classes (she considers threshold rules that vary with a covariate in her application) and lacks the budget efficiency properties derived here. An additional benefit of the PAC-Bayesian approaches here is their ability to utilize estimation tools from the Bayesian literature as demonstrated in Section (ref) below. Lastly, while one could estimate $\delta_{y}(x)$ and $\delta_{c}(x)$ separately and try to build a workaround via Theorem (ref) when $C_{0}>C_{1}$ is possible, the resulting ratio estimates may have increased variance and will again require batch implementation, which adds a complication in this setting.

Implementation and Estimation via Sequential Monte Carlo

To implement treatment rules associated with $\hat{\rho}_{\lambda, u}(\theta)$, we must evaluate the treatment assignment probabilities or majority vote scores of the form

To do so, we utilize the Sequential Monte Carlo (SMC) procedure considered, for example, in del2006sequential. While a Markov Chain Monte Carlo (MCMC) approach also could be derived, recently ridgway2014pac and alquier2016properties have highlighted the usefulness of the SMC procedure in PAC-Bayesian applications. One benefit is the ability to sample from a sequence of Gibbs posterior distributions for a range of $\lambda$ values. This can ease the computational burden for cross-validation. Here we discuss key elements of the approach, provide an estimation algorithm for our setting, and discuss implementation. We also discuss the choices utilized in implementing the procedure for Section (ref).

Throughout, we make the following computational adjustment to the definition of $\hat{\rho}_{\lambda,u}$ in order to make the implementation choices for Section (ref) applicable to more general settings. We define $\hat{\rho}_{\lambda, u}$ to be the distribution over $\Theta$ with RN derivative with respect to $\pi$ given by

where \[Z(\lambda, u)=\int_{\Theta} \exp \left [ -\lambda \left ( u\overline{K}_{n}(\theta) - \overline{W}_{n}(\theta)\right ) \right ] d\pi(\theta),\] and \[\overline{W}_{n}(\theta)= \frac{W_{n}(\theta)}{\frac{1}{n}\sum_{i=1}^{n}\delta_{y,i}} \ \mathrm{and} \ \overline{K}_{n}(\theta) = \frac{K_{n}(\theta)}{\frac{1}{n}\sum_{i=1}^{n}\delta_{y,i}}. \] This adjustment is relevant when the average treatment effect is expected to be is positive. Clearly, if we denote $\hat{\delta}_{y}=n^{-1}\sum_{i=1}^{n}\delta_{y,i}$, the distribution $\hat{\rho}_{\lambda, u}$ in (ref) is equivalent to $\hat{\rho}_{(\hat{\delta}_{y}\lambda),u}$ in Definition (ref). In practice we choose $\lambda$ via cross-validation from a wide range of values.

For given choices of $\lambda>0$ and $u\geq 0$, the SMC algorithm we adopt samples from $\hat{\rho}_{\lambda, u}$ to evaluate (ref) by simulating a set of parameter draws from each of a sequence of distributions $\{\hat{\rho}_{\lambda_{t}, u} \}_{t=0}^{T}$. Here, \[ 0 =\lambda_{0} < \lambda_{1} < \cdots < \lambda_{T} = \lambda \] is an increasing temperature ladder that must be specified. Note that $\hat{\rho}_{\lambda_{0},u} = \pi$, which the user may specify and we assume can be sampled from. The temperature ladder $\{\lambda_{t}\}_{t=0}^{T}$ is intended to be such that the corresponding distributions $\hat{\rho}_{\lambda_{t}, u}$ progress gradually from $\pi$ to the target distribution $\hat{\rho}_{\lambda, u}$.

For each $t=0,\dots, T$, the SMC algorithm produces a set of $N$ weighted samples $\{\Psi_{t}^{(i)}, \theta_{t}^{(i)}\}_{i=1}^{N}$ with $\Psi_{t}^{(i)}>0$ and $\sum_{i=1}^{N} \Psi_{t}^{(i)} =1$ where $\theta_{t}^{(i)}\in\Theta$ for all $t$ and $i$ in our setting. The set of parameter draws $\{\theta_{t}^{(i)}\}_{i=1}^{N}$ are referred to as particles (there are $N$ weighted particles for each $t$). SMC combines MCMC moves with sequential importance sampling; we refer to del2006sequential for additional details and discussion. This produces weighted particles that emulate, in terms of computing expectations, samples from the distributions $\hat{\rho}_{\lambda_{t},u}$ associated with

Conditional on $\hat{\rho}_{\lambda_{T},u}$, under general conditions, for a $\hat{\rho}_{\lambda_{T},u}$-integrable function $\varphi:\Theta\rightarrow \mathbb{R}$, \[\sum_{i=1}^{N}\Psi_{T}^{(i)}\varphi\left ( \theta_{T}^{(i)} \right )\overset{a.s.}{\rightarrow } \int_{\Theta} \varphi \left (\theta \right ) d\hat{\rho}_{\lambda_{T}, u}(\theta) \ \ \mathrm{as} \ N\rightarrow\infty.\]

In our setting, we are interested in $\varphi(\theta)=f_{\theta}(x)$ to approximate (ref) via \[\sum_{i=1}^{N}\Psi_{T}^{(i)}f_{\theta_{T}^{(i)}}(x), \ \ x\in\mathcal{X}.\] Once we have run the SMC algorithm to yield $\{\Psi_{T}^{(i)}, \theta_{T}^{(i)}\}_{i=1}^{N}$ for a given pair $(\lambda, u)=(\lambda_{T}, u)$, the treatment probability or majority vote score for any value $x$ in the covariate space can be computed as above. Alternatively, for example, we may be interested in $\varphi(\theta) = K_{n}(\theta)$, to approximate $K_{n}(f_{G,\hat{\rho}_{\lambda, u}})$.

The SMC algorithm utilized to estimate the treatment rules in Section (ref) is detailed in the algorithm tables below. We set the input parameters $\tau_{\mathrm{ESS}}$ and $N$ there equal to $1/2$ and $1,000$, respectively. $\tau_{\mathrm{ESS}}$ is an Effective Sample Size threshold criterion. When the variance of the weights at a given step $t$ is too high, the SMC procedure utilizes a re-sampling step. This is referred to in Step 2 of the algorithm below. In our application we utilize systematic resampling, which is also outlined below. The choice of temperature ladder, additional algorithm details, and cross-validation points are detailed below the algorithm descriptions.

\hrulefill

\noindentTempering SMC Algorithm

\hrulefill

\noindentInput $N$ (number of particles), $\tau_{\mathrm{ESS}}\in(0,1)$ (ESS threshold), $\{\lambda_{t}\}_{t=1}^{T}$ (temperature ladder).

\noindentOutput $\{\Psi_{t}^{(i)}, \theta_{t} ^{(i)}\}_{i=1}^{N}$ for $t=0,\dots, T$.

Step 1: initialization

Iterate steps 2 and 3

Step 2: Resampling

Step 3: Sampling

\hrulefill

\hrulefill

\noindentResampling Algorithm (systematic resampling):

\hrulefill

\noindentInput A set of (normalized) weights and associated particles, $\left\{ \Psi_{t}^{(i)}, \theta_{t}^{(i)} \right\} _{i=1}^{N}$ for some $t\in\{0,\dots, T\}$.

\noindentOutput Resampled particles for equal weighting, $\left\{ \overline{\theta}_{t}^{(i)} \right\} _{i=1}^{N}$

\hrulefill

Some additional implementation details utilized in Section (ref) are as follows. For the MCMC kernel in the sampling step of the SMC algorithm, we use a Gaussian random-walk Metropolis kernel with covariance matrix proportional to the empirical covariance matrix of the current set of particles. We scale the empirical covariance of the step $t$ particles by $t^{-0.9}$. In practice, the scaling factor can be adjusted, possibly dynamically rather than with a general rule like $t^{-0.9}$, to ensure reasonable acceptance rates in the MCMC steps of the SMC algorithm.

For a temperature ladder, we set $T=800$ and utilize a piece-wise linear structure as follows. $\{\lambda_{t}\}_{t=0}^{200}$ increases from $0$ to $4/(|1+u|)$ in equally spaced steps. Then, $\{\lambda_{t}\}_{t=201}^{320}$ increases from $4/(|1+u|)$ to $32/(|1+u|)=2^5/(|1+u|)$ in equally spaced increments, $\{\lambda_{t}\}_{t=321}^{470}$ increases from $2^5/(|1+u|)$ to $2^8/(|1+u|)$ in equally spaced increments, and $\{\lambda_{t}\}_{t=471}^{800}$ increases from $2^8/(|1+u|)$ to $2^{10}/(|1+u|)$ in equally spaced increments. For $\lambda$ values of interest less than $2^{10}$, the temperature ladder is cut short (at fewer than 800 steps) to end once $\lambda_{t}$ reaches the desired value. Let $\mathcal{W}_{\lambda}$ denote the elements of $\{\lambda_{t}\}_{t=0}^{800}$ that are closest to elements in $\{ 2^{2}, (2^{2}+2^{3})/2, 2^{3}, (2^{3}+2^{4})/2,2^{4},\dots, 2^{10} \}/(|1+u|)$. Rather than considering each value in $\{\lambda_{t}\}_{t=0}^{800}$ as a potential choice for a rule, during cross-validation $\lambda$ chosen from values in $\mathcal{W}_{\lambda}$.

Empirical Illustration

Here, we illustrate the procedure for Gibbs treatment rules centered around $\hat{\rho}_{\lambda,u}$ using data from the National Job Training Partnership Act (JTPA) Study. This study has been a popular choice for illustrating individualized treatment rule estimators and is utilized, for example, in KT2018, mbakop2021model, and kitagawa2023stochastic. Detailed descriptions of the study can be found in orr1994national and bloom1997benefits.

The JTPA study was a randomized controlled trial aimed at assessing the costs and benefits of the training and employment assistance programs of the JTPA. The study randomly assigned each participant to one of two groups. In the first group (the treatment group), participants had access to JTPA services, whereas in the second group (the control group), access to JTPA services was restricted. For example, access was limited to certain services, and a period of time was imposed when a control individual would be ineligible for services. Note that the treatment was ease of access to services, rather than participation in JTPA programs or any other type of compliance. The study collected background information on participants and tracked their earnings in the 30-month period following treatment assignments.

As in KT2018, we use an individual's total earnings in the 30 months following treatment as the outcome variable of interest ($Y$). Our Gibbs treatment rules, like those proposed in the referenced above, are based on two variables that policymakers might consider in designing access policies: an individual's years of education and their earnings in the year prior to treatment assignment. JTPA personnel assessed all participants prior to treatment assignments and provided service type recommendations, which were categorized by orr1994national into three types: classroom training, on-the-job training/job search assistance, and other services. To construct our cost variable, we use averages related to these categories, as described below.

Although treatment costs varied between individuals in the study, we don't have exact costs per person. Instead, we define the cost variable $C$ as follows: if an individual received $0$ hours of JTPA services, we set their cost to $0$. Otherwise, we take their cost to be the average cost of services for individuals with the same gender, treatment assignment, and service recommendation category. These averages are reported in Exhibit 5.3 of orr1994national and were adjusted for our purposes to reflect the averages among individuals who received services, using the proportion of individuals in each subcategory who received more than $0$ hours of services. As noted in orr1994national, it is relevant that services utilized correlated with service recommendations and individuals in the control group that did access JTPA services at some point in the study tended to incur similar costs as individuals in the treatment group that received services. The probability of using any services, on the other hand, was greatly impacted by treatment assignment and is a key driver in cost differences.

Our sample consists of 7,675 adults (22 years and older) for whom data on years of education, pre-program earnings, and service hours received are available. As in KT2018, we only consider individuals from the original program evaluation and studies around it (e.g. bloom1997benefits and other references provided in KT2018). The probability of being assigned treatment is $2/3$ in this sample. To estimate potential models of interest, we utilize the SMC procedure described in Section (ref). We consider $u\in\{0.05, 0.1,\dots, 3\}$ and cross-validate $\tilde{\lambda}_{u}\in \{2, 2^{2},\dots, 2^{10}\}/(1+u)$ for each. During the cross-validation step, for each $u$ we obtain an estimated cost and welfare, namely the averages of $\hat{B}(\hat{\rho}_{\tilde{\lambda}_{u},u})$ and $W_{n}(f_{G,\hat{\rho}_{\tilde{\lambda},u}})$ across hold out folds. Note we are abusing notation here because, during cross-validation, objects involving $\hat{\rho}_{\tilde{\lambda},u}$ are calculated from the k-fold training sample rather than the entire sample while the cost and welfare estimates are averages of objects calculated using hold out samples.

We use 2-fold cross-validation because the 30-month post-treatment earnings data is highly variable, and there is a potential to overfit noise in smaller cross-validation samples. We take $\mathcal{F}_{\Theta}$ to be the family of rules described in (ref) and (ref), where the transformations $\phi_{j}(x)$ are the monomials used in the construction of polynomial transformations on $\mathbb{R}^{2}$ of order at most 3. As in the simulation section, we normalize the monomial transformations by subtracting their sample means and scaling by the sample standard deviations since there is a considerable degree of variation in scale among the transformations, with education taking values from 7 to 18 years and pre-program earnings ranging from \$$0$ to \$$63{,}000$.

The cross-validation-based estimates of the welfare and cost pairs for different values of $u$ are plotted below in Figure (ref). We dropped points corresponding to models with dominated welfare-cost pairs, i.e., points where there existed an alternative model for a different choice of $u$ with a higher estimated welfare for the same or lower estimated cost, and these are not displayed. Following an approach where we consider multiple values of $u$ and examine feasible budget estimates of the policies, we can see that there are models with average costs per person ranging from roughly \$$100$ to about \$$650$. That is, we estimate that when these treatment rules are applied to a wider population similar to the sample, we can achieve average costs per person within these ranges.

We examine three of the estimated models corresponding to the circled points in Figure (ref) in greater detail. Starting from the left, the first circle corresponds to the model with an estimated cost closest to \$$200$ and with $u=2.45$. We refer to this model as the ``low-budget model." The second circled point corresponds to the model with an estimated cost nearest to \$$400$, with $u=2.1$, and we call this model the ``medium-budget model." The right circle, which we refer to as the "no budget model," has the highest estimated welfare and corresponds to $u=0.15$. Figure (ref) presents treatment probabilities for different values of education and pre-program earnings associated with the high, medium, and no budget models. The population densities linked to the covariate space for these models are shown in Figure (ref).

We observe that treatment probabilities transition fairly smoothly across the covariate space in all three models but less so in the no budget model. Treatment assignment probabilities are not uniform across the covariate space in any of the estimated models. Furthermore, as we consider models with lower costs, we do not simply obtain uniform reductions in treatment probabilities associated with higher-cost models. In the no budget model, treatment probabilities are either $1$ or $0$ for sizable portions of the covariate space. The no-budget model treats $81\%$ of individuals in the sample on average. The medium-budget model treats $49\%$ of individuals on average, and the treatment probabilities among individuals in the sample range from $46\%$ to $51\%$. The low-budget model treats $20\%$ of individuals on average, and treatment probabilities among covariate pairs encountered in the sample range from $4\%$ to $66\%$.

One common feature among most of the (non-stochastic) treatment rules estimated in KT2018 is the avoidance of treating individuals with the highest levels of education. The most comparable model to those considered here, the no budget model, differs from these rules in that it treats individuals with higher levels of education above a certain income level and randomizes treatment in regions of the covariate space with lower education. It also avoids treating individuals with middling pre-program earnings and low education, although these individuals are relatively less common. As we move to models with lower costs, the medium-budget model becomes more uniform in its treatment probabilities than the other Gibbs rules. It also features increased treatment probabilities among lower and higher education levels compared to the other models, particularly at lower income levels. The low-budget model reduces cost by lowering treatment probabilities among individuals with lower to middle education levels, especially at the most commonly encountered non-zero education levels.

Conclusion

In this paper, we proposed a new approach to estimating treatment rules in a budget constrained setting. Utilizing the PAC-Bayesian framework, theoretical properties of interest were derived, including generalization bounds and oracle-type inequalities demonstrating a type of budget efficiency for a proposed class of stochastic treatment rules. The treatment rule estimators can accommodate a variety of budget constraints of interest including settings with uncertain and or heterogeneous costs, quantity constraints, and settings where costs are not realized at the time of treatment. Another benefit is that the proposed rules can take advantage of well developed Bayesian estimation machinery. Lastly, the models were shown to be competitive against state-of-the-art alternatives in a simulation study and an empirical illustration was examined.

There are a number of considerations for future work. It would be of interest to determine if different prior choices, for example a sparsity-inducing prior or a normal prior with a different form for the covariance matrix than that considered here, would facilitate bounds of the type in Section (ref) or yield modeling suggestions for higher dimensional feature spaces. Rather than using the Gibbs posterior to form treatment rules, it could also prove fruitful to approximate the Gibbs posterior with alternative distribution such as a normal distribution. So-called variational approximations of Gibbs posteriors for general PAC-Bayesian approaches are considered in alquier2016properties. This could yield greater flexibility in terms of functional form constraints, beyond control over the variables included in the treatment rules featured here. It would also be of interest to incorporate estimated propensity scores into the PAC-Bayesian framework here and to explore how this impacts rates of convergence. Lastly, the analysis for balancing the primary welfare or regret objective against that of a secondary cost objective can be generalized to settings beyond the welfare-based potential outcomes framework. Balancing a secondary objective of concern could also be of interest in classification or regression settings.

\setcounter{section}{0}