Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper studies the problem of functional estimation under the infinite-armed bandit setting (Berry et al., 1997). Specifically, the authors considered online and offline algorithms for estimating multiple functionals, such as mean, median, maximum, and trimmed mean. The main contribution is determining the sample complexity bounds for these estimation tasks.
strengths_and_weaknesses: One strength is that the sample complexity bounds are tight, up to logarithmic factors in the error parameters.

Another strength is that the authors have unified formulations and algorithms for both settings, showing that the online and offline sample complexities can differ for some functions. One can find more details in Table 1. 

A weakness, in my opinion, is that the paper does not provide much motivation for learning functionals (other than the mean) under the infinite-armed bandit setting. I found one sentence on page 1 saying that "in many scenarios, including single-cell RNA-sequencing (Zhang et al., 2020)", but it doesn't seem that a related experiment appeared in the paper. 

Another significant weakness is the writing, especially the clarity. I suggest the authors introduce the critical definitions and formulations before explaining the results. In the paper, the authors seem to assume that the readers are already familiar with the related literature. 

One more weakness is the novelty. The offline algorithm is an averaging algorithm with standard concentration attributes. And the online algorithm essentially refines the rough ordering of elements by constructing finer and finer confidence intervals on the promising ones. I don't think these ideas are novel, or maybe they are relatively standard. 
questions: Please refer to the strengths and weaknesses section for suggestions or points to address.

A question here is whether the authors think some of these ideas apply to the classical bandit settings, and why.
limitations: I think the settings and results are reasonable. But I didn't find a specific section or paragraph discussing the limitations of the current work or future directions. The authors may consider adding such a section since there's still space.
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: The paper considered distribution functional estimation problems in the infinite armed bandit problem.
First, the authors formulated the distribution functional estimation problems (especially mean, median, maximum, trimmed mean estimations). 
The authors presented meta-algorithms for such distribution functional estimation problems for both online and offline settings together with the sample complexity guarantees.
Next, lower bounds on the sample complexities for both offline and online settings are shown. 
For the lower bound for the median estimation problem, the authors remarked on "thresholding phenomena" in order to prove tighter lower bounds. 

strengths_and_weaknesses: - Strengths

A relatively thorough upper/lower bound characterization of the distribution functional estimation problem has been made. (for both offline and online settings)


- Weaknesses

The online algorithm is based on the doubling trick so it may be unpractical. (although theoretically sound)
No numerical experiments have been made.
Positioning of the work (see Limitations section).


questions: Please see the Limitations section. 
limitations: 
My main concern is that the research associated with this paper is not well surveyed.
As the main objective is different from the papers cited in the related work, I don't think the paper deals with the problems that could only be cast as bandit problems. 
The problem considered in this paper (estimating the distribution functional estimation in online/offline setting) and the problem considered in the related work (minimizing regret or 
simple regret) have a largely different nature. 

It looks like there are many papers in statistics that deals with the problem of estimating the statistical functionals. for example,

Wasserman, Larry. All of statistics: a concise course in statistical inference. Vol. 26. New York: Springer, 2004.

Hall, Peter, and Soumendra N. Lahiri. "Estimation of distributions, moments and quantiles in deconvolution problems." The Annals of Statistics 36.5 (2008): 2110-2134.

(Note these areas are not my expertise.)

While there may be a novelty, I believe that appropriate comparisons with papers dealing with similar issues need to be made.
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: The paper studies distribution functional estimation (estimating mean, median, maximum, trimmed mean) in the infinite-armed bandit problem. 

For the offline setting, the authors design the appropriate number of points $n$ and the number of samples per point $m$ to minimize the sample complexity $m*n$. 

For the online setting, they propose an elimination-based algorithm that can adaptively screen out those redundant points, which are not related to the functional estimation. Thus, the online algorithm can reduce the sample complexity (in expectation). However, the online algorithm shares the same worst-case sample complexity as the offline algorithm.

They also provide matching lower bounds for the sample complexity under online/offline settings. For the mean and maximum estimation, the proof uses Wasserstein distances to upper bound the KL divergence.  For the median estimation, the Wasserstein distance-based method is too loose, so they propose a proof and show a ``thresholding phenomenon’’, KL divergence does not change smoothly with the noise level, which may be of independent interest.

strengths_and_weaknesses: Originality: It’s a novel work. The paper focuses on the sample complexity and reveals the differences between various functions and offline/online settings. My only concern is that the work seems to be more related to statistics, but the paper doesn't review papers in that area. I think a discussion of the connection to papers in statistics can help the position of the paper a lot.

Quality: It’s technically sound.

Clarity: The paper is written clearly and well organized.

Significance: The paper considers the sample complexity for different functionals and online/offline settings. It provides matching upper bound and lower bound for every scenario. The result (which is summarized in Table 1) is novel, complete, and solid. 

The paper shows interesting insights which can shed some light to future work. First, the work reveals the difficulty for various functions. For example, estimating the median is harder than the mean, but not harder than the trimmed mean. Second, the work reveals the difference between offline and online settings. For mean estimation, the online setting has no advantage. But online algorithm has improved over offline for other functionals.

questions: Note that the sample complexity depends on the target accuracy $\epsilon$ also the confidence level $\delta$. Why not consider the dependence on $\delta$ in Table 1? Is that because all the terms have the same growth rate $O(log(1/\delta))$?

Since the objective in this paper is no longer minimizing regret or identifying the best arm as in the classical MAB setting, could the author further list the related work in median/quantile estimation? For example, the result for mean estimation is a simple extension of concentration/Chebyshev inequality. For the online setting, there’s no need to discard points, since every point should contribute to the mean. 
limitations: NA
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: The authors study the infinite-armed bandit problem. Prior work focused on best arm identification in this setting; the authors instead consider estimating a functional of the underlying distribution F. They examine indicator-based functionals such as the mean, median, maximum, and trimmed mean. They study both the offline and online settings. They give a meta-algorithm for arbitrary indicator-based functionals with a general sample complexity and also provide lower bound results for each setting. 
strengths_and_weaknesses: Strengths:

It is nice that they have a unifying algorithm and sample complexity result for all settings. 

They provide lower bounds for all of the settings.

The problem formulation is mathematically elegant and it is interesting to consider indicator-based functionals.

Weaknesses:

The motivation for estimating a general functional seems weak to me. The authors mention single-cell RNA sequencing, but do not explain to the reader in detail how estimating the median or trimmed mean arise in these practical settings. I think it is particularly important to motivate estimating the median and trimmed mean because these seems like the most novel settings of this paper. In what real-world problems would we apply these algorithms? I also think the offline setting should be motivated here.

I also think the paper would benefit from experimentally validating the results. How much of a gap is there between the online and offline algorithms in practice? 

The algorithmic novelty is limited. While it is nice that the algorithm unify all settings, it uses standard ideas from the literature, applied to the indicator-based functional. It basically adaptively identifies which drawn arms belong to the set defined by the indicator-based functional using confidence bounds and order statistics. 

It would be nice to give some concrete examples where Theorem 2 gives a much better sample complexity than is possible in the online setting. 

I think that there could be a clearer presentation relating the upper bounds and the lower bounds. The authors argue that the bounds are tight, but for the online setting upper bounds contain a distance^2 term that does not appear in the lower bounds. So, it is difficult to evaluate the gap. 

The algorithm seems to require knowing the quantities from the assumptions in section 3.1. These do not seem like they would typically be known in practice. It would be useful and important to give guidance to practitioners on how to set these quantities in practice. 

questions: Could the authors comment on the optimality of the algorithms in all of the settings in more detail? 

Could the authors elaborate on the motivation more? As of now, the applications are unclear to me.

Post rebuttal: the authors have addressed my questions on optimality, theoretical comparison between the offline and online settings, and the motivation. 
limitations: Yes.
review_title: null

Meta-review: metareview: This paper studies offline and online statistical estimation in the infinite-armed bandit setting and gives a set of almost tight upper and lower bounds on the sample complexity.  Initially, some reviewers raised concerns about the motivation of general functional estimation and the comparison with existing statistical estimation literature. The authors have made efforts on addressing these issues; their arguments seem reasonable.
confidence: Less certain
Decision: Accept