# Regret Bounds and Experimental Design for Estimate-then-Optimize

Samuel Tan
School of Operations Research and Information Engineering
Cornell University
&Peter Frazier
School of Operations Research and Information Engineering
Cornell University

###### Abstract

In practical applications, data is used to make decisions in two steps:
estimation and optimization. First, a machine learning model estimates
parameters for a structural model relating decisions to outcomes. Second, a
decision is chosen to optimize the structural model’s predicted outcome as if
its parameters were correctly estimated. Due to its flexibility and simple
implementation, this “estimate-then-optimize” approach is often used for data-
driven decision-making. Errors in the estimation step can lead estimate-then-
optimize to sub-optimal decisions that result in regret, i.e., a difference in
value between the decision made and the best decision available with knowledge
of the structural model’s parameters. We provide a novel bound on this regret
for smooth and unconstrained optimization problems. Using this bound, in
settings where estimated parameters are linear transformations of sub-Gaussian
random vectors, we provide a general procedure for experimental design to
minimize the regret resulting from estimate-then-optimize. We demonstrate our
approach on simple examples and a pandemic control application.

_Keywords_ Estimate-then-optimize, Experimental Design, Optimization under
Uncertainty

##  1 Introduction

Consider a decision $x\\!\in\\!\mathbb{R}^{d}$ based on a model whose
parameter vector $\theta$ is estimated from data. Examples include:

  * •

Choosing nonpharmaceutical interventions to prevent the spread of a virus
given a structural epidemiological model of viral spread, where the model’s
predictions depend on viral transmission parameters;

  * •

Choosing staffing levels in a hospital to ensure timely service and good
health outcomes while controlling costs, given a structural queuing model for
patient arrivals and the time required to deliver care;

  * •

Choosing rates at which to pump oil from several wells to maximize the amount
of oil extracted, given a structural model for subsurface oil flow.

Perhaps the most common approach to solving this problem is to (1) estimate
the parameter vector $\theta$ from data; and then (2) choose decision vector
$x$ to maximize the value predicted by the structural model assuming this
estimated parameter vector is correct. Mathematically, if our estimator is
$\hat{\theta}$ and our model is $f(\cdot,\cdot)$, the resulting decision is
$\hat{x}\in\operatorname*{\arg\\!\max}_{x}f(x,\hat{\theta})$. This approach is
sometimes called “estimate-then-optimize” (Farias, 2007; Hu et al., 2020).

While more sophisticated methods exist for choosing a decision $\hat{x}$ based
on data, such as Bayesian methods (Wu et al., 2018) and robust optimization
(Bertsimas et al., 2018), they can be hard to implement. One barrier is the
computation required by the more complex optimization problems they solve
(e.g., $\max_{x}\min_{\hat{\theta}}f(x,\hat{\theta})$ for robust
optimization). Another barrier is the need to integrate engineering and
organizational structures that previously separated estimation from
optimization. For example, a company may have a team of machine learning
experts focused on estimation and a separate team trained in and focused on
optimization, each with their own engineering systems. Thus, estimate-then-
optimize is widely used in practice and it is valuable to understand and
improve its performance.

In estimate-then-optimize, errors in the statistical estimation can lead to
regret: the value of the decision made $f(\hat{x},\theta)$ may be smaller than
that of the best decision possible using the true parameters,
$\max_{x}f(x,\theta)$. While this is understood intuitively to be important by
practioners, past literature has not, to our knowledge, provided formal bounds
for this regret nor considered how the experimental design used to gather data
for estimation impacts regret.

Our contribution is a novel bound on the regret resulting from an estimate-
then-optimize approach for smooth $f$ and unconstrained $x$. We further show
how this approach can inform the experimental design used to collect data for
estimating $\theta$. In particular, our results can help a user decide how
much effort to allocate to parts of their parameters space so as to minimize
regret. In a setting where the parameter estimate is known to be a linear
transformation of a sub-Gaussian random vector, we provide bounds that depend
on its covariance; this covariance term can consequently be used to minimize
this asymptotic regret bound. We provide three examples: one in which the
parameters are directly assumed to be normal, a pricing example using a
logistic conversion model, and a more tangible real-world example of
controlling a pandemic.

We envision this work will be of substantial interest to those who currently
rely on the estimate-then-optimize paradigm to make decisions from data and
are prevented by the barriers described above from moving away from estimate-
then-optimize. For instance, a marketplace platform may use our result to
select not only prices to use for an experiment, but also the proportion of
participants to assign to each price so as to minimize the regret in finding
the optimal price.

The rest of the paper is structured as follows. Section 2 overviews related
work. Section 3 contains the main technical results and the prerequisite
assumptions. Section 4 expands on said technical results in cases when the
parameter estimates are assumed to be linear transformations of sub-Gaussian
random vectors. Section 5 connects our work to experimental design. Section 6
demonstrates our method on three examples. Finally, section 7 concludes and
mentions some future directions of this work.

##  2 Related Work

The general two-stage procedure of estimating parameters in an optimization
problem and then solving using those predicted parameters has appeared in the
literature in various forms.

From a statistical viewpoint, the framework presented in this paper can be
viewed as optimizing some function in the presence of a model parameter
(sometimes called a nuisance parameter), $\theta$, which must first be
estimated. Using this perspective, Foster and Syrgkanis (2019) derive fast
rates of convergence when a condition called Neyman-orthogonality is
satisfied, where the pathwise derivatives of $f$ with respect to $\theta$ and
$x$ at their true values vanishes. However, this cross-derivative term is
exactly the term which we consider in this work as (1) it is generally not
equal to 0 except in very specific applications and (2) it governs the slower
rate for the risk.

There has also been work done in similar settings in which one wishes to
perform estimate-then-optimize in a “smarter” way. In (Elmachtoub and Grigas,
2022), the authors specifically tackle a contextual stochastic optimization
problem, wherein the objective is linear and of the form
$\min_{x}\mathbb{E}_{c(w)\sim F_{w}}[c(w)^{\top}x|w].$ Here the authors call
this particular form “predict-then-optimize”. In particular, here the user is
presented with a context $w$ drawn from some distribution, and the parameters
$c(w)$ of the objective function depend on $w$. The standard estimate-then-
optimize approach would be to run some off-the-shelf regression method to
construct a prediction $\hat{c}$ for $\mathbb{E}[c(w)|w]$ based on past data
of the form $\\{(c_{i},w_{i})\\}_{i=1}^{n}$, and optimize the resulting
program $\min_{x}\hat{c}^{\top}x$. The proposed solution is to aim the
prediction of $\mathbb{E}[c(w)|w]$ towards minimizing the objective value in
the downstream optimization problem, dubbed the smart predict-then-optimize
(SPO) loss. As minimizing this directly is intractable, the authors propose
minimizing a convex surrogate. Later work, such as El Balghiti et al. (2019),
analyze generalization and risk bounds for this particular approach.

We emphasize that this “predict-then-optimize” framework focuses on the loss
for individual contexts, i.e. $\mathbb{E}[\theta|w]\cdot x(w)$ for a fixed
$w$. However, if one instead focuses on the average performance across $w_{i}$
chosen from the training set, then the overall loss would be of the form
$\sum_{i=1}^{n}\mathbb{E}[c(w_{i})|w_{i}]\cdot x(w_{i})$. We may encode this
in our framework via setting $\theta:=\\{\mathbb{E}[c(w)|w]:w\\}$ and
$x:=\\{x(w):w\\}$, and $f(x,\theta):=\sum_{i=1}^{n}\theta(w_{i})x(w_{i})$.

Ito et al. (2018) also consider the same estimate-then-optimize framework,
wherein one optimizes $f(x,\hat{\theta})$ using an estimate $\hat{\theta}$ for
the true $\theta^{*}$. However, their work does not analyze the value of
$f(\hat{x},\theta^{*})$, but rather establishes that the estimate
$f(\hat{x},\hat{\theta})$ is generally biased for $f(x^{*},\hat{\theta})$.
They additionally describe a bias-correction procedure under $f$ which is
affine in $\theta$, but do not offer asymptotic analysis of our quantity of
interest, $f(\hat{x},\theta^{*})-f(x^{*},\theta^{*})$.

Wilder et al. (2019) also consider the estimate-then-optimize framework,
though in their case the optimization problem is combinatorial, i.e. the
decision $x$ are discrete. Their approach is to (1) relax the combinatorial
problem to a continuous one, (2) derive gradients of the objective with
respect to the predictions, (3) use the closed-form gradients in a gradient-
based optimization algorithm, and (4) round the resulting solution to the
nearest integer. They also find that $\frac{\partial^{2}f}{\partial
x\partial\theta}$ plays a fundamental role in their gradient derivations, and
demonstrate their approach in detail on linear programming and submodular
maximization problems. However, they only offer empirical evidence that their
approach performs well, and obviously apply only to combinatorial problems.

Our work is also closely related to empirical risk minimization (ERM) (Vapnik,
1999) and sample average approximation (SAA) (Kim et al., 2015), though still
different in important ways. In our setting, toward the goal of minimizing
$f(x,\theta)$ over $x$, we consider the approximate minimizer
$\hat{x}\in\operatorname*{\arg\\!\max}_{x}f(x,\hat{\theta})$ for some
estimator $\hat{\theta}$ of $\theta$. In ERM and SAA, toward the goal of
minimizing $\mathbb{E}_{\psi}g(x,\psi)$ over $x$, one considers the
approximate minimizer
$\hat{x}\in\operatorname*{\arg\\!\max}_{x}\frac{1}{n}\sum_{i=1}^{n}g(x,\psi_{i})$
where $\psi_{i}$ are i.i.d. Except in trivial cases (such as those where $f,g$
do not depend on $\theta$), there is no way to construct an $f$ and $g$ so
that the quantities match. Our setting is therefore different from ERM/SAA
except in the special case where $f$ is linear in $\theta$ for all $x$.

The idea of using sensitivity of output to parameters to guide data collection
has also been explored, notably in the simulation community, e.g. Song and
Nelson (2015) and Freimer and Schruben (2002) give two approaches for deciding
on which parameters to collect more data in order to reduce the impact of
input uncertainty on simulation output. However, these approaches do not
consider the setting in which there is a decision to be optimized, whereas our
approach is concerned with targeting parameters to make better decisions.

Finally, experimental design is a mature field within statistics which has
explored the notion of optimal design for an experiment, where there are
several notions of optimality (Pukelsheim, 2006). In the particular case of
linear models, in which the experimenter has control over the proportion of
samples to allocate to a set of linearly independent vectors which comprise
the design matrix, various optimality criteria have been studied in the
literature. A commonly used definition of optimality is $A$-optimality, which
reduces to minimizing the average variance of the regression coefficients.
Similarly, $C$-optimality instead considers minimizing the variance of a
linear combination of the regression coefficients. When the decision variable
is one-dimensional, our regret bound induces a $C$-optimal design problem.
More generally, our regret bound induces an $A$-optimal design for a
particular parameter system $K\theta$.

##  3 General Regret Bound for Estimate-then-Optimize

This section defines the estimate-then-optimize framework more formally and
then states our general bound on regret and assumptions required by this
bound.

In the estimate-then-optimize framework we are concerned with optimizing some
smooth function $f(x,\theta)$ where $\theta$ is a model parameter and
$x\in\mathbb{X}$. Here $\mathbb{X}$ can equal $\mathbb{R}^{d}$ or a subset
thereof. The goal is to solve
$\operatorname*{\arg\\!\min}_{x}f(x,\theta^{*})$, where $\theta^{*}\in\Theta$
is unknown and must be estimated. Call
$x^{*}=\operatorname*{\arg\\!\min}_{x}f(x,\theta^{*})$. Note that here if
$\mathbb{X}\subsetneq\mathbb{R}^{d}$, Assumption 3.1 must be satisfied, i.e.
$x^{*}\in\text{int }\mathbb{X}$.

Below, we denote
$\mathcal{S}(z,z^{\prime}):=\\{tz+(1-t)z^{\prime}|t\in[0,1]\\}$, i.e. the line
segment between $z,z^{\prime}$. Also $\|\cdot\|$ (without a subscript) always
denotes the Euclidean norm. Finally, for higher-than-second-order directional
derivatives (as they appear in Taylor’s theorem), we denote
$D^{k}_{s}f(s)[p_{1},\ldots,p_{k}]$ to be

$\frac{\partial^{k}}{\partial t_{1}\ldots\partial
t_{k}}f(s+t_{1}p_{1}+\cdots+t_{k}p_{k})\Bigg{|}_{t_{1}=\cdots=t_{k}=0}.$

We consider an algorithm that first learns $\hat{\theta}$ from a sample $S$
(say a sample generated under a distribution with mean $\theta^{*}$) and then
learns $\hat{x}$ by minimizing $f(x,\hat{\theta})$, where the second
minimization step is exact.

######  Assumption 3.1 (First Order Optimality).

The minimizer $x^{*}$ satisfies $\frac{\partial f}{\partial
x}\Big{|}_{x=x^{*},\theta=\theta^{*}}=0.$

######  Assumption 3.2 (Strong Convexity).

The function $f$ is strongly convex with respect to $x$ in a neighorhood
$B_{\theta}$ around
$x^{*}(\theta):=\operatorname*{\arg\\!\min}_{x}f(x,\theta)$ for each $\theta$,
i.e. a universal $\rho$ exists such that

$(x-x^{*})^{\top}\frac{\partial^{2}f}{\partial
x^{2}}\Bigg{|}_{x=\overline{x},\theta=\theta^{\prime}}(x-x^{*})\geq\rho\|x-x^{*}\|^{2}$

for all $x\in B_{\theta^{\prime}},\overline{x}\in\mathcal{S}(x,x^{*})$, for
all $\theta^{\prime}$.

######  Assumption 3.3 (Higher Order Smoothness).

There exist constants $\beta_{1}$ and $\beta_{2}$ such that the following
derivative bounds hold:

  * •

For all $x\in\mathcal{X}$, $\overline{x}\in\mathcal{S}(x,x^{*})$

$(x-x^{*})^{\top}\frac{\partial^{2}f}{\partial
x^{2}}\Bigg{|}_{x=\overline{x},\theta=\theta^{*}}(x-x^{*})\leq\beta_{1}\|x-x^{*}\|^{2},$

  * •

For all $\theta\in\Theta$,
$\overline{\theta}\in\mathcal{S}(\theta,\theta^{*})$, $x\in\mathcal{X}$

$\displaystyle\Big{|}D^{2}_{\theta}D_{x}f(x^{*},\overline{\theta})[x-x^{*},\theta-\theta^{*},\theta-\theta^{*}]\Big{|}$
$\displaystyle\leq\beta_{2}\|x-x^{*}\|\|\theta-\theta^{*}\|^{2}.$

The higher order assumptions also appear in other literature, e.g. Foster and
Syrgkanis (2019), where it is shown that they are easily satisfied. We then
have the following theorem.

######  Theorem 3.4.

Under the above assumptions and when $x^{*}\in B_{\hat{\theta}}$, the
optimality gap of $\hat{x}$ under the true $\theta^{*}$, i.e.
$f(\hat{x},\theta^{*})-f(x^{*},\theta^{*})$, is upper bounded by
$\frac{4\beta_{1}}{\rho^{2}}\Bigg{(}\|\frac{\partial^{2}f}{\partial
x\partial\theta}\Bigg{|}_{x=x^{*},\theta=\theta^{*}}(\hat{\theta}-\theta^{*})\|^{2}+\frac{\beta_{2}^{2}}{4}\|\hat{\theta}-\theta^{*}\|^{4}\Bigg{)}.$

##  4 Regret Bound for Linear Transformations of sub-Gaussian Random Vectors
$\hat{\theta}$

We now consider a particular setting in which we place a distributional
assumption on our estimate $\hat{\theta}$. In particular, suppose we have some
dataset of size $n$ which we use to construct $\hat{\theta}$. Furthermore,
assume this estimate is known to be a linear transformation of a sub-Gaussian
random vector which has parameter 1 WLOG. This encompasses a wide class of
random variables. In particular, normal random variables are a special case
when taking the sub-Gaussian random vector to be an isotropic multivariate
Gaussian with identity covariance and the linear transformation to be the
square root of the covariance matrix. In the asymptotic regime, asymptotically
normal estimators are therefore also included, e.g. from the central limit
theorem or asymptotic theory governing maximum likelihood estimators. This is
summarized in the following assumption.

######  Assumption 4.1.

We have an algorithm which, from a dataset $\mathcal{S}$ of size $n$, produces
$\hat{\theta}$ such that $\hat{\theta}-\theta=\frac{\Sigma^{1/2}}{\sqrt{n}}X$
for positive definite $\Sigma$ and $X\sim$ subG(1).

######  Assumption 4.2.

The set $\Theta^{*}:=\\{\theta:x^{*}(\theta^{*})\in B(\theta)\\}$ is open.

Also for notational convenience we define $D:=\frac{\partial^{2}f}{\partial
x\partial\theta}\Big{|}_{x=x^{*},\theta=\theta^{*}}.$ We then have the
following lemma for converging to the strongly convex neighborhood.

######  Lemma 4.3.

There exist constants $\alpha,\beta>0$ such that for $n$ sufficiently large,
$x^{*}\in B_{\hat{\theta}}$ with probability at least $1-\alpha\exp(-\beta
n)$.

This lemma then yields the following theorem.

######  Theorem 4.4.

With probability at least $1-\alpha\exp(-\beta n)-\frac{2}{n}$

$\displaystyle
f(\hat{x},\theta^{*})-f(x^{*},\theta^{*})\leq\frac{4\beta_{1}}{\rho^{2}}\Bigg{(}\operatorname{Tr}\frac{D\Sigma
D^{\top}}{n}$ $\displaystyle+2\sqrt{\operatorname{Tr}\left[\left(\frac{D\Sigma
D^{\top}}{n}\right)^{2}\right]\log n}+2\|\frac{D\Sigma D^{\top}}{n}\|_{2}\log
n\Bigg{)}$ $\displaystyle+o(\operatorname{Tr}\frac{D\Sigma D^{\top}}{n}\log
n)$

##  5 Application to Experimental Design

We now imagine we have a class of experiments which informs us about the
uncertain parameter $\theta$. Each produces a different estimator and
corresponding distribution, which is assumed to satisfy the distributional
assumptions of Section 4. Our goal is to choose the experiment so as to
minimize the upper bound derived previously in Theorem 4.4.

In particular, the theorem tells us that minimizing the trace of the variance
term $\frac{D\Sigma D^{\top}}{n}$ minimizes the upper bound on the regret. In
the context of linear models, this is exactly equivalent to the $A$-optimality
criterion in experimental design (Pukelsheim, 2006) when using $D$ as a
coefficient matrix. 111Using other scalar values related to the matrix
$D\Sigma D^{\top}$ would correspond to other criteria. For instance,
minimizing the determinant (or equivalently log determinant), would correspond
to $D$-optimality, or minimizing the 2-norm would correspond to
$E$-optimality.

Therefore the problem is to minimize $\operatorname{Tr}\frac{D\Sigma
D^{\top}}{n}$, where the decision variable is the experimental design which
induces the form of $\hat{\theta}.$

In the discussion and results above, we assume $D$ is known to us. However in
practice, $D$ is unknown — it depends on the unknown value $\theta^{*}$. We
overcome this with a Bayesian approach: we place a prior $\pi$ on
$\theta^{*}$, and draw samples from the prior $\theta$, which we then use to
calculate $x^{*}(\theta)$. This then gives us access to
$D^{\prime}:=\frac{\partial^{2}f}{\partial
x\partial\theta}\Big{|}_{x^{*}(\theta),\theta}.$ We then solve the following
problem

$\min_{\hat{\theta}}\mathbb{E}_{\theta\sim\pi}\left[\operatorname{Tr}\frac{D^{\prime}\Sigma
D^{\prime\top}}{n}\right],$ (1)

where in practice we replace the true expectation with an empirical average
over draws from the prior.

##  6 Examples

This section provides three examples of how our method can be used to inform
experimental design, as well as corresponding numerical experiments
demonstrating the value of our method.

###  6.1 Experimental Design Under Normal Model Parameters from a Linear Model

We consider a particular setting for experimental design to which our method
directly applies. Suppose we can get samples $\theta_{ij}\sim
N(\theta^{*}_{i},\sigma_{i}^{2}),$ where $\theta_{ij}$ are i.i.d. for each $i$
and $\theta_{i}$ are independent between $i=1,\dots,n$.

First, for $i\in\\{1,\ldots,n\\}$, define $N_{i}$ as the number of times
$\theta_{i,j}$ was sampled. Then we define $\hat{\theta}$ component-wise via

$\hat{\theta}_{i}=\frac{\sum_{j=1}^{N_{i}}\theta_{i,j}}{N_{i}}.$

So in this case $\hat{\theta}-\theta\sim N(0,\hat{\Sigma}),$where
$\hat{\Sigma}$ is diagonal with
$\hat{\Sigma}_{ii}=\frac{\sigma_{i}^{2}}{N_{i}}.$

We see that minimizing the norm of the LHS is equivalent to minimizing the
variance $\mathbf{d}^{\top}\hat{\Sigma}\mathbf{d}$ (for instance, the squared
norm of the LHS is a $\chi^{2}$ distribution).

Now assume that $x\in\mathbb{R}$. Since $D$ in this case is just a vector, we
then denote $\mathbf{d}=\frac{\partial^{2}f}{\partial
x\partial\theta}\Big{|}_{x=x^{*},\theta=\theta^{*}}.$

Now referring back to Theorem 4.4, we see that the quantity of interest is
$\mathbf{d}^{\top}\Sigma\mathbf{d}$ (since the trace and $\|\cdot\|_{2}$ in
this case correspond to the same scalar). So the objective is to minimize
$\mathbf{d}^{\top}\Sigma\mathbf{d}$, subject to $\Sigma$ belonging to the
class of allowed by our allocations $N_{i}$.

At this point, we point out that this exactly coincides with $C$-optimal
experimental design. In particular, this is the special case that our linearly
independent vectors for samples are the unit vectors in $\mathbb{R}^{n}$ so
that $X=I$. Then standard results in $C$-optimal experimental design
(Pukelsheim, 2006) yield that, given a mass of unit $1$ to allocate across the
$n$ vectors,

$n_{i}=\frac{d_{i}\sigma_{i}}{\sum_{j=1}^{n}d_{j}\sigma_{j}}.$ (2)

In practice, if one had say $m$ samples to allocate across the $n$ components,
we would assign $mn_{i}$ to component $i$, rounding when necessary.

We now provide a simple problem to demonstrate our method on this setting.
Consider $f(x,\theta)=\frac{\theta_{1}}{2}x^{2}+\theta_{0}x,$ which satisfies
the assumptions of the theorem when $\theta_{1}>0$. Suppose that we can sample
$\theta_{i}\sim N(\theta_{i}^{*},\sigma_{i}^{2})$. Here
$D=\left(1,-\frac{\theta^{*}_{0}}{\theta^{*}_{1}}\right)$, and minimizing the
bound corresponds to minimizing
$\frac{\sigma_{0}^{2}}{n}+\frac{\sigma_{1}^{2}}{N-n}\left(\frac{\theta_{0}^{*}}{\theta_{1}^{*}}\right)^{2},$
where $N$ is the total number of samples to allocate. Note that we do not have
a constant term, as any samples used to estimate the constant term are wasted;
we care about $f(\hat{x},\theta^{*})$, and the constant term in
$f(x,\theta^{*})$ does not interact with the decision variable $x$.

For our experiment, we use the prior $\theta^{*}\sim
N\Big{(}\begin{pmatrix}10\\\ 5\end{pmatrix},I\Big{)}$ and
$\Sigma=\text{diag}(1,3)$. We repeated the method for 300 replications, where
100 draws from the prior are used for both optimization of the bound and
evaluation of the regret. Figure LABEL:fig:quad shows the regret under the
prior achieved by our method versus a uniform allocation which splits samples
across $\theta_{0}$ and $\theta_{1}$ evenly.

Figure 1b compares the estimated function $f(x,\hat{\theta})$ against
$f(x,\theta^{*})$, showing that the resulting estimate $\hat{x}$ yields a
better decision for $f(x,\theta^{*})$ when using the optimal allocation.

(a)

(b) Estimated objective function and decision

Figure 1: Simple quadratic example illustrating the general setting in Section
6.1. (a) A comparison of our method for collecting samples of $\theta_{0}$ and
$\theta_{1}$. Our method corresponds to the analytical optimum. The empirical
minimum regret (minimizer of the blue regret curve) is also shown, while the
uniform allocation can be seen to achieve significantly higher regret. (b) The
estimated quadratic function when using different allocations. The resulting
decision from using the optimal allocation yields a solution closer to the
optimizer of the true function.

###  6.2 Pricing Under Logistic Conversion

In this example, we consider pricing a product based on a data from a pricing
experiment. We observe a sequence of customers arriving to a website or mobile
app who are each presented with a price $x$. For each customer, we observe
whether they purchase (“convert”) or not, with the probability of purchase
being governed by a logistic function of the price $x$ with parameter
$\theta$, i.e.

$c(x,\theta)=\frac{1}{1+\exp(\theta_{0}+\theta_{1}x)}$

The objective function is then revenue, negated to yield a minimization
problem: $f(x,\theta)=-xc(x,\theta).$

Here we assume $\theta_{1}>1$ so that higher prices have lower purchase
probability. We suppose that estimate-then-optimize is implemented by
estimating $\theta$ via maximum likelihood estimation. From standard results
for the maximum likelihood estimate for logistic regression (Hastie et al.,
2009), we know that asymptotically $\hat{\theta}\sim
N(\theta,(X^{T}WX)^{-1}),$ where $X$ is a $n\times 2$ matrix with first column
all ones, and second column corresponding to prices $x_{i}$, and $W$ is a
diagonal $n\times n$ matrix with $c(x_{i},\theta)(1-c(x_{i},\theta)$ on the
diagonal.

In this case, $\mathbf{d}$ is given by

$\displaystyle\frac{\partial^{2}f}{\partial x\partial\theta_{0}}=$
$\displaystyle c(x,\theta)(1-c(x,\theta))$
$\displaystyle+\theta_{1}x\left(c(x,\theta)(1-c(x,\theta)\left(2c(x,\theta)-1\right)\right)$
$\displaystyle\frac{\partial^{2}f}{\partial x\partial\theta_{1}}=$
$\displaystyle 2xc(x,\theta)(1-c(x,\theta))$
$\displaystyle+x^{2}\theta_{1}c(x,\theta)(1-c(x,\theta))\left(2c(x,\theta)-1\right)$

It is easy to show that $f$ satisfies the conditions of our theorem. For
completeness, the proofs are provided in the supplementary material.

We consider a user who is designing an experiment to support selection of the
best price. The user has access to historical data on prices and conversion,
which she can use to construct a prior for $\theta$. Using this data, she
designs an experiment using $n$ samples constrained to use prices from among
$m$ distinct prices. The user then uses maximum likelihood to estimate
$\theta$, and solving the corresponding revenue maximization problem. This
yields the fixed price $\hat{x}$ which she holds in place moving forward. The
revenue of the selected price $\hat{x}$, under the true logistic model
$\theta^{*}$, is the quantity we wish to be as large as possible. The regret
is the difference between this quantity and the revenue at the optimal price
$x^{*}$ under the true logistic model.

We study this experimental design problem numerically via simulations. We
simulate the procedure described above, where one must decide how to allocate
samples (opportunities to sell the product to a customer) across prices to
yield the selected price $\hat{x}$ with the highest expected revenue,
considering $n=100$ samples and $m=10$ prices.

We evaluate our method and a baseline method under a collection of
multivariate normal priors for $\theta^{*}$ with covariance $0.01I$. The means
of the priors for $\theta^{*}$ were chosen so that the $x$ value for which
$c(x,\theta^{*})=0.5$ is at prices $1,2,\ldots,8$ (avoiding boundaries). 100
draws from the prior were used for optimization and evaluation of regret.

Due to the computational cost of considering all partitions of 100 allocations
among the 10 prices, we instead use random search to optimize the regret
bound. In particular, we choose 1000 random allocations uniformly at random
and return the allocation minimizing
$\frac{\mathbf{d}^{\top}(X^{\top}WX)^{-1}\mathbf{d}}{n}$.

We then simulate 100 customer purchase decisions (conversions) using prices
distributed among the 10 prices $0,\ldots,9$ according to the best allocation
found as well as according to the baseline uniform allocation, again using the
logistic model and the held out ground truth $\theta^{*}$. We again use
maximum likelihood to derive estimates $\hat{\theta}_{\text{optimized}}$ and
$\hat{\theta}_{\text{uniform}}$, and their corresponding revenue maximizers
$\hat{x}_{\text{optimized}},\hat{x}_{\text{uniform}}$.

Table 1 gives 95% confidence intervals for the resulting expected regrets from
these two approximate revenue maximizers, $\hat{x}_{\text{optimized}}$ and
$\hat{x}_{\text{uniform}}$. We see that our optimized approach provides
consistently lower regret than the baseline uniform allocation. We also note
that in our experiments, we observed the scale of the regret scales as
$O(\frac{1}{n})$: see the supplementary material for more experiments for
values of $n$.

| Optimized Allocation | Uniform Allocation
---|---|---
$\theta=[-1,1]$ | $1.0\pm 0.3$ | $1.4\pm 0.4$
$\theta=[-2,1]$ | $0.8\pm 0.3$ | $1.5\pm 0.4$
$\theta=[-3,1]$ | $1.2\pm 0.3$ | $1.5\pm 0.4$
$\theta=[-4,1]$ | $1.3\pm 0.3$ | $1.8\pm 0.5$
$\theta=[-5,1]$ | $2.4\pm 2.3$ | $2.5\pm 0.6$
$\theta=[-6,1]$ | $2.1\pm 0.6$ | $3.3\pm 1.0$
$\theta=[-7,1]$ | $2.8\pm 0.8$ | $3.2\pm 0.9$
$\theta=[-8,1]$ | $2.9\pm 0.8$ | $6.6\pm 2.8$
Table 1: Comparison of regret under optimized and baseline uniform allocations
in the pricing example of Section 6.2. The quantities are 95% confidence
intervals, where the units are in $10^{-2}$.

Figure LABEL:fig:price also shows an example of the optimal allocation found
by our method. We can observe that, compared to a uniform sampling strategy,
more samples are allocated near the peak of the function, yielding more
information about the maximum. In particular, more samples are allocated
slightly to the right where the conversion hovers around $\frac{1}{2}$ (at
$x=4$), suggesting that the change in curvature there also yields more
information than just the peak.

(a)

(b) Estimated objective function and decision

Figure 2: Pricing example from Section 6.2. (a) True revenue function (purple
line) and optimal experimental sample allocation (blue bars). (b) Estimated
revenue function under three different experiment sample allocations, using a
zoomed-in $x$-axis. The decision supported by the optimal allocation yields a
solution closer to the optimizer of the true revenue.

Finally, Figure 2b is the analogous figure of Figure 1b for this pricing
problem. Here it shows, again for $\theta^{*}=[-4,1]$, the estimated function
$f(x,\hat{\theta})$ for $\hat{\theta}$ coming from different allocations. We
again see that the optimal allocation yields an estimated function whose
optimizer is closer to the optimizer of the true function.

###  6.3 Application to Pandemic Control

We now apply our framework to controlling COVID-19 through regular testing as
a university or city reopens, subject to uncertainty about contact among
social groups.

We model viral spread via a multi-group SIR model (see, e.g., Guo et al.
2006), where people belong to one of $n$ social groups, indexed by $k$, and to
one of three disease states. A combination of social group and disease state
is called a “compartment”. The three disease states considered are:
Susceptible (S), someone who has never been infected; Infected (I), someone
who is infected and can infect others; and Removed (R), someone who was
previously infected, cannot infect others, and cannot be themselves infected.
A person can be Removed either because they have recovered from their
infection and developed immunity or because they were discovered through
testing and isolated away from others. $S_{k}$ indicates the number of
susceptible people from social group $k$, and similarly for $I_{k}$ and
$R_{k}$.

In this model, the following differential equations describe how people move
between disease states:

$\displaystyle\frac{dS_{k}}{dt}$
$\displaystyle=-\frac{\sum_{j=1}^{n}\beta_{kj}S_{k}I_{j}}{N_{k}}$ (3)
$\displaystyle\frac{dI_{k}}{dt}$
$\displaystyle=\frac{\sum_{j=1}^{n}\beta_{kj}S_{k}I_{j}}{N_{k}}-(\gamma+t_{k})I_{k}$
(4) $\displaystyle\frac{dR_{k}}{dt}$ $\displaystyle=(\gamma+t_{k})I_{k},$ (5)

where $N_{k}$ is the size of the $k$th group, $\beta_{kj}$ describes the
average rate at which infected individuals in group $j$ infect individuals of
group $k$ if group $k$ were fully susceptible, $\gamma$ is the rate at which
individuals recover, and $t_{k}$ is the rate at which we test individuals in
group $k$.

In (3), a group-$k$ infected person infects people in group $k$ at rate
$\beta_{kj}S_{k}/N_{k}$, since only a fraction $S_{k}/N_{k}$ of people in
group $k$ are susceptible. Multiplying by the number of group-$j$ infected
individuals, $I_{j}$, and summing across $j$ gives the rate at which people
are removed from the susceptible compartment in (3) and added to the infected
compartment in (4). Each infected person recovers at a rate $\gamma$ and is
tested at a rate $t_{k}$, resulting in $(\gamma+t_{k})I_{k}$ being subtracted
in (4) and added in (5).

Our decision vector $x=(x_{1},x_{2},x_{3})$, which is the amount of testing we
do, is limited by a capacity constraint $\sum_{j=1}^{3}N_{k}x_{k}\leq T$ for
some fixed T.

We model $\beta_{kj}=\kappa\,\theta_{kj}$, where $\kappa$ is a global
infectivity parameter and $\theta_{kj}$ is the number of individuals of group
$k$ that an infected individual of group $j$ interacts with per day.

The uncertain parameter vector is $\theta=(\theta_{kj}:k,j)$, which can be
estimated before the university or city reopens from contact tracing data that
can be obtained, with effort, from another university or city with similar
social groups. Contact tracing an infected person in social group $j$ yields a
sample of the vector $y_{\cdot,j}=(y_{kj}:k)$, i.e. the numbers of people from
each group with which that individual enjoyed social contact. We assume that
$y_{kj}\sim\text{Lognormal}(\log(\theta_{kj})-\frac{1}{2},1)$, and each
$y_{kj}$ is independent. Letting $M_{j}$ be the number of contact traces of
infected individuals in group $j$, our estimate for $\theta_{kj}$ is the
sample mean of the observed samples for that element, i.e.
$\hat{\theta}_{kj}=\frac{\sum_{i=1}^{M_{j}}y_{kj}^{i}}{M_{j}}$, where
$y_{\cdot,j}^{i}$ is the $i$th trace. Contact tracing requires time from a
trained individual and so is limited. We write this constraint as
$\sum_{j=1}^{3}M_{j}\leq C$.

Our objective function $f(x,\theta)$ is the cumulative number of infected
individuals over a finite horizon of 100 days, as given by the output of a
simulation. We solve this for any fixed $\theta$ by optimizing over $x$ using
L-BFGS-B. Partial derivatives in $D$ are calculated using finite differences.
The optimized allocation is found via a closed form similar to Equation 2, and
1000 samples are used for optimization of the experiment design and the
evaluation of the regret. The baseline allocates equal contact traces to the
three groups. For more implementation details, refer to the supplement.

Results are shown in Table 2 for parameters

$\theta=\begin{pmatrix}12&10&1\\\ 10&8&1\\\ 1&1&1\end{pmatrix},\
\kappa=\frac{1}{105},\ \gamma=0.1,\ T=100$

and varying $C$, where an infected person arrives in group 2 at $T=0$. We use
an independent Gamma prior with shape $\theta_{jk}$ and scale 1 for each
$j,k$, The mean for the prior was chosen so that the first two groups have
significantly more contacts than the third, modeling heterogeneity in contact
rates across social groups (Mossong et al., 2008).

Higher contact rates make it more important to provide sufficient testing in
the first two groups compared to the third, and also make it more important to
estimate the contact rates well in these two groups. Indeed, the optimized
allocation allocates more contact traces to the subpopulations with more
contacts and has significantly less regret.

$C$ | Allocation | Opt. Regret | Uni. Regret
---|---|---|---
$10$ | [5,4,1] | $37\pm 5$ | $49\pm 6$
$30$ | [17,12,1] | $16\pm 2$ | $24\pm 3$
$100$ | [57,42,1] | $6.5\pm 1.0$ | $9.3\pm 1.3$
$300$ | [172,126,2] | $2.2\pm 0.3$ | $3.1\pm 0.4$
Table 2: Comparison of regret under optimized and baseline uniform allocations
in the pandemic example of Section 6.3. The regrets reported are 95%
confidence intervals. The column “Allocation” shows the allocation of contact
traces to groups optimizing the bound in (1).  Figure 3: Interquartile range
of total infected under testing decisions made based on the optimized/baseline
allocation of contact traces for $C=10$.

Figure 3 depicts the pandemic trajectories resulting from testing decisions
made under the optimized and baseline allocations for a particular sample of
$\theta$. The trajectory under the optimized allocations yields notably fewer
infections, demonstrating an improvement in health outcomes.

We also show results when we increase the transmissibility per contact
parameter $\kappa$ by 50%, from $\frac{1}{105}$ to $\frac{1}{70}$ (the case of
decreasing the transmissibility significantly was not interesting as in either
case the number of infected does go over one person). Table 3 shows the
regrets for our optimized allocation versus the uniform allocation, where we
change $C$, the constraint on the number of contact traces performed. Figure 4
shows the corresponding infection trajectory plots over 1000 draws from the
prior. Both demonstrate that using our method results in better testing
decisions that improve health outcomes, even when a larger-scale outbreak
occurs.

$C$ | Allocation | Opt. Regret | Uni. Regret
---|---|---|---
$10$ | [5,4,1] | $45\pm 4$ | $56\pm 5$
$30$ | [16,13,1] | $22\pm 3$ | $26\pm 3$
$100$ | [57,42,1] | $7.6\pm 1.1$ | $10.1\pm 1.2$
$300$ | [172,126,2] | $2.6\pm 0.3$ | $3.4\pm 0.4$
Table 3: Comparison of regret under optimized and baseline uniform allocations
in the pandemic example, when transmissibility is increased 50%. The regrets
reported are 95% confidence intervals. Figure 4: Interquartile range of total
infected under testing decisions made based on the optimized/baseline
allocation of contact traces for $C=10$ and $\kappa=\frac{1}{70}$.

##  7 Conclusion

This work introduced a novel regret bound when using estimate-then-optimize
and a method for using this bound to optimize the experimental design under
distributional assumptions on the underlying model parameter. To justify our
theory, we analyzed three examples in detail, including a realistic
application to pandemic control.

There are several directions in theory and application which would address
some limitations of our method.

From a theoretical perspective, it would be interesting to consider how our
approach could be extended to make decisions about whether to use only a
subset of the uncertain parameters $\theta$. For instance, one may be able to
conclude that because the regret is insensitive to some components of
$\theta$, it may be okay to drop them completely in the experiment while still
maintaining a good decision.

Similarly, one could feasibly use a similar approach for the more general
problem of model selection. In this case, the $\theta$ may be infinite-
dimensional in order to capture non-parametric models. As such, we imagine
more technical machinery would likely be necessary.

Finally, we are improving the ability to make decisions based on data. When
this is used by those whose goals are aligned with the broader society, then
this should tend to improve societal outcomes, but our results could also be
used by those whose goals are not so-aligned.

## References

  * Farias [2007] V Farias.  Revenue management beyond estimate, then optimize.  _Unpublished doctoral thesis, Stanford University, Stanford, CA_ , 2007.
  * Hu et al. [2020] Yichun Hu, Nathan Kallus, and Xiaojie Mao.  Fast rates for contextual linear optimization.  _arXiv preprint arXiv:2011.03030_ , 2020.
  * Wu et al. [2018] Di Wu, Helin Zhu, and Enlu Zhou.  A bayesian risk approach to data-driven stochastic optimization: Formulations and asymptotics.  _SIAM Journal on Optimization_ , 28(2):1588–1612, 2018.
  * Bertsimas et al. [2018] Dimitris Bertsimas, Vishal Gupta, and Nathan Kallus.  Data-driven robust optimization.  _Mathematical Programming_ , 167(2):235–292, 2018\.
  * Foster and Syrgkanis [2019] Dylan J Foster and Vasilis Syrgkanis.  Orthogonal statistical learning.  _arXiv preprint arXiv:1901.09036_ , 2019.
  * Elmachtoub and Grigas [2022] Adam N Elmachtoub and Paul Grigas.  Smart “predict, then optimize”.  _Management Science_ , 68(1):9–26, 2022.
  * El Balghiti et al. [2019] Othman El Balghiti, Adam N Elmachtoub, Paul Grigas, and Ambuj Tewari.  Generalization bounds in the predict-then-optimize framework.  _Advances in neural information processing systems_ , 32, 2019.
  * Ito et al. [2018] Shinji Ito, Akihiro Yabe, and Ryohei Fujimaki.  Unbiased objective estimation in predictive optimization.  In _International Conference on Machine Learning_ , pages 2176–2185. PMLR, 2018.
  * Wilder et al. [2019] Bryan Wilder, Bistra Dilkina, and Milind Tambe.  Melding the data-decisions pipeline: Decision-focused learning for combinatorial optimization.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 33, pages 1658–1665, 2019.
  * Vapnik [1999] Vladimir Vapnik.  _The nature of statistical learning theory_.  Springer science & business media, 1999.
  * Kim et al. [2015] Sujin Kim, Raghu Pasupathy, and Shane G Henderson.  A guide to sample average approximation.  _Handbook of simulation optimization_ , pages 207–243, 2015.
  * Song and Nelson [2015] Eunhye Song and Barry L Nelson.  Quickly assessing contributions to input uncertainty.  _IIE Transactions_ , 47(9):893–909, 2015.
  * Freimer and Schruben [2002] Michael Freimer and Lee Schruben.  Collecting data and estimating parameters for input distributions.  In _Proceedings of the Winter Simulation Conference_ , volume 1, pages 392–399. IEEE, 2002.
  * Pukelsheim [2006] Friedrich Pukelsheim.  _Optimal design of experiments_.  SIAM, 2006.
  * Hastie et al. [2009] Trevor Hastie, Robert Tibshirani, Jerome H Friedman, and Jerome H Friedman.  _The elements of statistical learning: data mining, inference, and prediction_ , volume 2.  Springer, 2009.
  * Guo et al. [2006] Hongbin Guo, Michael Y Li, and Zhisheng Shuai.  Global stability of the endemic equilibrium of multigroup sir epidemic models.  _Canadian applied mathematics quarterly_ , 14(3):259–284, 2006.
  * Mossong et al. [2008] Joël Mossong, Niel Hens, Mark Jit, Philippe Beutels, Kari Auranen, Rafael Mikolajczyk, Marco Massari, Stefania Salmaso, Gianpaolo Scalia Tomba, Jacco Wallinga, et al.  Social contacts and mixing patterns relevant to the spread of infectious diseases.  _PLoS medicine_ , 5(3):e74, 2008.
  * Vershynin [2018] Roman Vershynin.  _High-dimensional probability: An introduction with applications in data science_ , volume 47.  Cambridge university press, 2018.
  * Hsu et al. [2012] Daniel Hsu, Sham Kakade, and Tong Zhang.  A tail inequality for quadratic forms of subgaussian random vectors.  _Electronic Communications in Probability_ , 17:1–6, 2012\.

##  Appendix A Proofs

###  A.1 Proof of Theorem 3.4

###### Proof.

By taking the second order Taylor expansion on $f$ at $x^{*},\hat{\theta}$,
there exists $\overline{x}\in\mathcal{S}(\hat{x},x^{*})$ such that

$\frac{1}{2}(\hat{x}-x^{*})^{\top}\frac{\partial^{2}f}{\partial
x^{2}}\Bigg{|}_{x=\overline{x},\theta=\hat{\theta}}(\hat{x}-x^{*})=f(\hat{x},\hat{\theta})-f(x^{*},\hat{\theta})-\frac{\partial
f}{\partial x}\Bigg{|}_{x=x^{*},\theta=\hat{\theta}}^{\top}(\hat{x}-x^{*}).$

Observe that $\overline{x}\in B_{\hat{\theta}}$ because $B_{\hat{\theta}}$ is
a convex set containing both $\hat{x}$ and $x^{*}$ (it contains
$\hat{x}=x^{*}(\hat{\theta})$ by construction and it contains $x^{*}$ by the
assumption made in the statement of the theorem), and $\overline{x}$ lies on a
line between $x^{*}$ and $\hat{x}$.

By strong convexity, and because $\overline{x}\in B_{\hat{\theta}}$, we have
that

$\displaystyle\frac{1}{2}(\hat{x}-x^{*})^{\top}\frac{\partial^{2}f}{\partial
x^{2}}\Bigg{|}_{x=\overline{x},\theta=\hat{\theta}}(\hat{x}-x^{*})$
$\displaystyle\geq\rho\|\hat{x}-x^{*}\|^{2}$

Combining the previous two equations, we have

$\displaystyle\frac{\rho}{2}\|\hat{x}-x^{*}\|^{2}$ $\displaystyle\leq
f(\hat{x},\hat{\theta})-f(x^{*},\hat{\theta})-\frac{\partial f}{\partial
x}\Bigg{|}_{x=x^{*},\theta=\hat{\theta}}^{\top}(\hat{x}-x^{*})$
$\displaystyle\leq
f(\hat{x},\hat{\theta})-\min_{x^{\prime}}f(x^{\prime},\hat{\theta})-\frac{\partial
f}{\partial x}\Bigg{|}_{x=x^{*},\theta=\hat{\theta}}^{\top}(\hat{x}-x^{*})$
$\displaystyle=-\frac{\partial f}{\partial
x}\Bigg{|}_{x=x^{*},\theta=\hat{\theta}}^{\top}(\hat{x}-x^{*})$ (6)

Now consider the second order Taylor expansion on $\frac{\partial f}{\partial
x}$ with respect to $\theta$, wherein we have that there exists
$\overline{\theta}\in\mathcal{S}(\hat{\theta},\theta^{*})$ such that

$\displaystyle-\frac{\partial f}{\partial
x}\Bigg{|}_{x=x^{*},\theta=\hat{\theta}}^{\top}(\hat{x}-x^{*})$
$\displaystyle=-\frac{\partial f}{\partial
x}\Bigg{|}_{x=x^{*},\theta=\theta^{*}}^{\top}(\hat{x}-x^{*})-(\hat{\theta}-\theta^{*})^{\top}\frac{\partial^{2}f}{\partial
x\partial\theta}\Bigg{|}_{x=x^{*},\theta=\theta^{*}}^{\top}(\hat{x}-x^{*})$
$\displaystyle\quad-\frac{1}{2}D^{2}_{\theta}D_{x}f(x^{*},\overline{\theta})[\hat{x}-x^{*},\hat{\theta}-\theta^{*},\hat{\theta}-\theta^{*}]$

Using first-order optimality of $x^{*}$, we can express this exactly as

$-\frac{\partial f}{\partial
x}\Bigg{|}_{x=x^{*},\theta=\hat{\theta}}=(\hat{\theta}-\theta^{*})^{\top}\frac{\partial^{2}f}{\partial
x\partial\theta}\Bigg{|}_{x=x^{*},\theta=\theta^{*}}^{\top}(\hat{x}-x^{*})-\frac{1}{2}D^{2}_{\theta}D_{x}f(x^{*},\overline{\theta})[\hat{x}-x^{*},\hat{\theta}-\theta^{*},\hat{\theta}-\theta^{*}]$

which by the second-order smoothness assumption implies

$\displaystyle-\frac{\partial f}{\partial
x}\Bigg{|}_{x=x^{*},\theta=\hat{\theta}}(\hat{x}-x^{*})$
$\displaystyle\leq(\hat{\theta}-\theta^{*})^{\top}\frac{\partial^{2}f}{\partial
x\partial\theta}\Bigg{|}_{x=x^{*},\theta=\theta^{*}}^{\top}(\hat{x}-x^{*})+\frac{\beta_{2}}{2}\|\hat{x}-x^{*}\|\|\hat{\theta}-\theta^{*}\|^{2}$

Combining these with equation (1) yields

$\frac{\rho}{2}\|\hat{x}-x^{*}\|^{2}\leq-(\hat{\theta}-\theta^{*})^{\top}\frac{\partial^{2}f}{\partial
x\partial\theta}\Bigg{|}_{x=x^{*},\theta=\theta^{*}}^{\top}(\hat{x}-x^{*})+\frac{\beta_{2}}{2}\|\hat{x}-x^{*}\|\|\hat{\theta}-\theta^{*}\|^{2}.$

As the left is positive, so is the right, and we can square both sides to
yield a valid inequality:

$\displaystyle\frac{\rho^{2}}{4}\|\hat{x}-x^{*}\|^{4}$
$\displaystyle\leq\left(-(\hat{\theta}-\theta^{*})^{\top}\frac{\partial^{2}f}{\partial
x\partial\theta}\Bigg{|}_{x=x^{*},\theta=\theta^{*}}^{\top}(\hat{x}-x^{*})+\frac{\beta_{2}}{2}\|\hat{x}-x^{*}\|\|\hat{\theta}-\theta^{*}\|^{2}\right)^{2}$
$\displaystyle\leq
2\left((\hat{\theta}-\theta^{*})^{\top}\frac{\partial^{2}f}{\partial
x\partial\theta}\Bigg{|}_{x=x^{*},\theta=\theta^{*}}^{\top}(\hat{x}-x^{*})\right)^{2}+\frac{\beta^{2}_{2}}{2}\|\hat{x}-x^{*}\|^{2}\|\hat{\theta}-\theta^{*}\|^{4}$
$\displaystyle\leq 2\|\hat{x}-x^{*}\|^{2}\|\frac{\partial^{2}f}{\partial
x\partial\theta}\Bigg{|}_{x=x^{*},\theta=\theta^{*}}(\hat{\theta}-\theta^{*})\|^{2}+\frac{\beta^{2}_{2}}{2}\|\hat{x}-x^{*}\|^{2}\|\hat{\theta}-\theta^{*}\|^{4},$

where the first inequality uses that $(a-b)^{2}\leq 2a^{2}+2b^{2}$ and the
second uses Cauchy-Schwarz.

As $\hat{x}=x^{*}$ is not meaningful to consider, we assume $\hat{x}\neq
x^{*}$ so that dividing through by $(4/\rho^{2})\|\hat{x}-x^{*}\|^{2}>0$
yields

$\|\hat{x}-x^{*}\|^{2}\leq\frac{8}{\rho^{2}}\left(\|\frac{\partial^{2}f}{\partial
x\partial\theta}\Bigg{|}_{x=x^{*},\theta=\theta^{*}}(\hat{\theta}-\theta^{*})\|^{2}+\frac{\beta^{2}_{2}}{4}\|\hat{\theta}-\theta^{*}\|^{4}\right).$
(7)

Now we use a final Taylor expansion to conclude that there exists
$\overline{x}\in\mathcal{S}(\hat{x},x^{*})$ such that

$\displaystyle f(\hat{x},\theta^{*})-f(x^{*},\theta^{*})$
$\displaystyle=\frac{\partial f}{\partial
x}\Bigg{|}_{x=x^{*},\theta=\theta^{*}}(\hat{x}-x^{*})+\frac{1}{2}\frac{\partial^{2}f}{\partial
x^{2}}\Bigg{|}_{x=\overline{x},\theta=\theta^{*}}(\hat{x}-x^{*})^{2}$
$\displaystyle\leq\frac{\beta_{1}}{2}\|\hat{x}-x^{*}\|^{2}.$ (8)

Combining (2) with (3) yields

$f(\hat{x},\theta^{*})-f(x^{*},\theta^{*})\leq\frac{4\beta_{1}}{\rho^{2}}\left(\|\frac{\partial^{2}f}{\partial
x\partial\theta}\Bigg{|}_{x=x^{*},\theta=\theta^{*}}(\hat{\theta}-\theta^{*})\|^{2}+\frac{\beta^{2}_{2}}{4}\|\hat{\theta}-\theta^{*}\|^{4}\right).$
(9)

∎

###  A.2 Proof of Lemma 4.3

###### Proof.

We observe that under assumption 4.1, we have that

$\sqrt{n}\Sigma^{-1/2}(\hat{\theta}-\theta^{*})\sim N(0,I_{d}),$

where $\theta\in\mathbb{R}^{d}$ and $I_{d}$ is the $d$-dimensional identity
matrix.

We then appeal to equation (3.7) in Vershynin [2018], which gives a high
probability bound for the norm of a multivariate Gaussian.

In particular, we have that

$\displaystyle\mathbb{P}\left(\|\hat{\theta}-\theta^{*}\|_{2}\geq\frac{\sqrt{\lambda_{max}(\Sigma)}}{\sqrt{n}}(t+\sqrt{d})\right)$
$\displaystyle\leq\mathbb{P}(\|\sqrt{n}\Sigma^{-1/2}(\hat{\theta}-\theta^{*})\|_{2}\geq
t+\sqrt{n})$ $\displaystyle=\mathbb{P}(\|g\|_{2}\geq t+\sqrt{d})$
$\displaystyle\leq\mathbb{P}(|\|g\|_{2}-\sqrt{d}|\geq t)$ $\displaystyle\leq
2\exp(-ct^{2})$

for a universal constant $c$ and where $g\sim N(0,I_{d})$.

Under assumption 4.2, we first observe that trivially
$\theta^{*}\in\Theta^{*}$. Furthermore, by definition of openness we know
there exists some $\epsilon$-ball $N_{\epsilon}(\theta^{*})\subset\Theta^{*}$.
Since we desire that $\hat{\theta}$ lies in this ball, we solve for $t$ such
that

$\frac{\sqrt{\lambda_{max}(\Sigma)}}{\sqrt{n}}(t+\sqrt{d})=\epsilon$

to yield the high probability event that $\hat{\theta}$ lying in this ball.

This yields

$t=\frac{\epsilon\sqrt{n}}{\sqrt{\lambda_{max}(\Sigma)}}-\sqrt{d}.$

For $n>\frac{d\lambda_{max}(\Sigma)}{\epsilon^{2}}$, we have that $t$ is
positive for a valid bound.

Plugging this into the probability bound, we get the probability that
$\|\hat{\theta}-\theta^{*}\|\geq\epsilon$ is bounded above by
$2\exp(-cd)\exp\left(-\frac{cn\epsilon^{2}}{\lambda_{max}(\Sigma)}+\frac{2c\epsilon\sqrt{nd}}{\sqrt{\lambda_{max}(\Sigma)}}\right)$.

Taking $n$ larger than, say, $\frac{16d\lambda_{max}(\Sigma)}{\epsilon^{2}}$,
we have an upper bound of
$2\exp(-cd)\exp\left(-\frac{cn\epsilon^{2}}{2\lambda_{max}(\Sigma)}\right)$.

So for $n$ sufficiently large, i.e.
$n\geq\max\left(\frac{d\lambda_{max}(\Sigma)}{\epsilon^{2}},\frac{16d\lambda_{max}(\Sigma)}{\epsilon^{2}}\right)=\frac{16d\lambda_{max}(\Sigma)}{\epsilon^{2}}$,
taking the complementary event concludes the proof.

∎

###  A.3 Proof of Theorem 4.4

###### Proof.

By the previous theorem,
$f(\hat{x},\theta^{*})-f(x^{*},\theta^{*})\leq\frac{4\beta_{1}}{\rho^{2}}\left(\|D(\hat{\theta}-\theta^{*})\|^{2}+\frac{\beta^{2}_{2}}{4}\|\hat{\theta}-\theta^{*}\|^{4}\right)$
when $x^{*}\in B_{\hat{\theta}}$.

Therefore, the probability that

$\displaystyle f(\hat{x},\theta^{*})-f(x^{*},\theta^{*})>$
$\displaystyle\frac{4\beta_{1}}{\rho^{2}}\left(\operatorname{Tr}\frac{D\Sigma
D^{\top}}{n}+2\sqrt{\operatorname{Tr}\left[\left(\frac{D\Sigma
D^{\top}}{n}\right)^{2}\right]\log n}+2\|\frac{D\Sigma D^{\top}}{n}\|_{2}\log
n\right)$ $\displaystyle+o(\operatorname{Tr}\frac{D\Sigma D^{\top}}{n}\log n)$

is bounded above by the sum of

  * •

the probability that $x^{*}\notin B_{\hat{\theta}}$.

  * •

the probability that
$\|D(\hat{\theta}-\theta^{*})\|^{2}\geq\operatorname{Tr}\frac{D\Sigma
D^{\top}}{n}+2\sqrt{\operatorname{Tr}\left[\left(\frac{D\Sigma
D^{\top}}{n}\right)^{2}\right]\log n}+2\|\frac{D\Sigma D^{\top}}{n}\|_{2}\log
n$,

  * •

the probability that $\|\hat{\theta}-\theta^{*}\|^{4}\in
o(\operatorname{Tr}\frac{D\Sigma D^{\top}}{n}\log n)$.

By the lemma, the probability that $x^{*}\notin B_{\hat{\theta}}$ is bounded
above by $\alpha\exp(-\beta n)$.

By Hsu et al. [2012], the probability that

$\|D(\hat{\theta}-\theta^{*})\|^{2}\geq\operatorname{Tr}\frac{D\Sigma
D^{\top}}{n}+2\sqrt{\operatorname{Tr}\left[\left(\frac{D\Sigma
D^{\top}}{n}\right)^{2}\right]}\sqrt{t}+2\|\frac{D\Sigma D^{\top}}{n}\|_{2}t$

is bounded above by $\exp(-t).$ Choosing $t=\log n$ yields the first term in
bound.

For the little-$o$ term, the same bound from Hsu et al. [2012] yields

$\|\hat{\theta}-\theta^{*}\|^{4}\geq\left(\operatorname{Tr}\frac{\Sigma}{n}+2\sqrt{\operatorname{Tr}\left(\frac{\Sigma}{n}\right)^{2}}\sqrt{t}+2\|\frac{\Sigma}{n}\|_{2}t\right)^{2}$

with probability $\exp(-t)$. Taking the same $t=\log n$ yields a term which is
$o(\operatorname{Tr}\frac{D\Sigma D^{\top}}{n}\log n)$ (note
$\operatorname{Tr}D\Sigma D^{\top}$ and $\operatorname{Tr}\Sigma$ are within a
constant factor corresponding to eigenvalues of $D$.)

Then by the union bound, the probability that
$f(\hat{x},\theta^{*})-f(x^{*},\theta^{*})>\operatorname{Tr}\frac{D\Sigma
D^{\top}}{n}+2\sqrt{\operatorname{Tr}\left[\left(\frac{D\Sigma
D^{\top}}{n}\right)^{2}\right]}\log n+2\|\frac{D\Sigma D^{\top}}{n}\|_{2}\log
n+o(\operatorname{Tr}\frac{D\Sigma D^{\top}}{n}\log n)$ is bounded above by
$\alpha\exp(-\beta n)+\frac{2}{n}$. Taking the complementary event completes
the proof.

Finally, we note that, as a function of $D\Sigma D^{\top}$, the first trace
term is the dominant term because $D\Sigma D^{\top}$ is symmetric and PSD, and
therefore all eigenvalues are nonnegative. Therefore the sum of the
eigenvalues (the trace), or equivalently the 1-norm of the eigenvalues, is
larger than the 2-norm (the second trace term), and also larger than the
largest eigenvalue (the 2-norm term).

∎

######  Remark.

The choice of $t=\log n$ in the bound above is due to the following argument.
Suppose $\theta$ lies in some compact set. Then there exists some upper bound
on the regret, say $M$. Then for large $n$, an upper bound on the expected
regret reduces to $1\cdot\frac{t}{n}+M\cdot\exp(-t).$ Minimizing this as a
function of $t$ yields $t=\log\frac{R}{c}+\log n$.

###  A.4 Verifying Assumptions for Pricing Example

One may easily derive the following

$\frac{\partial f}{\partial
x}=-c(x,\theta)+\theta_{1}xc(x,\theta)(1-c(x,\theta)).$ (10)

To verify the convexity assumptions, first note that setting (10) to 0 yields
that the optimal solution $x^{*}$ satisfies

$x^{*}=\frac{1}{\theta_{1}(1-c(x^{*},\theta))}.$

(This is not a closed form solution as the RHS depends on $x$, but it shows
that $x^{*}>0$.)

Furthermore, the second derivative of $f$ with respect to $x$ is

$\frac{\partial^{2}f}{\partial
x^{2}}=c(x,\theta)(1-c(x,\theta))\left(1+\theta_{1}-\theta_{1}^{2}x(1-2c(x,\theta))\right)$
(11)

Therefore we get

$\frac{\partial^{2}f}{\partial
x^{2}}\Bigg{|}_{x=x^{*}}=c(x^{*},\theta)(1-c(x^{*},\theta))\left(1+\theta_{1}-\theta_{1}\frac{1-2c(x^{*},\theta)}{1-c(x^{*},\theta)}\right)>0,$

since we assumed $\theta_{1}>0$. Also, for any $\theta$, it is easy to see
that this is bounded away from 0 for $x$ in a neighborhood around $x^{*}$.

Furthermore, we observe that Equation (11) is clearly bounded for
$x\in[0,\infty)$ and for all $\theta$ since the logistic function decays
exponentially.

Finally, it remains to check the Hessian of (10) with respect to $\theta$. One
can straightforwardly derive the expressions for the terms of the Hessian:

$\displaystyle\frac{\partial f^{3}}{\partial x\partial\theta_{0}^{2}}=$
$\displaystyle c(x,\theta)(1-c(x,\theta))(2c(x,\theta)-1)$
$\displaystyle+\theta_{1}xc(x,\theta)(1-c(x,\theta))\left((2c(x,\theta)-1)^{2}+2c(x,\theta)(1-c(x,\theta))\right)$
$\displaystyle\frac{\partial f^{3}}{\partial
x\partial\theta_{0}\partial\theta_{1}}=$ $\displaystyle
2xc(x,\theta)(1-c(x,\theta))(2c(x,\theta)-1)$
$\displaystyle+\theta_{1}x^{2}c(x,\theta)(1-c(x,\theta))\left((2c(x,\theta)-1)^{2}+2c(x,\theta)(1-c(x,\theta))\right)$
$\displaystyle\frac{\partial f^{3}}{\partial x\partial\theta_{1}^{2}}=$
$\displaystyle 3x^{2}c(x,\theta)(1-c(x,\theta))(2c(x,\theta)-1)$
$\displaystyle+\theta_{1}x^{3}c(x,\theta)(1-c(x,\theta))\left((2c(x,\theta)-1)^{2}+2c(x,\theta)(1-c(x,\theta))\right)$

Each term in the Hessian includes a multiplicative factor of
$c(x,\theta)(1-c(x,\theta)$. Therefore for any $x\in[0,\infty)$ and any
$\theta$, each term in the Hessian, and thus also its largest eigenvalue, must
remain bounded as the logistic function decays exponentially.

##  Appendix B Implementation Details for Pandemic Example

For our pandemic application, we built a discrete-time simulation of the
multi-group SIR model as described in the paper. In particular, for time
$t=1,\ldots,100$, we have that

$\displaystyle S[t]$ $\displaystyle=S[t-1]-S[t-1]\circ\beta
I[t-1]\circ\frac{1}{N}$ $\displaystyle I[t]$
$\displaystyle=I[t-1]+S[t-1]\circ\beta
I[t-1]\circ\frac{1}{N}-(\gamma\mathbf{1}+x)\circ I[t-1]$ $\displaystyle R[t]$
$\displaystyle=R[t-1]+(\gamma\mathbf{1}+x)\circ I[t-1],$

where $\circ$ denotes entrywise product and $\mathbf{1}$ denotes a vector of
ones. We treat $f(x,\theta)$ as the output of the simulation, where recall
that $\beta=\kappa\theta$.

When optimizing $f$ with respect to the decision variable $x$ for a given
$\theta$, we use L-BFGS-B. Since L-BFGS-B is used for unconstrained problems,
we reparameterized the problem to only have bounds on the variables instead of
constraints. In particular, we define another set of variables $y_{1},y_{2}$,
where $y_{1}$ is the proportion of testing capacity used by the first group,
$y_{2}$ is the proportion of the testing capacity which remains that the
second group uses. Therefore we may include $y_{1},y_{2}\in[0,1]$, which is
amenable to usage by L-BFGS-B.

We use finite difference estimates for the derivative term $D$, with step size
$h=10^{-6}$. In particular, we use

$\frac{\partial^{2}f}{\partial
x\partial\theta}\approx\frac{f(x+h,\theta+h)-f(x+h,\theta-h)-f(x-h,\theta+h)+f(x-h,\theta-h)}{4h^{2}}.$

Finally, $D$, the trace term is minimized in closed-form. In particular, it is
easy to see that we have a problem of the form (after relaxing integrality)

$\displaystyle\min_{n_{1},\ldots,n_{3}}\,$
$\displaystyle\sum_{i=1}^{3}\frac{\rho_{i}^{2}}{M_{i}}$ s.t.
$\displaystyle\sum_{i=1}^{3}M_{i}=C$ $\displaystyle M_{i}\geq 0\quad i=1,2,3$

where
$\rho_{i}^{2}=\sum_{\ell=1}^{2}\sum_{j=1}^{3}\sum_{k=1}^{3}\frac{\partial^{2}f}{\partial
x_{\ell}\partial\theta_{kj}}\sigma_{kj}^{2}$ for $\sigma_{kj}^{2}$ the
variance of a $\text{Lognormal}(\log(\theta_{kj},1))$ random variable.

The Karush-Kuhn-Tucker conditions yield the closed-form solution

$M_{i}=\frac{C\rho_{i}}{\sum_{j=1}^{d}\rho_{j}},$

and we round the solution to the nearest integer (rounding the first two and
taking the difference from $C$ as $M_{3}$). If $M_{3}$ is 0 (which we disallow
as then no samples are collected), we set $M_{3}=1$ and decrement one of
$M_{1},M_{2}$ each with probability 0.5.

##  Appendix C Additional Experiments

###  C.1 Pricing

Figure 5 shows regret versus the number of samples used for the allocation,
for a particular choice of $\theta=[-4,1]$. The linear relationship on the
log-log scale confirms that the regret behaves as $\frac{1}{n}$. This aligns
with our regret bound behaving as $O(\frac{\log n}{n})$, where the $\log n$ is
obscured.

Figure 5: Regret in the pricing example decays as $O(\frac{1}{n})$, where $n$
is the number of samples allocated. Here $\theta=[-4,1]$.

We also see from the above graph that the relative improvement of our optimal
allocation improves as $n$ increase. Table 4 shows the regret of the optimal
and uniform allocations for $n=1000$ samples and more values of $\theta$,
showing further relative improvement relative to when $n=100$.

| Optimized Allocation | Uniform Allocation
---|---|---
$\theta=[-1,1]$ | $1.0\pm 0.3$ | $1.6\pm 0.4$
$\theta=[-2,1]$ | $1.0\pm 0.3$ | $2.0\pm 0.5$
$\theta=[-3,1]$ | $0.9\pm 0.2$ | $1.8\pm 0.4$
$\theta=[-4,1]$ | $1.3\pm 0.4$ | $1.7\pm 0.4$
$\theta=[-5,1]$ | $1.1\pm 0.3$ | $2.4\pm 0.6$
$\theta=[-6,1]$ | $1.7\pm 0.5$ | $1.9\pm 0.4$
$\theta=[-7,1]$ | $1.6\pm 0.4$ | $2.6\pm 0.7$
$\theta=[-8,1]$ | $3.9\pm 1.5$ | $6.7\pm 4.4$
Table 4: Comparison of regret under optimized and baseline uniform allocations
in the pricing example, where 1000 samples are allocated. The quantities are
95% confidence intervals, where the units are in $10^{-3}$.

###  C.2 Pandemic

Figure 6 shows the analogous plot of regret vs number of samples allocated to
Figure 5 from the pricing example. Again, we see the roughly linear
relationship on the log-log scale confirms that the regret behaves as
$\frac{1}{n}$, agreeing with our bound.

Figure 6: Regret in the pandemic example also roughly decays as
$O(\frac{1}{n})$, where $n$ is the number of samples allocated.

##  Appendix D Code

Please find all code used at this anonymized repository:
https://anonymous.4open.science/r/ExpDesign4ETO-DEB3/.


* Folatelli et al. (2016) Folatelli G., et al., 2016, ApJ, 825, L22
  * Foley et al. (2007) Foley R. J., Smith N., Ganeshalingam M., Li W., Chornock R., Filippenko A. V., 2007, ApJ, 657, L105
  * Foley et al. (2011) Foley R. J., Berger E., Fox O., Levesque E. M., Challis P. J., Ivans I. I., Rhoads J. E., Soderberg A. M., 2011, ApJ, 732, 32
  * Foley et al. (2016) Foley R. J., et al., 2016, MNRAS, 461, 1308
  * Fox et al. (2010) Fox O. D., Chevalier R. A., Dwek E., Skrutskie M. F., Sugerman B. E. K., Leisenring J. M., 2010, ApJ, 725, 1768
  * Fox et al. (2011) Fox O. D., et al., 2011, ApJ, 741, 7
  * Fox et al. (2014) Fox O. D., et al., 2014, ApJ, 790, 17
  * Frame et al. (1995) Frame D. J., Cottrell P. L., Gilmore A. C., Kilmartin P. M., Lawson W. A., 1995, MNRAS, 276, 383
  * Fryer et al. (2007) Fryer C. L., et al., 2007, PASP, 119, 1211
  * Fuller & Ro (2018) Fuller J., Ro S., 2018, MNRAS, 476, 1853
  * Gal-Yam et al. (2014) Gal-Yam A., et al., 2014, Nature, 509, 471
  * Galbany et al. (2016a) Galbany L., et al., 2016a, MNRAS, 455, 4087
  * Galbany et al. (2016b) Galbany L., et al., 2016b, A&A, 591, A48
  * Gallagher (1992) Gallagher J. S., 1992, in Drissen L., Leitherer C., Nota A., eds, Astronomical Society of the Pacific Conference Series Vol. 22, Nonisotropic and Variable Outflows from Stars. p. 388
  * Georgy (2012) Georgy C., 2012, A&A, 538, L8
  * Gieles & Portegies Zwart (2011) Gieles M., Portegies Zwart S. F., 2011, MNRAS, 410, L6
  * Gieles et al. (2006) Gieles M., Larsen S. S., Bastian N., Stein I. T., 2006, A&A, 450, 129
  * Götberg et al. (2017) Götberg Y., de Mink S. E., Groh J. H., 2017, A&A, 608, A11
  * Götberg et al. (2019) Götberg Y., de Mink S. E., Groh J. H., Leitherer C., Norman C., 2019, A&A, 629, A134
  * Graur et al. (2017a) Graur O., Bianco F. B., Huang S., Modjaz M., Shivvers I., Filippenko A. V., Li W., Eldridge J. J., 2017a, ApJ, 837, 120
  * Graur et al. (2017b) Graur O., Bianco F. B., Modjaz M., Shivvers I., Filippenko A. V., Li W., Smith N., 2017b, ApJ, 837, 121
  * Graur et al. (2018) Graur O., Zurek D. R., Cara M., Rest A., Seitenzahl I. R., Shappee B. J., Shara M. M., Riess A. G., 2018, ApJ, 866, 10
  * Groh et al. (2008) Groh J. H., Damineli A., Hillier D. J., 2008, in de Koter A., Smith L. J., Waters L. B. F. M., eds, Astronomical Society of the Pacific Conference Series Vol. 388, Mass Loss from Stars and the Evolution of Stellar Clusters. p. 173
  * Guillochon et al. (2017) Guillochon J., Parrent J., Kelley L. Z., Margutti R., 2017, ApJ, 835, 64
  * Habets (1986) Habets G. M. H. J., 1986, A&A, 167, 61
  * Hachinger et al. (2012) Hachinger S., Mazzali P. A., Taubenberger S., Hillebrandt W., Nomoto K., Sauer D. N., 2012, MNRAS, 422, 70
  * Heger et al. (1997) Heger A., Jeannin L., Langer N., Baraffe I., 1997, A&A, 327, 224
  * Heger et al. (2003) Heger A., Fryer C. L., Woosley S. E., Langer N., Hartmann D. H., 2003, ApJ, 591, 288
  * Hora et al. (2012) Hora J. L., et al., 2012, in Proc. SPIE. p. 844239, doi:10.1117/12.926894
  * Hosseinzadeh et al. (2017) Hosseinzadeh G., et al., 2017, ApJ, 836, 158
  * Humphreys & Davidson (1994) Humphreys R. M., Davidson K., 1994, PASP, 106, 1025
  * Humphreys et al. (2002) Humphreys R. M., Davidson K., Smith N., 2002, AJ, 124, 1026
  * Ivanova et al. (2013) Ivanova N., et al., 2013, A&ARv, 21, 59
  * Ivezić et al. (2019) Ivezić Ž., et al., 2019, ApJ, 873, 111
  * Izzard et al. (2004) Izzard R. G., Ramirez-Ruiz E., Tout C. A., 2004, MNRAS, 348, 1215
  * Jacobson-Galán et al. (2020) Jacobson-Galán W. V., et al., 2020, arXiv e-prints, p. arXiv:2005.01782
  * James & Baron (2010) James S., Baron E., 2010, ApJ, 718, 957
  * Jones et al. (2019) Jones D. O., et al., 2019, Transient Name Server AstroNote, 148, 1
  * Jones et al. (2020) Jones D. O., et al., 2020, ApJ, in prep.
  * Kilpatrick & Foley (2018) Kilpatrick C. D., Foley R. J., 2018, MNRAS, 481, 2536
  * Kilpatrick et al. (2017) Kilpatrick C. D., et al., 2017, MNRAS, 465, 4650
  * Kilpatrick et al. (2018a) Kilpatrick C. D., et al., 2018a, MNRAS, 473, 4805
  * Kilpatrick et al. (2018b) Kilpatrick C. D., et al., 2018b, MNRAS, 480, 2072
  * Kiminki & Kobulnicky (2012) Kiminki D. C., Kobulnicky H. A., 2012, ApJ, 751, 4
  * Kippenhahn & Weigert (1967) Kippenhahn R., Weigert A., 1967, Z. Astrophys., 65, 251
  * Kleiser et al. (2018) Kleiser I., Fuller J., Kasen D., 2018, MNRAS, 481, L141
  * Kochanek et al. (2012) Kochanek C. S., Khan R., Dai X., 2012, ApJ, 759, 20
  * Kochanek et al. (2017) Kochanek C. S., et al., 2017, PASP, 129, 104502
  * Langer et al. (1994) Langer N., Hamann W. R., Lennon M., Najarro F., Pauldrach A. W. A., Puls J., 1994, A&A, 290, 819
  * Laplace et al. (2020) Laplace E., Götberg Y., de Mink S. E., Justham S., Farmer R., 2020, A&A, 637, A6
  * Li et al. (2011) Li W., et al., 2011, MNRAS, 412, 1441
  * Lobel et al. (2015) Lobel A., de Jager C., Nieuwenhuijzen H., van Genderen A. M., Oudmaijer R., 2015, in EAS Publications Series. pp 279–280, doi:10.1051/eas/1571062
  * Loeb & Ulmer (1997) Loeb A., Ulmer A., 1997, ApJ, 489, 573
  * Maeder & Meynet (2000) Maeder A., Meynet G., 2000, A&A, 361, 159
  * Margutti et al. (2014) Margutti R., et al., 2014, ApJ, 780, 21
  * Margutti et al. (2017) Margutti R., et al., 2017, ApJ, 835, 140
  * Mauerhan et al. (2013) Mauerhan J. C., et al., 2013, MNRAS, 430, 1801
  * Mauerhan et al. (2018) Mauerhan J. C., Filippenko A. V., Zheng W., Brink T. G., Graham M. L., Shivvers I., Clubb K. I., 2018, MNRAS, 478, 5050
  * Maund & Ramirez-Ruiz (2016) Maund J. R., Ramirez-Ruiz E., 2016, MNRAS, 456, 3175
  * Maund et al. (2006) Maund J. R., et al., 2006, MNRAS, 369, 390
  * Maund et al. (2011) Maund J. R., et al., 2011, ApJ, 739, L37
  * Maund et al. (2016) Maund J. R., Pastorello A., Mattila S., Itagaki K., Boles T., 2016, ApJ, 833, 128
  * McCully et al. (2018) McCully C., Volgenau N. H., Harbeck D.-R., Lister T. A., Saunders E. S., Turner M. L., Siiverd R. J., Bowman M., 2018, in Guzman J. C., Ibsen J., eds, Society of Photo-Optical Instrumentation Engineers (SPIE) Conference Series Vol. 10707, Software and Cyberinfrastructure for Astronomy V. p. 107070K (arXiv:1811.04163), doi:10.1117/12.2314340
  * McGregor et al. (2004) McGregor P., et al., 2004, in Moorwood A. F. M., Iye M., eds, Society of Photo-Optical Instrumentation Engineers (SPIE) Conference Series Vol. 5492, Proc. SPIE. pp 1033–1044, doi:10.1117/12.550288
  * Meakin & Arnett (2006) Meakin C. A., Arnett D., 2006, ApJ, 637, L53
  * Milisavljevic et al. (2015) Milisavljevic D., et al., 2015, ApJ, 815, 120
  * Murguia-Berthier et al. (2020) Murguia-Berthier A., Batta A., Janiuk A., Ramirez-Ruiz E., Mandel I., Noble S. C., Everson R. W., 2020, arXiv e-prints, p. arXiv:2005.10212
  * Neichel et al. (2014) Neichel B., Lu J. R., Rigaut F., Ammons S. M., Carrasco E. R., Lassalle E., 2014, MNRAS, 445, 500
  * Neugent et al. (2018) Neugent K. F., Levesque E. M., Massey P., 2018, AJ, 156, 225
  * Neugent et al. (2020) Neugent K. F., Levesque E. M., Massey P., Morrell N. I., Drout M. R., 2020, ApJ, 900, 118
  * Nomoto et al. (1993) Nomoto K., Suzuki T., Shigeyama T., Kumagai S., Yamaoka H., Saio H., 1993, Nature, 364, 507
  * Ofek et al. (2016) Ofek E. O., et al., 2016, ApJ, 824, 6
  * Oliveira et al. (2003) Oliveira A. S., Steiner J. E., Cieslinski D., 2003, MNRAS, 346, 963
  * Onken et al. (2020) Onken C. A., et al., 2020, arXiv e-prints, p. arXiv:2008.10359
  * Pan et al. (2020) Pan Y. C., Foley R. J., Jones D. O., Filippenko A. V., Kuin N. P. M., 2020, MNRAS, 491, 5897
  * Pastorello et al. (2008) Pastorello A., et al., 2008, MNRAS, 389, 131
  * Pastorello et al. (2010) Pastorello A., et al., 2010, MNRAS, 408, 181
  * Percy & Zsoldos (1992) Percy J. R., Zsoldos E., 1992, A&A, 263, 123
  * Pereira et al. (1998) Pereira C. B., Landaberry S. J. C., da Conceição F., 1998, AJ, 116, 1971
  * Phillips et al. (2013) Phillips M. M., et al., 2013, ApJ, 779, 38
  * Pickles & Depagne (2010) Pickles A., Depagne É., 2010, PASP, 122, 1437
  * Podsiadlowski (1993) Podsiadlowski P., 1993, Space Sci. Rev., 66, 439
  * Podsiadlowski et al. (1992) Podsiadlowski P., Joss P. C., Hsu J. J. L., 1992, ApJ, 391, 246
  * Pooley et al. (2019) Pooley D., et al., 2019, ApJ, 883, 120
  * Poznanski et al. (2012) Poznanski D., Prochaska J. X., Bloom J. S., 2012, MNRAS, 426, 1465
  * Ramirez-Ruiz et al. (2005) Ramirez-Ruiz E., García-Segura G., Salmonson J. D., Pérez-Rendón B., 2005, ApJ, 631, 435
  * Rest et al. (2005) Rest A., et al., 2005, ApJ, 634, 1103
  * Richmond et al. (1994) Richmond M. W., Treffers R. R., Filippenko A. V., Paik Y., Leibundgut B., Schulman E., Cox C. V., 1994, AJ, 107, 1022
  * Rigaut et al. (2014) Rigaut F., et al., 2014, MNRAS, 437, 2361
  * Rochowicz & Niedzielski (1995) Rochowicz K., Niedzielski A., 1995, Acta Astron., 45, 307
  * Sana et al. (2012) Sana H., et al., 2012, Science, 337, 444
  * Schechter et al. (1993) Schechter P. L., Mateo M., Saha A., 1993, PASP, 105, 1342
  * Schlafly & Finkbeiner (2011) Schlafly E. F., Finkbeiner D. P., 2011, ApJ, 737, 103
  * Schneider et al. (2015) Schneider F. R. N., Izzard R. G., Langer N., de Mink S. E., 2015, ApJ, 805, 20
  * Schoenberner & Drilling (1984) Schoenberner D., Drilling J. S., 1984, ApJ, 276, 229
  * Scolnic et al. (2015) Scolnic D., et al., 2015, ApJ, 815, 117
  * Shappee et al. (2014) Shappee B. J., et al., 2014, ApJ, 788, 48
  * Shappee et al. (2016) Shappee B. J., et al., 2016, ApJ, 826, 144
  * Shivvers et al. (2017a) Shivvers I., et al., 2017a, PASP, 129, 054201
  * Shivvers et al. (2017b) Shivvers I., et al., 2017b, MNRAS, 471, 4381
  * Siebert et al. (2020) Siebert M. R., Dimitriadis G., Polin A., Foley R. J., 2020, ApJ, 900, L27
  * Smartt et al. (2015) Smartt S. J., et al., 2015, A&A, 579, A40
  * Smith (2014) Smith N., 2014, ARA&A, 52, 487
  * Smith (2017) Smith N., 2017, Interacting Supernovae: Types IIn and Ibn. Cham, Switzerland : Springer, p. 403, doi:10.1007/978-3-319-21846-5_38
  * Smith & Arnett (2014) Smith N., Arnett W. D., 2014, ApJ, 785, 82
  * Smith & Conti (2008) Smith N., Conti P. S., 2008, ApJ, 679, 1467
  * Smith & McCray (2007) Smith N., McCray R., 2007, ApJ, 671, L17
  * Smith et al. (2004) Smith N., Vink J. S., de Koter A., 2004, ApJ, 615, 475
  * Smith et al. (2009) Smith N., et al., 2009, ApJ, 697, L49
  * Smith et al. (2011) Smith N., Li W., Filippenko A. V., Chornock R., 2011, MNRAS, 412, 1522
  * Smith et al. (2017) Smith N., et al., 2017, MNRAS, 466, 3021
  * Smith et al. (2019) Smith K. W., et al., 2019, Transient Name Server AstroNote, 161, 1
  * Sollerman et al. (2020) Sollerman J., et al., 2020, A&A, 643, A79
  * Srivastav et al. (2014) Srivastav S., Anupama G. C., Sahu D. K., 2014, MNRAS, 445, 1932
  * Stothers & Chin (1999) Stothers R. B., Chin C.-w., 1999, ApJ, 522, 960
  * Stothers & Chin (2001) Stothers R. B., Chin C.-w., 2001, ApJ, 560, 934
  * Stritzinger et al. (2009) Stritzinger M., et al., 2009, ApJ, 696, 713
  * Stritzinger et al. (2018) Stritzinger M. D., et al., 2018, A&A, 609, A135
  * Sukhbold et al. (2016) Sukhbold T., Ertl T., Woosley S. E., Brown J. M., Janka H.-T., 2016, ApJ, 821, 38
  * Sun et al. (2020) Sun N.-C., Maund J. R., Crowther P. A., 2020, MNRAS, 497, 5118
  * Tartaglia et al. (2020) Tartaglia L., et al., 2020, arXiv e-prints, p. arXiv:2009.03331
  * Thöne et al. (2017) Thöne C. C., et al., 2017, A&A, 599, A129
  * Tinyanont et al. (2016) Tinyanont S., et al., 2016, ApJ, 833, 231
  * Tinyanont et al. (2019) Tinyanont S., et al., 2019, ApJ, 887, 75
  * Valenti et al. (2011) Valenti S., et al., 2011, MNRAS, 416, 3138
  * Van Dyk et al. (2000) Van Dyk S. D., Peng C. Y., King J. Y., Filippenko A. V., Treffers R. R., Li W., Richmond M. W., 2000, PASP, 112, 1532
  * Van Dyk et al. (2014) Van Dyk S. D., et al., 2014, AJ, 147, 37
  * Van Dyk et al. (2018) Van Dyk S. D., et al., 2018, ApJ, 860, 90
  * Vanbeveren et al. (1979) Vanbeveren D., de Grève J. P., van Dessel E. L., de Loore C., 1979, A&A, 73, 19
  * Woolf (1973) Woolf N. J., 1973, ApJ, 185, 229
  * Woosley et al. (1994) Woosley S. E., Eastman R. G., Weaver T. A., Pinto P. A., 1994, ApJ, 429, 300
  * Wu et al. (2020) Wu S., Everson R. W., Schneider F. R. N., Podsiadlowski P., Ramirez-Ruiz E., 2020, ApJ, 901, 44
  * Yan et al. (2017) Yan L., et al., 2017, ApJ, 848, 6
  * Yoon (2015) Yoon S.-C., 2015, Publ. Astron. Soc. Australia, 32, e015
  * Yoon (2017) Yoon S.-C., 2017, MNRAS, 470, 3970
  * Yoon & Cantiello (2010) Yoon S.-C., Cantiello M., 2010, ApJ, 717, L62
  * Yoon et al. (2010) Yoon S.-C., Woosley S. E., Langer N., 2010, ApJ, 725, 940
  * Yoon et al. (2012) Yoon S.-C., Gräfener G., Vink J. S., Kozyreva A., Izzard R. G., 2012, A&A, 544, L11
  * Yoon et al. (2017) Yoon S.-C., Dessart L., Clocchiatti A., 2017, ApJ, 840, 10
  * de Jager (1998) de Jager C., 1998, A&ARv, 8, 145
  * de Jager & Nieuwenhuijzen (1997) de Jager C., Nieuwenhuijzen H., 1997, MNRAS, 290, L50
  * de Koter et al. (1996) de Koter A., Lamers H. J. G. L. M., Schmutz W., 1996, A&A, 306, 501
  * van der Hucht (2001) van der Hucht K. A., 2001, New Astron. Rev., 45, 135