Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
68,694 characters · 10 sections · 57 citation commands
Model Selection for Treatment Choice: Penalized Welfare Maximization
KEYWORDS: Treatment Choice, Minimax-Regret, Statistical Learning \\ JEL classification codes: C01, C14, C44, C52
\footnotetext[0]{(continued from previous page), NASMES 2017, and the Bristol Econometrics Study Group for helpful comments, as well as Nitish Keskar for help in implementing EWM. This research was supported in part through the computational resources and staff contributions provided for the Social Sciences Computing Cluster (SSCC), and the Quest high performance computing facility at Northwestern University. All mistakes are our own.}
This paper develops a new statistical decision rule for the treatment assignment problem. A major goal of treatment evaluation is to provide policy makers with guidance on how to assign individuals to treatment, given experimental or quasi-experimental data. Following the literature inspired by manski2004 dehejia2005, schlag2007, hirano2009, stoye2009, chamberlain2011, bhat2012, tetenov2012, stoye2012, athey2017, kt2015, armstrong2015, kock2017, rai2018, viviano2019, we treat the treatment assignment problem as a statistical decision problem of maximizing population welfare. Like many of the above papers, we evaluate our decision rule by its maximum regret.
The rule we develop, the Penalized Welfare Maximization (PWM) rule, is designed to address situations in which the policy maker can choose amongst a collection of constrained classes of allocations. To be concrete, suppose we have two treatments, and we represent assignment into these treatments by partitioning the covariate space into two pieces. We can then think of constraints on assignment as constraints on the allowable subsets that we can consider for the partitions. For example, policy makers may face exogenous constraints on how they can use covariates for legal, ethical, or political reasons. Even in cases where policy makers have leeway in how they assign treatment, plausible modeling assumptions may imply certain restrictions on assignment. kt2015 develop what they call the Empirical Welfare Maximization (or EWM) rule, whose primary feature is its ability to solve the treatment choice problem when certain exogenous constraints are placed on assignment. kt2015 focus on deriving bounds on maximum regret of the EWM rule for a fixed class of subsets of finite VC dimension devroye1996. In this paper, however, we consider settings where the class of allowable subsets is “large". We approach the problem by approximating our class of allowable allocations by a sequence of subclasses of finite VC dimension. We establish an oracle inequality for the regret of the PWM rule which shows that it behaves as if we knew the “correct" class to use in the sequence. We then use this result to derive bounds on the maximum regret of the PWM rule in two empirically relevant settings.
The main setting that we consider is one where the class of feasible allocations has infinite VC dimension. In particular, we argue that economic modeling assumptions may sometimes put restrictions on the unconstrained optimum that naturally generate classes of infinite VC dimension. For example, plausible assumptions may only impose shape restrictions on the optimal allocation. To solve the optimal welfare assignment problem in this setting, we approximate these large classes of feasible allocations by sequences of classes of finite VC dimension. The strength of the PWM rule in this setting will then be to provide a data-driven method by which to select an “appropriate" approximating class. In doing so we will derive bounds on the maximum regret of the PWM rule for a large set of classes of infinite VC dimension.
We also consider the setting where the class of feasible allocations may have large VC dimension relative to the sample size. This could arise, for example, if the planner has many covariates on which to base assignment. As is shown in kt2015, when the constraints placed on assignment are too flexible relative to the sample size available, the EWM rule may suffer from overfitting, which can result in inflated values of regret. By the same mechanism that allows PWM to select an appropriate approximating class in our first application, we can use PWM in order to select amongst simpler subclasses in this setting as well, in a way that improves the performance of the allocation rule in finite samples.
The PWM rule is heavily inspired by the literature on model selection in classification: see for example the seminal work of vapnik1974, as well as devroye1996, kolt2001, bartlett2002, boucheron2005, scott2006, bartlett2008, kolt2008 among many others. The theoretical contribution of our paper is to modify and extend some of these tools to the setting of treatment choice. In deciding which tools to extend, we have attempted to strike a balance between ease of use for practitioners, theoretical appeal, and performance in simulations. An important consequence of our results is that we are able to formalize model-selection using a “hold-out" procedure, where the policy maker would first estimate various policies using half of the data, and then select the policy which performs the best when evaluated on the other half of the data. The connection between classification and treatment choice has been explored in various fields, including machine learning, under the label of policy learning zadrozny2003, beygelzimer2009, swaminathan2015, kallus2016, and in epidemiology under the label of individualized treatment rules qian2011, zhao2012. kt2015 and athey2017 provide a discussion on the link between these various literatures.
The remainder of the paper is organized as follows. In Section (ref), we set up the notation and formally define the problem that the policy maker (i.e. social planner) is attempting to solve. In Section (ref), we introduce the PWM rule, present general results about its maximum regret, and explain how our results allow us to study the properties of the “hold-out" model selection procedure. In Section (ref) we derive bounds on maximum regret of the PWM rule when the planner is constrained to what we call monotone allocations, and then apply PWM in an application using data from the Job Training Partnership Act (JTPA) study.
Let $Y_i$ denote the observed outcome of a unit $i$, and let $D_i$ be a binary variable which denotes the treatment received by unit $i$. Let $Y_i(1)$ denote the potential outcome of unit $i$ under treatment $1$ (which we will refer to as “the treatment”), and let $Y_i(0)$ denote the potential outcome of unit $i$ under treatment $0$ (which we will refer to as “the control"). The observed outcome for each unit is related to their potential outcomes through the expression:
Let $X_i\in \mathcal{X}\subset \mathbb{R}^{d_x}$ denote a vector of observed covariates for unit $i$. Let $Q$ denote the distribution of $(Y_i(0),Y_i(1),D_i,X_i)$, then we assume that the planner observes a size $n$ random sample $$(Y_i, D_i, X_i)_{i=1}^n\sim P^n~,$$ where $P$ is jointly determined by $Q$, and the expression in ((ref)). Throughout the paper we will assume unconfoundedness, i.e.
This assumption asserts that, once we condition on the observable covariates, the treatment is exogenous. This assumption will hold in a randomized controlled trial (RCT), which is our primary application of interest, since the treatment is exogenous by construction.
The planner's goal is to optimally assign the treatment to the population. The objective function we consider is utilitarian welfare, which is defined by the average of the individual outcomes in the population: $$E_Q[Y(1) {\bf 1}\{X \in G\} + Y(0) {\bf 1}\{X \notin G\}]~,$$ where $G\subset \mathcal{X}$ represents the set of covariate values of the individuals assigned to treatment. The planner is tasked with choosing a treatment allocation $G \subset \mathcal{X}$ using the empirical data. Using Assumption (ref), we can rewrite the welfare criterion as: $$E_Q[Y(0)] + E_P\Big[\Big(\frac{YD}{e(X)} - \frac{Y(1-D)}{1-e(X)}\Big){\bf 1}\{X \in G\}\Big]~,$$ where $e(X)=E_P[D|X]$ is the propensity score. Since the first term of this expression does not depend on $G$, we define the planner's objective function given a choice of treatment allocation $G$ as: $$W(G) := E_P\Big[\Big(\frac{YD}{e(X)} - \frac{Y(1-D)}{1-e(X)}\Big){\bf 1}\{X \in G\}\Big]~.$$
Let $\mathcal{G}$ be the class of all feasible treatment allocations. Here, we consider the possibility that the planner may be restricted in what type of allocations she can (or wants to) consider. These restrictions may arise from legal, ethical, or political considerations, or could arise as natural constraints from an economic model. Consider the following three examples of $\mathcal{G}$:
Given a feasible class $\mathcal{G}$, we denote the highest attainable welfare by: $$W^*_\mathcal{G} := \sup_{G \in \mathcal{G}} W(G)~.$$ A decision rule is a function $\hat{G}$ from the observed data $\{(Y_i,D_i,X_i)\}_{i=1}^n$ into the set of admissible allocations $\mathcal{G}$. We call the rule that we develop and study in this paper the Penalized Welfare Maximization (or PWM) rule. As in much of the literature that follows the work of manski2004, we assume that the planner is interested in rules $\hat{G}$ that, on average, are close to the highest attainable welfare. To that end, the criterion by which we evaluate a decision rule is given by what we call maximum $\mathcal{G}$-regret: $$\sup_P E_{P^n}[W^*_\mathcal{G} - W(\hat{G})]~.$$
In this section, we present the main results of our paper. In Section (ref), we review some properties of the empirical welfare maximization (EWM) rule of kt2015, which will motivate the PWM rule and serve as an important building block in its construction. In Section (ref), we define the penalized welfare maximization rule and present bounds on its maximum $\mathcal{G}$-regret for general penalties. In Section (ref) we illustrate these results by applying them to some specific penalties, and in particular we show that a standard “hold-out" procedure can be formalized as a penalty which satisfies our assumptions. In Section (ref) we present results for a modification of the PWM rule for quasi-experimental settings where the propensity score is not known and must be estimated.
The EWM rule solves a sample analog of the population welfare maximization problem: $$\hat{G}_{EWM} \in \arg\max_{G \in \mathcal{G}} W_n(G)~,$$ where
kt2015 show how to formulate this problem as a Mixed Integer Linear Program (MILP) for many classes $\mathcal{G}$ of practical interest (see Appendix C for examples). Alternatively, direct parameter search has been shown to be very effective at solving the welfare maximization problem in certain applications as well: see for example zhou2018. Note that to solve this optimization problem, the planner must know the propensity score $e(\cdot)$. This assumption is reasonable if the data comes from a randomized experiment, but clearly could not be made in a setting where the planner is using observational data. kt2015 derive results for a modified version of the EWM rule where the propensity score is estimated, which we will review in Section (ref).
To derive their non-asymptotic bounds on the maximum $\mathcal{G}$-regret of the EWM rule, kt2015 make the following assumptions, which we will also maintain in our results:
In order to derive their results, kt2015 also make the following assumption, which we will not require:
Such an assumption may or may not be restrictive depending on the application in question. Consider Example (ref), the class of threshold allocations on $\mathbb{R}$. This class has VC dimension 2, thus Assumption (ref) holds. On the other hand, it can be shown that the class of monotone allocations on $[0,1]^2$ that was introduced in Example (ref) has infinite VC dimension devroye1996.
Given Assumptions (ref) and (ref), kt2015 derive the following non-asymptotic upper bound on the maximum $\mathcal{G}$-regret of the EWM rule:
for some universal constant $C$. Moreover, when $X$ has sufficiently “large" support, they derive the following lower bound: for any decision rule $\hat{G}$,
for $R$ a universal constant and for all sufficiently large $n$. This shows that the rate of convergence of maximum $\mathcal{G}$-regret implied by ((ref)) is the best possible, i.e. that no other decision rule could achieve a faster rate without imposing additional assumptions.
We now consider a setting where the class $\mathcal{G}$ of admissible rules is “large", but can be “approximated" by a sequence of less complex subclasses $\mathcal{G}_k$:\footnotemark[1] $$\mathcal{G}_1 \subseteq \mathcal{G}_2 \subseteq \mathcal{G}_3\subseteq \cdots \subseteq \mathcal{G}_k\subseteq \cdots \subseteq \mathcal{G}~.$$ \footnotetext[1]{As can be seen from the proofs, the results we present below remain valid even if the sequence $\{\mathcal{G}_k\}_k$ is not nested.} Let $\hat{G}_{n,k}$ be the EWM rule in the class $\mathcal{G}_k$. Then we can decompose the $\mathcal{G}$-regret of the rule $\hat{G}_{n,k}$ as follows: $$E_{P^n}[W^*_{\mathcal{G}} - W(\hat{G}_{n,k})] = E_{P^n}[W^*_{\mathcal{G}_{k}} - W(\hat{G}_{n,k})] + W^*_{\mathcal{G}} - W^*_{\mathcal{G}_{k}}~.$$ Given this decomposition, we call $$E_{P^n}[W^*_{\mathcal{G}_{k}} - W(\hat{G}_{n,k})]~,$$ the estimation error of the rule $\hat{G}_{n,k}$ in the class $\mathcal{G}_k$, and we call $$W^*_{\mathcal{G}} - W^*_{\mathcal{G}_{k}}~,$$ the approximation error (or bias) of the class $\mathcal{G}_k$. Note that since the classes $\{\mathcal{G}_k\}_k$ are nested, the estimation error (respectively approximation bias) is non-decreasing (resp. non-increasing) with respect to $k$. If one had sharp uniform bounds on these errors, then an appropriate choice of $k$ would be one that minimizes the sum of these bounds. In Theorem (ref), we derive an oracle inequality which shows that PWM selects such a $k$, in a data-driven fashion. We use this feature of PWM to derive bounds on maximum regret in two settings of empirical interest.
The first setting we consider is one where $\mathcal{G}$ has infinite VC dimension (see Examples (ref) and (ref)). In this setting, performing EWM on the whole class $\mathcal{G}$ may be undesirable. For example, regret may not converge to zero, or may converge to zero at a suboptimal rate birge1993, or it may simply be the case that maximization over $\mathcal{G}$ is computationally difficult. Instead, we apply EWM to an approximating class $\mathcal{G}_k$, and we allow the complexity of the approximating class to grow as the sample size increases. We present examples of relevant approximating classes in Examples (ref) and (ref) below. In Corollary (ref) we establish a bound on maximum regret in this setting.
The second setting that we consider is one where the class $\mathcal{G}$ has finite but large VC dimension relative to the sample size. This situation can arise, for instance, in applications where the planner has a large set of covariates on which to base treatment, and where the feasible allocations are threshold allocations (see Example (ref) below). The bound on regret given by ((ref)) increases with the VC dimension $V$ of $\mathcal{G}$, so that EWM tends to “overfit"' the data when $V$ is large relative to the sample size. In this situation, it may be beneficial to perform EWM in a subclass $\mathcal{G}'$ of smaller VC dimension, and hence we face the same tradeoff between estimation and approximation error that was noted above. In Corollary (ref) we specialize Theorem (ref) to a finite collection of approximating classes, and then in Corollary (ref) establish a bound for the PWM rule which shows that it behaves as if we knew the correct class $\mathcal{G'}$ to use ex-ante, in the special case where the optimal allocation in $\mathcal{G}$ is contained in $\mathcal{G}'$.
We impose the following assumption on our sequence of classes, which we call a sieve of $\mathcal{G}$:
\footnotetext[2]{kt2015 additionally assume that their class $\mathcal{G}$ is countable so as to avoid potential measurability concerns. We instead choose not to address these concerns explicitly, as is done in most of the literature on classification. See van1996 for a discussion of possible resolutions to this issue.}
We present three examples of sieves $\mathcal{G}_k$ in Examples (ref), (ref), (ref) below. Given a sieve $\{\mathcal{G}_k\}_{k}$, let $$\hat{G}_{n,k} := \arg\max_{G \in \mathcal{G}_k} W_n(G)~,$$ be the EWM rule in the class $\mathcal{G}_k$. Our goal is to select the appropriate class $k^*$ in which to perform EWM. We do this by selecting the class $k^*$ in the following way: for each class $\mathcal{G}_k$, suppose we had some (potentially data-dependent) measure $C_n(k)$ of the amount of “overfitting" that results from using the rule $\hat{G}_{n,k}$ (Assumption (ref) specifies our precise conditions on $C_n(k)$). Given such a measure $C_n(k)$, let $\{t_k\}_{k=1}^\infty$ be an increasing sequence of real numbers, and define the following penalized objective function:
Then the penalized welfare maximization rule $\hat{G}_n$ is defined as follows: $$\hat{G}_n := \hat{G}_{n,\hat{k}^*}~,$$ where $$\hat{k}^* := \arg\max_k R_{n,k}(\hat{G}_{n,k})~.$$ In words, the PWM rule selects an allocation which maximizes a penalized version of the empirical welfare, with the penalty for allocations in $\mathcal{G}_k$ given by the term $C_n(k)$ (plus the auxiliary term $\sqrt{t_k/n}$).
We present three examples of sieves $\{\mathcal{G}_k\}_k$:
We are now prepared to state the main results of the paper. We require the following high-level condition on the penalty $C_n(k)$:
Let us provide some intuition for this assumption. Given an EWM rule $\hat{G}_{n,k}$, the value of the empirical welfare is given by $W_n(\hat{G}_{n,k})$. To evaluate $\mathcal{G}$-regret, we would ideally like to know the value of population welfare $W(\hat{G}_{n,k})$. Although the latter quantity is unknown, if we could define the (infeasible) penalty $C_n(k)$ as $W_n(\hat{G}_{n,k}) - W(\hat{G}_{n,k})$, then the penalized objective $W_n(\hat{G}_{n,k}) - C_n(k)$ would be exactly equal to $W(\hat{G}_{n,k})$. Since implementing such a $C_n(k)$ is impossible, our assumption requires that our feasible penalty be a good (empirical) upper bound on $W_n(\hat{G}_{n,k}) - W(\hat{G}_{n,k})$. In Section (ref), we provide some specific examples of penalties that satisfy this assumption. In particular, we show that a standard “hold-out" procedure can be formalized as such a penalty. We are now ready to state our main workhorse result: an oracle inequality that characterizes the $\mathcal{G}$-regret of the PWM rule.
Theorem (ref) forms the basis of all the results we present in Sections (ref) and (ref). It says that, at least from the perspective of pointwise (as opposed to maximum) $\mathcal{G}$-regret, the PWM rule is able to balance the tradeoff between $E_{P^n}[C_n(k)]$ and the approximation error, at the cost of adding two additional terms that are $O(1/\sqrt{n})$. The relative importance of these terms is hard to quantify at this level of generality, and we will attempt to shed some light on them, for specific penalties, in Section (ref). Note that this result does not quite accomplish our initial goal of balancing the estimation and approximation error along our sieve: it is possible to choose a $C_n(k)$ that satisfies Assumption (ref) for which $E_{P^n}[C_n(k)]$ is too large a bound for the estimation error. For this reason, we also impose the requirement that any penalty we consider should have the following additional property:
This assumption ensures that $E_{P^n}[C_n(k)]$ is comparable to the estimation error for EWM derived in ((ref)), which was shown to be rate-optimal (for the class $\mathcal{P}(M,\kappa)$) in ((ref)).
The next result we present is a bound on maximum regret for our first setting of interest: choosing the appropriate approximating class when $\mathcal{G}$ has infinite VC dimension. As discussed in Remark (ref), a bound on maximum regret may not exist unless we impose additional regularity conditions on the family of DGPs under consideration. Hence we make the additional assumption that we restrict ourselves to a set of distributions $\mathcal{P}_r$ for which there exists a uniform bound on the approximation error. Note however that we do not assume that the rate of decay of the approximation bias is necessarily known to the econometrician, thus illustrating the “oracle" nature of our results.
The first assumption asserts that we have a uniform bound on the approximation error. We present an example of such a uniform bound for our application in Section (ref). The second assumption is made to highlight the following possibility: although Assumption (ref) guarantees that we can satisfy this restriction with $\zeta(k,n) = \sqrt{V_k/n}$, it is possible that, once we have imposed that $P$ must lie in $\mathcal{P}_r$, an even tighter bound may exist on $C_n(k)$ (see for example the discussion which follows Corollary (ref) below). We emphasize that PWM will balance the tradeoff between the estimation and approximation error according to the tighest possible bounds on $E_P[C_n(k)]$ and $W^*_{\mathcal{G}} - W^*_{\mathcal{G}_{k}}$, regardless of whether or not we know these bounds in a given application.
Given Assumption (ref), we immediately obtain our first corollary:
As mentioned in Remark (ref), if $\{\zeta(k,n)\}_{k,n}$ and $\{\gamma_k\}_k$ were known, then we could achieve such a result with a deterministic sequence $k(n)$. The strength of the PWM rule then is that we achieve the same behavior for any class $\mathcal{G}$ and approximating sequence $\{\mathcal{G}_k\}_k$ without having to know these quantities in practice. We present an application of this result in Section (ref), in the setting of Example (ref).
The second Corollary we present specializes Theorem (ref) to our second setting of interest: the appropriate selection of a subclass when the VC-dimension of $\mathcal{G}$ is finite and large relative to the sample size. The result highlights two important points. First, it shows that by balancing the trade-off between the approximation and estimation error, PWM can potentially lead to a reduction in regret (relative to EWM) for values of the sample size that are comparable in magnitude to the VC-dimension of $\mathcal{G}$. Second, it illustrates how our bound changes when the sieve is finite and we drop the auxiliary $\sqrt{k/n}$ component of our penalty.
Note that if the above bound is minimized at $k = K$, then the approximation error $W^*_{\mathcal{G}} - W^*_{\mathcal{G}_{k}}$ is zero and the resulting bound is comparable to the one derived in ((ref)), with one additional term. In Section (ref) we argue that for specific choices of $C_n(k)$ this term can be quantified more precisely.
Our final corollary of Section (ref) considers the particular setting in which the constrained optimum $W^*_\mathcal{G}$ over the class $\mathcal{G}$ is achieved in $\mathcal{G}_{k_0}$, for some $k_0$, but that this class is unknown to the econometrician. The result shows that the resulting upper bound on maximum regret for PWM is as if we had performed EWM in the appropriate class $\mathcal{G}_{k_0}$.
This section illustrates the results of Section (ref) with two concrete choices for the penalty $C_n(k)$, and quantifies the size of the auxiliary term in the bound of Theorem (ref) for these penalties. The first penalty we present, the holdout penalty, formalizes a sample-splitting procedure. The second penalty, the Rademacher penalty, does not involve sample-splitting but could be computationally burdensome in practice. Both of the penalties share the property that they do not require that the practitioner have precise bounds on the VC dimensions $V_k$ of the approximating classes (only that they are finite), which we feel is important to make the method broadly applicable.
The first penalty we introduce is motivated by the following idea: fix some number $\ell \in (0,1)$ such that $m := n(1-\ell)$ (for expositional simplicity suppose that $m$ is an integer), and let $r := n - m$. Given our original sample $S_n = \{(Y_i,D_i,X_i)\}_{i=1}^n$, let $S_n^E := \{(Y_i,D_i,X_i)\}_{i=1}^m$ denote what we call the estimating sample, and let $S_n^T := \{(Y_i,D_i,X_i)\}_{i=m+1}^n$ denote the testing sample. Now, using $S_n^E$, compute $\hat{G}_{m,k}$ for each $k$. Intuitively, we could get a sense of the efficacy of $\hat{G}_{m,k}$ by applying this rule to the subsample $S_n^T$ and computing the empirical welfare $W_{r}(\hat{G}_{m,k})$. We could then select the class $k$ that results in the highest empirical welfare $W_{r}(\hat{G}_{m,k})$.
This idea can be formalized in our framework by treating it as a PWM-rule on the estimating sample, with the following penalty: for each EWM rule $\hat{G}_{m,k}$ estimated on $S_n^E$, let $$W_m(\hat{G}_{m,k}) = \frac{1}{m}\sum_{i=1}^m\tau_i {\bf 1}\{X_i \in \hat{G}_{m,k}\}~,$$ be the empirical welfare of the rule $\hat{G}_{m,k}$ on $S_n^E$ and let $$W_r(\hat{G}_{m,k}) = \frac{1}{r}\sum_{i=m+1}^n\tau_i {\bf 1}\{X_i \in \hat{G}_{m,k}\}~,$$ be the empirical welfare of the rule $\hat{G}_{m,k}$ on $S_n^T$. We define the holdout penalty to be $$C_m(k) := W_m(\hat{G}_{m,k}) - W_r(\hat{G}_{m,k})~.$$
Now, recall that the PWM rule is given by $$\hat{G}_m = \arg\max_k \left[W_m(\hat{G}_{m,k}) - C_m(k) - \sqrt{\frac{k}{m}}\right]~,$$ which, given the definition of $C_m(k)$, simplifies to $$\hat{G}_m = \arg\max_k \left[W_r(\hat{G}_{m,k}) - \sqrt{\frac{k}{m}}\right]~.$$ Hence we see that the PWM rule with the holdout penalty reproduces the intuition presented above (with the usual addition of the $\sqrt{k/m}$ term; see Remark (ref)).
We check the conditions of Assumptions (ref) and (ref):
With Lemma (ref) established, Theorem (ref) becomes:
As we show in the next section, the bound in Proposition (ref) is similar to what we derive for the Rademacher penalty, but with larger constants which reflect the fact that we split the sample. However, a major benefit of the holdout penalty lies in the fact that it is simple to implement. The only remaining issue is how to split the data. Although we do not study this problem formally, we have found that it is more important to focus on accurate estimation of the rule $\hat{G}_{m,k}$ than on the computation of $W_r(\hat{G}_{m,k})$. In other words, we recommend that the estimating sample $S_n^E$ be a large proportion of the original sample $S_n$. Throughout the rest of the paper we designate three quarters of the sample as the estimating sample.
The second penalty we present is attractive in that it does not introduce sample splitting, but may be computationally burdensome when compared to the holdout procedure. Let $S_n := \{(Y_i,D_i,X_i)\}_{i=1}^n$ be the observed data. Then the Rademacher penalty is given by $$C_n(k) = E_{\sigma}\Big[\sup_{G \in \mathcal{G}_k} \frac{2}{n}\sum_{i=1}^n \sigma_i \tau_i {\bf 1}\{X_i \in G\}\mid S_n\Big]~,$$ where $\tau_i$ is defined as in equation ((ref)), and $\{\sigma_1,...,\sigma_n\}$ are a sequence of i.i.d Rademacher variables, i.e. they take on the values $\{-1,1\}$, each with probability half.
To clarify the origin of this penalty, recall that $C_n(k)$ must be a good upper bound on $W_n(\hat{G}_{n,k}) - W(\hat{G}_{n,k})$, which is the requirement of Assumption (ref). Bounding such quantities is common in the study of empirical processes, and the usual first step is to use what is known as symmetrization, which gives the following bound: $$E_{P^n}[\sup_{G\in\mathcal{G}} W_n(G) - W(G)] \le E_{P^n}\Big[E_{\sigma}\big[\sup_{G\in\mathcal{G}}\frac{2}{n}\sum_{i=1}^n \sigma_i \tau_i {\bf 1}\{X_i \in G\}\mid S_n\big]\Big]~.$$ It is thus this inequality that inspires the definition of $C_n(k)$. The concept of Rademacher complexity\footnotemark[4] is pervasive throughout the statistical learning literature kolt2001, bartlett2002rad, bartlett2002. Intuitively, it measures a notion of complexity that is finer than that of VC dimension, and is at the same time computable from the data at hand.
\footnotetext[4]{Note that the definition of Rademacher complexity is slightly different than the definition of our penalty. Here we follow bartlett2002 and do not include the absolute value in our definition of the penalty.}
First we prove that the conditions of Assumptions (ref) and (ref) hold for the Rademacher penalty:
We are thus able to refine Theorem (ref) to the case of the Rademacher penalty.
In this section we present a modification of the PWM rule where the propensity score is not known and must be estimated from the data. This situation would arise if the planner had access to observational data instead of data from a randomized experiment. Before describing our modification of the PWM rule, we first review results about the corresponding modification of the EWM rule. The modification we consider here is what kt2015 call the e-hybrid EWM rule. Recall the EWM objective function as defined in equation ((ref)). To define the e-hybrid EWM rule we modify this objective function by replacing $\tau_i$ with $$\hat{\tau}_i := \Big[\frac{Y_iD_i}{\hat{e}(X_i)} - \frac{Y_i(1-D_i)}{1-\hat{e}(X_i)}\Big]{\bf 1}\{\epsilon_n\le\hat{e}(X_i)\le1-\epsilon_n\}~,$$ where $\hat{e}(\cdot)$ is an estimator of the propensity score, and $\epsilon_n$ is a trimming parameter such that $\epsilon_n = O(n^{-\alpha})$ for some $\alpha > 0$. The e-hybrid EWM objective function is defined as follows: $$W^e_n(G):=\frac{1}{n}\sum_{i=1}^n\hat{\tau}_i{\bf 1}\{X_i \in G\}~.$$
Since we are now estimating the propensity score, we must impose additional regularity conditions on $P$ to guarantee a uniform rate of convergence. We impose the following high level assumption:
Although we do not explore low-level conditions that satisfy this assumption here, kt2015 do so in their paper. Let $\hat{G}_{e-hybrid}$ be the solution to the e-hybrid problem in a class $\mathcal{G}$ of finite VC dimension, then kt2015 derive the following bound on maximum $\mathcal{G}$-regret:
\[\sup_{P \in \mathcal{P}_e \cap \mathcal{P}(M,\kappa)} E_{P^n}\Big[W^*_{\mathcal{G}} - W(\hat{G}_{e-hybrid})\Big] \le O(\phi_n^{-1} \vee n^{-1/2})~.\] With a non-parametric estimator of $e(\cdot)$, $\phi_n$ will generally be slower than $\sqrt{n}$ and hence determine the rate of convergence. In a recent paper, athey2017 argue that more sophisticated estimators of the welfare objective can improve performance relative to the e-hybrid rule, and derive corresponding bounds on the maximum regret of their procedure. Importantly, by exploiting an orthogonal moments construction, the procedure in athey2017 converges at a $\sqrt{n}$-rate even when the propensity score is estimated non-parametrically. Modifying our method using their techniques would be an interesting direction for future work.
We now present the construction of the corresponding e-hybrid PWM estimator. Let $\mathcal{G}$ be an arbitrary class of allocations, and let $\{\mathcal{G}_k\}_k$ be some approximating sequence for $\mathcal{G}$. Let $\hat{G}^e_{n,k}$ be the hybrid EWM rule in the class $\mathcal{G}_k$. Let $C^e_n(k)$ be our penalty for the hybrid PWM rule. We require that the penalty satisfies the following properties:
Note that we have introduced an object $\tilde{C}_n(k)$ which we call an infeasible penalty. The first bullet point asserts that the infeasible penalty obeys a similar tail inequality to $C_n(k)$, except that $\tilde{C}_n(k)$ satisfies this assumption with respect to the e-hybrid EWM rule. However, we evaluate the hybrid rule through the empirical objective $W_n(\cdot)$, which is the objective when the propensity score is known. This is our motivation for calling $\tilde{C}_n(k)$ an infeasible penalty. Luckily, $\tilde{C}_n(k)$ is purely a theoretical device and does not serve a role in the actual implementation of PWM. We provide an example of such an infeasible penalty in the setting of the holdout penalty below. The second bullet point is the same as Assumption (ref), but now with respect to the infeasible penalty $\tilde{C}_n(k)$. The third bullet simply links the true penalty $C_n^e(k)$ to the infeasible penalty $\tilde{C}_n(k)$ in such a way that both should agree asymptotically and do so at an appropriate rate.
Given this, we obtain the following analogue to Theorem (ref):
As we can see, the only difference between this bound and the bound derived in Theorem (ref) is that there is an additional term of order $\phi^{-1}_n$.
Next, we check that the conditions in Assumption (ref) are satisfied with a modified version of the holdout penalty (the results for the Rademacher penalty follow similarly). To define the hybrid holdout penalty, let $\hat{e}^E(\cdot)$ be the propensity estimated on $S_n^E$, and let $\hat{e}^T(\cdot)$ be the propensity estimated on $S_n^T$. Define $$W_m^e(G) := \frac{1}{m}\sum_{i=1}^m\hat{\tau_i}^E{\bf 1}\{X_i \in G\}~,$$ where $$\hat{\tau_i}^E = \Big[\frac{Y_iD_i}{\hat{e}^E(X_i)} - \frac{Y_i(1-D_i)}{1-\hat{e}^E(X_i)}\Big]{\bf 1}\{\epsilon_n\le\hat{e}^E(X_i)\le1-\epsilon_n\}~.$$ Define $W_r^e(G)$ on the testing sample analogously. Letting $\hat{G}^e_{m,k}$ be the hybrid EWM rule computed on the estimating sample in the class $\mathcal{G}_k$, the hybrid holdout penalty is defined as: $$C_m^e(k) := W_m^e(\hat{G}^e_{m,k}) - W_r^e(\hat{G}^e_{m,k})~.$$
We must also assert the existence of an infeasible penalty $\tilde{C}_m(k)$ that satisfies our assumptions. The infeasible penalty we consider is given by $$\tilde{C}_m(k) := W_m(\hat{G}^e_{m,k}) - W_r(\hat{G}^e_{m,k})~,$$ where $W_m(\cdot)$ and $W_r(\cdot)$ are defined as in Section (ref), that is, they are computed as if the propensity score were known. Lemma (ref) verifies Assumption (ref) for the hybrid holdout penalty:
We thus obtain an analogous result to Proposition (ref) for PWM with the hybrid holdout penalty.
In this section we apply the PWM rule to the sieve we constructed in Example (ref) for monotone allocations. First, we apply our method to experimental data from the Job Training Partnership Act (JTPA) Study. Then, we derive bounds on maximum regret in a setting where our class has infinite VC dimension.
The JTPA study was a randomized controlled trial whose purpose was to measure the benefits and costs of employment and training programs. The study randomized whether applicants would be eligible to receive a collection of services provided by the JTPA related to job training, for a period of 18 months. The study collected background information about the applicants prior to the experiment, as well as data on applicants' earnings for 30 months following assignment bloom1997.\footnotemark[5]
\footnotetext[5]{The sample we use is the same as that in abadie2013, which we downloaded from \href{https://ideas.repec.org/c/boc/bocode/s457801.html}{ideas.repec.org/c/boc/bocode/s457801.html}. We supplemented this dataset with education data from the expbif.dta dataset available at the W.E. Upjohn Institute website. Observations with years of education coded as `99' were dropped.}
We revisit the setup in kt2015, which has frequently been considered in recent related papers. The outcome that we consider is total individual earnings in the 30 months following program assignment. The covariates on which we define our treatment allocations are the individual's years of education and their earnings in the year prior to the assignment. The set of allocations we consider is the set of monotone allocations defined in Example (ref), but with a non-increasing monotone function. To be precise, let $\mathcal{X}_1$ be the covariate set of years of education, and let $\mathcal{X}_2$ be the covariate set of previous earnings, then the set of allocations we consider is given by: $$\mathcal{G} = \big\{G : G = \{(x_1,x_2) \in \mathcal{X} | \hspace{1mm} x_2 \le f(x_1) \hspace{1mm} \text{for} \hspace{1mm} f:\mathcal{X}_1 \rightarrow \mathcal{X}_2 \hspace{1mm} \text{non-increasing}\} \big\}~.$$ In the context of this application, this restriction imposes that, the less education you have, the more accessible is the program based on your previous earnings. It is plausible that such a restriction may be exogenously imposed on the planner for political reasons; after all, it may not be politically viable to implement a job-training program where only those with high levels of education or income are accepted.
The approximating sequence we consider is the one described in Example (ref), but now with a non-increasing monotonicity constraint. Recall that this was a sequence such that the resulting allocations partitioned the covariate space with a progressively refined, piecewise linear, monotone boundary. Given any fixed class in this sequence, we can perform EWM in that class. Figure (ref) below illustrates the result of performing EWM on the simplest class in the approximating sequence. This class is equivalent to the class of linear treatment rules from kt2015, but with an additional slope constraint. Appendix C describes the computational details of our implementation.
At the other end of the spectrum, we could consider performing EWM in the most complicated class in our approximating sequence: this class corresponds to allocations that stipulate a threshold for previous income at every level of education (note that such a class exists here because years of education is discrete with finite support). Figure (ref) below illustrates the result of performing EWM in this class.
As we can see, the resulting allocation in the simplest class and in the most complicated class look quite different, and given the option to choose any class from our sequence, it is not obvious which one should be chosen given the size of the experiment. Given that we have a finite sieve in this application, we can view the use of PWM in this context through the lenses of Corollaries (ref) or (ref). In Figure (ref), we illustrate the result of performing PWM on our sequence of classes, where we used $3/4$ of our sample for estimation. Note that PWM selects the allocation from the second class in our sequence, which corresponds to a piecewise-linear allocation with one possible “kink".
Next, we derive a bound on maximum regret in the setting where $\mathcal{X} = [0,1]^2$, so that our class has infinite VC dimension. We consider the following restriction on the class of distributions:
In words, Assumption (ref) requires that the conditional distribution of $X_1$ given $X_2$ is continuous with a uniformly bounded density. With this regularity condition imposed, we are able to derive the following uniform bound on the approximation bias $W^*_\mathcal{G} - W^*_{\mathcal{G}_k}$:
To illustrate the use of Proposition (ref) in our setting, we derive a bound on maximum regret for monotone allocations. Proposition (ref) and Corollary (ref), along with the bound on $V_k$ given in Example (ref) allow us to conclude that:
Corollary (ref) establishes a polynomial rate of convergence for PWM. In contrast, we are not aware of any results which would allow us to derive a bound on maximum regret for EWM (or other related methods which do not employ a sieve construction) under Assumption (ref).
In Appendix B, we derive a series of results on the behavior of EWM under suitable entropy restrictions on the class $\mathcal{G}$, which show that under the stronger assumption that $X$ is continuous with a bounded density, EWM in fact achieves a root-n rate (up to a log factor) in this example, and that this rate is optimal. As we explain in Remark B.2, PWM can also achieve the same optimal rate of convergence in this setting, which would not be the case for a deterministic $k(n)$ chosen to obtain the rate derived in Corollary (ref). This further reinforces the observation made in Remark (ref) about the adaptation of PWM to additional regularities.