Fixed Budget Best Arm Identification in Unimodal Bandits
Authors: Debamita Ghosh
Manjesh Kumar Hanawal
Nikola Zlatanov
Venue: Accepted by TMLR ()

Abstract: We consider the best arm identification problem in a fixed budget stochastic multi-armed bandit in which arm means exhibit unimodal structure, i.e., there is only one local maximum. We establish that the probability of misidentifying the optimal arm within a budget of $T$ is lower bounded as $\mathcal{O}\left(\exp\left\{-T/\bar{H}\right\}\right)$, where $\bar{H}$ depends on the sub-optimality gaps of arms in the neighborhood of the optimal arm. % where $\bar{H}\leq 2\Delta^{-2}$. In contrast to the lower bound for the unstructured case, the error exponent in this bound does not depend on the number of arms $K$ and is smaller by a factor $\log K$, which captures the gain achievable by exploiting the unimodal structure. We then develop an algorithm named {\it Fixed Budget Best Arm Unimodal Bandits ( FB-BAUB)} that exploits unimodality to achieve the gain. Specifically, we show that the error probability of \algo{} is upper bounded as $\mathcal{O}\left(\log_2 K\exp\left\{-T\Delta^2\right\}\right)$, where $\Delta$ is the gap between the neighboring arms and $\bar{H}\leq 2\Delta^{-2}$. We demonstrate that \algo{} outperforms the state-of-the-art algorithms through extensive simulations. Moreover, \algo{} is parameter-free and simple to implement.

Published in Transactions on Machine Learning Research (04/2024)
Fixed Budget Best Arm Identification in Unimodal Bandits
Debamita Ghosh
debomnita ghansiittt.goohssiii
IITB-Monash Research Acodemy Indian Institute of Technology Bombay, India
Manjesh K. Hanawal
mhanawal
Department of Industrial Engineering & Operations Research Indian Institute of Technology Bombay, India
Nikola Zlatanov
n.dlatenoon@innopolli..r
Faculty of Computer and Engineering Sciences Innopolis University, Russia
Reviewed OpenReview: https: opwnrevveee.e..e..eemmmmm net/ formm? wwwppp/WWhee//hhoteaaaaegae
Abstract
We consider the best arm identification problem a fixed budget stochastic multi-armed bandit in which arm means exhibit unimodal structure, i.e, there only one local maximum. We establish that the probability of misidentifying the optimal arm within budget of T is lower bounded O (exp {-T/H}), where H depends the sub-optimality gaps of arms in the neighborhood of the optimal arm. In contrast to the lower bound for the unstructured case, the error exponent in this bound does not depend on the number of arms K and is smaller by a factor log K, which captures the gain achievable by exploiting the unimodal structure. We then develop an algorithm named Fized Budget Best Arm Unimodal Bandits (FB- (FB-BAUB) that exploits unimodality to achieve the gain. Specifically, we show that the error probability of FB-BAUB is upper bounded as O (logg K expp between the neighboring arms and / < 2A -2, We demonstrate that FB-BAUB outperforms the taate-of-the-rrt algorithms through extensive simulations. Moreover, FB-BAUB is parameter-free and simple to implement.
( (-TA²}) where A is the gap
1 Introduction
Multi-armed bandit (MAB) popular setup to study decisionnmakinng under uncertainty. It. has been applied in drug trials, recommendation systems, auctions, communication networks, and the list is growing, see Bouneffouf & Rish (2019). In MAB, policy is any strategy that sequentially selects arms basod on past observations. The performance of policy is evaluated using criteria such as cunulative regret, simple regret, or best arm identification (BAT), depending the application, refer to Lattimore & Szepesvári (2020) for details. While the policies optimizing cumulative regret balance exploration and exploitation optimally, the policies optimizing simple regret, or BAI, focus on optimal exploration. BAI, the goal is to minimize the sample complexity of identifying the best arm within given tolerance on the error probability (fixed confidence setting) or to minimize the error probability of not identifying the best arm within given number of rounds (fixed budget setting), see (Karnin et al., 2013; Carpentier & Locatelli, 2016; Atsidakou et al., 2022). We focus the fixed budget BAI setting.
The classical MAB setup considers the unstructured case, where reward distributions of the arms are independent with no relation among their means. However, many practical problems exhibit structural properties such as smoothness, linearity, unimodality, and convexity on the mean rewards, which can be exploited to improve the performance of the MAB algorithms (Magureanu et al., 2014; Combes et al., 2017; Yu & Mannor, 2011; Cheshire et al., 2021). Our objective in this paper to develop algorithms that exploit the unimodal structure of the means to improve learning performance.
1

---

Published in Transactions on Machine Learning Research (04/2024)
In unimodality, the arms' means are increasing and then decreasing in the arms' indices, exhibiting change in the monotonicity pattern only at the globally optimal arm. Many real-life applications of unimodal structure arise in network throughput, see Hashemi et al. (2018), sequential pricing, and bidding in online sponsored search auctions, see Yu & Mannor (2011). Unimodality is exploited in Combes & Prouticre (2014); Saber et al. (2020a) to improve the cumulative regret bounds, where it is shown that the regret bound is asymptotically optimal and does not depend on the number of arms. Unimodlity structure is also exploited in Blinn et al. (2021), where the transmitter identifies the best beam in the fixed confidence setting, which is aligned with the receiver's beam in the wireless network. However, in wireless networks where devices (e.g., base stations and mobiles) need to operate synchronously, fixed budget BAT is better suited as the devices can know exactly when to switch from exploration to exploitation and hence require less information exchange for synchronization This simplifies the protocol design. To the best of our knowledge, the fixed budget, BAI with unimodal structure has not been studied in the literature. Also, as noted in Atsidakou et al. (2022), fixed budget BAT is more challenging than their fixed confidence counterparts, and our work fills this gap.
We develop an algorithm named Fixed Budgel Best Arm in Unimodal Bundils (FB-BAUB) to address the BAI problem with the unimodal structure. The algorithm is motivated by the Line Search Eliménations (LSE) algorithm, introduced in Yu & Mannor (2011) and works in phases. In cach phase of FB-BAUB, a portion of the arms is eliminated (~ 33%) based on empirical means of the arms, thereby reducing the search space for the optimal arm in the subsequent phases. For a given budget. T and the number of arms K, we show that FB-BAUB achieves an error probability of the order of Ollog K exp(-TA3) under the assumption of the minimum separation gap between neighboring arms is at least A O. Under the same minimum gap assumption, the best known achievable error probability (by Sequential Halving) is of order O (log K exp (- TA= log for the unstructured case, see Audibert et al. (2010). Thus, by exploiting the unimodal structure, we reduced the error exponent by factor log K. We show that this reduction is the best possible by establishing a lower bound. Thus, we quantify the gain one can achieve by exploiting the unimodal structure. In establishing the lower bound, we generalize the "fipping constructions' of the bandit instance from Carpentier & Locatelli (2016) to include distribution with unbounded support and adapt it to unimodal bandits.
In summary, our contributions are as follows:
We establish a lower bound for the unimodal bandits in a fixed budget BAI setting.
We develop a parameter- probability. We show that the error exponent in the bound does not depend on K. The lower bound shows that the error exponent of FB-BAUB of the right order.
algorithm, named FB-BAUB, and derived an upper bound on its error
We empirically validate the superior performance of FB-BAUB compared the other state-of satte-of-the-art algorithms in the literature that exploit the unimodal structure.
Detailed proofs of all the statements are given in Appendix A.
2
Related Work
The BAI problem is well-studied in the unstructured bandits in both fixed confidence and fixed budget settings, see Mannor & Tsitsiklis (2004); Even-Dar et al. (2006); Kalyanakrishnan et al. (2012); Karnin et al. (2013); Kaufmann et al. (2016); Jamicson & Nowak (2014); Garivier & Kaufmann (2016); Atsidakou et al. (2022); Wang et al. (2021). The authors in Gabillon et al. (2012) develop unifying approach to analyse both settings leading to a meta-algon algoriith that can be applied to both settings. The lower bounds for these settings for unstructured bandits are developed by Chen & Li (2015); Carpenticr & Locatelli (2016); Audibert. et al. (2010).
Improving Cumulative Regret: Several works exploit the structural properties of the bandits to minimize cumulative regret. Abbasi-Yadkoo et al. (2011); Chu et al. (2011); Dani et al. (2008) exploit linearity of observed rewards. The authors in Desa-Bianchh Lugosi (2012); Combes et al. (2015) studied Combinatorial bandits with bandit. feedback exploit the combinatorial structure of the arms to learn the best subset of arms
2

---

Published in Transactions on Machine Learning Research (04/2024)
Unimodal structure is exploited in Yu & Mannor (2011); Combes & Proutiere (2014) to improve the regret performance. Combes & Proutiere (2014) provide lower bound on any policy exploiting unimodal structure and develop an Optimal Sampling for Unimodal Bandits (OSUB) algorithm with a matching upper bound. Saber et al. (2020b) developed algorithms that do not require force explorations as used in the OSUB. The smoothmess of the rewards expressed in terms of Lipschilz conditions are studied by Magureanu et al. (2014); Valko et al. (2014); Hanawal et al. (2015). A generic framework for analysing the cumulative regret of bandits exhibiting structural properties that include linearity, smoothness, and unimodality property is given in Combes et al. (2017). All of the aforementioned works are in the cummlative regret minimization setting.
Improving Best Arm Identification: In the bost arm identification sctting, the authors in Soare et al. (2014); Jedra & Proutiere (2020); Azizi et al. (2022) exploit the linearity structures, and the authors in Kocák & Garivier (2020) exploit the smoothness structures to improve performance of BAI algorithms. The authors in Wang et al. (2021) studied fixed confidence BAT problem and developed Frank- Wolfe-based Sampling (FWS) whose sample complexity matches the lower bounds for a wide class of pure exploration problems. They applied FWS to other structural bandits such as threshold, linear, and Lipschilz, but they did not. consider unimodal bandits. The authors in Garivier et al. (2017) consider threshold bandit problems (TBP), where the mcans of the arms are monotonically incrcasing, and the goal is to identify the set of arms with means above a given threshold. The authors characterise the sample complexity of the TBP in the fixed confidence setting. The TBP is extended to include other structural properties such as unimodality and concavity in Cheshire et al. (2020), and problem-inddependent bounds on the simple regret are derived. The paper Cheshire et al. (2021) extended the analysis of the TBP with monotonicity and concavity to establish problem-dependent bounds.
The lower bounds for the best arm identification are explored in Audibert et al. (2010); Garivier & Kaufmann (2016), and Carpentier & Locatelli (2016). In the fixed budget setting, Audibert et al. (2010) established first lower bound, and it was improved in Garivier & Kaufmann (2016) using 'flipping constructions! Notably, these approaches assume a parametric form (Bernoulli and Gaussian) for the underlying distributions and establish a minimax bound. Further, refining the flipping argument, Carpentier & Locatelli (2016) derived a lower bound that matches with the upper bound of the Successive Reject algorithm introduced in Audibert et al. (2010), thus establishing a tighter lower bound. The case of non-parametric bandits is studied in Barrier et al. (2023), which concentrates on developing instance-indepent instence-indeppndenn bounds for fixed budget scenarios. However, these bounds hold only asymptotically. The above work deals with the unstructured case, whereas we deal with the structured (unimodal) bandits.
Lower Bounds:
Our work is closer to Cheshire et al. (2020), Yu & Mannor (2011), and Carpentier & Locatelli (2016). Cheshire et al. (2020) focuses on TBPs to exploit the unimodal property and provide guarantee on the simple regret, which is different from our setting. The LSE algorithm introduced in Yu & Mannor (2011) provides the PAC guarantees in the fixed confidence setting for a continuous set of arms. The algorithm runs in phases, and the arms played in each phase are selected based on the golden ratio. Though our algorithm adapts the basic idcas of LSE, it differs in how arms are selected and climinated. Also, it docs not require any problem-dependent information. The details are given in Subsection 5.1.
3
Problem Setup
3.1 Notations
We consider the stochastic multi-armed bandit sctting where the learner explores a finite set A= = (1,2,..., K} of arms over a fixed horizon T. The reward sequence for arm k E A corresponds to independently and identically (i..d.) samples drawn from a distribution p(px) with an unknown mean Pk, i.e. μu = Ex [X]. We assume p(1))) is 3 sub-Gaussian, where 3 > 0, Vk E A.
Let EØ denote the set of all bandits instances that are B sub-Gaussian with distinct arm means. For any instance p(u)= == {p(H))..... p(ux)) E Eg with mean rewards of the arms as μ == {P let k² : k*t (p(n)) arg max μo denote the optimal arm, ie., the arm with the highest mean. We denote ey as the set of bandits in cæ satisfying unimodality, defined below.
kEA
3

---

Published in Transactions on Machine Learning Research (04/2024)
Definition 1. (Unimodality): A bondit instance p(μ) eg is said to be unimodal iff μa p2 < ... < pk
and pk > #1++1 > ...> μ.-
Let S be the set of the arm means satisfies the unimodal structure, i.e.,
S { pn p2 pk+ pk++1 1K).
3.2 Learning setup
We consider the following interaction between the learner and the environment over fixed rounds T >> 0. We refer to I' as the fixed budget. For any round 1 S t < T, the learner chooses arm ke E A and observes stochastic reward drawn from the distribution p(H,,). In each round t, the learner decides which arm to play based on the samples observed in the past. At the end of T, the learner returns an arm kr E A. policy x is any strategy that selects an arm in each round, given the past observations. For a given policy n, let kj denote the arm output the end of T budget. Let II denote the of all policics that output an arm within T budget on unimodal bandits instances.
Objective: The goal is to find policy in Il that exploits the unimodal structure of the mean rewards and minimizes the probability that the arm output at the end of T budget is not the optimal arm. Specifically, our objective is given as follows:
inf sup P(u) (KT + R*),
(1)
xlll μES
where Pr(-) is over the randomness of the reward and the policy. We refer to the BAI setup given in (1) as the fized budget BAI for unimodol bandits.
3.3 Problem Dependent Complexity
For a given instance p(u)= E ev with arm means μ, we express the complexity as H := (p(H)), and is given by
Σ (JE 14
(2)
We call H complexity the characterisation of the hardness of understanding the problem, will see later. Similar problen-dependent quantities are consider in Audibert et al. (2010); Carpentier & Locatelli (2016); Jamieson & Nowak (2014), that characterize the complexity of bandit problems, e.g.,
H1 = Σ (ui px) and H2 = sup Righk
k>1 (N m(x))
where P(k) denotes the 1ith largest mean of the arms. Following Audibert et al. (2010), is easy to show the following inequalities hold (see Appendix A.1 for proof)
min(Hz, H) S Hi S 2log(K)HH.
(3)
We next consider the lower bound for fixed budget BAI with the unimodal structure.
4 Lower Bound for Fixed Budget BAI of Unimodal Bandits
A lower bound on the error probability for BAI in the fixed budget setting without assuming any structure is established Audibert et al. (2010); Garivier Kaufmann (2016) and Carpentier & Locatelli (2016) using different techniques for constructing bandit problems, and all of them have provided minimax lower bound for the unstructured bandits. More specifically, Audibert et al. (2010) constructs K! bandit, problems by
4

---

Published in Transactions on Machine Learning Research (04/2024)
permutation of the arms and proposes that for any bandit problem, there exists permutation such that any algorithm will make an error with probability at least exp H2 Garivier & Kaufmann (2016) proposed the 'lipping constructions' and showed that there exists bandit problem such that any algorithm will make error with probability at least exp (-H)): where H2 < H1. Carpentier & Locatelli (2016) improved the flipping construction of Garivier & Kaufmann (2016) by providing further information to the algorithm. They proposed that there exists a bandit problem such that any algorithm will make an error with a probability of least exp (- loga (k))( The authors argue that in the fixed budget setting, unlike in the fixed confidence setting, there is an additional log(K) price pay for adaptation to H1 in the absence of knowledge over this quantity.
We adopt the lower bound proof of Carpentier & Locatelli (2016) for fixed budget BAI problems on unimodal instances. Carpentier & Locatelli (2016) provided a lower bound using a particular choice of Bernoulli rewards, whereas we do not assumee any particular choice of bandit instances. Our only assumption is that an unimodal structure exists over the mean rewards, and we consider Gaussian distributions for our case. Below, have given an overview of our construction.
Fix B 1. Let p(u)= := {p(U))]EA eu be unimodal bandit instance such that p(ux) == N (u,, 1), where [1/4, for all k E A and p 1/2. Let p'()') [[u')==== := (p'())) be another bandit instance where p'(x)) == Nul, 1) and #4 2pp- - pb for all & E A. Using p(H) and p' (n') we construct two more bandit instance pa- ( (1) and +1 with means 1at-1 and 4º* +1 as follows.
" k' -1 pi V k- - and n k' -1 14 for i = k -1
: +1 = Ms
+ k- + and pu! =1 = 14 for k." +11
It is easy to note that both bandit instances pa x (1= and p x (1**+1) are unimodal with the optimal arms being k' - 11 and k* + 1, respectively. Recall the definition of H given in (2). We define as
h h=
E
(E 1 +1)+ (Mk- 2.)2 pt (((())
where (p((tt) for bandit instance p² (u²') is defined as
H (P(("))
RE(i-1it11 (4 where Aj 2/1x= 14 pkk if + i, if === i.
Σ
Mk- Uss
Note that the authors in Carpentier & Locatelli (2016) have defined the quantity h" Σ SEA,iiE ((p=(1)) However, for the unimodality structure of the mean rewards, we can define
the quantity h on the neighbourhood of the optimal arm ks, We now provide the lower bound of the fixed budget BAI problem for unimodal bandits, as stated in the following theorem.
Theorem 1. For any unimodal bandit strotegy that returns arm ko after T budget, where T >
( (( 4) il holds that (E(k*=1,+++1)
max
12
)
T
1
max -1,k
Pricns(kr # exp 15 H( 2
(4)
Proof. The proof is given in Appendix A.2.
From the above theorem, conclude that the lower bound for the fixed budget unimodal bandit is O exp { ((TTT) }). Note that the exponent does not depend on K, but only on the sub-optimal gaps of
5

---

Published in Transactions on Machine Learning Research (04/2024)
the neighbours of the optimal arm. Our focus on improving the scaling in K is motivated by the study of unimodal bandits in the regret setting, where the unimodal property helps improve the scaling with respect to K. Specifically, a similar observation is also made for unimodal bandits in the cumulative regret setting, see Combes & Proutiere (2014).
5 FB-BAUB Algorithm
We propose an algorithm for unimodal bandit instances in the fixed budget BAI setting. The algorithm is based on the Line Search Elimination (LSE) method developed in Yu & Mannor (2011)and we refer it Fixed Budget Best Arm in Unimodal Bandits (FB-BAUB). It is parameter-free algorithm that only needs to know K and T, and the arms are eliminated based on their empirical means.
FB-BAUB splits the total budget T into L + 1 phases. Let N₁ for phase I = 1,2...., + 1, denotes the L+1
Ni = We have chosen N₁ such that after the first two phascs, the number of samples in phase I, whore Σ
number of samples increases by a factor of 3/2 in each subsequent phase, which helps to distinguish between the empirical means of the remaining arms, which are likely to be closer. Thus, N₁ is given by
34-1 T Ni
for I 1,2
(5)
2-10-11 T
for 1 = 3, 4, +1
36-0122
and satisfy the budget constraints, i.e,
2T-2T L+1 21-(111)
2 31-1
Σ 34-(1-2) T.
(6)
The arms are sampled and eliminated each phase, so only one arm survives after the L + phase.
The pseudo-code of FB-BAUB is given in ALGO 1. It works as follows: Let B₁ denote the set of arms available in phase and algorithm selects four arms S (A-M kA RB, ,NN Br, which include the first, last and the two middle arms uniformly spaced from them (lines 4-7). Each of the arms is sampled for N1/4 number of times (line 8). At the end of the phase, their empirical means, denoted as fu (line 9), are obtained as follows:
[B]] is the number of arms in the set B₁. In each phase 1 = 1.2........ L, the
N1/
A = N14 Σ X
Wk St.
(7)
where X denotes the 8th sample from the tthh arm in phase I. Based on these empirical means, we eliminate at most 1/3rd of the number of arms from the remaining set.1 Specifically, if the arms kM k-4 have the highest empirical means, eliminate all the arms succeeding B.5 in the set B (line 12). Similarly, if the arms g or A have the highest empirical means, eliminate all the arms preceding 4-4 in the set B, (line 14). Fig. gives a pictorial representation of the elimination of arms in two possible cases. The remaining set of arms is then transferred to the next phase. In phase I. + 1, we are left with three arms. Fach is sampled NL+1/3 times, and the one with the highest empirical mean is output as the optimal arm (lines 18-22).
Remark 1. Arms between M & A- or kB & KN are eliminated in each phase, and the arms between k- & kB always survive.
After phase 1 - .... L, (t of the arms survive. For case of exposition, we will drop the lJ function since this drop will influence only few constants in the analysis. Thus, after the end of the L phases, there will be three arms as
(2/3)* K 3 = == log2 K/3
(8)
log, 3/2
Therefore, FB-BAUB outputs the best arm as kLT1 (i.c., kr) after exploring for T rounds.
If the number of arms in phase is not multiple of 4, then less than 1/3rd will be eliminated that phase.

---

Published in Transactions on Machine Learning Research (04/2024)
ALGO 1: Fixed Budget Best Arm in Unimodal Bandits (FB-BAUB)
Input: T and K. Initialise: B1 A, J1 for (= 1 to L do
|B1]- Calculate L from (8).
4: kM - First arm of B;;
5: AN < Last arm of Br;
A + [i//3]th arm Bú;
7: B < 12//3 arm of Bi;
Sample each arm in S = {kM, kA, k. kB, K,K for N number of times from (5)
Obtain Ply,, Mla Piss Ply by (7).
10:
of - arg MES, Pu.
11:
if 2 = { kn then
12:
Bi+1 + {k E Br KM < k < kB Shrink to left
13:
else if o7 == ( k then
14:
BI+1 & {k By A S h Shrink to right
15: end
16: J++1 |B4+|:
17: end for
18: for / T, + do
19:
BL+1 = (k-M k };
20: Sample each arm in {KM A kND for Nu
of times and obtain Alas, , Plass Pla.
3
21: Obtain kL41 = arg m8 Pk.
22: end for
23: Output: KT hL-1
Case
Case 2
M
xi A
k
KN
kM
4
KB
Bi+1
B
B1
Bi
Figure Different cases of elimination in phase
5.1 Comparison between LSE and FB-BAUB
In Yu & Mannor (2011), LSE is developed for continuous set of arms. However, they have also applied LSF for finite set of arms in the fixed confidence setting. FB-BAUB and LSE differ primarily in four aspects.
Elimination: LSE eliminates about 1- 1/6 fraction of arms, where ø is the golden ratio. In contrast, FB-BAUB eliminates 1/3rd of the available arms in each phase.
2. Input parameters: LSE needs sequence of parameters (4) for every phase input, whereas such input parameters are required in FB-BAUB. Hence, it is parameter-free algorithm, which is highly desirable.
3. Number of samples: In the discrete case, LSE considers the instance where mean rewards of neighboring arms are separated at least by an amount Dr, i.e., > Dr (Yu & Mannor (2011)[Assum 3.4)), and uses this information dociding the arm plays in each phase (Combes & Proutiere (2014)(Prop. 5.4]). Whereas FB-BAUB does not require any problem-specte information and works as long means of the neighboring arms separated, i.e., A 0.

---

Published in Transactions on Machine Learning Research (04/2024)
4. Arms selection policy. LSE adds one new arm based on the golden ratio in each phase. Whereas FR-BAUB adds two new arms in each phase by uniformly dividing the space.
6 Performance Guarantee of FB-BAUB
This section provides the following theorem that gives the upper bound for the error probability of FB-BAUB.
Theorem 2. Let p(μ) eu follow sub- Gaussian with orm meons μ and A min | p4-1l > 0 denote 2sisk
the minimum gop between the means of any two neighboring arms. For any > K, the error probability of FB-BAUB is bounded as
TK
2
TK
A 2
P (k # k*) s 2 exp
2 exp
32
8
72
B
A
2
T
7 2
+ +exp
+ 2(L - exp
exp
(9)
24
3
8
3
Proof. The proof is given in Appendix A.3.
The first two terms in the upper bound correspond to the probability of eliminating the optimal arm k* in phases 1 & 2. The 3rd term bounds the probability of eliminating the optimal arm in phase L+ 1, and the 4thh term corresponds to the sum of the probabilities of eliminating the optimal arm in phases I = 3....,L L.
Note that, as K > 1, exp -TK ( (+)
2)
As a result, the 3rd and 4th terms dominate the upper bound (9). Therefore, the error probability is of order O (log, K exp (TA3)), where the error exponent term exp } does not depend on K.
< exp
-T -
Comparison with Sequential Halving: For unstructured bandits, the complexity parameter H2, as given in Subsection 3.3, can be upper bounded by H2 < H = Σ ( S Σ (- S 32 S g7
kek
Applying this inequalily, the upper bound of the error probability of Sequential Halcing as proposed in Karnin et al. (2013)/Thm. 4.1] is revised as of order O (Iog2 K exp {- {- Kn 1) and is optimal as matches with the lower bound derived in Carpentier & Locatelli (2016) up to a multiplicative factor of log, K. Note that the exponent. term in the error bound of Sequential Halving has log2 K factor. For unimodal bandits, the exponent term in the error bound of FB-BAUB does not depend on K and is smaller by factor of logz K. As expected, the error probability for unimodal bandits should be smaller, and our analysis captures this gain by shaving off the factor log, K in the error bound.
TA2 (aa2]
Comparision with LSE: The following points will discuss the novelty of the analysis of FB-BAUB, compared to the analysis of LSE, as follows:
1. Technical Challenges of FB-BAUB:
The PAC-bound provided by the LSE algorithm in Yu & Mannor (2011) is based on the known (ei, PtC bound of the Sampling Algorithm (refer to Thm. 4.1) for every iteration. However, FB- ---BBUBB does not run any sub-algorithm but has to carefully construct N so that the budget constraint that balances the trade-off of climination and exploration of new arms altained. Note that N; are of different lengths over the phases, and the error bound of the FB-BAUB obtained by carefully applying Hoeffding's inequality in each phase.
Minimum Gap Separation: For a finite set of arms, LSE assumes that the gap ween the mean rewards of the neighboring arms is separated by at least Dr (Assumption 3.2 in Yu & Mannor (2011)). More specifically, LSE requires knowledge of DL, and its sample complexity is expressed in terms of (e,, dc) for each phase I. However, BBBB only considers that A > 0, i.e., the arm means to be distinct. We do not need any assumptions on the minimum separation of the mean rewards of the neighboring arms, ie., FB-BAUB need not know Dr.- Therefore, FB-BAUB works when the arm means are distinct but arbitrarily close to each other, whereas LSE analysis assumes that this separation is least Dr-
8

---

Published in Transactions on Machine Learning Research (04/2024)
3. Analysis of fixed-budget setting vs. fixed-confidence setting: Our analysis for the finite set of arms differs from that of Yu & Mannor (2011), as we do not require the knowledge of Dr. Since Dr is unknown, this is not the same as 'computing the sample size with a required estimation error'. We have to carefully control the climination and decide the duration of the samples to moet the budget constraints. However, as rightly noted, the case of Yu & Mannor (2011); 'computing the sample size with a required estimation error' applies as they use the knowledge of Dr, for the finite set of arms.
4. Novelty in choice of Nr: The nature of selecting arm for sampling based on the golden ratio in Yu & Mannor (2011) makes the separation between the arms selected for sampling non-uniform, which in turn makes the number of arms eliminated in each phase a random quantity. Hence, LSE is not a good strategy for fixed-budget settings where the number of samples is constrained, and we need to have a good accounting of the remaining arms for analytical traceability. On the other hand, in FR-BAUB, 2/3 of the arms remain in each phase, and we increase the number of samples collected in subsequent phases by a factor of 3/2. This helps us in two ways. constraint exactly across the phases, and (b) the number of samples in phase independent of the problem instance (like knowing DL).
(a) meet the budget
We note that the error exponent of FB-BAUB differs from the optimal error exponent with respect to the complexity terms as H (p(w)) < 2/ and hence is not optimal with respect to the specific problem instance. It is an interesting open problem to develop an optimal algorithm in the fixed budget BAT setting with unimodality. However, our main focus is to improve the scaling of the error probability bound w.r.t. K. We have provided a near-optimal solution and have shown that the error exponent for both the lower and upper bounds does not involve K, quantifying the gain achieved by exploiting the unimodal structure. We are motivated by the study of unimodal bandits in the regret setting (Combes & Proutiere (2014)), where the unimodal property helps improve the scaling of the regret bound with respect to K.
7 Simulation Results
In this section, we corroborate the theoretical guarantec of FB-BAUB by applying it to problem instances of varying difficulty. As no algorithm exists for the BAI in unimodal bandits the fixed budget selting, we consider the following benchmark algorithms. The source code is available Sebamita-ghosh/FFe
hopps://githule com/
Sequential Halving (Seq. Halv.) Karnin et al. (2013): This fixed budget BAI algorithm is for unstructured bandits but is shown to be optimal by Carpentier & Locatelli (2016). A comparison with this algorithm gives gains achieved by exploiting structure.
Successive Rejects (SR) Audibert et al. (2010): This fixed budget BAI algorithm for unstructured bandits parameter-free and optimal up to a logarithmic term. SR outperforms UCB-E in Audibert et al. (2010); Shahrampour et al. (2017). Hence, we do not consider UCB-E for comparison. A comparison with this algorithm gives gains achieved by exploiting structure.
Linear Search Elimination (LSE) Yu & Mannor (2011): We consider the discrete variant of LSE proposed for a finite set of arms in the fixed confidence case and adopt it to the fixed budget setting. A comparison of FB-BAUB with LSE is pertinent as it is a well-known algorithm for unimodal bandits.
7.1 Comparison with pure exploration algorithms for unimodal structure
We consider two experimental setups to compare the performance of FB-BAUB with other benchmark algorithms. We consider K Gaussian arms with known variances o² = x² = 5, assuming that the mean of
the best arm is pa- = 252. Our simulations are averaged over 1000 runs and are shown with confidence intervals.
Experiment 1: Jn -312, pk+ -252, pkc -311, P2:k- Mn Pk- 2(k Mage -ax)
2(k - 1)(g Rz), and PK++1:K
K-W-1
9

---

Published in Transactions on Machine Learning Research (04/2024)
0.9
0.9
FB-BAUB, Experiment
FB-BAUB, Experiment
LSE, K Experiment
LSE, 100, Experiment
Error Probability
0.7
SR, K = 80, Experiment
Seq. Halv., K 80, Experiment
Error Probability
0.7
Seq. Halv., K 100, Experiment
SR, K 100, Experiment
0.6
FB-BAUB, 80, Experiment
0.6
FB-BAUB, k 100, Experiment 2
LSE, K 80, Experiment
LSE, 100, Experiment
Seq.
Experiment K 80, Experiment
0.5
Seq. Halv., 100, Experiment
SR, 100, Experiment
0.3
0.3
0.2
0.2
0.0
0.0
250
500
750
1000
1250
1500
1750
2000
250
500
750
1000
1250
1500
1750
2000
Budget (T)
Budget (T)
Figure 2: Error Probability vs T, K = 80.
Figure 3: Error Probability vs T, K 100.
FB-BAUB, K=80
FB-BAUB, K=80
LSE, K=80
LSE, K=80
Seq. Halv., K=80
Seq. Halv., K=80
Error Probability
Error Probability
FB-BAUB, K=100
FB-BAUB, K=100
LSE, K=100
LSE, K=100
Seq. Halv., 1-100
Seq. Halv., K-100
SR. K=100
SR, K=100
0.0
0
250
500
750
1000
1250
1500
1750
2000
0
250
500
750
1000
1250
1500
1750
2000
Budget (T)
Budget (T)
Figure 4: Exp. 3: Error Prob. vs T.
Figure Exp. 4: Error Prob. Vs
Experiment 2: A1 = 3312 pk- = -252, μK = -311, 12:k- A1 (I (k-1)(mmr-pi) and 44++1:KK (k*-1)
Pg- (k-k") -pk)
[K-
We examine each setup for two values of K {80, 100}. Exp. 1 and 2 are strictly unimodal in the sense that the optimal arm is lying in the interior. In Exp. 1, the means of the successive arms are well-separated compared to that in Exp. 2, i.e., is lower for Exp. 2. As we decrease the gap between the means of the neighboring arms, the means of the neighboring arms of the optimal arm come close to each other. Hence, identifying the best arm becomes complicated, which increases the error probability. This makes Exp. 2 more challenging to identify the optimal arm compared to Exp. 1, and thereby the error probability is higher for Exp. than Exp. 1. Moreover, the error probability increases pulls of each arm for Exp. 1 and 2 for the state-of-the-art algorithms in Appendix A.4, see Fig. 7 and Fig. 8.
Fig. 2 and Fig. 3 illustrate the performance of each algorithm for Exp. I and Exp. 2.
increase the arm size. We compared the empirical number of
SR has the worst error performance for each setup. For a small number of arms, both Seq. Halv. and FB-BAUB have comparable performance, but as the number arms increases, FB-BAUB has a lesser error probability compared to Soq. Halv. as evident from the case of K 100. Morcover, FB-BAUB can identify the best arm with probability of more than 95% with a lesser budget than other state-of-the-arl algorithms. More specifically, in Exp. FB-BAUB can identify the best with probability of more than 95% within 100 budget for 80 arms, while the other state-of-the-art algorithms need at least 500 budget for executions. Hence, FB-BAUB outperforms the srate-of-the-an algorithms.
10

---

Published in Transactions on Machine Learning Research (04/2024)
We note that the minimum budget requirement (as function of K) for LSE is much smaller than both FB-BAUB and Seq. Halv. for its feasible execution. However, LSE samples for a fixed number of times for each of the arms in every phase, the number of samples it runs for arms neighboring k is much lesser, resulting in a higher error probability. Seq. Halv. needs at least K (K) mumber of horizons to complete one phase and has samples for all arms every phase. Note that for each selup, Seq. Halv. requíres al least. 100 and 300 rounds for K graph starts after those many rounds. Thereby, it has fewer rounds remaining to explore the best arm when the algorithm is executed in the neighbourhood of k- compared to FB-BAUB. Thus, the minimum budget requirement for FB-BAUB as function of K is much less than that of Seq. Halv. In addition, FB-BAUB has better error probability performance. This demonstrates the advantage of exploiting the unimodality of the reward function.
and K = 100, respectively, to complete their execution, and hence, their
7.2 Comparison with pure exploration algorithms for monotone structure
We have considered two more experimental set-ups to compare FB-BAUB with the state-of-the-art algorithms. We consider K Gaussian arms with known variances of の² = 0.5, assuming that the mean of the best arm is μ1 = 0.7. Our simulations are averaged over 1000 runs and are shown with confidence intervals.
Experiment 3: μl 0.7 and P2:K A41 0.6(i-1)
Experiment 4: μ4 0.7 and P2:K = p41 0.01 (1+ 4)²-² i-2
Fig. 4 and Fig. 5 illustrate the performance of each algorithm for Exp. 3 and Exp. 4, respectively, for two values of K = {80, 100). Exp. 3 and Exp. 4 follow the monotone structure with the first arm as the optimal arm, similar to that considered probability increascs as we increase the arm size. In Exp. 3, the sub-optimal gap decreases in arithmetic progression, whereas in Exp. 4, the sub-optimal gap decreases in geometric progression. This makes Exp. 4 more challenging to find the best arm within a fixed budget, and thereby, the error probability of FB-BAUB is lower in Exp. 3 than in Exp. 4. We compared the empirical number of pulls of each arm for Exp. 3 and 4 for the state-of-thh-ar algorithms in Appendix A.4, see Fig. 9 and Fig. 10.
Shahrampour et al. (2017); Audibert et al. (2010). The error
Furthermore, in Exp. 3, FB-BAUB can identify the optimal arm with a probability of more than 80% within 100 budget for 80 arms, and in Exp. 4, it identifies the optimal arm with a probability of more than 75% within 100 budget. Whereas, the other state-of- thottrtt-rrttte algorithms need at least a 600 budget for execution. Hence, FB-BAUB perperfrms the other state-of-the-art algorithms for Exp. 3 and 4.
8 Conclusion
We studied the fixed budget BAI problem with an unimodal structure on a finite set of K arm mcans. Wo developed an algorithm named FB-BAUB to address the problem and derived an upper bound on its error probabilities. The algorithm works in phases and identifies the best arm with high probability. We established that the exponent in the error bound is independent of K in contrast to the unstructured bandits. We demonstrated that for any optimal algorithm, the error exponent should be independent of K by establishing lower bound. Simulations validated the efficiency of FB-BAUB compared to state-of-the-art algorithms. FB-BAUB is parameter-free and casy to implement.
Many interesting research directions could be further investigated. The exponent in the upper bound on the error probability of FB-BAUB is optimal in T' and K, but not in the problem-dependens complexity terms, which are characterized in terms of the smallest gap between any neighbouring arms. However, the lower bound is only dependent on the neighbours of the optimal arm. It is interesting to develop algorithms that. are also optimal with respect to the complexity terms.
Acknowledgement
Manjesh K. Hanawal thanks funding support from SERB, Govt. of India, through the Core Rescarch Grant DDNG/2022/008000 and MATRICS grant (MTR/2021/0006) and funding support from DST, Govt. of India, through the DST-INRIA targeted programme and the DST-INRIA joint research targeted programme.
11

---

Published in Transactions on Machine Learning Research (04/2024)
References
Yasin Abbasi- Yadkor,, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
Alexia Atsidakou, Sumeet Katariya, Sujay Sanghavi, and Branislav Kveton. Bayesian Exxee-Budget Best-Arm Identification. arXiv preprint arX1v:2211.0857,, 2022.
Yean-Yves Audibert, Sébastien Bubeck, and Rémi Munos. Best arm identification in multi-armed bandits. In COLT, pp. 41-53, 2010.
MohammadJavad Azizi, Branislav Kveton, and Mohammad Ghavamzadeh. Fixed-Budget Best-Arm Identification in Structured Bandits. In Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI-22, pp. 2798- 2804, 2022.
Antoine Barrier, Aurélien Garivier, and Gilles Stoltz. On Best-Arm Identification with a Fixed Budget in Non-Paramettr Multi-Armed Bandits. In International Conference Algorithmic Learning Theory, pp- 136 181. PMLR, 2023.
Nathan Blinn, Jana Boerger, and Matthicu Bloch. mmWave Beam Steering with Hicrarchical Optimal Sampling for Unimodal Bandits. In ICC 2021-IEEE International Conference on Communications, pp. 1-6. IEFE, 2021.
Djallel Bouneffouf and Trina Rish. A Survey on Practical Applications of Multi-Armed and Contextual Bandits. CoRR, Abs/1994.10040, 2019. URL http://aaii...orra////////// 10040.
Alexandra Carpentier and Andrea Locatelli. Tight (lower) bounds for the fixed budget best arm identification bandit problem. Conference on Learning Theory, pp. 690-604. PMLR, 2016.
Nicolò Cesa-Bianchi and Gábor Lugosi. Combinatorial bandits. Journal of Computer and System Sciences, 78(5):1404-1422, 2012. JCSS Special Issue: Cloud Computing 2011.
Lijie Chen and Jian Li. On the Optimal Sample Complexity for Best Arm Identification, 2015.
James Cheshire, Pierre Ménard, and Alexandra Carpentier. The influence shape constraints on the thresholding bandit problem. In Conference on Learning Theory, pp. 1228-1275. PMLR, 2020.
James Cheshire, Pierre, Ménard, and Alexandra Carpentier. Problem Dependent View Structured Thresholding Bandit Problems. In International Conference on Machine Learning, pp. 1846 1854. PMLR, 2021.
Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual Bandits with Linear Payoff Functions. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, volume of Proceedings of Machine Learning Research, pp. 208 214, Fort Lauderdale, FL, USA, 11-13 Apr 2011. PMLR.
Richard Combes and Alexandre Proutiere. Unimodal Bandits: Regret Lower Bounds and Optimal Algorithms. In Proceedings of the 31st International Conference on International Conference on Machine Learning Volume 32, ICML/14, pp. I-521-I-529, 2014.
Richard Combes, Mazrach Shahi Talebi, Sadegh Mohammad, Alexandre Proutiere, and Marc Lelarge. Combinatorial Bandits Revisited. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 28. Curran Associates, Inc., 2015.
Richard Combes, Stefan Magureanu, and Alexandre Proutiere. Minimal exploration in structured stochastic bandits. Advances in Neural Information Processing Systems, 30, 2017.
Varsha Dani, Thomas P. Hayes, and Sham M. Kakade. Stochastic Linear Optimization under Bandit Feedback. In Conference Learning Theory, 2008
12

---

Published in Transactions on Machine Learning Research (04/2024)
Eyal Even-Dar, Shie Mannor, and Yishay Mansour. Action Elimination and Stopping Conditions for the Multi-Armed Bandit and Reinforcement Learning Problems. J. Mach. Learn. Res., 7, 2006.
Victor Gabillon, Mohammad Ghavamzadeh, and Alessandro Lazaric. Best Arm Identification: A Unified Approach to Fixed Budget and Fixed Confidence. In Advances in Neural Information Processing Systems, volume 25, 2012.
A. Garivier, P. Ménard, L. Rossi, and P. Menard. Throsholding Bandit for Doso-ranging: The Impact of Monotonicity. Arzin, PMLR, 2017. URL https://doi. http::....rrr...../5///////1/// 1711.04454
Aurélien Garivier and Emilie Kaufmanm. Optimal best arm identification with fixed confidence. In Conference on Learning Theory, pp. 998-1027. PMLR, 2016.
Manjesh Kumar Hanawal, Venkatesh Saligrama, Michal Valko, and Rémi Munos. Cheap Bandits. In Proceedings of the 32nd International Conference on International Conference on Machine Learning, 2015.
Morteza Hashemi, Ashutosh Sabharwal, C. Emre Koksal, and Ness B. Shroff. Efficient Beam Aligmment in Millimeter Wave Systems Using Contextual Bandits. In JEEE Conference on Computer Communications (INFOCOM), pp. 2393 2401, 2018
Kevin Jamieson and Robert Nowak. Best-arm identification algorithms for multi-armed bandits in the fixed confidence setting. In 48th Annual Conference on Information Sciences and Systems (CISS), pp. 1-6. IEEE, 2014.
Yassir Jedra and Alexandre Proutiere. Optimal best-arm identification in linear bandits. Advances in Neural Information Processing Systems, 33:10007-10017, 2020.
Shivaram Kalyanakrishnan, Ambuj Tewari, Peter Auer, and Peter Stone. PAC Subset Selection in Stochastic Multi-Armed Bandits. Proceedings of the 29th International Conference on International Conference on Machine Learning (ICML), pp. 227 227-234, 2012.
Zohar Karnin, Tomer Koren, and Oren Somekh. Almost optimal exploration in multi-armed bandits. In International Conference on Machine Learning, pp. 1238 1246. PMLR, 2013.
Emilie Kaufmann, Olivier Cappé, and Aurélien Garivier. On the Complexity of Best Arm Identification in Multi-Armed Bandit Models. Journal of Machine Learning Reseorch, 17:1-42, 2016.
Tomáš Kocâk and Aurélien Garivier. Best arm identification in spectral bandits. In Proceedings of the International Joind Conference on Artificial Intelligence, IJCAI-20, 2020.
Tor Lattimore and Csaba Szepesvári. Bandit algorithmss. Cambridge University Press, 2020.
Stefan Magureanu, Richard Combes, and Alexandre Proutiere. Lipschitz bandits: Regret lower bound and optimal algorithms. Conference on Learning Theory, pp. 975-999 PMLR, 2014.
Shie Mannor and John N. Tsitsiklis. The Sample Complexity of Exploration in the Multi-Armed Bandit Problem. J. Mach. Learn. Res., 5:623-645 648, dec 2004. ISSN 1532-4435.
Hassan Saber, Pierre Ménard, and Odalric-Ambry Maillard. Forced-exploration free strategies for unimodal bandits. arXiu preprint Xrxi::0006. 16569, 2020a.
Hassan Saber, Pierre Ménard, and Odbrric-Ambrym Maillard. Forced-exploratiion free Strategies for Unimodal Bandits. working paper or preprint, 2020b. URL
Shahin Shahrampour, Mohammad Noshad, and Vahid Tarokh. On sequential elimination algorithms for best-arm identification in multi-armed bandits. IEEE Transactions on Signal Processing, 65(16):4481-4222, 2017.
Marta Soare, Alessandro Lazaric, and Remi Munos. Best-Arm Identification in Linear Bandits. In Advances in Neural Information Processing Systems, volume 27, 2014.
13

---

Published in Transactions on Machine Learning Research (04/2024)
Michal Valko, Rémi Munos, Branislav Kveton, and Tomas Kocak. Spectral Bandits for Smooth Graph Functions. In Proceedings of the 31st International Conference on International Conference on Machine Learning, 2014.
Po-An Wang, Ruo-Chun Tzeng, and Alexandre Proutiere. Fast pure exploration via frank-wolfe. Advances in Neural Information Processing Systems, 34:5810-5821, 2021.
Jia Yuan Yu and Shie Mannor. Unimodal Bandits. In Proceedings of the 28th International Conference on International Conference on Machine Learning, pp. 41-48, 2011.
14


Reviews:
[{"review_id": "woxeORpLCk", "reviewer": "Reviewer_NAro", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Overall assessments.\nThe problem setting is a simple and straightforward extension of the standard BAI. However, it seems practical and useful. I also prefer the proposed approach since I have been engaged in dynamic pricing, which I think is a potential application of the proposed strategy.\n\nFrom a theoretical viewpoint, less dependence on $K$ is interesting and matches our intuition.\n\nThe weakness of this study is a bit unrigorous mathematical arguments; however, it is still understandable. In particular, I worry about the definition of the bandit model. As I point out in the Requested Changes section, I think that the authors need to restrict the class more. For example, the authors should exclude a class of distributions such that both mean and variance shift. \n\nIn summary, while the idea and the strategy are straightforward and not so technical, the proposed algorithm is practical, and the theoretical findings are interesting. Although several parts should be fixed, I think that this study is worth publishing after revision. \n\n### Questions.\n- Could the authors give us some intuitive explanation as to why the $K$ disappears from the exponent of the upper bound? Specifically, I would like to know how it affects the behavior of strategies compared to strategies designed for the standard BAI setting. In general, the $K$ term in fixed-budget BAI appears from the behavior such that the decision-maker will draw each arm proportional to $T/K$ times. However, in an unimodal setting, the number of arms draws more concentration on some specific arms.\n- (If the authors have time,) it might be interesting if the authors show the empirical number of arm draws in each arm in experiments.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This study explores the problem of unimodal bandits within the context of fixed-budget best arm identification (BAI). The problem setting is characterized by an order in the mean rewards and a specific instance of the standard fixed-budget BAI. While the setting is restricted, the authors have established tighter lower and upper bounds alongside an optimal algorithm. Notably, $K$ is removed from the exponent in the probability of misidentification, marking a considerable theoretical advancement over strategies devised for more generalized settings.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "### Requests\n- We should define the distribution $p_k(\\mu_k)$ as a distribution which only depends on the mean parameters. For example, we do not consider various variances in the defined class. That is, we need to consider a class where only the means vary, but the other parameters are fixed. \n\n### Suggestions\nThe following is not a request, but I just suggest the authors reconsider them.\n- The authors repeatedly use the word \"unimodal.\" However, it is unclear until the definition in Section 3. It may help the readers if the authors briefly introduce the setting in earlier parts, such as the Abstract or Introduction.\n- The authors uses $p_k(\\mu_k)$ to denote the distribution of a reward of arm $k$. I think that we do not have to use the subscript $k$ twice. Instead, we can use $p(\\mu_k)$ to denote it. In fact, the authors defines $p_k(\\mu_k)$ as $N(\\mu_k, 1)$. Here, $N(\\mu, 1)$ is fixed among arms, but the only mean parameters $\\mu_k$ shift. In this sense, I considered that $p(\\mu_k)$ is more appropriate to denote the distribution (but both are fine).\n- Regarding the definition of the distributions, the authors mention that \"samples from an unknown distribution $p_k(\\mu_k)$.\" However, I think that the decision-maker may understand the distribution to some extent; the decision-maker does not know $\\mu_k$ only. Therefore, \"samples from a distribution $p_k(\\mu_k)$ with an unknown parameter $\\mu_k$\" may be a more accurate expression.", "broader_impact_concerns": "N / A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "y6qqF7SrFJ", "reviewer": "Reviewer_GGpE", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n* This paper is well-structured and easy to follow.\n* The topic addressed in this paper appears to be of interest to the theoretical community of bandit algorithms.\n\nWeaknesses:\n* The comparison with Sequential halving in Section 6 raises some concerns.\nThe paper asserts that the bounds achieved by Sequential halving are $O(\\log K \\exp (-\\frac{T \\Delta^2}{K \\log K}))$,\nwhich seems to be derived from substituting $\\frac{K}{\\Delta^2}$ for $H_2$ in the bound of \n$3 \\log_2 K \\cdot \\exp(- \\frac{T}{8 H_2 \\log_2 K})$\npresented in Theorem 4.2 by Karnin et al.(2013).\nHowever, in Theorem 2 of the submission,\n$\\Delta=\\min_{2\\le i \\le K} |\\mu_i - \\mu_{i-1}|$ is defined as the minimum difference in expected rewards between adjacent arms,\nwhich implies $\\Delta_i = \\mu_{k^*} - \\mu_{i} \\ge |i-k^*| \\Delta$,\nand thus $H_2 \\le \\sup_{k > 1}\\frac{k}{(\\mu_{k^*} - \\mu_{(k)})^2} \\le \\sup_{k > 1}\\frac{k}{ (\\Delta \\lfloor k/2 \\rfloor)^2} \\le \\frac{3}{\\Delta^2}$.\nConsequently,\nthe bounds achieved by Sequential halving would actually be\n$3 \\log_2 K \\cdot \\exp(- \\frac{T \\Delta^2}{24 \\log_2 K})$.\nFrom this observation,\nthe superiority of the bounds shown in Theorem 2 of this submission over those of Sequential halving --as the paper claims-- appears dubious.\nI would welcome any corrections if my interpretation has any inaccuracies.\n* The distinctions 1 and 4 claimed in Section 5.1 in comparison to LSE do not clearly emerge as fundamental.\nThe paper seems to advocate for replacing the division of intervals based on the golden ratio with a split into three equidistant intervals,\nbut the necessity and benefits of this approach remain unclear.\nThis difference appears to correspond to those between the golden ratio search (https://en.wikipedia.org/wiki/Golden-section_search) and ternary search (https://en.wikipedia.org/wiki/Ternary_search).\nIn typical optimization problems involving unimodal functions,\nboth the golden ratio search and ternary search can operate within a similar analytical framework,\nyet it's well-known that the golden ratio search tends to be more efficient.\n(In fact, the golden ratio search is mini-max optimal as shown by Kiefer, J. (1953), \"Sequential minimax search for a maximum\", Proceedings of the American Mathematical Society, 4 (3): 502–506)\nTherefore,\nthe choice to opt for an approach akin to ternary search is surprising,\nand I would be interested in hearing a compelling reason for this decision.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper addresses the problem of Fixed budget best arm identification in multi-armed bandit problems where the expected rewards have a unimodal structure. It presents new error lower bounds for this problem, and proposes an algorithm with new error upper bounds. The effectiveness of the proposed algorithm is validated not only through theoretical analysis but also by numerical experiments.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Regarding the weakness mentioned above, I would appreciate it if you could verify if there are misunderstandings in my review and respond with either a correction or a rebuttal.\nAdditionally, below are some minor points I have noticed:\n\n* In the definition of $H_2$ in Section 3.3,\nshould the range of \n$k$ be $k\\neq 1$?\n(from the definition of $\\mu_{(k)}$, not $\\mu_{(k^*)} = \\mu_{k^*}$ but $\\mu_{(1)} = \\mu_{k^*}$)\n* The usage of ordinal indicators such as \"-th\" or \"-rd\" appears to be inconsistent, with some instances using superscript formatting and others not.\n* It seems correct to place footnotes after punctuation (see, e.g., Section 4.2 in the example PDF of https://neurips.cc/Conferences/2023/PaperInformation/StyleFiles).\n* In the paragraph on Comparison with Sequential Halving in Section 6, it would be beneficial to add a reference to the literature proposing Sequential Halving. (I interpreted this as referring to the study by Karnin et al.(2013).)\n* The statement \"LSE eliminates about $1/\\phi$ fraction of arms\" may indeed be misleading. In LSE, $1/\\phi$ appears to be the proportion of arms that are retained, not eliminated. The correct interpretation would be that the fraction of arms eliminated is $1-1/\\phi$.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "vNSWFmRnvQ", "reviewer": "Reviewer_fuwp", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n\n1.\tThe studied problem, best arm identification in unimodal bandits with fixed budget, is an interesting problem and finds real-world applications such as network throughput, sequential pricing, and bidding in online sponsored search auctions.\n2.\tThe theoretical analysis in this paper is solid. This paper establishes an error probability lower bound for unimodal bandits with fixed budget, which shows the gain of utilizing the unimodal structure. In addition, this paper also designs an algorithm with error probability upper bounds.\n3.\tEmpirical evaluations are provided to validate the effectiveness of the proposed algorithm.\n\n\n**Weaknesses:**\n\n1.\tIt would further improve this paper if the authors can discuss the gap between their upper bound and lower bound. The comparison to existing unimodal bandit or unstructured bandit results can help readers understand the contributions of this paper to the literature.\n2.\tThe authors should discuss more on the novelty in analysis, compared to existing analytical procedure of unimodal bandits.\n\nOverall, I think this submission is a good paper, and tend to accept.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper considers the best arm identification problem in a fixed budget stochastic multi-armed bandit setting, where the arm mean rewards exhibit a unimodal structure. The authors establish an error probability lower bound for misidentifying the optimal arm within a budget of $T$. In contrast to the lower bound for the unstructured case, the error exponent in this bound does not depend on the number of arms $K$ and is smaller by a factor $K \\log K$, which captures the gain achievable by exploiting the unimodal structure. The authors also develop an algorithm named FB-BAUB that exploits unimodality to achieve the gain.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see the review on weaknesses above.", "broader_impact_concerns": "I do not have ethical concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper tackles the problem of best arm identification within a fixed budget setting for stochastic multi-armed bandit models exhibiting a unimodal structure. The authors first establish a lower bound of the probability of misidentifying the optimal arm, which captures the gain achievable by exploiting the unimodal structure. Then, they develop an algorithm named as Fixed Budget Best Arm Unimodal Bandits (FB-BAUB) to exploit unimodality and attain a tight upper bound. The paper is further enriched by comprehensive empirical evaluations demonstrating the superiority of FB-BAUB over state-of-the-art algorithms.

By establishing error probability lower bounds, the authors provide a deeper understanding of the fixed budget best arm identification problem in unimodal bandits. The FB-BAUB algorithm embodies a novel approach to utilizing unimodal properties, showcasing not only theoretical innovation but also practical applicability. Its parameter-free nature and ease of implementation further enhance the paper's appeal to both researchers and practitioners.
Decision: Accept (poster)