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.
102,425 characters · 25 sections · 104 citation commands
Optimizing Adaptive Experiments: A Unified Approach to Regret Minimization and Best-Arm Identification
\affil{Columbia University} \pdfoutput=1 \onehalfspacing
A vast body of research on the multi-armed bandit (MAB) problem studies effective adaptive experimentation lattimore2020bandit. In a typical model, an experimenter sequentially assigns treatment arms to a large pool of individuals. Feedback on the treatment assigned to one individual is rapidly incorporated and used to improve future treatment assignments. Algorithms from this literature have been widely adopted to drive experiments that optimize features of digital platforms.
It is common for real-life implementations to recommend running a bandit algorithm for some time, until enough data is gathered to confidently deploy one treatment arm to govern all future interactions. For instance, consider Google Analytics – a platform offering measurement and optimization tools that is used by 55% of websites worldwide – and Stitch Fix, an online personal styling service. Blog posts from both companies scott2013google, Amadio2020StitchFix contrast traditional A/B tests, which allocate a fixed proportion of experimental effort to each treatment arm, with multi-armed bandit experiments, emphasizing that the latter reduce costs and “waste’’ by adaptively shifting experimental effort away from underperforming arms. Regardless of how experimental effort is apportioned within the experiment, successful experiments end by deploying a treatment arm to the population.
Popular bandit algorithms are not designed to reach a deployment decision in this manner. In the academic literature, the typical goal is to design bandit algorithms that maximize total welfare across all treated individuals, or equivalently, to minimize total regret: the degradation in total welfare due to suboptimal treatment assignment. In principle, one could stop and deploy a fixed arm to the remaining population, but doing so is suboptimal. Moreover, it is known that algorithms designed to minimize regret are slow to gather the information needed to reach a deployment decision bubeck2009pure,villar2015multi; this is true of the Thompson sampling thompson1933likelihood, chapelle2011empirical algorithm deployed by Google Analytics and Stitch Fix.
A variant of the MAB problem called the “best-arm identification problem’’ studies deployment decisions, but ignores welfare (or regret) considerations. A common goal is to minimize the expected experiment length subject to deploying the correct treatment arm to the population with high probability.
This dichotomy between regret minimization and best-arm identification is reflected in the theoretical foundations of these problems. For regret minimization, the seminal work of lai1985asymptotically established sharp asymptotic lower bounds on the expected regret of any policy. Similarly, for best-arm identification, kaufmann2016complexity derived sharp asymptotic lower bounds on the expected sample complexity required to identify the best arm with a given confidence level. A compelling feature of this theory is that it often reveals popular algorithms, such as Thompson sampling, to be asymptotically optimal for their respective objectives. However, these sharp results are specific to each problem formulation in isolation.
A primary goal of our paper is to develop a unified framework that addresses both regret minimization and experiment length considerations while preserving the theoretical sharpness that characterizes each individual problem. This approach aims to develop academic theory that more closely aligns with common experimental practices in industry, providing insights into the tradeoffs inherent in adaptive experimentation with deployment decisions and into the nature of efficient experimentation policies.
This paper introduces a generalized model of bandit experiments. In this model, an experimenter interacts with a large population of individuals. During the experimentation phase, treatment arms are chosen sequentially, and noisy signals of their quality are observed. At any point, the experimenter can choose to conclude the experimentation phase and deploy an arm to the remaining population. Distinct per-period cost functions measure the cost of treatment decisions during the experimentation and deployment phases. We study policies that minimize cumulative expected costs, emphasizing insights into how treatments should be adaptively assigned within the experiment.
In our primary example, costs during each phase reflect the regret from treatment assignment, but costs during the experimentation phase are inflated to encode a desire to rapidly conclude adaptive experimentation and reach a deployment decision. Many of the same insights apply more broadly, so we allow for more abstract cost functions in our theory. Within-experiment costs could, for instance, reflect financial costs of treatment assignment in clinical trials. In simulation experiments hong2021review, they may reflect the differentiated time required to simulate the performance of certain arms to the desired accuracy chick2001new.
We characterize experimentation procedures that minimize cumulative expected costs when the size of the target population is sufficiently large. This leads to several insights:
\paragraph{Limitations of large-population asymptotics.} The main strengths and the main shortcomings of our paper stem from the asymptotic nature of the results. This approach inherits the sharpness of pioneering works like chernoff1959sequential or lai1985asymptotically, lending them a definitive quality. However, our large-population theory implicitly assumes that the benefits of deploying a superior treatment across the population far outweigh the costs of experimentation. In such cases, efficient policies minimize experimentation costs incurred in the process of gathering sufficient information. Our results are not appropriate in cases where the target population is small, experimentation costs are comparatively large, or the differences between treatment arms are nearly undetectable. In such cases, rapidly deploying a suboptimal treatment arm might be preferable to expensive experimentation.
We motivate our theoretical study with a simple numerical illustration. We consider an adaptive experiment conducted to select a single treatment arm to deploy in a population of $n$ individuals. The experimenter interacts with individuals in sequence, selecting one of $k$ treatment arms to assign and observing noisy `reward' outcomes. In this experiment, the mean reward of arm $i\in[k]$ is given by a fixed, unknown value $\theta_i$, and reward noise is standard Gaussian. At any point, the experimenter can choose to stop the experiment and deploy a treatment arm to the remaining population.
We compare policies in terms of their average experiment length and average cumulative regret. Regret measures the total suboptimality in treatments assigned across all individuals in the population, including those treated post-experiment. We imagine that committing to the deployment of a single treatment reduces operational costs. Hence, among policies that incur a given level of regret, those that reduce the average length of the adaptive experimentation phase are preferable.
The problem formulation is described formally in Section (ref) and implementation details of the experiments are discussed in Appendix (ref).
\paragraph{Policies compared.}
We compare two ways of adaptively selecting treatment arms within an experiment.
In these numerical experiments, we apply both methods with a simple stopping rule based on $Z$-statistics, which stops once there is a high-probability guarantee of having identified the best-arm. Our theory in Section (ref) implies this stopping rule is enough to attain a sharp asymptotic efficiency results.
\paragraph{Findings and observations.}
Figure (ref) compares the performance of these policies empirically. We make several observations:
These results highlight interesting performance tradeoffs when applying popular heuristic policies. Rather than focus on specific policies, we aim to answer more fundamental questions about the optimal way to gather information within an experiment. It will turn out to be the case, however, that top-two Thompson sampling gathers information “optimally” in an appropriate asymptotic sense, and that this holds for a broad class of objectives. Therefore, this section may provide intuition that is helpful to understanding our broader theory in subsequent sections.
Many papers have provided guarantees on both within-experiment and post-experiment performance in models of adaptive experimentation. Ours is unique in providing a sharp theory of asymptotic efficiency (Definition (ref)) that unifies and generalizes two parts of the canon of the multi-armed bandit literature: pure regret minimization problems in the style of lai1985asymptotically and (fixed-confidence) best-arm identification problems in the style of garivier2016optimal. An attractive feature of sharp theory, like that of lai1985asymptotically, is that it provides a sense in which algorithms such as Thompson sampling or upper confidence bound (UCB) are exactly optimal, and not e.g. within a factor of five of optimal. This approach also yields some novel insights, as discussed in Section (ref).
Our analysis builds on foundational insights by chernoff1959sequential, anantharam1989asymptotically2, rajeev1989asymptotically1 and graves1997asymptotically. These papers all study a min-max optimization problem that characterizes asymptotic limits on cost or regret. In the appendix, we establish our main insights by analyzing this min-max problem as a two-player game and identifying its unique equilibrium.
Our model allows the experimenter to choose when to stop experimenting adaptively as information is revealed. Our work is most closely related to papers of chan2006sequential, bui2011committing, jamieson2014lilUCB, degenne2019bridging, and zhang2023fast, which allow for adaptive stopping and study both within-experiment regret and post-experiment decision quality. Similar to our length-regret objectives, bui2011committing study a modified regret measure that incentivizes early commitment to a single treatment arm. Our results improve on their Theorem 3 and 5, which provide (non-matching) lower and upper bounds on this modified regret measure. jamieson2014lilUCB and degenne2019bridging study upper confidence bound algorithms that can ensure that the optimal treatment arm is selected with high probability. degenne2019bridging carefully studies how varying tuning parameters trades off regret and probability of incorrect selection, whereas jamieson2014lilUCB mentions this possibility informally. While these three papers construct specific policies which guarantee low experiment-length and low regret, we develop a sharp asymptotic theory of optimal experimentation for a broad class of objectives and, as a consequence, characterize the Pareto frontier between experiment-length and regret. Recent work of zhang2023fast carefully studies an extreme point of the Pareto frontier; they minimize experiment length subject to the constraint that the asymptotic scaling of regret is exactly minimized.
Our contribution is most related to the paper of chan2006sequential, which has been largely overlooked in the literature. Their results are asymptotically sharp, but different from ours. First, in our formulation there is no constraint on the stopping rule the experimenter can employ. Instead, an overall cost function incentivizes them to stop only once adequate information is gathered. Second, chan2006sequential only study the probability of selecting an arm whose distance from optimality exceeds a pre-specified tolerance. Our post-experiment cost function can be quite general, encompassing regret measures as a special case. These differences are essential to recovering the regret results of lai1985asymptotically and accommodating them introduces challenges in the analysis.\footnote{See Remark (ref) for comments on how the first change impacts the lower bound proof. In terms of modeling, our link to lai1985asymptotically results from the ability to set within-experiment and post-experiment cost functions (nearly) equal to the per-period regret. Formulations that constrain the probability of incorrect selection seem to be unable to recover the overall regret objective. } Concurrently with our work, kanarios2024cost study a model similar to that of chan2006sequential but without requiring an indifference zone. While these papers offers sharp theory, they study different models and do not contain the four main insights mentioned in Section (ref).
Many other works study problems in which the experimenter must stop at a pre-determined time. In these settings, BUBECK20111832, russo2018learning, krishnamurthy2023proportional, qin2023adaptive, zhong2023achieving study both within-experiment and post-experiment regret. There is currently no sharp theory of asymptotically efficient policies in this formulation, even in simpler models which focus solely on the probability of selecting the best arm. An influential work of glynn2004large used large deviation theory to study optimal static allocations, providing a new perspective on so-called optimal computing budget allocation chen2000simulation. Implementing the ideal allocation in glynn2004large requires knowledge of the true arm-means. Much effort has gone into designing implementable adaptive algorithms that converge almost surely to the ideal allocation. See chen2023balancing and the references therein. Unfortunately, these do not satisfy the same large-deviations guarantee, and there are questions of whether universally efficient policies exist at all in problems with a pre-determined stopping time; see qin2022open,ariu2021policy,degenne2023existence.
A third kind of asymptotic theory looks at the rate of concentration of a Bayesian posterior distribution as information is acquired. russo2016simple,russo2020simple constructed asymptotically optimal top-two sampling algorithms according to this measure. Most of the expressions defining asymptotic optimality matched those derived from a purely frequentist perspective by garivier2016optimal, whose work appeared in the same conference. Later papers by qin2017improving and shang2020fixed provided guarantees for these top-two sampling algorithms in the same setting as garivier2016optimal, which involves minimizing the expected stopping time subject to a constraint on the probability of identifying the optimal arm. We build on that work in Section (ref) to give insight into the asymptotic efficiency of top-two Thompson sampling for our generalized problem formulation. The exploration sampling algorithm of kasy2021adaptive is very similar to top-two Thompson sampling applied with an unbiased coin, and exactly equivalent in large populations. Both top-two Thompson sampling and exploration sampling have been used in recent real-world field experiments kasy2021adaptive, Rosenzweig2022Conversations.
Other works have studied within-experiment and post-experiment performance from very different angles. A line of work on information acquisition concentrates on the exact characterization of optimal strategies tailored to specific objective functions Wald:1947, arrow1949bayes, lai1980sequential, Fudenberg2018, morris2019wald, Liang2022, adusumilli2023sample. This tends to require studying very specialized models that cannot be easily compared to ours. Other papers derive useful algorithms by directly approximating the dynamic programming problem that defines Bayesian optimal performance chick2009economic, chick2012sequential, chick2021bayesian. Additionally, LiuMBP14, li2022algorithms, caria2023adaptive, athey2022contextual contribute to the literature through simulation, numerical analyses, empirical studies or field experiments, encompassing a spectrum of within- and post-experiment objectives.
It is crucial that our work emphasizes the quality of post-experiment decision-making, rather than the goal of accurately estimating the post-experiment performance of all arms or their treatment effects. Adaptive experiments for treatment effect estimation are most often studied in problems with two arms, treatment and control. See bhat2020near, zhao2023adaptive, dai2023clipogd and references therein for recent work along these lines. Interesting work of adusumilli2022neyman observes that adaptive experiments for treatment effect estimation are also ideal for identifying the best arm, if there are just two treatment arms. When there are many arms, as in erraqabi17a, simchi-levi2023MABExperimentalDesign, accurately estimating the post-experiment quality of all arms requires measuring clearly inferior treatment arms many times to understand precisely how inferior they are. Multi-armed bandit algorithms derive their efficiency by focusing on post-experiment decision quality; they reduce cost by learning just enough about inferior arms to confidently distinguish them from the best arm. (In other words, the precision with which an arm is related to its optimality gap).
An adaptive experiment is conducted to select a single treatment arm to deploy to a target population of $n$ individuals, among $k$ options. The potential outcome when treatment $i \in [k] \triangleq \{1,\ldots, k\}$ is assigned to individual $t\in \{0,1,\ldots,n-1\}$ is a scalar random variable $Y_{t,i}$, with larger values indicating more desirable outcomes. Assume the potential outcomes $(Y_{t,i})_{t\in \{0, 1, \ldots, n-1\} } \overset{\text{i.i.d}}\sim P(\cdot \mid \theta_i)$ associated with any treatment $i\in[k]$ are drawn independently across individuals from a distribution $P(\cdot \mid \theta_i)$ with unknown parameter. If these parameters were known, the experimenter would deploy an arm with highest average treatment effect, $\max_{i\in[k]} \intop y P(\mathrm{d}y\mid \theta_i)$.
Instead, they conduct an adaptive experiment to gather information before deploying an arm to the population. The experimenter interacts sequentially with individuals in the population. Assuming the experiment has not yet stopped, then on basis of the outcomes $Y_{0,I_0}, \ldots, Y_{t-1, I_{t-1}}\in \mathbb{R}$ of treatments $I_0,\ldots, I_{t-1}\in [k]$ assigned to the first $t <n$ individuals, the experimenter can choose either to continue experimental treatment assignments or to stop and deploy a single treatment to the remaining population:
Once $t=n$, the entire population has been treated and the experiment must end by default. In this case, we set the stopping time $\tau=n$.
A policy $\pi$ is a (possibly randomized) rule for making the sequential decisions above. Formally, it is a function that maps the population size $n$, the observations $(I_\ell, Y_{\ell, I_{\ell}})_{\ell \in\{0,\ldots, t-1\}}$ with $t<n$ in a non-stopped experiment, and an exogenous random seed $\zeta$, to a decision $\pi(n, (I_\ell, Y_{\ell, I_{\ell}})_{\ell \in\{0,\ldots, t-1\}}, \zeta)$. A decision is a pair of the form $(\mathtt{Continue}, I_t)$ or $(\mathtt{Stop}, \hat{I}_t)$. We make explicit that decisions depend on the population size to accommodate asymptotic analysis in which the population size grows.
The experimenter's goal is to deploy a policy that optimally balances the expected cost of experimenting with a desire to administer high quality treatments. The objective is formulated precisely in Sections (ref) and (ref).
We study the case where potential outcome distributions are members of a one-dimensional exponential family. The reader may have in mind Gaussian distributions with known variance, Bernoulli distributions, or Poisson distributions. See efron2022exponential or cappe2013kullback for background. Formally, we study outcome distributions that assign to any subset of outcomes $\mathcal{Y} \subset \mathbb{R}$ the probability
Here $\eta(\cdot)$ is a strictly increasing function that associates any $\theta$ with a unique canonical parameter $\eta(\theta)$, the base measure is denoted by $\rho$, and $b(\theta) = \log \intop_{\mathbb{R}} \exp\left(\eta(\theta) y\right) \rho(\mathrm{d}y)$ is the cumulant generating function. We assume the exponential family is regular, i.e. that the natural parameter space $\{\theta \in \mathbb{R} : b(\theta) < \infty \}$ is an open interval. Finally, we assume that $\theta$ denotes the mean of the distribution, i.e. $\theta = \intop y P(\mathrm{d}y \mid \theta)$, which can always be ensured by change of variables.
We let $\bm{\theta} =(\theta_1, \ldots, \theta_k)$ denote the vector of unknown parameters and call $\bm{\theta}$ a problem instance. We define $I^*(\bm{\theta}) \triangleq \operatorname*{arg\,max}_{i \in [k]} \theta_i$ to be the set of optimal arms. In this paper, we focus on the set of problem instances with a unique best arm, formally defined as \[ \Theta \triangleq \left\{\bm{\theta} = (\theta_1,\ldots,\theta_k)\in \mathbb{R}^k \,\, : \,\, b(\theta_i) < \infty, \, \forall \, i\in [k]\, \text{ and } \, I^*(\bm{\theta}) \text{ is a singleton set}\right\}. \] For $\bm{\theta}\in\Theta$, we overload the notation $I^*(\bm{\theta})$ to be the only element in the singleton set. We often use the shorthand $I^* = I^*(\bm{\theta})$.
This subsection introduces an important special case of our model. For any $\bm{\theta}\in\Theta$ and $c \geqslant 0$, the overall cost function
assesses a policy's performance through the regret incurred and experimentation time required, defined as
As a reminder, we follow the convention that $I_{t} =\hat{I}_{\tau}$ for each $t\in \{\tau,\ldots, n-1\}$, reflecting that the experimenter has effectively pre-committed to assigning an arm to future individuals.
The traditional multi-armed bandit literature focuses solely on minimizing regret, or, equivalently, on maximizing the cumulative reward generated by treatment assignment. The cost measure in (ref) augments regret considerations by assigning a cost to adaptive experimentation itself. Among policies with similar regret, those that quickly cease experimentation and commit to a treatment arm are preferred. When $c$ is large, the experimenter may prefer to prioritize aggressive information gathering early on, incurring extra regret in order to stop experimentation early.
We will see that, as the population size $n$ tends to infinity, efficient algorithms have the character of multi-armed bandit algorithms if $c$ is a very small constant and that of best-arm identification algorithms if $c$ is a very large constant. Varying $c$ enables us to characterize the nature of optimal policies in between these two extremes and, indirectly, to characterize the Pareto frontier between length and regret. A practitioner may then simulate an optimal policy (e.g. top-two TS in Algorithm (ref)) for a range of different $c$'s and select a value that best aligns with their goals.
We now introduce a general class of objective functions, of which the length-regret objectives in Section (ref) are a special case. While this may seem to suggest that precise specification of an objective function is the most important design consideration, our main insight is that a simple class of policies (mostly characterized by an information balance condition) is asymptotically optimal for a very broad class of objectives.
Define the total expected cost of the experiment by
where for any $i\in[k]$, $C_i:\mathbb{R}^k \mapsto\mathbb{R}_{\geqslant 0}$ and $\Delta_i:\mathbb{R}^k \mapsto\mathbb{R}_{\geqslant 0}$ are positive cost functions; respectively, these assign a per-individual cost to each treatment assignment within- and post-experiment. Length-regret objectives are a special case in which $C_{i}(\bm{\theta}) = c+(\theta_{I^*}-\theta_{i})$ and $\Delta_{i}(\bm{\theta})=\theta_{I^*}-\theta_{i}$. Note that while the function forms are known to the experimenter, the function values $C_i(\bm{\theta})$ and $\Delta_i(\bm{\theta})$ depend on the unknown parameter $\bm{\theta}$.
The next example illustrates one natural specification of the generalized cost function.
We place two assumptions on the cost functions. The first is mild and assumes that deploying the best arm $I^*$ to the population is preferred and (without loss of generality) $\Delta_{I^*}(\bm{\theta})=0$.
The next assumption is more substantial and indicates that the continued experimentation is strictly more costly than immediate deployment of the optimal arm. For a length-regret objective, the cost $c$ can be arbitrarily close to zero, but never exactly equal to zero. Unsurprisingly, our theory approximates known results in the case of $c=0$ by picking $c$ to be sufficiently small.
We want to be able to argue that a specific policy incurs nearly minimal cost in a regime where the population size is very large. To provide sharp statements, we construct a sequence of problems in which the population size $n$ grows. Given some broad class of policies $\Pi$, we seek a policy $\pi^*\in \Pi$ that is universally efficient in the large population limit, in the sense that for any other competing policy $\pi\in \Pi$,
This notion of optimality is quite stringent, since it requires that $\pi^*$ is asymptotically optimal simultaneously for all arrangements of the arm means $\bm{\theta}$. We emphasize that this notion of optimality, which is a rewriting of lai1985asymptotically, is different from minimax optimality because since the large population limit is taken after fixing $\bm{\theta} \in \Theta$.
The choice of a reasonable class of policies $\Pi$ is crucial. To understand the crux of the issue, consider a policy that stops experimentation after gathering very little information and then “guesses” which arm to deploy to the population. At the extreme, it may forego experimentation and deploy a fixed arm immediately. This policy incurs zero cost on instances $\bm{\theta}$ in which it happens to deploy the true best arm --- a benchmark against which no reasonable policy can compete. The next definition excludes brittle policies of this type. Peaking ahead at our theory (see e.g. Theorem (ref)), we will construct policies whose costs scale with $\ln(n)$, i.e. just logarithmically in the population size. Therefore, following lai1985asymptotically and Definition 16.1 in lattimore2020bandit, we say a policy is consistent if its total cost never scales exponentially faster than $\ln(n)$.
Within the broad class of consistent policies, we seek one which is universally efficient.
Note that it is easy to show that a policy $\pi^*$ must also be consistent if it satisfies (ref).
\paragraph{Optimal cost scaling.} As mentioned above, our theory will show that total costs scale just logarithmically in the population size. The following lemma, which we state without proof, connects the notion of universal efficiency to the optimality of an instance-dependent constant that determines the scaling of costs. For two sequences of scalars $\{a_n\}$ and $\{b_n\}$, we write $a_n \sim b_n$ if $a_n/b_n \to 1$.
This section presents our main insights into the nature of asymptotically efficient policies. We restrict to the special case where observations are normally distributed with known variance, i.e $p(y\mid\theta_i) = \mathcal{N}(\theta_i, \sigma^2)$, making the presentation easier to follow. The core theory extends gracefully to one-dimensional exponential family distributions.
Our main insights, previewed first in the introduction, are established here. In particular, Sections (ref) and (ref) establish the insights into the nature of asymptotically efficient policies. Section (ref) studies the Pareto frontier between regret and experiment length, and Section (ref) provides a formula for optimal scaling of total cost that connects to a famous result of lai1985asymptotically.
This subsection provides a general algorithm template that specifies the condition upon which an experiment stops and which arm will be deployed upon stopping, but leaves open how information is gathered within the experiment itself. First we introduce some notation that is needed in the algorithm statement. For some $t\leqslant \tau$, if the number of samples of arm $i$, denoted by $N_{t,i} \triangleq \sum_{\ell=0}^{t-1} \mathbb{1}(I_\ell =i)$, is positive, define the empirical mean reward and associated standard error as
When $N_{t,i} = 0$, we let $m_{t,i} = 0$ and $s_{t,i} = \infty$.
For any two arms $i, j\in[k]$, the $Z$-statistic for the difference in means
measures the strength of evidence that arm $i$ outperforms arm $j$ in the population. In non-adaptive experiments, $Z_{t,i,j}\sim \mathcal{N}\left(\frac{ \theta_i - \theta_j }{ \sqrt{\sigma^2/N_{t,i} + \sigma^2/N_{t,j} } }, 1\right)$ has a Gaussian distribution with unit variance. When $N_{t,i}=0$ or $N_{t,j}=0$, we let $Z_{t,i,j}=0$.
Algorithm (ref) provides a general template for algorithm design. The experimenter continues experimenting until certain $Z$-statistics are uniformly large, with threshold picked so that the probability of selecting a suboptimal arm is $O\left(\frac{1}{n}\right)$. In this paper, we focus on the following instantiation of such threshold: let $\gamma_0(n) = +\infty$ and for $t=1,\ldots, n-1$,
Upon stopping, the experimenter deploys the arm with highest empirical mean to the remaining population. An unspecified “anytime\footnote{The term “anytime” refers to the fact that the allocation rules do not take the population size $n$ as input. They are fixed functions that map histories of arbitrary length to action distributions. This is not a requirement in our lower bounds, but it is sufficient for designing asymptotically optimal rules and simplifies analysis of them.} allocation rule” governs adaptive assignment of treatment arms during the experiment. This section focuses on the nature of optimal allocation rules.
For asymptotic analysis of the allocation rule supplied in Algorithm (ref), it is convenient to ignore the stopping rule altogether and imagine the allocation rule were applied indefinitely. For this purpose, we extend the array of latent potential outcomes associated with arm $i\in [k]$ to the infinite array $(Y_{t,i})_{t \in \mathbb{N}_0}$. An anytime allocation rule can be applied without stopping to produce an infinite sequence of actions $(I_{t})_{t \in \mathbb{N}_0}$ with
We call the infinite sequence of within-experiment outcomes $(I_t, Y_{t,I_t})_{t\in \mathbb{N}_0}$ an indefinite-allocation sample path.
Notice that the population size $n$ is not relevant to the above construction. It plays a role only in the stopping time
which is a function of the indefinite-allocation sample path and the specified population size.
We emphasize that this construction is used only to analyze policies that fit the template of Algorithm (ref). Our lower bound proofs do not use such a construction.
We offer a sufficient (and almost necessary) condition on allocation rules for Algorithm (ref) to be universally efficient. The result references a custom notion of convergence for random variables that is slightly more stringent than almost sure convergence. We defer discussion of this technical detail until to Section (ref). Throughout, we denote the empirical allocation vector by
It is helpful to think of the long-run allocation as having two components: a scalar exploitation rate $p^*_{I^*}$ and a vector allocation of residual exploration rates $(p_j^*)_{j\neq I^*} \in \mathbb{R}^{k-1}$. Empirical analogues of these rates were depicted by black and gray bars, respectively, in Section (ref) -- Figure (ref). Theorem (ref) reveals the following insight:
As the name suggests, one can interpret information balance (ref) as balancing the weight of evidence against suboptimal arms. From the formula for the (squared) $Z$-statistics in (ref), information balance is easily seen to be equivalent to the property
i.e. $ Z^2_{t,I^*,i}/Z^2_{t, I^*, j} \to 1$. Attaining information balance requires sampling grossly suboptimal arms less frequently and allocating more samples to more competitive arms. Popular bandit algorithms are designed to somewhat `automatically' meet such a constraint. The next remark provides some intuition for this result.
We close this section with a remark on linking ${\bm p}^*$ to segments of the literature that study best-arm identification and regret-minimization.
The pioneering work of lai1985asymptotically identified that a policy $\pi$ has asymptotically optimal regret scaling if and only if,
The notation $f(n) \sim g(n)$ means that $f(n)/g(n) \to 1$ and $ {\rm KL}(\theta, \theta')$ denotes the KL-divergence between the distributions $p(y\mid\theta)$ and $p(y\mid\theta')$ parameterized by mean values $\theta$ and $\theta'$, respectively.
The next theorem provides a similar result for our generalized problem formulation.
Consider the length-regret objectives in Section (ref), where $C_{i}(\bm{\theta}) = c+(\theta_{I^*}-\theta_i)$. As $c \to 0$, the objective is equivalent to the regret objective in lai1985asymptotically. In that limit, (ref) recovers (ref), since $C_{i}(\bm{\theta}) \to \theta_{I^*}-\theta_i$ and $p^*_{I^*}\to 1$. See also Remark (ref). Although this expressions look very different, (ref) also matches one from garivier2016optimal in best-arm identification problems where $C_{i}(\bm{\theta})=1$. (See Theorem (ref) for simplification of the min-max problem studied in garivier2016optimal.)
It is not difficult to engineer a universally efficient allocation rule that mimics the long-run proportions ${\bm p}^*$. See Algorithm (ref) in Appendix (ref). Here we demonstrate that, after simple modifications, leading bandit algorithms can also be universally efficient.
We focus on a modification of Thompson sampling (TS) thompson1933likelihood, a leading bandit algorithm that is widely used in both academia and industry. Pseudocode for standard TS is presented in Algorithm (ref). Rather than play the arm with the highest estimated mean, it plays the arm with the highest posterior sample; the variance in this sampling drives exploration. Another interpretation of this method is that it samples an arm according the posterior probability it is the optimal arm scott2010modern. Algorithm (ref) is presented using an improper prior.\footnote{With an improper prior, $s_{t,i}=\infty$ if an arm has never been played before. In that case, $\tilde{\theta}_i$ takes on either positive or negative infinity, with equal probabilities.} If related data is available prior to the experiment, encoding this in an informed prior can have a substantial impact on practical performance.
As mentioned in Section (ref), Thompson sampling can perform poorly when the length of the experimentation phase is a key consideration (see Section (ref)). As the experimenter gains confidence about the identity of the optimal arm, it plays that arm almost exclusively. Therefore, it is slow to gather information about competing arms. Algorithm (ref) presents pseudocode for the top-two sampling russo2020simple variant of Thompson sampling discussed previously in Section (ref). It overcomes this shortcoming of regular Thompson sampling by exploring competing arms more frequently. It runs Thompson sampling until two distinct arms are drawn --- a leader $I_t^{(1)}$ and a challenger $I_t^{(2)}$ --- and flips a biased coin to pick among them. As the posterior concentrates, the same arm is consistently picked as the leader, and the challenger is picked randomly according the posterior probability it is is optimal given that the leader is not.
russo2016simple,russo2020simple showed that asymptotic efficiency in best-arm identification problems could be attained by “tuning" the coin's bias, but suggested that simple constant choices (like $h_t=1/2$) already performed well. qin2023dualdirected shows that an extremely simple selection rule attains asymptotic optimality in best-arm identification problems (though subtle mathematics is involved in proving this). Building on their proposal, we suggest the rule:
where $p_{t,i} = \frac{N_{t,i}}{t}$ is the proportion of time arm $i$ has been played in the past. The bias $h_t$ is large, meaning arm $I_t^{(1)}$ is more likely to be chosen, when this arm has been played less often or has lower estimated experimentation cost. If either the leader or challenger has never been sampled before, we use the default choice $h_t=1/2$.
The next result (nearly) establishes that top-two TS is a universally efficient allocation rule. The proof adapts results on top-two TS from qin2017improving, russo2020simple, shang2020fixed and qin2023dualdirected to establish (strong) convergence of empirical sampling proportions $\bm{p}_t$ to the optimal allocation ${\bm p}^*$. The analysis on which we build is quite intricate, and imposes some simplifying assumptions. For this reason, Proposition (ref) does not cover instances in which two arms have identical performance, and requires a more stringent regularity condition (Assumption (ref)). These restrictions relate to challenges\footnote{These technical restrictions are used in an initial part of the analysis that, essentially, excludes the possibility that top-two TS neglects to explore an arm as the number of interactions $t$ goes to infinity. See Section (ref). Uniform bounds on $C_{i}(\cdot)$ play a role in analyzing (ref) during this initial phase, which otherwise could blow up if the empirical mean vector $\bm{m}_t$ takes very extreme values. A more thorough proof might apply concentration inequalities to control $\bm{m}_t$ rather than assume $C_i(\cdot)$ is uniformly bounded.} of analyzing the transient performance of top-two TS while dealing with the bespoke converge notion in Definition (ref).
Past theory gives some insight into the inner working of top-two Thompson sampling. It suggests information balance (ref) is somehow attained automatically through posterior sampling. Intuitively, if the weight of evidence against a suboptimal arm is especially large, that arm is very unlikely to be chosen as the challenger $I_t^{(2)}$. As information about the other arms accumulates, information imbalances correct. This result leaves open how to adjust the long-run exploitation rate; one can interpret (ref) as a resolution to that problem.
We have seen in Theorem (ref) that the optimal long-run proportions depend on the particulars of the cost-functions only through a single scalar: the optimal long-run exploitation rate. This structure makes it easy to study the tradeoffs between different measures of performance.
As in Section (ref), our presentation here focuses on the tension between two important performance measures: the cumulative regret in treatment decisions applied to the population and the length of the experimentation phase, which are induced by a special case of our model in which for any treatment arm $i\in[k]$, $C_{i}(\bm{\theta}) = c+(\theta_{I^*}-\theta_{i})$ and $\Delta_{i}(\bm{\theta})=\theta_{I^*}-\theta_{i}$ with $c > 0$ penalizing long experiment. With Lemma (ref), we define the (asymptotic) attainable region as follows:
For interpretation of the attainable region, it is important that the set of consistent policies $\Pi$, introduced in Definition (ref), does not depend on the particular cost functions. As a result, the set $\mathcal{F}_{\bm{\theta}}$ characterizes which pairs are attainable, independently of whether they are desirable under specific cost functions. This is ensured by the next lemma.
Figure (ref) displays the (asymptotic) attainable region. The Pareto frontier between these measures the fundamental tradeoffs between experiment length and regret across the population. The tradeoff between the two metrics is surprisingly mild, reflected in the nearly rectangular shape of the feasible region. Varying the exploiting rate (or coin bias) in top-two Thompson sampling provides one way to trace the Pareto frontier. This can be done either by adjusting the fixed coin bias, as in russo2020simple, or applying (ref) for a length-regret objective (ref) and varying the parameter $c>0$. Appendix (ref) provides details on how to plot the attainable region and Pareto frontier. More specifically, refer to Proposition (ref).
Theoretical results give some insights into the somewhat benign tradeoff between length and regret and the nearly rectangular shape of the feasible region. Denote the minimal attainable (normalized) length and regret by \[ L^*_{\bm{\theta}} \triangleq \inf\{L : (L,R) \in \mathcal{F}_{\bm{\theta}} \} \qquad \text{and} \qquad R^*_{\bm{\theta}} \triangleq \inf\{R : (L,R) \in \mathcal{F}_{\bm{\theta}} \}. \] On Figure (ref), $L^*_{\bm{\theta}}$ is the leftmost boundary of the feasible region, and $R^*_{\bm{\theta}}$ is the bottom boundary. The next lemma shows that approaching minimal regret requires infinite normalized length. Intuitively, stopping and committing to deploy a treatment always leads to some degradation in expected treatment quality, since it forgoes the possibility of adapting based on future information.
The next proposition reveals that the price of early commitment is mild. For instance applying this result at $\beta = 0.9$ shows that a 10% increase in normalized regret is associated with an enormous reduction in normalized length --- from the infinite value in Lemma (ref) to a finite one. Plugging in $\beta = 1/2$ shows that it is possible to run an experiment that is no more than twice as long as the shortest possible and incurs regret no more than twice as large as the minimal.
Our proofs go further, and also reveal which algorithms attain the point $\left(L^{(\beta)}_{\bm{\theta}}, R^{(\beta)}_{\bm{\theta}}\right)$. Algorithm (ref) will attain that point if applied with an allocation rule under which the empirical allocation converges strongly to the proportions $\bm{p}^{\beta}$ identified in Remark (ref). For example, top-two Thompson sampling with fair coin (bias $h_t=1/2$) simultaneously incurs regret no more than $2R^*_{\bm{\theta}}$ and length no more than $2L^*_{\bm{\theta}}$ for $\bm{\theta}\in \widetilde{\Theta}$. This follows from Lemma (ref), given in Appendix (ref), together with shang2020fixed.
A segment of the literature focuses on establishing almost sure convergence of ${\bm p}_{t}$ to ${\bm p^*}$. Unfortunately, almost sure convergence does not guarantee any reasonable scaling of total expected costs.
We define a custom notion of convergence for random variables which rules out the degenerate behavior in the example above. To understand this, it is helpful to start with the usual definition of almost sure convergence. For a sequence of random variables $\{X_\ell\}_{\ell\in\mathbb{N}_1}$ on a probability space $(\Omega, \mathcal{F}, \mathbb{P})$, we say $X_\ell \to x$ almost surely if \[ \mathbb{P}\left( \omega : \lim_{\ell\to\infty} X_\ell(\omega) =x \right)=1. \] That is, with probability 1, for any $\epsilon>0$ there exists $L(\omega)<\infty$ such that $|X_{\ell}(\omega) - x| \leqslant \epsilon$ holds for every $\ell\geqslant L(\omega)$. Eventually, after the random amount of time $L$, the random variables $X_\ell$ stay in the neighborhood of $x$. The issue in Example (ref) was that the expected time one needs to wait could be infinite (that is, one could have $\mathbb{E}\left[L\right]=\infty$). To bound quantities like the expected stopping time of our algorithms, we rely on the following stronger notion of convergence.
Let the space $\mathcal{L}^1$ consist of all measurable random variables $L$ with $\mathbb{E}[|L| ] <\infty$.
This section generalizes insights derived in the Gaussian case. The Lai-Robbins formula in Theorem (ref) holds without modification. Again, the optimal allocation of experimental effort is mostly determined by a purely statistical information-balance constraint. A scalar variable, the long-run exploitation rate is what must vary depending on the experimenter's goal (i.e. the cost functions). The substantial change is that the $Z$-statistics used in the Gaussian case need to be replaced with a more subtle notion of statistical separation between reward distributions.
To address problems in which rewards are drawn from general one-dimensional exponential family distributions, we slightly modify Algorithm (ref). Rather than stop when certain $Z$-statistics are uniformly large, as in Algorithm (ref), under Algorithm (ref) the experimenter stops when Chernoff-information statistics are uniformly large. The form of this stopping rule is the same as a generalized likelihood ratio statistic rule used in chernoff1959sequential, chan2006sequential, with a threshold that is derived based on Kaufmann2021martingale.
We define a weighted version of the Chernoff information between, a fundamental quantity in the theory of hypothesis testing cover2006elements which as appeared previously in the pure exploration literature garivier2016optimal,russo2020simple. Consider an instance $\bm{\theta}$ and its two entries $\theta_i \geqslant \theta_j$. For any weights $p_{i},p_j\geqslant0$, define
where the weighted average
is the unique minimizer to (ref) if $\max\{p_i,p_j\} > 0$. We let $\bar{\theta}_{i,j}\triangleq \theta_j$ if $p_i=p_j=0$.
This weighted version of the Chernoff information measures the strength of evidence distinguishing $\theta_{i}$ and $\theta_j$ under the weights $p_{i}$ and $p_j$. It is hardest to rule out the alternative state of nature with both arms $i$ and $j$ having mean $\bar{\theta}_{i,j} \in [\theta_j, \theta_{i}]$.
The subsection generalizes Theorem (ref) to one-dimensional exponential family distributions. Again we show The information balance condition introduced in (ref) below generalizes the one for Gaussian distributions in (ref). As before, this purely statistical constraint largely determines the optimal limiting proportions ${\bm p}^*$. For any fixed exploitation rate $\beta\in[0,1]$, information balance condition (ref) uniquely determines the residual exploration rates $\left(p_j^{(\beta)}\right)_{j\neq I^*}\in \mathbb{R}^{k-1}$. Optimal performance requires adjusting the exploitation rate $\beta$ based on the within-experiment cost functions so that (cost-aware) exploitation rate condition (ref) holds. Denote the optimal exploitation rate by $\beta^*$, and then the optimal limitation proportions $\bm{p}^* = (p^*_1,\ldots,p^*_k)$ has entries: $p^*_{I^*} = \beta^*$ and $p^*_{j} = p_{j}^{(\beta^*)}$ for any $j\neq I^*$.
Given the developments above, it is not hard to directly construct a universally efficient allocation rule. In Appendix (ref), we do this by building on the tracking algorithm of garivier2016optimal; see Algorithm (ref) there. Essentially, we use a number of samples that grows slowly in the population size to estimate $\bm{\theta}$, solve for the optimal long-run proportions assuming our estimate were correct, and allocate all future measurements according to this. Similar ideas date back as far as the work of chernoff1959sequential.
It is not difficult to generalize top-two Thompson sampling to non-Gaussian reward distributions. The original paper russo2020simple studied the algorithm under exponential family distributions (with general priors) and showed that its long-run measurement proportions satisfy information balance condition. However, two gaps in the existing literature prevent us from easily establishing that asymptotic efficiency in our model:
The next result confirms that the result in Theorem (ref) holds even for non-Gaussian distributions.
As discussed in the literature review, the analysis leading to our results in Theorems (ref) and (ref) builds on an approach that dates back to chernoff1959sequential. We introduce a two-player zero-sum game whose equilibrium characterizes both the limits of attainable costs and the nature of universally asymptotically efficient policies. We call this game the Skeptic's Standoff. This two-player, zero-sum, simultaneous-move game occurs between an experimenter and a skeptic. The experimenter believes $\bm{\theta}= (\theta_1,\ldots,\theta_k)\in\Theta$ is the true state of nature, and tries to gather convincing evidence that $I^*(\bm{\theta})$ is the unique optimal treatment arm by choosing proportional allocation of measurement effort $\bm{p}=(p_1,\ldots,p_k)\in\Sigma_k$; here $\Sigma_k$ denotes the $(k-1)$ dimensional probability simplex. The skeptic picks some alternative state of nature $\bm{\vartheta}=(\vartheta_1,\ldots,\vartheta_k)$ under which a different arm can be optimal. Specifically, the skeptic chooses from the set \[ \overline{\rm Alt}(\bm{\theta}) \triangleq {\rm Closure}\left({\rm Alt}(\bm{\theta})\right), \quad\text{where}\quad {\rm Alt}(\bm{\theta})\triangleq\{\bm{\vartheta}\in \Theta \,:\, I^*(\bm{\vartheta}) \neq I^*(\bm{\theta})\} \] is the set of parameters under which $I^*(\bm{\theta})$, the optimal arm under $\bm{\theta}$, is suboptimal; the closure $\overline{\rm Alt}(\bm{\theta})$ also includes the parameters with multiple optimal arms with $I^*(\bm{\theta})$ being one of them. Since $I^*(\bm{\theta})$ is the unique optimal arm, it must be strictly optimal, so $\bm{\theta}\notin \overline{\rm Alt}(\bm{\theta})$.
Roughly speaking, the experimenter hopes to gather evidence that rules out whatever alternative the skeptic raises, and hopes to do so cheaply. Define the payoff function for the experimenter as
Since the game is zero-sum, $-\Gamma_{\bm{\theta}}(\bm{p},\bm{\vartheta})$ is the payoff function for the skeptic. The denominator in (ref) measures the average per-period cost the experimenter incurs during experimentation, while the numerator measures the average amount of discriminative information acquired against the skeptic's alternative. The payoff function measures bits of discriminative information acquired per unit cost.
To seek a Nash equilibrium of this game, we allow the skeptic to play a mixed strategy $\bm{q}\in \mathcal{D}\left( \overline{\rm Alt}({\bm \theta}) \right)$, where $\mathcal{D}\left( \overline{\rm Alt}({\bm \theta}) \right)$ denotes the set of distribution over the set of alternative states of nature $\overline{\rm Alt}({\bm \theta})$. We overload the definition of the payoff function to \[ \Gamma_{\bm{\theta}}( {\bm p} , {\bm q} ) = \mathbb{E}_{\bm{\vartheta}\sim \bm{q} }\left[ \Gamma_{\bm{\theta}}(\bm{p},\bm{\vartheta})\right]. \] A pair of strategies $(\widetilde{\bm p}, \widetilde{\bm q})\in\Sigma_k\times \mathcal{D}\left( \overline{\rm Alt}({\bm \theta}) \right)$ forms an equilibrium if it satisfies \[ \inf_{\bm{q}\in \mathcal{D}\left(\overline{\rm Alt}(\bm{\theta})\right)}\Gamma_{\bm{\theta}}(\widetilde{\bm p}, \bm{q}) =\Gamma_{\bm{\theta}}(\widetilde{\bm p}, \widetilde{\bm q}) =\sup_{\bm{p}\in\Sigma_k}\Gamma_{\bm{\theta}}(\bm{p},\widetilde{\bm q}). \]
\paragraph{Skeptic's strategy over hard alternative states of nature.} We introduce a specific mixed strategy $\bm{q}^*$, which is shown to be the skeptic's unique equilibrium strategy. See Theorem (ref), which will be presented shortly. The mixed strategy $\bm{q}^*$ is supported on $(k-1)$ alternative states of nature $\{\bm{\vartheta}^{*j}\}_{j\neq I^*}\subset\overline{\rm{Alt}}(\bm{\theta})$, where $I^*=I^*(\bm{\theta})$ is the optiaml arm under $\bm{\theta}$. The $j$-th alternative $\bm{\vartheta}^{*j}=(\vartheta^{*j}_1,\ldots,\vartheta^{*j}_k)$ satisfies
where $\bar{\theta}^*_{I^*,j}=\frac{p^*_{I^*}\theta_{I^*}+p_j^* \theta_j}{p^*_{I^*}+p^*_j}$ is the weighted average of $\theta_{I^*}$ and $\theta_j$ with respect to the unique probability vector $\bm{p}^*$ satisfying information balance condition (ref) and (cost-aware) exploitation rate condition (ref). Under the alternative $\bm{\vartheta}^{*j}$, it is hard for the experimenter to distinguish the treatment arms $I^*$ and $j$. The probability of playing these alternatives $\bm{\vartheta}^{*j}$ is
the RHS equals the $j$-th term of the optimal scaling in Lai-Robbin-type formula in Theorem (ref).
Now we formally present Theorem (ref), which identifies the unique equilibrium strategies $({\bm p}^*, {\bm q}^*)$ and the equilibrium value to the Skeptic's Standoff game.
Theorem (ref) provides a new interpretation of some of our most important results. Since the experimenter's unique equilibrium strategy in the game corresponds to the optimal long-run sampling proportions $\bm{p}^*$ identified in Theorem (ref), we can restate Theorem (ref) as follows.
Theorem (ref) also shows that the equilibrium value of the game is equal to the Lai-Robbins-style formula in Theorem (ref), so we can reinterpret Theorem (ref) as follows.
Our analysis in the appendix starts with the proof of Theorem (ref) and subsequently proves these restated results of Theorems (ref) and (ref). The alternative presentation in the main paper is meant to allow a reader to understand the conceptual takeaways without digesting the two-player game.
\paragraph{Novelty in the equilibrium analysis.} A lot of the core insights in the paper follow from the explicit characterization of the equilibrium above. Relative to the literature, one uncommon feature is that we also characterize the skeptic's equilibrium strategy ${\bm q}^*$. A more common approach in the best-arm identification literature only allows the skeptic to play pure strategies garivier2016optimal, in which case no equilibrium exists. Subsequent papers degenne2019MultipleCorrectAnswers, degenne2019Non-Asymptotic, degenne2020structure adopt a similar game-theoretic view as ours, but do not characterize ${\bm q}^*$. Identifying the skeptic's equilibrium strategy ${\bm q}^*$ is crucial to overcoming technical challenges in proving our lower bound (see Remark (ref) in Appendix (ref)) and to deriving the form of the equilibrium value in Theorem (ref), which ties the connection to a famous formula of lai1985asymptotically.
This paper offers a model and analysis that unifies and generalizes two strands of the multi-armed bandit literature: pure regret minimization problems in the style of lai1985asymptotically and (fixed-confidence) best-arm identification problems in the style of garivier2016optimal. Beyond the unification, the theory seems to offer interesting insights about the nature of asymptotically efficient policies and the tradeoffs between experiment length and total regret. It would be interesting to generalize the asymptotic results to multi-parameter exponential family distributions, and to relax the conditions needed to analyze top-two sampling algorithms. In addition, there is lots of room to design algorithms with desirable finite-time performance in this problem.
\singlespacing { {2pt plus 0.4ex} }