Functional Sequential Treatment Allocation

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.

80,122 characters · 15 sections · 133 citation commands

Rendered from LaTeX for readability, not typeset faithfully. Citation keys are highlighted; maths is left as source; figures, tables and equation environments are summarised rather than reproduced; unrecognised commands are greyed out so nothing is silently dropped. Email addresses are removed.

tabular[tabular omitted — 139 chars of source]

\and

tabular[tabular omitted — 139 chars of source]

\and

tabular[tabular omitted — 110 chars of source]

} \singlespacing

abstractConsider a setting in which a policy maker assigns subjects to treatments, observing each outcome before the next subject arrives. Initially, it is unknown which treatment is best, but the sequential nature of the problem permits learning about the effectiveness of the treatments. While the multi-armed-bandit literature has shed much light on the situation when the policy maker compares the effectiveness of the treatments through their mean, much less is known about other targets. This is restrictive, because a cautious decision maker may prefer to target a robust location measure such as a quantile or a trimmed mean. Furthermore, socio-economic decision making often requires targeting purpose specific characteristics of the outcome distribution, such as its inherent degree of inequality, welfare or poverty. In the present paper we introduce and study sequential learning algorithms when the distributional characteristic of interest is a general functional of the outcome distribution. Minimax expected regret optimality results are obtained within the subclass of explore-then-commit policies, and for the unrestricted class of all policies.

Keywords: Sequential Treatment Allocation, Distributional Characteristics, Randomized Controlled Trials, Minimax Optimal Expected Regret, Multi-Armed Bandits, Robustness.

\doublespacing

Introduction

A fundamental question in statistical decision theory is how to optimally assign subjects to treatments. Important recent contributions include chamberlain2000econometrics, manski2004statistical, dehejia2005program, hirano2009asymptotics, stoye2009minimax, bhattacharya2012inferring, stoye2012minimax, tetenov2012statistical manski2016sufficient, athey2017efficient, kitagawa2018should, and manski2019treatment; cf. also the overview in hirano2018statistical. In the present paper we focus on assignment problems where the subjects to be treated arrive sequentially. Thus, in contrast to the above mentioned articles, the dataset is gradually constructed during the learning process. In this setting, a policy maker who seeks to assign subjects to the treatment with the highest expected outcome (but who initially does not know which treatment is best), can draw on a rich and rapidly expanding literature on “multi-armed bandits.” Important contributions include thomp, robbins1952some, gittins1979bandit, lai1985asymptotically, agrawal1995sample, auer1995gambling, MOSS; cf. bubeck2012regret and lattimore2019bandit for introductions to the subject and for further references. In many applications, however, the quality of treatments cannot successfully be compared according to the expectation of the outcome distribution: A cautious policy maker may prefer to use another (more robust) measure of location, e.g., a quantile or a trimmed mean; or may actually want to make assignments targeting a different distributional characteristic than its location. Examples falling into the latter category are encountered in many socio-economic decision problems, where one wants to target, e.g., a welfare measure that incorporates inequality or poverty implications of a treatment. Inference for such “distributional policy effects” has received a great deal of attention in non-sequential settings, e.g., Gastwirth1974, manski1988ordinal, Thistle1990, mills1997statistical, davidson2000statistical, abadie2002instrumental, abadie2002bootstrap, chernozhukov2005iv, davidsonflachaire2007, BarrettDonald2009, hirano2009asymptotics, SCHLUTER2009, rostek2010quantile, rothe2010nonparametric, rothe2012partial, chernozhukov2013inference, kit2017 and manski2019remarks.\footnote{In contrast to much of the existing theoretical results concerning inference on inequality, welfare, or poverty measures, we do not investigate (first or higher-order) asymptotic approximations, but we establish exact finite sample results with explicit constants. To this end we cannot rely on classical asymptotic techniques, e.g., distributional approximations based on linearization arguments.}

Motivated by robustness considerations and the general interest in distributional policy effects, we consider a decision maker who seeks to minimize regret compared to always assigning the unknown best treatment according to a functional of interest. In order to achieve a low regret, the policy maker must sequentially learn the distributional characteristic of interest for all available treatments, yet treat as many subjects as well as possible.

While most of the multi-armed bandit literature focuses on targeting the treatment with the highest expectation, there are articles going beyond the first moment. This previous work has focused on risk functionals: maillard considers problems where one targets a coherent risk measure. NIPS2012_4753, 7515237 and vakili2018decision study a problem targeting the mean-variance functional, i.e., the variance minus a multiple of the expectation. zimin2014generalized, motivated by earlier results on problems targeting specific risk measures, and kock2017optimal consider problems where one targets a functional that can be written as a function of the mean and the variance. tran2014functional and cassel2018general do not restrict themselves to functionals of latter type, and consider bandit problems, where the target can be a general risk functional. These papers use various types of regret frameworks. tran2014functional consider a “pure-exploration” regret function into which the errors made during the assignment period do not enter. maillard, zimin2014generalized, kock2017optimal and vakili2018decision consider a “cumulative” regret function that is closely related to the regret used in classical multi-armed bandit problems (i.e., where the expectation is targeted). NIPS2012_4753, 7515237 and cassel2018general consider a “path-dependent” regret function. The just-mentioned articles have in common that pointwise regret upper bounds are derived for certain policies (and the regret considered). Except for 7515237 and vakili2018decision, who exclusively consider the mean-variance functional, matching lower bounds are not established. Therefore, apart from the mean-variance functional, it remains unclear if the policies developed are optimal. The main goal of the present paper is to develop a minimax optimality theory for general functional targets. The regret function we work with is cumulative, and thus has the following important features which are relevant for many socio-economic assignment problems:

itemize• Every subject not assigned to the best treatment contributes to the regret. • A loss incurred for one subject cannot be compensated by future assignments.

The first bullet point is not satisfied by a “pure-exploration” regret; the second is violated by “path-dependent” regrets.

Our first contribution is to establish minimax expected regret optimality properties within the subclass of “explore-then-commit” policies (cf. Theorems (ref) and (ref)). These are policies that strictly separate the exploration and exploitation phases: one first attempts to learn the best treatment, e.g., by conducting a randomized controlled trial (RCT), on an initial segment of subjects. Based on the outcome, one then assigns all remaining subjects to the inferred best treatment (which is not guaranteed to be the optimal one). Such policies are close to current practice in many socio-economic decision problems. garivier2016explore recently studied optimality properties of explore-then-commit policies in a 2-arm Gaussian setting targeting exclusively the expectation.

Our second contribution is to obtain lower bounds on maximal expected regret over the class of all policies (cf. Theorem (ref)), and to show that they are matched by uniform upper bounds for the following two policies: Firstly, the “F-UCB" policy (an extension of the UCB1 policy of auer2002finite), and secondly the “F-aMOSS" policy (an extension of the anytime MOSS policy of degenne2016anytime), cf. Theorems (ref) and (ref).

Our lower bounds hold under very weak assumptions. Therefore, they settle firmly what can and cannot be achieved in a functional sequential treatment assignment problem.

As a corollary to our results, comparing the regret upper bounds derived for the F-UCB and the F-aMOSS policy to the lower bound obtained for explore-then-commit policies, we reveal that in terms of maximal expected regret all explore-then-commit policies are inferior to the F-UCB and the F-aMOSS policy, and therefore should not be used if it can be avoided. If an explore-then-commit policy has to be used, our results provide guidance on the optimal length of the exploration period.

In Sections (ref) and (ref) we provide numerical results (based on simulated and empirical data) comparing the regret-behavior of explore-then-commit policies with that of the F-UCB and the F-aMOSS policy. In this context we develop test-based and empirical-success-based explore-then-commit policies that might be of independent interest, because they provably possess desirable performance guarantees.

Concerning the functionals we permit our theory is very general. We verify in detail that it covers many inequality, welfare, and poverty measures, such as the Schutz coefficient, the Atkinson-, Gini- and Kolm-indices. This discussion can be found in Appendix (ref). We also show that our theory covers quantiles, U-functionals, generalized L-functionals, and trimmed means. These results can be found in Appendix (ref). The results in these appendices are of high practical relevance, because they allow the policy maker to choose the functional-dependent constants appearing in the optimal policies in such a way that the performance guarantees apply.

In the companion paper kpv2 we address the important but nontrivial question how to construct policies that optimally incorporate covariate information. The results in the present paper are crucial for obtaining those results.

Setting and assumptions

We consider a setting, where at each point in time $t=1,\hdots,n$ a policy maker must assign a subject to one out of $K$ treatments. Each subject is only treated once.\footnote{We emphasize that the sequential setting is different from the “longitudinal” or “dynamic” one in, e.g., robins1997causal, lavori2000flexible, murphy2001marginal, murphy2003optimal and murphy2005experimental, where the same subjects are treated repeatedly.} Thus, the index $t$ can equivalently be thought of as indexing subjects instead of time. The observational structure is the one of a multi-armed bandit problem: After assigning a treatment, its outcome is observed, but the policy maker does not observe the counterfactuals. Having observed the outcomes of treatments $1,\hdots,t-1$, subject $t$ arrives, and must be assigned to a treatment. The assignment can be based on the information gathered from all previous assignments and their outcomes, and, potentially, randomization. Thus, the data set is gradually constructed in the course of the treatment program. Without knowing a priori the identity of the “best” treatment, the policy maker seeks to assign subjects to treatments so as to minimize maximal expected regret (which we introduce in Equation (ref) further below).

This setting is a sequential version of the potential outcomes framework with multiple treatments. Note also that restricting attention to problems where only one out of the $K$ treatments can be assigned does not exclude that a treatment consists of a combination of several other treatments (for example a combination of several drugs) --- one simply defines this combined treatment as a separate treatment at the expense of increasing the set of treatments.

The precise setup is as follows: let the random variable $Y_{i,t}$ denote the potential outcome of assigning subject $t\in\cbr[0]{1,\hdots,n}$ to treatment $i\in\mathcal{I}:=\cbr[0]{1,\hdots,K}$.\footnote{We do not explicitly consider the case of individuals arriving in batches. However, in our setup, one may also interpret $Y_{i,t}$ as a summary statistic of the outcomes of batch $t$, when all of its subjects were assigned to treatment $i$. For a more sophisticated way of handling batched data in case of targeting the mean treatment outcome, we refer to perchet2016batched.} That is, the potential outcomes of subject $t$ are $Y_t := (Y_{1,t}, \hdots, Y_{K, t})$. We assume that $a \leq Y_{i,t} \leq b$, where $a<b$ are real numbers. Furthermore, for every $t$, let $G_t$ be a random variable, which can be used for randomization in assigning the $t$-th subject. Throughout, we assume that $Y_t$ for $t \in \mathbb{N}$ are independent and identically distributed (i.i.d.); and we assume that the sequence $G_t$ is i.i.d., and is independent of the sequence $Y_t$. Note that no assumptions are imposed concerning the dependence between the components of each random vector $Y_t$. We think of the randomization measure, i.e., the distribution of $G_t$, as being fixed, e.g., the uniform distribution on $[0, 1]$. We denote the cumulative distribution function (cdf) of $Y_{i,t}$ by $F^i \in D_{cdf}([a,b])$, where $D_{cdf}([a,b])$ denotes the set of all cdfs $F$ such that $F(a-) = 0$ and $F(b) = 1$. The cdfs $F^i$ for $i = 1, \hdots, K$ are unknown to the policy maker.

A policy is a triangular array of (measurable) functions $\pi=\cbr[0]{\pi_{n,t}: n \in \mathbb{N}, 1\leq t\leq n}$. Here $\pi_{n,t}$ denotes the assignment of the $t$-th subject out of $n$ subjects. In each row of the array, i.e., for each $n\in \mathbb{N}$, the assignment $\pi_{n,t}$ can depend only on previously observed treatment outcomes and randomizations (previous and current). Formally,

equation[equation omitted — 120 chars of source]

Given a policy $\pi$ and $n\in \mathbb{N}$, the input to $\pi_{n,t}$ is denoted as $(Z_{t-1}, G_t)$. Here $Z_{t-1}$ is defined recursively: The first treatment $\pi_{n,1}$ is a function of $G_1$ alone, as no treatment outcomes have been observed yet (we may interpret $(Z_{0}, G_1) = G_1$). The second treatment is a function of $Z_1:=(Y_{\pi_{n,1}(G_1),1}, G_1)$, the outcome of the first treatment and the first randomization, and of $G_2$. For $t \geq 3$ we have $$Z_{t-1}:=(Y_{\pi_{n,t-1}(Z_{t-2},G_{t-1}), t-1}, G_{t-1}, Z_{t-2}) = (Y_{\pi_{n,t-1}(Z_{t-2},G_{t-1}), t-1}, G_{t-1}, \hdots, Y_{\pi_{n,1}(G_{1}),1}, G_{1}).$$ The $2(t-1)$-dimensional random vector $Z_{t-1}$ can be interpreted as the information available after the $(t-1)$-th treatment outcome was observed. We emphasize that $Z_{t-1}$ depends on the policy $\pi$ via $\pi_{n,1}, \hdots, \pi_{n, t-1}$. In particular, $Z_{t-1}$ also depends on $n$, which we do not show in our notation. For convenience, the dependence of $\pi_{n,t}(Z_{t-1}, G_t)$ on $Z_{t-1}$ and $G_t$ is often suppressed, i.e., we often abbreviate $\pi_{n,t}(Z_{t-1}, G_t)$ by $\pi_{n,t}$ if it is clear from the context that the actual assignment $\pi_{n,t}(Z_{t-1}, G_t)$ is meant, instead of the function defined in Equation (ref).

remark[Concerning the dependence of $\pi_{n,t}$ on the horizon $n$] We have chosen to allow the assignments $\pi_{n,1}, \hdots, \pi_{n,n}$ to depend on $n$, the total number of assignments to be made. Consequently, for $n_1<n_2$ it may be that $\cbr[0]{\pi_{n_1,t}:1\leq t\leq n_1}$ does not coincide with the first $n_1$ elements of $\cbr[0]{\pi_{n_2,t}:1\leq t\leq n_2}$. This is crucial, as a policy maker who knows $n$ may choose different sequences of allocations for different $n$. For example, one may wish to explore the efficacies of the available treatments in more detail if one knows that the total sample size is large, such that there is much opportunity to benefit from this knowledge later on. We emphasize that while our setup allows us to study policies that make use of $n$, we devote much attention to policies that do not. The latter subclass of policies is important. For example, a policy maker may want to run a treatment program for a year, say, but it is unknown in advance how many subjects will arrive to be treated. In such a situation, one needs a policy that works well irrespective of the unknown horizon. Such policies are called “anytime policies,” as $\pi_t:=\pi_{n,t}$ does not depend on $n$.

The ideal solution of the policy maker would be to assign every subject to the “best” treatment. In the present paper, this is understood in the sense that the outcome distribution for the best treatment maximizes a given functional

equation[equation omitted — 83 chars of source]

We do not assume that the maximizer is unique, i.e., $\operatorname*{arg\,max}_{i \in \mathcal{I}} \mathsf{T}(F^i)$ need not be a singleton. The specific functional chosen by the policy maker will depend on the application, and encodes the particular distributional characteristics the policy maker is interested in. For a streamlined presentation of our results it is helpful to keep the functional $\mathsf{T}$ abstract at this point (see Section (ref) below for an example, and a brief overview of examples we study in detail in appendices).

The ideal solution of the policy maker of assigning each subject to the best treatment is infeasible, simply because it is not known in advance which treatment is best. Therefore, every policy will make mistakes. To compare different policies, we define the (cumulative) regret of a policy $\pi$ at horizon $n$ as

equation[equation omitted — 227 chars of source]

i.e., for every individual subject that is not assigned to the best treatment one incurs a loss. One important feature of $R_n(\pi)$ is that the losses incurred at time $t$ cannot be nullified by later assignments. As discussed in the introduction, cumulative regret functions have previously been used by maillard, zimin2014generalized, kock2017optimal and vakili2018decision, the latter explicitly emphasizing the practical relevance of this regret notion in the context of clinical trials where the loss in each individual assignment needs to be controlled.

The unknown outcome distributions $F^1, \hdots, F^K$ are assumed to vary in a pre-specified class of cdfs. Following the minimax-paradigm, we evaluate policies according to their worst-case behavior over such classes. We refer to manski2016sufficient for further details concerning the minimax point-of-view in the context of treatment assignment problems, and for a comparison with other approaches such as the Bayesian. Formally, we seek a policy $\pi$ that minimizes maximal expected regret, that is, a policy that minimizes

equation[equation omitted — 113 chars of source]

where $\mathscr{D}$ is a subset of $D_{cdf}([a,b])$. The supremum is taken over all potential outcome vectors $Y_t$ such that the marginals $Y_{i,t}$ for $i = 1, \hdots, K$ have a cdf in $\mathscr{D}$. The set $\mathscr{D}$ will typically be nonparametric, and corresponds to the assumptions one is willing to impose on the cdfs of each treatment outcome, i.e., on $F^1, \hdots, F^K$. Note that the maximal expected regret of a policy $\pi$ as defined in the previous display depends on the horizon $n$. We will study this dependence on $n$. In particular, we will study the rate at which the maximal expected regret increases in $n$ for a given policy $\pi$; furthermore, we will study the question of which kind of policy is optimal in the sense that the rate is optimal.

The following assumption is the main requirement we impose on the functional $\mathsf{T}$ and the set $\mathscr{D}$. We denote the supremum metric on $D_{cdf}([a,b])$ by $\|\cdot\|_{\infty}$, i.e., for cdfs $F$ and $G$ we let $\|F-G\|_{\infty} = \sup_{x \in \mathbb{R}} |F(x) - G(x)|$.

assumptionThe functional $\mathsf{T}: D_{cdf}([a,b]) \to \mathbb{R}$ and the non-empty set $\mathscr{D} \subseteq D_{cdf}([a,b])$ satisfy \begin{equation} |\mathsf{T}(F) - \mathsf{T}(G)|\leq C\|F- G\|_{\infty} \quad for every \quad F \in \mathscr{D} and every G \in D_{cdf}([a,b]) \end{equation} for some $C > 0$.

remark[Restricted-Lipschitz continuity] Assumption (ref) implies that the functional $\mathsf{T}$ is Lipschitz continuous when restricted to $\mathscr{D}$ (the domain being equipped with $\|\cdot\|_{\infty}$). We emphasize, however, that if $\mathscr{D} \neq D_{cdf}([a,b])$, the functional $\mathsf{T}$ is not necessarily required to be Lipschitz-continuous on all of $D_{cdf}([a,b])$. This is due to the asymmetry inherent in the condition imposed in Equation (ref), where $F$ varies only in $\mathscr{D}$, but $G$ varies in all of $D_{cdf}([a,b])$.

remarkA simple approximation argument\footnote{ Let $\bar{F} \in D_{cdf}([a,b])$ be such that $\|F_m - \bar{F}\|_{\infty} \to 0$ as $m \to \infty$ for a sequence $F_m \in \mathscr{D}$, and let $G \in D_{cdf}([a,b])$. Then, $|\mathsf{T}(\bar{F}) - \mathsf{T}(G)| \leq |\mathsf{T}(\bar{F}) - \mathsf{T}(F_m)| + |\mathsf{T}(F_m) - \mathsf{T}(G)|$, which, by Assumption (ref), is not greater than $2C\|\bar{F} - F_m\|_{\infty} + C\|\bar{F} - G\|_{\infty} \to C\|\bar{F} - G\|_{\infty}$ as $m \to \infty$.} shows that if Assumption (ref) is satisfied with $\mathscr{D}$ and $C$, then Assumption (ref) is also satisfied with $\mathscr{D}$ replaced by the closure of $\mathscr{D} \subseteq D_{cdf}([a,b])$ (the ambient space $D_{cdf}([a,b])$ being equipped with the metric $\|\cdot\|_{\infty}$) and the same constant $C$.

remarkThe set $\mathscr{D}$ encodes assumptions imposed on the cdfs of each treatment outcome. In particular, the larger $\mathscr{D}$, the less restrictive is $F^i\in\mathscr{D}$ for $i\in\mathcal{I}$. Ideally, one would thus like $\mathscr{D} = D_{cdf}([a,b])$, which, however, is too much to ask for some functionals. Furthermore, there is a trade-off between the sizes of $C$ and $\mathscr{D}$, in the sense that a larger class $\mathscr{D}$ typically requires a larger constant $C$. The reader who wants to get an impression of some of the classes of cdfs we consider may want to consult Appendix (ref), where important classes of cdfs are defined.

Functionals that satisfy Assumption (ref): A summary of results in Appendix (ref) and Appendix (ref)

In the present paper, we do not contribute to the construction of functionals for specific questions. Rather, we take the functional as given. To choose an appropriate functional, the policy maker can already draw on a very rich and still expanding body of literature; cf. lambert, chakravarty2009 or cowell for textbook-treatments. To equip the reader with a specific and important example of a functional $\mathsf{T}$, one may think of the Gini-welfare measure (cf. SEN1974387)

equation[equation omitted — 120 chars of source]

Because all of our results impose Assumption (ref), a natural question concerns its generality. To convince the reader that Assumption (ref) is often satisfied, and to make the policies studied implementable (as they require knowledge of $C$), we show in Appendix (ref) that Assumption (ref) is satisfied for many important inequality, welfare, and poverty measures (together with formal results concerning the sets $\mathscr{D}$ along with corresponding constants $C$). For example, it is shown that for the above Gini-welfare measure, Assumption (ref) is satisfied with $\mathscr{D} = D_{cdf}([a,b])$, i.e., without any restriction on the treatment cdfs $F^1, \hdots, F^K$ (apart from having support $[a,b]$), and with constant $C = 2(b-a)$. At this point we highlight some further functionals that satisfy Assumption (ref):

enumerate• The inequality measures we discuss in Appendix (ref) include the Schutz-coefficient (schutz, schutzcomment), the Gini-index, the class of linear inequality measures of mehran, the generalized entropy family of inequality indices including Theil's index, the Atkinson family of inequality indices (atkinson1970), and the family of Kolm-indices (kolm1). In many cases, we discuss both relative and absolute versions of these measures. • In Appendix (ref) we provide results for welfare measures based on inequality measures. • The poverty measures we discuss in Section (ref) are the headcount ratio, the family of poverty measures of sen1976 in the generalized form of kakwani1980, and the family of poverty measures suggested by foster84.

The results in Appendices (ref), (ref), and (ref) mentioned above are obtained from and supplemented by a series of general results that we develop in Appendix (ref). These results verify Assumption (ref) for U-functionals defined in Equation (ref) (i.e., population versions of U-statistics, e.g., the mean or the variance), quantiles, generalized L-functionals due to serflinggen defined in Equation (ref), and trimmed U-functionals defined in Equation (ref). These techniques are of particular interest in case one wants to apply our results to functionals $\mathsf{T}$ that we do not explicitly discuss in Appendix (ref).

The results in Appendix (ref) and Appendix (ref) could also be of independent interest, because they immediately allow the construction of uniformly valid (over $\mathscr{D}$) confidence intervals and tests in finite samples. To see this, observe that Assumption (ref) together with the measurability Assumption (ref) given further below and the Dvoretzky-Kiefer-Wolfowitz-Massart inequality in massart1990 implies that, uniformly over $F \in \mathscr{D}$, the confidence interval $\mathsf{T}(\hat{F}_n) \pm C\sqrt{\log(2/\alpha)/(2n)}$ covers $\mathsf{T}(F)$ with probability not smaller than $1-\alpha$; here $\hat{F}_n$ denotes the empirical cdf based on an i.i.d. sample of size $n$ from $F$.

Further notation and an additional assumption

Before we consider maximal expected regret properties of certain classes of policies, we need to introduce some more notation: Given a policy $\pi$ and $n \in \mathbb{N}$, we denote the number of times treatment $i$ has been assigned up to time $t$ by

equation[equation omitted — 105 chars of source]

and we abbreviate $S_{i,n}(n) = S_{i}(n)$. Defining the loss incurred due to assigning treatment $i$ instead of an optimal one by $\Delta_i:=\max_{k \in \mathcal{I}}\mathsf{T}(F^{k})-\mathsf{T}(F^i)$, the regret $R_n(\pi)$, which was defined in Equation (ref), can equivalently be written as

align[align omitted — 158 chars of source]

On the event $\{S_{i,n}(t) > 0\}$ we define the empirical cdf based on the outcomes of all subjects in $\{1, \hdots, t\}$ that have been assigned to treatment $i$

equation[equation omitted — 211 chars of source]

Note that the random sampling times $s$ such that $\pi_{n, s}(Z_{s-1}, G_s) = i$ depend on previously observed treatment outcomes.

We shall frequently need an assumption that guarantees that the functional $\mathsf{T}$ evaluated at empirical cdfs, such as $\hat{F}_{i, t, n}$ just defined in Equation (ref), is measurable.

assumptionFor every $m \in \mathbb{N}$, the function on $[a,b]^m$ that is defined via $x \mapsto \mathsf{T}(m^{-1} \sum_{j = 1}^m \mathds{1}\cbr[0]{x_j \leq \cdot}),$ i.e., $\mathsf{T}$ evaluated at the empirical cdf corresponding to $x_1, \hdots, x_m$, is Borel measurable.

Assumption (ref) is typically satisfied and imposes no practical restrictions.

Finally, and following up on the discussion in Remark (ref), we shall introduce some notational simplifications in case a policy $\pi$ is such that $\pi_{n,t}$ is independent of $n$, i.e., is an anytime policy. It is then easily seen that the random quantities $S_{i,n}(t)$ and $\hat{F}_{i,t,n}$ do not depend on $n$ (as long as $t$ and $n$ are such that $n \geq t$). Therefore, for such policies, we shall drop the index $n$ in these quantities.

Explore-then-commit policies

A natural approach to assigning subjects to treatments in our sequential setup would be to first conduct a randomized controlled trial (RCT) to study which treatment is best, and then to use the acquired knowledge to assign the inferred best treatment to all remaining subjects. Such policies are special cases of explore-then-commit policies, which we study in this section. Informally, an explore-then-commit policy deserves its name as it (i) uses the first $n_1$ subjects to explore, in the sense that every treatment is assigned, in expectation, at least proportionally to $n_1$; and (ii) then commits to a single (inferred best) treatment after the first $n_1$ treatments have been used for exploration. Here, $n_1$ may depend on the horizon $n$.

Formally, we define an explore-then-commit policy as follows.

definition[Explore-then-commit policy] A policy $\pi$ is an explore-then-commit policy, if there exists a function $n_1: \mathbb{N} \to \mathbb{N}$ and an $\eta \in (0, 1)$, such that for every $n \in \mathbb{N}$ we have that $n_1(n) \leq n$, and such that the following conditions hold for every $n \geq K$: \begin{enumerate} • Exploration Condition: We have that $$\inf_{\substack{F^i \in \mathscr{D} \\ i = 1, \hdots, K}} \inf_{j \in \mathcal{I}}~\mathbb{E}[ S_{j,n}(n_1(n))] \geq \eta n_1(n).$$ Here, the first infimum is taken over all potential outcome vectors $Y_t$ such that the marginals $Y_{i,t}$ for $i = 1, \hdots, K$ have a cdf in $\mathscr{D}$. [That is, regardless of the (unknown) underlying marginal distributions of the potential outcomes, each treatment is assigned, in expectation, at least $\eta n_1(n)$ times among the first $n_1(n)$ subjects.] • Commitment Condition: There exists a function $\pi^c_n: ([a,b] \times \mathbb{R})^{n_1(n)}\to \mathcal{I}$ such that, for every $t = n_1(n)+1, \hdots, n$, we have \begin{equation} \pi_{n,t}(z_{t-1}, g) = \pi^c_n(z_{n_1(n)}) \quad for every z_{t-1} \in ([a,b] \times \mathbb{R})^{t-1} and every g \in \mathbb{R}, \end{equation} where $z_{n_1(n)}$ is the vector of the last $2n_1(n)$ coordinates of $z_{t-1}$. [That is, the subjects $t = n_1(n)+1, \hdots, n$ are all assigned to the same treatment, which is selected based on the $n_1(n)$ outcomes and randomizations observed during the exploration period.] \end{enumerate}

It would easily be possible to let the commitment rule $\pi_n^c$ depend on further external randomization. For simplicity, we omit formalizing such a generalization. We shall now discuss some important examples of explore-then-commit policies.

exampleA policy that first conducts an RCT based on a sample of $n_1(n) \leq n$ subjects, followed by any assignment rule for subjects $n_1(n) + 1, \hdots, n$ that satisfies the commitment condition in Definition (ref), is an explore-then-commit policy, provided the concrete randomization scheme used in the RCT encompasses sufficient exploration. In particular, $\pi_{n,t}(Z_{t-1},G_t)=G_t$ with $\mathbb{P}(G_t=i):=\frac{1}{K}$ for every $1 \leq t \leq n_1(n)$ and every $i\in\mathcal{I}$ satisfies the exploration condition in Definition (ref) with $\eta=\frac{1}{K}$; more generally, Definition (ref) holds if $\eta := \inf_{i \in \mathcal{I}} \mathbb{P}(G_t = i) >0$. Alternatively, a policy that enforces balancedness in the exploration phase through assigning subjects $t = 1, \hdots, n_1(n)$ to treatments “cyclically,” i.e., $\pi_{n,t}(Z_{t-1}, G_t) = (t \mod K) + 1$, satisfies the exploration condition in Definition (ref) with $\eta = 1/(2K)$ if $n_1(n) \geq K$ for every $n \geq K$. Concrete choices for commitment rules for subjects $n_1(n) + 1, \hdots, n$ include: \begin{enumerate} • In case $K=2$, a typical approach is to assign the fall-back treatment if, according to some test, the alternative treatment is not significantly better, and to assign the alternative treatment if it is significantly better. The sample size $n_1(n)$ used in the RCT is typically chosen to ensure that the specific test used achieves a desired power against a certain effect size. We refer to the description of the ETC-T policy in Section (ref) for a specific example of a test and a corresponding rule for choosing $n_1$, of which we establish that it achieves the desired power requirement (while holding the size). • As an alternative to test-based commitment rules, one can use an empirical success rule as in manski2004statistical, which in our general context amounts to assigning an element of $\operatorname*{arg\,max}_{i \in \mathcal{I}} \mathsf{T}(\hat{F}_{i, n_1(n),n})$ to subjects $n_1(n)+1, \hdots, n$. Specific examples of such a policy, together with concrete ways of choosing $n_1$ that come with certain performance guarantees, are discussed in Policy (ref) below and in the description of the ETC-ES policy in Section (ref). \end{enumerate}

We now establish regret lower bounds for the class of explore-then-commit policies. To exclude trivial cases, we assume that $\mathscr{D}$ (which is typically convex) contains a line segment on which the functional $\mathsf{T}$ is not everywhere constant.

assumptionThe functional $\mathsf{T}: D_{cdf}([a,b]) \to \mathbb{R}$ satisfies Assumption (ref), and $\mathscr{D}$ contains two elements $H_1$ and $H_2$, such that \begin{equation} J_{\tau} := \tau H_1 + (1-\tau)H_2 \in \mathscr{D} \quad for every \tau \in [0, 1], \end{equation} and such that $\mathsf{T}(H_1) \neq \mathsf{T}(H_2)$.

Since there only have to exist two cdfs $H_1$ and $H_2$ as in Assumption (ref), this is a condition that is practically always satisfied.

The next theorem considers general explore-then-commit policies, as well as the subclass of policies where $n_1(n)\leq n^*$ holds for every $n \in \mathbb{N}$ for some $n^* \in \mathbb{N}$. This subclass models situations, where the horizon $n$ is unknown or ignored in planning the experiment, and the envisioned number of subjects used for exploration $n^*$ is fixed in advance (here $n_1(n) = n^*$ for every $n \geq n^*$, and $n_1(n) = n$, else); the subclass also models situations where the sample size that can be used for experimentation is limited due to budget constraints.

theoremSuppose $K = 2$ and that Assumption (ref) holds. Then the following statements hold:\footnote{The constants $c_l$ depend on properties of the function $\tau \mapsto \mathsf{T}(J_{\tau})$ for $\tau \in [0, 1]$. More specifically, the constants depend on the quantities $\varepsilon$ and $c_-$ from Lemma (ref). The precise dependence is made explicit in the proof.} \begin{enumerate} • There exists a constant $c_l > 0$, such that, for every explore-then-commit policy $\pi$ that satisfies the exploration condition with $\eta \in (0, 1)$, and for any randomization measure, it holds that \begin{align*} \sup_{\substack{F^i \in \{J_{\tau} : \tau \in [0,1]\} \\ i = 1, 2}}\mathbb{E} [R_n(\pi)] \geq \eta c_l n^{2/3} \quad for every n \geq 2. \end{align*} • For every $n^* \in \mathbb{N}$ there exists a constant $c_l = c_l(n^*)$, such that, for every explore-then-commit policy $\pi$ that satisfies (i) the exploration condition with $\eta \in (0,1)$ and (ii) $n_1(\cdot)\leq n^*$, and for any randomization measure, it holds that \begin{align*} \sup_{\substack{F^i \in \{J_{\tau} : \tau \in [0,1]\} \\ i = 1, 2}}\mathbb{E} [R_n(\pi)] \geq \eta c_l n \quad for every n \geq 2. \end{align*} \end{enumerate}

The first part of Theorem (ref) shows that, under the minimal assumption of $\mathscr{D}$ containing a line segment on which $\mathsf{T}$ is not constant, any explore-then-commit policy must incur maximal expected regret that increases at least of order $n^{2/3}$ in the horizon $n$.

The second part implies in particular that when $n$ is unknown, such that the exploration period $n_1$ cannot depend on it, any explore-then-commit policy must incur linear maximal expected regret. We note that this is the worst possible rate of regret, since by Assumption (ref) no policy can have larger than linear maximal expected regret.

The lower bounds on maximal expected regret are obtained by taking the maximum only over all potential outcome vectors with marginal distributions in the line segment in Equation (ref). This is a one-parametric subset of $\mathscr{D}$ over which $\mathsf{T}$ nevertheless varies sufficiently to obtain a good lower bound.

We now prove that a maximal expected regret of rate $n^{2/3}$ is attainable in the class of explore-then-commit policies, i.e., we show that the lower bound in the first part of Theorem (ref) cannot be improved upon. In particular, we show that employing an empirical success type commitment rule after an RCT in the exploration phase as discussed in Example (ref) yields a maximal expected regret of this order. To be precise, we consider the following policy, which in contrast to test-based commitment rules (which require the choice of a suitable test and taking into account multiple-comparison issues in case $K>2$) can be implemented seamlessly for any number of treatments:

\onehalfspacing

policy[H] \caption{Explore-then-commit empirical-success policy $\tilde{\pi}$ } \For{$t = 1, \hdots, n_1(n) := \min(K \lceil n^{2/3} \rceil, n)$}{assign $\tilde{\pi}_{n,t}(Z_{t-1}, G_t) = G_t$, with $G_t$ uniformly distributed on $\mathcal{I}$} \For{$t = n_1(n)+1, \hdots, n$}{assign $\tilde{\pi}_{n,t}(Z_{t-1}, G_t) = \min \operatorname*{arg\,max}\limits_{i: S_{i, n}(n_1(n)) > 0} \mathsf{T}(\hat{F}_{i,n_1(n), n})$}

\doublespacing

Note that the policy $\tilde{\pi}$ is an explore-then-commit policy that requires knowledge of the horizon $n$, which by Theorem (ref) is necessary for obtaining a rate slower than $n$. The outer minimum in the second for loop in the policy is just taken to break ties (if necessary). Our result concerning $\tilde{\pi}$ is as follows (an identical statement can be established for a version of $\tilde{\pi}$ with cyclical assignment during the exploration phase as discussed in Remark (ref); the proof follows along the same lines, and we skip the details).

theoremUnder Assumptions (ref) and (ref), the explore-then-commit empirical-success policy $\tilde{\pi}$ satisfies \begin{equation} \sup_{\substack{F^i \in \mathscr{D} \\ i = 1, \hdots, K }} \mathbb{E} [R_n(\tilde{\pi})] \leq 6CKn^{2/3} \quad for every n \in \mathbb{N}. \end{equation}

Theorems (ref) and (ref) together prove that within the class of explore-then-commit policies, the policy $\tilde{\pi}$ is rate optimal in $n$. An upper bound as in Theorem (ref) for the special case of the mean functional can be found in Chapter 6 of lattimore2019bandit. We shall next show that policies which do not separate the exploration and commitment phase can obtain lower maximal expected regret. In this sense, the natural idea of separating exploration and commitment phases turns out to be suboptimal from a decision-theoretic point-of-view in functional sequential treatment assignment problems.

The finding that for large classes of functional targets explore-then-commit policies are suboptimal in terms of maximal expected regret does, of course, by no means discredit RCTs and subsequent testing for other purposes. For example, RCTs are often used to test for a causal effect of a treatment, cf. imbens2009recent for an overview and further references. The goal of the present article is not to test for a causal effect, but to assist the policy maker in minimizing regret, i.e., to keep to a minimum the sum of all losses due to assigning subjects wrongly. This goal, as pointed out in, e.g., manski2004statistical, manski2016sufficient and manski2019treatment, is only weakly related to testing. For example, the policy maker may care about more than just controlling the probabilities of Type 1 and Type 2 errors. In particular the magnitude of the losses when errors occur are important components of regret.

Functional UCB-type policies and regret bounds

In this section we define and study two policies based on upper-confidence-bounds. We start with the Functional Upper Confidence Bound (F-UCB) policy. It is inspired by the UCB1 policy of auer2002finite for multi-armed bandit problems targeting the mean, which is derived from a policy in agrawal1995sample, building on lai1985asymptotically. Extensions of the UCB1 policy to targeting risk functionals have been considered by NIPS2012_4753, maillard, zimin2014generalized, 7515237, and vakili2018decision. The F-UCB policy can target any functional (and reduces to the UCB1 policy of auer2002finite in case one targets the mean). It has the practical advantage of not needing to know the horizon $n$, cf. Remark (ref) (recall also the notation introduced in Section (ref)). Furthermore, no external randomization is required, which will therefore be notationally suppressed as an argument to the policy. The policy is defined as follows, where $C$ is the constant from Assumption (ref).

\onehalfspacing

policy[H] \caption{F-UCB policy $\hat{\pi}$ } Input: $\beta > 2$ \\ \For{$t = 1, \hdots, K$}{assign $\hat{\pi}_{t}(Z_{t-1}) = t$} \For{$t \geq K+1$}{assign $\hat{\pi}_{t}(Z_{t-1}) = \min \operatorname*{arg\,max}_{i\in \mathcal{I}}\cbr[2]{\mathsf{T}(\hat{F}_{i,t-1})+C\sqrt{ \beta \log(t)/(2 S_i(t-1))}}$}

\doublespacing

After the $K$ initialization rounds, the F-UCB policy assigns a treatment that i) is promising, in the sense that $\mathsf{T}(\hat{F}_{i,t-1})$ is large, or ii) has not been well explored, in the sense that $S_i(t-1)$ is small. The parameter $\beta$ is chosen by the researcher and indicates the weight put on assigning scarcely explored treatments, i.e., treatments with low $S_i(t-1)$. An optimal choice of $\beta$, minimizing the upper bound on maximal expected regret, is given after Theorem (ref) below. We use the notation $\overline{\log}(x):=\max(\log(x), 1)$ for $x > 0$.

theoremUnder Assumptions (ref) and (ref), the F-UCB policy $\hat{\pi}$ satisfies \begin{align} \sup_{\substack{F^i \in \mathscr{D} \\ i = 1, \hdots, K }}\mathbb{E} [R_n(\hat{\pi})]\leq c\sqrt{K n \overline{\log}(n)} \quad for every n \in \mathbb{N}, \end{align} where $c=c(\beta,C) = C \sqrt{ 2 \beta + (\beta+2)/(\beta-2)}$.

The upper bound on maximal expected regret just obtained is increasing in the number of available treatments $K$. This is due to the fact that it becomes harder to find the best treatment as the number of available treatments increases. Note also that the choice $\beta=2+\sqrt{2}$ minimizes $c(\beta,C)$ and implies $c\leq\sqrt{11}C$.

In case of the mean functional, an upper bound as in Theorem (ref) can be obtained from Theorem 1 in auer2002finite as explained after Theorem 2 in MOSS, cf. also the discussion in Section 2.4.3 of bubeck2012regret.\footnote{High-probability bounds as in Theorem 8 in audibert2009exploration can also be obtained for the F-UCB policy, cf. Theorem (ref) in Appendix (ref).} The proof of Theorem (ref) is inspired by their arguments. However, we cannot exploit the specific structure of the mean functional and related concentration inequalities. Instead we rely on the high-level condition of Assumption (ref) and the Dvoretzky-Kiefer-Wolfowitz-Massart inequality as established by massart1990 to obtain suitable concentration inequalities, cf. Equation (ref) in Appendix (ref). Since adaptive sampling introduces dependence, we also need to take care of the fact that the empirical cdfs defined in (ref) are not directly based on a fixed number of i.i.d. random variables. This is done via the optional skipping theorem of doob, cf. Appendix (ref). For functionals that can be written as a Lipschitz-continuous function of the first and second moment (a situation where Assumption (ref) holds), an upper bound of the same order as in Theorem (ref) has been obtained in kock2017optimal for a successive-elimination type policy.

The lower bound in Theorem (ref) combined with the upper bound in Theorem (ref) shows that the maximal expected regret incurred by any explore-then-commit policy grows much faster in $n$ than that of the F-UCB policy. What is more, the F-UCB policy achieves this without making use of the horizon $n$. Thus, in particular when $n$ is unknown, a large improvement is obtained over any explore-then-commit policy, as the order of the regret decreases from $n$ to $\sqrt{n\log(n)}$. Hence, in terms of maximal expected regret, the policy maker is not recommended to separate the exploration and commitment phases.

Theorem (ref) leaves open the possibility that one can construct policies with even slower growth rates of maximal expected regret. We now turn to establishing a lower bound on maximal expected regret within the class of all policies. In particular, the theorem also applies to policies that incorporate the horizon $n$.

theoremSuppose $K = 2$ and that Assumption (ref) holds. Then there exists a constant $c_l > 0$, such that for any policy $\pi$ and any randomization measure, it holds that \begin{align} \sup_{\substack{F^i \in \{J_{\tau} : \tau \in [0,1]\} \\ i = 1, 2}} \mathbb{E} [R_n(\pi)] \geq c_ln^{1/2} \quad for every n \in \mathbb{N}. \end{align}

Under the same assumptions used to establish the lower bound on maximal expected regret in the class of explore-then-commit policies, Theorem (ref) shows that any policy must incur maximal expected regret of order at least $n^{1/2}$. In combination with Theorem (ref) this shows that, up to a multiplicative factor of $\sqrt{\log(n)}$, no policy exists that has a better dependence of maximal expected regret on $n$ than the F-UCB policy. In this sense the F-UCB policy is near minimax (rate-) optimal.

For the special case of the mean functional a lower bound as in Theorem (ref) was given in Theorem 7.1 in auer1995gambling. Their proof is based on suitably chosen Bernoulli cdfs with parameters about $1/2$, and thus provides a lower bound over all sets $\mathscr{D}$ containing these cdfs, in particular over $D_{cdf}([0,1])$. Depending on the functional considered, however, Bernoulli cdfs may not create sufficient variation in the functional to get good lower bounds. Furthermore, Bernoulli cdfs may not be contained in $\mathscr{D}$, if, e.g., the latter does not contain discrete cdfs, in which case a lower bound derived for Bernoulli cdfs is not informative. For these two reasons, we have tailored the lower bound towards the functional and parameter space $\mathscr{D}$ under consideration. As in the proof of Theorem (ref) this is achieved by working with a suitably chosen one-parametric family of binary mixture cdfs of elements of the functional-specific line segment $\{J_{\tau} : \tau \in [0,1]\}$; cf. Lemma (ref) in Appendix (ref).

It is natural to ask whether a policy exists, which avoids the factor of $\sqrt{\log(n)}$ appearing in Theorem (ref). In the special case of the mean functional, MOSS and degenne2016anytime answered this question affirmatively for the MOSS policy and an anytime MOSS policy, respectively. As the second policy in this section, following the construction in degenne2016anytime, we now consider a Functional anytime MOSS (F-aMOSS) policy, and establish an upper bound on its maximal expected regret that matches the lower bound in Theorem (ref). The policy is of UCB-type in the sense that it proceeds similarly as Policy (ref), but uses a slightly different confidence bound; cf. Policy (ref) where for $x > 0$ we write $\log^+(x) = \max(\log(x), 0)$,

\onehalfspacing

policy[H] \caption{F-aMOSS policy $\check{\pi}$ } Input: $\beta > 1/4$ \\ \For{$t = 1, \hdots, K$}{assign $\check{\pi}_{t}(Z_{t-1}) = t$} \For{$t \geq K+1$}{assign $\check{\pi}_{t}(Z_{t-1}) = \min \operatorname*{arg\,max}_{i\in \mathcal{I}}\cbr[2]{\mathsf{T}(\hat{F}_{i,t-1})+C \sqrt{\frac{\beta}{S_i(t-1)} \log^+\left(\frac{t-1}{ KS_i(t-1)}\right) }}$}

\doublespacing A regret upper bound for the F-aMOSS policy is given next.

theoremUnder Assumptions (ref) and (ref), the F-aMOSS policy $\check{\pi}$ satisfies \begin{align} \sup_{\substack{F^i \in \mathscr{D} \\ i = 1, \hdots, K }}\mathbb{E} [R_n(\check{\pi})]\leq C (4.83 + 6.66 \times d(\beta) + \sqrt{2\beta})\sqrt{\pi} \sqrt{K n} \quad for every n \in \mathbb{N}, \end{align} for $d(\beta) = \frac{( \beta W_0(e/4 \beta))^{\frac{1}{2}}}{ 1-(4\beta W_0(e/4 \beta))^{\frac{1}{2}-\frac{1}{2 W_0(e/4 \beta)}}}$, and for $W_0$ the inverse of $w \mapsto w e^w$ on $(0, \infty)$.

To prove the result, we generalize to the functional setup a novel argument recently put forward by garivier2018kl for obtaining a regret upper bound for the anytime MOSS policy of degenne2016anytime. As in the proof of Theorem (ref) we need to replace arguments relying on concentration inequalities for the mean, and rely heavily on optional skipping arguments. Furthermore, in contrast to garivier2018kl, we do not only consider the case $\beta = 1/2$, but we show that the argument actually goes through for $\beta > 1/4$, also expanding the range $\beta > 1/2$ considered in degenne2016anytime.\footnote{Interestingly, in the special case of the mean functional (with $\mathscr{D} = D_{cdf}([0, 1])$), Theorem (ref) shows that the multiplicative constant $113$ given in Theorem 3 of degenne2016anytime for $\beta = 2.35/2$ can be improved to $(4.83 + 6.66 \times d(2.35/2) + \sqrt{2.35})\sqrt{\pi} \approx 32.5$.} This establishes theoretical guarantees for parameter values close to $1/4$, which turned out best in their numerical results (but for which no regret guarantees were provided). Finally, we note that while the upper bound just given is of the order $\sqrt{n}$, and improves on the upper bound for the F-UCB policy in this sense, this is bought at a price: the multiplicative constant appearing in the upper bound is larger than that obtained in Theorem (ref).

Numerical illustrations

We now illustrate the theoretical results established in this article by means of simulation experiments. Throughout this section, the treatment outcome distributions $F^i$ will be taken from the Beta family, a parametric subset of $D_{cdf}([0, 1])$, which has a long history in modeling income distributions; see, for example, thurow1970analyzing, mcdonald1984some and mcdonald2008generalized. An appealing characteristic of the Beta family is its ability to replicate many “shapes” of distributions. We emphasize that the policies investigated do not exploit that the unknown treatment outcome distributions are elements of the Beta family.

Our numerical results cover different functionals $\mathsf{T}$, with a focus on situations where the policy maker targets the distribution that maximizes welfare, and where we consider the case $a = 0$ and $b = 1$. In all our examples the feasible set for the marginal distributions of the treatment outcomes $\mathscr{D} = D_{cdf}([0, 1])$.

The specific welfare measures we consider are as follows (and correspond to the Gini-, Schutz- and Atkinson- inequality measure, respectively, through the transformations detailed in Appendix (ref), to which we refer the reader for more background information):

enumerate• Gini-index-based welfare measure: $\mathsf{W}(F)=\mu(F) - \frac{1}{2}\int \int |x_1 - x_2| dF(x_1) dF(x_2)$, where $\mu(F) := \int x dF(x)$ denotes the mean of $F$. [Assumption (ref) is satisfied with $\mathscr{D}= D_{cdf}([0,1])$ and $C=2$, cf. the discussion after Lemma (ref).] • Schutz-coefficient-based welfare measure: $\mathsf{W}(F)=\mu(F) - \frac{1}{2} \int |x - \mu(F)| dF(x)$. [Observing that $\mathsf{W}(F)=\mu(F) -\mathsf{S}_{abs}(F)$ with $\mathsf{S}_{abs}$ as defined in Equation (ref), it follows from Lemmas (ref) and (ref) that Assumption (ref) is satisfied with $\mathscr{D}= D_{cdf}([0,1])$ and $C=2$.] • Atkinson-index-based welfare measure: $\mathsf{W}(F)= [\int x^{1-\varepsilon}dF(x)]^{1/(1-\varepsilon)}$ for a parameter $\varepsilon\in (0,1)\cup (1,\infty)$. [Restricting attention to $\varepsilon\in(0,1)$, the mean value theorem along with Example (ref) in Appendix (ref) yield that Assumption (ref) is satisfied with $\mathscr{D}= D_{cdf}([0,1])$ and $C=\frac{1}{1-\varepsilon}$. We shall consider $\varepsilon\in\cbr[0]{0.1,0.5}$.]

In this section we consider two settings: (A) we compare the performance of explore-then-commit policies which do not incorporate $n$ with the F-UCB and the F-aMOSS policy (which also do not incorporate $n$); (B) as in (A) but where we now consider explore-then-commit policies that optimally incorporate $n$. Throughout in this section, we consider the case of $K = 2$ treatments. In the following, the symbol $\mathsf{W}$ shall denote one of the welfare measures just defined in the above enumeration.

Numerical results in Setting A

In this setting the total number of assignments to be made is not known from the outset. Thus, the policies we study do not make use of the horizon $n$. We consider explore-then-commit policies as in Section (ref), the F-UCB policy, and the F-aMOSS policy. While the F-UCB policy is implemented as in Policy (ref) of Section (ref) with $\beta = 2.01$, and the F-aMOSS policy is implemented as in Policy (ref) with $\beta = 1/3.99$, the concrete development of explore-then-commit policies with certain performance guarantees requires some additional work which we develop next.

Implementation details for explore-then-commit policies

In all explore-then-commit policies we consider, Treatments 1 and 2 are assigned cyclically in the exploration period. This ensures that the number of assignments to each treatment differs at most by $1$ (cf. also Example (ref) in Section (ref)).\footnote{Investigating policies with randomized assignment in the exploration phase would necessitate running the simulations repeatedly, averaging over different draws for the assignments in the exploration phase. The numerical results are already quite computationally intensive, which is why we only investigate a cyclical assignment scheme. This scheme already reflects to a good extent the average behavior of a randomized assignment with equal assignment probabilities.} Given this specification, the policy maker must still choose i) the length of the exploration period $n_1$, and ii) a commitment rule to be used after the exploration phase. The choice of $n_1$ (while independent of $n$) depends on the commitment rule, of which we now develop a test-based and an empirical-success-based variant:

enumerate• ETC-T: This policy is built around a test-based commitment rule. That is, one uses a test for the testing problem “equal welfare of treatments,” i.e., $\mathsf{W}(F^1) = \mathsf{W}(F^2)$, in deciding which treatment to choose after the exploration phase. Given a test that satisfies a pre-specified size requirement, the length of the exploration phase is chosen such that the power of the test against a certain deviation from the null (effect size) is at least of a desired magnitude. A typical desired amount of power against the deviation from the null of interest is 0.8 or 0.9. The deviation from the null that one wishes to detect is clearly context dependent. We refer to jacob1988statistical, murphy2014statistical and athey2017econometrics, as well as references therein, for in-depth treatments of power calculations. To make this approach implementable, we need to construct an appropriate test. Given $\alpha\in(0,1)$, and for $n_1 \geq 2$, we shall consider the test that rejects if (and only if) $|\mathsf{W}(\hat{F}_{1,n_1})-\mathsf{W}(\hat{F}_{2,n_1})|\geq c_\alpha$ with $c_\alpha=\sqrt{2\log(4/\alpha)C^2/\lfloor n_1/2\rfloor}$. Under the null, i.e., for every pair $F^1$ and $F^2$ in $D_{cdf}([0,1])$ such that $\mathsf{W}(F^1)=\mathsf{W}(F^2)$, this test has rejection probability at most $\alpha$ (a proof of this statement is provided in Appendix (ref)). Hence, the size of this test does not exceed $\alpha$. For this test, in order to detect a deviation of $\Delta:=|\mathsf{W}(F^1)-\mathsf{W}(F^2)|>0$ with probability at least $1-\eta$, where $\eta\in(0,1)$, it suffices that $n_1 = 2\lceil\frac{8\log(4/\min(\alpha, \eta))C^2}{\Delta^2}\rceil$ (for a proof of this statement, see Appendix (ref)). In our numerical studies we set $\eta=\alpha=0.1$. We consider $\Delta\in\cbr[0]{0.15,0.30}$, which amounts to a small and moderate desired detectable effect size, respectively. Note that while choosing $\Delta$ small allows one to detect small differences in the functionals by the above test, this comes at the price of a larger $n_1$. Thus, we shall see that neither $\Delta=0.15$ nor $\Delta=0.30$ dominates the other uniformly (over $t\in\mathbb{N}$) in terms of maximal expected regret. The commitment rule applied is to assign $\operatorname*{arg\,max}_{1\leq i\leq 2} \mathsf{W}(\hat{F}_{i,n_1})$ if the above test rejects, and to randomize the treatment assignment with equal probabilities otherwise. Finally, we sometimes make the dependence of ETC-T on $\Delta$ explicit by writing ETC-T($\Delta$). • ETC-ES: This policy assigns $\pi_{n}^c(Z_{n_1}): = \min\operatorname*{arg\,max}_{1\leq i\leq K} \mathsf{W}(\hat{F}_{i,n_1})$ to subjects $t=n_1+1,\hdots,n$, which is an empirical success commitment rule inspired by manski2004statistical and manski2016sufficient. Here, given a $\delta>0$, $n_1$ is chosen such that the maximal expected regret for every subject to be treated after the exploration phase is at most $\delta$; i.e., $n_1$ satisfies $$\sup_{\substack{F^i \in \mathscr{D} \\ i = 1, \hdots, K }}\mathbb{E}\del[1]{\max_{i\in\mathcal{I}}\mathsf{W}(F^i)-\mathsf{W}(F^{\pi_{n}^c(Z_{n_1})}}\leq \delta.$$ We prove in Appendix (ref) that $n_1 = 2 \lceil 16C^2/(\delta^2 \exp(1))\rceil$ suffices. In our numerical results, we consider $\delta\in\cbr[0]{0.15,0.30}$, which should be contrasted to the treatment outcomes taking values in $[0,1]$. Note that the $n_1$ required to guarantee a maximal expected regret of at most $\delta$ for every subject treated after the exploration phase is decreasing in $\delta$. Thus, we shall see that it need not be the case that choosing $\delta$ smaller will result in lower overall maximal expected regret. Finally, we sometimes make the dependence of ETC-ES on $\delta$ explicit by writing ETC-ES($\delta$).

The following display summarizes the numerical implementation.

\RestyleAlgo{boxed}

\onehalfspacing

simulation[H] Input: $n=100{,}000,\ r=20$ and\\ $\mathcal{G} = \{0.1,0.425,0.75,0.8,0.85,0.9,0.95,0.9625,0.975,0.9875, 1,1.0125,1.025,$\\$1.0375,1.05,1.10,1.15,1.20,1.25,3.125,5\}$ \For{$p_1\in\mathcal{G}$ such that $p_1 < 5$}{ \For{$p_2\in\mathcal{G},\ p_2>p_1$}{ \For{$l=1,\hdots,r$}{Generate~$n$ independent observations from~$\mathsf{Beta}(1,p_1) \otimes \mathsf{Beta}(1,p_2).$ \For{$t=1,\hdots,n$}{Calculate the regret of each policy over all assignments~$s=1,\hdots,t$. } } Estimate expected regret for each policy and for~$t = 1, \hdots, n$ by the arithmetic mean of regret over the~$r$ data sets. } } Estimate, for every~$t = 1, \hdots, n$, the maximal expected regret by maximizing the arithmetic means over the~$|\mathcal{G}|(|\mathcal{G}|-1)/2=210$ parameter vectors~$(p_1,p_2)$.

\doublespacing

\RestyleAlgo{ruled}

Since maximizing expected regret over all Beta distributions would be numerically infeasible, we have chosen to maximize expected regret over a subset of all Beta distributions indexed by $\mathcal{G}$ as defined in the previous display. We stress that since none of the three policies above needs to know $n$, the numerical results also contain the maximal expected regret of the policies for any sample size less than $n=100{,}000$.

Results

The left panel of Figure (ref) illustrates the maximal expected regret for the F-UCB, F-aMOSS, ETC-T and ETC-ES policies in the case of Gini-welfare. Each point on the six graphs is the maximum of expected regret over the $210$ different distributions considered at a given $t$. In accordance with Theorems (ref), (ref) and (ref), the maximal expected regret of the policies in the explore-then-commit family is generally higher than the one of the F-UCB and the F-aMOSS policy. For $t=100{,}000$, the maximal expected regret of F-UCB is $498$, and $159$ for F-aMOSS, while the corresponding numbers for ETC-T(0.15), ETC-ES(0.15), ETC-T(0.30) and ETC-ES(0.30) are $4{,}248$, $777$, $7{,}281$ and $836$, respectively. Note also that no matter the values of $\Delta$ and $\delta$, the maximal expected regret of ETC-ES($\delta$) is much lower than the one of the ETC-T($\Delta$) policy.\footnote{This result on the ranking of test-based vs. empirical success-based commitment rules is similar to an analogous finding in a non-sequential setting in manski2016sufficient.} In fact, we shall see for all functionals considered that the F-aMOSS policy generally incurs the lowest maximal expected regret, followed by the F-UCB policy and subsequently by the ETC-ES policies, which in turn perform much better than ETC-T policies.

figure[figure omitted — 434 chars of source]

The shape of the graphs of the maximal expected regret of the explore-then-commit policies can be explained as follows: in the exploration phase maximal expected regret is attained by a distribution $P_1$, say, for which the value of the Gini-welfare differs strongly at the marginals. However, such distributions are also relatively easy to distinguish, such that none of the commitment rules (testing or empirical success) assigns the suboptimal treatment after the exploration phase. This results in no more regret being incurred and thus a horizontal part on the maximal expected regret graph. For $t$ sufficiently large, however, maximal expected regret will be attained by a distribution $P_2$, say, for which the marginals are sufficiently “close” to imply that the commitment rules occasionally assign the suboptimal treatment. For such a distribution, the expected regret curve will have a positive linear increase even after the commitment time $n_1$ and this curve will eventually cross the horizontal part of the expected regret curve pertaining to $P_1$. This implies that maximal expected regret increases again (as seen for ETC-T(0.30) around $t=14{,}000$ and ETC-ES(0.30) around $t=23{,}000$ in the left panel of Figure (ref)). Such a kink also occurs for ETC-T(0.15) and eventually also for ETC-ES(0.15). Thus, the left panel of Figure (ref) illustrates the tension between choosing $n_1$ small in order to avoid incurring high regret in the exploration phase and, on the other hand, choosing $n_1$ large in order to ensure making the correct decision at the commitment time.

The right panel of Figure (ref), which contains the maximal expected regret for the Schutz-welfare, yields results qualitatively similar to the ones for the Gini-welfare. The best explore-then-commit policy again has a terminal maximal expected regret that is more than $4.8$ times that of the F-aMOSS policy.

figure[figure omitted — 491 chars of source]

We next turn to the two welfare measures in the Atkinson family. The left panel of Figure (ref) contains the results for the case of $\varepsilon=0.1$. While F-aMOSS incurs the lowest maximal expected regret uniformly over $t=1,\hdots,100{,}000$, the most remarkable feature of the figure is that maximal expected regret of all explore-then-commit policies is eventually increasing within the sample considered. The reason for this is that $\varepsilon=0.1$ implies a low value of $n_1$ such that i) the steep increase in maximal expected regret becomes shorter and ii) more mistakes are made at the commitment time. The ranking of the families of polices is unaltered with F-UCB and F-aMOSS dominating ETC-ES, which in turn incurs much lower regret than ETC-T.

The right panel of Figure (ref) considers the case of Atkinson welfare when $\varepsilon=0.5$. The findings are qualitatively similar to the ones for the Gini- and Schutz-based welfare measures.

Numerical results in Setting B

Implementation details

In this section we compare the explore-then-commit Policy (ref) (but with cyclical assignment in the exploration phase, cf. Footnote (ref)) with the F-UCB policy as implemented as in the previous subsection. Note that Policy (ref) depends on $n$ in an optimal way, cf. Theorem (ref), while the F-UCB policy does not incorporate $n$.

Results

Table (ref) contains maximal expected regret computations for Policy (ref) relative to that of the F-UCB policy for $n\in\cbr[0]{1{,}000;5{,}000;10{,}000;20{,}000;40{,}000;60{,}000}$. Thus, numbers larger than 1 indicate that the F-UCB policy has lower maximal expected regret. Since Policy (ref) is not anytime, cf. Remark (ref), to study its regret behavior it must be implemented and run anew for each $n$; i.e., for each $n$ we proceed as in the display describing the implementation details for Setting A, but only record the terminal value of the numerically determined maximal expected regret. Producing a plot analogous to Figure (ref) but for a policy incorporating $n$ would require us to run the simulation 100{,}000 times, i.e., one simulation per terminal sample size $n$, which would be extremely computationally intensive.\footnote{To reduce the computational cost we set $\mathcal{G} = \cbr[0]{0.1,0.75,0.85,0.95,0.975,1,1.025,1.05,1.15,1.25,5}$ in the results reported in the present section.} As can be seen from Table (ref), the F-UCB policy achieves lower expected regret than Policy (ref) at all considered horizons for all welfare measures even though the former policy does not make use of $n$ while the latter does. Note also that the relative improvement of the F-UCB policy over Policy (ref) is increasing in $n$ as suggested by our theoretical results.

table[table omitted — 586 chars of source]

As shown by the simulation results reported in the previous section, using the F-aMOSS policy as a benchmark instead of the F-UCB policy would lead to even larger relative improvements over the explore-then-commit Policy (ref).

Illustrations with empirical data

We here compare the performance of the policies using three (non-sequentially generated) empirical data sets, each containing the outcomes of a treatment program. From every data set we generate synthetic sequential data by sampling from the empirical cdfs corresponding to the treatment/control groups. That is, the empirical cdfs in the data sets are taken as the respective (unknown) treatment outcome distributions $F^1, \hdots, F^K$, from which observations are then drawn sequentially. This approach allows us to study the policies' performance on cdfs resembling specific characteristics arising in large scale empirical applications. The data sets considered are as follows; cf. also Appendix (ref).

enumerate[leftmargin=1cm] • The Cognitive Abilities program studied in hardy2015enhancing. In this RCT, the participants were split into a treatment group who participated in an online training program targeting various cognitive capacities and an active control group solving crossword puzzles. Thus, $K=2$. The outcome variable is a neuropsychological performance measure. • The Detroit Work First program studied in autor2010temporary and autor2017effect. Here low-skilled workers took temporary help jobs, direct hire jobs or exited the program. Thus, $K=3$. The outcome variable is the total earnings in quarters 2--8 after the start of the program. • The Pennsylvania Reemployment Bonus program studied originally in bilias2000sequential and also in, e.g., chernozhukov2018double. The participants in the program are unemployed individuals who are either assigned to a control group, or to one of five treatment groups who receive a cash bonus if they find and retain a job within a given qualification period. Thus, $K=6$. The size of the cash bonus and the length of the qualification period vary across the five treatment groups. The outcome variable is unemployment duration which varies from 1 to 52 weeks.

To facilitate the comparision with the other results in the previous section, all data were scaled to $[0,1]$, and we consider the Gini-, Schutz- and two Atkinson-welfare measures. We focus on the Gini-based-welfare, and report the results for the remaining functionals in Appendix (ref). The reported expected regrets are averages over $100$ replications, with $n=100{,}000$ in each setup. When interpreting the results, it is important to keep in mind that in contrast to the maximal expected regret studied in Section (ref), where for each $t$ the worst-case regret over a certain family of distributions is reported, the focus is now on three particular data sets, i.e., three instances of pointwise expected regret w.r.t. fixed distributions.

For the Detroit Work First Program, for which $K=3$, the ETC-ES policies are implemented as in Section (ref) with $\delta\in\cbr[0]{0.15,0.30}$. For the Pennsylvania Reemployment Bonus experiment, where $K=6$, this rule led to exploration periods exceeding $n=100{,}000$. Hence, we instead considered exploration periods assigning $250,\ 500,\ 750$ and $1{,}000$ observations to each of the six arms, respectively. We only implemented the ETC-T policies for the cognitive ability program for which $K=2$.\footnote{This is justified by the fact that these policies were always inferior in Section (ref). Furthermore, implementing the ETC-T policies when $K>2$ would require taking a stance on how to control the size of the (multiple) testing problem at the commitment time.} The F-UCB and F-aMOSS policies are implemented as in Section (ref).

figure[figure omitted — 441 chars of source]

The results for the Gini-welfare measure are summarized in Figure (ref). The main take-aways are: i) F-aMOSS performs solidly across all data sets. ii) Except for the cognitive training program data, the F-UCB policy is not among the best. Note that this is not in contradiction to the theoretical results of this paper (nor the simulations in Section (ref)) as these are concerned with the worst-case performance of the policies. iii) There always exists an exploration horizon such that an ETC-ES policy incurs a low expected regret (over the sample sizes considered). However, this horizon is data dependent: Note that for the cognitive and Pennsylvania data sets long exploration horizons are preferable, while for the Work First data the opposite is the case. From the Pennsylvania data it is also seen that the optimal length of the exploration horizon depends on the length of the program.

The figures containing the results for the remaining functionals are contained in Appendix (ref). For the Schutz- and Atkinson-welfare measure with $\varepsilon=0.5$ the results are qualitatively similar to those of the Gini-based welfare. Regarding the Atkinson-based welfare with $\varepsilon=0.1$, F-aMOSS and F-UCB now even incur the lowest regret for the cognitive data. For the Work First and Pennsylvania data F-aMOSS remains best (at the end of the program). It is interesting that for the Work First data the ordering of the two ETC-ES policies is reversed at the end of the treatment period compared to the remaining functionals. The latter observation again underscores the difficulty in getting the length of the exploration period “right." This echoes our theoretical results showing that there is no way of constructing an ETC-based rule that would uniformly dominate the UCB-type policies.

Conclusion

In this paper we have studied the problem of a policy maker who assigns sequentially arriving subjects to treatments. The quality of a treatment is measured through a functional of the potential outcome distributions. Drawing crucially on the results and the framework developed in the present paper, the companion paper kpv2 studies how the setting and regret notion can be adapted to allow for covariates, and explores how those can be optimally incorporated in the decision process.

\singlespacing

\doublespacing