The exact contents of citations.db main_text.text for this paper — one flattened LaTeX string, title through conclusion, appendix excluded, unmodified except for removing email addresses. This is what our citation measures are computed over.
102,425 characters
Optimizing Adaptive Experiments: A Unified Approach to Regret Minimization and Best-Arm Identification
\title{Optimizing Adaptive Experiments: A Unified Approach to Regret Minimization and Best-Arm Identification}
\author{Chao Qin and Daniel Russo}
\affil{Columbia University}
\pdfoutput=1
\maketitle
\onehalfspacing
\begin{abstract}
Practitioners conducting adaptive experiments often encounter two competing priorities: maximizing total welfare (or `reward') through effective treatment assignment and swiftly concluding experiments to implement population-wide treatments. Current literature addresses these priorities separately, with regret minimization studies focusing on the former and best-arm identification research on the latter. This paper bridges this divide by proposing a unified model that simultaneously accounts for within-experiment performance and post-experiment outcomes. We provide a sharp theory of optimal performance in large populations that not only unifies canonical results in the literature but also uncovers novel insights. Our theory reveals that familiar algorithms, such as the recently proposed top-two Thompson sampling algorithm, can optimize a broad class of objectives if a single scalar parameter is appropriately adjusted. In addition, we demonstrate that substantial reductions in experiment duration can often be achieved with minimal impact on both within-experiment and post-experiment regret.
\end{abstract}
\section{Introduction}
A vast body of research on the multi-armed bandit (MAB) problem studies effective adaptive experimentation \citep{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 \citep{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 \citep{bubeck2009pure,villar2015multi}; this is true of the Thompson sampling \citep{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 \citet{lai1985asymptotically} established sharp asymptotic lower bounds on the expected regret of any policy. Similarly, for best-arm identification, \citet{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.
\subsection{Contributions}\label{subsec:contributions}
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 \citep{hong2021review}, they may reflect the differentiated time required to simulate the performance of certain arms to the desired accuracy \citep{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:
\begin{enumerate}
\item {\bf Unification of canonical theory:} Our findings generalize and unify canonical results in the literature. When the cost functions, both within-experiment and post-experiment, are measured almost exclusively by the regret of treatment assignment, our objective aligns with that of \cite{lai1985asymptotically}. Our theory recovers their famous formula for optimal regret and the optimal division of experimentation effort among the arms. Another special case of our model sets the within-experiment cost of each arm to be the same. In this case, our results recover the sharp theory of optimal best-arm identification presented by \citet{garivier2016optimal}. This unification is noteworthy, given that the formulation of \cite{garivier2016optimal} appears quite different from that of \cite{lai1985asymptotically}, as do various mathematical expressions.
\item {\bf The Pareto frontier between experiment length and total regret:} Section \ref{subsec:frontier} discusses our theory's application in characterizing the inherent tradeoffs between the expected length of an adaptive experiment and the total regret incurred. The latter measures the cumulative suboptimality of assigned treatments across the whole population, including both within- and post-experiment treatments. Optimal multi-armed bandit algorithms minimize regret (or, equivalently, maximize welfare) by engaging in adaptive, sequential treatment assignments throughout the entire population. Our theory reveals that significant reductions in experiment duration can be achieved with negligible impact on cumulative regret. In regimes where the tradeoff is more substantial, we provide an exact characterization of the Pareto frontier and complement it with interpretable bounds (Proposition~\ref{prop:Pareto_robustness}).
\item {\bf Implications for popular bandit algorithms:} Our theory suggests that small, careful adjustments to leading bandit algorithms are sufficient to optimize adaptive experimentation in very large populations. We illustrate this through the top-two Thompson sampling algorithm, a modification of Thompson sampling proposed by \citet{russo2016simple,russo2020simple}. Adjusting a single tuning parameter in this algorithm is enough to attain any point on the Pareto frontier between experiment length and total regret. More surprisingly, adjusting this parameter is sufficient (asymptotically) to optimize any one of our generalized objectives. We also provide a method to apply this algorithm without tuning.
\item {\bf Insights into the nature of asymptotically efficient policies:} The surprising results about top-two Thompson sampling serve to illustrate a more general insight into the optimal allocation of experimental effort. We demonstrate that the nature of asymptotically efficient policies is nearly independent of the per-period cost functions. To articulate this precisely, we differentiate two aspects of algorithm design: the choice of an 'exploitation rate,' which determines the fraction of experimentation effort dedicated to the true best arm, and the intelligent division of exploration effort among the other arms. The optimal division of exploration effort turns out to be completely independent of the cost functions. Instead, it is determined by a certain information-balance property, which asserts that the strength of statistical evidence against the optimality of suboptimal alternatives should grow at an equal rate. Leading bandit algorithms like Thompson sampling attain this property ‘automatically.’ Because information balance is a purely statistical property, tailoring experimentation to specific cost considerations is reduced to an appropriate choice of exploitation rate.
\end{enumerate}
\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 \cite{chernoff1959sequential} or \cite{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.
\section{Numerical teaser}\label{sec:teaser}
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{sec:formulation} and implementation details of the experiments are discussed in Appendix \ref{app:implementation details}.
\paragraph{Policies compared.}
We compare two ways of adaptively selecting treatment arms within an experiment.
\begin{enumerate}
\item \emph{Epsilon-Greedy:} At any round within the experiment, the experimenter identifies the arm with the highest empirical-average reward so far. It plays that arm with probability $1-\epsilon$, exhibiting 'greedy' behavior. With probability $\epsilon$, it 'explores' by selecting an arm uniformly at random. The parameter $\epsilon$ thus balances exploitation of the current best arm with exploration of potentially better arms.
\item \emph{Top-two Thompson sampling (Top-two TS):} Thompson sampling (TS) is a prominent bandit algorithm that is widely used in industry and academia. The algorithm maintains a posterior beliefs over the true mean reward of each arm. At decision-time, an arm to play is sampled randomly according the posterior probability an arm offers the highest true mean. Top-two TS \citep{russo2016simple} modifies TS to explore more aggressively within an experiment. To select an arm, it first runs standard TS until two distinct arms are sampled. The first arm, called the leader, tends to concentrate on whichever arm is believed to be best. The second, called the challenger, samples an arm that may plausibly outperform the leader. Applied with tuning parameter $\beta \in (0,1)$, the algorithm plays the leader with probability $\beta$ and the challenger with probability $1-\beta$. If $\beta = 1$, top-two TS is standard TS. If one does not want to tune $\beta$, Section \ref{subsec:ttts} provides a more automatic way to tailor top-two TS to a specific objective.
\end{enumerate}
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{sec:main-Gaussian} implies this stopping rule is enough to attain a sharp asymptotic efficiency results.
\begin{figure}[!htbp]
\centering
\begin{subfigure}[t]{0.9\textwidth}
\centering
\includegraphics[width=4in]{fig/TTTS_teaser.pdf}
\caption{The set of length-regret outcomes attained for various exploitation-rate parameters (given by $\beta$ for top-two TS or $1-\epsilon+\frac{\epsilon}{k}$ for Epsilon-Greedy). The Pareto frontier (among all policies) predicted by our asymptotic theory is plotted in green.}
\label{fig:teaser_pareto}
\end{subfigure}
\vspace{1em}
\begin{subfigure}[t]{0.9\textwidth}
\centering
\includegraphics[width=6in]{fig/play_counts.pdf}
\caption{Within-experiment distribution of treatment arm allocations of top-two TS with $\beta=0.7$ and Epsilon-Greedy with $\epsilon=0.4$. The exploitation rate is largely determined by the tuning parameters ($\beta,\epsilon)$. Epsilon-Greedy distributes samples equally among suboptimal arms whereas top-two Thompson sampling shifts most samples to more competitive arms.}
\label{fig:teaser_play_counts}
\end{subfigure}
\caption{Numerical performance of policies on the six arm instance $\bm{\theta}=(\theta_1,\theta_2,\theta_3,\theta_4,\theta_5,\theta_6)=(0,0.2,0.4,0.6,0.8,1)$ with population size $n=10^8$.}
\label{fig:teaser_combined}
\end{figure}
\paragraph{Findings and observations.}
Figure \ref{fig:teaser_combined} compares the performance of these policies empirically. We make several observations:
\begin{enumerate}
\item \emph{Dominance of top-two TS over Epsilon-Greedy:} Figure \ref{fig:teaser_pareto} shows that relative to Epsilon-Greedy, top-two TS results in \emph{both} substantially shorter experiments and a large reduction in cumulative regret.
\item \emph{Efficient identification and deprioritization of clearly suboptimal arms:} Figure \ref{fig:teaser_play_counts} illustrates why top-two TS offered superior performance. While Epsilon-Greedy allocates equal probability to all non-greedy arm choices, top-two TS strategically shifts measurement away from arms that are clearly inferior and toward arms that have a plausible chance of being optimal.
\item \emph{Low price of reducing experiment duration:} Standard Thompson sampling is analogous to top-two TS with extremely large exploitation rate parameter $\beta \approx 1$. By reducing $\beta$ and moving away from this standard algorithm, it is possible to massively reduce experiment length while having a negligible impact on the overall quality of treatment decisions (cumulative regret).
\end{enumerate}
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.
\section{Literature review}
Many papers have provided guarantees on both within-experiment and post-experiment performance in models of adaptive experimentation. Ours is unique in providing a \emph{sharp} theory of asymptotic efficiency (Definition~\ref{def:universal-efficiency}) that unifies and generalizes two parts of the canon of the multi-armed bandit literature: pure regret minimization problems in the style of \cite{lai1985asymptotically} and (fixed-confidence) best-arm identification problems in the style of \cite{garivier2016optimal}. An attractive feature of sharp theory, like that of \cite{lai1985asymptotically}, is that it provides a sense in which algorithms such as Thompson sampling or upper confidence bound (UCB) are \emph{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{subsec:contributions}.
Our analysis builds on foundational insights by \cite{chernoff1959sequential, anantharam1989asymptotically2, rajeev1989asymptotically1} and \cite{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 \cite{chan2006sequential}, \citet{bui2011committing}, \cite{jamieson2014lilUCB}, \cite{degenne2019bridging}, and \cite{zhang2023fast}, which allow for adaptive stopping and study both within-experiment regret and post-experiment decision quality. Similar to our length-regret objectives, \cite{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. \cite{jamieson2014lilUCB} and \cite{degenne2019bridging} study upper confidence bound algorithms that can ensure that the optimal treatment arm is selected with high probability. \cite{degenne2019bridging} carefully studies how varying tuning parameters trades off regret and probability of incorrect selection, whereas \cite{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 \citet{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 \cite{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, \cite{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 \cite{lai1985asymptotically} and accommodating them introduces challenges in the analysis.\footnote{See Remark \ref{rem:lower_bound_proof} for comments on how the first change impacts the lower bound proof. In terms of modeling, our link to \cite{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, \cite{kanarios2024cost} study a model similar to that of \cite{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{subsec:contributions}.
Many other works study problems in which the experimenter must stop at a pre-determined time. In these settings, \cite{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 \cite{glynn2004large} used large deviation theory to study optimal static allocations, providing a new perspective on so-called optimal computing budget allocation \citep{chen2000simulation}. Implementing the ideal allocation in \cite{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 \cite{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 \citep{qin2022open,ariu2021policy,degenne2023existence}.
A third kind of asymptotic theory looks at the rate of concentration of a Bayesian posterior distribution as information is acquired.
\cite{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 \cite{garivier2016optimal}, whose work appeared in the same conference. Later papers by \cite{qin2017improving} and \cite{shang2020fixed} provided guarantees for these top-two sampling algorithms in the same setting as \cite{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{subsec:ttts} to give insight into the asymptotic efficiency of top-two Thompson sampling for our generalized problem formulation. The exploration sampling algorithm of \cite{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 \citep{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 \citep{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 \citep{chick2009economic, chick2012sequential, chick2021bayesian}. Additionally, \citet{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 \cite{bhat2020near, zhao2023adaptive, dai2023clipogd} and references therein for recent work along these lines.
Interesting work of \cite{adusumilli2022neyman} observes that adaptive experiments for treatment effect estimation are also ideal for identifying the best arm, \emph{if there are just two treatment arms.}
When there are many arms, as in \cite{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).
\section{Problem formulation}\label{sec:formulation}
An adaptive experiment is conducted to select a single treatment arm to deploy to a target population of $n$ individuals, among $k$ options.
The \emph{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:
\begin{itemize}
\item If the experimenter chooses to continue experimenting, they select a treatment arm $I_{t}\in[k]$ and observe the associated outcome $Y_{t,I_t}$.
\item If the experimenter chooses to stop the experiment after observing treatment outcomes for $t$ individuals, they set the stopping time $\tau=t$ and choose an arm $\hat{I}_{\tau}$ to deploy to the remaining individuals throughout timesteps $\{\tau, \ldots, n-1\}$. In other words, they commit irrevocably to select $I_{\ell} = \hat{I}_{\tau}$ for each $\ell \in \{\tau, \ldots, n-1\}$, yielding the treatment outcomes $\left\{Y_{\tau, \hat{I}_\tau}, \ldots, Y_{n-1, \hat{I}_\tau}\right\}$.
\end{itemize}
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 \emph{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{subsec:lenght-regret-objectives} and~\ref{subsec:general-objectives}.
\subsection{Restrictions on outcome distributions}
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 \cite[Chapter 1]{efron2022exponential} or \cite[Section 4]{cappe2013kullback} for background. Formally, we study outcome distributions that assign to any subset of outcomes $\mathcal{Y} \subset \mathbb{R}$ the probability
\begin{equation}
\label{eq:exponential-family}
P( \mathcal{Y} \mid \theta ) = \int_{\mathcal{Y}} \exp\left(\eta(\theta) y - b(\theta)\right)\rho(\mathrm{d}y).
\end{equation}
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})$.
\subsection{Length-regret objectives}\label{subsec:lenght-regret-objectives}
This subsection introduces an important special case of our model. For any $\bm{\theta}\in\Theta$ and $c \geqslant 0$, the overall cost function
\begin{equation}\label{eq:length-regret-objective}
\mathrm{Cost}_{\bm{\theta}}(n, \pi) = c\cdot \mathrm{Length}_{\bm{\theta}}(n, \pi) + \mathrm{Regret}_{\bm{\theta}}(n, \pi)
\end{equation}
assesses a policy's performance through the regret incurred and experimentation time required, defined as
\begin{align*}
\mathrm{Length}_{\bm{\theta}}(n, \pi) \triangleq \mathbb{E}_{\bm{\theta}}^{\pi}[\tau]
\quad \text{and}\quad
\mathrm{Regret}_{\bm{\theta}}(n, \pi) \triangleq&\, \mathbb{E}_{\bm{\theta}}^{\pi}\left[ \sum_{t=0}^{n-1} \left(\theta_{I^*} - \theta_{I_t}\right)\right]\\
=&\, \mathbb{E}_{\bm{\theta}}^{\pi}\left[ \sum_{t=0}^{\tau-1} \left(\theta_{I^*} - \theta_{I_t}\right) + (n-\tau)\left(\theta_{I^*} - \theta_{\hat{I}_{\tau}} \right)\right].
\end{align*}
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 \eqref{eq:length-regret-objective} 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{alg:ttts}) for a range of different $c$'s and select a value that best aligns with their goals.
\subsection{Generalized objectives}\label{subsec:general-objectives}
We now introduce a general class of objective functions, of which the length-regret objectives in Section \ref{subsec:lenght-regret-objectives} 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
\begin{equation}\label{eq:general-objective}
\mathrm{Cost}_{\bm{\theta}}(n, \pi) \triangleq \mathbb{E}_{\bm{\theta}}^{\pi}\left[ \sum_{t=0}^{\tau-1}C_{I_t}(\bm{\theta}) + (n-\tau)\Delta_{\hat{I}_\tau}(\bm{\theta}) \right],
\end{equation}
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.
\begin{example}[Best-arm identification with differentiated sampling costs]
Consider $\bm{\theta}\in\Theta$. For any $i\in[k]$, let $C_{i}(\bm{\theta}) =c_i$ be an arm specific cost independent of the unknown parameter~$\bm{\theta}$,
and $\Delta_{i}(\bm{\theta}) = \mathbb{1}(I^*\neq i)$ be an indicator of incorrect selection where $I^* = I^*(\bm{\theta})$. Then
\[
\mathrm{Cost}_{\bm{\theta}}(n,\pi) = \mathbb{E}^{\pi}_{\bm{\theta}}\left[\sum_{t=0}^{\tau-1} c_{I_t} + (n-\tau)\mathbb{1}\left(\hat{I}_{\tau}\neq I^*\right) \right].
\]
It will be clear in our theory that efficient policies stop in time $\tau=\tau(n)$ that is just logarithmic in the population size $n$ for optimal policies, so minimizing $\mathrm{Cost}_{\bm{\theta}}(n,\pi)$ is asymptotically equivalent to minimizing
\[
\mathbb{E}^{\pi}_{\bm{\theta}}\left[\sum_{t=0}^{\tau-1} c_{I_t} + n\cdot \mathbb{1}\left(\hat{I}_{\tau}\neq I^*\right) \right].
\]
When all $c_i$'s are equal, this is the Lagrangian form of the ``fixed-confidence'' best-arm identification problem \citep{kaufmann2016complexity}.
The terms $(c_1, \ldots, c_k)$ might capture the time required to simulate the performance of an arm using a stochastic simulator \citep{chick2001new}. By picking $n$ to be very large, this formulation captures the problem of minimizing average simulation time required to select the optimal alternative.
\end{example}
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$.
\begin{assumption}
\label{asm:post-experimentation cost}
For any $\bm{\theta}\in\Theta$, zero post-experiment cost is incurred if and only if the best treatment arm is deployed to the population, i.e.,
\[
\Delta_{I^*}(\bm{\theta})=0 \quad\text{and}\quad \Delta_{j}(\bm{\theta})>0, \quad \forall j\neq I^*.
\]
\end{assumption}
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.
\begin{assumption}
\label{asm:sampling cost}
For any $\bm{\theta}\in\Theta$, there is a strictly positive cost to continuing to experiment with any treatment arm, i.e.,
\[
C_{\min}(\bm{\theta})\triangleq \min_{i\in[k]} C_{i}(\bm{\theta})>0.
\]
In addition, for any arm $i\in[k]$,
$C_i(\cdot)$ is continuous at~$\bm{\theta}\in\Theta$.
\end{assumption}
\subsection{Large population asymptotics}
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$,
\begin{equation}
\label{eq:universally efficient rule_initial}
\sup_{\bm{\theta} \in \Theta} \, \limsup_{n\to \infty} \frac{\mathrm{Cost}_{\bm{\theta}}(n, \pi^*)}{\mathrm{Cost}_{\bm{\theta}}(n, \pi)} \leqslant 1.
\end{equation}
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 \cite{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{thm:Lai-Robbins-type formula_general}), we will construct policies whose costs scale with $\ln(n)$, i.e. just logarithmically in the population size. Therefore, following \cite{lai1985asymptotically} and Definition 16.1 in \cite{lattimore2020bandit}, we say a policy is \emph{consistent} if its total cost never scales \emph{exponentially faster} than $\ln(n)$.
\begin{definition}[Consistent policy]
\label{def:uniformly good rule}
A policy $\pi$ is said to be consistent if
\begin{equation}
\label{eq:uniformly good rule}
\forall \bm{\theta}\in\Theta:\quad
\lim_{n\to \infty} \frac{\ln\left(\mathrm{Cost}_{\bm{\theta}}(n, \pi )\right)}{\ln(n)} = 0.
\end{equation}
Let $\Pi$ be the set of all consistent policies.
\end{definition}
Within the broad class of consistent policies, we seek one which is universally efficient.
\begin{definition}[Universally efficient policy]
\label{def:universal-efficiency}
A policy $\pi^*$ is universally efficient if for any other consistent policy $\pi \in \Pi$,
\begin{equation}
\label{eq:universally efficient rule}
\sup_{\bm{\theta} \in \Theta} \limsup_{n\to \infty} \frac{\mathrm{Cost}_{\bm{\theta}}(n, \pi^*)}{\mathrm{Cost}_{\bm{\theta}}(n, \pi)} \leqslant 1.
\end{equation}
\end{definition}
Note that it is easy to show that a policy $\pi^*$ must also be consistent if it satisfies \eqref{eq:universally efficient rule}.
\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$.
\begin{lemma}
\label{lem:cost-scaling}
Consider a policy $\pi^*$ that satisfies
\begin{equation}
\label{eq:cost-scaling}
\forall\bm{\theta}\in \Theta: \quad \mathrm{Cost}_{\bm{\theta}}(n, \pi^* )\sim \kappa_{\bm{\theta}} \times \ln(n),
\quad\text{where}\quad \kappa_{\bm{\theta}}>0.
\end{equation}
It is universally efficient if and only if, every other consistent policy $\pi \in \Pi$ satisfies the following lower bound:
\[
\forall\bm{\theta}\in \Theta: \quad \liminf_{n\to \infty} \frac{\mathrm{Cost}_{\bm{\theta}}(n, \pi ) }{\ln(n)} \geqslant \kappa_{\bm{\theta}}.
\]
\end{lemma}
\section{Main Results, specialized to the Gaussian setting}\label{sec:main-Gaussian}
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{subsec:info_balace_gaussian} and~\ref{subsec:ttts} establish the insights into the nature of asymptotically efficient policies. Section~\ref{subsec:frontier} studies the Pareto frontier between regret and experiment length, and Section~\ref{subsec:lai_robbins_gaussian} provides a formula for optimal scaling of total cost that connects to a famous result of \cite{lai1985asymptotically}.
\subsection{An algorithm template}
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
\begin{equation}\label{eq:posterior}
m_{t,i} \triangleq \frac{\sum_{\ell=0}^{t-1} \mathbb{1}(I_\ell=i) Y_{\ell,i}}{N_{t,i}} \quad \text{and} \quad s_{t,i} \triangleq \frac{\sigma}{ \sqrt{N_{t,i}} }.
\end{equation}
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
\begin{equation}\label{eq:z-stats}
Z_{t,i,j} \triangleq \frac{ m_{t,i} - m_{t,j} }{ \sqrt{ s_{t,i}^2 + s_{t,j}^2 } } = \frac{ m_{t,i} - m_{t,j} }{ \sqrt{\sigma^2/N_{t,i} + \sigma^2/N_{t,j} } }
\end{equation}
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{alg:general-template-gaussian} 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$,
\begin{equation}
\label{eq:tight threshold T}
\gamma_t(n) \triangleq \ln(n) + \ln(k-1) + 6\ln\left(\frac{\ln(n)+\ln(k-1)}{2}+2\right) + 6\ln\left(\ln\left(\frac{t}{2}\right)+1\right) + 14.
\end{equation}
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.
\begin{algorithm}[H]
\centering
\caption{General template for Gaussian distributions}\label{alg:general-template-gaussian}
\begin{algorithmic}[1]
\State{\bf Input:} $\mathtt{AllocationRule}(\cdot)$, a function which takes an input a history $\mathcal{H}_t$ of arbitrary length and returns a probability distribution over $[k]$.
\State {\bf Initialize:} $\mathcal{H}_0 \gets \{ \}$, $\tau=n$.
\For{$t=0,1,\ldots, n-1$}
\If{$t < \tau$}
\LineComment{\emph{\textcolor{blue}{If experimentation has not yet stopped, ...}}}
\State Obtain $\hat{I}_t \in \operatorname*{arg\,max}_{i \in [k]} m_{t,i}$ and $\gamma_t(n)$ as in \eqref{eq:tight threshold T}.
\If {$\frac{1}{2}\min_{j\neq \hat{I}_t }Z^2_{t, \hat{I}_{t}, j} \geqslant \gamma_t(n)$}
\LineComment{\emph{\textcolor{blue}{If all $Z$-statistics are large, stop experimenting. }}}
\State Set $\tau=t$ and $\hat{I}_{\tau} \in \operatorname*{arg\,max}_{i \in [k]} m_{\tau,i}$.
\State Assign arm $I_t = \hat{I}_{\tau}$.
\Else
\LineComment{\emph{\textcolor{blue}{Otherwise, continue experimenting using the allocation rule.}}}
\State Assign arm $I_t \sim \mathtt{AllocationRule}(\mathcal{H}_t)$.
\State Observe $Y_{t,I_t}$ and update history $\mathcal{H}_{t+1} \gets \mathcal{H}_t\cup \{(I_t, Y_{t,I_t}) \}$.
\EndIf
\Else
\LineComment{\emph{\textcolor{blue}{If experimentation has stopped, ...}}}
\State Assign arm $I_t = \hat{I}_{\tau}$.
\EndIf
\EndFor
\end{algorithmic}
\end{algorithm}
\begin{remark}[A constraint on the probability of incorrect select]
The threshold $\gamma_{t}(n)$ is adapted from \cite{Kaufmann2021martingale}, and ensures that Algorithm \ref{alg:general-template-gaussian} obeys the following constraint on the probability of incorrect selection:
\begin{equation}\label{eq:pcs_constraint_initial}
\sup_{\bm{\vartheta} \in \Theta} \mathbb{P}_{\bm{\vartheta}}\left( \hat{I}_{\tau} \neq I^*(\bm{\vartheta}) \wedge \tau < n \right) \leqslant \frac{1}{n}.
\end{equation}
See Appendix \ref{app:post-experiment-cost}. However, unlike much of the literature on (fixed-confidence) best-arm identification, we do not impose this as a constraint. In our formulation, the experimenter is free to stop at any time, and it is a surprising consequence of our theory that universally asymptotically efficient rules can be constructed while obeying \eqref{eq:pcs_constraint_initial}. See Remark \ref{rem:lower_bound_proof} in the appendix for discussion of technical challenges in the lower bound proof.
\end{remark}
\subsection{Model for sample path asymptotics of Algorithm \ref{alg:general-template-gaussian}}
For asymptotic analysis of the allocation rule supplied in Algorithm \ref{alg:general-template-gaussian}, 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
\begin{equation}\label{eq:allocaiton-only-sample}
I_t \mid \mathcal{H}_t \sim \mathtt{AllocationRule}(\mathcal{H}_t) \quad \text{where} \quad \mathcal{H}_t = (I_0, Y_{0,I_0}, \ldots, I_{t-1}, Y_{t-1, I_{t-1}}).
\end{equation}
We call the infinite sequence of within-experiment outcomes $(I_t, Y_{t,I_t})_{t\in \mathbb{N}_0}$ an \emph{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
\begin{equation}\label{eq:stopping_time}
\tau = \min\left\{ t \leqslant n \,:\, \min_{j\neq \hat{I}_t }Z_{t, \hat{I}_{t}, j} \geqslant \gamma_t(n) \right\},
\end{equation}
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{alg:general-template-gaussian}. Our lower bound proofs do not use such a construction.
\subsection{Properties of an optimal allocation: information balance with a cost-aware exploitation rate}\label{subsec:info_balace_gaussian}
We offer a sufficient (and almost necessary) condition on allocation rules for Algorithm \ref{alg:general-template-gaussian} 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{subsec:strong-convergence}. Throughout,
we denote the empirical allocation vector by
\begin{equation}
\label{eq:empirical allcoation}
{\bm p}_t = \left(p_{t,1}, \ldots, p_{t,k}\right)
\text{ with }
p_{t,i} \triangleq \frac{N_{t,i}}{t}
\text{ being the fraction of measurements allocated to arm $i\in [k]$.}
\end{equation}
\begin{Theorem}[Optimality condition of allocation rules]
\label{thm:efficient-p-gaussian}
Algorithm~\ref{alg:general-template-gaussian} is universally efficient (Definition \ref{def:universal-efficiency}) if
the allocation rule satisfies the following condition: for any $\bm{\theta}\in\Theta$, under any produced indefinite-allocation sample path~\eqref{eq:allocaiton-only-sample}, the empirical allocation ${\bm p}_t$ converges strongly (Definition \ref{def: strong convergence}) to a unique probability vector $\bm{p}^* = \left(p_1^*,\ldots,p_k^*\right) > \bm{0}$ satisfying the information balance condition
\begin{equation}
\label{eq:info-balance-gaussian}
\frac{ (\theta_{I^*} - \theta_{i})^2}{ \sigma^2/p^*_{I^*} + \sigma^2/p^*_{i}} = \frac{ (\theta_{I^*} - \theta_{j})^2}{ \sigma^2/p^*_{I^*} + \sigma^2/p^*_{j}}, \quad \forall i,j \neq I^*
\end{equation}
and (cost-aware) exploitation rate condition
\begin{equation}
\label{eq:exploitation-rate-gaussian}
p^*_{I^*} = \sqrt{\sum_{j\neq I^*} (p_j^*)^2 \frac{C_j(\bm{\theta})}{C_{I^*}(\bm{\theta})} }.
\end{equation}
By contrast, Algorithm~\ref{alg:general-template-gaussian} is not universally efficient
if there exists $\bm{\theta}\in\Theta$ such that the allocation rule's empirical allocation ${\bm p}_t$ converges strongly to a probability vector other than ${\bm p}^*$.
\end{Theorem}
It is helpful to think of the long-run allocation as having two components: a scalar \emph{exploitation rate} $p^*_{I^*}$ and a vector allocation of residual \emph{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{sec:teaser} -- Figure \ref{fig:teaser_play_counts}. Theorem~\ref{thm:efficient-p-gaussian} reveals the following insight:
\begin{enumerate}
\item The optimal choice of scalar exploitation rate $p^*_{I^*}$ depends on the within-experiment cost functions $(C_i(\bm{\theta}))_{i\in [k]}$.
\item Given an exploitation rate, the vector of exploration rates is uniquely determined by the information balance condition \eqref{eq:info-balance-gaussian}, independently of the cost functions $(C_i(\bm{\theta}), \Delta_i(\bm{\theta}))_{i\in [k]}$.
\end{enumerate}
As the name suggests, one can interpret information balance~\eqref{eq:info-balance-gaussian} as balancing the weight of evidence against suboptimal arms. From the formula for the (squared) $Z$-statistics in \eqref{eq:z-stats}, information balance is easily seen to be equivalent to the property
\begin{equation}\label{eq:Z-growth-rate}
Z_{t,I^*,i}^2 \sim Z_{t, I^*, j}^2, \quad \forall i,j\neq I^*,
\end{equation}
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.
\begin{remark}
Theorem \ref{thm:efficient-p-gaussian} may appear strange. How could optimal long-run behavior depend so little on the within-experiment and post-experiment cost functions? The first observation is that \eqref{eq:Z-growth-rate} itself does not depend on the cost functions and yet nearly determines the optimal proportions ${\bm p}^*$. Intuition for \eqref{eq:Z-growth-rate} can be given through hand-wavy calculations. Under non-adaptive allocation rules\footnote{This first inequality would hold if the allocation rule were not adaptive. \cite{russo2020simple} analyzes adaptive allocations and provides rigorous expressions for posterior probabilities that are of this type. Be careful, however, as purely frequentist large deviations analysis of this type breaks down when allocation rules are adaptive. }, the probability of incorrectly selecting arm $i\neq I^*$ roughly behaves as
\begin{equation}
\mathbb{P}( m_{t,i} \geqslant m_{t, I^*} ) \lessapprox \Phi( - Z_{t,I^*, i}) \approx \exp\left\{ - \frac{Z_{t,I^*, i}^2}{2} \right\}.
\end{equation}
The information balance property in \eqref{eq:Z-growth-rate} roughly translates to the property that $\ln \mathbb{P}( m_{t,i} \geqslant m_{t, I^*} ) \sim \ln \mathbb{P}( m_{t,j} \geqslant m_{t, I^*} )$ for each $i,j \neq I^*$. Correspondingly, information imbalance roughly translates to the event of incorrectly selecting one arm $i$ being exponentially rare relative to the event that arm $j$ is incorrectly chosen:
\begin{equation}\tag{Information-Imbalance}\label{eq:information-imbalence}
\mathbb{P}( m_{t,i} \geqslant m_{t, I^*} ) \lessapprox \exp\{ - \alpha t\} \times \mathbb{P}( m_{t,j} \geqslant m_{t, I^*} )
\end{equation}
for some $\alpha>0$. See \cite{russo2016simple} for Bayesian arguments of this type. Information imbalance is wasteful. If \eqref{eq:information-imbalence} holds, then for large $t$ the experimenter knows that mistakes, if they occur at all, are exponentially more likely to come from arm incorrect selections of $j$ and not $i$. It would be better to shift experimentation effort away from arm $i$ and reallocate it to reducing uncertainty about $j$, roughly rebalancing the information gathered about those two arms.
\end{remark}
We close this section with a remark on linking ${\bm p}^*$ to segments of the literature that study best-arm identification and regret-minimization.
\begin{remark}[Connections to existing allocations]\label{rem:connections} Consider objective in Section \ref{subsec:lenght-regret-objectives}, where
$C_{j}(\bm{\theta}) = c+ (\theta_{I^*} - \theta_j)$. As $c\to \infty$, $\frac{C_j(\bm{\theta})}{C_{I^*}(\bm{\theta})} \to 1$ and the formula for ${\bm p}^*$ recovers the optimal allocation in the best-arm identification literature \citep{kaufmann2016complexity, russo2020simple}.
As $c\to 0$, $\frac{C_j(\bm{\theta})}{C_{I^*}(\bm{\theta})} \to \infty$ and one must have $p_{I^*}^* \to 1$. We observe that information balance condition~\eqref{eq:info-balance-gaussian} requires
\[
\frac{p_{j}^*}{1-p_{I^*}^*} \sim
\frac{(\theta_{I^*} - \theta_{j})^{-2}}{ \sum_{i\neq I^*} (\theta_{I^*} - \theta_{i})^{-2} } \quad \text{as}\quad p_{I^*}^*\to 1.
\]
Suboptimal arms are sampled with frequency inversely-proportional to their squared optimality gap, a defining property of optimal algorithms for regret minimization \citep{lai1985asymptotically, lattimore2020bandit}.
\end{remark}
\begin{remark}[Connections to optimal computing budget allocations]
When $C_{i}(\bm{\theta})=1$ for any $i\in[k]$, the allocation $\bm{p}^*$ matches that derived in the simulation optimization literature by \cite{glynn2004large} as a refinement and justification of \cite{chen2000simulation}. This should be interpreted with caution, however, since the derivation is quite different and the formula does not match in non-Gaussian cases.\footnote{The allocation $\bm{p}^*$ in Theorem~\ref{thm:efficient-p-general} only matches that in \cite{glynn2004large} for Gaussian distributions where the KL divergence is symmetric.} See the literature review for further discussion and open questions in that theory.
\end{remark}
\subsection{A Lai-Robbins-type formula for the optimal cost scaling}\label{subsec:lai_robbins_gaussian}
The pioneering work of \cite{lai1985asymptotically} identified that a policy $\pi$ has asymptotically optimal regret scaling if and only if,
\begin{equation}
\label{eq:lai-robbins-regret} \forall\bm{\theta}\in\Theta:\quad\mathrm{Regret}_{\bm{\theta}}(n, \pi) \sim \sum_{j\neq I^*} \frac{\theta_{I^*} -\theta_j }{ {\rm KL}(\theta_j , \theta_{I^*}) } \times \ln(n) \quad\text{as}\quad n\to \infty.
\end{equation}
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.
\begin{Theorem}[Lai-Robbins-type formula]
\label{thm:Lai-Robbins-type formula}
A policy $\pi$ is universally efficient if and only if,
\begin{equation}
\label{eq:sufficient and necessary condition of universal efficiency Gaussian}
\forall\bm{\theta}\in\Theta:\quad
\mathrm{Cost}_{\bm{\theta}}(n, \pi) \sim \sum_{j\neq I^*} \frac{C_{j}(\bm{\theta}) }{ {\rm KL}(\theta_j , \bar{\theta}^*_{I^*,j}) } \times \ln(n)
\quad\text{as}\quad n\to \infty,
\end{equation}
where $\bar{\theta}^*_{I^*,j} \triangleq \frac{p^*_{I^*}\theta_{I^*}+p_j^* \theta_j}{p^*_{I^*}+p^*_j}$ with $\bm{p}^* = (p_1^*,\ldots,p_k^*)$ identified in Theorem~\ref{thm:efficient-p-gaussian}.
\end{Theorem}
Consider the length-regret objectives in Section \ref{subsec:lenght-regret-objectives}, where $C_{i}(\bm{\theta}) = c+(\theta_{I^*}-\theta_i)$. As $c \to 0$, the objective is equivalent to the regret objective in \cite{lai1985asymptotically}. In that limit, \eqref{eq:sufficient and necessary condition of universal efficiency Gaussian} recovers \eqref{eq:lai-robbins-regret}, since $C_{i}(\bm{\theta}) \to \theta_{I^*}-\theta_i$ and $p^*_{I^*}\to 1$. See also Remark \ref{rem:connections}. Although this expressions look very different, \eqref{eq:sufficient and necessary condition of universal efficiency Gaussian} also matches one from \cite{garivier2016optimal} in best-arm identification problems where $C_{i}(\bm{\theta})=1$. (See Theorem \ref{thm:equilibrium} for simplification of the min-max problem studied in \cite{garivier2016optimal}.)
\subsection{Automatic information balance via top-two Thompson sampling}\label{subsec:ttts}
It is not difficult to engineer a universally efficient allocation rule that mimics the long-run proportions ${\bm p}^*$. See Algorithm \ref{alg:D-Tracking} in Appendix \ref{app:tracking}. Here we demonstrate that, after simple modifications, leading bandit algorithms can also be universally efficient.
We focus on a modification of Thompson sampling (TS) \citep{thompson1933likelihood}, a leading bandit algorithm that is widely used in both academia and industry. Pseudocode for standard TS is presented in Algorithm \ref{alg:ts}. 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 \citep{scott2010modern}. Algorithm \ref{alg:ts} 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{sec:teaser}, Thompson sampling can perform poorly when the length of the experimentation phase is a key consideration (see Section~\ref{subsec:lenght-regret-objectives}). 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{alg:ttts} presents pseudocode for the top-two sampling \citep{russo2020simple} variant of Thompson sampling discussed previously in Section \ref{sec:teaser}. 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.
\begin{figure}[t]
\begin{minipage}[t]{0.46\textwidth}
\begin{algorithm}[H]
\centering
\caption{Thompson sampling (TS)}\label{alg:ts}
\begin{algorithmic}[1]
\State {\bf Input:} History $\mathcal{H}_t$.
\State Form posterior $\nu_t = (m_{t,i}, s_{t,i}^2)_{i\in [k]}$ as in~\eqref{eq:posterior}.
\State Sample $\tilde{\theta}_i \sim \mathcal{N}(m_{t,i}, s_{t,i}^2)$ \,\, for each $i\in [k]$.
\State \Return $\operatorname*{arg\,max}_{i \in [k]} \tilde{\theta}_{i}$.
\end{algorithmic}
\end{algorithm}
\end{minipage}
\begin{minipage}[t]{0.46\textwidth}
\begin{algorithm}[H]
\centering
\caption{Top-two Thompson sampling with cost-aware selection rule}\label{alg:ttts}
\begin{algorithmic}[1]
\State {\bf Input:} History $\mathcal{H}_t$.
\State Sample $I_t^{(1)} \sim \mathrm{TS}(\mathcal{H}_t)$ using Algorithm \ref{alg:ts}.
\Repeat
\State Sample $I_t^{(2)} \sim \mathrm{TS}(\mathcal{H}_t)$ using Algorithm \ref{alg:ts}.
\Until{$I_t^{(2)} \neq I_t^{(1)}$}
\State Determine coin bias $h_t$ via~\eqref{eq:cost-aware-IDS}.
\State \Return $I_t^{(1)}$ w/ prob $h_t$, $I_{t}^{(2)}$ otherwise.
\end{algorithmic}
\end{algorithm}
\end{minipage}
\vspace{1mm}
\end{figure}
\cite{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. \cite{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:
\begin{equation}
\label{eq:cost-aware-IDS}
h_{t} = h_{t, I_t^{(1)}, I_{t}^{(2)}} \quad \text{where} \quad h_{t,i,j} \triangleq \frac{ \frac{1}{p_{t,i} C_{i}( \bm{m}_t)} }{\frac{1}{p_{t,i} C_{i}( \bm{m}_t)} + \frac{1}{p_{t,j} C_{j}( \bm{m}_t)} },
\end{equation}
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 \cite{qin2017improving, russo2020simple, shang2020fixed} and \cite{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{prop:TTTS} does not cover instances in which two arms have identical performance, and requires a more stringent regularity condition (Assumption~\ref{asm:sampling cost stronger}). 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{subsec:app_sufficient_exploration}. Uniform bounds on $C_{i}(\cdot)$ play a role in analyzing \eqref{eq:cost-aware-IDS} 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{def: strong convergence}.
\begin{restatable}[Optimality of Algorithm \ref{alg:ttts}]{proposition}{TTTS}
\label{prop:TTTS}
Let observations follow the Gaussian model where for any $i\in[K]$, $p(y\mid\theta_i) = \mathcal{N}(\theta_i, \sigma^2)$.
Let $\widetilde\pi$ implement Algorithm \ref{alg:general-template-gaussian} with Algorithm~\ref{alg:ttts} serving as the allocation rule. Under Assumption~\ref{asm:sampling cost stronger}, for any consistent policy $\pi \in \Pi$,
\[
\sup_{\bm{\theta} \in \widetilde{\Theta}} \,
\limsup_{n\to \infty} \, \frac{\mathrm{Cost}_{\bm{\theta}}(n, \widetilde\pi)}{\mathrm{Cost}_{\bm{\theta}}(n, \pi)} \leqslant 1,
\]
where $\widetilde{\Theta} \triangleq \left\{\bm{\theta}=(\theta_1,\ldots,\theta_k)\in\Theta \,:\, \theta_i\neq \theta_j, \, \forall i,j\in[k] \right\}$ is the set of instances with distinct arm means.
\end{restatable}
\begin{assumption}[A stronger assumption than Assumption~\ref{asm:sampling cost}]
\label{asm:sampling cost stronger}
For any arm $i\in[k]$, its within-experiment cost function $C_i(\cdot)$ is uniformly bounded away from~$0$ and~$\infty$.
That is, there exist $c_{\min}, c_{\max}\in(0,\infty)$ such that
\[
c_{\min} \leqslant C_i(\bm{\theta}) \leqslant c_{\max}, \quad\forall \bm{\theta}\in\mathbb{R}^k,\,\, \forall i\in[k].
\]
In addition,
$C_i(\cdot)$ is Lipschitz continuous at~$\bm{\theta}\in\Theta$.
\end{assumption}
Past theory gives some insight into the inner working of top-two Thompson sampling. It suggests information balance~\eqref{eq:info-balance-gaussian} is somehow attained \emph{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 \eqref{eq:cost-aware-IDS} as a resolution to that problem.
\begin{remark}[\cite{russo2020simple, shang2020fixed}]
\label{remark:TTTS beta}
Suppose top-two Thompson sampling (Algorithm \ref{alg:ttts}) is applied with a coin bias $h_t$ that converges almost surely to some fixed $\beta>0$. Then, with probability 1, ${\bm p}_{t} \to {\bm p}^{(\beta)}$ as $t\to \infty$, where ${\bm p}^{(\beta)} = \left(p^{(\beta)}_1,\ldots,p^{(\beta)}_k\right)$ is the unique probability vector satisfying $p^{(\beta)}_{I^*} = \beta$ and
\begin{equation}\label{eq:preview-info-balance}
\frac{ \theta_{I^*} - \theta_{i}}{ \sigma^2/\beta + \sigma^2/p^{(\beta)}_{i}} = \frac{ \theta_{I^*} - \theta_{j}}{ \sigma^2/\beta + \sigma^2/p^{(\beta)}_{j}}, \quad \forall i,j \neq I^*.
\end{equation}
\end{remark}
\subsection{Tracing the Pareto frontier between length and regret by adjusting the exploitation rate}
\label{subsec:frontier}
We have seen in Theorem~\ref{thm:efficient-p-gaussian} 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{subsec:lenght-regret-objectives}, 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{lem:consistency independent of cost functions}, we define the (asymptotic) attainable region as follows:
\begin{definition}[Attainable region]
\label{def:attainable region}
Fix some $\bm{\theta} \in \Theta$. A (normalized) length-regret pair $(L,R) \in \mathbb{R}^2$ is asymptotically attainable if there exists some policy $\pi \in \Pi$ satisfying
\[
\limsup_{n\to \infty} \frac{\mathrm{Length}_{\bm{\theta}}(n,\pi)}{\ln(n)} \leqslant L \quad \mathrm{and} \quad \limsup_{n\to \infty} \frac{\mathrm{Regret}_{\bm{\theta}}(n,\pi)}{\ln(n)} \leqslant R.
\]
The set of all attainable length-regret pairs is denoted $\mathcal{F}_{\bm{\theta}}$.
\end{definition}
For interpretation of the attainable region, it is important that the set of consistent policies $\Pi$, introduced in Definition~\ref{def:uniformly good rule}, 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.
\begin{lemma}[Consistency is determined independently of the cost functions]
\label{lem:consistency independent of cost functions}
A policy $\pi$ is an element of $\Pi$ if and only if, for each fixed $\bm{\theta} \in \Theta$, as $n\to \infty$,
\[
\ln\left(\mathbb{E}_{\bm{\theta}}^{\pi}\left[ \tau \right]\right) = o_{\bm{\theta}}(\ln(n))
\quad\text{and}\quad
\mathbb{P}^{\pi}_{\bm{\theta}}\left( \hat{I}_{\tau} \neq I^*(\bm{\theta}) \right)= o_{\bm{\theta}}\left(\frac{\ln(n)}{n}\right).
\]
\end{lemma}
Figure \ref{fig:Pareto-frontier} 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~\cite{russo2020simple}, or applying~\eqref{eq:cost-aware-IDS} for a length-regret objective~\eqref{eq:length-regret-objective} and varying the parameter $c>0$.
Appendix~\ref{app:frontier} provides details on how to plot the attainable region and Pareto frontier. More specifically, refer to Proposition \ref{prop:frontier}.
\begin{figure}[ht]
\centering
\caption{The set of length-regret outcomes that are attainable by a consistent policy. The plot considers the 6-arm instance $\bm{\theta}=(\theta_1,\theta_2,\theta_3,\theta_4,\theta_5,\theta_6)=(0,0.2,0.4,0.6,0.8,1)$. All points on the Pareto frontier are attained by adjusting the exploitation rate $\beta$ of top-two Thompson sampling. }
\label{fig:Pareto-frontier}
\includegraphics[width=3in]{fig/TheoreticalParetoFrontier.pdf}
\end{figure}
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{fig:Pareto-frontier}, $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 \emph{some} degradation in expected treatment quality, since it forgoes the possibility of adapting based on future information.
\begin{lemma}[Length cost of attaining optimal regret]
\label{lem:infinite_length}
Define $L^*_{\bm{\theta}}(R) \triangleq \inf\{ L' : (L', R') \in \mathcal{F}_{\bm{\theta}}, \, R'\leqslant R \}$. Then
\[
\lim_{R\downarrow R^*_{\bm{\theta}}} L^*_{\bm{\theta}}(R) = \infty.
\]
\end{lemma}
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{lem:infinite_length} 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.
\begin{proposition}
\label{prop:Pareto_robustness}
For any $\beta \geqslant 1/3$,
there exits an attainable point $\left(L^{(\beta)}_{\bm{\theta}}, R^{(\beta)}_{\bm{\theta}}\right) \in \mathcal{F}_{\bm{\theta}}$ such that
\[
L^{(\beta)}_{\bm{\theta}} \leqslant \frac{L^*_{\bm{\theta}}}{1-\beta} \qquad \text{and} \qquad R^{(\beta)}_{\bm{\theta}} \leqslant \frac{R^*_{\bm{\theta}}}{\beta}.
\]
\end{proposition}
Our proofs go further, and also reveal which algorithms attain the point $\left(L^{(\beta)}_{\bm{\theta}}, R^{(\beta)}_{\bm{\theta}}\right)$. Algorithm~\ref{alg:general-template-gaussian} 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{remark:TTTS beta}. 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{lem:length-regret-under-pi-beta}, given in Appendix \ref{app:frontier}, together with \citet{shang2020fixed}.
\subsection{Technical subtleties and almost sure vs. `strong' convergence}\label{subsec:strong-convergence}
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 \emph{expected} costs.
\begin{example}[Failure of almost sure convergence]\label{ex:failure-of-almost-sure}
Consider the following randomized allocation rule. Before the experiment begins, it samples a random time $T$. For the initial $T$ individuals, it samples arm 1. Those observations are then discarded and ignored. Starting with individual $T+1$, the experiment proceeds according to Algorithm \ref{alg:general-template-gaussian} with top-two Thompson sampling (Algorithm \ref{alg:ttts}) serving as the allocation rule. One can show that ${\bm p}_t \to {\bm p}^*$ almost surely. (It's as if the first $T$ samples never occurred.)
But if $T$ has Pareto-type tails with $\alpha < 1$: $\mathbb{P}(T>x) = x^{-\alpha}$ for $x\geqslant 1$, then ${\rm Cost}_{\bm{\theta}}(n, \pi) = \Omega(n^{1-\alpha})$, since expected costs are lower bounded as
\[
{\rm Cost}_{\bm{\theta}}(n, \pi) \geqslant C_{\min}(\bm{\theta})\cdot\mathbb{E}\left[T \wedge n\right] \geqslant C_{\min}(\bm{\theta})\cdot n \cdot \mathbb{P}\left(T>n\right) = n^{1-\alpha},
\]
where $C_{\min}(\bm{\theta})=\min_{i \in [k]}C_{i}(\bm{\theta})$ is strictly positive by Assumption \ref{asm:sampling cost}.
\end{example}
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{ex:failure-of-almost-sure} 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$.
\begin{definition}[Strong convergence]
\label{def: strong convergence}
For a sequence of real valued random variables $\{X_\ell\}_{\ell\in \mathbb{N}_1}$ and a scalar $x\in \mathbb{R}$,
we say $X_\ell$ converges strongly to $x$, denoted by $X_\ell\xrightarrow{\mathbb{S}} x$, if
\[
\text{for all } \epsilon>0 \, \text{there exists } \, L \in \mathcal{L}^1 \, \text{ such that for all } \ell\geqslant L,\,\, |X_\ell - x| \leqslant \epsilon.
\]
For a sequence of random vectors $\{\bm{X}_\ell\}_{\ell\in \mathbb{N}_1}$ taking values in $\mathbb{R}^d$ and a vector $\bm{x}\in \mathbb{R}^d$, we say $\bm{X}_\ell$ converges strongly to $\bm{x}$, denoted by $\bm{X}_\ell\xrightarrow{\mathbb{S}} \bm{x}$, if for all $i\in [d]$, $X_{\ell,i}$ converges strongly to $x_{i}$ .
\end{definition}
\section{Generalization to exponential family distributions }
This section generalizes insights derived in the Gaussian case.
The Lai-Robbins formula in Theorem~\ref{thm:Lai-Robbins-type formula} holds without modification. Again, the optimal allocation of experimental effort is mostly determined by a purely statistical \emph{information-balance} constraint. A scalar variable, the long-run \emph{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.
\subsection{A similar algorithm template}
To address problems in which rewards are drawn from general one-dimensional exponential family distributions, we slightly modify Algorithm \ref{alg:general-template-gaussian}. Rather than stop when certain $Z$-statistics are uniformly large, as in Algorithm \ref{alg:general-template-gaussian}, under Algorithm \ref{alg:general-template-exp-family} 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 \citep{chernoff1959sequential, chan2006sequential}, with a threshold that is derived based on \cite{Kaufmann2021martingale}.
\begin{algorithm}[H]
\centering
\caption{General template}\label{alg:general-template-exp-family}
\begin{algorithmic}[1]
\State{\bf Input:} $\mathtt{AllocationRule}(\cdot)$, a function which takes an input a history $\mathcal{H}_t$ of arbitrary length and returns a probability distribution over $[k]$.
\State {\bf Initialize:} $\mathcal{H}_0 \gets \{ \}$, $\tau=n$.
\For{$t=0,1,\ldots, n-1$}
\If{$t < \tau$}
\LineComment{\emph{\textcolor{blue}{If experimentation has not yet stopped, ...}}}
\State Obtain $\hat{I}_t \in \operatorname*{arg\,max}_{i \in [k]} m_{t,i}$ and $\gamma_t(n)$ as in \eqref{eq:tight threshold T}.
\If {$t \cdot \min_{j\neq \hat{I}_t} D_{{\bm m}_t , \hat{I}_t,j}({p}_{t,\hat{I}_t}, {p}_{t,j}) \geqslant \gamma_t(n)$}
\LineComment{\emph{\textcolor{blue}{If all Chernoff information statistics are large, stop experimenting. }}}
\State Set $\tau=t$ and $\hat{I}_{\tau} \in \operatorname*{arg\,max}_{i \in [k]} m_{\tau,i}$.
\State Assign arm $I_t = \hat{I}_{\tau}$.
\Else
\LineComment{\emph{\textcolor{blue}{Otherwise, continue experimenting using the allocation rule.}}}
\State Assign arm $I_t \sim \mathtt{AllocationRule}(\mathcal{H}_t)$.
\State Observe $Y_{t,I_t}$ and update history $\mathcal{H}_{t+1} \gets \mathcal{H}_t\cup \{(I_t, Y_{t,I_t}) \}$.
\EndIf
\Else
\LineComment{\emph{\textcolor{blue}{If experimentation has stopped, ...}}}
\State Assign arm $I_t = \hat{I}_{\tau}$.
\EndIf
\EndFor
\end{algorithmic}
\end{algorithm}
\subsection{Chernoff information as a generalization of $Z$-statistics}
We define a weighted version of the Chernoff information between, a fundamental quantity in the theory of hypothesis testing \citep{cover2006elements} which as appeared previously in the pure exploration literature \citep{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
\begin{align}
D_{\bm{\theta}, i,j}(p_{i}, p_j) &\triangleq \min_{\vartheta_j \geqslant \vartheta_i} \, p_{i} \cdot {\rm KL}\left(\theta_{i} , \vartheta\right) + p_j \cdot {\rm KL}\left(\theta_{j} , \vartheta\right) \label{eq:chernoff-info}\\
&= p_{i} \cdot {\rm KL}(\theta_{i} , \bar{\theta}_{i,j}) + p_j \cdot {\rm KL}(\theta_{j} , \bar{\theta}_{i,j}),\label{eq:chernoff-info-minimizer}
\end{align}
where the weighted average
\begin{equation}
\label{eq:weighted average}
\bar{\theta}_{i,j} \triangleq \frac{p_{i} \theta_{i}+ p_j\theta_j}{ p_{i}+p_j}.
\end{equation}
is the unique minimizer to~\eqref{eq:chernoff-info} 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}]$.
\begin{example}[Connection to Z-statistics]\label{ex:chernoff-to-z}
If observations are Gaussian with $p(y\mid\theta_i) =\mathcal{N}(\theta_i, \sigma^2)$, then
\[
D_{\bm{\theta}, i,j}(p_{i}, p_j) = \frac{ (\theta_{i}-\theta_j)^2 }{2\sigma^2 \left( \frac{1}{p_{i}} + \frac{1}{p_{j}}\right)}.
\]
In particular, for the empirical mean reward ${\bm m}_t$ and empirical allocation $\bm{p}_t$,
\[
D_{{\bm m}_t , i,j}({p}_{t,i}, {p}_{t,j}) = \frac{ (m_{t,i}-m_{t,j})^2 }{2\sigma^2 \left( \frac{1}{p_{t,i}} + \frac{1}{p_{t,j}}\right)} = \frac{Z_{t, i, j}^2}{2t},
\]
where $Z_{t, i, j}$ is the Z-statistic for the mean difference defined in~\eqref{eq:z-stats}.
\end{example}
\subsection{Properties of an efficient allocation: information-balance with a cost-aware exploitation rate}
The subsection generalizes Theorem~\ref{thm:efficient-p-gaussian} to one-dimensional exponential family distributions. Again we show The information balance condition introduced in~\eqref{eq:info-balance-general} below generalizes the one for Gaussian distributions in~\eqref{eq:info-balance-gaussian}.
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~\eqref{eq:info-balance-general} 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~\eqref{eq:exploitation-rate-general} 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^*$.
\begin{restatable}[Optimality condition of allocation rules]{Theorem}{SufficientCondition}
\label{thm:efficient-p-general}
Algorithm~\ref{alg:general-template-exp-family} is universally efficient (Definition \ref{def:universal-efficiency}) if
the allocation rule satisfies the following condition:
for any $\bm{\theta}\in\Theta$, under any produced indefinite-allocation sample path~\eqref{eq:allocaiton-only-sample}, the empirical allocation $\bm{p}_t$ converges strongly (Definition \ref{def: strong convergence}) to a unique probability vector $\bm{p}^* = \left(p_1^*,\ldots,p_k^*\right) > \bm{0}$ satisfying the information balance condition
\begin{equation}
\label{eq:info-balance-general}
D_{\bm{\theta}, I^*, i}(p^*_{I^*}, p_i^*) = D_{\bm{\theta}, I^*, j}(p^*_{I^*}, p_j^*), \quad \forall i,j \neq I^*
\end{equation}
and (cost-aware) exploitation rate condition
\begin{equation}
\label{eq:exploitation-rate-general}
\sum_{j\neq I^*}\frac{{\rm KL}(\theta_{I^*},\bar{\theta}^*_{I^*,j})/C_{I^*}(\bm{\theta})}{{\rm KL}(\theta_{j},\bar{\theta}^*_{I^*,j})/C_j(\bm{\theta})} = 1
\quad\text{with}\quad
\bar{\theta}^*_{I^*,j} \triangleq \frac{p_{I^*}^*\theta_{I^*} + p^*_j\theta_j}{p_{I^*}^* + p_j^*}.
\end{equation}
By contrast, Algorithm~\ref{alg:general-template-exp-family} is not universally efficient if there exists $\bm{\theta}\in\Theta$ such that the allocation rule's empirical allocation ${\bm p}_t$ converges strongly to a probability vector other than ${\bm p}^*$.
\end{restatable}
\subsection{Is top-two Thompson sampling still universally efficient?}
Given the developments above, it is not hard to directly construct a universally efficient allocation rule. In Appendix \ref{app:tracking}, we do this by building on the tracking algorithm of \cite{garivier2016optimal}; see Algorithm \ref{alg:D-Tracking} 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 \cite{chernoff1959sequential}.
It is not difficult to generalize top-two Thompson sampling to non-Gaussian reward distributions. The original paper \citep{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:
\begin{enumerate}
\item Our theory requires strong convergence to the optimal proportions (Definition \ref{def: strong convergence}) whereas \cite{russo2020simple} established only almost sure convergence. Strong convergence was established for Gaussian distributions by \cite{shang2020fixed} and bounded distributions (e.g. Bernoulli) by \cite{jourdan2022top}, but not for general exponential family distributions.
\item The simple rule for setting the coin bias is adapted from \cite{qin2023dualdirected}, who provided theory only in the Gaussian case. It's worth pointing out that there is a natural generalization to exponential family distributions which sets
\begin{equation*}
h_{t} = h_{t, I_t^{(1)}, I_{t}^{(2)}} \quad \text{where} \quad h_{t,i,j}\triangleq
\frac{ \frac{p_{t,i}{\rm KL}(m_{t,i}, \bar{m}_{t,i,j})}{C_{i}( \bm{m}_t)} }{ \frac{p_{t,i}{\rm KL}(m_{t,i}, \bar{m}_{t,i,j})}{C_{i}( \bm{m}_t)} + \frac{p_{t,j}{\rm KL}(m_{t,j}, \bar{m}_{t,i,j})}{C_{j}( \bm{m}_t)} }
\quad\text{with}\quad
\bar{m}_{t,i,j} \triangleq \frac{p_{t,i}m_{t,i} + p_{t,j}m_{t,j}}{p_{t,i} + p_{t,j}},
\end{equation*}
but it is an open question to provide rigorous convergence guarantees under this choice. One can set the coin bias equal to the estimated optimal exploitation rate, formed solving an empirical analogue of the \eqref{eq:info-balance-general} and \eqref{eq:exploitation-rate-general}. But the formula above seems much simpler.
\end{enumerate}
\subsection{The Lai-Robbins formula continues to hold}
The next result confirms that the result in Theorem~\ref{thm:Lai-Robbins-type formula} holds even for non-Gaussian distributions.
\begin{restatable}[Lai-Robbins-type formula]{Theorem}{LaiRobbins}
\label{thm:Lai-Robbins-type formula_general}
A policy $\pi$ is universally efficient if and only if,
\begin{equation}
\label{eq:sufficient and necessary condition of universal efficiency}
\forall\bm{\theta}\in\Theta:\quad
\mathrm{Cost}_{\bm{\theta}}(n, \pi) \sim \sum_{j\neq I^*} \frac{C_{j}(\bm{\theta}) }{ {\rm KL}(\theta_j , \bar{\theta}^*_{I^*,j}) } \times \ln(n) \quad\text{as}\quad n\to\infty,
\end{equation}
where $\bar{\theta}^*_{I^*,j}=\frac{p^*_{I^*}\theta_{I^*}+p_j^* \theta_j}{p^*_{I^*}+p^*_j}$ is identified in Theorem~\ref{thm:efficient-p-general}.
\end{restatable}
\section{Characterizing asymptotic efficiency by the ``Skeptic's Standoff'' game}
\label{sec:game}
As discussed in the literature review, the analysis leading to our results in Theorems~\ref{thm:efficient-p-general} and \ref{thm:Lai-Robbins-type formula_general} builds on an approach that dates back to \cite{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 \emph{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
\begin{equation}\label{eq:payoff-function}
\Gamma_{\bm{\theta}}(\bm{p},\bm{\vartheta}) \triangleq \frac{\sum_{i\in[k]} p_i {\rm KL}(\theta_i,\vartheta_i)}{\sum_{i\in[k]}p_iC_i(\bm{\theta})},
\quad \forall (\bm{p},\bm{\vartheta})\in \Sigma_k\times \overline{\rm Alt}(\bm{\theta}).
\end{equation}
Since the game is zero-sum, $-\Gamma_{\bm{\theta}}(\bm{p},\bm{\vartheta})$ is the payoff function for the skeptic.
The denominator in \eqref{eq:payoff-function} 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{thm:equilibrium}, 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
\begin{equation}
\label{eq:hard instance}
\vartheta^{*j}_{I^*} = \vartheta^{*j}_j = \bar{\theta}^*_{I^*,j}
\quad\text{and}\quad
\vartheta^{*j}_i = \theta_i, \quad\forall i\notin \{I^*,j\},
\end{equation}
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~\eqref{eq:info-balance-general} and (cost-aware) exploitation rate condition~\eqref{eq:exploitation-rate-general}. 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
\begin{equation}
\label{eq:optimal q}
\bm{q}^*(\bm{\vartheta}^{*j}) \propto \frac{C_j(\bm{\theta})}{{\rm KL}(\theta_{j},\bar{\theta}^{*}_{I^*,j})};
\end{equation}
the RHS equals the $j$-th term of the optimal scaling in Lai-Robbin-type formula in Theorem~\ref{thm:Lai-Robbins-type formula_general}.
Now we formally present Theorem~\ref{thm:equilibrium}, which identifies the unique equilibrium strategies $({\bm p}^*, {\bm q}^*)$ and the equilibrium value to the Skeptic's Standoff game.
\begin{Theorem}[Equilibrium]
\label{thm:equilibrium}
The Skeptic's Standoff game has a unique pair of equilibrium strategies $({\bm p}^*, {\bm q}^*)$, and
the equilibrium value satisfies the formula\footnote{This formula indicates that the probability vector $\bm{q}^*$, defined in \eqref{eq:optimal q}, has the explicit expression: for any $j\neq I^*$,
$\bm{q}^*(\bm{\vartheta}^{*j}) = \frac{C_j(\bm{\theta})}{{\rm KL}(\theta_{j},\bar{\theta}^{*}_{I^*,j})}\Gamma_{\bm{\theta}}(\bm{p}^*,\bm{q}^*)$.}
\begin{equation}
\label{eq:equilibrium value's formula}
\frac{1}{\Gamma_{\bm{\theta}}(\bm{p}^*,\bm{q}^*)} = \sum_{j\neq I^*} \frac{C_j(\bm{\theta})}{ {\rm KL}(\theta_j , \bar{\theta}^*_{I^*,j}) },
\quad\text{where}\quad \bar{\theta}^*_{I^*,j}=\frac{p^*_{I^*}\theta_{I^*}+p_j^* \theta_j}{p^*_{I^*}+p^*_j}.
\end{equation}
\end{Theorem}
Theorem~\ref{thm:equilibrium} 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{thm:efficient-p-general},
we can restate Theorem~\ref{thm:efficient-p-general} as follows.
\begin{corollary}[Restatement of Theorem~\ref{thm:efficient-p-general}]
Algorithm \ref{alg:general-template-exp-family} is universally efficient (Definition \ref{def:universal-efficiency}) if the input allocation rule satisfies the following property: for any $\bm{\theta}\in\Theta$, the empirical allocation ${\bm p}_t$ converges strongly (Definition \ref{def: strong convergence}) to the experimenter's unique equilibrium strategy~${\bm p}^*$.
By contrast, Algorithm~\ref{alg:general-template-exp-family} is not universally efficient if there exists $\bm{\theta}\in\Theta$ such that the allocation rule's empirical allocation ${\bm p}_t$ converges strongly to a probability vector other than the experimenter's unique equilibrium strategy~${\bm p}^*$.
\end{corollary}
Theorem~\ref{thm:equilibrium} also shows that the equilibrium value of the game is equal to the Lai-Robbins-style formula in Theorem~\ref{thm:Lai-Robbins-type formula_general},
so we can reinterpret Theorem~\ref{thm:Lai-Robbins-type formula_general} as follows.
\begin{corollary}[Restatement of Theorem~\ref{thm:Lai-Robbins-type formula_general}]
A policy $\pi$ is universally efficient if and only if,
\[
\forall\bm{\theta}\in\Theta:\quad
\mathrm{Cost}_{\bm{\theta}}(n, \pi) \sim \frac{1}{\Gamma_{\bm{\theta}}(\bm{p}^*,\bm{q}^*)} \times \ln(n)
\quad\text{as}\quad n\to\infty.
\]
\end{corollary}
Our analysis in the appendix starts with the proof of Theorem~\ref{thm:equilibrium} and subsequently proves these restated results of Theorems~\ref{thm:efficient-p-general} and \ref{thm:Lai-Robbins-type formula_general}. 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 \citep{garivier2016optimal}, in which case no equilibrium exists.
Subsequent papers \citep{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{rem:lower_bound_proof} in Appendix \ref{app:lower bound proof}) and to deriving the form of the equilibrium value in Theorem~\ref{thm:equilibrium}, which ties the connection to a famous formula of \cite{lai1985asymptotically}.
\section{Conclusion}
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 \cite{lai1985asymptotically} and (fixed-confidence) best-arm identification problems in the style of \cite{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.
\newpage
\singlespacing
{\footnotesize
\setlength{\bibsep}{2pt plus 0.4ex}
\bibliographystyle{plainnat}
\bibliography{references}
}
\newpage