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.
69,529 characters · 9 sections · 41 citation commands
Qini Curves for Multi-Armed Treatment Rules
The Qini curve, initially proposed in the marketing literature radcliffe2007using, plots the average policy effect of treating the units most responsive to the treatment as we vary the budget. We can then quantify the value of treatment targeting via cost-benefit evaluations undertaken at a series of distinct budget levels. The Qini curve has been adopted in a variety of practical applications to evaluate the empirical performance of treatment targeting rules albert2022commerce,belbahri2021qini, diemert2018large, uplift_review, rzepakowski2012decision, zhao2017uplift, zhao2019uplift.
The theoretical properties of Qini-like metrics under a binary treatment, and extensions to area under the curve summaries, have recently received attention in the statistics literature by a number of authors, including imai2021experimental, imai2022statistical, sun2021treatment, and yadlowsky2021evaluating. These approaches consider the problem of targeting the assignment of a (possibly costly) binary intervention. In this paper, we explore the extension to scenarios where there are multiple treatment arms, and where the benefits and costs of assignment may vary across units. For example, a low-cost drug may be beneficial for a certain group of people, but a high-cost drug may be even more beneficial for a subset of these. Analyzing this setting through separate Qini curves for the two available arms can conceal important efficiency trade-offs. For a specific budget, the optimal policy may entail assigning different drugs to different people; a less expensive drug for one group and a costlier drug for another. Determining the optimal treatment assignment policy that maps individual characteristics to one of several treatment arms involves solving a constrained optimization problem.
We develop a theoretical and statistical framework to extend the Qini curve to the case where we have many mutually exclusive and costly treatments. We show that the Qini curve extended to multiple arms retains the desirable ratio-based interpretation of the Qini for a single treatment arm, where it is the incremental efficiency of each arm that determines the optimal allocation. This means that it is not necessary to denominate treatment effects and costs on the same scale. An additional unit of budget is allocated to an arm and a set of targeted participants (defined by their characteristics) if the ratio of the benefits to the set of participants relative to the cost is greater than the corresponding ratio for any other arm and set of participants.
To gain an intuition for the generalization of the Qini to multiple arms, recall that the Qini curve is a metric for evaluating a treatment rule implied by a policy. With a single treatment arm, where for simplicity the cost of assignment is the same for each unit, the optimal policy is to allocate treatment in decreasing order of the conditional average treatment effect. Given estimates of these treatment effects, the Qini curve plots the value of assigning treatment to individuals as prioritized by their estimated treatment effects. Figure (ref) shows Qini curves in a setting with two treatment arms. For example, if we can only use arm 1 and have a total budget of 0.2, then we can achieve a gain of 0.54; whereas if we can only use arm 2 the same budget yields an estimated gain of 0.60. Note that, once we pass a spend level of 0.3, the arm-1 Qini curve plateaus---this is because, once we have reached this spend level using arm 1, we are already giving treatment to all units believed to benefit from it, and so cannot achieve further gains via increased spending.
The single-armed curves in Figure (ref) are straightforward to compute, as the underlying policies induce a priority rule that involves sorting units in order of the estimated conditional average treatment effect. Computing the optimal allocation for a multi-armed policy is more complicated, as it involves solving a constrained cost-benefit problem across many arms. We show that, even though the underlying multi-armed policies are more complicated, they still yield a tractable treatment rule that can be evaluated with Qini curves. The Qini curve for a multi-armed policy in Figure (ref) highlights that since different arms can be better for different groups, targeting enables the arms to be assigned accounting for the cost-benefit analysis appropriate for distinct subgroups. For example, with a budget of 0.2, we can now achieve a gain of 0.75, which is better than what we could get with either arm alone.
Incorporating additional arms beyond two improves (i.e., raises) the Qini curve for two reasons. First, even in the absence of targeting, expanding the budget leads to greater use of arms that on average are less efficient (lower cost-benefit ratio) but are relatively beneficial. Second, targeting allows the identification of subgroups who particularly benefit from arms that might perform poorly on average, and thus not be prioritized in the absence of targeting.
We characterize the optimal multi-armed policy, showing that when expanding the budget, the optimal assignment selects units to receive more effective treatments according to where the incremental cost-benefit ratio is highest. We further show how, for given characteristics of a unit, the optimal policy can be characterized by a set of budget thresholds where the unit's assignment changes to a more beneficial but less efficient arm. We propose an efficient algorithm for estimating the solution path of the multi-armed policies that underlie the Qini curve by leveraging a connection to the linear multiple-choice knapsack problem.
Our main theoretical result quantifies uncertainty for points on the Qini curve via a central limit theorem for the estimated multi-armed policy values. The result takes estimates of conditional average treatment effects and costs as given but accounts for the uncertainty from approximating the optimal allocation for each level of budget, and from estimating the policy value for that allocation. The central limit theorem can be used to, for example, quantify the value of employing more arms when targeting treatment.
An open-source software implementation, maq for R and Python, is available at \href{https://github.com/grf-labs/maq}{\textcolor{PineGreen}{github.com/grf-labs/maq}}.
To characterize the optimal multi-armed treatment allocation, we operate under the potential outcomes framework imbens2015causal. We assume that we observe independent and identically distributed samples $(X_i, W_i, Y_i, C_i) \,{\buildrel \text{iid} \over \sim\,} P$ for $i=1,\ldots,n$, where $X_i \in \mathcal{X}$ denotes pre-treatment covariates, $W_i \in \{0, 1,\ldots, K\}$ denotes the treatment assignment ($W_i=0$ is the control group), $Y_i \in \mathbb{R}$ denotes the observed outcome, and $C_i \in \mathbb{R}$ denotes the incurred cost of assigning the unit the given treatment. We posit the potential outcomes $\{Y_i(0),\ldots, Y_i(K)\}$, $\{C_i(0), \ldots, C_i(K)\}$ and we assume $Y_i = Y_i(W_i)$ and $C_i = C_i(W_i)$ (SUTVA).
For the mutually exclusive treatment arms $k = 1,\ldots, K$, let $\tau(X_i)$ and $C(X_i)$ denote the vectors of conditional average treatment effects and cost contrasts, i.e. the $k$-th elements are:
In our intended application, the role of arm $k=0$ is to provide us with an option to hold back treatment without incurring any costs. To accommodate this setup we need to assume that the cost of assigning arm this arm is 0 and the remaining arms have non-zero costs,
Our goal is to gain insight into how much there is to gain from treatment targeting if treatment is assigned optimally. To do so, denote a policy by $\pi: \mathcal{X} \rightarrow \mathbb{R}^{K}$, a mapping from covariate $X_i$ to a treatment assignment. The policy $\pi(X_i)$ is a $K$-dimensional vector where the $k$-th element is equal to 1 if arm $k$ is assigned, and zero otherwise.\footnote{Fractional assignments between 0 and 1 are admissible and can be interpreted as probabilistic assignment between arms.} The associated value of this treatment assignment policy is the expected value:\footnote{In the policy learning literature it is sometimes common to define the value of a policy via potential outcome means athey2021policy. Had we instead encoded $\pi$ to be a non-fractional policy taking values in the set $\{0, \, 1, \ldots, K\}$ then an equivalent formulation of the gain (ref) would be $V(\pi) := \mathbb{E}_{}\left[Y(\pi(X_i)) - Y_i(0)\right]$.}
The cost of this policy is $\Psi(\pi) = \mathbb{E}_{}\left[\langle \pi(X_i), C(X_i)\rangle\right]$. Throughout the manuscript, we assume the cost function $C(\cdot)$ is known (i.e., the cost structure is a modeling decision). The optimal policy is the one that, for a given budget level, maximizes the expected gain while incurring costs less than or equal to the budget in expectation. Given a budget $B$, the optimal unrestricted policy $\pi^*_B$ that only depends on $X_i$ solves the following stochastic optimization problem:
The asterisk is to emphasize that this policy has access to the population oracle $\tau(\cdot)$ function. In the case of only a single treatment arm ($K=1$), but where each unit's cost may be different, (ref) is an instance of the fractional knapsack problem dantzig1957discrete and the optimal policy induces an appealing treatment rule allocating treatment to units in decreasing order of the cost-benefit ratio $\mathbb{E}_{}\left[Y_i(1) - Y_i(0) \mid X_i=x\right] / \mathbb{E}_{}\left[C_i(1) - C_i(0) \mid X_i=x\right]$ until the budget runs out luedtke2016optimal, sun2021treatment. The treatment allocation in this induced ranking constitutes the solution path over varying budget levels.
The multi-armed case ($K > 1$) is more complicated, as (ref) then belongs to the class of multiple-choice knapsack problems sinha1979multiple, a type of optimization problem that involves filling a knapsack up to a capacity by selecting at most one item from a set of classes, where each item has an associated “profit” and “weight”. In our formulation, the class is a unit and the item is a treatment arm with the profits and weights corresponding to the conditional average treatment effect and cost of the particular arm. The knapsack capacity is the budget constraint. Allowing for fractional treatment allocation reduces this problem to a linear program with $nK$ choice variables. Using the transformation principles presented in zemel1980linear, it is possible to recast this into inducing a similar treatment priority rule, but where the priority is based on “incremental” cost-benefit ratios.
The idea behind characterization via incremental cost-benefit ratios is to recast the problem of choosing between both units and treatment arms into thresholding a suitable priority rule that captures both which unit and which arm is optimal to assign at a given budget level. For any given unit $i$, the only treatment arms that will be active in the optimal solution are the ones that lie on the convex hull of the cost-reward plane sinha1979multiple. For any $x \in \mathcal{X}$, define the convex hull formed by the points $(C_k(x), \tau_k(x)), \, k = 0,\ldots,K$ to be a set of $m_x$ points with the ordering $k_1(x), \ldots, k_{m_x}(x)$ such that
where we define the incremental cost-benefit ratio as
and we let $\rho_0(x) = \infty$ and $\rho_{k}(x) = -\infty$ if $k \notin \{k_1(x),\ldots,k_{m_x}(x)\}$.
Figure (ref) illustrates the case of optimally assigning treatment for a single unit $i$. If we have an available budget of 1, it would be optimal to assign arm 3 to the $i$-th unit. If we increase the available budget to 2, then we have two choices: upgrade to either arm 2 or 4. Since arm 2 lies outside the convex hull, it is strictly sub-optimal to assign this arm, and the optimal assignment is arm 4. For the optimal policy, we are faced with a distribution of convex hulls, one for each unit, and have to decide whether to assign a new unit a treatment or upgrade an existing unit to a costlier arm. In Theorem (ref), we show that the insight from zemel1980linear carries over to the stochastic setting: What matters in each of these convex hulls are the slopes of the tangent lines between arms, i.e., the incremental cost-benefit ratio (ref). For a given budget level, when choosing between selecting an arm for unit $i$ or $j$, the (unit, arm) with the largest tangent slope is optimal. The following theorem formalizes this intuition by characterizing the optimal stochastic policy at a given budget level $B$, in terms of thresholding of the distribution of incremental cost-benefit ratios.
For generic distributions where $X$ has continuous support, $\mathbb{P}[\rho_{k_j(x)}(x) = \lambda_B] = 0$ for all $\lambda_B > 0$, and so the optimal policy will almost surely be integer-valued.
Section (ref) provides a characterization that maps a budget $B$, a cost function $C(\cdot)$ and the population function $\tau(\cdot)$, to an optimal policy $\pi_B^*(X_i)$. Given an independent and identically distributed random sample from this population, we can obtain, through various estimation methods, estimates $\hat \tau(\cdot)$ of the function $\tau(\cdot)$ (see Section (ref) for an example). We refer to the sample used to obtain these estimates as the training sample. These estimates induce a policy:
As a metric to evaluate treatment allocation according to an induced policy, we define the Qini curve:
The challenge now is, once we have a test sample of independent and identically distributed random sample from the population, how do we form estimates of $Q(B)$? To keep concepts clear we define the empirical induced policy on the test set:
In order to form an estimate of $Q(B)$ on a test sample, there are three subsequent challenges we need to address: how to handle the budget constraint, how to efficiently express $\hat \pi_B$, and finally, how to estimate the policy value of $\pi_B$. The first issue, we address by satisfying the budget in expectation on the test set as in Definition (ref).
\paragraph{Expressing $\hat \pi_B$ on the test set.} The optimization problem in (ref) has a linear program formulation that takes the following form,
The direct approach of solving (ref) via generic LP-solvers is computationally infeasible as this would involve computing a large collection of linear programs with $nK$ choice variables, one for each budget constraint $B \in (0, B_{max}]$.
A more feasible approach is to instead directly compute the path of solutions $\{\hat \pi_B\}_{B \rightarrow 0}^{B_{max}}$ via an algorithm tailored to the structure (ref) embeds. To this end, the characterization of the optimal policy in Theorem (ref) as a thresholding rule of incremental cost-benefit ratios $\rho$ is promising as it suggests the problem can be reduced to a single-dimensional fractional knapsack problem (with some additional bookkeeping). This is exactly the approach taken by zemel1980linear, to solve (ref) via sorting the incremental cost-benefit ratios kellerer2004multidimensional.\footnote{Faster algorithms for the LP-relaxation of the multiple-choice knapsack problem exits, dyer1984n, zemel1984n derive linear-time solutions for a fixed budget level, but these do not readily generalize to a path algorithm.} Figure (ref) illustrates how $\rho$ determines a solution. The vertical axis shows the incremental cost-benefit ratios for each unit's arm on the convex hull (with units indexed by the horizontal axis). A solution to (ref) is given by a particular threshold $\lambda_B$ on the vertical axis and determines the optimal allocation through a planar separation of unit-arm pairs.
A limitation of the algorithm in zemel1980linear is that it solves (ref) at only a single budget level $B$, as determined by a single planar separation. In order to adapt this algorithm to deliver a path of solutions over budget levels, we can make use of a priority queue ordered by decreasing $\rho$ that acts as a construction that keeps track of which (unit, arm) enters the active set of the solution path, as we lower $\lambda_B$ in Figure (ref) in accordance with the budget $B$ we are tracing out.
\paragraph{Estimating the value of $\pi_B$.} Now that we have a promising strategy to obtain the estimated path $\{\hat \pi_B\}_{B \rightarrow 0}^{B_{max}}$, how do we estimate its value? We show in Section (ref) that the approximation error of the empirical optimization in (ref) is asymptotically linear with zero means. This means we can leverage standard policy evaluation arguments for this component. Thus, with a suitable construction $\widehat \Gamma_i$ that satisfies $\mathbb{E}_{}\left[\widehat \Gamma_i \mid X_i\right] \approx \tau(X_i)$ policy evaluation arguments motivates forming an estimate of $Q(B)$ with the plug-in construction\footnote{Note that we are using the empirical induced policy $\hat\pi_B$ (Definition (ref)) to estimate the value of the population induced policy $\pi_B$ (Definition (ref)). Theorem (ref) verifies the validity of this approach.}
where $\widehat \Gamma_i$ could be obtained with, in the case of known treatment randomization probabilities (as in a randomized controlled trial), inverse propensity weighting horvitz1952generalization:
If the treatment randomization probabilities are unknown (as would be the case in an observational setting under unconfoundedness), then a more robust alternative to forming (ref) via plug-in estimates of the propensity score, is to rely on augmented inverse propensity weighting robins1994estimation. This approach relies on nuisance estimates in the form of propensity scores $e_k(x) = \mathbb{P}_{}\left[W_i = k \mid X_i = x\right]$ and conditional response surfaces $\mu_{k}(x) = \mathbb{E}_{}\left[Y_i \mid X_i = x, W_i = k\right]$. In order to construct this score, these components need to be estimated on the test set data.
To ensure that these estimated components are independent of the outcome for each unit, a popular approach is to employ cross-fitting dml, schick1986asymptotically where the $i$-th unit's estimate is obtained without using that unit for estimation. The multi-armed score then takes the following form robins1994estimation, zhou_multi_action, with $k$-th entry equal to
where the super script $-q(i)$ denotes fitting using the data excluding the fold $X_i$ belongs to. This approach for evaluation can yield an efficiency gain over inverse-propensity weighting (see yadlowsky2021evaluating for a discussion).
\paragraph{Computing the solution path and values.} With all the pieces needed to estimate $Q(B)$ in place, Algorithm (ref) outlines pseudo-code for all the components needed to compute the Qini curve for a multi-armed policy, starting with estimating conditional average treatment effects on a training set. With these, a chosen cost function, and suitable evaluation scores in place, Algorithm (ref) formalizes the intuition behind Figure (ref) with pseudo-code for computing the induced multi-armed policy and value up to some maximum budget level $B_{max}$.
After a reduction to convex hulls, Algorithm (ref) starts by adding each unit's first arm on the convex hull to a priority queue ordered by decreasing estimates $\hat \rho$ of the cost-benefit ratios. The first unit assigned is the unit on top of this queue (top square in Figure (ref)). If this unit has remaining arms on its convex hull (i.e., there are arms below the unit's initial allocation in Figure (ref)), then this subsequent arm is added to the queue with priority equal to its incremental cost-benefit ratio. The subsequent assignments might either be upgrades, in which case we move to a costlier arm lower on the vertical plane, or a new unit allocation. The exact sequence of upgrade-or-allocate-new-unit decisions is dictated by the priority queue order $\hat \rho$. The time complexity of this algorithm is log-linear in $nK$.\footnote{To give an impression of the practical performance of using this as an evaluation metric, for a sample size of one million, and five treatment arms, our open-source implementation computes the full solution path in around 1.5 seconds on a standard laptop.}
Depending on the value of $B_{max}$, the treatment allocation for the last unit to be assigned might not be integer-valued. By Theorem (ref) there are two such cases. The first case is if the $i$-th unit has previously not been assigned an arm, and there is not sufficient budget left to allocate the first arm on the convex hull. The second case is if the $i$-th unit has previously been assigned an arm, but there is not sufficient budget left to upgrade the unit to the next arm on the convex hull. In these cases, we may think of assigning the $i$-th unit an arm with a certain probability, as given by the fractional allocation $c_B$. In our intended setup, treatment is assigned to a large number $N$ of units matching the covariate profile of $X_i$, a fractional solution would simply mean that, in the second case, we assign one arm to $c_B N$ units, and the other arm to the remaining $(1-c_B)N$ units.
Finally, while Algorithm (ref) does not explicitly construct and return the vectors $\hat \pi_B(X_i)$, these are implicitly given by the sequence of (unit, arm) allocations and can be efficiently constructed ex-post, which is the approach taken in the accompanying software.
\afterpage{\FloatBarrier}
In order to employ the Qini curve for decision-making, we need to form the uncertainty estimate of $\widehat V(\pi_B)$, a point on the curve (we consider functionals such as area under the curves as an interesting extension for future work). In this section, we provide an asymptotic linearity theorem for the policy value estimate, which enables confidence intervals and hypothesis tests via resampling-based methods chung2013exact,yadlowsky2021evaluating.
We first make some standard identifying assumptions on the population,
Recall from Theorem (ref) that the policy $\pi_B$ in Definition (ref) can be expressed via the thresholding function $T(\cdot \, ; \, \hat \rho, \, \lambda_B, \, c_B)$, where $\hat \rho$ are estimates of the cost-benefit ratios using the estimated function $\hat \tau(\cdot)$, and $C(\cdot)$. The argument $\lambda_B$ in this function represents the value of the threshold of $\hat \rho$ that maximizes the gain under the given treatment and cost rules while satisfying the budget in population. The empirical policy $\hat \pi_B$ we obtain in Definition (ref) is a function $T(\cdot \, ; \, \hat \rho, \, \hat \lambda_B, \, \hat c_B)$, i.e., the estimated policy is determined by the empirical threshold $\hat \lambda_B$ (the argument $\hat \rho$ is the same as we are fixing the $\hat \tau(\cdot)$ and $C(\cdot)$ functions that give rise to the treatment rule under consideration).
Our goal is to verify that the empirical threshold $\hat \lambda_B$ converges to the population threshold $\lambda_B$, and that the plug-in construction (ref) serves as a valid estimate of $V(\pi_B)$. The convenience of representing $\pi_B$ via the function $T$ is that it yields expressions of our objects of interest as functions of the threshold $\lambda_B$. To this end, we make the following assumptions on the gain and cost functions:
With suitable assumptions in place, recall from Section (ref) that there are two components needed to form an estimate of a point on the Qini curve, an empirical induced policy and an evaluation score $\widehat \Gamma_i$. As outlined in the previous paragraph, we have an exact expression for the first component, via an estimated threshold $\hat \lambda_B$. This yields a representation of the estimated policy value (ref) via
Our goal is to quantify the uncertainty in estimating $V(T(\cdot \, ; \, \hat \rho, \, \lambda_B, \, c_B)) = \mathbb{E}_{}\left[\langle T(X_i; \, \hat \rho, \, \lambda_B, \, c_B), \tau(X_i) \rangle\right]$ through the sampling variability of this plug-in estimate. This construction has two levels of approximation: using an estimated threshold $\hat \lambda_B$, arising from solving for the empirical induced policy via empirical optimization on the test set, and using an estimated score $\widehat{\Gamma}_i$ constructed on the test set in order to construct the estimate $\widehat V(T(\cdot \, ; \, \hat \rho, \, \hat \lambda_B, \, \hat c_B))$.
If we were using a fixed deterministic $\lambda_B$, the asymptotic property of $\widehat V(T(\cdot \, ; \, \hat \rho, \, \lambda_B, \, c_B))$ follows from classical doubly robust arguments. The main challenge for proving central limit theorems for Qini curves is that the budget-satisfying threshold $\hat{\lambda}_B$ (and thus the actual policy deployed on the test set) is random. So results in, e.g., athey2021policy, on test-set evaluation of fixed policies, are not directly applicable. Our idea is to argue asymptotic linearity by building on results of yadlowsky2021evaluating who prove a central limit theorem for Qini curves in the two-arm setting, by first proving asymptotic linearity of the threshold $\hat{\lambda}_B$. Then, we combine with the standard doubly robust argument to prove that $\widehat V(T(\cdot \, ; \, \hat \rho, \, \lambda_B, \, c_B))$ satisfies asymptotic linearity.
To argue about $\hat{\lambda}_B$, we note that we can view $\hat{\lambda}_B$ as an approximate Z-estimator assuming the empirical threshold $\hat{\lambda}_B$ approximately makes the cost equal to the budget $B$ on the test set. The following theorem details the argument and states a central limit theorem; the overall architecture outlining where the various estimates come from is in Algorithm (ref).
In Theorem (ref) we condition on the training set used to obtain the conditional average treatment effect function, and consider the randomness on the test set used to evaluate the induced policies. Asymptotic linearity justifies bootstrap-based inference of the Qini curves, in particular, it makes half-sampling a suitable choice for resampling Algorithm (ref) yadlowsky2021evaluating. To compute one single bootstrap replicate, rerun Algorithm (ref) on a random half-sample of units to obtain a path of policy value estimates, then interpolate this to the grid of spend values on the path computed for the full sample. As only half of the samples are passed to Algorithm (ref), the evaluation score $\widehat \Gamma_j$ for the $j$-th drawn unit is given a weight equal to 2. Algorithm (ref) outlines the steps.
This framework for evaluating multi-armed treatment rules can also be applied in observational settings where Assumption (ref) does not hold, by instead relying on “proximal” identifying assumptions tchetgen2020introduction, where we only have access to noisy measurements of the confounding variables. In this setting, similar arguments as in pmlr-v202-sverdrup23a can be applied to learn a function $\tau(\cdot)$, and then replace the score construction $\widehat \Gamma_i$ with the proximal doubly robust score of cui2020semiparametric.
There is a wide variety of strategies available to estimate conditional average treatment effects $\tau(X_i)$ that can be extended to the multi-armed setting, including athey2016recursive, kennedy2020drlearner, kunzel2019metalearners, nie2020quasi, and seibold2016model. In the empirical illustrations, we use the forest-based multi-armed treatment effect estimator of \citet*{wager2019grf}, which is based on the R-learner framework nie2020quasi. The method is available via the R package grf GRF, Rcore via the function multi_arm_causal_forest, which has built-in functionality to produce the multi-armed evaluation scores (ref). This approach estimates $\tau(X_i)$ directly using the following forest-weighted loss
where $\hat m$ are estimates of the conditional mean function marginalizing over treatment $\mathbb{E}_{}\left[Y_i \mid X_i = x\right]$, $\hat e$ are estimates of the propensity scores, and the superscript $(-i)$ indicates that the estimates for the $i$-th observation is obtained without using unit $i$ for training. The forest weights $\alpha(x)$ are adaptive nearest neighbor weights obtained by a generalized random forest wager2019grf searching for heterogeneity in the vector-valued target parameter $\tau(X_i)$.
As a synthetic illustration, we adapt the three-armed data generating process in zhou_multi_action, treating the first arm as a zero-cost control, with covariates $X_i$ identically and independently distributed on $[0, 1]^{10}$, and potential outcomes distributed according to
where $\mathbf{1_0}(X_i), \mathbf{1_1}(X_i), \mathbf{1_2}(X_i)$ indicate which region a unit belongs to:
We let the assignment probabilities for the different arms be the same,
We treat the cost for the two treatment arms as known and equal to a unit's observable pre-treatment covariates, $C_i(1) = X_{i1}, C_i(2) = 2X_{i2}$. Outcomes are observed with noise $N(0, 4)$.
To study the practical inferential properties of points on the Qini curve for multiple arms, using flexible machine learning estimators, we calculate coverage of 95% confidence intervals for $Q(B)$. We first fix a $\hat \tau(\cdot)$ function estimated on a training set with $n=10000$. We consider ten points $B = \{0.05, 0.10, 0.15, 0.20, 0.25, 0.30, 0.35, 0.4, 0.45, 0.5\}$ on the Qini curve, then on a test set with size $n=\{1000, 2000, 5000, 10000\}$ compute the policy $\hat \pi_B$, estimate doubly robust scores $\widehat \Gamma$, then calculate coverage of the estimated $Q(B)$ using bootstrapped standard errors. The results in Table (ref) show the mean empirical coverage of this procedure over $1000$ Monte Carlo repetitions. In Appendix (ref) we repeat this exercise, but where we form the nuisance estimates needed to construct the multi-armed evaluation score (ref) via boosting instead of random forests.
Our proposed method can be used to compare different targeting rules in two ways. A first use case is as a tool for practitioners to quantify the benefit of employing more arms as presented in, e.g., Figure (ref). A second use case is as a tool for practitioners to quantify how much benefit there is to treatment targeting. Addressing this use case involves constructing a suitable baseline policy $\bar \pi_B$ that ignores covariates, and then quantifying the value of treatment targeting via a difference in Qini curves. In the case of only a single treatment arm, the policy that ignores covariates is simple to compute, as it for a given budget amounts to treating some fraction of the population, and the value of this policy is simply a fraction of the average treatment effect of the arm. With more than one treatment arm, $\bar \pi_B$ needs to take into account the average treatment effect and average costs of the $K$ arms, which motivates the following definition.
Intuitively, this policy collapses all the information from the $X_i$-specific convex hulls to the single convex hull traced out by $\bar \tau$ and $\widebar C$. For a given budget, it splits the budget between two consecutive arms on the convex hull. Computing the value of this policy is straightforward by using Algorithm (ref) on the single convex hull traced out by $(\bar \tau$, $\widebar C)$ and evaluating it with $\widehat \Gamma_i := 1/n \sum_i \widehat \Gamma_i$.
To shed light on how to address the two targeting use cases mentioned above, Table (ref) presents an overview of different policy objects that arise when there are three treatment arms available. The traditional Qini curve for a single treatment arm allows for comparisons between rows and columns in the first three rows. For example, using the simplified notation in Table (ref), $Q_1 - Q_2$ is the value of targeting with arm 1 over arm 2; and $Q_1 - \widebar Q_1$ is the value of optimally allocating arm 1 based on covariates vs. spending the same budget allocating arm 1 to a random subset of units, at a given budget level. Our proposed Qini curve extension to multiple arms facilitates policy value comparisons across all entries in Table (ref), for example, $Q_{1,2,3} - Q_1$ measures the value of targeting with all available arms over targeting with only arm 1.
To conduct hypothesis tests for the value of different targeting strategies, we can employ the central limit theorem in Section (ref) to construct asymptotically valid confidence intervals for the difference in policy values. To assess the value of targeting with an optimal combination of all available arms over using only one, or a subset of arms, we can employ the following pairwise comparison:
Figure (ref) provides a stylized example of what Qini curves could look like in the scenario where there, depending on budget, is a benefit to using an optimal combination of arms over just a single arm, when there are 3 treatment arms (plus a control) available. For example, at $B=2$ the difference $Q(B) - Q_1(B)$ is the vertical difference between the curve for all arms and the curve for arm 1 and indicates that optimally selecting among all available arms can yield an increase in gain of around 1.5 over only targeting with arm 1.
To assess the value of targeting based on covariates, we can employ a similar pairwise comparison:
Figure (ref) illustrates how Qini curves may look in the scenario where there is a benefit to targeting based on subject characteristics. For a fixed spend point and policy, the quantity $Q(B) - \widebar Q(B)$ measures the vertical difference between the targeting curve for all arms and one of the remaining lines, which signifies a baseline policy using all or only a single arm without targeting. Since this distance is positive, it signifies a benefit of targeting based on subject characteristics.
To verify the practical performance of the hypothesis test constructions in this Section, we revisit the simulation setup in Section (ref) and repeat the same exercise as in Table (ref), but for five different policy value comparisons with standard errors calculated via a paired bootstrap (that takes into account the correlation between curves evaluated on the same test set data). The results in Table (ref) indicate these constructions can be justified in practice.
\afterpage{\FloatBarrier}
gerber2008social conducts a multi-armed randomized controlled trial to study the social determinants of voter turnout in the 2006 US primary election, by mailing out letters of various forms. 180 002 households were randomly assigned one of $K=4$ treatment arms where arm 1 (“Civic”) tells the recipient to do their civic duty and vote. Arm 2 (“Hawthorne”) informs the recipient that their decision to vote or not is being monitored. Arm 3 (“Self”) informs the recipient about their and similar households' past voting history, and arm 4 (“Neighbors”) will let the recipient's neighbors know about their voting history. The control group receives no letter. The outcome of interest is whether a person in the household votes in the upcoming primary election. gerber2008social finds that sending out the “Neighbors” letter is the most effective at increasing voter turnout, with little evidence of heterogeneity.
This treatment arm choice is intrusive, and to characterize the tradeoff between increases in voter turnout and incurred “intrusions”, and to investigate whether targeting with less aggressive options might give similar increases in turnouts, we utilize Qini curves. The publicly available dataset from gerber2008social includes variables that are associated with election turnout, and that we use to train a $\hat \tau(\cdot)$ function using the grf estimator described in Section (ref). These covariates include age, year of birth, gender, and household size, as well as six binary variables indicating if the subject voted in the general and primary elections in the years 2000, 2002, and 2004. To evaluate policies we hold out a random half-sample of the households and use inverse-propensity weighting with the known randomization probabilities $\mathbb{P}_{}\left[W_i = k\right] = 1/9~ (k=1\ldots4)$, where the control arm $k=0$ has assignment probability $5/9$. To incorporate costs, there are many modeling approaches one might take. In this example, we denominate costs in “intrusion units” where treatment arm 1 is least intrusive with $C_i(1) = 1$, then measure costs of the remaining arms as some multiple of this.
Here, we assume arm costs of $C_i(2)=15, C_i(3)=30, C_i(4)=45$, resulting in the Qini curves shown in Figure (ref). These curves suggest a benefit of multi-armed treatment rules over single-armed ones. For example, an optimal combination of the arms can at a budget level $B=5$ yield an increase in voter turnout of $2\%$ (95% CI: $[1.2, 2.8]$) where only the least intrusive first arm (“Civic”) would yield $1\%$ (95% CI: $[0.1, 1.8]$). A paired test between the two policies at $B=5$ yields a 95% CI of $[0.5, 1.5]$ for the difference in Qini curves.
Figure (ref) compares the Qini curves from using all arms together with the non-targeting baseline policy $\bar \pi_B$, which in this case will only allocate between the non-intrusive arm 1 (“Civic) and the most intrusive but effective arm 4 (“Neighbors”). At $B=5$ a random 91% of units are assigned arm 1 and the remaining 9% arm 4 for a gain that is practically the same as for the targeting policy using all arms (95% CI for the difference $Q_{1,2,3,4} - \widebar Q_{1,2,3,4}:~ [-0.9, 0.4]$). Thus, in this application, it appears that the gains seen in Figure (ref) are not primarily due to targeting---but rather to the flexibility offered by multi-armed policies in splitting budget between one arm that is cheaper but less effective and another that is more effective but also more expensive.
We thank the Golub Capital Social Impact Lab at Stanford Graduate School of Business, and the Office of Naval Research (grants N00014-19-1-2468 and N00014-22-1-2668) for their financial support of this research. We are also grateful to Vitor Hadad and Emil Palikot for helpful feedback and to James Yang for helpful input on templatization in C++.