1 Introduction↩︎

Heterogeneous data sources in sequential decision-making problems have received considerable attention, since access to multiple sources allows a decision-maker to reach a decision faster by adaptively sampling the most informative source. In the context of sequential hypothesis testing, Chernoff [1] proposed the first adaptive selection strategy, which uses a maximum likelihood estimate (MLE) based on accumulated log-likelihood ratios to guide the choice of data source at each time slot, successfully demonstrating that the gain of adaptivity (so-called the gain of heterogeneous data sources in this paper) is a lower expected stopping time in an asymptotic regime with the same reliability. Following this work, many subsequent papers [3]–[9] have extended Chernoff’s action-selection principle to various scenarios, including settings with expected budget constraints and temporally available data sources.

However, all these methods are “likelihood-based”, and rely strongly on either the knowledge of the data distributions, or assume that the stochastic model is parametric. Such conditions are often violated in many practical real-world scenarios. The main motivation of our work is to initiate the study of the active sequential hypothesis testing problem in more general settings. As a first step in this direction, we base on sequential nonparametric two-sample testing (SN2T), where the goal is to test whether two unknown data distributions are equal based only on sequentially collected paired samples without any parametric model assumptions. This setting naturally arises in applications where the underlying distributions are often complex and not well captured by simple parametric models. Prior works on SN2T [2], [10] have only developed sequential tests in the case of a single data source (in this paper, one data source has a pair of distributions). To investigate the gain of adaptivity, we extend this single-source formulation to multiple data sources and a corresponding global null (and alternative).

Our active generalization of the sequential two-sample testing problem models many real-world problems. For example, consider an online A/B test on a large platform. Users are divided into several segments, such as different regions or device types. For each segment, the platform can observe how users interact under the current recommendation policy (version A) and under a new policy (version B), but the platform can only select one segment to get the observation per time slot due to some constraints, e.g., cost or bandwidth. The major question of this extension is how to exploit source heterogeneity to have the gain of adaptivity.

Before proceeding to our results, we first briefly introduce our problem framework for the active SN2T, so-called ASN2T in this paper. We assume that there are \(K\) data sources and any data source, say source \(k \in [K]\), consists of a pair of distributions \(P_{k,1}\) and \(P_{k,2}\), which are unknown. The global null hypothesis is that for any data source, its two distributions are the same. Then, in each time slot, the decision-maker can (adaptively) select one data source and collect paired samples drawn from the corresponding paired distributions. If the global null is false, it should stop and reject the null as soon as possible; if the global null is true, it wants to control the false alarm probability. Recall the online A/B test example, \(P_{k,1}\) and \(P_{k,2}\) may represent user-interaction distributions under two recommendation policies for segment \(k\). This problem structure generalizes the single-source setting in the current literature on SN2T, where they consider \(K=1\).

Our main result is that, following the “sequential tests of power one’’ criterion introduced by [11], we design an adaptive source-selection policy combined with the general framework of two-sample testing by betting [2]. The resulting procedure (including the stopping rule and the adaptive selection rule) has the following three properties. First, it ensures the level-\(\alpha\) property, i.e., under the global null, the probability of ever stopping is at most \(\alpha\). Second, it has the power-one property, i.e., if the global null is false (when at least one data source has different distributions for its two samples, so-called global alternative), the probability of stopping in finite time is one. Third, under some additional conditions, we derive a nonasymptotic upper bound on the expected stopping time under the global alternative, showing that its order is at least as good as that in the single-source setting studied by [2]. Moreover, when the global alternative holds and there exists a data source that has a better”distinguishability’’ than those of all other sources, our adaptive selection strategy concentrates sampling on this most informative source through a vanishing greedy exploration, leading to an asymptotically smaller expected stopping time than the single-source setting.

For the stopping rule, we follow the method of [2], which adapts an adaptive betting strategy (to make the betting-wealth process grow as fast as possible under the alternative) with an adaptive prediction strategy (to measure the empirical “distance’’ between distributions), providing a computationally and statistically powerful two-sample test. We show that, even with adaptive source selection, the associated betting-wealth process remains a nonnegative supermartingale, so Ville’s inequality [12] yields the level-\(\alpha\) property. In addition, by applying the martingale strong law of large numbers, we can guarantee the power-one property under mild assumptions. The more interesting part is in the design of the selection rule. While our setting is similar to sequential hypothesis testing in multi-armed bandits [9] and heterogeneous population models [13], these results cannot be applied to our problem. In our case, the”reward’’ induced by the adaptive prediction strategy is time-varying and non-i.i.d.. Moreover, we do not have parametric assumptions on the data distributions, and the decision-maker can sample only one data source at each time slot rather than all sources simultaneously. Building on the ideas of [3], we propose a simple forced exploration strategy with a vanishing exploration rate (denoted by \(\epsilon(t)\)) as the time \(t\) goes to infinity. The guidance of the selection is the empirical distance induced by the prediction strategy sequentially updated for each data source. Specifically, at each time \(t\ge1\), with probability \(1-\epsilon(t)\), we select the source with the largest empirical distance at time \(t-1\), and with the probability \(\epsilon(t)\), we sample a source uniformly at random. By carefully choosing the decay of \(\epsilon(t)\) (related to the gap between the best distinguishability and the second best distinguishability, so-called sub-optimality gap), we balance exploration and exploitation and satisfy the third property mentioned earlier.

To the best of our knowledge, this is the first work to study active source selection in sequential nonparametric hypothesis testing, with a particular focus on two-sample testing.

2 Problem Formulation↩︎

Throughout, we assume that there are \(K<\infty\) data sources, and we use the notation \([K]\) to represent the set \(\left\{1,2,\ldots,K\right\}\).

2.1 Statistical model and hypotheses↩︎

For each data source \(k\in[K]\), there are two distributions \(P_{k,1}\) and \(P_{k,2}\) (probably in a nonparametric distribution class). If a data source \(k\in[K]\) is selected, the decision-maker receives \((X_{k,1}, X_{k,2})\) drawn from the product distribution \(P_{k,1} \times P_{k,2}\). Moreover, both \(X_{k,1}\) and \(X_{k,2}\) lie on a common alphabet \(\mathcal{X}\) (which for simplicity we assume is the same across all \(k \in [K]\)).

For the hypotheses, there are global null \(H_0\), which means for any data source \(k\in[K]\), their corresponding paired distribution \(P_{k,1}\) and \(P_{k,2}\) are the same, and the global alternative \(H_1\), which means there exists at least one \(k\in[K]\), such that their corresponding paired distributions are different. That is \[\begin{align} &H_0:\forall\,k\in[K]\quad P_{k,1}=P_{k,2},\\ &H_1:\exists k\in[K]\quad P_{k,1}\neq P_{k,2}. \end{align}\] For all \(k\in[K]\), \(P_{k,1}\) and \(P_{k,2}\) are unknown to the decision-maker, and we make no further assumptions. We respectively denote \(\mathbb{P}_{H_i}(\cdot)\) and \(\mathbb{E}_{H_i}[\cdot]\) as the “probability’’ and the”expectation’’ under \(H_i\) for \(i\in\left\{0,1\right\}\).

2.2 Metric for distance measure↩︎

In this paper, we utilize a distance metric on the space of probability distributions utilized by [2]. In particular, let \(\mathcal{G}\) denote a class of test functions \(g:\mathcal{X}\rightarrow[-1/2, 1/2]\). For any \(k \in [K]\), we can use \(\mathcal{G}\) to define a distance denoted by \(D^{(k)}_{\mathcal{G}}\) between two distributions under \(H_1\): \[\begin{align} D^{(k)}_{\mathcal{G}}:=\sup_{g_k\in\mathcal{G}}\mathbb{E}_{H_1}[g_k(X_{k,1})-g_k(X_{k,2})]\quad\forall\,k\in[K], \end{align}\] and the corresponding maximizer is \[\begin{align} g^*_k:=\mathop{\mathrm{arg\,sup}}_{g_k\in\mathcal{G}}\mathbb{E}_{H_1}[g_k(X_{k,1})-g_k(X_{k,2})]\quad\forall\,k\in[K],\label{eq:optimal95pred} \end{align}\tag{1}\] which is the so-called witness function. Different choices of the function class \(\mathcal{G}\) lead to different distance measures (or metrics), such as the \(L_2\)-norm or the kernel MMD metric. Moreover, let \(D^{(a^*)}_{\mathcal{G}}:=\max_{k\in[K]}D^{(k)}_{\mathcal{G}}\) and \(a^*\) is the data source that attains \(D^{(a^*)}_{\mathcal{G}}\). Then, the sub-optimality gap is defined as \[\begin{align} r:=D^{(a^*)}_{\mathcal{G}}-\max_{k\neq a^*}D^{(k)}_{\mathcal{G}}. \end{align}\] We assume the decision-maker knows a lower bound of \(r\), defined as \(L>0\) for the alternative hypothesis (see Remark 1). To make our problem meaningful, we will work under the following assumptions on the function class \(\mathcal{G}\).

This last assumption is primarily to simplify the presentation, and we can relax this following the same “hedging” argument as discussed by [2].

2.3 Source-selection, stopping time, and performance measure↩︎

At time slot \(t\ge1\), the decision-maker selects a source \(\delta_t\in[K]\) according to a (possibly randomized) selection policy, which can be fully adaptive. In other words, \(\delta_t\) is a random variable whose distribution is determined by all information observed up to time \(t-1\), including past actions, collected samples, or any functions or statistics that have been updated from these samples.

After taking the action, if \(\delta_t = k\) for any source \(k\in[K]\), the decision-maker receives a pair of observations \(X_{k,1}(t)\) and \(X_{k,2}(t)\) generated by \(P_{k,1}\) and \(P_{k,2}\), respectively. That is, for any \(t\ge1\), \[\begin{align} X_{k,1}(t)\sim P_{k,1},\quad X_{k,2}(t)\sim P_{k,2}\quad\text{if }\delta_t=k\in[K]. \end{align}\] We assume that, for the selected source \(k\) at time \(t\), the samples \(X_{k,1}(t)\) and \(X_{k,2}(t)\) are independent of each other. In addition, for each \(t\ge1\) and given \(\delta_t=k\), the pair \((X_{k,1}(t), X_{k,2}(t))\) is conditionally independent of all past information.

At the end of each time slot, the decision-maker uses all paired samples collected so far to decide whether to stop and reject \(H_0\) or to continue sampling. The corresponding stopping time is denoted by \(\tau\).

The procedure of the action-taking and stopping time is summarized below.

Then, for the performance guarantee, we say that an active sequential two-sample test (as in Definition 1) is a level-\(\alpha\) power-one test if the probability of ever stopping under the null hypothesis is at most \(\alpha\), and the probability of ever stopping under the alternative is equal to one. In short, a level-\(\alpha\) power-one sequential test should satisfy \[\begin{align} \mathbb{P}_{H_0}(\tau<\infty)\leq\alpha\quad\text{and}\quad\mathbb{P}_{H_1}(\tau<\infty)=1, \end{align}\] where \(P_{H_i}\) means that the samples are drawn from distributions under hypothesis \(H_i\). Furthermore, the expected stopping time is defined under \(H_1\), i.e., we denote it as \(\mathbb{E}_{H_1}[\tau]\).

Our goal is to construct a level-\(\alpha\) power-one active sequential two-sample test in a fully nonparametric setting, and derive an upper bound on the expected stopping time, in the process precisely characterizing the gain of adaptive sampling.

In the following sections, to understand our proposed test, we begin by introducing an oracle test in our problem setting, following the idea in [2]. Then, since the oracle test depends on the knowledge of data distributions, we propose our practical test, including the stopping and the selection rule. The stopping rule basically follows the testing-by-betting method proposed by [2], and the selection rule is based on a vanishing greedy mechanism. We then demonstrate our main theorem. Finally, we compare our expected stopping time with the passive setting in [2] and identify conditions for the gain of adaptivity.

3 Oracle test↩︎

In this section, we describe an “oracle test” that relies on the knowledge of the true (and unknown) distributions. While this test is clearly not practical, it serves as a template for the design of our practical test in the next section. In parametric settings, such as that considered by [1], [5], [9], the optimal approach is to design tests based on cumulative log-likelihood ratio processes. However, in our setting, the statistical model is nonparametric and unknown; hence, we follow the oracle test proposed by [2] but with heterogeneous data sources.

The oracle test is associated with the optimal sampling policy with \(\delta_t=a^*\) for all \(t\ge1\), and accumulates the difference \(g^*_{a^*}(X_{a^*,1}(t))-g^*_{a^*}(X_{a^*,2}(t))\) over time slot \(t\ge1\) via a log-optimal betting process. Specifically, we denote the oracle betting-wealth process as \(\left\{W^*_t\right\}_{t\ge0}\), with \(W^*_0=1\), and \[\begin{align} &W^*_{t}=W^*_{t-1}\cdot(1+\lambda^*v^{(a^*)}_t(g^*_{a^*})), \; \forall \; t \geq 1, \end{align}\] where \(\forall\,t\ge1\) and \(g\in\mathcal{G}\), we use the notation \[\begin{align} &v^{(k)}_t(g):=g(X_{k,1}(t))-g(X_{k,2}(t))\quad\forall\,k\in[K],\label{eq:v}\\ &\lambda^*\in\mathop{\mathrm{arg\,max}}_{\lambda\in[-1,1]} \mathbb{E}\left[\log\left(1+\lambda(g^*_{a^*}(X_{a^*,1}) - g^*_{a^*}(X_{a^*,2})\right)\right],\nonumber\\ &\text{with}\;(X_{a^*,1}, X_{a^*,2})\sim P_{X_{a^*,1}}\times P_{X_{a^*,2}}\nonumber. \end{align}\tag{2}\] We can then define the oracle stopping time as \(\tau^*:=\inf\left\{t\ge1:W^*_t\geq1/\alpha\right\}\). The term \(\lambda^*\) is the optimal constant bet that ensures \(\left\{W^*_t\right\}_{t\ge1}\) to (exponentially) grows with the fastest rate under \(H_1\), leading to the smallest expected stopping time. Moreover, \(g^*_{a^*}\) can be interpreted as the function that best distinguishes \(P_{a^*,1}\) and \(P_{a^*,2}\), and the per-time difference \(v^{(a^*)}_t(g^*_{a^*})\) is from the most informative data source for the decision-maker under the alternative, implicitly showing the possibility of the gain of heterogeneous data sources. Also, it is easy to show that the oracle test \(\tau^*\) satisfies the level-\(\alpha\) power-one property by the argument in [2]. We omit this discussion here.

However, since \(\left\{g^*_k\right\}_{k\in[K]}\), \(\lambda^*\), and \(a^*\) require the knowledge of \(\left\{(P_{k,1},P_{k,2})\right\}_{k\in[K]}\), this oracle betting-wealth process is not practical. Therefore, following [2], we utilize a data-driven method consisting of a prediction strategy and a betting strategy to approximate \(\left\{g^*_k\right\}_{k\in[K]}\) and \(\lambda^*\) by two \(F_{t-1}\)-measurable sequences, \(\left\{g_{k,t}\right\}_{t\ge1}\) for each \(k\in[K]\) and \(\left\{\lambda_t\right\}_{t\ge1}\). For the selection strategy, we propose a data-driven randomized policy that balances exploration and exploitation well, which ensures the decision-maker can select the most informative data source \(a^*\) most of the time. We discuss the details of our approach in the next section.

4 Main Results↩︎

4.1 Our proposed test↩︎

For each \(k\in[K]\), the update strategy of \(\left\{g_{k,t}\right\}_{t\ge1}\) is denoted by \(\mathcal{A}^{(k)}_{\text{pred}} := \left\{A^{(k)}_{\text{pred},t} : t \ge 1\right\}\), where each \(A^{(k)}_{\text{pred},t}\) maps the past information \(F_{t-1}\) to a function \(g_{k,t} \in \mathcal{G}\). Similarly, the update strategy of \(\left\{\lambda_t\right\}_{t\ge1}\) is denoted by \(\mathcal{A}_\text{bet} := \left\{A_{\text{bet},t} : t \ge 1\right\}\), where each \(A_{\text{bet},t}\) maps \(F_{t-1}\) to a bet \(\lambda_t \in [-1,1]\). Then, we follow similar updates as [2] for these two strategies (see Remark 2). More importantly, since the prediction strategy depends on the function class \(\mathcal{G}\), the quality of the prediction function of each data source is represented by the individual regret \(R^{(k)}_t(\mathcal{A}^{(k)}_{\text{pred}})\) for each \(k\in[K]\) and \(t\ge1\), defined as \[\begin{align} R^{(k)}_t\equiv R^{(k)}_t(\mathcal{A}^{(k)}_{\text{pred}})\mathrel{\vcenter{:}}= &\sup_{g_k\in\mathcal{G}} \bigg( \sum_{s=1}^{t}v^{(k)}_s(g_{k})\mathbb{1}\left\{\delta_s=k\right\} \nonumber\\ &- \sum_{s=1}^{t}v^{(k)}_s(g_{k,s})\mathbb{1}\left\{\delta_s=k\right\} \bigg),\label{eq:individual95regret} \end{align}\tag{3}\] where \(\mathbb{1}\left\{\cdot\right\}\) is the indicator function. In this paper, \(R^{(k)}_t\) is equivalent to \(R^{(k)}_t(\mathcal{A}^{(k)}_{\text{pred}})\) for notational simplicity. This definition of regret extends the single-source setting in [2], where \(K=1\). We will show the role of individual regret in our main theorem.

For our selection policy, after replacing \(g^*_k\) by \(\left\{g_{k,t}\right\}_{t\ge1}\) for each \(k\in[K]\), we define the selection rule in terms of the resulting empirical distances over received samples. At time slot \(t\ge1\), if source \(\delta_t\in[K]\) is selected, the empirical distance in that slot is \[v^{(\delta_t)}_{t}(g_{\delta_t,t}) = g_{\delta_t,t}\bigl(X_{\delta_t,1}(t)\bigr) - g_{\delta_t,t}\bigl(X_{\delta_t,2}(t)\bigr).\] Based on these quantities, the distribution of \(\delta_t\) is chosen according to a vanishing \(\epsilon(t)\)-greedy policy. In words, at each time slot \(t\ge1\), with probability \(1-\epsilon(t)\) the policy exploits by selecting the data source whose running average of the empirical distances is largest until time \(t-1\), and with probability \(\epsilon(t)\) it explores by selecting a source uniformly at random from \([K]\). The exploration rate satisfies \(\epsilon(t)\in\Theta(1/t)\), which ensures that each data source is selected \(\Omega(\log(t))\) times. This frequency is sufficient to learn the running average of the empirical distances of \(a^*\) is larger than others. Hence, as \(t\) is large enough, the probability of selecting \(\delta_t=a^*\) approaches one. In addition, we choose the constant in \(\epsilon(t)\) to be proportional to \(K/L^2\). Consequently, when \(L\) is small or \(K\) is large, identifying \(a^*\) is more difficult; hence, the policy naturally allocates more probability to exploration.

In short, our proposed test is summarized as follows: The data-driven betting-wealth process and our stopping time are defined as \(\left\{W_t\right\}_{t\ge0}\) and \(\tau^{(\text{ASN2T})}\). Set \(W_0=1\) and \(C\in O\left(\frac{K}{L^2}\right)\). Then, at each time slot \(t\ge 1\), \[\begin{align} &\epsilon(t)=\min\left\{1,C/t\right\},\\ &\delta_t \begin{cases} =\mathop{\mathrm{arg\,max}}_{k\in[K]}\hat{\mu}_{k,{t-1}}\quad\text{with probability }1-\epsilon(t),\\ \sim\text{Unif}([K])\quad\text{with probability }\epsilon(t), \end{cases}\\ &W_{t}=W_{t-1}\cdot(1+\lambda_t v^{(\delta_t)}_t(g_{\delta_t,t})), \end{align}\] and \(\tau^{(\text{ASN2T})}:=\inf\left\{t\ge1:W_t\geq1/\alpha\right\}\), where the running average \(\hat{\mu}_{k,t}\) is defined as, \(\forall\,k\in[K]\) and \(t\ge1\), \[\begin{align} &\hat{\mu}_{k,t}:=\frac{1}{N_{k,t}}\sum_{s=1}^{t}v^{(k)}_s(g_{k,s})\mathbb{1}\left\{\delta_s=k\right\},\\ &N_{k,t}:=\sum_{s=1}^{t}\mathbb{1}\left\{\delta_s=k\right\},\quad\hat{\mu}_{k,t}:=-\infty\,\text{if }N_{k,t}=0. \end{align}\] The exact constant \(C\) is defined in Appendix 6.1.

4.2 Main theorems↩︎

Before stating our main theorem, we first present several lemmas that describe how the proposed test controls the action-taking process. These results will be used in the proof of our main theorem.

The following lemmas are built under Assumptions 1 to 3. All detailed proof can be found in Appendix 6.3.

Lemma 1 is the intuitive result since our selection policy does uniform selection with probability \(\Theta(1/t)\) at each time slot.

Our next result builds upon 1. The high-level idea is that if a data source \(k\in[K]\) is selected \(\Omega(\log(t))\) times, its running average \(\hat{\mu}_{k,t}\) will be close to the corresponding expected value \(D^{(k)}_{\mathcal{G}}\) if the quality of the prediction is good.

Lemma 2 demonstrates that as time is large enough, our selection policy selects the optimal data sources with a high probability. The condition on the regret of the prediction strategy can be achieved by a direct application of the regret bound of OGA [2].

Lemma 3 is an application of Lemma 2.

With these three Lemmas, we can view that our proposed test usually receives samples drawn from the data source \(a^*\). Then, our main theorem is as follows: We use \(\forall\,H_i\) to denote the class of all distributions that satisfy the hypothesis \(H_i\) for \(i\in\left\{0,1\right\}\).

The proof of Theorem 1 is in Appendix 6.4. We incorporate the active selection with the ideas in [2]. Specifically, the level-\(\alpha\) property is a direct application of Ville’s inequality since \(\left\{W_t\right\}_{t\ge0}\) is a non-negative martingale. The power-one property follows as a consequence of a martingale strong law of large numbers argument, where the condition 4 can be achieved since \(R^{(a^*)}_{t}(\mathcal{A}^{a^*}_{\text{pred}})/t\) converges to zero as \(t\rightarrow\infty\) almost surely (by the regret of OGA [2]), \(N_{a^*,t}/t\) converges to one as \(t\rightarrow\infty\) almost surely (from Lemma 3), and \(D^{(a^*)}_{\mathcal{G}}>0\).

More interestingly, the expected stopping time obtained here may be smaller than the passive setting [2] in some cases. In applications considered in [2], one can verify that the quantity \(t_0\) defined in this paper and the term \(\sum_{t\geq 1}\mathbb{P}(E^c_{t,a^*})+T_{\text{explore}}\in O(1)\) are both of order \(O(\sigma^2_{a^*}\log(1/D^{(a^*)}_{\mathcal{G}}\alpha)/(D^{(a^*)}_{\mathcal{G}})^2)\). Consequently, when \(\alpha\) is small enough so that this term dominates the expected stopping time, and when \(\sigma_{a^*}^2 \leq \max_{k \neq a^*} \sigma_k^2\), our proposed test achieves a smaller expected stopping time than the procedure in [2] whenever their (single) data source does not coincide with the most informative source \(a^*\) in our setting. This demonstrates the gain from heterogeneity (so-called the gain of adaptivity). We summarize this comparison in Corollary 1.

The additional cost in the upper bound 5 is due to exploration. The detailed proof of the corollary is in Appendix 6.5.

5 Conclusion↩︎

In this paper, we introduce active source selection into general nonparametric sequential two-sample testing. Our proposed test combines the powerful testing-by-betting framework of [2] with a simple yet effective \(\epsilon(t)\)-greedy exploration strategy. Our test is a level-\(\alpha\) power-one procedure, and we show that adaptive source selection yields a provable gain in terms of the expected stopping time. To the best of our knowledge, this is the first work that studies active selection in sequential hypothesis testing in a nonparametric model (without the knowledge of data distribution). Our selection policy may also be adapted to more general sequential nonparametric testing problems. Finally, our setting naturally suggests a new best-arm identification problem with time-varying rewards, where each arm has an unknown reward distribution that somehow converges over time.

6 Appendix↩︎

In this Appendix, we first provide details of our proposed test in Appendix 6.1. The ONS betting strategy in Appendix 6.2, which is similar to that in [2]. Following this, the detailed proofs of Lemma 1, Lemma 2, and Lemma 3 are shown in Appendix 6.3. The proof of Theorem 1 is provided in Appendix 6.4, where we mainly follow the proof idea in [2] with careful handling of the action-taking behavior. Then, we provide the detailed proof of Corollary 1 in Appendix 6.5. Finally, we list technical lemmas in Appendix 6.6 for the above proofs.

6.1 Proposed test↩︎

Our proposed test is summarized as follows: The data-driven betting-wealth process and our stopping time are defined as \(\left\{W_t\right\}_{t\ge0}\) and \(\tau^{(\text{ASN2T})}\). Set \(W_0=1\) and \[\begin{align} C:=K(c_1 + 40K) + 4K \sqrt{5K(c_1 + 20K)},\quad c_1=\frac{2560}{L^2}, \end{align}\] where \(L\) is the lower bound of the suboptimal gap \(r\) defined in Section 2. Then, at each time slot \(t\ge1\), \[\begin{align} &\epsilon(t)=\min\left\{1,C/t\right\},\\ &\delta_t \begin{cases} =\mathop{\mathrm{arg\,max}}_{k\in[K]}\hat{\mu}_{k,{t-1}}\quad\text{with probability }1-\epsilon(t),\\ \sim\text{Unif}([K])\quad\text{with probability }\epsilon(t), \end{cases}\\ &W_{t}=W_{t-1}\cdot(1+\lambda_t v^{(\delta_t)}_t(g_{\delta_t,t})), \end{align}\] and \(\tau^{(\text{ASN2T})}:=\inf\left\{t\ge1:W_t\geq1/\alpha\right\}\), where \(v^{(k)}_t(g)\) and the running average \(\hat{\mu}_{k,t}\) are defined as, \(\forall\,k\in[K], t\geq1, g\in\mathcal{G}\), \[\begin{align} &v^{(k)}_t(g):=g(X_{k,1}(t))-g(X_{k,2}(t)),\\ &\hat{\mu}_{k,t}:=\frac{1}{N_{k,t}}\sum_{s=1}^{t}v^{(k)}_s(g_{k,s})\mathbb{1}\left\{\delta_s=k\right\},\\ &N_{k,t}:=\sum_{s=1}^{t}\mathbb{1}\left\{\delta_s=k\right\}. \end{align}\]

6.2 ONS betting strategy↩︎

In this section, we provide the ONS betting strategy for updating \(\lambda_{t}\) defined in our proposed test. Recall that \[\begin{align} v^{(k)}_t(g):=g(X_{k,1}(t))-g(X_{k,2}(t))\quad\forall\,k\in[K], t\ge1, g\in\mathcal{G}, \end{align}\] we have the following definition.

Therefore, following the argument in [15], the lower bound of the growth rate of \(W_t\) in our proposed test is as follows, \[\begin{align} W_t&\geq \frac{1}{\sum_{s=1}^t (v^{(\delta_s)}_{s}(g_{\delta_s,s}))^2} \exp\left( \frac{\left( \sum_{s=1}^t v^{(\delta_s)}_{s}(g_{\delta_s,s}) \right)^2}{4 \left( \sum_{s=1}^t (v^{(\delta_s)}_{s}(g_{\delta_s,s}))^2 + \sum_{s=1}^t v^{(\delta_s)}_{s}(g_{\delta_s,s}) \right)} \right)\\ &\geq \exp\left( \frac{t}{8} \left( \frac{1}{t} \sum_{s=1}^t v^{(\delta_s)}_{s}(g_{\delta_s,s}) \right)^2 - \log(t) \right). \end{align}\] One can notice that under the alternative, if \(\delta_s=a^*\), the lower bound of the growth rate of \(W_t\) is intuitively the fastest.

6.3 Proof of lemmas in the paper↩︎

The lemmas introduced in the paper are for the analysis of the expected stopping time, so it is sufficient only to consider the alternative is true. Hence, we may ignore the index \(H_1\) in \(\mathbb{P}_{H_1}\) and \(\mathbb{E}_{H_1}\) for notational simplicity in these lemmas and their relatives.

6.3.1 Proof of Lemma 1↩︎

Recall \(N_{k,t}:=\sum_{s=1}^{t}\mathbb{1}\left\{\delta_s=k\right\}\). We have, \(\forall\,k\in[K]\), and any finite \(c_1>0\), \[\begin{align} \mathbb{P}\left(N_{k,t}<c_1\log(t)\right)&=\mathbb{P}\left(\sum_{s=1}^{t}\mathbb{1}\left\{\delta_s=k\right\}<c_1\log(t)\right)\\ &=\mathbb{P}\left(\sum_{s=1}^{t}\left(\mathbb{1}\left\{\delta_s=k\right\}-P(\delta_s=k|F_{s-1})\right)<c_1\log(t)-\sum_{s=1}^{t}P(\delta_s=k|F_{s-1})\right),\label{eq:lemma1951} \end{align}\tag{6}\] where 6 is by subtracting \(\sum_{s=1}^{t}P(\delta_s=k|F_{s-1})\) on both sides. We will apply Lemma 5 to propose an upper bound.

For notational simplicity, we define \(a_s:=\mathbb{1}\left\{\delta_s=k\right\}-P(\delta_s=k|F_{s-1})\). It is easy to verify that \(\left\{a_s, F_{s}\right\}_{s\ge0}\) is a martingale difference. Then, by our selection policy, \[\begin{align} P(\delta_s=k|F_{s-1})=(1-\epsilon(s))\mathbb{1}\left\{\hat{\mu}_{k,s-1}\geq\max_{m\neq k}\hat{\mu}_{m,{s-1}}\right\}+\epsilon(s)\frac{1}{K}, \end{align}\] we know \(P(\delta_s=k|F_{s-1})\geq\frac{1}{K}\epsilon(s)\), where \(\epsilon(s):=\min\left\{1,C/s\right\}\), leading to \[\begin{align} \sum_{s=1}^{t}P(\delta_s=k|F_{s-1})\geq\frac{1}{K}\sum_{s=1}^{t}\epsilon(s)=\frac{1}{K}\left(C+\sum_{s=C+1}^{t}\frac{C}{s}\right)\geq\frac{C}{K}\left(\log(t)+1-\log(C)\right), \end{align}\] where the last inequality is due to \(\sum_{s=C+1}^{t}1/s\geq \log(t)-\log(C)\) and \(t\geq C+1\). Plugging the definition of \(a_s\) and this upper bound into 6 , we have \[\begin{align} \mathbb{P}\left(N_{k,t}<c_1\log(t)\right)&\leq\mathbb{P}\left(\sum_{s=1}^{t}a_s<c_1\log(t)-\frac{C}{K}\left(\log(t)+1-\log(C)\right)\right)\\ &=\mathbb{P}\left(\sum_{s=1}^{t}a_s<\left(c_1-\frac{C}{K}\right)\log(t)-\frac{C}{K}\left(1-\log(C)\right)\right),\label{eq:lemma1952} \end{align}\tag{7}\] where in 7 , we put \(\log(t)\) together. Then, to apply Lemma 5, we know \(|a_s|\leq 1\) for all \(s\ge1\). It remains to ensure that the right-hand side of 7 is negative and to upper bound \(\sum_{s=1}^{t}\mathbb{E}[a_s^2|F_{s-1}]\).

First of all, we set \(C>Kc_1\) (we will provide the overall requirement of \(C\) later) and have \[\begin{align} \sum_{s=1}^{t}\mathbb{E}[a_s^2|F_{s-1}]&=\sum_{s=1}^{t}\mathbb{E}[\mathbb{1}\left\{\delta_s=k\right\}^2|F_{s-1}]-P(\delta_s=k|F_{s-1})^2\tag{8}\\ &=\sum_{s=1}^{t}\mathbb{E}[\mathbb{1}\left\{\delta_s=k\right\}|F_{s-1}]-P(\delta_s=k|F_{s-1})^2\tag{9}\\ &=\sum_{s=1}^{t}P(\delta_s=k|F_{s-1})(1-P(\delta_s=k|F_{s-1}))\tag{10}\\ &\leq\sum_{s=1}^{t}\min\left\{P(\delta_s=k|F_{s-1}), 1-P(\delta_s=k|F_{s-1})\right\} \tag{11} \end{align}\] where 8 is from the definition of \(a_s\), 9 holds true since \(\mathbb{1}\{\delta_s=k\}\) is a binary value, 10 is from the definition of the expectation, and 11 is due to \(ab\leq \min\left\{a,b\right\}\) if \(a,b\in[0,1]\). Moreover, by our selection policy, we know \(P(\delta_s=k|F_{s-1})\) is either \((1-(K-1)\epsilon(s)/K)\) or \(\epsilon(s)/K\) at each time slot \(s\ge1\), hence, \(\min\left\{P(\delta_s=k|F_{s-1}), 1-P(\delta_s=k|F_{s-1})\right\}\) equals to \[\begin{align} \min\{(1-\frac{K-1}{K}\epsilon(s)), \frac{K-1}{K}\epsilon(s)\}\quad\text{or}\quad\min\{\frac{1}{K}\epsilon(s), 1-\frac{1}{K}\epsilon(s)\}. \end{align}\] Then, by \(\epsilon(s)=\min\{1,C/s\}\leq\frac{1}{2}\frac{K}{K-1}\), where we can assume \(K\ge2\) for the heterogeneous data sources, we have \[\begin{align} \min\left\{P(\delta_s=k|F_{s-1}), 1-P(\delta_s=k|F_{s-1})\right\}\leq\frac{K-1}{K}\epsilon(s)\quad\forall\,s\ge1. \end{align}\] Therefore, we get \[\begin{align} \sum_{s=1}^{t}\mathbb{E}[a_s^2|F_{s-1}]&\leq C+\sum_{s=C+1}^{t}\frac{C}{s}\frac{K-1}{K} \tag{12}\\ &\leq C+ \frac{C(K-1)}{K}(\log(t)-\log(C))\tag{13}\\ &\leq\frac{C(K-1)}{K}\log (t)+C\tag{14}, \end{align}\] where 12 is from the definition of \(\epsilon(s)\), 13 is from \(\sum_{s=C+1}^{t}1/s\leq\log(t)-\log(C)\) and \(t\geq C+1\), and 14 holds if \(C\ge1\) (we will set \(C\) later).

Then, we can apply Lemma 5. For notational simplicity, define \(A:=\frac{C}{K} - c_1\) and \(B:=\frac{C}{K}(\log(C)-1)\) and \(C>\max\{1,Kc_1\}\), then for all \(t>\max\{C+1,\exp\left( \frac{ B}{ A}\right)\}\), i.e., \(A\log(t)-B>0\), \[\begin{align} \mathbb{P}\left(N_{k,t}<c_1\log(t)\right)&\leq\mathbb{P}\left(\sum_{s=1}^{t}a_s<-(A\log(t)-B)\right)\\ &\leq2\exp\left(-\frac{1}{2}\frac{(A\log(t)-B)^2}{\frac{C(K-1)}{K}\log (t)+C+\frac{A\log(t)-B}{3}}\right), \end{align}\] where the last inequality is from Lemma 5.

In the following, we simplify the exponent. For the numerator, \(A\log(t)-B\geq\frac{A}{2}\log(t)\), \(\forall\,t\ge \exp(2B/A)\). Moreover, the upper bound of the denominator is derived as follows \[\begin{align} \frac{C(K-1)}{K}\log (t)+C+\frac{A\log(t)-B}{3}&\leq\frac{C(K-1)}{K}\log (t)+C+\frac{A}{3}\log(t)\tag{15}\\ &=\left(\frac{C(K-1)}{K}+\frac{A}{3}\right)\log(t)+C\tag{16}\\ &=\left(\frac{3CK-2C}{3K}-\frac{c_1}{3}\right)\log(t)+C\tag{17}\\ &\leq C\log(t)+C\tag{18}, \end{align}\] where 15 holds if \(C>2\), i.e., \(B>0\), in 16 we put \(\log(t)\) together, 17 is from the definition of \(A\), and 18 is from \(C\geq0\) and \(c_1\geq0\). Then, \(\forall\,t\geq 2\), \(C\leq C\log(t)\), leading to \[\begin{align} \frac{C(K-1)}{K}\log (t)+C+\frac{A\log(t)-B}{3}\leq 2C\log(t). \end{align}\]

Consequently, combining the above results, we have, \(\forall\,t>\max\left\{C+1, 2, \exp(2B/A)\right\}\), \(C>\max\{Kc_1, 2\}\), \[\begin{align} \mathbb{P}\left(N_{k,t}<c_1\log(t)\right)&\leq2\exp\left(-\frac{1}{2}\frac{\frac{A^2}{4} \log^2(t)}{2C\log(t)}\right)=2\exp\left(-\frac{A^2}{16C}\log(t)\right)=\frac{2}{t^{A^2/(16C)}}=\frac{2}{t^{(C/K - c_1)^2/16C}}. \end{align}\] Then, we further set \(C \geq K(c_1 + 40K) + 4K \sqrt{5K(c_1 + 20K)}\), leading to \[\begin{align} \mathbb{P}\left(N_{k,t}<c_1\log(t)\right)\leq\frac{2}{t^{5}}. \end{align}\]

To conclude this proof, we get for any \(c_1>0\), if \(C \geq K(c_1 + 40K) + 4K \sqrt{5K(c_1 + 20K)}\), then \[\begin{align} \mathbb{P}\left(N_{k,t}<c_1\log(t)\right)\leq\frac{2}{t^{5}}\quad\forall\,t>T_1:=t>\max\left\{C+1, \exp(2B/A)\right\}. \end{align}\] where \(A:=\frac{C}{K} - c_1\) and \(B:=\frac{C}{K}(\log(C)-1)\). One can notice that the \(T_1\in O(C^{3})\). Moreover, this lemma only depends on the design of the exploration. Therefore, the inequality also holds for the null hypothesis.

6.3.2 Proof of Lemma 2↩︎

The goal is to show that there exists a finite constant time \(T_2>0\) such that \[\begin{align} \mathbb{P}(\max_{k\neq a^*}\hat{\mu}_{k,t}\geq\hat{\mu}_{a^*,t})\in O(\frac{K}{t^5}\frac{1}{r^2})\quad \forall\,t>T_2, \end{align}\] under the sublinear regret condition, \(R^{(a^*)}_t\in O\left(\sqrt{N_{a^*,t}}\right)\).

Recall \(r:=D^{(a^*)}_{\mathcal{G}}-\max_{k\neq a^*}D^{(k)}_{\mathcal{G}}\). Since \[\begin{align} \left\{\max_{k\neq a^*}\hat{\mu}_{k,t}\geq\hat{\mu}_{a^*,t}\right\}&=\left\{D^{(a^*)}_{\mathcal{G}}-\hat{\mu}_{a^*,t}+\max_{k\neq a^*}\hat{\mu}_{k,t}-\max_{k\neq a^*}D^{(k)}_{\mathcal{G}}\ge r\right\}\tag{19}\\ &\subseteq\left\{D^{(a^*)}_{\mathcal{G}}-\hat{\mu}_{a^*,t}\geq\frac{r}{2}\right\}\cup\left\{\max_{k\neq a^*}\hat{\mu}_{k,t}-\max_{k\neq a^*}D^{(k)}_{\mathcal{G}}\geq \frac{r}{2}\right\}\tag{20}\\ &\subseteq\left\{D^{(a^*)}_{\mathcal{G}}-\hat{\mu}_{a^*,t}\geq\frac{r}{2}\right\}\cup\left\{\cup_{k\neq a^*}\left\{\hat{\mu}_{k,t}-D^{(k)}_{\mathcal{G}}\geq\frac{r}{2}\right\}\right\},\tag{21} \end{align}\] where 19 is from the definition of \(r\), 20 is due to \(\{a+b\geq r\}\subseteq\{a\geq r/2 \cup b\geq r/2\}\), and 21 is due to \(\max_k(a_k-b_k)\geq\max_k a_k-\max_k b_k\) and the definition of \(\text{max}\). Then, by union bound, we have \[\begin{align} \mathbb{P}(\max_{k\neq a^*}\hat{\mu}_{k,t}\geq\hat{\mu}_{a^*,t})\leq\mathbb{P}\left(D^{(a^*)}_{\mathcal{G}}-\hat{\mu}_{a^*,t}\geq\frac{r}{2}\right)+\sum_{k\neq a^*}\mathbb{P}\left(\hat{\mu}_{k,t}-D^{(k)}_{\mathcal{G}}\geq\frac{r}{2}\right). \end{align}\] Consequently, by Lemma 6 and Lemma 7, if \(\exists M>0\) such that \[\begin{align} \frac{R^{(a^*)}_t}{N_{a^*,t}}\leq \frac{M}{\sqrt{N_{a^*,t}}}\quad\text{almost surely}, \end{align}\] we have \[\begin{align} \mathbb{P}(\max_{k\neq a^*}\hat{\mu}_{k,t}\geq\hat{\mu}_{a^*,t})&\leq \frac{K}{1-\exp\left\{-\frac{r^2}{512}\right\}}\frac{1}{t^{5}}+\frac{2K}{t^{5}}\\ &\leq \frac{K}{t^5}(1+\frac{512}{r^2})+\frac{2K}{t^5}\quad\forall t\geq \max\left\{T_1, T_{2,1}\right\}\label{eq:lemma2954} \end{align}\tag{22}\] where 22 is due to \(1/(1-\exp(-x))\leq1+1/x\) for \(x>0\), and \(T_1\) is defined in Appendix 6.3.1 with \(c_1\geq\frac{2560}{r^2}\). Therefore, we have \(T_2:=\max\left\{T_1, T_{2,1}\right\}\) with \(T_{2,1}:=\exp(16M^2/(r^2 c_1))\).

6.3.3 Proof of Lemma 3↩︎

The goal is to show that there exists a finite \(T_3>0\) such that \(\forall\,t\geq T_3\), \[\begin{align} \mathbb{P}\left(N_{k,t}>\sqrt{t}\right)\in O(\frac{K}{t^2}\cdot\frac{1}{r^2}), \end{align}\]

For any \(k\neq a^*\), let us define \(a_s=\mathbb{1}\left\{\delta_s=k\right\}-P(\delta_s=k|F_{s-1})\) and from Appendix 6.3.1, it is a martingale process adapted to \(\left\{F_{s}\right\}_{s\ge1}\). By the definition of \(N_{k,t}\), we have \[\begin{align} \mathbb{P}\left(N_{k,t}>\sqrt{t}\right)&\leq\mathbb{P}\left(\sum_{s=1}^{t}a_s>\sqrt{t}-\sum_{s=1}^{t}P(\delta_s=k|F_{s-1})\right). \end{align}\] Then, by our selection policy, \(P(\delta_s=k|F_{s-1})=(1-\epsilon(s))\mathbb{1}\left\{\hat{\mu}_{k,s-1}\geq\max_{m\neq k}\hat{\mu}_{m,s-1}\right\}+\epsilon(s)/K\) for any \(k\in[K]\), \(s\ge1\), we have \[\begin{align} \sum_{s=1}^{t}P\left(\delta_s=k|F_{s-1}\right)&\leq\sum_{s=1}^{t}\mathbb{1}\left\{\hat{\mu}_{k,s-1}\geq\max_{m\neq k}\hat{\mu}_{m,s-1}\right\}+\sum_{s=1}^{t}\epsilon(s)/K\\ &\leq\sum_{s=1}^{t}\mathbb{1}\left\{\hat{\mu}_{k,s-1}\geq\max_{m\neq k}\hat{\mu}_{m,s-1}\right\}+C/K+C\log(t)/K\label{eq:lemma3951}, \end{align}\tag{23}\] where 23 is due to the definition of \(\epsilon(s)\) and \(\sum_{s=C+1}^{t}1/s\leq\log(t)\) (\(t\geq C+1\) and \(C>1\) are required). Hence, we have \[\begin{align} \mathbb{P}\left(N_{k,t}>\sqrt{t}\right)&\leq\mathbb{P}\left(\sum_{s=1}^{t}a_s>\sqrt{t}-\left(\sum_{s=1}^{t}\mathbb{1}\left\{\hat{\mu}_{k,s-1}\geq\max_{m\neq k}\hat{\mu}_{m,s-1}\right\}+C/K+C\log(t)/K\right)\right)\\ &=\mathbb{P}\left(\sum_{s=1}^{t}a_s>\sqrt{t}-E_t\right),\label{eq:lemma3952} \end{align}\tag{24}\] where \(E_t:=\sum_{s=1}^{t}\mathbb{1}\left\{\hat{\mu}_{k,s-1}\geq\max_{m\neq k}\hat{\mu}_{m,s-1}\right\}+C/K+C\log(t)/K\) in 24 . Then, we have \[\begin{align} \mathbb{P}\left(N_{k,t}>\sqrt{t}\right)&\leq\mathbb{P}\left(\sum_{s=1}^{t}a_s>\sqrt{t}-E_t, E_t<\frac{1}{2}\sqrt{t}\right)+\mathbb{P}(E_t\geq \frac{1}{2}\sqrt{t})\tag{25}\\ &\leq\mathbb{P}\left(\sum_{s=1}^{t}a_s>\frac{1}{2}\sqrt{t}\right)+\frac{64K}{t^2}\left(\frac{1}{1-\exp\left\{-\frac{r^2}{512}\right\}}+2\right)\quad\forall\,t\geq\max\{T_2+1, T_{3,1}\}\tag{26}\\ &\leq\mathbb{P}\left(\sum_{s=1}^{t}a_s>\frac{1}{2}\sqrt{t}\right)+\frac{64K}{t^2}\left(3+\frac{512}{r^2}\right)\tag{27}, \end{align}\] where 25 is similar to 43 , 26 is from Lemma 8 with \(T_2\) defined in Appendix 6.3.2 and \(T_{3,1}\) defined in Lemma 8, and 27 is due to \(1/(1-\exp(-x))\leq1+1/x\) for \(x>0\).

For the first term in@eq:eq:lemma3955 , following a similar argument in Appendix 6.3.1, we have \[\begin{align} \mathbb{P}\left(\sum_{s=1}^{t}a_s>\frac{1}{2}\sqrt{t}\right)&\leq 2\exp\left(-\frac{1}{2}\frac{t/4}{C\log(t)/2+C+\sqrt{t}/6}\right)\\ &\leq2\exp\left(-\frac{1}{2}\frac{t/4}{\sqrt{t}/3}\right)\quad \forall\,t\geq 144C^2\log^2(12C)\\ &=2\exp\left(-\frac{3}{8}\sqrt{t}\right). \end{align}\] Finally, by defining \(T_3:=\max\left\{T_2+1, T_{3,1},144C^2\log^2(12C)\right\}\) and noticing that \(\exp\left(-3\sqrt{t}/8\right)\) is faster decaying than \(O(1/t^2)\), we can combine the above results and complete the proof.

6.4 Proof of Theorem 1↩︎

We combine our active selection strategy with the ideas in [2] to prove Theorem 1. Therefore, we will use the lemmas introduced in 6.3 to control the selection behavior.

6.4.1 Proof of Level-\(\alpha\) property↩︎

The goal is to show: for any \(\left\{\mathcal{A}^{(k)}_{\text{pred}}\right\}_{k\in[K]}\), \(\mathcal{A}_{\text{bet}}\), and selection policy defined in Definition 1, given a predefined accuracy \(\alpha\in(0,1)\), \[\begin{align} \mathbb{P}_{H_0}(\tau^{(\text{ASN2T})}<\infty)\leq\alpha\quad\forall\,H_0. \end{align}\]

We only need to show that the wealth process \(\left\{W_t\right\}\) is a nonnegative supermartingale (or martingale) and apply Ville’s inequality. \(\forall\,H_0\), we have \[\begin{align} \mathbb{E}_{H_0}[W_{t}|F_{t-1}] &= W_{t-1} +W_{t-1}\mathbb{E}_{H_0}\left[\lambda_{t}v_{t}^{(\delta_t)}(g_{\delta_t,t})\,|\,F_{t-1}\right]\\ &=W_{t-1}+W_{t-1}\sum_{k\in[K]}\mathbb{E}_{H_0}\left[\lambda_{t}(g_{k,t}(X_{k,1}(t))-g_{k,t}(X_{k,2}(t)))\,|\,F_{t-1},\delta_{t}=k\right]P(\delta_{t}=k\,|\,F_{t-1}) \tag{28}\\ &=W_{t-1}\tag{29}, \end{align}\] where 28 is by the definition of \(v^{(k)}_{t}(g)\) in 2 and 29 is due to the fact that \((X_{\delta_t,1}(t), X_{\delta_t,2}(t))\sim P_{\delta_t,1}\times P_{\delta_t,2}\), and \(\lambda_{t}\) and \(g_{k,t}\) are \(F_{t-1}\) measurable, and under the null hypothesis, \(X_{k,1}\) and \(X_{k,2}\) have the same distribution for all \(k\in[K]\).

Therefore, \(\{W_t\}_{t\geq0}\) is a martingale. Then, since the range of \(g_{k,t}\) for each \(k\in[K]\) is in \([-1/2,1/2]\) and \(\lambda_t\in[-1,1]\), \(W_t\geq0\) for any \(t\geq0\). That is, \(\{W_t\}_{t\geq0}\) is a non-negative martingale since \(1+\lambda_t v_{t}^{(\delta_t)}(g_{\delta_t,t})\geq0\).

Consequently, we can apply Ville’s inequality, leading to \[\begin{align} \mathbb{P}_{H_0}(\tau^{(\text{ASN2T})}<\infty) = \mathbb{P}_{H_0}(\exists t\geq1:W_t\geq\frac{1}{\alpha})\leq \alpha, \end{align}\] where the last inequality is due to Ville’s inequality.

6.4.2 Proof of power-one property↩︎

The goal is to show that, if almost surely, \[\begin{align} \limsup_{t\rightarrow\infty}\left(\frac{R^{(a^*)}_{t}}{t}-\frac{1}{t}\sum_{s=1}^{t}D^{(a^*)}_{\mathcal{G}}\mathbb{1}\left\{\delta_s=a^*\right\}\right)<0, \end{align}\] then \[\mathbb{P}_{H_1}(\tau^{(\text{ASN2T})}<\infty)=1\quad\forall H_1.\] Equivalently, let us prove \(\mathbb{P}_{H_1}(\tau=\infty)=0\). By the property of the stopping time, \[\begin{align} \mathbb{P}_{H_1}(\tau^{(\text{ASN2T})}=\infty)\leq\mathbb{P}_{H_1}(\tau^{(\text{ASN2T})}>t)\quad\forall\,t\ge1, \end{align}\] we have \(\mathbb{P}_{H_1}(\tau^{(\text{ASN2T})}=\infty)\leq\liminf_{t\rightarrow\infty}\mathbb{P}_{H_1}(\tau^{(\text{ASN2T})}>t)\). Then, we proceed to show \(\liminf_{t\rightarrow\infty}\mathbb{P}_{H_1}(\tau>t)=0\).

By the definition of \(\tau^{(\text{ASN2T})}\), we have \[\begin{align} \mathbb{P}_{H_1}(\tau^{(\text{ASN2T})}>t)\leq\mathbb{P}_{H_1}(W_{t}\leq\frac{1}{\alpha}). \end{align}\] Then, by Appendix 6.2, we have \(W_t\geq\exp\left( \frac{t}{8} \left( \frac{1}{t} \sum_{s=1}^t v^{(\delta_s)}_{s}(g_{\delta_s,s}) \right)^2 - \log(t) \right)\). Plugging this into the above inequality, we have \[\begin{align} \mathbb{P}_{H_1}(W_{t}\leq\frac{1}{\alpha})&\leq\mathbb{P}_{H_1}\left(\exp\left( \frac{t}{8} \left( \frac{1}{t} \sum_{s=1}^t v^{(\delta_s)}_{s}(g_{\delta_s,s}) \right)^2 - \log(t) \right)\leq\frac{1}{\alpha}\right)\\ &=\mathbb{P}_{H_1}\left(\frac{1}{t}\sum_{s=1}^{t}v^{(\delta_s)}_{s}(g_{\delta_s,s})\leq\sqrt{\frac{8(\log(1/\alpha)+\log(t))}{t}}\right)\label{eq:power95one951}, \end{align}\tag{30}\] where 30 is rearrangement.

Following this, by \(b_t:=\sqrt{\frac{8(\log(1/\alpha)+\log(t))}{t}}\), we have, \[\begin{align} &\left\{\frac{1}{t}\sum_{s=1}^{t}v^{(\delta_s)}_{s}(g_{\delta_s,s})\leq b_t\right\}\\ &=\left\{\frac{1}{t}\sum_{s=1}^{t}v^{(a^*)}_{s}(g_{a^*,s})\mathbb{1}\{\delta_s=a^*\}+\frac{1}{t}\sum_{s=1}^{t}\sum_{k\neq a^*}v^{(k)}_{s}(g_{k,s})\mathbb{1}\{\delta_s=k\}\leq b_t\right\}\\ &\subseteq\left\{\frac{1}{t}\sum_{s=1}^{t}v^{(a^*)}_{s}(g_{a^*,s})\mathbb{1}\left\{\delta_s=a^*\right\}\leq b_t+\sum_{k\neq a^*}\frac{N_{k,t}}{t},\cap_{k\neq a^*}\left\{N_{k,t}\leq\sqrt{t}\right\}\right\}\cup\left\{\cup_{k\neq a^*}\left\{N_{k,n}>\sqrt{n}\right\}\right\}\tag{31}\\ &\subseteq\left\{\frac{1}{t}\sum_{s=1}^{t}v^{(a^*)}_{s}(g_{a^*,s})\mathbb{1}\left\{\delta_s=a^*\right\}\leq b_t+\frac{K-1}{\sqrt{t}}\right\}\cup\left\{\cup_{k\neq a^*}\left\{N_{k,t}>\sqrt{t}\right\}\right\}\tag{32}\\ &=\left\{\frac{1}{t}\sup_{g_{a^*}\in\mathcal{G}}\sum_{s=1}^{t}(g_{a^*}(X_{a^*,1}(s))-g_{a^*}(X_{a^*,2}(s)))\mathbb{1}\left\{\delta_s=a^*\right\}\leq\frac{R^{(a^*)}_t}{t}+\frac{K-1}{\sqrt{t}}+b_t\right\}\cup\left\{\cup_{k\neq a^*}\left\{N_{k,t}>\sqrt{t}\right\}\right\}\tag{33}\\ &\subseteq\left\{\frac{1}{t}\sum_{s=1}^{t}(g^*_{a^*}(X_{a^*,1}(s))-g^*_{a^*}(X_{a^*,2}(s)))\mathbb{1}\left\{\delta_s=a^*\right\}\leq\frac{R^{(a^*)}_t}{t}+\frac{K-1}{\sqrt{t}}+b_t\right\}\cup\left\{\cup_{k\neq a^*}\left\{N_{k,t}>\sqrt{t}\right\}\right\}\tag{34}\\ &=\left\{\frac{1}{t}\sum_{s=1}^{t}a_s\leq\frac{R^{(a^*)}_t}{t}-\frac{1}{t}\sum_{s=1}^{t}D^{(a^*)}_{\mathcal{G}}\mathbb{1}\left\{\delta_s=a^*\right\}+\frac{K-1}{\sqrt{t}}+b_t\right\}\cup\left\{\cup_{k\neq a^*}\left\{N_{k,t}>\sqrt{t}\right\}\right\}\tag{35}, \end{align}\] where 31 is due to \(|v^{k}_{s}(g)|\leq 1\) for all \(k\in[K], g\in\mathcal{G}, s\ge1\), the definition of \(N_{k,t}\), and the set operation in 43 , in 32 we apply the fact that \(\{N_{k,t}\leq \sqrt{t}\}\) for all \(k\neq a^*\) for the first term, 33 is due to the definition of the individual regret defined in 3 , 34 is due to the definition of supremum, and in 35 we denote \(a_s:=(g^*_{a^*}(X_{a^*,1}(s))-g^*_{a^*}(X_{a^*,2}(s))-D^{(a^*)}_{\mathcal{G}})\mathbb{1}\left\{\delta_s=a^*\right\}\) for all \(s\ge1\), which is a martingale difference.

Therefore, plugging 35 into 30 , by union bound, we have \[\begin{align} \mathbb{P}_{H_1}(W_{t}\leq\frac{1}{\alpha})\leq\mathbb{P}_{H_1}\left(\frac{1}{t}\sum_{s=1}^{t}a_s\leq\frac{R^{(a^*)}_t}{t}-\frac{1}{t}\sum_{s=1}^{t}D^{(a^*)}_{\mathcal{G}}\mathbb{1}\left\{\delta_s=a^*\right\}+\frac{K-1}{\sqrt{t}}+b_t\right)+\sum_{k\neq a^*}\mathbb{P}_{H_1}(N_{k,t}>\sqrt{t})\label{eq:power95one957}. \end{align}\tag{36}\] For the second term in 36 , by Lemma 3, we get \(\lim_{t\rightarrow\infty}\sum_{k\neq a^*}\mathbb{P}_{H_1}(N_{k,t}>\sqrt{t})\)=0. Then, by Fatou’s lemma, 36 turns to \(\liminf_{t\rightarrow\infty}\mathbb{P}_{H_1}(W_{t}\leq\frac{1}{\alpha})\leq\lim_{t\rightarrow\infty}\mathbb{E}_{H_1}[\mathbb{1}\left\{A_t\right\}]\), where \[A_t:=\left\{F_t:\frac{1}{t}\sum_{s=1}^{t}a_s\leq\frac{R^{(a^*)}_t}{t}-\frac{1}{t}\sum_{s=1}^{t}D^{(a^*)}_{\mathcal{G}}\mathbb{1}\left\{\delta_s=a^*\right\}+\frac{K-1}{\sqrt{t}}+b_t\right\}.\]

We then show, almost surely, \(\lim_{t\rightarrow\infty}\mathbb{1}\left\{A_t\right\}=0\). Since \(\sum_{t=1}^{\infty}\frac{\mathbb{E}[|a_t|^2]}{t^2}<\infty\) due to \(\mathbb{E}_{H_1}[|a_t|^2]<\infty\), and \(\{a_s\}_{s\ge0}\) is a martingale difference, by [16], we have \(\frac{1}{t}\sum_{s=1}^{t}a_s\) almost surely converges to \(0\). Moreover, by the assumption 4 , we have \(\limsup_{n\rightarrow\infty}\text{LHS}\geq 0> \limsup_{n\rightarrow\infty}\text{RHS}\), where \[\begin{align} \text{LHS}:=\frac{1}{t}\sum_{s=1}^{t}a_s,\quad\text{RHS}:=\frac{R^{(a^*)}_t}{t}-\frac{1}{t}\sum_{s=1}^{t}D^{(a^*)}_{\mathcal{G}}\mathbb{1}\left\{\delta_s=a^*\right\}+\frac{K-1}{\sqrt{t}}+b_t, \end{align}\] leading to \(\mathbb{1}\left\{A_t\right\}\overset{a.s.}{\rightarrow}0\). Therefore, by the bounded convergence theorem, we have \(\lim_{t\rightarrow\infty}\mathbb{E}_{H_1}[\mathbb{1}\left\{A_t\right\}]=0\). Hence, \(\mathbb{P}_{H_1}(\tau=\infty)=0\) holds true. Proof completes.

6.4.3 Proof of expected stopping time↩︎

For the expected stopping time, we make some notations in advance, for all \(k\in[K]\), \[\begin{align} &\tilde{\sigma}^2_k:=\sup_{g_k\in\mathcal{G}}\mathbb{E}[(g_k(X_{k,1})-g_k(X_{k,2}))^2],\quad \gamma_k=\sup_{g_k\in\mathcal{G}}\text{Var}((g_k(X_{k,1})-g_k(X_{k,2}))^2). \end{align}\]

The goal is to show that, if there exists \(\left\{r_{t}\right\}_{t\ge1}\) and \(E_{t,a^*}:=\left\{R^{(a^*)}_{t}/t\leq r_{t}\right\}\), then \[\begin{align} \mathbb{E}_{H_1}[\tau^{(\text{ASN2T})}]\in O(t_0+\sum_{t\geq 1}\mathbb{P}(E^c_{t,a^*})+T_{\text{explore}}) \end{align}\] where \(T_{\text{explore}}\) is proportional to \(K\) and \(1/L\), and \[\begin{align} t_0:=\inf\left\{t\ge1:D^{(a^*)}_{\mathcal{G}}\geq r_{t}+\sigma_{a^*}\sqrt{\frac{\log\frac{t}{\alpha}}{t}}+\frac{\log \frac{t}{\alpha}}{t}\right\},\quad\sigma_{k}:=\sqrt{\sup_{g_{k}}\text{Var}(g_{k}(X_{k,1})-g_{k}(X_{k,2}))}\quad\forall\,k\in[K]. \end{align}\] The proof of the upper bound of the expected stopping time basically follows the steps in [2]. However, in our case, we need to control the action-taking behavior since the lemmas in Appendix 6.3 will be used.

Let us start from a common representation of the expected stopping time. In the following, we consider the alternative to be true and ignore the index \(H_1\) in the notations of expectation and probability. Recall that \[\begin{align} \tau^{(\text{ASN2T})}:=\inf\left\{t\ge1:W_t\geq1/\alpha\right\},\quad\text{where}\;W_t=\Pi_{s=1}^{t}(1+\lambda_s v^{(\delta_s)}_{s}(g_{\delta_s,s})).\nonumber \end{align}\] We have \[\begin{align} \mathbb{E}[\tau^{(\text{ASN2T})}]&=\sum_{t=0}^{\infty}\mathbb{P}(\tau^{(\text{ASN2T})}>t) \leq\sum_{t=0}^{\infty}\mathbb{P}(\log(W_t)<\log(1/\alpha)). \end{align}\]

We proceed to show the upper bound of \(\mathbb{P}(\log(W_t)<\log(1/\alpha))\). By the fact of ONS betting strategy [2], \[\begin{align} \log(W_t)\geq\sup_{\lambda\in[-1/2, 1/2]}\sum_{s=1}^{t}\log(1+\lambda v^{(\delta_s)}_{s}(g_{\delta_s,s}))-12\log(t) , \end{align}\] we know \[\begin{align} \mathbb{P}(\log(W_t)<\log(1/\alpha))&\leq\mathbb{P}\left(\sup_{\lambda\in[-1/2, 1/2]}\sum_{s=1}^{t}\log(1+\lambda v^{(\delta_s)}_{s}(g_{\delta_s,s})))-12\log(t)<\log(1/\alpha)\right)\\ &=\mathbb{P}(A_t), \end{align}\] where \[\begin{align} A_t:=\left\{\sup_{\lambda\in[-1/2, 1/2]}\sum_{s=1}^{t}\log(1+\lambda v^{(\delta_s)}_{s}(g_{\delta_s,s})))-12\log(t)<\log(1/\alpha)\right\}. \end{align}\] Then, let us define \(B_t:=\left\{\lvert\sum_{s=1}^{t}v^{(\delta_s)}_{s}(g_{\delta_s,s}))\rvert\leq\sum_{s=1}^{t}(v^{(\delta_s)}_{s}(g_{\delta_s,s}))^2\right\}\) and get \[\begin{align} A_t=(A_t\cap B_t)\cup(A_t\cap B_t^c). \end{align}\] For \((A_t\cap B_t)\), we follow the first bullet point in [2] and get

\[\begin{align} (A_t\cap B_t)&\subseteq\left\{\frac{1}{4}\left(\sum_{s=1}^{t}v_s^{(\delta_s)}(g_{\delta_s,s})\right)^2/\sum_{s=1}^{t}(v_s^{(\delta_s)}(g_{\delta_s,s}))^2<12\log(\frac{t}{\alpha})\right\}\cap B_t\\ &=\left\{\left(\frac{1}{t}\sum_{s=1}^{t}v_s^{(\delta_s)}(g_{\delta_s,s})\right)^2<\frac{48}{t}\sum_{s=1}^{t}(v_s^{(\delta_s)}(g_{\delta_s,s}))^2\cdot\frac{1}{t} \log(\frac{t}{\alpha})\right\}\cap B_t:=D_{t,1}. \end{align}\] For \((A_t\cap B_t^c)\), we follow the second bullet point in [2]. Let us define two disjoint sets \(C_{t,1}\) and \(C_{t,2}\) such that \(B_t^c:=C_{t,1}\cup C_{t,2}\) and \[\begin{align} C_{t,1}:=\left\{\sum_{s=1}^{t}v^{(\delta_s)}_{s}(g_{\delta_s,s})\geq\sum_{s=1}^{t}(v^{(\delta_s)}_{s}(g_{\delta_s,s}))^2\right\}\quad\text{and}\quad C_{t,2}:=\left\{\sum_{s=1}^{t}v^{(\delta_s)}_{s}(g_{\delta_s,s})\leq-\sum_{s=1}^{t}(v^{(\delta_s)}_{s}(g_{\delta_s,s}))^2\right\}. \end{align}\] Then, taking \(\lambda=1/2\) in \(A_t\) and \(\log(1+\lambda v^{(\delta_s)}_{s}(g_{\delta_s,s}))\geq\lambda v^{(\delta_s)}_{s}(g_{\delta_s,s})-\lambda^2(v^{(\delta_s)}_{s}(g_{\delta_s,s}))^2\), we have \[\begin{align} (A_t\cap C_{t,1})&\subseteq\left\{\frac{1}{2}\sum_{s=1}^{t}v^{(\delta_s)}_{s}(g_{\delta_s,s})-\frac{1}{4}\sum_{t=1}^{n}(v^{(\delta_s)}_{s}(g_{\delta_s,s}))^2<12\log\frac{t}{\alpha}\right\}\cap C_{t,1}\\ &\subseteq\left\{\frac{1}{4}\sum_{s=1}^{t}v^{(\delta_s)}_{s}(g_{\delta_s,s})<12\log\frac{t}{\alpha}\right\}\label{eq:exp95time951}\\ &=\left\{\frac{1}{t}\sum_{s=1}^{t}v^{(\delta_s)}_{s}(g_{\delta_s,s})<\frac{48}{t}\log\frac{t}{\alpha}\right\}:=D_{t,2}, \end{align}\tag{37}\] where 37 is from the fact of \(C_{t,1}\), and \[\begin{align} (A_t\cap C_{t,2})\subseteq C_{t,2}\subseteq\left\{\frac{1}{t}\sum_{s=1}^{t}v^{(\delta_s)}_{s}(g_{\delta_s,s})<0\right\}:=D_{t,3}. \end{align}\] Therefore, we have \[\begin{align} \mathbb{P}(\tau^{(\text{ASN2T})}>t)\leq\mathbb{P}(A_t)\leq\mathbb{P}(D_{t,1})+\mathbb{P}(D_{t,2})+\mathbb{P}(D_{t,3})\label{eq:exp95time952}, \end{align}\tag{38}\]

Then, by 38 , the expected stopping time is upper-bounded by \[\begin{align} \mathbb{E}[\tau^{(\text{ASN2T})}]\leq 1+\sum_{t\ge1}\mathbb{P}(D_{t,1})+\mathbb{P}(D_{t,2})+\mathbb{P}(D_{t,3}). \end{align}\]

As a result, by Lemma 9, Lemma 10, and Lemma 11, we have, \[\begin{align} \mathbb{E}[\tau^{\text{ASN2T}}]&\leq T+T_3+\sum_{t\geq T+T_3}3\mathbb{P}(E^c_{t})+3\mathbb{P}(E^c_{t,a^*})+3\mathbb{P}(G^c_{t,1})+\mathbb{P}(G^c_{t,2}) \end{align}\] where \(T:=\max\left\{t_1,t_2,t_3,t_4\right\}\), \(t_1,t_2,t_3,t_4\) are defined in Lemma 9, Lemma 10, and Lemma 11, and \(T_3\) is defined in Appendix 6.3.3.

Consequently, by [2], we know \(T\in O(t_0)\) where \(t_0\) is defined in Theorem 1, and with the fact that \(T_{\text{explore}}\equiv T_3\in \tilde{O}(C^3)\asymp\tilde{O}\left(\frac{K^3}{L^6}\right)\) and \(3\sum_{t\geq T_3}\left(\mathbb{P}(E^c_{t})+\mathbb{P}(G^c_{t,1})+\mathbb{P}(G^c_{t,2})\right)\in O(1)\), we get the desired result.

6.5 Proof of Corollary 1↩︎

The goal is to show that if the passive setting [2] uses the sub-optimal data source and \(\sigma_{a^*}^2\leq\max_{k\neq a^*}\sigma_{k}^2\), then \[\begin{align} \mathbb{E}[\tau^{\text{ASN2T}}]\leq\mathbb{E}[\tau^{(p)}]+O\left(\frac{K^2}{r^2}(\log(1/\alpha))^{2/3}\right), \end{align}\] where \(\tau^{(p)}\) denotes the stopping time in the general test proposed in [2]. Asymptotically, \[\begin{align} \lim_{\alpha\rightarrow0}\frac{\mathbb{E}[\tau^{\text{ASN2T}}]}{\log(1/\alpha)}\leq\lim_{\alpha\rightarrow0}\frac{\mathbb{E}[\tau^{(p)}]}{\log(1/\alpha)}. \end{align}\]

The ground truth hypothesis is \(H_1\) in this proof. Let us compare \(t_1\), \(t_2\), \(t_3\) defined in the proof of the expected stopping time, Appendix 6.4.3, with those in the passive setting (we do not need to compare \(t_4\) since they are the same). Assume in the passive setting, they use any data source \(k\) where \(k\neq a^*\) and assume \(\sigma_{a^*}\leq \sigma_{k}\). For \(t_2^{(p)}\), representing the passive version of \(t_2\), from [2], we know \[\begin{align} t_2^{(p)}=\inf\left\{t\ge1:\frac{D^{(k)}_{\mathcal{G}}}{2}\geq\frac{48}{t}\log\frac{t}{\alpha}+\sigma_{k}\sqrt{\frac{4\log(t)}{t}}+\frac{2\log(t)}{3t}+r_{t}\right\}, \end{align}\] where \(\sigma^2_k\) is the corresponding variance of that source. Recall the definition of \(t_2\) in this paper \[\begin{align} t_2:=\inf\left\{t\ge1:\frac{D^{(a^*)}_{\mathcal{G}}}{2}\geq\frac{K-1}{\sqrt{t}}+\frac{48}{t}\log\frac{t}{\alpha}+\sigma_{a^*}\sqrt{\frac{4\log(t)}{t}}+\frac{2\log(t)}{3t}+r_t\right\}. \end{align}\] Therefore, we have \(t_2= t_2^{(p)}+O(\frac{4(K-1)^2}{r^2})\).

Similarly, for \(t_3^{(p)}\) defined as \[\begin{align} t_3^{(p)}=\inf\left\{t\ge1:\frac{D^{(k)}_{\mathcal{G}}}{2}\geq\sigma_{k}\sqrt{\frac{4\log(t)}{t}}+\frac{2\log(t)}{3t}+r_{t}\right\}. \end{align}\] Recall the definition of \(t_3\) in this paper \[\begin{align} t_3:=\inf\left\{t\ge1:\frac{D^{(a^*)}_{\mathcal{G}}}{2}\geq\frac{K-1}{\sqrt{t}}+\sigma_{a^*}\sqrt{\frac{4\log(t)}{t}}+\frac{2\log(t)}{3t}+r_t\right\}. \end{align}\] Therefore, we also have \(t_3= t_3^{(p)}+O(\frac{4(K-1)^2}{r^2})\).

Finally, for \(t_1^{(p)}\) defined as \[\begin{align} t_1^{(p)}:=\inf\left\{t\ge1:\frac{D^{(k)}_{\mathcal{G}}}{2}\geq r_{t}+9\sigma_{k}\sqrt{\frac{2\log(t/\alpha)}{t}}+7\sqrt{2\tilde{\sigma}_k}\Big(\frac{\log\frac{t}{\alpha}}{t}\Big)^{3/4}+\frac{8\log\frac{t}{\alpha}}{t}\right\}, \end{align}\] recall the definition of \(t_1\) 61 , \[\begin{align} t_1:=\inf\left\{t\ge1:\frac{D^{(a^*)}_{\mathcal{G}}}{2}\geq r_t+\frac{K-1}{\sqrt{t}}+7\frac{\sqrt{(K-1)\log\frac{t}{\alpha}}}{t^{3/4}}+9\sigma_{a^*}\sqrt{\frac{2\log(t/\alpha)}{t}}+7\sqrt{2\tilde{\sigma}_{a^*}}\Big(\frac{\log\frac{t}{\alpha}}{t}\Big)^{3/4}+\frac{8\log\frac{t}{\alpha}}{t}\right\}, \end{align}\] we have \(t_1= t_1^{(p)}+O\!\left(\frac{K^2}{r^2}\Big(\log\frac{1}{\alpha}\Big)^{2/3}\right)\) by a simple algebra.

Therefore, we have \[\begin{align} \max\left\{t_1,t_2,t_3\right\}\leq\max\left\{t_1^{(p)},t_2^{(p)},t_3^{(p)}\right\}+O\!\left(\frac{K^2}{r^2}\Big(\log\frac{1}{\alpha}\Big)^{2/3}\right). \end{align}\] Then, since \(\sum_{t\geq t_0}\mathbb{P}(E_{t})+\mathbb{P}(E_{t,a^*})+\mathbb{P}(G_{t,1})+\mathbb{P}(G_{t,2})\in O(1)\) and \(T_3\in o(\frac{K^2}{r^2}(\log\frac{1}{\alpha})^{2/3})\) as \(\alpha\) is small, we have \[\begin{align} \mathbb{E}[\tau^{\text{ASN2T}}]\leq\mathbb{E}[\tau^{(p)}]+O\left(\frac{K^2}{r^2}(\log(1/\alpha))^{2/3}\right). \end{align}\] Asymptotically, we have \[\begin{align} \lim_{\alpha\rightarrow0}\frac{\mathbb{E}[\tau^{\text{ASN2T}}]}{\log(1/\alpha)}\leq\lim_{\alpha\rightarrow0}\frac{\mathbb{E}[\tau^{(p)}]}{\log(1/\alpha)}. \end{align}\]

6.6 Technical lemmas↩︎

References↩︎