Beyond the Best:  Distribution Functional Estimation in Infinite-Armed Bandits
Authors: Yifei Wang
Tavor Baharav
Yanjun Han
Jiantao Jiao
David Tse
Venue: NeurIPS 2022 Accept (2022)
Keywords: Multi-armed bandits
information-theoretic lower bounds
algorithm design
functional estimation

Abstract: In the infinite-armed bandit problem, each arm's average reward is sampled from an unknown distribution, and each arm can be sampled further to obtain noisy estimates of the average reward of that arm. Prior work focuses on the best arm, i.e. estimating the maximum of the average reward distribution. We consider a general class of distribution functionals beyond the maximum and obtain optimal sample complexities in both offline and online settings. We show that online estimation, where the learner can sequentially choose whether to sample a new or existing arm, offers no advantage over the offline setting for estimating the mean functional, but significantly reduces the sample complexity for other functionals such as the median, maximum, and trimmed mean. We propose unified meta algorithms for the online and offline settings and derive matching lower bounds using different Wasserstein distances. For the special case of median estimation, we identify a curious thresholding phenomenon on the indistinguishability between Gaussian convolutions with respect to the noise level, which may be of independent interest.

Beyond the Best: Estimating Distribution Functionals in Infinite-Armed Bandits
Yifei Wang
Tavor Baharav Department of Electrical Engineering Stanford University Stanford, CA 94305 tavorb@stanford.c
Department of Electrical Engineering Stanford University Stanford, CA 94305 wangyf18@stanf
Yanjun Han
Institute for Data, Systems, and Society Massachusetts Institute of Technology
Cambridge, MA 02142 yj yjhan@itt... edu
Jiantao Jiao
Department of Electrical Engineering and Computer Sciences and Department of Statistics University of California, Berkeley
Berkeley, CA 94720 j jiantaoBeecs berkeley. edu
David Tse Department Electrical Engineering Stanford University Stanford, CA 94305 dntse@atanford edu
Abstract
In the infinite-armen bandit problem, each arm's average reward is sampled from an unknown distribution, and each arm can be sampled further to obtain noisy estimates of the average reward of that arm. Prior work focuses on identifying the best arm, i.e., estimating the maximum of the average reward distribution. We consider a general class of distribution functionals beyond the maximum, and propose unified meta algorithms for both the offline and online settings, achieving optimal sample complexities. We show that online estimation, where the learner can scquentially choose whether to sample a new or existing arm, offers no advan- tage over the offline setting for estimating the mean functional, but significantly reduces the sample complexity for other functionals such as the median, maxi- mum, and trimmed mean. The matching lower bounds utilize several different Wasserstein distances. For the special case of median estimation, we identify a curious thresholding phenomenon the indistinguishability between Gaussian convolutions with respect to the noise level, which may be independent interest.
1 Introduction
In the infinite- armed bandit problem (Berry et al. 1997), at each time instance the learner can either sample an arm that has been previously observed, or sample from a new arm, whose average reward
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

is drawn from an unknown distribution F. The learner's goal is to identify arms with large average reward, with the objective being achieving either small cumulative regret (Berry et al. 1997 Wang et al. 2008 [oonldd and Proutiere 2013), or small simple regret (Carpentier and Valko 2015). This setting differs from the classical multi-armed bandit formulation as the number of observed arms is not fixed priori and needs to be carefully chosen by the algorithm.
We consider the problem of estimating some functional g(F)) of an underlying distribution F', as is illusrated in Figure | From this point of view, the classical infinite-armed bandit problem can Once we cast the infinite- armed bandit problem in this manner, it immediately suggests several additional questions. For example, what about offline sampling algorithms? Indeed, online sampling requires continual interactions with the environment which may be infeasible in certain applications, and recent work in online and offline reinforcement learning have demonstrated the significant value of both formulations (Rashidinejad et al. [021] /Zhan et al. [021 [Schrittwieser et al. [021]. Additionally, it worth estimating functionals beyond the maximum:
be viewed as an online sampling algorithm to estimate the maximum of the distribution F. F
many practical scenarios, including mean estimation in single-cell RNA-sequencing (Zhang et al. (020) and Benjamini Hochberg (BH) threshold estimation in multiple hypothesis testing (Zhang et al. 2019). we are interested in the mean, median (quantile), or trimmed mean of the underlying distribution F. The estimation of quantiles is similar to estimation of the BH threshold, as both depend on the order statistics of the underlying distribution. Estimating the median trimmed mean has further applications in robust statistic for instance, maintaining the fidelity of an estimator in the presence of adversarial corruption or outliers. Another natural setting where such problems arise is in large-scale distributed learning (Son and Simon 2012). Here, a server platform wants to estimate how much test-users like their newly released product. Users return noisy realization of their affinity for the product, and the platform can decide to pay the user further to spend more time with the product, to test it further. For many natural objectives which are robust to a small fraction of adversarial users, e.g. trimmed mean, median, or quantile estimation, we see that our algorithm will enable estimation of the desired quantity to high accuracy while minimizing the total cost (number of samples taken). Since sampling expensive, is critical to identify the optimal method to collect samples, and identify the improvements afforded by adaptivity. For example, do online methods offer significant gains over offline methods? Are the fundamental limits of estimating the median and trimmed mean different from that of the maximum?
F
aubaampla
X1
X
n
noi
Y1,1
Y1.m
m1
Ynm
Figure 1: Problem setting. Level O: underlying distribution F(z). Level 1: unobserved samples N,, ~ F(x). Level 2: noisy observations Yi, ~ N(,,,
In this paper we initiate the study of distribution functional estimation in both online and offline settings and obtain both information theoretic limits and efficient algorithms for estimating the mean, median, trimmed mean, and maximum. We propose unified meta algorithms for both offline and online settings, and provide matching upper and lower boundsfor the sample complexity of estimating the aforementioned functionals in [
We also reveal new insights on the fundamental differences between the offline and online algorithms, as well as the fundamental differences between different functionals. To determine these sharp statistical limits, setting, while the Wasserstein--s co distance is applied in the online setting instead. This approach leads to valid sample complexity lower bounds for general functionals g. which turn out be tight for estimating the mean and maximum. However, a curious thresholding phenomenon, which is not
use the Wasserstein-2 distance to upper bound the KL divergence in the offline
'To be precise, the objectives in infinite- armed bandit works (Berry et al. 1997 Wang et al. 2008 Bonald
and Proutiere 2013 Carpentier and Valko 2015) are slightly different, minimizing simple cumulative regret.

---

captured by the previous approach and does not occur for the mean and maximum, appears in the median and trimmed mean analyses: the KL divergence does not change smoothly with the noise level and enjoys a phase transition after the noise level exceeds some threshold. This phenomenon calls for different treatments under different estimation targets and could be of independent interest.
Offline complexity
Online complexity
Functional
Comments
Mean
(
O(c-²)
No gain from online sampling
Median
9)
2.5)
Holds for any quantile not on the boundary
Maximum
((+-
Depends on the tail regularity
Trimmed mean
g(F) E X E (((a),FF((1) a)l}
Table 1: Sample complexity of estimating different functionals g(F), where F is the cumulative distribution function (CDF) of the distribution to estimate. The trimmed mean result holds for a fixed a E 10,). Here ε is the target accuracy and we use Ô denote the matching upper and lower bounds up to constants not depending on e. Additionally, we use θ, R and S to suppress constants and logarithmic factors in e, and e for any fixed c arbitrarily close to zero. If h(s) S (() and f(e) & he) then we denote this as (ee x I(e)). For maximum estimation, we assume that the distribution satisfies IP (XX= F (1) - =) x 2 Other assumptions on F are detailed in Section 3
The rest of this paper is structured as follows. In Section I.1 we discuss the relevant literature. We then formulate our distribution functional estimation problem in Section 2 Our unified meta algorithms for the offline and online settings are presented in Section 3 where we show the sample complexity upper bounds. We present information theoretic lower bounds proof's via Wasserstein distance for the online and offline settings in Section 4 and discuss special thresholding phenomenon arising in median estimation in Section 5 Section concludes this work.
1.1 Related works
The field of multi-armed bandits has seen broad interest and utility since its formalization in 1985 (Lai ct al. 1985). Across clinical trials, multi-agent learning, online recommendation systems, and beyond (Lattimore and Szepesvári 2020), multi-armed bandits have proven be an excellent framework for modeling and solving complex tasks regarding exploration in an unknown environment. In the classical multi-armed bandit setting we have a set of distributions, where the player sequentially pulls one arm per round and observes a sample drawn from the associated reward distribution. In the infinite-armed bandit setting (Berry et al. 1997), the average arm reward for each arm is sampled i..d. from an unknown distribution, i.e., we have infinitely many available arms. There are many possible objectives that can be formulated in this online learning problem. from cumulative/simpll regret minimization (Wang et al.) 2008: [ooaad and Proutiere 2013; Carpentier and Valko 2015)
Li and Xial 2017) to identification tasks (for example identifying an arm whose average reward is 8 close to the largest average reward) (Aziz et al. 2018 Chaudhuri and Kalyanakrishnan 2017
2019). Many works have studied best-arm identification, and we now have essentially matching instance-dependent upper and lower bounds (Jamieson and Nowak [014] Kaufmann et al., 2016).
One could also use the average reward estimate of the identified best arm to estimate the maximum of the average reward distribution in the infinite-armed bandit setting (Carpentier and Valko 2015
Aziz et al. 2018. Chaudhuri and Kalyanakrishnan 2017 2019).
From a statistical perspective, the sample complexity in the offline setting is closely related to deconvolution distribution estimation (Cordy and Thomas [997| Wasserman, [0044] Hall and Lahiri 2008; Delaigle et al. 2008; Dattner et al. 2011). Nevertheless, these previous works mainly focus on the expected L2 difference between the underlying distribution function and its estimation. This simplified setting does not allow for consideration of the trade-off inherent in our setting between the number of points and the (variable) number of observations per point, Additionally, these past works did not calculate the specific sample complexity for more general functionals like quantile and trimmed mean. Since the noise is treated as fixed and uniform, there has been no study of the online setting where adaptive resampling can enable dramatic sample complexity improvements. In particular, the challenge that we have noisy observations, which makes deriving lower bounds even in offline cases significant challenge that has not been dealt with in the past, let alone analyzing
3

---

the online case. The dramatic performance gains afforded by adaptive resampling for functional estimation, combined with its lack of formal study, motivates the focus of this work.
Problem formulation
We interested in estimating the distribution functional g lK of an underlying distribution with cumulative distribution function (CDF) F. We study a class of indicator- based functionals defined as follows.
Definition (Indicator-basee functionals).
The functional g can be represented as
g( F) =E [X| E S(F))
for some set S(F), where ~ F. The set S(F) is defined as follows:
S(F) (F F (a2)), o S sn 1.
We denote S(F) by S throughout this work when F is clear from context. This class encompasses many natural functionals of interest, which we formulate in Table In Appendix ??, we discuss extending our results more general functionals, and show that our approach can extend to smooth reweighting functions h(X) and more complex sets S.
Functional
g(F)
02
Comment
Mean
E[
1
Quantile
F (a)
a (0, 1), e.g. a 1/2 for median
Maximum
F (1)(1)
1 a1 012 0 for minimum
Trimmed mean
E (X) E (on, 02)
a E (0, 1/2)
Table 2: Indicator-based functionals.
As in the infinite-armen bandit setting, only have access to noisy observations of samples drawn from the distribution with CDF F. We can either choose to sample from point X which we already have some noisy observations of, draw where Z ~ (0, 1) is independent of everything observed so far.
point X from F. We then observe Y = = Z,
In this paper characterize the online and offline sample complexities of these problems, and in Section propose online and offline algorithms achieving them. For > and å E (0, 1), we call an estimator an (e, PP- approximation of gFF) if P( G -gggg( g(F) > E) S 6.
Offline and online algorithms
3.1 Offfine estimation algorithms
We study a special class of offline algorithms, which uniformly obtain observations of the points following the underlying distribution. To be precise, based prior information regarding the distribution in question, F, it will choose an appropriate number of points n and number of samples per point
obtain an (e, 8)-PAC approximation of g(F). Specifically, the latent variables XI,..., Xn, are drawn from F, and our observations {Yi, k are drawn i.i.d. from WX,,, 1), independently for each For i E [n], denote X; m Σ/ Yi, as the empirical mean of the observations for arm i. Then, across Define S, A {i X((aan]) S X; ([ as the of arms relevant for estimating the functional g. and define our n sample estimate of g as gn. (& 8n)
write X;
X; Z, where 2, NN(0,) 1/m), independent
1- X;. Here X()) denotes the i-th order statistic, that is the i-th smallest entry in XI....,XX Then, Gn.m = for ((F) from the noisy observations. With this, we can state the following theorem:
Xx), where each X, has been sampled m times, serves as a natural estimator
Theorem (Offline PAC sample complexity). An (s, P)A offiine
sai---smmppppuuue algo- rithm for estimating g( requires (mm) samples where n. m depend on E, 8, the functional g, and information about F, with orderwise dependence detailed in Table 3

---

For the rest of this section, we discuss in greater detail our assumptions on the underlying distribution. We defer the proofs and calculations for and m ??, as well discussion regarding the trimmed mean to ??.
Functional
Mean
((1)
(
Median
(
(
Maximum
(E)=))
Trimmed mean
+ (E log (s (s-))
O 3)
Table 3: Choice of (m, n) for estimating different functionals accuracy
3.1.1 Mean
To guarantee that the empirical mean is good estimator for the true mean, we impose assumptions on the tail of the distribution F:
Assumption 1. The distribution F satisfies Varx~ S
Assumption 1 ensures that estimation of the mean of the distribution can be accomplished with finite samples. The following proposition gives the sample complexity of the offline algorithm. Proposition 1. Suppose that Assumption is satisfied. By choosing the estimator Gnmm is an (SAC approximation of g(F). Thus, the offline algorithm requires O 2) samples.
1 and 81+ c)e c)
3.1.2 Median
For median estimation we require different assumptions than the mean, as listed below. Assumption 2. There exist constants C1, such that
('(x) 2 e for lxr median (F)
(F) for median (F) & VE.
The first assumption ensures that the median of F is unique. The second assumption precludes the distribution from being dumbbell-shape (very little mass near the median), in which case estimating the true median is meaningless and can be arbitrarily difficult. The following proposition gives suitable choice of (n, m) for providing an (c, PPC approximation of g(F).
Proposition 2. Suppose that Assumption holds. Then, by choosing m 2 4(cz + ()/(ce)) and 2 28 log(1/5)/ (c1)) the estimator Gn,m is an 8)AC approximation of g(F). Thus, the offline algorithm requires Olg-)) samples.
3.1.3 Maximum
For maximum estimation, we require an assumption on the tail of common in the infinite-armed bandit literature.
Assumption 3. There exist constants c1 C2 and 3 0 such that
F(F E [cit 1. for all < S
This ussumption is also known as the 8-regularity of F around F F-1(1), see (Wag et al. 2008). We present suitable choice of (n, m) in the following proposition.
Proposition 3. Suppose that Assumption 3 holds. By choosing 2 1288 log(2/0) and > 4s Log(2n/)) the estimator Gr. is an [E, 8)-PAC approximation of (FF). Therefore, the offline algorithm requires 002-8-2) samples.
3.2 Online estimation algorithm
We now present our general algorithm (Algorithm 1. an elimination-basee (c, 8)- algorithm that efficiently estimates g F), where g a known input functional and F an unknown distribution from which we are able to sample X, independently, and observe noisy observations Y., of X,,

---

Algorithm Meta Algorithm
Input: target accuracy E, error probability ö, functional 9 parameterized by (01, (:))
2: Compute (n, m) for 6/2)-PAC estimation of g( F)) based on Theorem
3: Construct active A [n]. and define by and to
4: for r -or=111 1,2 do
5: Define 4, = 2- and 4 min(m, [81=2 log(1 (1 6n log(m))6)1)
6: Pull each arm in A, for 1, 4-11 times, construct j((r)
7: Compute A,+1 = {i: (p:(r) PC. (n))))(() & b, or (ix(r) (((aza)) s br}
8: t, m then
9:
Break, exit For loop
end if
11: end for
12: Construct Sn ( ((la)a)a))))))) S (c(r)= S ((ann))
13: af 02 then
return [S,,] Eies, (r((r)
15: else
16: Draw one observation from each E Sn, construct j
17: return 185ml Dies, f4
18: end if
In order to exploit the Bayesian nature of the problem, analyze the algorithm in two parts. First, we use the fact that our arms are drawn from a common distribution to find some n, m as in Theorem [ such that the plug-in estimator Gn.,n will be an (e/2, 6/2)-PAC approximation of g()). Second, we show that our adaptive algorithm is an (e/2, 6 22)--PAC approximation of Gn,m. but is able to accomplish this using significantly fewer than
samples.
Notationally, we denote by ji(r) the estimated mean vector all arms at round r, and denote the i-th entry of this vector by (r(r). We have that with high probability each arm's mean estimate stays within its width b, = 2- confidence interval for each round r. analyze our algorithm, we denote p!ni ..... puii as the estimates of X1..... ........ Xn generated by the offline algorithm after sampling each arm m times. Then, we see that for the offline algorithm the arms relevant for the estimation task and the corresponding sample estimator
S, = uni ([oin]) S 14th S uni (((ozn)) Gn,m
Σ uni
(3)
S.
FES.
Here Sn indicates the arms that the offline algorithm believes are in S. We show that our online algorithm is able to efficiently estimate the set S, as Sn, determining whether not arms are in Sn. sampling these arms in S, sufficienlly, and returning a plug-in estimator. By construction each arm is only pulled by the adaptive algorithm at most times, as know from the analysis of the offline algorithm that for the utilized nt, m, if each arm is pulled m times then the output is an (e/2, 2 estimate of 9F)). Thus, the online algorithm's 's objective is essentially emulating the output of the offline algorithm, for which it only needs to sample any arm at most m times.
Note that when On # 02, we have many samples X; that are within S, with J.S. 2 [n(a2 a1)]- In order avoid issues of dependence, we discard all previous samples (as arms in S, will have been construct
sampled different numbers of times), and that since we have (n)) arms in 8, sufficiently accurate estimate by sampling each arm in S,, once, Algorithmically, we denote this as obtaining one fresh observation and constructing fi..
To upper bound the sample complexity of algorithm,
that each arm only needs to be sampled to determine whether is S,, or not. As we show in ??, the number of samples (i) needed for point X; satisfies
256 log
16n log
N(1) S min
m, [ddit(X X,, K,,& 2 Conv : Sw)))
(4)
with probability least 1 - 5/4 4 for all arms simultaneously. where A denotes the boundary of set A, CAn denotes the convex hull of a set A. and dist(XX AA) min X al. In the limit

---

uni as + 0 we show that ([(an])) + F=1( (similarly with ([ )). This allows us to state the following theorem regarding the expected sample complexity of Algorithm I with respect to the
distribution's relevant set of values S rather than the estimated indices Sp.
Theorem (Meta algorithm). For functional g satisfying Definition 7 Algorithm provides an (e, -PAC estimate of g with M samples when given the requisite inputs. Here m and n are and the number of samples M required satisfies
calculated as Theorem 7
log(n/o) min m,
(oss(X,,))² )I)
EIM = n1E
(5)
The proof of this Theorem is deferred to ??.
Evaluating this expression for different functionals under their corresponding assumptions yields the stated sample complexity upper bounds, as we show in ??.
4 Lower bounds via Wasserstein distance
In this section we derive general lower bounds on the sample complexity of functional estimation for both offline and online algorithms, where two different Wasserstein distances play important roles. These Wasserstein-basee lower bounds yield tight results for mean and maximum estimation.
4.1 General lower bounds based on Wasserstein distance
A classical technique for proving minimax lower bounds is Le Cam's 's two-point method (Le Cam al. (2000): let F1 and Fz2 be two distributions with (F(Fi - g F2)] 2 2c, and let Pr,F; and P=, be the probability distributions of all observations queried by policy и under the true population distributions Fi and F2, respectively. One version of Le Cam's two-point lower bound (Tsybakov
2009 Theorem 2.2) gives
inf sup Fst
PF(00 g(F) 2))
exp exp (- (lpx.F:))
Consequently, to construct lower bound on the PAC sample complexity of estimating g(F), it suffices to find the largest e such that there exist Fi, P3 with (g(Fi) gg(E2) 2 2s while DKL (Pr.Fi [IPx.r)) 0(1).
key step in the above analysis to upper bound the KL divergence (KL F. (IP,,F.): which differs significantly between offline and online algorithms. For offline algorithms, the learner samples n arms i.i.d. from F with average rewards X1, ... X,, ~ F, and each arm is pulled m times with Gaussian observations. Consequently, Px,F = (F (0, 1/m)) Sn, where n denotes the n-fold product distribution and denotes the convolution operation. The following lemma presents an upper bound on the KL. divergence for offline algorithms.
Lemma 1. For any offline algorithm defined in Section
3.1 it holds that
DEL D.
7nn
W F1, F2),
2
where W2(P, Q) is the Wasserstein-2 distance defined as W (P, P,PO Q) -inf Exxy)~ (x--)-(XX-)))))) 1ox-Yy Y) with r being the class of all couplings between P and Q
For online algorithms the distribution Pr, is no longer a product distribution as actions can depend on past observations. As result, the KI. divergence becomes larger, but still enjoys an upper bound based on another Wasserstein distance.
Lemma 2. For any online algorithm n which queries T samples, holds that
T
(KL(P (l) < W (F1. F2),
2
where Wo (P.Q) is the Wasserstein-co distance: W (P, Q) inf (sssup(x,r)_//x YI.
with I being the class of all couplings between P and Q.
7

---

As Q) S (P.Q). the upper bound of Lemma 2 is no smaller than that of Lemma showing the stronger power of online algorithms. The following corollary is then immediate from Lemmas and
|
Corollary 2.1. The sample complexity of (s,, -1P- estimation of g (F) is
m/l (F, F2): F1, F2 (o(g - (22)) 2 2+})
for offline algorithms, and is
2211 ( (Fi, F2): Fi, E FF g(F2) 2 2+
for online algorithms.
In the remainder of this section, we show that Corollary 2.1 leads to tight lower bounds for mean and maximum estimations for both offline and online settings.
4.2 Lower bounds for mean estimation
Consider two distributions Fi and F2 which are Dirac masses supported on 1/2 - E and 1/2 + E. respectively. Clearly W2 (Fi, F2) = Woo F2) 2s, which is the best possible W2(F1, F2) 2
|mean(F) - meann [2) 2 2e. Corollary 2.1 gives the following lower bounds.
Corollary 2.2. The (1..1) sample complexity for mean estimation is 2) for both offline and online algorithms..
4.3 Lower bounds for maximum estimation
For maximum estimation, the Wasserstein distances W2 and Wo behave differently, as summarized in the following lemma. Let F3 be the class of densities satisfying Assumption 3
Lemma 3. For e E (0, 1/2), holds that
(Wn (W2 (Fi, Fb): Fi, e Fo, (max(F) max(F22 2 (
min oo (F1, F2): F1, E FB, mmax max(F2)) 2 2E} O(e):
min (Fi (F) F1, e FB, |max(F) max(F2))
2 2c} O(5").
Note that we have included another term (FL(Fi in Lemma
3 as it can provide better lower
bound than using Wo if 3 > 2, as (Pr.F. (lPr,F,) S T D [Fill F2) always holds due to the data-processsin inequality (i.e. assuming that all arm rewards are independent). Consequently, we have the following corollary on the sample complexity of maximum estimation.
Corollary 2.3. The (e, .1) -AC sample complexity for maximun estimation over Fg is Q(E ((== (f+2))
for offline algorithms, and Q(e= max(3.2) for online algorithms.
5 Lower bounds via thresholding phenomenon
Although the Wasserstein distance-based approach in Section 4 provides general lower bounds for both offline and online algorithms, and these lower bounds are tight for mean and maximum estimation, sometimes this approach can be loose. For example, Lemma ssows that using the Wo distance might be looser than using the original KL divergence for maximum estimation. This section provides tight lower bounds for median estimation, revealing curious thresholding phenomenon.
shows
5.1 Thresholding phenomenon for offline algorithms
Let F denote the set of distributions satisfying Assumption 2 To use Le Cam's two-point method to prove lower bounds for offline algorithms for median estimation, the key quantity is:
KLo(e) A min (F1 * N0 o F NN(0, F1, FF
(1/2)) > 2z).
Its inverse KT,- is referred to as the modulus of smoothness of the median with respect to the KI. divergence under Gaussian convolution. The Wasserstein-basee approach to upper bound KL,
(E)

---

is the following: let (2) be the counterpart of the above quantity with the KL divergence replaced by the Wasserstein-2 distance, Lemma shows that
in Lemma [
(2) = + 202
2.5
KL (E) -
(6)
o2
an upper bound decreasing continuously with o, where the proof of the last identity is presented in the Appendix. However, this upper bound is not tight, as shown in the following lemma.
Lemma 4, For e E (0, (
(5) can be characterized as follows:
{E {
ifa S cE112
KT, (c)
C(0,
2
where 0 (0, 10,1/4), N are arbitrary fixed parameters, and e, C1, C(O,K) are absolute constants with the last one depending only on (0,k).
Lemma shoows a thresholding phenomenon as follows: when a increases from 0 to 1, the quantity (e) stabilizes at ((=2) whenever S e1/2; however, when exceeds this threshold slightly (i.e. Z e1/2-0 for any constant 0 0), this quantity immediately drops to o(=") for every possible K. The main intuition behind this thresholding phenomenon that, a = (g2/22, the "bandwidth" of F1 F32 exceeds that of (000 o²), and the convolution is effectively using N o0) as a Gaussian kernel (which preserves polynomials up to order for smoothing F1 F2 (which second-order differentiable). In contrast, when a >> el/2, the "bandwidth" of be smaller than N(0,o²), and the convolution is effectively using F1 F2 as a kernel (which could preserve polynomials up to any desired order) for smoothing (0, 1) (which infinitely differentiable). Approximation theory tells us that the latter approximation error could be much smaller than the former, leading to the thresholding phenomenon. We remark that this phenomenon is not captured by using the W2 distance.
F2 could
This thresholding behavior has an important consequence for median estimation. By Lemma 4 with = 1/Vm, PAC learning requires that m = 90 for any offline algorithm, as otherwise the KL divergence could be made arbitrarily small. When is large enough, the first line of Lemma then requires = 22==-) 2) to result in large KL. divergence for PAC learning, which comes from the idendity that
(P""IIQ = nPll(PI)))
Consequently, we have the following corollary for median estimation using offline algorithms.
Corollary 2.4. Fix any 0 > O. The (E,-1)-PAC sample complexity for median estimation is ((x-3++ -3+) for any offline algorithm.
5.2 Thresholding phenomenon for online algorithms
To prove the PAC lower bound for online algorithms, one first wonders the same observation in Lemma 4 could still work. However, close inspection of the proof reveals issue: the optimizers 0(2 and a = ((= An online learning algorithm could first identify the right scenario and then choose proper sample size to tackle the problem, and thus the above lower bound arguments break down.
(F1, F2) in the definition of (E) are different under the regimes
To resolve this issue, aim to choose proper pair of distributions (Fi, F2) with [median (Fi)
median [2] 2 2e, and investigate the behavior of (Ki (O oz) * (0)) as function of a with FF), fixed along the line. The following lemma shows that, even for some fixed pair (Fi, F2), a similar thresholding phenomenon still holds for the KL divergence.
Lemma 5. Fix any 0 E (0, 1/4), and K E N. There exist two distributions F1, E F with Imedian (i) modian( Fz)l 2 28, and
C/2 (E 1/2 (C C(0, k)e"
if S c/
(RI * NN(0, * (((0,")))
i 2 1/2-0
where c, C1, C2,, C(O, k) are absolute constants with the last depending only (0, R).

---

Compared with Lemma Lemma 5 still shows similar thresholding phenomenon for the KL divergence when a >> e 1/22 but the KL divergence becomes larger for small a due to the additional constraint that (41, is held fixed. Under the choice of (Fi, F22) in Lemma S each arm should be pulled least ((s20-1) times, while (/s0-//2) arms need to be pulled in view of the first line. The following theorem makes the above intuition formal.
Theorem 3. The -I-PAC sample complexity for median estimation is ((g-5/2+6) ( for any fixed > 0 and any online algorithm.
The formal proof of Theorem 3 is more complicated and requires explicit computation of the KL divergence DKL (px, (P.,F; Ilpx,,,), .. We relegate the full proof to ??. This thresholding phenomenon of the noise level also applies to the case of trimmed mean, which is discussed further and analogous result proved in Appendix ??.
Conclusion
In this work we formulated and studied offline and online algorithms for estimating functionals of distributions. We developed unified algorithms for estimating the mean, median, maximum, and trimmed mean, providing sample complexity upper bounds. We additionally proved information theoretic lower bounds in these settings, which show that our algorithms are optimal up to e where e is a fixed constant arbitrarily close to zero. We used different Wasserstein distances to construct information theoretic lower bounds for mean and maximum estimation, and showed how fundamentally different techniques are required for median and trimmed mean estimation. The lower bounds for median and trimmed mean estimation elucidate an interesting thresholding phenomenon of the noise level to distinguish two distributions after Gaussian convolution, which may be of independent interest. Interesting directions of future work include extending our analysis to non- silcatto-bbsed functionals, such as the BH threshold and analyzing the limiting behavior as + co.
Acknowledgements
Yifei Wang and David Tse were partially supported by NSF Grants CCF-1909499 Tavor Z. Baharav was supported in part by the NSF GRFP and the Alcatel-Lucent Stanford Graduate Fellowship. Yanjun Han is supported by a Simons-Berkeley research fellowship and Norbert Wiener postdoctoral fellowship. Jiantao Jiao was partially supported by NSF Grants 190-19,, and CCF-1909499.
References
Aziz, M., Anderton, J., Kaufmann, E., and Aslam, J. (2018). Pure exploration in infinitely-armed bandit models with fixed-confidence. In Algorithmic Learning Theory, pages 3-24. PMLR.
Berry, D. A., Chen, R. W., Zame, A., Heath, D. C., and Shepp. (1997). Bandit problems with infinitely many arms. The Annals of Statistics, 25(5):2103-2116.
Bonald, T. and Proutiere, A. (2013). Two-target algorithms for infinite-armed bandits with bernoulli rewards. Advances in Neural Information Processing Systems, 26.
Carpentier, A. and Valko, M. (2015). Simple regret for infinitely many armed bandits. In International Conference on Machine Learning, pages 1133-1141, PMLR.
Chaudhuri, A. R. and Kalyanakrishnan, S. (2017). Pac identification of a bandit arm relative to a reward quantile. In Thirly-First AAAI Conference on Artificial Intelligence.
Chaudhuri, A. R. and Kalyanakrishnan, S. (2019). Pac identification of many good arms in stochastic multi-armed bandits. In International Conference on Machine Learning, pages 991-1000. PMLR.
Cordy, C. B. and Thomas, D. R. (1997). Deconvolution of a distribution function. Journal of the American Statistical Association, 155444):
Dattner, I., Goldenshluger, A., and Juditsky, A. (2011). On deconvolution of distribution functions. The Annals of Statistics, pages 2477-2501.
10

---

Delaigle, A., Hall, P., and Meister, A. (2008). On deconvolution with repeated measurements. The Annals of Statistics, 36(2):665-685.
Hall, and Lahiri, S. N. (2008). Estimation of distributions, moments and quantiles deconvolution problems. The Annals of Statistics, 10-21344.
Jamieson, K. and Nowak, R. (2014). Best-arm identification algorithms for multi-armed bandits in the fixed confidence setting. Information Sciences and Systems (CISS), 2014 48th Annual Conference on, pages 1-6. IEEE.
Kaufmann, E., Cappé. O., and Garivier, A. (2016). On the complexity of best-arm identification in multi-armed bandit models. The Journal of Machine Learning Research, 17(1):1-42.
Lai, T. L., Robbins, H., et al. (1985). Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1):4-22.
Lattimore, T. and Szepesvári, (2020). Bandit algorithms. Cambridge University Press.
Le Cam, L.,, LeCam, L. M., and Yang. G. L. (2000). Asymptotics in statistics: some basic concepts. Springer Science & Business Media.
Li, H. and Xia, Y. (2017). Infinitely many-armed bandits with budget constraints. In Thirty-Fine AAAI Conference on Artificial Intelligence.
Rashidinejad, P., Zhu, B., Ma, C., Jiao, J., and Russell, S. (2021). Bridging offline reinforcement learning and imitation learning: A tale of pessimism. Advances in Neural Information Processing Systems, 34.
Schrittwieser, J., Hubert, T., Mandhane, A., Barekatain, M., Antonoglou, I., and Silver, D. (2021). Online and offline reinforcement learning by planning with a learned model. Advances Neural Information Processing Systems, 34.
Son, L. K. and Simon, D. A. (2012). Distributed learning: Data, metacognition, and educational implications. Educational Psychology Review, 24(3):77-399.
Tsybakov, A. (2009). Introduction to Nonparametrie Estimation. Springer- Verlag.
Opringer-Verlag.
Wang. Y., Audibert, J.-Y., and Munos, R. (2008). Algorithms for infinitely many-armed bandits. Advances in Neural Information Processing Systems, 21.
Wasserman, L. (2004). All of statistics: a concise course in statistical inference, volume 26. Springer.
Zhang, M., Zou, J., and Tse, D. (2019). Adaptive monte carlo multiple testing via multi-armed bandits. In International Conference Machine Learning, pages 7512-7522. PMLR.
Zhang, M. J., Ntranos, V., and Tse, D. (2020). Determining sequencing depth in single-cell ma-seq experiment. Nature communications, 11(1):1-11.
Zhang, Z. Ji, X., and Du, S. (2021). Is reinforcement learning more difficult than bandits? near-optimal algorithm escaping the curse of horizon. In Conference on Learning Theory, pages 4528 4531. PMLR.

---

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] Results are stated and properly qualified.
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes) All theorem's have clearly stated assumptions
(b) Did you include complete proofs of all theoretical results? [Yes] All proofs are detailed in the Appendix
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you eite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you're you're using/curating? [N/A]
(c) 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 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]
12


Reviews:
[{"review_id": "uZ-fNyiPED", "reviewer": "Reviewer_9e61", "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. ", "questions": "Could the authors comment on the optimality of the algorithms in all of the settings in more detail? \n\nCould the authors elaborate on the motivation more? As of now, the applications are unclear to me.\n\nPost rebuttal: the authors have addressed my questions on optimality, theoretical comparison between the offline and online settings, and the motivation. ", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nIt is nice that they have a unifying algorithm and sample complexity result for all settings. \n\nThey provide lower bounds for all of the settings.\n\nThe problem formulation is mathematically elegant and it is interesting to consider indicator-based functionals.\n\nWeaknesses:\n\nThe 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.\n\nI 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? \n\nThe 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. \n\nIt would be nice to give some concrete examples where Theorem 2 gives a much better sample complexity than is possible in the online setting. \n\nI 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. \n\nThe 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. \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": "F3TAi0UoVC", "reviewer": "Reviewer_Go45", "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.", "questions": "Please refer to the strengths and weaknesses section for suggestions or points to address.\n\nA 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.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "One strength is that the sample complexity bounds are tight, up to logarithmic factors in the error parameters.\n\nAnother 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. \n\nA 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. \n\nAnother 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. \n\nOne 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. ", "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": "DWH1ydaTvTn", "reviewer": "Reviewer_YnSc", "summary": "The paper studies distribution functional estimation (estimating mean, median, maximum, trimmed mean) in the infinite-armed bandit problem. \n\nFor 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$. \n\nFor 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.\n\nThey 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.\n", "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))$?\n\nSince 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", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n\nQuality: It’s technically sound.\n\nClarity: The paper is written clearly and well organized.\n\nSignificance: 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. \n\nThe 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.\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": "3nH9STRkPrS", "reviewer": "Reviewer_246j", "summary": "The paper considered distribution functional estimation problems in the infinite armed bandit problem.\nFirst, the authors formulated the distribution functional estimation problems (especially mean, median, maximum, trimmed mean estimations). \nThe authors presented meta-algorithms for such distribution functional estimation problems for both online and offline settings together with the sample complexity guarantees.\nNext, lower bounds on the sample complexities for both offline and online settings are shown. \nFor the lower bound for the median estimation problem, the authors remarked on \"thresholding phenomena\" in order to prove tighter lower bounds. \n", "questions": "Please see the Limitations section. ", "limitations": "\nMy main concern is that the research associated with this paper is not well surveyed.\nAs 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. \nThe 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 \nsimple regret) have a largely different nature. \n\nIt looks like there are many papers in statistics that deals with the problem of estimating the statistical functionals. for example,\n\nWasserman, Larry. All of statistics: a concise course in statistical inference. Vol. 26. New York: Springer, 2004.\n\nHall, Peter, and Soumendra N. Lahiri. \"Estimation of distributions, moments and quantiles in deconvolution problems.\" The Annals of Statistics 36.5 (2008): 2110-2134.\n\n(Note these areas are not my expertise.)\n\nWhile there may be a novelty, I believe that appropriate comparisons with papers dealing with similar issues need to be made.\n\n\n\n\n", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- Strengths\n\nA relatively thorough upper/lower bound characterization of the distribution functional estimation problem has been made. (for both offline and online settings)\n\n\n- Weaknesses\n\nThe online algorithm is based on the doubling trick so it may be unpractical. (although theoretically sound)\nNo numerical experiments have been made.\nPositioning of the work (see Limitations section).\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept