Nearly Optimal Catoni's M-estimator for Infinite Variance

1 In this paper, we extend the remarkable Mestimator of Catoni (2012) to situations where the variance is infinite. In particular, given a sequence of i.i.d random variables X i n i=1 from distribution D over R with mean µ, we only assume the existence of a known upper bound υ ε > 0 on the (1 + ε) th central moment of the random variables, namely, for ε ∈ (0, 1] The extension is non-trivial owing to the difficulty in characterizing the roots of certain polynomials of degree smaller than 2. The proposed estimator has the same order of magnitude and the same asymptotic constant as in Catoni ( 2012 ), but for the case of bounded moments. We further propose a version of the estimator that does not require even the knowledge of υ ε , but adapts the moment bound in a data-driven manner. Finally, to illustrate the usefulness of the derived non-asymptotic confidence bounds, we consider an application in multi-armed bandits and propose best arm identification algorithms, in the fixed confidence setting, that outperform the state of the art.