Minimax Optimal Fixed-Budget Best Arm Identification in Linear Bandits
Authors: Junwen Yang
Vincent Tan
Venue: NeurIPS 2022 Accept (2022)
Keywords: best arm identification
linear bandits

Abstract: We study the problem of best arm identification in linear bandits in the fixed-budget setting. By leveraging properties of the G-optimal design and incorporating it into the arm allocation rule, we design a parameter-free algorithm, Optimal Design-based Linear Best Arm Identification (OD-LinBAI). We provide a theoretical analysis of the failure probability of OD-LinBAI. Instead of all the optimality gaps, the performance of OD-LinBAI depends only on the gaps of the top $d$ arms, where $d$ is the effective dimension of the linear bandit instance. Complementarily, we present a minimax lower bound for this problem. The upper and lower bounds show that OD-LinBAI is minimax optimal up to constant multiplicative factors in the exponent, which is a significant theoretical improvement over existing methods (e.g., BayesGap, Peace, LinearExploration and GSE), and settles the question of ascertaining the difficulty of learning the best arm in the fixed-budget setting. Finally, numerical experiments  demonstrate considerable empirical improvements over existing algorithms on a variety of real and synthetic datasets.

Minimax Optimal Fixed-Budget Best Arm Identification in Linear Bandits
Junwen Yang
Institute of Operations Research and Analytics National University of Singapore yang@u_ nus. edu
Vincent Y. F. Tan
Department of Mathematics Department of Electrical and Computer Engineering Institute of Operations Research and Analytics National University of Singapore vtanênus edu. sg
Abstract
We study the problem best arm identificaiinn linear bandits the fixed-budget setting. By leveraging properties of the G-optimal design and incorporating it into the arm allocation rule, we design a parameter-free free algorithm, Optimal Design- based Linear Best Arm Identification (OD-LinBAD) We provide a theoretical analysis of the failure probability of OD-LinBAL. Instead of all the optimality gaps, the performance of OD-LinBAT depends only the gaps of the top d arms, where d is the effective dimension of the linear bandit instance. Complementarily, we present minimax lower bound for this problem. The upper and lower bounds show that OD-LinBAI is minimax optimal up to constant multiplicative factors in the exponent, which is a significant theoretical improvement over existing methods (e.g., BayesGap. Peace, LinearExploration and GSE), and settles the question of ascertaining the difficulty of learning the best amm the fixed-budget setting. Finally, numerical experiments demonstrate considerable empirical improvements over existing algorithms on variety of real and synthetic datasets.
Introduction
The multi-armed bandit problem is a model that exemplifies the exploration-exxllottaioo tradeoff in online decision making. It has various applications in drug design, online advertising, recommender systems, and so on. In stochastic multi-armer bandit problems, the agent sequentially chooses an arm from the given arm unknown distribution associated with the chosen arm.
each time step and then observes random reward drawn from the
The standard multi-armed bandit problem, where the arms not correlated with another, has been studied extensively in the literature. While the regret minimization problem aims at maximizing the cumulative rewards by the trade-off between exploration and exploitation [14 the pure exploration problem focuses on efficient exploration with specific goals, e.g., to identify the best arm [T- There
complementary settings for the problem of best (i) Given T E N. the agent aims to maximize the probability time steps; (ii) Given 8 > 0, the agent aims to find the best arm with the probability of at least 1- in the smallest number of steps. These settings are respectively known as the fixed-budget and fixed-confidence settings.
identification: finding the best arm in at most T
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

In this paper, we consider the problem of best arm identification in linear bandits in the fixed-budge setting, In linear bandits. the arms are correlated through an unknown global regression parameter vector 0" E Rd. In particular, each arm i from the arm set A is associated with an arm vector a(i) E Rdd and the expected reward of arm i given by the inner product between 0* and a(i). Hence, the standard multi-armed bandits and linear bandits are fundamentally different due to the fact that for the latter, pulling one arm can indirectly reveal information about the other arms but in the former, the arms are independent.
wide range of applications in practice can be modeled by linear bandits. For example, Tao al. [2] considered online advertising. where the goal is to select an advertisement from pool to maximize the probability of clicking for web users with different features. Empirically, the probability of clicking can be approximated by a linear combination of various attributes associated with the user and the advertisements (such as age, gender, the domain, keywords, advertising genres, etc.). Moreover, Hoffman et al. [33 applied the linear bandit model into the traffic sensor network problem and the problem of automatic model selection and algorithm configuration.
Main contributions. Our main contributions are as follows:
(i) We design an algorithm Optimal Design- basedd Linear Best Arm Identification (OD-LinBAI). This computationally efficient algorithm utilizes a phased elimination- strategy in which the number of times each arm is pulled in each phase depends on G-optimal designs [14. Besides, OD-LinBAI is totally parameter-free whereas some existing methods (e.g.. BayesGap and Peace) require the knowledge of the problem instance (which is typically not known in practice).
(ii) We derive an upper bound on the failure probability of OD-LInBAL. The failure probability is a significant improvement over those of existing methods which we survey detail in Section 4.2 In particular, we show that the exponent of the failure probability depends on a hardness quantity H2. This quantity is function of only the first d optimality gaps, where d is the dimension of the arm vectors. This is surprising and significant difference compared to the upper bounds of the failure probabilities of various algorithms for best arm identification in standard multi-armed bandits 7 9 15 and BayesGap [13 in linear bandits, which all depend on a hardness quantity that depends on all the gaps. Moreover, OD-LinBAI improves the exponent of the error probability by factor of Olog d) over Peace [6] the worst-case sense or factor of ((log K)) /)ool d)) (which could be much larger than 1) over LinearExploration [17] and GSE [8] in general.
(iii)
Lastly, using ideas from Carpentier and Locatelli [10), we prove a minimax lower bound which involves another hardness quantity H1, By comparing 1,i Hy.lin. we show that OD-LinBAl is minimax optimal up to constants in the exponent. OD-L.iBAT is the first algorithm that provably achieves minimax optimality in this problem, and finally settles the question of ascertaining the hardness of learning the best arm in the exed-budger setting for linear bandits. In addition, experiments in both synthetic and real-world datasets firmly corroborate the efficacy of OD-LinBAI vis-à-vis other existing methods.
Related work. The problem of regret minimization in linear bandits was first studied by Abe and Long [19]. and has attracted extensive interest in the development of various algorithms (e.g.. UCB- style algorithms 24). Thompson sampling (25] (6)). In particular, in the book of Lattimore and Szepesvári 277. regret minimization algorithm based on the G-optimal design was proposed for linear bandits with finitely many arms. Although both this algorithm and our algorithm OD-LinBAI utilize the G-optimal design technique, they differ in numerous aspects including the manner of elimination and arm allocation, which emanates from the two different objectives.
For the problem of best arm identification in linear bandits, the fixed-coffidence setting has previously been studied in [2] [3/ J In particular, Soare et al. [28] introduced the optimal G-allocation problem and proposed static algorithm X3y-Oracle as well as semi-adaptive algorithm X Adaptive; see Remark 2 for more discussions on Soare et al. [28). Degenne et al. [32 treated the problem two-player zero-sum game between the agent and the nature, and thus designed an asymptotically optimal algorithm for the fixed-confidence setting.
The exed-budged setting for the problem of best arm identification in linear bandits has also been studied in a few previous and concurrent works. Hoffman al. [33 introduced a gap-based explo- ration algorithm BayesGap, which is a Bayesian treatment of UGapEb [8] for standard multi-armed

---

bandits. Peace by Katz- Latz-Samuels et al. [6] utilizes an experimental design based on the Gaussian- Width of the underlying arm set, which characterizes the geometry of the instance better in some instances. However, both BayesGap and Peace are computationally expensive and not parameter-free. Recently, Alieva et al. [7 introduced an elimination algorithm named LinearExploration, which also robust to moderate levels of model misspecification. Generalized Successive Elimination (GSE) by Azizi et al. [8] shares similar structure with LinearExploration and applies to generalized linear models. Nevertheless, none of the above is minimax optimal. See Section 4 and Section for more comparisons between OD-LinBAI and other existing algorithms.
2 Problem setup and preliminaries
Best arm identification in linear bandits. We consider the standard linear bandit problem with an unknown global regression parameter. In linear bandit instance v, the agent given an arm set A = [K], which corresponds to known arm vectors {a(1), (())), ...)..... {{K)} C IR.. At each time t, the agent chooses an arm At from the arm set A and then observes a noisy reward
X, (8", a( A,)) + 7)
where 8* E Rd is the unknown parameter vector and l) is independent zero-mean 1-subgaussian random noise.
In the fixed-budget setting, given a time budget 7 E N, the agent aims at maximizing the probability of identifying the best arm, i.e., the arm with the largest expected reward, with no more than T arm pulls. More formally, the agent uses an online algorithm II to decide the arm A! to pull at each time step and the arm 311 E A output as the identified best arm by time T. We abbreviate A! as A, and font as fout when there is no ambiguity.
For any arm i A, let p(i) = (0" a(i)) denote the expected reward. For convenience, we assume that the expected rewards of the arms are in descending order and the best arm is unique, That is to say, p(1) p(2) 2 2 p(K). For any suboptimal arm denote A; p(1) p(i) as the optimality gap. For ease of notation, we also set A = Ag. Furthermore, let & denote the set of all the linear bandit instances defined above.
rimensionality-rdduedd arm vectors. For any linear bandit instance, if the corresponding arm vectors do not span R. i... span((a(1)) (())aa)))@)),......... a2.) a (K))) & Rd. the agent work with set of dimensionality-redueee arm vectors {al (1), al (2), a' (K) C Rda,, that spans Rd with little consequence. Specifically, let B Radxd be a matrix whose columns form an orthonormal basis of the subspace spanned by (2).. .....a(K Then the agent can simply set a' d'(i) B a(i) for each arm i. To verify this, notice that BB is projection matrix onto the subspace spanned by {a(1), al2 2)................... ......,,.. a(K)) and consequently
p(i) = (8", a(i) (0", BBBBBBC a(1) (B (T.TT(()) a()) B
"00",a'(())
Note that 8" is the unknown parameter vector for original arm vectors while 6" = B 8* is the corresponding unknown parameter vector for the dimensionality-redeeee arm vectors. In the problem of linear bandits, what we really care about is not the original unknown parameter 0" itself but the inner products between 0* and the arm vectors a(i), which establishes the equivalence of original arm vectors and dimensionality-reddeee arm vectors.
In our work, without loss of generality, we assume that the entire set of original arm vectors {a(1), a())...., {(K) span I and d 2 However, this idea of transforming into dimensionality- reduced arm vectors is often used in our elimination-based algorithm. See Section for details.
Least squares estimators. Let A₁, Ag,... ... ., An be the sequence of arms pulled by the agent and X1, X2, X2..... X, be the corresponding noisy rewards. Suppose that the corresponding arm vectors ((A)), a(An)) span Rdd, then the ordinary least squares (OLS) estimator of 6* given by
Q-V-1 Σ a,
'Such an orthonormal basis can calculated efficiently with the reduced singular value decomposition. Schmidt process, etc.
"The situation that d = 1 is trivial: each arm vector is scalar multiple of another.
3

---

where V = Ei= a(Ar)a(A)) E R is invertible. By applying the properties of subgaussian random variables, a confidence bound for the OLS estimator can be derived as follows.
Proposition (Lattimore and Szepesvári [27] Chapter 201). If A1, A2...., An are deterministically chosen without knowing the realizations of X2....... Xn, then for any E R and i > O,
Pr
10
0" 221aa1 -1 log
S 8.
Remark 1. When the arm pulls are adaptively chosen according to the random rewards, Proposition ! no longer applies and an extra factor v has to be paid for adaptive arm pulls [23] Our algorithm avoids this issue by deciding the arm pulls at the beginning of each phase, and designing the OLS
estimator only based on the information from the current phase, See Section 3 for details.
G-optimal design. The confidence interval in Proposition I shows the strong connection between the arm allocation in linear bandits and experimental design theory [35]. To control the confidence bounds, we first introduce the G-optimal design technique into the problem of best arm identification in linear bandits in the fixed-budget setting. Formally, the G-optimal design problem aims at finding probability distribution
{a(i)= E A) + [o, 1] that minimises
g(TT) max ([a())] iEA
where ((x)=Exe x ((())))()))()))) Theorem
states the existence a small-support G-optimal
design and the minimum value of
Theorem (Kiefer and Wolfowitz (14). If the arm vectors {a(i): : E A} span IR the following statements are equivalent: (i) x² is a minimiser of g: (ii) π² is maximiser of f(T) = log det V (T); (iii) g( d. Furthermore, there exists a minimiser x" of g such that Supp (7r
d(d + 1)/2.
Remark 2. It is worth mentioning that the G-optimal design problem for finite arm vectors is a convex optimization problem while the original G-allocation problem in Soare et al. (28) for the fixed-confidence best arm identification in linear bandits is an NP-hard discrete optimization problem. A classical algorithm to solve the G-optimal design problem is the Frank-Wolfe algorithm (36), whose modified version guarantees linear convergence 37.. For our work, it is sufficient to compute an e-approximate optimal design with minimal impact performance. Recently, a near-optimal design with smaller support was proposed in I Lattimore et al. (38), which might be helpful in some scenarios. See Appendix A for more discussions on the above issues. To reduce clutter and ease the reading, henceforward in the main text, we assume that a G-optimal design for finite arm vectors can be found accurately and efficiently.
3 Algorithm
Pseudocode for our algorithm Optimal Design-based Linear Best Arm Identification (OD-LinBAI) is presented in Algorithm 0
The algorithm partitions the whole horizon into [lgg d] phases, and maintains active arm set A, in each phase r. The length of each phase roughly equals m, which will be formally defined in ①
Motivated by the equivalence of the original arm vectors and the dimensionalitt-reddcee arm vectors, at the beginning of each phase r, the algorithm computes a set of dimensionalliy--rdueedd arm vectors (ar( é E Ar-1) C RR which spans the dy-dimensional Euclidean space Rd,, This can be implemented based on the dimensionality-rddeee in an iterative manner (Lines 5 - 11).
arm vectors of the last phase (a)-1()) : A,-1)
After that, Algorithm | finds a G-optimal design म, for the current dimensionallty-reduce arm vectors, with restriction on the cardinality of the support when = 1. OD-LinBAl then pulls each arm in A according to the proportions specified by the optimal design म, Specifically, the algorithm chooses each arm i E A, exactly T, [i) (a, m is fixed among different phases and defined as
(i)) m times, where the parameter
[log d1 -1
T- - T-min(K K, d(d+1))
Σ 2
1=1
Mogz df
For an c-approximate optimal design n. g()) S (1 e)d.

---

Algorithm Optimal Design-based Linear Best Arm Identification (OD-LinBAI)
Input: time budget T, arm set A = [ and arm vectors (a(1), ((())))())....a((k))) C R
1: Initialize to = L, Ao + A and do = d.
2: For each arm Ag. set ao a())
3: Calculate m using Equation
4: for
to [log2 d] do 5: Set d, = dim (span (fa : Ar-1))).
6: if d, d then
7: For each arm i E Ar-1, set (r) i
8: else
9:
Find matrix B, E Rdd-ixd, whose columns form orthonormal basis of the subspace spanned by {a--1(1): For each arm i Ar-1, set (i) B, 11)) end if
Ar-1).
11:
if r
then
Find a G-optimal design (1) : Ar- } + [0, with SSupp (T+) d(d+1)
13:
14:
else
15:
Find a G-optimal design (i) : A + [0, 1].
16:
end
17:
Set
T₁(1) = |T (i)( m] and T, Σ T,().
iEA,-1
Choose each arm E A exactly (i(1) times.
19:
Calculate the OLS estimator:
4+ -1
0, V
Σ
(A)) with V Σ T.(
t=yy
iEA,-1
20:
For each arm i A estimate the expected reward:
(r(()) = (0,, (i))
Let A, be the set of [d/2"] arms in A,-1 with the largest estimates the expected rewards. Set l,+1 = lr + Tr.
22:
end for
Output: the only arm fout in A
Note that m O(T/ log, d) as as + oo with K fixed. Lemma I in Appendix shows with such choice of m, the total time budget consumed the agent is a significant role in the implementation as well as the theoretical analysis of Algorithm
than T. The parameter plays
Since the support of the G-optimal design n, must span Rd, the OLS estimator can be directly applied (Line 19). Then for each arm E Ar-1, an estimate of the expected reward is derived. Algorithm Peerithmmeeccuullpie decouples the estimates of different phases and only utilizes the information obtained in the current phase r.
At the end of each phase r, Algorithm I K [[dd/2] arms are eliminated in the first phase and about half of the active arms are eliminated in each of the following phases. Eventually, there is only single arm fout in the active set, which is the output of Algorithm
eliminates subset of possibly suboptimal arms. In particular,
Remark 3. It is worth considering the case of standard multi-armed bandits, which be modeled as a special case of linear bandits. In particular, for any arm E A = [K], the corresponding arm vector is chosen to be e,, which the 7th standard basis vector of R It follows that d K, 8" [p(1), p(2), p(K)] E R and arms not correlated with one another. A simple mathematical derivation shows that we can always use set of standard basis vectors of Rdd to represent the arm vectors regardless of which arms remain active during phase r. Also, the G-optimal design for a set of standard basis vectors is the uniform distribution on all of the active arms. Since
5

---

pulling one arm does not provide information about the other arms, the empirical estimates based on the OLS estimator are exactly the empirical means, Altogether, for standard multi- nuuti bandits, OD-LinBAl reduces to the procedure of Sequential Halving [2) which is a state-of- offte-of-theeee the-art algorithm for best arm identification in standard multi-armed bandits the fixed-budget setting.
Remark 4. The G-optimal design steps in Lines 13 and 15 in OD-LinBAl may be replaced by the X')-allocation (28) other techniques in experimental designs. However, work focuses establishing minimax optimality and thus the application of G-optimal designs, which optimize over the worst cases, is natural. The X'Aaallocatiin may result in better empirical performance but the improvement might be limited or even absent in worst-case scenarios. More importantly. as noted Degenne al. 32 Remark 1J, for the general XY>allocation problem, only heuristic solutions can be obtained (without convergence guarantees). Nevertheless, the G-optimal design problem can be provably solved with a linear convergence guarantee [37] Overall, the implementation of OD-LinBAl is computationally very efficient.
4
Main results
4.1
Upper bound
We first state an upper bound on the error probability of OD-LinBAI (Algorith))) D The proof of Theorem Dis deferred to Appendix B
Theorem 2. For any linear bandit instance E OD-LinBAl outputs an arm oou satisfying
Pr (oou # 115
[KK
+ +3 d
exp
m1
H2
where is defined in Equation
7 and
i
H2
max 25i5d A?
Theorem 2 shows the error probability of OD-LinBAl is upper bounded by
(-2
H2, log, d )
T
exp
which depends on T, and Hg.inn We remark that none the three terms is avoidable in view of our lower bounds (see Section 4.3
In particular, T the time budget of the problem and d the effective dimension of the arm vectors Given T and d. H2 quantifies the difficulty of identifying the best arm in the linear bandit instance. The parameter H2 generalizes its analogue
H2
max 2515 K A?
proposed by Audibert et al. 7 for standard multi-armed bandits. However, H2, is not larger than H2 since Hg.nin is only function of the first 1 optimality gaps while H2 considers all of the K optimality gaps. In the extreme case that all of the suboptimal arms have the same optimality Ak. the two terms H2 and H2 can differ significantly. In general,
gaps, i.e., Ag Ds we have
K
H H2
H22lin d
and both inequalities are essentially sharp. i.c., can be achieved by some linear bandit instances. This highlights& a major difference between best arm identification in the fixed-budget setting for linear bandits and standard multi-armed bandits. Due to the linear structure, arms are correlated and we can estimate the mean reward of one arm with the help the other arms. Thus, the hardness quantity H2jim is only a function of the top d arms rather than all the arms.
RReaal that assume the entire of original arm vectors {a(1), a(2), ... a(K) span Rd

---

4.2 Comparisons to other algorithms
We compare OD-LinBAI and other existing algorithms with respect to the algorithm design as well as the theoretical guarantees in the following.
Comparisons to BayesGap [13].
(i) The model used BayesGap parameter vector 0 is drawn from a known prior distribution .V 7² and the additive noise is required to be Gaussian. However, OD-LinBAI does not require these assumptions and the upper bound holds for any deterministic or random 0" E R
H is based on Bayesian linear bandits, where the unknown
(ii) The algorithm and theoretical guarantee of BayesGap explicitly require the knowledge of a hardness quantity H1 = Eigick A,2 to control the confidence region and then allocate exploration. However, this hardness quantity H1 is almost always unknown the agent in practice. In most practical applications, BayesGap has to estimate H1 in an adaptive way, which works reasonably well numerical experiments but lacks theoretical guarantees. (iii) BayesGap's 's error probability is upper bounded by
T
exp
(3)
H
which depends on T and H1- Compared with (3). the upper bound of OD-LinBAI in 2 has an extra log2 term. This is an interesting phenomena which is also present in standard multi-armed bandits 77 [0]. For best arm identification in standard multi-armed bandits, without the knowledge of the hardness quantity Hi, the agent has to pay a price of log, K for the adaptation to the problem complexity. In Theorem 3 prove similar result for linear bandits, in which the price of adaptation is log, d.
The upper bound (3) involves H1, function of all the optimality gaps. It holds that H1 2 H2 2 H2.lin- Thus, the upper bound of OD-LinBAl is not worse (and often better) in its dependence the harpeess/compplextt parameter.
Comparisons to Peace [6 (Also see Appendix
(i) To ensure there is only single arm in the final active set, the fixed-budget version of Peace requires 7 (i))), (a((())((())) (()))
for all suboptimal arms i (where 7()) is defined in Katz- Samuels et al. (66).. Note that this is not only a requirement for the theoretical bound but also a requirement for the feasibility of the algorithm. If this inequality not satisfied, the linear bandit instance needs to be "rescaled" before the algorithm is run, resulting in a larger bound on the error probability. In practice, the best arm unknown and the rescaling factor can thus only be conservatively bounded as min, > ((((()) (())) 2 min:,j ((((()) a(i))). However, the latter quantity can be miniscule. In particular, if there exist two arms that are nearly identical, i.e., min.,j ((f(t), a(i)}) is very small, the bound on the error probability may be larger than 1, and hence vacuous. Besides, the algorithm may terminate with most of its time budget wasted. In contrast, OD-LinBAI is fully parameter-free and does not require any information about the instance.
(ii) It is not straightforward to compare the error probabilities of OD-LinBAI and Peace in general since Peace involves some tricky terms that do not admit closed -formm expressions. Here consider the special case of standard multi-armes bandits (as discussed in 3)mark with all optimality gaps equal to the minimal one A1. In this case p" O d). 7" O d log d) and lo)( Ologg d): these terms appear in the denominator of the exponent in Peace's bound on the error probability. Therefore, the error probability of Peace is exp (- [-22(_ dloga ))
T&f )) while ours is exp (- ( )) which also shows Peace is not minimax optimal in the exponent in view of our lower bounds, to be presented in Section 4.3 See Appendix [ for the precise details of the above derivations.
Comparisons to LinearExploration 17 and GSE 18].
(i) The idea of elimination has been rell-veceived and is ubiquitous linear bandits. Although LinearExploration [17], GSE [18] and OD-LinBAI all leverage this idea, we emphasize that the elimination criteria for these algorithms are different. In particular, OD-LinBAl divides the time budget into roughly log, d phases while the other algorithms divide the budget into roughly log, K phases. Additionally, OD-LinBAl always controls the dimension of the active set in each phase, using the dimensionality reduction techinique in Section 2
7

---

Table 1: Comparisons of different hardness quantities: H1. Hz, H1,lin and H2,
H1 Eisisk 4,2
H2 = max i. 4,2 1 H1/Ha & l2g( 77]
H1,1in = -EisisA A,? H2, maxosigai A,? 15 H1.li// H22 I log(2d)
15 H1,i S K/d 1 H2/H22ii S K/d
(ii) The error probabilities of LinearExploration and GSE are upper bounded by exp
O F log, K and exp (-St(, (2(
(-1( TA7
x) respectively. Note that K 2 d. H2,lin S d/
and the hardness quantity H2 in Alieva et al. [17] is of the same order as H2,lin. Hence, our exponent of the bound on the error probability is an improvement over their exponents by factor of ((log, K)/ (log, d)), which may be much larger than 1.
4.3 Lower bound
Before stating the lower bound formally, introduce
i A,7
15iSd
This quantity is generalization of H1 that characterizes the difficulty of linear bandit instance. This parameter is also associated with the top d arms similarly to H2, See Table [ for a thorough comparison on different hardness quantities.
For any linear bandit instance v E &, we denote the hardness quantity H1,im of v as H1,1u (v) In addition, let {h) denote the set of linear bandit instances in & whose hardness parameter H1 lin upper bounded by (for some > 0), i.e., (h) = {v E E H1,in (v) S h).
Theorem 3. IfT 2 h² (og(6Td)) ///900, then
240T
min max Pr [ + 1] wEE(N)
exp
h
Further h 2 15d?, then
2700T
min max wEE(K)
Pr
III pout * 1] exp
exp
H1 (v) log
The proof of Theorem 3 is deferred to Appendix D We emphasize that even though the proof of the lower bound follows some common ideas behind the proof's of most minimax lower bounds in bandit algorithms for various purposes, its value does not lie in its technical novelty, but rather that the result is right vis-à-vis the upper bound we have derived based on the OD-LinBAI algorithm. The usual strategy, which is the strategy we adopt here, is to construct and analyze specific hard instances. In particular, we leverage the instances in Carpentier and Locatelli [10] for standard multi-an armed bandits to construct hard linear bandit instances for any arbitrary K and d. We discuss the tightness of the lower bound in the following.
Theorem 3 first shows that for any best arm identification algorithm II even with the knowledge of an upper bound h on the hardness quantity H1,li there exists linear bandit instance such that the error probability is at least
exp (-o
Furthermore, for any best arm identification algorithm II, without the knowledge of an upper bound h on the hardness quantity H1 there exists linear bandit instance such that the error probability least
exp (-0
H H (v) loga d (
T
)))
(5)
When there is no ambiguity, Hi,ii will also be used.
8

---

Comparing the lower bounds 4 and (5) in two different settings, we show that the agent has to pay price of log, in the absence of the knowledge about the problem complexity. Finding best arm identification algorithm that matches the lower bound (4) remains an open problem since the upper bound of BayesGap (3) involves H1 but not Hiji However, notice that the knowledge about the complexity quantity which is required for BayesGap is usually unavailable in real-life applications.
Now we compare the upper bound on the error probability of OD-LinBAI in (2) with the lower bound (5. Table I shows that H Jin 2 H2.lin always holds. Therefore, the upper bound in (2) is not larger than the lower bound in (5) in the exponent up to absolute constants. This shows OD-LinBAI (Algorithm[) 1 is minimax optimal up to multiplicative factors in the exponent and the upper bound cannot be improved an order-wise sense in the exponent general. At the same time, note that the upper bound holds for all instances while the lower bound is a minimax result which holds for specific instances. Since an upper bound can never be smaller than lower bound, we know that the difficult instances for the problem of best arm identification in linear bandits in the fixed-budget setting are those whose H1, and H2 are of the same order.
Numerical experiments
In this section, evaluate the performance of our algorithm OD-LinBAI and compare it with Sequential Halving (9) BayesGap 13]. Peace [16), LinearExploration 17 and GSE [18). For BayesGap, there two versions: one is BayesGap--race Oracle, which is given the exact information of the required hardness quantity H1; the other is BayesGap-Adaptive, which adaptively estimates the hardness quantity by the three-sigma rule. In each setting, the reported error probabilities of different algorithms are averaged over 1024 independent trials and the (tiny) error bars indicate the standard errors of the error probabilities. We present the results of one synthetic dataset here. Additional implementation details and numerical results (including another synthetic dataset, one real-world dataset and comparison the recent LT&S algorithm for best arm identification in linear bandits with fixed confidence (33) are provided in Appendix E
5.1 Synthetic dataset I: a hard instance
This benchmark dataset, in which there are numerous competitors for the second best arm, was considered for the problem of best arm identifi- cation in linear bandits in the fixed- confidence setting [30] 311 (33. Simi- larly, we consider the situation that d 2 and K 2 3. We assume that the additive random noise fol- lows the standard Gaussian distribu- tion (0, 1). For simplicity, we set the unknown parameter vector 0* [1,0]. There one best arm and worst arm, which correspond to the arm vectors a(1) = [1, 0] and a(K) = [cos(33 /4), sinnt/n//// [ respectively. For any arm (2,3....,
Errur probnbility
0.8
Error grubaliiitty
0.8
66
0.6
82
0.2
0
10
15
20
25
10
70
30
40
50
K
K
OD-LinBAI
BaynsGap- Oracle
Peence
GSE
Sequential Halving
BayreGag-A Adipappiiveee
LinescEeploration
Figure 1: Error probabilities for different numbers of arms K with T 25, 50 from left to right.
Bzsor prolalaiity e
08
Eerue probslsllty
0.0
1), the correspond- ing arm vector is chosen to be a(i) [cos(m/44 /// + sin(s + 6:)]T with Φ; drawn independently from (.09).. Therefore, there are K-2 almost second best arms. Considering the definitions of four hardness quantities, it holds that à H2,in-
0.6
1'
%0
T
T
OD-LiaBAI Sequential Halving
BayesGap-Ornd
Poace
GSE
BayesCap Adaptive
LisoueEppharation
H1 H2 K Hi.in K
Hence this is a hard instance in sense that the linear structure is ex-
Figure Error probabilities for different time budgets T with K = 25, 50 from left to right.

---

tremely strong. A good algorithm needs to fully utilize the correlations of the arms to obtain information as efficiently as possible.
The experimental results with fixed 7 and K are presented in Figure and Figure 2 respectively. In terms of this hard linear bandit instance, OD-LinBAl is clearly superior compared to its competitors. In fact, OD-LinBAI consistently pulls only one arm from the K - 2 almost second best arms and thus suffers minimal impact from the increase K.
Conclusions and Future Work
We introduce the G-optimal design technique into the problem of best arm identification in linear bandits in the sxed-budget setting. We design a parameter-free free and efficient algorithm OD-LinBAL. To characterize the difficulty of a linear bandit instance, and H2.lnn The upper bound of the error probability of OD-LinBAl and minimax lower bound of this problem are respectively characterized by H1 Jin and H2, instead of their analogues H1 and Hz in standard multi armed bandits. For the first time, minimax optimality (up to constant multiplicative factors in the exponent) has been achieved in this problem. While submit that the ingredients that constitute OD-LinBAI are not surprising in the bandit literature. an open problem thus far has hence been solved in this contribution (by the careful derivation of upper bound the error probability of OD-LinBAl and an accompanying minimax lower bound). Our theoretical findings also supported by the considerable improvements of the empirical performance of OD-LinBAI vis-à-vix vis existing algorithms on benchmark datasets.
introduce two hardness quantities Hi
A direction for future work is to design an instance-depender asymptotically optimal algorithm for this problem. However, finding such an algorithm or an instance-dependent asymptotic lower bound for the problem of best arm identification in standard (i.e., K-armed) multi-armed bandits in the fixed- budget setting remains open. Finally, as Thompson sampling [[] has been successfully extended to pure exploration in standard multi-armes bandits (39, it is interesting to study whether this technique can be generalized to linear bandits, both the fixed-budget and fixed-confidence settings.
Acknowledgments and Disclosure of Funding
This research/project is supported by the National Research Foundation Singapore and DSO National Laboratories under the AI Singapore Programme (AISG Award No: AISG2-RP-2020-011) and by Singapore Ministry of Education (MOE) AcRF Tier I Grants (A-0009042-01-00 and A-8000189-01- 00).
10

---

References
[1] William Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, (5(3/4):285-2944 1933.
[2] Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Learning, 47(2):235-25 22062225--66.20 2002.
[3] Sébastien Bubeck, Nicolo Cesa-Bianchi, al. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends8 in Machine Learning, 5(1):1-122, 2012.
[4] Shipra Agrawal and Navin Goyal. Analysis of Thompson sampling for the multi- bandit problem. In Conference on Learning Theory, pages 39-1. JMLR Workshop and Conference Proceedings, 2012.
[5] Eyal Even-Dar, Shie Mannor, Yishay Mansour, and Sridhar Mahadevan. Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. Journal of Machine Learning Research, 7(6), 2006.
[6] Sébastien Bubeck, Rémi Munos, and Gilles Stoltz. Pure exploration multi-armed bandits problems. In International Conference Algorithmic Learning Theeory pages 23-37. Springer, 2009.
[7] Yves Audibert, Sébastien Bubeck, and Rémi Munos. Best arm identification in multi-armed bandits. In Conference on Learning Theory, pages 41-53, 2010.
[8] Victor Gabillon, Mohammad Ghavamzadeh, and Alessandro Lazaric. Best arm identification: unified approach to fixed budget and fixed confidence. Advances Neural Information Processing Systems, 25, 2012.
[9] Zohar Karnin, Tomer Koren, and Oren Somekh. Almost optimal exploration in multi-armed bandits. In International Conference on Machine Learning, pages 1238-1246. PMLR, 2013.
[10] Alexandra Carpentier and Andrea Locatelli. Tight (lower) bounds for the fixed budget best arm identification bandit problem. In Conference on Learning Theory, pages 590-604. PMIR, 2016.
[11] Aurélien Garivier and Emilic Kaufmann. Optimal best arm identification with fixed confidence. In Conference on Learning Theory, pages 1998-107. PMLR, 2016.
[12] Chao Tao, Saúl Blanco, and Yuan Zhou. Best arm identification linear bandits with linear dimension dependency. In International Conference Machine Learning, pages 4877-4886. PMLR, 2018
[13] Matthew Hoffman, Bobak Shahriari, and Nando Freitas. On correlation and budget constraints model-based bandit optimization with application to automatic machine learning. In Artificial Intelligence and Statistics, pages 365-374. PMLR, 2014.
[14] Jack Kiefer and Jacob Wolfowitz. The equivalence of two extremum problems. Canadian Journal of Mathematics, 12:363-366, 1960.
[15] 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 42292, 2017.
[16] Julian Katz-Samuells Lalit P. Jain, Zohar S. Karnin, and Kevin G. Jamieson. An empirical process approach to the union bound: Practical algorithms for combinatorial and linear bandits. Advances in Neural Information Processing Systems, 33, 2020.
[17] Ayya Alieva, Ashok Cutkosky, and Abhimanyu Das. Robust pure exploration in linear bandits with limited budget. In International Conference on Machine Learning, pages 187-195. PMLR, 2021.
11

---

[18] MohammadJavad Azizi, Branislav Kveton, and Mohammad Ghavamzadeh. Fixed-budged best-arm identification in structured bandits. In International Joint Conference on Artificial Intelligence, pages 2894, 2022.
[19] Naoki Abe and Philip M Long. Associative reinforcement learning using linear probabilistic concepts. In International Conference on Machine Learning, pages 3-11, 1999.
[20] Peter Auer. Using confidence bounds for exploitation-exploraiio trade-offs. Journal of Machine Learning Research, 3(Nov):397-422, 2002.
[21] Varsha Dani, Thomas P. Hayes, and Sham M. Kakade. Stochastic linear optimization under bandit feedback. In Conference Learning Theory, pages 355-366, 2008
[22] Paat Rusmevichientong and John N Tsitsiklis. Linearly parameterized bandits. Mathematics of Operations Research, 35(2):395 411, 2010.
[23] Yasin Abbasi- Yadkor,, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, volume 11, pages 2312-2320, 2011.
[24] Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff functions. In Artificial Intelligence and Statistics, pages 208-214. PMLR, 2011.
[25] Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoffs. In International Conference on Machine Learning, pages 127-135. PMLR, 2013.
[26] Mare Abeille and Alessandro Lazaric. Linear Thompson sampling revisited. In Artificial Intelligence and Statistics, pages 176-184. PMLR, 2017.
[27] Tor Lattimore and Csaba Szepesvári. Bandit Algorithms. Cambridge University Press, 2020.
[28]
Marta Soare, Alessandro Lazaric, and Rémi Munos. Best-arm identification in linear bandits. In Advances in Neural Information Processing Systems, 2014.
[29] Liyuan Xu, Junya Honda, and Masashi Sugiyama. A fully adaptive algorithm for pure explo- ration in linear bandits. In International Conference on Artificial Intelligence and Statistics, pages
PMLR, 2018
[30] Mohammadi Zaki, Avinash Mohan, and Aditya Gopalan. Towards optimal and efficient best arm identification in linear bandits. arXiv preprint 1rX.vv191..01695, 2019.
[31] Tanner Fiez, Lalit Jain, Kevin G. Jamieson, and L. Ratliff. Sequential experimental design for transductive linear bandits. In Advances in Neural Information Processing Systems, 2019,
[32] Rémy Degenne, Pierre Ménard, Xuedong Shang, and Michal Valko. Gamification of pure exploration for linear bandits. In International Conference on Machine Learning, pages 2432- 2442. PMLR, 2020.
[33] Yassir Jedra and Alexandre Proutiere. Optimal best-arm identification in linear bandits. Ad- vances in Neural Information Processing Systems, 33, 2020.
[34] Abbas Kazerouni and Lawrence M Wein. Best arm identification in generalized linear bandits. Operations Research Letters, 3353)336-- 2021.
[35] Friedrich Pukelsheim. Optimal Design of Experiments. SIAM, 2006.
[36] Marguerite Frank and Philip Wolfe. An algorithm for quadratic programming. Naval Research Logistics Quarterly, 3(1-2):95-110, 1956.
[37] S Damla Ahipasaoglu, Peng Sun, and Michael J. Todd. Linear convergence of a modified Trank-Wolfe algorithm for computing minimum-volume enclosing ellipsoids. Optimisation Methods and Software, 23(1):5-19, 2008.
[38] Tor Lattimore, Csaba Szepesvari, and Gellert Weisz. Learning with good feature representations in bandits and in RL with generative model. International Conference on Machine Learning, pages 5662-5670. PMLR, 2020.
12

---

[39] Daniel Russo. Simple bayesian algorithms for best arm identification. In Conference on Learning Theory, pages 1417-1418. PMLR, 2016.
[40] Xuedong Shang, Rianne Heide, Pierre Menard, Emilie Kaufmann, and Michal Valko. Fixed- confidence guarantees for bayesian best-arm identification. In International Conference Artificial Intelligence and Statistics, pages 1823-1832. PMLR, 2020.
[41] Chao Qin and Daniel Russo. Adaptivity and confounding in multi-armed bandit experiments. arXiv preprint arXiv:2202.09036, 2022.
[42] Mare Jourdan, Rémy Degenne, Dorian Baudry, Rianne de Heide, and Emilic Kaufmann. Top two algorithms revisited. arXiv preprint arXiv:2206 050,99206.09999 2022.
[43] Michael J. Todd. Minimum-volume ellipsoids: Theory and algorithms. SIAM, 2016.
[44] Tony Cai, Jianqing Fan, and Tiefeng Jiang. Distributions of angles in random packing spheres. Journal of Machine Learning Research, 14:1837, 2013.
[45] Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL http::ttt///hhhiee ics. uci, edu/ml ml
13

---

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]
(b) Did you describe the limitations of your work? [Yes] See Section 6
(c) Did you discuss any potential negative societal impacts of your work? [No]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes] See Appendix and the code in the supplementary.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [No]
(c) Did you include any assets either in the supplemental material URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you's 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating 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, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "_ToLRD1crt6", "reviewer": "Reviewer_RdL2", "summary": "This work studies linear bandit with the goal of identifying the best arm. The goal is to minimize the error probability when the best arm is not identified with limited number of pulls. The contribution of this paper is three-fold: 1) The author(s) introduced an elimination-based algorithm called OD-LinBAI utilizing the G-optimal design. Compared with the prior arts, the proposed one is parameter-free. 2) The author(s) also presented a lower bound, which shows that OD-LinBAI is nearly optimal. 3) Experiment results are presented to demonstrate the superior performance of the proposed algorithm.", "questions": "When the author(s) discuss the optimality of the proposed algorithm, $\\Omega( \\frac{K}{d} + \\log_2(d) )$ is omitted. Could the author(s) help clarify the reason why such parameter can be omitted? Under the current presentation, it is hard for me to believe the proposed algorithm is minimax optimal.", "limitations": "N/A", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "* Strengths\n\n** This paper is written well and in good presentation which make it easy to follow.\n** The newly proposed algorithm OD-LinBAI is parameter-free and computation-efficient, which makes it easier to be applied to real-world applicaitons.\n** Both synthetic and real-world experiments are provided to prove the superior performance of the proposed policy.\n\n* Weaknesses\n\n** The ideas and techniques applied in this paper are not new. Specifically, the proposed algorithm is quite similar to the one proposed in [1] although the latter one targets best arm identification under fixed-confidence setting. I am not saying it is a bad thing since the goals of the problems in these two papers are different. However this will harm the originality of this paper.\n\n[1] Chao Tao, Saúl Blanco, and Yuan Zhou. Best arm identification in linear bandits with linear\n403 dimension dependency. In International Conference on Machine Learning, pages 4877–4886.\n404 PMLR, 2018.\n\n** There is still some gap between the upper and lower bounds despite the constant parameters inside the exponent. In particular, the parameter is $\\Omega( \\frac{K}{d} + \\log_2(d) )$.", "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": "Bk5REC7t9zw", "reviewer": "Reviewer_W2wD", "summary": "The main contributions:\n1. Novel Algorithm for Linear Bandits \n2. Upper and Lower performance bounds\n3. Numerical Experiments\n4. (smaller) comparision and collation of existing methods.\n\nThe authors propose a new algorithm that combines various advancements of previous work and add their own novel contribution in the usage of G-optimality. They then proceed to show differences to existing algorithms and to prove lower and upper bounds. The proof for mini-max is argued verbally and more loosely than the rest of the paper. Numerical results then demonstrate the effictiveness on one experimental setup.\n", "questions": "Questions:\n1. What do you mean by \\delta_1 = \\delta_2 in line 104? (I assume that you mean the value is the same of the deltas, is that true for all of them?)\n2. It is unclear in the presentation of the paper whether the vectors a(i) are available to the algorithm or not. (The reviewers assumption is that they are).\n3. The verbal argument of Mini-max needs to be improved, as it actually shows that it isn't a strict mini-max, rather only an approximate one. The suggestion would be to analyse this better and to show which problem instances lead to what bounds. \n4. (smaller suggestion) Also the multiplicative constants of the mini-max bound would be interesting to analyse.\n5. Perhaps adding more details on the experimental setup would be helpful too (as opposed to looking up references).", "limitations": "Limitations:\n1. Mini-Max is perhaps not strictly satisfied and so the core claim of the paper is slightly in question.\n\nSocietal Impact:\n1. Everything seems to have been addressed. ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strenghts:\n1. Strong and Novel (and complex) Algorithm\n2. Good mathematical analysis and comparison to other papers\n3. Good Upper and Lower Bound Proofs\n4. Good Numerical Results.\n\nWeaknesses:\n1. Weak verbal \"proof\" of Mini-max.", "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": "-EB0lZBfJf2", "reviewer": "Reviewer_4Xns", "summary": "This paper proposes a study of fixed budget BAI with linear bandits. The authors derive a minimax lower bound for linear BAI based on the lower bound provided by Carpentier and Locatelli and propose an algorithm with an upper bound matching the lower bound.", "questions": "The following paper may be a relevant study (the authors do not have to cite it, as it is not peer reviewed), \n\nhttps://arxiv.org/pdf/2202.09036.pdf", "limitations": "See the above comments. ", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The authors' work is based on ideas that seem natural and convincing in the context of BAI study. The theoretical contributions are not surprising and the results may be somewhat obvious given the existing context. However, it is a result that deserves to be adopted in this field. Therefore, I vote to weak accept.\n\n---- After receiving a reply from the author ----\n\nI thank the authors for their replies to my comments. First, \"weak accept\" in my comment was a typo for \"borderline accept\". After receiving your reply, I checked the submitted manuscript again, but the scores were still the same.\n\nThis study deals with BAI for linear bandits in a fixed budget setting, which has not been well studied. In that sense, it is interesting. However, as a high-level comment, I felt that there is little strong technical novelty. In that sense, I do not think it makes a strong contribution.\n\nIn conclusion, while I do not strongly support acceptance, there is no reason to reject it, and there is a novelty in the proposed method. For this reason, I have voted to borderline the scoring, although the score may change after discussion among the reviewers.\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": "-0qsTEP504V", "reviewer": "Reviewer_MHo7", "summary": "The paper studies the problem of best arm identification in linear arms, with a budget $T$. A key element in their algorithm is the utilization of a G-optimal design to select arms, resulting in a parameter-free algorithm at each steps eliminates non-optimal arms. The authors provide theoretical results for the probability error depending only on the top $d$ arms, where $d$ is the effective dimension of the arm vectors seen as a vector space. The authors compare their algorithm to other previous algorithms and prefer experiments showcasing the empirical and theoretical improvements of their algorithm from the previous ones. \n\n", "questions": "Would it make sense to add \"with budget\" to the title of the paper?\n\nIn line 306, you write \"cannot be improved in an order-wise sense in the exponent in general.\" Could you please explain what is meant by \"order-wise\" in this context?", "limitations": "The authors do not seem to mention any real-life applications that their work can have. They do mention other contexts where bandits are applied in the real world, but not including a budget setting. I think they would benefit from adding a potential application in industry of their work.\n\nThey also do not discuss any negative societal impact of their work, but I think for theory papers this is a bit harder to do. ", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\nTheir algorithm has several improvements from previous algorithms in the literature. In particular, while the idea of partitioning the set of arms into pieces and eliminating certain pieces of the set at each step isn't new, most divide the budget into $\\log_2 K$ phases, where $K$ is the number of arms. The author(s)'s algorithm divides the budget into $\\log_2d$ phases, where $d$ is the effective dimension of the set of arms as a vector space. Moreover, when compare to Peace in Katz-Samuels, the algorithm does is fully parameter-free, and does not need that suboptimal arms satisfy a certain inequality is not satisfied. If the inequality is not satisfied, the linear bandit instance needs to be rescaled before Peace is run, resulting in a larger bound on the error probability. Furthermore, the exponential term of the error probability is improved by logarithmic factors from Katz-Samuels et al (2020), Ayya et al (2021), and Azizi et all (2021). Finally, it seems their algorithm performs well empirically. \n\nAnother important point is that their lower bound is tight and their algorithm is minimax optimal up to multiplicative factors in the exponent. \n\nWeakness:\n\nThe authors do not seem to directly address potential applications and limitations of their work. I think they would benefit from including a real world example where linear bandits with a budget is used. \n\nMinor typographical error\nLine 182: $\\theta^*$ ... change the \"$\\cdots$\" for \"$\\ldots$\"", "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