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.
36,571 characters · 9 sections · 35 citation commands
Adaptive Combinatorial Allocation
\onehalfspacing
Adaptive experimentation uses information obtained in the course of an experiment in order to optimize the treatment assignment for later study participants.\footnote{We thank Daniel Privitera and Manos Perdikakis for excellent research assistance.} For example, if job seekers arrive at a job center over time, a policymaker can use the outcomes of earlier job seekers in order to improve the assignment of labor market interventions for later participants caria2020adaptive. Using this information, adaptive experimentation can for instance be used to maximize the welfare of study participants, or to inform subsequent policy choices kasy2019adaptive.
In many policy settings, however, policymakers do not simply choose between a few interventions. Instead, they need to select an entire allocation of resources among participants. These resources are typically scarce, and feasible allocations can be described by combinatorial constraints. For example, if the policymaker wants to allocate students to classrooms when classroom composition affects student outcomes graham2010measuring, she must ensure that all students are assigned to classrooms, that the capacity of classrooms is not exceeded, and that the allocation respect the demographic composition of students in the population. If the policymaker wants to allocate children to foster families when families impact the outcomes of the children, she needs to ensure that siblings are placed together and that foster homes are close to schools and family homes macdonald2019foster,robinson2019gets. If the policymaker wants to allocate tenants to social housing, she needs to ensure that housing matches the needs of tenants and respects waiting-list priorities thakral2016public,waldinger2018targeting,van2019socio. If the policymaker wants to allocate combinations of therapies to different patients in order to overcome a disease, she needs to ensure that the therapies are actually available at the appropriate time and can be combined.
Combinatorial resource constraints might make adaptive experimentation more difficult relative to the unconstrained case, as considered in the multi-armed bandit literature, since the number of possible allocations can be vast. For example, the number of ways to allocate students to classrooms grows exponentially in the number of students. This might cause both computational difficulties (requiring optimization over a large discrete space), and statistical difficulties (the expected rewards for many different allocations have to be learned). We show, however, that remarkably despite these difficulties, performance close to the unconstrained case can be achieved. In this paper we consider an adaptive allocation policy extending the idea of Thompson sampling thompson1933likelihood. This policy is close to optimal for maximizing the outcomes of experimental participants in the presence of combinatorial resource constraints.
The general setting we consider is the following. The decision-maker has access to a finite number of options (e.g., matches) but is constrained to selecting only allocations (combinations of options; e.g., matchings) that satisfy the resource constraints (e.g., a one-to-one matching). Participants arrive in batches every period. The decision-maker selects an allocation and observes the outcome of each selected option. The outcome of each option results in a reward. The decision-maker's objective is to maximize the expected cumulative rewards from all the options she picked over time; equivalently, the decision-maker aims to minimize expected regret, i.e., the expected difference between the optimal combination of options in each period. This type of setting has been called a combinatorial semi-bandit setting with linear rewards in the literature audibert2011minimax. “Combinatorial” because the decision-maker can choose combinations of options; “semi-bandit” because the decision-maker can observe the outcomes of every match, not just of the entire matching; and “linear rewards” because the objective function is the sum of the rewards of all matches made.
Our main theoretical result is a bound on the worst-case regret obtained by using Thompson sampling in our setting. Thompson sampling is a classic heuristic for standard bandit problems; it requires that each action is picked with probability equal to the posterior probability that this action is optimal. Our theoretical result is appealing for three reasons. First, the worst-case expected regret does not depend on the batch size even though the number of possible actions (i.e., allocation) grows exponentially in the batch size. Second, our bound holds in finite-samples and does not rely on asymptotic approximations. Third, our bound is prior-independent allowing for arbitrary statistical dependence across match outcomes; this is particularly relevant for matching contexts.\footnote{This contrasts with existing bounds which require prior independence across options, as discussed below.}
We apply our approach to the problem of matching resettled refugees to local communities in the United States bansak2018improving,trapp2018placement. Our data cover the placement of all refugees by HIAS, an American resettlement agency, between 2014 and 2020. Our objective is to maximize the probability of employment of refugees in the first three months after their arrival. The allocation of refugees to local communities is subject to constraints. Local communities have a quota on the total number of refugees they can resettle in a given year, and refugees who come from the same family must be placed together. The implied optimization problem is equivalent to a “multiple knapsack problem” trapp2018placement,delacretaz2019matching.
Our paper is closely related to the literature on multi-armed bandit problems. Rather than attempting to characterize analytical solutions (e.g., gittins1979bandit), we focus on analyzing properties of the well-known probability matching heuristic due to thompson1933likelihood. agrawal2012analysis and kaufmann2012thompson have shown, for the fixed parameter case, that the asymptotic bound on expected regret of the Thompson algorithm in bandit settings matches the lower bound on regret for any bandit algorithm, which was derived by lai1985asymptotically. wang2018thompson provide a distribution-dependent regret bound for the Thompson algorithm in the combinatorial semi-bandit setting; our result is distribution-free. Adaptive experimentation using the Thompson algorithm has been proposed for applications such as drug trials berry2006bayesian, recommender systems kawale2015efficient, and customer acquistion schwartz2017customer. More recently, adaptive experimentation has been deployed in field experiments in development contexts kasy2019adaptive,caria2020adaptive.
The rest of the paper is organized as follows. Section (ref) describes our combinatorial semi-bandit setting and the Thompson heuristic; Section (ref) then discusses several examples covered by this general framework. Section (ref) gives our main theoretical result and the intuition for its proof. Section (ref) covers several considerations for implementation in practice, including the choice of model and prior, methods for sampling from the posterior, and statistical inference. Section (ref) discusses calibrated simulations based on the motivating applications. Appendix (ref) provides a brief review of information theory, which is need for the proof of our main result. All proofs can be found in Appendix (ref).
We denote all random variables with capital letters (e.g., $A$) and the realizations of random variables with lower-case letters (e.g., $a$).
\paragraph{Feasible options\ and actions} The decision-maker\ has access to options\ (e.g., matches or projects) $j \in 1,\ldots,J$, but only has sufficient resources to select $M \leq J$ of these. We denote by $\mathcal{A} \subseteq \{a\in \{0,1\}^J:\, \|a\|_1 = M\}$ a collection of feasible combinations of options. $\mathcal{A}$ is a strict subset if the decision-maker\ faces additional allocation constraints. The decision-maker's action $a \in \mathcal{A}$ is a feasible combination of options.
\paragraph{Timing, potential outcomes, and observability} The program\ takes places in a finite number of periods $t = 1,\ldots, T$. In each period, there is a vector $Y_t \in [0,1]^J$ of potential outcomes, where $Y_{j t}$ is the potential outcome for option $j$ in period $t$. The vectors $Y_t$ are i.i.d. across periods. We denote the average potential outcome (or average structural function) for option $j$ by $\Theta_j$, that is, $\Theta_j=\mathbf{E}[Y_{jt} | \Theta]$. The decision-maker\ holds a prior belief over the vector $\Theta \in [0,1]^J$, where we allow for arbitrary dependence of this prior across the option s $j$.
In each period, the decision-maker\ chooses an action $A_t \in \{0,1\}^J$. If the decision-maker\ chooses action $a$, they observe the outcomes of the chosen options $j$ (the option s $j$ for which $a_j =1$), i.e., the vector \be Y_t(a) =(a_{j}\cdot Y_{j t} :\; j = 1,\ldots,J). \ee
We assume “stable unit treatment values” (i.e., no spillovers or interference) across options $j$, in the sense that $Y_{j t}$ does not depend on the chosen action $a_{j' t}$ for any $j'$. Note that this assumption is consistent with settings where $Y_{j t}$ is itself the equilibrium outcome of interactions across multiple individuals comprising an option\ $j$, as is the case for example in the applications to peer effects or matching discussed below.
Given our assumption about observability, the information available at the beginning of period $t$ is given by \be \mathcal{F}_t = \left\{ \left ( A_{t'}, Y_{t'}(A_{t'}) \right ) : \; 1\leq t' < t \right\}. \ee Throughout this paper, the subscript $t$ on $\mathbf{E}_t$ indicates that the expectation is evaluated under the posterior distribution $\mathbf{P}_t(\cdot) = \mathbf{P}(\cdot\mid\mathcal{F}_t)$, where $\mathcal{F}_t$ is the information available at the beginning of period $t$. The decision-maker\ can choose their action $A_t$ at the beginning of each period $t$ based on the information $\mathcal{F}_t$, as well as possibly based on a randomization device that is statistically independent across periods and independent of the sequence of potential outcomes $\left ( Y_t \right )_{t = 1}^T $.
\paragraph{Objective and policy}
If the decision-maker\ chooses action $a$ in period $t$, they receive a reward which is equal to $\langle a, Y_t \rangle$. Therefore, upon taking action $a$ the decision-maker's expected reward given $\Theta$, which is the same across periods $t$, equals \be R(a) =\mathbf{E}_t[\langle a, Y_t \rangle | \Theta]= \langle a, \Theta \rangle. \ee The decision-maker would like to maximize cumulative expected rewards, \be \mathbf{E}_1 \left [ \sum_{t = 1}^T R(A_t) \right ]. \ee The expectation in this expression is taken over the randomness in the choice of actions $A_t$, the sampling distribution of potential outcomes $Y_t$, and over the prior distribution of $\Theta$. Denote by $A^*$ a feasible action that maximizes the expected reward conditional on $\Theta$ (but not conditional on the vector $Y_t$), that is, \be A^* \in \operatorname*{argmax\;}_{a \in \mathcal{A}} R(a) = \operatorname*{argmax\;}_{a \in \mathcal{A}} \langle a, \Theta \rangle. \ee
The decision-maker's objective is equivalent to minimizing expected regret at $T$ \be \mathbf{E}_1 \left [ \sum_{t = 1}^T \left ( R(A^*) - R(A_t) \right ) \right ]. \ee
Solving this dynamic stochastic combinatorial optimization problem is computationally quite costly. Rather than solving it, we propose that the decision-maker\ adopt the following heuristic policy. In each period the decision-maker\ should take an action $a$ from the feasible set $\mathcal{A}$ according to the posterior probability that $a$ is optimal, that is, for each $a\in\mathcal{A}$, \be \mathbf{P}_t(A_t=a)= \mathbf{P}_t(A^*_t=a). \ee This assumption implies in particular that $ \mathbf{E}_t[A_t] = \mathbf{E}_t[A^*]. $ This heuristic approach is known as Thompson sampling, and was originally introduced by thompson1933likelihood for treatment assignment in adaptive experiments.
In the following we discuss several examples that are covered by our general framework, and thus in particular by the regret bound provided in Theorem (ref) below. These examples correspond to practically relevant policy problems. They also illustrate how various combinatorial allocation problems that have been studied in the literature fit into our framework, such as assignment to peers, one-to-one matching, many-to-one matching, knapsack problems, etc.
For each of these examples, several options might correspond to same underlying parameter, so that $\Theta_j = \Theta_{j'}$ with prior probability $1$, for some $j, j'$. In the case of one-to-one matching, for instance, each matched pair corresponds to one option, but $\Theta_j$ is the same for all matched pairs $j$ with the same observed covariates on both sides of the match.
We next state our main theoretical result. This result provides tight worst-case guarantees for the expected regret of Thompson sampling in our setup.
\paragraph{Discussion of Theorem (ref)} Several features of the regret bound in Theorem (ref) are worth emphasizing. First, this bound is a finite sample bound. There is no large sample limit and no remainder term. Second, this bound does not depend on the prior distribution for $\Theta$ in any way. Furthermore, it allows for prior distributions with arbitrary statistical dependence across the components of $\Theta$, as required by our motivating examples. Third, this bound implies that Thompson sampling in our setting achieves the efficient rate of convergence for regret: As shown by audibert2014regret, the minimax regret in our setting grows at a rate of $\sqrt{J T M}$, up to logarithmic terms.
Theorem (ref) bounds the worst case expected regret across all possible priors, summed across units. To get the worst case expected regret per unit, divide this expression by $T M$, which yields the bound $\sqrt{J \cdot \left [ \log\left ( \tfrac{J}{M} \right ) +1 \right ] \big / \left ( 2 T M \right ) }$. This bound goes to $0$ at a rate of $1$ over the square root of the sample size, that is, at a rate of $1/\sqrt{T M}$. The theorem furthermore shows that this worst case expected regret grows, as a function of the number of possible options $J$, like $\sqrt{J}$ (neglecting the logarithmic term). Remarkably, worst case regret does not grow in the batch size $M$. This is despite the fact that the setup of Section (ref) allows for action sets of size ${J}\choose{M}$. For comparison, application of the worst case regret bound for Thompson sampling in bandits with dependent arms provided by Proposition 3 in russo2016information yields a much larger bound which grows in proportion to $\sqrt{{J \choose M} \log {J \choose M} }$. Instead, the regret bound in Theorem (ref) grows like that for a simple multiarmed bandit with $J$ arms.
\paragraph{Intuition for the proof of Theorem (ref)}
The proof of Theorem (ref) is provided in Appendix (ref). This proof builds on several definitions and standard results from information theory which are reviewed in Appendix (ref). Here we just sketch some of the key steps in our proof.
First, we use Pinsker's inequality in order to relate expected regret to the information about the optimal action $A^*$ provided by observations, where information is measured by the KL-distance of posteriors and priors. Pinsker's inequality implies, for Bernoulli random variables $B$ and $B'$, that $(\mathbf{E}[B] - \mathbf{E}[B'])^2 \leq \tfrac{1}{2} D_{KL}(B,B').$ Lemma (ref) applies Pinsker's inequality to terms showing up in the definition of expected regret which are of the form $\mathbf{E}_t[\Theta_j | A^*_j = 1] - \mathbf{E}_t[\Theta_j]$. This use of Pinsker's inequality is at the core of the proofs in russo2016information.
Second, following some of the ideas introduced in bubeck2020first, Lemma (ref) relates the KL-distance to the entropy of the events $A^*_j = 1$. The combination of these two Lemmas allows to bound the expected regret for option $j$ in terms of the entropy reduction for the posterior of $A^*_j$.
Third and lastly, Lemma (ref) shows that the total reduction of entropy across the options $j$, and across the time periods $t$, can be no more than the sum of the prior entropy for each of the events $A^*_j = 1$, which is bounded by $M \cdot \left [ \log\left ( \tfrac{J}{M} \right ) +1 \right ] $. The proof of Theorem (ref) then combines these three Lemmas.
\paragraph{Relationship to the literature} Our proof builds on the information theoretic approach pioneered by russo2016information (in particular Lemma 1 and 2 as well as Proposition 6 therein) and some variations of this approach proposed by bubeck2020first (in particular Lemma 13). Despite the close relationship to their arguments, Theorem (ref) differs from the bounds provided in these papers as follows. The closest result in russo2016information is their Proposition 6. Their result, however, requires statistical independence of the prior and posterior distribution for the components of $\Theta$ at all times $t$. By contrast, Theorem (ref) above allows for arbitrary dependence. This is especially relevant for the matching setting, where independence in the prior distribution would be quite hard to justify.
The closest result in bubeck2020first is their Theorem 21. Their result is asymptotic, rather than providing an exact finite sample bound. The main interest of bubeck2020first is an asymptotic refinement of regret bounds that scales in the best achievable regret, allowing for the latter to converge to $0$; this is something which our result does not aim to do.
In order to achieve good performance in practice, our proposed procedure relies on specifying an appropriate model for the data generating process, and an appropriate prior distribution for the underlying parameters. We generally advocate for the use of default priors that are diffuse and symmetric across types, while incorporating reasonable assumptions about the dependency structure between different options $j$.
Table (ref) proposes some variants of models and priors for matching settings, covering our leading motivating examples, including those used in our empirical applications. For each of these variants, we assume that the options $j$ consist of two-sided matches between types $u_j$ and types $v_j$. For each possible match (option), the potential outcomes $Y_{j t}$ are drawn from some distribution with mean $\Theta_{j}$. We need to specify this distribution of $Y_{j t}$, as well as a joint prior distribution of the parameters $\Theta_{j}$ across $j$.
Each of these models assumes that the option-effect $\Theta_{j}$ is determined by the sum of type-effects ${\Gamma^u}_{u_j}$ and ${\Gamma^{v}}_{v_j}$, plus an interaction effect ${\Gamma^{u v}}_{u_j, v_j}$. For continuous outcomes, we assume that $\Theta_{j}$ is directly given by this sum. For binary or discrete outcomes, we assume that $\Theta_{j}$ is given by the logit link function applied to this sum.
For the model for outcomes with discrete bounded support, the distribution of $Y_{j t}$ is governed by the mean parameter $\Theta_{j}$ as well as a dispersion parameter $m$. The latter is necessary to allow for larger dispersions relative to a more restrictive Binomial model, which might put excessive weight on the information content of single observations.
In order to implement Thompson sampling, we need to sample from the posterior for $\Theta$. This posterior is also relevant for statistical inference on parameter values. Such inference is often a secondary goal, in additional to the primary goal of maximizing participant outcomes. Such inference might be Bayesian, using the same posterior distributions that go into the assignment algorithm. Alternatively, such inference might be based on permutation tests, as described below.
\paragraph{Markov Chain Monte Carlo and Bayesian inference} For hierarchical priors, such as those discussed in Section (ref), posterior distributions are not available in closed form, in general. We can, however, sample from the posterior for $\Theta$ using Markov Chain Monte Carlo (MCMC) methods. Such MCMC methods only require us to specify the posterior up to a multiplicative constant (typically, up to the denominator of the posterior density, which is given by the marginal density of the observed data). MCMC methods are based on constructing a Markov Chain which converges to an ergodic distribution that is given by the posterior of interest. There are various ways of constructing such Markov Chains; one of them is Hamiltonian Monte Carlo. In our applications, we sample from the posterior using Hamiltonian Monte Carlo as implemented in the software STAN carpenter2017stan.
Let $\hat \Theta_t$ be a draw from the posterior given $\mathcal{F}_t$ generated by MCMC, after a sufficiently long warm-up period. Choose \be A_t = \operatorname*{argmax\;}_{a \in \mathcal{A}} \langle a, \hat \Theta_t \rangle. \ee Then $A_t$ follows the distribution required for Thompson sampling, that is, it satisfies Equation (ref).
In order to form $1-\alpha$ credible sets for the parameters $\Theta_j$ given the history $\mathcal{F}_t$, sample a large number of draws $\hat \Theta_t$ from the posterior, and form a credible interval based on the $\alpha/2$ and $1-\alpha/2$ quantiles of $\hat \Theta_{j, t}$ across these draws.
\paragraph{Randomization inference}
An alternative to Bayesian inference is randomization (permutation) inference. In the context of treatment effect estimation, randomization inference can be used to test the null hypothesis that treatment does not affect any outcome, so that for instance $Y_i^1 = Y_i^0$ for all units $i$ and treatment value $0,1$.
In the context of our setting, we need to modify this null hypothesis. Permutation inference requires that we specify the counterfactual outcome vector $Y_t^0(a)$ for any counterfactual action $a \in \mathcal{A}$ under the null hypothesis $H^0$, given knowledge of $Y_t(A_t)$ for the realized action $A_t$. In many cases of interest, there might be more than one plausible way to specify such a null hypothesis and the corresponding counterfactual outcome vectors.
To illustrate, consider the case of one-to-one matching (of refugees to local communities, say), where each option $j$ corresponds to a match of a refugee family to a local community. We could formalize the null hypothesis that “the matching does not matter” in two different ways. We could consider the hypothesis that refugee outcomes are the same, no matter which community they are allocated to. Or we could consider the hypothesis that outcomes in a community are the same, no matter which refugees are allocated to be there.
Given some specification of counterfactual outcomes, we can sample counterfactual histories $\tilde \mathcal{F}_t$ by re-running the Thompson sampling algorithm iteratively. In each period $s$, draw $\tilde \Theta_{t'}$ and the corresponding $\tilde A_{t'}$ from the posterior given $\tilde \mathcal{F}_{t'}$. Impute a counter-factual outcome vector $Y_{t'}^0(\tilde A_{t'})$, based on the null hypothesis to be tested. Update the history $\mathcal{F}_{t'}$ by adding $\tilde A_{t'}, Y_{t'}^0(\tilde A_{t'})$, and iterate for the next period. Once $t'=t$, calculate a realization of the test-statistic as a function of $\tilde \mathcal{F}_t$. Repeat this process to generate a sampling distribution of the test-statistic, and corresponding critical values and p-values for testing the null hypothesis under consideration.
The United States has historically been the world's largest destination of resettled refugees, with 78,340 admitted in 2016. There is a lot of evidence that the initial match between refugees and local communities dramatically affects the socioeconomic outcomes of refugees bansak2018improving,trapp2018placement. However, local community capacities are tightly regulated by the US government. As a result, one US resettlement agency (HIAS) optimizes the placement of the resettled refugees using its recommendation system called Annie MOORE. However, Annie's estimates of refugee employment are static and come from a LASSO regression run annually trapp2018placement.
Here, we draw on the data used by Annie MOORE in order to run calibrated simulations for our proposed procedure subject to realistic constraints, hoping to inform actual refugee placement by Annie MOORE in the future.
\paragraph{Data} Our data covers all refugees resettled by HIAS between October 2005 and September 2020. There were a total of 37,149 refugees that constitute 15,523 cases (i.e., families). We focus on the employment of primary applicants in each family. For each primary applicant in the family, we observe three binary variables: whether the applicant is of prime working age (25-54), their gender, and whether they are English-speaking. We also observe the family size, and the affiliate where the family was resettled. We furthermore observe whether the primary applicant had any US ties. Applicants with US ties (e.g., US resident friends or family) are automatically resettled to the community where their US ties reside. Applicants without US ties can be resettled to any of the communities where HIAS operates. Finally, we observe whether or not the primary applicant was employed within 90 days of arrival. This is a key metric used by the State Department to assess the performance of American resettlement agencies.
There are 57 affiliates in our data. We drop any affiliate with fewer than 150 resettled cases over the whole period under consideration, leaving us with 17 affiliates.\footnote{In their analysis, trapp2018placement also pool some affiliates because of small numbers of observations.} All affiliates are anonymized. Based on the available observables, we classify refugees into 8 “types” $u$, while treating each of the 17 affiliates as a separate “type” $v$. This means that there are $8 \cdot 17 = 136$ parameters (probabilities of finding employment) that we might wish to learn.
As noted above, the affiliates have a limited capacity in hosting refugees, where capacity is the total number of resettled people (primary applicants and their family members). The capacities of affiliates can sometimes change throughout the course of the year. For our simulations, we conservatively set the available annual capacities to be 110% of the total number of refugees without US ties actually resettled to each affiliate in a given year.\footnote{Resettlement agencies are allowed to exceed their official capacity by 10% without further approval; however, in practice, agencies occasionally have to seek approval for capacity extensions and reductions because of stochastic refugee flows. Dynamic capacity management is beyond the scope of this paper.} The monthly quota for each affiliate is therefore 110% of its annual capacity divided by 12.
\paragraph{Simulation design} Our simulated matching process works as follows. For each month $t$ in the available data, we consider all the refugees who were resettled by HIAS in this month. We match the refugees with US ties to their actual affiliates. For all the refugees without US ties, we match them to affiliates using the Thompson algorithm discussed above. This matching has to satisfy the capacity constraints of affiliates described above, and the varying sizes of refugee families. Solving for the optimal matching for a given draw $\hat \Theta$ from the posterior defines a so-called multiple knapsack problem. Any leftover capacity and any unmatched refugees without US ties are carried over to the next month.
We then impute counterfactual outcomes for the refugees allocated using the Thompson algorithm. based on calibrated parameter values $\Theta_0$. These calibrated parameter values are set to the posterior mean for the Bayesian hierarchical model for binary outcomes described in Section (ref).
\paragraph{Results}
WORK IN PROGRESS.