Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The main contributions:
1. Novel Algorithm for Linear Bandits 
2. Upper and Lower performance bounds
3. Numerical Experiments
4. (smaller) comparision and collation of existing methods.

The 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.

strengths_and_weaknesses: Strenghts:
1. Strong and Novel (and complex) Algorithm
2. Good mathematical analysis and comparison to other papers
3. Good Upper and Lower Bound Proofs
4. Good Numerical Results.

Weaknesses:
1. Weak verbal "proof" of Mini-max.
questions: Questions:
1. 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?)
2. 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).
3. 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. 
4. (smaller suggestion) Also the multiplicative constants of the mini-max bound would be interesting to analyse.
5. Perhaps adding more details on the experimental setup would be helpful too (as opposed to looking up references).
limitations: Limitations:
1. Mini-Max is perhaps not strictly satisfied and so the core claim of the paper is slightly in question.

Societal Impact:
1. Everything seems to have been addressed.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: 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. 


strengths_and_weaknesses: Strengths

Their 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. 

Another important point is that their lower bound is tight and their algorithm is minimax optimal up to multiplicative factors in the exponent. 

Weakness:

The 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. 

Minor typographical error
Line 182: $\theta^*$ ... change the "$\cdots$" for "$\ldots$"
questions: Would it make sense to add "with budget" to the title of the paper?

In 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.

They also do not discuss any negative societal impact of their work, but I think for theory papers this is a bit harder to do.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: 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.
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.

---- After receiving a reply from the author ----

I 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.

This 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.

In 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.

questions: The following paper may be a relevant study (the authors do not have to cite it, as it is not peer reviewed), 

https://arxiv.org/pdf/2202.09036.pdf
limitations: See the above comments.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: 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.
strengths_and_weaknesses: * Strengths

** This paper is written well and in good presentation which make it easy to follow.
** The newly proposed algorithm OD-LinBAI is parameter-free and computation-efficient, which makes it easier to be applied to real-world applicaitons.
** Both synthetic and real-world experiments are provided to prove the superior performance of the proposed policy.

* Weaknesses

** 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.

[1] Chao Tao, Saúl Blanco, and Yuan Zhou. Best arm identification in linear bandits with linear
403 dimension dependency. In International Conference on Machine Learning, pages 4877–4886.
404 PMLR, 2018.

** 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) )$.
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
review_title: null

Meta-review: metareview: This paper proposed an algorithm and presented a good theoretical evaluation. In particular, the tight lower bound is a nice theoretical contribution.
It is also good that it appears to be descriptively and mathematically sound.

The novelty of the algorithm has been questioned by some reviewers, but even with that contribution, it is shown to have some sufficient advantage.

confidence: Less certain
Decision: Accept