Sharp Empirical Bernstein Inequalities for the Variance of Bounded Random Variables

We develop novel "empirical Bernstein" inequalities for the variance of bounded random variables. Our inequalities hold under constant conditional variance and mean, without further assumptions like independence or identical distribution of the random variables, making them suitable for sequential decision making contexts. The results are instantiated for both the batch setting (where the sample size is fixed) and the sequential setting (where the sample size is a stopping time). Our bounds are asymptotically "sharp": when the data are iid, our CI adapts optimally to both unknown mean $\mu$ and unknown $\mathbb{V}[(X-\mu)^2]$, meaning that the first order term of our CI exactly matches that of the oracle Bernstein inequality which knows those quantities. We compare our results to a widely used (non-sharp) concentration inequality for the variance based on self-bounding random variables, showing both the theoretical gains and improved empirical performance of our approach. We finally extend our methods to work in any separable Hilbert space.

In machine learning, algorithms must measure how much their data fluctuates (the variance) to make safe decisions. While previous researchers have developed ways to bound this uncertainty using observed data, these existing formulas are often mathematically "loose", which forces algorithms to be overly cautious and inefficient when exploring new environments. Our paper introduces sharp empirical Bernstein bounds to create highly precise confidence intervals for the variance itself. Building on prior alternatives, our method calculates strictly tighter upper and lower limits using only the data at hand, automatically adapting to the environment without requiring hidden system properties. We mathematically prove these new bounds are "asymptotically sharp", meaning their accuracy approaches what would be possible if the algorithm had perfect prior knowledge of the system. By reducing unnecessary caution, these bounds give researchers a tighter, more efficient tool for quantifying uncertainty in dynamic applications like reinforcement learning and multi-armed bandits.