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.
101,040 characters · 23 sections · 57 citation commands
Individualized Policy Evaluation and Learning under Clustered Network Interference
\def\spacingset#1{ {#1}} \spacingset{1}
\spacingset{1}
\etocdepthtag.toc{mtchapter} \etocsettagdepth{mtchapter}{subsection} \etocsettagdepth{mtappendix}{none}
During the past decade, a number of scholars have studied the problem of developing optimal individualized treatment rules (ITRs) that maximize the average outcome in a target population imai:stra:11,zhang2012estimating,zhao2012estimating,swaminathan2015counterfactual,kitagawa2018should,athey2021policy,zhang2022safe. Beyond academia, these methods have played an essential role in the implementation of personalized medicine and micro-targeting in advertising and political campaigns. In addition, new methodologies have been developed to evaluate the empirical performance of learned ITRs imai:li:23.
Much of this existing policy evaluation and learning literature assumes no interference between units, i.e., one's outcome is not affected by the treatments of others. Yet, in real-world applications, such spillover effects are the norm rather than an exception. This means that there is a potential to exploit spillover effects when learning an optimal ITR by incorporating information about individuals and their network relationships. For example, assigning influential and well-connected students to an anti-bullying program may more effectively reduce the number of conflicts within a school paluck2016changing. Another example is that individuals who are at the center of the social network can spread information more widely banerjee2019using.
Despite these potential advantages, there exist key methodological challenges when learning ITRs in the presence of interference between units. First, the structure of spillover effects is often little understood. It is difficult to obtain information about people's relationships, and the existence of unobserved networks can invalidate the performance evaluation of the learned ITRs egami_2021. Second, the total number of possible treatment allocations increases exponentially, leading to the difficulty of inferring causal effects of high-dimensional treatments.
Thus, efficient individualized policy learning and evaluation require an assumption that is sufficiently informative to constrain the structure of spillover effects. At the same time, we must avoid unrealistic assumptions. In particular, many researchers assume anonymous (stratified) interference, in which spillover effects are determined by the number of treated neighbors regardless of which neighbors are treated toward_hudgens_2008,large_liu_2014,viviano2019policy. However, the way in which one unit's treatment influences another unit's outcome often depends on their specific relationship. Our goal is to relax this anonymous interference assumption by allowing for heterogeneous spillover effects for efficient policy evaluation and learning.
In this paper, we consider the evaluation and learning of individualized policies under clustered (partial) network interference sobel2006randomized,toward_hudgens_2008,eric2012. Under this setting, units are grouped into non-overlapping clusters and interference arises within each of these disjoint clusters rather than between them. In other words, the outcome of one unit is possibly affected by the treatments of the other units in the same cluster, but not by those of units in other clusters. We first focus on experimental studies where the treatment assignment probabilities are known (Sections (ref) and (ref)). We then consider observational studies, in which propensity scores are unknown and must be estimated (Section (ref)).
We propose a methodology for the evaluation and learning of individualized policies based on a semiparametric structural model. Specifically, we assume that each individual's conditional mean outcome function is additive in the treatment vector of all individuals within the same cluster. Importantly, under this additivity assumption, the proposed model uses individual-specific nonparametric functions that place no restriction on the heterogeneity of spillover effects. The model, for example, accommodates the possibility that well-connected units within a cluster have a greater influence on other units. Indeed, this semiparametric model contains as a special case the standard parametric model based on the anonymous (stratified) interference assumption.
Next, we introduce a new policy evaluation estimator that exploits the proposed semiparametric model. Our estimator, which we call the additive inverse-probability weighting (addIPW) estimator, leverages the semiparametric structural assumption of spillover effects without the need to fit an outcome model. We show that the addIPW estimator is unbiased and is more efficient than the standard IPW estimator, which makes no assumption about the structure of within-cluster spillover effects toward_hudgens_2008,liu2016inverse,tchetgen2012causal. Finally, using this addIPW estimator, we find an optimal ITR within a pre-specified policy class. Following the previous works kitagawa2018should,athey2021policy,zhou2023offline, we show that the empirical policy optimization problem can be formulated as a mixed-integer linear program, which can be solved with off-the-shelf optimization tools. Theoretically, we establish a finite-sample regret bound and show that the regret converges at the same optimal rate as the standard i.i.d. policy learning settings.
We further extend our methodology to observational studies with unknown treatment assignment probabilities. We introduce an efficient semiparametric doubly robust policy evaluation estimator under our additivity assumption. This addDR estimator is robust to estimation errors, either in the propensity score or outcome models. Leveraging results from the semiparametric literature, we establish an asymptotic regret bound that achieves a convergence rate comparable to that in the experimental setting.
We conduct simulation studies to examine the finite-sample empirical performance of the proposed methodology (Section (ref)). We demonstrate the superiority of the proposed methodology over the optimal policy learned with the standard IPW estimators. Lastly, we apply our methodology and learn an optimal ITR to increase the household-level school attendance among Colombian schoolchildren through its conditional cash transfer program (Section (ref)).
\paragraph{Related work.} Numerous scholars have studied the problem of interference between units liu2016inverse,aronow2017estimating,bass:fell:17,athey2018exact,leung2020treatment,imai2021interference,savje2021average,hu2022average,li2022random,puelz2022,gao2023causal,ambarish2023. Much of this literature, however, has focused upon the estimation of various causal effects, including spillover and diffusion effects. At the same time, others have studied policy learning and evaluation zhang2012estimating,zhao2012estimating,swaminathan2015counterfactual,kallus2018balanced,kitagawa2018should,chernozhukov2019semi,athey2021policy,jin2022policy,imai:li:23,zhou2023offline. The vast majority of this policy learning literature requires the assumption of no interference between units. In contrast to these existing works, we consider the problem of policy learning and evaluation under clustered network interference where units influence one another within each cluster.
A relatively small number of studies have addressed the challenge of interference when learning optimal ITRs. Some utilize parametric outcome models kitagawa2023should,ananth2020optimal, while others adopt an exposure mapping approach ananth2020optimal,viviano2019policy,park2023minimum. These works often impose strong functional form assumptions on the conditional mean outcome model. In particular, a vast majority of previous studies, if not all, rely on anonymous (or stratified) interference where spillover effects are assumed to be a function of the number of treated units in a cluster viviano2019policy,ananth2020optimal,park2023minimum. Our approach avoids placing these restrictive assumptions on the structure of spillover effects.
Two of the aforementioned studies are closely related to our work. First, viviano2019policy assumes anonymous interference but is able to develop an optimal policy learning methodology under a single network setting. Our methodology avoids the anonymous interference assumption, but requires a random sample of clusters from a target population. Second, like our work, park2023minimum study policy learning in clustered network interference settings. The authors consider an optimal cluster-level treatment policy that suggests the minimum proportion of treated units required within a cluster to achieve a pre-defined target average outcome level. Their methodology, however, cannot specify which individual units within a cluster should receive treatment. In contrast, we propose an individualized policy learning methodology that optimally assigns treatments to individuals based on both individual and network characteristics.
There also exists a literature on policy evaluation under clustered network interference. For example, eric2012 and large_liu_2014 study causal effect estimates under a “type-B" policy, where units independently select to receive the treatment with a uniform probability. In addition, papadogeorgou2019causal and barkley2020causal propose policy-relevant causal estimands based on a shift in parametric propensity score models. lee2022efficient introduce an incremental propensity score intervention that further relaxes these parametric assumptions. In contrast, we propose an efficient policy evaluation estimator by leveraging the semiparametric additivity assumption that places a relatively weak restriction on the structure of spillover effects. Our semiparametric model is closer to the one considered by yu2022estimating who use the model to estimate treatment effects in a design-based single network setting.
As discussed later, a fundamental challenge of policy learning and evaluation under clustered network intereference is that the treatment assignment is high-dimensional. In particular, the number of possible treatment combinations grow exponentially as the cluster size increases. The problem of policy learning and evaluation with high-dimensional treatments has been studied in different contexts. For example, Xu2023optimal examine policy learning with multiple treatments, while chernozhukov2019semi study policy learning with continuous treatments.
We begin by describing the setup and notation of individualized policy learning under clustered network interference.
Consider a setting in which observed units can be partitioned into clusters, such as households, classrooms, or villages. Let $M_i$ denote the number of units in cluster $i \in$ $\{1,2, \ldots, n\}$. For unit $j \in \{1,2, \ldots, M_i\}$ in cluster $i$, we let $Y_{ij}\in \mathbb{R}$ represent the observed outcome, $A_{ij}\in\{0,1\}$ denote the binary treatment condition assigned to this unit, and $\boldsymbol{X}_{ij}\in \mathbb{R}^p$ be the vector of $p$-dimensional pre-treatment covariates. We use $\boldsymbol{Y}_i=\left(Y_{i 1}, Y_{i 2}, \ldots, Y_{i M_i}\right)^\top $, $\boldsymbol{A}_{i}=\left(A_{i 1}, A_{i 2}, \ldots, A_{i M_i}\right)^\top $ and $\boldsymbol{X}_i=\left(\boldsymbol{X}_{i1}, \boldsymbol{X}_{i2}, \ldots, \boldsymbol{X}_{i M_i}\right)^\top$ to denote the cluster-level vectors of outcome and treatment, and the cluster-level matrix of pre-treatment covariates, respectively. Lastly, we use $\mathcal{A}$, $\mathcal{X}$, and $\mathcal{Y}$ to represent the support of $A_{ij}$, $\boldsymbol{X}_{ij}$, and $Y_{ij}$. Thus, $\mathcal{A}\left(m_i\right)=\{0,1\}^{m_i}$ is the set of all the possible $2^{m_i}$ combinations of individual-level treatment assignments within a cluster of size $m_i$.
Throughout the paper, we assume clustered network interference, also called partial interference, where interference between individuals only occur within a cluster rather than across different clusters. This assumption is widely used in the literature when units are partitioned into non-overlapping clusters sobel2006randomized,toward_hudgens_2008,liu2016inverse,bass:fell:17,liu2019doubly,imai2021interference. Under this assumption, we define the potential outcome of one unit as a function of their own treatment as well as the treatment of others in the same cluster. Formally, we let $Y_{ij}\left(\boldsymbol{a}_i\right)$ denote the potential outcome of unit $j$ in cluster $i$ when the cluster is assigned to the treatment vector $\boldsymbol{a}_i=\left(a_{i 1}, a_{i 2}, \ldots, a_{i M_i}\right)\in\mathcal{A}\left(M_i\right)$ and define the cluster-level potential outcome vector by $\boldsymbol{Y}_i\left(\boldsymbol{a}_i\right)=\left(Y_{i1}\left(\boldsymbol{a}_i\right), Y_{i 2}\left(\boldsymbol{a}_i\right), \ldots, Y_{iM_i}\left(\boldsymbol{a}_i\right)\right)^\top$. Additionally, we make the standard consistency assumption that the vector of observed outcome, i.e., $\boldsymbol{Y}_i= \sum_{\boldsymbol{a}_i \in \mathcal{A}\left(M_i\right)} \boldsymbol{Y}_i\left(\boldsymbol{a}_i\right)\mathds{1}(\boldsymbol{A}_i=\boldsymbol{a}_i)$.
Consider the cluster-level (generalized) propensity score under clustered network interference by jointly modelling all treatment assignments in a cluster, i.e., $e\left(\boldsymbol{a}_i \mid \boldsymbol{X}_i\right):=\ensuremath{\mathbb{P}}(\boldsymbol{A}_i=\boldsymbol{a}_i \mid \boldsymbol{X}_i)$. This represents the probability of observing treatment vector $\boldsymbol{a}_i \in \mathcal{A}\left(M_i\right)$ given the cluster-level covariates $\boldsymbol{X}_i\in \mathcal{X}\left(M_i\right)$, where $\mathcal{X}\left(M_i\right)$ is the support of $\boldsymbol{X}_i$ for a cluster of size $M_i$. The following assumption is maintained throughout this paper.
We first consider experimental settings, where propensity scores are known and hence Assumption (ref) is satisfied by design. In Section (ref), we extend our methodology to observational studies, in which the propensity scores are unknown and must be estimated under Assumption (ref).
Without loss of generality, assume that a greater value of outcome is preferable. Thus, we focus on learning an optimal individualized treatment rule (ITR) that maximizes the within-cluster average of outcome while allowing for possible interference between units within each cluster. Although the individual outcome of interest is aggregated to the cluster-level, the learned policy will be a function of both individual-level and cluster-level characteristics. Thus, our methodology provides guidance to policy makers about which individuals in what type of cluster should receive treatment.
We define an ITR as a mapping from the individual-level covariates $\boldsymbol{X}_{ij}$ to a binary treatment decision for an individual unit, i.e., $\pi: \mathcal{X}\rightarrow\{0,1\}$. The cluster-level vector of treatment assignment under a policy $\pi$, therefore, is given by $$\{\pi(\boldsymbol{X}_{ij})\}_{j=1}^{M_i} \ = \ (\pi(\boldsymbol{X}_{i1}),\ldots,\pi(\boldsymbol{X}_{iM_i}))\in\{0,1\}^{M_i}.$$ In practice, researchers can also specify a class of policies $\Pi$ that incorporate various constraints. For example, the linear policy class is defined as, \[ \Pi=\{\pi:\mathcal{X}\rightarrow \{0,1\}\mid \pi(X) = \mathds{1}(\gamma_0+X^\top\gamma\geq0),\quad \gamma_0\in\mathbb{R},\gamma\in\mathbb{R}^p\}. \] Other forms of policies, such as decision trees and decision tables, have also been considered athey2021policy,benm:etal:21,jia2023bayesian,zhou2023offline.
Our individualized policy learning formulation enables different treatment decisions for units within the same cluster. This potentially yields a much improved outcome and allows for individual-level cost, fairness, and other considerations. Indeed, $\boldsymbol{X}_{ij}$ may include not only the attributes of unit $j$, but also those of its neighbors or friends within the same cluster $i$, as well as cluster-level characteristics such as cluster size $M_i$ or other network attributes. It is also possible to include the interactions between these individual, network, and cluster-level characteristics, as long as the dimension of $\boldsymbol{X}_{ij}$ remains fixed.
While we allow policies to depend on any covariates at both individual and cluster levels, we impose the restriction that each individual's treatment decision does not directly depend on those of others. Thus, individualization is achieved through covariates rather than formulating a different treatment rule $\pi$ for each individual. In other words, our policy class precludes any joint treatment rules across individuals even when such policies achieve better outcomes. Although a policy class that includes joint treatment rules is more general, specifying and optimizing such a policy when the cluster size varies leads to additional parameterization and optimization challenges.
To evaluate a policy $\pi\in\Pi$, we follow existing work and focus on the population mean of the potential outcome distribution. A key departure from the literature on policy learning without interference is that we must consider how each individual's outcome depends on the treatment assignments of the other units in the same cluster. Specifically, we define the value of policy $\pi$ as:
where the expectation is taken over the super-population of clusters $\mathcal{O}$. Given a pre-specified policy class $\Pi$, we wish to find an optimal policy $\pi^\ast$ within this class that maximizes the policy value,
As mentioned above, our framework does not allow for a policy class that directly constrains joint treatment decisions across individuals. However, it is possible to discourage (or encourage) certain joint treatment decisions by incorporating a treatment cost function that depends on the treatment decisions of multiple individual units within the same cluster. For example, in Section (ref), we use a cost function that is proportional to the total number of units who receive treatment within each cluster.
Finally, we define the regret of policy $\pi$ as the difference in value between the optimal policy $\pi^\ast$ and the policy under consideration:
Our goal is to learn a policy with minimal regret within a policy class whose complexity is bounded.
Before we turn to the problem of learning an optimal ITR, we must identify and estimate the policy value $V(\pi)$ defined in Equation (ref) for any given policy $\pi$. We first show that the high-dimensional nature of treatments under clustered network interference makes the standard IPW estimator inefficient. To address this challenge, we propose a semiparametric model that imposes a constraint on the structure of spillover effects while allowing for unknown heterogeneity in how units affect one another in the same cluster. We then propose a new efficient estimator of policy value that leverages this semiparametric outcome model.
Under Assumption (ref), the policy value function in Equation (ref) can be identified as
Then, the following IPW estimator can be used to estimate the policy value $V(\pi)$,
where $\overline{Y}_i=\sum_{j=1}^{M_i} Y_{i j}/M_i$ is the cluster-level average of the observed individual outcomes. The weight for cluster $i$ is given by the reciprocal of the cluster-level propensity score.
As noted earlier, we first consider an experimental study in which the propensity score is known. Under this setting, it is straightforward to show that this IPW estimator is both unbiased and $\sqrt{n}-$consistent. Similar IPW estimators have been applied to policy learning without interference swaminathan2015counterfactual,zhang2012estimating,zhao2012estimating,kitagawa2018should. Indeed, the IPW estimator given in Equation (ref) is a natural extension of the standard IPW estimator to clustered network interference and has been used for the estimation of treatment effects in the presence of interference tchetgen2012causal,liu2016inverse,papadogeorgou2019causal,imai2021interference.
While Assumption (ref) is sufficient for causal identification, IPW estimators often suffer from a large variability when a data set is of moderate size. This issue is exacerbated in clustered network interference settings because $\boldsymbol{A}_i$ is a high-dimensional treatment vector. Because there exist a large number of treatment combinations, the probability of any treatment assignment combination can take an extremely small value, leading to a high variance. As an example, consider an Bernoulli randomization design where units are independently assigned to the treatment condition with probability $q\leq 0.5$. Then, the inverse propensity score for treating all units in the same cluster is given by $1/q^{M_i}$, with the denominator scaling exponentially in cluster size $M_i$. In practice, therefore, we may not even observe a single cluster whose treatment vector aligns with the treatment assignment under a given policy especially when the cluster size is relatively large. In such cases, the IPW estimator is not applicable as one cannot precisely estimate the policy value.
A large variance of the standard IPW estimator will negatively affect the performance of subsequent policy learning, which optimizes the empirical estimate of the value $\widehat{V}^{\text{IPW}}(\pi)$ across all policies in the policy class $\Pi$. A simulation study in Section (ref) demonstrates that a learned policy based on $\widehat{V}^{\text{IPW}}(\pi)$ can exhibit a slow rate of learning and substantially deviate from an optimal policy. An alternative is to use an efficient semiparametric estimator that is known to be asymptotically efficient and often exhibits improved finite-sample performance relative to the standard IPW estimator park2022efficient. Unfortunately, these efficient semiparametric estimators may still suffer from a large variance when the inverse-propensity weights are large.
Indeed, it is generally impossible to improve the IPW estimator without an additional assumption given that the IPW estimator has been shown to be minimax optimal (up to some constant factors) in the non-asymptotic regime wang2017optimal. This observation motivates our semiparametric modeling assumption, to which we now turn.
To reduce a large estimation variance, we propose a semiparametric model that places a restriction on the interference structure. We seek a relatively weak but informative assumption that allows for a sufficiently complex pattern of interference within each cluster, while significantly improving the efficiency of policy value estimate. Specifically, we assume that each individual's conditional mean potential outcome is linear in the treatment vector of all individuals within the same cluster.
The expectation in Equation (ref) is taken over the sampling distribution of the clusters. The additive relationship holds for all units within each cluster and is invariant to any permutation of the unit index $j$ within cluster $i$. The reason is that the coefficients $g_j^{(k)}(\boldsymbol{X}_i)$ for $k=0,1,\dots,M_i$ are completely unrestricted and can be adapted to any ordering of units. Finally, this assumption only characterizes the conditional expectation of potential outcomes given observed covariates $\boldsymbol{X}_i$ while allowing for the presence of unmeasured effect modifiers that are not confounders.
A key feature of the proposed model is that it does not restrict the degree of heterogeneity in spillover effects. This is important because how individuals affect one another may depend on their specific relationships. For example, the influence of one's close friend may be greater than that of an acquaintance. Moreover, spillover effects may be asymmetric with one person exerting greater effects on others without being influenced by them. In other words, the causal effect of one unit's treatment on another unit's outcomes can depend on the characteristics of both units and their relationship. Our model accommodates these and other possibilities by representing spillover effects with a nonparametric function that is specific to a directed relationship from one unit to another that depends on the whole cluster-level vector of characteristics.
The proposed model incorporates, as special cases, more restrictive assumptions on the structure of interference considered in the literature. For example, scholars studied the following parametric linear-in-means model liu2016inverse,liu2019doubly,park2022efficient.
A popular model based on the anonymous (stratified) interference assumption large_liu_2014,toward_hudgens_2008,tchetgen2012causal,bargagli2020heterogeneous,viviano2019policy,park2023minimum is also a special case of our model.
While the proposed model enables units to arbitrarily influence one another within each cluster, it rules out an interaction between spillover effects. For example, the effect of treating one child in a household cannot depend on whether their siblings are treated. In Section (ref), we show that the proposed model can be extended to a more complex, semiparametric polynomial model that incorporates interaction terms. Such a general model, however, may yield a highly variable estimate of policy value, worsening the performance of learned treatment rules. In Section (ref), we provide empirical evidence that the proposed model serves as a good approximation to a more complex interference structure and that the proposed estimator, introduced below, substantially outperforms the IPW estimator, which makes no structural assumption.
We now propose an estimator of policy value function that leverages the additive structural assumption (Assumption (ref)). Under this assumption, model complexity grows only linearly with cluster size $M_i$ rather than at an exponential rate. Before describing our estimator, we introduce an additional assumption about the treatment assignment mechanism that replaces Assumption (ref)(b). Specifically, we assume that treatments are assigned to individuals independently within each cluster conditional on the observed covariates.
Assumption (ref) is satisfied under a Bernoulli randomized trial, i.e., each $A_{ij}\sim \operatorname{Bern}(p_{ij})$ for $p_{ij}\in(0,1)$. The assumption implies the conditional independence of treatment assignments across individuals within the same cluster eric2012, i.e., $A_{ij}\protect\mathpalette{\protect\independenT}{\perp}\boldsymbol{A}_{i(-j)}\mid \boldsymbol{X}_i$ where $\boldsymbol{A}_{i(-j)} \in \mathcal{A}\left(M_i-1\right)$ denotes the vector of treatment indicators for all units in cluster $i$ other than unit $j$. Recall that Assumption (ref)(b) demands strong overlap for every treatment combination, which is unlikely to hold when $\boldsymbol{A}_i$ is a high-dimensional treatment vector. In contrast, Assumption (ref) only requires the individual-level propensity scores to be sufficiently bounded from zero. This means that the constant, which satisfies Assumption (ref)(b), is likely to satisfy Assumption (ref).
Under this setup, we introduce the following additive Inverse-Propensity-Weighting (addIPW) estimator of the policy value $V(\pi)$ for a given policy $\pi\in\Pi$,
where $e_j\left(a_{ij} \mid \boldsymbol{X}_i\right):=\ensuremath{\mathbb{P}}(A_{ij}=a_{ij} \mid \boldsymbol{X}_i)$ is the individual-level propensity score, and subscript $j$ emphasizes the fact that units are allowed to have different propensity score models.
The addIPW estimator is a weighted average of the cluster-level mean outcomes, where the weight of each cluster equals the sum of individual inverse propensity scores up to a normalizing constant $M_i-1$. When there is only a single unit within each cluster, i.e., $M_i = 1$ for all $i$, the estimator reduces to the standard IPW estimator under no interference settings.
Crucially, the addIPW estimator leverages the linear additive assumption of the conditional outcome regression by ensuring that the cluster-level weights scale linearly with the individual-level inverse probability weights, which are typically of reasonable magnitude. In contrast, the IPW estimator given in Equation (ref) uses the product of individual-level inverse probability weights, which tends to zero as cluster size increases, leading to a large variance.
We next show that when the propensity scores are known, the addIPW estimator is unbiased for the policy value.
Below, we provide an additional intuition for this result. First, using the law of iterated expectation and Assumption (ref)(a), we rewrite the value function under Assumption (ref) as follows,
Thus, we can estimate the value function by substituting the unknown nuisance parameters $\boldsymbol{g}_{j}(\boldsymbol{x})=\left(g^{(0)}_{j}(\boldsymbol{x}),g^{(1)}_{j}(\boldsymbol{x}),\ldots,g^{(m)}_{j}(\boldsymbol{x})\right)^\top$ with their empirical estimates.
Unconfoundedness (Assumption (ref)(a)) enables us to rewrite Equation (ref) using observable quantities. We can then view $\boldsymbol{g}_{j}(\boldsymbol{X}_i)$ given $\boldsymbol{X}_i$ as the coefficients of the treatment vector $\tilde{\boldsymbol{A}}_i:=(1,A_{i1},\ldots,A_{iM_i})^\top$ in a unit-specific OLS regression of $Y_{ij}$ on $\tilde{\boldsymbol{A}}_i$. In principle, this regression problem cannot be directly solved due to non-identifiability, as there is only one observation for the $M_i+1$ predictors. However, we can find the population solution $\boldsymbol{g}_{j}(\boldsymbol{X}_i)$ that minimizes the mean squared error (MSE), leading to the following MSE minimizer
Since the matrix $\mathbb{E}\left[\tilde{\boldsymbol{A}}_{i}\tilde{\boldsymbol{A}}_{i}^\top \mid \boldsymbol{X}_i\right]$ is a function of known propensity scores, we can directly compute it. Under Assumption (ref), this matrix is invertible and its inverse is given by,
Given that $\mathbb{E}\left[Y_{ij}\tilde{\boldsymbol{A}}_{i}\mid \boldsymbol{X}_i\right]$ is unknown, we replace it with the single realized observation $(Y_{ij},\tilde{\boldsymbol{A}}_{i})$ in Equation (ref), resulting in the following estimator,
The unbiasedness of this estimator is immediate:
Therefore, the linearity of expectation implies the following unbiased estimator of $V(\pi)$:
where $\tilde{\pi}(\boldsymbol{X}_i):=(1,\pi(\boldsymbol{X}_{i1}),\ldots,\pi(\boldsymbol{X}_{iM_i}))^\top$ is a binary treatment assignment vector under a given policy $\pi$. Finally, substituting Equation (ref) into Equation (ref) yields our estimator $\widehat{V}^{\textsf{addIPW}}(\pi)$ given in Equation (ref).
Equation (ref) shows that the addIPW estimator can also be written as a weighted average of individual outcomes based on the inverse of {\it individual-level} propensity scores. Importantly, the proposed estimator utilizes the data from a cluster whose realized treatment assignment does not agree with the policy. This contrasts with the IPW estimator given in Equation (ref) that equals a weighted average of cluster-level mean outcome using the inverse of {\it cluster-level} propensity scores, dropping any cluster whose realized treatment assignment does not match with the policy under consideration. This difference explains why the variance of the addIPW estimator is much smaller than that of the IPW estimator. As demonstrated in Section (ref), this efficiency gain in policy evaluation leads to a better performance of policy learning.
The addIPW estimator is derived by considering the unit-specific least squares regression of outcome on a treatment vector. However, rather than explicitly fitting the outcome model for estimation, it modifies the weights of the IPW estimator such that it is consistent with the semiparametric outcome model. A similar technique has been used in the previous literature for off-policy evaluation for online recommendation systems swaminathan2017off, the estimation of total treatment effect in a design-based single network interference setting cortez2022exploiting, and the estimation of average total treatment effect in bipartite network experiments harshaw2023design. In Section (ref), we provide an additional justification of the addIPW estimator by establishing its relation to the efficient semiparametric estimator under Assumption (ref).
We emphasize that the proposed unbiased estimator in Equation (ref) (as well as the generalized estimator proposed below in Section (ref)) remains valid even without the factored propensity score assumption (Assumption (ref)). Specifically, the estimator $\widehat{V}(\pi)$ remains valid so long as the experimental design matrix $\mathbb{E}\left[\tilde{\boldsymbol{A}}_{i}\tilde{\boldsymbol{A}}_{i}^\top \mid \boldsymbol{X}_i\right]$ is invertible, although its expression may differ from $\widehat{V}^{\textsf{addIPW}}(\pi)$ depending on the propensity score structure. In scenarios where the treatment assignment ensures that every low-order treatment combination for a cluster has nonzero probability, this matrix is likely to be invertible. Even if the experimental design matrix is not invertible, we can use the Moore-Penrose pseudoinverse in place of the matrix inverse, yielding an unbiased estimator.
It is possible to extend our semiparametric additive model by including interactions. Consider the following polynomial additive model,
where we use the following augmented treatment vector that contains up to $\beta$-order interactions between treatments of different units with $\beta < m_{\max}$ where $m_{\max}$ is an upper bound of $M_i$,
Under this model, $\boldsymbol{g}_{j}(\boldsymbol{x})$ represents the unknown heterogeneous effect function set whose size equals the length of $\phi(\boldsymbol{a}_i)$. We can derive an unbiased estimator for $V(\pi)$ as before,
The explicit form of this estimator can be obtained by calculating the inverse of $\mathbb{E}\left[\phi(\boldsymbol{A}_i)\phi(\boldsymbol{A}_i)^\top \mid \boldsymbol{X}_i\right]$, which contains up to the $\beta$-order product of individual-level treatment probabilities. Since directly computing the inverse of this matrix is tedious, one may obtain the weights for individual outcomes by leveraging the linearity of expectation and unbiasedness property of the estimator yu2022estimating. Appendix (ref) provides an explicit expression of the proposed estimator under the general polynomial additive model.
In principle, $\phi(\boldsymbol{A}_i)$ can be extended to a vector of at most length $\sum_{k=0}^{M_i} {M_i \choose k} =2^{M_i}$, which allows for all possible treatment interactions within a cluster of size $M_i$. Under this extreme scenario, which implies no assumption about spillover effects, the proposed estimator can be shown to be equal to the IPW estimator given in Equation (ref). In practice, however, researchers must choose the value of polynomial order $\beta$ by considering a bias-variance tradeoff cortez2022exploiting. We can further extend our model by letting $\beta$ depend on cluster size $M_i$. This approach will allow for the inclusion of fewer interactions in smaller clusters.
Our experience suggests that in most cases the linear or quadratic additivity assumption is sufficient for effective policy evaluation and learning. Formally, when the true model includes higher-order interactions, our estimator based on the linear additive assumption can be interpreted as the following approximation to the true policy value $V(\pi)$ given in Equation (ref), i.e.,
where $\boldsymbol{g}_{j}^{\text{Proj.}}(\boldsymbol{x})$ is the projection of each unit's true outcome function $\mu_j(\boldsymbol{A}_i, \boldsymbol{X}_i)=\ensuremath{\mathbb{E}}[Y_{ij}\mid \boldsymbol{A}_i, \boldsymbol{X}_i]$ onto the linear treatment vector space,
For simplicity, we assume the linear additivity semiparametric model (i.e., Assumption (ref)) throughout this paper and leave the data-driven choice of $\beta$ to future work.
We now consider the problem of policy learning. Specifically, we solve the following empirical analog of the optimization problem given in Equation (ref) using our addIPW estimator in Equation (ref),
We first measure the learning performance of $\hat{\pi}$ by deriving a non-asymptotic upper bound on the true population regret of $\hat{\pi}$ defined in Equation (ref), i.e., $R(\hat{\pi})$. We then show that the optimization problem can be solved using a mixed-integer linear program formulation.
We establish a finite-sample regret bound for $\hat{\pi}$, assuming that the propensity scores are known. In Section (ref), we extend our theoretical results to observational studies where propensity scores are unknown and must be estimated. We begin by stating the following standard assumptions.
Assumption (ref)(a) is standard in the literature. Assumption (ref)(b) restricts cluster size $M_i$ to be bounded, implying that cluster size is not too large relative to the number of clusters $n$. The proposed methodology may not perform well when the number of clusters is small. Assumption (ref)(c) restricts the complexity of the policy class $\Pi$ of interest using the concept of VC dimension vapnik2015uniform. This assumption is often made in the existing policy learning literature to avoid overfitting kitagawa2018should,athey2021policy. The assumption holds for common policy classes such as linear and fixed-depth decision trees.
Theorem (ref) provides a finite-sample upper bound on the regret, under the case of known propensity scores. The regret converges to zero at the rate of $1/\sqrt{n}$, which matches the optimal regret rate for i.i.d. policy learning kitagawa2018should,athey2021policy. Moreover, the bound linearly depends on the maximal cluster size, and is inversely proportional to the lower bound of the individual-level propensity score $\eta$. This result is distinct from the regret bound based on the standard IPW estimator given in Equation (ref), which is typically of order $O_p\left(\frac{B}{\eta^{m_{\max}}} \sqrt{\frac{\nu}{n}}\right)$. While Theorem (ref) assumes that the outcome model satisfies Assumption (ref), we find that the learned optimal policy \( \hat{\pi} \) in Equation (ref) often achieves satisfactory learning performance in practice, even when the outcome model is misspecified (see Section (ref)). In such a misspecified case, \( \hat{\pi} \) optimizes the best linear semiparametric approximation of the true value function, given in Equation (ref), reflecting an important bias-variance tradeoff in policy learning.
The above results hold for the exact solution to Equation (ref). In general, solving Equation (ref) leads to a nonconvex optimization problem, which is difficult to solve in practice. For a certain policy class, however, we can considerably simplify the optimization problem using a mixed-integer program (MIP) formulation. Such policy classes include linear decision rules, fixed-depth decision trees, and treatment sets with piecewise linear boundaries kitagawa2018should,viviano2019policy,athey2021policy,zhou2023offline.
For example, consider a linear policy rule of the following form: \[ \Pi=\{\pi:\mathcal{X}\rightarrow \{0,1\}\mid \pi(\boldsymbol{X}) = \mathds{1}(\boldsymbol{X}^\top\boldsymbol{\beta}\geq0),\quad \boldsymbol{\beta}\in\mathcal{B}\}. \] Following kitagawa2018should, we introduce binary variable $p_{ij}$ and write \[ \frac{\boldsymbol{X}_{ij}^\top \boldsymbol{\beta}}{C_{ij}}< p_{ij} \leq 1+\frac{\boldsymbol{X}_{ij}^\top\boldsymbol{\beta}}{C_{ij}}, \quad\quad C_{ij}>\sup _{\boldsymbol{\beta}\in \mathcal{B}}\left|\boldsymbol{X}_{ij}^\top \boldsymbol{\beta}\right|, \quad\quad p_{ij} \in\{0,1\}. \] Then, $p_{ij}$ is equal to one if $\boldsymbol{X}_{ij}^\top\boldsymbol{\beta}$ is non-negative and zero otherwise, i.e., $p_{ij}=\pi(\boldsymbol{X}_{ij})$. We now can write the objective function (up to some constants) as, \[ \frac{1}{n}\sum_{i=1}^{n}\overline{\boldsymbol{Y}}_{i}\sum_{j=1}^{M_i} \left( \frac{A_{ij}}{ e_j(1 \mid\boldsymbol{X}_{i})}-\frac{1-A_{ij}}{ e_j(0 \mid\boldsymbol{X}_{i})}\right)p_{ij}. \] This implies that Equation (ref) can be equivalently represented as the following mixed-integer linear program (MILP), which can be solved using an off-the-shelf algorithm:
where constants $C_{ij}$ should satisfy $C_{ij}>\sup _{\boldsymbol{\beta} \in \mathcal{B}}\left|\boldsymbol{X}_{ij}^\top \boldsymbol{\beta}\right|$.
While this MIP formulation enables exact optimization for many policy classes, solving large-scale MIP problems can be computationally demanding, especially in settings with many clusters or large cluster sizes. As a computationally scalable alternative, we also consider a smooth stochastic approximation approach. Following fang2022fairness, we approximate the binary deterministic ITR $\pi(\boldsymbol{X}_{ij})$ with a logistic function $f(\boldsymbol{X}_{ij}) = {1 + \exp(-\boldsymbol{X}_{ij}^\top \boldsymbol{\beta})}^{-1}$. This replaces the discrete decision rule with a continuous and differentiable surrogate, enabling the use of fast gradient-based optimization algorithms.
So far, we have focused on the experimental setting in which the propensity score is known. In this section, we extend our methodology to observational studies in which the propensity score is unknown and must be estimated. Consider a plug-in approach that directly replaces the true propensity score $e_j$ with its estimate $\hat{e}_j$ in the policy value estimator given in Equation (ref). It can be shown that the resulting regret of $\hat{\pi}$ depends on the estimation error of unknown propensity scores (see Theorem (ref) in Appendix (ref)). This implies that in all but the simplest cases, the plug-in approach will result in a sub-optimal rate, which is slower than $1 / \sqrt{n}$, for the learned policy $\hat{\pi}$.
Given this suboptimality of the plug-in approach, we develop alternative efficient policy evaluation and learning methods by building on chernozhukov2019semi, who studies efficient policy learning with continuous actions. Specifically, we specialize their approach and propose a doubly robust policy value estimator under our linear additive structural assumption. As shown below, this approach is robust to estimation errors of the propensity score model or the outcome regression model. Moreover, it attains the semiparametric efficiency bound under Assumption (ref), provided the estimation errors of the nuisance functions satisfy mild rate conditions. Finally, we show that the established asymptotic regret bound of the learned optimal policy based on the doubly robust estimator achieves a fast $1 / \sqrt{n}$ convergence rate.
To define the doubly robust estimator, let $\mu(\boldsymbol{a},\boldsymbol{x})= \ensuremath{\mathbb{E}}\left[\boldsymbol{Y}_{i}\mid \boldsymbol{A}_i=\boldsymbol{a},\boldsymbol{X}_i=\boldsymbol{x}\right]$ be the vector of true conditional expected outcomes in cluster $i$. Using this notation, we rewrite Assumption (ref) as,
where $\phi(\boldsymbol{a}):=(1,a_1,\ldots,a_m)^\top$ is the treatment assignment vector, and $G(\boldsymbol{x})$ is a $m\times(m+1)$ unknown function matrix of the following form, \[ G(\boldsymbol{x}):=\left(
\right)=\left(
\right). \] Following the strategy described in Section (ref), it is possible to increase the model complexity by augmenting the treatment vector with interaction terms (see Equation (ref)). For the sake of simplicity, however, we assume the linear additive model in this section.
We also define the conditional covariance matrix of $\phi(\boldsymbol{a})$ as $\Sigma(\boldsymbol{x})=\ensuremath{\mathbb{E}}[\phi(\boldsymbol{a})\phi(\boldsymbol{a})^\top\mid \boldsymbol{x}]$. The doubly robust estimator we propose below, will rely on estimates of these two nuisance functions. Notice that $\Sigma(\boldsymbol{X}_i)$ is exactly equal to the matrix $\mathbb{E}\left[\tilde{\boldsymbol{A}}_{i}\tilde{\boldsymbol{A}}_{i}^\top \mid \boldsymbol{X}_i\right]$ defined in Section (ref), except that it now involves unknown propensity scores. Due to the factorized propensity score assumption (Assumption (ref)), $\Sigma$ can be inverted, and the resulting expression is given by Equation (ref).
Based on Equation (ref), the policy value is identified as $V(\pi)=\ensuremath{\mathbb{E}}\left[ w(M_i)^\top G(\boldsymbol{X}_i) \phi(\pi(\boldsymbol{X}_i)) \right]$, where $w(M_i)=\frac{1}{M_i}\mathbf{1}_{M_i}$ are the uniform weights for averaging the outcomes of units within the cluster and $\pi(\boldsymbol{X}_i)=(\pi(\boldsymbol{X}_{i1}),\ldots,\pi(\boldsymbol{X}_{iM_i}))^\top$ is the vector of treatment assignment under policy $\pi$. We propose the following doubly-robust estimator (addDR),
where
can be viewed as an estimate of $G(\boldsymbol{X}_i)$ based on a single observation, and $ \widehat{G}$ and $\widehat{\Sigma}$ are the estimates for the nuisance quantities $G$ and $\Sigma$. Equation (ref) has a form similar to the standard doubly robust estimators in the literature, which typically consist of an outcome regression estimate plus an augmented weighted residual term. It can be easily shown that $\widehat{V}^{\textsf{addDR}}(\pi)$ enjoys a doubly robust property --- it is consistent if either of the two nuisance models is consistently estimated. Therefore, the addDR estimator is more robust to the estimation errors of propensity score and outcome regression models. In addition, if we substitute $\widehat{G}_\textsf{addDR}(\boldsymbol{Y}_i,\boldsymbol{X}_i)$ in Equation (ref) with ${G}_\textsf{addIPW}(\boldsymbol{Y}_i,\boldsymbol{X}_i)=\boldsymbol{Y}_i\phi(\boldsymbol{A}_i)^\top{\Sigma}(\boldsymbol{X}_i)^{-1} $, this policy value estimator reduces to our addIPW estimator, providing an additional justification of the proposed estimator under the experimental settings.
We give an example of constructing the addDR estimator in practice. Under Assumption (ref), the formula of $\widehat{V}^{\textsf{addDR}}(\pi)$ simplifies to
where $\overline{\boldsymbol{g}}^\top(\boldsymbol{x}):=w(m)^\top G(\boldsymbol{x})=\frac{1}{m}\sum_{j=1}^{m}\boldsymbol{g}^\top_{j}(\boldsymbol{x})$ denotes the vector of unknown function sets in the cluster-level average outcome model. Thus, in this case, the construction of the addDR estimator reduces to obtaining the nuisance estimates $\hat{\overline{\boldsymbol{g}}}(\cdot)$ and $\{\hat{e}_j(\cdot)\}_{j=1}^m$.
We mainly discuss the estimation of $\overline{\boldsymbol{g}}(\boldsymbol{x}):=\left(\overline{g}^{(0)}(\boldsymbol{x}),\overline{g}^{(1)}(\boldsymbol{x}),\ldots,\overline{g}^{(m)}(\boldsymbol{x})\right)$ and $\{e_j(\boldsymbol{x})\}_{j=1}^m$ for $\boldsymbol{x}\in\mathcal{X}$ using nonparametric sieve estimators newey1997convergence,chen2007large. Since cluster sizes $m$ vary and clusters with significantly different sizes may exhibit different behaviors, we propose stratifying the data based on cluster size and fitting the nuisance models separately for each $m$. In practice, when sample size is limited for some clusters, one can alternatively fit a universal model using cluster size as one of the covariates in the model.
We employ cross-fitting chernozhukov2018double. Specifically, we randomly split the sample of clusters into several disjoint folds such that each fold contains clusters of all cluster sizes, and the proportion of each cluster size type is nearly identical across different folds (see also Section 4.2 in park2022efficient). For each fold, we train the nuisance models on the remaining folds and predict the nuisance estimates on the held-out fold. This process is repeated for every fold, yielding nuisance predictions on the entire dataset. For simplicity, we omit explicit dependence on the folds in our notation and focus on the estimation strategy throughout this section.
We define the conditional cluster-level average outcome model as $\overline{\mu}(\boldsymbol{a},\boldsymbol{x})= \ensuremath{\mathbb{E}}[\overline{\boldsymbol{Y}}_{i}\mid \boldsymbol{A}_i=\boldsymbol{a},\boldsymbol{X}_i=\boldsymbol{x}]=\overline{\boldsymbol{g}}(\boldsymbol{x})^\top\phi(\boldsymbol{a})=\overline{g}^{(0)}(\boldsymbol{x})+\sum_{j=1}^{m}\overline{g}^{(j)}(\boldsymbol{x})a_j$. Our goal is to estimate the nonparametric functions $\left(\overline{g}^{(0)}(\boldsymbol{x}),\overline{g}^{(1)}(\boldsymbol{x}),\ldots,\overline{g}^{(m)}(\boldsymbol{x})\right)$ separately for each stratum defined by the cluster size $m$. Let $\{r_{m,k}(\boldsymbol{x})\}_{k=1}^\infty$ be a sequence of known basis functions (e.g, polynomials, splines). We impose a structural assumption on $r_{m,k}(\boldsymbol{x}_j,\boldsymbol{x}_{(-j)})$, requiring it to be permutation invariant with respect to the covariates of the remaining $(m-1)$ units in the same cluster. For example, $r_{m,k}(\boldsymbol{x}_j,\boldsymbol{x}_{(-j)})$ can be defined as a function of $\boldsymbol{x}_j$ and summary statistics of $\boldsymbol{x}_{(-j)}$ within each subset $\{(-j)\}$, such as the mean or second moment. Let $\hat{\overline{g}}_K^{(j)}(\boldsymbol{x})$ denote the estimator for $\overline{g}^{(j)}(\boldsymbol{x})$, using the first $K$ basis functions $R_{m,K}(\boldsymbol{x}_j,\boldsymbol{x}_{(-j)}):=\left(r_{m,1}(\boldsymbol{x}_j,\boldsymbol{x}_{(-j)}),\ldots,r_{m,K}(\boldsymbol{x}_j,\boldsymbol{x}_{(-j)}) \right)^\top$, given in the form of \[ \hat{\overline{g}}_K^{(j)}(\boldsymbol{x})=R_{m,K}(\boldsymbol{x}_j,\boldsymbol{x}_{(-j)})^\top \hat{\bfsym \theta}_{m,K},\quad j = 1, \ldots, m, \] where $\hat{\bfsym \theta}_{m,K}$ represents the coefficients to be estimated. We assume that the coefficient parameter \( \bfsym \theta_{m,K} \) does not depend on the unit index $j$. This assumption is reasonable when the heterogeneity of spillover effects can be fully captured by the covariates \( \{\boldsymbol{x}_j\}_{j=1}^m \) of the units. Intuitively, $\hat{\overline{g}}_K^{(j)}(\boldsymbol{x})$ provides a better approximation of ${\overline{g}}^{(j)}(\boldsymbol{x})$ as $K$ increases. Similarly, the intercept term $\overline{g}^{(0)}(\boldsymbol{x})$ is approximated using a sieve estimator $\hat{\overline{g}}_K^{(0)}(\boldsymbol{x})=R_{m,K}(\boldsymbol{x})^\top \hat{\boldsymbol{\gamma}}_{m,K}$.
Finally, we estimate ${\bfsym \theta}_{m,K}$ and ${\boldsymbol{\gamma}}_{m,K}$ by fitting an OLS regression to clusters of the same size:
where the summation term is permutation invariant. This approach eliminates the need to enumerate individual units, as the basis functions are permutation invariant with respect to the covariates of neighboring units, and the effect coefficients $\bfsym \theta_{m,K}$ and $\boldsymbol{\gamma}_{m,K}$ do not depend on $j$.
Similarly, we estimate the propensity scores $\{{e}_j(\boldsymbol{x})\}_{j=1}^m$ using (a possibly different) $K$ approximation functions $R_{m,K}(\boldsymbol{x})$. To simplify the estimation process and avoid the need to enumerate units within a cluster, we may assume a universal model for all units $j$ for clusters of size $m$:
where \( \operatorname{expit}(z) = \frac{1}{1 + e^{-z}} \) is the sigmoid function. The parameter \( \ensuremath{\boldsymbol{\tau}}_{m,K} \) is then estimated by fitting a logistic regression across all units within clusters of size $m$.
In the above example, we focus on nonparametric series estimators, which are consistent under regularity conditions. Notably, qu2021efficient also employs nonparametric series estimators for nuisance models. However, their approach assumes the conditional exchangeability of potential outcomes, which is distinct from our semiparametric structural assumption. In practice, alternative parametric or nonparametric estimators, such as matching, kernel regression, and other machine learning methods, may also be used to estimate the propensity and outcome models.
Next, we establish the theoretical properties of the doubly robust estimator while remaining agnostic to the specific method used to obtain nuisance estimates $\hat{\overline{\boldsymbol{g}}}(\cdot)$ and $\widehat{\Sigma}(\cdot)$ and simply imposing high-level conditions on their convergence rates. Throughout, we present the theoretical results for the simpler case where the nuisance estimates are trained on an independent, separate data split. However, these results qualitatively extend to the case where the cross-fitting technique is applied.
Assumption (ref) requires that the nuisance estimators $\hat{\overline{\boldsymbol{g}}}(\cdot)$ and $\widehat{\Sigma}(\cdot)$ are uniformly consistent and that the product of their mean squared errors (MSE) achieves the $o_p(1/\sqrt{n})$ rate. Such conditions have been extensively used in the semiparametric estimation literature newey1997convergence,chernozhukov2018double and can be satisfied by many machine learning and nonparametric estimators, depending on the regularity of the underlying function being estimated. In experimental studies where the true propensity scores are known, the estimated outcome model can converge to the true outcome model at any rate while still satisfying Assumption (ref).
Under Assumptions (ref) and (ref) and an additional assumption of homoskedastic error, the variance of the doubly robust estimator achieves the semiparametric efficiency bound for estimating the policy value of a given policy.
The assumption of homoskedastic error in the residual function is often seen in the semiparametric literature robinson1988root,ai2003efficient,chamberlain1992efficiency.
This result suggests that the addDR estimator can yield efficient policy value estimates in observational studies. In experimental studies where the propensity score is known, our estimator addDR can achieve a greater reduction in variance in the estimation of the policy value than addIPW estimator while maintaining unbiasedness.
Finally, we perform policy learning based on this addDR estimator: \[ \hat{\pi}^{\textsf{addDR}}:= \underset{\pi\in\Pi}{ \operatorname{argmax}}\ \widehat{V}^{\textsf{addDR}}(\pi).\] In Appendix (ref), we show that this policy optimization problem can also be formulated as a linear MIP problem, enabling the use of off-the-shelf algorithms. More importantly, we establish the asymptotic regret bound for $\hat{\pi}^{\textsf{addDR}}$, demonstrating its fast convergence rate with optimal dependence on both the sample size $n$ and the policy class $\Pi$.
The regret bound is asymptotic in the number of clusters $n$ as in the literature athey2021policy,zhou2023offline. Furthermore, it achieves regret guarantees with optimal dependence on both the sample size $n$ and the policy class complexity $\nu$, matching the fast convergence rate established in Theorem (ref) under the assumption of known propensity scores.
We conduct simulation studies to assess the finite-sample learning performance of our proposed methodology. We compare this against the performance of the oracle policy, the learned policy under anonymous interference, and the one based on the standard IPW estimator. We also examine the finite-sample performance of the proposed policy value estimators for policy evaluation.
We generate $n\in \{50,100,200,400,800\}$ clusters, and for each cluster $i$, we randomly generate cluster size $M_i\in\{5,10,15\}$ with uniform probability. For each unit $j$, we independently sample four covariates $(X_{i j 1},\ldots,X_{i j 4})$ from the standard normal distribution. We generate the treatment variable $A_{ij}$ from independent Bernoulli distributions with success probability of 0.3. Thus, our propensity score model satisfies Assumption (ref). Throughout, we assume that the propensity score is known. Lastly, we sample the outcome variable $Y_{ij}$ from the following two models.
The outcome regression model under Scenario A above satisfies Assumption (ref), while the outcome model under Scenario B, which includes interaction terms, does not.
We consider the following class of linear thresholding policies, \[ \pi(\boldsymbol{X}) = \mathds{1}(\beta_0+\beta_1X_1+\beta_2X_2+\beta_3X_3+\beta_4X_4\geq0). \] Within this policy class, we find the best policy using our proposed addIPW and addDR policy evaluation estimators. Since the propensity scores are known, we only need to train the cluster-level outcome regression model for the addDR estimator. We fit a linear regression model using all cluster-level covariates and their interaction terms with cluster-level treatments.
For comparison, we also consider optimal policies learned based on three standard IPW estimators. The first is the IPW estimator with {\it unknown interference} $\widehat{V}^{\textsf{IPW}}(\pi)$, which is given in Equation (ref) and makes no assumption about the interference structure. The second is the IPW estimator with the widely used {\it anonymous interference} assumption, denoted by $\widehat{V}^{\textsf{AnonyInt}}(\pi)$, which assumes that one's outcome depends only on the proportion of the treated units in the same cluster, $$\widehat{V}^{\textsf{AnonyInt}}(\pi)= \frac{1}{n}\sum_{i=1}^{n} \frac{1}{M_i}\sum_{j=1}^{M_i} \frac{\mathds{1}\left\{ A_{ij}=\pi(\boldsymbol{X}_{ij}), \sum_{k\neq j } A_{ik}=\sum_{k\neq j } \pi(\boldsymbol{X}_{ik}) \right\}}{ \ensuremath{\mathbb{P}}\left( A_{ij}=\pi(\boldsymbol{X}_{ij}), \sum_{k\neq j } A_{ik}=\sum_{k\neq j } \pi(\boldsymbol{X}_{ik}) \mid \boldsymbol{X}_{i}\right)}Y_{ij}.$$ The third is the standard IPW estimator with {\it no interference} kitagawa2018should, which is slightly adjusted for our cluster setting, i.e.,
For our proposed estimators and the standard IPW estimator with no interference $\widehat{V}^\textsf{NoInt}(\pi)$, we formulate the optimization problem as an MILP problem, which we efficiently solve using a stochastic approximation approach described in Section (ref).
In contrast, the estimators, $\widehat{V}^{\textsf{IPW}}(\pi)$ and $\widehat{V}^{\textsf{AnonyInt}}(\pi)$, lead to more challenging optimization problems. The former involves the cluster-level policy indicator variable, i.e., $\mathds{1}\left\{ \boldsymbol{A}_i=\{\pi(\boldsymbol{X}_{ij})\}_{j=1}^{M_i}\right\}$, while the latter involves the indicator of the number of treated neighbors within the same cluster, i.e., $\mathds{1}\left\{ \sum_{k\neq j } A_{ik}=\sum_{k\neq j } \pi(\boldsymbol{X}_{ik}) \right\}$. To address these challenges, we again apply stochastic approximation techniques. For the cluster-level policy indicator, we use the stochastic ITR approximation described above. For the anonymous interference estimator $\widehat{V}^{\textsf{AnonyInt}}(\pi)$, we smooth the treated neighbors' indicator using an exponential weighting function, where each possible number of treated neighbors $h$ is assigned a weight of $\exp \left\{-\left(h-\sum_{k\neq j }\pi(\boldsymbol{X}_{ik})\right)^2\right\}$.
We also include the oracle estimator that directly optimizes the empirical policy value based on the true outcome model given in Equation (ref), using the same stochastic approximation approach. Finally, all approximate optimization problems are solved using a gradient-based L-BFGS algorithm.
For each simulation setup, we generate 4,000 independent data sets and examine the performance of the aforementioned six estimators: the proposed addIPW and addDR estimators, the IPW estimators with unknown, anonymous, and no interference, and the oracle estimator. Since the true policy value under each learned policy cannot be easily calculated analytically, we separately obtain an additional sample of 10,000 clusters from the assumed outcome model and approximate the true policy value.
The left panel of Figure (ref) shows that under Scenario A where Assumption (ref) is met, the proposed methodology, based on the addIPW (red boxplot) and addDR (orange) estimators, outperforms policies learned based on the standard IPW estimators. Since the addIPW and addDR estimators are both unbiased in this setting, the performance of our policy learning approach converges to that of the oracle as the sample size increases. Moreover, when compared to the addIPW estimator, the addDR estimator provides additional variance reduction, further enhancing learning performance. Among the IPW estimators, accounting for unknown interference (blue) improves performance but suffers from high estimation variance, making it substantially less effective than the proposed methodology. The anonymous IPW estimator (brown), while incorporating some interference effects, introduces bias by neglecting heterogeneous spillover effects in Equation (ref). This results in the second-worst performance. As expected, the IPW estimator that ignores interference entirely (green) performs the worst. Overall, the proposed methodology outperforms the existing IPW estimators.
The right panel of Figure (ref) shows the results under Scenario B where Assumption (ref) is violated and our addIPW and addDR estimators are biased. As shown in Equation (ref), however, the proposed estimators still provide a reasonable approximation and capture a substantial proportion of the spillover effects. We find that our approach remains superior to the existing IPW estimators due to a favorable bias-variance tradeoff. While the performance gaps between the proposed estimators and the IPW estimators with unknown and anonymous interference are smaller than in Scenario A, our approach still achieves lower variance, with the addDR estimator further reducing variance compared to the addIPW estimator. As before, the IPW estimators that account for interference significantly outperform the one that ignores it, highlighting the importance of modeling spillover effects in policy learning.
Efficient policy learning relies on accurate policy evaluation. Next, we assess the finite-sample performance of the proposed estimators in estimating policy values. We compare this performance with that of the IPW estimators that account for interference. We use the same two simulation scenarios and consider the evaluation of three different policies: (i) linear policy: $\pi(\boldsymbol{X})=\mathds{1}(0.5X_1+X_2+X_3+0.5X_4\geq 2)$, (ii) depth-2 decision tree policy: $\pi(\boldsymbol{X})=\mathds{1}(X_1>0.5,X_3>0)$ and (iii) treat-nobody policy: $\pi(\boldsymbol{X})=0$.
Figure (ref) shows the results, with each plot corresponding to a different combination of policy class (rows) and a data generation scenario (columns). The results for the sample size of $n=50$ are omitted due to large variability. Overall, the proposed addIPW (red) and addDR (orange) estimators exhibit a substantial advantage over the standard IPW estimators with unknown (blue) and anonymous (brown) interference in terms of standard deviation, across the settings we have considered.
In cases where Assumption (ref) is satisfied (Scenario A; left panel), our proposed estimators and the IPW estimator with unknown interference provide unbiased estimates of the policy value. However, the addIPW and addDR estimators exhibit considerably lower variability compared to the IPW estimator with unknown interference. In contrast, when Assumption (ref) is violated (Scenario B; right panel), the proposed estimators may deviate from the true policy value due to model misspecification. The degree of bias varies across policies with the most substantial bias arising for evaluating the treat-nobody policy. Meanwhile, the IPW estimator with unknown interference remains unbiased in both scenarios. The anonymous IPW estimator, however, is biased in both settings, with variance between those of our proposed estimators and the IPW estimator with unknown interference. An exception occurs when evaluating the treat-nobody policy, where the anonymous IPW estimator exactly reduces to the IPW estimator with unknown interference.
In addition, the differences in variance between our proposed estimators and the existing IPW estimators are much greater for linear and decision-tree policies than for the treat-nobody policy. This is because the variance of a policy value estimator depends on the deviation between the baseline policy (i.e., following propensity score) and the (deterministic) policy to be evaluated.
If the true optimal policy significantly deviates from the baseline policy, the IPW estimator with unknown interference can yield a highly variable estimate of the optimal policy value. This in turn can negatively impact the downstream empirical policy optimization. This bias-variance tradeoff is evident in our findings about policy learning (Figure (ref)), where learned policies based on the proposed estimators are more robust than those based on the existing IPW estimators, even when Assumption (ref) is not met.
We illustrate our methodology by applying it to a randomized experiment from a conditional cash transfer program in Colombia barrera2011improving.
The experiment was conducted in two regions of Bogota, Colombia: San Cristobal and Suba. In each region, the researchers recruited households that have one to five schoolchildren, and within each household, the children were randomized to enroll in the cash transfer program. Specifically, the researchers stratified children based on locality (San Cristobal or Suba), type of school (public or private), gender, and grade level. While within each stratum, every child had an equal probability of receiving treatment, the treatment assignment probabilities varied across strata. The original treatment randomization probability for each stratum is known, and is on average $0.63$ for children in San Cristobal and $0.45$ for those in Suba. Since randomization was based on fine strata that include gender and grade level, almost all children within each household belong to different strata. Therefore, we can assume that the treatment assignment mechanisms for children are conditionally independent of one another and satisfy Assumption (ref).
Previous studies focused on estimating the effects of the conditional cash transfer program on the attendance rate of students. The program was designed such that enrolled students received cash subsidies if they attended school at least 80% of the time in a given month. For example, the original study estimated the spillover effects on the siblings of an enrolled student in the same household barrera2011improving. In our application, we analyze the same dataset (a total of 1010 households with 2129 students) as the one examined by park2022efficient who developed and applied semiparametric efficient estimators to estimate the direct and spillover effects of the program on school attendance rates.
In contrast to these previous studies, however, we focus on learning an optimal individualized treatment rule to maximize the average household-level school attendance rate. We consider the following linear policy class based on three pre-treatment variables: student’s grade, household's size, and household’s poverty score (with lower scores indicating poorer households): \[\pi(\boldsymbol{X}_{ij}) = \mathds{1}\{\beta_0+\beta_1\times\text{student's grade}+\beta_2\times \text{household's size} +\beta_3 \times\text{household’s poverty score}\geq 0\}. \]
In order to evaluate the performance of the learned individualized policy, we randomly split the data into $K=5$ folds $\mathcal{I}_k$, $k=1,\ldots,K$, and for each fold $k$, learn an optimal individualized treatment policy $\hat{\pi}^{(-k)}(\cdot)$ using all but the $k$-th fold data. We incorporate the cost of treatment into the objective function to ensure that the optimal treatment rule is not trivial athey2021policy. We then evaluate the the learned policy using the $k$th fold, and compute the overall empirical policy value by averaging over the resulting five estimates. Specifically, we use the following policy value estimator with a varying treatment cost $C$ ($15\%$, $20\%$ and $25\%$ of the school-attendance rate benefit, which ranges from 0 to 1).
Table (ref) presents the estimated values of the learned individualized policies based on our proposed addIPW estimator and those based on the standard IPW estimators with unknown, anonymous, and no interference. While both addIPW and addDR estimators are consistent when propensity scores are known, we exclude the addDR estimator in this application due to poor fit of the outcome model, leading to a degenerate learned policy.
We find that the proposed policy learning methodology consistently achieves the best performance across all treatment cost specifications, yielding the highest estimated policy values. In this example, since each cluster contains only a small number of units (mostly 2 or 3), the standard IPW estimator with unknown interference does not suffer from a significantly large estimation variance and performs reasonably well. As a result, its estimated policy value and the proportion of treated units (reported in parentheses) are relatively close to those of our proposed method. The IPW estimator with anonymous interference performs slightly worse, as it fails to account for heterogeneous spillover effects within clusters. In contrast, the learned policy based on the standard IPW estimator that ignores interference performs the worst in all cases, yielding the lowest policy values and treating the smallest proportion of units.
We also report the estimated coefficients of the linear policies in Table (ref), normalized by the absolute magnitude of the estimated intercept $|\hat\beta_0|$. Here, we use the entire data to learn a single policy under each methodology. We find that, regardless of costs, the optimal ITR tends to negatively depend on the student's grade and the household's poverty score, while it has a positive relationship with household's size across all methodologies. This implies that optimal policies tend to give priority to children who are in a lower grade level and reside in larger and poorer households.
However, the estimated optimal policy based on the standard IPW estimator without interference can yield qualitatively different results. For example, when the cost is 20% and 25%, the estimated coefficients for the grade level become positive, implying the opposite treatment recommendation rule. Furthermore, although the standard IPW estimator with interference yields the estimated coefficients of the same sign as those based on our methodology, its statistical inefficiency may have produced lower policy values, as shown in Table (ref).
In this paper, we propose new policy evaluation and learning methodologies under clustered network interference. We introduce the semiparametric additive effect model that flexibly captures heterogeneous spillover effects among individuals while avoiding restrictive assumptions used in the existing literature. Our proposed addIPW and addDR estimators for policy evaluation exploit this structural assumption and substantially improve statistical efficiency relative to the standard IPW estimator. Theoretically, we establish regret bounds for the learned ITR that achieve optimal rates with respect to sample size, under both known and unknown propensity score settings.
The empirical results demonstrate the importance of considering individual-level network information in the policy learning problem. Consistent with our theoretical analysis, we find that even when our assumption is violated, the proposed estimators outperform the standard IPW estimators. Thus, the proposed methodology achieves a desirable degree of bias-variance tradeoff by leveraging a structural assumption that is sufficiently informative but is not too restrictive.
An interesting future direction is to extend our methodology to more general network settings, such as incorporating weak dependencies between clusters or adapting it to a single-network setup. Our proposed semiparametric additive model could be modified to accommodate these interference structures, relaxing the current restrictive assumptions on spillover effects. While these extensions may require a different theoretical analysis framework, they would further enhance the applicability of individualized policy learning in real-world settings with complex interdependence.