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.
67,110 characters · 18 sections · 113 citation commands
Generalized Neyman Allocation for Locally Minimax Optimal Best-Arm Identification
Keywords: best-arm identification, adaptive experimental design, Neyman allocation
We investigate a minimax optimal algorithm for the problem of fixed-budget best-arm identification Audibert2010,Bubeck2011. Fixed-budget BAI is a specific instance of adaptive experimentation where, given multiple treatment arms and sample size (budget), we allocate these arms to experimental units during the experiment, aiming to identify the best arm, the one with the highest expected outcome, at the end of the experiment.\footnote{The term “arms” is also referred to as “treatments” or “arms” in the literature.} \footnote{There is another setting called fixed-confidence BAI, in which we continue an adaptive experiment until we identify the best arm with a certain fixed probability. In this setting, the sample size is not fixed but is treated as a stopping time.} BAI is closely connected to both bandit problems and causal inference, and it has been extensively studied in various fields, including machine learning Kaufman2016complexity, economics Kasy2021, and operations research Shin2018.
In this study, we propose an asymptotically minimax optimal algorithm whose performance upper bound matches the lower bound under the worst-case distribution as the budget approaches infinity and the differences between the expected outcomes of the best and suboptimal arms approach zero. Note that the differences (gaps) correspond to the average treatment effects in causal inference. We call this setting the small-gap regime. The existence of optimal algorithms in fixed-budget BAI has long been an open question Ariu2021. We address this issue by introducing a novel minimax algorithm.
Our proposed algorithm generalizes the Neyman allocation Neyman1934OnTT, a method that has gained significant attention in the field of adaptive experimental design Hahn2011,Meehan2018,Kato2020adaptive,adusumilli2022minimax,CAI2024105793. The existing Neyman allocation is limited to binary arms, and their extension to the multi-armed case remains unexplored. In this study, we bridge this gap by presenting a generalized version of the Neyman allocation.
The remainder of this paper is structured as follows. In this section, we outline the problem setting, provide background information on BAI, discuss related work, and summarize our contributions. Section (ref) develops a worst-case lower bound under the small-gap regime. In Section (ref), we introduce the Generalized Neyman Allocation (GNA) algorithm. Section (ref) derives an upper bound for the GNA algorithm and demonstrates its local asymptotic minimax optimality by proving that the lower and upper bounds converge as the budget approaches infinity and the gap between arm outcomes diminishes.
In our problem, we consider a decision-maker who conducts an adaptive experiment with a fixed budget (sample size) $T$ and a fixed set of arms $[K] \coloneqq \{1,2,\dots, K\}$. Each arm $a \in [K]$ has a potential random outcome $Y_a \in \mathcal{Y} \subset \mathbb{R}$, where $\mathcal{Y}$ is an outcome space Neyman1923,Rubin1974. Let $P_a$ be the marginal distribution of $Y_a$ for each $a \in [K]$, and let $P \coloneqq (P_a)_{a\in[K]}$ be the set of $P_a$.\footnote{We can define $P$ as a joint distribution of $(Y_a)_{a\in[K]}$. However, since multiple outcomes cannot be observed simultaneously, both definitions lead to the same consequences in our analysis. Following the literature on bandit studies, such as Kaufman2016complexity, we define $P$ as a set of marginal distributions.} Let $\mathbb{P}_{P}$ and $\mathbb{E}_{P}$ be the probability and expectation under $P$, respectively. Under $P$, let $a^\star(P) \coloneqq \operatorname*{arg\,max}_{a \in [K]} \mu_a(P)$ be the best arm, where $\mu_{a}(P) \coloneqq \mathbb{E}_{P}[Y_a]$ is the expected value of $Y_a$. Let $P_0$ be the distribution that generates data during an adaptive experiment, called the true distribution.
In each round $t \in [T] \coloneqq \{1,2,\dots, T\}$,
At the end of the experiment, the decision-maker constructs an estimator $\widehat{a}_T \in [K]$ of the best arm $a^\star(P_0)$. The decision-maker's goal is to identify the arm with the highest expected outcome, minimizing the probability of misidentification $\mathbb{P}_{P_0}(\widehat{a}_T \neq a^\star(P_0))$ at the end of the experiment.
We define an algorithm as a pair of $((A_t)_{t \in [T]}, \widehat{a}_T)$, where $(A_t)_{t \in [T]}$ is the allocation rule, and $\widehat{a}_T$ is the estimation rule. Formally, with the sigma-algebras $\mathcal{F}_{t} = \sigma(A_1, Y_1, \ldots, A_t, Y_t)$, an algorithm is a pair $((A_t)_{t \in [T]}, \widehat{a}_T)$, where
We denote an algorithm by $\pi$. We also denote $A_t$ and $\widehat{a}_T$ by $A^\pi_t$ and $\widehat{a}^\pi_T$ when we emphasize that $A_t$ and $\widehat{a}_T$ depend on $\pi$.
The allocation rule is closely connected to the probability of arm allocation, $\mathbb{P}_{P_0}(A_t = a)$, or the ratio of arm allocation, $\frac{1}{T}\sum^T_{t=1}\mathbb{P}_{P_0}(A_t = a)$. Depending on the context, these probabilities and ratios have different implications for designing the allocation rule. However, for simplicity, we do not distinguish between them in our algorithm design. We refer to the arm allocation probability (or ratio) associated with optimal algorithms as the optimal allocation probability (or ratio).
For this problem, we derive a lower bound for the probability of misidentification $\mathbb{P}_{P_0}(\widehat{a}_T \neq a^\star(P_0))$ and develop an algorithm whose probability of misidentification aligns with the lower bound.
We review the existing literature on fixed-budget BAI to clarify the issues. For well-designed algorithms $\pi$ and the true distribution $P_0$, the probability of misidentification, $\mathbb{P}_{P_0}\left( \widehat{a}^\pi_T \neq a^\star(P_0)\right)$, decreases exponentially as the budget $T$ approaches infinity. Specifically, for a value $C^\pi(P_0) > 0$ depending on $P_0$ and $\pi$ and independent of $T$, under a well-designed algorithm, we can have $\mathbb{P}_{P_0}\left( \widehat{a}^\pi_T \neq a^\star(P_0)\right) \approx \exp(-T C(P_0))$. A larger $C^\pi(P_0)$ indicates a faster decrease in the probability of misidentification. Thus, the goal is to develop algorithms that maximize $C^\pi(P_0)$.
To evaluate this exponential convergence, we use the following measure, called the complexity of the probability of misidentification:
Here, $C^\pi(P_0) \approx -\frac{1}{T}\log\mathbb{P}_{P_0}\left( \widehat{a}^\pi_T \neq a^\star(P_0)\right)$, and a larger complexity implies better performance. Typically, a lower bound represents the theoretical best performance (an upper bound on complexity), while an upper bound of an algorithm corresponds to the worst attainable performance (a lower bound on complexity). This complexity measure is widely used in studies on large-deviation evaluations in hypothesis testing Bahadur1960,Vaart1998, ordinal optimization glynn2004large, economics Kasy2021, and BAI Kaufman2016complexity.
Several studies evaluate performance using (simple) regret instead of the probability of misidentification. The regret is defined as \[ \mathrm{Regret}_{P_0}(\pi) \coloneqq \mathbb{E}_{P_0}\left[\mu_{a^\star(P_0)}(P_0) - \mu_{a^\pi_T}(P_0)\right], \] where the expectation is taken over the randomness of $a^\pi_T$. This metric is referred to as the simple regret Bubeck2011 or policy regret Kasy2021. The regret is closely related to complexity since the following bound holds: \[ \mathrm{Regret}(\pi) \leq \max_{a\in[K]}\left(\mu_{a^\star(P_0)}(P_0)- \mu_a(P_0)\right)\mathbb{P}_{P_0}\left( \widehat{a}^\pi_T \neq a^\star(P_0)\right), \] which follows from the decomposition $ \mathrm{Regret}(\pi) = \sum_{a\in[K]}\left(\mu_{a^\star(P_0)}(P_0)- \mu_a(P_0)\right)\mathbb{P}_{P_0}\left( \widehat{a}^\pi_T = a\right) $. Under a fixed $P_0$, the probability of misidentification and regret become asymptotically equivalent Kasy2021, but they lead to different results in minimax and Bayesian analyses Bubeck2011,Komiyama2021. In any analytical framework, the probability of misidentification plays a fundamental role. Since regret analysis introduces additional difficulties due to different assumptions and theoretical challenges, this study focuses solely on the probability of misidentification and its complexity to highlight our contributions explicitly. For an extension of our results to regret analysis, see kato2025minimaxoptimalsimpleregret.
If the distributional information is fully known, optimal algorithms can be derived using large-deviation principles Gartner1977,Ellis1984. For instance, when $Y_a$ follows a Gaussian distribution for all $a \in [K]$, chen2000 proposes an asymptotically optimal algorithm for Gaussian distributions. For general distributions, glynn2004large and degenne2023existence provide refined results. However, assuming complete knowledge of the distribution is unrealistic since it implies prior knowledge of the mean, variance, and the best arm.
In practice, BAI algorithms are often designed without assuming full knowledge of the underlying distributions Karnin2013,Shin2018. When such knowledge is incomplete, the existence of optimal algorithms remains an open question kaufmann2020hdr,Ariu2021,Qin2022open,degenne2023existence. Most studies in this area derive lower bounds for the complexity of the problem, as expressed in ((ref)), and aim to design algorithms whose misidentification probability matches these bounds.
Kaufman2016complexity proposes a general framework for deriving information-theoretical lower bounds using change-of-measure arguments Lai1985. These lower bounds depend on the underlying true distributions through the Kullback–Leibler (KL) divergence between the true and alternative distributions and are conjectured to be tight. When the number of arms is two ($K = 2$) and potential outcomes follow Gaussian distributions with known variances, Kaufman2016complexity establishes the asymptotic optimality of the Neyman allocation by demonstrating that the probability of misidentification matches the derived lower bound. Since the variances are known, we can allocate arms according to the ratio of their standard deviations without the need for adaptive estimation during the experiment.
However, for cases involving multiple arms, more general distributions, or unknown variances, the derivation of lower bounds and the development of corresponding optimal algorithms remain open challenges. For example, Garivier2016 conjectures a lower bound for the multi-armed setting, but kaufmann2020hdr identifies the reverse KL problem, which suggests limitations of this conjecture.\footnote{To be more precise, the challenges arising from multiple arms, more general distributions, and unknown variances stem from different underlying issues. The reverse KL problem is primarily associated with the multi-armed case and persists even when distributions are Gaussian and variances are known. The issue related to general distributions arises when considering KL divergence. The problem of unknown variances becomes significant when evaluating the estimation error of the allocation ratio. While multiple complexities exist in this problem, one of the most notorious challenges is the reverse KL problem.}
The existence of optimal algorithms whose probability of misidentification matches these lower bounds, including constant terms, remains a longstanding issue. Kasy2021 attempts to design such an algorithm for lower bounds in Kaufman2016complexity,\footnote{Rigorously, Kasy2021 considers a large-deviation bound presented in glynn2004large, which is equivalent to or closely related to the lower bounds proposed in Kaufman2016complexity. For further details, see degenne2023existence.} but Ariu2021 identifies technical issues in their proof related to the reverse KL problem in kaufmann2020hdr and shows that there exists a distribution under which no algorithm achieves the lower bound conjectured in Kasy2021 and Kaufman2016complexity. degenne2023existence further refines these impossibility arguments, providing deeper insights into the challenges of achieving such optimality.
Motivated by these challenges, Komiyama2022 and Komiyama2021 propose minimax and Bayes-optimal algorithms, respectively. However, their algorithms exhibit constant gaps between their upper and lower bounds, leaving room for improvement in either the upper bound or the lower bound. Furthermore, Komiyama2022 does not account for the estimation error in the arm allocation probability (or ratio), which depends on parameters such as means and variances that are typically unknown and must be estimated during experiments. If the estimation error is included in their analysis, their algorithm fails to achieve the lower bound. degenne2023existence refines the minimax approach. Note that minimax optimal algorithms have also been investigated by Carpentier2016 using a different approach; however, our minimax formulation is more closely related to that of Komiyama2022 and degenne2023existence.
Here, we elaborate on the issue related to the estimation error of the arm allocation probability. The allocation rule plays a critical role in best-arm identification. For two-armed problems with Gaussian outcomes, Kaufman2016complexity shows that Neyman allocation, which allocates arms in proportion to the standard deviations of their outcomes, is asymptotically optimal when the variances are known. However, this result no longer holds when the variances are unknown. Jourdan2022 addresses the problem of variance estimation in the context of fixed-confidence BAI, which differs from our setting. Their analysis reveals that the algorithms and their theoretical properties change when variances must be estimated.
Additionally, when considering multiple arms, the arm allocation probability depends on the mean and best arm, which are also unknown, not only on the variances. In the two-armed case, the unknown best arm does not pose a significant problem because the "optimal" arm allocation probability does not depend on which arm is the best.\footnote{Here, the "optimal" arm allocation probability refers to the allocation probability that, if followed, allows for identifying the best arm with a probability of misidentification that matches the lower bound.} However, in the multi-armed case, the optimal arm allocation probability may depend on the best arm, meaning that estimation error can influence the probability of misidentification.\footnote{Note that the optimal arm allocation probability has not been fully explored in existing studies. glynn2004large conjectures the optimal arm allocation probability given full information about the distribution. Under the optimal arm allocation probability proposed by glynn2004large and with additional restrictions on algorithms, degenne2023existence show that the probability of misidentification aligns with the lower bound established by Kaufman2016complexity. Shin2018 considers a heuristic algorithm for conducting BAI using the optimal arm allocation probability derived by glynn2004large when the distribution information is unknown.}
In this study, we develop a novel algorithm and refine both the upper and lower bounds for multiple arms and general distributions while explicitly incorporating the estimation error in the arm allocation probability. The reverse KL problem is mitigated by adopting the minimax framework. Under the small-gap regime, we address the issues related to general distributions and the estimation error of the arm allocation probability. First, in the small-gap regime, the KL divergence can be approximated by that of Gaussian distributions, simplifying the analysis. Second, the estimation error of the arm allocation probability can be relatively ignored compared to the leading term of the performance metric, as the problem becomes increasingly difficult as the gaps approach zero.
Other studies addressing this open problem include Barrier2023, atsidakou2023bayesian, nguyen2024priordependent, kato2024worstcase, and wang2023uniformly.
In fixed-confidence BAI, optimal algorithms have been proposed Garivier2016. In Bayesian settings, asymptotically optimal algorithms have been developed based on posterior convergence rates Russo2016,Shang2020, but these do not guarantee optimality for fixed-budget BAI Kasy2021,Ariu2021.
We propose an asymptotically minimax optimal algorithm whose probability of misidentification matches the worst-case lower bound under the small-gap regime, where the gaps between the expected outcomes of the best and suboptimal arms are small. This property, which we term local (asymptotic) minimax optimality, is demonstrated through the following contributions:
Informally, given an algorithm class $\Pi$ and a class of distributions restricted by the small-gap regime $\mathcal{P}^{\mathrm{small}}$, we have
where $C^{\pi*}(P)$ denotes an optimal constant, and $\widehat{a}^{\mathrm{GNA}}_T$ denotes the estimated best arm under the GNA algorithm.
In the subsequent sections, we define the algorithm class $\Pi$, the distribution class $\mathcal{P}^{\mathrm{small}}$, the optimal constant $C^\pi(P)$, and our proposed algorithm in greater detail. We summarize our contributions in Table (ref).
The complexity under the small-gap regime allows us to analyze performance while ignoring the estimation error of nuisance parameters, including the optimal arm allocation probability, which is not a parameter of interest. This regime reflects situations where, although the problem is challenging due to a small parameter of interest, the estimation error of nuisance parameters can be relatively neglected. Such a regime is also referred to as local Bahadur efficiency and has been widely used in the large-deviation analysis of statistical inference and decision-making with unknown parameters Kremer1979,Kremer1981,He1996.
It is important to note that this analysis differs from the local asymptotic normality framework, where parameters approach zero at the order of $\sqrt{T}$ for a sample size $T$. In the small-gap regime, the gaps approach zero independently of $T$. Thus, this small-gap analysis can be interpreted as a large-deviation analysis under distributions restricted to a specific range of parameters that are independent of $\sqrt{T}$.
By employing this regime, we can circumvent the impossibility result shown in Ariu2021. While Ariu2021 demonstrates that there exists a distribution under which no algorithm matches the lower bound, we address this by restricting the analysis to distributions with small gaps, effectively rejecting such problematic distributions.
For the expected outcome estimation, we employ the Adaptive Augmented Inverse Probability Weighting (A2IPW) estimator Kato2020adaptive,Kato2021adr,cook2023semiparametric, also known as the doubly robust estimator BangRobins2005, which is widely used across fields Laan2008TheCA.
This section establishes a lower bound for the probability of misidentification, focusing on the worst-case scenario under the small-gap regime. Lower bounds not only reveal the theoretical performance limit but also provide valuable insights into the design of optimal algorithms.
As a preparation, we define a class of distributions for $(Y_a)_{a\in[K]}$, which will be used to derive both lower and upper bounds. We refer to this class as a bandit model. First, we define a class $\mathcal{P}_a$ of distributions for $Y_a$. Then, we define a bandit model as the set $(\mathcal{P}_a)_{a\in[K]}$ of $\mathcal{P}_a$.
This is a class of mean-parameterized distributions with finite variances. For example, Gaussian distributions with fixed variances and Bernoulli distributions belong to this class. In the case of Gaussian distributions, the variances are typically defined to be independent of $\mu_a$, meaning that for all $\mu_a$, $\sigma^2_a(\mu_a) = \sigma^2_a$, where $\sigma^2_a$ is a constant. In contrast, for Bernoulli distributions, the variances are given by $\sigma^2_a(\mu_a) = \mu_a(1-\mu_a)$.
For a distribution $P_{a, \mu_a} \in \mathcal{P}_a$ of $Y_a$, let $P_{\bm{\mu}} = (P_{a, \mu_a})_{a\in[K]}$ represent a set of distributions for $(Y_a)_{a\in[K]}$. Then, given $\bm{\sigma} = (\sigma_a(\cdot))_{a\in[K]}$, $\Theta$, $\mathcal{Y}$, and $0 < \underline{\Delta} < \overline{\Delta}$, we define the following class of distributions (bandit models) for $(Y_a)_{a\in[K]}$: \[ \mathcal{P}\big(\underline{\Delta}, \overline{\Delta}\big) \coloneqq \mathcal{P}\big(\underline{\Delta}, \overline{\Delta}, \bm{\sigma}, \Theta, \mathcal{Y}\big) \coloneqq \Big\{ P_{\bm{\nu}} \colon \ \forall a \in [K],\ P_{a, \nu_a}\in\mathcal{P}_a,\ \ \forall b \in [K],\ \underline{\Delta} < \max_{a\in[K]}\nu_a - \nu_b \leq \overline{\Delta} \Big\}, \] where $\underline{\Delta}$ and $\overline{\Delta}$ are the lower and upper bounds of the gap $\max_{a\in[K]}\nu_a - \nu_b$. Here, $P_{a, \mu_a}$ is the distribution of $Y_a$ marginalized over the other variables $(Y_b)_{b\neq a}$. We do not assume any specific relationships among $(Y_a)_{a\in[K]}$. Therefore, $\mathcal{P}\big(\underline{\Delta}, \overline{\Delta}\big)$ is simply a set of distributions and does not imply any joint distribution structure.
Next, we define a class of algorithms and later show the asymptotic optimality for an algorithm belonging to this class. This study focuses on consistent algorithms that estimate the best arm with probability one as $T\to\infty$ Kaufman2016complexity.
Without this restriction, we could allow an algorithm that always returns arm $1$ independently of $P_0$. Such an algorithm would have zero probability of misidentification if $a^\star(P_0) = 1$ happens to hold. However, since such an algorithm is meaningless, we reject it by restricting the analysis to consistent algorithms.
Next, we derive a lower bound that any consistent algorithm must satisfy for mean-parameterized distributions. To obtain a tight lower bound, we employ the change-of-measure argument LeCam1972,LeCam1986,LehmCase98,Vaart1991,Vaart1998,Lai1985. Using this argument, Kaufman2016complexity develop a general framework for deriving lower bounds. In their results, the lower bounds are characterized by the KL divergence $\mathrm{KL}(P, Q)$ between two distributions $P$ and $Q$. Typically, we are interested in the KL divergence between the true distribution $P_0$ and an alternative hypothesis $Q$.
These lower bounds not only establish the theoretical performance limit but also provide insights for designing optimal algorithms, particularly in the construction of allocation rules. For example, in fixed-confidence BAI, Garivier2016 develops an optimal allocation probability (ratio) of treatment arms based on the KL divergence. Assuming full knowledge of the distribution, glynn2004large derives an optimal allocation probability (ratio) for fixed-budget BAI.
Thus, if the data-generating distribution $P_0$ were known, the KL divergence could be computed exactly, enabling the design of an asymptotically optimal algorithm based on the KL divergence, as demonstrated by glynn2004large. However, in practice, $P_0$ is unknown—if it were, the best arm could be identified without experimentation. In the context of BAI, the challenge is to develop algorithms that do not rely on prior knowledge of $P_0$.\footnote{Such "oracle" algorithms are referred to as static proportion algorithms in degenne2023existence.}
To account for the fact that $P_0$ is unknown in evaluation, we employ the statistical decision-making framework pioneered by Wald1945. Among several evaluation criteria, such as Bayesian evaluation Komiyama2021, we focus on the worst-case or minimax analysis. Specifically, we evaluate the worst-case probability of misidentification under the small-gap regime, defined as \[ \limsup_{0 < \underline{\Delta} < \overline{\Delta} \to +0}\inf_{P\in\mathcal{P}\left(\underline{\Delta}, \overline{\Delta}\right)}\limsup_{T \to \infty} -\frac{1}{\overline{\Delta}^2T}\log \mathbb{P}_{P}\left(\widehat{a}^\pi_T \neq a^\star(P)\right). \] OTSU200853 introduces a similar minimax framework in the large-deviation analysis of statistical decision-making (treatment choice), in contrast to the local asymptotic normality analysis by Hirano2009.
For the worst-case complexity, the following theorem provides a lower bound. The proof is presented in Appendix (ref).
Our lower bound depends on the worst-case variance $(\sigma^2_a(\mu^\dagger))_{a\in[K]}$ with the worst-case mean parameter $\mu^\dagger \in \Theta$ defined as \[\min_{a\in[K]}\frac{1}{2\left(\sigma_{a}(\mu^\dagger) + \sqrt{\sum_{b\in[K]\backslash\{a\}}\sigma^2_b(\mu^\dagger)}\right)^2} = \min_{a\in[K], \mu \in \Theta}\frac{1}{2\left(\sigma_{a}(\mu) + \sqrt{\sum_{b\in[K]\backslash\{a\}}\sigma^2_b(\mu)}\right)^2}.\]
While several existing studies, such as Carpentier2016, Komiyama2022, yang2022minimax, and degenne2023existence, have introduced the minimax evaluation framework, there is a constant gap between the lower and upper bounds, and only the leading factors in lower and upper bounds match. We conjecture that this is due to the estimation error of $P_0$ affecting the evaluation. To address this issue, we consider a restricted class for the distribution $P$, characterized by the small gap; that is, $\mu_{a^\star(P_0)} - \mu_a$ is sufficiently small for all $a\in[K]$. Under this regime, we can obtain matching lower and upper bounds, as shown in Section (ref). We refer to this as local minimax optimality.
Here, we emphasize that in the two-armed case, the lower bound simplifies to \[V(a^\star(P_0), \mu_{a^\star(P_0)}(P_0)) = \frac{1}{2\left(\sigma_{1}(\mu) + \sigma_{2}(\mu)\right)^2},\] where the denominator is identical to the efficiency bound in ATE estimation when the propensity score is set to the ratio of the standard deviations Kato2020adaptive.
Based on the lower bounds, we design the GNA-A2IPW algorithm, which consists of the allocation rule using the generalized Neyman allocation and the estimation rule using the Adaptive Augmented Inverse Probability Weighting (A2IPW) estimator. The pseudo-code is shown in Algorithm (ref).
First, we define a target allocation ratio. Let $\left(\sigma^2_a\right)_{a\in[K]}$ be the variances of $Y_a$ under the true distribution $P_0$. Using the variances, we define the oracle allocation rule as the one allocates arm $a$ following the probability $w^{\mathrm{GNA}}(a)$, defined as follows:
where
Note that this probability is unknown since the best arm $a^\star(P_0)$ and the variance $(\sigma^2_a)_{a\in[K]}$ are unknown. This target allocation ratio is given from the proof of the lower bound in Theorem (ref). We conjecture that an algorithm using the ratio ((ref)) is optimal and aim to design an algorithm using it. We confirm that such an algorithm is actually optimal by checking that the performance matches the worst-case lower bound derived in the previous section; that is, the target allocation ratio is optimal.
During our experiment, in each round $t$, we estimate $\bm{w}^{\mathrm{GNA}}$ using observed data until the round. Then, by using an estimated allocation ratio, we define our allocation rule. Our allocation rule is characterized by a sequence $\{\widehat{\bm{w}}^{\mathrm{GNA}}_t\}^T_{t=1}$, where $\widehat{\bm{w}}^{\mathrm{GNA}}_t = \left(\widehat{w}^{\mathrm{GNA}}_{a, t}\right)_{a\in[K]} \in \Delta^K$. The first $K$ rounds are the initialization phases. In each round $t = 1,\dots, K$, we set $\widehat{w}^{\mathrm{GNA}}_{1, t} = \cdots = \widehat{w}^{\mathrm{GNA}}_{K, t} = 1/K$ and sample $A_t = t$. Next, in each round $t = K + 1, K + 2, \dots, T$, we estimate $\sigma^2_a$ by using the past observations up to ($t-1$)-th round $\mathcal{F}_{t-1}$. By using the estimate $\widehat{\sigma}^2_{a, t}$, we obtain $\widehat{\bm{w}}^{\mathrm{GNA}}_t$ as
where $\widehat{a}_t = \operatorname*{arg\,max}_{a\in[K]}\widetilde{\mu}_{a, t}$ and $\widetilde{\mu}_{a, t} = \frac{1}{\sum^{t-1}_{s=1}\mathbbm{1}\left[A_s = a\right]}\sum^{t-1}_{s=1}\mathbbm{1}\left[A_s = a\right]Y_{a, s}$. Then, we allocate arm $a$ with probability $\widehat{w}^{\mathrm{GNA}}_{a, t}$.
In this study, we define an estimator $\widehat{\sigma}^2_{a,t}$ as \[\widehat{\sigma}^2_{a,t} \coloneqq
,\] where $\eta > 0$ is a small positive value, $\widetilde{\sigma}^2_{a,t} \coloneqq \frac{1}{\sum^{t-1}_{s=1}\mathbbm{1}\left[A_s = a\right]}\sum^{t-1}_{s=1}\mathbbm{1}\left[A_s = a\right]\Big(Y_{a, s} - \widetilde{\mu}_{a, t}\Big)^2$.
Note that $\widetilde{\sigma}^2_{a,t} > 0$ holds almost surely. However, to ensure a well-defined algorithm, we introduce $\eta$. The performance can be stabilized by modifying $\widehat{w}^{\mathrm{GNA}}_{a,t}$, provided that such modifications do not affect its consistency. For the modification ideas, see Section 3.3 in Kato2020adaptive, which studies ATE estimation using the Neyman allocation in an adaptive experiment.
At the end of the experiment (after observing $Y_T$), we estimate the best arm, an arm with the highest estimated expected outcome. We estimate the best arm by estimating the expected outcome $\mu_a$ for each $a\in[K]$. In this section, we define an estimation rule that employs an A2IPW estimator, proposed in Kato2020adaptive.
Let $\overline{C}_{\mu} > 0$ be a sufficiently large value. With a truncated version of the estimated expected reward $\widehat{\mu}_{a, t} \coloneqq \mathrm{thre}(\widetilde{\mu}_{a, t}, -\overline{C}_{\mu}, \overline{C}_{\mu})$, we define the A2IPW estimator of $\mu_a$ for each $a\in[K]$ as
Here, $\overline{C}_{\mu}$ is introduced for technical purposes to bound the estimators and any large positive value can be used.
At the end of the experiment (after the round $t=T$), we estimate $a^\star(P_0)$ as
The A2IPW estimator consists of a martingale difference sequence (MDS), which enables the application of various asymptotic analysis tools and simplifies the theoretical analysis. Utilizing the MDS property, Kato2020adaptive establish the asymptotic normality of the A2IPW estimator via the central limit theorem for an MDS. The unbiasedness of the A2IPW estimator follows directly from the definition of an MDS.
Although the A2IPW estimator is typically used in settings with covariates, we employ it in this study without covariates, as its MDS property significantly simplifies the theoretical analysis. While we conjecture that a naive sample mean estimator also possesses the same asymptotic theoretical properties, proving this result is not straightforward, as noted by hirano2003.
This section provides an upper bound of the probability of misidentification of the GNA algorithm.
We show the following upper bound for the probability of misidentification of the GNA algorithm, held for each $P_0$. We show the proof in Appendix (ref).
Here, recall that $V(a, \mu) = \frac{1}{2\left(\sigma_{a}(\mu) + \sqrt{\sum_{b\in[K]\backslash\{a\}}\sigma^2_b(\mu)}\right)^2}$.
Then, by considering the worst-case scenario for $P_0$, we obtain the following worst-case upper bound.
Recall that $\inf_{P \in \mathcal{P}\big(\underline{\Delta}, \overline{\Delta}\big)}$ represents the worst case, as a smaller value of $-\frac{1}{T}\log\mathbb{P}_P\left(\widehat{a}^{\mathrm{GNA}}_T \neq a^\star(P)\right)$ implies a lower probability of misidentification, i.e., $\mathbb{P}_P\left(\widehat{a}^{\mathrm{GNA}}_T \neq a^\star(P)\right)$ becomes smaller.
This section proves the local minimax optimality of our proposed GNA algorithm. The following result demonstrates that the probability of misidentification of the GNA algorithm matches the worst-case lower bound derived under the small-gap regime. This establishes that our proposed algorithm is local asymptotic minimax optimal.
Note again that the upper and lower bounds appear flipped due to the properties of the logarithm function, $\log(x)$.
We illustrate the concept of local asymptotic minimax optimality in Figure (ref). In the figure, the upper (red) region represents the upper bound, while the lower (blue) region represents the lower bound, and they converge as $\Delta \to 0$ (small-gap). That is, although a discrepancy remains between the lower and upper bounds, it diminishes as the gap approaches zero.
We provide an intuitive explanation of why the GNA algorithm is effective. BAI algorithms are closely connected to constructing tight confidence intervals for testing whether $\mu_{a^\star(P_0)}(P_0) \neq \mu_a(P_0)$ for all $a\neq a^\star(P_0)$. To accurately identify the best arm $a^\star(P_0)$, given $a^\star(P_0)$, we aim to allocate treatment arms such that the discrepancies between the confidence intervals of the expected outcomes of the best and suboptimal arms become large.
First, we consider how the GNA algorithm operates when $K = 2$, which corresponds to the standard Neyman allocation algorithm. For instance, assuming that the best arm is $a^\star(P_0) = 1$, we estimate the ATE $\mu_1(P_0) - \mu_2(P_0)$ to test whether $a^\star(P_0) \neq 1$. If the null hypothesis is rejected, we conclude that the alternative hypothesis $a^\star(P_0) = 1$ is accepted. To efficiently test this hypothesis using asymptotic properties, it is crucial to minimize the asymptotic variance of the ATE estimators. In ATE estimation, the asymptotic variance of an efficient ATE estimator is given by $ \frac{\sigma^2_{1}(\mu_1(P_0))}{w_1} + \frac{\sigma^2_{2}(\mu_2(P_0))}{w_2}$, where $(w_1, w_2)$ represents the probability of treatment assignment [propensity score,][]hahn1998role. This variance is minimized when applying the Neyman allocation for $(w_1, w_2)$. Notably, the Neyman allocation does not depend on which arm is the best, ensuring its effectiveness when $K = 2$.
Next, we consider the case where $K \geq 3$. In this scenario, assuming that the best arm is $a^\star(P_0) = a^\dagger \in [K]$, we test whether $a^\star(P_0) \neq a^\dagger$. If the null hypothesis is rejected, we accept the alternative hypothesis $a^\star(P_0) = a^\dagger$. To efficiently test this hypothesis using asymptotic properties, we aim to estimate the ATEs $\mu_{a^\dagger}(P_0) - \mu_a(P_0)$ for all $a\neq a^\dagger$ as efficiently as possible. A challenge arises because focusing solely on one arm $b\neq a^\dagger$ to estimate the ATE $\mu_{a^\dagger}(P_0) - \mu_b(P_0)$ efficiently may result in inefficient estimation of other ATEs $\mu_{a^\dagger}(P_0) - \mu_c(P_0)$ for $c\neq a^\dagger, b$. Therefore, we set the propensity score as \[ \bm{w}^* \coloneqq \operatorname*{arg\,min}_{\bm{w}\in\mathcal{W}}\max_{a\neq a^\dagger} \left\{ \frac{\sigma^2_{a^\dagger}(\mu_{a^\dagger}(P_0))}{w_{a^\dagger}} + \frac{\sigma^2_{a}(\mu_{a^\dagger}(P_0))}{w_a} \right\}. \] The minimizer $\bm{w}^*$ in this case is given by $\bm{w}^{\mathrm{GNA}}$ in the GNA algorithm. Thus, by setting the arm allocation probability to $\bm{w}^{\mathrm{GNA}}$, we can efficiently test whether $a^\star(P_0) \neq a^\dagger$.
This section examines the behavior of the GNA strategy when potential outcomes follow Bernoulli distributions, representing a specific case of the general results. Specifically, we consider the following model:
which is a subset of $\mathcal{P}_a$, with $\sigma_a(\mu) = \mu(1 - \mu)$ representing the variance of the Bernoulli outcomes.
In the case of two-armed Bernoulli bandits, the GNA strategy allocates arms uniformly, with the allocation ratio $w^{\mathrm{GNA}}_1 = w^{\mathrm{GNA}}_2 = \frac{1}{2}$. This uniform allocation occurs because the variances are identical under the small-gap regime. This result is consistent with the findings of Kaufman2016complexity and wang2023uniformly, which state that such a uniform allocation is optimal.
For multi-armed Bernoulli bandits with $K \geq 2$, the allocation ratio becomes
This allocation ratio depends on the best arm $a^\star(P_0)$, which is needed to be estimated.
The lower and upper bounds are given by
In Bernoulli bandits, we do not have to estimate the variances since, under the small-gap regime with the worst-case analysis, they are determined from the worst-case mean parameters. Additionally, the variances approach the same values as the gaps approach zero. Therefore, there is no need to estimate the variances. However, note that when $K \geq 3$, we need to estimate the best arm during the experiment.
Our results also address an open issue highlighted in Kasy2021corrigendum, which provides a correction to Kasy2021. The technical issue in Kasy2021 arises in their proof due to flipping $\mathrm{KL}(Q_a, P_a)$ and $\mathrm{KL}(P_a, Q_a)$, where $P_a$ is the true distribution and $Q_a$ is the alternative distribution. In their correction, they say that “An interesting question for future work will be to bound the differences (between $\mathrm{KL}(Q_a, P_a)$ and $\mathrm{KL}(P_a, Q_a)$) in the implied optimal allocations; in many settings, these will be very small.”
Our small-gap regime provides a case where these differences are indeed small. In this regime, while Kasy2021 proposes exploration sampling for BAI with Bernoulli outcomes using a Bayesian method to compute the allocation rule, we demonstrate that this method can be significantly simplified. As shown above, the allocation rule can be computed in closed form.
In this section, we investigate the empirical performance of our proposed GNA algorithm. We compare GNA with the Uniform-EBan algorithm Bubeck2011, which allocates arms with the GNA given known variances (GNA); an equal allocation ratio ($1/K$); the successive rejects algorithm Audibert2010; and the large-deviation optimal (GJ) algorithm proposed by glynn2004large
The GJ algorithm is an oracle algorithm that is proven to be asymptotically optimal in cases where we have full knowledge of the distributions, including mean parameters and the identity of the best arm. Note that this algorithm is practically infeasible. The GNA algorithm does not estimate variances but directly allocates arms according to the ratio $\bm{w}^{\mathrm{GNA}}$ using known variances.
Let $K \in \{3, 5\}$. The best arm is arm $1$ with $\mu_1 = \mu_1(P_0) = 1$. We consider two cases. In the first case, we set $\mu_a = \mu_a(P_0) = 0.95$ for all $a\in[K]\backslash\{1\}$. In the second case, we set $\mu_2 = \mu_2(P_0) = 0.95$ and choose $\mu_a = \mu_a(P_0)$ from a uniform distribution with support $[0.90, 0.95]$ for all $a\in[K]\backslash\{1, 2\}$.
The variances are given as a permutation of the set $\{\overline{\sigma}, \underline{\sigma}, \sigma_{(3)},\dots,\sigma_{(K)}\}$, where $\overline{\sigma}$ is chosen from $\{5, 10\}$, $\underline{\sigma} = 0.1$, and $\sigma_{(3)}$ is chosen from a uniform distribution with support $[\underline{\sigma}, \overline{\sigma}]$.
We investigate the performance for each $T\in\{100, 200, 300, \cdots, 49900, 50000\}$. We conduct $3000$ independent trials for each setting and compute the empirical probability of misidentification. We plot the empirical probability of misidentification $\widehat{p}$ in Tables (ref)--(ref) and Figures (ref)-- (ref). Note that the variance of the empirical probability of misidentification $\widehat{p}$ is $\widehat{p}(1 - \widehat{p})$. Thus, $\widehat{p}$ provides sufficient information about its distribution, so we do not show other graphs such as box plots and confidence intervals.
According to our results and existing studies, we theoretically expect the highest performance from the GJ algorithm, followed by the GNA algorithm in large samples. Our GNA algorithm follows these, with the other algorithms trailing.
Our empirical results align with theoretical expectations. The GNA algorithm tends to outperform the other methods, while the GJ is usually the best, which is an oracle algorithm, Additionally, as the variances are largeer, the GNA algorithm outperfoms the other more significantly. Interestingly, the GNA algorithm often outperforms the GJ algorithm. In finite samples, we observe cases where the SR and Uniform algorithms outperform the GJ and GNA algorithms. However, in large samples, the GJ and GNA algorithms tend to outperform them. This result implies that our proposed algorithms are asymptotically optimal but can be suboptimal in finite samples.
This study develops the GNA algorithm for the fixed-budget BAI problem. We demonstrate that the upper bound on its probability of misidentification aligns with the worst-case lower bound under the small-gap regime, providing an answer to a longstanding open problem regarding the existence of optimal algorithms in fixed-budget BAI, at least within a restricted distribution class. By restricting the class of distributions to the small-gap regime, we address the challenges posed by alternative lower bounds identified in existing studies Ariu2021, degenne2023existence.
The GNA algorithm represents a significant advancement in the theory of BAI. As a generalization of the Neyman allocation Neyman1934OnTT, it extends the applicability of this classical method beyond two-armed cases to multi-armed cases. By incorporating adaptive estimation and leveraging properties of the small-gap regime, our approach provides a natural and theoretically grounded solution to this extension. Furthermore, we resolve unresolved technical issues highlighted in previous works, such as those in Kasy2021,Kasy2021corrigendum, by demonstrating that the differences in KL divergence terms become negligible under the small-gap regime.
In addition to its theoretical contributions, the simplicity and adaptability of the GNA algorithm make it a promising approach for practical applications. The closed-form allocation rule derived under the small-gap regime offers computational advantages, enabling efficient implementation without requiring Bayesian methods or extensive computational resources.
For future work, it would be interesting to investigate the finite-sample properties of the GNA algorithm and explore finite-sample optimal algorithms. While our results establish asymptotic optimality, practical applications often operate under finite budgets where deviations from the theoretical results may occur. Investigating algorithms that optimize performance in such settings or incorporating robust allocation strategies could further enhance the practical utility of the GNA algorithm. Kato2020adaptive examine the finite-sample properties of the A2IPW algorithm using the law-of-iterated logarithms, which has been refined by cook2023semiparametric, using the concentration inequalities proposed by Balsubramani2016 and Howard2020TimeuniformNN. In the study of finite-sample optimal algorithms, the lower bound by Carpentier2016 is particularly insightful, as it has already been used in existing studies yang2022minimax,Ariu2021,degenne2023existence.
Another potential research direction is extending the analysis to cases with larger gaps. Additionally, exploring connections between the small-gap regime and other adaptive experimental designs could provide deeper insights into the generalizability of our approach.
In summary, this study contributes a theoretically optimal and practically implementable algorithm for fixed-budget BAI, offering both an answer to open theoretical questions and a foundation for future advancements in adaptive experimentation and BAI research.
\onecolumn