Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
75,548 characters · 32 sections · 36 citation commands
Minimax and Bayes Optimal Best-Arm Identification
We investigate the problem of fixed-budget best-arm identification Audibert2010bestarm, an instance of adaptive experimental design for identifying the arm with the highest expected outcome. This problem is also known by various names across disciplines, including ordinal optimization Chen2000simulationbudget and adaptive experimental design for policy choice Kasy2021adaptivetreatment.
An adaptive experimental procedure in BAI usually consists of two phases Kaufmann2016complexity, the sampling phase and the recommendation phase. Given a total of $T$ rounds, the sampling phase allocates samples to arms at each round based on the observations obtained up to that point. After the final round, the procedure enters the recommendation phase, where an arm is selected based on the collected data.
In this setting, we propose a strategy and establish its minimax and Bayes optimality in terms of the simple regret, defined as the difference between the expected outcome of the best arm and that of the recommended arm. We first describe our strategy, Two-Stage Saddle-Point Allocation with Screening (TS-SPAS). We then derive minimax and Bayes lower bounds and show that our worst-case and average-case upper bounds coincide exactly with these lower bounds, including the constant terms.
We formulate the problem as follows. There are $K$ arms, and each arm $a \in [K] \coloneqq \{1,2,\dots, K\}$ has a potential outcome $Y_a \in {\mathcal{Y}}$, where ${\mathcal{Y}} \subseteq {\mathbb{R}}$ denotes the outcome space. Each potential outcome $Y_a$ follows a (marginal) distribution $P_{a, \mu_a}$ parameterized by $\mu_a \in {\mathcal{M}}$, where ${\mathcal{M}} \subset {\mathbb{R}}$ is a parameter space. For the parameter vector ${\bm{\mu}} \coloneqq (\mu_1, \mu_2, \dots, \mu_K) \in {\mathcal{M}}^K$, let ${\bm{P}}_{{\bm{\mu}}} \coloneqq (P_{1, \mu_1}, P_{2, \mu_2}, \dots, P_{K, \mu_K})$ be a collection of parametric distributions. The parameter $\mu_a \coloneqq {\mathbb{E}}_{P_{a,\mu_a}}[Y_a]$ is the mean of arm $a$.
Under a distribution ${\bm{P}}_{{\bm{\mu}}}$, our objective is to identify the best arm \[ a^*_{{\bm{\mu}}} = \operatorname*{arg\,max}_{a \in [K]} \mu_a, \] through an adaptive experiment in which data are sampled from ${\bm{P}}_{{\bm{\mu}}}$ according to our strategy.
\paragraph{Adaptive experiment.} Let $T$ denote the total sample size, also referred to as the budget. Assume there exist i.i.d. random vectors $(Y_{1,t},\ldots,Y_{K,t})_{t\in[T]}$ such that for each $a\in[K]$ and each $t\in[T]$, $Y_{a,t}\sim P_{a,\mu_a}$. Then, we consider an adaptive experimental procedure consisting of two phases:
Our task is to design a strategy $\delta$ that determines how arms are selected during the sampling phase and how the best arm is recommended at the end of the experiment. A strategy $\delta$ is formally defined as a pair $\left(\left(A_t^{\delta}\right)_{t \in [T]}, \widehat{a}_T^{\delta}\right){\delta}}$, where $\left(A_t^{\delta}\right)_{t \in [T]} \in [K]^T$ are the arm indices (actions) selected in the sampling phase, and $\widehat{a}_T^{\delta}$ is the estimator of the best arm $a^*_{{\bm{\mu}}}$ in the recommendation phase. For simplicity, we omit the dependence on $\delta$ when it is clear from the context.
\paragraph{Regret.} The performance of a strategy $\delta$ is measured by the expected simple regret, defined as:
This measures the welfare loss from deploying the recommended treatment in a future population. In other words, the goal is to design a strategy $\delta$ that minimizes the simple regret ${\mathrm{Regret}}^\delta_T({\bm{P}}_{{\bm{\mu}}})$. For simplicity, we refer to the expected simple regret as the simple regret in this study, although the simple regret originally refers to the random variable $Y_{a^*_{{\bm{\mu}}}} - Y_{\widehat{a}_T^{\delta}}$ without expectation.
\paragraph{Notation.} Let ${\mathbb{P}}_{{\bm{P}}_{{\bm{\mu}}}}$ denote the probability law under ${\bm{P}}_{{\bm{\mu}}}$, and let ${\mathbb{E}}_{{\bm{P}}_{{\bm{\mu}}}}$ represent the corresponding expectation operator. For notational simplicity, depending on the context, we abbreviate ${\mathbb{P}}_{{\bm{P}}_{{\bm{\mu}}}}[\cdot]$, ${\mathbb{E}}_{{\bm{P}}_{{\bm{\mu}}}}[\cdot]$, and ${\mathrm{Regret}}^\delta_T({\bm{P}}_{{\bm{\mu}}})$ as ${\mathbb{P}}_{{\bm{\mu}}}[\cdot]$, ${\mathbb{E}}_{{\bm{\mu}}}[\cdot]$, and ${\mathrm{Regret}}^\delta_T({\bm{\mu}})$, respectively. For each $a \in [K]$, let $P_{a, \mu_a}$ denote the marginal distribution of $Y_a$ under ${\bm{P}}_{{\bm{\mu}}}$. Denote the variance of $Y_a$ under the data-generating process by $\sigma_a^2(\mu_a)$, and write $\sigma_a(\mu_a)\coloneqq \sqrt{\sigma_a^2(\mu_a)}$. Let ${\mathcal{F}}_t = \sigma(A_1, Y_1, \ldots, A_t, Y_t)$ be the sigma-algebra. For each arm $a$ and mean $\mu\in{\mathcal{M}}$, let ${\mathbb{P}}_{a,\mu}$ and ${\mathbb{E}}_{a,\mu}$ denote probability and expectation under $P_{a,\mu}$. When the arm index is clear from context, we also write ${\mathbb{E}}_{\mu}$ for ${\mathbb{E}}_{P_{\mu}}$.
We denote the gap between the expected outcomes for the best arm $a^*_{{\bm{\mu}}}$ and an arm $a\in[K]$ by $\Delta_{{\bm{\mu}}}(a) \coloneqq \max_{b\in[K]}\mu_{b} - \mu_a = \mu_{a^*_{{\bm{\mu}}}} - \mu_a$. In the bandit literature, this gap plays an important role in theoretical evaluations.
To make all argmax-based rules measurable without appealing to “ties occur with probability zero”, we fix the following deterministic tie-break: for any finite set $S\subset{\mathbb{N}}$ and any real vector $(x_a)_{a\in S}$, we define the argmax as $\operatorname*{arg\,max}_{a\in S} x_a \coloneqq \min\Big\{a\in S\colon x_a=\max_{b\in S}x_b\Big\}$. For any $m$-dimensional vector ${\bm{v}} = (v_i)_{i\in{\mathcal{V}}}\in {\mathbb{R}}^m$, where ${\mathcal{V}}$ is its index set, let $v_{(i)}$ be its $i$-th largest value; that is, $v_{(1)} = \max_{i\in{\mathcal{V}}} v_i$ and $v_{(2)} = \operatorname*{arg\,max}_{i\in{\mathcal{V}}\setminus \{\operatorname*{arg\,max}_{k\in{\mathcal{V}}} v_k\}} v_i$.
Let $N_{a,t}\coloneqq \sum_{s=1}^t \mathbbm{1}[A_s=a]$. Let $\widehat{\mu}_{a, t}$ be the sample mean of the observed outcomes for arm $a$, that is, $\widehat{\mu}_{a,t}\coloneqq \frac{1}{N_{a,t}}\sum_{s=1}^t \mathbbm{1}[A_s=a]Y_s$, with the convention $\widehat{\mu}_{a,t}=0$ if $N_{a,t}=0$. Define ${\bm{\sigma}}^2 \coloneqq (\sigma_a^2)_{a\in[K]}$ and ${\bm{\sigma}} \coloneqq (\sigma_a)_{a\in[K]}$, where $\sigma_a\coloneqq \sqrt{\sigma_a^2}$. Similarly, define $\widehat{{\bm{\sigma}}}_{t}^2\coloneqq(\widehat{\sigma}_{a,t}^2)_{a\in[K]}$ and $\widehat{{\bm{\sigma}}}_{t}\coloneqq(\widehat{\sigma}_{a,t})_{a\in[K]}$ with $\widehat{\sigma}_{a,t}\coloneqq \sqrt{\widehat{\sigma}_{a,t}^2}$.
This study develops an asymptotically minimax and Bayes optimal strategy for fixed-budget BAI. Our proposed TS-SPAS strategy uses two-stage sampling in the sampling phase, where we sample arms according to a sampling ratio given as a solution (saddle point) of a Gaussian minimax game. We then recommend an arm according to a decision rule, which is also given as a solution of a Gaussian minimax game.
In the theoretical analysis, we focus on minimax and Bayes regret as criteria for evaluating the optimality of the proposed strategy. In the minimax analysis, we evaluate the worst-case regret of our proposed strategy over a class of distributions, and in the Bayesian analysis, we evaluate the expected regret under a prior distribution on the parameters. By showing that the upper and lower bounds coincide exactly, including the constant terms, we establish exact asymptotic minimax and Bayes optimality of our strategy.
\paragraph{Summary of main theoretical results.} To briefly illustrate our contributions, we assume in this section that $Y_a$ follows a Gaussian distribution with mean $\mu_a$ and variance $\sigma^2_a$. Let ${\mathcal{B}}_{\bm{\sigma}^2}$ denote the set of distributions ${\bm{P}}_{{\bm{\mu}}} = (P_{a, \mu_a})_{a\in[K]}$ where the means vary while the variances are fixed at $(\sigma^2_a)_{a\in[K]}$. We refer to such a set of distributions as a bandit model. In Section (ref), we define more general bandit models, which include other distributions such as Bernoulli distributions.
We define the minimax and Bayes regret as follows:
Remarkably, we show that our proposed strategy is asymptotically optimal in both minimax and Bayes senses.
\paragraph{Asymptotic Minimax optimality.} We show that our proposed algorithm attains asymptotic minimax optimality as follows:
where $\mathfrak C^{\mathrm{mm}}$ is called the sharp minimax constant defined in Section (ref).
\paragraph{Asymptotic Bayes optimality.} We also show that our proposed algorithm attains asymptotic Bayes optimality as follows:
where $C^{\mathrm{Bayes}}$ is called the sharp Bayes constant defined in Section (ref).
\paragraph{Main message.} Two phenomena determine the sharp constants: (i) minimax regret is governed by near ties where the top means differ by $O(T^{-1/2})$, and (ii) Bayes regret under regular priors is governed by pairwise near ties between the best and second-best arms. These facts imply that a single two-stage design, which combines variance estimation, screening, and a saddle-point allocation, is optimal under both criteria with exact leading constants.
\paragraph{Contents of this paper.} The remainder of this paper is organized as follows. In Section (ref), we review related work. Section (ref) defines our strategy. Section (ref) introduces a class of distributions that we consider. Sections (ref) and (ref) present the lower and upper bounds, respectively, for minimax and Bayes regret. In Section (ref), we discuss related problems.
This section provides a brief literature review. For a more detailed review, see Appendix (ref). The earliest BAI formulation appeared under the name ordinal optimization Chen2000simulationbudget,Glynn2004largedeviations, focusing on non-adaptive optimal designs via large-deviation principles. That literature often assumes that an experimenter knows how to sample arms to attain optimality, which requires knowledge of the distributional information of the arms' outcomes. Beginning in the 2010s, BAI was formulated by explicitly addressing the estimation of the optimal sampling rule Audibert2010bestarm,Bubeck2011pureexploration.
BAI is typically studied under two settings: the fixed-confidence setting and the fixed-budget setting Bubeck2011pureexploration,Audibert2010bestarm,Kaufmann2016complexity. While optimal strategies have been studied well in the fixed-confidence setting, they are not fully explored in the fixed-budget setting due to various technical difficulties reported in existing studies Kaufmann2020contributions,Ariu2021policychoice,Degenne2023existence.
We show the optimality of strategies by establishing matching lower and upper bounds. In fixed-budget BAI, Garivier2016optimalbest conjectures an information-theoretic lower bound for the probability of misidentification ${\mathbb{P}}_{{\bm{\mu}}}\left(\widehat{a}^\delta_T \neq a^*_{{\bm{\mu}}}\right)$, but there is no strategy that matches the lower bound. In fact, Ariu2021policychoice and Degenne2023existence establish theorems showing the impossibility and the difficulty. Note that this difficulty is closely related to the information-theoretic or distribution-dependent analysis, where we evaluate the performance measure under each fixed distribution ${\mathbb{P}}_{{\bm{\mu}}}$. See also the reverse Kullback--Leibler divergence problem in Kaufmann2020contributions. Note that the evaluation of the probability of misidentification ${\mathbb{P}}_{{\bm{\mu}}}\left(\widehat{a}^\delta_T \neq a^*_{{\bm{\mu}}}\right)$ and the (simple) regret ${\mathrm{Regret}}^\delta_T({\bm{\mu}})$ are asymptotically equivalent under exponential convergence to zero. This is because the regret is given as ${\mathrm{Regret}}^\delta_T({\bm{\mu}}) = \sum_{a \in [K]} \Delta_{{\bm{\mu}}}(a) {\mathbb{P}}_{{\bm{\mu}}}\left( \widehat{a}^\delta_T = a \right)$, where the constant $\Delta_{{\bm{\mu}}}(a)$ is negligible compared to the exponentially converging term ${\mathbb{P}}_{{\bm{\mu}}}\left( \widehat{a}^\delta_T = a \right)$.
Subsequent works consider the possibility of avoiding this difficulty by considering minimax and Bayes analyses, where we evaluate the performance measure under the worst case of ${\mathbb{P}}_{{\bm{\mu}}}\left( \widehat{a}^\delta_T = a \right)$ or the average of ${\mathbb{P}}_{{\bm{\mu}}}\left( \widehat{a}^\delta_T = a \right)$ weighted by a prior Komiyama2022minimaxoptimal,Komiyama2023rateoptimal,Atsidakou2023bayesianfixed,Kato2024generalizedneyman,Nguyen2024priordependent. In minimax and Bayes analyses, the evaluation of the probability of misidentification and the regret differ.
This study develops BAI strategies with exactly matching lower and upper bounds. Our lower bounds rely on change-of-measure identities and information inequalities for events measurable with respect to the bandit filtration, as well as existing bandit studies with other formulations such as cumulative reward maximization Lai1985asymptoticallyefficient and fixed-confidence BAI Garivier2016optimalbest. We then establish tight upper bounds for our strategy. To the best of our knowledge, this is the first work to show optimal strategies in minimax and Bayes analyses with exactly matching lower and upper bounds.
Closer to our fixed-budget simple-regret objective, Komiyama2023rateoptimal studied Bayesian simple regret for Bernoulli bandits under regular priors and obtained an explicit $1/T$ upper bound with a conjectured sharp leading constant. In the Bernoulli case, our sharp Bayes constant coincides with the constant in Komiyama2023rateoptimal, and our matching lower bound verifies its optimality; more generally, we allow heteroscedastic outcomes in mean-parameterized exponential families.
We use change-of-measure arguments with local asymptotic normality (LAN) and Le Cam's third lemma LeCam1972theoryofstatisics,LeCam1986asymptoticmethods. There are existing studies applying LAN to bandit experiments Hirano2025asymptoticrepresentations,Adusumilli2022neymanallocation,Adusumilli2023risk,Adusumilli2025samplestopsampling,Armstrong2022asymptoticefficiency. However, those works first restrict all parameters to local alternatives and discuss lower and upper bounds simultaneously. These approaches do not yield globally optimal strategies and also do not effectively eliminate suboptimal arms. To eliminate suboptimal arms effectively, as this study shows, we need to use large deviations for non-local arms to eliminate them in early rounds and then apply LAN to the final remaining arms. In fact, those existing studies do not provide optimal strategies in the fixed-budget BAI setting, as they only provide lower bounds or show optimal strategies only in the two-armed case.
From this section onward, we present the theoretical analysis of our TS-SPAS strategy, aiming to establish its minimax and Bayes optimality. We first define a class of distributions ${\mathcal{P}}$ for outcomes $Y$, over which we discuss the worst-case and average-case performance of strategies.
We consider canonical exponential families for this class, which are typically defined as follows Garivier2016optimalbest: \[ \left\{ (P_\theta)_{\theta \in \Theta} \colon \frac{dP_\theta}{d\xi}(y) = \exp\big( y \theta - b\big(\theta\big) \big)) }\right\}, \] where $P_\theta$ is a distribution parameterized by a natural parameter $\theta$, rather than $P_{\mu}$ used elsewhere, $\Theta \subset {\mathbb{R}}$ is the space of natural parameters $\theta$, $\xi$ is a reference measure on ${\mathcal{Y}}$, and $b \colon \Theta \to {\mathbb{R}}$ is a convex and twice differentiable function.
In this study, however, we consider worst-case and average-case performance over the mean parameter and characterize the lower and upper bounds in terms of variances, where the mean corresponds to $\dot{b}(\theta)$ and the variance corresponds to $\ddot{b}(\theta)$. Therefore, it is more convenient to define a class of distributions in terms of mean and variance parameters. This section provides such a definition and introduces a bandit model as a collection of $K$ distribution families.
We define the following mean-parameterized exponential families. Note that this class is essentially the same as the standard canonical exponential family, but we introduce it for the following purposes: (i) to define a distribution class parameterized by the mean, (ii) to ensure the correspondence between the inverse Fisher information and the variance, and (iii) to guarantee finite third moments, which are required for our analysis. Common distributions such as Gaussian and Bernoulli are included in this class.
For each arm $a\in[K]$, let $\sigma_a^2\colon{\mathcal{M}}\to(0,\infty)$ be continuous and bounded away from $0$ and $\infty$. Define the $K$-arm outcome model \[ {\mathcal{B}}_{\bm\sigma^2} \coloneqq \Big\{ (P_{a,\mu_a})_{a\in[K]}\colon \forall a, \{P_{a,\mu}\}_{\mu\in{\mathcal{M}}}\in{\mathcal{P}}(\sigma_a^2,{\mathcal{M}},{\mathcal{Y}})\Big\}, \qquad \bm\sigma^2=(\sigma_a^2)_{a\in[K]}. \]
We propose an adaptive design that attains both the minimax and Bayes sharp constants. Our strategy consists of two phases, the sampling phase and the recommendation phase. In the sampling phase, we adopt a two-stage sampling rule. Before the experiment begins, we divide the total number of rounds $T$ into two stages, the first stage consists of $T_0$ rounds and the second stage consists of $T - T_0$ rounds, where $T_0$ is defined in Section (ref). In the first stage, we sample arms uniformly across all arms, assigning $\lfloor T_0/K\rfloor$ rounds to each arm (In the following arguments, for notational simplicity, we assume that $T_0/K$ is an integer). At the end of this stage, we apply screening and eliminate clearly suboptimal arms using a concentration inequality, resulting in a candidate set of potentially optimal arms. In the second stage, we sample the remaining arms according to a sampling ratio that is given as a solution of the Gaussian minimax game defined in Section (ref). Once all $T$ sampling rounds have been completed, we proceed to the recommendation phase. In the recommendation phase, we select an arm using a decision rule obtained from the Gaussian minimax game. Since the solution of the Gaussian minimax game is given as a saddle point, we refer to our strategy as the Two-Stage Saddle-Point Allocation with Screening (TS-SPAS) strategy and denote it by $\delta^{\text{TS}\mathchar`-\text{SPAS}}$. Algorithm (ref) presents the pseudocode.
Before describing our strategy in detail, we define the Gaussian game, which plays an important role in our strategy and the subsequent optimality arguments. Fix an integer $m\ge 2$. Let ${\mathcal{S}} \subseteq [K]$ be a nonempty subset of $[K]$. For the case where $|{\mathcal{S}}| = m$, let us define a vector of standard deviations as ${\bm{\sigma}} =(\sigma_a)_{a\in{\mathcal{S}}}\in(0,\infty)^m$. Let us define \[ {\mathcal{W}}^{{\mathcal{S}}} \coloneqq \Bigg\{{\bm{w}} \coloneqq (w_a)_{a\in{\mathcal{S}}}\in[0,1]^m\colon \sum_{a\in{\mathcal{S}}} w_a=1\Bigg\}, \qquad {\mathcal{W}}^{{\mathcal{S}}\circ} \coloneqq \Bigg\{{\bm{w}}\in{\mathcal{W}}^{{\mathcal{S}}}\colon \min_a w_a>0\Bigg\}. \] Given ${\bm{w}}\in{\mathcal{W}}^{{\mathcal{S}}\circ}$ and ${\mathcal{S}} \subseteq [K]$, define the diagonal covariance
In the Gaussian proxy experiment, Nature chooses an unknown mean vector ${\bm{h}} = (h_a)_{a\in{\mathcal{S}}}\in{\mathbb{R}}^m$ and we observe \[ {\bm{X}} = {\bm{h}}+{\bm{Z}},\qquad {\bm{Z}}\sim{\mathcal{N}}\left(0,\Sigma^{{\mathcal{S}}}\left({\bm{w}}, {\bm{\sigma}}\right)\right)a\right)}, \] which can also be written as $(X_a)_{a\in{\mathcal{S}}} = (h_a)_{a\in{\mathcal{S}}} + (Z_a)_{a\in{\mathcal{S}}}$, that is, indices in ${\bm{X}}$ and ${\bm{Z}}$ also depend on ${\mathcal{S}}$. Let $\zeta^{{\mathcal{S}}}({\bm{h}}, {\bm{w}}, {\bm{\sigma}})$ be the distribution of ${\bm{X}}$.
A (possibly randomized) decision rule is a Markov kernel $g(\cdot\mid {\bm{x}})$ on ${\mathcal{S}}$ given ${\bm{X}} = {\bm{x}} = (x_a)_{a\in{\mathcal{S}}}\in{\mathbb{R}}^m$, and the decision-maker outputs $A\sim g(\cdot\mid {\bm{X}})$. We evaluate decisions under the simple regret
We may denote $A$ by $A(g)$ to emphasize the dependency of $A$ on $g$.
When convenient, for ${\mathcal{S}}\subseteq [K]$ such that $|{\mathcal{S}}| = m \geq 2$, we identify deterministic decision rules with measurable maps $g:{\mathbb{R}}^m\to{\mathcal{S}}$, and write $A=A(g)=g({\bm{X}})$.
The sampling phase consists of two stages. For simplicity, we assume that $\lfloor T_0/K\rfloor \geq 2$. In the first stage, each arm is sampled an equal number of times, that is, $\lfloor T_0/K\rfloor$ rounds per arm. Based on the outcomes, we identify the empirical best arm and select candidate arms that are competitive with it. When the number of remaining arms is one, we immediately return that arm as the estimated best arm. If the number is greater than or equal to two, then in the second stage, we compute the sampling ratio by solving the Gaussian minimax game. Note that when the number of remaining arms is two, there exists a closed-form solution to the Gaussian minimax game such that we sample each arm proportionally to its standard deviation. Such a sampling rule is called Neyman allocation Neyman1934ontwo. We describe the strategy in detail below.
\paragraph{Sample size in the first stage.} Fix $\epsilon\in(0,1/3)$. We define the first-stage budget as $T_0 \coloneqq \lceil T^{1-\epsilon}\rceil$, where $T_0\to\infty$ and $T_0 / T\to0$ as $T\to\infty$.
First stage. We sample each arm $\lfloor T_0/K\rfloor$ times.
Suboptimal arm elimination after the first stage. For each arm $a \in [K]$, we construct the following lower and upper confidence bounds:
where \[ \overline C\coloneqq \max_{a\in[K]} C_a, \qquad C_{\mathrm{scr}}>6, \qquad \tau_{T_0} \coloneqq \sqrt{\frac{C_{\mathrm{scr}}\overline C K\log T}{T_0}}. \] Here we use the unbiased sample variance (division by $\lfloor T_0/K\rfloor-1$), but one can also use the biased variant dividing by $\lfloor T_0/K\rfloor$.
Using these bounds, we construct the set of candidate arms: \[ \widehat{{\mathcal{S}}}_{T_0} \coloneqq \left\{a \in [K] \colon \widehat{u}_{a, T_0} \geq \widehat{l}_{\widehat{a}_{T_0}, T_0}\right\}, \] where $\widehat{a}_{T_0} \coloneqq \operatorname*{arg\,max}_{a\in[K]} \widehat{\mu}_{a, T_0}$.
This stage serves two purposes. First, it gathers enough data to estimate the variances used in the second stage. Second, it eliminates clearly suboptimal arms early, allowing greater focus on distinguishing between the top-performing arms.
Second stage. We obtain an estimate of the sampling ratio. The sampling in the second stage depends on the cardinality of $\widehat{{\mathcal{S}}}_{T_0}$. Let $\widehat{\sigma}^2_{b, T_0}$ is the empirical variance estimator defined as
We also let $\widehat{\sigma}_{b,T_0}\coloneqq \sqrt{\widehat{\sigma}^2_{b,T_0}}$.
\paragraph{Case 1: $\left|\widehat{{\mathcal{S}}}_{T_0}\right| = 1$.} If $|\widehat{{\mathcal{S}}}_{T_0}|=1$, we set the recommendation to be the unique arm in $\widehat{{\mathcal{S}}}_{T_0}$. The remaining budget can be spent arbitrarily (e.g., repeatedly pulling this arm), without affecting the recommendation.
\paragraph{Case 2: $\left|\widehat{{\mathcal{S}}}_{T_0}\right| = 2$.} We sample arms in the second stage following the Neyman allocation, that is, in proportion to the estimated standard deviations $\widehat{\sigma}_{a,T_0}$ for $a \in \widehat{{\mathcal{S}}}_{T_0}$. Equivalently, we set $\widehat{w}_{a,T_0} \coloneqq \frac{\widehat{\sigma}_{a,T_0}}{\sum_{c \in \widehat{{\mathcal{S}}}_{T_0}} \widehat{\sigma}_{c,T_0}}$. Since we have already sampled a certain number of samples in the first stage, we take these samples into account and sample arms according to $(\widehat{\pi}_{a, T_0})_{a \in \widehat{{\mathcal{S}}}_{T_0}}$, which is defined as $\widehat{\pi}_{a, T_0} \coloneqq \frac{\widetilde{\pi}_{a, T_0}}{\sum_{a\in\widehat{{\mathcal{S}}}_{T_0}}\widetilde{\pi}_{a, T_0}}$, where $\widetilde{\pi}_{a, T_0} \coloneqq \max\left\{\frac{\widehat{w}_{a, T_0} - T_0/(KT)}{1-T_0/T},0\right\}$.
\paragraph{Case 3: $\left|\widehat{{\mathcal{S}}}_{T_0}\right| \geq 3$.} If $\left|\widehat{{\mathcal{S}}}_{T_0}\right| \geq 3$, we sample arms so that the empirical sampling ratio $\sum_{t=1}^T \mathbbm{1}[A_t = a] / T$ converges to the sampling ratio $w_a$ defined as
where ${\bm{\sigma}}_{\widehat{{\mathcal{S}}}_{T_0}}\coloneqq\bigl(\sigma_a(\mu_a)\bigr)_{a\in\widehat{{\mathcal{S}}}_{T_0}}$, and $\sigma_a^2(\cdot)$ denotes the variance function in the model, and the true variance equals $\sigma_a^2(\mu_a)$ under $P_{a,\mu_a}$. If $Y_a$ is generated from a distribution $P_{a, \mu_a}$ with parameter $\mu_a$, then $\sigma^2_a = \sigma^2_a(\mu_a)$. We refer to this sampling ratio as an ideal sampling ratio given $\widehat{{\mathcal{S}}}_{T_0}$. In many studies such as Garivier2016optimalbest, such an ideal sampling ratio is used as a target in the sampling phase of adaptive experimental design. One common ideal sampling ratio is the Neyman allocation, and our ideal sampling ratio can be regarded as a variant of it.
Since the variances are unknown, the ideal sampling ratio is also unknown. Therefore, by estimating the variances, we estimate the ideal sampling ratio $(\widehat{w}_{a, T_0})_{a \in \widehat{{\mathcal{S}}}_{T_0}}$ as
We then sample arms in the second stage by sampling from a multinomial distribution with probabilities $(\widehat{\pi}_{a, T_0})_{a \in \widehat{{\mathcal{S}}}_{T_0}}$, which is defined as $\widehat{\pi}_{a, T_0} \coloneqq \frac{\widetilde{\pi}_{a, T_0}}{\sum_{a\in\widehat{{\mathcal{S}}}_{T_0}}\widetilde{\pi}_{a, T_0}}$, where $\widetilde{\pi}_{a, T_0} \coloneqq \max\left\{\frac{\widehat{w}_{a, T_0} - T_0/(KT)}{1-T_0/T},0\right\}$.
After the sampling phase, we recommend an arm using a decision rule $\widehat{g}$ obtained as a solution (saddle point) of the Gaussian minimax game.
When $|\widehat{{\mathcal{S}}}_{T_0}| = 2$, there exists a closed form solution for the decision rule, which is given as the empirical-best arm (EBA); that is, $\widetilde{g}(x)\in\operatorname*{arg\,max}_{a\in\{a,b\}} x_a$ for every ${\bm{w}}$. When $|\widehat{{\mathcal{S}}}_{T_0}|\ge 3$, there is no closed form except for some special cases such as equal variances. In this case, we recommend an arm following the decision rule $\widehat{g}$, a saddle point of the Gaussian minimax game, that is, \[ \widehat{a}^{\delta^{\text{TS}\mathchar`-\text{SPAS}}}_T \coloneqq \widehat{g}\left(\widehat {\bm{X}}_T\right), \] where $\widehat {\bm{X}}_T \coloneqq \sqrt{T}\left(\widehat\mu_{a, T}\right)_{a\in\widehat{{\mathcal{S}}}_{T_0}}\in{\mathbb{R}}^m$.
In this section, we establish the minimax lower bound and the worst-case upper bound for the simple regret for the TS-SPAS strategy. The performance upper bound depends on the parameters of the distributions. By taking the worst case for the parameters, we develop the lower and upper bounds.
The sharp minimax constant is given as the Gaussian minimax value defined in Section (ref) with ${\mathcal{S}} = [K]$. We define the mean-dependent standard deviation as ${\bm{\sigma}}(\mu)=(\sigma_1(\mu),\dots,\sigma_K(\mu))\in(0,\infty)^K$. Recall that we have defined the open simplex as ${\mathcal{W}}_{[K]}^{\circ}\coloneqq\{{\bm{w}}\in(0,1)^K\colon\sum_{a=1}^K w_a=1\}$. Given ${\bm{w}}\in{\mathcal{W}}_{[K]}^{\circ}$ and ${\bm{\sigma}}(\mu)$, let us define a covariance matrix as \[ \Sigma^{[K]}\left({\bm{w}},{\bm{\sigma}}(\mu)\right)\coloneqq \text{diag}\left(\frac{\sigma_1(\mu)^2}{w_1},\dots,\frac{\sigma_K(\mu)^2}{w_K}\right). \] Let ${\bm{h}} = (h_a)_{a\in{\mathcal{S}}}\in{\mathbb{R}}^K$ and \[ {\bm{X}} = {\bm{h}}+{\bm{Z}},\qquad {\bm{Z}}\sim{\mathcal{N}}\left(0,\Sigma^{[K]}\left({\bm{w}}, {\bm{\sigma}}(\mu)\right)\right))\right)}, \] whose distribution is denoted by $\zeta^{[K]}({\bm{h}}, {\bm{w}}, {\bm{\sigma}}(\mu))$. Given ${\bm{X}}$, we sample an arm $A\sim g(\cdot\mid {\bm{X}})$, where $g(\cdot\mid {\bm{x}})$ is a Markov kernel on $[K]$. We define the sharp minimax constant as
where $\mathfrak C^{[K]}\left({\bm{\sigma}}\right)$ is the Gaussian minimax value from Definition (ref) (Section (ref)) evaluated at $m=K$ and ${\bm{\sigma}}={\bm{\sigma}}(\mu)$: \[ \mathfrak C^{[K]}\bigl({\bm{\sigma}}(\mu)\bigr) \coloneqq \inf_{{\bm{w}}\in{\mathcal{W}}^{[K]\circ}}\inf_{g}\sup_{{\bm{h}}\in{\mathbb{R}}^K}{\mathbb{E}}_{\zeta^{[K]}({\bm{h}}, {\bm{w}}, {\bm{\sigma}})}\left[\Delta^{[K]}_{{\bm{h}}}(A)\right], \] where $\Delta^{{\mathcal{S}}}_{{\bm{h}}}(A)\coloneqq \max_{a\in{\mathcal{S}}} h_a - h_{A}$, and $A\sim g(\cdot\mid X)$. In the minimax regime, least favorable instances are near-ties: $\mu_a-\mu_b=O(T^{-1/2})$ among competing treatments. Thus, competing treatments share a common limit $\mu$ as $T\to\infty$, and their variances evaluate at the same $\mu$. This is why the sharp constant depends on ${\bm{\sigma}}(\mu)$.
We now present the minimax lower bound, which characterizes the best possible performance in the worst-case distribution.
Thus, we upper bounded the simple regret of the proposed strategy in Theorem (ref).
The results in the minimax lower bound (Theorem (ref)) and the worst-case upper bound (Theorem (ref)) imply the asymptotic minimax optimality.
Then, we derive the following worst-case upper bound for the simple regret under the TS-SPAS strategy. The proof is shown in Appendix (ref).
In this section, we establish the Bayes lower bound and the average upper bound for the simple regret for the TS-SPAS strategy. By taking the average of the regret bound weighted by the prior distribution, we develop the lower and upper bounds.
We now show the asymptotic Bayes optimality. Let $H$ be a prior distribution on ${\mathcal{M}}^K$. We assume the following regularity conditions for the prior distribution:
This assumption follows from those in Theorem 1 of Lai1987adaptivetreatment and Assumption 1 of Komiyama2023rateoptimal.
For each $a\in[K]$, let ${\bm{\mu}}_{\setminus\{a\}} = (\mu_b)_{b\in[K]\setminus\{a\}} \in {\mathcal{M}}^{K-1}$. For each $a\in[K]$, define the (tie-broken) best-of-others index and its value \[ b^*_{\setminus \{a\}}\coloneqq \operatorname*{arg\,max}_{b\in[K]\setminus\{a\}} \mu_b, \qquad m_a({\bm{\mu}}_{\setminus \{a\}})\coloneqq \mu_{b^*_{\setminus \{a\}}}. \] Let $H^{\setminus \{a\}}$ denote the marginal of $H$ on ${\bm{\mu}}_{\setminus \{a\}}$. Let $h_a(\cdot\mid{\bm{\mu}}_{\setminus\{a\}})$ be a version of the conditional density from Assumption (ref), and let $H_a(\mu\mid{\bm{\mu}}_{\setminus\{a\}})\coloneqq {\mathbb{P}}_H(\mu_a\le \mu\mid{\bm{\mu}}_{\setminus\{a\}})$ denote the corresponding conditional cumulative density function.
We define the sharp Bayes constant as
We now show a Bayes lower bound. Let $H$ be a prior distribution on ${\mathcal{M}}^K$.
We derive the following average upper bound under the TS-SPAS strategy. The proof is shown in Appendix (ref).
The results in the Bayes lower bound (Theorem (ref)) and the average upper bound (Theorem (ref)) imply the asymptotic Bayes optimality.
This section records decision-theoretic facts about the Gaussian proxy game introduced in Section (ref). The proxy game determines the sharp constants in Theorems (ref)--(ref), and it also provides an implementable characterization of the Stage 2 objects $(\widehat{{\bm{w}}}_{T_0},\widehat g)$ used by TS-SPAS (Algorithm (ref)).
Throughout, we fix a nonempty ${\mathcal{S}}\subseteq[K]$ with $m\coloneqq|{\mathcal{S}}|\ge 2$. Recall from Section (ref) that, for ${\bm{w}}\in{\mathcal{W}}^{{\mathcal{S}}\circ}$ and ${\bm{\sigma}}\in(0,\infty)^m$, the Gaussian proxy experiment observes ${\bm{X}}={\bm{h}}+{\bm{Z}}$ with ${\bm{Z}}\sim{\mathcal{N}}(0,\Sigma^{{\mathcal{S}}}({\bm{w}},{\bm{\sigma}}))$ and loss $\Delta^{{\mathcal{S}}}_{{\bm{h}}}(A)=\max_{a\in{\mathcal{S}}}h_a-h_A$. The associated minimax risk is $V^{{\mathcal{S}}}({\bm{w}},{\bm{\sigma}})$ and the Gaussian minimax value is $\mathfrak C^{{\mathcal{S}}}({\bm{\sigma}})$ (Definition (ref)).
The main uses of this section are:
The next results provide regularity properties of the Gaussian minimax value. They are used when plugging in $\widehat{{\bm{\sigma}}}_{T_0}$ in Stage 2 and when establishing existence of an interior minimizer $w^*$.
\paragraph{Deterministic rules and tie-breaking.} We call a decision rule $g$ deterministic if there exists a Borel measurable map $a\colon{\mathbb{R}}^m\to{\mathcal{S}}$ such that $g(b\mid x)=\mathbbm{1}[a(x)=b]$. Since ${\bm{X}}\sim{\mathcal{N}}({\bm{h}},\Sigma^{{\mathcal{S}}}({\bm{w}},{\bm{\sigma}}))$ has a continuous density for every fixed ${\bm{h}}$, ties occur with probability zero; hence any deterministic tie-breaking convention is immaterial for the risk. (We still fix a deterministic tie-break to make argmax selectors measurable.)
Recall from Remark (ref) that the loss depends only on differences of coordinates. The following lemma formalizes the corresponding invariance reduction and is used to justify centering.
For later reference (and for sanity-checking numerical solvers), the binary case admits a closed form.
Stage 2 of TS-SPAS requires computing an (approximate) saddle point \( (\widehat{{\bm{w}}}_{T_0},\widehat g) \) for the Gaussian minimax value \( \mathfrak C^{{\mathcal{S}}}({\bm{\sigma}}) \) (Definition (ref)) on the candidate set ${\mathcal{S}}=\widehat{{\mathcal{S}}}_{T_0}$ with $m\coloneqq|{\mathcal{S}}|\ge 3$. When $m=2$ there is a closed form (Lemma (ref)), but for $m\ge 3$ we solve the saddle-point problem numerically. In Appendix (ref), we describe a practical procedure that is consistent with the decision-theoretic characterization in Section (ref), in particular Proposition (ref) and Lemma (ref) (finite-support approximation of least-favorable priors).
If we focus solely on minimax optimality, we do not need to eliminate suboptimal arms in the first stage. This is because the worst case is governed by instances where all arms have gaps of order $O(1/\sqrt{T})$. After the first stage, even without eliminating suboptimal arms, we can sample each arm according to the solution of the Gaussian minimax game and recommend an arm according to the same solution. Such a strategy also guarantees minimax optimality.
If our interest lies solely in a Bayes optimal strategy, we can omit solving the Gaussian minimax game. In the second stage, if $|\widehat{{\mathcal{S}}}_{T_0}| = 2$, we apply the Neyman allocation; if $|\widehat{{\mathcal{S}}}_{T_0}| \geq 3$, we draw the other arms uniformly. Since, in the Bayes optimal case, only two arms dominate the regret, this simplification still works.
If we apply LAN to all arms, we cannot obtain an optimal strategy in a global sense. For example, Adusumilli2022neymanallocation,Adusumilli2023risk adopt such an approach, but these works do not provide an optimal strategy. This is because screening suboptimal arms using large-deviation arguments remains important, even when we apply LAN.
The proofs combine two complementary viewpoints. Bandit lower bounds often start from a change-of-measure identity Lai1985asymptoticallyefficient,Kaufmann2016complexity. Asymptotic statistics instead emphasizes LAN expansions and Le Cam's third lemma. These approaches are actually based on the same change-of-measure arguments. Therefore, our arguments closely follow the existing literature on bandits and asymptotic statistics.
When outcomes follow a Bernoulli distribution, our strategy can be simplified by omitting the variance estimation step. We describe this simplification in this section.
As discussed above, in both minimax and Bayesian analyses, regret is primarily influenced by instances in which the gap between the best and suboptimal arms shrinks at the rate $1/\sqrt{T}$. Formally, as $T \to \infty$, we have $\mu_{a^*_{{\bm{\mu}}}} - \mu_b \to 0$. Recall that for Bernoulli outcomes, the variance of arm $a$ is $\sigma^2_a(\mu_a) = \mu_a(1 - \mu_a)$. As the mean differences converge to zero, the variances of the best arm and its competitors also converge, $\sigma_{a^*_{{\bm{\mu}}}}(\mu_{a^*_{{\bm{\mu}}}}) - \sigma_b(\mu_b) \to 0$. When these variances become asymptotically equivalent, variance-based sampling in the second stage of the sampling phase is unnecessary. Instead, we sample arms in the candidate set $\widehat{{\mathcal{S}}}_{T_0}$ uniformly, that is, with probability $1 / |\widehat{{\mathcal{S}}}_{T_0}|$ for each arm. We then obtain the following result.
In this study, for fixed-budget BAI, we proposed the TS-SPAS strategy, which eliminates clearly suboptimal arms early and samples the remaining arms to distinguish the best arm from the others. In our theoretical analysis, we derived minimax and Bayes lower bounds for the simple regret, establishing fundamental performance limits for any regular strategy. We further proved that the simple regret of the proposed strategy matches these lower bounds, including the constant term, not only the rate.