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.
45,156 characters · 6 sections · 44 citation commands
Functional Sequential Treatment Allocation with Covariates
\and
\and
}
\onehalfspacing
Keywords: Sequential Treatment Allocation, Multi-Armed Bandit, Distributional Characteristics, Covariates, Minimax Optimal Expected Regret.
\doublespacing
The classical multi-armed bandit literature considers a sequential decision problem in which a policy maker attempts to assign subjects to the treatment with the highest expected outcome. Two practically relevant generalizations of this setting have attracted much attention: (i) a problem where the decision maker can incorporate a vector of covariates in the assignment of each subject, cf. woodroofe1979one, yang2002randomized, rigollet2010nonparametric and perchet2013multi; (ii) problems where instead of targeting the outcome distribution with highest expectation, the decision maker is interested in targeting another functional such as a quantile, a risk measure, or other characteristics of the distribution, cf. maillard, NIPS2012_4753, 7515237, vakili2018decision, zimin2014generalized, kock2017optimal, tran2014functional, cassel2018general. Particularly relevant for the present article is the recent paper kpv1, where a general theory is built for functional assignment problems albeit without covariates.
While both types of generalizations have been well studied in isolation, the only article we are aware of to consider a multi-armed bandit problem with a target other than the conditional expectation in the presence of covariates is kock2017optimal. That paper has two limitations: First, it considers the special class of functionals which can be written as a function of the conditional mean and the conditional variance. Therefore, many fundamental functionals are not covered by their theory, e.g., conditional quantiles or trimmed means. Secondly, regret lower bounds for functional targets (beyond the mean) are not discussed, and thus the question whether the algorithm they suggest is optimal remains open.
The goal of the present article is to develop a minimax expected regret optimality theory for multi-armed-bandit problems with functional targets and covariates. The regret function we work with is cumulative, i.e., every subject not assigned to the best treatment leads to a loss that cannot be offset by later assignments. The worst-case growth rate of the expected regret of a policy is thus linear in the number of assignments.
The structure of the paper is as follows: The framework is discussed in Section (ref). Here we first show that to obtain sublinear maximal expected regret it is not enough to assume that the conditional potential outcome distributions depend equicontinuously on the covariates. This insight motivates us to work with a minimally stronger Hölder-equicontinuity condition. As a consequence, even a slight relaxation of this assumption implies that every policy incurs the worst-case linear maximal expected regret. We also show that if a policy does not incorporate covariate information, then its regret grows linearly. In Section (ref) we introduce the functional upper-confidence-bound (F-UCB) policy in the presence of covariates. This is a binned version of the F-UCB policy introduced in kpv1, the binning being inspired by the UCBogram of rigollet2010nonparametric. We then establish regret upper bounds for the F-UCB policy and obtain lower bounds, proving its near minimax expected regret optimality. The lower bounds are established under an assumption that essentially only requires the functionals not to be constant over the set of potential outcome distributions considered. This requirement is very weak, and thus guarantees that the lower bounds hold even under quite stringent restrictions on the conditional outcome distributions.
We first obtain such bounds without restricting the similarity of the best and second best treatment. Intuitively, however, this similarity crucially influences the difficulty of the decision problem and is therefore an important component. In particular, one may ask whether the F-UCB policy automatically “adapts” in an optimal way to the degree of similarity. To regulate the degree of similarity, we work with a version of the “margin-condition” tailored towards our functional target; similar conditions have been used in mammen1999smooth, tsybakov2004optimal, audibert2007fast, perchet2013multi, and rigollet2010nonparametric, the latter article, albeit targeting the conditional expectation, being particularly important for our developments. We first derive an upper bound on maximal expected regret of the F-UCB policy over subclasses of distributions that---besides the above-mentioned Hölder condition---satisfy the margin condition. We then establish nearly matching lower bounds over the just-mentioned classes of distributions. Finally, we show that the expected number of suboptimal assignments made increases as slowly as possible in the number of assignments. The latter result can be interpreted as an ethical guarantee on the F-UCB policy: only few persons will receive a treatment which is not optimal for them. The proofs can be found in the appendices.
The observational structure in this paper is the one of a multi-armed bandit problem with covariates. That is, the subjects to be treated $t = 1, \hdots, n$ arrive sequentially, and have to be assigned to one out of $K \geq 2$ treatments. The assignment decision can incorporate previously observed outcomes, covariates and randomization. We denote the potential outcome of assigning subject $t$ to treatment $i$ by $Y_{i,t}$, and assume throughout that $a \leq Y_{i,t} \leq b$, where $a<b$ are real numbers. The vector of potential outcomes is denoted as $Y_t = (Y_{1, t}, \hdots, Y_{K, t})$; note that per subject only one coordinate of this vector can be observed. The covariate vector that comes with subject $t$ is denoted by $X_t$, and we assume throughout that $X_t\in [0,1]^d$. Furthermore, for every $t$, we let $G_t$ be a random variable, which can be used for randomization in assigning the $t$-th subject. Throughout this article, we assume that $(Y_t, X_t) = (Y_{1,t}, \ldots, Y_{K, t}, X_t)$ for $t \in \mathbb{N}$ are i.i.d.; and we assume that the sequence of randomizations $G_t$ is i.i.d., and is independent of the sequence $(Y_t, X_t)$. The distribution of $G_t$ will be referred to as the randomization measure, which we think about as being fixed, e.g., the uniform distribution on $[0, 1]$. Note that the dependence structure within each $Y_t$ is not restricted. We denote the distribution of $(Y_t, X_t)$ as $\mathbb{P}_{Y, X}$, and let $\mathbb{P}_X$ be the marginal distribution of $X_t$. The conditional cumulative distribution function (cdf) of $Y_{i,t}$ given $X_t = x$ is defined as $F^i(y, x) = \mathsf{K}^i((-\infty, y], x)$, where $\mathsf{K}^i: \mathcal{B}(\mathbb{R}) \times [0, 1]^d \to [0,1]$ denotes a regular conditional distribution of $Y_{i,t}$ given $X_t$, where $\mathcal{B}(\mathbb{R})$ are the Borel sets of $\mathbb{R}$. We shall often impose the following condition (cf. Remark (ref) for a discussion of discrete covariates).
A policy $\pi$ is a triangular\footnote{We allow a policy to incorporate $n$, because a decision maker who knows the number of subjects to be assigned might want to incorporate this into the assignment mechanism.} array $\{\pi_{n,t}: n \in \mathbb{N}, 1 \leq t\leq n \}$, where the assignment of the $t$-th subject $\pi_{n,t}$ takes as input the covariates $X_t$, previously observed outcomes, covariates and randomizations (i.e., the complete observational history), and a randomization $G_t$. We therefore have
Given a policy $\pi$ and $n\in \mathbb{N}$, the input to $\pi_{n,t}$ is denoted as $(X_t, Z_{t-1}, G_t)$, where $Z_{t-1}$ is defined recursively: The first treatment $\pi_{n,1}$ is a function of $(X_1, Z_{0}, G_1) = (X_1, G_1)$. The second treatment is a function of $X_2$, of $Z_1:=(Y_{\pi_{n,1}(X_1, Z_0, G_1),1}, X_1, G_1)$, and of $G_2$. For $t \geq 3$ we have $$Z_{t-1}:=(Y_{\pi_{n,t-1}(X_{t-1}, Z_{t-2},G_{t-1}), t-1}, X_{t-1}, G_{t-1}, Z_{t-2}).$$ The $(t-1)(d+2)$-dimensional random vector $Z_{t-1}$ can be interpreted as the information available after the $(t-1)$-th treatment outcome has been observed.
In the present article treatments are evaluated according to a functional $\mathsf{T}$ (e.g., the median) of the conditional potential outcome distribution, where the conditioning is on the covariates: The best assignment for a subject with covariate vector $x \in [0, 1]^d$ is defined as
where the minimum has been taken as a concrete choice of breaking ties.
We denote the “parameter”-space of all potential conditional cdfs $F^i(\cdot, x)$ by $\mathscr{D}$. More precisely, we assume that
where $\mathscr{D}$ is a potentially large and nonparametric subset of $D_{cdf}([a,b])$, the latter denoting the set of all cdfs on $\mathbb{R}$ satisfying $F(a-) = 0$ and $F(b) = 1$. Note that the set $\mathscr{D}$ encodes the assumptions one is willing to impose on the conditional outcome distributions.
The main assumption on $\mathsf{T}$ we work with in the present paper is a Lipschitz-type condition first introduced in kpv1 in the non-covariate setting. The assumption takes the following form, where $\|\cdot\|_{\infty}$ denotes the supremum metric on the set of cdfs on $\mathbb{R}$. For further discussion of the assumption see Remarks 2.3-2.5 in kpv1.
As discussed at length in Appendices C and E of kpv1, under suitable assumptions on $\mathscr{D}$, Assumption (ref) is satisfied, e.g., for quantiles, (trimmed) U-functionals, generalized L-functionals (cf. serflinggen), and many inequality-, poverty-, and welfare-measures important for socio-economic decision making. We keep the functional abstract in the present paper and refer the interested reader to the just-mentioned appendices for examples and detailed discussions. Apart from Assumption (ref), we shall also impose the following measurability condition which does not impose any practical restrictions.
We shall now introduce the regret function used in the present paper to compare different policies. Given a policy $\pi$, we define its (cumulative) regret as
This regret function is “individualistic” in the sense that mistakes made for an individual cannot be compensated by later assignments. This property is attractive in settings where every individual matters. We note that for functional targets, and in the absence of covariates, other types of regret than the cumulative one have been considered. In particular cassel2018general consider a “path-dependent” regret notion, which is a useful alternative to cumulative regret. However, path-dependent regret seems to be very difficult to handle in the presence of covariates.
We evaluate policies based on their worst-case behavior, i.e., we shall study minimax expected regret properties of policies. Here, the maximum will be taken over sets of possible joint distributions $\mathbb{P}_{Y,X}$.
When establishing lower bounds on maximal expected regret we shall impose the following rather weak condition. It guarantees that there is a minimal amount of variation in the functional over a small subset of $\mathscr{D}$, the set of all potential conditional outcome distributions.
We emphasize that Equation (ref) in Assumption (ref) is satisfied if, e.g., $\tau \mapsto \mathsf{T}(J_{\tau})$ is continuously differentiable on $[0,1]$ with an everywhere positive derivative.
Up to this point no assumption has been imposed on the dependence of the conditional cdfs $F^i(\cdot, x)$ on $x \in [0, 1]^d$. Keeping this dependence unrestricted would allow two subjects with similar covariates to have completely different conditional outcome distributions. We now prove that the maximal expected regret of any policy increases linearly in $n$ if the dependence of $F^i(\cdot, x)$ on $x$ is not further restricted. It even turns out that this statement continues to hold if one imposes the restriction that subjects with similar covariates have similar outcome distributions in the sense that
The theorem is as follows; it is obtained as an application of the lower bound developed in Theorem (ref) of Section (ref).
Since Assumption (ref) (which is a part of Assumption (ref)) implies that $\mathsf{T}$ is bounded, Theorem (ref) shows that without imposing further restrictions beyond Equations (ref) and (ref) every policy incurs the worst case linear maximal expected regret.
We shall from now on impose a Hölder equicontinuity condition on $F^i(\cdot,x)$. This condition is only slightly stronger than uniform equicontinuity, but will turn out to be enough to ensure existence of (near) minimax optimal policies with nontrivial maximal expected regret.
Before studying policies that incorporate covariate information, one may wonder (e.g., as a sanity check of the framework considered) what happens if one uses a policy that ignores covariates. Our next result shows that---unless the underlying distribution $\mathbb{P}_{Y, X}$ happens to be such that the covariates are completely irrelevant for the assignment problem---any policy that ignores covariates must incur a linear expected regret. Formally, a policy $\pi$ is said to ignore covariates, if there exists another double array $\tilde{\pi}_{n,t}: \left[ [a,b] \times \mathbb{R} \right]^{t-1} \times \mathbb{R} \to \mathcal{I}$ of measurable functions, such that, for every $n$ and every $t = 1, \hdots, n$, we have $\pi_{n,t} = \tilde{\pi}_{n, t} \circ \Pi_t$, where the function $\Pi_t$ projects every $w = (x, z, g)$ in the domain of $\pi_{n,t}$ to $(\tilde{z}, g)$, $\tilde{z}$ being obtained from $z \in \left[ [a,b] \times [0, 1]^d \times \mathbb{R} \right]^{t-1}$ by dropping the $(t-1)$ coordinates taking values in $[0, 1]^d$. Note that then, $\pi_{n,t}(Z_{t-1}, G_t) = \tilde{\pi}_{n,t}(\tilde{Z}_{t-1}, G_t)$, where for $t \geq 2$ we have $\tilde{Z}_{t-1} = (Y_{\tilde{\pi}_{n,t-1}(\tilde{Z}_{t-2}, G_{t-1})}, G_{t-1}, \hdots , Y_{\tilde{\pi}_{n,1}(\tilde{Z}_{0}, G_{1})}, G_1)) $ and $(\tilde{Z}_{0}, G_{1}) = G_1$.
Thus, the expected regret of any policy ignoring covariates must increase at the worst-case linear rate in $n$, for any distribution $\mathbb{P}_{Y, X}$ for which the identity of the best treatment depends on the covariates in the sense that
Contrary to all other lower bounds established in this article, the lower bound in the previous theorem is valid even pointwise, as it makes a statement about any fixed distribution $\mathbb{P}_{Y, X}$.
We now introduce a version of the F-UCB policy that incorporates covariate information. This policy generalizes the UCBogram in rigollet2010nonparametric from the conditional mean setting to the general functional setup. The underlying idea is to categorize subjects into groups, according to the similarity of their covariate vector, and to run, separately within each group, a policy targeting the treatment that is best for the “average” subject in each group. Two covariate vectors $x_1$ and $x_2$ are considered similar, if they fall into the same element of a given partition $B_{n,1}, \hdots,B_{n, M(n)}$ of $[0, 1]^d$, where every $B_{n,i}$ is a non-empty Borel set. Targeting the “on average”-best treatment for each group here means that for $B_{n,j}$ with $\mathbb{P}_{X}(B_{n,j}) > 0$ our policy targets a treatment that attains $\max_{i\in\mathcal{I}}\mathsf{T}(F_{n,j}^i)$, where $F_{n,j}^i$ is the conditional cdf of $Y_{i,t}$ given $X_t \in B_{n,j}$, i.e.,
Note that in general $\operatorname*{arg\,max}_{i \in \mathcal{I}} \mathsf{T}(F_{n,j}^i) \neq \operatorname*{arg\,max}_{i \in \mathcal{I}} \mathsf{T}(F^i(\cdot, x))$. Targeting $\max_{i \in \mathcal{I}} \mathsf{T}(F_{n,j}^i)$ hence results in a bias. The choice of the partition $B_{n,1}, \hdots, B_{n,M(n)}$ needs to balance this bias against an increase in variance due to having fewer subjects in each group. This is akin to choosing a bandwidth to balance variance and bias terms in nonparametric estimation problems.
In order to describe the F-UCB policy in the presence of covariates, we need to introduce the following notation. For any policy $\pi$ and $B_{n,1}, \hdots, B_{n, M(n)}$ as above let
be the number of times that it has assigned treatment $i$ to individuals with covariates in $B_{n,j}$ up to time $t$. On the event $\cbr[0]{S^i_{n,j}(t)>0}$ define the empirical cdf based on the outcomes of all subjects in $\{1, \hdots, t\}$ with covariates in $B_{n,j}$ that have been assigned to treatment $i$ as
The F-UCB policy with covariates, $\bar{\pi}$, is described in Policy (ref). We note that it amounts to using the F-UCB policy $\hat{\pi}$, say, of kpv1 locally on each $B_{n,j}$. Their policy was defined in a setting without covariates and it does not rely on external randomization. We refer the reader to kpv1 for more details on the F-UCB policy in the absence of covariates. We shall in particular use their Theorem 4.1, which provides a regret upper bound for this policy in their setting. In kpv1 it is also shown that choosing the tuning parameter $\beta=2+\sqrt{2}$, minimizes the constant in the uniform upper bounds on expected regret.
\onehalfspacing
\doublespacing
The following theorem gives an upper bound on the maximal expected regret of the F-UCB Policy (ref) in the presence of covariates, and for any choice of partition. This flexibility may be useful since the policy maker is often constrained in the way groups can be formed. The result quantifies how the partitioning affects the regret guarantees. We denote $\overline{\log}(x) := \max(1, \log(x))$ for $x > 0$.
Each of the summands $j = 1, \hdots, M(n)$ in the upper bound on the maximal expected regret in Equation (ref) consists of two parts: The first part is structurally very similar to the upper bound of Theorem 4.1 in kpv1, which the proof of the theorem draws on. The difference is that the total number of subjects to be treated, $n$, has now been replaced by $n\mathbb{P}_X(B_{n,j})$, the number of subjects expected to fall into $B_{n,j}$. Inspection of the proof shows that the first part is the regret we expect to accumulate on $B_{n,j}$, compared to always assigning the treatment that is best for the “average subject” in $B_{n,j}$, i.e., compared to always assigning an element of $\operatorname*{arg\,max}_{i\in\mathcal{I}}\mathsf{T}(F_{n,j}^i)$, where we recall the definition of $F_{n,j}^i$ from Equation (ref). The second part in each summand in the upper bound in (ref) is a bias term: It is the approximation error incurred due to $\bar{\pi}$ effectively targeting $\max_{i\in\mathcal{I}}\mathsf{T}(F_{n,j}^i)$ instead of $\mathsf{T} \big(F^{\pi^\star(x)} (\cdot, x) \big)$ for every $x \in B_{n,j}$.
A frequently used class of partitions of $[0,1]^d$ are hypercubes, which are obtained by hard thresholding each coordinate of $X_t$. The so-created groups may not only result in low regret, but are also relevant due to their simplicity and resemblance to ways of grouping subjects in practice. More precisely, fix $P\in \mathbb{N}$ and define for every $k=(k_1,\hdots,k_d)\in\{1,\hdots,P\}^d$ the hypercube
where $\preceq$ is to be interpreted as $\leq$ for $k_l=P$, and as $<$ otherwise. This defines a partition of $[0,1]^d$ into $P^d$ hypercubes with side length $1/P$ each. We now order these hypercubes lexicographically according to their index vector $k$, to obtain the corresponding cubic partition $B_1^P, \hdots, B_{P^d}^P$. The following result specializes Theorem (ref) to this specific partition and for a choice of $P$ that will be shown to be optimal below.
Corollary (ref) reveals that it is possible to achieve sublinear (in $n$) maximal expected regret under the Hölder equicontinuity condition imposed through Assumption (ref). This is interesting also in light of Theorem (ref), which showed that under the slightly weaker assumption of uniform equicontinuity, every policy has linearly increasing maximal expected regret. Hence, there is little room for weakening Assumption (ref). Note that a “curse of dimensionality” is present, in the sense that the upper bound in Corollary (ref) gets close to linear in $n$, as the number of covariates $d$ increases. This is due to the fact that as a part of the regret minimization, one sequentially estimates the conditional distributions $F^i(y,\cdot)$ of the treatment outcomes, where each cdf is a function of $d$ variables. Finally, we observe that the upper bound is increasing in the number of available treatments $K$. Intuitively, this is because more observations must be used for experimentation when more treatments are available.
The partitioning used in Corollary (ref) results in a near-minimax optimal policy, as we show in the following theorem, which establishes a lower bound on maximal expected regret. The statement follows from Theorem (ref) in Section (ref) below.
Comparing the lower bound on maximal regret in Theorem (ref) to the upper bound on maximal expected regret established in Corollary (ref), reveals that the F-UCB policy with a cubic partition and with $P = \lceil n^{1/(2 \gamma +d)} \rceil$ is near-optimal: If a policy with strictly smaller maximal expected regret exists, the order of improvement must be $o(n^\varepsilon)$ for all $\varepsilon \in (0, \gamma/(2\gamma + d))$, e.g., logarithmic. In particular this also means that if nothing prohibits cubic partitioning, not much can be gained from a maximal expected regret point-of-view in searching for “better” partitions under the given set of assumptions.
Besides mild conditions on $\mathbb{P}_X$, our results so far have only assumed that the conditional distributions of the treatment outcomes are Hölder equicontinuous. In particular, the sets of distributions over which the F-UCB policy has been shown to be optimal does not restrict the (unknown) similarity of the best and second best treatment. In the present section, we shall see that in classes of distributions where the best and second best treatment are “well-separated,” the upper bound on maximal expected regret of the F-UCB policy can be lowered (without changing the policy), and that the F-UCB policy optimally adapts to the degree of similarity of the best and the remaining treatments.
Besides being of interest in their own right, the results in the present section are instrumental to proving our impossibility result Theorem (ref) and to establishing the expected regret lower bound in Theorem (ref).
To formally define the well-separateness condition we shall work with, we need to define for every $x \in [0, 1]^d$ the second best treatment $\pi^{\sharp}(x)$; note that in principle there can be multiple treatments that are as good as the best treatment $\pi^*(x)$. For $x \in [0,1]^d$, if $\min_{i \in \mathcal{I}}\mathsf{T}(F^i(\cdot, x)) < \mathsf{T}\big(F^{\pi^{\star}(x)}(\cdot, x)\big)$, we define the second best treatment as
and we set $\pi^{\sharp}(x)=1$ otherwise, i.e., if all treatments are equally good. We can now introduce the margin condition.
The margin condition restricts how likely it is that the best and second best treatment are close to each other. In particular, it limits the probability of these two treatments being almost equally good, i.e., being within a $\delta$-margin. Assumptions of this type have previously been used in the works of mammen1999smooth, tsybakov2004optimal, and audibert2007fast in the statistics literature. In the context of statistical treatment rules, the margin condition has recently been used in the work of kitagawa2018should, who considered empirical welfare maximization in a static treatment allocation problem. Finally, the margin condition was used by rigollet2010nonparametric and perchet2013multi in the context of a multi-armed bandit problem targeting the conditional mean. The proofs of the results in the present section draw in particular their ideas.
Adding the margin condition, the maximal expected regret of the F-UCB policy based on cubic partitions can be bounded as follows.
Compared to Corollary (ref) the exponent on $n$ in the upper bound on regret is smaller, the difference depending on $\alpha$. Thus, in the presence of Assumption (ref), the regret guarantee of the F-UCB policy is stronger, even without incorporating $\alpha$ into the policy. We shall see in Theorem (ref) below that the upper bound on maximal expected regret in Theorem (ref) is optimal in $n$ up to logarithmic factors.
The margin condition also allows us to prove an upper bound on the expected number of suboptimal assignments made by the F-UCB policy. We shall define the total number of suboptimal assignments for a policy $\pi$ over the course of a total of $n$ assignments as
We now establish a uniform upper bound on $\mathbb{E}[S_n(\bar{\pi})]$ for the F-UCB policy $\bar{\pi}$ based on cubic partitions.
The upper bound in Theorem (ref) is a useful theoretical guarantee, because it limits the number of subjects who receive suboptimal treatments. As the last result in this section, we prove that the upper bounds in Theorems (ref) and (ref) are near minimax optimal. This ensures, in particular, that the good behavior of the maximal expected regret of the F-UCB policy does not come at the price of excessive experimentation, leading to unnecessarily many suboptimal assignments.
Together with Theorem (ref) the statement in Equation (ref) shows that the F-UCB policy is near minimax optimal in terms of maximal expected regret. Similarly, together with Theorem (ref) the lower bound in Equation (ref) proves that the F-UCB policy assigns the minimal number of suboptimal treatments. The proof idea is classic and links regret to testing problems. In particular, as in rigollet2010nonparametric who target the conditional mean functional, we first use the margin condition to lower bound the expected regret by the expected number of false assignments (cf. Lemma (ref)). Then, we show that the expected number of false assignments can be lower bounded by sums of Type 1 and Type 2 errors of testing problems in certain binary experiments between elements of a subfamily of the joint distributions of $(X_t, Y_t)$ over which the suprema in the previous theorem are taken. In order to get good lower bounds, we are required to work with a family of joint distributions (in particularly satisfying the assumption in Equation (ref) and Assumption (ref)) the elements of which are difficult to distinguish, while having sufficient variation in $x \mapsto \mathsf{T}(F^i(\cdot, x))$. This constitutes one main complication compared to the argument in rigollet2010nonparametric, where the functional is the conditional expectation, and where one can work with joint distributions where $Y_t$ given $X_t$ is a Bernoulli distribution with a certain success probability depending on the covariate vector. In our case Equation (ref) needs to be satisfied. The only assumption on $\mathscr{D}$ we can work with is Assumption (ref). Therefore, we need to choose the conditional distributions from the line segment provided in this Assumption. While rigollet2010nonparametric construct joint distributions replicating conditional mean surfaces such that the above testing problems are difficult enough to warrant large lower bounds, we construct joint distributions replicating conditional functional surfaces that render the testing problems difficult; that is, we construct joint distribution that are similar enough such that testing between them is difficult, but such that at the same time the conditional functionals associated to these distributions are far apart.
In the present paper we have established lower and upper bounds on maximal expected regret in a functional sequential assignment problem with covariates. Our results show that the optimality theory developed in rigollet2010nonparametric can be generalized to a large class of functionals of the conditional potential outcome distributions beyond the conditional mean.