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.
91,551 characters · 24 sections · 153 citation commands
Best Arm Identification with Contextual Information under a Small Gap
This paper considers an adaptive experimental design to accurately identify the best treatment arm among a finite set of candidates after the last round of the experiment. The stochastic multi-armed bandit (MAB) problem is a classical abstraction of the sequential decision-making problem Thompson1933,Robbins1952,Lai1985. Best arm identification (BAI) is an instance of the MAB problem. In BAI, we consider pure exploration to identify the best treatment arm, which is a treatment arm that yields the highest expected reward. In this study, we study BAI with a fixed budget and contextual information, whose goal is to identify the best treatment arm minimizing the probability of misidentifying the best treatment arm after a fixed number of rounds of adaptive experiments, called a sample size or a budget Bubeck2009,Bubeck2011,Audibert2010. To gain efficiency in this task, during an adaptive experiment, one strategy is to employ a random covariate (side information) that characterizes the features of treatment arms, which is referred to as a context. A context can be observed before drawing one of treatment arms in an adaptive experiment. Based on observed context, a strategy chooses a treatment arm. Our setting is a generalization of BAI with a fixed budget Carpentier2016. The main focus of this paper is to derive asymptotically optimal strategies for the purpose of efficiently identifying the best treatment arm, rather than how to learn optimal context-specific bandit strategies, as studied in the literature of contextual bandit.
One of the main research interests in bandit problems is clarifying a tight lower bound on the probability of misidentification (a theoretical limit of performance). In this study, we call a strategy asymptotically optimal if, under the strategy, a probability of misidentification matches a lower bound as the budget goes to infinity. However, in BAI, it is unknown whether a strategy exists under which a probability of misidentification matches the lower bound in BAI with a fixed budgetKaufman2016complexity. Furthermore, when we can employ contextual information, even the lower bound has been unknown as well as an asymptotically optimal strategy, unlike BAI with fixed confidence Russac2021,Kato2021Role, another setting of BAI Garivier2016.
We develop an asymptotically optimal strategy for BAI with a fixed budget and contextual information under a small-gap regime, where the gaps of the expected rewards of the best and suboptimal treatment arms converge to zero.\footnote{This regime is also considered by Kato2022small, and some of our results are employed and extended from their results.} This regime is one of the hardest situation to identify the best treatment arms among the other suboptimal treatment arms. First, we derive lower bounds for the probability of misidentification by extending the lower bound of Kaufman2016complexity under the small-gap regime. Based on this lower bound, we derive an optimal target sample allocation ratio, which is the limit of the ratio of the number of samples allocated to each treatment arm within an adaptive experiment under an optimal strategy. Then, we propose our BAI strategy, the Random Sampling (RS)-Augmented Inverse Probability Weighting (AIPW) strategy, which consists of the RS rule using an estimated target sample allocation ratio and a recommendation rule using the AIPW estimator. We prove the asymptotic optimality of the proposed strategy when the budget goes to infinity under the small-gap regime.
The existence of an asymptotically optimal strategy has long been an open problem in this field. glynn2004large proposes optimal strategies based on optimally selected target sample allocation ratios. However, they assume that the optimal target sample allocation ratio is known in advance and do not consider the issue of estimating it. Based on the change-of-measure arguments popularized by Lai1985, Kaufman2016complexity derives lower bounds for the misidentification probability, which are agnostic to the optimal target sample allocation ratios. Despite the seminal result, optimal strategies has not been proposed for the lower bounds kaufmann2020hdr. In fact, when the gaps between the expected rewards of the best and suboptimal treatment arms are fixed, Carpentier2016 shows that there is no strategy under which the probability of misidentificaton matches the lower bounds derived by Kaufman2016complexity. Thus, the debate over tight lower bounds and optimal algorithms is not settled, and various approaches have been proposed kaufmann2020hdr,Kasy2021,Ariu2021,Komiyama2022.
We consider that a contributing factor on the mismatch between the upper and lower bounds is an estimation error of the optimal target sample allocation ratio, which affects the probability of misidentification. To address this issue, we propose a small-gap regime for the following two reasons. The first is that an optimal strategy under a small gap has an important practical implication itself because it means asymptotic optimality under one of the worst cases. The second reason is more technical. Under the fixed-gap regime, it has been shown that there is no asymptotically optimal strategy in the sense that its upper bounds match lower bounds derived in the way of Lai1985 Carpentier2016. This regime makes the asymptotic optimality argument in fixed-budget BAI tractable by allowing the evaluation of optimal allocation probabilities to be ignored. Thus, this study addresses the open question by showing an asymptotically optimal strategy under a small-gap regime. In addition, we investigate the efficiency gain by using contextual information, which is a generalization of conventional BAI. Furthermore, we demonstrate an analytical solution for the target sample allocation ratio, which has long been unknown.
In both settings of BAI with a fixed budget and fixed confidence, strategies using contextual information have not been sufficiently explored. In BAI with fixed confidence, recent studies have proposed the use of contextual information to identify a treatment arm with the highest expected reward marginalized over contextual information Kato2021Role,Russac2021.
Related problems have been frequently considered in studies of causal inference, which mainly discuss the efficient estimation of causal parameters such as the gap between expected outcomes of two treatment arms marginalized over the covariate (contextual) distribution Laan2008TheCA,Hahn2011,Meehan2020,Kato2020adaptive, rather than BAI. The gap is also called the average treatment effect (ATE) in this literature imbens_rubin_2015. In efficient ATE estimation with an adaptive experiment, the asymptotic variance of the estimator can be reduced with the help of covariate information.
In this study, we find that when identifying the best treatment arm marginalized over contextual information in BAI with a fixed budget, we can improve the performance of a strategy by employing contextual information. To the best of our knowledge, our study is the first to consider BAI with contextual information in a fixed-budget setting.
\paragraph{Organization.} This paper is organized as follows. In Section (ref), we formulate our problem. In Section (ref), we derive the general lower bounds for BAI with a fixed budget and the target sample allocation ratio under a small-gap regime. In Section (ref), we propose the RS-AIPW strategy. Then, in Section (ref), we show that the proposed strategy is optimal in a sense that the upper bound for the probability of misidentification matches the lower bound. We introduce related work in (ref) and discuss several topics in Sections (ref). Finally, we present the proof of the lower bound in Section (ref).
We consider the following setting of BAI with a fixed budget and contextual information. Given a fixed number of rounds $T$, also called a budget, for each round $t = 1,2,\dots, T$, an agent observes a context (covariate) $X_t\in\mathcal{X}$ and chooses a treatment arm $A_t \in [K] = \{1,2,\dots, K\}$, where $\mathcal{X}\subset \mathbb{R}^d$ denotes the context space. Then, the agent immediately receives a reward (or outcome) $Y_t$ linked to the chosen treatment arm $A_t$. This setting is called the bandit feedback or Rubin causal model Neyman1923,Rubin1974; that is, a reward 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) reward, 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 reward marginalized over contextual distribution of $X_t$ with a minimal probability of misidentification after observing the reward 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)$ at round $t$. We call distributions of the potential random variables $(Y^1, Y^2, \dots, Y^K, X)$ full-data bandit models Tsiatis2007semiparametric,imbens_rubin_2015. For $P$, let $\mathbb{P}_{P}$, $\mathbb{E}_{P}$, and $\mathrm{Var}_{P}$ be the probability, expectation, and variance in terms of $P$ respectively and $\mu^a(P) = \mathbb{E}_{P}[Y^a] = \mathbb{E}_P[\mu^a(P)(X) ]$ be the expected reward marginalized over the context $X$, where $\mu^a(P)(x) = \mathbb{E}_{P}[Y^a|X=x]$ is the conditional expected reward given $x\in\mathcal{X}$. Let $\mathcal{P}$ be a set of all joint distributions $P$ such that the the best treatment arm $a^*(P)$ uniquely exists; that is, there exists $a^*(P)\in[K]$ such that $\mu^{a^*(P)} > \max_{b \in [K]\backslash a^*(P)} \mu^b$. An algorithm in BAI is called a strategy, which recommends a treatment arm $\widehat{a}_T \in [K]$ after sequentially sampling 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
Let $P_0$ be the “true” bandit model of the data generating process. Then, our goal is to find a BAI strategy that minimizes the probability of misidentification $\mathbb{P}_{P_0}( \widehat{a}_T \neq a^*(P_0))$.
\paragraph{Notation.} For all $a\in[K]$ and $x\in\mathcal{X}$, let $\nu^a(P)(x) = \mathbb{E}_{P}[(Y^a)^2|x]$ and $\mathrm{Var}_P(Y^a|x) = \left(\sigma^a(P)(x)\right)^2$. For the true bandit model $P_0\in\mathcal{P}$, we denote $\mu^a(P_0) = \mu^a_0$, $\mu^a(P_0)(x) = \mu^a_0(x)$, $\nu^a_0(x) = \nu^a(P_0)(x)$, and $\sigma^a_0(x) = \sigma^a(P_0)(x)$. Let $Y^{a^*_0}_t = Y^*_t$, $a^*(P_0) = a^*_0$, $\mu^{a^*_0}_0 = \mu^*_0$, and $\nu^{a^*_0}_0 = \nu^*_0$. For the two Bernoulli distributions with mean parameters $\mu, \mu' \in [0, 1]$, we denote the KL divergence by $d(\mu, \mu') =\mu\log (\mu/\mu') + (1-\mu)\log((1-\mu)/(1-\mu'))$ with the convention that $d(0, 0) = d(1,1) = 0$.
In this section, we derive lower bounds for the probability of misidentification $\mathbb{P}_{P_0}( \widehat{a}_T \neq a^*_0)$ under a small gap; that is, $\mu^*_0- \mu^{a}_0 \to 0$ for all $a\in [K]$. Our lower bounds are extensions of distribution-dependent lower bounds shown by Kaufman2016complexity. We call them the lower bounds under a small-gap. We derive the lower bounds for two-armed bandits and bandits with more than three arms separately.
First, the following conditions for a class of the bandit model $\mathcal{P}$ are assumed throughout this study.
For a class of bandit models, we consider the locally location-shift class class defined as follows.
Let $\zeta(x)$ be a density of $X_t$ under a location-shift bandit class. Then, according to the law of total variance, the (unconditional) variance $\left(\sigma^{a}(P)\right)^2$ of $Y^a_t$ given as \[\left(\sigma^{a}(P)\right)^2 = \int \left(\sigma^a(x)\right)^2 \zeta(x)\mathrm{d}x + \int \left(\mu^a(P)(x) - \mu^a(P)\right)^2\zeta(x)\mathrm{d}x\geq \int \left(\sigma^a(x)\right)^2 \zeta(x)\mathrm{d}x. \] for all $a\in[K]$. For simplicity, $\sigma^{a^*_0}$ is denoted by $\sigma^*$.
Here, we raise two examples as members of this class.
In this section, we derive the lower bounds for this class.
To derive the lower bound, we first restrict our BAI strategy to a consistent strategy, which is also considered in Kaufman2016complexity.
In large deviation efficiency of hypothesis testing, a similar consistency is assumed Vaart1998.
Although we can derive the lower bound for any consistent strategy for two-armed bandits ($K=2$), we need further restrictions on a class of strategies to derive the lower bound for multi-armed bandits with $K\geq 3$. In this paper, we restrict a class of strategies to an asymptotically invariant strategy defined as follows:
Then, we present lower bounds for bandit models belonging to the location-shift bandit class. Let $\mathcal{W}$ be a set of all measurable functions such that $w: [K]\times\mathcal{X} \to (0, 1)$ and $\sum_{a\in[K]} w(a|x) = 1$ for all $x\in\mathcal{X}$. We refer to $w\in\mathcal{W}$ an allocation ratio, which can be used to obtain the following lower bound. The proof is shown in Appendix (ref).
We refer to a statistical model as a semiparametric model if the distribution is characterized by both of the finite dimensional parameters (gaps of the expected rewards) and infinite dimensional parameters (e.g., the distribution of contextual information). The denominator of the first term of the RHS in the lower bound corresponds to a semiparametric efficiency bound, which corresponds to a Cram\'er-Rao lower bound for semiparametric models bickel98,Vaart1998, of the gap (ATE) between two treatment arms $a,b\in[K]$ $a\neq b$ under an allocation ratio $w \in \mathcal{W}$ in the supremum hahn1998role\footnote{More precisely, the semiparametric efficiency bound of the asymptotic variance of the ATE between two treatment arms $a,b\in[K]$ $a\neq b$ is given as $\mathbb{E}_{P_0}\left[\frac{\left(\sigma^a_0(X_t)\right)^2}{w(a| X_t)} + \frac{\left(\sigma^b_0(X)\right)^2}{w(b| X_t)} + \big\{(\mu^*_0(X_t) - \mu^a_0(X_t)) - (\mu^*_0 - \mu^a_0)\big\}^2\right]$ hahn1998role, where $\big\{(\mu^*_0(X_t) - \mu^a_0(X_t)) - (\mu^*_0 - \mu^a_0)\big\}^2$ appears unlike ours.}. This result implies that the optimal BAI strategy chooses treatment arms so as to reduce the asymptotic variance of estimators for the gaps (ATEs) between the best and suboptimal treatment arms. Here, When the asymptotic variance of the gap estimators is small, the gaps can be estimated more accurately. Theorem (ref) will make this implication clearer.
Here, the supremum of the RHS in the lower bound can be replaced with the maximum as
In Theorem (ref), we show the analytical solution of $w^* = \operatorname*{arg\,max}_{w \in \mathcal{W}}\min_{a\neq a^*_0} \frac{1}{2\Omega^{a}_0(w)}$. Then, the analytical solution of this maximization problem and refined lower bound are shown in the following theorem.
Because all gaps $\mu^*_0 - \mu^a_0$ are assumed to be upper bounded by $\Delta_a$, we consider a situation where the expected rewards of all suboptimal treatment arms are in $[\mu^*_0 - \Delta_0, \mu^*_0)$. To obtain lower bounds, it is sufficient to consider a case where $\mu^b = \mu^*_0 = \Delta_0$, under which the largest lower bounds are given (Figure (ref)). Based on implications obtained from Theorem (ref), we construct our strategy in Section (ref).
Here, note that an allocation ratio $w$ in the supremum corresponds to an expectation of sampling rule $\frac{1}{T}\sum^T_{t=1}\mathbbm{1}[A_t = a]$ conditioned on $x$ under an alternative hypothesis $Q\in\mathcal{P}$ such that $Q\neq P_0$, which is used to derive the lower bound. From the definition of asymptotically invariant strategies, the maximizer $\widetilde{w}$ also work as a target sample allocation ratio used in our proposed strategy; that is, n expectation of sampling rule $\frac{1}{T}\sum^T_{t=1}\mathbbm{1}[A_t = a]$ conditioned on $x$ under an alternative hypothesis $P_0\in\mathcal{P}$. In Sections (ref) and (ref), we show that by allocation samples following the target sample allocation ratio, the upper bound for the probability of misidentification in our proposed strategy matches the lower bound. Thus, we can confirm that these maximizers correspond to the optimal target sample allocation ratio.
In this section, we discuss the interpretations of lower bounds under the small-gap regime and restrictions on strategies. Although Kaufman2016complexity and Carpentier2016 derive the lower bound for BAI with a fixed budget, their lower bounds do not employ a small-gap regime. Besides, Kaufman2016complexity considers only a consistent strategy while we further restrict strategies to asymptotically invariant. We discuss the meanings of these elements in lower bounds. First, we review the lower bound for two-armed Gaussian bandits of Kaufman2016complexity, which is derived for consistent strategies. However, this lower bound cannot be extended to multi-armed bandits. Therefore, we next consider restricting strategies to asymptotically invariant ones and the small-gap regime. We explain the meanings and benefits of these restrictions. Finally, we raise specific cases of our locally location-shift bandit class.
\paragraph{Review of distribution-dependent lower bounds without contextual information.} First, we review the distribution-dependent lower bound for the probability of misidentification in two-armed bandits following Gaussian distributions with a fixed budget when there is no contextual information Kaufman2016complexity. Let $\left(\sigma^a(P_0)\right)^2 = \left(\sigma^a_0\right)^2$. When the potential outcome of each treatment arm $a\in[K]$ follows the Gaussian distributions, the distribution-dependent lower bound is given as the following proposition.
The proof is shown in Kato2022small. This lower bound can be derived without restrictions of the asymptotically invariant strategy (Definition (ref)) and small gap ($|\mu^1_0 - \mu^2_0| \to 0$). Although the optimal target sample allocation ratio from this lower bound cannot be derived, by using $w^{*}(1) = \frac{\sigma^1_0}{\sigma^1_0 + \sigma^2_0}$ and $w^{*}(0) = 1- w^{*}(1)$ as a target sample allocation ratio, we can find an asymptotically optimal algorithm whose upper bound matches the lower bound when $|\mu^1_0 - \mu^2_0| \to 0$ when $\sigma^1_0$ and $\sigma^2_0$ are known glynn2004large,Kaufman2016complexity.
\paragraph{Restrictions on a strategy class and the small-gap regime.} We restrict our strategies to asymptotic invariant strategies in addition to consistent strategies. As shown in Proposition (ref), this restriction is unnecessary to derive a lower bound for two-armed bandits with a Gaussian distribution without contextual information. However, without this restriction, we conjecture that we cannot derive lower bounds due to the reverse KL problem kaufmann2020hdr when the number of treatment arms is larger than three or contextual information is available. We conjecture the following reason for why this restriction is a necessity. In BAI with a fixed budget, an estimation error of a target sample allocation ratio affects the evaluation of the probability of misidentification. In particular, if the target sample allocation ratio depends on $a^*_0$, we need to estimate $a^*_0$ to obtain the target sample allocation ratio. By restricting strategies to asymptotically invariant ones, we can avoid this estimation. On the other hand, when $K=2$, the target sample allocation ratio depends only on the standard deviation and not on the $a^*_0$ even if we use the restriction. Therefore, even without restriction, we can derive the lower bound when there are only two treatment arms.\footnote{In addition, we also do not have to use this restriction when considering the Equal-variance class (Definition (ref)), such as Bernoulli distributions, defined below. In those cases, the uniform sampling is target sample allocation ratio.} In fact, the lower bound for two-armed Gaussian bandits without contextual information with the restriction is the same as that without the restriction.
In addition to the asymptotically invariant strategies, we consider the small-gap regime. We consider this regime mainly for the technical purpose of deriving the lower bounds, as explained in the next paragraph, but this regime has its own meaning. As we mentioned, this regime corresponds to one of the hardest (worst) cases to identify the best treatment arm. Therefore, we can interpret that asymptotically optimal strategies are a kind of asymptotically minimax optimal in the sense that the worst-case probability of misidentification matches the worst-case lower bound.
From a technical perspective, asymptotically invariant strategies and the small-gap regime are important because they allow us to ignore the estimation error of a target sample allocation ratio. As shown by Carpentier2016, we cannot develop strategies under which the probability of misidentification matches the lower bound of Kaufman2016complexity when the gaps are large and strategies are restricted only to consistent ones. We consider that when gaps are large, an estimation error of the optimal target sample allocation ratio is a contributing factor of the probability of misidentification. Under the small-gap regime, we can ignore the estimation error relative to the probability of misidentification because identification of the best treatment arm becomes difficult when the gaps are sufficiently small. Thus, the small-gap regime makes the asymptotic optimality argument in fixed-budget BAI tractable by allowing the evaluation of optimal allocation probabilities to be ignored.
As another advantage of the restrictions, we can obtain an analytical solution for the target sample allocation ratio. Under the small gap regime, if we constrain a strategy to be asymptotically invariant, we can express the target sample allocation ratio in terms of variance. This property is a great advantage in the computation of the target sample allocation ratio and in the interpretation of the algorithm.
\paragraph{Specific classes of the locally location-shift bandit class.} By generalizing two cases, where all bandit models follow Gaussian distributions and those following Bernoulli bandit models, we define location-shift and equal-variance bandit classes as specific classes of the locally location-shift bandit class.
First, we consider the following location-shift bandit class, where the conditional variances are fixed, and only mean parameters vary across bandit models. This class is a generalization of a class of Gaussian distributions.
For this class, from Theorem (ref), the lower bound given as $\frac{1}{2\sum_{b\in[K]}\mathbb{E}_{P_0}\left[\left(\sigma^b(X_t)\right)^2\right]} + o\left(1\right)$.
As a generalization of bandit models whose potential outcomes follow one-parameter distributions such as Bernoulli, Binomial, and Gamma distributions, we define the following equal-variance bandit class.
When outcomes follow Bernoulli distributions, the bandit model belongs to the equal-variance bandit class because the variances are the same when the expected rewards are the same. For this class, from Theorem (ref), the lower bound given as $\frac{1}{K\mathbb{E}_{P_0}\left[\left(\sigma(X_t)\right)^2\right]} + o(1)$. Because the variances are equal across treatment arms, the target sample allocation ratio is also equal across treatment arms. This lower bound and the target sample allocation ratio implies that the uniform-EBA strategy is optimal, where we choose each treatment arm with the same probability (the uniform sampling rule) and recommend a treatment arm with the highest sample average of observed rewards (the empirical best arm (EBA) recommendation rule). The fact that the uniform-EBA strategy is approximately optimal for two-armed Bernoulli bandits is also reported by Kaufman2016complexity.
We investigate when a strategy can gain efficiency by using contextual information; that is, how lower bounds are tightened by using contextual information. We first show lower bounds to investigate the efficiency gain when contextual information is unavailable. Let $w^*:[K]\to (0,1)$ such that $\sum_{a\in[K]}w^*(a) = 1$ be a target sample allocation ratio when contextual information is not available.
As we show the following theorem, lower bounds can be improved by using contextual information. The equality holds, for example, if $\left(\sigma^a_0\right)^2 = \left(\sigma^a(x)\right)^2$ for any $x\in\mathcal{X}$ and all $a\in[K]$ for $K=2$, and if $\left(\sigma^a_0\right)^2 = \mathbb{E}_{P_0}\left[\left(\sigma^a(X_t)\right)^2\right]$ for all $a\in[K]$ for $K \geq 3$.
We show the proof below. Here, we can find a case where $\frac{1}{2 \big(\sigma^1_0 + \sigma^2_0\big)^2} < \frac{1}{2\mathbb{E}_{P_0}\left[\left(\sigma^1(X_t) + \sigma^2(X_t)\right)^2\right]}$; that is, $\left(\sigma^1_0 + \sigma^2_0\right)^2 > \mathbb{E}_{P_0}\left[\left(\sigma^1(X_t) + \sigma^2(X_t)\right)^2\right]$. Suppose that contextual information is discrete, and we observe context $X_{1}$ with probability $0.5$ and $X_{2}$ otherwise. Let $\left(\sigma^1(X_{1})\right)^2 = 7.5$, $\left(\sigma^1(X_{2})\right)^2 = 0.5$, $\left(\sigma^2(X_{1})\right)^2 = 0.5$, $\left(\sigma^2(X_{2})\right)^2 = 1.5$. We also suppose that $\mu^a(x) = \mu^a$ for $x\in\{X_{1}, X_{2}\}$. In this case, $\left(\sigma^a_0\right)^2 = \mathbb{E}_{P_0}\left[\left(\sigma^a(X_t)\right)^2\right] = 0.5\left(\sigma^a(X_1)\right)^2 + 0.5\left(\sigma^a(X_2)\right)^2$; therefore, $\left(\sigma^1_0\right)^2 = 4$ and $\left(\sigma^2_0\right)^2 = 1$. Then, we have $\mathbb{E}_{P_0}\left[\left(\sigma^1(X_t) + \sigma^2(X_t)\right)^2\right] \approx 7.8 < \left(\sigma^1_0 + \sigma^2_0\right)^2 = 9$. Therefore, we can gain efficiency by using contextual information. We discuss the efficiency gain in Section (ref).
This section presents our strategy, which consists of sampling and recommendation rules. For each $t = 1,2,\dots, T$, our sampling rule randomly chooses a treatment arm with a probability identical to an estimated target sample allocation ratio. In final round $T$, our recommendation rule recommends a treatment arm with the highest-estimated expected reward. Based on these rules, we refer to this as the RS-AIPW strategy.\footnote{This strategy resembles ones in efficient ATE estimation via an adaptive experiment Laan2008TheCA,Hahn2011. A sampling rule using the target sample allocation ratio (ref) for a case with $K=2$ is referred to as the Neyman allocation rule Armstrong2022,adusumilli2022minimax. Kato2022small discusses its asymptotic optimality in BAI with a fixed budget when the number of treatment arms is two, contextual information is not available, and the potential outcomes follow Gaussian distributions. Generalizing their result, we refine the Neyman allocation rule to cases where there are multiple treatment arms and contextual information. Regarding the upper bound, we apply the results of Fan2013,fan2014generalization with the modifications by Kato2022small.}
First, we define a target sample allocation, which is used to define a sampling rule. We estimate it during an adaptive experiment and employ the estimator as a probability of choosing a treatment arm. We call a target sample allocation worst-case optimal if the upper and lower bounds for the probability of misidentification match under a small-gap, one of the worst cases, when using our strategy using the allocation ratio. We conjecture the worst-case optimal target sample allocation ratio using the results of Section (ref). In particular, the results of Theorem (ref) yields the following conjectures for the worst-case optimal target sample allocation ratio $w^*\in\mathcal{W}$: when $K = 2$, for each $x\in\mathcal{X}$,
when $K \geq 3$, for each $x\in\mathcal{X}$ and all $a\in[K]$, \[w^*(a|x) = \frac{\left(\sigma^a(x)\right)^2}{\sum_{b\in[K]}\left(\sigma^b(x)\right)^2}.\] Under this conjectured target sample allocation ratio, we can show that the upper and lower bounds for the probability of misidentification match under a small-gap regime in Section (ref); hence, we call this target sample allocation ratio worst-case optimal. This target sample allocation ratio is unknown when the variances are unknown; therefore, it must be estimated via observations during the bandit process.
We provide a sampling rule referred as to a random sampling (RS) rule. For $a\in[K]$ and $t\in[T]$, let $\widehat{w}_{t}(a|x)$ be an estimated target sample allocation ratio at round $t$. In each round $t$, we obtain $\gamma_t$ from the uniform distribution on $[0,1]$ and choose a treatment arm $A_t = 1$ if $\gamma_t \leq \widehat{w}_{t}(1|X_t)$ and $A_t = a$ for $a \geq 2$ if $\gamma_t \in (\sum^{a-1}_{b=1}\widehat{w}_{t}(b|X_t), \sum^a_{b=1}\widehat{w}_{t}(b|X_t)]$.
As an initialization, we choose a treatment arm $A_t$ at round $t \leq K$ and set $\widehat{w}_t(a| x) = 1/K$ for $a\in[K]$ and $x\in\mathcal{X}$. In a round $t > K$, for all $a\in[K]$, we estimate the target sample allocation ratio $w^{*}$ using past observations $\mathcal{F}_{t-1}$, such that for all $a\in[K]$ and $x\in\mathcal{X}$, $\widehat{w}_{t}(a|x) > 0$ and $\sum_{a\in[K]} \widehat{w}_{t}(a|x) = 1$. Then, in round $t$, we choose a treatment arm $a$ with a probability $\widehat{w}_{t}(a|X_t)$. To construct an estimator $\widehat{w}_{t}(a| x)$ for all $x\in\mathcal{X}$ in each round $t$, we denote a bounded estimator of the conditional expected reward $\mu^a_0(x)$ by $\widehat{\mu}^a_{t}(x)$, that of the conditional expected squared reward $\nu^a_0(x)$ by $\widehat{\nu}^a_{t}(x)$, and that of the conditional variance $\left(\sigma^a_0(x)\right)^2$ by $(\widehat{\sigma}^a_t(x))^2$. All estimators are constructed only from samples up to round $t$. More formally, they are constructed as follows. For $t=1,2,\dots, K$, we set $\widehat{\mu}^a_{t} = \widehat{\nu}^a_{t} = (\widehat{\sigma}^a_t(x))^2 = 0$. For $t > K$, we estimate $\mu^a(x)$ and $\nu^a(x)$ using only past samples $\mathcal{F}_{t-1}$ and converge to the true parameter almost surely (Assumption (ref)). For the estimators, we can use nonparametric estimators, such as the nearest neighbor regression estimator and kernel regression estimator, which are prove to converge to the true function almost surely under a bounded sampling probability $\widehat{w}_t$ by yang2002 and qian2016kernel. As long as these conditions are satisfied, any estimators can be used. Note that we do not assume specific convergence rates for these estimators because we can show the asymptotic optimality without them owing to the unbiasedness of the AIPW estimator Kato2021adr. Let $(\widehat{\sigma}^{\dagger a}_t(x))^2 = \widehat{\nu}^a_{t}(x) - \left(\widehat{\mu}^a_{t}(x)\right)^2$ for all $a\in[K]$ and $x\in\mathcal{X}$. Then, we estimate the variance $\left(\sigma^a_0(x)\right)^2$ for all $a\in[K]$ and $x\in\mathcal{X}$ in a round $t$ as $\left(\widehat{\sigma}^a_{t}(x)\right)^2 =\max\{ \min\{((\widehat{\sigma}^{\dagger a}_t(x))^2,C_{\sigma^2}\},1/C_{\sigma^2}\}$ and define $\widehat{w}_{t}$ by replacing the variances in $w^*$ with corresponding estimators; that is,
when $K \geq 3$, for each $x\in\mathcal{X}$, \[\widehat{w}_{t}(a|x) = \frac{(\widehat{\sigma}^a_t(X_t))^2}{\sum_{b\in[K]}(\widehat{\sigma}^b_t(X_t))^2}\] If there are multiple elements in $\operatorname*{arg\,max}_{a\in[K]} \widehat{\mu}^a_{t}(x)$, we choose one of them as $\widehat{a}_t$ in some way.
We employ 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).
The following section presents our recommendation rule. In the recommendation phase of round $T$, for each $a\in[K]$, we estimate $\mu^a$ for each $a\in[K]$ and recommend the maximum. To estimate $\mu^a$, the AIPW estimator is defined as
In the final round $t=T$, we recommend $\widehat{a}_T \in [K]$ as
The AIPW estimator has the following properties: (i) its components $\{\varphi^a(Y_t, A_t, X_t; \widehat{\mu}^a_t, \widehat{w}_t)\}^T_{t=1}$ are a martingale difference sequence, thereby allowing us to use the large deviation bounds for martingales; (ii) it has the minimal asymptotic variance among the possible estimators. For instance, we can use other estimators with a martingale property, such as the inverse probability weighting (IPW) estimator Horvitz1952, but their asymptotic variance will be larger than that of the AIPW estimator. For the $t$-th element of the sum in the AIPW estimator, we use the nuisance parameters estimated from past observations up to the round $t-1$ to make the sequence in the sum a martingale difference sequence. This technique is often used in adaptive experiments Laan2008TheCA,hadad2019,Kato2020adaptive,Kato2021adr and also has a similar motivation to double machine learning ChernozhukovVictor2018Dmlf. Note that in double machine learning for a doubly robust (DR) estimator, we usually impose specific convergence rates for the estimators of the nuisance parameter, which are not required in our case owing to the unbiasedness of the AIPW estimator (Assumption (ref)). Also see Kato2021adr.
We present the pseudo-code in Algorithm (ref). Note that $C_{\mu}$ and $C_{\sigma^2}$ are introduced for technical purposes to bound the estimators. Therefore, any large positive value can be used.
In this section, we derive the following upper bound of the misspecification probability of the RS-AIPW strategy, which implies that the strategy is asymptotically optimal.
We derive the upper bounds for bandit models, where the rewards are sub-exponential random variables.
We also suppose that estimators of $\mu^a_0(x)$ and $\nu^a_0(x)$ converges to the true values almost surely.
This assumption is satisfied when we sample each treatment arm with a probability larger than a positive constant and use appropriate estimation methods yang2002. Let us define $\widetilde{V}^a = \mathbb{E}_{P_0}\left[\frac{\left(\sigma^*(X_t)\right)^2}{w^*(a^*_0| X_t)} + \frac{\left(\sigma^a(X_t)\right)^2}{w^*(a| X_t)} + \left(\mu^*_0(X_t) - \mu^a_0(X_t) - (\mu^*_0 - \mu^a_0)\right)^2\right]$.
This theorem allows us to evaluate the exponentially small probability of misidentification up to the constant term when $\Delta_0\to 0$. Moreover, this result also implies that the estimation error of the target sample allocation ratio $w^{*}$ is negligible when $\Delta_0\to 0$. This is because the upper bound matches the performance of strategies for Gaussian bandit models developed by glynn2004large given the optimal target sample allocation ratio. This also means that the estimation error of the target sample allocation ratio is insensitive to the probability of misidentification in situations where identifying the best treatment arm is difficult due to the small gap.
\paragraph{Asymptotic optimality.} When $\mathcal{P}$ is the locally location-shift bandit class, this upper bound matches the lower bounds in Theorems (ref) under a small-gap regime.
Although the upper bound also matches the lower bound for the equal-variance bandit class, the uniform-EBA strategy is also obviously optimal.
\paragraph{Efficiency gain.} As well as Section (ref), we investigate the efficiency gain by using contextual information from the viewpoint of upper bound. First, we show the upper bound when we cannot employ contextual information. Recall that we defined the target sample allocation ratios without contextual information as $w^*(a)$ for each $a\in[K]$ in Corollary (ref).
By comparing upper bounds for cases where we can use contextual information and we cannot use contextual information, we obtain the following relationship on the efficiency gain.
Owing to the dependency among samples in BAI, it is also difficult to apply the standard large deviation bound Dembo2009large to a sample average of some random variable. For example, G\"{a}rtner-Ellis theorem Gartner1977,Ellis1984 provides a large deviation bound for dependent samples, but it requires the existence of the cumulant, a logarithmic moment generating function, which is not easily guaranteed for the samples in BAI.
For these problems, we derive a novel Cram\'er-type 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 deterministically; that is, for some martingale difference sequence $\{W_s\}^n_{s=1}$ of some random variable $W_s$, for any $n > 0$, there exists a real number $0< \epsilon < 1/2$ such that $\mathbb{E}\left[\sum^n_{s=1}\mathbb{E}[W^2_s| \mathcal{F}_{s-1}] - 1\right] \leq \epsilon^2$; then, Fan2013,fan2014generalization derive the upper bound for $\mathbb{P}\left(\sum^n_{s=1}W_s > z\right)$, where $\epsilon$ belongs to a range upper bounded by $\epsilon^{-1}$. Thus, their large deviation bound holds when $\mathbb{E}\left[\sum^n_{s=1}\mathbb{E}[W^2_s| \mathcal{F}_{s-1}] - 1\right]$ can be bounded by any $\epsilon$ for any $n > 0$. Kato2022small modifies the results of Fan2013,fan2014generalization by bounding the conditional second moment for large $T$ to apply the problem of BAI with a fixed budget. We basically follow Kato2022small and generalize the result to the multi-armed bandit case. For the sake of completeness, we show a part of the results of Kato2022small. Using the large deviation bound and AIPW estimator, under our proposed strategy, the upper and lower bounds for probability of misidentification match as the gaps converge to zero.
Here, we introduce key elements of our analysis. For each $t\in[T]$, we define the difference variable
We also define its sum $Z^a_t = \sum^t_{s=1}\xi^a_{s}$, and a sum of conditional moments $W_t = \sum^t_{s=1}\mathbb{E}_{P_0}[(\xi^a)^2_{s}| \mathcal{F}_{s-1}]$ with initialization $W_0 = 0$. Using the difference variable $\xi^a_t$, we can express the gap estimator as $\sqrt{T}(\widehat{\mu}^{\mathrm{AIPW}, a^*_0}_{T} - \widehat{\mu}^{ \mathrm{AIPW}, a}_T - (\mu^*_0 - \mu^a_0)) / \sqrt{\widetilde{V}^a} = \sum^T_{t=1}\xi^a_t = Z^a_T$. Here, $\left\{\left(\xi^a_t, \mathcal{F}_t\right)\right\}^T_{t=1}$ is a martingale difference sequence (Appendix (ref)), using the fact that $\widehat{\mu}^a_{t}$ and $\widehat{w}_t(a|X_t)$ are $\mathcal{F}_{t-1}$-measurable random variables. Let us also define $V_T = \mathbb{E}_{P_0} [ | \sum_{t=1}^T \mathbb{E}_{P_0}[(\xi^a_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 obtain the following theorem on the tail probability of $Z^a_T$:
As described by fan2014generalization, if $T\mathbb{E}[(\xi^a_t)^2|\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^a_t)^k|\mathcal{F}_{t-1}]| \leq \frac{1}{2} k!(C/\sqrt{T})^{k-2}\mathbb{E}[(\xi^a_t)^2|\mathcal{F}_{t-1}]$ for all $k\geq 2$ and all $t\in[T]$.
For $u = \sqrt{T} (\mu^*_0- \mu^a_0) / {\sqrt{\widetilde{V}^a}}$ and
Then, the probability that we fail to make the correct treatment arm comparison is bounded as
Here, we provide the proof sketch of Theorem (ref). The formal proof is shown in Appendix (ref).
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). By combining this bound with Theorem (ref) and Proposition (ref) in Appendix (ref), which shows the rate of convergence in the Central limit theorem (CLT) for $0 \leq u \leq 1$, we have the following corollary.
This approximation can be considered a Gaussian approximation because the probability is represented by $\exp(-{\left(\mu^*_0- \mu^a_0\right)^2} T / ({2 \widetilde{V}^a}))$. Condition B is satisfied as $\mu^*_0- \mu^a_0 \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{P}$.
With regards to Condition C, we introduce the following lemma for the convergence of $V_T$, which corresponds to 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.
Finally, the proof of Theorem (ref) is completed as follows:
The stochastic MAB problem is a classical abstraction of the sequential decision-making problem Thompson1933,Robbins1952,Lai1985, and BAI is a paradigm of the MAB problem EvanDar2006,Audibert2010,Bubeck2011. Though the problem of BAI itself goes back decades, its variants go as far back as the 1950s bechhofer1968sequential.
kaufmann14,Kaufman2016complexity conjectures distribution-dependent lower bounds for BAI. In the BAI literature, there is another setting, known as BAI with fixed confidence Jenninson1982,Mannor2004,Kalyanakrishnan2012,wang2021fast. For the fixed confidence setting, Garivier2016 solves the problem in the sense that they develop a strategy whose upper bound of the sample complexity, an expected stopping time, matches the distribution-dependent lower bound. The result is further developed by Degenne2019b to solve the two-player game by the no-regret saddle point algorithm. Furthermore, Qin2017, Shang2020, and Jourdan2022 extend the Top Two Thompson Sampling (TTTS), proposed by Russo2016 and shows the asymptotic optimality of their strategies in the fixed confidence setting. wang2021fast develops Frank-Wolfe-based Sampling (FWS) to characterize the complexity of fixed-confidence BAI with various types of structures among the arms. See wang2021fast for techniques in the fixed-confidence setting and a further comprehensive survey.
Russo2016, Qin2017, and Shang2020 propose the Bayesian BAI strategies, which are optimal in the sense of the posterior convergence rate. Although the upper bounds of the sample complexity are shown to match the lower bounds of Kaufman2016complexity in fixed-confidence BAI for some of the methods, the upper bounds for the probability of misidentification do not match that for fixed-budget BAI. Although the rate of the posterior convergence is also optimal in the fixed-budget setting, it does not imply the asymptotic optimality for the probability of misidentification Kasy2021,Ariu2021. For example, the KL divergence in the lower and upper bounds is flipped between the evaluations of posterior convergence and probability of misidentification. In addition, for the posterior convergence, we consider a convergence of a random variable, while for the probability of misidentification, we consider a convergence of a non-random variable.
In evaluation, we can use the simple regret. Bubeck2009 provides a non-asymptotic minimax lower and upper bound of simple regret for bandit models with a bounded support. Following their results, the uniform-EBA strategy is optimal for bandit models with a bounded support. This result is compatible with lower bounds under the equal-variance bandit class, which implies that the uniform sampling is asymptotically optimal for the equal-variance bandit class. Because Bubeck2009 does not use other parameters, such as variances, their result does not contradict with Theorem (ref), which implies that the target sample allocation ratio using the variances is optimal. Recently, adusumilli2022minimax,Adusumilli2022diffusion consider another minimax and Bayes evaluations of BAI, by employing diffusion process approaches Fan2021,Wager2021. Komiyama2021 discusses the optimality of Bayesian simple regret minimization, which is closely related to BAI in a Bayesian setting. They showed that parameters with a small gap make a significant contribution to Bayesian simple regret.
The framework of bandit problems is closely related to the potential outcome framework of Neyman1923,Rubin1974. In causal inference, the gap is often referred to as the average treatment effect, and the estimation is studied in this framework. To estimate the average treatment effect efficiently, Laan2008TheCA, Hahn2011, Meehan2020, Kato2020adaptive, and gupta2021efficient propose adaptive strategies. The AIPW estimator, which is also referred to as a DR estimator, plays an important role in treatment effect estimation Robins1994,hahn1998role,bang2005drestimation,dudik2011doubly,Laan2016onlinetml,Luedtke2016. The AIPW estimator also plays an important role in double/debiased machine learning literature because it mitigates the convergence rate conditions of the nuisance parameters ChernozhukovVictor2018Dmlf,Ichimura2022.
In adaptive experiments for efficient ATE estimation, the AIPW estimator has also been used by Laan2008TheCA and Hahn2011. Karlan2014 applied the method of Hahn2011 to test how donors respond to new information regarding the effectiveness of a charity. These studies have been extended by Meehan2020 and Kato2020adaptive. However, the notion of optimality is based on the analogue of the efficient estimation of the ATE under i.i.d. observations and not complete in adaptive experiments.
When constructing AIPW estimator with samples obtained from adaptive experiments, including BAI strategies, a typical construction is to use sample splitting and martingales Laan2008TheCA,hadad2019,Kato2020adaptive,Kato2021adr. Howard2020TimeuniformNN, Kato2020adaptive, and provide non-asymptotic confidence intervals of the AIPW or DR estimator, which do not bound a tail probability in large deviation as ours. The AIPW estimator is also used in the recent bandit literature, mainly in regret minimization dimakopoulou2021online,Kim2021. hadad2019, Bibaut2021, and Zhan2021 consider the off-policy evaluation using observations obtained from regret minimization algorithms.
The small-gap regime is inspired by limit experiments framework LeCam1986,Vaart1998,Hirano2009. For a parameter $\theta_0\in\mathbb{R}$ and $n$ i.i.d. observations for a sample size $n$, the limit experiments framework considers local alternatives $\theta = \theta_0 + h/\sqrt{n}$ for a constant $h\in\mathbb{R}$ Vaart1991,Vaart1998. Then, we can approximate the statistical experiment by a Gaussian distribution and discuss the asymptotic optimality of statistical procedures under the approximation. Hirano2009 relates the asymptotic optimality of statistical decision rules Manski2000,Manski2002,Manski2004,DEHEJIA2005 to the limit experiment framework. This framework is further applied to policy learning, such as AtheySusan2017EPL.
Independently, Armstrong2022 proposes an application of the local asymptotic framework to a setting similar to BAI by replacing the CLT used in the original framework, such as Vaart1998, with that for martingales. In their analysis, the gaps converge to zero with $1/\sqrt{T}$, and a class of BAI strategies is restricted for the second moment of the score to converges to a constant, whereas our gaps converge to zero independently of $T$, and a class of BAI strategies is restricted to be consistent.
Here, note that taking the parameter $\theta = \theta_0 + h/\sqrt{T}$ does not produce the distribution-dependent analysis; that is, the instance is not fixed as $T$ increases. Therefore, a naive application of the distribution-dependent analysis like Proposition (ref) does not provide a lower bounds for BAI in this setting. To match the lower bound of Kaufman2016complexity, we need to consider the large deviation bound, rather than CLT. In other words, the limit experiment framework first applies a Gaussian approximation and then evaluates the efficiency under that approximation, where efficiency arguments are complete within the Gaussian distribution. In contrast, we derive the lower bounds of an event under the true distribution in our limit decision-making and approximate it by considering the limit of the gap. Therefore, in limit decision-making, we first consider the optimality for the true distribution and find the optimal strategy in the sense that the upper bound matches the lower bound when the gaps converge to zero.
Our small-gap regime is also inspired by lil'UCB Jamieson2014. Balsubramani2016 and Howard2020TimeuniformNN propose sequential testing using the law of iterated logarithms and discuss the optimality of sequential testing based on the arguments of Jamieson2014.
Ordinal optimization has been studied in the operation research community peng2016myopic, Dohyun2021, and a modern formulation was established in the 2000s chen2000,glynn2004large. Most of these studies consider the estimation of the optimal sampling rule separately from the probability of misidentification.
In addition to Fan2013,fan2014generalization, several studies have employed martingales to obtain tight large deviation bounds Cappe2013,Juneja2019,Howard2020TimeuniformNN,Kaufmann2021. Some of these studies have applied change-of-measure techniques.
Tekin2015, GuanJiang2018, and Deshmukh2018 also consider BAI with contextual information, but their analysis and setting are different from those employed in this study.
Kaufman2016complexity derives distribution-dependent lower bounds for BAI with a fixed confidence and budget, based on similar change-of-measure arguments to those found in Lai1985. In BAI with fixed confidence, Garivier2016 develops a strategy whose upper bound and lower bounds for the probability of misidentification match. In contrast, in the fixed-budget setting, the existence of a strategy whose upper bound matches the lower bound of Kaufman2016complexity was unclear. We consider that this is because the estimation error of an optimal target sample allocation ratio is negligible in BAI with a fixed budget, unlike BAI with fixed confidence, where we can draw each treatment arm until the strategy satisfies a condition. Furthermore, there are lower bounds different from Kaufman2016complexity, such as Audibert2010, Bubeck2011, and Carpentier2016.
Audibert2010 proposes the UCB-E and Successive Rejects (SR) strategies. Using the complexity terms $H_1(P) = \sum_{a \in [K] \backslash\{a^*(P)\}} 1/(\Delta^a(P))^2$ and $H_2(P) = \max_{a \in [K] \backslash\{a^*(P)\}} a/(\Delta^a(P))^2$, where $\Delta^a(P) = \mu^{a^*(P)} - \mu^a$, they prove an upper bound for the probabilities of misidentification of the forms $\exp\left( - T/(18 H_1(P_0))\right)$ and $\exp \big( - T/( \log (K) H_2(P_0))\big)$, for UCB-E with the upper bound on $H_1(P_0)$ and SR, respectively.
Kato2022small shows that the upper bound for the probability of misidentification of the RS-AIPW strategy matches the lower bound derived by Kaufman2016complexity (Proposition (ref)) under the small-gap regime when the number of treatment arms is two, contextual information is not available, and the potential outcomes follow Gaussian distribution. They approximate only the upper bound by the small gap but do not consider the approximation of the lower bound.
Carpentier2016 discusses the optimality of the method proposed by Audibert2010 by an effect of constant factors in the exponents of certain bandit models. They proved the lower bound on the probability of misidentification of the form: $ \sup_{P\in\mathcal{P}^B}\Big\{ \mathbb{P}_{P_0}\big(\widehat{a}_T \neq a^*_0\big) \exp \big(400T/( \log(K) H_1(P))\big)\Big\}$, where for all $P\in\mathcal{P}^B$, there exists a constant $B>0$ such that $H_1(P) < B$. Our result does not contradict with the result that found by Carpentier2016, as we consider a small-gap regime, rather than the large-gap regime employed by Carpentier2016. In the other words, their results are complementary to ours because we consider situations with a small gap.
Our RS-AIPW strategy is also applicable to a setting where we can update the sampling rule in batch, ratner than a sequential manner, as well as other BAI strategies in different settings. For example, even in a two-stage setting, where we are allowed to update the sampling rule only once, we can show the asymptotic optimality if the budgets separated into two-stages go to infinity simultaneously. Such a setting has frequently been adopted in the field of economics, such as Hahn2011 and Kasy2021.
In this study, we considered BAI with a fixed budget and contextual information under a small-gap regime. Subsequently, we derived lower bounds for the probability of misidentification by applying semiparametric analysis under the small-gap regime. Then, we proposed the RS-AIPW strategy. With the help of a new large deviation expansion we developed, we showed that the performance of our proposed RS-AIPW strategy matches the lower bound under a small gap. We also addressed a long-standing open issue in BAI with a fixed budget; even without contextual information, the existence of an asymptotically optimal BAI strategy was unclear. Because BAI with a fixed budget and without contextual information is a special case in our setting, we addressed this question. Furthermore, we demonstrated an analytical solution for the target sample allocation ratio, which has also been unknown for a long time. Thus, our study serves as a breakthrough in the field of BAI with a fixed budget. Our future direction is to develop BAI strategies for various settings, such as linear Hoffman2014,Liang2019,KatzSamuels2020, combinatorial Chen2014, and policy learning Kitagawa2018,AtheySusan2017EPL,Zhou2020.