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.
81,843 characters · 16 sections · 31 citation commands
Optimal sequential treatment allocation
A policy maker must often assign treatments gradually as the individuals to be treated do not arrive simultaneously. For example, people become unemployed gradually throughout the year and assignment to one of several unemployment programs is often made shortly thereafter. Similarly, patients with too high blood pressure arrive gradually to a medical clinic and the doctor assigns one of several treatments to each of them. The policy maker or doctor gradually accrues information by observing the outcome of previous treatments prior to the next assignment. Throughout the paper we shall use these two examples as illustrations of our results and be particularly concerned with how treatments should be assigned in order to maximize welfare. In doing so one faces a tradeoff between exploring which treatment works best and exploiting the information gathered so far from previous assignments in order to assign the best treatment to as many individuals as possible.
The above setup is in stark contrast to typical estimation of treatment effects where one presupposes the existence of a data set of a certain size $N$ (perhaps obtained from a randomized control trial). Thus, in the typical setting, the size and composition of the data set are determined prior to estimation. Based on this given data set, treatment effects are estimated and assignments are made. We consider the case where the observed data that the treatment assignments must be based on is a part of the policy in the sense that it depends on the previous choices of the the policy maker. Thus, the policy maker enters already in the design phase of the treatment program and can adjust the experiment as data accumulates. In other words, he decides how to draw the sample and thus its composition by the allocations he makes. Furthermore, the sample size itself may be a random variable unknown to the policy maker as he does not know a priori how many individuals will become unemployed in the course of the year that the program is scheduled to run, and the exact shape of a good treatment rule will depend on the expected number of individuals to be treated: if many individuals are expected to become unemployed in the course of the year it might be beneficial to experiment relatively more in the beginning to harvest the benefits of increased information later on.
We contribute by considering a setting where the desirability of a treatment cannot be measured only by its expected outcome. A sensible welfare function must take into account the risk of a treatment. For example, it may well be that drug A is expected to lower the blood pressure slightly more than drug B but A might still not be preferred if it is much more risky than B. In this paper we shall measure the risk of a treatment by its variance and take into account that mean as well as variance may be relevant in determining the most desirable treatment. Thus, we push beyond the classic focus on first moments (expected treatment outcomes) and take into account that also second moments (uncertainty about treatment outcome) play an important role in determining the most desirable treatment. We also indicate how one may incorporate more than two moments into the welfare function thus allowing welfare functions that allow for policy makers to be, say, skewness averse. This underscores the central idea of the paper: to go beyond focusing solely on the location (expected value) of the outcome distribution of treatments but also to focus on the shape as measured by higher moments. We study a treatment policy, which we call the sequential treatment policy, and show that it achieves the minimax optimal regret compared to the infeasible policy that knows in advance which treatment is best for each individual and assigns this. An upper bound on the expected number of times that the sequential treatment policy assigns any suboptimal treatment is provided as well. This is an important ethical guarantee since it ensures that the minimax optimal regret is not obtained at the cost of wild experimentation or maltreatment of many individuals in order to achieve a greater cumulative welfare in the long run.
In addition, we contribute by studying the properties of the sequential treatment policy when the outcomes of previous treatments are observed only with delay. In a medical trial, for example, one may choose to delay the measurement of the outcome of the treatment in order to obtain more precise information of the effect of a certain drug. As it takes time for the effect of a drug to set in the delaying of the measurement can lead to more precise information on the effect of the drug. The price of this delay is that less information is available when treating other patients prior to the measurement being made. Thus, there is a tradeoff between obtaining imprecise information quickly (by making the measurement shortly after the treatment) and obtaining more precise information later (by postponing the measurement). We quantify this tradeoff and indicate the optimal delay (when this is a choice variable) and establish that our policy is guaranteed to deliver high welfare even in this setting.
Furthermore, we allow for a setting where individuals, and thus information, may arrive in batches. For example, people do not get assigned to an unemployment program on the exact day they become unemployed as new programs might only start once a month. Thus, people are pooled and as a result data arrives in batches. This setup strikes a middle ground between the bandit framework where individuals arrive one-by-one and the classic treatment effect framework where a data set of size $N$ is presupposed. In our setting we also allow $N$ to be an unknown random variable which is important as the length of the treatment period may not be known at the beginning of the treatment period.
Our approach easily accommodates practical policy concerns restricting the type of treatment rules that are feasible. For instance, the policy maker may want rules that depend on the individual's characteristics in a simple way due to political or ethical reasons.
It should be noted that the goal of this paper is not to test whether one treatment is better than the other ones at the end of the treatment period. This would amount to a pure exploration problem where the sole purpose of the sampling is to maximize the amount of information at the end of the sample without regard to the welfare of the treated individuals. While this problem is interesting in its own right it is often not viable for ethical reasons in the social sciences. Instead, the problem under investigation here is how to sample (assign treatments) in order to maximize the expected cumulative welfare of the treated individuals. That being said, we also propose a policy, the out-of-sample policy, which indicates how treat individuals after running the sequential treatment policy in the initial period. This is done in the setting where the total number of treatments is known from the outset. The out-of-sample policy is guaranteed to yield high welfare thus indicating that a lot has been learned about the individual treatments in our welfare maximization problem even though maximizing information was not the objective. Heuristically, the reason for non-negligible learning from observing the outcomes of the sequential treatment policy even when its purpose is to maximize welfare is that it has to experiment with the available treatments to make sure that one is assigning the best one often. Thus, learning is build into the welfare maximization of the initial period.
Our paper is related to two strands of literature: the literature on statistical treatment rules in econometrics and the one on bandit problems on sequential allocation. In the former Manski2004 proposed conditional empirical success (CES) rules which take a finite partition of the covariate space and on each set of this partition dictate to assign the treatment with the highest sample average. When implementing CES rules one must decide on how fine to choose the partition of the covariate space and thus faces a tradeoff between using highly individualized rules and having enough data to accurately estimate the treatment effects for each group in the partition. Among other things, Manski2004 provides sufficient conditions for full individualization to be optimal. The tradeoff between full individualization of treatments and having sufficient data to estimate the treatment effects accurately is also found in our dynamic treatment setting.
Stoye2009 showed that if one does not restrict how outcomes vary with covariates then full individualization is alway minimax optimal. Thus, if age is a covariate, information on treatment effects for 30 year olds should not be used when making treatment decisions for 31 year olds. This result relies on the fact that without any restrictions on how the outcome distribution varies with covariates, this relationship could be infinitely wiggly such that even similar individuals may carry no information about how treatments affect the other person. Also, as the support of the covariate vector grows, these “no-cross-covariate" rules become no-data rules as for many values of the covariates there will be no observations. This is certainly the case for continuous covariates. Our assumptions rule out such wiggliness as no practical policy can be expected to work well in such a setting.
Furthermore, our work is related to the recent paper by Kitagawa2015 who consider treatment allocation through an empirical welfare maximization lens. The authors take the view that realistic policies are often constrained to be simple due to ethical, legislative, or political reasons. Using techniques from empirical risk minimization they show how their procedure is minimax optimal within the considered class of realistic policies. Our approach is related to theirs in that we also allow the policy maker to focus on simple rules in the dynamic framework. Furthermore, athey2017efficient have used concepts from semiparametric efficiency theory to establish regret bounds that scale with the semiparametrically efficient variance.
Other papers on statistical treatment rules in econometrics focusing on the case where the sample is given include chamberlain2000econometrics, dehejia2005program, hirano2009asymptotics, bhattacharya2012inferring, stoye2012minimax, tetenov2012statistical and kasy2014using.
The most important distinguishing feature of our work compared to the classic literature on statistical treatment rules is that we are working in a sequential setting where the individuals to be treated arrive gradually. Thus, we do not have a data set of size $N$ at our disposal from the outset based on which the best treatment must be found. The sequential setting poses new challenges such as not maltreating too many individuals in the search for the best treatment and how to handle data that arrives in batches as well as treatment outcomes that only are observed with delay. We shall address all of these in this work. Consequently, our paper is also related to the vast literature on bandit problems. In the classic bandit problems one seeks to maximize the expected cumulative reward from pulling arms with unknown means one by one. In a seminal paper Robbins1952 introduced a class of bandit problems and proposed some initial solutions guaranteeing that the average reward will converge to the mean of the best arm.
Broadly speaking, bandit problems can be classified into three categories based on the nature of the reward process: i) stochastic bandits where the arms are iid across time, ii) the markovian setting where the state of the arms changes according to a Markov process, iii) the adversarial setting in which nature chooses (an adversarial) distribution of rewards at the same time as the experimenter pulls an arm. In this work we focus on the stochastic setting as patients to be treated or unemployed individuals to be assigned to job training programs do not generally coordinate their effort against the doctor or policy maker in an adversarial manner. In the medical example in particular, the interests of the doctor and patient are often well-aligned. Furthermore, the markovian setting is concerned with infinite time horizons amounting to infinitely many treatments being made. In this work we are interested in the case where we have to make a finite, albeit often unknown, number of treatments. That being said, we certainly believe that also the adversarial setting or the markovian setting can be of interest to study in the context of sequential treatment allocation problems. In the latter setting, the Gittins index, gittins1979bandit, is the most famous procedure.
The first paper which considered bandit problems where one observes a covariate prior to making an allocation decision was woodroofe1979one who made a parametric assumption on how covariates affect outcomes. The first work allowing covariates to affect the distribution of outcomes in a nonparametric way was yang2002randomized. For an excellent review of the literature on bandit problems we refer to bubeck2012regret who also elaborate more on the three fundamental settings and give further references. From an algorithmic point of view our work is related to CovBandit who introduced a successive elimination (SE) policy of suboptimal arms. Their policy is in turn related to the work of even2003action.
Compared to the existing literature on bandits we contribute on several fronts. Most notably, we introduce potentially non-linear welfare functions depending not only on the mean treatment outcome but also on the variance of the outcome. Allowing the uncertainty (variance) of the treatment outcome to enter the welfare function is important as a policy maker may not only target the treatment with the highest expected outcome. It is likely that he also takes into account how risky the treatment is. This is a non-trivial extension of the classic bandit (and treatment) setting which has focused only on means and allows us to capture the dynamic risk-return tradeoff facing a policy maker when deciding which treatment to assign. From a technical point of view this is challenging since one must control the finite sample estimation error of estimators of the first and second moments of the treatment outcome distribution as well as non-linear transformations thereof i order to provide finite sample performance guarantees of our treatment policy. In addition, we consider the case where the outcome of treatments is only observed with delay. To the best of our knowledge, the consequences of delay and how to optimally deal with it have not been studied yet. As explained delay creates a tradeoff between obtaining imprecise information quickly and obtaining precise information later. This makes the sequential treatment problem more challenging as the policy maker must now also choose when to make a measurement in addition to which treatment to assign. Third, we provide upper bounds on the regret of the sequential treatment policy for any choice of grouping individuals. These upper bounds depend on the geometry of the chosen grouping. Allowing for groups of general shapes is important to inform policy makers about how exactly their choice of grouping individuals affects regret since the choice of groups achieving minimax regret may not always be politically or ethically feasible. Fourth, we provide upper bounds on the expected number of suboptimal treatments our policy assigns. Fifth, we quantify how much has been learned in the course of the treatment period by proposing the out-of-sample policy. Our regret bounds show that even though we seek to maximize the cumulative welfare by our treatment assignments enough is learned in order to guarantee a low regret out of sample.
The multi-armed bandit setup has also been used in the context of social learning and strategic experimentation in the works of e.g. bolton1999strategic, keller2005strategic and klein2011negatively. Here several agents have to choose the amount of experimentation (pulling a risky arm) taking into account that the information obtained will be available to all other players as well. While the agents have an incentive to free ride they also want to experiment in order to bring forward the time where extra information is generated.
The term optimal sequential treatment allocation in the bandit framework as discussed in this paper should not be confused with similar terms in the medical statistics literature. In that literature adaptive treatment strategies/adaptive interventions and dynamic treatment regimes refer to a setting where the same individual is observed repeatedly over time and the level as well as the type of the treatment is adjusted according to the individual's needs. References to this setting include robins1997causal, lavori2000flexible, murphy2001marginal, murphy2003optimal and murphy2005experimental.
The remainder of the paper is organized as follows. Section (ref) considers a setting where the treatment outcomes do not depend on observable individual specific characteristics. Next, Section (ref) introduces covariates and establishes regret bounds for the sequential treatment policy. When grouping individuals in a specific way, these bounds are minimax optimal. It is also shown that the expected number of sub-optimal assignments increases slowly and we investigate how to handle discrete covariates. Section (ref) investigates the effect of outcomes being observed with delay. Finally, Section (ref) concludes while (ref) contains all proofs.
We begin by considering the sequential treatment problem where the distributions of treatment outcomes do not depend on observable individual specific characteristics. While this setting may often be too restrictive, the regret bounds established in this section will be used as ingredients in establishing the properties of our treatment rules in the setting where covariates are observed on each individual prior to the treatment assignment.
Consider a setting with $K+1$ different treatments and $N$ assignments\footnote{We consider a setting with $K+1$ treatments for purely notational reasons since it is the number of suboptimal treatments, $K$, which will enter our regret bounds as well as many of the arguments in the appendix.}. $N$ is a random variable whose value need not be known to the policy maker at the beginning of the treatment assignment problem. For example, at the beginning of the year, he does not know how many will become unemployed during the year. Let $Y_t^{(i)}\in[0,1]$ denote the outcome from assigning treatment $i,\ i=1,...,K+1$ to individual $t,\ t=1,...,N$ where the subscript $t$ indicates the order in which individuals are treated. It is merely for technical reasons that we assume the treatment outcomes to take values in $[0,1]$ and this interval can be generalized to any interval $[I_1,I_2]$ for some $I_1,I_2\in\mathbb{R},\ I_1\leq I_2$ or $Y_t^{(i)}$ being sub-gaussian without qualitatively changing our results. The framework accommodates treatments with different costs since, whenever it makes sense, $Y_t^{(i)}$ can be defined net of costs.
We allow for the data to arrive in $M$ batches of sizes $m_j,\ j=1,...,M$, such that the total number of assignments $N=\sum_{j=1}^Mm_j$. If an unemployment program is run for twelve months and new programs start every month then $M=12$ and the $m_j$ indicate how many individuals become unemployed in the $j$th month. The $m_j$ are allowed to be random variables as the policy maker does not a priori know how many will become unemployed each month. This is in contrast to typical treatment allocation problems where the size as well as the composition of the data set are taken as given. Every individual $t$ belongs to exactly one of the batches. For each batch the outcomes of the assignments are only observed at the end of the batch. Thus, the treatment assignments for individuals belonging to batch $\tilde{j}$ can only depend on the outcomes observed from previous batches $j=1,...,\tilde{j}-1$. This is reasonable as information gained from treating persons who have become unemployed prior to person $t$, yet in the same month/batch, cannot be used to inform the treatment allocation of person $t$ as all persons from the same batch start their programs at the same time.
For each $t=1,...,N$ the treatment outcomes can be arbitrarily correlated in the sense that we put no restrictions on the dependence structure of the entries of the vector $Y_t=(Y_t^{(1)},...,Y_t^{(K+1)})$, i.e.\ the joint distribution of the entries of $Y_t$ is left unspecified. This in accordance with real applications where an unemployed individual's response to two types of job training programs may be highly correlated. As individuals arrive independently, we assume the $Y_t$ are i.i.d.
Compared to the existing literature a distinguishing feature of our work is that we consider general welfare functions $f:\mathbb{R}^2\to\mathbb{R}$ of the mean $\mu^{(i)}=\mathbb{E}Y_t^{(i)}$ and variance $(\sigma^2)^{(i)}=\mathbb{E}(Y_t^{(i)}-\mu^{(i)})^2$ of the treatment outcome $Y_{t}^{(i)}$. This is in contrast to most other work which only considers the expected effect of a treatment which amounts to only considering welfare functions depending on the mean. However, it is often very important to also take into account the risk of a treatment.
Defining $f^{(i)}=f(\mu^{(i)},(\sigma^2)^{(i)})$ the welfare maximizing (best) treatment is denoted by $*$ and satisfies $f^{(*)}=\arg\max_{1\leq i\leq K+1}f^{(i)}$ \footnote{We assume without loss of generality that the best treatment is unique.}. The welfare maximizing treatment strikes the optimal balance between expected treatment outcome and the riskiness of the treatment. Let $\Delta_i=f^{(*)}-f^{(i)}\geq 0$ be the difference between the best and the $i$th treatment and assume that $\Delta_1\geq...\geq \Delta_K> \Delta_*=0$. The ranking of the $\Delta_i$ is without loss of generality and does not necessarily imply a ranking of neither the $\mu^{(i)}$ nor the $(\sigma^2)^{(i)}$.
A treatment allocation rule is a sequence of (random) functions $\pi=\cbr[0]{\pi_t}$ assigning a treatment from the set $\cbr[0]{1,...,K+1}$ to every individual $t=1,...,N$ . This allocation can only depend on the outcomes from previous batches.
Our goal is to provide a rule $\pi$ that maximizes expected cumulated welfare over the $N$ treatments. This is equivalent to minimizing the expected difference to the infeasible welfare that would have been obtained from always assigning the best treatment $*$, i.e. minimizing the expected value of the regret
where the second equality is due to the fact that each individual $t$ can be uniquely identified with an assignment $i$ made in a batch $j$; the assignment rule can also be written as $\pi_{j,i}$ for $j\in\cbr{1,...,M}$ and $i\in \cbr{1,...,m_j}$.
Throughout this paper we assume that $f$ is Lipschitz continuous from $[0,1]^2$ equipped with the $\ell_1$-norm to $\mathbb{R}$ with Lipschitz constant $\mathcal{K}>0$, i.e.
By making concrete choices for $f$ our framework contains the following instances as special cases.
Heuristically, the sequential treatment policy works by eliminating treatments that are deemed to be inferior based on the outcomes observed so far. We then take turns assigning each of the remaining treatments in the next batch. This is the exploration step. After this step, elimination takes place again.
To describe the policy more formally, let $m_{i,j}$ be the number of times treatment $i$ is assigned in batch $j$. Thus, $m_j=\sum_{i=1}^{K+1}m_{i,j}$ and we define $B_i(b)=\sum_{j=1}^bm_{i,j}$ as the number of times treatment $i$ has been assigned up to and including $b$ batches, $b=1,...,M$. Next, for a policy $\pi$ let $\hat{\mu}^{(i)}_{N_{s,i}}=\frac{1}{N_{s,i}}\sum_{t=1}^sY_t^{(i)}1_{\cbr[0]{\pi_t=i}}$ and $(\hat{\sigma}^2_{N_{s,i}})^{(i)}=\frac{1}{N_{s,i}}\sum_{t=1}^s(Y_t^{(i)}-\hat{\mu}^{(i)}_{N_{s,i}})^21_{\cbr[0]{\pi_t=i}}$ with $N_{s,i}=\sum_{t=1}^s1_{\cbr[0]{\pi_t=i}}$ be estimators of $\mu^{(i)}$ and $(\sigma^2)^{(i)}$, respectively based on observing outcomes on $s\in\cbr{1,...,N}$ individuals.
Sequential treatment policy: Denote by $\hat{\pi}$ the sequential treatment policy. Let $\mathcal{I}_b\subseteq\cbr[0]{1,...,K+1}$ be the set of remaining treatments before batch $b$ and let $\underline{B}(b)=\min_{i\in\mathcal{I}_b}B_i(b)$ be the number of times that each remaining treatment at least has been assigned up to and including batch $b$.
The sequential treatment policy uses the sample counterparts of $\mu^{(i)}$ and $(\sigma^2)^{(i)}$ to evaluate whether treatment $i$ is inferior to the best of the remaining treatments. Concrete choices of $\gamma$ and $T$ guaranteeing low regret are given in Theorem (ref) and we provide some initial intuition here. The parameter $\gamma$ controls how aggressively treatments are eliminated. Small values of $\gamma$ make it easier to eliminate inferior treatments but also induce a risk of potentially eliminating the best treatment. The exact form of the elimination threshold comes from the fact the sample moments concentrate at rate $1/\sqrt{\underline{B}(b)}$ around their population counterparts. The parameter $T$, which will often be set equal to the expected sample size $n=\mathbb{E}(N),$ is needed exactly to ensure that we are cautious eliminating treatments after the first couple of batches where $\hat{\mu}^{(i)}_{\underline{B}(b)}$ and $(\hat{\sigma}^2_{\underline{B}(b)})^{(i)}$ could be based on few observations and thus need not be precise estimates of $\mu^{(i)}$ and $(\sigma^2)^{(i)}$, respectively \footnote{We are slightly more cautious than $1/\sqrt{\underline{B}(b)}$. On the other hand, one does not want to be too cautious either since this results in slow elimination of suboptimal treatments.}. From a technical point of view, this ensures that we can uniformly (over treatments) control the probability of eliminating the best treatment. Note that eliminating the best treatment is very costly as regret will accumulate linearly after such a mistake\footnote{If the best treatment is eliminated then the regret from each subsequent treatment is $f^{(*)}-f^{(\hat{\pi}_t)}\geq \Delta_K>0$}. Furthermore, the sequential treatment policy need neither to know sample size $N$, nor the number of batches $M$ in order to run. It can be stopped at any point in time with regret bounds as outlined in Theorem (ref) below.
Without an upper bound on the size of the batches it is clear that no non-trivial upper bound on regret can be established. For example, the data could arrive in one batch of size $N$ implying that feedback is never received prior to any assignment. Thus, we shall assume that no batch is larger than $\overline{m}$ where $\overline{m}$ is non-random, i.e. $m_j\leq \overline{m}$ for $j=1,...,M$. Our first result provides an upper bound on the regret incurred by the sequential treatment policy.
The upper bound in Theorem (ref) consists of two parts. The first part is adapting to the unknown distributional characteristics $\Delta_j$. Note that the regret in this part only increases logarithmically in the the expected number of treatments $n$. This logarithmic rate is unimprovable in general since it is known to be optimal even in the case where one only targets the mean (which in our setting corresponds to $f(x,y)=x)$ such that $\mathcal{K}=1$) and the treated individuals arrive one-by-one ($\overline{m}=1$), see e.g.\ Theorem 2.2 in bubeck2012regret. On the other hand, the first part of ((ref)) can be made arbitrarily large by letting e.g.\ $\Delta_1\rightarrow 0$. Thus, the bound is not uniform in the underlying distribution of the data. The second part of ((ref)) is uniform over all $(K+1)$ tuples of distributions on $[0,1]$ and in fact yields the minimax optimal rate up to a factor of $\sqrt{\log(K)}$ even in the case where only the welfare function $f(x,y)=x$ is considered and $\overline{m}=1$. It is reasonable that both parts of the upper bound in ((ref)) are increasing in $\overline{m}$ since as the maximum batch size increases the time between potential elimination of suboptimal treatments increases implying that these are assigned more often. Similarly, more experimentation between treatments takes place when the number of these, $K+1$, is increased which results in increased regret.
Note that the implementation of the sequential treatment algorithm requires knowledge of the expected number of individuals that are going to be treated. In medical experiments the total number of individuals participating is often determined a priori making $N$ known and deterministic (and equal to $n$). On the other hand, when allocating unemployed to treatments the total number of individuals becoming unemployed in the course of the year is unknown. However, one often has a good estimate of the expected value $n$ which is what matters for the treatment policy. For example, one may use averages of the number of individuals who have become unemployed in previous years to estimate $n$. Alternatively, one can use the doubling trick which resets the treatment policy at prespecified times in order to avoid any assumptions on the size of $N$ or $n$. Usage of the doubling trick would imply that eliminated treatments reappear and get another chance every time the policy is reset thus allowing for the efficiency of treatments to vary over time. For further details on the doubling trick and its implementation we refer to shalev2012online.
Theorem (ref) showed that the expected cumulated welfare of the sequential treatment policy will not be much smaller than the one from the infeasible policy that always assigns the best treatment. However, for an assignment rule to be ethically and politically viable it is important that it does not yield high welfare at the cost of maltreating certain individuals by wild experimentation. For example, it may not be ethically defendable for a doctor to assign a suboptimal treatment to a patient in order to gain more certainty for future treatments. The following theorem shows that the sequential treatment policy does not suffer from such a problem in the sense that the expected number of times any suboptimal treatment is assigned only increases logarithmically in the sample size.
The important ethical guarantee on the treatment rule is that it only assigns very few persons to a suboptimal treatment (logarithmic growth rate in the sample size). It is in line with intuition that the closer any suboptimal treatment is to being optimal ($\Delta_i$ closer to zero) the more difficult it is to guarantee that this treatment is rarely assigned. The reason is that this treatment must be assigned more often before it confidently can be concluded that it is suboptimal and thus eliminated. On the other hand, the regret incurred by assigning such a treatment is low exactly because $\Delta_i$ is small such that the increased amount of experimentation does not necessarily lead to high regret.
So far we have considered the performance of our sequential treatment policy on the $N$ individuals being treated. However, one may also ask how much has been learned in the course of the $N$ assignments. Or, put differently, how well can we expect to treat “out of sample”-individuals. Thus, imagine an $(N+1)$st individual to whom a treatment $I_{N}\in\cbr[0]{1,...,K+1}$ must be assigned in order to maximize the expected welfare of said individual. To be precise, the goal is to choose $I_n$ to minimize the expected value of
Compared to the problem we have studied so far this is a pure exploitation problem --- there are no gains from gathering more knowledge about the treatments as all that enters the objective function is the welfare of the $(N+1)st$ individual. To do so, one must first choose how to assign the treatment to the out of sample individual. Here we shall show that assigning the treatment that has been assigned most often in the exploration-exploitation phase by our sequential treatment policy $\hat{\pi}$ works well, i.e.
with an arbitrary tie-breaker. We call this policy the out-of-sample policy. Heuristically, the reason that this policy works well is that in the initial treatment period the sequential treatment policy operates by gradually eliminating sub-optimal treatments while at the same time ensuring that the best treatment is not eliminated. Thus, it is likely that the best treatment has been assigned most often. Note that the following result relies on the sample size $N$ being non-random and therefore equal to its expectation $n$. An analogous result can be proven for the case of random $N$ if one is willing to restrict the support of $N$.
The requirements on the constant $c$ can likely be refined but we focus on the rate on the upper bounds on $\mathbb{E}(r_N)$ here. As in Theorem (ref) the bound in Theorem (ref) consists of a distribution dependent and a uniform part (where the uniformity is over all $(K+1)$ tuples of distributions on $[0,1]$). Both parts witness that even though the sequential treatment policy assigns treatments in order to maximize the welfare of the $n$ treated individuals as opposed to maximizing the information by the end of $n$ treatments enough is learned to construct a policy that guarantees high welfare out of sample. This possibility is due to the fact that learning about the available treatments is inherent to maximizing the welfare over the treated individuals. In particular, both parts of the upper bound in Theorem (ref) tend to zero as $n\to\infty$.
So far we have considered the case where the outcome of a treatment does not depend on the characteristics of the individual it is assigned to. In reality, however, different persons react differently to the same type of treatment: while a certain medicine may work well for one person it may be outright dangerous to assign it to another person if this person is allergic to some of its substances. Similarly, the effect of further education on the probability of an unemployed individual finding a job may also depend on, e.g., the age of the individual: individuals close to the retirement age may benefit more from short courses updating their skill set while young individuals may benefit more from going back to school for an extended period of time.
Prior to assigning individual $t$ to a treatment we observe a vector $X_t\in[0,1]^d$ of covariates with distribution $\mathbb{P}_X$. In the case of assigning unemployed persons to various unemployment programs $X_t$ could include age, length of education, and years of experience. It is merely for technical convenience that we assume the variables to take values in $[0,1]$ and the assumption of bounded support can be replaced by tail conditions on the distribution of $X_t$. $\mathbb{P}_X$ is assumed to be absolutely continuous with respect to the Lebesgue measure with density bounded from above by $\bar{c}>0$. This rules out discrete covariates which may be very relevant in practice. In Section (ref) we shall show how policies with low regret in the presence of discrete covariates can be constructed. As we now observe covariates on each individual prior to the treatment assignment we condition on these as, for example, the risk of a treatment may be individual specific and depend on, e.g., whether the person has an allergy or not. Thus, in close analogy to the setting without covariates, we now define the conditional means and variances $\mu^{(i)}(X_t)=\mathbb{E}(Y^{(i)}|X_t)$ and $(\sigma^2)^{(i)}(X_t)=\mathbb{E}\sbr[1]{(Y^{(i)}-\mu^{(i)}(X_t))^2|X_t}$ as well as $f^{(i)}(X_t)=f(\mu^{(i)}(X_t), (\sigma^2)^{(i)}(X_t))$. As $\mu^{(i)}(X_t)$ and $(\sigma^2)^{(i)}(X_t)$ are unknown to the policy maker they must be gradually learned by experimentation. In the presence of covariates a policy $\pi=\cbr[0]{\pi_t}$ is a sequence of random functions $\pi_t: [0,1]^d\to \cbr[0]{1,...,K+1}$ where $\pi_t$ can only depend on treatment outcomes from previous batches. For any $X_t$, a social planner (oracle) who knows the conditional mean and variance functions and wishes to maximize welfare assigns the treatment\footnote{If there are several treatments achieveing the maximal welfare the oracle assigns any of these.}
and receives $f^{\left(\pi^\star(X_t)\right)}(X_t)=\max_{i=1,...,K+1}f^{(i)}(X_t)=:f^{(\star)}(X_t)$. Thus, $f^{(\star)}(x)$ is the pointwise maximum of the $f^{(i)}(x)$, $i=1,...,K+1$. The goal of a treatment policy is to get as close to the oracle solution as possible in terms of welfare. The welfare loss (regret) of a policy $\pi$ compared to the oracle is
It is important to note the difference between equation ((ref)) and ((ref)). While ((ref)) considers the difference between unconditional moments ((ref)) considers the difference between conditional moments. The latter is more ambitious as we consider each individual separately through $X_t$ and seek to minimize the distance to the treatment that would have been optimal for this specific person (with covariates $X_t$). On the other hand, in the setting without covariates, we only seek to get as close to the outcome of the treatment that is best on average.
In order to prove upper bounds on the regret we restrict the $\mu^{(i)}(X_t)$ and $(\sigma^2)^{(i)}(X_t)$ to be reasonably smooth. This is a sensible property to impose since individuals with similar characteristics can be expected to react similarly to the same treatment. In particular, we assume that $\mu^{(i)}(X_t)$ and $\sigma^{(i)}(X_t)$ are $(\beta,L)-$H{\"o}lder continuous. To be precise, letting $\enVert[0]{\cdot}$ denote the Euclidean norm on $[0,1]^d$, we assume that $\mu^{(i)},\ (\sigma^2)^{(i)}\in \mathcal{H}(\beta, L)$ for all $i=1,...,K+1$, where $\mathcal{H}(\beta, L)$ is characterised by being those $g:[0,1]^d\to[0,1]$ such that there exist $\beta\in(0,1]$ and $L>0$ such that
In the presence of covariates the idea of the sequential treatment policy is to group individuals into groups according to the values of the covariates. Thus, we define a partition of $[0,1]^d$ which consists of Borel measurable sets $B_1,...,B_F$, called groups/bins, such that $\mathbb{P}_X(B_j)>0$, $\cup_{j=1}^FB_j=[0,1]^d$, and $B_j\cap B_k=\emptyset$ for $j\neq k$. The policy maker groups individuals according to the value of their covariates and seeks to treat each group in a welfare maximizing way. However, the policy maker may be constrained by political or ethical considerations in his choice of grouping individuals. For example, a realistic unemployment policy cannot group individuals into overly many groups and the rules determining which group an individual belongs to cannot be too complicated. Most realistic policies would choose the groups in such a way that individuals with similar characteristics belong to the same group as it can be expected that the same policy is best for similar individuals. Figure (ref) illustrates various ways of grouping individuals.
For any group $B_j$ define
and
as the mean and variance of $Y_{t}^{(i)}$ given that $X_t$ falls in $B_j$. We apply the sequential treatment policy without covariates separately to each group. To do so, define the groupwise counterpart of the welfare pertaining to treatment $i$ from the setting without covariates in Section (ref) as $f_j^{(i)}=f(\bar{\mu}^{(i)}_j,(\bar{\sigma}^2)^{(i)}_j)$. As $\bar{\mu}^{(i)}_j$ and $(\bar{\sigma}^2)^{(i)}_j$ vary across groups one can target different optimal treatments for each group, $j=1,...,F$. We use the sequential treatment policy without covariates of Section (ref) to target $\max_{1\leq i\leq K+1}f(\bar{\mu}^{(i)}_j,(\bar{\sigma}^2)^{(i)}_j)$ for each group. By the smoothness assumptions on $f, \mu^{(i)}(x)$ and $(\sigma^2)^{(i)}(x)$, $\max_{1\leq i\leq K+1}f(\bar{\mu}^{(i)}_j,(\bar{\sigma}^2)^{(i)}_j)$ will not be very far from the "fully individualized" target $f^{(\star)}(x)=\max_{1\leq i\leq K+1}f(\mu^{(i)}(x), (\sigma^2)^{(i)}(x))$ for any $x\in B_j$ as formalized in the appendix. At this stage one may ask why one does not simply use a treatment policy which directly targets $\max_{1\leq i\leq K+1}f(\mu^{(i)}(x), (\sigma^2)^{(i)}(x))$. First, full individualization/discrimination is often not possible due to ethical or legislative constraints. Second, the regret bound obtained in Corollary (ref) for the proposed policy is minimax rate optimal. Thus, even though for each group we target the policy which is best on average for that group nothing is lost (up to a multiplicative constant) even when we compare our performance to the fully individualized optimal policy. Third, a high degree of individualization is only useful for very large data sets as very small groups (in terms of the Lebesgue measure of the group) would otherwise imply very few individuals belonging to each group. This would result in only exploration being carried out for each group as no treatments can be eliminated based on very few assignments. We shall provide an example of how to optimally (in the sense of minimax regret) handle this tradeoff in Corollary (ref) below.
Let $N_{B_j}(t)=\sum_{s=1}^t1_{\cbr[0]{X_s\in B_j}}$ denote the number of individuals who have been assigned to group $B_j$ when $t$ individuals have been treated. Furthermore, $\bar{B}_j=\lambda_d(B_j)$ denotes the Lebesgue measure of group $j$. Let $\hat{\pi}_{{B_j},N_{B_j}(t)}$ be the assignment made by the sequential treatment policy without covariates applied only to individuals who belong to group $B_j$. This policy is implemented with parameters $\gamma=\mathcal{K}L$ and $T=n\bar{B}_j$. The sequential treatment treatment policy $\bar{\pi}$ with covariates is then a sequence of mappings $\bar{\pi}_t:[0,1]^d\to\cbr[0]{1,...,K+1}$ where
Thus, when $X_t\in B_j$, the sequential treatment policy with covariates makes the assignment dictated by the sequential treatment policy without covariates when applied only to individuals belonging to group $B_j$.
Denote by $\mathcal{S}=\mathcal{S}(\beta, L, \mathcal{K},d, \bar{c}, \overline{m})$ a treatment problem where $f$ is Lipschitz continuous with constant $\mathcal{K}$, $X_t\in[0,1]^d$ has distribution $\mathbb{P}_X$ which is absolutely continuous with respect to the Lebesgue measure with density bounded from above by $\bar{c}>0$, maximal batch size $\overline{m}$ and $\mu^{(i)},\ (\sigma^2)^{(i)}\in \mathcal{H}(\beta, L)$ for all $i=1,...,K+1$. Unless stated otherwise we will consider problems in $\mathcal{S}$ in the sequel.
The performance of our policy depends critically on the way the policy maker chooses to group individuals. To characterize this grouping, define $V_j=\sup_{x,y\in B_j}\enVert[0]{x-y}$ as the maximal possible difference in the characteristics of any two individuals assigned to group $j$. The next result provides an upper bound on the regret compared to the infeasible oracle which knows $\mu^{(i)}(x)$ and $(\sigma^2)^{(i)}(x)$ and thus whose treatment is optimal for an individual with characteristics $x\in[0,1]^d$.
Theorem (ref) provides an upper bound on the regret of the sequential treatment policy for any type of grouping of individuals that the policy maker may choose. Allowing for groups with arbitrary characteristics is useful since the policy maker may be constrained in such a way that choosing the groups such that the right hand side of ((ref)) is minimized over groups is not possible. The size of the regret depends on the characteristics $\bar{B}_j$ and $V_j$ of the grouping. Note that the upper bound on the regret is increasing in these two quantities. However, choosing the groups such that $\bar{B}_j$ and $V_j$ are small implies that the number of groups, $F$, must be large. In general the upper bound in ((ref)) cannot be improved since by choosing the groups as in Corollary (ref) below one achieves the minimax rate of regret. We elaborate further on this below.
The first part of the upper bound in ((ref)) is the regret accumulated from implementing the sequential treatment policy without covariates on each group separately targeting $\max_{1\leq i\leq K+1} f(\bar{\mu}^{(i)}_j,(\bar{\sigma}^2)^{(i)}_j)$ for group $j=1,...,F$. The second part of the bound in ((ref)) is the approximation error resulting from targeting $\max_{1\leq i\leq K+1}f(\bar{\mu}^{(i)}_j,(\bar{\sigma}^2)^{(i)}_j)$ instead of $\max_{1\leq i\leq K+1}f(\mu^{(i)}(x), (\sigma^2)^{(i)}(x))$. Clearly, the larger the groups are chosen (as measured by $\bar{B}_j$ and $V_j$) the more dissimilar could the treatment that is best for the average individual of the group be from the treatment which is best for any given individual in the group.
A particular type of groups are the square ones which use hard thresholds for each entry of $X_t$ to create hypercubes that partition $[0,1]^d$. These are particularly relevant in practice due to their simplicity and an example of these bins is given in the second display of Figure (ref). More precisely, fix $P\in \mathbb{N}$ and define
for $k=(k_1,...,k_d)\in\{1,...,P\}^d$. Thus, $P$ is the number of splits along each dimension of $X_t$ creating a partition of $P^d$ smaller hypercubes $B_1,...,B_{P^d}$ with side lengths $1/P$.
Note that the larger the number of covariates $d$, the smaller will the number of splits $P$ in each dimension be as it must be ensured that enough observations fall in each group. The larger the number of potential treatments $K+1$ is the more experimentation will take place and hence the regret compared to the infeasible oracle policy increases.
The bound in ((ref)) is, as a function of $n$, optimal in a minimax sense and cannot be improved by more than multiplicative constants. To see this consider the the case of $\overline{m}=1$ and $K=1$ (two treatments are available) such that ((ref)) reduces to $E\left[R_N(\bar{\pi})\right]\leq C n^{1-\frac{\beta}{2\beta+d}}$.
Theorem (ref) shows that up to multiplicative constants no treatment policy can have a lower maximal regret over $\mathcal{S}$ than the sequential treatment policy as any policy must incur a regret at least of the same order as the sequential treatment policy.
We next show that even in the presence of covariates the sequential treatment policy does not make many suboptimal assignments. Our first result is a consequence of Theorem (ref). On any bin $1\leq j\leq F$ the result bounds the number of times that a treatment $1\leq i\leq K+1$ which does not maximize $f(\bar{\mu}^{(i)}_j,(\bar{\sigma}^2)^{(i)}_j)$ is assigned. Let $T_{i,j}(N)$ be the number of times treatment $i$ is assigned on bin $j$ in the course of a total of $N$ assignments. Calling treatment $i$ suboptimal on bin $B_j$ if $\Delta_i:=f_j^{(*)}-f(\bar{\mu}^{(i)}_j,(\bar{\sigma}^2)^{(i)}_j)>0$ we have the following result.
Theorem (ref) guarantees that any treatment whose combination of mean and variance over $B_j$ does not maximize $f$ will only rarely be assigned. In fact, the number of times a treatment that is suboptimal on bin $B_j$ is assigned only grows logarithmically in the expected number of individuals belonging to bin $B_j$. Notice the similarity to Theorem (ref) where $n$ has now been replaced by $n\bar{B}_j$ which up to the constant $\bar{c}$ is an upper bound on the expected number of individuals falling in group $j$.
A potential shortcoming of Theorem (ref) is that the for each group $B_j$ the maximizer of $f(\bar{\mu}^{(i)}_j,(\bar{\sigma}^2)^{(i)}_j)$ depends on the way the policy maker has chosen $B_j$. A different way of assessing the number of suboptimal treatments assigned is to consider each person individually and check whether the optimal treatment was assigned or not to this person. We say that treatment $i$ is suboptimal for individual $t$ if $f^{(\star)}(X_t)> f^{(i)}(X_t)$. Therefore, another way of declaring the fairness of a policy $\pi$ is to provide an upper bound on the number of individuals to whom a suboptimal treatment was assigned:
It is sensible that a nontrivial upper bound on $\mathbb{E}(S_N(\pi))$ (a bound less than $n$) can only be established if the best treatment is sufficiently much better than the second best --- otherwise these cannot be distinguished from each other. To formalize this notion let
denote the value of the second best treatment for an individual with characteristics $x\in[0,1]^d$.
The margin condition limits the probability that the best and the second best treatment are very close to each other. Larger values of $\alpha$ mean that it is easier to distinguish the best and second best treatment from each other. The margin condition has been used in the literature on statistical treatment rules by Kitagawa2015 to improve the rates of their empirical welfare maximization classifier. Before this, similar assumptions had been used in the literature on classification analysis, mammen1999smooth, tsybakov2004optimal. CovBandit have used the margin condition in the context of bandits. The margin condition is satisfied if, for example, $f^{(\star)}(X_t)-f^{(\sharp)}(X_t)$ has a density with respect to the Lebesgue measure which is bounded from above by a constant $a>0$. In that case we may set $C=a$ and $\alpha=1$. We refer to Kitagawa2015 for more examples of when the margin condition is satisfied.
((ref)) provides an upper bound on the expected number of times a policy $\pi$ assigns a treatment which is suboptimal for individual $t$. This is done in terms of the regret incurred by the policy. ((ref)) considers the case of the sequential treatment policy with a particular group structure. Note that $\mathbb{E}(S_N(\pi))$ is guaranteed to grow only sublinearily in $n$. However, as $\alpha$ approaches 0, which amounts to relaxing the margin condition and making the best and second best treatments indistinguishable, the upper bound on $\mathbb{E}(S_N(\pi))$ becomes almost linear in $n$.
Sometimes the groups $B_1,...,B_F$ are dictated exogenously upon the policy maker and thus can not be chosen to maximize welfare as in the previous section. As a result we can no longer target the welfare from the fully individualized policy, $f^{(\star)}(x)$. In our context this means that we must find one treatment which best suits all individuals in each of the prespecified groups. For individuals in group $B_j,\ j=1,...,F$ a candidate for the omnibus best treatment is $f_j^{(*)}=\operatorname*{arg\,max}_{1\leq i\leq K+1} f(\bar{\mu}^{(i)}_j,(\bar{\sigma}^2)^{(i)}_j)$, i.e. the treatment maximizing the welfare of a person with average characteristics $\bar{\mu}^{(i)}_j$ and $(\bar{\sigma}^2)^{(i)}_j$. Recalling that $f_j^{(i)}=f(\bar{\mu}^{(i)}_j,(\bar{\sigma}^2)^{(i)}_j)$ and introducing the modified regret $\tilde{R}_j(\bar{\pi})=\sum_{t=1}^{N_{B_j}(N)}\del[2]{f_j^{(*)}-f_j^{(\hat{\pi}_{B_j,t)})}}$ of group $B_j$ of the sequential treatment policy we seek to upper bound
Note that ((ref)) differs from the regret in ((ref)) in that we no longer target the outcome of the fully individualized treatment.
The upper bound on modified regret is identical to the one in Theorem (ref) except for the absence of the term $C\sum_{j=1}^F\bar{B}_jV_j^{\beta}$ which previously served as an upper bound on the approximation error $f^{(\star)}(x)-f_j^{(*)}$ for all $x\in B_j$. However, as the groups are now exogenously given, this approximation error is unavoidable and it no longer makes sense to target $f^{(\star)}(x)$ as we can no longer choose the characteristics of the groups $\bar{B}_j$ and $V_j^{\beta}$ such that $n\bar{B}_jV_j^{\beta}$ is small. Note also how we no longer need the Hölder continuity of $\mu^{(i)}$ and $\sigma^{(i)}$ since there is no approximation error to control.
Until now we have assumed $\mathbb{P}_X$ to be absolutely continuos with respect to the Lebesgue measure. However, many covariates that may influence the identity of the optimal treatment are discrete. For example, gender may affect the outcome of an allocation in an unemployment program. Furthermore, we may not always observe a continuous variable perfectly as data might only be informative about which of finitely many wealth groups an individual belongs to without providing the exact, continuously scaled, wealth.
In order to accommodate discrete covariates, partition $X_t=(X_{t,D}',X_{t,C}')'$ where $X_{t,D}\in A=A_1\times...\times A_{d_D}$ contains the measurements of the $d_D$ discrete covariates. Each $A_{l}\subseteq \mathbb{N},\ l=1,...,d_D$ is finite with cardinality $|A_{l}|$. For the continuous covariates we assume $X_{t,C}\in [0,1]^{d_C}$ such that $X_t$ is $(d_D+d_C)$-dimensional. As in ((ref)) the regret of our treatment policy is measured against the infeasible target $f^{(\star)}(X_t)=\max_{1\leq i\leq K+1}f(\mu^{(i)}(X_t), (\sigma^2)^{(i)}(X_t))$. On the other hand, it does not make sense to assume $\mu^{(i)}(x)=\mu^{(i)}(x_D,x_C)$ or $(\sigma^2)^{(i)}(x)=(\sigma^2)^{(i)}(x_D,x_C)$ to be $(\beta,L)-$H{\"o}lder continuous in $x_D$. Thus, discrete covariates must be handled differently from continuous ones. Instead we shall now assume that for each fixed $a\in A$ one has that $\mu_{a}^{(i)}(x_C):=\mu^{(i)}(a,x_C)$ and $(\sigma^2)_{a}^{(i)}(x_C):=(\sigma^2)^{(i)}(a,x_C)$ belong to $\mathcal{H}(\beta,L)$. Since $a$ can only take $F_D=|A|=|A_1|\cdot...\cdot|A_{d_D}|$ possible values it is without loss of generality to assume $\beta$ and $L$ not to depend on $a$.
Our treatment policy now works by fully individualizing treatments across the discrete covariates. In other words, for any of the $F_D$ possible values of the vector of discrete covariates we implement the sequential treatment policy $\bar{\pi}$ by constructing groups only based on the continuous variables just as in Section (ref). For each value of the discrete covariate we allow for different ways of grouping based on the continuous covariates. For example, one may want to construct different wealth groups for men and women in order to obtain, e.g., groups with equally many individuals. For each $a\in A$ let $B_{a,j},\ j=1,...,F_{a}$ be the partition of $[0,1]^{d_C}$ used.
Formally, for each $a\in A$, let $\bar{\pi}_{t,a}$ be the sequential treatment policy with continuous covariates applied to the grouping $B_{a,j},\ j=1,...,F_{a}$. Thus, the sequential treatment policy in the presence of discrete covariates, $\tilde{\pi}$, is a sequence of mappings $\tilde{\pi}_t: A_1\times...\times A_{d_D}\times [0,1]^{d_C}\to \cbr[0]{1,...,K+1}$ where
with $N_{a,j}(t)=\sum_{s=1}^t1_{\left(X_{s,D}=a,X_{s,C}\in B_{a,j}\right)}$. Denote by $\tilde{\mathcal{S}}=\tilde{\mathcal{S}}(\beta, L, \mathcal{K},d_C, \bar{c},\overline{m})$ a treatment problem where $f$ is Lipschitz continuous with constant $\mathcal{K}$, $X_{t,D}\in A$ is discrete, $X_{C,t}\in[0,1]^d$ has distribution $\mathbb{P}_X$ which is absolutely continuous with respect to the Lebesgue measure with density bounded from above by $\bar{c}$, maximal batch size $\overline{m}$ and $\mu_{a}^{(i)},\ (\sigma^2)_{a}^{(i)}\in \mathcal{H}(\beta, L)$ for all $i=1,...,K+1$ and $a\in A$. Letting $V_{a,j}=\sup_{x,y\in B_{a,j}}||x-y||$ we have that $\tilde{\pi}$ enjoys the following upper bound on regret.
The upper bound on regret in ((ref)) generalizes the upper bounds in Theorems (ref) (no covariates) and (ref) (continuous covariates only). For example, the latter follows from ((ref)) by letting $|A|=1$ and using that $X_{t,C}$ is absolutely continuous with respect to the Lebesgue measure with density bounded from above by $\bar{c}$. Also, the case of purely discrete covariates is covered as a special case of ((ref)). In that case the approximation error vanishes as $V_{a,j}=0$
Oftentimes the outcome of a treatment is only observed with delay. For example, a medical doctor may choose not to measure the effect of a treatment immediately after it has been assigned as it takes time for the treatment to work. However, delaying the measurement for an extended period of time also implies that many new patients will arrive before the outcome of the previous treatment is known. Thus, the type of treatment assigned to these patients must be decided based on less information. Put differently, there is a tradeoff between getting imprecise information now and obtaining precise information later. A similar tradeoff exists when assigning unemployed to job training programs as it takes time to find a job. Therefore, it may not be advisable to measure the effect of a job training program very shortly after its termination.
In this section we formalize this intuition by proposing the following model for treatments being observed with delay. For simplicity, we focus first on the setting without covariates. We can decompose $Y_{t}^{(i)}$ as
where $\mathbb{E}(\eta_t^{(i)})=0$. Since $Y_t^{(i)}, \mu^{(i)}\in[0,1]$ it follows that $\eta_t^{(i)}=Y_t^{(i)}-\mu^{(i)}\in[-1,1]$. Thus, without further assumptions, the deviations of $Y_t^{(i)}$ around its mean are in $[-1,1]$. We shall model the idea of measurements becoming more precise if they are delayed by restricting this interval. To be precise, we assume that
where $\bar{a}_l,\bar{a}_u\in[0,1]$. In this section we let $\bar{a}(D)=\bar{a}_u(D)+\bar{a}_l(D)$ be a function of the number of batches $D$ the measurements are delayed by. Thus, if $\bar{a}(D)$ is a decreasing function, increasing the delay results in $Y_t^{(i)}$ being a less noisy measure of $\mu^{(i)}$. Restricting the support of $\eta_t^{(i)}$ is not the only way of modelling that measurements become more precise if they are delayed. One could also let the variance of the $\eta_t^{(i)}$ be a decreasing function of $D$. In fact, any assumption which implies stronger concentration of sample averages around the population means will suffice. As the welfare function $f$ also depends on the second moment $\mu_2^{(i)}=\mathbb{E}\sbr[1]{{Y_t^{(i)}}^2}$ and since ${Y_t^{(i)}}^2, \mu_2^{(i)}\in[0,1]$ we will model increased measurement precision of second moments due to delay as\footnote{Assuming the same lower and upper bounds in ((ref)) and ((ref)) is without loss of generality as one can simply take the smallest of the lower bounds and the largest of the upper bounds as the common values. }
First, we establish an upper bound on regret of the sequential treatment policy when treatment outcomes are observed with delay in the absence of covariates.
Sequential treatment policy Denote by $\hat{\pi}$ the sequential treatment policy. Let $\mathcal{I}_b\subseteq\cbr[0]{1,...,K+1}$ be the set of remaining treatments before batch $b$ and let $\underline{B}(b)=\min_{i\in\mathcal{I}_b}B_i(b)$ be the number of outcomes that have been observed for each of the remaining treatments after batch $b$.
Notice how the sequential treatment policy in the presence of delay differs from the one without delay. First, no elimination takes place after the first $D-1$ batches as no treatment outcomes are observed after these. Second, the elimination rule has been slightly modified as we can now eliminate more aggressively if $\bar{a}$ is small, i.e. the treatment outcomes are less noisy measurements of the population parameters.
Assume that $\bar{a}=\bar{a}(D)$ is a decreasing function. Then Theorem (ref) illustrates the tradeoff between getting imprecise information now and precise information later. This tradeoff is found in the adaptive part (first part) as well as the uniform part (second part) of the upper bound on regret of the sequential treatment policy. Increasing $D$ directly increases the upper bound on regret since information is obtained later but indirectly decreases the regret via a reduced $\bar{a}$. By making a concrete choice for $\bar{a}(D)$ one can determine the optimal delay by minimizing the upper bound on regret. It can also be shown that the bound in Theorem (ref) reduces to the one in Theorem (ref) when $D=0$ and $\bar{a}=1$.
We turn next to the setting with continuous covariates and treatment outcomes being observed with delay. The introduction of covariates leads to a variant of ((ref)). To be precise, we assume that
where $\mu_1^{(i)}(X_t)=\mathbb{E}\sbr[1]{Y_t^{(i)}|X_t}$ and $\mu_2^{(i)}(X_t)=\mathbb{E}\sbr[1]{{Y_t^{(i)}}^2|X_t}$. As in the setting without delay, we implement the sequential treatment policy separately for each group $B_1,...,B_F$ with parameters $\gamma=\mathcal{K}L$ and $T=n\bar{B}_j,\ j=1,...,F$.
The first part of the upper bound on expected regret in ((ref)) (the sum over the $F$ groups) is identical to the upper bound in Theorem (ref) except for the presence of $\bar{a}$. The smaller $\bar{a}$ is the smaller will this part be as the observed outcomes of the treatments will be very close to the population counterparts and the treatment that is best for each group is quickly found. As $\bar{a}$ is usually a decreasing function in $D$, the upper bound in ((ref)) clearly illustrates the tradeoff between postponing the measurement to get precise information later and getting (imprecise) information quickly. The term under the square root holds the key to the benefit from delaying as it corresponds to the regret of a treatment problem which starts only after $D$ batches but where measurements are observed more precisely. On the other hand, the term $\overline{m}D$ is an upper bound on the regret incurred from assigned individuals blindly for $D$ batches each of which contains no more than $\overline{m}$ individuals.
This paper considers a treatment allocation problem where the individuals to be treated arrive gradually and potentially in batches. The goal of the policy maker is to maximize the welfare over the $N$ treatment assignments made. As the policy maker does not know a priori about the virtues of the available treatments, he faces an exploration-exploitation tradeoff. Prior to each assignment he observes covariates on the individual to be treated thus allowing for the optimal treatment to vary across individuals. Our setup allows the welfare function not only to depend on the expected treatment outcome but also on the risk of the treatment. We show that a variant of the sequential treatment policy obtains the minimax optimal regret. This strong welfare guarantee does not come at the price of overly wild experimentation as we show that the number of suboptimal treatments only grows quite slowly in the total number of assignments made. We also establish upper bounds on the regret of the sequential treatment policy when the outcome of the treatments are observed with delay. Finally, we introduce the “out-of-sample” policy for treating individuals after the initial treatment period and provide upper bounds on its regret.