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.
78,499 characters · 23 sections · 120 citation commands
Locally Optimal Fixed-Budget Best Arm Identification in Two-Armed Gaussian Bandits with Unknown Variances
This study investigates the problem of best arm identification (BAI) with a fixed budget in stochastic two-armed Gaussian bandits. In this problem, we consider an adaptive experiment with a fixed number of rounds, called a budget. At each round, we can draw an arm and observe the reward. The goal of the problem is to identify the best arm with the highest expected reward at the end of the experiment Bubeck2009,Audibert2010.
\ifnum\Comments=1\textcolor{black}{ Formally, we consider the following adaptive experiment with two arms and Gaussian rewards. There are two arms $1$ and $2$, and an arm $a \in \{1, 2\}$ has an $\mathbb{R}$-valued Gaussian reward $Y_a \sim \mathcal{N}(\mu_a, \sigma_a^2)$ with the mean $\mu_a \in [-C_{\mu}, C_{\mu}]$ and the variance $\sigma_a^2 \in [C_{\sigma^2}, 1/C_{\sigma^2}]$ for some universal constants $C_{\mu}, C_{\sigma^2} > 0$. We assume that $C_{\mu}$ and $C_{\sigma^2}$ are known to us for a technical purpose, and it is enough to set $C_{\mu}$ as a sufficiently large value and $C_{\sigma^2}$ as a sufficiently small value. Given fixed $(\sigma^2_1, \sigma^2_2)$, let \[\mathcal{P}^{\mathrm{G}} \coloneqq \mathcal{P}^{\mathrm{G}}_{(\sigma^2_1, \sigma^2_2)} \coloneqq \big\{P = (\mathcal{N}(\mu_1, \sigma^2_1), \mathcal{N}(\mu_2, \sigma^2_2)): \mu_1, \mu_2 \in (-\infty, +\infty),\ \ \mu_1\neq \mu_2\big\}\] be a set of distributions generating the data, which is referred to as the Gaussian bandit models, where $P \in \mathcal{P}$ is a pair of distributions that generate $(Y_1, Y_2)$, and $\mathcal{N}(\mu, \sigma^2)$ is a Gaussian distribution with a mean $\mu$ and a variance $\sigma^2$. For an instance $P$, the best arm $a^\star(P) \in \{1,2\}$ is defined as $a^\star(P) = \operatorname*{arg\,max}_{a \in \{1, 2\}} \mu_a$, which is assumed to exist uniquely. }\fi
In the adaptive experiment, we consider a strategy to identify the best arm. A fixed budget $T$ is given. For each round $t \in [T] \coloneqq \{1,2,\dots, T\}$, let $(Y_{1, t}, Y_{2, t})$ be an independent and identically distributed (i.i.d.) copy of $(Y_1, Y_2)$. At each round $t$, we draw arm $A_t \in \{1,2\}$ and observe a reward $Y_t = \sum_{a\in\{1, 2\}}\mathbbm{1}[A_t = a]Y_{a, t}$. At the end of the experiment (after round $T$), we recommend an estimated best arm $\widehat{a}_T \in \{1, 2\}$. During an experiment, we follow a strategy that determines which arm to draw and which arm to recommend as the best arm. The performance of strategies is evaluated by a minimal probability of misidentification $\mathbb{P}_{P}( \widehat{a}_T \neq a^\star(P))$, where $\mathbb{P}_{P}$ is the probability law under $P$.
\paragraph{Background.} In fixed-budget BAI, it has been an important question of interest to investigate the probability of misidentification $\mathbb{P}_{P}( \widehat{a}_T \neq a^\star(P))$ in the limit $T \to \infty$. For the interest, a typical approach is to derive an upper and lower bound of the probability separately and specify its value.
For a lower bound of the probability of misidentification, Kaufman2016complexity develops a general theory for deriving lower bounds of the probability. Their theory applies the change-of-measure argument, which has been employed in various problems Vaart1998, including studies for regret minimization Lai1985. Their lower bound is general and can be applied to a wide range of settings, such as the fixed confidence setting Garivier2016 as well as the fixed budget setting.
In contrast, an upper bound of the misidentification probability has not been fully clarified. A typical way to derive upper bounds is to construct a specific strategy and evaluate its misidentification probability. Kaufman2016complexity develops a strategy under a setting in which the variance $(\sigma^2_1, \sigma^2_2)$ of the reward is known and shows its misidentification probability corresponds to the lower bound. However, this strategy is not available under the usual setting with unknown variance. Based on these situations, the current results are insufficient to establish an upper bound for the misidentification probability when the variances are unknown.
Based on the situation above, our interest is in strategies for identifying misidentification probabilities in the adaptive experimental setting described above. Specifically, we need a strategy such that an upper bound on its misidentification probability aligns with the lower bound proposed in Kaufman2016complexity. Further, this strategy must be valid when the variance is unknown.
\paragraph{Our approach and contribution.} In this study, we develop a strategy whose probability of misidentification aligns with the lower bound under an additional setting. To accomplish this, we develop the Neyman allocation-augmented inverse probability weight (NA-AIPW) strategy. Then, we show that the probability of misidentification aligns with the lower bound under a small-gap regime. The details of each are described below.
The NA-AIPW strategy consists of a sampling rule using the Neyman allocation (NA) and a recommendation rule using the augmented inverse probability weighting (AIPW) estimator. NA is a method of sampling arms using a ratio of the root of the variance of rewards, as utilized in Neyman1934OnTT, Kaufman2016complexity. The NA-AIPW strategy samples the arms by estimating this variance during the adaptive experiment. At the end of the experiment, the NA-AIPW strategy recommends an arm with the highest expected reward estimated by using the AIPW estimator, which is an unbiased estimator with a small asymptotic variance.
The small-gap regime considers a situation $\mu_1 - \mu_2 \to 0$ as $T \to \infty$. Although this additional setting slightly simplifies the problem with BAI, the problem is still sufficiently complicated since the small gap makes it difficult to identify the best arm. This setting has been utilized in BAI with fixed confidence, such as the analysis of lil'UCB Jamieson2014. In the realm of statistical testing, such an evaluation framework is known as the local Bahadur efficiency Bahadur1960,Wieand1976,Akritas1988187,He1996. From a technical perspective, the small-gap regime is a situation where we can ignore the estimation error of the variances compared to the difficulty of identifying the best arm. Since the error of the estimation of the variance is relatively negligible in the small-gap setting, we can show that the misidentification probability of the NA-AIPW strategy matches the lower bound.
We summarize the backgrounds and our contributions. In BAI with two-armed Gaussian rewards and a fixed budget, a strategy has been needed in which its misidentification probability achieves the lower bound derived by Kaufman2016complexity. Although Kaufman2016complexity demonstrates an asymptotically optimal strategy that satisfies the requirement with known variances, it remains an unresolved issue to find a strategy whose upper bound matches their derived lower bound when variances are unknown. For this issue, this study proposes the NA-AIPW strategy whose probability of misidentification matches the lower bound under the small-gap regime.
\paragraph{Organization.} This study is organized as follows. First, in Section (ref), we review the lower bound of Kaufman2016complexity. Then, in Section (ref), we propose our NA-AIPW strategy. In Section (ref), we show that the misidentification probability of the strategy asymptotically corresponds to the lower bound by Kaufman2016complexity under the small-gap setting. We show the proof in Section (ref), where we also provide a novel concentration inequality based on the Chernoff bound. In Section (ref), we discuss the difficulty in this problem. In Section (ref), we introduce related work and remaining problems, which includes an extension of our small-gap setting to a setting with multi-armed bandits and non-Gaussian rewards.
Notation. Let $\mathcal{F}_{t}$ be the sigma-algebra generated by all observations up to round $t$. We define a truncation operator: for a variable $v \in \mathbb{R}$ and a constant $c \geq 1$, \ifnum\Comments=1\textcolor{black}{$\mathrm{thre}(v;c_1, c_2) \coloneqq \min\{ \max\{v,c_1\},c_2\}$}\fi.
As a preparation, we introduce a lower bound for the probability of misidentification in BAI with a fixed budget. We call a strategy is consistent, if for any $P\in\mathcal{P}^{\mathrm{G}}$, $\mathbb{P}_{P}( \widehat{a}_T \neq a^\star(P)) \to 0$ as $T \to \infty$. To evaluate the performance of strategies For any $P\in\mathcal{P}^{\mathrm{G}}$, we focus on the following metric for $\mathbb{P}_{P}( \widehat{a}_T \neq a^\star(P))$ used in many studies, such as Kaufman2016complexity:
Note that the upper bound (resp. lower bound) of this term works as a lower bound (resp. upper bound) of the probability of misidentification $\mathbb{P}_{P}( \widehat{a}_T \neq a^\star(P))$ since $x \mapsto -\log x$ is a strictly decreasing function.
For two-armed Gaussian bandits, Kaufman2016complexity presents the following lower bounds.
\ifnum\Comments=1\textcolor{black}{Note that we can remove the condition that we know constants $C_{\mu}, C_{\sigma^2} > 0$ independent of $T$ such that $\mu_a \in [-C_{\mu}, C_{\mu}]$ and $\sigma^2_1, \sigma^2_2 > C_{\sigma^2}$ hold for deriving the lower bound. However, it is required to implement our strategy and to derive an upper bound. For the conditions of the lower bound to align with those of the upper bound, we add the conditions in this proposition.}\fi
From the statement, there are some important aspects of this lower bound: (i) The term $\Delta = \mu^*_1 - \mu^*_2$, which referred to a gap, appears in the numerator and the magnitude of the error is described by the gap. (ii) The variances $(\sigma_1^2, \sigma_2^2)$ appear in the denominator, which plays an important role.
It has been discussed to find a strategy in which the upper bound of its probability of misidentification coincides with this lower bound in Proposition (ref). Although Kaufman2016complexity develops a strategy that satisfies the requirement, it needs to sample arms with some probability depending on the known variances $(\sigma_1^2, \sigma_2^2)$. To the best of our knowledge, if the variances are unknown and need to be estimated during adaptive experiments, no one has found the desired strategy.
In this section, we define our strategy. Formally, a strategy gives a pair $((A_t)_{t\in[T]}, \widehat{a}_T)$, where (i) $(A_t)_{t\in[T]} \in \{1,2\}^T$ is a sequence of arms generated by a sampling rule that determines which arm $A_t$ is chosen in each $t$ based on $\mathcal{F}_{t-1}$, and (ii) $ \widehat{a}_T \in \{1,2\}$ is a recommended arm by a recommendation rule based on $\mathcal{F}_T$. Our proposed NA-AIPW strategy consists of (i) a sampling rule with the Neyman Allocation (NA) Neyman1923, and (ii) a recommendation rule using the Augmented Inverse Probability Weighting (AIPW) estimator Robins1994,bang2005drestimation. Based on these rules, we refer to this strategy as the NA-AIPW strategy\footnote{Similar strategies are often used in the context of the average treatment effect estimation by an adaptive experiment Laan2008TheCA,Kato2020adaptive.}.
As preparation, we introduce the notion of a target allocation ratio, which will be used for the sampling rule. We define target allocation ratios $w_1^*, w_2^* \in (0,1)$ as
A sampling rule following this target allocation ratio is known as the Neyman allocation rule Neyman1934OnTT. glynn2004large and Kaufman2016complexity also propose this allocation. This target allocation ratio is characterized by the variances (standard deviations); therefore, the target allocation ratio is unknown when the variances are unknown. Therefore, to use this ratio, we need to estimate it from observations.
We present the sampling rule with the NA. At each round $t \in [T]$, our sampling rule randomly draws an arm $a \in \{1,2\}$ with a probability identical to an estimated version of the target allocation ratio $w_a^*$. To estimate the target allocation ratio $w_a^*$, we estimate the variances during the adaptive experiment. For $a \in \{1,2\}$, let $\{\widehat{\sigma}_a\}_{t \in [T]}$ and $\{\widehat{w}_{a,t}\}$ be sequences of estimators of $\sigma_a, \mu_a$ and $w_a^*$, that will be defined bellow.
We use the rounds $t=1$ and $t=2$ for initialization. Specifically, we draw the arm $1$ at round $t=1$ and the arm $2$ at round $t=2$, and also set $\widehat{w}_{a,1} = \widehat{w}_{a,2} = 1/2$ for $a\in\{1,2\}$.
At the round $t \geq 3$, we estimate the target allocation ratio (variances) $w^*_a$ for $a\in\{1,2\}$ using past observations $\mathcal{F}_{t-1}$. For each $t \geq 3$, we first define an estimator of the expected reward $\mu_a$ as \[\widetilde{\mu}_{a, t} \coloneqq \frac{1}{\sum^{t-1}_{s=1}\mathbbm{1}[A_s = a]}\sum^{t-1}_{s=1}\mathbbm{1}[A_s = a] Y_{a, s}.\] Also, we define a second moment estimator $\widetilde{\zeta}_{a, t} \coloneqq ({\sum^{t-1}_{s=1}\mathbbm{1}[A_s = a]})^{-1}\sum^{t-1}_{s=1}\mathbbm{1}[A_s = a] Y^2_{a, s}$, and a root of variance estimator $\widetilde{\sigma}_{a,t} = \{\widetilde{\zeta}_{a, t} - \left(\widetilde{\mu}_{a, t}\right)^2\}^{1/2}$. Then, we define the estimator $\widehat{\sigma}_{a,t} = \mathrm{thre}(\widetilde{\sigma}_{a,t};\underline{C}_{\sigma^2}^{1/2}, 1/\overline{C}_{\sigma^2})$ with the constant $C_{\sigma^2}> 0$, defined in Section (ref). \ifnum\Comments=1\textcolor{black}{Note that this truncation is introduced for a technical purpose to draw each arm infinitely many times as $T\to \infty$ and avoid the estimators of $\mu^*_1$ and $\mu^*_2$, defined below, diverging to infinity. We just use a sufficiently small value for $C_{\sigma^2}> 0$.}\fi Also, we define the estimator $\widehat{w}_{1,t}$ and $\widehat{w}_{2,t}$ as
In each round $t \geq 3$, we draw arm $A_t = 1$ with probability $\widehat{w}_{1, t}$ and $A_t = 2$ with probability $\widehat{w}_{2, t}$.
\ifnum\Comments=1\textcolor{black}{ We note the possibility of increasing the number of initialization rounds, although our strategy utilizes only the first two rounds for this purpose. The additional rounds of initialization serve to stabilize the sampling rule in practical applications, akin to the concept of the forced-sampling Garivier2016. We can change the number of initialization rounds if the condition $\widehat{w}_{a, t} \xrightarrow{\mathrm{a.s.}} w^*_a$ is satisfied as $t \to \infty$ for every $a \in \{1, 2\}$, which is crucial for our theoretical analysis. For instance, instead of using $\widehat{w}_{1, t}$ directly, an alternative arm-drawing probability could be defined as $\widetilde{w}_{1, t} = \alpha_t/2 + (1-\alpha_t)\widehat{w}_{1, t}$, assuming $\alpha_t \in [0, 1]$ and converges to zero as $t$ approaches infinity (here, we define $\widetilde{w}_{2, t} = 1 - \widetilde{w}_{1, t}$). Moreover, the number of initialization rounds can be made dependent upon the number of arms without impacting the theoretical outcomes. }\fi
We present our recommendation rule. In the recommendation phase after round $T$, we estimate $\mu^*_a$ for each $a\in\{1,2\}$ and recommend an arm with the bigger estimated expected reward. With a truncated version of the estimated expected reward $\widehat{\mu}_{a, t} \coloneqq \mathrm{thre}(\widetilde{\mu}_{a, t}, -C_\mu, C_\mu)$ with some predetermined constant $C_\mu > 0$, defined in Section (ref), we define the augmented inverse probability weighting (AIPW) estimator of $\mu^*_a$ for each $a\in\{1,2\}$ as
At the end of the experiment (after the round $t=T$), we recommend $\widehat{a}_T$ as
We adopt the AIPW estimator for our strategy because it has several advantages. First, the AIPW estimator has the property of semiparametric efficiency, which indicates that it has the smallest asymptotic variance among a certain class hahn1998role. The property is necessary to prove that the strategy using the AIPW estimator is optimal, which means the misidentification probability is small enough to achieve its lower bound. The second reason is more technical; the AIPW estimator simplifies the theoretical analysis (see Section (ref)). Specifically, we can decompose an error by the AIPW estimator into a sum of random variables with martingale properties, making it suitable for analysis using the central limit theorem. This property is unique to the AIPW estimator but not to naive estimators such as an empirical average. Details will be given in Section (ref).
We provide the pseudo-code for our proposed strategy in Algorithm (ref). Note that we introduce $C_{\mu}$ and $C_{\sigma^2}$ for technical purposes to bound the estimators and any large positive value can be used.
In this section, we show the following upper bound of the misspecification probability of the NA-AIPW strategy, which also implies that the strategy is asymptotically optimal.
\ifnum\Comments=1\textcolor{black}{We note again that $C_{\mu}$ and $C_{\sigma^2}$ are introduced for technical purpose. The constant $C_{\mu}$ is introduced to guarantee the boundedness of the estimators, and it is sufficient to use a sufficiently large value for it. The constant $C_{\sigma^2}$ is used to draw each arm infinitely many times as $T\to \infty$ and avoid the estimators of the means $\mu^*1$ and $\mu^*_2$ diverging to infinity, and it is sufficient to use a sufficiently small value for $C_{\sigma^2}> 0$.}\fi
Note that the lower bound of $-\frac{1}{T}\log\mathbb{P}_{P^*}\left(\widehat{a}^{\mathrm{AIPW}}_T \neq a^\star(P^*)\right)$ implies the upper bound of $\mathbb{P}_{P^*}\left(\widehat{a}^{\mathrm{AIPW}}_T \neq a^\star(P^*)\right)$. This theorem implies us to evaluate the probability of misidentification up to the constant term, even when it is exponentially small, as $\Delta\to 0$.
This result directly implies the asymptotic optimality of the NA-AIPW strategy. As $\Delta\to 0$, the upper bound matches the lower bound in Proposition (ref). This asymptotic optimality result suggests that the estimation error of the target allocation ratio (variances) $w^{*}$ is negligible when $\Delta\to 0$. This is because the estimation error is insignificant compared to the challenges of identifying the best arm due to the small gap.
Although studies, such as Ariu2021, Qin2022open, and degenne2023existence, point out the non-existence of the optimal strategies in fixed-budget BAI against the lower bound shown by Kaufman2016complexity, our result does not yield a contradiction. Existing impossibility results discuss the existence of a strategy that violates the lower bound. Note that the lower bounds in Kaufman2016complexity are applicable to any instances in the bandit models (with some regularity conditions). In other words, if we consider the lower bound in Kaufman2016complexity for all instances, there exists an instance under which there exists a strategy whose lower bound is larger than the lower bound derived by Kaufman2016complexity. In contrast, we only consider bandit models where $\Delta \to 0$. Our result implies that if we restrict bandit models, the upper bounds of our strategy within the restricted bandit models match the lower bound. Because our optimality is limited to a case where $\Delta \to 0$, we refer to our optimality as asymptotic optimality under the small-gap regime or local asymptotic optimality.
We conjecture that even if we replace the AIPW estimator with the sample average estimator, defined as $\widetilde{\mu}_{a, t} = ({\sum^{t-1}_{s=1}\mathbbm{1}[A_s = a]})^{-1}\sum^{t-1}_{s=1}\mathbbm{1}[A_s = a] Y_{a, s}$ in Section (ref), the upper bound of the strategy still matches the lower bound. However, the proof is an open issue. hirano2003 and Hahn2011 show that the sample average estimator $\widetilde{\mu}_{a, t}$ and the AIPW estimator have the same asymptotic variance (or asymptotic distribution). To show the result, we need to employ empirical process arguments. One of the problems in extending the result to analysis for BAI is that their result focuses on the asymptotic distribution, not the tail probability. Therefore, to show the asymptotic optimality of the strategy with the sample average in the sense of the probability of misidentification, we need to modify the result in hirano2003 and Hahn2011 to analyze the tail probability.
To show Theorem (ref), we derive the upper bound of $\mathbb{P}_{P^*}\left(\widehat{\mu}^{\mathrm{AIPW}}_{a^\star(P^*),T} \leq \widehat{\mu}^{\mathrm{AIPW}}_{b, T}\right)$ for $b\in\{1,2\}\backslash \{a^\star(P^*)\}$, which is equivalent to $\mathbb{P}_{P^*}\left(\widehat{a}^{\mathrm{AIPW}}_T \neq a^\star(P^*)\right)$. Without loss of generality, we assume that $a^\star(P^*) = 1$ and $b=2$. Let us define $V \coloneqq \frac{\sigma^2_1}{w^*_1} + \frac{\sigma^2_2}{w^*_2} = \left(\sigma_1 + \sigma_2\right)^2$ and
Therefore, in the following parts, we aim to derive the upper bound of $\mathbb{P}_{P^*}\left(\widehat{\mu}^{\mathrm{AIPW}}_{a^\star(P^*), T} \leq \widehat{\mu}^{\mathrm{AIPW}}_{b, T}\right) = \mathbb{P}_{P^*}\left(\widehat{\mu}^{\mathrm{AIPW}}_{1, T} \leq \widehat{\mu}^{\mathrm{AIPW}}_{2, T}\right) = \mathbb{P}_{P^*}\left(\sum^T_{t=1}\Psi_t \leq - \frac{T\Delta}{\sqrt{V}}\right)$. Let $\mathbb{E}_{P}$ be the expectation under $P\in\mathcal{P}^{\mathrm{G}}$. We derive the upper bound using the Chernoff bound. This proof is partially inspired by techniques in hadad2019, and Kato2020adaptive.
First, because there exists a constant $C > 0$ independent of $T$ such that $\widehat{w}_{a,t} > C$ by construction, the following lemma holds.
Furthermore, from $\widehat{\sigma}^2_a \xrightarrow{\mathrm{a.s}} \sigma^2_a$ and continuous mapping theorem, for any $P^*\in \mathcal{P}^{\mathrm{G}}$ and all $a\in\{1,2\}$, $\widehat{w}_{a,t}\xrightarrow{\mathrm{a.s}}w^*_{a,t}$.
We prove that $\{\Psi_t\}^T_{t=1}$ is an MDS; that is, $\mathbb{E}_{P^*}\left[\Psi_t|\mathcal{F}_{t-1}\right] = 0$. Although this fact is well-known in the literature of causal inference Laan2008TheCA,hadad2019,Kato2020adaptive, we show the proof for the sake of completeness.
By applying the Chernoff bound, for any $v < 0$ and any $\lambda < 0$, it holds that
From the Chernoff bound and a property of an MDS, we have
\ifnum\Comments=1\textcolor{black}{ Then, the Taylor expansion around $\lambda = 0$ yields
as $\lambda \to 0$. This is given as follows. Since $\mathbb{E}_{P^*}\left[\Psi^k_t\exp(\lambda \Psi_t)|\mathcal{F}_{t-1}\right]$ are finite everywhere in an open interval $(0, \infty)$ for $k = 1,2,3$, the Taylor expansion yields the following (for the details, see the textbook such as page 75 in Bulmer1967 and Theorem 5.19 in Apostol1974): \[\mathbb{E}_{P^*}\left[\exp\left(\lambda\Psi_t\right)|\mathcal{F}_{t-1}\right] = 1 + \sum^2_{k=1}\mathbb{E}_{P^*}\left[\Psi^k_t / k!|\mathcal{F}_{t-1}\right] + o\left(\lambda^2\right)\] as $\lambda \to 0$. Note that the finiteness of $\mathbb{E}_{P^*}\left[\Psi^k_t\exp(\lambda \Psi_t)|\mathcal{F}_{t-1}\right]$ comes from the following in $\Psi_t$: (i) $Y_{a, t}$ is a Gaussian random variable, (ii) $\widehat{\mu}_{a, t}$ and $\widehat{w}_{a, t}$ are bounded random variables by our truncation, and (iii) the lower bound of $\widehat{w}$ is given by $C_{\sigma^2}$. }\fi \ifnum\Comments=1\textcolor{black}{ By using the Taylor expansion again, we approximate $\log(1 + z)$ around $z = 0$ as $\log(1 + z) = z - z^2/2 + z^3/3 - \cdots$. Therefore, we have
as $\lambda \to 0$. Here, we used $\mathbb{E}_{P^*}\left[\Psi_t| \mathcal{F}_{t-1}\right] = 0$. Thus, the (ref) holds. }\fi
We next show $\mathbb{E}_{P^*}\left[\Psi^2_t|\mathcal{F}_{t-1}\right] - 1\xrightarrow{\mathrm{a.s}} 0$. This result is a direct consequence of Lemma (ref).
This lemma immediately yields the following lemma.
\ifnum\Comments=1\textcolor{black}{This result is a variant of the Ces\`{a}ro lemma for a case with almost sure convergence. For completeness, we show the proof, which is based on the proof of Lemma 10 in hadad2019.}\fi
Let $v = \lambda$. Then, we have
From Lemma (ref), for any $\epsilon > 0$, there exists $t(\epsilon) > 0$ such that for all $T > t(\epsilon)$, we have
\ifnum\Comments=1\textcolor{black}{For any $\epsilon > 0$, there exists $t(\epsilon) > 0$ such that for all $T > t(\epsilon)$, we obtainz
as $\lambda \to 0$.}\fi
\ifnum\Comments=1\textcolor{black}{ Let $\lambda = - \frac{\Delta}{\sqrt{V}}$. Then, we have
as $\Delta \to 0$.}\fi By letting $\Delta \to 0$ and $T \to \infty$, and then letting $\epsilon \to 0$ independently of $T$ and $\Delta$, we have
Thus, the proof is complete.
\color{black}
In this section, we discuss related topics.
For two-armed Gaussian bandits with known variances, chen2000, glynn2004large, and Kaufman2016complexity conclude that sampling each arm with a proportion of the standard deviation is optimal, which corresponds to the Neyman allocation Neyman1934OnTT.
The Neyman allocation with unknown variances has been long studied in various fields. Laan2008TheCA and Hahn2011 develop algorithms for estimating the gap parameter $\Delta$ itself in an adaptive experiment with the Neyman allocation. They estimate the variances and show their algorithms' optimalities under the framework of semiparametric efficiency, which closely connects to the Gaussian approximation of estimators using the central limit theorem. Although they show their optimality under the framework, they do not investigate the asymptotic optimality in the large-deviation framework. Meehan2018, Kato2020adaptive, and zhao2023adaptive also attempt to adrress related problems.
Jourdan2023 examines BAI with unknown variances in a fixed-confidence setting. Beyond the difference in settings (we focus on fixed-budget BAI), the methods of deriving lower bounds differ between our approach and theirs. They determine the lower bound while incorporating the assumption that the variances are unknown. Moreover, under a large-gap regime ($\Delta$ is fixed), they confirm a discrepancy between the lower bounds when variances are known versus unknown. Specifically, they consider alternative hypotheses related to both variances and means. In contrast, the lower bounds presented by Kaufman2016complexity and ourselves are based on alternative hypotheses with fixed variances. While Jourdan2023 suggests that the upper bounds of strategies with unknown variances cannot align with the lower bound when variances are known, our findings indicate a match under the small-gap regime.
First, we discuss the necessity of the small-gap regime.
\paragraph{Estimation error of the variances.} The most critical reason we employ the small-gap regime is that the estimation error of the variances cannot be ignored in evaluating the probability of misidentification. To clarify this point, we review the probability of misidentification when we know the variances.
\paragraph{Probability of misidentification of the Kaufman2016complexity's strategy with known variances.} Kaufman2016complexity proposes drawing arm $a$ in $\frac{\sigma^a}{\sigma^1 + \sigma^2}T = w^*_aT$ rounds (for simplicity, we deal with $w^*_aT$ as an integer). Without loss of generality, we consider draw arm $1$ in the first $w^*_1T$ rounds and draw arm $2$ in the following $T - w^*_1T = w^*_2T$ rounds. Then, they estimate the best arm as $\widehat{a}^{\mathrm{KCG}}_T \coloneqq \operatorname*{arg\,max}_{a\in \{1, 2\}} \widehat{\mu}^{\mathrm{SA}}_{a, T}$, where $\widehat{\mu}^{\mathrm{SA}}_{a, T}$ is the sample average defined as
where $A^{\mathrm{KCG}}_t$ denotes an arm drawn by the Kaufman2016complexity's strategy. For the strategy, they show that its probability of misidentification is given as
Note that this upper bound comes from the upper bound of
in case where arm $1$ is the best arm ($a^\star(P^*) = 1$). In contrast, in Theorem (ref), we show that our strategy's upper bound is $\liminf_{T \to \infty} - \frac{1}{T}\log \mathbb{P}_{P^*}\left(\widehat{a}^{\mathrm{AIPW}}_T \neq a^\star(P^*)\right) \geq \frac{\Delta^2}{2(\sigma_1 + \sigma_2)^2} - o(\Delta^2)$. The difference between our upper bounds and theirs is the existence of $-o(\Delta^2)$ term, which vanishes as $\Delta \to 0$. This difference comes from the estimation error of the variances.
\paragraph{Intuitive explanation about the influence of the influence of the variance estimation.} To understand the variance estimation, we rewrite the sample average as
where we used $\sum^T_{t=1}\mathbbm{1}[A^{\mathrm{KCG}}_t = a] = w^*_aT$. Here, we consider a strategy that estimates $w^*_a$ by estimating the variances. Let $\widetilde{w}_a$ be some estimator of $w^*_a$. Then, we design a strategy that draws arm $a$ in $\widetilde{w}_a T$ rounds in some way. In that case, the sample average roughly becomes
where $\widetilde{A}_t$ denotes an arm drawn by some strategy that draws arm $a$ in $\widetilde{w}_a T$ rounds. Then, if we recommend arm $\widetilde{a}_T \coloneqq \operatorname*{arg\,max}_{a\in\{1, 2\}} \widetilde{\mu}^{\mathrm{SA}}_{a, T}$ as the best arm, we evaluate
From Markov's inequality, for any $\lambda > 0$, we have
To obtain the same upper bound as that in the Kaufman2016complexity's strategy, we consider the following decomposition:
Suppose that the following holds in some way:
Note that this decomposition does not generally hold, but we assume it since it makes it easy to understand the variance estimation problem. Under the assumption, it holds that
This inequality implies that to obtain the same upper bound as that of Kaufman2016complexity's strategy, we need to bound
with an arbitrage rate of convergence; more exactly, we need to show that for any $\varepsilon > 0$, \[\liminf_{T \to \infty} - \frac{1}{T}\log \mathbb{E}\left[\exp\left(T\lambda\left(\left\{\widetilde{\mu}^{\mathrm{SA}}_{1, T} - \widetilde{\mu}^{\mathrm{SA}}_{2, T}\right\} - \left\{\widehat{\mu}^{\mathrm{SA}}_{1, T} - \widehat{\mu}^{\mathrm{SA}}_{2, T}\right\}\right)\right)\right] \geq -\varepsilon\] holds. However, it is impossible to achieve that convergence rate with commonly known theorems about convergence. Therefore, we introduced the small-gap regime, which evaluates the term as \[\liminf_{T \to \infty} - \frac{1}{T}\log \mathbb{E}\left[\exp\left(T\lambda\left(\left\{\widetilde{\mu}^{\mathrm{SA}}_{1, T} - \widetilde{\mu}^{\mathrm{SA}}_{2, T}\right\} - \left\{\widehat{\mu}^{\mathrm{SA}}_{1, T} - \widehat{\mu}^{\mathrm{SA}}_{2, T}\right\}\right)\right)\right] = - o(\Delta^2).\] Note that this argument is not rigorous and is simplified for explanation.
A key component of our analysis is the AIPW estimator, which comprises an MDS and boasts minimum asymptotic variance. By using the properties of an MDS, we tackle the dependence among observations. The upper bound can also be applied to the Inverse Probability Weighting (IPW) estimator, but in this case, the upper bound may not coincide with the lower bound. This discrepancy occurs because the AIPW estimator's asymptotic variance is smaller than the IPW estimator's. The minimum variance property of the AIPW estimator stems from the efficient influence function hahn1998role, Tsiatis2007semiparametric.
We conjecture that the asymptotic optimality of strategies employing the naive sample average estimator in the recommendation rule can be demonstrated, although we do not prove it in this study. This is because Hahn2011 shows that, using the CLT, the AIPW and sample average estimators have the same asymptotic distribution. However, due to the inability to utilize MDS properties and the presence of sample dependency, the analysis becomes challenging when we derive a corresponding result for a large deviation (exponential rate of the probability of misidentification).
For the reader's reference, we detail the problems related to the IPW estimator and the sample average estimator.
\paragraph{The NA-IPW strategy.} We consider the following strategy. In the NA-AIPW strategy, instead of the AIPW estimator, we use the following IPW estimator to estimate the means:
At the end of the experiment (after the round $t=T$), we recommend $\widehat{a}^{\mathrm{IPW}}_T$ as
We refer to this strategy as the NA-IPW strategy, whose probability of misidentification of this strategy is given as follows.
Note that $2(\sigma_1 + \sigma_2)\left(\frac{\zeta^*_1}{\sigma_1} + \frac{\zeta^*_2}{\sigma_2}\right) \geq 2(\sigma_1 + \sigma_2)^2$ since $\left(\frac{\zeta^*_1}{\sigma_1} + \frac{\zeta^*_2}{\sigma_2}\right) \geq \left(\frac{\zeta^*_1 - (\mu^*_1)^2}{\sigma_1} + \frac{\zeta^*_2 - (\mu^*_2)^2}{\sigma_2}\right) = (\sigma_1 + \sigma_2)$. Therefore, the upper bound of probability of misidentification of the NA-IPW strategy is larger than that of the NA-AIPW strategy (Note that the inequality is flipped due to $-\frac{1}{T}\log \mathbb{P}_{P^*}$; that is, $\frac{\Delta^2}{2(\sigma_1 + \sigma_2)^2} \geq \frac{\Delta^2}{2(\sigma_1 + \sigma_2)\left(\frac{\zeta^*_1}{\sigma_1} + \frac{\zeta^*_2}{\sigma_2}\right)}$ implies that the upper bound of the probability of misidentification of the NA-AIPW strategy is smaller than that of the NA-IPW strategy). In the case of the evaluation using the CLT, similar results have been known in existing studies, such as hirano2003 and Kato2020adaptive.
\paragraph{The NA-SA strategy.} Next, we consider the following strategy. In the NA-AIPW strategy, instead of the AIPW estimator, we use the following sample average estimator:
At the end of the experiment (after the round $t=T$), we recommend $\widehat{a}^{\mathrm{IPW}}_T$ as
We refer to this strategy as the NA-SA strategy. Evaluation of the probability of misidentification of this strategy is not easy since we cannot employ a martingale property, which has been used in the analysis of the NA-AIPW strategy and the NA-IPW strategy. In order to derive its upper bound, we need to evaluate $\widehat{\mu}^{\mathrm{SA}}_{1, T} - \widehat{\mu}^{\mathrm{SA}}_{2, T}$. Here, note that
holds, and the variance of $\Psi^*_t \coloneqq \left\{\frac{\mathbbm{1}[A_t = 1]\big(Y_{1, t} - \mu^*_1\big)}{\widehat{w}_{1,t}} - \frac{\mathbbm{1}[A_t = 2]\big(Y_{2, t} - \mu^*_2\big)}{\widehat{w}_{2,t}} - \Delta\right\}$ is $V$ in the proof of Theorem (ref), and $\{\Psi^*_t\}^T_{t=1}$ consists of an MDS. Therefore, if $\widehat{\mu}^{\mathrm{SA}}_{1, T} - \widehat{\mu}^{\mathrm{SA}}_{2, T} - \left\{\frac{\mathbbm{1}[A_t = 1]\big(Y_{1, t} - \mu^*_1\big)}{\widehat{w}_{1,t}} - \frac{\mathbbm{1}[A_t = 2]\big(Y_{2, t} - \mu^*_2\big)}{\widehat{w}_{2,t}} - \Delta\right\} = 0$, we can directly apply the proof of Theorem (ref) to obtain the same upper bound in Theorem (ref). However, $\widehat{\mu}^{\mathrm{SA}}_{1, T} - \widehat{\mu}^{\mathrm{SA}}_{2, T} - \left\{\frac{\mathbbm{1}[A_t = 1]\big(Y_{1, t} - \mu^*_1\big)}{\widehat{w}_{1,t}} - \frac{\mathbbm{1}[A_t = 2]\big(Y_{2, t} - \mu^*_2\big)}{\widehat{w}_{2,t}} - \Delta\right\}$ is not zero and remains as a bias term, and it is known that its evaluation requires several techniques. For example, to show $\sqrt{T}\left(\widehat{\mu}^{\mathrm{SA}}_{1, T} - \widehat{\mu}^{\mathrm{SA}}_{2, T} - \Delta\right) \xrightarrow{\mathrm{d}}\mathcal{N}(0, V)$, Hahn2011 bounds $\widehat{\mu}^{\mathrm{SA}}_{1, T} - \widehat{\mu}^{\mathrm{SA}}_{2, T} - \left\{\frac{\mathbbm{1}[A_t = 1]\big(Y_{1, t} - \mu^*_1\big)}{\widehat{w}_{1,t}} - \frac{\mathbbm{1}[A_t = 2]\big(Y_{2, t} - \mu^*_2\big)}{\widehat{w}_{2,t}} - \Delta\right\}$ using the property of the stochastic equicontinuity, which is based on the arguments in hirano2003. This problem is related to the use of the Donsker condition in semiparametric analysis, as explained in kennedy2016semiparametric. We may show the upper bound of the NA-SA strategy by using a similar approach used in Hahn2011, but there are two issues. First, it is unknown what condition corresponds to the stochastic equicontinuity in the setting of BAI, where the samples are dependent. Second, it is unclear whether we can directly apply the stochastic equicontinuity or similar properties to show the large deviation upper bound since such conditions have been used for the central limit evaluation. Therefore, although the findings of hirano2003 and Hahn2011 may aid in resolving this issue, it is an open issue how we use it. Note that this issue caused by the bias of $\widehat{\mu}^{\mathrm{SA}}_{1, T} - \widehat{\mu}^{\mathrm{SA}}_{2, T}$, which is non-zero. Also note that in contrast, the bias of $\widehat{\mu}^{\mathrm{AIPW}}_{1, T} - \widehat{\mu}^{\mathrm{AIPW}}_{2, T}$ is zero due to the properties of an MDS.
In fixed-confidence BAI, the tracking strategy is popular, as used in Garivier2016. In the existing studies of the Neyman allocation, such a strategy has been used. For example, Hahn2011 splits the whole samples into two groups. In the first stage, we uniformly randomly draw each arm and estimate $w^*_a$. In the second stage, for the estimators $\widehat{w}_a$ of $w^*_a$ we draw each arm so that $\frac{1}{T}\sum^T_{t=1}\mathbbm{1}[A_t = a] = \widehat{w}_a$ holds. Then, Hahn2011 estimates $\Delta = \mu^*_1 - \mu^*_2$ using the sample average estimator. This strategy is quite similar to that in Garivier2016, since it draws arms to track the ratio of $w^*_a$.
However, the strategy of Hahn2011 makes analyzing upper bounds difficult. As we explained in Section (ref), in our analysis, the unbiasedness of the AIPW estimator plays an important role. In contrast, if we use the tracking strategy, we cannot employ the property of $\mathbb{E}_{P^*}\left[\frac{\mathbbm{1}[A_t = a]}{\widehat{w}_t}|\mathcal{F}_{t-1}\right] = 1$. Note that the NA-AIPW strategy draws arm $A_t$ with probability $\widehat{w}_t$, but the tracking strategy draws arm $A_t$ more complicatedly, under which we cannot use the martingale property.
As well as we explained in Section (ref), the bias term makes the analysis significantly difficult. According to the existing studies, we need to use some techniques for the analysis, such as the Donsker condition hirano2003,Hahn2011. Existing studies have proposed using the AIPW estimator to avoid this issue, as shown in Laan2008TheCA and Kato2020adaptive.
Thus, although we acknowledge the possibility of using the tracking strategy, the analysis requires some sophisticated techniques. We expect that existing studies such as hirano2003 and Hahn2011 will help the analysis, but it is still an open issue. Note that even in the tracking strategy, existing strategy such as hirano2003 and Hahn2011 bypass the evaluation of the AIPW-type estimators in the analysis. This proof procedure is also related to the semiparmaetric efficiency bound hahn1998role, under which the semiparametric efficient score is given as $\Psi^*_t = \left\{\frac{\mathbbm{1}[A_t = 1]\big(Y_{1, t} - \mu^*_1\big)}{\widehat{w}_{1,t}} - \frac{\mathbbm{1}[A_t = 2]\big(Y_{2, t} - \mu^*_2\big)}{\widehat{w}_{2,t}} - \Delta\right\}$.
\color{black}
This section presents related works.
There is a long debate on the optimal strategies for fixed-budget BAI. glynn2004large develops their strategies by using the large deviation principles. However, while they justify their strategies using the large deviation principles, they do not provide lower bounds for strategies. Therefore, there remains a question about whether their strategies are truly asymptotically optimal.
Kaufman2016complexity establishes distribution-dependent lower bounds for BAI with fixed confidence and budget, utilizing change-of-measure arguments. According to their results, we can confirm that for two-armed Gaussian bandits, the strategy of glynn2004large is optimal.
However, Kaufman2016complexity leaves lower bounds for multi-armed fixed-budget BAI as an open issue. Based on the arguments of glynn2004large and Russo2016, Kasy2021 attempts to derive an asymptotically optimal strategy, but their attempt does not succeed. As pointed out by Ariu2021, without additional assumptions, there exists an instance $P^*$ whose lower bound is larger than that of Kaufman2016complexity. This result is based on another lower bound discovered by Carpentier2016. These arguments are summarized by Qin2022open.
To address this issue, kato2023fixedbudgethyp and degenne2023existence consider a restriction such that sampling rules do not depend on $P^*$. Under this restriction, we can show the asymptotic optimality of the strategy provided by glynn2004large, which requires full knowledge about $P^*$ and is practically infeasible.
komiyama2022 and atsidakou2023bayesian discuss asymptotically optimal strategies from minimax and Bayesian perspectives, respectively, where the leading factor ignoring some constant terms of lower and upper bounds match, unlike our optimality up to constant terms. This open issue is further explored by komiyama2022, wang2023uniformly, wang2023best, and kato2023worstcase.
Note that in the fixed confidence BAI setting, Garivier2016 proposes a strategy with an upper bound matching the derived lower bound. However, in the fixed-budget BAI, it remains unclear whether a strategy with an upper bound matching Kaufman2016complexity's lower bound exists.
Alternative lower bounds have been proposed by Audibert2010, Bubeck2011, Komiyama2021 and Kato2023minimax for the expected simple regret minimization, which is another performance measure different from the probability of misidentification.
Some research employs local asymptotics to examine the asymptotic optimality of the Neyman allocation rule in this context, such as Armstrong2022 and adusumilli2022minimax.
Ordinal optimization in the operations research community is another related field Dohyun2021,chen2000.
In contrast to two-armed bandit problems and BAI with fixed confidence, lower bounds for MAB problems remain unknown. One primary reason is the reversal of KL divergence. kato2023fixedbudgethyp, degenne2023existence, kato2023worstcase consider strategies that use sampling rules that are (asymptotically) invariant for any $P^* \in \mathcal{P}^{\mathrm{G}}$. Such a class of strategies is sometimes called static in the sense that it cannot estimate parameters during an adaptive experiment to avoid the dependency on $P^*$. However, if we consider Gaussian bandit models, sampling strategies that are invariant for $P^*$ do not imply non-adaptive (static) strategies because we can still adaptively estimate the variances during an adaptive experiment (the variances are assumed to be the same for any $P^*$).
\color{black}
This section provides simulation studies to investigate the empirical performance of the NA-AIPW strategy. For comparison, we also investigate the performances of the NA-IPW and NA-SA strategies defined in Section (ref). Furthermore, we also conduct simulation studies of the “oracle” strategy with the known variances, denoted by Oracle, and the uniform strategy that draws an equal number of arms, denoted by Uniform. We recommend an arm with the highest sample average in the Oracle and Uniform strategies.\footnote{The oracle strategy is the one proposed by glynn2004large and Kaufman2016complexity. The Uniform strategy with the recommendation rule is referred to as the Uniform-Empirical Best Arm (EBA) strategy by Bubeck2011.}
Throughout the experiment, we set arm $1$ as the best arm. We conduct experiments with the three settings.
In the first experiment, we set $\mu^*_1 = 1.00$ and choose $\mu^*_2$ from the set $\{0.80, 0.85, 0.90, 0.95, 0.99\}$. The variances $(\sigma_1, \sigma_2)$ are selected with a probability of $1/2$ from either $(1, v_2)$ or $(v_2, 1)$, where $v_2$ is chosen from ${5, 10, 20, 50}$. We continue the strategies until $T = 10,000$ and report the empirical probability of misidentification at $T \in \{100, 200, 300, \dots, 9,900, 10,000\}$.\footnote{This means we report the empirical probability of misidentification at $T \in \{100, 200, 300, \ldots, 9,900, 10,000\}$.} We conduct $1,000$ independent trials for each choice of parameters and plot the results in Figures (ref) and (ref).
In the second experiment, the variances $(\sigma_1, \sigma_2)$ are selected with a probability of $1/2$ from either $(5, v_2)$ or $(v_2, 5)$, where $v_2$ is chosen from ${5, 10, 20, 50}$. The other settings are the same as the first experiment. The results are shown in Figures (ref) and (ref).
In the third experiment, we set $\mu^*_1 = 10.00$ and choose $\mu^*_2$ from the set $\{9.80, 9.85, 9.90, 9.95, 9.99\}$. The other settings are the same as the first experiment. The results are shown in Figures (ref) and (ref).
Our theoretical results imply that the probability of misidentifications of the NA-AIPW and Oracle strategies approach the same as $\Delta \to 0$. We can confirm the phenomenon. In the results, the Oracle strategy is a bit better than the NA-AIPW strategy when $\Delta$ is large. However, the gap approaches zero as $\Delta \to 0$. Note that when $\Delta$ is large, the convergence of the probability of misidentification is very fast, so the gap is still not so large even if $\Delta$ is large because both the probability of misidentifications of the NA-AIPW and Oracle strategies converge to zero very fast.
We can also find that the performance improvement of the NA-AIPW strategy from the Uniform strategy is large as the difference of variances is large. For example, in the second experiment, when $(\sigma_1, \sigma_2) = (5. 5)$, there is no improvement by using the NA-AIPW strategy from the Uniform strategy because the NA allocation also leads us to draw each arm with equal ratio.
The difference between the NA-AIPW and NA-IPW strategies becomes large as the mean outcome of each arm becomes large. We can find that in the third setting, the NA-IPW strategy behaves badly since $\mu^*_1 = 10.00$ and $\mu^*_2$ is chosen from $\{9.80, 9.85, 9.90, 9.95, 9.99\}$, while $\mu^*_1 = 1.00$ and $\mu^*_2$ is chosen from $\{0.80, 0.85, 0.90, 0.95, 0.99\}$ in the first and second settings.
\color{black}
This study investigated fixed-budget BAI for two-armed Gaussian bandits with unknown variances. We first reviewed the lower bound shown by Kaufman2016complexity. Then, we proposed the NA-AIPW strategy and found that its probability of misidentification matches the lower bound when the budget approaches infinity and the gap between the expected rewards of the two arms approaches zero. We referred to this setting as the small-gap regime and the optimality as the local asymptotic optimality. Although there are several remaining open questions, our result provides insight into long-standing open problems in BAI.