Venue: NeurIPS 2022 Conference

Reviews:

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 presents a new algorithm and analysis for multi-fidelity
best-arm identification.  It builds on the ideas of previous
algorithms that do successive elimination of arms until only one is
left.  A unique aspect is their joint consideration of the costs and
accuracies of each fidelity level.  They demonstrate their method
empirically on a couple toy/synthetic problems.

strengths_and_weaknesses: The paper is well written and covers the prior work well.  My only
concern is that the contributions are relatively incremental given the
large amount of prior work on best arm identification, and
multi-fidelity methods.

The idea of using multi-fidelity best arm identification as a planning algorithm is interesting.  Perhaps that needs to be left for another paper but it would be interesting to explore it more and see how it compares to SOTA planning algorithms.

questions: none
limitations: none
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 multi-fidelity best arm identification (BAI). Here, we have a bandit model
with M different fidelities. On each round, a decision-maker should choose which arm to
pull and which fidelity to pull the arm at. It's goal is to identify the best arm (the arm
with the largest mean at the highest fidelity), but can pull the arms at lower fidelities
to obtain cheaper approximations at lower cost. The authors assume that the lower
fidelities may be biased from the highest fidelity, but these biases are bounded by some known
quantity.
They first prove a lower bound for this problem and describe a racing-style algorithm
which achieves this lower bound under certain assumptions on the biases and costs.


Multi-fidelity bandits are well-studied in the regret minimization setting under the same
model considered by the authors
However, I am not
aware of papers which have studied multi-fidelity BAI. It is a very natural formalism with
useful applications.
While the paper falls short of solving this problem completely, I think the authors have
made meaningful advances.
Hence, I believe it would be a nice addition to the proceedings.
strengths_and_weaknesses: The lower bound given in the paper is quantifiably better than the lower bound for regular
BAI. However, I am not sure if it is tight enough. In particular, taking the minimum on
each term in the summation seems a bit too optimistic as it doesn't account for the
exploration cost at other fidelities. 

Related to the above: Assumption 1 seems to only consider problems where there is large
separation between fidelities (i.e. the costs increase sharply between a lower fidelity to
a higher while the gaps decrease sharply). This rules out many challenging problems where
the fidelities might be similar (i.e. similar costs/gaps); here, you might still expect a
smart enough policy to use that information or quickly ignore that information and move to
higher fidelities.

It might be useful to discuss the above issues to elucidate on the gap between the lower
and upper bounds. My hunch is that they will both need to be tightened outside of
Assumption 1.

Other comments:
Footnote 1 is very unclear, what does it mean for costs and fidelity to hold with
equality and what does it mean for it to be discarded. You need to be more clear and
precise about what is meant here.

questions: See above
limitations: See above
review_title: null

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: This work studies the multi-fidelity variant of the best-arm-identification problem. It first proposes a new performance measure called cost complexity, then gives a lower bound for the cost complexity of this problem. To solve this problem, this work offers an algorithm called Iterative Imprecise Successive Elimination (IISE), along with the cost complexity upper bound analysis. Then this work gives a better result when the algorithm has access to some more fine-grained knowledge of the multi-fidelity setting. Finally, empirical studies validate the effectiveness of the proposed method.
strengths_and_weaknesses: Strengths:
1. This work gives a solution to this novel problem along with the corresponding upper bound, which also closely mimics the behavior of the lower bound.
2. The overall paper is well-written and quite readable, especially some discussions about the intuition behind certain conclusions.

Weakness:
Not much.
questions: Typos:
1. Line 179: convenient provably convenient -> provably convenient
limitations: Not much.
review_title: null

final_score: rating: 3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
review_content: summary: The authors tackle establishing the best arm in a multi-arm bandit problem, where each arm can be pulled with a different “fidelity”.  Lower fidelity evaluations are cheaper to evaluate, but provide a more biased estimate of the objective function.  They present and analyse a new algorithm, IISE, that theoretically outperforms basic bandit algorithms that do no exploit the multi fidelity structure of the problem.  They then numerically confirm this on two experiments.  

strengths_and_weaknesses: ====== I posted this in a comment after my review, but it isn't visible to the authors for some reason.  Sorry for the confusion.

## Slight revision.

I have thought about this paper and my review a little more since initially writing it.  I figure I'd say this in the discussion phase anyway so I might as well put it here so the authors can respond in their rebuttal.  

My stance on the paper has relaxed a little bit.  While I still broadly stand by my concerns, I think if the authors can allay them, then I would endorse this paper.  

Specifically:
- I believe the paper could benefit from simplification of the exposition, maybe even cutting some material to the supplement.  I would consider adding an executive summary of the method, banner figure, algorithm/pseudo-code block*, flow chart etc.  Right now it is an impenetrable wall of math.
- The fixed subgaussian noise ($\sigma^2$) still troubles me.  I think this is my main technical reservation.  
- The empirical validation is very weak.  Right now the paper is hinging on the significance of the theoretical and methodological contribution, as it hasn't, in my opinion, been shown empirically _beyond doubt_ to be better than the alternatives.  

Thanks, LAgF

*I know you have an algorithm block in there, but it is still quite low-level.  I'd like to see a higher-level / word-based / pseudocode version of this.



========= Original Review:


I will preface my review with the statement that I am not an expert on bandits, or on multi fidelity methods.  That said, the paper is well written enough on a high level that I get the general point.

There is a huge amount of theoretical work that has gone into this paper, and for that, the authors are to be commended.  I think there is definitely an audience at NeurIPS that will get a lot from reading this paper and the accompanying materials (I only skimmed the results presented in the supplement).  

That said, I am not currently endorsing the publication of this paper, as I have some fairly substantial questions.  If the authors can allay my concerns and make some (again, fairly substantial) updates to the paper, then I would be willing to endorse it. 

I query some of the modelling choices made (1).  I also struggle with some elements of the presentation (2), and the empirical validation (3) .  I will try and break my criticism down a bit.

# Major Comments:

### 1.  Fixed subgaussian noise.
You assume a fixed variance for the subgaussian noise across all arms.  This seems like a pretty fundamental limitation to me.  I often think about mutlifidelity in terms of how many iterations / MC samples I allow my simulator/solver to take.  Therefore, lower fidelity simulators have a much higher variance on their evaluation than higher fidelity simulators.  Alternatively, lower-fidelity simulators may have lower variance because they are too simple to capture the full variability.  Finally, in the MDP example you give, longer windows have a higher variance, and therefore this doesn’t apply.  As the variable evaluation noise operating regime is not catered for in your work, it therefore excludes a large set of practical application domains where your theoretical guarantees don’t hold.  I invite the authors to comment on this.


### 2.  I really struggle with the presentation of the material.  
I understand that bandits and MF methods are individually quite notationally dense and difficult to get down on paper; and that a bandit + MF method is probably that difficulty squared.  However, the authors must do better (in my opinion) to strip out all the complexity and present the ideas as simply and as notationally clear as possible.  

- This paper may benefit greatly from a banner diagram to try and visually present the ideas, and at least unload some of the burden of explaining everything from the text.  

- For instance, the aside on MDPs and Prop 1 doesn’t seem to be used.  This should be cut from the main text and placed entirely in the supplement to clear space and reduce the amount of technical content.
  
- A table of notation in the supplement would be very helpful as well.
 
- Really try to keep subscripts, superscripts, diacritics to a minimum. 


### 3.  Weak empirical validation
There is obviously a sizeable theoretical contribution in this paper, however, the empirical validation is lacking in my opinion.  A toy synthetic problem and a single other problem tested against a single baseline doesn’t really convince me that your method works and is superior.  Obviously this isn’t required for publication, but, I do not consider this method to have been empirically validated.  To convince me of this, I would want to see a few more baselines evaluated on a range of more standard problems on which existing methods have been tested.  I have little-to-no idea if “X” is a good score on “synthetic toy problem 2”, whether synthetic toy problem 2 is a fair baseline on which to apply MFE etc.  I imagine there is a wealth of domains you can leverage to get a good example – image classification with different length glimpse sequences [Harvey, Teng, Wood, 2019], maybe train different stochastic classifiers with different sizes, number of latent samples, numbers of particles etc.  Maybe we just actually use the MDP / RL examples?  I really think this paper would be strengthened by using a domain that many readers will “understand.”  There is also a chronic shortage of implementation and experimental details in the main text and the supplement.  I do note however that code was released. 


# Minor Comments.
None, actually.


# Very Minor / Typographical Comments.
i. Theorem 3:  “upper bounder” -> “upper bounded.

ii.  Throughout:  (I.e. in Theorem 3)  Inconsistent use of “Equation \\eqref\{\}”, “\\eqref\{\}”, “Equation \\ref\{\}” and just “\\ref\{\}”.

iii.   Line 232:  “w.r.t” -> “w.r.t.”.

iv.  Line 243: “0” -> “zero”  (numbers less than 13 are typically written out).

v.  Try to avoid footnotes.  They are bad for readability.  If they are important then they should be integrated into the main text, otherwise, they should be removed. 

vi.  Line 454:  Matyas shouldn’t be “et al.”.  Also inconsistent use of just first initial.  


# Summary.
As outlined above, I think this paper has some serious limitations and weaknesses as it is currently presented.  I think there is a good conference paper in there somewhere, but I do not believe it is currently at that point.  There could even be a better, more impactful, and more widely distributed conference paper if published at a more specialised venue, if you are unfortunately rejected in this review cycle.  Good luck.  

questions: I raised several questions in my main review.

limitations: There are no ethical considerations.

I raised several comments on the limitations of the work above, including the limitations of the setting, the approach taken, the presentation and the empirical validation.
review_title: null

Meta-review: metareview: This paper considers the multi-fidelity variant of the best-arm identification problem. I recommend its acceptance and I strongly encourage the authors to take the several fantastic points raised by the reviewers while crafting their next draft. For instance, please include a discussion about (and clarification of) Assumption 1 that reflects the discussion with the reviewers.  
confidence: Certain
Decision: Accept