1

The answer depends on whether you want a bound for a single, fixed $Q\subseteq M$ or uniformly over all such $Q$. For a single, fixed $Q$, the Chernoff-Hoeffding bound is essentially the best you can do (see also empirical Bernstein's inequality for "fast rates"). If you want the bound to hold simultaneously for all $Q\subseteq M$, you need apply the union ...


Only top voted, non community-wiki answers of a minimum length are eligible