In Section , we upper-bound the sample complexity of PPR-ME for the base case of \(K = 2\) , showing it to be optimal up to a logarithmic factor for the well-studied “Bernoulli” setting. This finding might independently bear significance to the push for tighter confidence bounds
in the bandits literature [1]}, [2]}. In Section , we describe PPR-ME for \(K \ge 2\)  and derive an upper bound on its sample complexity. Interestingly, this upper bound also matches the lower bound in Theorem REF  up to a logarithmic factor, and marginally improves upon the constant factor in the upper bound from Theorem REF . In sections  and , we also provide empirical comparisons between PPR-ME and other approaches to PAC mode estimation. We find strong support for using “one-versus-one” comparisons for mode estimation (as in PPR-ME), as opposed to a “one-versus-rest” approach (as in \(\mathcal {A}_{1}\)  [3]}).
