{'fraction_non_alphanumeric': 0.043951550085683126, 'fraction_numerical': 0.00930830347406138, 'mean_word_length': 4.482331589623145, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 13, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 18, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Evidence-Based Policy Learning

The past years have seen seen the development and deployment of machine-learning algorithms to estimate personalized treatment-assignment policies from randomized controlled trials. Yet such algorithms for the assignment of treatment typically optimize expected outcomes without taking into account that treatment assignments are frequently subject to hypothesis testing. In this article, we explicitly take significance testing of the effect of treatment-assignment policies into account, and consider assignments that optimize the probability of finding a subset of individuals with a statistically significant positive treatment effect. We provide an efficient implementation using decision trees, and demonstrate its gain over selecting subsets based on positive (estimated) treatment effects. Compared to standard tree-based regression and classification tools, this approach tends to yield substantially higher power in detecting subgroups with positive treatment effects.


INTRODUCTION
Recent years have seen the development of machine-learning algorithms that estimate heterogeneous causal effects from randomized controlled trials. While the estimation of average effectsfor example, how effective a vaccine is overall, whether a conditional cash transfer reduces poverty, or which ad leads to more clicks -can inform the decision whether to deploy a treatment or not, heterogeneous treatment effect estimation allows us to decide who should get treated.
Existing algorithms for the assignment of treatment typically optimize welfare without taking hypothesis testing into account. These algorithms aim to maximize realized outcomes, and thus focus on assigning treatment to individuals with positive (estimated) treatment effects. Yet in practice, the deployment of assignment policies often only happens after passing a test that the assignment produces a positive net effect relative to some status quo. For example, a drug manufacturer may have to demonstrate that the drug is effective on the target population by submitting a hypothesis test to the FDA for approval. When target groups differ not only in their treatment effects, but also in how precisely these treatment effects can be measured in a trial, then this additional testing step may affect the optimal choice of treatment assignment.
In this article, we explicitly take significance testing of the effect of treatment-assignment policies into account. In our baseline setting, we assume that a policy obtained from training data only gets implemented when a hypothesis test on additional hold-out data shows a significant positive effect relative to not assigning anybody to treatment. In the drug example, the manufacturer decides based on a training sample for which subset of individuals to apply for approval, and subsequently submits additional data for that subpopulation to the FDA.
In the main article, we optimize for the testing goal of maximizing the probability of passing the test. Such a goal may correspond to a researcher who wants to obtain significance to get published, or the drug manufacturer targeting approval. Under a Normal approximation, we show that this goal is equivalent to maximizing the ratio of mean to standard error of treatment effect estimates in the hold-out data. When conditional variances differ across covariates, then the oracle solution to this goal can differ markedly from an oracle assignment based on which individuals have predictably positive treatment effect.
We discuss an implementation based on greedy optimization of sample analogues, and present an example algorithm based on decision trees. We show that empirical optimization of our target goal approximates an optimal assignment in finites samples, and present approximation bounds for finite support and under a sparsity assumptions on conditional treatment effects and conditional variances.
We illustrate theoretically the benefit of the evidence-based approach by proving that an algorithm that splits groups empirically according to our main target criterion outperforms a naive classification approach when observations vary considerably in their predictable noise.
In a simulation study, we compare the performance of our algorithm that optimizes for this testing goal to tree-based algorithms that target maximal average outcome by assigning based on positive estimated treatment effects. We demonstrate the improvement in performance with respect to our main target metric, and highlight cases in which such an assignment policy tests better than a simple overall -test in the full training and hold-out sample combined.
The main intuition behind our results can already be seen in the case where treatment effects are directly observed, yielding the goal of selecting subgroups of the data that have significantly positive outcomes. Figure 1 plots a draw of treatment effects on the -axis against their univariate covariate on the -axis. In this simulated example, there are three parts of the covariate space: the left ( ∈ [0, 1]) has negative mean and high variance, the middle ( ∈ [1,2]) has high average treatment effect and high noise, and the right ( ∈ [2,3]) has small positive treatment effects with small noise. A standard classification tree that aims to assign individuals with positive treatment effect (dashed blue line) would often separate the leftmost from the remaining parts, yielding a test with low power on a hold-out dataset because of the noisy outcomes in the middle. In this example, our algorithm that targets significance (blue solid line) selects instead only the right-most segment for treatment, yielding better evidence of a positive effect. Extensions. As immediate extensions, we also consider the conditional assignment goal of maximizing the expectation of actual outcome when the policy only gets implemented when a significance test is passed. This goal effectively interpolates between the testing goal -which does not account for effect sizes beyond their implied significance -and the pure assignment goal that aims to assign only based on absolute effects. We consider this a relevant framework for welfare evaluation e.g. in the case of drug or vaccine approval.
For both the testing goal and the assignment goal, we also consider randomized assignment policies that map individual characteristics to the probability of receiving treatment. Considering these policies represents a continuous relaxation of the binary assignment problem in the main article. The implementation becomes particularly straightforward when we consider stochastic treatment policies for the testing goal. Specifically, this goal motivates a tree that recursively splits the covariate space to optimize the sum of leaf-wise squared (positive-part) -statistics.
Related work. Learning personalized policies from experimental or observational data has been extensively studied in the recent machine learning literature [14,19,28,39]. A large volume of works use ideas from the doubly robust literature in semi-parametric inference [12,20,21,33,34,41] so as to construct objectives to be optimized over a space of policies. However, the majority of these works optimize the mean policy value and do not focus on the objective of succeeding in a subsequent test on a fresh sample. In the experimental section we compare to a predominant such approach.
Our work is also very closely related to the work on recursive partitioning and treatment effect estimation in the causal machine learning literature [1-3, 6-8, 17, 18, 22, 28, 30, 43]. We compare to some predominant methods from this line of work in our experiments. This line of work uses dataadaptive machine learning procedures to learn how the effect of a treatment varies with observable characteristics, even when these characteristics are high-dimensional. Unlike the treatment effect literature, we do not care about learning an accurate model of how the effect varies, but rather only learn a model of who-to-treat. Thus we solely need to understand for which subset of the population the treatment effect is positive. Moreover, the majority of the heterogeneous treatment effect literature constructs sub-groups solely based on some mean heterogeneity criterion. Arguably closest to us is the work of [31] which analyze a tree algorithm whose criterion uses a standardized heterogeneity of the form ( ( 1 ) − ( 2 )) 2 /( ( 1 ) 2 + ( 2 ) 2 ) (already proposed in [1], where 1 , 2 is a candidate split, ( ) is the mean effect on each sub-group and ( ) the standard deviation. However, this criterion tries to identify the modes of heterogeneity and does not target the policy problem directly. Thus it might be creating very fine partitions in regions of the space where the effect is definitely positive. Such sub-grouping is irrelevant from the perspective of policy learning, where all we care about is the sign of the effect.
Our work also relates to recent work on false discovery rate control in multiple and adaptive hypothesis testing [24,32]. Unlike our setting, the FDR literature typically considers the statistically more daunting task of testing on the same data that was used to construct the adaptive hypothesis.
Here we consider a sample splitting setting, where testing will be constructed on a separate data set. Moreover, unlike the FDR literature we construct algorithms for optimizing the out-of-sample power of the test. Arguably closest to our work from the FDR literature is the concurrent work of [13], which instantiates the FDR line of work on the heterogeneous treatment effect problem and presents an interactive algorithm that controls the false discovery rate of the constructed sub-group to be treated. On the contrary our work focuses on finding an assignment in a non-interactive manner, which maximizes the power of a test on a separate sample.
There has also been recent work on providing robust versions of off-policy learning, which is similar in spirit to our motivation. The work of [16], presents a stability based objective for estimating sub-group effects and for creating sub-groups with treatment effect heterogeneity, that are stable (i.e. do not vary a lot) and are well-calibrated out of sample, i.e. the average effect of sub-groups for which we declared a large effect has to also be large on out-of-sample. Finally, the concurrent work of [25] provides a way of estimating assignment policies that maximize the median policy value, instead of the expected policy value, which typically is more robust to outlier samples. Both of these works could lead to better out-of-sample power of statistical tests, since they lead to more robust sub-group heterogeneity identification. Unlike these works, our work directly targets the out-of-sample power as an objective.
Structure of the article. Section 1 introduces our assumptions about the data, and formalizes different goals when finding treatment assignment policies. In Section 2, we characterize the (infeasible) theoretically optimal solution to the main testing goal, before we feasible implementations in Section 3. We illustrate the utility of this approach theoretically in Section 4 and in a simulation study with hybrid data in Section 5. Section 6 discusses extensions.

SETUP AND GOAL
We consider the problem of estimating an assignment policy : X → {0, 1} that maps a covariate ∈ X to an assignment ( ) ∈ {0, 1} of being assigned to the treatment group. For a population distribution of ( (1) , (0) , ) with potential outcomes (1) , (0) and covariates , we consider the expected lift under assignment according to relative to the status quo of assigning everybody to control, where denotes the conditional average treatment effect. We learn an assignment policy from a randomized trial with iid draws ( , , ), where treatment ∈ {0, 1} is assigned randomly with probability E[ ] = ∈ (0, 1), = ( ), and ( (1) , (0) , ) follow the population distribution. Randomization of allows us to identify ( ) from the data.
Yet in practice, after estimating an assignmentˆthat determines who should get treated, we often have to validate that the assignment does indeed improve the outcome (ˆ) relative to the status quo. A standard tool for such validation -and frequent constraint to deployment -is a test for statistical significance against the null hypothesis that (ˆ) ≤ 0. For example, a drug company may only get a drug approved for a subgroup of the population after passing a statistical test that provides evidence of the effectiveness of the drug against a placebo condition. Rather than arguing in favor or against such hypothesis testing, we take it as a given constraint for deployment.
We therefore assume that there is an additional hold-out dataset with draws ( , , ) from the same distribution as the experiment available, on which we perform a hypothesis test of the formˆ(ˆ) whereˆ(ˆ) is an estimate of (ˆ) and

√︃
Var(ˆ(ˆ)) is an estimate of the measurement noise Var(ˆ(ˆ)|ˆ) from the hold-out data, and 1− is the critical value of a one-sided Normal test with significance level (that is, the 1 − -quantile of a standard Normal).
In this article, we focus on estimators based on the pseudo-outcomes˜= ( − ( )) −

1− 1−
for the propensity = E[ ] and the centered outcome − ( ), yieldinĝ Note that E[˜|ˆ] = E[ˆ( ) ( (1) − (0) )|ˆ] = (ˆ) irrespective of the centering , but the centering can reduce the variance. In practice, may be estimated on the training sample. We will justify a specific choice of in Section 3 below. Similarly, we may replace the true propensity of treatment by its sample analogueˆ( ) = =1 , in which case we obtain the difference in averageŝ We obtain straightforward extensions when propensity scores are non-constant or have to be estimated, and for alternative outcomesˆ(see Section 6).
The test above is justified under standard regularity conditions bŷ under the null hypothesis (ˆ) = 0, where we assume throughout thatˆassigns a sufficiently large part of the sample to treatment so the limit remains well-behaved.
In the main article, we consider the goal of maximizing the probability of passing the test, so we want to choose an assignmentˆwith maximal expected probability where expectation and probability are over the hold-out sample. For an assignment that assigns nobody to treatment, we can in practice assume that -values are uniformly distributed, yielding baseline utility (ˆ) = . This goal would correspond, for example, to the goal of a drug company to get a drug approved, or the goal of a researcher to find a subset with a significantly positive treatment effect. (By splitting the sample, optimizing for such a goal does not distort inference as long as the hold-out data is only used for the test.)

CHARACTERIZATION OF ORACLE POLICIES
In the previous section, we motivated the objective function for the expected lift ( ) = E[ ( ) ( )] of the assignment. In this section, we solve for their theoretically optimal (but generally infeasible) oracle maximizers when we apply a large-sample approximation for the training sample. Expanding on the above notation, we write where − ( ) is the centered outcome (and we assume wlog that is chosen such that E[ − ( )] = 0 in the case of using empirical propensity). We focus on the case where treatment effects ( ) are small, Assuming that treatment effects are of the order of magnitude 1 √ allows us to model non-trivial testing in the limit, and expresses the use case where data is so noisy or effects so small that testing is meaningful. In Section 3 below, we extend our approach beyond this asymptotic framework and instead provide finite-sample results.
In the local-to-zero limiting regime and for the estimators outlined above, for any fixed rule with E[ ( )] > 0 we have thatˆ( , 1 .
Since the asymptotic power of the resulting test is thus (with the Normal cdf Φ), maximizing asymptotic power corresponds to maximizing . Theorem 2.1 (Oracle policy characterization). Asymptotically as → 0 and under standard regularity assumptions, the policy that maximize the testing objective solves * = arg max ( ) = arg max when there are positive treatment effects, and otherwise * ≡ 0. Note that the optimizer does not depend on the hold-out size , or the size of the test.
The result holds more generally for continuous relaxations of the assignment problem, to which we return in Section 6. In the binary case we study here, 2 ( ) = ( ), so the criterion becomes

IMPLEMENTATION USING EMPIRICAL OPTIMIZATION OF SAMPLE ANALOGUES
In Section 2, we characterized an oracle solution for the goal of finding an assignment that optimizes for passing a hypothesis test on hold-out data. In principle, one could use any estimation method of treatment effects ( ) and variances 2 ( ) on the training data to estimate such an assignment.
In this section, we study implementations that optimize the sample analogue of the criterion in Theorem 2.1 in the training data. Specifically, we now drop the assumption that treatment effects are local to zero, and consider finding an assignment policy that approximates a maximizer of the population -score Var(ˆ( )) by maximizing its empirical analogue in the training sample, which is the usual in-sample -score. We formalize this task below before discussing solutions to the empirical optimization problem and their properties.

Empirical and Population Objectives
When given access to samples { , , } =1 of features ∈ X, outcome ∈ R and treatment ∈ {0, 1}. We can estimate the mean value of any assignment policy : X → {0, 1} in an un-biased manner using the inverse-propensity scoring approach. If we let = P( = 1), be the probability of a treatment assignment in the randomized control trial, then we have that an un-biased estimate of the value of a policy is Even though it is un-biased, the latter estimate typically has high variance. Hence, we can typically improve the performance of our estimate by considering the semi-parametric efficient doubly-robust estimate of the value. If we construct a regression estimateˆ( , ) of the conditional expectation ( , ) := E[ | = , = ], then an un-biased, lower variance estimate of the policy value is We first start by using the observation that equivalently, one can simplify the doubly-robust estimate in the form of an appropriately centered IPS estimate (see e.g. [42]), i.e.
After straightforward numerical manipulations it is easy to show that 0 ( ) = ( ). Moreover, observe that the optimal centering function can be written as the minimizer of a weighted least squares regression problem (e.g. [37]), 1 which can subsequently be estimated by arbitrary machine learning non-parametric methods in a data-adaptive manner. Thus we can estimate the value of any policy using the IPS formula on a centered outcome = − ( ). Subsequently, we can define the -statistic for the value of a policy as where AVG(·) is simply the average of the numbers and STD(·) is their standard deviation. First we re-write our objective as Thus we see that maximizing ( ) is equivalent to minimizing Thus, we can re-write the following equivalent objective: 1 The first-order condition for each is: [42] proposes a leave-one-out estimator of average treatment effects in experiments based on residualization by this score. [37] argues that this specific score solves the weighted prediction problem in (5). [29] also considers an implementation for average effects in experiments using cross-fitted centering.
Moreover, throughout our analysis in this section it will be helpful to define the population analogue ( ) of the latter objective, We also note the following useful properties that relate the expected value of quantities in the empirical objective with quantities in the population objective.
Lemma 3.1. The following properties hold: .

Optimal policy for finite X via submodular minimization
Observe that for a finite set X, the empirical optimization problem of the objective ( ), is equivalent to finding a subset ⊂ X that maximizes =˜. Without loss of generality, when solving the empirical maximization problem, we can discard features ∈ for which ( ) ≤ 0, thus when solving the optimization problem it suffices consider the case when ( ) > 0, for all ∈ X. The latter is equivalent to minimizing the ratio of a monotone submodular function over a monotone modular function. Corollary 3.3 of [5] shows that the latter can be solved up to a (1 + )-approximation with (log(1/ )) calls to a submodular minimization process (which can be solved in polynomial time [35]) that minimizes √︁ ∈ ( ) − ∈ ( ), which is also submodular, for some appropriately chosen in each call. We note however that the result in [5] requires solving a constrained submodular minimization, subject to the constraint of a non-empty solution. This constraint is non-trivial and not the standard submodular minimization problem solved by existing solvers (covering constraints can render submodular minimization NP-hard). We show here how to modify the result and the algorithm in [5] to only require an un-constrained submodular minimization oracle.
Theorem 3.2 provides an approximation guarantee on the empirical criterion. However, for finite X of size , a simple uniform deviation bound implies that the empirical objective converges to the population objective for any assignment : for any fixed centering function and for ( , . Moreover, by Lemma 3.1, In fact, we can invoke tighter uniform deviation bounds to get the following theorem: Moreover, the algorithm will terminate after log(1/ ) + log( ( )/min ∈ ( )) iterations.
Set¯:= ( max + min )/2 and solve unconstrained submodular minimization problem: If^= ∅ or Thus for finite X we can arbitrarily approximate the optimal assignment policy problem with respect to our objective function. Moreover, the latter function is a special case of a submodular function that can be solved much more efficiently than generic submodular minimization [38].
This reduction also draws strong connections between our approach and the variance penalization literature in policy learning. In particular, [39] proposes that one maximizes an objective of the form (after bringing it to our notation) with a vanishing at a roughly ( −1/2 ) rate when belongs to a VC class. We see that unlike variance penalization we balance the standard deviation with the mean policy outcome and we do not necessarily have a vanishing penalty . Even closer to our objective is the second moment penalization in [17], which recommends maximizing Again this objective has the same discrepancy with our objective in that we balance the root of the second moment and we do not necessarily have a vanishing . Moreover, in our objective the is auto-tuned so as to minimize the -statistic.

Infinite or exponentially-sized X
However, we note that in typical applications X will not be finite but either uncountable or exponential in some implicit representation. For instance if is represented by binary features, then |X| = 2 . Moreover, typically, will be represented by continuous features. In this setting we not only need to solve the optimal assignment problem for a set of finite pre-defined sub-groups, but in some sense we need to also construct what these sub-groups are. In other words we need to partition the X space in a finite set of partitions and then find the optimal assignment with respect to this partition. However, the choice of partitions also needs to happen in a manner that will lead to large -statistic.
A tree-policy based direct approach. A popular approach in data science for such partitioning is recursive partitioning via binary decision trees [1]. Given the success of greedy tree-based heuristics in the statistical estimation literature, we focus on such heuristic solutions to this maximization problem. In particular, we define a greedy tree construction algorithm that at every step investigates the expansion of each leaf into two child nodes by splitting on a particular feature and at a particular threshold. Subsequently, we investigate the combination of the two possible treatment configurations of the two candidate child nodes and evaluate the t-statistic of each such new candidate policy, choosing the candidate split that maximizes the statistic. We note that unlike typical tree criteria, our -statistic criterion cannot be solely computed based on the samples of a node, since the standard deviation in the denominator is a global policy property. Thus at every candidate split we need to use the whole assignment policy to evaluate the performance of a new split. The details of our heuristic are presented in Algorithm 2.
A model-based approach. Observe that to identify the optimal policy it suffices to consider policies that offer a uniform treatment assignment for groups of 's for which neither the mean treatment effect ( ) or ( ) changes. Lemma 3.4 (Exact Partitions). There exists an optimal policy such that all elements in X with both ( ) = and ( ) = , for some and ≥ 0, receive the same treatment assignment.

ALGORITHM 2: Evidence-Based Policy Tree Learning
Input: samples { , , } =1 of features ∈ R , centered outcome ∈ R and treatment ∈ {0, 1}; Input: minimum score increase min , maximum depth max , minimum number of leaf samples min ; Calculate fraction of treated population = 1 ; Add root node to a queue, set = 1; while queue is not empty do Pop a node ( , , , ) from the head of the queue; Suppose that * is an optimal policy and that min ∈ [ ] 2 ≥ 2 and max ∈ [ ] / 2 ≤¯. Then there exists an assignment policy , which for every ∈ [ ], assigns the same treatment to all ∈ , and which satisfies: Thus if we can find a partition of the X space into a finite set of partitions 1 , . . . , , such that for all ∈ [ ], and for all , ′ ∈ : ( ) = ( ′ ) = and ( ) = ( ′ ) = , then observe that it suffices to optimize over policies ( ) = ( ( )), where ( ) denotes the index of the partition that lies in. Equivalently, it suffices to identify the subset ⊆ [ ] of partitions to treat, with value ( ) := ∈ ∈ 2 . Subsequently, the reduction to submodular minimization for finite elements X applies, but now the partitions { 1 , . . . , }, take the role of the finitely many elements of X. Hence, a (1 + )-approximate optimal policy can be found with (log(1/ )) oracle calls to a submodular minimization oracle for decomposable submodular functions, as in Theorem 3.2.
Importantly, we assume that the variables in are -strictly relevant, in the sense that the variance reduction incurred by conditioning on one of the variables in by an additive factor , larger than conditioning on any variable in [ ]/ . More formally: We say that function satisfies the ( , )-strong sparsity condition if there exists a set of size | | = , such that, for all ∈ and ∈ [ ]/ and ∈ [ ]/{ }: Observing that E[˜| = ] = ( ) and that E[˜2 | = ] = 2 ( ), we have the following corollary of the results in [40] (in particular Theorem C.10.2). and based on the Breiman criterion and with depth ≥ , satisfies w.p. 1 − , that every , ′ that fall in the same leaf of the tree, have ( ) = ( ′ ). Similarly, a greedy level-split regression tree trained on labels˜2 and based on the Breiman criterion and with depth ≥ , satisfies w.p. 1 − , that every , ′ that fall in the same leaf of the tree, have 2 ( ; 0 ) = 2 ( ′ ; 0 ).
Thus by taking the intersection of the partitions defined by two greedy decision trees with depth = , we guarantee the property required by Lemma 3.4. This partition can also be thought as the leafs of a decision tree with depth = 2 .
Subsequently for any policy value defined on the leafs of a binary tree of depth , adaptively chosen based on the data, we want to understand the concentration of the numerator and denominator of our objective . If we let denote the space of binary policies defined on the leafs of an adaptively built binary decision tree of depth , then we need to control the uniform deviations: w.p. 1 − , is the VC-dimension of policy space Π. By existing results in statistical learning theory, the VC dimension of a binary classification tree of depth , with features is 2 log( ) (see [26] for the first claim of this fact and e.g. Section A.2 of [40] for a proof, or Lemma 4 of [44], or [23] for a more extensive treatment). Thus we have the following lemma: Lemma 3.8. Let denote the space of binary policies defined on the leafs of an adaptively built binary decision tree of depth . Let be a fixed centering function. Let := 4 2 + 2 +1 log(2 ). Assume that |˜| ≤ a.s.. Then w.p. 1 − , for all ∈ : Combining all the latter facts we have the following final theorem: . Finally suppose that 2 ( ; 0 ) ≥ 2 for all ∈ X nad that |˜^| ≤ a.s.. Let = 4 2 + 2 +1 log(2 )) and: Let * be an optimal policy for the criterion ( ). Thenˆsatisfies w.p. 1 − : Moreover, the algorithm runs in time polynomial in {2 , log(1/ ), , }.
Finally, in the latter theorem we note that we can remove the log( ) factor in the leading term of the error, if the regression trees for learning ( ) and 2 ( ) are also trained on a separate sample.
This will lead to a leading error term of √︁ 2 +2 log(2/ )/ , which could lead to an improvement for large .

THEORETICAL ILLUSTRATION
The Section 2 we argued in favor of choosing an assignment that maximizes the oracle criterion In the previous section, we showed how empirical maximization in the training data approximates an optimal assignment, in the sense that it yields a value of the oracle criterion that is close to the maximum. We now demonstrate in a theoretical example how choosing an assignment according to this empirical maximization can improve power relative to a simple assignment based on estimating conditional average treatment effect alone.
Specifically, for illustration we consider a data-generating process with equally-sized covariate cells ∈ {1, . . . , }, with all outcomes bounded. In the training data of size , cell-wise average treatment effects are where we again assume local-to-zero effects as in Section 2 to obtain non-degenerate solutions for the power of the test. In the training data, we obtain treatment effect estimatesˆwith asymptotic variance 2 and variance estimatesˆ2 for every cell , where We consider two policy-learning algorithms on the training data: (A) A simple classification algorithm that targets the average outcome under assignment, choosing an assignmentˆ( ) ∈ {0, 1} that maximizes (B) An evidence-based algorithm that targets the sample analogue of the testing criterion as in Section 3, choosing an assignmentˆ( ) ∈ {0, 1} that maximizes We assume that we evaluate both policies on a hold-out sample of size = , where > 0 is fixed throughout. We then compare the expected utility  between the two approaches, where we average over the hold-out (outer expectation) and over the training data (inner probability). For illustration, we consider an extreme case -that treatment effects are arbitrary, but noise levels vary so much that only one of them is worth testing in the hold-out.
for sufficiently large.
This result illustrates the more general approximation results in the previous section. Specifically, by Theorem 3.3, we can approximate the value of an optimal assignment up to an error that is of the same order of magnitude as the difference between different treatment assignments in this local-to-zero framework. Moreover, the leading term in the error in Theorem 3.3 does not depend on the specific assignment or variances. By choosing sufficiently low variances that lead to a probability of rejection that is arbitrarily close to one for an optimal policy, we therefore also obtain an assignment with probability of rejection that is arbitrarily close to one from the training dataset with high probability. The simple classification algorithm, on the other hand, will select the bucket with variance max 2 ≥ at least half of the time in large samples, leading to an assignment with rejection probability that can be arbitrarily close to the size of the test. Taken together, we find some (extreme) conditions that (for , not too large) imply that the evidence-based assignment dominates.

SIMULATION STUDY
We evaluate experimentally how our algorithm compares to alternative methods in the policy learning and heterogeneous treatment effect literature. We consider two experimental designs. In the first setting we consider a stylized data generating process that highlights vividly the regime where our algorithm substantially out-performs the alternative approaches in the literature. Subsequently, we consider a semi-synthetic experiment where we use the features and treatment assignments from a real-world dataset from an HIV trial [15] that consists of a four-armed randomized trial among youth in western Kenya and assesses the effect on herpes type 2 (HSV-2) prevalence. We find that in both settings our evidenced based policy tree achieves strictly higher or comparable out-of-sample -values, as compared to the treatment subgroups identified by the alternative methods, across multiple signal-to-noise regimes, with the difference being very stark in some conditions.
Benchmarks. We consider the following benchmark policies/methods: (1) all: Treating everyone (2) cate: First, estimating a heterogeneous treatment effect ( ) based on the -learner method (double machine learning for heterogeneous effects) [28], which is one of the most popular methods for heterogeneous treatment effect estimation and has several favorable formal statistical properties [9,17]. In particular, we used random forest regression and classification to estimate the residual outcome and residual treatment required in the -learner algorithm. Moreover, we used a single decision tree as a final stage treatment effect model, to make it comparable to the model that is constructed by our policy tree. Subsequently, we set the policy to be ( ) = 1{ ( ) ≥ 0}. can be used as labelsˆ= ( ), and the absolute value of these values as sample weight. We used a decision tree classifier to solve these classification problem. The variant classifier does not perform optimal centering and simply uses ( ) = 1 , i.e. the mean of the . The variant classifierres performs optimal centering of the values. All of our methods are judged by calculating the out-of-sample -value of the chosen treatment policy . In other words, we use the optimally centered policy value ( ) and calculate the quantity ( ) defined in Equation (6) on a held-out sample. The machine learning model that is trained to calculate the optimal centering (we used a random forest regressor), was trained on the training sample and was only evaluated on the held-out sample.

Simple synthetic setting
We first consider a very simple setting that portrays the regime where our method shines compared to these alternative aforementioned approaches. We consider the case of a single feature ∈ [0, 3]. The feature space is partitioned in three intervals [0, 1], [1,2], [3,4]. In each interval , the value of the outcome of each sample can be described by the following equation: = · + + , The parameters for the three regions are = (0, 2, 1), = (0, 10, 100), = (5, 10, 1). Thus we see that in the first region the treatment effect is null, and samples from this region should not really be treated. In the second regime the treatment effect is very positive, but samples from that region also have high variance (i.e. unobserved heterogeneity). Thus even though with many samples we would have clear evidence that samples from this regime should be treated, in a small sample regime, treating this region runs the risk of getting a statistically insignificant result and hence not being able to declare that the treatment is effective. The final regime has a modest treatment effect, but is much less noisier. Moreover, we observe that these three regions operate in orders of magnitude different baseline outcome regimes. Thus without correct centering of the outcomes, we have a very noisy outcome which can hurt both the accuracy of the method. We exactly recover these intuitive expectations from our experiments. We find that the evidence based algorithm with optimal centering evidenceres, significantly out-performs all other benchmarks for a large range of sample sizes. The results are portrayed in Figure 2.

Semi-synthetic experiments from HIV randomized trial
The HIV randomized trial data [15], is a four-arm trial that was deployed among youths in Kenya. See [15] for the details of the data collection and evaluation process. We used one of the four binary arms as our treatment and subselected 2456 samples that did not contain NaN values in the treatment or outcome. Each sample contains 44 observable features/characteristics. The outcome of interest was the prevalence of herpes type 2 (HSV-2) virus, two years after the treatment (binary outcome ∈ {0, 1}).
We analyzed the performance of our algorithm in a semi-synthetic manner. We used the raw 2456 × 44 features , and their corresponding treatment form the real data. Subsequently, we trained a ℓ 1 -penalized (sparse) logistic regression outcome model, separate on the treated and untreated population, to learn the functions ( ) = Pr( = 1 | = , = ) = ( ⊤ ). Subsequently, we also trained un-penalized logistic regressions, to de-bias the learned coefficients. The learned coefficients are depicted in Figure 3. We see that there are three significant factors of heterogeneity, with two factors increasing the effect and one factor decreasing the effect. Subsequently, we generated new outcome data from several manipulations of the learned models. In particular, we generated binary outcome data based on the probabilistic models where¯= 1

=1
. The constant "cov-strength" controls the signal/heterogeneity contained in the features, while the constant "separation" controls the baseline effect of the treatment.
Our experimental results are depicted in Figures 4, 5 and 6. We find that our evidenceres and submod methods outperform the benchmarks in the medium signal regimes where the signal in the features is relatively low, while being comparable with the alternative methods in the two extreme regimes (very low/very high signal). Morever, the performance of both algorithms is comparable, with evidenceres having a slight advantage. Moreover, we see that running submodular minimization at the end of the evidence based policy tree has little to no-effect, implying that the greedy tree algorithm not only found good sub-groups, but the assignment that it constructed was optimal for these sub-groups.

Semi-synthetic experiments from HIV randomized trial with continuous outcomes
We also simulated a variant of the semi-synthetic experiment in the previous section but now with continuous outcome data. We use the group structure from our synthetic analysis, but we define groups based on the real covariates from the HIV trial. Moreover, we use the treatment variable from the real data. The continuous outcome in each experiment is generated as follows:     cov-strenght=20, separation=0.1 Fig. 6. Fraction of 1000 experiments where out-of-sample -value ≤ 1 − 3, which we declare as a "discovery".
Our experimental results are depicted in Figure 7. We find that our submod method outperforms the benchmarks, correctly identifying not to include high-variance sub-groups, even though they might have a slightly positive effect. Moreover, the evidenceres method comes a close second, albeit in this setting we see that submod is strictly better than the evidenceres method.

Continuous relaxation
In the main article, we focussed on obtaining a binary assignment : X → {0, 1} that assigns an individual with a given covariate vector to treatment or not. We can relax the assumption and consider instead probabilistic assignments : X → [0, 1], where our target is the expected list Testing for E[ ( ) ( )] ≥ 0 can now be understood in two ways: first, as a test of a specific probabilistic assignment; or second, as a test of the null hypothesis that there is no (deterministic) assignment with positive expected effect (even if we do now not construct such a deterministic assignment). The oracle result in Theorem 2.1 remains applicable in this case. Indeed, since the hold-out data is already given, we do not actually randomize, but instead estimate the weighted estimand (ˆ) without adding additional randomness (which would be statistically inefficient). Only in the population would we then randomize for an individual with covariate based on the probabilityˆ( ). The continuous relaxation allows for the direct solution of optimal weights in the framework of Section 2: Proposition 6.1 (Optimal relaxed policy). Asymptotically as → 0, the probabilistic policy maximizing the power of the test on the hold-out sample is given by * ( ) ∝ + ( ) 2 ( ) yielding expected power (Note that the absolute scale of the policy does not matter here.) This particularly tractable formulation implies a criterion that can be used to partition the covariate space recursively using trees with binary splits. Specifically, for¯ℓ the average treatment effect of a leaf and¯2 ℓ = Var(ˆℓ ) the variance of the corresponding estimatorˆℓ , we aim to find a partition that maximizes ∑︁ ℓ¯2 l 2 ℓ , corresponding to weights¯ℓ ∝¯l 2 ℓ onˆℓ . When we also writeˆ2 ℓ for an estimator of¯2 ℓ , this suggests maximizing the sample analogue ∑︁ ℓˆ2 l 2 ℓ over partitions of the data, which can be achieved recursively, and then settingˆℓ ∝^l 2 ℓ . For illustration, Figure 8 compares a greedily fitted tree that maximizes the criterion in Theorem 2.1 over binary assignments with a greedily fitted tree that recursively maximizes this weighted criterion.

Passing the test as a constraint
The testing goal ignores the actual outcome under the policy. We therefore also consider a second goal that incorporates the expected outcome subject to passing the test, namely This goal would correspond for example to a drug manufacturer caring about the health outcomes of a drug subject to approval. It mixes the expected outcome (ˆ) with the testing goal E[ˆ(ˆ)|ˆ] to trade off the value of the policy with how easy it is to pass the test. In the approximation of Section 2, the optimal policy would then solve

Estimation for alternative outcomes and estimated propensity score
In the main article, we considered a treatment effect that is identified in an experiment by ( ) = E ˜ = = E − (1− ) ( − ( )) = and can be estimated accordingly. We can extend the same techniques to a family of parameters ( ) defined via a linear conditional moment equation: for data , target causal parameter ( ), and nuisance functions ℎ. For ( ) defined in this way, we aim to obtain an assignment that provides a significant test against the null that ( ) := E[ ( ) ( )] ≤ 0. If the moment function satisfies the conditional Neyman orthogonality property [9,17,30], and these nuisance estimates are estimated in a cross-fitting manner and are ( 1/4 ) estimable, then their error is asymptotically negligible. In this case, all our algorithms can be directly generalized by simply renaming the pseudo-outcome: The estimation and optimization algorithms as well as the analysis of their finite-sample performance easily generalizes to this general pseudo-outcome setting. Moreover, Neyman orthogonality for this setting can be easily achieved via an automated-double machine learning process as outlined in the recent work of [10,11]. For example, we can generalize the case of conditional average treatment effects to cases where the propensity score is unknown and has to be estimated, in which case ℎ

Cross-evaluation and bagging
So far, we have focussed on separating the training of a policy from its evaluation. While this may be the most applicable case in many heavily regulated settings, we may gain power by re-using training and hold-out samples by switching their roles. Relatedly, our main implementation is based on a simple tree that could be aggregated to a forest, either across the full sample or even within the training sample alone.

Testing for alternative reference assignments
Our results generalize to reference assignments other than assigning all observations to control. In the case of a reference assignment ( ), In that case, all results go through if we relabel ( ) = ( | − ( ) |) for observations with = .
CONCLUSION Treatment policies are often only implemented when the resulting assignment passes a hypothesis test. In this article, we formalize this requirement, and provide a characterization of optimal policies that are optimized for yielding significant evidence for treatment effects on sub-samples. We provide a greedy implementation using decision trees and document the performance of our algorithm in a simulation study. Our analysis remains limited in a number of ways we currently address in ongoing research. First, for simplicity we focus here on testing on a hold-out sample, but we consider extensions that use cross-validation to use data more efficiently. Second, we focus on a randomized trial, but these ideas apply similarly to observational data under selection on observables. Finally, we consider here a test against the null of no improvement over assigning everybody to control, but the methods extend e.g. to testing against other reference assignments and to testing for heterogeneous treatment effects.
For the estimated propensity scoreˆ= =1 , for which =1 ^− Proof. The first property is the standard derivation of the un-biasedness of the doubly robust estimator with known propensities: Optimizing: is equivalent to optimizing: . Thus the property that max ⊇ ∅ is maintained with the new max . Hence, we conclude that throughout the algorithm this property is maintained.
Moreover, we have that at the initial setting of min that Moreover, at any point where we change min to¯we know that eitherˆ= ∅, in which case min¯( ) = 0 or that √︃ (ˆ) ≥¯(ˆ), which implies that¯(ˆ) = min¯( ) ≥ 0. Thus at all points during the algorithm we have the property that min ⊆ [ ] min ( ) ≥ 0.
We first consider the case where > 0, i.e. when is not the only element that is assigned the treatment. Since by removing from assignment or adding ′ to the assignment, we are deteriorating the objective, we must have that: Consider the function: By the Equation (32), we must have that (0) < ( ( )) and ( ( )) > ( ( ) + ( ′ )). Since for > 0, ( ) is a smooth twice differentiable function in [0, 1] and we have the latter inequalities, it means that there must be a point * ∈ (0, ( ) + ( ′ )) at which it achieves a maximum. By the first order optimality condition at that point, we must have that: Since * > 0, we also have that 2 − 2 > 0 =⇒ 2 > 2 . Moreover, by the second order optimality condition we must have that: But for ≥ 0 and ≥ 0, the latter two inequalities cannot hold simultaneously, leading to a contradiction. Thus either removing or adding ′ must be a weakly improving change, leading to an optimal policy where and ′ are given the same assignment. Repeatedly applying the above argument, we can arrive to an assignment policy where any pair of , ′ that have ( ) = ( ′ ) and ( ) = ( ′ ) are assigned the same treatment. Now consider the edge case when is the only element assigned by the policy . In this case since adding the element ′ to the assignment leads to a deterioration we have: which is a contradiction. □ B.5 Proof of Lemma 3.5 Proof. Consider a partition ∈ [ ], such that a subset ⊆ , with density is treated, and the complement = / , with density is not treated by * . Let be the mean value of ( ) for all elements in , i.e. = 1 ∈X ( ) ( ). Similarly, let 2 be mean value of ( ) 2 . By our assumption, we know that for all ∈ : | ( ) − | ≤ and | 2 ( ) − 2 | ≤ . Moreover, denote with ,0 and 2 ,0 the corresponding means on the untreated sub-population and ,1 , 2 ,1 the means on the treated sup-population . By our assumption we also have that for all ∈ and for any ∈ {0, 1}: | ( ) − , | ≤ and | 2 ( ) − 2 , | ≤ . Let * be an optimal policy. We can write our objective as: where , ≥ 0, since an optimal assignment never allocates to any ∈ X with ( ) ≤ 0. Moreover, , are quantities that do not depend on how the policy behaves for any ∈ . We first consider the case where > 0, i.e. when is not the only partition that contains elements that are assigned the treatment. Since by removing from assignment or adding to the assignment, we are deteriorating the objective by more , we must have that:

+ (1 +¯)
Similarly, we have that: Thus for ≥ 2 (1 +¯), we can combine the latter inequalities to conclude that: Using an argument identical to that in the proof of Lemma 3.4, we can show that the latter leads to a contradiction. Thus either assigning all of the partition to the treatment or removing all of the partition from the treatment, can lead to a new policy which achieves and objective ( ) at least an additive smaller than the optimal policy. Repeating this process for every partition ∈ [ ], we can arrive at a new policy that achieves an objective that is at most an additive smaller than that of the optimal policy and in which all partitions have a uniform assignment to either treatment or non-treatment. □ B.6 Proof of Lemma 3.7 Proof. The result for is an immediate consequence of Theorem C.10.2 of [40]. For the case of 2 we need to make a small adjustment to account for the fact thatˆ≠ 0 . In particular, even though 2 ( ; 0 ) might satisfy the ( , )-strong sparsity condition, the function 2 ( ;ˆ) might not. Moreover, we want to guarantee that 2 ( ; 0 ) = 2 ( ′ ; 0 ) for every , ′ that fall in the leaf of the constructed tree and not that 2 ( ;ˆ) = 2 ( ;ˆ).
However, we note that the main argument in Theorem C.10.2 of [40] is robust to small errors. In particular, Lemma C.1 of [40], shows that the empirical splitting criterion¯( ;ˆ) for every possible split up to depth , is within an ( , ) of it's population counterpart w.p. 1 − , for . Moreover, the population criterion is: where we overloaded notation and denoted with¯( ; ) the function¯( ; (·; )). Since by Lemma 3. Proof. By Lemma 3.7, we have that w.p. 1 − , the partitions defined by the leafs of the two trees will contain 's that all have the same value of ( ) and 2 ( ; 0 ). Thus the policy space that is being searched over in the last step of the algorithm contains an optimal policy * . Moreover, combining Lemma 3.8 and Lemma 3.1 and a proof almost identical to that of Theorem 3.3 (replacing with /2 and log(2/ ) with log(2 / ), where = 4 2 + 2 +1 log(2 )), we can show that if we let:  For any fixed ( 2 ) =1 with min 2 ≤ 1 , max 2 > and any fixed assignment ∈ {0, 1} , we have that as → ∞ on the training sample. Since there are only 2 assignments, for sufficiently large. Hence, with probability at least 1 − /2 and for large , By (38) applied to the test sample, on that sample with probability at least 1 − /2 for sufficiently high. Taken together, we reject with probability at least 1 − once , are sufficiently high. On the other hand, for the simple classifier, P(ˆ( 1) = 1) > 1 2 for all and sufficiently large, including for some with > . In that case, and we therefore reject with overall probability at most as , sufficiently large. where the upper bound does not depend on and is attained at ( ) = + ( )/ 2 ( ). □