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.
87,133 characters · 24 sections · 156 citation commands
Worst-Case Optimal Multi-Armed Gaussian Best Arm Identification with a Fixed Budget
Experimental design is crucial in decision-making Fisher1935,Robbins1952. This study investigates scenarios involving multiple arms\footnote{The term 'arm' is used in the bandit literature lattimore2020bandit. There are various names for this concept, including 'treatment arms' Nair2019,Athey2017, 'policies' Kasy2021, 'treatments' Hahn2011, 'designs' chen2000, 'populations' glynn2004large, and 'alternatives' Shin2018.}, such as online advertisements, slot machine arms, diverse therapeutic strategies, and assorted unemployment assistance programs. The objective of an experiment is to identify the arm that yields the highest expected outcome (the best arm), while minimizing the probability of misidentification. This problem has been examined in various research areas under a range of names, including best arm identification Audibert2010, ordinal optimization Ho1992\footnote{Ordinal optimization often considers non-adaptive experiments, and BAI primarily addresses adaptive experiments. However, there are also studies on adaptive experiments in ordinal optimization and non-adaptive experiments in BAI.}, optimal budget allocation chen2000, and policy choice Kasy2021. We mainly follow the terminologies in BAI. BAI has two formulations: fixed-budget and fixed-confidence BAI; this study focuses on the fixed-budget BAI\footnote{The fixed-confidence BAI formulation resembles sequential testing, where a sample size is a random stopping time.}.
We consider a decision-maker who conducts an experiment with a fixed number of rounds $T$, referred to as a sample size or a budget, and a fixed set of arms $[K] \coloneqq {1,2,\dots, K}$. In each round $t \in [T] \coloneqq {1,2,\dots, T}$, the decision-maker allocates arm $A_t \in [K]$ to an experimental unit and immediately observes outcome $Y_t$ linked to the allocated arm $A_t$. The decision-maker's goal is to identify the arm with the highest expected outcome, minimizing the probability of misidentification at the end of the experiment.
\paragraph{Potential outcomes.} To describe the data-generating process, we introduce potential outcomes following the Neyman-Rubin model Neyman1923,Rubin1974. Let $P$ be a joint distribution of $K$-potential outcomes $(Y^1, Y^2, \dots, Y^K)$. Let $\mathbb{P}_{P}$ and $\mathbb{E}_{P}$ be the probability and expectation under $P$, respectively, and let $\mu^a(P) = \mathbb{E}_{P}[Y^a]$ be the expected outcome. Let $a^*(P) \coloneqq \operatorname*{arg\,max}_{a\in[K]}\mu^a(P)$ be the best arm under $P$, and $\mathcal{P}$ be the set of all possible joint distributions such that $a^*(P)$ is unique for all $P \in \mathcal{P}$. This study focuses on an instance $P\in\mathcal{P}$ where $(Y^1, Y^2, \dots, Y^K)$ follows a multivariate Gaussian distribution with a unique best arm $a^*(P)\in [K]$, defined as
where $\mathcal{N}(\mu, v)$ is a Gaussian distribution with a mean (expected outcome) $\mu \in \mathbb{R}$ and a variance $v > 0$, $\underline{\Delta}$ and $\overline{\Delta}$ are constants independent of $T$ such that they are lower and upper bounds for a gap $\mu^{a^*} - \max_{a\in[K]\backslash\{a^*\}}\mu^a$ ($0 < \underline{\Delta} \leq \overline{\Delta} < \infty$ holds), and $\underline{C}$ and $\overline{C}$ are unknown universal constants such that $0 < \underline{C} < \overline{C} < \infty$. Note that $\underline{C}$ and $\overline{C}$ are just introduced for a technical purpose to assume that $\left(\sigma^a\right)^2$ is bounded, and we do not use them in designing algorithms. We refer to $\mathcal{P}^{\mathrm{G}}(a^*, \underline{\Delta}, \overline{\Delta})$ as a Gaussian bandit model \footnote{Kaufman2016complexity considers a Gaussian bandit model $\mathcal{P} \coloneqq \Big\{\mathcal{P}^{\mathrm{G}}(a^*, \underline{\Delta}, \overline{\Delta}) \subset \mathcal{P} \mid \forall a^* \in [K] \Big\}$. In this study, we explicitly define the existence of universal constants $\underline{C}$, $\overline{C}$, $\underline{\Delta}$, and $\overline{\Delta}$. Although Kaufman2016complexity omits them, their results do not hold without such constants; that is, boundedness of the means and variances are essentially required. For example, if variances are zero or infinity, their lower bounds become infinity or zero. Additionally, under such cases, their proposed strategy ($\alpha$-Elimination) becomes ill-defined, since their allocation rule cannot be defined well.}
\paragraph{Experiment.} Let $P_0 \in \mathcal{P}^{\mathrm{G}}(a^*, \underline{\Delta}, \overline{\Delta})$ be an instance of bandit models that generates potential outcomes in an experiment, which is decided in advance of the experiment, and fixed throughout the experiment. The decision-maker knows the true values of the variances $((\sigma^a)^2)_{a\in[K]}$ but does not know $a^*$ and $(\mu^a)_{a\in[K]}$. We use $P_0$ when emphasizing the dependency on the data-generating process (DGP). An outcome in round $t\in[T]$ is $Y_t= \sum_{a\in[K]}\mathbbm{1}[A_t = a]Y^a_{t}$, where $Y^a_{t}\in\mathbb{R}$ is a potential independent outcome (random variable), and $(Y^1_{t}, Y^2_{t}, \dots, Y^K_{t})$ be an independent (i.i.d.) copy of $(Y^1, Y^2, \dots, Y^K)$ at round $t\in[T]$ under $P_0$. Then, we consider an experiment with the following procedure of a decision-maker at each round $t\in[T]$:
At the end of the experiment, the decision-maker estimates $a^*(P_0)$, denoted by $\widehat{a}_T \in [K]$. Here, an outcome in round $t\in[T]$ is $Y_t= \sum_{a\in[K]}\mathbbm{1}[A_t = a]Y^a_{t}$.
\paragraph{Probability of misidentification.} Our goal is to minimize the probability of misidentification, defined as \[\mathbb{P}_{P}( \widehat{a}_T \neq a^*(P)).\] To evaluate the exponential convergence of $\mathbb{P}_{P}( \widehat{a}_T \neq a^*(P))$ for any $P$, we employ the following measure, called the complexity: \[-\frac{1}{T}\log\mathbb{P}_{P}( \widehat{a}_T \neq a^*(P)).\] The complexity $-\frac{1}{T}\log \mathbb{P}_{ P }(\widehat{a}_T \neq a^*)$ has beeen widely employed in the literature on ordinal optimization and BAI glynn2004large,Kaufman2016complexity. In hypothesis testing, Bahadur1960 suggests the use of a similar measure to assess performances of methods in hypothesis testing. Also see Section (ref).
\paragraph{Strategy.} We define a strategy of a decision-maker as a pair of $((A_t)_{t\in[K]}, \widehat{a}_T)$, where $(A_t)_{t\in[K]}$ is the allocation rule, and $\widehat{a}_T$ is the recommendation rule. Formally, with the sigma-algebras $\mathcal{F}_{t} = \sigma(A_1, Y_1, \ldots, A_t, Y_t)$, a strategy is a pair $ ((A_t)_{t\in[T]}, \widehat{a}_T)$, where
We denote a strategy 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$. Let $\Pi$ be the set of all possible strategies.
This definition of strategies allows us to design adaptive experiments where we can decide $A_t$ using past observations. In this study, although we develop lower bounds that work for both adaptive and non-adaptive experiments,\footnote{Non-adaptive experiments are also referred to as static experiments. The difference between adaptive and non-adaptive experiments is the dependency on the past observations. In non-adaptive experiments, we first fix $\{A_t\}_{t\in[T]}$ at the beginning of an experiment and do not change it. Both in adaptive and non-adaptive experiments, $\widehat{a}_T$ depends on observations $\{(A_t, Y_t)\}^T_{t=1}$.} our proposed strategy is non-adaptive; that is, $A_t$ is decided without using observations obtained in an experiment. As we show later, our lower bounds depend only on variances of potential outcomes. By assuming that the variances are known, we design a non-adaptive strategy that is asymptotically optimal in the sense that its probability of misidentification aligns with the lower bounds. If the variances are unknown, we may consider estimating them during an experiment and using $\mathcal{F}_{t-1}$-measurable variance estimators at each round $t$. However, it is unknown whether an optimal strategy exists when we estimate variances during an experiment. We leave it as an open issue (Section (ref)).
\paragraph{Notation.} When emphasizing the dependency of the best arm on $P$, we denote it by $a^*(P) \coloneqq \operatorname*{arg\,max}_{a\in[K]}\mu^a(P)$. Let $\Delta^a(P) \coloneqq \mu^{a^*(P)}(P) - \mu^a(P)$. For $P\in\mathcal{P}$, let $P^a$ be a distribution of a reward of arm $a\in[K]$.
The existence of optimal strategies in fixed-budget BAI has been a longstanding issue, which is related to tight lower bounds and corresponding optimal strategies.
To discuss tight lower bounds, we consider restricting a class of strategies. Following the existing studies such as Kaufman2016complexity, we focus on consistent strategies that recommend the true best arm with probability one as $T \to \infty$.
Kaufman2016complexity discusses lower bounds for both fixed-budget and fixed-confidence BAI and presents lower bounds for two-armed Gaussian bandits in fixed-budget BAI. Based on their arguments, Garivier2016 presents a lower bound and optimal strategy for fixed-confidence BAI. They also conjecture a lower bound for fixed-budget BAI as $-\frac{1}{T}\log\mathbb{P}_{P}( \widehat{a}_T \neq a^*(P)) \leq \max_{w\in\mathcal{W}}\Gamma^*(P, w)$ for all $P\in\widetilde{\mathcal{P}}$ for some well-defined bandit models $\mathcal{P}$,\footnote{In a more rigorous analysis, we should use $\sup_{w\in\mathcal{W}}\Gamma^*(P, w)$ and then discuss the existence of the maximum. However, for simplicity, we use $\max_{w\in\mathcal{W}}\Gamma^*(P, w)$ in literature review.}\footnote{Note that lower bounds (resp. upper bounds) for $\mathbb{P}_{P}( \widehat{a}^\pi_T \neq a^*)$ corresponds to upper bounds (resp. lower bounds) for $ -\frac{1}{T}\log \mathbb{P}_{P}( \widehat{a}^\pi_T \neq a^*)$.} where
where $\widetilde{\mathrm{KL}}$ denotes the KL divergence between two distributions parameterized by mean parameters, and $\mathcal{W}$ is the probablity simplex defined as \[\mathcal{W} = \left\{w:[K] \to (0, 1)\mid \sum_{a\in[K]}w(a) = 1\right\}.\] This conjectured lower bound is a straightforward extension of the basic tool developed by Kaufman2016complexity and an analogy of the lower bound for fixed-confidence BAI shown by Garivier2016. However, while a lower bound for two-armed Gaussian bandits is derived for any consistent strategies, this lower bound cannot be derived only under the restriction of any consistent strategies. Summarizing these early discussions, kaufmann2020hdr clarifies the problem and points out that there exists the reverse KL divergence problem, which makes the derivation of the lower bound difficult.
Following these studies, the existence of optimal strategies is discussed by Kasy2021 and Ariu2021. Ariu2021 proves that there exists a distribution $P$ under which a lower bound is larger than the conjectured lower bound $\max_{w\in\mathcal{W}}\Gamma^*(P, w)$ by showing that for any strategies, \[\exists P \in \mathcal{P},\ -\frac{1}{T}\log\mathbb{P}_{P}( \widehat{a}_T \neq a^*(P)) \leq \frac{800}{\log(K)}\sup_{w\in\mathcal{W}} \Gamma^*(P, w),\] where $\frac{800}{\log(K)}\sup_{w\in\mathcal{W}} \Gamma^*(P, w) \leq \sup_{w\in\mathcal{W}} \Gamma^*(P, w)$ holds when $K$ is sufficiently large. Qin2022open summarizes these arguments as an open question.
Komiyama2022 tackles this problem by considering the minimax evaluation of $\limsup_{T \to \infty} -\frac{1}{T}\log \mathbb{P}_{P}( \widehat{a}^\pi_T \neq a^*(P))$, defined as \[\inf_{P\in\mathcal{P}}H(P)\liminf_{T\to \infty}-\frac{1}{T}\log\mathbb{P}_{P}( \widehat{a}_T \neq a^*),\] where $H(P)$ represents the difficulty of the problem $P$. See Komiyama2022 for a more detailed definition. This approach allows us to avoid the reverse KL problem in the lower bound derivation.
degenne2023existence explores the open question and shows that for any consistent strategies, a lower bound is given as $\inf_{P\in\mathcal{P}}H(P)\liminf_{T\to \infty}-\frac{1}{T}\log\mathbb{P}_{P}( \widehat{a}_T \neq a^*) \leq \max_{w\in\mathcal{W}}\Lambda^*(P, w, H)$ for any $P\in\widetilde{\mathcal{P}}$, where \[\Lambda^*(P, w, H) \coloneqq \inf_{\mu^{a} < v^a < \mu^{a^*(P)}}H(P)\sum_{a\in[K]}w(a)\widetilde{\mathrm{KL}}\big(v^a, \mu^{a}(P)\big).\] Note that degenne2023existence's lower bound is tighter than Komiyama2022's.
A candidate of an optimal strategy is the one proposed by glynn2004large, which is feasible only when we know the full information about the DPG $P_0$. Although their upper bound aligns with the conjectured lower bound $\max_{w\in\mathcal{W}}\Gamma^*(P, w)$, it does not match the lower bounds by Ariu2021 and degenne2023existence for any consistent strategies. One of the reason for this difference is the knowledge about the DGP $P_0$; if we do not have the full information and need to estimate it, the upper bound does not match $\max_{w\in\mathcal{W}}\Gamma^*(P, w)$ for the estimation error about the information.
To fill this gap between the lower and upper bounds, we and degenne2023existence consider restricting the strategy class to asymptotically invariant (static) strategies, in addition to consistent strategies. For an instance $P\in\mathcal{P}$ and a strategy $\pi\in\Pi$, let us define an average sample allocation ratio $\kappa^\pi_{T, P}:[K]\to (0,1)$ as $\kappa^\pi_{T, P}(a) \coloneqq \mathbb{E}_{P}\left[\frac{1}{T}\sum^T_{t=1} \mathbbm{1}[A^\pi_t = a]\right]$, which satisfies $\sum_{a\in[K]}\kappa^\pi_{T, P}(a) = 1$. This quantity represents the average sample allocation to each arm $a$ over a distribution $P\in\mathcal{P}^{\mathrm{G}}(a^*, \underline{\Delta}, \overline{\Delta})$ under a strategy $\pi$. Then, we define asymptotically invariant strategies as follows.\footnote{Note that degenne2023existence independently considers a similar class of strategies and refers to them as static strategies. degenne2023existence considers strategies that are completely independent of the DGP $P_0$, while we consider strategies that are asymptotically independent of $P_0$. This is because we aim to include strategies that estimate the variance from $P_0$ under a bandit model with fixed variances. Therefore, we keep our terminology.}
Asymptotically invariant strategies allocate arms with the proportion $w^\pi$ under any distribution $P \in \mathcal{P}^{\mathrm{G}}(a^*, \underline{\Delta}, \overline{\Delta})$ as $T$ approaches infinity (see Definition (ref)); that is, the strategies does not depend on the DGP $P_0$ asymptotically.
degenne2023existence shows that any consistent and asymptotically invariant strategies $\pi$ satisfy
where $\widetilde{\mathcal{P}}\subset \mathcal{P}$ is a well-defined general bandit models, while any strategies $\pi$ satisfy
where $\mathcal{P}^{\mathrm{G}}_{\sigma=1} \coloneqq \Big\{\mathcal{P}^{\mathrm{G}}(a^*, \underline{\Delta}, \overline{\Delta}) \subset \mathcal{P} \mid \forall a^* \in [K],\ \ \forall a \in [K]\ \ \sigma^a = 1\Big\}$.
Note that although the lower bound is given as $\max_{w\in\mathcal{W}}, \Gamma(P, w)$, the allocation should be constructed to be independent of $P_0$ due to the definition of asymptotically invariant strategies. We can still define the allocation as $w^* = \operatorname*{arg\,max}_{w\in\mathcal{W}}, \Gamma(P_0, w)$ for the DGP instance $P_0$. However, we can construct $w^*$, depending on $P_0$. In this sense, the meaning of a strategy implied from the lower bound of degenne2023existence will be significantly different from the strategy by glynn2004large, although they look similar.
This result implies that for any strategies $\pi$ and the problem difficulty defined as $H(P) = \Big(\max_{w\in\mathcal{W}}, \Gamma(P, w)\Big)^{-1}$, \[\inf_{P\in\mathcal{P}}H(P)\liminf_{T\to \infty}-\frac{1}{T}\log\mathbb{P}_{P}( \widehat{a}^\pi_T \neq a^*) < 1,\] holds; that is, $\max_{w\in\mathcal{W}}, \Gamma(P, w)$ is unattainable unless we assume the access to the full information about the DGP $P_0$.
We list the open questions raised in Kaufman2016complexity, Garivier2016, kaufmann2020hdr, Kasy2021, Ariu2021, Qin2022open, degenne2023existence, and wang2023uniformly. We also summarize related arguments below to clarify what has been elucidated and what remains unelucidated.\footnote{degenne2023existence also raises another open question in his Section 4, which focuses on Bernoulli bandits. Because this study focuses on Gaussian bandits, we omit introducing the open question.}
There are several impossibility theorems for this open question, as follows:
Here, $\Gamma^*(P, w)$ corresponds to an upper bound of the strategy proposed by glynn2004large and a lower bound of consistent strategies shown by Kaufman2016complexity. Note that glynn2004large requires full information about bandit models, including the mean parameters. They show that there is an instance $P\in\mathcal{P}$ such that its lower bound is larger than $\max_{w\in\mathcal{W}}\Gamma^*(P, w)$.
A next open question is whether there is a strategy whose probability of misidentification is smaller than those using uniform allocation (allocating arms with equal sample sizes; that is, $\kappa^\pi_{T, P} = 1/K$ for all $a\in[K]$ and any $P\in\mathcal{P}$). For consistent strategies, Kaufman2016complexity notes that a strategy using the uniform allocation is nearly optimal when outcomes follow two-armed Bernoulli bandits. Furthermore, they show that a strategy allocating arms in proportion to the standard deviations of outcomes is asymptotically optimal in two-armed Gaussian bandits if the standard deviations are known. Such a strategy, known as the Neyman allocation, is conjectured or shown to be optimal in various senses under Gaussian bandits Neyman1934OnTT,Hahn2011,glynn2004large,Kaufman2016complexity,adusumilli2022minimax.
Lastly, we introduce an open question about the asymptotically invariant strategy. The open question is whether a strategy that outperforms the asymptotically invariant strategy exists. This problem is raised by existing studies such as degenne2023existence and wang2023uniformly. From its definition, the asymptotically invariant strategy cannot depend on $P$. Therefore, as we point out in Sections (ref) and (ref), such a strategy would be the uniform allocation or depend on some parameters invariant across $P$. Specifically, in Sections (ref) and (ref), we find that the best arm itself should be known in advance of an experiment. degenne2023existence uses such a strategy as a baseline and compares feasible strategies to it. As a result, degenne2023existence shows that there exists $P$ under which the probability of misidentification of any strategies cannot align with the lower bound.
This section provides our main results. In fixed-budget BAI, the following problems have not been fully explored:
This study tackles these problems by providing the following results:
In this section, we first show the lower bound in Section (ref). Then, based on the lower bound, we develop a non-adaptive strategy in
In Section (ref), we derive lower bounds for strategies based on available information. Specifically, we focus on how the available information affects lower bounds and the existence of strategies whose probability of misidentification aligns with these lower bounds. We find that lower bounds depend significantly on the amount of information available regarding the distribution of rewards for arms prior to the experiment.
From the information theory, we can relate the lower bounds to the Kullback–Leibler (KL) divergence $\mathrm{KL}(Q^a, P^a_0)$ between the DGP $P_0\in\mathcal{P}$ and an alternative hypothesis $Q\in\cup_{b \neq a^*}\mathcal{P}(b, \underline{\Delta}, \overline{\Delta})$ Lai1985,Kaufman2016complexity. From the lower bounds, we can compute an ideal expected number of times arms are allocated to each experimental unit; that is, $\kappa^\pi_{T, P_0}$. When the lower bounds are linked to the KL divergence, the corresponding ideal sample allocation rule also depends on the KL divergence glynn2004large.
If we know the distributions of arms' outcomes completely, we can compute the KL divergence, which allows us to design a strategy whose probability of misidentification matches the lower bounds of Kaufman2016complexity as $T\to \infty$ glynn2004large,chen2000,Gartner1977,Ellis1984. However, the full information requires us to know which arm is the best arm, and without the knowledge, the strategy is infeasible. Since optimal strategies are characterized by distributional information, the lack of full information hinders us from designing asymptotically optimal strategies. Therefore, we reflect the limitation by considering the worst cases regarding the mean parameters and the choice of the best arm. Specifically, we consider the worst-case lower bound defined as \[\inf_{P\in\cup_{a^*\in[K]}\mathcal{P}^{\mathrm{G}}(a^*, \underline{\Delta}, \overline{\Delta})}\limsup_{T \to \infty} -\frac{1}{T}\log \mathbb{P}_{P}( \widehat{a}^\pi_T \neq a^*(P)).\] While the lower bounds with full information are characterized by the KL divergence Lai1985,Kaufman2016complexity, the worst-case lower bounds are characterized by the variances of potential outcomes. Hence, knowledge of at least the variances is sufficient to design worst-case optimal strategies.
Then, the following theorem provides a worst-case lower bound. The proof is shown in Appendix (ref).
Additionally, in Section (ref), we discuss that a lower bound for any consistent strategies is the same as that for any consistent and asymptotically invariant strategies when we consider the worst-case lower bound characterized by $\overline{\Delta}$.
Based on the lower bounds, we design a strategy and show that its probability of misidentification aligns with the lower bounds. In the experimental design, we assume that the variances of outcomes are known. Then, we propose the Generalized-Neyman-Allocation (GNA)-empirical-best-arm (EBA) strategy, which can be interpreted as a generalization of the Neyman allocation proposed by Neyman1934OnTT. The pseudo-code is shown in Algorithm (ref).
\paragraph{Allocation rule: Generalized Neyman Allocation (GNA).} First, we define a target allocation ratio, which is used to determine our allocation rule, as follows:
which is identical to that in (ref). Then, we allocate arms to experimental units as follows:
\paragraph{Recommendation rule: Empirical Best Arm (EBA).} After the final round $T$, we recommend $\widehat{a}_T \in [K]$, an estimate of the best arm, defined as
Our strategy generalizes the Neyman allocation because for $w^{\mathrm{GNA}} $ in the GNA allocation rule, $w^{\mathrm{GNA}} = \left(\frac{\sigma^1}{\sigma^1 + \sigma^2},\ \frac{\sigma^2}{\sigma^1 + \sigma^2}\right)$ when $K=2$, which is a target allocation ratio of the Neyman allocation. The EBA recommendation rule is one of the typical recommendation rules and used in other strategies in fixed-budget BAI, such as the Uniform-EBA strategy Bubeck2009,Bubeck2011.
This section shows an upper bound for the probability of misidentification of the GNA-EBA strategy. The proof is shown in Appendix (ref).
Then, the worst-case upper bound is given as the following theorem.
By comparing the lower bound in Theorem (ref) and the upper bound in Theorem (ref), the following theorem shows that they approach as $\underline{\Delta} - \overline{\Delta} \to 0$ and match when $\underline{\Delta} = \overline{\Delta}$. This case implies a situation in which the difference between the expected outcome of the best arm and the next best arm is equal to the difference between the expected outcome of the best arm and the worst arm. In such a situation, it is possible to construct an optimal algorithm even if the expected outcomes are unknown. This concept is illustrated in Figure (ref).
This result implies that $\inf_{P\in\overline{\mathcal{P}}^{\mathrm{G}}(\Delta)}\max_{w\in\mathcal{W}}\Gamma^*(P, w)$ is lower and upper bounds for any consistent strategies ($\mathrm{LowerBound}(\overline{\Delta}) = \mathrm{UpperBound}(\underline{\Delta}) = \inf_{P\in\overline{\mathcal{P}}^{\mathrm{G}}(a^*, \Delta)}\max_{w\in\mathcal{W}}\Gamma^*(P, w)$), although there exists $P \in \mathcal{P}^{\mathrm{G}}_{\sigma=1}$ such that a lower bound is larger than $\max_{w\in\mathcal{W}}\Gamma^*(P, w)$ degenne2023existence. Thus, without contradicting the existing results by Ariu2021 and degenne2023existence, we show the existence of an optimal strategy for a lower bound conjectured by Kaufman2016complexity and Garivier2016. We illustrate this result in Figure (ref). Our findings do not present a contradiction to the results by Ariu2021 and degenne2023existence because we restrict the bandit models.
Additionally, when $\underline{\Delta} = \overline{\Delta}$ and the variances are known, we design an asymptotically worst-case optimal strategy, which is not based on the uniform allocation.
Note that our optimality criterion is closely related to local optimality that has been used in various studies, including the bandit problem and statistical testing. For example, the optimality under a small-gap setting such that $\mu^{a^*(P)}(P) - \mu^a(P) \to 0$ for all $a\in [K]\backslash\{a^*\}$ is a particular case of our optimality. Such a small-gap optimality has been discussed in Jamieson2014 and Shin2018, where the former is a study about fixed-confidence BAI, and the latter is about fixed-budget BAI. The local Bahadur efficiency is also a closely related optimality criterion, which has been used in the literature of statistical testing Wieand1976,Akritas1988187,He1996. In many cases, such a location has been employed to discuss the optimality of the main performance measure while ignoring estimation errors of other parameters.
From the viewpoints of open questions, we answer them as follows:
As a side-product of our study, we propose a novel setting called hypothesis BAI (HBAI) in Section (ref). The results shown above consider a lower bound that is valid for any choices of the mean parameters and the best arm, reflecting a situation where they are unknown. However, we can consider a situation where there is a conjecture of the best arm prior to an experiment. For example, as well as hypothesis testings, we can set null and alternative hypotheses such that a conjectured best arm $\widetilde{a} \in [K]$ is truly best (alternative) or not (null). Under this setting, if we set $\widetilde{a}$ as a proxy of $a^*$ and conduct an experiment, then the probability of minimization is minimized when $\widetilde{a} = a^*$ (the alternative hypothesis is true). As an analogy of hypothesis testing, we call this setting HBAI.
Results of simulation studies are shown in Section (ref). We discuss related work in Appendix (ref). In Appendix (ref), we explain intuitive ideas about the lower bounds, which include the preliminary of the proof of Theorem (ref).
Finally, we discuss our results in comparison to existing results. This section aims to clarify our study's contribution by showing how we approach the open question raised in existing studies. \paragraph{Comparison with Komiyama2022 and degenne2023existence.} First, we compare our results with those in Komiyama2022 and degenne2023existence. While Komiyama2022 and degenne2023existence measure a performance by $\inf_{P\in\mathcal{P})}H(P)\limsup_{T \to \infty} -\frac{1}{T}\log \mathbb{P}_{P}( \widehat{a}^\pi_T \neq a^*)$, we measure it by $\inf_{P\in\mathcal{P})}\limsup_{T \to \infty} -\frac{1}{T}\log \mathbb{P}_{P}( \widehat{a}^\pi_T \neq a^*)$, where the main difference is the existence of the problem difficulty term $H(P)$. degenne2023existence shows a lower bound $\inf_{P\in\mathcal{P}}H(P)\liminf_{T\to \infty}-\frac{1}{T}\log\mathbb{P}_{P}( \widehat{a}_T \neq a^*) \leq \max_{w\in\mathcal{W}}\Lambda^*(P, w, H)$, which is tighter than the lower bound in Komiyama2022. We compare this lower bound to ours. Let us consider a case $H(P)$ is constant independent of $P$ and $T$; that is, $H(P) = \overline{H}$ holds for a constant $\overline{H}$ independent of $P$ and $T$. Then, from degenne2023existence's lower bound, we have $\inf_{P\in\mathcal{P}}\liminf_{T\to \infty}-\frac{1}{T}\log\mathbb{P}_{P}( \widehat{a}_T \neq a^*) \leq \inf_{\mu^{a} < v^a < \mu^{a^*(P)}}\sum_{a\in[K]}w(a)\widetilde{\mathrm{KL}}\big(v^a, \mu^{a}(P)\big) \leq \mathrm{LowerBound}(\overline{\Delta})$, which aligns with our lower bound. This difference comes from how we interpret the difficulty of the problem of interest. degenne2023existence considers a lower bound under $\mathcal{P}$, instead of introducing some difficulty term $H(P)$. In contrast, we consider a lower bound that matches the upper bound when $\overline{\Delta} - \underline{\Delta} \to 0$, which implies that we restrict the class of $\mathcal{P}$ when considering the asymptotic optimality.
\paragraph{Asymptotically invariant Strategy.} In fixed-budget BAI, the strategy proposed by glynn2004large has been considered a candidate for asymptotically optimal strategies. We and degenne2023existence show that it is actually an asymptotically optimal strategy among a class of consistent and asymptotically invariant (static) strategies. degenne2023existence proves that there exists $P\in\mathcal{P}$ under which a lower bound for consistent strategies does not match that for consistent and asymptotically invariant (static) strategies. In contrast, in the following corollary, we show that under the worst-case analysis, the lower bound for consistent strategy is the same as that for consistent and asymptotically invariant (static) strategies, and the upper bound of the GNA-EBA strategy matches the lower bound. This result implies that (i) we cannot obtain a strategy with a smaller probability of misidentification even if relaxing the class of strategies, and (ii) there exists an asymptotically optimal strategy, at least if we know variances. This result challenges the conclusion of degenne2023existence, which states that there exists no optimal strategy in the sense that its upper bound aligns with that of asymptotically invariant strategies. Our result does not contradict to his result because we restrict the bandit models $\mathcal{P}$, rather than the strategy class.
\paragraph{Matching lower and upper bounds.} Instead of considering restricted bandit models ($\overline{\Delta} - \underline{\Delta} \to 0$), we develop tight lower and upper bounds that match as $\overline{\Delta} - \underline{\Delta} \to 0$. degenne2023existence considers a lower bound characterized by a problem difficulty terms, where there is a gap from upper bounds. In other words, we derive matching lower and upper bounds for restricted bandit models under $\overline{\Delta} - \underline{\Delta} \to 0$, while degenne2023existence derives a lower bound whose leading factor aligns with an upper bound (but it is not a perfect match) for global bandit models $\mathcal{P}$ (there is no restriction such that $\overline{\Delta} - \underline{\Delta} \to 0$).
\paragraph{Applications of interest.} Thus, there are two frameworks, asymptotic optimality for restricted bandit models and that depending on the problem difficulty. The former is closely related to large-deviation-based asymptotically optimal strategies such as glynn2004large, while the latter is closely related to the standard fixed-budget BAI strategies such as the successive halving. The remaining question is which framework is appropriate, and it depends on applications. The asymptotic optimality for restricted bandit models is often considered in epidemiology and economics, where the number of arms is not large, and we need to identify the best arm among the other arms whose expected outcomes are close to but less than that of the best arm. For example, Laan2008TheCA and Hahn2011 consider local models, where parameters have $1/\sqrt{T}$-perturbation Vaart1998, and discuss asymptotic optimality in such models. In contrast, the use of optimality based on the problem difficulty is appropriate for recommendation systems and online advertisements, where the number of arms is significantly large. In this case, as well as the successive halving, it is desirable to remove suboptimal arms as early as possible, depending on how fast and accurately we can remove them depending on the problem difficulty.
This section provides intuitive ideas behind Theorem (ref) and Corollary (ref) with preliminaries for their proofs. Our arguments about lower bounds are based on the information-theoretical approach. We reveal that different available information yields different lower bounds. Finally, we develop the worst-case lower bound for multi-armed Gaussian bandits.
The existence of asymptotically optimal strategies is a longstanding open question kaufmann2020hdr,Ariu2021,degenne2023existence. Kaufman2016complexity provide a lower bound and an asymptotically optimal strategy for two-armed Gaussian bandits with known variances. However, when the number of arms is three or more ($K\geq 3$), even the lower bounds remain unknown (see Table (ref)).
There are multiple reasons why this problem is challenging, and it is difficult to offer a single clear explanation. For instance, factors affecting the upper bounds of strategies include (i) the estimation error of distributional information, (ii) the class of strategies, and (iii) the dependency of optimal sample allocation ratios on the best arm.
To address this problem, we develop novel lower bounds by extending those shown by Kaufman2016complexity, focusing on the lack of distributional information.
Our arguments about lower bounds start from a (conjectured) lower bound shown by Kaufman2016complexity and Garivier2016.
Here, $Q$ is an alternative hypothesis that is used for deriving lower bounds and not an actual distribution. Note that upper (resp. lower) bounds for $- \frac{1}{T}\log \mathbb{P}_{P_0}(\widehat{a}^\pi_T \neq a^*)$ corresponds to lower (resp. upper) bounds for $ \mathbb{P}_{P_0}(\widehat{a}^\pi_T \neq a^*)$.
For two-armed Gaussian bandits, the lower bound can be simplified (See Theorem 12 in Kaufman2016complexity). In this case, it is known that by allocating arm $1$ and $2$ with sample sizes $\frac{\sigma^1}{\sigma^1 + \sigma^2} T$ and $\frac{\sigma^2}{\sigma^1 + \sigma^2} T$, we can design asymptotically optimal strategy. Strategies using this allocation rule are called the Neyman allocation Neyman1934OnTT.
However, when $K \geq 3$, there occur several issues in the derivation of lower bounds, and there does not exist an asymptotically optimal strategy whose upper bound aligns with the conjectured lower bound in Lemma (ref) kaufmann2020hdr,Ariu2021,degenne2023existence. One of the difficulties comes from the fact that the term $\kappa^\pi_{T, Q}(a)$ does not correspond to sample allocation under the DGP $P_0$ kaufmann2020hdr, which incurs a problem called the reverse KL problem kaufmann2020hdr.
To derive lower bounds, we consider restricting strategies to ones such that the limit of $\kappa^\pi_{T, P}(a)$ ($\lim_{T\to\infty}\kappa^\pi_{T, P}(a)$) is the same across $P\in\mathcal{P}^{\mathrm{G}}(a^*, \underline{\Delta}, \overline{\Delta})$. Such a class of strategies are defined as asymptotically invariant strategies in Definition (ref). Note that $\kappa^\pi_{T, P}$ is a deterministic value without randomness because it is an expected value of $\frac{1}{T}\sum^T_{t=1} \mathbbm{1}[A^\pi_t = a]$. A typical example of this class of strategies is one using uniform allocation, such as the Uniform-EBA strategy Bubeck2011. Another example is a strategy using the allocation rule only based on variances, such as the Neyman allocation Neyman1934OnTT.
Given an asymptotically invariant strategy $\pi$, there exists $w^\pi\in \mathcal{W}$ such that for all $P\in\mathcal{P}^{\mathrm{G}}(a^*, \underline{\Delta}, \overline{\Delta})$, and $a\in[K]$, $\left|w^\pi(a) - \frac{1}{T}\sum^T_{t=1}\mathbb{E}_P\left[\mathbbm{1}[A_t = a]\right]\right| \to 0$ holds.
Therefore, for any consistent and asymptotically invariant strategy $\pi$, the following lower bounds hold. The proof is shown in Appendix (ref).
We refer to a limit of the average sample allocation deduced from lower bounds as the target allocation ratio and denote it by $w^*$. We can derive various $w^*$ in different lower bounds. For example, in Lemma (ref), because $\max_{w\in\mathcal{W}}\min_{a\in[K]\backslash\{a^*\}}\inf_{\stackrel{(\mu^b)\in\mathbb{R}^K}{\mu^a > \mu^{a^*}}}w(a)\frac{\left(\mu^a - \mu^a(P_0)\right)^2}{2\left(\sigma^a\right)^2}$ exists, we define the target allocation ratio as
The target allocation ratio $w^*$ works as a candidate about optimal sample allocation of optimal strategies. Here, note that the average sample allocation ratio is linked to an actual strategy, and we can compute $w^*$ independently of each instance $P_0$.
For the asymptotically invariant strategy, we can show that the strategy proposed by glynn2004large is feasible if we can compute $\mathrm{KL}(Q^a, P^a_0)$, and under the strategy, the probability of misidentification aligns with the lower bound with asymptotically invariant strategies. This result is also shown by degenne2023existence for more general distributions.
As discussed by glynn2004large and us, when we know distributional information completely, we can obtain an asymptotically optimal strategy whose probability of misidentification matches the lower bounds in Lemma (ref). However, when we do not have full information, the strategy by glynn2004large is infeasible. Furthermore, there exists $P_0\in\mathcal{P}^{\mathrm{G}}(a^*, \underline{\Delta}, \overline{\Delta})$ whose lower bound is larger than that of Kaufman2016complexity.
For example, in Lemma (ref), the target allocation ratio is given as (ref). However, the target allocation ratio depends on unknown mean parameters $\mu^a(P_0)$ and the true best arm $a^*$. Therefore, strategies using the target allocation ratio are infeasible if we do not know those values.
We elucidate this problem by examining how our available information affects the lower bounds. Specifically, we consider lower bounds that are uniformly valid regardless of the missing information. First, we consider characterizing the lower bound in Lemma (ref) by $\overline{\Delta}$, an upper bound of $\Delta^a(P_0)$ as the following lemma.
The proof is shown in Appendix (ref). Here, the target allocation ratio is given as
Note that the lower bounds are characterized by the variances and the true best arm $a^*$. If we know them, we can design optimal strategies whose upper bound aligns with these lower bounds.
When designing strategies, variances and the best arm are required to construct the target allocation ratio. However, assuming that the best arm $a^*$ is known is unrealistic. We also cannot estimate it during an experiment because such a strategy violates the assumption of asymptotically invariant strategies. For example, Shin2018 estimates $a^*$ during an experiment under the framework of glynn2004large, but such a strategy does not satisfy the asymptotically invariant strategies because $a^*$ and $w^*$ can differ across the choice of $P_0$. When considering asymptotically invariant strategies, we need to know $a^*$ before starting an experiment.
To circumvent this issue, one approach is to fix $\widetilde{a}$, independent of $P_0$, before an experiment. We then construct a target allocation ratio as $w^\dagger(\tilde{a}) = \frac{\sigma^{\tilde{a}}}{\sigma^{\tilde{a}} + \sqrt{\sum_{b\in[K]\backslash{\tilde{a}}}\left(\sigma^b\right)^2}}$ and $w^\dagger(a) =(1 - w^\dagger(\tilde{a}))\frac{\left(\sigma^a\right)^2}{\sum_{b\in[K]\backslash{\tilde{a}}}\left(\sigma^b\right)^2}$ for all $a \in [K]\backslash{\tilde{a}}$. arms are then allocated following this target allocation ratio. Under a strategy using such an allocation rule, if $\widetilde{a}$ equals $a^*$, the target allocation ratio $w^\dagger$ aligns with $w^*$ in (ref). We refer to this setting as hypothesis BAI (HBAI), as the formulation resembles hypothesis testing. For details, see Section (ref).
However, when $\widetilde{a}$ is not equal to $a^*$, the target allocation ratio $w^\dagger$ does not equal $w^*$, under which the strategy becomes suboptimal. In the following section, we consider a best-arm agnostic lower bound by contemplating the worst-case scenario for the choice of $a^*$.
As discussed above, $a^*$ is unknown in practice, and we consider the worst-case analysis regarding the choice of the best arm. We represent the worst-case for all possible best arms by using the following metric: \[\inf_{P_0\in\cup_{a^*\in[K]}\mathcal{P}^{\mathrm{G}}(a^*, \underline{\Delta}, \overline{\Delta})}\limsup_{T \to \infty} -\frac{1}{T}\log \mathbb{P}_{P_0}( \widehat{a}^\pi_T \neq a^*(P)).\] Thus, by taking the worst case over $P_0$, we obtain the following lower bound.
The target allocation ratio deduced from this lower bound is
Here, note that $\max_{w\in\mathcal{W}}\max_{a^*\in[K]}\min_{ a\in[K]\backslash\{a^*\}}\frac{\underline{\Delta}^2}{2\Omega^{a^*, a}(w)}$ does not have a closed-form solution and requires numerical computations.
Note that when $K = 2$, the target allocation ratio has a closed-form solution such that $w^*(a) = \frac{\sigma^a}{\sigma^1 + \sigma^2}$ for $a\in[2]$. Additionally, the lower bound is given as
This target allocation ratio and lower bound are equal to those in the lower bound for two-armed Gaussian bandits shown by Kaufman2016complexity.
The target allocation ratio is independent of $a^*$. Therefore, we can avoid the issue of dependency on $a^*$, which cannot be estimated in an experiment.
In Theorem (ref), we restrict the strategies to consistent and asymptotically invariant ones. However, the latter restriction can be removed. We introduced the restriction of asymptotically invariant strategies to derive a lower bound from $\limsup_{T \to \infty} - \frac{1}{T}\log \mathbb{P}_{P_0}(\widehat{a}^\pi_T \neq a^*) \leq \limsup_{T \to \infty}\inf_{Q\in\cup_{b \neq a^*}\mathcal{P}(b, \underline{\Delta}, \overline{\Delta})}\sum_{a\in[K]} \kappa^\pi_{T, Q}(a)\mathrm{KL}(Q^a, P^a_0)$ in Lemma (ref). Although we discussed $\inf_{P_0\in\cup_{a^*\in[K]}\mathcal{P}^{\mathrm{G}}(a^*, \underline{\Delta}, \overline{\Delta})}\limsup_{T \to \infty} -\frac{1}{T}\log \mathbb{P}_{P_0}( \widehat{a}^\pi_T \neq a^*(P))$ as a result of information-theoretical analysis, we can derive a lower bound from \[\inf_{Q\in\cup_{a^*\in[K]}\mathcal{P}^{\mathrm{G}}(a^*, \underline{\Delta}, \overline{\Delta})}\limsup_{T \to \infty} -\frac{1}{T}\log \mathbb{P}_{Q}( \widehat{a}^\pi_T \neq a^*(Q)) \leq \limsup_{T \to \infty}\inf_{Q\in\cup_{b \neq a^*}\mathcal{P}(b, \underline{\Delta}, \overline{\Delta})}\sum_{a\in[K]} \kappa^\pi_{T, P_0}(a)\mathrm{KL}(P^a_0, Q^a).\] This metric is mathematically equivalent to $\inf_{P_0\in\cup_{a^*\in[K]}\mathcal{P}^{\mathrm{G}}(a^*, \underline{\Delta}, \overline{\Delta})}\limsup_{T \to \infty} -\frac{1}{T}\log \mathbb{P}_{P_0}( \widehat{a}^\pi_T \neq a^*(P))$, but we can derive a lower bound without using the asymptotically invariant strategy restriction. This is because $\kappa^\pi_{T, P_0}(a)$ appears in the lower bound, instead of $\kappa^\pi_{T, Q}(a)$.
We show the lower bound in Theorem (ref) and the proof in Appendix (ref).
Additionally, from the lower bounds in Theorems (ref) and (ref) and the upper bound in Theorem (ref), we obtain Corollary (ref). This corollary implies that when $\overline{\Delta} = \underline{\Delta}$, we can obtain an asymptotically optimal strategy if we know variances.
Based on the arguments in Section (ref), we design the Hypothesis GNA-EBA (H-GNA-EBA) strategy that utilizes a conjecture $\widetilde{a}\in[K]$ of $a^*$, instead of considering the worst-case for $a^*$. We refer to $\widetilde{a}$ as a hypothetical best arm.
In the H-GNA-EBA strategy, we define a target allocation ratio as $w^{\mathrm{H}\mathchar`-\mathrm{GNA}}(\widetilde{a}) = \frac{\sigma^{\tilde{a}}}{\sigma^{\tilde{a}} + \sqrt{\sum_{b\in[K]\backslash\{\tilde{a}\}}\left(\sigma^b\right)^2}}$ and $ w^{\mathrm{H}\mathchar`-\mathrm{GNA}}(a) =\left(1 - w^{\mathrm{H}\mathchar`-\mathrm{GNA}}(\widetilde{a})\right)\frac{\left(\sigma^a\right)^2}{\sum_{b\in[K]\backslash\{\tilde{a}\}}\left(\sigma^b\right)^2}$ for all $a \in [K]\backslash\{\widetilde{a}\}$. If $\widetilde{a}$ is equal to $a^*$, the upper bound of the H-GNA-EBA strategy for the probability of misidentification aligns with the lower bound in Theorem (ref).
This strategy is more suitable under a setting different from BAI, where there are null and alternative hypotheses such that $H_0: a^* \neq \widetilde{a} \in [K]$ and $H_1: a^* = \widetilde{a}$; that is, the null hypothesis corresponds to a situation where the hypothetical best arm is not the best. In contrast, the alternative hypothesis posits that the hypothetical best arm is the best. Then, we consider minimizing the probability of misidentification when the alternative hypothesis is true. This probability corresponds to power in hypothesis testing. Our aim is to minimize the misidentification probability when the null hypothesis is false, corresponding to the power of the test. We refer to this setting as Hypothesis BAI (HBAI). We present two examples for this setting.
The asymptotic efficiency of hypothesis testing is referred to as the Bahadur efficiency Bahadur1960,Bahadur1967,Bahadur1971 of the test\footnote{Note that the Bahadur efficiency of a test evaluates $P$-values (random variable), not the probability of misidentification (non-random variable). However, these are closely related. See Bahadur1967.}.
Using simulation studies, we investigate the performances of our GNA-EBA and the H-GNA-EBA strategies. We compare them with the Uniform-EBA strategy Bubeck2011, which allocates arms with the same allocation ratio ($1/K$), the successive rejects strategy Audibert2010, and the strategy for ordinal optimization (OO) proposed by glynn2004large. Note that the OO requires full knowledge about distributions, including mean parameters and which arm is the best arm. However, if we know it, the OO yields the theoretically lowest probability of misidentification glynn2004large,kaufmann2020hdr,degenne2023existence. Therefore, we regard the OO as a practically infeasible oracle strategy. We investigate two H-GNA-EBA strategies by setting $\widetilde{a} = 1$ and $\widetilde{a} = 2$. The SR strategy is often regarded as the most practical strategy.
Let $K \in \{2, 5, 10, 20\}$. The best arm is arm $1$ and $\mu^1(P) = 1$. The expected outcomes of suboptimal arms $0.75$ ($\mu^a(P) = 0.75$ for all $a\in[K]\backslash\{1\}$). The variances are drawn from a uniform distribution with support $[0.5, 5]$. We continue the strategies until $T = 100,000$. We conduct $100$ independent trials for each setting. For each $T\in\{100, 200, 300, \cdots, 99,900, 100,000\}$, we plot the empirical probability of misidentification in Figures (ref)-- (ref). For each result, we show three figures with different scales on the $x$-axis and $y$-axis to observe the details.
Our theoretical results imply that the strategies with the highest performance are the OO and then the H-GNA-EBA strategy with $\widetilde{a} = 1$ (their performances are equal). Then, the GNA-EBA strategy and the Uniform strategy follow them. The other strategies follow these three strategies, but the order of the performances is not predictable from the theory.
From the results, as the theory predicts, strategies that use more information can achieve a lower probability of misidentification; that is, the OO and the H-GNA-EBA strategy with $\widetilde{a} = 1$ are the best strategies. Then, the GNA-EBA strategy follows them. Note that the OO and H-GNA-EBA strategies with $\widetilde{a} = 1$ are oracle strategies, which are feasible only when we can conjecture which arm is the best arm in advance. Interestingly, the SR strategy performs well in early rounds, but the other asymptotically optimal strategies outperform it in late rounds.
In Appendix (ref), we conduct the additional three experiments. In the first experiment in the Appendix, the expected outcomes of suboptimal arms are drawn from a uniform distribution with support $[0.75, 0.90]$ for $a\in[K]\backslash\{1, 2\}$, while $\mu^2(P) = 0.75$. The variances are drawn from a uniform distribution with support $[0.5, 5]$. We continue the strategies until $T = 10,000$. We conduct $100$ independent trials for each setting. For each $T\in\{100, 200, 300, \cdots, 99,900, 100,000\}$, we plot the empirical probability of misidentification in Figures (ref)-- (ref). In this case, our theoretical results imply that the highest performance is the OO, and then the H-GNA-EBA strategy with $\widetilde{a} = 1$, the GNA-EBA, and the Uniform strategies follow. The other strategies follow them, but the order of the performances is not predictable from the theory. In this experiment, the strategies show the predicted performances.
In the remaining two experiments, we conduct experiments with the same setting as the previous two experiments, but we changed the variances are drawn from a uniform distribution with support $[0.5, 10]$, while the variances are drawn from a uniform distribution with support $[0.5, 5]$ in the previous experiments. We plot the empirical probability of misidentification in Figures (ref)-- (ref). In those cases, our proposed strategies outperform the others due to the larger diversity of the variances. However, because the convergence also becomes slow, the SR outperforms in the early stages longer than the previous experiments, though our strategies outperform it in late rounds.
We investigated scenarios in experimental design, known as BAI or ordinal optimization. We found that the optimality of strategies significantly depends on the information available prior to an experiment. Based on our findings, we developed the novel worst-case lower bounds for the probability of misidentification and then proposed a strategy whose worst-case probability of misidentification matches these worst-case lower bounds.
Lastly, we propose two important extensions of our results. First, we suggest the potential extension of our results to BAI with general distributions. In this study, we developed lower bounds for multi-armed Gaussian bandits. By approximating the KL divergence of distributions in a broader class under the small-gap regime, we can apply our results to various distributions, including Bernoulli distributions and general nonparametric models. In fact, kato2023fixedbudgethyp extends our results, developing lower bounds for more general distributions using semiparametric theory bickel98,Vaart1998. These extended results, which refine those of kato2023fixedbudgethyp, will be published later. It is important to note that in the small-gap regime, asymptotically optimal strategies for one-parameter bandit models, such as Bernoulli distributions, utilize uniform allocation because variances of outcomes become equal as gaps approach zero\footnote{Under the small-gap regime, as $\Delta^a(P)\to 0$, variances in Bernoulli bandits become equal because the variances are $\mu^a(1-\mu^a)$. For details, see kato2023fixedbudgethyp.}. The results from kato2023fixedbudgethyp align with the conjecture in Kaufman2016complexity. From the results of kato2023fixedbudgethyp, we can interpret the GNA-EBA strategy as an extension of the Uniform-EBA strategy proposed by Bubeck2009,Bubeck2011, which recommends uniform allocation in bandit models with bounded supports.
The second extension is optimal strategies that estimate variances during an experiment, instead of assuming known variances. If variances are estimated during an experiment, the estimation error affects the probability of misidentification. We conjecture that an optimal strategy exists that estimates variances during an experiment because similar results can be obtained under the central limit theorem Laan2008TheCA,Hahn2011,hadad2019,Kato2020adaptive,Kato2023minimax. However, its existence remains unproven due to the difficulty in evaluating tail probabilities. Related work, such as that by Kato2023minimax and Jourdan2023, may help to resolve this issue.
\onecolumn