Bernstein inequality is a very powerful concentration inequality, and can obtain a sharper bound than Hoeffding providing the variance is sufficiently small. The following statements exactly show this [1].
- Bernstein Inequality.
Let $X_1,X_2,\ldots,$ be a sequence of independent random variables such that for all $i\geq 1$, with $\mathbb{E}[X_i]=0$ and $X_i\in [-1,1]$. Suppose their variance is smaller than $\sigma$, that is, $\mathbb{E}[X_i^2]\leq \sigma$. Then the classic Bernstein ineqality says that $$ \Pr\left[\sum_{i=1}^m X_i > t \right]\leq \exp\left\{-\frac{t^2}{2m\sigma + 4t}\right\}. $$ - Maximal Form of Bernstein Inequality. With the same condition as shown in Bernstein inequality, then the maximal form says that $$ \Pr\left[\max_{1\leq j\leq m}\sum_{i=1}^j X_i > t \right]\leq \exp\left\{-\frac{t^2}{2m\sigma + 4t}\right\}. $$
In many scenarios, however, we prefer to adopt the empirical Bernstein inequality shown as follows (Theorem 1 in [2]),
Empirical Bernstein Inequality. Let $X_1,X_2,\ldots,$ are iid random variables taking values in $[0,b]$, and $\mathbb{E}[X_i]=0$ for all $i$. Define the emprical variance as $\hat{\sigma}_t=\sum_{i=1}^t(X_t-\hat{\mu}_t)^2/t$, with $\hat{\mu}_t = \sum_{i=1}^t X_i/t$, then for any $t\in \mathbb{N}$ and $s>0$, $$ \Pr\left[|\hat{\mu}_t|\leq \sqrt{\frac{2\hat{\sigma}_t s}{t}} + \frac{3bs}{t}\right] \geq 1-3e^{-s}. $$
My question: is there a maximal version of empirical Bernstein inequality? Thanks.
Reference:
[1] A note on a maximal Bernstein inequality, https://arxiv.org/pdf/1107.3365.pdf
[2] Exploration-exploitation trade-off using variance estimates in the multiarmed bandit setting, http://certis.enpc.fr/~audibert/RR0731.pdf