Minimax Optimal Algorithms for Fixed-Budget Best Arm Identification
Authors: Junpei Komiyama
Taira Tsuchiya
Junya Honda
Venue: NeurIPS 2022 Accept (2022)
Keywords: Best Arm Identification
Online Learning

Abstract: We consider the fixed-budget best arm identification problem where the goal is to find the arm of the largest mean with a fixed number of samples. It is known that the probability of misidentifying the best arm is exponentially small to the number of rounds. However, limited characterizations have been discussed on the rate (exponent) of this value. In this paper, we characterize the minimax optimal rate as a result of an optimization over all possible parameters. We introduce two rates, $R^{\mathrm{go}}$ and $R^{\mathrm{go}}_{\infty}$, corresponding to lower bounds on the probability of misidentification, each of which is associated with a proposed algorithm. The rate $R^{\mathrm{go}}$ is associated with $R^{\mathrm{go}}$-tracking, which can be efficiently implemented by a neural network and is shown to outperform existing algorithms. However, this rate requires a nontrivial condition to be achievable. To address this issue, we introduce the second rate $R^{\mathrm{go}}_\infty$. We show that this rate is indeed achievable by introducing a conceptual algorithm called delayed optimal tracking (DOT).

Minimax Optimal Algorithms for Fixed-Budget Best Arm Identification
Junpei Komiyama New York University
Taira Tsuchiya Kyoto University, Kyoto, Japan
New York, NY, United States junpei@komiyama.. info
RIKEN AIP, Tokyo, Japan tsuchiyadsys kyoto-u..... ac.
Junya Honda
Kyoto University, Kyoto, Japan RIKEN AIP, Tokyo, Japan honda@i kyoto-u.ac.jp
Abstract
We consider the fixed-budget best arm identification problem where the goal is to find the arm of the largest mean with fixed number of samples. Tt is known that the probability misidentifying the best arm is exponentially small to the number of rounds. However, limited characterizations have been discussed on the rate (exponent) of this value. In this paper, we characterize the minimax optimal rate result of optimization over all possible parameters. We introduce two rates, R and Rgg corresponding to lower bounds on the probability of misidentification, each of which is associated with a proposed algorithm. The rate 8 is associated with R**-tracking, which be efficiently implemented by neural network and is shown outperform existing algorithms. However, this rate requires a nontrivial condition to be achievable. To address this issue, introduce the second rate R We show that this rate is indeed achievable by introducing a conceptual algorithm called delayed optimal tracking (DOT).
Introduction
We consider K-armed best arm identification problem with T samples. In this problem, each arm i E [K] = (1, 2..... K} is associated with (unknown) distribution P; E P for some class of distributions drawn independently from P.. The forecaster then trics to identify (one of) the best arm I' = arg max; μ4 with the largest mean μ² = max; μ4; for μ4; = Ex~P [X] The problem² called the best arm identification (BAI, Audibert et al. (2010)), or the ranking and selection (R&S, Hong el al. (2021)).
Upon choosing arm i, the forocaster observes reward (t),, which
To this aim, the forecaster uses some algorithm that would adaptively choose an arm based on its history of rewards. At each round f, the algorithm chooses one of the arms I(t) [K] and receives the corresponding reward (t). After the T-thh round, the algorithm outputs recommendation arm J(T) [K), which corresponds an estimator of the best arm. The probability of misidentification is expressod by IP P[J(T) I"), which will be referred to as
We use I" (P) [K] as the set of best and (P) E (P) one of them (ties are broken an arbitrary way). These differences not matter much this paper. 28ee Section 1.3 regarding the related work on BAT and R&S.
36th Conference on Neural Information Processing Systems (NeurIPS 2022).

---

the probability of the error (PoE) throughout the paper. Best arm identification has two settings. In the fixed confidence (FC) setting, the forecaster minimizes the number of draws T until the confidence level on the PoE reaches given value 5 E (0. 1). In this case, 7 is stopping time that can be chosen adaptively. In the fixed-budget (FB) setting, the forecaster tries to minimize the PoE given constant T. In this paper, we shall focus on the FB setting. In general, a good algorithm for the FC setting is very different from that for the FB setting, To be more specific, an algorithm for the FC setting can be uniformly optimal. Namely, several FC algorithms exist (Garivier and Kaufmann, 2016) that able to adapt to each instance of distributions P = (P1. ....... Pk). On the contrary, setting requires consideration of the tradeoff in that improving the PoE for an instance P can compromise the PoE for another instance P'. Thus, we must consider an optimization of the performance over all possible P E pk See Appendix C for demonstration of the asymptotic inconsistency between the two settings.
algorithm for the FB
1.1 Minimax optimality in the fixed-budget setting
In the FB setting, the PoE decays exponentially to T as (T) for some rate R > 0. The uniform optimality given above no longer available here. To demonstrate this, assume that we make an estimate of P based on the initial o(T) rounds, say, VT rounds. In this case, can obtain the estimate of P that e-correct with probability exp(-&O((T)) = exp(-o(T)). (()))) However, this estimation does not help to improve the rate of exponential convergence. In other words, estimating P requires non-negligible (i.e. O(T)) cost for exploration. As result, we cannot fully adapt the PoE to each instance P unlike the FC setting, Instead, to discuss optimality in the FB setting, we must choose a complexity function H (P)), and the performance of an algorithm must be evaluated on the rate normalized by the complexity (xp(-RT/H(P))
In the literature, little is known about the optimal rate of the exponent. Several papers considered what rate R is achievable for all P given complexity function HPP). Kaufmann et al. (2016) showed that this rate is larger than the corresponding rate of the FC setting.* Audibert al. (2010) proposed the successive rejects (SR) algorithm, which has the rate of 1/olog K) with the complexity function H2(P) [ A? for A maxy My μ4 satisfying A S A2 .... < Ax. Carpentier and Locatelli (2016) showed a particular set of instances such that this rate matches the lower bound up to constant factor. However, the constant used there is by far loose", and there is limited discussion on the actual rate of such algorithms.
1.2 Contributions
This paper tightly characterizes the optimal minimax rate of the PoE as result of an optimization given P. Let H = HP)) PK - R+ {oo) be any complexity mcasure. We then discuss the best possible rate R > 0 such that the PoE is bounded by exp(-RT) (P)) o(T)) for all P E pk and make the following contributions.
We derive an upper bound on R (corresponding to a lower bound of the PoE), denoted by R which we obtain by considering a class of oracle algorithms that can determine the allocation of trials to each arm knowing the final empirical distribution after T rounds (Theorem 1).
We propose an algorithm (R#*-trackngg) that tracks this oracle allocation based on the current empirical distribution (Section 2.1). Although this oracle allocation is expressed by complicated minimax optimization, we propose a technique to learn this by a neural network and empirically confirm that the PoE of the learned algorithm is close to the lower bound (Sections 3 and 4). We also discuss that the algorithm is
3 AA more complete discussion this topic can be found in Section B. 4 "That is, given the complexity of the FC setting, the rate for some instances smaller than in the FB setting.
Theorem 1 therein includes large constant 400.

---

unlikely to provably achieve the bound even when the minimax problem is perfectly solved because of the impossibility of tracking.
We lighten the PoE lower bound by weakening the oracle algorithms to obtain new rate - We propose the delayed optimal tracking (DOT) algorithm that asymptotically achieves this rate for Bernoulli and Gaussian arms. While DOT is minimax, the algorithm is computationally almost infeasible (Sections 2.2 and 2.3).
In summary, we propose a nearly tight minimax lower bound rate on the PoE with computationally feasible algorithm that is empirically close to this bound. We also propose exact minimax rate and matching algorithm in a computationally infcasible form. Notation listed in the Section A in the appendix.
1.3 Related work
Compared with the works of the fixed-confidence (FC) BAI, less is known about the fixed- budget (FB) BAI. For example, a book on this subject (Lattimore and Szepesvári, 2020) spends only two pages on the FB-BAT. Many algorithms designed for the FC-BAI, such al., 2016), do not have a finite-time PoE guarantee when we
as D-tracking (Kaufmann apply them to the FB sctting. Nevertheless, there are two well-known FB BAT algorithms: Successive rejection (SR, Audibert et al. (2010)) and successive halving (SH, Shahrampour et al. (2017)). Both SR and SH decompose T time steps to finite number of time segments, and then progressively narrow the candidate of the best arm at the end of each segment. While SR discards one arm after each segment, SH discards half of the remaining arms after each segment. SR and SH have the guarantee on the PoE of the rate exp RRT (1TT/HH((P) for some constant R O. Other FB BAI algorithms, such UCB-E (Audibert et al., 2010) and UGapE (Gabillon et al., 2012), require the knowledge of minimum gap min; A; and thus are not universal to all best arm identification instances.
Another literature on this topic the ranking and selection (R&S) problems (Bechhofer and Sobel, 1954; McDonald, 1998; Powell and Ryzhov, 2018; Hong et al., 2021). Although the goal of R&S problems is to identify the best arm, many R&S papers do not consider the estimation error of P in finite time. As result, algorithms therein do not have the guarantee on the PoE in the best arm identification setting. The optimal computing budget allocation (OCBA, Chen et al. (2000); Glynn and Juneja (2004)) algorithm tries to minimize the PoE assuming the plug-in estimator matches the true parameter. Bayesian R&S algorithms try solve the dynamic programming of minimizing the PoE marginalized by a prior (Bayesian PoE), which is computationally prohibitive, and thus approximated solutions have been sought (Frazier al., 2008; Powell and Ryzhov, 2018).
2 Minimax optimal algorithm
In this section, we derive several lower bounds on the PoE and propose algorithms to empirically or theoretically achieve these bounds.
First, we formalize the problem. Let P be known class of reward distributions, We consider the case where P is the set of Bernoulli distributions with mean θ C [0, 1] (including the case = [0, 1)), or Gaussian distributions with mcan in θ C R (including the case θ = R) and known variance o² > O. It should be noted that many parts of the results in this paper can be generalized to much wider classes of distributions, but it makes the notation much longer and discussed in Appendix D.
When we derive lower bounds and construct algorithms, we introduce Q as a class of distributions corresponding to the estimated distributions of the arms. Namely, we set Q as the set of all Bernoulli (resp. Gaussian) distributions with mean in [0, (resp. R) when P is the set of Bernoulli (resp. Gaussian) distributions with mean in θ. As such, we take 2 P so that the estimator of P. is always in Q. In these models, we identify the distribution P. P with its mean paramctor in θ C R.
"Section 33.3 therein.
3

---

Algorithm 1: R -Taackin
input: : (e-joptimal solution (r*(),,)*))) of (2).
1 Draw each arm once.
2 for f = K + .,2,...,7 T do
3 L Draw arm arg [(X] (Q) - 1)) - (,(t - 1)
return J(T) = (Q).
Our interest lies in the rale lim + log(1/P(J(T) & (P)) of convergence of the PoE. Since we are interested in lower and upper bounds of the rate of algorithms including those requiring the knowledge of T, we define the rate for a sequence' of algorithms {गr} by
R((TT}) = inf (P)) lim inf T-x T log (og(L/)( (P)))
(1)
PEPK
Here, a larger H((TT)) indicates a faster convergence of the PoE.
2.1 PoE for oracle algorithms
First, we derive a lower bound on the PoE that is unlikely to be achievable but strongly related to an optimal algorithm. Let D(PI(Q) = Ex-rlag (X)] be the Kullback Leibler (KL) divergence between P and Q. In the case of Bernoulli distributions, D(PII)) = up log(up/uQ)) (1- log (appppppplpppaa pQ)) where μp, μQ are the means of P, Q. In the case of Gaussian distributions, Q() (pP p2)2/(20"). We then have the following bound.
Theorem Under any sequence of algorithm { it holds that
R((TT)) S
inf (N)AAx.J)EE) QEO" PERK (Q))
sup
inf H(P) Σ
((Q))D(Q)1))) =: R:o (2)
[E]K]
where the outer supremuun is taken over all functions r()) QK AK, J() QK + [K].
All proofs are provided in the appendix. This theorem states that under any algorithm there exists an instance P such that the PoE is at least exp (H() o(T)). Intuitively speaking, the bound in Theorem corresponds to the best possible rate oracle algorithms that can determine the allocation r (Q) AK knowing the final empirical mean == Q(T), where r' (-) is the (e-)optimal solution of Eq. (2).
However, whether the rate Re or not by some algorithm is highly nontrivial. 10 In the actual trial, the algorithm can only know the empirical mean Q(t-1) at the beginning of the current round t; cannot ensure the achievability of the bound for oracle algorithms. Despite this, one reasonable choice of the algorithm would be to keep tracking this optimal allocation r* (Q(t- - 1)), expecting that the current empirical mean Q(t-1) 1) is close to Q(T). R**-tracking in Algorithm is the algorithm based on this idea. Here, N2 - 1) is the mumber of times that the arm i is drawn at the beginning of the t-th round, and it draws the arm such that the current fraction of the allocation N,(t-1)/(( - 1) is the most insufficient compared with the estimated optimal allocation r (Q(t+1)).
As we will see in Section 4, the empirical performance of Algorithm is very close to the PoE lower bound stated above. However, it is difficult to expect that this algorithm provably achieves this bound in general because of the following: We could prove that R8*-tracking is optimal if the fraction of allocation always satisfies N.(1)/t r (Q(()) + o(1), that is,
7 Heere, we use {тr} to denote sequence of algorithms for each T' 1.2.... For example, successive halving (Audibert et al., 2010) is a sequence of algorithms in this sense.
TThis corresponds to the rate R = R((T)] }) of (xp(-RT/H(P))
"This paper uses e >> 0 as an arbitrarily small gap to the optimal solution. This e introduced so that we can avoid the discussion on the existence of a supremum and does not matter much in this paper. An asterisk is used to denote optimality. 10 We leave this open problem.
4

---

the algorithm is able to track the ideal allocation r" (Q)().. However, this does not hold in general. For example, the empirical mean Q(t) sometimes changes rapidly in the Gaussian case. Whilst such an event occurs with an exponentially small probability, the PoE, itself is also an exponentially small probability and is highly nontrivial to specify in which case the tracking failure probability becomes negligible.
Remark 1. (Derivation of Theorem 1) From a technical point of view, the main difference from the lower bound in the FC setting is that we also have to consider candidates for empirical distributions Q and true distributions P. This makes the analysis much more difficult because slight difference of the empirical distribution might (possibly discontinuously) affect the allocation unlike the difference of the true distribution P unknown to the algorithm. A naive analysis only depending on the empirical distribution fails because of this discontinuity of the allocation. To overcome this difficulty, we adopt technique inspired by the typical set analysis that is often used in the field of information theory (Cover and Thomas, 2006). We define the lypical allocation for each candidate of empirical distribution Q and prove the theorem by evaluating the error probability based on the typical allocation.
a complexity measure, but R can become zero if H (P) is not taken reasonably. For example, if we take H (P) E, 1/A, (rather than Σ, 1/42 that is widely used), any positive rate is not achievable around a small gap min, A, and thus R = O. When R = 0 any algorithm trivially satisfics PoE S exp(-TRe (P) + o()). This means that any algorithm minimax optimal in terms of H()), that is, such a choice of (P)) gives meaningless results.
Remark 2. (Trivial solutions) We can lake arbitrary H(P)
Remark 3. (Empirical best arm) Eq. (2) also involves the optimization of the recommen- dation arm J(Q) and rQ)). We can casily
that it is optimal to set J(Q) (Q), that is, to take the empirical best arm as the recommendation arm when p = Q since R(x)) otherwise becomes zero. However, J(Q)= = (Q) might not hold for $ P when P 5 Q.
Sections 2.2 2.4 that follow this section are for achieving the minimax optimal rate and are of theoretical interest. A reader who is mainly interested in an actual implementation may skip these sections.
2.2 PoE considering trackability
To construct provably optimal algorithm, we begin by refining the lower bound of the PoE by weakening the "strength" of the oracle algorithm.
We consider splitting T' rounds into B batches of size [T/B] or [T/B] + 1. Let
T (Qi( (2 Q2), ra(Qu, Q2. Qa)...., FBBQQ.. (T......... .Q))
be sequence of B functions, where r3 Q Ax corresponds the allocation in the b-th batch when the empirical means of the first 6 batches are Q³ = (Q1, Q Qo). Based on this class of allocation rule, we have the following PoE lower bound.
Theorem 2. (PoE Bound for batch-oracle algorithms) Under any sequence of algorithms TT and B BeN. N,
H(P) B
R((mr)) S sup
inf inf p ())6)) QBE (I
Σ
To,:((Qu, =: R (3)
(E[K],0E[B]
Here, the outer supremum is taken over all functions (.) (ri(), ro(:): Qkb AK and J(-): OKB - [K].
for
Theorem 1 the special case this theorem with B = 1. This bound corresponds to the best bound of oracle algorithms that determine the allocation of the b-th batch knowing the empirical distribution of this batch. It is tighter than that given in Theorem 1, as the oracle considered here cannot know the empirical distribution of the later batches b + 1, 2,..., B. It follows that we can obtain the following result.
,..,
Corollary 3. We have R < R for any E N.
We will show that R = limg-+00 R exists and is the best possible rate.
5

---

Algorithm 2: Delayed optimal tracking (DOT)
input: e-optimal solution r rB)*() (ri0) ................................ rB(),, (-()) of Eq. (3).
1 for 1, ..,........................... K do
L Set b2, 1 bj for i E [K] and draw arm for Ta times.
3 Set Qi := QK for the empirical mcan Qx-
for b K 1, K 2..... + K do
5 Compute Tb (ro,1 76....... [b, T K ( Q2...... .e.....Qu. Q6-k).
Draw each arm for no.; times, where nb, 2 rb,i (T' K) is taken so that Σie[K] Thi3 TB-
7
Observe empirical mean Qb of the batch. Update the stored empirical average as
0-- = Q K + rQ Qbxk),
where r denotes the element-wise product.
9 Recommend J(T)= = (Q' Q²²).
2.3 Matching algorithm
In this section, derive an algorithm that has a rate that almost matches R For any 6 > O, let (e)ooptimal solution of Eq. (3) be ()B,))))(())) (310),30) ... J(()) with objective at least
inf H(P) B
inf EBEORB (ET
E
(Q ((Q,..I))))) 2 R c.
(E(K)
We cannot naively follow the allocation rf, (Qt) because it requires the empirical mean of the current batch Qs, which is not fully available until the end of the current batch. The delayed optimal tracking algorithm (DOT, Algorithm 2) addresses this issue. This algorithm divides T rounds inlo B + K - 1 batches, where the b-th batch corresponds to (bTB- + 1, bT + ..... (b+ (b+1)TB) ) rounds for TB T/(B K - 1). Here, for simplicity, we assume that T is a multiple of B + K 1. In the other case, we can reach almost the same result by just ignoring the last
(B K- 1)LT K - 1)] rounds.
The crux of Algorithm 2 is to determine allocation rb by using the stored empirical mean D1=QQ.....Q Q'g rather than the true empirical mean Q1, Q QB+K-1: The first K batches are devoted to uniform exploration and the samples are stored in a queue (though this explanation is not strict, in that the actual procedure stored samples). At the b-th batch for 2 K + 1, we draw each arm i for na, R TaMs, 12 where r (ro,))ee[] is determined based on the stored samples in the queue. When drawing arm i for no,; times, we dequeue and open N&,, stored samples instead of opening actual no, samples, the latter of which are enqueued and kept unopened."
done after taking the mean of the
By the nature of this algorithm, we can ensure the following property.
Lemma 4. Assume that rum Algorithm 2. Then, the following inequality always holds:
B
R
Σ
Thes D(Qu.i)
(4)
B+K K-1
B+K H()
BE B+K-1]
Lemma 4 states that the empirical divergence of DOT given in the LHS of Eq. (4) almost matches the upper bound (HFHH(P) for sufficiently large B despite delayed allocation. Using this property, we obtain the following bound.
11 "gaain, e > can be arbitrarily small and is introduced to avoid the issue on the existence of the supremum.
12The -K in Line of Algorithm for the ceiling fractional values. This reflected term 1" in Theorem 5. If I' is large compared to B, K, the difference between I' and 1" does not matter. In other words, observations do not affect the allocation until opened.

---

Theorem 5. (Performance bound of Algorithm 2) The PoE of the DOT algorithm satisfies
BT
B -
P(J(T) $ (P) & exp
+ +,(K,
B -1 H(P)
where T" -B 1)K and (K, 2BK log(2T)).
The following corollary is immediate since fKK, B) o(T) holds for fixed K, B. Corollary 6. The worst-case rate of the DOT algorithm TDOT, satisfies
B
R({TDOrA]) 2
(R - t).
B+K K
2.4 Optimality
In this section, we show that the rate R(TDOT) DOT becomes arbitrarily close to optimal when we take sufficiently large number of batches B.
Theorem 7. (Optimality of DOT) Assume (P) be such that R < co. Then, the limit
R
lim R
B+200
exists. Moreover, for any 1j > 0, there exist parameters B, such that the following holds on the performance of the DOT algorithm:
inf (PP) lim log(1/P(J(T) & (P))))
R([TDOT,T]
R 17.
(6)
PEP T-x
T
Remark 4. (n-optimality) Since R((TT) & R holds for any sequence algorithms {TT} and B N, we have
R((Tr)) & inf
I lim inf
R
= Rgoo
BEN B
B-000
from Eq. (5).
Remark 4 states that the rate of the DOT algorithm given in Eq. (6) is optimal up to 17 for arbitrary small 7 > 0. This essentially states that, no algorithm can be r-better than DOT in terms of the rate against the worst-case instance P. In that sense, DOT is asymptotically minimax optimal. Note that the discussion here first takes T - oc, and then takes a large B, which implies that B should be taken o(T) (i.e., each batch has sufficiently large number of samples).
Remark 5. (Utility of the DOT algorithm) Although DOT (Algorithm 2) has an asymptoti- cally optimal rate Rgo difficult to calculate, or even approximate, the optimal solution of Eq. (3) since it is not an optimization of finite-dimensional vector but an optimization of function B which has a high input dimension proportional to B. In this sense, the DOT algorithm as well as Theorem 7 is purely theoretical thus far, and the existence of computationally tractable and provably optimal algorithun is an important open question.
Instead of pursuing the direction of batching, the subsequent sections rather focus on implementing Algorithm 1.
Learning
In this soction, we propose method to learn r(Q) Eq. (2) by utilizing neural network to practically realize R**-tracking in Algorithm 1. Throughout this section, we assume a class of algorithms that recommend the empirical best arm, which is guaranteed when P = º (see Remark 3). This section focuses on Bernoulli arms, and with slight abuse of notation, we use P; and Q; to denote the true mean and the empirical mean of arm i, respectively.
be optimal

---

Algorithm 3: Gradient descent method for 0
input: : learning rate 1) 1 while not converged do
/* Compute pmin and Qmin which minimizes the negative exponent */
2 Set Euin f- 00.
3
for #1 11 2,.,.... Nerue do Sample true parameters P from P uniformly at random.
5
for n22 = .., Nemp do
Sample Q from {Q Q (Q) (Z) 0}.
E(P, Q: 0) Emin then
puin + P. Qmin Q, Emin + E(pmin Qmin, 0)
Update parameters - V ( pmin Qmin; 0).
9
Algorithm 4: R -Tacking by Neural Network (TNN)
1 Draw each arm once.
2 for K + .,, T do Draw arm arg max (Qa, - 1)) 1))
N,(t - 1)/(t 1)).
4 return J(T) = arg max (T) (empirical best arm).
3.1 Learning allocation
Let re( o - Ax be neural network with set of parameters O. We consider alternately optimizing ro(+) and the worst pair of instances (P,Q), and we update 0 via mini-batch gradient descent. Given a complexity function H(P), Eq. (2) is defined as the minimum over all (P.Q) such that the best arm different. Our learning method (Algorithm 3) uses L mini-batches. Let
K (Q..
E(P,Q:0) H Σ rO.
Given allocation ræ, Eq. (7) the negative log- le-liiklihoodd (rate) of the bandit instance P against the empirical means Q. At each batch, it obtains the pair pmin Qmin such that Eq. (7) is minimized. Specifically, for each iteration, we sample V candidates of true mcans P uniformly from pk then for each P, we sample Nemp values of empirical mcans Q e OK such that (Q) (P) = 0 uniformly at random.
3.2 Tracking by neural network
Having trained rg, we propose the -e--Tracking by the neural network (TNN) algorithm (Algorithm 4), which is an implementation of Rso-Tracking by the trained neural network. This algorithm draws the arm such that the current fraction of samples N₂(t 1)/(t - 1) is the most insufficient compared to the learned allocation re(Q(t 1)).
4 Simulation
This section numerically tests the performance of the TNN algorithm." 14 We compared the performance of TNN (Algorithm 4) with two algorithms: Uniform algorithm, which samples each arm in a round-robin fashion, and Successive Rejects (SR, Audibert et al., 2010), where the entire trial is divided into segments before the game starts, and one arm with the smallest estimated mean reward is removed for each segment.
The source code of the simulation is available at https: wtw.h//...oottccchihieeeeeeeeeee budget-bai.
8

---

Unitorm
Unifoem
SR
SR TNN
SR TNN
TNN
probabiity of urror
Ocacle
Onacle
probabiity
10"1
500
1000 Tound
1.000
2000
1500
2000
round /
round
(a)
Instance 1, PoF
(b)
Instance 2, PoE
(c) Instance 3, PoF
TNN (word)
TNN (overage)
0.4
TNN (wont)
TNN (weest)
(average)
0.4
(average
(average
(average
rndking aTTH
0.3
madiin cster
0.3
touking
0.2
0.1
0.1
0.0
0.0
0.0
500
1000
1500
2000
500
1000
1500
2000
500
1000
1500
2000
(d) Instance 1, tracking error
(e) Instance 2, tracking error
(f) Instance 3, tracking error
Figure 1: Bernoulli bandits, K 3, 2000, average over 105 trials.
We consider Bernoulli bandits with K = arms, where each mean parameter is in [0, 1]. In particular, we consider the three sets of true parameters: (instance 1) P (0.5, 0.45, 0.3), (instance 2) P = (0.5, 0.45, 0.05), and (instance 3) P P= (0.5, 0.45, 0.45). The number of the rounds T fixed to 2000, and we repeated the experiments for 10 times.
4.1 Training neural networks
Here, we show experimental details for training neural networks for the TNN algorithm
discussed in Section 3.2.
We used the complexity measure Hi (P) = Eidr(p)) (P* P:)-2 as a standard choice of ((P). We used the neural network with four layers (including the input layer and output layer), where used the ReLU for the activation functions and introduced the skip-connection (He et al., 2016) between each hidden layer to make training the network casier. To obtaín the map to Ak. adopted the softmax function. The number of nodes in the hidden layers was fixed to K 3. We used AdamW (Loshchilov and Hutter, 2019) with a learning rate 10-3 and weight decay 10-7 to update the parameters.
For training the neural network, we ran Algorithm with Ntrue and Nrmpp 90. Fur- thermore, to allow the neural network to casily learn r, the elements of P = (P1, P2.... .2....,k) Pk) were sorted beforehand.
P2.
4.2 Experimental results
Figure illustrates the results our simulations. Each column corresponds to the result for each instance.
The first row ((a) (c)) shows the PoE of the compared methods when the arm with the largest empirical mean is regarded as the est estimated best arm J(l) at each round L. Here, the black line represents exp(-/inf info Σ, D(Q P:)), which corresponds to the exponent of the oracle algorithm that can perfectly track the allocation (Q.).. Therefore, the asymptotic

---

slope of TNN cannot be better than that of the black line. We can see from the figures that the slope of the TNN close the oracle algorithm and performs better than or comparable to the other algorithms. Note that this is the result. for fixed time horizon T. Although the final slope of SR seems to be steeper than that of TNN, it is just due to the fact. that SR not anytime and is an algorithm that divides T rounds into several segments.
The second row ((d) (f)) shows the tracking error of the TNN algorithm, which is defined as disc(t) - max Ira (Q()) NN(t)/t), which measures the discrepancy between the ideal allocation r. (Q)))) and the act allocation (2(L)/t. If this quantity is o(T) in almost all tests (including those in which the algorithm failed to recommend the best arm) and in all instances, then we can guarantee R = S The labels TNN (average), TNN (worst), and TNN (average in fail) correspond to the average tracking error of all trials, the worst-case tracking error and the average tracking error of all failed trials, respectively. The fact that "TNN (worst)' is small at T 2,000 implies that the gap between R8 and Rg is small, which supports the reasonablenest of algorithms based on 1850
5
Conclusion
This paper considered the fixed-budget best arm identification problem. We identified the minimax rate R on the exponent of the probability of error by introducing a matching algorithm (DOT algorithm). Optimization of rate R is very challenging implement, and we considered learning a simpler optimization problem of rate R by using a neural network (TNN algorithm). The TNN algorithm outperformed existing algorithms. Several possible lines of future work include the following points.
More scalable learning rQ):: TNN adopted a neural network to obtain the oracle allocation rQ).. While its empirical results are promising and support our theorel limited the case of K = 3 arms because the
findings, the current experiment learning is very costly even for small K. A more sophisticated learning algorithm is desired to realize R tracckng for larger K.
Learning complexity measure H(P): We have assumed the complexity measure ((P) is given exogenously. A principled way to choose H(P) is an interesting future work.
Identifying the existence (or nonexistence) of the gap: Although the empirical results suggest that R is very close (or maybe equal) to the optimal rate Rg for the Bernoulli case, a formal analysis of this gap for general cases is demanded since the DOT algorithm to achieve R is computationally almost infeasible.
A bound for another rate mcasure: we defined the worst-case rate by (1), which first takes the limit of T and then takes the worst-case instance P. Another natural choice of the rate would be to exchange them, that is, to consider
H(P)
R(((TT)) = inf inf inf T-2 PEPK T log(1/P(/(T) Iz(P)) < R((TT)).
Whereas Theorems and 2 on the upper bounds R(TT) are still valid for R' ((xTT)) < R((TT)), ), the current achievability analysis does not apply and analyzing the tightness of R for R' (((T)) is an open problem.
Acknowledgement
The authors thank the reviewers and the associated editor for constructive discussion and suggested corrections. To include the discussion during the review process, we have rewritten Sections B and G.1. We have also added Section C. All errors in the paper our own. TT was supported by JST, ACT-X Grant Number JPMJAX210E, Japan and JSPS, KAKENHI Grant Number JP21J21272, Japan. JH was supported by JSPS KAKENHI Grant Number JP21K11747.
10

---

References
Eves Audibert, Sébastien Bubeck, and Rémi Munos. Best arm identification in multi- armed bandits. In COLT 2010 The 23rd Conference on Learning Theory, pages 41-53.
Omnipress, 2010.
L. Jeff Hong, Weiwei Fan, and Jun Luo. Review on ranking and selection: A new perspective. Frontiers of Engineering Management, 8(3):321-343, Sep 2021.
Aurélien Garivier and Emilie Kaufmann. Optimal best arm identification with fixed confidence. In Conference on Learning Theory, Proceedings of Machine Learning Research, 2016.
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):1-42, 2016.
Alexandra Carpentier and Andrea Locatelli. Tight (lower) bounds for the fixed budget best arm identification bandit problem. In Conference on Learning Theory, 2016.
Tor Lattimore and Csaba Szepesvári. Bandit Algorithms. Cambridge University Press, 2020. doi: 00.101/998810557114
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):4281 4292, 2017.
Victor Gabillon, Mohammad Ghavamzadeh, and Alessandro Lazaric. Best arm identification: A unified approach to fixed budget and fixed confidence. In Advances in Newral Information Processing Systems, 2012.
Robert E. Bechhofer and Milton Sobel. A Single-Sample Multiple Decision Procedure for Ranking Variances of Normal Populations. The Annals of Mathematical Statistics, 25(2): 273 289, 1954. doi: 11..214/aoms/11777287777
Gary C. McDonald. A conversation with Shanti Gupta. Statistical Science, 13(3):291 305, 1998. doi: 10.1214/ss/ #0228995000
Warren Buckler Powell and 1lya O. Ryzhov. Optimal Learning. Second edition. Unpub- lished Manuscript, March 2018. URL
Chun-Hung Chen, Jianwu Lin, Enver Viccsan, and Stephen F. Chick. Simulation budget allocation for further enhancing theefficiency of ordinal optimization. Discrete Event Dynamic Systems, 10(3):251 270, July 2000.
Peter Glynn and Sandeep Juneja. large deviations perspective on ordinal optimization. In Winter Simulation Conference, volume 1. IEFF, 2004.
Peter I. Frazier, Warren B. Powell, and Savas Dayanik. knowledge-gradient policy for sequential information collection. SIAM J. Control Oplim., (7(5):2410-2453 sep 2008.
Thomas M. Cover and Joy A. Thomas. Elements of Information Theory. Wilcy-Interscienee, second edition, July 2006. ISBN 0471241954.
K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In 2016 IEEE Conference Computer Vision and Pattern Recognition (CVPR), pages 770 778, Los Alamitos, CA, USA, jun 2016. IEEE Computer Society.
Tlya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In International Conference Learning Representations, 2019.
11

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] See Section 1.2
(b) Did you describe the limitations of your work? [Yes] See Section 5
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes] This methodology paper and ethical concerns do not directly apply here.
2. If you are inchuding theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] Section
See
(b) Did you include complete proofs all theorctical results?
(Yss]
See Appendices
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL)? [Yes]
We will publish the source code upon acceptance. + published.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section 4
(c) Did you report error bars (e.g., with respect to the random seed after running experiments multiple times)? [Yes] Yes
(d) Did you include the total amount of compute and the type resources used (e.g,, type of GPUs, internal cluster, or cloud provider)? [Yes] See appendix.
4. If you are using existing assets (e.g.. code, data, models) or ourating/releasigg new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you'l re ssiing/urrttig' [N/A]
(c) Did you discuss whether the data you are shing/curatin contains personally
identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
12


Reviews:
[{"review_id": "_kYsZyab8M1", "reviewer": "Reviewer_RNv6", "summary": "The authors consider the problem of best arm identification in the fixed budget setting. The authors introduce a notion of global optimality specific to a prescribed complexity measure $H$. They establish a characterization of the optimal rate fo such notion via the rate $R^{go}$ (see Theorem 1) and provide Algorithm 1, which samples by tracking an $\\epsilon$ solution of the optimal allocation that achieves $R^{go}$. While algorithm 1 remains infeasible since it requires accesss to unavailable information, the authors propose weakened characterizations of the optimal rate $R^{go}$ via the rates $R^{go}_B, R^{go}_\\infty$ (See Theorem 2). These new rates take into account the fact that an algorithm throughout its learning may not have information about future empirical mean estimates of the arms. Then the authors provide Algorithm 2 (Delayed Optimal Tracking) which enjoys a guarantee that matches the lower bound of Theorem 2 (see Theorem 5 and Theorem 7). The proposed algorithms so far do require solving a nontrivial optimization problem. To remedy this, the authors propose an approach that uses a neural network to learning the optimal solution of such optimization problems, and provide along with that numerical experiments to consolidate their approach.\n", "questions": "\n- How could one choose the complexity measure? The authors claim that one cannot obtain an instance specific lower bound as in fixed confidence setting, which I am not convinced of. However, if this is the case, does this suggest some sort of trade-off when choosing what complexity measure to focus on? Could the authors comment on this?\n- By now we do have practical algorithm for the fixed confidence setting. Is there a big gain from tracking an allocation determined from solving the fixed budget lower bound instead of the fixed confidence lower bound? In Kaufmann et al. it has been shown that in the two armed bandit for the class of gaussian distributions the complexity measures that arise from both problems are the same, so perhaps there is no gain, and one could simply track allocations from the fixed confidence setting. Could the authors comment on this?\n- As far as I understand the results are only valid when $\\mathcal{Q}$ is restricted to the class of Gaussian distributions or Bernoulli distributions but not both at the same time. Could the author comment on this?\n", "limitations": "I think the authors have properly addressed the limitations of their work both theoretically and practically. The work remains theoretical at large, so I don't see any potential negative societal impact or ethical issue that apply.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n\n- This paper is well written paper with solid theoretical results, good literature review, and a clear presentation. This makes the paper easy to follow even though it is quite technical.\n- The problem considered by this work lacks considerable understanding in the literature and as highlighted by the authors remains poorly understood. Therefore, the theoretical results of this paper, especially the characterisations of the lower bound in section 2 (Theorem 1 and 2) appear to be worthwhile contributions in my opinion that further our understanding in the fixed budget setting.\n- It is really appreciated that that the authors did not stop at providing a perhaps theoretically good, but computationally infeasible algorithm. Instead the authors proposed a neural networked based learner to remedy this challenged and accompanied that with numerical experiments.\n\n\nWeaknesses\n\n- I am not fully convinced about the discussion in section 1.1. (lines 42-51) that one has to choose a complexity $H(\\cdot)$ to characterize optimality in the fixed budget setting. I do not have an answer but at the same time this opens the question of how one should choose the the complexity measure $H(\\cdot)$ which I think the author could clarify further. Is there a better complexity measure? are they even comparable in some sense?\n-  Another weakness of the current work is that the proposed algorithms whether they rely on neural networks or not remain largely impractical (the authors also highlighted this).\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "_8ibmwV5cxx", "reviewer": "Reviewer_BbC9", "summary": "The paper characterizes the optimal rate of error in the fixed budget best arm identification setting. It introduces two tracking algorithms as an endeavor for achieving the best error rate; the first algorithm is not practical but it theoretically achieves the optimal rate. The second algorithm solves a simpler optimization problem but it is computationally expensive. ", "questions": "1. Considering the similarity of your results to the one in Kaufmann et al. (2016) ($\\sup \\inf \\left(H(P)\\sum r D(Q \\| P) ... \\right)$ is first introduced in there), how is your analysis are different than them?\n2. How do your bounds compare to Carpentier and Locatelli (2016)? (See Major comment 1)\n\nPlease also see the \"Major comments\" section above.", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths*\n1. The problem considers an important open question in the BAI literature, namley FB BAI.\n2. The proposed algorithms seem to achieve the oracle rate in the experiments.\n\n\n**Major comments**\n1. The positioning of the paper seems inadequate. Carpentier and Locatelli (2016) already discussed the optimal rate for FB BAI problems. It could improve the paper to discuss how the work is different than theirs. Line 55 seems to only mention the fact that the constants in Carpentier and Locatelli (2016) are loose. How does your bound $R^{\\text{go}}_{...}$ compare to theirs as it does not have a closed form?\n2. The difference between FC and FB settings is an essential motivating point for designing FB BAI algorithms as there are already several near-optimal FC BAI algorithms in the literature. However, the discussion starting at Line 32 (and Appendix D) does not convey the message and needs clarifications. For instance, what is \"instant-wise optimal\"? Following up, how did you get the expression after Line 422?\n3. A concrete example for Remark 1 could explain what \"reasonably\" mean therein.\n4. Remark 2, Line 167: Why does $R(\\pi)$ become zero otherwise?\n5. How can we let $B\\to\\infty$ while it seems $B$ is the integer number of batches which needs to be $B\\leq T$ ?\n6. I could not understand the crux of Algorithm 2. Why is this algorithm called \"delayed\" ?\n\n**Minor comments**\n1. Submiting the code could improve the reproducibility of the results.\n2. Lin 159: It seems like $r^*(Q...$ should be used instead of $r(Q...$\n3. Line 197: Do you have the analysis showing that ignoring the last rounds does not hurt the results?\n4. Line 204: what does \"open $n_{b,i}$\"  means?\n5. Line 222: Is it $B \\mathbb{N}$ instead of $b\\in \\mathbb{N}$ ?\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "PInJ6EfHEX2", "reviewer": "Reviewer_f8dM", "summary": "It is known that the probability of error in identifying a best arm in a fixed-budget $T$ is bounded by $\\exp(-RT/H)$ where $H$ is a complexity term and $R$ quantifies the rate of decay as $T \\rightarrow \\infty$. This paper describes methods to possibly attain the best possible rate for the hardest instance in a given class, i.e., minimax optimal rate, which is called $R^{go}$. First a lower bound $R^{go}_B \\leq R^{go}$ is described, next an algorithm with error rate $O(R^{go}_B - \\epsilon)$ is described. Nevertheless, this algorithm assumes an $\\epsilon$-optimal solution to an intractable sup-inf optimization and thus cannot be implemented. Consequently, a heuristic $R^{go}$-tracking algorithm using neural network (TNN) is described and compared to other methods in experiments.", "questions": "* Algorithm 2 describes one of the key contributions by introducing the \"stored\" queue of means but I'm unable to fully understand. In Algorithm 2 pseudocode the input is assumed to be an oracle that can solve for $\\mathbf{r}^{B,*}$. From eq (3) the input to this optimization is the $\\mathbf{P}$ and $\\mathbf{Q}^B$ that attain the inf. \n\nBut in line 5 the allocation $\\mathbf{r}^*_{b-K}$ is computed. How this step can be realized without knowing all the elements of $\\mathbf{Q}^B$ which include $(\\mathbf{Q}'_{b-K+1}, .. , \\mathbf{Q}'_B)$ is unclear. \n\n* It seems when $B=1$ the quantity $R^{go} = R^{go}_B$ and for $B > 1, R^{go}_B < R^{go}$. Then why are we interested in $R^{go}_\\infty$, in the sense that it is going farther from the true oracle rate? Possible related, why is eq (21) true?\n\n* How sensitive is the choice of $N^{true}$ and $N^{emp}$ for the performance of TNN algorithm?", "limitations": "None noted", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Obtaining good bounds on the optimal minimax rate has not been considered a lot in the existing literature, possibly because it is a hard resource allocation problem. Viewed in this light, the problem is similar to dynamic programming. However the rate $R$ is defined when the budget $T \\rightarrow \\infty$, and this brings it closer to prior work in best arm identification. Overall, the task considered in this paper is novel. \n\nThe claims made in the paper seem to be technically well-supported. However the same cannot be said about the remarks. For eg, remark 1 says $R^{go}$ may be 0. But shouldn't the choice of $\\mathbf{Q}$ ensure at least one of the divergence terms is positive, and thus the outer sup over $\\mathbf{r}$ would make the objective positive? Remark 2 mentions that a $P$ may be in $\\mathcal{P}\\setminus \\mathcal{Q}$ without discussing the possible zero denominator in the KL divergence. Remark 3 mentions no algorithm can be better than DOT but I think the statement is only true for algorithms that are restricted to operate in a batched manner with equal-sized batches. \n\nThese comments are to the best of my understanding and I may have missed something as I felt the paper was generally quite hard to read. I do not understand the description in the introduction and section 1.1 about fixed budget BAI being impossible in an instance-wise optimal manner. For eg, the probability of error of successive rejects algorithm is at most $\\exp(-T/(\\log(K)H))$ which is optimal in order as described by Carpentier and Locatelli (2016). At some places, notation could be recapped to aid readability. For eg, in Theorem 2, it could be recapped that the domain of each $\\mathbf{r}_i$ is all possible collections $(\\mathbf{Q}_1, ..., \\mathbf{Q}_i)$ to emphasize the batched nature of algorithms to which the lower bound applies. In the proof of Lemma 10 it will be better to describe the proof for the base case. The proof of Theorem 2 could be made easier to read by adding more explanations for the notation. It is not clear to me what $\\mathbf{r}_1(\\mathbf{Q}^1; \\pi, \\epsilon)$ means.\n\nWhile the paper tries to address a hard problem, I believe some of the arguments need to be made more readable and explained bette for it to have a much higher impact. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "7nYcbonv4Wf", "reviewer": "Reviewer_tDsK", "summary": "This work studies best arm identification (BAI) under fixed budget. Two rates (of lower bounds) $R^{\\text{go}}$ and $R^{\\text{go}}_\\infty$ are derived, where a matching algorithm for $R^{\\text{}go}_\\infty$ is proposed despite computationally not trackable. Then a heuristic approach is proposed to empirically match $R^{\\text{go}}$.", "questions": "See weakness.", "limitations": "This work is most on maths and algorithm perspective, its social impact depends on the application of the proposed approach, which goes beyond the scope of current paper.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "(+) This work studies lower bounds on relatively less studied BAI with fixed budget. Since there are not many works in this area, these results are useful and can guide the design of new algorithms.\n\n(+) A lower bound matching algorithm for $R^{\\text{}go}_\\infty$ is proposed. Though still can be improved by reducing computationally overhead, it is still inspiring for the problem at hand.\n\n(-) Successive halving (SH) is not included in numerical tests.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept