\section{Competing Concentration Bounds}
\begin{thm}[Hoeffding; Theorem 3.1.2 of~\citet{gine2016mathematical}]
If $X_1, \ldots, X_n$ are independent mean-zero random variables satisfying $\mathbb{P}(\underline{B} \le X_i \le B) = 1$, then
    \[
        \P \left( S_n \geq \sqrt{\frac{1}{2} n (B - \underline{B})^2 \log \left(\frac{1}{\delta}\right)} \, \right) \leq \delta, \quad  \forall \delta \in [0, 1].
    \]
\end{thm}
(There is a generalization of Hoeffding's inequality that relaxes the boundedness assumption by a sub-Gaussian assumption; see~\citet{zhao2016adaptive} for details.)


\begin{thm}[Adaptive Hoeffding; Corollary 1 of~\citet{zhao2016adaptive}]
If $X_1, \ldots, X_n$ are independent mean-zero random variables satisfying $\mathbb{P}(\underline{B} \le X_i \le B) = 1$, then
    \[
        \P \left(\exists n\ge 1:\, S_n \geq (B-\underline{B}) \sqrt{ 0.6 n \log(\log_{1.1}n + 1) + \frac{\log(12/\delta)}{1.8}n } \, \right)
        \leq \delta, \quad \forall \delta \in [0, 1].
    \]
\end{thm}

\begin{thm}[Bernstein; Theorem 3.1.7 of~\citet{gine2016mathematical}] If $X_1, \ldots, X_n, \ldots$ are independent random variables satisfying~\eqref{eq:boundedness-conditions}, then
    \[
        \P \left( S_n \geq \sqrt{
         2 \sum_{i=1}^n A_i^2 \log\left(\frac{1}{\delta}\right)
         + \frac{1}{9} B^2\log^2\left(\frac{1}{\delta}\right)
        } + \frac{1}{3}B\log\left(\frac{1}{\delta}\right)\, \right)
        \leq \delta, \quad \forall \delta \in [0, 1].
    \]
\end{thm}

\begin{thm}[Empirical Bernstein; Eq. (5) of~\citet{mnih2008empirical}]
If $X_1, X_2, \ldots$ are independent mean zero random variables satisfying~\eqref{eq:boundedness-conditions} with $A_1 = A_2 = \ldots = A$, then
\[
\mathbb{P}\left(\exists n \ge 1:\, S_n \ge \sqrt{2 n \eta \widehat{A}_n^2\log(3h(k_n)/(2\delta))} + 3 B \eta\log(3h(k_n)/(2\delta))\right) \le \delta,
\]
where $\widehat{A}_n^2$ is the sample variance and $k_n$ is the constant defined in Theorem~\ref{thm:uniform-in-n}.
\end{thm}


\section{More Simulations}\label{appsec:more-simulations}
\subsection{Hyperparameters of Stitching}\label{appsec:hyperparam_stitch}
In Section~\ref{sec:unif-conf-seq}, we mentioned that there are two hyperparameters of our stitching methods: (1) the spacing parameter $\eta >
1$ and (2) the power parameter $c > 1$ for the stitching function $h_c(k) = \zeta(c)
(k+1)^c$ where $\zeta(\cdot)$ is the Riemann zeta function.
\clearpage
\begin{figure}[h]
    \centering
    \includegraphics[width=0.5\textwidth]{bentkus_different_eta}
    \caption{The upper bound of $S_n$ obtained by adaptive Bentkus bound in Theorem~\ref{thm:uniform-in-n} for different values of $\eta$.
        Both the variance $A = \sqrt{3}/4$ and the upper bound $B=3/4$ is known.}
    \label{fig:hyperparam_eta}
\end{figure}
Figure~\ref{fig:hyperparam_eta} illustrates that
the choice of $\eta$ determines how the budget $\delta$ is distributed across different sample sizes.

\begin{figure}[h]
    \centering
    \includegraphics[width=0.45\textwidth]{h_different_power}
    \includegraphics[width=0.43\textwidth]{bentkus_different_power}
    \caption{
        \textbf{Left:} The stitching function $h_c(\cdot)$ for different values of $c$.
        \textbf{Right:} The upper bound of $S_n$ obtained by \bk with different values
        of $c$. Both the variance $A^2 = 3/16$ and the upper bound $B=3/4$ is known.
    }
    \label{fig:hyperparam_power}
\end{figure}
Figure \ref{fig:hyperparam_power} shows both the stitching function $h_c(\cdot)$
and corresponding upper bound \bk obtains. For a fixed sample size $n$,
the bigger $h_c(k_n)$ is, the smaller budget
$\delta / h_c(k_n)$ it obtains and hence it needs a larger upper bound.
Hence, the faster $h_c(\cdot)$ grows, the more conservative upper bound (and
corresponding, wider confidence interval) one will get.


\subsection[Confidence Sequence Unbiased Coin Toss]{Confidence Sequence for $\Bern{0.5}$}
In this section, we present a comparison of our confidence sequence with \ah, \eb,
\ho, and \hog on synthetic data from $\Bern{0.5}$. In this case, $Y_1, Y_2, \ldots\sim\Bern{0.5}$ and the variance is $1/4$. Hence in this case Hoeffding's inequality is sharp and nothing can be gained by variance exploitation. We observe this very fact in our experiment, where our method behaves as well as \ah for moderate to large sample sizes. Figures~\ref{fig:one-replication_phalf} and~\ref{fig:multi-replications_phalf} show the comparison of confidence sequences in one replication and comparison of average width over 1000 replications. As in the case of $\Bern{0.1}$ (Section~\ref{sec:comparison-with-conf-seq}), for small sample sizes, \ah and \bk behave very closely and are better than all other methods but for $n$ moderately large, the sharpness of \bk clearly pays off by outperforming \ah and all other methods.
\begin{figure}[h]
        \centering
        \begin{subfigure}{.49\textwidth}
            \includegraphics[width=0.95\textwidth]{ci_example_20k_phalf.pdf}
        \caption{One Replication}
        \label{fig:one-replication_phalf}
        \end{subfigure}
        \begin{subfigure}{.49\textwidth}
        \includegraphics[width=0.95\textwidth]{ci_width_phalf_with_hrms_gamma.pdf}
        \caption{Average Width over 1000 Replications}
        \label{fig:multi-replications_phalf}
        \end{subfigure}
        \caption{
            Comparison of the 95\% confidence sequences for the mean when $Y_i \sim \Bern{0.5}$. Except \ah, all other methods estimate the variance. \bk is the confidence sequence in~\eqref{eq:empirical-bentkus-conf-seq}. \hog involves a tuning parameter $\rho$ which is chosen to optimize the boundary at $n = 500$.
            \textbf{(a)} shows the confidence sequences from a single replication.
            \textbf{(b)} shows the average widths of the confidence sequences over 1000 replications.
            The upper and lower bounds for all the other methods are cut at $1$ and $0$
            for a fair comparison. The failure frequency is $0.001$ for \hog and $0$
            for the others.
            
        }
\end{figure}


\input{07-bandit_expr_discussion}

\section{Computation of $q(\delta; n, \mathcal{A}, B)$}\label{appsec:computation-of-q-function}
In this section we provide some details on the computation of $q(\delta; n, \mathcal{A}, B)$ based on~\citet{bentkus2004hoeffding} and~\citet{pinelis2009bennett}. We will restrict to the case where $A_1 = A_2 = \cdots = A_n = \cdots = A$.

For any random variable $\eta$, define
\[
P_2(u; \eta) ~:=~ \inf_{x \le u}\frac{\mathbb{E}[(\eta - x)_+^2]}{(u - x)_+^2}.
\]
For any $A, B$, set $\pab = {A^2}/{(A^2+B^2)}$.
Define Bernoulli random variables $R_1, R_2, \ldots, R_n$ as
\[
    \mathbb{P}(R_i = 1) ~=~ \pab ~=~ 1 - \mathbb{P}(R_i = 0).
\]
Set $Z_n = \sum_{i=1}^n R_i$. $Z_n$ is a binomial random variables
with $n$ trials and success probability $\pab$: $Z_n \sim \mbox{Bi}(n, \pab)$.
For $0 \le k\le n$, define
\begin{align*}
    p_{k} ~&:=~ \mathbb{P}\left(Z_n \ge k\right),\quad e_{k} ~:=~ \mathbb{E}\left[Z_n\mathds{1}\left\{Z_n \ge k\right\}\right],\quad v_{k} ~:=~ \mathbb{E}\left[Z_n^2\mathds{1}\left\{Z_n \ge k\right\}\right].
\end{align*}
\begin{prop}
For all $u\in\mathbb{R}$,
\[
    P_2\left(u; \sum_{i=1}^n G_i\right) ~=~ P_2\left(\frac{Bu + nA^2}{A^2 + B^2};\, Z_n \right) ~=~ P_2\left(\frac{Bu + nA^2}{A^2 + B^2}; Z_n\right).
\]
Furthermore, for any $x\ge 0$ and $1\le k \le n-1$,
\[
P_2\left(x; Z_n\right) ~=~
\begin{cases}
    1,  &   \mbox{if }x ~\le~ n \pab,\\
    \frac{n\pab(1 - \pab)}{(x - n\pab)^2 + n\pab(1 - \pab)}, &\mbox{if }n \pab < x \le \frac{v_0}{e_0},\\
    \frac{v_{k}p_{k} - e_{k}^2}{x^2p_{k} - 2xe_{k} + v_{k}}, &\mbox{if }\frac{v_{k-1} - (k-1)e_{k-1}}{e_{k-1} - (k-1)p_{k-1}} < x \le \frac{v_k - ke_k}{e_{k} - kp_k},\\
    \mathbb{P}\left(Z_n = n\right) = \pab^n, &\mbox{if }x~\ge~ \frac{v_{n-1} - (n-1)e_{n-1}}{e_{n-1} - (n-1)p_{n-1}} = n.
\end{cases}
\]
Formally, we can set $P_2(x; Z_n) = 0$ for all $x > n$ because $\mathbb{P}(Z_n > n) = 0$.
\end{prop}

\begin{proof}
The result is mostly an implication of Proposition 3.2 of~\citet{pinelis2009bennett}.

It is clear that
\[
M_n := \sum_{i=1}^n G_i ~\overset{d}{=}~ \frac{A^2 + B^2}{B}\left(\sum_{i=1}^n R_i - \frac{nA^2}{A^2 + B^2}\right),
\]
where $R_i\sim\mathrm{Bernoulli}(A^2/(A^2 + B^2))$, that is,
\[
    \mathbb{P}\left(R_i = 1\right) ~=~ \pab ~=~ 1 - \mathbb{P}(R_i = 0).
\]
Proposition 3.2(vi) of~\citet{pinelis2009bennett} implies that
\[
    P_2(u;\, M_n) ~:=~ P_2\left(\frac{Bu + nA^2}{A^2 + B^2};\, Z_n \right).
\]
Hence it suffices to find $P_2(x;\,Z_n)$ for all $x\in\mathbb{R}$. The support of $Z_n$ is given by
\[
\mathrm{supp}(Z_n) = \{0, 1, 2, \ldots, n\}.
\]

Proposition 3.2(iv) of~\citet{pinelis2009bennett} (with $\alpha = 2$) implies that
\[
    P_2\left(x; Z_n \right) ~=~
\begin{cases}
    1,&\mbox{if }x \le n \pab,\\
    \mathbb{P}\left(Z_n = n\right), &\mbox{if }x\ge n.
\end{cases}
\]
Furthermore, $x\mapsto P_2(x; \sum_{i=1}^n R_i)$ is strictly decreasing on $(n \pab,
n)$. Define function $F(h): \R \rightarrow \R$ such that
\begin{equation}\label{eq:definition-F_h}
F(h) ~:=~ \frac{\mathbb{E}[Z_n\left(Z_n - h\right)_+]}{\mathbb{E}\left(Z_n -
        h\right)_+}.
\end{equation}
For any $n \pab < x < n$, let $h_x$ be the unique solution of
\begin{equation}\label{eq:root-solving}
    F(h)~=~ x
\end{equation}
(Uniqueness here is established by Proposition 3.2(ii) of~\citet{pinelis2009bennett}.) Then by Proposition 3.2(iii) of~\citet{pinelis2009bennett},
\begin{equation}\label{eq:P_2-based-on-h-x}
\begin{split}
      P_2\left(x; Z_n\right) ~&=~ \frac{\mathbb{E}[(Z_n - h_x)_+^2]}{(x - h_x)_+^2}\\
~&=~ \frac{\mathbb{E}[Z_n\left(Z_n - h_x\right)_+] - h_x\mathbb{E}[\left(Z_n - h_x\right)_+]}{(x - h_x)_+^2}\\
~&=~ \frac{(x - h_x)\mathbb{E}[\left(Z_n - h_x\right)_+]}{(x - h_x)_+^2}\\
~&=~ \frac{\mathbb{E}[\left(Z_n - h_x\right)_+]}{(x - h_x)_+}.
\end{split}
\end{equation}
This holds for all $nA^2/(A^2 + B^2) < x < n$. We will now discuss solving~\eqref{eq:root-solving}.

Proposition 3.2(i) of~\citet{pinelis2009bennett} implies that $h\mapsto F(h)$ is
continuous and increasing. 


If $h\le0$,
\[
F(h)
= \frac{\mathbb{E}[Z_n(Z_n - h)]}{\mathbb{E}[Z_n - h]}
= \frac{n\pab(1 - \pab) + n^2\pab^2 - hn\pab}{n\pab - h} = n\pab + \frac{np(1-\pab)}{np-h}.
\]
This is strictly increasing on $(-\infty, 0]$, and $F(0) = n\pab + (1 - \pab)$.
We get that for any $n\pab < x \leq n\pab + (1 - \pab)$,
\[
F(h) = x \quad\Leftrightarrow\quad h_x = n\pab - \frac{n\pab(1 - \pab)}{x - n\pab}.
\]
This further implies (from~\eqref{eq:P_2-based-on-h-x}) that
\begin{align*}
P_2(x; Z_n) ~&=~ \frac{\mathbb{E}[Z_n - h_x]}{x - h_x}\\
~&=~ \frac{n\pab(1 - \pab)}{(x - n\pab)^2 + n\pab(1 - \pab)},\quad\mbox{for}\quad n\pab \le x \le n\pab + (1 - \pab).
\end{align*}

If $0 < h < n-1$, set $k = \ceil{h}$, in other words, $k -1 < h \leq k$.

Since $\{Z_n \ge h\} \Leftrightarrow \{Z_n \ge k\}$, hence
\begin{align*}
   \mathbb{E}[Z_n\left(Z_n - h\right)_+]
&= \mathbb{E}[Z_n^2\mathds{1}\{Z_n \ge h\}] - h\mathbb{E}[Z_n\mathds{1}\{Z_n \ge h\}]\\
&= \mathbb{E}[Z_n^2\mathds{1}\{Z_n \ge k\}] - h\mathbb{E}[Z_n\mathds{1}\{Z_n \ge k\}],\\
    \mathbb{E}[(Z_n - h)_+]
&= \mathbb{E}[Z_n\mathds{1}\{Z_n \ge k\}] - h\mathbb{P}(Z_n \ge k).
\end{align*}
Therefore,
\begin{align*}
F(h) ~&=~ \frac{\mathbb{E}[Z_n^2\mathds{1}\{Z_n \ge k\}] - h\mathbb{E}[Z_n\mathds{1}\{Z_n \ge k\}]}{\mathbb{E}[Z_n\mathds{1}\{Z_n \ge k\}] - h\mathbb{P}(Z_n \ge k)}\\
~&=~ \frac{v_k - he_k}{e_k - hp_k}.
\end{align*}

It is not difficult to verify that $F(\cdot)$ is strictly increasing in $(k-1, k]$ and hence
\[
    h_x ~=~ \frac{v_k - xe_k}{e_k - xp_k}, \quad\mbox{if}\quad F(k-1) < x \le F(k).
\]
Substituting this $h_x$ in~\eqref{eq:P_2-based-on-h-x} yields the value of $P_2(x;\,Z_n)$, that is,
\begin{align*}
P_2(x;\,Z_n) ~&=~ \left(x - \frac{v_{k} - xe_{k}}{e_{k} - xp_{k}}\right)^{-1}\left(e_{k} - \frac{v_{k} - xe_{k}}{e_{k} - xp_{k}}p_{k}\right)\\
~&=~ \left(\frac{e_{k} - xp_{k}}{2xe_{k} - x^2p_{k} - v_{k}}\right)\left(\frac{e_{k}^2 - v_{k}p_{k}}{e_{k} - xp_{k}}\right)\\
~&=~ \frac{e_{k}^2 - v_{k}p_{k}}{2xe_{k} - x^2p_{k} - v_{k}},\quad\mbox{whenever}\quad
F(k-1) < x \le F(k),
\end{align*}
where $F(k) = \frac{v_k - k e_k}{e_k - k p_k}$, $1 \le k \le n-1$.


Hence for $1\le k \le n-1$,
\[
P_2(x; Z_n) ~=~ \frac{v_{k}p_{k} - e_{k}^2}{x^2p_{k} - 2xe_{k} + v_{k}},\quad\mbox{whenever}\quad \frac{v_{k-1} - (k-1)e_{k-1}}{e_{k-1} - (k-1)p_{k-1}} < x \le \frac{v_k - ke_{k}}{e_k - kp_k}.
\]

Finally, we prove that $F(\cdot)$ is a constant on $[n-1, n]$. It is clear that
\begin{align*}
F(n-1) &=  \frac{v_{n-1} - (n-1)e_{n-1}}{e_{n-1} - (n-1)p_{n-1}}\\
&= \frac{\mathbb{E}[Z_n^2\mathds{1}\{Z_n \ge n-1\}] - (n-1)\mathbb{E}[Z_n\mathds{1}\{Z_n \ge n-1\}]}{\mathbb{E}[Z_n\mathds{1}\{Z_n \ge n-1\}] - (n-1)\mathbb{P}(Z_n \ge n-1)}\\
&= \frac{(n^2 - n(n-1))\mathbb{P}(Z_n = n)}{(n - (n-1))\mathbb{P}(Z_n = n)} = n.
\end{align*}
Further if $h > n-1$, then $(Z_n - h)_+ > 0$ if and only if $Z_n = h$ and hence from~\eqref{eq:definition-F_h}
\[
F(h) = \frac{\mathbb{E}[Z_n(Z_n - h)_+]}{\mathbb{E}[(Z_n - h)_+]} = \frac{n(n - h)\mathbb{P}(Z_n = n)}{(n-h)\mathbb{P}(Z_n = n)} = n.
\]
Therefore, the function $F(h)$ is constant on $[n-1, n]$.

For $h > n$, we set $F(h) = n$ since $\mathbb{P}(Z_n > h) = 0$. To put all the pieces together, we have
\begin{equation}
    \label{eq:Fh_final}
    F(h) =
    \begin{cases}
        n\pab + \frac{np(1-\pab)}{np-h} & \quad\mbox{if} \quad h <= 0, \\
        \dfrac{v_\ceil{h} - h e_\ceil{h}}{e_\ceil{h} - hp_\ceil{h}} & \quad\mbox{if} \quad 0 < h \le n-1,\\
        n & \quad\mbox{if} \quad  h > n-1.
    \end{cases}
\end{equation}
Consequently, for $n\pab < x < n$,
\begin{equation}
    \label{eq:Fh_inv_final}
    h_x = F^{-1}(x) =
    \begin{cases}
        n\pab - \frac{n\pab(1 - \pab)}{x - n\pab}, & \quad\mbox{if} \quad n\pab < x \leq n\pab + (1 - \pab), \\
        \frac{v_k - xe_k}{e_k - xp_k}, & \quad\mbox{if}\quad F(k-1) < x \le F(k), \,1 \leq k \leq n-1. \\
    \end{cases}
\end{equation}
\end{proof}
As a graphical example, Figure~\ref{fig:function_F_and_P2} plots $F(h)$ and $P_2(x; Z_n)$ when $n=3$, $A=0.1$ and
        $B=1.0$.
        
\begin{figure}[t]
    \centering
    \includegraphics[width=0.32\textwidth]{function_F_n3}
    \hspace{0.01\textwidth}
    \includegraphics[width=0.64\textwidth]{function_P2_n3}
    \caption{Examples functions $F(h)$ and $P_2(x; Z_n)$ when $n=3$, $A=0.1$ and
        $B=1.0$. We plot $P_2(x;Z_n)$ in both linear (second plot) and log (third plot) scales on the y-axis.}
    \label{fig:function_F_and_P2}
\end{figure}

\subsection{Computation of the Quantile}\label{subsec:computation-of-quantile}
Recall $\pab = A^2/(A^2 + B^2), Z_n = \sum_{i=1}^n R_i,$ and $\sum_{i=1}^nG_i$ is identically distributed as $B^{-1}(A^2 + B^2)(Z_n - n\pab)$. We will compute $x_{\delta}$ such that
\begin{equation}\label{eq:quantile-of-Zn}
P_2(x_{\delta}; Z_n) = \delta.
\end{equation}
This implies that
\[
P_2\left(\frac{(A^2 + B^2)x_{\delta} - nA^2}{B};\,\sum_{i=1}^n G_i\right) = \delta,\quad\mbox{or equivalently,}\quad q(\delta; n, A, B) = \frac{(A^2 + B^2)x_{\delta} - nA^2}{B}.
\]
Hence we concentrate on solving~\eqref{eq:quantile-of-Zn}. Recall that for any $x\ge 0$ and $1\le k \le n-1$,
\begin{equation}\label{eq:recall-p2}
P_2\left(x; Z_n\right) ~=~
\begin{cases}
    1,  &   \mbox{if }x ~\le~ n \pab,\\
    \frac{n\pab(1 - \pab)}{(x - n\pab)^2 + n\pab(1 - \pab)}, &\mbox{if }n \pab < x \le \frac{v_0}{e_0} = n\pab + (1 - \pab),\\
    \frac{v_{k}p_{k} - e_{k}^2}{x^2p_{k} - 2xe_{k} + v_{k}}, &\mbox{if }\frac{v_{k-1} - (k-1)e_{k-1}}{e_{k-1} - (k-1)p_{k-1}} < x \le \frac{v_k - ke_k}{e_{k} - kp_k},\\
    \mathbb{P}\left(Z_n = n\right) = \pab^n, &\mbox{if }x~\ge~ \frac{v_{n-1} - (n-1)e_{n-1}}{e_{n-1} - (n-1)p_{n-1}} = n.
\end{cases}
\end{equation}
The function $P_2(\cdot; Z_n)$ is a non-increasing function and hence if $\delta \le \pab^n$, then we get $x_{\delta} = n + 10^{-8}$; this corresponds to the last case in~\eqref{eq:recall-p2}. If $P_2(v_0/e_0; Z_n) \le \delta \le 1$, then
\[
x_{\delta} = n\pab + \sqrt{\frac{(1 - \delta)n\pab(1-\pab)}{\delta}};
\]
this corresponds to the first and second case in~\eqref{eq:recall-p2}; note that $P_2(v_0/e_0; Z_n) = n\pab(1-\pab)/[(1-\pab)^2 + n\pab(1-\pab)]$.
For the remaining cases, note that if
there exists a $1 \le k\le n-1$ such that
\[
P_2\left(\frac{v_k - ke_k}{e_{k} - kp_k}; Z_n\right) ~\le~ \delta ~\le~ P_2\left(\frac{v_{k-1} - (k-1)e_{k-1}}{e_{k-1} - (k-1)p_{k-1}}; Z_n\right),
\]
then
\begin{equation}\label{eq:finding-k}
\frac{v_{k-1} - (k-1)e_{k-1}}{e_{k-1} - (k-1)p_{k-1}} ~\le~ x_{\delta} ~\le~ \frac{v_k - ke_k}{e_{k} - kp_k},
\end{equation}
and using the closed form expression of $P_2(\cdot; Z_n)$ on this interval, we get
\begin{equation}\label{eq:final-formula-x-delta}
x_{\delta} = \frac{e_k + \sqrt{e_k^2 - p_k(v_k - (v_kp_k - e_k^2)/\delta)}}{p_k}.
\end{equation}
Using these calculations, one can find $k$ looping over $1\le k\le n-1$ such that~\eqref{eq:finding-k} holds. This approach has a complexity of $O(n)$, assuming the availability of $p_k, e_k,$ and $v_k$.

We now describe an approach that reduces the complexity by finding quick-to-compute upper and lower bounds on $x_{\delta}$. Lemmas 1.1 and 3.1 of~\citet{bentkus2006domination} show that
\begin{equation}\label{eq:two-bounds-P2}
\mathbb{P}(Z_n \ge x) \le P_2(x; Z_n) \le \frac{e^2}{2}\mathbb{P}^{\circ}(Z_n \ge x),
\end{equation}
where $\mathbb{P}^{\circ}(Z_n \ge x)$ represents the log-linear interpolation of $P(Z_n \ge x)$, that is, for $x \in \{0, 1, \ldots, n\}$
\begin{equation}\label{eq:at-lattice-points}
\mathbb{P}^{\circ}(Z_n \ge x) ~=~ \mathbb{P}(Z_n \ge x),
\end{equation}
and for $x\in(k-1, k)$ such that $x = (1 - \lambda)(k-1) + \lambda k$,
\[
\mathbb{P}^{\circ}(Z_n \ge x) = (\mathbb{P}(Z_n \ge k-1))^{1-\lambda}(\mathbb{P}(Z_n \ge k))^{\lambda}.
\]
Equation (2) of~\citet{bentkus2002remark} further shows that
\begin{equation}\label{eq:linear-interpolation}
\mathbb{P}^{\circ}(Z_n \ge x) \le (1 - \lambda)\mathbb{P}(Z_n \ge k-1) + \lambda\mathbb{P}(Z_n \ge k).
\end{equation}
Hence, to find $x = x_{\delta}$ satisfying $P_2(x; Z_n) = \delta$, find $k_1\in\{0, 1,\ldots, n\}$ such that
\[
\mathbb{P}(Z_n \ge k_1) \ge \delta.
\]
This implies (from~\eqref{eq:two-bounds-P2}) that $P_2(k_1; Z_n) \ge \delta$ and because $x\mapsto P_2(x; Z_n)$ is decreasing, $x_{\delta} \ge k_1$. Further, find $k_2\in\{0, 1, \ldots, n\}$ such that
\[
\mathbb{P}(Z_n \ge k_2) \le {2\delta}/{e^2}.
\]
This implies (from~\eqref{eq:linear-interpolation}) that $\mathbb{P}^o(Z_n \ge k_2) = \mathbb{P}(Z_n \ge k_2) \le 2\delta/e^2$. Hence using~\eqref{eq:at-lattice-points}, we get $P_2(k_2; Z_n) \le \delta$ which implies that $x_{\delta} \le k_2$. Summarizing this discussion, we get that $x_{\delta}$ satisfying $P_2(x_\delta; Z_n) = \delta$ also satisfies
\begin{equation}\label{eq:initial-bounds}
k_1 \le x_{\delta} \le k_2,
\end{equation}
where
\[
\mathbb{P}(Z_n \ge k_1) \ge \delta\quad\mbox{and}\quad \mathbb{P}(Z_n \ge k_2) \le {2\delta}/{e^2}.
\]
The bounds in~\eqref{eq:initial-bounds} are not very useful because the closed form experssion~\eqref{eq:final-formula-x-delta} of $x_{\delta}$ requires finding upper and lower bounds for $x_{\delta}$ in terms of $(v_k - ke_k)/(e_k - kp_k)$'s.

Now we note that
\[
v_{k} \ge ke_{k} \ge k^2p_{k}\quad\Rightarrow\quad \frac{v_{k_2} - k_2e_{k_2}}{e_{k_2} - k_2p_{k_2}} \ge k_2.
\]
This combined with~\eqref{eq:initial-bounds} proves that
\[
k_1 \le x_{\delta} \le k_2 \le \frac{v_{k_2} - k_2e_{k_2}}{e_{k_2} - k_2p_{k_2}}.
\]
The lower bound here is still not in terms of the ratios $(v_k - ke_k)/(e_k - kp_k)$. But given the upper bound, we can search for $k \le k_2$ (by running a loop from $k_2$ to 0) such that
\begin{equation}\label{eq:finding-k-second}
\frac{v_{k-1} - (k-1)e_{k-1}}{e_{k-1} - (k-1)p_{k-1}} ~\le~ x_{\delta} ~\le~ \frac{v_k - ke_k}{e_{k} - kp_k}.
\end{equation}
Another approach is to make use of the lower bound in~\eqref{eq:initial-bounds}. Because $k_1 \le (v_{k_1} - k_1e_{k_1})/(e_{k_1} - k_1p_{k_1})$, there are two possibilities:
\begin{enumerate}
    \item $k_1 \le x_{\delta} \le (v_{k_1} - k_1e_{k_1})/(e_{k_1} - k_1p_{k_1})$;
    \item $k_1 \le (v_{k_1} - k_1e_{k_1})/(e_{k_1} - k_1p_{k_1}) < x_{\delta}$.
\end{enumerate}
In the first case, it suffices to search for $k \le k_1$ such
that~\eqref{eq:finding-k-second}. In the second case, we can search over $k_1 + 1 \leq k \le k_2$ as before.


\section{Proof of Theorem~\ref{thm:initial-maximal-ineq}}\label{appsec:proof-of-theorem-initial-maximal-ineq}
It is clear that $(S_t, \mathcal{F}_t)_{t = 1}^{n}$ with $\mathcal{F}_t = \sigma\{X_1, \ldots, X_t\}$ is a martingale because
\[
\mathbb{E}\left[S_t|\mathcal{F}_{t-1}\right] = S_{t-1} + \mathbb{E}[X_t] = S_{t-1}.
\]
Consider now the process
\[
D_t := \left(S_t - x\right)_+^2\quad\mbox{for a fixed}\quad x > 0.
\]
The function $f:y\mapsto (y - x)^2_+$ is continuous and satisfies
\[
f'(y) = \begin{cases}0,&\mbox{if }y \le x,\\2(y - x), &\mbox{if }y > x,\end{cases}\quad\mbox{and}\quad f''(y) = \begin{cases}0,&\mbox{if }y \le x,\\
2, &\mbox{if }y > x.\end{cases}
\]
Therefore, $f(\cdot)$ is a convex function. This implies by Jensen's inequality that
\[
\mathbb{E}[D_t|\mathcal{F}_{t-1}] = \mathbb{E}[f(S_t)|\mathcal{F}_{t-1}] \ge f(S_{t-1}).
\]
Hence $(D_t, \mathcal{F})_{t=1}^{n}$ is a submartingale. Doob's inequality now implies that
\begin{align*}
\mathbb{P}\left(\max_{1 \le t \le n} S_t \ge u\right) ~&\overset{(a)}{=}~ \mathbb{P}\left(\max_{1 \le t \le n}(S_t - x)^2_+ \ge (u - x)_+^2\right)\\
~&=~ \mathbb{P}\left(\max_{1 \le t\le n}D_t \ge (u - x)_+^2\right)\\
~&\overset{(b)}{\le}~ \frac{\mathbb{E}[D_{n}]}{(u - x)_+^2} ~\le~ \frac{\mathbb{E}[(S_{n} - x)_+^2]}{(u - x)_+^2}.
\end{align*}
Here equality (a) holds for every $x \le u$ and inequality (b) holds because of Doob's inequality. Because $x \le u$ is arbitrary, we get
\[
\mathbb{P}\left(\max_{1 \le t \le n} S_t \ge u\right) \le \inf_{x \le u}\frac{\mathbb{E}[(S_{n} - x)_+^2]}{(u - x)_+^2},
\]
and condition~\eqref{eq:boundedness-conditions} along with Theorem 2.1 of~\citet{bentkus2006domination} (or~\citet{pinelis2006binomial}) imply that
\[
\mathbb{P}\left(\max_{1 \le t\le n}S_t \ge u\right) ~\le~ \inf_{x\le u}\,\frac{\mathbb{E}[(\sum_{i=1}^n G_i - x)_+^2]}{(u - x)_+^2}.
\]


The definition~\eqref{eq:quantile-A-B-2nd-version} of $q(\delta; n, \mathcal{A}, B)$ readily implies
\[
\mathbb{P}\left(\max_{1 \le t\le n} S_t ~\ge~ q(\delta; n, \mathcal{A}, B)\right) \le \delta.
\]
This completes the proof of~\eqref{eq:maximal-inequality}. We now prove the sharpness. Note that the condition
\[
\mathbb{P}\left(\max_{1\le t\le n}\,S_t \ge n\tilde{q}(\delta^{1/n};A, B)\right) \le \delta\quad\mbox{for all}\quad \delta\in[0, 1],
\]
is equivalent to the existence of a function $x\mapsto H(x; A, B)$ such that
\[
\mathbb{P}\left(\max_{1\le t\le n}\,S_t \ge nu\right) \le H^n(u; A, B),\quad\mbox{for all}\quad u.
\]
(The function $\delta\mapsto \tilde{q}(\delta^{1/n}; A, B)$ is the inverse of $u\mapsto H^n(u; A, B)$.) In particular, this implies that
\[
\mathbb{P}\left(S_n \ge nu\right) \le H^n(u; A, B)\quad\mbox{for all}\quad u.
\]
Now, Lemma 4.7 of~\citet{bentkus2004hoeffding} (also see Eq. (2.8) of~\citet{hoeffding1963probability}) implies that
\begin{align*}
H^n(u; A, B) ~&\ge~ \left\{\left(1 + \frac{Bu}{A^2}\right)^{-(A^2 + Bu)/(A^2 + B^2)}\left(1 - \frac{u}{B}\right)^{-(B^2 - Bu)/(B^2 + A^2)}\right\}^n\\
~&=~ \inf_{h\ge0}\,e^{-nhu}\mathbb{E}\left[e^{h\sum_{i=1}^n G_i}\right],
\end{align*}
where $G_1, \ldots, G_n$ are independent random variables constructed through~\eqref{eq:G_distribution}. Proposition 3.5 of~\citet{pinelis2009bennett} implies that
\[
\inf_{h\ge0}\,e^{-nhu}\mathbb{E}\left[e^{h\sum_{i=1}^n G_i}\right] \ge \inf_{x \le nu}\,\frac{\mathbb{E}[(\sum_{i=1}^n G_i - x)_+^2]}{(nu - x)_+^2}.
\]
Summarizing the inequalities, we conclude
\[
\mathbb{P}\left(S_n \ge nu\right) \le \inf_{x \le nu}\,\frac{\mathbb{E}[(\sum_{i=1}^n G_i - x)_+^2]}{(nu- x)_+^2} \le \inf_{h\ge0}\,\mathbb{E}\left[e^{h\sum_{i=1}^n G_i - h(nu)}\right] \le H^n(u; A, B)\quad\forall\; u.
\]
This proves that $q(\delta; n, A, B) \le n\tilde{q}(\delta^{1/n}; A, B)$ for any valid $\tilde{q}(\cdot; A, B)$.
\section{Proof of Theorem~\ref{thm:uniform-in-n}}\label{appsec:proof-of-theorem-uniform-in-n}
The proof is based on~\eqref{eq:maximal-inequality} and a union bound. It is clear that
\begin{align*}
&\mathbb{P}\left(\exists\, t\ge 1:\,\sum_{i=1}^t X_i \ge q(\delta/h(k_t); c_t, \mathcal{A}, B)\right)\\
&\qquad=~ \mathbb{P}\left(\bigcup_{k=0}^{\infty}\left\{\exists\,\lceil\eta^k\rceil\le t\le \lfloor\eta^{k+1}\rfloor:\,\sum_{i=1}^t X_i \ge q(\delta/h(k_t); c_t, \mathcal{A}, B)\right\}\right)\\
&\qquad=~ \mathbb{P}\left(\bigcup_{k=0}^{\infty}\left\{\exists\,\lceil\eta^k\rceil \le t \le \lfloor\eta^{k+1}\rfloor:\,\sum_{i=1}^t X_i \ge q(\delta/h(k); \lfloor\eta^{k+1}\rfloor, \mathcal{A}, B)\right\}\right)\\
&\qquad\le~ \sum_{k=0}^{\infty} \mathbb{P}\left(\max_{\lceil\eta^k\rceil \le t \le \lfloor\eta^{k+1}\rfloor}\sum_{i=1}^t X_i \ge q(\delta/h(k); \lfloor\eta^{k+1}\rfloor, \mathcal{A}, B)\right)\\
&\qquad\le~ \sum_{k=0}^{\infty} \frac{\delta}{h(k)} \le \delta.
\end{align*}


\section{Proof of Theorem~\ref{thm:uniform-in-n-empirical-Bentkus}}\label{appsec:proof-of-lemma-variance-estimation}
Theorem~\ref{thm:uniform-in-n} implies that
\[
\mathbb{P}\left(\exists n\ge 1:\, S_n\ge q\left(\frac{\delta_1}{h(k_n)}; c_n, A, B\right)\right) \le \delta_1.
\]
Lemma~\ref{lem:uniform-in-n-variance} (below) proves
\[
\mathbb{P}\left(\exists n\ge1:\,A \ge \widebar{A}_n(\delta_2)\right) \le \delta_2.
\]
In particular this implies that
\[
\mathbb{P}\left(\exists n\ge1:\,A \ge \min_{1\le s\le n}\widebar{A}_s(\delta_2)\right) \le \delta_2.
\]
Combining the inequalities above with a union bound (and Lemma~\ref{lem:non-decreasing-quantile}) proves the result.
\begin{lem}\label{lem:uniform-in-n-variance}
Under the assumptions of Theorem~\ref{thm:uniform-in-n-empirical-Bentkus}, we have for any $\delta\in[0, 1],$
\begin{equation}\label{eq:uniform-in-n-variance}
\mathbb{P}\left(\exists t\ge 1:\, V_{2\lfloor t/2\rfloor} - \lfloor t/2\rfloor A^2 \le -\frac{\sqrt{\lfloor c_t/2\rfloor}(B - \underline{B})A}{\sqrt{2}}\Phi^{-1}\left(1 - \frac{2\delta}{e^2h(k_t)}\right)\right) \le \delta,
\end{equation}
where $W_i = (X_{2i} - X_{2i-1})^2/2$ and $V_t := \sum_{i=1}^{\lfloor t/2\rfloor} W_i.$
\end{lem}
\begin{proof}
Fix $x \ge 0$. Note that for any $u\ge -x$,
\begin{align*}
\mathbb{P}\left(\max_{1\le t\le n}\,\{V_{2t} - tA^2\} \le -x\right)
&= \mathbb{P}\left(\max_{1\le t\le n}\,(u - \{V_{2t} - tA^2\})_+ \ge (u + x)_+\right),\\
&{\le} \frac{\mathbb{E}[(u - \{V_{2n} - 2nA^2\})_+^2]}{(u + x)_+^2}.
\end{align*}
where the last inequality follows from the fact that $\{(u - \{V_{2t} - tA^2\}\}_{t\ge1}$ is a submartingale. Therefore,
\begin{align*}
\mathbb{P}\left(\max_{1\le t\le n}\,\{V_{2t} - tA^2\} \le -x\right) &\le \inf_{u \ge -x}\,\frac{\mathbb{E}[(u - \{V_{2n} - nA^2\})_+^2]}{(u + x)_+^2}\\
&= \inf_{u\ge -x}\,\frac{\mathbb{E}[(u + nA^2 - V_{2n})_+^2]}{(u + x)_+^2}\\
&= \inf_{u\ge nA^2 - x}\,\frac{\mathbb{E}[(u - V_{2n})^2_+]}{(u - nA^2 + x)^2}.
\end{align*}
Corollary 2.7 (Eq. (2.24)) of~\citet{pinelis2016optimal} implies that
\begin{equation}\label{eq:second-moment-best}
\inf_{u\ge nA^2 - x}\,\frac{\mathbb{E}[(u - V_{2n})^2_+]}{(u - nA^2 + x)^2} \le P_2(E_{1,n} + Z\sqrt{E_{2,n}}; nA^2 - x) = P_2(E_{1,n} + Z\sqrt{E_{2,n}}; E_{1,n} - x),
\end{equation}
where $E_{j,t} = \sum_{i=1}^{\lfloor t/2\rfloor}\mathbb{E}[W_i^j]$ for $j = 1,2$ and $Z$ stands for a standard normal distribution. Inequality~\eqref{eq:second-moment-best} is \emph{not} the best inequality to use and there is a more precise version; see Theorem 2.4(I) and Corollary 2.7 of~\citet{pinelis2016optimal}. With the more precise version, the following steps will lead to a refined upper bound on $A$; we will not pursue this direction here.

It now follows from~\citet{bentkus2008extension} that
\[
P_2(E_{1,n} + Z\sqrt{E}_{2,n}; E_{1,n} - x) \le \frac{e^2}{2}\mathbb{P}\left(Z \le -\frac{x}{\sqrt{E_{2,n}}}\right).
\]
Because $X_i\in[\underline{B}, B]$ with probability 1, $W_i \le (B - \underline{B})^2/2$ and hence
\[
E_{2,n} = \mathbb{E}\sum_{i=1}^{n} \mathbb{E}[W_i^2] \le \frac{(B - \underline{B})^2}{2}\sum_{i=1}^{n} \mathbb{E}[W_i] = (B - \underline{B})^2E_{1,n}/2 = n(B - \underline{B})^2A^2/2.
\]
This implies that
\[
\mathbb{P}\left(\max_{1\le t\le n}\{V_{2t} - tA^2\} \le -x\right) \le \frac{e^2}{2}\mathbb{P}\left(Z \le -\frac{\sqrt{2}x}{\sqrt{n}(B - \underline{B})A}\right).
\]
Equating the right hand side to $\delta$ yields
\begin{equation}\label{eq:maximal-variance-case}
\mathbb{P}\left(\max_{1\le t\le n}\{V_{2t} - tA^2\} \le - \frac{\sqrt{n}(B - \underline{B})A}{\sqrt{2}}\Phi^{-1}\left(1 - \frac{2\delta}{e^2}\right)\right) \le \delta.
\end{equation}
Because of this maximal inequality, we can apply stitching and get~\eqref{eq:uniform-in-n-variance}.
Note that
\begin{align*}
&\mathbb{P}\left(\exists t\ge 1:\,V_{2\lfloor t/2\rfloor} - \lfloor t/2\rfloor A^2 \le -\frac{\sqrt{\lfloor c_t/2\rfloor}(B - \underline{B})A}{\sqrt{2}}\Phi^{-1}\left(1 - \frac{2\delta}{e^2h(k_t)}\right)\right)\\
&= \mathbb{P}\left(\exists t \ge 2:\,V_{2\lfloor t/2\rfloor} - \lfloor t/2\rfloor A^2 \le -\frac{\sqrt{\lfloor c_t/2\rfloor}(B - \underline{B})A}{\sqrt{2}}\Phi^{-1}\left(1 - \frac{2\delta}{e^2h(k_t)}\right)\right)\\
& = \mathbb{P}\left(\bigcup_{k=0}^{\infty}\left\{\exists \lceil\eta^k\rceil \le t\le \lfloor\eta^{k+1}\rfloor:\, V_{2\lfloor t/2\rfloor} - \lfloor t/2\rfloor A^2 \le -\frac{\sqrt{\lfloor c_t/2\rfloor}(B - \underline{B})A}{\sqrt{2}}\Phi^{-1}\left(1 - \frac{2\delta}{e^2h(k_t)}\right)\right\}\right)\\
& \le \sum_{k=0}^{\infty} \mathbb{P}\left(\exists\lceil\eta^k\rceil \le t\le \lfloor\eta^{k+1}\rfloor:\, V_{2\lfloor t/2\rfloor} - \lfloor t/2\rfloor A^2 \le -\frac{\sqrt{\lfloor c_t/2\rfloor}(B - \underline{B})A}{\sqrt{2}}\Phi^{-1}\left(1 - \frac{2\delta}{e^2h(k_t)}\right)\right)\\
&\le \sum_{k=0}^{\infty} \frac{\delta}{h(k)} \le \delta,
\end{align*}
where the last inequality follows from~\eqref{eq:maximal-variance-case} applied to $\{1\le t\le \lfloor c_t/2\rfloor\}$.

Inequality~\eqref{eq:uniform-in-n-variance} yields
\[
\mathbb{P}\left(tA^2 - \frac{\sqrt{\lfloor c_t/2\rfloor}(B - \underline{B})A}{\sqrt{2}}\Phi^{-1}\left(1 - \frac{2\delta}{e^2h(k_t)}\right) - V_{2t} \le 0\quad\forall\, t\ge 1 \right) \ge 1 - \delta.
\]
Inequality
\[
tA^2 - \frac{\sqrt{\lfloor c_t/2\rfloor}(B - \underline{B})A}{\sqrt{2}}\Phi^{-1}\left(1 - \frac{2\delta}{e^2h(k_t)}\right) - V_{2t} \le 0
\]
holds for $A > 0$ if and only if
\[
A \le g_{2,t} + \sqrt{g_{2,t}^2 + g_{3,t}},
\]
where
\[
g_{2,t} = \frac{\sqrt{\lfloor c_t/2\rfloor}(B - \underline{B})A}{2\sqrt{2}t}\Phi^{-1}\left(1 - \frac{2\delta}{e^2h(k_t)}\right)\quad\mbox{and}\quad g_{3,t} = \frac{V_{2\lfloor t/2\rfloor}}{\lfloor t/2\rfloor}.
\]
Hence a rewriting of~\eqref{eq:uniform-in-n-variance} is
\[
\mathbb{P}\left(A \ge g_{2,t} + \sqrt{g_{2,t}^2 + g_{3,t}}\quad\forall\; t\ge 1\right) \ge 1 - \delta.
\]
It is clear that $g_{2,t} = O(1/\sqrt{t})$ and $\mathbb{E}[V_{2\lfloor t/2\rfloor}/\lfloor t/2\rfloor] = A^2$ and hence the upper bounds above grows like $A + O(\sqrt{\log(h(k_t))/t})$.
\end{proof}
\section{Proof of Theorem~\ref{thm:empirical-Bentkus-arbitrary-mean}}\label{appsec:proof-empirical-bentkus-arbitrary-mean}
The assumption $\mathbb{P}(L \le X_i \le U) = 1$ implies that $\mathbb{P}(L - \mu \le X_i - \mu \le U - \mu) = 1$ and hence applying Theorem~\ref{thm:uniform-in-n} with $X_i - \mu$ and its upper bound $U - \mu$ yields
\begin{equation}\label{eq:upper-tail}
\mathbb{P}\left(\exists n\ge1:\, \sum_{i=1}^n (X_i - \mu) \ge q\left(\frac{\delta_1/2}{h(k_n)};\,c_n,\,A,\,U - \mu\right)\right) \le \frac{\delta_1}{2}.
\end{equation}
Similarly applying Theorem~\ref{thm:uniform-in-n} with $\mu - X_i$ and its upper bound $\mu - L$ yields
\begin{equation}\label{eq:lower-tail}
\mathbb{P}\left(\exists n\ge1:\, \sum_{i=1}^n (\mu - X_i) \ge q\left(\frac{\delta_1/2}{h(k_n)};\,c_n,\,A,\,\mu - L\right)\right) \le \frac{\delta_1}{2}.
\end{equation}
Finally Lemma~\ref{lem:uniform-in-n-variance} implies that
\begin{equation}\label{eq:variance-bound-arbitrary-mean}
\mathbb{P}\left(\exists n\ge1:\, A \ge \widebar{A}_n^*(\delta_2; U, L)\right) \le \delta_2.
\end{equation}
Now combining inequalities~\eqref{eq:upper-tail},~\eqref{eq:lower-tail}, and~\eqref{eq:variance-bound-arbitrary-mean} yields with probability $\ge 1 - \delta_1 - \delta_2$, for all $n\ge1$
\begin{align*}
-\frac{1}{n}q\left(\frac{\delta_1/2}{h(k_n)};\,c_n,\,A,\,\mu - L\right) \le \frac{S_n}{n} - \mu \le \frac{1}{n}q\left(\frac{\delta_1/2}{h(k_n)};\,c_n,\,A,\,U - \mu\right),\;\mbox{and}\; A \le \widebar{A}_n^*(\delta_2).
\end{align*}
On this event, we get by using $U - \mu \le U - L$ and $\mu - L \le U - L$,
\[
\mu^{\low}_0 \le \mu \le \mu^{\up}_0,
\]
and then recursively using $\mu_{n-1}^{\low} \le \mu \le \mu_{n-1}^{\up}$,
\[
-\frac{1}{n}q\left(\frac{\delta_1/2}{h(k_n)};\,c_n,\,\widebar{A}_n^*(\delta_2),\,\mu_{n-1}^{\up} - L\right) ~\le~ \frac{S_n}{n} - \mu ~\le~ \frac{1}{n}q\left(\frac{\delta_1/2}{h(k_n)};\,c_n,\,\widebar{A}_n^*(\delta_2),\,U - \mu_{n-1}^{\low}\right).
\]
This proves the result.


\section{Auxiliary Results}\label{appsec:auxiliary-results}
Define $M_t, t \ge 1$ as $M_t := \sum_{i=1}^t G_i,$
with
\[
\mathbb{P}\left(G_i = -A_i^2/B\right) = \frac{B^2}{A^2_i + B^2}\quad\mbox{and}\quad\mathbb{P}\left(G_i = B\right) = \frac{A^2_i}{A^2_i + B^2}.
\]
\begin{lem}\label{lem:empirical-variance-first-step}
For any $t\ge1$ and $x\in\mathbb{R}$, the map $(A_1, \ldots, A_t)\mapsto \mathbb{E}[(M_t - x)_+^2]$ is non-decreasing.
\end{lem}
\begin{proof}
Suppose we prove that for every $y\in\mathbb{R}$,
\begin{equation}\label{eq:non-increasing-bernoulli}
A_1 \mapsto \mathbb{E}[(G_1 - y)_+^2]\mbox{ is non-decreasing},
\end{equation}
then by conditioning on $G_2, \ldots, G_t$ and taking $y = x + G_2 + \cdots + G_t$, we get for $A_1 \le A_1'$
\[
\mathbb{E}[(G_1(A_1) - y)_+^2] \le \mathbb{E}[(G_1(A_1') - y)_+^2].
\]
Now taking expectations on both sides with respect to $G_2, \ldots, G_t$ implies non-decreasingness of $A_1 \mapsto \mathbb{E}[(M_t - x)_+^2]$. This implies the result.

To prove~\eqref{eq:non-increasing-bernoulli},
\[
\mathbb{E}[(G_1 - y)_+^2] = \frac{B^2}{A^2_1 + B^2}\left(-\frac{A_1^2}{B} - y\right)_+^2 + \frac{A_1^2}{A_1^2 + B^2}(B - y)_+^2.
\]
Because $A_1 \to A_1^2/B^2$ is increasing, it suffices to show $A_1^2/B^2 \mapsto \mathbb{E}[(G_1 - y)_+^2]$ is non-decreasing with respect to $A_1^2/B^2$. Set $p = A_1^2/B^2$ and define
\[
g(p) = \frac{1}{1 + p}\left(-Bp - y\right)_+^2 + \frac{p}{1 + p}(B - y)_+^2.
\]
Differentiating with respect to $p$ yields
\begin{align*}
\frac{\partial g(p)}{\partial p} &= -\frac{(-Bp - y)_+^2}{(1 + p)^2} -\frac{2B(-Bp-y)_+}{1 + p} + \frac{(B - y)_+^2}{(1 + p)^2}\\
&= \frac{- (-Bp - y)_+^2 - 2B(1 + p)(-Bp - y)_+ + (B - y)_+^2}{(1 + p)^2}.
\end{align*}
If $y \le -Bp$ then $y + Bp < 0$ and $B - y > B(1 + p) > 0$ and hence
\[
\frac{\partial g(p)}{\partial p} = \frac{-(Bp + y)^2 + 2B(1 + p)(Bp + y) + (B - y)^2}{(1 + p)^2} = \frac{B^2 + B^2p^2 + 2B^2p}{(1 + p)^2} > 0.
\]
If $-Bp < y < B$ then $y + Bp > 0$ and $B - y > 0$ and hence
\[
\frac{\partial g(p)}{\partial p} = \frac{(B - y)^2}{(1 + p)^2} > 0.
\]
If $y > B$, then $\partial g(p)/\partial p = 0$. Hence $\partial g(p)/\partial p \ge 0$ for all $p$.
This proves~\eqref{eq:non-increasing-bernoulli}.
\end{proof}
Recall the definition of $q(\delta; t, \mathcal{A}, B)$ from~\eqref{eq:quantile-A-B-2nd-version}. In the case of equal variances, that is, $A_1 = A_2 = \ldots = A$, we write $A, q(\delta; t, A, B)$ for $\mathcal{A}, q(\delta; t, \mathcal{A}, B),$ respectively. We now prove that $A\mapsto q(\delta; t_2, A, B)$ is an non-decreasing function.
\begin{lem}\label{lem:non-decreasing-quantile}
For any $t\ge1$, the function $A\mapsto q(\delta; t, A, B)$ is an non-decreasing function.
\end{lem}
\begin{proof}
Lemma~\ref{lem:empirical-variance-first-step} proves that $A\mapsto \mathbb{E}[(M_{t} - x)_+^2]$ is non-decreasing. This implies that $I(A; u)$ is also non-decreasing in $A$, where
\[
I(A; u) ~:=~ \inf_{x\le u}\,\frac{\mathbb{E}[(M_{t} - x)_+^2]}{(u - x)_+^2}.
\]
Lemma 3.1 of~\citet{bentkus2006domination} proves that $I(A; u)$ is also non-increasing in $u$.
Fix $A_1 \le A_2$. From the definition of $\delta$,
\[
I(A_1, q(\delta; t, A_1, B)) = \delta\quad\mbox{and}\quad I(A_2, q(\delta; t, A_2, B)) = \delta.
\]
Because $I(A; u)$ is non-decreasing in $A$,
\[
I(A_2; q(\delta; t, A_2, B)) = \delta = I(A_1; q(\delta; t, A_1, B)) \le I(A_2; q(\delta; t, A_1, B))
\]
Hence $I(A_2; q(\delta; t, A_2, B)) \le I(A_2; q(\delta; t, A_1, B))$ and because $I(A; u)$ is non-increasing in $u$, we conclude that $q(\delta; t, A_1, B) \le q(\delta; t, A_2, B)$. This proves the result modulo the condition $A\mapsto \mathbb{E}[(M_{t} - x)_+^2]$ is non-decreasing.
\end{proof}
\begin{lem}\label{lem:homogenity-delta-function}
For any $\delta\in[0, 1]$, $q(\delta; t, AB, B^2) = Bq(\delta; t, A, B)$.
\end{lem}
\begin{proof}
Recall that $q(\delta; t, AB, B^2)$ is defined as the solution of
\[
\inf_{x\le u}\,\frac{\mathbb{E}[(M_t' - x)^2_+]}{(u - x)_+^2} = \delta,
\]
where $M_t'$ is defined as $M_t' = \sum_{i=1}^t G_i'$ with
\begin{align*}
\mathbb{P}\left(G_i' = -(A^2B^2)/B^2\right) &= \frac{B^4}{A^2B^2 + B^4} = \frac{B^2}{A^2 + B^2}\quad\mbox{and},\\
\mathbb{P}\left(G_i' = B^2\right) &= \frac{A^2B^2}{A^2B^2 + B^4} = \frac{A^2}{A^2 + B^2}.
\end{align*}
This implies that $G_i'\overset{d}{=}BG_i$ and hence $M_t'\overset{d}{=}BM_t$. Therefore,
\[
\mathbb{E}[(M_t' - x)_+^2] = \mathbb{E}[(BM_t - x)_+^2] = B^2\mathbb{E}[(M_t - x/B)_+^2],
\]
and
\[
\inf_{x\le u}\,\frac{\mathbb{E}[(M_t' - x)_+^2]}{(u - x)_+^2} = B^2\inf_{x\le u}\,\frac{\mathbb{E}[(M_t - x/B)_+^2]}{B^2(u/B - x/B)_+^2} = \inf_{x \le u/B}\,\frac{\mathbb{E}[(M_t - x)_+^2]}{(u/B - x)_+^2}.
\]
The right hand side above equals $\delta$, when $u = Bq(\delta; t, A, B)$ because the definition of $q(\delta; t, A, B)$ implies that
\[
\inf_{x \le q(\delta; t, A, B)}\,\frac{\mathbb{E}[(M_t - x)_+^2]}{(q(\delta; t, A, B) - x)_+^2} = \delta.
\]
This completes the proof.
\end{proof}

\section{Alternative Empirical Bentkus Confidence Sequences with Estimated Variance} \label{appsec:alternative_variance_estimation}
In Section~\ref{sec:empirical-Bentkus}, we presented one actionable version of Theorem~\ref{thm:uniform-in-n}, where we used an analytical upper bound on the variance $A^2$. In this section, we present an alternative empirical Bentkus confidence sequence that requires numerical computation. In our initial experiments, we found solving for the upper bound of $A$ in this way to be unstable. Because the proof technique here is very analogues to that of the empirical Bernstein bound in~\citet[Eq. (48)-(50)]{audibert2009exploration}, we present the alternative bound below.

Define the empirical variance as
\begin{equation}\label{eq:variance-def}\textstyle
\widehat{A}_n^2 ~:=~ n^{-1}\sum_{i=1}^n (X_i - \widebar{X}_n)^2,\quad\mbox{where}\quad \widebar{X}_n = n^{-1}\sum_{i=1}^n X_i.
\end{equation}

For any $\delta_1, \delta_2\in[0,1]$, define
\begin{equation}\label{eq:variance-upper-bound}\textstyle


\widebar{A}_n := \sup\left\{a\ge0:\,\widehat{A}_n^2 ~\ge~ a^2 - \frac{B}{n}q\left(\frac{\delta_1}{h(k_n)}; c_n, a, B\right) - \frac{1}{n^2}q^2\left(\frac{\delta_2}{2h(k_n)}; c_n, a, B\right)\right\}.

\end{equation}
Lemma~\ref{lem:variance-estimation} shows that $\widebar{A}_n$ is an over-estimate of $A$ uniformly over $n$ and yields the following actionable bound.
Recall that $S_n = \sum_{i=1}^n X_i = n\widebar{X}_n$.
\begin{thm}\label{thm:uniform-in-n-empirical-variance}
If $X_1, X_2, \ldots$ are mean-zero independent random variables satisfying
$\mathrm{Var}(X_i) = A^2$ and $\mathbb{P}(|X_i| > B) = 0$ for all $i\ge1$,
then for any $\delta_1, \delta_2 \in [0, 1]$,
\[
\mathbb{P}\left(\exists n\ge1:\,\abs{S_n} \ge q\left(\frac{\delta_2}{2h(k_n)}; c_n, \widebar{A}_n^*, B\right)\quad\mbox{or}\quad A \ge \widebar{A}^*_n(\delta_1) \right) \le \delta_1 + \delta_2,
\]
where $\widebar{A}^*_n := \min_{1\le s\le n}\widebar{A}_s$. Here $k_n$ and $c_n$ are same as those defined in Theorem~\ref{thm:uniform-in-n}.
\end{thm}
This theorem is an analogue of the empirical Bernstein inequality \citet[Eq. (5)]{mnih2008empirical}. Furthermore, the upper bound $\widebar{A}_n$ on $A$ is better than that in the Bernstein version \citet[Eq. (49)-(50)]{audibert2009exploration}; see Lemma~\ref{lem:better-than-Bernstein-variance}.  
\subsection{Proof of Theorem~\ref{thm:uniform-in-n-empirical-variance} and Comparison of Standard Deviation Estimation from Other Inequalities}
\begin{lem}\label{lem:variance-estimation}
If $X_1, X_2, \ldots$ are mean-zero independent random variables satisfying
\[
\mathrm{Var}(X_i) = A^2\quad\mbox{and}\quad \mathbb{P}(|X_i| > B) = 0,\quad\mbox{for all}\quad i\ge1,
\]
then for any $\delta\in[0,1]$
\[
\mathbb{P}\left(\exists\,t\ge1:\,\widehat{A}_t^2 ~\le~ A^2 - \frac{B}{t}q\left(\frac{\delta}{h(k_t)}; c_t, A, B\right) - \frac{1}{t^2}\left|\sum_{i=1}^t X_i\right|^2\right) \le \delta.
\]
\end{lem}
\begin{proof}
Consider the random variable $X_i^2 - \mathbb{E}[X_i^2]$. These are mean zero and are bounded in absolute value by $B^2$. Further the variance can be bounded as
\[
\mathrm{Var}(X_i^2 - \mathbb{E}[X_i^2]) = \mathbb{E}[(X_i^2 - \mathbb{E}[X_i^2])^2] \le B^2\mathbb{E}[|X_i|^2] = B^2A^2.
\]
Applying Theorem~\ref{thm:uniform-in-n} with variables $X_i^2 - \mathbb{E}[X_i^2]$ implies
\[
\mathbb{P}\left(\exists t\ge1:\,\sum_{i=1}^t -(X_i^2 - \mathbb{E}[X_i^2]) \ge q\left(\frac{\delta}{h(k_t)};c_t, AB, B^2\right)\right) \le \delta.
\]
Lemma~\ref{lem:homogenity-delta-function} proves that
\[
q\left(\frac{\delta}{h(k_t)};c_t, AB, B^2\right) = Bq\left(\frac{\delta}{h(k_t)};c_t, A, B\right).
\]


Hence we get with probability at least $1 - \delta$, simultaneously for all $t\ge1$
\begin{align*}
\sum_{i=1}^t (X_i - \widebar{X}_t)^2 ~&=~ \sum_{i=1}^t X_i^2 - \frac{1}{t}\left(\sum_{i=1}^t X_i\right)^2\\
~&\ge~ \sum_{i=1}^t \mathbb{E}[X_i^2] - Bq\left(\frac{\delta}{h(k_t)}; c_t, A, B\right) - \frac{1}{t}\left|\sum_{i=1}^t X_i\right|^2.
\end{align*}
Hence for any $\delta\in[0,1]$,
\[
\mathbb{P}\left(\exists\,t\ge1:\,t\widehat{A}_t^2 \le tA^2 - Bq\left(\frac{\delta}{h(k_t)}; c_t, A, B\right) - \frac{1}{t}\left|\sum_{i=1}^n X_i\right|^2\right) \le \delta.
\]
This completes the proof.
\end{proof}

We will now prove Theorem~\ref{thm:uniform-in-n-empirical-variance}. Theorem~\ref{thm:uniform-in-n} implies that
\begin{equation}\label{eq:implication-thm-unknown-A}
\mathbb{P}\left(\exists\, t\ge 1:\,\left|\sum_{i=1}^t X_i\right| \ge q\left(\frac{\delta_2}{2h(k_t)}; c_t, \mathcal{A}, B\right)\right) \le \delta_2,
\end{equation}
Lemma~\ref{lem:variance-estimation} implies that
\[
\mathbb{P}\left(\exists\,t\ge1:\,\widehat{A}_t^2 ~\le~ \frac{t}{t-1}A^2 - \frac{B}{t-1}q\left(\frac{\delta_1}{h(k_t)}; c_t, A, B\right) - \frac{1}{t(t-1)}\left|\sum_{i=1}^t X_i\right|^2\right) \le \delta_1.
\]
Hence with probability at least $1 - \delta_1 - \delta_2$, simultaneously for all $t\ge1,$
\begin{align*}
\left|\sum_{i=1}^t X_i\right| ~&\le~ q\left(\frac{\delta_2}{2h(k_t)}; c_t, A, B\right),\\
\widehat{A}_t^2 ~&\le~ \frac{t}{t-1}A^2 - \frac{B}{t-1}q\left(\frac{\delta_1}{h(k_t)}; c_t, A, B\right) - \frac{1}{t(t-1)}\left|\sum_{i=1}^t X_i\right|^2
\end{align*}
On this event, $A \le \widebar{A}_t$ simultaneously for all $t\ge1$ which in turn implies that $A\le \min_{1\le s\le t}\widebar{A}_s$ also holds simultaneously for all $t\ge1$. Substituting this in~\eqref{eq:implication-thm-unknown-A} (along with Lemma~\ref{lem:non-decreasing-quantile}) implies the result.
\begin{lem}\label{lem:better-than-Bernstein-variance}
Suppose $\delta\mapsto\tilde{q}(\delta^{1/n}; A, B)$ is a function such that
\begin{equation}\label{eq:power-quantile-bound}
\mathbb{P}\left(\max_{1\le t\le n}\,S_t \ge n\tilde{q}(\delta^{1/n}; A, B)\right) \le \delta,
\end{equation}
for all $\delta\in[0, 1]$ and independent random variables $X_1, \ldots, X_n$ satisfying~\eqref{eq:boundedness-conditions}. Define the (over)-estimator of $A$ as
\[
\tilde{A}_t ~:=~ \sup\left\{a\ge0:\,\widehat{A}_t^2 \ge a^2 - \frac{Bc_t}{t}\tilde{q}\left((\delta/(3h(k_t)))^{1/c_t}; a, B\right) - \frac{c_t^2}{t^2}\tilde{q}^2\left((\delta/(3h(k_t)))^{1/c_t}; a, B\right)\right\}.
\]
Then $\widebar{A}_n \le \tilde{A}_n.$
\end{lem}
\begin{proof}
We have proved in Appendix~\ref{appsec:proof-of-theorem-initial-maximal-ineq} that~\eqref{eq:power-quantile-bound} implies
\[
q\left(\delta; n, a, B\right) \le n\tilde{q}\left(\delta^{1/n}; a, B\right),
\]
for all $n, a,$ and $B$. Hence if $a$ satisfies
\[
\widehat{A}_t^2 \ge a^2 - \frac{B}{t}q\left(\frac{\delta}{3h(k_t)}; c_t, a, B\right) - \frac{1}{t^2}q^2\left(\frac{\delta}{3h(k_t)}; c_t, a, B\right),
\]
then
\[
\widehat{A}_n^2 \ge a^2 - \frac{Bc_t}{t}\tilde{q}\left((\delta/(3h(k_t)))^{1/c_t}; a, B\right) - \frac{c_t^2}{t^2}\tilde{q}^2\left((\delta/(3h(k_t)))^{1/c_t}; a, B\right),
\]
which implies the result.
\end{proof}
{"config": "arxiv", "file": "2006.05022/06-appendix.tex"}