Empirical-Bernstein confidence sequences under adaptive sampling

If $c=0$, then $X_t={\widehat{X}}_t=a$ almost surely for every $t$. By [F6], each $m_t=a$ almost surely, so ${\mu }_t=a$ simultaneously almost surely and the algorithm's singleton $C_t=[a,a]$ covers it. If $c>0$, boundedness gives $X_t\in L^1(P)$; choose the versions in the Statement using [A1]. Any two versions agree almost surely by [F5], and the countable union of their exceptional null sets is null, so the all-times coverage probability does not depend on those choices.

For $x>-1$ define $r(x)=(x-\log (1+x))\mathrm{/}{x}^2$ when $x\mathrm{\ne }0$ and $r(0)=1\mathrm{/}2$. Direct integration gives $r(x)={\int }_0^{1}t\mathrm{/}(1+tx)dt$. The integrand decreases in $x$ for every $t>0$, so $r$ is decreasing on $(-1,\mathrm{\infty })$. If $c>0$, $0<\lambda <1\mathrm{/}c$, and $\mathrm{\mid }\xi \mathrm{\mid }\le c$, then $x=\lambda \xi \ge -\lambda c>-1$, whence $\lambda \xi -\log (1+\lambda \xi )=(\lambda \xi {)}^{2}r(\lambda \xi )\le (\lambda \xi {)}^{2}r(-\lambda c)={\psi }_{E,c}(\lambda ){\xi }^2$. Exponentiating yields $\exp (\lambda \xi -{\psi }_{E,c}(\lambda ){\xi }^2)\le 1+\lambda \xi$; the same holds at $\lambda =0$ by equality.

Fix any one-sided sub-exponential pair at scale $c>0$ and any finite mixture parameters from the Statement. For each $j$, its defining condition [F13] supplies a dominating nonnegative test supermartingale $L^{{\lambda }_j}$. For $x=c{\lambda }_j\in (0,1)$, define $h(t)=-\log (1-t)-t$ on $t<1$. By [F17], $h(0)=0$ and the chain and sum rules give $h^{\mathrm{\prime }}(t)=1\mathrm{/}(1-t)-1=t\mathrm{/}(1-t)$. The function is continuous on $[0,x]$ and differentiable on $(0,x)$ by [F17]. The mean value theorem [F17] gives $h(x)-h(0)=x{h}^{\mathrm{\prime }}(\theta )\ge 0$ for some $0<\theta <x<1$. Since $c^2>0$, ${\psi }_{E,c}({\lambda }_j)=h(x)\mathrm{/}{c}^2\ge 0$. For each fixed $v\ge 0$, $g_v(s)={\sum }_j{w}_j{e}^{{\lambda }_{j}s-{\psi }_{E,c}({\lambda }_j)v}$ is continuous by [F14] and [F18]. Every term is strictly increasing in $s$, since $w_j>0$ and ${\lambda }_j>0$, so [F14] makes the sum strictly increasing. As $s\to -\mathrm{\infty }$, each affine exponent tends to $-\mathrm{\infty }$, so [F14] makes every term tend to zero; the finite sum tends to zero. As $s\to \mathrm{\infty }$, its first term tends to infinity by [F14] and every other term is positive, so the sum tends to infinity. Also $g_v(0)={\sum }_j{w}_j{e}^{-{\psi }_{E,c}({\lambda }_j)v}\le {\sum }_j{w}_j=1<1\mathrm{/}\alpha$. The two limits give finite $s_{-}<0<s_{+}$ with $g_v(s_{-})<1\mathrm{/}\alpha <g_v(s_{+})$; the intermediate value theorem [F15] on $[s_{-},s_{+}]$ gives a root between them, and strict increase makes it unique and positive. Write this root as $u_{\alpha ,c}(v)$. For each real $r\le 0$, $\{v\ge 0:u_{\alpha ,c}(v)<r\}$ is empty. For $r>0$, strict increase and the root equation give $\{v\ge 0:u_{\alpha ,c}(v)<r\}={\bigcup }_{\begin{array}{c}q\in \mathbb{Q}\\ 0<q<r\end{array}}\{v\ge 0:g_v(q)>1\mathrm{/}\alpha \}$. Indeed, if $u_{\alpha ,c}(v)<r$, [F16] supplies a rational $q$ strictly between the positive root and $r$; conversely, $g_v(q)>1\mathrm{/}\alpha$ implies $q>u_{\alpha ,c}(v)$. For fixed $q$, $g_v(q)={\sum }_j{w}_j{e}^{{\lambda }_{j}q-{\psi }_{E,c}({\lambda }_j)v}$ is continuous in $v$ by [F14] and [F18], so each set in the union is open relative to $[0,\mathrm{\infty })$ and the union is open. To apply [F19] directly, if $r\ge 0$, strict increase gives $\{v\ge 0:u_{\alpha ,c}(v)>r\}=\{v\ge 0:g_v(r)<1\mathrm{/}\alpha \}$, which is also relatively open by [F14] and [F18]; if $r<0$, this inverse image is all of $[0,\mathrm{\infty })$. Thus the inverse images of every open right ray are Borel. The real sets whose inverse images are Borel form a sigma-algebra, so [F19] implies that $u_{\alpha ,c}$ is Borel. There are finitely many indices $j$ and countably many integer times, so the almost-sure domination inequalities for all $L^{{\lambda }_j}$ hold simultaneously outside one null set. The finite mixture $L_t={\sum }_j{w}_j{L}_t^{{\lambda }_j}$ is a test supermartingale by [F11]; finite support makes its product measurability immediate. If $S_t\ge u_{\alpha ,c}(V_t)$, then $L_t\ge g_{V_t}(S_t)\ge 1\mathrm{/}\alpha$. Ville's inequality [F12] bounds this crossing event by $\alpha$, so the root is a boundary as in [F13].

On the increasing filtration [F1], for $t\ge 1$ put $Y_t=X_t-m_t$, ${\eta }_t={\widehat{X}}_t-m_t$, and ${\xi }_t=Y_t-{\eta }_t=X_t-{\widehat{X}}_t$. By [F6], $a\le m_t\le b$ almost surely, so $\mathrm{\mid }{\eta }_t\mathrm{\mid }\le c$; by [F8], $E[Y_t\mid {\mathcal{F}}_{t-1}]=0$. Also [F3] and [F4] make ${\eta }_t$ bounded and ${\mathcal{F}}_{t-1}$-measurable, and $\mathrm{\mid }{\xi }_t\mathrm{\mid }\le c$. Apply step 1.2 to ${\xi }_t$ and multiply by $e^{\lambda {\eta }_t}$. Taking conditional expectations, using [F6] and the bounded-factor identity [F7], gives $E[e^{\lambda Y_t-{\psi }_{E,c}(\lambda ){\xi }_t^2}\mid {\mathcal{F}}_{t-1}]\le e^{\lambda {\eta }_t}(1-\lambda {\eta }_t)\le 1$, since $1-z\le e^{-z}$ for $z=\lambda {\eta }_t<1$.

For each $0\le \lambda <1\mathrm{/}c$, define $M_0^{\lambda }=1$ and $M_t^{\lambda }=\exp \text{\hspace{0.17em}⁣}(\lambda {\sum }_{i=1}^t{Y}_i-{\psi }_{E,c}(\lambda )V_t)$. This process is nonnegative and adapted. At each fixed $t$, its exponent is bounded because $\mathrm{\mid }{Y}_i\mathrm{\mid }\le c$ and $0\le V_t\le c^{2}t$, so it is integrable. The one-step inequality in step 2.1, multiplied by the bounded ${\mathcal{F}}_{t-1}$-measurable $M_{t-1}^{\lambda }$, proves the supermartingale condition. Thus [F9], [F10], and [A1] make $M^{\lambda }$ a nonnegative test supermartingale with initial expectation one, so $L_t^{\lambda }=M_t^{\lambda }$ verifies the domination condition in [F13]. Replacing every $Y_i,{\eta }_i$ by $-Y_i,-{\eta }_i$ gives the same conclusion for the pair $(-S_t,V_t)$, where $S_t={\sum }_{i=1}^t{Y}_i$.

For the supplied boundary, [F13] and step 3.1 show that the crossing probability is at most $\alpha$ for both $(S_t,V_t)$ and $(-S_t,V_t)$. Outside their union, $\mathrm{\mid }{S}_t\mathrm{\mid }<u_{\alpha ,c}(V_t)$ for every $t$. Since $S_t=t({\bar{X}}_t-{\mu }_t)$, this is exactly ${\mu }_t\in C_t$ for every interval returned by [L2], with probability at least $1-2\alpha =1-\delta$. By [F1] and [F4], each $m_i$ is ${\mathcal{F}}_{i-1}$-measurable, so ${\mu }_t$ is ${\mathcal{F}}_t$-measurable; ${\bar{X}}_t,V_t$ are also ${\mathcal{F}}_t$-measurable by [F2] and [F3], and composition with the Borel boundary makes the interval endpoints measurable. Thus [L1] applies. If all $m_i=\mu$ almost surely for one fixed $\mu$, their countable intersection has probability one and then ${\mu }_t=\mu$ for all $t$, proving the fixed-mean clause.