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.
45,434 characters · 15 sections · 71 citation commands
Optimal Best Arm Identification in Two-Armed Bandits with a Fixed Budget under a Small Gap
We study the best arm identification (BAI) with a fixed budget in stochastic two-armed Gaussian bandit problems. The goal is to identify an arm that has the highest expected reward with the smallest failure probability under a fixed number of rounds, called a budget Bubeck2009,Audibert2010. Formally, we consider the following setting given a fixed budget $T$: for $t\in [T] := \{1,2,\dots, T\}$ and $a \in \{1,0\}$, there exists a potential independent reward $X_{a, t} \in\mathbb{R}$ from a distribution $\nu_a$ with an expected reward $\mu_a$. Let $\mathcal{F}_{t}$ be the sigma-algebra by all observations up to time $t$.
A tuple of the distributions ${\nu} = (\nu_1, \nu_0)$ is called a bandit model. In this study, we consider Gaussian bandit models defined as $\mathcal{M} = \{\nu = (\mathcal{N}(\mu_1, \sigma^2_1), \mathcal{N}(\mu_0, \sigma^2_0)): (\mu_1, \mu_0)\in\mathbb{R}^2, \mu_1\neq \mu_0\}$, where $\mathcal{N}(\mu_a, \sigma^2_a)$ is a Gaussian distribution with the mean $\mu_a$ and variance $\sigma_a^2$ for $a \in \{1,0\}$. The best arm $a^*(\nu) \in \{1,0\}$ is defined as $\mu_{a^*} > \max_{a \neq a^*(\nu)} \mu_a$, which is assumed to exist uniquely. Without loss of generality, we assume that $\mu_1 > \mu_0$, hence $a^*(\nu) = 1$. At time $t$, an agent randomly samples an arm $A_t \in \{1,0\}$ and receives a reward $X_t=\sum_{a\in\{1, 0\}}\mathbbm{1}[A_t = a]X_{a, t}$.
A strategy for the BAI problem determines which arms to sample and which arm to choose as the best arm. Formally, we define a strategy as a pair $((A_t)_{t\in[T]}, \hat{a}_T)$, where (i) $(A_t)_{t\in[T]}$ is a sampling rule that determines which arm $A_t$ is chosen in each $t$ based on $\mathcal{F}_{t-1}$, and (ii) $ \hat{a}_T$ is a recommendation rule that samples an arm $\hat{a}_T$ based on $\mathcal{F}_T$. A sampling rule is often designed based on a target allocation ratio; that is, the ratio of the expected number of samples of an arm. A target allocation ratio determines the number of samples allocated to each arm, and estimating the ratio during the round plays an important role in the strategy.
Our goal is to find a strategy that minimizes the probability of misidentification $\mathbb{P}_{\nu}( \hat{a}_T \neq a^*(\nu))$, where $\mathbb{P}_{\nu}$ (resp. $\mathbb{E}_{\nu}$) is the probability law (resp. expectation) of a sequence of random variables $(X_t)_{t\in[T]}$. We call a strategy is consistent, if $\mathbb{P}_{\nu}( \hat{a}_T \neq a^*(\nu)) \to 0$ as $T \to \infty$. To evaluate the performance of strategies, we focus on the following metric for $\mathbb{P}_{\nu}( \hat{a}_T \neq a^*(\nu))$ used in many studies, such as Kaufman2016complexity:
We remark that the upper bound (resp. lower bound) of this term works as a lower bound (resp. upper bound) of the probability $\mathbb{P}_{\nu}( \hat{a}_T \neq a^*(\nu))$ since $x \mapsto -\log x$ is a strictly decreasing function.
One of the main interests in this field is to derive a tight lower bound for the probability of misidentification and an optimal strategy under which the probability of misidentification matches the lower bound. glynn2004large proposes an optimal strategy when an optimally selected target allocation ratio is given. Their target allocation ratio is identical to the one given in the Neyman allocation Neyman1934OnTT, where samples are allocated to each treatment arm based on the ratio of its standard deviation. However, they assume that the standard deviations is known and do not consider the issue of estimating them. Kaufman2016complexity derives a distribution-dependent lower bound for the misidentification probability, which is agnostic to the optimal target allocation ratio; that is, their lower bound presumes the knowledge of the standard deviations. Despite the seminal result, it is still unknown whether there exists a strategy under which the probability of misidentification matches the lower bound of Kaufman2016complexity when the standard deviations are unknown. kaufmann2020hdr.
The main contribution of this study is the development of a strategy under which the probability of misidentification matches the distribution-dependent lower bound of Kaufman2016complexity. First, we propose the Neyman Allocation-Augmented Inverse Probability Weight (NA-AIPW) strategy consisting of the following two components. (i) a sampling rule with the Neyman Allocation (NA), and (ii) a recommendation rule using the Augmented Inverse Probability Weighting (AIPW) estimator Robins1994,bang2005drestimation. We show that the NA-AIPW strategy is asymptotically optimal under a small gap. When $T \to \infty$ and a gap $\Delta = \mu_1 - \mu_0$ between the expected rewards goes to zero, the upper bound of the NA-AIPW strategy matches the lower bound of Kaufman2016complexity. In Table (ref), we summarize our contributions.
Investigating optimality under the small gap corresponds to evaluating one of the worst-case performances. A small gap implies a situation in which it is difficult to identify the best arm. Our proposed strategy is asymptotically optimal in the sense that it matches the lower bound in the small gap asymptotically. Therefore, our result can be interpreted as a worst-case optimality of the NA-AIPW strategy for the probability of misidentification. From the technical viewpoint, one of the reasons why the probability of misidentification matches the lower bound is partly because the estimation error of the optimal target allocation ratio becomes negligible with respect to the probability of misidentification. In BAI with fixed confidence, lil'UCB Jamieson2014 considers optimality under a similar situation.
To evaluate the probability of misidentification under a small gap, we modified a large deviation bound for martingales shown by Fan2013,fan2014generalization. Then, we apply the large deviation bounds to obtain the upper bound with the AIPW estimator whose asymptotic variance matches the lower bound for the asymptotic variance.
Organization. The remainder of this paper is organized as follows. In Section (ref), we describe the lower bound, following Kaufman2016complexity. In Section (ref), we define the NA-AIPW strategy. In Section (ref), we present our main theorem on the asymptotic optimality of our proposed strategy with its proof. In Section (ref), we provide the empirical results of the numerical experiments to demonstrate the efficiency of our strategy. In Section (ref), we discuss the related work and remaining problems. A detailed discussion of the AIPW estimator can be found in Sections (ref) and (ref) and Appendix (ref).f
As a preparation, we introduce a distribution-dependent lower bound for the probability of misidentification in BAI with a fixed budget. For BAI, Kaufman2016complexity presents the distribution-dependent lower bounds specific to each reward distribution. Their lower bounds correspond to those for regret minimization, popularized by Lai1985. Based on their results, we provide lower bounds for Gaussian bandit models $\mathcal{M}$.
In order to present lower bounds and for subsequent theoretical analysis, we assume the following conditions on the bandit models.
Recall that $\Delta = \mu_1 - \mu_0$ is a gap of the means between $\nu_1$ and $\nu_0$ in $\nu$. Then, we obtain the following statement from the arguments in Section 5.1 in Kaufman2016complexity.
For the sake of completeness, we show it in Appendix (ref).
It is known that there exist optimal strategies under which the probability of misidentification asymptotically matches the lower bound when the standard deviations are known glynn2004large,Kaufman2016complexity. In existing optimal strategies using the known standard deviations, such as Kaufman2016complexity, we sample each arm with the ratio of the standard deviations as well as the Neyman allocation. However, to the best of our knowledge, if standard deviations need to be estimated by adaptive experimentation, no optimal strategy has been proposed. Furthermore, Carpentier2016 derives another lower bound, which implies that there is no optimal strategies for the lower bound in Proposition (ref) when the gap $\Delta$ is fixed. In this study, we consider a strategy under which the probability of misidentification matches the lower bound in Proposition (ref) under the small gap, $\Delta \to 0$. This result implies optimality in a worst-case.
In this section, we define our strategy, which consists of sampling and recommendation rules. We define a truncation operator: for a variable $v \in \mathbb{R}$ and a constant $c \geq 1$, $\mathrm{thre}(v;c) := \max\{ \min\{v,c\},1/c\}$.
First, we define a target allocation ratio, which determines the ratio of the expected number of samples of an arm that the sampling rule follows. Then, we define an optimal target allocation ratio as
A sampling rule following this allocation ratio is known as the Neyman allocation rule Neyman1934OnTT. glynn2004large and Kaufman2016complexity also propose this allocation. This optimal target allocation ratio is unknown when the variances are unknown; therefore, to use this ratio, we need to estimate it from observations during the bandit process.
In each $t \in [T]$, our sampling rule randomly samples an arm, following an estimated target allocation ratio; that is, we sample an arm with the probability identical to the estimated target allocation ratio (target allocation probability). In final time $T$, our recommendation rule recommends an arm with the highest estimated expected reward. Based on these rules, we refer to this 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.}
We provide a sampling strategy referred to as a Neyman allocation (NA) strategy. For $a\in\{1,0\}$ and $t\in[T]$, let $w_{a,t}$ be an estimated target allocation ratio such that $\forall a\in\{1,0\}, \ w_{a, t} > 0$ and $\sum_{a\in\{1,0\}} {w}_{a,t} = 1$. In each time $t$, we obtain $\gamma_t$ from the uniform distribution on $[0,1]$ and sample arm $A_t = 1$ if $\gamma_t \leq w_{1, t}$ and $A_t = 0$ if $\gamma_t > w_{1, t}$.
As an initialization, we sample arm $1$ at time $1$ and arm $0$ at time $2$ and set $w_{a,1} = w_{a,2} = 1/2$ for $a\in\{1,0\}$. In time $t > 2$, for all $a\in\{1,0\}$, we estimate the optimal target allocation ratio $w^*_a$ using past observations $\mathcal{F}_{t-1}$. To construct $w_{a,t}$, we define a estimator of the expected reward as $\tilde{\mu}_{a, t} = ({\sum^{t-1}_{s=1}\mathbbm{1}[A_s = a]})^{-1}\sum^{t-1}_{s=1}\mathbbm{1}[A_s = a] X_{a, s}$, a second moment estimator $\tilde{\zeta}_{a, t} = ({\sum^{t-1}_{s=1}\mathbbm{1}[A_s = a]})^{-1}\sum^{t-1}_{s=1}\mathbbm{1}[A_s = a] X^2_{a, s}$, and a variance estimator $\tilde{\sigma}^2_{a,t} = \tilde{\zeta}_{a, t} - \left(\tilde{\mu}_{a, t}\right)^2$ for $t \geq 3$. For $t=1,2$, we set $\tilde{\mu}_{a, t} = \tilde{\zeta}_{a, t} = 0$. Then, we estimate the variance $\sigma^2_a$ for $a\in\{1,0\}$ in time $t$ as $\hat{\sigma}^2_{a,t} = \mathrm{thre}(\tilde{\sigma}^2_{a,t};C_{\sigma^2})$ and define $w_{1,t}$ and $w_{0,t}$ as
We use this strategy to apply the large deviation expansion for martingales to the estimator of the expected reward, which is the core of our theoretical analysis in Section (ref).
We present our recommendation rule. In the recommendation phase in time $T$, for each $a\in\{1,0\}$, we estimate $\mu_a$ for each $a\in\{1,0\}$ and recommend a arm with the bigger estimated expected reward. With a truncated version of the estimated expected reward $\hat{\mu}_{a, t} = \mathrm{thre}(\tilde{\mu}_{a, t}, C_\mu)$, we define the augmented inverse probability weighting (AIPW) estimator of $\mu_a$ as
In the end of time $t=T$, we recommend $\hat{a}_T$ as
The AIPW estimator $\hat{\mu}^{\mathrm{AIPW}}_{a, T}$ has the following properties: (i) its components satisfy the martingale property and hence, allow us to use the large deviation principle shown in Theorem (ref); (ii) it has the smallest asymptotic variance among the possible estimators, which is needed for achieving the lower bound. For instance, we can use other estimators with a martingale property, such as the inverse probability weighting (IPW) estimator, but their asymptotic variance will be larger than that of the AIPW estimator. On the other hand, the sample average may have the same asymptotic variance as the AIPW estimator, but we cannot apply our large deviation bound. See also Section (ref).
We show the pseudo-code in Algorithm (ref). We note that $C_{\mu}$ and $C_{\sigma^2}$ are introduced for technical purposes to make the estimators bounded. Therefore, we can use any large positive value.
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. We show the upper bounds for bandit models, where the rewards are sub-exponential random variables. We assume the following convergence rate assumptions on estimators of $\mu_a$ and $w^*_a$.
Then, the upper bound is given as follows.
This theorem allows us to evaluate the exponentially small probability of misidentification up to the constant term when $\Delta\to 0$. From this theorem, we can obtain the following corollary, which states the optimality of our proposed strategy in the small gap.
Using this corollary, when bandit models follow the Gaussian bandit models, we can show that the upper bound in Theorem (ref) matches the lower bound in Proposition (ref) as $\Delta \to 0$. When $\Delta \to 0$, there is no strategy under which the probability of misidentification is lower than that under the NA-AIW strategy. In other words, this result implies that the NA-AIPW estimator is asymptotically optimal in the sense that the probability of misidentification matches one of a worst-case lower bound under the small gap.
Moreover, this result also implies that the estimation error of the optimal target allocation ratio $w^*_a$ is negligible when $\Delta\to 0$. As a result, the upper bound matches the performance of the strategies of glynn2004large given the optimal target allocation ratio; that is, the true standard deviations are known. This also means that under the small gap, the estimation error of the optimal target allocation ratio does not affect the probability of misidentification.
The remaining part of this section provides proof of Theorem (ref).
Owing to the non-stationary adaptive process in BAI, it is also difficult to apply the standard large deviation bound Dembo2009large to the simple sample average. For example, G\"{a}rtner-Ellis theorem Gartner1977,Ellis1984 provides a large deviation bound for dependent samples, but it requires the existence of the logarithmic moment generating function, which is not easy to be guaranteed for the samples in BAI.
For these problems, we derive a novel Cram\'er large deviation bounds for martingales by extending the results of Grama2000 and Fan2013,fan2014generalization. Note that their original large deviation bound is only applicable to martingales whose conditional second moment is bounded by any accuracy deterministically in advance. However, in BAI, we can only bound the conditional second moment by any accuracy in a given random path. This randomness prevents us from applying the original results of Grama2000 and Fan2013,fan2014generalization. In the following arguments, we show a large deviation bound for martingales given by the BAI strategy under the mean convergence of the unconditional second moment. Using the novel bound and the AIPW estimator, as the gap $\Delta$ goes to zero, the performance guarantee matches the lower bound.
Following Fan2013,fan2014generalization, we derive a large deviation bound for sub-exponential random variable, which is more general than Gaussian distributions.
Here, we introduce key elements of our analysis. For each $t\in[T]$, we define the difference variable
We also define its sum $Z_t = \sum^t_{s=1}\xi_{s}$, and a sum of conditional moments $W_t = \sum^t_{s=1}\mathbb{E}_{\nu}[\xi^2_{s}| \mathcal{F}_{s-1}]$ with initialization $W_0 = 0$. By using the difference variable $\xi_{t}$, we can rewrite the estimator of the gap as $\sqrt{T}(\hat{\mu}^{\mathrm{AIPW}}_{1, T} - \hat{\mu}^{\mathrm{AIPW}}_{0, T} - \Delta) / \tilde{\sigma} = \sum^T_{t=1}\xi_{t} = Z_T$. Here, $\left\{\left(\xi_{t}, \mathcal{F}_t\right)\right\}^T_{t=1}$ is a martingale difference sequence (Appendix (ref)), using the fact that $\hat{\mu}_{a,t}$ and $w_{a,t}$ are $\mathcal{F}_{t-1}$-measurable random variables. Let us also define $V_T = \mathbb{E}_\nu [ | \sum_{t=1}^T \mathbb{E}_{\nu}[\xi_t^2 | \mathcal{F}_{t-1}] -1 |]$ and denote the cumulative distribution function of the standard normal distribution by $\Phi(x) = ({\sqrt{2\pi}})^{-1} \int_{-\infty}^x \exp(- {t^2} / {2})\mathrm{d}t$. We have the following theorem on the tail probability of $Z_T= \sum^T_{t=1}\xi_{t}$.
Here, as explained by fan2014generalization, if $T\mathbb{E}[\xi^2_t|\mathcal{F}_{t-1}]$ are all bounded from below by a positive constant, Condition A implies the conditional Bernstein condition: for a positive constant $C$, $|\mathbb{E}[\xi^k|\mathcal{F}_{t-1}]| \leq \frac{1}{2} k!(C/\sqrt{T})^{k-2}\mathbb{E}[\xi^2_t|\mathcal{F}_{t-1}]$ for all $k\geq 2$ and all $t\in[T]$. Thus, the condition is sufficiently general and holds for our strategy under appropriate assumptions.
Here, we provide the proof sketch of Theorem (ref). The formal proof is shown in Appendix (ref).
From Theorem (ref), for $u = \sqrt{T} { \Delta} / {\tilde{\sigma}}$ and $\mathbb{P}_{\nu}(Z_T \leq - \sqrt{T} { \Delta} / {\tilde{\sigma}}) = \mathbb{P}_{\nu}( \sum_{t =1}^T ({\hat{X}_{1,t} - \hat{X}_{0,t} - \Delta})/({\sqrt{T} \tilde{\sigma}} )\le - \sqrt{T} { \Delta} / {\tilde{\sigma}} ) = \mathbb{P}_{\nu}(\hat{\mu}^{\mathrm{AIPW}}_{1, T} \le \hat{\mu}^{\mathrm{AIPW}}_{0, T})$, the probability that we fail to make the correct arm comparison is bounded as
Finally, we consider an approximation of the large deviation bound. Here, $\Phi(-u)$ is bounded as $\frac{1}{\sqrt{2 \pi} (1 + u)} \exp(- \frac{u^2}{2})\le \Phi(-u) \le \frac{1}{\sqrt{\pi} (1 + u)} \exp( - \frac{u^2}{2}),\; u\ge 0$ (see Fan2013). \ifnum\Comments=1\textcolor{black}{By combining this bound with Theorem (ref) and Proposition (ref) in Appendix (ref), which shows the rate of convergence in the CLT for $0 \leq u \leq 1$, we have the following corollary.}\fi
This approximation can be thought of as a Gaussian approximation because the probability is represented by $\exp(-{\Delta^2} T / ({2 \tilde{\sigma}^2}))$. Condition B is satisfied as $\Delta \to 0$. To use Corollary (ref), we need to show that Conditions A and C hold. First, the following lemma states that Condition A holds with the constants $C_0$ and $C_1$, which are universal to the problems in $\mathcal{M}$.
Next, regarding Condition C, we introduce the following lemma for the convergence of $V_T$, which also means the mean convergence of the variance of the AIPW estimator scaled with $\sqrt{T}$.
The proofs of Lemma (ref) and Lemma (ref) are shown in Appendix (ref) and (ref), respectively.
We compare the proposed NA-AIPW (NA) strategy with the alpha-elimination Kaufman2016complexity and uniform sampling strategies (Uniform). The alpha-elimination strategy is an oracle strategy, which assumes that the variances are known. See Kaufman2016complexity for more details of the alpha-elimination strategy. In the uniform sampling strategy, we sample arm $1$ if the time is odd and sample $0$ otherwise; finally, we recommend an arm with the highest average reward defined as $\tilde{\mu}_{a,T+1}$ in Section (ref). Besides, we also investigate the performances of the following three additional strategies :\\ NA-DR (ND) strategy. We replace the AIPW estimator in the NA-AIPW strategy with the DR estimator defined as $\hat{\mu}^{\mathrm{DR}}_{a, T} =\frac{1}{T} \sum^T_{t=1}\hat{X}^\dagger_{a, t}$, where $\hat{X}^\dagger_{a,t} = \frac{\mathbbm{1}[A_t = a]\big(X_{a, t}- \hat{\mu}_{a, t}\big)}{\frac{1}{t-1}\sum^{t-1}_{s=1}\mathbbm{1}[A_s = a]} + \hat{\mu}_{a, t}$.\\ NA-IPW (NI) strategy. We replace the AIPW estimator in the NA-AIPW strategy with the inverse probability weighting (IPW) estimator defined as $\hat{\mu}^{\mathrm{IPW}}_{a, T} =\frac{1}{T} \sum^T_{t=1}\hat{X}^\diamond_{a, t}$, where $\hat{X}^\diamond_{a,t} = \frac{\mathbbm{1}[A_t = a]X_{a, t}}{w_{a,t}}$.\\ NA-SA (NS) strategy. We replace the AIPW estimator in the NA-AIPW strategy with the simple sample average defined as $\hat{\mu}_{a, T}^{\mathrm{SA}} = \frac{1}{\sum^{T}_{t=1}\mathbbm{1}[A_t = a]}\sum^{T}_{t=1}\mathbbm{1}[A_t = a] X_{a, t}$.\\ The DR estimator replaces the allocation probability $w_{a,t}$ with its estimator. The IPW estimator does not use the adjustment term $\hat{\mu}_{a,t}$. The sample average corresponds to the IPW estimator whose allocation probability is replaced with its estimator $\frac{1}{T}\sum^{T}_{t=1}\mathbbm{1}[A_t = a]$ because $\hat{\mu}_{a, T}^{\mathrm{SA}}$ can be rewritten as $\hat{\mu}_{a, T}^{\mathrm{SA}} = \frac{1}{T}\sum^{T}_{t=1}\frac{\mathbbm{1}[A_t = a] X_{a, t}}{\frac{1}{T}\sum^{T}_{t=1}\mathbbm{1}[A_t = a]}$.
Besides, to stabilize the allocation probability $w_{a,t}$, instead of directly using $w_{a,t}$, we use $\tilde{w}_{a,t} = r_t \frac{1}{2} + (1-r_t) w_{a,t}$ for $r_t$ such that $r_t \to 0$ as $t\to\infty$. This prevents $w_{a,t}$ from being some extreme value. Note that $w^\gamma_{a,t} \xrightarrow{\mathrm{a.s.}} w^*_{a}$ if $w_{a,t} \xrightarrow{\mathrm{a.s.}} w^*_{a}$. In this experiments, we use $w^\gamma_{a,t}$ with $\gamma_t = \frac{1}{\sqrt{t}}$ and $100$ initialization times for the NA-AIPW, NA-DR, NA-IPW, and NA-SA strategies.
We consider the following eight sample scenarios: (1) $\mu_1 = 0.05$, $\mu_0 = 0.01$, $\sigma^2_1 = 1$, and $\sigma^2_0 = 0.2$; (2) $\mu_1 = 0.05$, $\mu_0 = 0.01$, $\sigma^2_1 = 1$, and $\sigma^2_0 = 0.1$; (3) $\mu_1 = 0.05$, $\mu_0 = 0.03$, $\sigma^2_1 = 1$, and $\sigma^2_0 = 0.2$; (4) $\mu_1 = 0.05$, $\mu_0 = 0.01$, $\sigma^2_1 = 1$, and $\sigma^2_0 = 0.1$; (5) $\mu_1 = 0.8$, $\mu_0 = 0.75$, $\sigma^2_1 = 5$, and $\sigma^2_0 = 3$; (6) $\mu_1 = 0.8$, $\mu_0 = 0.75$, $\sigma^2_1 = 5$, and $\sigma^2_0 = 1$; (7) $\mu_1 = 0.8$, $\mu_0 = 0.79$, $\sigma^2_1 = 5$, and $\sigma^2_0 = 3$; (8) $\mu_1 = 0.8$, $\mu_0 = 0.79$, $\sigma^2_1 = 5$, and $\sigma^2_0 = 1$. We set $T = 1,000$ and ran $10,000$ independent trials for each setting. Although we set $T = 1,000$, we save the recommended arm for each $t\in\{1,2,\dots, 10000\}$. Then, by taking the average over $10,000$ independent trials, we compute the empirical probability of identification for $t\in\{1,2,\dots, 3000\}$. The results of Scenarios 1 and 2 are shown in Figure (ref). The other results are shown in Appendix (ref).
We can confirm that the NA-AIPW (NA), NA-DR (ND), and NA-SA (NS) strategies perform as well as the alpha-elimination. On the other hand, the uniform sampling and NA-IPW strategies show sub-optimal results. The sub-optimal performance of the NA-IPW strategy can be considered that the IPW estimator has a larger variance than that of the AIPW estimator; in fact, the upper bound of the NA-IPW strategy does not match the lower bound, as will be shown in the following.
As well as Lemma (ref), we can show the following corollary. If we use the NA-IPW strategy, we cannot achieve the lower bound owing to the variance $\kappa$, which is different from that of Lemma (ref).
We conjecture that the reason why the NA-DR strategy performs well is that the re-estimated allocation probability mitigates the fluctuation of the allocation probability $w_{a,t}$. A similar phenomenon is reported by Kato2021adr in the context of off-policy evaluation as a paradox because even if we know the true allocation probability, replacing it with an estimator improves the performance.
We also conjecture that the NA-SA strategy also has the same asymptotically optimal properties as our proposed NA-AIPW strategy. See the discussion in Section (ref).
This section presents discussions and related works. More details are shown in Appendix (ref).
Kaufman2016complexity derives distribution-dependent lower bounds for BAI with fixed confidence and a fixed budget, based on the change-of-measure arguments as well as Lai1985. In BAI with fixed confidence, Garivier2016 provides a strategy whose upper bound matches the lower bound. In contrast, in the fixed-budget setting, it was unclear whether there was a strategy whose upper bound matches the lower bound of Kaufman2016complexity. We consider that this is because the estimation error of an optimal target allocation ratio is negligible in BAI with a fixed budget, unlike BAI with fixed confidence, where we can sample each arm until the strategy satisfies a condition. Besides, there are lower bounds different from Kaufman2016complexity, such as Audibert2010, Bubeck2011, and Carpentier2016. \ifnum\Comments=1\textcolor{black}{Recently, Russo2016, Qin2017, Shang2020, and Jourdan2022 propose the Bayesian BAI methods, which are optimal in the sense of the convergence rate of the posterior. Although some of their methods are shown to achieve the lower bounds of Kaufman2016complexity for fixed-confidence BAI, their methods also do not achieve that for fixed-budget BAI. Although the posterior convergence is also optimal in the fixed-budget setting, it does not imply the optimality of the probability of misidentification. For this problem, also see Kasy2021 and Ariu2021.}\fi Another literature is ordinal optimization in the operation research community Dohyun2021,chen2000,glynn2004large. Most of those studies have considered the estimation of the allocation ratio separately from the error rate under known optimal target allocation ratios. There are slaos several studies using local asymptotics to discuss the asymptotic optimality of the Neyman allocation rule in this problem Armstrong2022,adusumilli2022minimax
The key ingredient of our analysis is the AIPW estimator, which consists of a martingale difference sequence and has the minimum asymptotic variance. By focusing on the martingale difference sequence, we address the dependence among observations. Then, we derive the large deviation bound. Our large deviation bound also can be applied to the IPW estimator; however, in this case, the upper bound may not match the lower bound. This is because the asymptotic variance of the AIPW estimator is known to be smaller than that of the IPW estimator but the same as the sample average when there is no selection bias Hahn2011. Note that the minimum variance property of the AIPW estimator is derived from the efficient influence function hahn1998role,Tsiatis2007semiparametric.
We also conjecture that we can show the asymptotic optimality of strategies using the naive sample average estimator in the recommendation rule, although we do not show it in this study. The reason why is because Hahn2011 shows that when using the CLT, the AIPW and sample average estimators have the same asymptotic distribution in a setting similar to BAI with a fixed budget. According to their analysis and our experimental results, we also consider that these have the same large deviation property. This conjecture also implies that the NA-DR and NA-SA strategies are also asymptotically optimal as our proposed NA-AIPW strategy. However, since we cannot use the large deviation bound for martingales to investigate the asymptotic properties of the NA-DR and NA-SA strategies, the analysis becomes difficult owing to the sample dependency. The results of hirano2003 and Hahn2011 may be helpful for solving this problem. Hahn2011 shows the asymptotic distributions of the sample average by going through that of the AIPW estimator.
Unlike two-armed bandit problems and BAI with fixed confidence, the lower bounds are also still unknown for the MAB problems. One of the main reasons is that the KL-divergence is reversed. Under our small gap framework, we can consider two approaches. First, assuming the gap between the top two arms is small, we may directly extend our results. Similarly, the second direction is to assume that the gap among all arms is small; a similar approach could be used to realize proof in the multi-armed case, although we may need more assumptions.
We characterized the optimal probability of misidentification for BAI with a fixed budget when the gap between the expected rewards is small. With the help of a new large deviation expansion we developed, we showed that the performance of our proposed NA-AIPW strategy matches the lower bound under a small gap. Although there are several remaining open questions, our result provides insight into long-standing open problems in BAI. Furthermore, we can extend our results to BAI with multiple arms and contextual information, such as Kato2021Role,Russac2021,QinRusso2022,Kato2022semipara.