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.
43,666 characters · 20 sections · 38 citation commands
Asymptotically Optimal Fixed-Budget Best Arm Identification with Variance-Dependent Bounds
We consider adaptive experiments with multiple treatment arms, such as slot machine arms, different therapies, and distinct unemployment assistance programs. In industrial applications, interactive learning with human feedback for identifying a treatment arm with the highest expected outcome (best treatment arm) is of great interest. This problem is known as the best arm identification (BAI) problem and is a variant of the stochastic multi-armed bandit (MAB) problem Thompson1933,Lai1985. In this study, we investigate fixed-budget BAI, where we aim to minimize the expected simple regret after a fixed number of rounds of an adaptive experiment known as a budget Bubeck2009,Bubeck2011,Audibert2010. In particular, we focus on the worst-case performance of BAI strategies to reflect the uncertainty of human feedback.
In our setting, a decision maker sequentially draws one of the treatment arms based on past observations in each round of an adaptive experiment and recommends an estimated best treatment arm for future experimental subjects after the experiment. We measure the performance of the decision maker's strategy using the expected simple regret, which is the difference between the maximum expected outcome that could be achieved with complete knowledge of the distributions and the expected outcome of the treatment arm recommended by the strategy. Due to the inherent uncertainty, we evaluate the performance using the worst-case criterion among a given class of bandit models Bubeck2011. For nonparametric bandit models with finite variances, we derive worst-case lower bounds. The lower bound's leading factor is characterized by the variances of potential outcomes. We then propose the Two-Stage (TS)-Hirano-Imbens-Ridder (HIR) strategy and show that it is asymptotically minimax optimal, meaning that the leading factor of its worst-case expected simple regret matches that of the lower bound.
In Bubeck2011, worst-case lower bounds for the expected simple regret are derived for bandit models with bounded supports. These lower bounds only rely on the boundedness of the bandit models and do not depend on any other distributional information. In this study, we derive lower bounds that depend on the variances of the bandit models, which require the use of distributional information for an optimal strategy. Our lower bounds are based on change-of-measure arguments using the Kullback-Leibler (KL) divergence, which has been used to derive tight lower bounds in existing studies Kaufman2016complexity. Note that the variance appears as the second-order expansion of the KL divergence.
Furthermore, to improve efficiency in this task, we consider a scenario where a decision-maker can draw a treatment arm based on contextual information. We assume that the contextual information can be observed just before drawing a treatment arm and that arm draws can be optimized using this information. Unlike in the conventional setting of contextual bandits, our goal is to identify the treatment arm with the highest unconditional expected outcome rather than the conditional expected outcome. This setting is motivated by the goals of ATE estimation Laan2008TheCA, Hahn2011 and BAI with fixed confidence and contextual information Russac2021, Kato2021Role. Our findings indicate that utilizing contextual information can reduce the expected simple regret, even if our focus is on the unconditional best treatment arm. Note that this setting is a generalization of fixed-budget BAI without contextual information, and our result holds novelty even in the absence of contextual information.
In BAI, target sample allocation ratios play a critical role in determining the proportion of times each treatment arm is drawn. In many BAI settings, target allocation ratios do not have closed-form solutions and require numerical analysis. However, in our analysis, we derive analytical solutions for several specific cases characterized by the standard deviations or variances of the outcomes. When there are only two treatment arms, the target allocation ratio is the ratio of the standard deviation of outcomes. When there are three or more treatment arms without contextual information, the target allocation ratio is the ratio of the variance of outcomes. This contrasts with the findings of Bubeck2011, which explores the minimax evaluation for bandit models with bounded outcome supports and finds that a strategy of drawing each treatment arm with an equal ratio and recommending a treatment arm with the highest sample average of observed outcomes is minimax optimal. Our results differ from theirs and suggest drawing treatment arms based on the ratio of the standard deviations or variances of outcomes.
Our problem is also closely related to theories of statistical decision-making Wald1949,Manski2000,Manski2002,Manski2004, limits of experiments LeCam1972,Vaart1998, and semiparametric theory hahn1998role, not only to BAI. Among them, semiparametric theory plays an essential role because it allows us to characterize the lower bounds with the semiparametric analogue of the Fisher information Vaart1998. A more detailed survey is presented in Appendix (ref).
In summary, our contributions include: (i) a lower bound for the worst-case expected simple regret; (ii) an analytical solution for the target allocation ratio, characterized by the variances of outcomes; (iii) the TS-HIR strategy; (iv) an asymptotic minimax optimality of the TS-HIR strategy; These findings contribute to a variety of subjects, including statistical decision theory and causal inference, in addition to BAI.
Organization. In Section (ref), we formulate our problem. In Section (ref), we establish lower bounds for the worst-case expected simple regret and a target allocation ratio. In Section (ref), we introduce the TS-HIR strategy. Then, in Section (ref), we demonstrate upper bounds of the strategy and its asymptotic minimax optimality. Finally, we discuss related literature in Section (ref).
We investigate the following setup of fixed-budget BAI. Given a fixed number of rounds $T$, referred to as a budget, in each round $t = 1,2,\dots, T$, a decision maker observes contextual information (covariate) $X_t\in\mathcal{X}$ and draws a treatment arm $A_t \in [K] = \{1,2,\dots, K\}$. Here, $\mathcal{X}\subset \mathbb{R}^D$ is a space of contextual information\footnote{BAI without contextual information corresponds to case where $\mathcal{X}$ is a singleton.}. The decision maker then immediately observes an outcome (or reward) $Y_t$ linked to the drawn treatment arm $A_t$. This setting is referred to as the bandit feedback or Neyman-Rubin causal model Neyman1923,Rubin1974, in which the outcome in round $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 (random) outcome, and $Y^1_t,Y^2_t,\dots, Y^K_t$ are conditionally independent given $X_t$. We assume that $X_t$ and $Y^a_{t}$ are independent and identically distributed (i.i.d.) over $t \in [T] = \{1,2,\dots, T\}$. Our goal is to find a treatment arm with the highest expected outcome marginalized over the contextual distribution of $X_t$ with a minimal expected simple regret after observing the outcome in the round $T$.
We define our goal formally. Let $P$ be a joint distribution of $(Y^1, Y^2, \dots, Y^K, X)$, and $(Y^1_t, Y^2_t, \dots, Y^K_t, X_t)$ be an i.i.d. copy of $(Y^1, Y^2, \dots, Y^K, X)$ in round $t$. We refer to the distribution of the potential outcome $(Y^1, Y^2, \dots, Y^K, X)$ a full-data bandit model Tsiatis2007semiparametric. For a given full-data bandit model $P$, let $\mathbb{P}_{P}$ and $\mathbb{E}_{P}$ denote the probability law and expectation with respect to $P$, respectively. Besides, let $\mu^a(P) = \mathbb{E}_{P}[Y^a_t]$ denote the expected outcome marginalized over $X$. Let $\mathcal{P}$ denote the set of all $P$. An algorithm in BAI is referred to as a strategy, which recommends a treatment arm $\widehat{a}_T \in [K]$ after sequentially drawing treatment arms in $t = 1,2,\dots,T$. With the sigma-algebras $\mathcal{F}_{t} = \sigma(X_1, A_1, Y_1, \ldots, X_{t}, A_t, Y_t)$, we define a BAI strategy as a pair $ ((A_t)_{t\in[T]}, \widehat{a}_T)$, where $(A_t)_{t\in[T]}$ is a sampling rule and $\widehat{a}_T$ is a recommendation rule. The sampling rule draws a treatment arm $A_t \in [K]$ in each round $t$ based on the past observations $\mathcal{F}_{t-1}$ and observed context $X_t$. The recommendation rule returns an estimator $\widehat{a}_T$ of the best treatment arm $\widehat{a}^*(P)$ based on observations up to round $T$. Here, $\widehat{a}_T$ is $\mathcal{F}_T$-measurable. For a bandit model $P\in\mathcal{P}$ and a strategy $\pi\in\Pi$, let us define the simple regret as
Our goal is to find a strategy that minimizes the worst-case expected simple regret $\sup_{P\in\widetilde{\mathcal{P}}} \mathbb{E}_P[r_T(\pi)(P)]$, where the expectation is taken over the randomness of $\widehat{a}_T\in[K]$ and $\widetilde{\mathcal{P}}\subseteq \mathcal{P}$ is a specific class of bandit models. First, we derive the worst-case lower bounds in Section (ref). Then, we propose an algorithm in Section (ref) and show the minimax optimality for the expected simple regret in Section (ref).
Notation. Let $\mu^a(P)(x) := \mathbb{E}_P[Y^a|X=x]$ be the conditional expected outcome given $x\in\mathcal{X}$ for $a\in[K]$. Let $\left(\sigma^a(P)\right)^2$ be the variance of $Y^a$ under $P\in\mathcal{P}$. Let $\Delta^a(P)$ be a gap $\max_{a\in[K]}\mu^a(P) - \mu^{\widehat{a}_T}(P)$.
In this section, we derive lower bounds for the worst-case expected simple regret. The expected simple regret can be expressed as \[\mathbb{E}_P[r_T(\pi)(P)] = \sum_{b\in[K]}\Delta^b(P)\mathbb{P}_{P}\left(\widehat{a}_T = b\right).\] Here, for each fixed $\mu^a(P), P\in\widetilde{\mathcal{P}}$, independent of $T$, the probability of misidentification, \[\mathbb{P}_{P}\left(\widehat{a}_T \notin \operatorname*{arg\,max}_{a\in[K]}\mu^a(P)\right),\] converges to zero with an exponential rate, while $\Delta^{\widehat{a}_T}(P)$ is the constant. Therefore, we disregard $\Delta^{\widehat{a}_T}(P)$, and the convergence rate of $\mathbb{P}_{P}\left(\widehat{a}_T \notin \operatorname*{arg\,max}_{a\in[K]}\mu^a(P)\right)$ dominates the expected simple regret. In this case, to evaluate the convergence rate of $\mathbb{P}_{P}\left(\widehat{a}_T \notin \operatorname*{arg\,max}_{a\in[K]}\mu^a(P)\right)$, we utilize large deviation upper bounds. In contrast, if we examine the worst case among $\widetilde{\mathcal{P}}$, which includes a bandit model such that the gaps between the expected outcomes converge to zero with a certain order of the sample size $T$, a bandit model $P$ whose gaps converge to zero at a rate of $O(1/\sqrt{T})$ dominates the evaluation of the expected simple regret. In general, for the gap $\Delta^{b}(P)$, the worst-case simple regret is approximately given as
where $(C^b)_{b\in[b]}$ are constants Bubeck2011. This is because $\mathbb{P}_{P}\left(\widehat{a}_T = b\right)$ is approximately $\exp\Big(-T\left(\Delta^{b}(P)\right)^2/ C^b\Big)$. Then, the maximum is obtained when $\Delta^b(P) = \sqrt{\frac{C^b}{T}}$ for a constant $C^b > 0$, which balances the regret caused by the gap $\Delta^{b}(P)$ and probability of misidentification $\mathbb{P}_{P}\left(\widehat{a}_T = b\right)$.
Bubeck2011 shows a (non-asymptotic) lower bound for bandit models with bounded support, where a strategy with the uniform sampling rule is optimal. Let us denote the class of bandit models with bounded outcomes by $P^{[0, 1]}$, where each potential outcome $Y^a_t$ is in $[0, 1]$. Then, the authors show that for all $T \geq K \geq 2$, any strategy $\pi\in \Pi$ satisfies $\sup_{P\in P^{[0, 1]}} \mathbb{E}_P[r_T(\pi)(P)] \geq \frac{1}{20} \sqrt{\frac{K}{T}}$. For this worst-case lower bound, the authors show that a strategy with the uniform sampling rule and empirical best arm (EBA) recommendation rule is optimal, where we draw $A_t = a$ with probability $1/K$ for all $a\in[K]$ and $t\in[T]$ and recommend a treatment arm with the highest sample average of the observed outcomes, which is referred to as the uniform-EBA strategy. Under the uniform-EBA strategy $\pi^{\mathrm{Uniform}\mathchar`-\mathrm{EBM}}$, for $T = K\lfloor T / K \rfloor$, $\sup_{P\in\mathcal{P}^{[0, 1]}} \mathbb{E}_P\left[r_T\left(\pi^{\mathrm{Uniform}\mathchar`-\mathrm{EBM}}\right)(P)\right] \leq 2 \sqrt{\frac{K\log K}{T + K}}$. Thus, the upper bound matches the lower bound if we ignore the $\log K$ and constant terms.
Although the uniform-EBA strategy is nearly optimal, a question remains whether more knowledge about the class of bandit models could be used to derive a tight lower bound and propose another optimal strategy consistent with the novel lower bound. As the worst-case lower bound in Bubeck2011 is referred to as a distribution-free lower bound, the lower bound does not utilize distributional information, such as variance. In this study, although we still consider worst-case expected simple regret, we develop lower and upper bounds depending on distributional information. Specifically, we characterize the bounds by the variances of potential outcomes. In a worst-case analysis of simple regret, the evaluation of the simple regret is dominated by an instance of a bandit model such that the gaps between the best and suboptimal treatment arms are $O(1/\sqrt{T})$. Here, recall that tight lower bounds depend on the KL divergence Lai1985,Kaufman2016complexity. Additionally, the second-order Taylor series expansion of the KL divergence with regard to the gaps can be interpreted as the variance (inversed Fisher information). Therefore, the tight lower bounds employing distributional information in the worst-case expected simple regret should be characterized by the variances (the second-order Taylor series expansion of the KL divergence). In the following sections, we consider worst-case lower bounds characterized by the variances of bandit models.
In this section, we derive asymptotic lower bounds for the worst-case expected simple regret. To derive lower bounds, we often utilize an alternative hypothesis. We consider a bandit model whose expected outcomes are the same among the $K$ treatment arms. We refer it to as the null bandit model.
Then, we consider a class of bandit models with unique fixed variances for null bandit models, called local location-shift bandit models. Furthermore, we assume that the moments of potential outcomes are bounded. We define our bandit models as follows.
We refer to this class of bandit models as local location-shift bandit models. Our lower bounds are characterized by $\sigma^a(x)$, a conditional variance of null bandit models.
Local location-shift models are a commonly employed assumption in statistical analysis LehmCase98. Two key examples are Gaussian and Bernoulli distributions. Under Gaussian distributions with fixed variances, for all $P$, the variances are fixed and only mean parameters shift. Such models are generally called location-shift models. Additionally, we can consider Bernoulli distributions if $\mathcal{P}^*$ includes one instance of $\mu^1(P) = \cdots = \mu^K(P)$ to specify one fixed variance $\sigma^a(x)$. Furthermore, our bandit models are nonparametric within the class and include a more wide range of bandit models, similar to the approach of Barrier2022.
When contextual information is unavailable, condition (v) can be omitted. Although condition (v) may seem restrictive, its inclusion is not essential for achieving efficiency gains through the utilization of contextual information; that is, the upper bound can be smaller even when this condition is not met. However, it is required in order to derive a matching upper bound for the following lower bounds. Note that the same lower bounds can be derived without condition (v).
We consider a restricted class of strategies such that under null bandit models, any strategy in this class recommends one of the arms with an equal probability ($1/K$).
For each $x\in\mathcal{X}$, let us define an average allocation ratio under a bandit model $P\in\mathcal{P}$ and a strategy $\pi\in\Pi$ as $\kappa_{T, P}(a|x) = \frac{1}{T}\sum^T_{t=1}\mathbb{E}_{P}\left[ \mathbbm{1}[A_t = a]| X_t = x\right]$. This quantity represents the average sample allocation to each treatment arm $a$ under a strategy. Let $\mathcal{W}$ be a set of all measurable functions $\kappa_{T, P}:\mathcal{X} \to (0, 1)$ such that $\sum_{a\in[K]} \kappa_{T, P}(a|x) = 1$ for each $x\in \mathcal{X}$. Then, we prove the following lower bound. The proof is shown in Appendix (ref).
We refer to $w^* = \operatorname*{arg\,min}_{w\in\mathcal{W}}\max_{a\in[K]}\sqrt{\mathbb{E}^X\left[\frac{\left(\sigma^{a}(X)\right)^2}{w(d|X)}\right]}$ as the target allocation ratio, which is an optimal sample allocation ratio that an optimal strategy aims to achieve. The target sample allocation ratios are used to define a sampling rule in our proposed strategy. In some specific cases, we can obtain analytical solutions for $w^*$. In this study, we consider two cases. As an example, in the following section, we consider a case without contextual information.
Our result generalizes BAI without contextual information, where $\mathcal{X}$ is a singleton. Let $(\sigma^a)^2$ be the unconditional variance of $Y^a_t$. When there is no contextual information, we can obtain the following lower bound with an analytical solution of the target allocation ratio $w^*\in\mathcal{W}$.
When contextual information is available, for $w(a|x) = \frac{\left(\sigma^a(x)\right)^2}{\sum_{b\in[K]}\left(\sigma^b(x)\right)^2}$, the lower bound is \[\frac{1}{12}\sqrt{\sum_{a\in[K]}\mathbb{E}^X\left[\left(\sigma^a(X)\right)^2\right]} + o(1).\] It is worth noting that by using the law of total variance, $(\sigma^a)^2 \geq \mathbb{E}^X\left[\left(\sigma^{a}(X)\right)^2\right]$. Therefore, by utilizing contextual information, we can tighten the lower bounds as \[\sqrt{\sum_{a\in[K]}\left(\sigma^{a}\right)^2} \geq \sqrt{\sum_{a\in[K]}\mathbb{E}^X\left[\left(\sigma^{a}(X)\right)^2\right]} \geq \min_{w\in\mathcal{W}}\max_{d\in[K]}\sqrt{\mathbb{E}_X\left[\frac{\left(\sigma^{d}(X)\right)^2}{w(d|X)}\right]}.\] This improvement is efficiency gain by using contextual information.
For two-armed bandits ($K=2$), we can refine the lower bound as follows. In this case, we can also obtain an analytical solution of the target allocation ratio even when there is contextual information.
Here, note that $\sqrt{\sum_{a\in[2]}\left(\sigma^{a}\right)^2} \geq \sqrt{\left(\sigma^{1} + \sigma^{2}\right)^2}$. This target allocation ratio is the same as that in Kaufman2016complexity for the probability of misidentification minimization. Also see Section (ref). The proofs is shown in Appendix (ref).
Note that for $K\geq 3$, we have an analytical solution of the target allocation ratio only when there is no contextual information, and the target allocation ratio is the ratio of the variances. In contrast, for $K=2$, we can obtain analytical solutions of the target sample allocation ratio even when there is contextual information, and it is the ratio of the (conditional) standard deviation.
This section introduces our strategy, which is inspired by the adaptive experimental design of Hahn2011. Our strategy comprises the following sampling and recommendation rules: First, we divide the budget into two parts. In the first stage, we uniformly randomly draw a treatment arm. In the second stage, we draw treatment arms to achieve the target allocation ratio. After the second stage, we recommend the best arm using the HIR estimator. We refer to this strategy as the TS-HIR strategy.
First, we define a target allocation ratio, which is used to determine our sampling rule. As discussed in Section (ref), for certain cases, the target allocation ratio has analytical solutions: for $a\in[K]$, $w^*(a|x) = \frac{\sigma^{a}(x)}{\sigma^{1}(x) + \sigma^{2}(x)}$ if $K = 2$, and $w^*(a) = \frac{ \left(\sigma^{a}\right)^2}{\sum_{b\in[K]} \left(\sigma^{b}\right)^2}$ if $K \geq 3$ and there is no contextual information. When the variances are unknown, this target allocation ratio is also unknown. Therefore, we estimate it during the adaptive experiment and use the estimator as the probability of drawing a treatment arm.
The TS-HIR strategy consists of the following two stage experiments. For each $a\in[K]$ and $x\in\mathcal{X}$, let $w^{(1)}(a|x)$ and $w^{(2)}(a|x)$ be sample allocation ratios in the first and second stages, respectively. When there is no contextual information, let $w^{(s)}(a|x)$ be $w^{(s)}(a)$ fore each $s\in\{1, 2\}$. We first fix $r\in(0, 1)$ independent from $T$ and $w^{(1)}(a|x)$ such that $w^{(1)}(a|x) > C$ and $\sum_{a\in[K]}w^{(1)}(a|x) = 1$, where $C$ is independent from $T$ \footnote{Although $r$ is assumed to be independent from $T$, we use $r$ such that $\lceil rT \rceil > K + 1$ in the following sections.}. In Stage 1, after drawing each treatment arm $1,2,\dots, K$ at each round $1,2,\dots,K$, we draw treatment arm $A_t = a$ with probability $w^{(1)}(a)$ until $\lceil rT\rceil$.
After Stage 1, we draw treatment arms with probability $w^{(2)}$, chosen to minimize empirical version of the lower bounds as follows:
where $\mathcal{H}$ is a class of models of $w^{(2)}$ and can be constrained if there are constraints on the target allocation ratio. Suppose that $r$ is sufficiently small. If $K= 2$ or $K \geq 3$ and there are not contextual information, we have the following analytical solutions for each $a\in [K]$: \[w^{(2)}(a|x) = \left\{\frac{\widehat{\sigma}^a(x)}{\widehat{\sigma}^1(x) + \widehat{\sigma}^2(x)} - rw^{(1)}(a|x)\right\}/(1-r)\] if $K = 2$, and \[w^{(2)}(a) = \left\{\frac{\left(\widehat{\sigma}^a\right)^2}{\sum_{b\in[K]}\left(\widehat{\sigma}^b\right)^2} - rw^{(1)}(a)\right\}/(1-r)\] if $K \geq 3$ and there is no contextual information. Specifically, at each $t\in [T]$, we first draw $\gamma_t$ from a uniform distribution with support $[0, 1]$. Then, we draw $A_t = 1$ if $\gamma_t \leq w^{(2)}(1|X_t)$ and $A_t = a$ for $a \geq 2$ if $\gamma_t \in \left(\sum^{a-1}_{b=1}w^{(2)}(b|X_t), \sum^a_{b=1}w^{(2)}(b|X_t)\right]$.
After Stage 2 (after round $T$), for each $a\in[K]$, we estimate $\mu^a$ for each $a\in[K]$ and recommend the maximum. To estimate $\mu^a$, we use the HIR hirano2003,Hahn2011 estimator defined as
Then, we recommend $\widehat{a}^{\mathrm{HIR}}_T \in [K]$ as
Note that when there is no contextual information, the HIR estimator is equivalent to the following Sample Average (SA) estimator: $\widehat{\mu}^{\mathrm{SA}, a}_{T} =\frac{1}{\sum^T_{s=1}\mathbbm{1}[A_s = a]}\sum^T_{s=1}\mathbbm{1}[A_s = a]Y^a_s$.
In this section, we derive upper bounds for the worst-case expected simple regret under local location-shift models with our proposed TS-HIR strategy. Let us define $\Delta^{a,b}(P) = \mu^a(P) - \mu^b(P)$, $\Delta^{a,b}(P)(x) = \mu^a(P)(x) - \mu^b(P)(x)$, and $\widehat{\Delta}^{\mathrm{HIR}, a, b}_{T} = \widehat{\mu}^{\mathrm{HIR}, a}_{T} - \widehat{\mu}^{\mathrm{HIR}, b}_{T}$ for all $a,b\in]K]$ and $x\in\mathcal{X}$. The asymptotic normality of the HIR estimator, which is derived by Hahn2011 using arguments of empirical process, plays an important role in our proof.
Then, to prove the upper bound for the expected simple regret, we first derive the that for the probability of misidentification by the Chernoff bound an Proposition (ref). After that, we derive the worst-case upper bound as well as Bubeck2011.
First, we show the upper bound for the probability of misidentification, which is needed for deriving the upper bound for the expected simple regret. Let $V^{a}(P) = V^{a^*(P),a}(P)$ for each $a\in[K]$.
The asymptotic optimality for the probability of misidetification is also intriguing problem. There are several arguments for the lower bounds kaufmann2020hdr. In Section (ref), we show that the upper bound in Theorem (ref) is asymptotically optimal when $K=2$ and $\Delta^{1, 2}(P) \to 0$. Also see Section (ref). The proof is shown in Appendix (ref), which utilizes the asymptotic normality of $\widehat{\Delta}^{\mathrm{HIR}, a, b}_{T}$.
Theorem (ref) yields the following theorem on the upper bound for the expected simple regret.
We first present an asymptotic worst-case upper bound of our proposed TS-HIR strategy. Suppose that there is no contextual information or $\mathcal{X}$ is discrete. We put the following assumption on the convergence rate of estimators of the nuisance parameters. We show the following theorem on the worst-case upper bound and the asymptotic minimax optimality. The proof is shown in Appendix (ref).
Because we can obtain an analytical solution of $w^*$ when $K = 2$ with and without contextual information and $K \geq 3$ without contextual information, we have the following upper bound in those case:
when $K = 2$, and
when $K \geq 3$, and there is no contextual information. Thus, when $T\to \infty$, the upepr and lower bound match.
Although we do not discuss the lower bounds for the probability of misidentification, our upper bound for the probability of misidentification in Theorem (ref) aligns with the lower bound established by Kaufman2016complexity for two-armed Gaussian bandits. Let $\mathcal{P}^G \subset \mathcal{P}^*$ denote two-armed Gaussian bandits defined in Kaufman2016complexity with fixed variance $(\sigma^1)^2. (\sigma^2)^2 > 0$. Their work demonstrates that $\limsup_{T \to \infty} - \frac{1}{T}\log \mathbb{P}_{P}(\widehat{a}^{\mathrm{HIR}}_T \neq a^*(P)) \le {(\Delta^{1,2}(P))^2}/{2 \big(\sigma^1 + \sigma^2\big)^2}$ when $P\in\mathcal{P}^G$. Our upper bound coincides with the lower bound when $\Delta^{1,2}(P) \to 0$.
From Theorem (ref), $- \frac{1}{T}\log \mathbb{P}_{P}\left(\widehat{a}^{\mathrm{HIR}}_T \neq a^*(P)\right)\geq \frac{(\Delta^{1,2}(P))^2}{2V^{1, 2}(P)} - \left\{\frac{\Delta^{1, 2}(P)}{\sqrt{TV^{1, 2}(P)}} + \frac{(\Delta^{1, 2}(P))^2}{2V^{1, 2}(P)}\right\}\varepsilon$.
When for two-armed Gaussian bandits, the upper bound matches the lower bound in Kaufman2016complexity. We do not discuss the details of the lower bounds for probability of misidentification for more general cases because there are technical difficulties and many open problems. Also see kaufmann2020hdr, Ariu2021, Qin2022open, and degenne2023existence for the details.
When the contextual information is continuous, we cannot apply the TS-HIR strategy. In this case, we use the AS-AIPW strategy, which consists of the Adaptive Sampling (AS) and Augmented Inverse Probability Weighting (AIPW) rules. Under the AS rule, at each $t$, we estimate $w^*$ and draw treatment arm $a$ with probability $\widehat{w}_{t}(a|X_t)$, where $\widehat{w}_{t}$ is an estimates of $w^*$. Then, at each $T$, we estimate $\mu^{a}(P)$ by using the AIPW estimator defined in Appendix (ref) and recommend a treatment arm with the highest estimate value as the best arm. The AIPW estimator debiases the sample selection bias resulting from arm draws based on contextual information. The details is shown in Appendix (ref).
We compare our TS-HIR and AS-AIPW strategies with the Uniform-EBA Bubeck2011, and Successive Rejection Audibert2010 Gabillon2012.
In this section, we investigate two setups with $K=2, 5$ without contextual information. The best treatment arm is arm $1$ and $\mu^1(P) = 1$. The expected outcomes of suboptimal treatment arms are equivalent and denoted by $\widetilde{\mu} = \mu^2(P) = \cdots = \mu^K(P)$. We use $\widetilde{\mu} = 0.90$. When $K=2$, we fix the variances as $((\sigma^1)^2, (\sigma^2)^2) = (5, 1)$; when $K = 5$, we fix the variances as $((\sigma^1)^2, (\sigma^2)^2, (\sigma^3)^2, (\sigma^4)^2, (\sigma^5)^2) = (5, 1, 2, 3, 4)$. We continue the experiments until $T = 5,000$ when $\widetilde{\mu} = 0.80$ and $T=15,000$ when $\widetilde{\mu} = 0.90$. We conduct $100$ independent trials for each setting. At each $t\in\{1000, 2000, 3000, \cdots, 14000, 15000\}$, we plot the empirical simple regret in Figure (ref). Additional results with other settings, including contextual information, are presented in Appendix (ref).
From Figure (ref) and Appendix (ref), we can observe that our proposed strategies perform well when $K=2$. When there exists a contextual information, our methods tends to show better performances than the others. Although our strategies show preferable performances in many settings, other strategies also perform well. We conjecture that our strategies exhibit superiority against other methods when $K$ is small (mismatching term in the upper bound), the gap between the best and suboptimal arms is small, and the variances significantly vary across arms. As the superiority depends on the situation, we recommend a practitioner to use several strategies in a hybrid way.
We conducted an asymptotic worst-case analysis of the simple regret in fixed-budget BAI with contextual information. Initially, we obtained lower bounds for local location-shift bandit models, where the variances of potential outcomes characterize the asymptotic lower bounds as a second-order approximation of the KL divergence. Based on these lower bounds, we derived target allocation ratios, which were used to define a sampling rule in the TS-HIR strategy. Finally, we demonstrated that the TS-HIR strategy achieves minimax optimality for the expected simple regret.
\onecolumn