Fast and Regret Optimal Best Arm Identification: Fundamental Limits and Low-Complexity Algorithms
Authors: Qining Zhang
Lei Ying
Venue: NeurIPS 2023 poster (2023)
Keywords: stochastic multi-armed bandits
regret optimal best arm identification
commitment
TL;DR: We consider Regret Optimal Best Arm Identification with dual objectives: quick action commitment and regret minimization. We characterize its limits and propose the EOCP algorithms.

Abstract: This paper considers a stochastic Multi-Armed Bandit (MAB) problem with dual objectives: (i) quick identification and commitment to the optimal arm, and (ii) reward maximization throughout a sequence of $T$ consecutive rounds. Though each objective has been individually well-studied, i.e., best arm identification for (i) and regret minimization for (ii), the simultaneous realization of both objectives remains an open problem, despite its practical importance. This paper introduces \emph{Regret Optimal Best Arm Identification} (ROBAI) which aims to achieve these dual objectives. To solve ROBAI with both pre-determined stopping time and adaptive stopping time requirements, we present an algorithm called EOCP and its variants respectively, which not only achieve asymptotic optimal regret in both Gaussian and general bandits, but also commit to the optimal arm in $\mathcal{O}(\log T)$ rounds with pre-determined stopping time and $\mathcal{O}(\log^2 T)$ rounds with adaptive stopping time. We further characterize lower bounds on the commitment time (equivalent to the sample complexity) of ROBAI, showing that EOCP and its variants are sample optimal with pre-determined stopping time, and almost sample optimal with adaptive stopping time. Numerical results confirm our theoretical analysis and reveal an interesting ``over-exploration'' phenomenon carried by classic UCB algorithms, such that EOCP has smaller regret even though it stops exploration much earlier than UCB, i.e., $\mathcal{O}(\log T)$ versus $\mathcal{O}(T)$, which suggests over-exploration is unnecessary and potentially harmful to system performance.

Fast and Regret Optimal Best Arm Identification: Fundamental Limits and Low-Complexity Algorithms
Qining Zhang
Lei Ying University of Michigan, Ann Arbor leiyingdumich. edu
University of Michigan, Ann Arbor qiningz@umich.
Abstract
This paper considers stochastic Multi-Araa Bandit (MAB) problem with dual objectives: (i) quick identification and commitment to the optimal arm, and (ii) reward maximization throughout sequence of T consecutive rounds. Though each objective has been individually well-studied, i.e., best arm identification for (i) and regret minimization for (ii), the simultaneous realization of both objectives remains an open problem, despite its practical importance. This paper introduces Regret Optimal Best Arm Identification (ROBAI) which aims achieve these dual objectives. To solve ROBAI with both pre-determined stopping time and adaptive stopping time requirements, we present an algorithm called EOCP and its variants respectively, which not only achieve asymptotic optimal regret in both Gaussian and general bandits, but also commit to the optimal arm in Olog T') rounds with pre- determined stopping time and Ollog" T)) rounds with adaptive stopping time. We further characterize lower bounds on the commitment time (equivalent to the sample complexity) of ROBAL, showing that EOCP and its variants are sample optimal with pre-determined stopping time, and almost sample optimal with adaptive stopping time. Numerical results confirm our theoretical analysis and reveal an interesting "over-exploratioon phenomenon carried by classic UCB algorithms, such that EOCP has smaller regret even though it stops exploration much earlier than UCB, i.e., Olog I') versus O(T', which suggests over-exploration is unnecessary and potentially harmful to system performance.
Introduction
The stochastic Multi-Armed Bandit (MAB) problem [I] which models a wide range of applications including online recommendations 2 3 4 job assignments [5] 6 77, clinical trials [ 9 and etc. sequential decision-make
process between an agent and an environment which consists of number of arms (actions). In this paper, we will use "arm" and "action" interchangeably. Most
existing studies, say [10] [1 12 I3 14 [5], formulate regret minimization problem to study the bandit model, where the agent aims to maximize the cumulative reward through interacting with the environment for a number of consecutive rounds. The well-known UCB algorithm [TO] and its variants [12] are among the most popular bandit algorithms for regret minimization, which exhibit outstanding performances both theoretically and empirically in bandit models. Moreover, state-of- the-art reinforcement learning algorithms, e.g.. [1 17). also motivated by the essence of UCB which sets up confidence intervals to encourage exploration. However, the UCB algorithms do not commit to a single arm. Instead, they continue switch among all arms based reward signals received. Since one of the ultimate goals of the MAB model to learn the optimal arm, would be ideal if the algorithm would commit and in practice, a number of applications such as occupational decisions [18), medicine release and pandemic control [19 20 and long-term investments (21), require or prefer quick commitment an action instead of continuous exploration. This motivated us to consider an MAB problem with dual
quickly without sacrificing the regret. In fact
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Algorithm
Regret
Setting
Optimality
Commitment
Confidence
UCB 22
2+o(1]
log T
Gaussian
Yes
T
N/A
A 1+0(1)
KL-UCB 12
log
General
Yes
N/A
KL (
TS [15
A
log
General
Yes
N/A
(L
BAI-ETC 22
4+
log T
Gaussian
No
Ollog T)
O(T
A
DETC 23
2+0(1)
log T
Gaussian
Yes
2(log" 2 T)
O(T
UCB, 24
2a +o(l)
log T
Gaussian
No
Ollog T)
Ó(T
A
EOCP (Ours)
2 1+
log T
Gaussian
Yes
O T)
0 (T-1)
EOCP-UG (Ours)
2 2+0
log T
Gaussian
Yes
Ollo" T)
0 (TT))
KL-EOCP (Ours)
+
log T
General
Yes
O T)
(T7))
(B(rre-determined)
2+o(1)
log T
Gaussian
O (log" T)
(log T)
O(T-I)
A
LB(adaptive)
2+0(1)
log T
Gaussian
(log T)
Olog"--T)
O(T
[4 μ2) is the expected reward difference, KL (L) is the Kullback-Leibler divergence between reward distributions, and 1. EOCP and KL--OCCP use pre-determined stopping time and require the knowledge of A, while EOCP- UG uses an adaptive stopping time. Both LBs represent the commitment time lower bound under Gaussian bandits for regret optimal algorithms with Olog" '") finite-time regret violation and O(7-1) confidence.
Table I: Caparison under 2-armed bandits where A
objectives: (i) quick identification and commitment to the optimal arm, and (ii) minimization of the cumulative regret throughout sequence of rounds.
Regret Optimal Best Arm Identification: The lack of commitment in traditional regret minimization formulation motivates us propose new viewpoint towards online decision-making called Regret Optimal Best Arm Identification (ROBAI), which intends to manage two goals at the same time: minimizing regret while committing to an arm quickly. Specifically, commit to the optimal arm which has the highest expected reward while minimizing the exploration regret. To solve ROBAI, we need to answer three fundamental questions: (I) how should the learner explore arms while maintaining low-regret performance (exploration strategy)? ? (2) when should the learner stop exploration and commit to an arm (stopping criterion)? and (3) which arm to commit to when the exploration ends (action selection strategy)? All three components need to be designed together to make the algorithm most efficient. The fundamental question this paper addresses is: Can we design an efficient algorithm that is both regret optimal and identifies the optimal arm quickly, and what are the fundamental limits of such algorithms?
ideal for the agent to quickly
One approach people may take to solve ROBAI is the Best Arm Identification (BAI) algorithm, which studies how learn the optimal arm with the minimum number of samples (rounds) and then commit to the selected arm. However, since BAI focuses purely on sample complexity (or commitment time), the algorithms for BAI explore sub-optimal arms too aggressively and too often, leading to large regret. As shown in [22]. the regret is asymptotically least twice as large as the regret under the classic UCB algorithm. Modifications shown in [2] may lead to better regret performance, but they also make the algorithm too complicated to find the optimal arm quickly. Moreover, these algorithms adapted from BAI often exhibit poor empirical regret performances shown in our numerical experiments of Fig-
Connection to Best Arm Identification:
We propose an algorithm called EOCP, which stands for Explore Optimistically then Commit Pessimistically, to solve the ROBAI problem. It first uses an optimistic modified version of the classic UCB algorithm explore arms with slightly larger exploration function, and then it commits to the optimal arm candidate according to pessimistic LCB algorithm when the exploration ends, by selecting the arm that has the largest lower confidence bound. The exploration and action identification strategies are respectively motivated by the inflated bonus trick [4] and the
Our Contributions:
principle pessimism from the literature offline bandits [25 26 27 and offline reinforcement
Our greatest contributions include designing new stopping rules with both pre- determined stopping time (vanilla EOCP) and adaptive stopping time (the FOCP-UG variant), which probably balance the trade-off between regret minimization and action identification. We theoretically
learning [28 29 30

---

show that both algorithms are asymptotically regret optimal in Gaussian bandit models. Moreover, EOCP and EOCP-UG algorithms commit to the optimal arm in (log and (log" I") number of rounds respectively, both with O(T"1) confidence. We further characterize the fundamental commitment time (sample complexity until commitment) limits of action identification for regret optimal algorithms, which shows that (log T) number of samples always required with pre- determined stopping time, and ((oo2--TT) T) number of samples is required with adaptive stopping time if the finite-time regret of the algorithm does not exceed its asymptotic regret rate by O(log" T). This shows that EOCP sample optimal and EOCP-UG is nearly sample optimal. We also propose an improved algorithm called KL-EOCP to achieve regret optimality in general bandits beyond Gaussian rewards. To the best of our knowledge, KL-EOCP the first algorithm that not only achieves asymptotic regret optimality in general bandit models but also commits to the optimal arm in O (log T') rounds, which also matches the commitment time lower bound. The more detailed comparison between existing algorithms and our proposed algorithms with lower bounds is summarized in Tab, Numerical experiments confirm the superiority of our proposed algorithm and show an interesting "over-exploration" phenomenon carried by UCB algorithms. As shown in Fig. [ our EOCP algorithm reduces more than 20% of regret compared to the vanilla UCB algorithm by finding and committing to the optimal arm early.
2 Preliminaries
Stochastic Multi-armed Bandits: A stochastic multi-armed bandit problem is an online decision- making process between an agent and an environment for number of T consecutive rounds. At each round t E {1, 2.. ,T, the agent can choose an action A, among a set of actions (arms) with cardinality A, denoted by A [1,2 A), interact with the environment. Each action is associated with a probability distribution Va and we denote the set of distributions as = fVi....,. ,VA) with respective expectations μ1 {Mz.... HAA] which unknown to the agent priori. The expectations are assumed to be bounded so without loss of generality, we have Ma E [0. 1] for any action a. After the agent chooses an action, say action A, at round t, it will observe an independent reward r, which is sampled from the distribution VA, associated with the action A, that it chooses. We define the optimal action a* to be the action which has the highest expected reward, i.e., Na* arg A Mas and for simplicity, we assume it is unique. Let A. 1/4** Hal (0, 1] to be the expected reward gap between the optimal action and sub-optimal action a. and we use A min min.::..00 |Ma Mal to denote the minimum reward gap among all sub-optimal actions.
Regret: The goal of the agent is to maximize the expected cumulative reward from the total T rounds of interactions with the environment, i.e., to maximize E[r; + 72 ...... + rrl, where the expectation taken over all randomness. The performance of any bandit algorithm Alg chosen by the agent is usually measured by the cumulative Regret up to round T defined as follows:
T Σ
Als (T) = T # E, Reg
Ft
where the subscript μ denotes the bandit instance represented by the reward expectations. Maximizing reward is equivalent to minimizing the cumulative regret. For most of the algorithms to achieve this goal, the agent will make action-choosing decisions based on two statistics maintained and updated at each round for every action: the empirical mean Fa(a) and the number of pulls Nz(a) in previous rounds. They are defined as:
(i)a) Σ LA
P((a)
A.AA
Ni(a)
The theoretical regret limit of any algorithm Alg is studied and characterized in 13 which shows:
Reg Als
Σ A
lim inf
(I)
T-
log
KL(Vo, Va*)
a. 50
where KL denotes the Kullback-Leibler divergence between two distributions. We call an algorithm Alg regret optimal (asymptotically) the asymptotic regret performance of Alg achieves this lower bound. Therefore, whether algorithm is asymptotically regret optimal will depend on
3

---

the distributions of the rewards. Specifically, for Gaussian bandits, the KL divergence between distributions N (p 1) and Wi 1) is simply (14- - Pa So the asymptotic regret rate lower bound in the RHS for Gaussian bandits would be 2 2 __a A.
Commitment: In ROBAI, commitment to single action (ideally, the optimal action) is required. After stopping time Te. the agent will not be allowed to switch actions and will commit to the same action until the end. We consider two categories of commitment: the pre-determined stopping-time setting and the adaptive stopping time setting. The pre-determined stopping time requires Te to be pre-specified before the first round of interaction, while the adaptive stopping criterion requires Te to be a stopping time measurable to the natural filtration. How quickly the agent commits is measured by the Sample Complexity until Commitment (also called commitment time) which the expected number of exploration rounds, i.e., SCC (T) [T[TT]. The accuracy of identifying the optimal action is measured by the confidence, which is the probability that the agent commits to sub-optimal action, i.e., (á * a²). An ideal algorithm should minimize the commitment time while maintaining confidence lower than pre-specified threshold.
ROBAI Problem Formulation: We use URo to denote the class of regret optimal algorithms which commit to the optimal action with a confidence lower than (TT i.e.,
Regya
Ale (T)
KL(Va, Uan) and pa of a*) O (T)))-
An
RRO
Alg
lim sup T-200
log T
a:A.>0
ROBAI aims to design a regret optimal algorithm Alg e IRRO minimize the commitment time:
[Ty))E,[TT] s.t., Alg IRO- min SCC 14
3
Low-Complexity Algorithms
In this section, we propose a low-complexity algorithm called EOCP with a pre-determined stopping time solve ROBAI. Then, propose variant called EOCP-UG with adaptive stopping time.
3.1 The Pre-determined Stopping Time Setting
The pre-determined stopping time setting is motivated by real-world applications such as A/B tests in medical experiments with operational or budget limits [31] where the number of testers is usually pre- designed and determined before the experiment starts. Therefore, we require the agent to pre-specify the stopping time Te before the first round. We also assume the algorithm knows strictly positive lower bound Åb on the minimum reward gap Amiu between the optimal action and sub-optimal actions.
We propose our EOCP algorithm in Algorithm.
Algorithm EOCP with Pre-determined Stopping Time
Require: Exploration function I; Lower bound Alb minimum reward gap. 8.41 + A be the pre-determined stopping time.
1: Let T
Ai
2: Initialize by pulling each arm once.
3: for t = A + 1: T do
4: Set uncertainty bonus b(-1(0)= = V (aj and UCB = F + ba))
5: Take action A, arg max, UCB.-1(a). // UCB Exploration
6: end for
7: Set bonus by. (a) =
21 and LCBr, (a) = Fr. (a) - br, (a). (o)
8: t [Te + 1,7]. commit to action à arg max, LCBT. (a). // LCB Commitment
In EOCP, the agent will spend the first rounds exploring each arm once as start. Our choice of exploration strategy is modified version of the classic UCB algorithm where the agent will choose the action with the largest upper confidence bound in terms of empirical reward. The exploration function / controls the intensity of exploration to achieve the optimal trade-off between reducing uncertainty for action identification and minimizing regret. After the pre-determined stopping time Te, the agent will commit to an action that has the largest lower confidence bound of empirical

---

reward. This LCB commitment strategy is inspired by the principle of pessimism from the literature
of offline learning 25 26 27 28
29 30], where the empirical reward of each action penalized by the amount of uncertainty to combat the imbalanced data coverage of actions in the offline dataset. also shown that the pessimistic principle works well when the data coverage concentrated on the optimal action, i.e., the optimal action has the largest number of pulls. This trait of the LCB algorithm matches the trait of UCB exploration, in which the optimal action will be chosen much more often than sub-optimal actions in exploration. So by designing such proper To. we will be able to achieve the best of both worlds: a low-regret exploration of the UCB algorithm, and a fast best arm identification through the choice of LCB algorithm.
3.2 The Adaptive Stopping Time Setting
In this setting, we do not assume the algorithm is provided a priori with additional information on the lower bound An on the minimum reward gap, so there is no hope of designing pre-determined stopping time. Instead, we design our stopping criterion based on the samples collected from the explorations, which leads to the fact that Te is stopping time measurable to the natural filtration. We propose our EOCP-UG algorithm in Algorithm corresponding to an unknown gap.
Algorithm 2 EOCP-UG with Adaptive Stopping Time
Require: Exploration function I. 1: Initialize by pulling each arm once.
2: while max, mina N (a) IN, (a') & do
3: Set uncertainty bonus b (a) Naji UCB,-i = it-((a) + by ba))
20
4: Take action A, arg maxa UCB,-1 // UCB Exploration
5: end while
6: Let To + t - 1, bonus (a) = V Nr. laj and LCBT, (a) = FT, (T. - bT. (a).
7: For t E [Te + 1, 1. commit to the action arg max, LCBr,(a). L/BBB Commitment
In EOCP-UG, we use the same UCB exploration and LCB best action identification strategies as in the pre-determined stopping time setting. The only difference compared to EOCP comes from the new stopping rule based on the number of pulls N₂(a) for each action. Specifically, the exploration ends if there is an imbalanced fraction of Na(a) among all actions, that is, one action has / times more pulls than all other actions in previous rounds. Here, is the exploration function and we will select / be slightly larger than log T in later sections. The intuition of such a stopping criterion comes from the characteristics of UCB exploration, i.e., as round f increases, the algorithm will slowly adapt to choosing the optimal action more often. When the fraction between the number of pulls for the optimal action and any sub-optimal action is large enough, the optimal action will be identifiable. Note that in action identification, we can simply choose the action that has the largest number of pulls Nr. (a) when we stop, and obtain exactly the same performance guarantees. However, to keep it consistent with the pre-determined stopping time setting, we use the LCB commitment.
4 Main Results
In this section, assume the distributions (u,,-.. "....,,,) MA) come from a Gaussian family, where Va associated with action a follows a Gaussian distribution with mean μa and unit variance, i.c., Va ~N(H,, 1). The results in this section can be easily generalized to sub-Gaussian distributions. The key idea towards the optimal trade-off between controlling regret and identifying the optimal action is inspired by the inflated bonus trick from (24), where will choose the exploration function I to be slightly larger than the log T used in vanilla UCB algorithms to encourage more exploration of sub-optimal arms, i.e., we will select = log T OVTooTT)
4.1 Regret Optimality for Gaussian Bandits with Pre- Pre-Determined Stopping Time
In Theorem. [
we present the theoretical regret performance guarantee of the EOCP algorithm:
5

---

Theorem Ler = log(T) O Vlo T) and when T is large enough, the expected regret of the with pre-determined stopping time can be upper- by:
EOCP algorithm in Algorithm. 7
2log
O Vlog?"
Regu
EOCP (T)
Σ
A
Amin
0:Aa20
direct asymptotic bound can be obtained from Theorem, T i.e.
Reg
EOCP (T)
lim sup
Σ
T-
log T
a:A_>0
Aa
Comparing it to Eq. [ clear that EOCP asymptotically regret optimal in Gaussian bandits. The commitment time and confidence guarantees can be extracted from the setup of Algorithm. itself and the proof of Theorem. [ Recall that Algorithm, [ we pre-determined the length of exploration To to be O(A The following corollary characterizes these parts of theoretical performance:
Corollary Let = log(T) + O(ylog 7), the expected commitment time for EOCP in Algorithm. / given by
SCCEOCP (T) O0 log T),
1
and the confidence level is O(T
The complete proofs of Theorem. and Corollary. T Jre provided in the supplementary material. In order to upper bound the cumulative regret of T rounds, we divide the total regret into the regret accumulated in exploration and the regret accumulated in commitment.
To bound the regret accumulated exploration and since we use variant of UCB exploration, we follow the standard procedure of proofs for UCB algorithms, e.g. proof of Theorem 8 from. [22]. Then, this procedure results in an order (1) dominating regret term, which is Oloog 7) by the choice of our exploration function. Through carefully applying any-time concentration inequalities, we are able to show that the constant in front of this dominating regret term is exactly the constant we obtained in Theorem. [
Bounding Regret from Exploration:
Bounding Regret from Committing the Wrong Action: As for the regret accumulated from commitment, the key is to prove the O(T-1) confidence level upper bound presented in Corollary, We follow a procedure similar to the proof of Theorem 1 in [2] utilize the adaptivity of UCB exploration and the pessimistic LCB commitment. We first show that with high probability. the number of pulls Na(a) for any sub-optimal actions the exploration phase is upper-bounded. This because after certain number of pulls, the uncertainty bonus b (a) for any sub-optimal action will be so small that the upper confidence bound UCB,-I(a) cannot be larger than Mas, thus less than the upper confidence bound of the optimal action. Therefore, sub-optimal actions will not be chosen in future rounds. After our carefully designed Te, we make sure that the optimal action has the largest number of pulls Nr. (a) among all actions, thus its bonus is so small so that its lower confidence bound L LCBr. (a*) larger than the expectations Pa any sub-optimal action a, and thus larger than the lower confidence bound of other actions. So with high probability, we will commit to the optimal action. Then, the O confidence level will provide us with a constant regret in commitment, and the overall dominating regret comes from exploration.
Combining both bounds, we are able to show the regret performance upper bound in Theorem, [
4.2 Regret Optimality for Gaussian Bandits with Adaptive Stopping Time
We present the regret performance of EOCP-UG in Theorem. 2 Compared to Theorem. I EOCP-UG has exactly the same regret performance guarantees as EOCP even without the knowledge of lower bound AT on the minimum reward gap. This implies that EOCP-UG adapts to the reward gap.
Theorem 2 Les = log(T) O( log T) and when T is large enough, the expected regret of the EOCP-UG algorithm in Algorithm. with adaptive stopping time is upper-bounded by:
2og
VlogT'
Reg
EOCP.
&
Σ
A
Amin
A
a:

---

We can also directly derive an asymptotic regret bound which shows that EOCP-UG is regret optimal in Gaussian bandits:
Reg
EOCE-UGG
UGPP-UGGT (T)
lim sup
T-200
log T
2:
A
With adaptive stopping. the sample complexity until the commitment not a pre-determined value. However, we can still extract similar guarantees along with the confidence level from the proof of Theorem. We present these results in the following corollary:
Corollary Let = (T) + Dlylog" T), the sample complexity until commitment EOCP-UG algorithm in Algorithm, upper-bounded by:
8log T
log n T A min
SCC (T)
+
O
A7
a:
and the confulence level is upper bounded by O(T-1).
The complete proofs of Theorem. 2 and Corollary 2 are provided in the supplemen- tary material. Compared to the proof of Theorem. [] the major difference lies bounding the regret of commitment. Similarly, we are required to bound the probability of committing to sub-optimal action. We first show that when the agent stops exploration according Line 2 of Algorithm, 2 the action that has the maximum number of pulls is the optimal action with high probability. Then, we show that under this event we will commit to the optimal action if we use LCB commitment.
Proof Roadmap:
Magic Choice of Exploration Function: Bounding the regret in both exploration and commitment requires a delicate analysis with any time concentration inequalities. Our choice of exploration function / plays an important role which manages the trade-off between low-regret exploration and high-probability optimal action commitment. If the exploration function is too large, i.e., if I = 2 log T. the regret in exploration will not be optimal. If the exploration function is too small, i.e., if log T, the probability of committing to the wrong action can not be bounded by O(T-1), magic choice of exploration function I achieves the best of both worlds.
).. Our
Loss of SCC from Unknown Gap: Even though we have the same regret performance, the guarantee for commitment time is Olog T)) which is worse than Olog 7') in the pre-determined setting, So, this order fundamental with adaptive stopping time? In the next section, we provide the answer by investigating the theoretical limits of commitment time for asymptotic regret optimal algorithms.
4.3 Fundamental Limits of Sample Complexity until Commitment
In order answer the question regarding the fundamental sample complexity until commitment for regret optimal algorithms with both pre-determined and adaptive stopping times, we consider simplified Gaussian bandit model where there are only 2 arms. The reward gap between the two actions is A, so Amin = A. From Eq. (I), it is clear that the optimal regret of any algorithm is asymptotically 2A 11 log(T)) so the set of all regret optimal algorithms is characterized by:
Reg Alg (
and P (á a²) a=)=
IRo = Alg lim sup
T-
log T
A
Furthermore, for each regret optimal algorithm, we say it has c-logarithm regret violation if there exists constant E (0. 1) (choose the minimum if there exists multiple) such that the following inequality is satisfied when T is large enough:
Reg Alg (T) 2 log(T) (log T).
A
If an algorithm has c-logarithm regret violation, the largest additional lower order term in its finite- time regret bound should be Ollog On the other hand, it also characterizes the convergence rate of the regret to its asymptote. For example, the vanilla UCB algorithm has at most 1/2-logarithm regret violation, and our EOCP and EOCP-UG algorithms both have at most 1/2-logarithm regret violation 22 Theorem. 8). We then provide the following theorem to characterize the fundamental commitment time limits for algorithms in IIRo:
7

---

Theorem (Information- Theoretic Limits of SCC) Consider a 2-armed Gaussian bandits, for any asymptotically regret optimal algorithm Alg which has c-logarithm regret violation, in order to guarantee ( confidence level, the sample complexity until commitment with pre-determined stopping time is lower bounded by
= TM -2 log(T)),
and with adaptive stopping time, the sample complexity until commilment is lower-bounded by:
E = 22 log 1og2 (T)).
The proof is provided in the supplementary material. The proof idea relies on the well-known "transportation" lemma [2] Lemma. I] originally derived to prove the theoretical limits of best arm identification algorithms. This lemma characterizes the expected number of pulls for each action by hypothesis testing between the original bandit problem and another bandit instance with a different optimal action. Then by finding a proper bandit instance and combining the lemma with regret optimal algorithms, we will be able to prove Theorem. 3 for both settings.
Proof Roadmap:
Sample Optimality: It is shown by Corollary. | and Theorem. (rroree.,ttogehher that our proposed EOCP algorithm achieves the optimal commitment time with Ollog 7') with pre-determined stopping time if the reward gap A is known a priori. However, with adaptive stopping time, our EOCP-UG algorithm has 1/2-logarithm regret violation and O(log"
2 T) commitment time which is larger than
the Oloog 1.5 T) lower bound indicated by Theorem. 3 Even though EOCP-UG is not shown to be exactly sample optimal, we conjure that the performance gap comes from our analysis techniques which makes one of the bounds (maybe both) not tight. Whether EOCP-UG is indeed sample optimal, and if not, how to design regret optimal algorithms with Ollog" .5 T) commitment time remains open.
Regret Optimality for General Bandits
Even though EOCP is applicable in sub-Gaussian bandits, it is not regret optimal any more heyond Gaussian bandits. This can be seen by comparing Theorem, [ [andd the fundamental regret limit (I with Pinsker's incquality, and it is clear that the lower bound is smaller than our upper bound asymptotically beyond Gaussian bandits. To close this gap, we propose an improved algorithm called KL-EOCP which is provably regret optimal in general bandits.
Natural Exponential Family: We assume the reward distributions of each action belong a natural exponential family, i.e.. P = ((va)ee / dc = exp @r b(0) h x)), where Q c R is the set of all parameters such that the expectation f positive and bounded, i.e., ! E [0. 1]. E some reference measure on R and b θ - R is convex twice differentiable function. This distribution vo can also be parameterized by its expectation 1 = 1/ (0), the derivative b6.), and for every l we denote by n" the unique distribution in P with expectation μ and by 0² its corresponding parameter. Gaussian distribution with unit variance is an example of this family. Moreover, the Kullback-Leible divergence from ve, va, (with a little abuse of notation) can be expressed as [12]
(L (22 = KL vo.) = b(02) - b(8)) (((0)) 01).
The set of exponential family bandit models v (va.. ... vra)) can be characterized by the expectations of the actions = (H), MA). We assume for all A E R, and E θ the moment generating function Myg (A) E., [exp(AW)) for the distribution ve well-defined and is finite.
Algorithm: Analog to Åb in Algorithm. [ the KL-EOCP algorithm requires the knowledge of strictly positive lower bound KL on the "minimum KL divergence", denoted as KL which captures the minimum reward distribution gap (distance) between the optimal action and any sub- optimal action. Considering the asymmetricity of the KI. divergence, we define KL as follows:
KL
min min (KL(Ha, pa*). (KL(H'ss 0
where 14, (Day pa*) such that 4KL(1's (a*)) )- = KL (ax)). The term 4KL( (aa) reflects the skew of KL divergence when the two distributions are switched. A simple lower bound to KLmin can be easily computed given lower bound An on the minimum reward gap Amin with the expression of the exponential family, while our KL-EOCP algorithm can operate with any lower bound KL
8

---

The KL-EOCP algorithm is summarized in Algorithm. 3 It designs the UCB and LCB bonuses based on the KL divergence of the reward distributions for all actions. general, these designs would lead to smaller confidence intervals with the same ( concentration guarantees as first adopted in the KI.UCBB algorithm proposed in 12]. If the lower bound information KL not known priori, we can combine Algorithm. 3 with the adaptive stopping time of EOCP-UG to deal with this setting.
Algorithm 3 KL-EOCP with Pre- Fre-Determined Stopping Time
Require: Exploration function Lower bound KL on the minimum KL divergence.
4.4L + A be the length of the exploration phase. 1: Let T. KL
2: Initialize by pulling each arm once.
3: for ( = A + 1: To do
4: Set upper confidence bound:
UCB.-1(a) arg max (N=-1a)KL((=-1(00, E (3))-1(a)
5: Take action A, arg max, UCB;-1(a). // UCB Exploration
6: end for
7: Set lower confidence bound:
LCBT,()) arg min (Nr, (a)KL((T, (a). < JeE
8: For E [Te + 1, 1,7,, commit to action à max, LCBT, (n). // LCB Commitment
Regret Optimality in General Bandits: The theoretical regret performance of the KL-EOCP is summarized in the following Theorem. To the best of our knowledge, is the first result achieving asymptotic regret optimality in general bandit problems with commitment.
Theorem Let = log(T) + O(Vlog T), when T is large enough and the reward distributions v of each action belong to the same natural exponential family, the expected regret of KL-BOCP in Algorithm. 3 is upper-bon bounded by:
A. logo
log T
Reg p (T) &
Σ
+
KL m1)
KLmin
Therefore, is clear that we can derive an asymptotic upper bound as follows:
Reg (T) log T
A
lipsup T-
Σ a:A.>0
(L((a,
which exactly matches the regret limit in Eq. ①1. The complete proof of Theorem. 4 is provided in the supplementary materials. Even though the proof roadmap is similar to the proof of Theorem, [ the major difference comes from the use of a tighter concentration lemma modified from (12
Theorem. 1 I] which captures the low probability event when the KL divergence of the empirical mean is far away from its expectation. The sample complexity until commitment and confidence level guarantees can also be extracted from the proof. Specifically, SCCKL-EOCP (T") O(KL log and the confidence level upper bounded by O(T-1).
Numerical Experiments
In this section, we study the empirical performance of our proposed EOCP algorithm with variants compared to existing algorithms in the literature, including BAI-ETC (2), UCB [10), KL-UCB [[2] and DETC [23 both Gaussian and Bernoulli bandit settings. In this section, we only test algorithms on two-armed bandit problem because some baselines are only applicable in two-armed settings. The performance of our algorithms in bandit models with multiple arms is demonstrated in
Appendix. E In the Gaussian setting, test all the algorithms with distributions N(s, for arm

---

60
ECCP KLUEOOP
50
UCB
40
Regre
Regrel
30
00
BDGP
DO37-00 45
US3
10 10
10
10
10
10
Number of Rounds
Number Rounds
(a) Gaussian Bandits
(b) Bernoulli Bandits
Figure 1: Comparison of regret performance of EOCP with variants and existing algorithms in the literature. The gap A between the two 0.5 and results are averaged over 10 iterations.
i 1,2 with a total of 10 rounds, and the Bernoulli bandit setting, we test the algorithms with distribution Ber( for arm i = 1,2 with a total of 10 rounds. We set /41 0.7 and /12 0.2, so the gap between the arms is A = 0.5. The results are averaged over 10 iterations and in Fig. 1
In the Gaussian bandit setting, it shows that both BAI-ETC and DETC algorithms exhibit unsatisfac- torily high regret. On the contrary, our proposed algorithms EOCP and EOCP-UG have lower final regret even compared to the popular UCB algorithm, surprisingly. Even though our algorithms use larger exploration function than the vanilla UCB algorithm, and accumulate regret more quickly in exploration, i.e., approximately the first 1000 rounds, it allows to commit to the optimal action. Our algorithms almost find the optimal action in all simulated traces which gives rise to the very slowly-increasing behavior of regret in the commitment phase. This phenomenon coincides with our theoretical analysis which shows that the regret in commitment is O(1). However, the UCB algorithm continues explore sub-optimal actions, its regret continues to grow when the EOCP algorithm has already committed to the optimal action. Numerically, the EOCP algorithm reduces 20% of the final regret compared to UCB through early commitment, and conjure that preventing the "over-exploration" phenomenon of the UCB algorithm is behind the reason for such empirical regret reduction. Comparing the commitment time of EOCP-UG and EOCP, algorithms stop exploration at approximately 1000 rounds. This means that not knowing the gap information won't 't harm the empirical sample complexity until commitment too much, which in turn may imply that our theoretical analysis of commitment time upper bound in Corollary. not tight enough. The same trend can be witnessed in the results of the Bernoulli bandits. However, in Bernoulli bandits, KI-UUB and KL-FOCP algorithms have a much better regret performance than other algorithms, which shows that knowledge of the reward distribution family improves the performance significantly.
see that both
7 Conclusion
We studied ROBAI which intends both minimize regret and commit to the optimal action. We proposed EOCP with variants, which combine UCB exploration and LCB commitment with novel stopping criteria in both pre-determined and adaptive settings. We showed that both EOCP and EOCP. UG are regret asymptotic optimal in Gaussian bandits with Ollog T) and Olog" T) commitment time respectively, almost matching the theoretical limits we derived. For general bandits, we proposed KL-EOCP which is provably regret optimal. Numerical experiments confirmed the superiority of our algorithms and revealed the "over-exploration" phenomenon of UCB algorithms.
Acknowledgments and Disclosure of Funding
The work of Qining Zhang and Lei Ying supported in part by NSF under grants 2112471, 2134081, 2207548, and 222897.
10

---

References
[1] William R Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3-4):285-294, 1933.
[2] Zixian Yang, Xin Liu, and Lei Ying. Exploration. exploitation, and engagement in aulli bandits with abandonment. In 2022 58th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 1-2, 2022.
[3] Pushmeet Kohli, Mahyar Salek, and Greg Stoddard. A fast bandit algorithm for recommenda- tion to users with heterogenous tastes. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 27, pages 1135-1141, 2013.
[4] Chunqiu Zeng, Qing Wang, Shekoofeh Mokhtari, and Tao Li. Online context-aware recom- mendation with time varying multi- multi-armed bandit. In Proceedings of the 22nd ACM SIGKDD international conference Knowledge discovery and data mining, pages 2025-2034, 2016.
[5] Xin Liu, Bin Li, Pengyi Shi, and Lei Ying. Pond: Pessimistic-optimisticc online dispatching. arXiv preprint arXiv:20/0.09995, 2020.
[6] Jiatai Huang, Leana Golubchik, and Longbo Huang. Queue scheduling with adversarial handit learning. arXiv preprint 2rXiv:2303.01745. 2023.
[7] Zixian Yang. R Srikant, and Lei Ying. Maxweight with discounted ucb: A provably stable scheduling policy for nonstationary multi-server systems with unknown statistics. arXiv preprint arXiv:2209.01 126, 2022.
[8] Soffa S Villar, Jack Bowden, and James Wason. Multi-armed bandit models for the optimal design of clinical trials: benefits and challenges. Statistical science: a review journal of the Institute of Matemattcal Statistics, 30(2):199, 2015.
[9] Maryam Aziz, Emilie Kaufmann, and Marie-Karelle Riviere. On multi-armed bandit designs for dose-finding clinical trials. The Journal of Machine Learning Research, 22(1):686-723, 2021.
[10] Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47:235-256, 2002.
[11] Shipra Agrawal and Navin Goyal. Analysis of thompson sampling for the multi-armed bandit problem. In Conference on learning theory, pages 39-1. JMLR Workshop and Conference Proceedings, 2012.
[12] Aurélien Garivier and Olivier Cappé. The kl-ueb algorithm for bounded stochastic bandits and beyond. Proceedings of the 24th annual conference on learning theory, pages 359-376. JMLR Workshop and Conference Proceedings, 2011.
[13] Tze Leung Lai, Herbert Robbins, et al. Asymptotically efficient adaptive allocation rules. Advances applied mathematies, 6(1):4 22, 1985.
[14] Michael N Katehakis and Herbert Robbins. Sequential choice from several populations. Pro- ceedings of the National Academy of Sciences, 92(19):8584 8585, 1995.
[15] Emilie Kaufmann, Nathaniel Korda, and Rémi Munos. Thompson sampling: An asymptotically optimal finite-time analysis. In Algorithmic Learning Theory: 23rd International Conference, ALT 2012, Lyon, France, October 29-31, 2012. Proceedings 23, pages 199-213. Springer, 2012.
[16] Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforcement learning. In International Conference on Machine Learning, pages 263-272. PMLR, 2017.
[17] Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael Jordan. Is q-lamrning provably efficient? Advances in neural information processing systems, 31, 2018
[18] Susan D Phillips, Nicholas Pazienza, and Donna Walsh. Decision making styles and progress in occupational decision making. Journal of Vocational Behavior, 25(1):96-105, 1984.
11

---

[19] TJJOPS Higuchi. Mechanism of sustained action medication. theoretical analysis of rate of release of solid drugs dispersed in solid matrices. Journal of pharmaceutical sciences, 52(12):1145-1144 1963.
[20] Qining Zhang, Honghao Wei, Weina Wang, and Lei Ying. On low-complexity quickest in- tervention of mutated diffusion processes through local approximation. In Proceedings of the Twenty-Thire Third International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing, pages 141-150, 2022.
[21] Jeremy J Siegel. Stocks for the long run: The definitive guide to financial market returns & long-term investment strategies. McGraw-Hill Education, 2021.
[22] Aurélien Garivier, Tor Lattimore, and Emilie Kaufmann. On explore-then-commit strategies. Advances in Neural Information Processing Systems, 29, 2016.
[23] Tianyuan Jin, Pan Xu, Xiaokui Xiao, and Quanquan Gu. Double totic optimality and beyond. In Conference on Learning Theory, pages 2584-2633. PMLR, 2021.
Asymp-
[24] Rémy Degenne, Thomas Nedelec, Clément Calauzènes, and Vianney Perchet. Bridging the gap between regret minimization and best arm identification, with application to a/b tests. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1988-1996. PMLR, 2019.
[25] Paria Rashidinejad, Banghua Zhu, Cong Ma. Jiantao Jiao, and Stuart Russell. Bridging offline reinforcement learning and imitation learning: A tale of pessimism. Advances in Neural Information Processing Systems, 34:1 11:11700-11716, 2021.
[26] Gen Li, Cong Ma, and Nathan Srebro. Pessimism for offline linear contextual bandits using lp confidence sets. arXiv preprint arXiv:2205. 10671, 2022.
[27] Chenjun Xiao, Yifan Wu, Jincheng Mei, Bo Dai, Tor Lattimore, Lihong Li, Csaba Szepes- vari, and Dale Schuurmans. On the optimality of batch policy optimization algorithms. In International Conference on Machine Learning, pages 11362-112 11371. PMLR, 2021.
[28] Gen Li, Laixi Shi, Yuxin Chen, Yuejie Chi, and Yuting Wei. Settling the sample complexity of model-based offline reinforcement learning. arXiv preprint arXiv:2204.05275. 2022.
[29] Laixi Shi, Gen Li, Yuting Wei, Yuxin Chen, and Yuejie Chi. Pessimistic q-learning for offline reinforcement learning: Towards optimal sample complexity. arXiv preprint 13X9 2022.
[30] Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is pessimism provably efficient for offline ri? In International Conference on Machine Learning, pages 5084-5095 PMLR, 2021.
[31] Dan Siroker and Pete Koomen. A/B testing: The most powerful way to turn clicks into customers. John Wiley & Sons, 2015.
[32] Emilic Kaufmann, Olivier Cappé, and Aurélien Garivier. On the complexity of best arm identification in multi-armed bandit models. Journal of Machine Learning Research, 17:1 -2:1-42, 2016.
[33] Emilie Kaufmann, Olivier Cappé, and Aurélien Garivier. On bayesian upper confidence bounds for bandit problems. In Artificial intelligence and statistics, pages 592-600. PMLR, 2012.
[34] Daniel J Russo, Benjamin Van Roy, Abbas Kazerouni, Ian Osband, Zheng Wen, et al. A tutorial on thompson sampling. Foundations and Trends@ in Machine Learning, 11(1):1-96, 2018.
[35] Daniel Russo and Benjamin Van Roy. An informattion-theoreticc analysis of thompson sampling. The Journal of Machine Learning Research, 17(1 (7(1):24422241, 2016.
[36] Aurélien Garivier and Emilie Kaufmann. Optimal best arm identification with fixed confidence. In Conference on Learning Theory, pages 998-1027. PMLR, 2016.
12

---

[37] Rayadurgam Srikant and Lei Ying. Communication networks: an optimization, control, and stochastic networks perspective. Cambridge University Press, 2013.
[38] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020,
[39] Guanyu Nic, Mridul Agarwal, Abhishek Kumar Umrawal, Vancet Aggarwal, and Christo- pher John Quinn. An explore-then-commit algorithm for submodular maximization under full-bandit feedback. In Uncertainty in Artificial Intelligence, pages 1 1541-1551. PMLR, 2022.
[40] Ali Yekkehkhany, Ebrahim Arian, Mohammad Hajiesmaili, and Rakesh Nagi. Risk-averse explore-then-commit algorithms for finite-time bandits. In 2019 IEEE 58th Conference on Decision and Control (CDC), pages 8441-8446. IEEE, 2019.
[41] Ali Yekkehkhany, Ebrahim Arian, Rakesh Nagi. and Ilan Shomorony. A cost-basee based analysis for risk-averse explore-then-comee time bandits. IISE Transactions, 53(10))1094-1111 2021.
[42] Eyal Even-Dar, Shie Mannor, Yishay Mansour, and Sridhar Mahadevan. Action elimination and stopping conditions for the multi- bandit and reinforcement learning problems. Journal of machine learning research, 7(6), 2006.
13

---

A Related Works
In this section, we provide more detailed review of related works. We first review two classic problem formulations of the multi-armed bandit model: the regret minimization problem and the best arm identification problem. Then we review previous works on explore-then-commit algorithms which takes commitment into account. Finally, we review the offline stochastic bandit literature which motivated our choice of pessimistic principle in action identification.
A.1 Regret Minimization
The theoretical limits of regret minimization have been revealed by L3 14,, which shows that the expected regret of any algorithm is lower bounded when horizon T a'apprracchs infinity:
Reg Alg (T)
lim inf T -0
Σ a:Aa=0
log T
va*)
where KL(-.)) denotes the Kullback-eeibler divergence between two distributions. Based on the asymptotic lower bound, we say an algorithm is asymptotically regret optimal its regret performance achieves the regret lower bound asymptotically. Two sets of algorithms prevail in the regret mini- mization literature. One is the family of UCB algorithms [1O [2] [33. which reflects the principal of optimism in action selection to encourage exploration. To be specific, the UCB algorithms will select the action which has the largest upper confidence bound of reward estimation. This upper confidence bound represents the highest possible expected reward given the samples collected from previous rounds under a high probability event. Usually the additional bonus from the empirical mean to the upper confidence bound for specific action decreases as the number of pulls increases. Therefore, actions which have not been tried frequently in previous rounds will have larger bonus. This trait encourages exploration. By designing the bonus carefully, one can find the optimal trade-off between exploration and exploitation. The other set of prevailing algorithms
the family of Thompson Sampling Algorithms [T 34 11 [13 (35. The TS algorithm assumes each action is associated with posterior distribution given the reward feedback from previous rounds. Then the agent will collect one virtual sample from each posterior distribution and choose the action which has the largest virtual sample. As the number of pulls grows, the posterior distribution will be more and more concentrated around the expectation hand, the remaining randomness encourages exploration of other under-explored actions. However, both algorithms do not commit to single action because their action selection policies have to be re-evaluated at each round based on new observations.
the virtual sample will also be closer its expectation. On the other
A.2 Best Arm Identification
The best arm identification algorithms consist of three components: action sampling rule deciding which action to choose at each round, a stopping rule deciding a time T to stop collecting new samples, and a decision rule which outputs best action candidate à. We call an algorithm d-PAC the probability of outputting a sub-optimal action is less than 6, i..., Py.(a * 1) & 8. Here, is also called the confidence level. The performance of best arm identification algorithms is measured by both the sample complexity until identifying the optimal action and the confidence level. The theoretical limits for best arm identification algorithms that any 5-PAC algorithm would incur at least Ollog 5-1) sample complexity asymptotically. The constant in front of the logarithmic term depends on the bandit instance, i.c., the reward expectation and distribution of every action. Based on the this lower bound, the authors of (36) proposed the Track and Stop (TAS) algorithm which proved be asymptotic optimal if the distribution associated with each action is from single parameter natural exponential family. The TAS algorithm estimates the expectation of each action and at the same time calculates the optimal proportion of pulls for each action so that the optimal action is identifiable from the sub-optimal ones. Then, it designs a feedback control dynamic to track this proportion, similar to the Max-weight dynamic in queueing systems [37]. The stopping criterion of TAS is based on a generalized likelihood test. When the optimal action is identifiable from sub-optimal ones, the optimal action candidate chosen to be the action which has the largest empirical reward mean.
also well studied in (36 32 which shows
14

---

A.3 Explore-Theme Then-Commit Algorithms
natural bridge between regret minimization and best arm identification problems, which also takes into account action commitment, is the xxpore-then-comee algorithms [8 22
23
39 40)
41] Researchhss have long been hoping that such algorithms will achieve the best of both worlds: maintaining low regret and identifying the optimal action quickly. In these algorithms, clear separation of exploration phase and exploitation phase exists. At each round, the agent will only make action selection decisions based on the samples collected from the exploration phase, and commitment to a single action during the exploitation phase is required. No samples from the exploitation phase can be utilized although the agent may determine the length of both phases. It clear that explore-then-comme algorithms, i.e., one would first run the best arm identification algorithm in the exploration phase, and then commit to the action à found by the algorithm. However, it is shown in [22 that these type of BAI-ETC algorithms essentially regret sub-optimal. To be specific, the regret lower bound of such algorithms is asymptotically twice as large as the upper bound of optimal regret minimization algorithms such UCB and Thompson Sampling even with careful tuning. A recent work (23) provides a double explore-then-commit algorithm called DETC which is shown to be asymptotically regret optimal. But the algorithm itself very complex and requires multiple stages of exploration and exploitation. This trait makes its sample complexity to identify the optimal action large, i.c., M(ogg T). Moreover, in empirical studies, the DETC algorithm incurs very large regret which is no match for the vanilla UCB algorithm. Another work [24] proposes an exploration algorithm with inflated UCB, which can be naturally adapted to an ETC algorithm. Even though the sample complexity is order optimal, i..., Olog T), the regret performance is essentially sub-optimal due to the inflation of UCB bonus.
algorithms can be easily designed from best arm identification
A.4 Offline Stochastic Bandits and Reinforcement Learning
Our action identification policy is inspired by the principle of pessimism widely adopted in offline stochastic bandit problems [26 27 25 and reinforcement learning problems [28] 30 29]. In offline bandit problems, the agent is not allowed to interact with the environment at will. Instead, it is provided with a training dataset which contains action and reward pairs collected from the same bandit problem. Based this dataset, the agent is asked to choose the optimal action. It is shown in (25) that greedily selecting the action with largest empirical mean would fail to produce the optimal action in some bandit problems. This failure results from the randomness of samples in the dataset and the imbalanced number of samples for each action. Instead, choosing the action with largest lower confidence bound to combat the imbalanced uncertainty between estimations of different actions leads to better performance as justified in (27 25). Similar to the UCB algorithm, the penalty term between the empirical mean and the lower confidence bound for each action decreases as the number of pulls increases, so the action which has not been tried frequently will suffer large penalty. In this way, the agent will avoid selecting an action which has large uncertainty to enhance stability. Our proposed algorithm incorporates the idea of pessimism in action identification.
B Proofs of Main Results for EOCP and EOCP-UG
In this section, we provide the proofs of main results presented in Section. 4 Throughout the proof section, we let Wa, be the i-th sample from pulling arm a the i-th time. Let Ta.s be the empirical mean of arm a after it has been pulled 8 times. Before proving the theorems, we provide several lemmas which gathers specific large deviation results useful in our analyses. Then we prove the regret performance based on the concentration lemmas.
B.1 Concentration Inequalities
We first present two concentration lemmas which characterize the sum and mean of empirical realizations of independent sub-Gaussian random variables as follows:
15

---

Lemma (Theorem 9.2 in (38) Let W1, W2,... WT be a sequence of independent a- subgaussian random variables with E[Wi] O. Then, for any > have:
8
Is & T.
W;
& exp
2T
Lemma (Lemma C.3
23 Ler Tj
T2 T be two real numbers in R
Let
W1. W,.... Wr be sequence of identically and independently distributed random variable ac- cording a o-subaaussaann distribution with E[W1] 0. Then, for any 8 > O, we have:
Σ. W. 37 & 8 8
T18
& exp
(3)
2
The proof's of aforementioned concentration lemmas can be found in the references respectively, Now we present the concentration results for our design of confidence bonuses as follows:
Lemma Let W1, W2.... Wr be identically and independently distributed I-sub-Gaussian ran- dom variables with E[Wi] = 0. Let Tı
< T2
& T, then the following holds:
Σ: W
21
min (T2 T1, el (log T2 log T1) + e)
(a) ift 2,
E [2).
+
cxp(1)
(4a)
Σ
W
21
(f) (0, v3..
E [T].
8 < 0
(vV++ + ón
exp
(4b)
Ti
Th
Ei=1
W
21
21 v 4ml
(c)
P
8
Ti.
(4c)
+
The proof of the Lemma.
will be delayed Sec. D
B.2 Proof of Regret Optimality for EOCP with Pre-Determined Stopping Time
We prove the following Theorem which characterizes the finite-time performance of Algorithm. Theorem, can be directly derived.
Theorem Ifl log(T) + 4 2og and T > max(16, 16, A, 161A,)))), the expected regret of the EOCP algorithu in Algorithm. 7 with pre-determined stopping time upper bounded by:
log (8+ v2 TogT
2
Reg,
EOCP (T)-
&
Σ a:
+ Do
+ o(1).
A.
A
A
Remark: The asymptotic regret upper bound is clear from Theorem infinity, i.c.
5 by letting I' increases to
lim sup T T-2
Reg
EOCP (T))
Tim sup Σ
(
2
(8+ v 20
2
A
o(1)
log T
T-
Aa
log
A. log T
log T
a:..50
2
A
a.A. 20
Proof. Without loss of generality, assume action 1 is the unique optimal action. From the regret decomposition lemma [38] Lemma 4.5), we can decompose the regret Algorithm, to the number of pulls for each sub-optimal arm follows:
Reg
EOCP (T) = Σ (.E]Nr(a)).
a
16

---

Then, the key to bound the total regret is to bound the number of pulls for each sub- arms. Since our EOCP algorithm has a clear separation of exploration and exploitation phases, so for any sub-optimal action we can bound its pulls in different phases as follows:
([N, (T.)) + + Tc) PP a)
where T. is the end of exploration phase and is the action that the algorithm commits to. Notice that the bound 12 gives the confidence level result provided in Corollary. [
Bounding 1 We first bound J, which is similar to the proof of bounding the regret for the traditional
UCB algorithm [22 10 22). We have:
Te Σ
11 10
A
=1+E
L JuB
1-++1
L1-A+1
A
A2
Notice that A, = a indicates UCB,-1(1) < UCB;-1(a) due to the dynamic of UCB exploration, we bound the last term as:
Te Σ
Tc Σ P(UCB:-1(1) < m)). A-A+1
A2 &
E
=
P- A-A+1
Event (UCB;-I(1) [1) means that round the mean estimation (1- of the optimal arm from previous pulls is lower than f41 b1), which incurs a large deviation, so we can bound this event with union over all rounds in the exploration phase:
(UCB,-1(1) m1) {36' (A,T)) UCB < mn).
which doesn't 't depend round number f any more, have:
Tc
T
P(UCB,-1(1)
m)) <1)
&
Σ
P ((a' e (.T.T.,UBBBA < <1)
(Te
A)P (3(' E [A, T.), UCB < m))
21
(Te A)P
3t E [A,TT), (1) + V Nr
p1
It is worth-noting that if there is pulls for arm 1 between time interval, its empirical mean and number pulls will remain the same. So we have:
21
[1, NT,(N)))))))) (1)) (...
21
31' E [A,T.), + V No(1) sm)
Is [1,
+ V < pn
Notice that Nr. (1) & T. - A 1,
bound the probability follows:
3t' E Fz() (1 < 14
21
<P
Ese e [1,T. - A+ 1), Fz,1 - 141 + +1 < <0
Fd SW1,5 12)
21
<P
E [1, A+ 1),
+
1
i
T. A+1
exp(I)
where the last inequality uses Eq. (4a) of Lemma and the fact that Wi, in is 1-sub-Gaussian with mean. Notice that Vlog T log log T when T is large and we have:
exp(!) exp (logT' T + 4 4 2og'T) > exp[log T + 4 log
T
17

---

So putting the above bound back to the bound of A2, we have:
2
8A(ling 744/21ng 7
+
A2 & (Tc -A+
Aj
Tlog²1
Tlog"
T
where the last inequality is due to the fact that when T 3 3, VlogT log T. Next, attempt bound the middle term A₁ as follows:
Te Σ 1=++1
To Σ 1=1+1
A =
=E
LA Fa-(at))
Notice that the number of pulls (a) will only increase by 1 every time there is new pull, i.c. when A, a. Otherwise, the term inside summation 0. instead of counting on the time step t, we can count over the number of pulls over arm a as follows:
N (a) I
Σ 1-1+1
As 11 Pe-1(0)+ (1 S01
=E
Pa.a Pr.at
2
3m
a=1
T, P
21
8s.a - +
where the last inequality is due to Nr.(a)
& Te. Then, by Eq. 44 of Lemma.
we have:
21
(W a. Pa)
2
P Ps.a
Ma + 1
Aa
P
Da
(logT T + 4422lgg +
4T (log T 4v 2oog T)
+
A
2log A3
(8 + /20
log 2
+
+ 1
A3
A
where the first inequality is due to the fact that Wa,i - Ma -ssub-Gaussia with zero mean, and the last inequality is due to / 2oog' T Ag, we can bound 1 follows:
log when 9. Therefore, combining the bounds on A₃ and
2 log T
(8 + 20m
log T
2
I
+1
A
A2
A2
Bounding 12: The bound on /2 gives the confidence level result provided in Corollary. I After the exploration phase, recall that select the arm with the largest lower confidence bound commit to. The idea of bounding I2 is very similar to the regret bound in 2 where since we use UCB to explore in the exploration phase, the optimal arm should be pulled very often such that its bonus becomes very small when exploration phase ends. Then selecting the arm with largest LCB will ensure we select the optimal arm with high probability. This because the LCB of the optimal arm is larger than the true means of any sub-optimal arms, and the true means of sub-optimal arms are larger than their respective LCB, both with high probability. We can first bound the probability of selecting sub-optimal arm a as:
PP (ā a) <PP (LCBT. (a) > LCBT. (1))
81
81 AZ
F
LCBT. > LCBr, (T,,
+P (1.
&
B₂
We first bound the term Bg which states that during the first exploration phase with UCB exploration, the optimal arm is under-pulled, which means that one of the sub-optimal arms have been pulled with larger number of times. Therefore, we have:
81 = Σ
81
(1) &
(a) > T
A
2
18

---

Recall that Tc 5.11 Aft
+ A, so we have:
P
(1) &
8/
=P
Σ
8(A - 1)1
+ A
Ab
A
8l
EP
Ea 1, (T)
+11
A
Then by union bound, we have:
P Consider fixed sub-optimal arm then for each probability inside the summation, we have:
(1aa= la 1, (a)
81
+1
Σ
P
Nr. (r)
81
+1)
A
A
30
81
NI. (a) >
+
88
Ee [4 + 1, T.], Nz-1(a)
A, -
A
81
e [A + 1,T.),N-1100 =
UCB,-1(1) & UCB.-1(a)
A
88
31 [A 1, (a) P
:1 UCB,_1(a)
A
Ba
(3t E [A+ + T.J, UCB:-1()) & 14).
B4
Notice that B4 can be bounded from concentration lemma. First, switch the count from time step è to the number of pulls for arm 1 since the empirical estimation Fr F and count for pulls (1) won't 't change unless there is pull. Then, will apply Eq.
4a the probability follows:
21
B4 =P
[A + Tol (1) in +
$ 0
V
N
N
<P
Ese [1e1,TT A+ 1), F..1 11
$0
Σ (W1, 11)
21
E [1. - -A+ <P
+ \ <0
A
exp!
where the last inequality is due to the fact that W1, - is 1-sub-Gaussian with zero mean. Similar to the procedure of bounding I, notice that exp(1) > Tlog" T, we have:
8A (log + 4 2 log
1
B4 &
T
A
T Tlogg* -log+T
On the other hand, let pulls for arm a. Then, Bg can be expressed as follows:
8t and we also change the count from time step to the number of
A
2/
B3
31E [1E[A+1,4 - 1], 1 = 7.11 & F2-1(a) + V N2
21
=P
Fyaa + 1 7
11
19

---

Notice that
A
81
81 Ag
so we have
21
V
2103
Aa 2
Then By can be bounded as follows:
Da
B3 $ P
77, +
1n = P 87,0 Pa
E cxp
2
2
exp(1)
Tlog'T
where the first inequality uses Hoeffding's 's inequality and the second inequality uses the lower bound on mentioned above. The last inequality is due to the fact that exp(l) i I' log T. So combine B3 and B₁ together, can bound B2 as follows:
Σ (Bs B1) = ( a.
B2 &
Next, we attempt to bound Bi. Notice that Bi can also be bounded as follows:
8/
B1 =P (a) > LCBr (1), No. (1)
A
8/
P Na > LTB
+ P (ma & LCBT. (a))
A
Bs
The term Bg be expressed by counting the number of pulls of arm follows:
B8
P
Na & Fr. (a)
V Nr. (a)
21
<P
E e [1, Te - A 17,14 - F8 +
VVs. =0
E E (Ha Wa,s)
21
=P
e E [1, A 1],
Notice that (Ha Wa,s) is
with zero mean, so we can apply concentration lemma
Eq. (4a) from Lemma. (3) as follows:
T A+1
8A (logT + 4,2
+
Bg
exp(l)
A exp(1)
exp(1)
where the last inequality is due to log T > 22 T and exp(!) > Tlog* 4 T when T > 9. Similarly, term B3 can expressed as:
2/
81
B, = P Ha (1.
Nr. (1)
V
Nr. (1)
A7
First notice that when (1. (1) >
we have the bonus term by. (1)
Am
A
A
Nr. (1)
Then have:
A
A
81
Bg < IP 2 FT. (1)
Nr. (1)
= P P1 Fr. (1)
Nr. (1)
2
2
Then it is equivalent to count over the number of pulls for arm 1:
8/
A F.
BB EP
]s
T
A
81
Σi=1 (m Wi.e)
5
A
3ss E
T
A²
$
Then, by the maximal concentration Eq.
3
from Lemma.
2
we can bound B3 as follows:
81
A
2
P
E
A
81
T
Σ (H1
W1.)
Aa
2
&
exp
A
exp(1)
1
T Tlog
1
20

---

Therefore, collecting the bounds for B5 and B6, we have bound for B1 as follows:
B1 B5 B6
T
And therefore from the bounds of B1 and B2, we can bound term 12 follows:
2 B1
This means the the confidence of selecting the wrong action to commit to is o(7~)) as indicated in Finally, putting the bounds on 1 and 12 together, we have:
Corollary. [
E[Na(T)] 11 + T12
2 log' T (8 2lgg A
2
+1+
A
A
Therefore, by the regret decomposition lemma,
bound the total regret follows:
Reg (T) <
Σ
2 loo'
+
(8 + 220g)//oog
+
2
+ Da + +0(1))
An
A.
A
0:
log T
(8 + (20
2
Da + d1).
Aa
A
A
0:A.30
B.3 Proof of Regret Optimality for EOCP-UG with Adaptive Stopping Time
We prove the following theorem which characterizes the finite-time performance of Algorithm. Theorem, 2 can be derived directly.
Theorem Ifl log(T)) + (A/2loo(T)) and T max 16, A, 161mmin), the regret of EOCP-UG algorithm in Algorithm. with adaptive stopping time can be upper bounded as:
2 log T
(8 20m) + O(1).
Reg
EOCP-UG (T)
Σ
A
Aa
a:A,30
Remark: The asymptotic regret upper bound clear from Theorem 6 by letting increases to infinity, i.e.,
Reg EOCP-UG(T) (T))
2 (8 20mm
lim sup T-
lim sup
Σ T T- 0:
Ollo 'T))
Σ a: 20
log T
A Aovlog
A
Proof. Without loss of generality, action be the unique optimal action. The first step for proving the regret performance is regret decomposition lemma [38] Lemma 4.5J. We also decompose the regret of Algorithm. into the number of pulls for each sub-optimal arm as follows:
Reg (T)
Σ A.E(Nr(a)).
a:
Then, for specific sub-optimal arm a, we bound the number of pulls. Since our EOCP-UG algorithm has clear separation of exploration and exploitation phases, we can bound the pulls in the two phases respectively. However, the unique characteristic of unknown gap scenario is we don't 't have fixed end time of exploration phase. Recall that T. & T is the stopping time that the exploration phase ends and à is the arm we choose for commitment, into two phases as:
can decompose the number of pulls
[[)] (T.) + E[[
La=al & B[Na(Ta] +TP(a=
Fa
Notice that upper bound the two terms / and 12 separately. In order to simplify the proof, we first prove a lemma which characterizes a high probability upper bound for the stopping time Tc. This lemma also proves the sample complexity to commitment result in Corollary. The proof of Lemma. 4 will be delayed.
gives the confidence level result in Corollary, We then bound
21

---

Lemma 4 Ifl = (T) 4v log(() and T > max 16, A. 16/4 exploration of Algorithm. upper bounded with high probability:
minh, our stopping time T for
1)²
10eA
Te
+ A(1+2)
A
T Tlog"1
a:A.0
Bounding 4: With the help of Lemma.
we have a high probability upper bound for the exploration
A(I 2) to be the high probability upper bound of stopping time to end the exploration phase. Notice that Na & T, we have:
phase. We let TV -m...>0 A
8(1+1)*
1 = (nr +
& TP (Te > Th) + E[Na(Ta)
10eAA
InNa log27 T
Then, bounding la is similar to bounding 4 for Theorem. 5
We decompose 13 as follows:
13 =E
TT
LA
To Σ
To LTET Σ
=1 =1+ ++E
TTET
JAB (a)am
+
14.=a LCB, 1
(a))m)
1=A+1
t=A+1
A
A
In order to bound A₁ and A2, assume there is virtual process that after the end time T. of exploration phase, continues to select the arm with largest UCB and receive the corresponding reward until time T This is only virtual process used in our proof, while in reality our algorithm will stop exploration after stopping time Te. We will use and P' to denote the expectation and probability over this virtual process. Then, we can bound A2 follows:
Te Σ t=1+1
A2 <E
IT
E'
JUCB
1=A+1
T
Σ P' P'(UCB,-1(1) m4).
1-++1
where the first inequality is because A, indicates UCB,-1(1) UCB,-1(a) due the dynamic of UCB exploration. The second inequality is because and are totally the same for the first Te time steps. This step also allows to bound A₃ over the events E' and IP', Event (UCB,-I(1) < μr means that at time step t, the mean estimation fr-1(1) of the optimal arm from previous pulls lower than μ1 (1), which incurs large deviation, can bound this event with a union over all time steps:
different probability measure
{UCB,- (1) < pi) c {J'' [A,T.), (CB < m1).
which doesn't t depend on time step any more, so we have:
Σ P'' (UC <m)
Σ F' (3/ UCBT)), < m1)
= (T A)P' (3/' UCB: < <()))
21
(T A)F'
3t [A,T")) (e( +
#1
Ne((1)
If there is no pulls for arm 1 in time interval, the empirical mean and number of pulls will remain the same. So instead of counting on the time steps, we can count the number of pulls for arm 1:
21 No(()
21
W'' +
< Mn = Js [T, Fr,1 + 1
< m1
22

---

Notice that (r) & T - -A+ 1, so we can bound the probability as follows:
3t' E [A,T P
(1 < fn
21
<
E [1 - -A+ F,, P1 + +1 <00
Σ (W1, - -11
e [1 - A 1), <P'
T A cxp(I)
where the last inequality uses Eq. 4a) of Lemma and the fact that W1,: 14g is resub-Gaussian with zero mean. Notice that exp(I) > Tlg" T, so putting the above bound back to the bound of A2, have:
812 + Al ))²
(En:d.00
2o0 2 log
Ag
A
A2 <
O)
Tlog"
Tlog" TT
where the first inequality is due to the fact that when T 3 3, / T & log T. Next, we attempt to bound A₁ follows:
TH Σ 1-A+1
T Σ [-A+1
A E
1 TT
IA
<E'
1 1A Pe-1(0)+ Ne-i 301
where the inequality is also due the fact that the virtual and real processes identical before time Te. Notice that the number of pulls (a(a) will only increase by every time there is new pull, i.e., when A, a. Otherwise, the term inside summation So instead of counting on the time step f, we can count over the number of pulls over arm follows:
Tec
Nyp (a)
E
Σ (-1+1
1 A 11 " ((11)) Ne-1oo
E
Σ
1
Fa.a
2
33
T
pl
Psja
Ma +
where the last inequality is due to Ny (a) & T Then, by Eq.
4c) of Lemma.
we have:
21
W a.. paa
27
Pll
Fs.a
pa + 1
Do
P
An
2 (log + AvologT) +
4T (log T + 2/ T)
+
+
A2
2log T
(8 + /20m)
Mog T
+
A2
A
A2
where the first inequality is due the fact that Wa,t Haa Buub-Gaussian with zero mean, and the last inequality is due /2 /olog T log T when T 9. Therefore, combining the bounds A and A2, we can bound T3 as follows:
2 log T'
(8 + v 20m)
log T
2
Ig
+1+ O
A2
A
A
Therefore, similar bound can be established on I as follows:
2log
(8 + /20m) / log
2
1
11 <
+
1
+ O(T-l).
A
A
A2
log
2
T
23

---

Bounding 1y: Recall that our stopping criterion is when there exists an arm à whose number of pulls sigmificantly larger than other arms, i.e., NN. (ā) ž maxx44a (a) Therefore, its bonus br, (ā) should be very small compared to other arms. Also recall that we select the arm á with highest LCB to commit to, so the proof follows two steps. First we will show that with high probability the arm à with most number of pulls is the best arm. Then we will show that under this circumstance, the maximum LCB arm is also the best arm. Therefore, consider an arbitrary sub-optimal arm a:
P a) TP (Nr, (a) > (INT;()) 1)-
Notice that if Nr.(a) (a) > [,NT, (1)] + 1 at the end time Te. we must have pulled arm at time step Te. This also means that the number of pulls N
arm a after time step T. is exactly 17NT. (1)] and and -r) = Nr. (1). It also means that arm has the largest UCB. So we have:
P (NT, (a) > [tNr; (1)] + 1) P (Nr, (a) - UCB. - (a)) UCBI,-1(1)
21
21
<P 3t Te, (a) [IN(()),, Ni(a)
(1) +1 V (((1))
Notice that separate the two random quantities with union bound as follows:
P PNNr. (a) > (1)T((1)) 1)
21
31 Te, Fr(a)) 3 Na + P
Ní(a)
B1
21 Ni(a)
21
P
3 Tt, [IN Ma +2
f((1
V
M1)1)
Ba
We first bound Bj. Notice that we can switch from counting of time step t to count the number of pulls for a. is clear that (a) & To T when & & To, so we have:
/2/
B1 &P
3s & T, Fs.a pa +
V=
Σ i- (Ma
Wa,i)
21
=P
3s & T,
+1
x0)
el log T + e
expl
where the last inequality uses Eq.
4a
of Lemma.
3
Also notice that exp(l) > T loog' T, have:
10e log
2 T +
1
-
T Tlog'
Next, we bound the term B2. we can rearrange the terms inside B3 follows:
11 T (a) (NN(0)) - (1
2
21
+ < 20)
B2 P
+
vt
N.(1)
Denote a =
2 and switch the count from time step to the number of pulls for arm 1, we can .
bound Bg as follows:
2a
B2 $P
78 & T,Fs,1
14 +
+ A. $ $0)
(W1i 111)
202l
3s &
An $0)
5
A exp (a²l)
24

---

When T' is large enough, we have = 4v1 + 4 > log T + 4, so we have:
4
B2 &
A
Therefore, combining B1 and B2 together, we can bound the probability as follows:
(
P P a) & P (NT. (a) > (NT,(1)] +1 & B + B2 & O
Recall that arm 1 is the optimal arm. Therefore, by a union bound, we can characterize the probability that of event {ā 1] as follows:
P(
Σ P(ā=a)<0f a:A.>0
Next, we investigate the probability of choosing the wrong arm à to commit to. Recall that for the arm which we commit to, we choose the one with the largest LCB. Consider any sub-optimal arm a, if we wrongly choose the arm à it means its LCB should be larger than the LCB of the optimal arm, which with high probability has the largest number of pulls. So, we have:
< P = a, à = 1) + (ā # 1) < P (LCBz, > LCB1, (1), 1) +)+ (T)
(a = a)
When 1, arm has times more pulls than arm a when the exploration phase stops, so we have:
P P(LCBr, (a) > LCBr. (1), 1)
21 (a)
21
(1. > INT. (1) (c)
<P
Fr. (a)
Fr. (T)
V
V (1)
Similarly, we separate the two random variables as follows:
P P(LCBT.(a) (a) > LCBr. (1), 1)
21
21 Nr. > LNT.(a)
(a) \ Nr. (a)
2 pI
2
Nr. (I)
21
+ P
(1) 11 V (1)
1
2
27
(Ma - (a) + <
A. <0 +P (1)(1) < P1 - Ny. (1)
vi V (a)
Bs
For B4, notice that T. is random stopping time, so we bound the probability over all time step when the number of pulls is larger than as follows:
27
CW,, m1)
27
B4 P Et [1,T], 11
=
Es [1,
0
Since W1,+ 11 is 1-subgaussian, use Eq. B4 as follows:
44) from the concentration Lemma. to bound
Bi & E E [1, E (i M1)
21
el log T expl
(
8
where the last inequality is due /2 T log T when T 9 and exp(I) T Tlog" T. On the other hand, bounding B3 is similar to the proof of probability upper bound regarding ā. recall that (1 (1-2) ).. 41 and notice that T. is random variable, so we use union over all possible arm pulls
25

---

to bound the event on time step Te as follows:
2222
B3 P
F8 = (1' (s,a)
Da $ $0
8
E Di=1(1u
Wa,s)
2202
P
3s E T,
V
+ Au $0
5
A exp (a²1)*
where the last inequality uses the second concentration inequality Eq. (4b) from Lemma. and the fact that Ma aa, is I-subgaussian. Then when 7 is large enough, we have:
4
B3
ACT
Combining Bg and B4, we can bound the probability that we select the wrong arm as:
4
( [ T
& O 1 T
P P(LCBr. (a) 3 LCBT. (1),
B3
B4
+
2T
Therefore, we finally bound Iz as follows:
=) 0 .
P(à & a.
0
Here, the bound on 1n shows that the confidence level of our algorithm is O(T-1) indicated in Corollary. 2 Combining I and 1z, we can bound B[NaaT)) finite time as follows:
2log T A
(Dr)ylogg 220 (8
E[N. & + Th2 &
+
+ +11).
A
So by the regret decomposition lemma, bound the regret performance
2 log
(8 +
(000)//o Vog + 0(1)
Reg
EOCP-UG
(T)
Σ
A
Au
a:A.>0
B.4 Proof of Lemma. Jand Corollary.
Consider specific sub-optimal arm We first show that it only be pulled Olog 7) with high probability during the exploration phase due to the dynamic of our exploration strategy, i.c., the UCB exploration strategy. To be specific, we intend show the following inequality:
P T Nel
8l
+1
10c
A
T 2 T
Since during the exploration phase, we select the arm with the largest UCB to explore, if there exists time which the number of pulls for action larger than & A + 1, which means that there exists
time t' [A, t), where time t' + 1 the number of pulls for previous rounds (a) is exactly and arm has the largest UCB. Therefore, we can bound the probability as:
8i X!
81 &
= 81
P 36 Te, N((a) >
+1
38 SEEEET,NNCO
arg max UCB:
2
A
d'
26

---

Therefore, the UCB of arm a should be larger than the UCB of the optimal amm 1, i.e., UCBrr(a) > (1). So we can further derive an upper bound as follows:
81
P
3t & & (a)
a arg max UCB:r(a))
81
<P
1/ & T, Nz
(CB UCBr(1))
=
A
81
21
=P
31' & T, (a)
(F((aa) +
3 Fx(11 +
A2
(a(a)
(1)
A
21
<
3t & T, Fr
(1)
2
Then, separate the two empirical means
and (1) with a union bound as follows:
a
A
21
P
31' & T,P
(1) + V (1)
2
A3
21
An
<
31' & T, (1)
& pa + Do
+P
Pa +
(1)
81
2
A1
The term A2 can be easily bounded through Hoeffding's inequality as:
(W e,
Ha)
Aa 3
81
A 8
A2 P
< exp
A
exp(1)
where the first incqulity is due to the fact that Wa,; - Ma is L-subgaussian. For term A,, notice that the empirical estimation Fe (1) and the counter N1-(1) will remain the same there is no pull for arm switch the count of time step e' to the count of number of pulls for Nţ(1). To be specific,
21 Ma + Da
E (W1, p1)
21
A & 18 1, +
+1= & Ma
=P
38 & TT T,
Since Wi.: - μ4 is 1 1-subgaussian, we can use the concentration result Eq. 4a of Lemma. bound A1 follows:
Ei (W1,5 M1)
21 +
el lo T +e exp(1)
is T.
VV
<
Therefore, we have can bound the probability of overpull for sub-optimal arm a as follows:
81 = Ai
e(log T + 4v log 7') log T + 2e exp(1)
10e Tlog2 T
P 3t < Te, Tc,
+1
A2
A2
where the third inequality is due to log T' exp(I) & Tlog" T. Recall that in Algorithm. whose pulls Nr. (α) the stopping time have exceeds / times of all other arms, i.e.
>>
2 log T when T > 9 and the last incquality is due to 2 the exploration phase will stop if there exists an arm
| mmax Nr. (a) + Nr. (ā) I mmax Nr. (a) 1.
27

---

8(++1)² So if To is larger than La:A,>0 >0
+ A(l 2), means that there exists least sub-optimal
2y
arm a whose pulls Nr. (a) is larger than 8l A
+ 1. So have:
8(1 1)2
To >
Σ
+ A(I + A(I
+2)
<P
3a: Da > (T)
>
A + 1
A
a:A.>0
Σ P
3t Te,
Nolaaa
>
8l
+1) 1)
A
a:A.>0 >0
10e.A
T T'log2T'
where the second inequality, union bound over Then Corollary, 2 SCC (T) =B[T.
can be easily proved with:
E
Tel
T,
S0++132 +A((++2)
Ag
E
Tcl
To
2u:da00
M(C+1)
+.((+2)
8(1+ 1)2
8(1 + 1)2
<TP
Te 2
A((1+2)
Σ
A(I +2
A
A
a:
a:A
8log T + 80 log 3 T 200
10eA
6.A T
A?
log T
B:A.>0
Therefore, taking T to infinity, we have:
SCC (T)
8
lim sup
log² 2 T
A
T-
a:A.30
B.5 Proof of Theorem. 3
We first prove the fundamental limits of sample complexity until commitment in the pre-determined stopping time setting. Suppose the bandit problem (instance) as follows: the reward expectation of action 1 is Yr and the reward expectation of action 2 is (22. We assume Consider another bandit instance with reward expectations \1 and X2 for the two actions respectively, and d + A & A2. By the "transportation" lemma [32 Lemma. 1] when T > 10, we have for any stopping time that:
> H2 and A = μM μ22-
T
E.IN(())KL(AI A1) + E, A2) > log
2.4
Since under Gaussian bandit, the KL divergence is simply the squared norm, have:
[T)] (1I
>1)2 + [x(NN(TT] (22 (22-12) log
T
2
2
2.4
Since the inequality holds for any A and d2 such that that A1 + A & X2, we can minimize the LHS
obtain tighter bounds. So minimizing the LHS over X₁ and X2 gives:
N4 E [N) + (M2 (2()) A (M1 + A [ + (NE,)
A
(N) + B. (N()T)
[N + ET (N2(7)
So plug the optimization result into the "transportation" lemma, have:
(N))) (E) + (2())) (E) [N(()))) > log
24 (N))
T
2.4
Therefore, rearranging the terms in the inequality, we can derive a lower bound on E, N₂ (7)] as follows:
2 log
T E [2)
E. [7]
2,4 [2
2A
2 log 2.44
28

---

Let Te be the fixed length of exploration. Thus, we can derive the following lower bound on the expectation stopping time as follows:
2 (E,
B [T. [ (T.) E [2 [NV - 2 log 2244
According to assumption, the algorithm has c-logarithm regret violation with ((T confidence, which means the the number of pulls for the sub-optimal action is upper and lower bounded when T large enough. So we have:
2 log((T) O(log" E [N)
2
Recall that à is the action the algorithm chooses commit and action the optimal action in instance μe, so we have IE [TT) < E, [Te) + TPμ, (å * 1). Since the algorithm has O(T")) confidence, so we have F, (ā * 1) = O(T-1) and E N (T) & Ex [N2(Ta)] + O(1). So we can
lower bound the numerator follows:
2 (E (Ta))))
22 (E N2 [T) 0(1))
22
A log 2 T O + T)
log T O1log
A
Notice that [T,)
E (TT)) the denominator, derive upper bound similarly
as follows:
T
T
2A EA 2 log
<A E - 2og
2.4
2.4
2 2A
T
A log T O(log T)) 2log
2.4
$2 T O(log")),
where the second inequality uses the fact that the algorithm has c-logarithm regret violation. So combining both bounds in the numerator and the denominator, we have:
8 log 2 T O(log + T) Ω
log T A
E.[Ta]
A
log Olog T)
which concludes the proof for the pre-determined stopping time setting. In the adaptive stopping time setting, we can use the same procedure to prove the lower bound sample complexity until commitment, also create another bandit instance with reward expectations x and Az. Unlike in the pre-determined stopping time setting, now A and X2 satisfies A & A2. We also use the "transportation" lemma and optimize \ and X2 to get lower bound for E[T.] follows:
A (E,
F [T.]
(N (7a) + (2((,))
A [N, 2 2log (24))
Similar to the proof of pre-determined stopping time setting, we utilize the fact that E, (T)( E [N2(T)] & E,, [N2)T.)] + 0(1) and the algorithm has c-logarithm regret violation to bound the numerator and denominators separately. For the numerator, we have:
(ET)()((T)))) A (E,[N22T) O())
4 log T (log)++e7)
2
t
4
2 log" T OOog 1tc
For the denominator, we use the fact that the algorithm has c-logarithm regret violation:
T
2
log T Ollog T) 222 2 T
A A
2og
- A
2.4
2
2.4
(log T).
29

---

So combining both bounds in the numerator and the denominator, we have:
3 log T - Olog' (7
logg===""
[T
Ollog" T)
A
C Proofs of Main Results for KL-EOCP
Now we are ready to prove the regret and sample complexity until commitment results for our KL-EOCP Algorithms, i.e., Algorithm. 3 Without loss of generality, suppose action is the unique optimal action. Recall that for any time index I, UCB,(a) and LCB;(a) denotes be KI. upper and lower confidence bound of action
(a)
arg max { (f) E LCB:(a) arg min ( (N.(a)KL((((())))) < ((F+(()
p²
Throughout the proof section, we let Wa, be the i-th sample from pulling arm a the i-th time. Recall that Te is the length of exploration phase. Let Fo,s be the empirical mean of arm a after it has been pulled s times. Moreover, we let:
UCB arg max (sKL(Ts, & 1), LCBs,a arg min (sKL(Ts,a p)) & E ,r,,,
In order to incorporate this new definition of UCB and LCB, we need new sets of concentration inequalities, which will be summarized in the next subsection. The proof will be delayed to Sec. D
C.1 Concentration Inequalities for Natural Exponential Families
Since we no longer assume the distributions [M,,... VAA are subgaussian any more, the concentration inequalities from Sec. B.1 especially Lemma. [ longer holds. Therefore, need set of new concentrations specialized in the natural exponential family regime. To be specific, we want to bound the probability that the KL divergence of empirical estimations and the true expectation very large. First, we provide concentration lemma which is analogous to the Hoeffding's 's inequality widely used in the subgaussian scenario follows:
Lemma 5 Let W1, W WT be identically and independently distributed random variables with common expectation μ [[[1] and sampled from a distribution v that belongs canonical
exponential family P. For any & T. Let S. Ei=1 W; and P. S. denote the sum and the empirical mean of the first samples. For any 5 > O, we have:
P(,, & μ. sKL [As, p)) > 6) < exp( -),
(5a)
IP (ñ. 14, sKL (fs, p.) d) & exp(-5).
(5b)
Based on Lemma. 5 we propose the following lemmas characterizing the any-time concentration property of random variables.
Lemma 6 Let W1, W2. ... WT be identically and independently distributed random variables with common expectation μ [[W1] and sampled from a distribution v that belongs canonical exponential family P. For any s & Let S. Σi= W; and is denote the sum and the empirical mean of the first samples. Let Ti To T be two real numbers in R For any 1 > the following holds:
T2 - Ti +1 el (log T2 - log exp(I)
Tı) +e
(Js E T2, & sKL (Do, 2 1) & min
exp(1)
(6a)
T2 Ti + el (log T2 log Ti) + exp(I)
P(3s e [Ti, Po > 14, sKL (1s, 2 x min
exp(1)
(6b)
Lemma Let W1, Wz.... WT be identically and independently distributed random variables with common expectation μ = [E[W]] and sampled from a distribution v that belongs canonical
30

---

exponential family P. For any & T. Let S, = Ei=1 We and μı S.. denote the sum and the empirical mean of the first samples. Let UCB, arg max {sKL( H1) & 1] be the upper confidence bound for empirical mean. For any any Ti $ T, any pt μ4, and any e > 0, the following holds:
21 Σ
(1 (1+
82(6)
P (UCB, 2 1²) KL(P, +
TDi(s))
where (I(e)= ( and Bo(e) 3 are constants.
C.2 Proof of Regret Optimality for KL-EOCP
In this section, we provide complete proof of Theorem. We prove the following Theorem which characterizes the finite-time performance of Algorithm, and Theorem. 4 can be derived directly.
Theorem Ifl = log( T + 14//2oog(TT and T > max 16, A, 8IKL the regret of KL-EOCP algorithm in Algorithm, can upper bounded as:
Da log
104 log a T KL(Ma: M1) + o11)
Reg
KL-EOCP (T)
Σ
KL(Pa:
a:A.>0 >0
Remark: The asymptotic result clear from Theorem by letting T increases infinity, i.e.,
Reg KL-KKCPP(T (T)
A
lim sup T-
Σ
log
(L(Pa,JA1)
Proof. Without loss of generality, let arm be the unique best arm. From the regret decomposition lemma [8 Lemma 4.5], we can decompose the regret Algorithm. 3 to the number of pulls for each sub-optimal arm as follows:
Reg (T)
Σ A.E[Nr(a)] a:A,>0
Then, the key to bound the total regret to bound the number of pulls for each sub-optimal arms. Since our KL-FEOPP algorithm has clear separation of exploration and exploitation phases, so for any sub-optimal action a, we can bound its pulls in different phases as follows:
E[N,(T)) (T.) +(T - T.) P(a = a),
I2
where recall that T. is the end of exploration phase and à is the arm that the algorithm commits to during exploitation phase.
Bounding I, We first bound J, which is similar to the proof bounding the regret for the traditional
KL-UCB algorithm [12]. We have:
Tc Σ
J
1A-a
= I
Σ
1 Mu-a
+
E
Σ 1-A+1
A -a
(c)
1-A+1
A
A2
Notice that A, a indicates UCB,-1(1) UCB,-I(a) due the dynamic of UCB exploration, we can bound the last term as:
T
T (0)c)_10))ml = Σ P(UCB,-1(1) < p1).
A₂ <
Σ 1-A+1
E
1-1+1
Event (UCB;-1(1) < 31 means that at time step f, the mean estimation FT-1(1) (1) of the optimal arm from previous pulls is lower than μn b1),(1), which incurs large deviation, so can bound this event with a union over all time steps:
(UCB:-1(1) =n = (3t' e T.). UCB: < pn).
31

---

which doesn't it depend on time step any more, so we have:
Te Σ
Σ P P(UCBL_I(1) m))
P P( [A, UCB UCB()) m1)
1-1+1
-(T A)P (3'' e [A,T.), (1) < (11)
For two time steps T < 12, if there is no pulls for arm between them, then the term (1) will remain the same through t' E [2o. So instead of counting on the time steps, we can count the number of pulls for arm 1 instead. We have:
f3t' [A, (CB < mn)
(3s Nr; (a)) UCB,, m1).
Notice that Nr. (a) & T. A+ 1, so we can bound the probability as follows:
P P(3t' [A,T.), UCB,) < p1) <P [1. A 1), UCB x1)
P As [1, A 1), parF.1
KL(Fs,1,
m2)
Notice that for any and under event (UCB,,1 < #1}. we have μi > UCB,,1 > f.11 By definition of UCB we also have KL (Fs,1, UCB.,1) = 4 Therefore, we come to the conclusion that KL (Fs.1, > I using Eq. 6a of Lemma
we have:
1 (L(FA1,)) & m1
P E [1, - A+ + 1), max
<P (3s (as [1 A+ 1), sKL (Fs,1,1)
To A
exp(1)
Using the fact that exp(l) 3/ T log T when T 3 16 and putting the above bound back to the bound of A2, we have:
8Allog
(Te A)2 Tlog" 4
KL
1
A <
0
T
Tlog* T
where the last inequality is due the fact that when T > Vlog log T. Next, attempt bound the middle term A1 as follows:
=
Σ 1=A+1
=E
Σ 1=A+1
IA,a IUC
Notice that the number of pulls (a) will only increase by 1 every time there is new pull. i.c. when At Otherwise, the term inside summation is O. So instead of counting on the time step t, we can count over the number of pulls over arm a as follows:
Nr. (a)
E
Σ A+111
AA 1 LUBK (1))
=
Σ
LUCB
P (UCB,,. > 211)
where the last inequality is due to Nr, (a) & Te- Using Lemma. can bound the sum of probabilities. Specifically, for any E > O, there exists two constants Bi(e) O(e2) and 32(c) O(e-3 such that:
Σ P (UCB,, > (1) & (1+ KL(Ha, TPi(s))
T.
B₂(E)
+
Let = log : T, and when T > 16, we have log T' > VlogT and 4 4 & 5lgg T. so we have:
To
log T
10 T KL(Har o())
P PUCB, s.a m1) KL(Has p1)
32

---

Therefore, combining the bounds on A1 and A2, we can bound I1 as follows:
log T 10log T 11 E (L( (L u1)
+ o(1).
Bounding 12: After the exploration phase, recall that we select the arm with largest LCB to commit to. The idea of proof is very similar the regret bound in [ and our proof of Theorem, S We can first bound the probability of selecting a sub-optimal arm a as:
P (a a) EP (LCBT. (a) LCBr. (1))
41
=P LCBB, (a) (C), NT. KL
+P (LCBr.(a) LCBr, Nr; &
41
KLib
41
4/ KL
<P (CBr.(a) > LCBr. (1,, (1)
+P
Nr. (1) &
KL
B1
B2
We first bound the term B2 which states that during the first exploration phase with UCB exploration, the optimal arm is under-pur ander-pulled, which means that one of the sub-optimal arms have been pulled with larger number of times. Therefore, we have:
P NN, (1)
41
41 KLb//
P
Σ la:A.30
(r) Tc
KL
Recall that To
KL + A, so we have:
P
Nr. (1) &
41
=P
Σ
(a)
4(A 1)1
+ A
KL
KL
aidd. >0
CP Ea
1, N.
41
+ 11.
KL1b
Then by union bound, we have:
P 3a > 1, (a)
41
P
Nr.
(a)
4/
+1)
KL
KL
a:A,30
Consider fixed sub-optimal arm then for each probability inside the summation, we have:
4/
P (r. >
KL +
4/
<P
36 [A + 1, Tol N₂ (())
Ar = a
KL
41
<P
E [A + 1,T.],
.UBB,-1(1) & UCB.-1(a)
KL
41
P
3 [A N,
14 & UCB:-1(a)
KL
P E [A+ + 1,1,J UCB,-1(1) & p1).
B.
Notice that B4 can be bounded from concentration lemma. First, we switch the count from time step I to the number of pulls for arm 1 since the empirical estimation Fr (1) and count for pulls N2-1(1) won't 't change unless there is a new pull. Then, we will apply Eq. (4a to the probability as follows:
B4 I [s
[1, T. A 1), UCB,,1 & mI)
<P [s [1, T. A F,, & μ1, (KL(( (F..1.111) 1)
T A
expl"
33

---

where the second inequality is because under event {UCB,,1 & f1 and according to the definition of UCB we have xx & UCB,.1 & fr. and since sKL(f,.1 x, UCB,,1) with μ4 UCB..,, we have sKL((s.1, > L. The last inequality uses Lemma. Similar to the procedure of bounding 71, notice that exp(!) > T log" T, we have:
4A (log T + 4 220g
1
20.4
B4 <
KL
Tlog" T
KL log
On the other hand, let pulls for arm a. Then, By can be expressed as follows:
41
and also change the count from time step to the number of
KLn
B3 P (36 [A 1, 1J, ( 7.44 UCBN.-1(aa.a) (mi UCB..a). For any pair of means v,
[0, 1]. define KL (1x v) KL( ())lzzyy Then, have:
P (M1 < UCB < P [KL (Fy p1) 4)
Notice that 7
41 KL
KL(Ha, we can also bound Bg as follows:
41
B3 & P KL (Fx.ai))))) & KL(Ma: H1l
Recall that U'g (Mas M1) such that KL u1) KL(masus) so we have Fria 2 1/a under the event that (KL*(Fyxon (Fy.aa & KL(Maine) ). and thus KL(F Ma) 3 KL(H/a Ma). By Lemma. 5 have:
(L(HasH1) & IP (KL KL(U Ma)) & exp(~>KL(yb,
IP KKL 1KL (Fras
LIKL(p'sHal Rlib
Notice that 7KL(((7), Ma) 2
E by the definition of KLmin we then have:
Bg & exp(-1) < T Tlog TT'
The last inequality is due to the fact that exp(1) > Tlog* T. So combine By and BN together, we bound B2 follows:
20A
1
B2 E
Σ (Bs+ Ba) &
+ Tlog*T)
KL log
a:A.30
Next, we attempt to bound By. Notice that B₁ can also be bounded as follows:
41
B1 =P LCBr. (a) > LCBr, Nr,
KLJb
4/
E Mo 3 LCBT. NT:
(Ma & LCBr.
KL
Bg
B,
The term Bg can be expressed by counting the number of pulls arm a as follows:
BB &P (Js E [1, Te A LC,LCB,,a 2 Ma))
=P (ss e [1,Te A 1), pa, sKL (Fs,as Ma) > 1)
T. A +1 exp(1)
where in the last inequality, we can apply Lemma. 6). Since log 7 2 2 /2log T and exp(!) > Tlog"
when T > 16, have:
4A Alog T + 2.442/10 log
Bo <
+
(
KL log T
T Flog
34

---

For any pair of means E [0, 1]. define KL expressed as:
-z, v) = KL(x,, v) Similarly, term Bs can be
4/
BB &P
38 >
Ma 22 LCB
KLmh²
4/
<P
18
sKL- (Fa, E1)
KL
41
KL(HarH))
T
As
KL (Fa,
KL
4
Recall that il E (Mor p1) satisty KL (Hla ua) = Ki(maale) so under event (KL (Fa,1, & KL(jaa)t)) } we conclude Fs,1 & p/a which means KL (Fs,1, 2 KL (1'a M1), have:
41
KL(Mas HI)
P
38
KL (Fx,1,
KL
4
41
TP
3s
Fss1 pn, KL WL,KL((Fs, (Fs,1.14) 3 KL (Ha:
KL
41
4IKL (Maa ue)
<P
3a
Fs,1 M1 (Fa,,,
KL1b
KL
el log T' +e
4IKL(H', .m)) KLib
exp
where the last inequality comes from Lemma. 6 By the definition of KLmins we know that 41KL (KL( > so have:
KLm
B3 eog te exp(l)
10c log
1
T
T Tlog*1
Therefore, collecting the bounds for B3 and Bg and Bz, we have bound for 12 follows:
1
1 2 B B2 < Bs + BB + =2=
T
Finally, putting the bounds on I and 1z together, have:
log
10 log T
(T)] < I1 + T12 < KL(Aaa M1)
+ o(1).
KL m1)
Therefore, by the regret decomposition lemma, bound the total regret follows:
Du log
104, log T
Reg
KOCP
(T) & Σ
+ o(1).
KL(Ha,
KL(Ma. M2)
a:A.>0
D Proof of Concentration Inequalities
In this section, we provide the proof of the concentration inequalities presented in previous sections.
D.I Proof of Lemma. 3
The proof of Lemma. 3 relies the maximal inequalities in Lemma. and Lemma. 2 and the famous Hoeffding's 's inequality which we state here for the sake of completeness.
Lemma (Hoeffding's Inequality) Let (W.)_ be i.i.d. --suu-Gaussann random variables with B[W]]= 0, we have;
T
W.
T
P
-=
3
8
$ exp
T
20
35

---

We now prove Eq. 4aa of Lemma. 3 We will first base our proof on the anytime concentration on union bound, which tight only when T2 Ti relatively small, This procedure will result in the first term in the minimum at the RHS. To prove a stronger result when T2 122-7 Ti relatively large, we resort to the technique of "peeling device" which divide the time horizon into exponential grids, where we will perform maximal inequality inside each grid and union bound over the grids. This will result in the second term in the minimum at the RHS. We first perform union bound on as follows:
Eq. 4a) of Lemma. 3
Σ W
21
PP 3s (Ti, T2)
0
=Pp
E
(Ti,
Σ
W
21s
8 J. Σ
8
W 22s
Then, we can bound each probability with Hoeffding's concentration inequality as follows:
P S J: Σ W 21s <0) )
Σ
W. 25 <0)
< exp
(-(v23)²
1
2j
exp(()
Therefore, summing up the probabilities, we will have:
E
W
21
T Σ i-T1+1
T2 T1 exp(l)
P Ese (Ti, [2),
0
&
(8)
exp(1)
Next, apply the peeling method prove the second inequality. Take 3 to be constant. Let M = [logs I. J. we apply peeling method and divide the time horizon over exponential grids
[Ti, Ti3), T133,. ... [Ti,3A, T2] as follows:
P e T2),
EL W +
21
E 0
=P
E (Ti, [T),b
Σ
W; + v 21s & $0)
i=1
P
3s E [Ti Ti 8i8++1
Σ W; + v 21s <0
=
Since at each grid, >/ Ti00, we can upper bound each probability as:
P sse , T3 Σ W. 221s <0)
& 3s [Ti91,
1T,,,,,3344 T13++ JJ Σ W, + 20,
Let B 1. T then according to the anytime concentration inequality from Lemma,
we have:
P i [T,,,, Σ w. 21 <
2T,
= exp (-¹)
< exp
2T,,3
exp(1)
Then, summing up the probabilities, we can bound the total probability as follows:
Σ. W
21 <00
e(M + +1)
e (log T2 log Ti)
P E [T),
exp(1)
log 3 exp()))
exp /
where the last inequality is due to the definition of M flog,3
T 7
Notice that when 1 > 2,
log 3 log ( > J. so we can further upper bound the probability as:
W
21
el (log T2 log Ti)
e
PP
J&E (Ti, T2).
E 0 <
+
(9)
exp(1)
expl
36

---

Finally, combining the two bounds Eq. Lemma. Das follows:
8 and Eq. 9 together, we can prove the first result of
As (Ti, Tel. W
21
T2 Ti el (log T2 log Ti)
min
exp(1)
exp(l)
expl)
Eq. (4b) of Lemma. 3 Next, we prove Eq. 4bb of Lemma. 3 Our result is only based on performing
union bound, but can also modify the proof of Eq. (4a) with peeling trick prove Eq. (4b).
However, the result from peeling trick is no better than simply performing union bound, at least not order-wise better. So for simplicity, we apply union bound to the probability follows:
Σ1_1 W
21
IP
3s E [T1, T2).
+ 8 0
=P
E
[T. T2].
W + 21s + ós $ 0
P
8 J,
W3 2 + 8z E
-=
t=1
P
Σ
W: + 23l 83 <
Then, we can apply Hoeffding's ' inequality to upper bound each probability as follows:
(v2jl+ + 6j)
P
22(+ W + ōj =0)
E exp
2j
22l + 2 2jlōj 82
=xx
2j
exp( S/2 exp (1 + 6v 2717)
where the last inequality due to j > Ti. So summing up all the probabilities, we can bound the anytime concentration as:
Σ
W
21
exp( 1
P
e
[2],
& 0
<
8
j= exp (1 8n 2
8" 2
1
exp(
exp (1 Sv27(()
exp
2
4
8 8cc cxp
(VI+ 1
11 51
2
where the last step is due to e- 22 2 of Lemma. 3
8²
when 5 E [0, v3.. Then we finish the proof of Eq. 4bb)
2
Eq. (4c) of Lemma. 3 Finally, we prove Eq. 4a of Lemma. 3 which bounds the summation of
probability for deviation events over the time horizon. Since we can bound the probabilities when & & y by as follows:
8 >
we define
#2 > Ti. Then,
W
21
Ta
W
21 3 8 8)
PPP
8
7
Ti
P
1-1
s
-= T
When > [y/, we have:
21
8 /
T So, for each probability inside the summation, we have:
18
W
21
> 1-1
W
21
2
W 8 1 7 2) ))
P
8
P
8
<
37

---

Then, we can bound the probability with Hoeffding's 's inequality as follows:
21 W
(1-V3) exp
s62
(1 (1- exp ( -VE-
82
P
2
Notice that the upper bound function exp(- 2 (V (+))) on the RHS is uni-modal when 8 3> If a function f(s is uni-modal, then we can bound the summation Σx=, with the sum of max, fs)
and integral 5 (())ds. Therefore, putting the upper bound back to the summation, we have:
Ei=1
W +
21
8²
2 (v8 v7)²)
P
8
7
8²
Σ
(V3 v3)²²)
exp
h
2
82
(V8- vン)²)
$1
+
exp
ds
2
+
8²
So the whole term can be bounded by:
22
Σ W.
21
v V2T7
21 +
4ml
+2
2
77
TT,
6
8²
s-Ti
which completes the proof of Lemma. 3
D.2 Proof of Lemma. 5
We only prove the inequality when P. & μ. The other inequality can be proved exactly the same way. For every À E R, let (A) log [[xxp(XXx)] which well-defined and finite by assumption. Let W = and for > 1, we define W.A = exp (AS, (A). We show that (W>), s31 W.). In fact,
is a
martingale with respect to the a-flld F, = a (W1,
IF
E [exp (AS, + AW, s+1 8Φ (A) - (A)) [FA]
= exp (AS, - s (A)) E [exp (AW - oz( [F.]
W.* E [exp (AW [11
E Exxp [AX]]
-WA
where the second equality is because S, is measurable w.r.t. F., and the third equality uses the fact that s+1 independent w.r.t. F.. Th last equality is due to the i.i.d. nature of W1 and W Ws+1. Let
E [0, [4] be such that KL /1) ö/s, and let A(x)) = f - A". It is worth-noting that since H a monotonically non-decreasing function since its inverse function j = (()) is monotonically non-decreasing. So we have A(x) < 0 since & μ.. Observe that:
8 s¹
B. E p. KL (H. 11) >
and, x e KL (L p)
Then it holds that > P... Notice that for natural parameter exponential family, (A) b(A + 0²) - b(0*). Hence on the event (i, < μ1 o {sKL (Me, 14) > 5), we have:
X(z)a - (A(x)) > X(rx - (A(z)) = x (0 - 0*) - b(00) + b(0") = KL 1)) =
where the first inequality is because X(x) < 0, and the second last equality uses the expression KL divergence for natural exponential families. Putting everything together, we have:
X(r) - (n()(z)) 8
(ū. & uu, sKL (ps, n)) > 8) <P
IP (W>(.)> =6) 8)
E [[ exp( -5),
38

---

where the last inequality uses Markov inequality. Since w:(x) is martingale, we have:
P P & n. sKL (Ma, p)) = 8) & E[W, exp(-5) cxp(-5).
D.3 Proof of Lemma 6
We only prove the inequality when jis & μ.. The other inequality can be proved exactly the same way. The proof of Lemma/ partly resembles the Proof of Lemma. 5 However, to show an any-time partly
concentration bound, we need either the union bound or a peeling trick. We first apply union bound as follows:
P (3 T2,T2),. n. sKL (Ts. 11 > 1) &
Σ
PP ( & sKL (Ns. 2 1)
=
<(T - exp((1),
which obtains the first term in the RHS Lemma. Next, we apply the peeling trick. For ev- cry À E IR, let (A) = log E[exp(A.X) AX1)] which is well-defined and finite by assumption. Let W = and for 8 > 1, we define W = exp (AS, so²x Recall that (W²) e31 is a mar- tingale with respect to the o-field Fe o(W,, W.). Take 3 > 1 to be a constant. Let M = [log J. we apply peeling method and divide the time horizon over exponential grids
[T,, T.. (T. T1 ... [T 3M .T2] as follows:
(3ss T.]. B. & n, sKL (Me, 1) 2
Σ PaSE [718 11 P. sKL (Pas (1) 2 l).
Let 8; = Ti and let a & such that sKL(x, p)) = I. let A(x) = 0" 0t < 0. Then, we have KL(x, (u) = ((x)a (n()(=)). Consider = such that 2j < and KL
so we have when
s [s;, 8;+1
1 KL(z+11,))
KL(
8i+1
So we can conclude that n. & 2 Also, we have:
1
1
11
KL(2++1.14-
3
8i+1
8 8:
3
Therefore, we have:
- - (M((2(1))) > -(z+11)2411-000 ((((((2+1)) = KL(2+1,14)
Bs
So we can bound each probability as:
1)
1
P (3s E [2,, 2111. As & μ. sKL (Te. 1)) > 8) <P 1(31+1)7.- - (x(A(((+2))
Bs
=P [W exp (b))
( exp 1 )
where the last inequality uses Markov inequality. Since W (=++i) is martingale, so we have:
P (Bs e [24,2411:PP P. μ, sKL (p., n)) > 8) E[ (a exp (-+)= exp(l)'
where in the last step, we choose B E Then, summing up the probabilities, we can bound the total probability follows:
(AsE E (Ti, T2), Po & ur, sKL (Ds, > 1) &
M
e(M+ + 1) e e(log T2 llg Ti) exp(1)
e cxpl' 1'
exp(l)
log B cxx(())
39

---

where the last inequality is due to the definition of M = |log, 711. Notice that when / > 2. J. so we can further upper bound the probability as:
log 3 log [
el (log T2 log Ti) IP (3 E (Ti, Ms Ps & n4 sKL (Pss 11) 2 1) & exp(1)
+
(10)
expl'
D.4 Proof of Lemma. 7
Our proof is based on the analysis of Theorem. 2 of [12. For any pair of means 2, [0, 1J. define KL KL+(x, v) KL(x, l axy- Then for fixed under event (UCB, > μ²) we have either μ' ps. or nu > nt but sKL(Es. n²) L. So in general we can conclude that sKL aKL*tppp ("a, & l. Then we can bound the sum probabilities as follows:
T Σ
T1 P (UCB, 3 11) & Σ PP (sKL* (Mx, (sKL=(pss &1).
Define y (1+e)t
(L*(u.p") KL(u,y then if Ti > % we can bound the first 7/ terms in the summation
(1+e)t
with 1. If otherwise Ti < y, the whole summation is bounded by y. So without loss with generality, assume < Ti and let E > 0 be a constant, we have:
IP (sKL + (') ()) +
Σ
P (sKLL*
& (A.. P(sKL*(Ho.'d'
s-1y
Ti
< +
Σ
P (>KLL* (po. & E
s-1
Ti
( & KL(H,
=7 +
Σ
P
KL
1+
where the second inequality is due to KL (jx, 1²))
0. For any 8, let r(s) e (M, such that we have is 3 r(s). Hence,
KL(r(e), = KL(m.() KL (KLt(Ws;HH) < lte
KL(u.')
1tz
(L(H,)') P KL( > KL(r(e), & exp((skL(r(e)),
TP (K.t &
1+e
where the last inequality uses Lemma.
5
So we can bound the sum of probabilities as follows:
20
exp(=>kL(r(e).nu)
(sKL+ (B., +)) x exp(-sKL(r(e), p)) < 1-
Σ
1-
Notice that exp(- exp(->kL(r(E)),u))
exp (- (1 (1t+=))K(((())))) KL(U.n))
T-1)(s), where 81(e)
(L(t))(()(E))a) Let B2(E) = (=xp(-KL(r(e)wn)) It is easy to check that r(e) 0(e), so KL(Hn)))
we have (e) (E22) and BB(c) ((= So we have:
T
T
(1 (1+e)l B2(e)
Σ
P (UCB, > w/)
Σ P (SKL &1) &
KL(H. TBite)
Remark: Let = 1 we have:
T
P (UCB, n²) (1 e]
32(5)
1+1
v7
$ KL( n1)
+0
KL(H,)1) (B)(6)
exp (Vl)
40

---

900
220
EOGPUU
200
T0CP
250
USB
TAS-EIC
180
TAG-TTC
160
200
Regret
Regret
40-0OCP
120
100
100
60
0
10/
10'
10'
10"
1c
10'
15
Number of Rounds
Number of Rounds
(a) Gaussian Bandits
(b) Bernoulli Bandits
Figure 2: Regret performance in bandit models with arms.
E
Numerical Experiments Beyond 2-Armed Bandits
In this section, we present numerical experiments based on bandits with more than two arms. We consider four armed bandit model with expected rewards [0.7, 0.2, 0.2, 0.2]. We study the cumulative regret performance of all our proposed algorithms, i.e., EOCP in Algorithm. T EOCP-UG in Algorithm. - and KL-EOCP in Algorithm. 3 with both Gaussian and Bernoulli rewards. Since some baseline algorithms we chose Section. 6 (e.g.. DETC and BAI-ETC) does not directly generalize the multi-arm model, we replace them with DETC-K 23 and TAS-ETC respectively, where the TAS-ETC algorithm first uses the famous Track and Stop [36] algorithm to identify the best arm and commits we also compare our algorithms to the Action-Fllimintionn algorithm
for the rest of horizon. Additional to all other baselines used in Sec. 6
42 which provably has both Olog T') regret and O (log 7)) commitment time. We choose the reward all sub-optimal arms be the same value so that BAI based algorithms can utilize a closed form expression to solve the optimal arm pull fraction w* and does not need to solve non-convex minimax problem. We choose Ap to be 0.5 for EOCP and KL-EOCP, and the results are shown in Fig. and averaged over 10 iterations.
In both Gaussian and Bernoulii bandits, observe very similar trends compared to Fig. T in two- armed models. the TAS-ETC algorithm and DETC-K algorithm incurs high regret over the total time horizon due to their aggressive exploration the beginning of the trials, similar the performance of BAI-ETC and DETC in 2-armed models. The Action Elimination algorithm incurs even larger regret because of its almost uniform sampling rule the beginning of the trials. It selects sub-optimal actions even more often than BAI based algorithms and could not identify the optimal action as quickly. On the other hand, our proposed algorithms take more delicate exploration strategy and result in lower regret, which indicates that the EOCP algorithm and its variants generalize well beyond two-armed bandit models. The everexxploration phenomenon is also witnessed in this experiment the UCB algorithm and the KL-UCB algorithm continues to explore sub-optimal actions even after the EOCP algorithms have identified the best action. The regret of UCB algorithms continues to increase during the whole time horizon, which shows that over-exploration is common and fundamental issue in optimistic algorithms. Preventing ever-exploration will significantly boost the performance of algorithms not only in bandits but also in other online decision- cocision-mmaing problems.
41


Reviews:
[{"review_id": "aoqGZdRxa0", "reviewer": "Reviewer_tQKP", "summary": "The paper delves into the study of the 'Explore Then Commit' (ETC) policy, where the algorithm is divided into two stages: exploration and commitment. During exploration, the algorithm is permitted to switch actions, while the commitment phase restricts the algorithm to pulling only the commit arm. The primary objective of the algorithm is to reduce the expected commit time, denoted as $T_c$, and ensure that at time $T_c$, $\\hat a \\neq a^*$ holds true with a probability of $O(1/T)$. \n\nThree variations of the ETC policy are introduced in this paper: EOCP, EOCP-UG, and KL-EOCP.\n\nFor EOCP, it's structured for a known gap setting, achieving regret in the order of $2\\log T/\\Delta_i$. The authors assert that this outcome is asymptotically optimal. However, this claim appears to be incorrect. As per reference [On Explore-then-Commit Strategy], the asymptotic optimal regret for a known gap should be $\\log T/(2\\Delta_i)$. Furthermore, the authors have not discussed this setting's reference in a comprehensible manner. For instance, DETC with a known gap achieves exact asymptotic optimality.\n\nFor EOCP-UG, the authors show that it achieves asymptotic optimality with a commit time of $\\log^2 T$.\n\nAs for KL-EOCP, it necessitates knowledge of certain parameters for the design of the pre-determined stopping time.\n\nIn summary, the claim that the EOCP and KL-EOCP algorithms are asymptotically optimal appears to be overstated. The upper bound for EOCP-UG and its associated lower bound is the same as DETC. As for the lower bound, the assumption seems excessively strong. The authors did not clearly indicate whether algorithms must adhere to the equation given in Line 241.\n\nPrimarily, this paper targets two-armed bandit problems, focusing on asymptotic regret. However, I am intrigued by the finite-time bound. I would appreciate an algorithm that is not only asymptotically optimal but also demonstrates a robust finite-time bound. In addition, the paper only considers a fixed horizon T setting. What about the case with an unknown $T$? From my understanding, DECT and its variant [Almost Optimal Anytime Algorithm for Batched Multi-Armed Bandits], are also suitable for an unknown T setting. Furthermore, the necessity of the assumption in Line 141 is not clearly articulated and requires clarification.\n\nRegarding experimental results, the performance of ETC and DECT presented in this paper is inconsistent with previous papers. This discrepancy might be due to parameter adjustments in these algorithms. I would appreciate seeing empirical results with parameter tuning for both ETC and DETC.\n\n----\n\n# At the end of discussion phase\n\nThe authors fail to address my primary concerns. Below, I elaborate on these issues:\n\n1. Line 174 of the manuscript asserts that in the pre-determined setting (where the gap $\\Delta$ is known), $\\frac{2\\log T}{\\Delta}$ is asymptotically optimal. This claim is misleading. Algorithm 4 in reference [21] shows that in the pre-determined setting with $T_c = \\log^2 T$, there exists an algorithm with a regret of $\\frac{\\log T}{2\\Delta}$. Moreover, the known lower bound (Theorem 6 in [20]) for known gap setting is $\\frac{\\log T}{2\\Delta}$. Therefore, stating $ \\frac{2\\log T}{\\Delta}$ as asymptotically optimal is an overstatement. \n\nIn their response, the authors attempt to equate the lower bound of the pre-determined setting with the lower bound of the known gap setting in the ETC strategy [20]. This comparison is problematic and has the potential to mislead other readers. Specifically, Table 1 in the authors' response erroneously claims that $4\\log T/\\Delta$ is the lower bound for the known gap setting, whereas this is actually the lower bound proven for the **unknown gap** setting in Theorem 4 of [20]. Additionally, they assert that $2\\log T/\\Delta$ is the lower bound for the known gap and pre-determined settings, which contradicts Algorithm 4 in [21] that shows regret $\\frac{\\log T}{2\\Delta}$. \n\n\n2. As I pointed out in my initial review, DECT [21] (Algorithm 5 and 2) can be directly applied to the unknown gap setting. The results for DECT in an unknown gap setting are identical to those presented in this paper.\n\nGiven the paper's significant overstatements and the paper's limited contributions, I am revising my score from 4 to 3.", "questions": "Please refer to the Summary.", "limitations": "The main consideration of mine is that the proposed algorithm considers asymptotic bounds other than finite $T$ (probabily unknown). This limits the contribution of the paper heavily.", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "In this paper, the authors propose an algorithm called Explore Optimistically then Commit Pessimistically (EOCP) to solve the Regret Optimal Best Arm Identification (ROBAI) problem. It first uses an optimistic modified UCB algorithm to explore actions with a slightly larger exploration function , and then commits to actions according to a pessimistic LCB algorithm when the exploration ends. The main contributions include designing new stopping rules with both pre-determined stopping time (vanilla EOCP) and adaptive stopping time (the EOCP-UG variant), which provably balance the trade-off between regret minimization and optimal action identification", "weaknesses": "Please refer to the Summary.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the comments/suggestions and included a detailed response below. We also would like to point out a couple of misunderstandings the reviewer had in the preliminary review (see 1 and 2 below).\n\n### Limitation of Targeting Two-armed Bandits ###\n\nThe main theorems (Theorem 1, 2, and 4) of our paper are for general MAB with more than 2 arms. Even though our Theorem 3 focuses on a 2-arm case, it can be generalized to models with more than two arms. \n\n### Limitation of Asymptotic Regret and Lack of Finite-time Bounds ###\n\nOur asymptotic regret guarantees (Theorem 1,2 and 4) are derived from the finite-time bounds, specifically,  the bounds in Theorem 5, 6 and 7 in the complete version (included as the supplementary material of the original submission). We chose to keep the asymptotic results n our main body due to its simplicity but we are happy to add the finite-time bounds to the main body as well.\n\n### Unknown $T$ ###\n\nAny algorithm for ROBAI should satisfy the two properties : (1) the termination time $T_c$ of exploration (the commitment time) is a stopping time (either pre-determined or depends on the samples before $T_c$). (2) the confidence of best arm is $T^{-1},$ in order to guarantee regret optimality. Theoretically, it is impossible to design an ETC algorithm satisfying the above two properties without knowing $T$, because no matter when the agent stops exploration and what confidence $\\delta$ it holds, an adversary can always choose $T$ large enough such that $\\delta> T^{-1/2}$, which violates property (2). \n\nThe variant of DETC works for an unknown $T$ because its exploration termination time is not a valid stopping time. In their algorithm, they guess $T$ in epochs. In the $r$-th epoch, they assume $T=2^r$ and perform an exploration period with a commitment period. If after $t=2^r$, the interaction continues, they will re-guess $T=2^{r+1}$ and consider the commitment period in the $r$-th epoch as part of the exploration. In other words, the \"commitment\" continues to change in their algorithm. For our problem, once a commitment is made, the agent cannot change the decision. However, If we don't require $T_c$ to be a stopping time and allow the agent to change the commitment as in DETC,  it is straightforward to adapt our algorithms to the unknown $T$ setting using the exact same idea. The theoretical guarantees can also be straightforwardly extended.\n\n### Overstating Asymptotic Optimality in Pre-determined Setting ###\n\nWe respectfully disagree with the reviewer on this because the pre-determined setting is more difficult than the known gap setting studied in [20,21], and thus $\\log T/2\\Delta$ is not a tight lower bound. \n\n(1) Algorithms in the known gap setting, e.g., SPRT-BAI [20] and DETC-KG [21], use the exact value of $\\Delta$ to design all sampling, stopping, and action decision rules so that the regret performance can be lower than $2\\log T/\\Delta$. Changing $\\Delta$ to any other value (even a slight mismatch) would harm the performance. The is also implied by the proof of Theorem 6 from [20] that one would need the exact value of $\\Delta$ to achieve $\\log T / 2\\Delta$ lower bound. Our algorithms in the pre-determined setting only requires a value smaller than $\\Delta$ and only use it in stopping time. The theoretical regret performance would still be the same if we under-estimate $\\Delta$. \n\n(2) In the known gap setting, the algorithm can use reward samples from exploration to design the stopping time, but in the pre-determined setting, $T_c$ must be pre-specified before the exploration starts.\n\nBased on the two comparisons above, we believe $\\log T/2\\Delta$ is not achievable in the pre-determined setting. In fact, this setting is more comparable to the fixed-design setting [20] whose regret lower bound is $4\\log T/\\Delta$. But it requires all actions to be pre-specified before exploration, which is harder. Overall, we believe $2\\log T/ \\Delta$ is a more valid lower bound since the algorithms do not entirely depend on $\\Delta$, i.e., any hyper-parameter lower than $\\Delta$ would suffice. We compare all scenarios as follows:\n\n```\n| Setting                 | Lower Bound       | Knowledge of $\\Delta$ (Where it is used)     | Stopping Rule |\n| ----------------------- | ----------------- | -------------------------------------------- | ------------- |\n| Fixed-Design            | 4 \\log T / \\Delta | Yes (Stopping Time)                          | Pre-determined|\n| Known Gap               | \\log T/ 2\\Delta   | Yes (Sampling, Stopping, Arm Identification) | Adaptive      |\n| Unknown Gap             | 2\\log T/\\Delta    | No                                           | Adaptive      |\n| Pre-determined Stopping | 2\\log T/\\Delta    | lower bound of $\\Delta$ (Stopping Time)      | Pre-determined|\n| Adaptive Stopping       | 2\\log T/\\Delta    | No                                           | Adaptive      |\n```\n\n### Lower Bound Condition ###\n\nWe require all ROBAI algorithms to satisfy the condition in line 241. It is not excessively strong because ROBAI focuses on asymptotic regret optimal algorithms, i.e., the regret dominating term is $2\\log T/\\Delta$. These algorithms naturally satisfy the condition in line 241 with a $c<1$.\n\n### Empirical Results with Parameter Tuning  ###\nWe tune the parameters for BAI-ETC and DETC, and the results are presented in our uploaded pdf file. After tuning $T_1$ and the confidence bounds, the performance of DETC beats BAI-ETC and almost matches UCB, but not our algorithms.\n\nGiven we indeed provide general results for bandits with more than two arms and also finite-time bounds for all algorithms in the original paper, which are the main limitations the reviewer is concerned about, we would appreciate it if the reviewer could re-evaluate the rating and review based on our response. We are happy to address any additional questions and concerns."}, {"review_id": "MqFigSrrwg", "reviewer": "Reviewer_WGiE", "summary": "The work studies how to design an algorithm with an asymptotically optimal regret rate such that it will also commit to the best arm with high probability after a stopping time (e.g., O(logT)). The paper proposes two algorithms in the Gaussian bandits setting: one with pre-determined stopping time (EOCP), which requires the knowledge of the minimum reward gap, and another with adaptive stopping time (EOCP-UG). The authors prove both algorithms are asymptotically optimal and will commit to the best arm with confidence O(1/T) after O(log(T)) and O(log^2(T)) respectively. The paper further shows the corresponding lower bounds for commitment times (expected stopping time) and finds EOCP is sample optimal and EOCP-UG is nearly sample optimal. In addition, the authors extend the EOCP to KL-EOCP for general bandits, whose commitment time also matches the lower bound.  \n", "questions": "See above.", "limitations": "Na.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1) In general, the studied question is interesting and the paper is well-written and easy to follow.\n\n2) The proposed algorithms are novel which are based on well-designed stopping rules.\n\n3) The theoretical results and the proofs are clear. The numerical results also show the advantages of the proposed algorithms compared to the benchmark algorithms, including UCB and BAI algorithms in the literature.\n", "weaknesses": "1) The problem setting is the fixed-confidence BAI setting (note for the setting of EOCP, the stopping time is pre-determined by the algorithm instead of by the environment). It would be great if the authors can give some discussions on the fixed budget setting (the stopping time is given), like the challenges of extending the proposed algorithms. \n\n2) In the general bandits setting, the authors only extend EOCP to KL-EOCP, which needs the KL_min of arms. The authors demonstrate if KL_min is not known, an extension of EOCP-UG can deal with this setting.  But there is no pseudo-code or provable results on it. More details or discussions would be helpful.\n\nMinor comments:\n\nIn Table 1, it might be helpful to add another column ‘Setting’, since ‘Optimality’ is a bit confusing for explaining ‘Gaussian’ or ’General’.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewers for the precious time they spent on reviewing our paper. We discuss the points raised by the reviewer below.\n\n### Fixed-budget Setting ###\n\nWe thank the reviewer for the great question! Generally, our algorithm is not designed for the fixed-budget setting because EOCP has to decide the stopping time based on the problem parameters. For fixed budget, the goal is to find the best arm as accurately as possible with the given budget. The budget does not adapt to the problem parameters but the decision and learning process do. The challenge of extending our algorithm to the fixed budget setting is that it is not clear whether our algorithm makes optimal decisions when the budget is different from the stopping time we need to have.  \n\nFor example, in a two-armed Gaussian bandit example, if the stopping budget $T_c$ is much smaller than our stopping time, then the algorithm may have to explore more aggressively than EOCP since the commitment needs to be made much earlier. However, if $T_c$ (the budget) is larger than the stopping time, then our algorithm can be used to stop early without using the full budget. It is an interesting question whether we should use the remaining budget for exploration or commit without further exploration. As we can see from the numerical example in the paper, over-exploration hurts the system's performance. This somewhat counter-intuitive observation could be an interesting contribution (or at least an implication) to the fixed budget setting. \n\n### KL-EOCP with Unknown Gap ###\n\nWe provide a short psudo-code and theoretical guarantees below:\n\n\n***\n> ### Algorithm: KL-EOCP-UG ###\n\n> 1: Initialize by pulling each arm once.\n\n>2: **While** $\\max_a \\min_a' N_{t-1}(a) - l N_{t-1}(a')\\leq 1$ **do**\n\n>3: &nbsp;&nbsp;&nbsp;&nbsp; take action $A_{t+1} = \\arg\\max_a\\mathsf{UCB}_{t-1}(a)$\n\n>5: **end while**\n\n>6: Let $T_c = t-1$, $\\hat{a} = \\arg\\max_{a} \\mathsf{LCB}_{T_c } (a)$\n\n>7: Commit to $\\hat{a}$ for the rest of time horizon.\n***\n\nwhere $\\mathsf{UCB}_t(a)$ and $\\mathsf{LCB}_t(a)$ are defined according to Line 4 and 7 in Algorithm 3. We can also derive the following theoretical guarantee for this algorithm which requires additional assumptions on the $b(\\theta)$ function defining the KL-divergence (Line 270):\n\n***\n> ### Aymptotic Optimality for KL-EOCP-UG ###\n\n>If we choose $l = \\log(T) + 4\\sqrt{2\\log(T)}$, suppose $b(\\theta)$ is strongly convex and smooth, the expected regret of the KL-EOCP-UG algorithm is asymptotically upper bounded by:\n\n>$\\lim\\sup_{T\\to\\infty} \\frac{Reg(T)}{\\log T} \\leq \\sum_{a:\\Delta_a >0} \\frac{\\Delta_a}{\\mathsf{KL}(\\mu_a,\\mu_1)}$\n***\n\n### Table 1 ###\n\nWe will add another coloum in table 1 to make sure there is no confusion. We thank the reviewer for pointing it out.\n\nWe hope that our response addresses the reviewer's questions regarding the fixed-budget setting and the KL-EOCP algorithm with unknown gaps, and we are happy to answer any additional questions or concerns. We would also be grateful if the reviewer could re-evaluate the rating and review based on our response."}, {"review_id": "SI6twuzaEf", "reviewer": "Reviewer_T4df", "summary": "This paper studies the classical multi-armed bandits problem with the goal to design algorithms achieving tight regret bound and tight sample complexity to identify the best arm simultaneously. To this end, three algorithms are proposed based on upper confidence exploration and lower confidence commitment for three settings: Gaussian bandits with known and unknown suboptimality gap $\\Delta_{\\min}$, general bandits when suboptimality gap (in terms of KL divergence) is known. It is proved that all the three algorithms enjoy tight regret bound up to the constant in front of the dominating term ($\\log T$), and they also have polylog sample complexity scaled linearly with $1 / \\Delta_{\\min}^2$. There is also a lower bound on the sample complexity given the regret to have a tight constant in the $\\log T$. The lower bound states that the rate of sample complexity is tight when $\\Delta_{\\min}$ is given, and can also be tight when $\\Delta_{\\min}$ is unknown as long as the order of remaining terms in the regret is smaller than $\\log T$.", "questions": "1. Why you only consider the setting where the regret should be constant-optimal while the sample complexity can be rate-optimal. From the perspective of theory, is it possible to obtain both constant-optimal algorithm or constant-optimal sample complexity and rate-optimal regret?\n\n2. How is the identification accuracy of the vanilla UCB algorithm at the step it gets the same regret of EOCP? Is this accuracy comparable to the commitment accuracy of EOCP?", "limitations": "See above.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1.The paper addresses the classical settings of regret minimization and best arm identification problems in bandit theory. The investigation of their combination opens up new avenues for fundamental methods in this field. The paper stands out for its clean and clear presentation, making it accessible to readers and facilitating understanding of the proposed techniques.\n\n2.The paper introduces several novel techniques that enable the simultaneous bounding of regret and sample complexity. The incorporation of lower confidence bound (LCB) commitment following upper confidence bound (UCB) exploration is a particularly interesting departure from the traditional approach of UCB commitment. This novel technique offers fresh insights and potential improvements in bandit algorithms. Additionally, the stopping criterion employed in the unknown gap setting is highly appreciated in theory by leveraging the deep connections between the number of pulls across different arms and the total pulls of suboptimal arms.\n\n3.The analysis of lower bounds in the paper sheds light on the fundamental limits and trade-offs involved in identifying the best arm. These findings provide valuable insights into the design of algorithms, emphasizing the need to balance regret and sample complexity. The paper's techniques offer the potential for achieving a near-perfect balance between these two factors in practical applications of multi-armed bandits.\n", "weaknesses": "1. The unified achievement of both optimal regret and optimal sample complexity is an important problem in theory and application. However, I am not fully convinced of the motivation of this paper to study the constant-level tight regret bound but rate-level tight sample complexity. It somehow looks like a beam search of different settings in multi-armed bandits that are not fully addressed, since algorithms with both rate-optimal regret and rate-optimal sample complexity have been extensively studied. The vanilla multi-armed bandits is a fundamental model in theory, and the algorithms of multi-armed bandits provide prominent insights in many other problems. However, the UCB and LCB algorithms, which are conceptual in nature, require significant domain-dependent modifications to be applicable in real-world scenarios. This lack of naturalness in the setting detracts from the paper, despite the appreciation for the introduction of new techniques.\n\n2. Two of the three proposed algorithms require the minimal gap to be known, which I believe is not very possible in application (except for the synthetic task). There are two reasons for it. Consider some tasks that aim to identify the user's favorite items: the expected reward is 1 if the item is liked by the user, and 0 otherwise, with some noise to model random attributes of the user. In this case, the gap is known and large, which greatly simplifies the problem. In general, it takes a very short period of time to find the favorite items even in the presence of noises, so it is totally acceptable that the regret is rate-optimal instead of constant-optimal. When the gap is not determined manually and small, it is not likely one can obtain the exact value of the gap. People often guess this gap by some binary search routines. However, the Algorithm 2 suffers a $\\log^2 T$ sample complexity, where $\\log T$ is the dominating term. This means the overall sample complexity of this algorithm is even not rate-optimal, though the regret is constant-optimal. It would be better in this case to use other methods such as elimination to keep both regret and sample complexity rate-optimal.\n\n3. The experimental results presented in the paper have limitations in their scope. Firstly, comparing and plotting cumulative rewards instead of regret would provide a more convincing demonstration, as the sum of rewards and regret is a linear function rather than a constant. Additionally, the experiments should be conducted in more diverse environments, including scenarios with a higher number of arms. The current results do not suggest a significant improvement over the vanilla UCB algorithm, raising questions about the practical advantage of the proposed EOCP and its variants (see the questions below).\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewers for the precious time they spent on reviewing our paper. We discuss the points raised by the reviewer below.\n\n### Motivation of Constant-level Tight Regret but Rate-level Tight Sample Complexity And Contributions ###\n\nWhether it is necessary for constant-level tight regret bound or we could just be satisfied with rate optimal regret bound depends on the application. In some applications it is better to use elimination based algorithms to maintain rate optimality for both measures. However, the applications that motivates our research are those where reward performance is more important than commitment time, even though commitment time is also important. One conceptual example would be investment strategies, where the reward is the profit of a strategy and the commitment time is the time that the company decides on the strategy. In this case, a commitment needs to be made as early as possible but the profit is more important so it makes sense to take more time to make a better decision. The same also applies to people's occupation choices, where the potential career achievement and the commitment time is when one figures out which career he/she wants to pursue. It makes sense that achieving life goals is more important than choosing one's major early. We believe in these cases, rate optimality in regret is not satisfactory enough. The trade-off between constant-level regret optimality and commitment time we discovered in our paper shed lights on these applications. On the other hand, even though the upper bound of Algorithm 2 is $\\log^2 T$, the empirical stopping time is quite close to Algorithm 1 (Fig.2). In general, we don't necessarily disagree with the the comment raised in Weakness 2, but again, which regime is the best model to study is application dependent.\n\nBuilding upon the fundamental MAB model, one major contribution of our paper is to consider three fundamental questions in online learning in a single model: how to explore? when to commit? which arm to choose? Through our stylized model, we demonstrate that these three questions are fundamentally related. In the current literature, the first question is studied under online MAB, the third question is considered under offline MAB and the stopping time was not well studied directly. We are hoping our model motivates the research interest in looking at these three questions together instead of individually. \n\n### Both Constant Optimality in regret and sample complexity? ###\n\nIt is possible to achieve constant optimal sample complexity with rate optimal regret. Take Gaussian 2-armed bandit for example, this can be done by an explore-then-commit algorithm which uniformly samples two arms and starts commitment once enough statistical separation can be witnessed from the past samples with confidence $T^{-1}$, i.e., BAI-ETC [20]. Its sample complexity is asymptotically $8\\log(T)/\\Delta$ which is constant optimal (compared to Theorem 1 [34]), and its regret is order optimal (Theorem 5 [20]). It is not possible to achieve constant optimality for both, as they require different trade-offs in exploration and exploitation. According to (Theorem 1 [34]), any algorithm to achieve constant optimal sample complexity in Gaussian 2-armed bandits should pull the two arms equal likely in exploration in order to stop early, and this aggressive strategy completely ignores the exploration-exploitation trade-off to maintain low regret. Therefore, it incurs regret asymptotically larger than UCB algorithms (rigorously shown in [20]). Our paper is dual to [20], in the way that [20] contributes to the regret performance of algorithms with constant-level optimality in sample complexity, while we contributes to the sample complexity of algorithms with constant-level optimality in regret.\n\n### Identification Accuracy of Vanilla UCB algorithm ###\nThe vanilla UCB algorithm does not output a best arm for us to commit to, and our proposed algorithm's exploration strategy is in fact the UCB algorithm. One could modify the vanilla UCB algorithm to stop at a certain time, and then makes a decision on the best arm, just like we did in our paper. The accuracy in this case will depend on the design of the stopping time and the decision rule. We remark that our major contribution in terms of the algorithm is to design such a stopping rule and an action identification rule using LCB. We illustrates the improvement of LCB by comparing EOCP to an algorithm which uses the UCB exploration strategy and the same stopping time as our algorithm (which would results in the same regret in exploration), but uses UCB to identify the best arm instead of LCB. The accuracy is compared below:\n\n```\n| Algorithm                | Number of committing wrong arm | Accuracy |\n| ------------------------ | ------------------------------ | -------- |\n| EOCP                     | 11                             | 0.000011 |\n| UCB Explore + UCB Comm   | 17293                          | 0.0173   |\n```\nTime horizon is $10^3$ and experiment is done over $10^6$ iterations. It can be witnessed that LCB provides better accuracy than simple UCB commitment and UCB commitment does not satisfy the required $T^{-1} = 10^{-3}$ accuracy.\n\n### Numerical Experiments with More Arms ###\nWe conducted an experiment in a $4$-armed bandit model to compare our algorithms to existing algorithms in the literature, including an Action Elimination algorithm. The results are presented in our submitted rebuttal pdf file. In general, the observations we see in 2-armed bandit models can still be witnessed in this $4$-armed bandit model, which demonstrates the regret improvement of our algorithm and the over-exploration phenomenon is not unique to the 2-armed case.\n\nWe hope that our response addresses the reviewer's concerns are happy to answer any additional questions or concerns. We would also be grateful if the reviewer could consider reevaluating the review and rating based on our response.\n"}, {"review_id": "8lALAL2Nmb", "reviewer": "Reviewer_SqBM", "summary": "This work focuses on simultaneously achieving regret minimization and best arm identification in multi-armed bandits, which is called Regret-Optimal Best Arm Identification (ROBAI). That is, the goal is to identify with high probability and as fast as possible / within a certain time frame the optimal arm, and play until round T. In practice, authors propose three algorithmic contributions, which have guarantees on the cumulative regret, the time before commitment to exploiting a single arm (called stopping time in the paper) and the error on the identification of the optimal arm. The first two algorithms are asymptotically optimal regretwise for Gaussian bandits, and respectively tackle the pre-determined stopping time case and the adaptive stopping time case. They consist in exploring arms using the UCB principle, and committing to the arm which maximizes the LCB. The last one is a variant of the previous algorithms which achieves asymptotical regret optimality for subgaussian distributions, by leveraging KL confidence intervals.", "questions": "-  What does ROBAI bring more than classical regret minimization (i.e., why playing pessimistically at the end of the sampling phase is better) in the predetermined stopping time setting?", "limitations": "This paper deals with theoretical work, and does not raise significant concerns about negative impacts.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- Originality: This paper tackles an interesting problem which has been seldom considered. Although the algorithms reuse well-known principles (UCB / LCB), their analysis allow to prove very good results (regret optimality, interesting bound for adaptive “stopping” time). Table 1 is clear and shows that the work is well-grounded in prior literature.\n- Quality: The results seem technically sound, although I did not check the appendix in detail.\n- Clarity: The submission and the proof sketches are clearly written.\n- Significance: This paper provides and substantiates an interesting insight on the behavior of UCB algorithms with respect to over-exploration", "weaknesses": "- Significance: I am not 100% convinced about the real-life applications of this framework. If the “stopping” time is fixed because of budget limits (predetermined setting), I don’t see what ROBAI brings more than classical regret minimization (i.e., why playing pessimistically at the end of the sampling phase is better), especially since it is not feasible in practice, as the related algorithm requires the knowledge of Delta_min to be optimal. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewers for the precious time they spent on reviewing our paper. We discuss the points raised by the reviewer below.\n\n### Clarification on Pre-determined Stopping Time and Fixed-Budget ###\n\nWe thank the reviewer for raising this question, and we would like to make a clarification on how the pre-determined stopping time setting is different from the fixed budget setting usually considered in the literature. The stopping time $T_c$ in our setting is chosen based on the parameters of the problem instead of being enforced by the environment. Generally, our algorithm is not designed for the fixed-budget setting because EOCP has to decide the stopping time based on the problem parameter. The goal of fixed budget is to find the best arm as accurately as possible with a given budget which does not adapt to the problem parameters. It is not clear whether our algorithm makes optimal decisions when the budget is different from the stopping time we need to have. For example, if the stopping budget $T_c$ is smaller than our stopping time then the algorithm may have to explore more aggressively than EOCP since the commitment needs to be made much earlier. However, if $T_c$ (the budget) is larger than the stopping time, then our algorithm can be used to stop earlier without using the full budget to achieve $T^{-1}$ confidence. It is an interesting question whether we should use the remaining budget for exploration or commit without further exploration. As we can see from the numerical example, over-exploration hurts the system's performance. This somewhat counter-intuitive observation could be an interesting implication for the fixed budget setting. \n\n### Comparison to Regret Minimization in Pre-determined Stopping Time Setting ###\n\nWe would also like to make a clarification on how ROBAI is different from classic regret minimization. In ROBAI, we care about the regret performance for the total horizon $[1,T]$, instead of just the regret before the pre-determined stopping time $[1:T_c]$. If there is no commitment requirement, the problem is same as regret minimization with horizon $T$. However, since ROBAI requires the algorithm to commit as soon as possible while maintaining asymptotic optimal regret, and also note that EOCP uses $T_c = \\mathcal{O}(\\log T)$ which is much smaller, the agent must identify the optimal action with sufficiently large confidence ($T^{-1}$) to have good regret in commitment. Playing pessimistic actions after sampling phase ensures selecting the best arm for commitment with this high probability. This guarantee cannot be achieved by simply playing an UCB action in commitment (optimistically selecting the arm which has highest UCB). We conducted an empirical experiment to compare the accuracy of different commitment strategies:\n```\n| Algorithm                | Number of committing wrong arm | Accuracy |\n| ------------------------ | ------------------------------ | -------- |\n| EOCP                     | 11                             | 0.000011 |\n| UCB Explore + UCB Comm   | 17293                          | 0.0173   |\n```\n\nIt can be witnessed that LCB provides better accuracy than simple UCB commitment which ensures low regret. ROBAI with time horizon $T$ is also different from regret minimization with horizon $T_c$ if $T_c$ is fixed due to budget limits. For regret minimization problems with horizon $T_c$, the theoretical regret limit is $\\mathcal{O}(\\log T_c) = \\mathcal{O}(\\log \\log (T))$, which is much smaller than ROBAI with time horizon $T$. To achieve this limit, the UCB algorithm should choose a different optimistic bonus (a bonus $b_t(a) = \\sqrt{\\frac{2l}{N_t(a)}}$ with an exploration function $l$ in the order of $\\log T_c$ instead of $\\log T$). With this much smaller bonus, even though the regret of this algorithm will match $\\mathcal{O}(\\log \\log (T))$, it will not be possible to identify the best arm with $T^{-1}$ confidence at time-step $T_c$ (even with LCB commitment), since the sub-optimal arms have not been explored enough and the empirical reward estimation is not accurate enough. So, ROBAI requires more aggressive exploration compared to regret minimization with horizon $T_c$, but it is less agressive than regret minimization with horizon $T$ as there is an interesting over-exploration phenomenon shown in our Fig.1.\n\nWe hope that our response addresses the reviewer's concerns about the the contributions of ROBAI, and we are happy to answer any additional questions or concerns."}]

Author rebuttal:
We thank the reviewers for their precious time spent on reviewing our paper. To address the questions and concerns raised in the preliminary reviews, we present additional numerical results in the uploaded pdf File. Due to the limited time, we can only provide results with Gaussian bandits, and the results for Bernoulli bandits will be added to the revision.

In the PDF file, Fig.1 is a comparison of EOCP with existing algorithms in the literature under bandit models with more than 2 arms, and Fig. 2 is a comparison of EOCP with the tuned versions of DETC and BAI-ETC. Numerical results show that EOCP and its variants still outperform existing algorithms, with a similar trend as shown in Fig.1 in our original paper. The extended results demonstrate EOCP's ability to generalize to more complex settings.

We hope that our response addresses the reviewers' questions regarding the numerical results of EOCP, and we are happy to answer additional questions and concerns.

Meta-review: This is a paper that simultaneously tackles two fundamental problems in bandit theory -- regret minimization (and committing to an action after a pre-determined stopping time) and best arm identification. Both have been traditionally studied separately, but this paper brings them under the same analytical framework. Reviewers were generally in praise of the theoretical importance of the problem and also the novel use and combination of traditional technical tools. The results are clean and easy to interpret and collectively form a useful contribution to bandit theory. Committing to an action after a fixed stopping time also seems to have some interesting practical applications, but this is of secondary importance to the theoretical contributions contained herein.
Decision: Accept (poster)