  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
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 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. The matching lower
bounds utilize several 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.
