Constructing nonasymptotic confidence intervals (CIs) for the mean of a univariate distribution from independent and identically distributed () observations is a fundamental task in  statistics. For bounded observations, a classical nonparametric approach proceeds by inverting standard concentration bounds, such as Hoeffding's or Bernstein's inequalities. Recently, an alternative betting-based approach for defining CIs and their time-uniform variants called confidence sequences  (CSs), has been shown to be empirically superior to the classical methods. In this paper, we provide theoretical justification for this improved empirical performance of betting CIs and CSs.

Our main contributions are as follows: (i) We first compare CIs using the values of their first-order asymptotic widths (scaled by $\sqrt{n}$), and show that  the  betting CI of Waudby-Smith and Ramdas, 2023  has a smaller limiting width than  existing empirical Bernstein (EB)-CIs. (ii) Next, we establish two lower bounds  that characterize the minimum width achievable by any method for constructing CIs/CSs in terms of certain inverse information projections. (iii) Finally, we show that the betting CI and CS match the fundamental limits, modulo an additive logarithmic term and a multiplicative constant. Overall these results imply that  the betting CI (and CS) admit stronger theoretical guarantees than the existing state-of-the-art EB-CI (and CS); both in the asymptotic and finite-sample regimes.

§ INTRODUCTION

This paper studies the fundamental limits of the width of nonasymptotic confidence intervals (CIs) and confidence sequences (CSs) for the mean $\mu$ of a distribution $P^*$ on $\mc{X}=[0,1]$ from an sample $X_1, X_2, \ldots, X_n$ drawn according to $P^*$.  We define these below, but note first that all the methods analyzed in this paper are fully nonparametric, and make no assumptions whatsoever about knowledge of any aspect of the distribution $P^*$ except that it is bounded on $[0,1]$. Throughout this paper, we use $P^*$ to denote the  distribution generating the observations $(X_t)_{t \geq 1}$, and use $P$ when referring to an arbitrary probability distribution.

Formally, a level-$(1-\alpha)$ CI for $\mu$ is a $\sigma(X_1, \ldots, X_n)$-measurable subset ${C}_n$ of the  domain $\mc{X}$ that satisfies the coverage guarantee $\mathbb{P}\lp \mu \in {C}_n \rp \geq 1-\alpha$. CIs can be constructed for datasets of fixed  (and non-random) size, and cannot be used for tasks that involve processing streams of observations of possibly data-dependent random size. In such cases, a time-uniform variant of CIs, called confidence sequences (CSs), are the appropriate tool for inference. Given $X_1, X_2, \ldots \simiid P^*$, a level-$(1-\alpha)$ CS for the mean $\mu$ is a collection of sets $\{C_t: t \geq 1\}$ such that $C_t$ is $\sigma(X_1, \ldots, X_t)$ measurable for all $t \geq 1$, and  these sets satisfy the following uniform coverage guarantee: $\mathbb{P}\lp \forall t \in \mathbb{N}: \mu \in C_t \rp \geq 1-\alpha$.

The size of a CI,  assuming it satisfies the $(1-\alpha)$ coverage guarantee,  is a natural metric for evaluating its quality. Since we are concerned with observations on the unit interval, a good measure of the `size' is the width of the CI, which is the length of the smallest interval containing the CI. Formally, the width of ${C}_n$ is

\begin{align}
|{C}_n| = \inf \{ b-a: {C}_n \subset [a,b]\}.
\end{align}

Note that the width of a CI is a possibly random quantity, and most sensible strategies for constructing CIs usually ensure that it converges to $0$ almost surely. In fact, for our setting of bounded univariate observations,  the width typically converges to $0$ at a $\mc{O}\lp 1/\sqrt{n} \rp$ rate. Another desirable property of CIs, in addition to the order optimal convergence rate, is variance adaptivity. That is, we want the leading constant (in the width of the CI) to be proportional to the standard deviation of the distribution. This means, for example, that the width of the CI for observations drawn from a $\texttt{Bernoulli}(0.99)$ distribution will be significantly tighter than that for a $\texttt{Bernoulli}(0.5)$ distribution (for the same value of $n$) for variance adaptive CIs.

A standard approach for constructing non-asymptotic CIs proceeds by inverting finite-sample concentration inequalities. For bounded random variables, the earliest such result was derived by Hoeffding, 1963, who constructed a CI with the order-optimal width (i.e., decaying at $1/\sqrt{n}$ rate). However, the resulting CI, referred to as Hoeffding's CI, is not variance adaptive, as it uses the worst case variance of $1/4$ for random variables supported on the unit interval. This was addressed by CIs based on the inequalities of Bennett, 1962 and Bernstein, 1927, but these methods require  knowledge of the variance (or at least a good upper bound), which limits their applicability. This has led to the construction of so-called empirical Bernstein (EB) inequalities, that manage to replace the true (unknown) variance with their empirical estimates [Audibert et al., 2009, Maurer and Pontil, 2009]. Additionally, time-uniform analogs (i.e., confidence sequences) of all these CIs have been recently derived [Howard et al., 2021].

In a recent discussion paper at the Royal Statistical Society, Waudby-Smith and Ramdas, 2023 developed a new approach for constructing CIs and CSs for the mean of bounded random variables (both with and without replacement, the latter being a setting we briefly return to at the end of this paper). They consider a family of hypothesis tests, each testing whether the true mean $\mu$ equals $m$, for all values of $m \in [0,1]$. The CI is then defined by inversion (as is standard): it is the set of the values of $m$, for which the corresponding null hypothesis has not yet been rejected. The key novelty is the type of test that is employed, both for the CI and the CS, which involves “testing by betting”. In short, one converts the hypothesis test into a game, such that if the null is true, no bettor can make money in that game, but if the null is false, a smart bettor can grow their wealth exponentially. We introduce the details of this strategy in <Ref>. Using this strategy, the authors constructed two new CIs and CSs: a closed-form “predictable plug-in” empirical Bernstein CI/CS (that they refer to as CI/CS), as well as a non-closed-form (but easy to numerically solve) betting CIs/CSs.

In a thorough empirical evaluation spanning a variety of competing methods derived over the last 60 years, these new CIs and CSs were shown to significantly outperform all existing methods. However, while some intuition was provided by the authors, the theoretical results of Waudby-Smith and Ramdas, 2023 do not explain this large improvement. We were also not able to find any information-theoretic lower bounds on the best possible width achievable by any CI/CS. The main motivation of our current paper is to close the gap between theory and practice for this basic and well-studied problem.

Comparison of the widths of different level-$(1-\alpha)$ CIs of the mean of Bernoulli observations with means $0.50$ (left) and $0.95$ (right), with $\alpha=0.005$. In both cases,  the betting CI of Waudby-Smith and Ramdas, 2023 dominates other methods, while the plot on the right further differentiates the variance-adaptive CIs from Hoeffding CI, that fails to exploit the low-variance observations. In the right plot, the CIs can be clipped to lie in $[0,1]$ — we have not done that for higher visual clarity.

Overview of results. Our results provide theoretical justification of the benefits of the betting CI over competing methods. Despite the CIs being nonasymptotically valid, it turns out to be quite insightful to first compare their asymptotic behavior. To do this, we use the notion of first-order limiting widths of CIs, denoted by $\gamma_1$. In particular, for any level-$(1-\alpha)$ CI, whose width is a possibly random quantity $2w_n$, we define its first-order limiting (half-)width as

\begin{align}
\gamma_1 =  \limsup_{n \to \infty} \sqrt{n}\, w_n.  \label{eq:first-order}
\end{align}

For all the CIs we consider in this paper, $\gamma_1$ is  either a constant, or bounded above by a constant almost surely. We refer to $\gamma_1$ as the `first-order' limiting (half-)width, because it is solely determined by the dominant $\mc{O}(1/\sqrt{n})$  term in the width. This already leads to a separation amongst the CIs: they do not all have the same first order limiting width. For those that do,  we can also similarly analyze the `higher-order' limiting widths the $\mc{O}(1/n)$,  $\mc{O}(1/n^{3/2})$, etc. terms; this is not the goal of the paper but we return to this briefly in <Ref>. Using $\gamma_1$, we can define a total  order over the space of CIs:
for any two level-$(1-\alpha)$ CIs, denoted by $\text{CI}^{(a)}$ and $\text{CI}^{(b)}$, we have

\begin{align}
\text{CI}^{(a)} \leq_{\gamma} \text{CI}^{(b)} \quad \Longleftrightarrow \quad
\gamma_1^{(a)} \stackrel{a.s.}{\leq} \gamma_1^{(b)}.  \label{eq:CI-ordering}
\end{align}

In words, $\text{CI}^{(a)}$ is smaller (hence better) than $\text{CI}^{(b)}$, if the first-order limiting width $\gamma_1^{(a)}$ is smaller than $\gamma_1^{(b)}$. We use a strict inequality $<_\gamma$, and equality $=_{\gamma}$ in the natural way. In our first main result, <Ref> in <Ref>,  we use this ordering to compare  betting CIs with some popular existing CIs (namely Hoeffding, Bernstein, , and CIs, formally defined in <Ref>). More specifically, we show that the betting CI, with a suitable choice of bets, is a strict improvement over Hoeffding and CIs, and its limiting width is at least as good as that of the Bernstein CI, without the knowledge of the variance of the distribution (needed to construct Bernstein CI).  To summarize, this result implies that

\begin{align}
\text{betting CI } \leq_{\gamma} \prpieb \text{ CI}  =_{\gamma} \text{Bernstein CI} <_{\gamma} \mpeb \text{ CI} <_{\gamma}^* \text{ Hoeffding CI}.
\end{align}

The asterisk in the last inequality is to indicate that the strict inequality is valid when $\sigma < (1/2) \sqrt{\log(2/\alpha)/\log(4/\alpha)}$. For example, with $\alpha=0.05$, this condition reduces to $\sigma < 0.458$ (recall that $\sigma$ is upper bounded by $0.5$).

The previous result establishes the benefits of betting CI in an asymptotic sense, by showing that $\gammabet$ compares favorably with the limiting first-order widths of competing CIs. Our next set of results, presented in <Ref>, demonstrate the near-optimality of the betting CI in a non-asymptotic regime.

We first establish a fundamental, method-agnostic, lower bound on the width achievable by any valid level-$(1-\alpha)$  CI in <Ref>, in terms of certain inverse information projection terms. Such nonasymptotic width (or, more generally, volume) lower bounds appear to be quite rare in the nonparametric estimation literature, and we have not been able to find references for other problem classes.

We then show that the betting CI width nearly matches the lower bound in <Ref>. To elaborate,  for  $P^* \in \mc{P}([0,1])$ and an $m \in [0,1]$, define the information projection $\klinf(P^*, m)$ (resp. $\klinfminus(P^*, m))$ as the smallest value of $\dkl(P^*, P)$  over all distributions $P \in \mc{P}([0,1])$ with mean at least $m$ (resp. at most $m$). Accordingly, the inverse information projection, $\klinf(P^*, \cdot)^{-1}(x)$, is the smallest $m$ such that $\klinf(P^*, m)$ is at least $x$ (the inverse of $\klinfminus$ is defined similarly). The information projection terms $\klinf$ and $\klinfminus$, formally introduced in <Ref>, have been used in the multi-armed bandits literature to characterize the optimal instance-dependent cumulative regret [Lai and Robbins, 1985, Honda and Takemura, 2010]. Our results provide an analogous instance-dependent characterization of the width of CIs using their inverse. In particular, if $2w_n$ denotes the width of any level-$(1-\alpha)$ CI, and $2\widthbet$ denotes the width of the betting CI, then we have the following, for $a(n, \alpha) \defined \log\lp (1-\alpha)^{1-\alpha} \alpha^{2\alpha -1}\rp/n$:

\begin{align}
&w_n \geq \frac{1}{2} \max \lbr \klinf(P^*, \cdot)^{-1}\lp a(n,\alpha) \rp - \mu, \; \mu -  \klinfminus(P^*, \cdot)^{-1}\lp a(n, \alpha)\rp \rbr,  \\
\text{and} \quad
& \widthbet \leq \max \lbr \klinf(P^*, \cdot)^{-1}\lp b(n, \alpha) \rp - \mu, \; \mu - \klinfminus(P^*, \cdot)^{-1}\lp b(n, \alpha) \rp \rbr, \\
\quad \text{with} \quad & a(n, \alpha) = \frac{ \log \lp (1-\alpha)^{1-\alpha} \alpha^{2\alpha -1} \rp}{n}, \quad \text{and} \quad b(n, \alpha) = \frac{\log(1/\alpha) + \mc{O}(\log n)}{n}.
\end{align}

Since $a(n, \alpha) \approx \log(1/\alpha)/n$ as $\alpha \to 0$, this proves that the  betting CI  nearly matches the fundamental performance limit, but for two differences:  an extra leading multiplicative factor of $2$, and an additional $\mc{O}(\log(n)/n)$ term in the argument of the inverse information projection. The main takeaway form these results is that (i) the optimal instance-dependent width of any CI is precisely characterized by an instance-dependent `complexity parameter' based on the inverse of $\klinf$ and $\klinfminus$, and (ii) the width of the betting CI  also depends on nearly the same complexity term.  To the best of our knowledge, none of the existing CIs admit such upper bounds on their widths.

Having analyzed the performance of betting CI, we then establish similar guarantees for the betting CS in <Ref>. Due to their time-uniform coverage guarantees, it is  not reasonable to order CSs by comparing their widths at some specific value of $n$. To address this, we introduce a notion of effective width, that is more suitable for comparing CSs. More specifically, we define the effective width of a CS after $n$ observations, as the smallest $w>0$ for which the expected number of observations needed for the width of the CS to go below $2w$, is at most $n$.
Using this definition, we first establish a general lower bound on the effective width of any valid level-$(1-\alpha)$ CS in <Ref> in <Ref>. This lower bound also depends on an appropriate inverse information projection term, similar to the corresponding bound for CIs discussed above. We then obtain a nearly matching upper bound (modulo the same constant multiplicative factor, and an additive logarithmic term in the argument of the inverse information projection) on the effective width of the betting CS in <Ref>.

Overall, our results provide rigorous justification for the empirically observed supremacy of the betting CI/CSs of Waudby-Smith and Ramdas, 2023 over previously state-of-the-art methods, and also opens us several interesting directions for future work.

Outline of the paper. We present the background information about some popular existing CIs in <Ref>, and then formally describe the betting approach to constructing CIs in <Ref>. The next three sections contain the details of the main technical results. In particular, in <Ref> we show that the betting-CI of Waudby-Smith and Ramdas, 2023 is at least as good as the  best existing EB-CI in terms of the first-order limiting width defined in (<ref>). Next, in <Ref>, we show that the betting CI has nearly-optimal width even in the finite sample setting, by establishing a method-agnostic lower bound, and then showing that the width of the betting CI is close to the lower bound. Finally, in <Ref>, we show that the betting CS also satisfies a similar notion of near-optimality. We discuss some extensions of our results in <Ref>, and conclude the paper with some interesting questions for future work in <Ref>.

§ PRELIMINARIES

We begin by describing some popular existing CIs in <Ref>, and then present the betting based approach for CI/CS constructing <Ref>. Finally, we end with a discussion on a class of powerful betting strategies used for constructing CI/CS in <Ref>.

§.§ CIs/CSs based on concentration inequalities

A standard approach for constructing CIs is by inverting high probability, non-asymptotic, concentration inequalities for the empirical mean based on observations. Here, we recall three of the most popular CIs constructed using exponential concentration inequalities for bounded observations.

Hoeffding CI. Hoeffding, 1963 derived one of the earliest concentration inequalities for the mean of bounded random variables. The main idea is to use the general Cramer-Chernoff method, with an appropriate exponential upper bound on the moment generating function of bounded random variables.
On inverting the resulting concentration inequality, we get the following closed form CI:

\begin{align}
\label{eq:hoeffding-ci}
C_n^{(H)} = \lb \muhat_n \pm w_n^{(H)}\rb \defined \lb \muhat_n - w_n^{(H)}, \, \muhat_n + w_n^{(H)} \rb, \quad \text{with } \muhat_n = \frac{1}{n} \sum_{i=1}^n X_i, \quad \text{and } w_n^{(H)}= \sqrt{\frac{\log(2/\alpha)}{2n}}.
\end{align}

Note that the width of Hoeffding CI converges to zero at an order-optimal $1/\sqrt{n}$ rate. Despite this order-optimality, it can be quite loose for random variables with low variance; in fact, the Hoeffding CI can be interpreted as assuming of a worst case variance of $1/4$.

Bernstein CI.  The aforementioned weakness can be addressed by constructing a CI based on a variance-aware concentration inequality, such as Bernstein exponential concentration inequality <cit.>. In particular, inverting this concentration inequality results in the following CI:

\begin{align}
\label{eq:bernstein-ci}
C_n^{(B)} = \lb \muhat_n \pm  w_n^{(B)} \rb, \quad \text{where } w_n^{(B)} = \sigma \sqrt{ \frac{ 2 \log(2/\alpha)}{n}} + \frac{\log(2/\alpha)}{3n}.
\end{align}

Since the maximum value of $\sigma$ of a random variable supported on $[0,1]$ is $1/2$,  the dominant $\mc{O}(1/\sqrt{n})$ term reduces to the Hoeffding CI width for this value of $\sigma$. However for problem instances with $\sigma \ll 1/2$, the above CI is a significant improvement over Hoeffding's. One drawback of Bernstein CI is that constructing it requires the additional information of the variance $\sigma$, or at least a good upper bound on it. In our setup, we do not assume that such additional side information is available.

Maurer & Pontil's Empirical Bernstein (MP-EB) CI.  Maurer and Pontil, 2009 addressed the above issue, by deriving a fully data-driven empirical Bernstein CI:

\begin{align}
\label{eq:emp-bern-ci-maurer}
C_n^{(\mpeb)} = \lb \muhat_n \pm  w_n^{(\mpeb)} \rb, \quad \text{where } w_n^{(\mpeb)} = \sigmahat_n\sqrt{\frac{2 \log(4/\alpha)}{n}} + \frac{7 \log(4/\alpha)}{3(n-1)}, \; \text{and} \; \sigmahat_n^2 = \frac{1}{n} \sum_{i=1}^n (X_i - \muhat_n)^2.
\end{align}

The above CI satisfies many qualities of a good CI: it is variance-adaptive, has  order-optimal dependence on $n$, and it is fully data-driven, not requiring any prior information about the variance. However, it can still be significantly improved in theory and practice.

Predictable Plugin-EB () CI. Recently, Waudby-Smith and Ramdas, 2023 obtained an improved empirical Bernstein CI using a martingale technique that avoids a union bound, thus achieving a better dependence on $\alpha$.
Define $\muhat_0:=0$, $V_0:=1/4$, and

\begin{align}
\psi_E(\lambda) \defined \frac{-\log(1-\lambda) - \lambda}{4}, \quad \muhat_{t} = \frac{1}{t}\sum_{i=1}^{t}X_i,\quad   tV_t =  \frac{1}{4} + \sum_{i=1}^t (X_i - \muhat_{i-1})^2,
\quad
\lambda_{t,n} = \sqrt{\frac{2 \log(2/\alpha)}{nV_{t-1}}}.
\label{eq:eb-ci-lambda}
\end{align}

Then, the level-$(1-\alpha)$ CI after $n$ observations is defined as

\begin{align}
&C_n^{(\prpieb)}  = \lb \mutilde_n \pm w_n^{(\prpieb)}\rb, \label{eq:prpieb-def} \\
\text{where} \quad  & \mutilde_n \defined \frac{\sum_{t=1}^n \lambda_{t,n}X_i}{\sum_{t=1}^n \lambda_{t,n}}, \quad \text{and} \quad w_{n}^{(\prpieb)} = \frac{\log(2/\alpha) + 4\sum_{t=1}^n \psi_{E}(\lambda_{t,n})(X_i - \muhat_{i-1})^2}{\sum_{t=1}^n \lambda_{t,n}}.  \label{eq:prpieb-width}
\end{align}

The first-order limiting width, introduced in (<ref>), for the three classical CIs introduced above (Hoeffding, Bernstein, ) can be easily calculated:

\begin{align}
&\gamma_1^{(H)} = \sqrt{\frac{\log(2/\alpha)}{2}}, \quad
\gamma_1^{(B)} = \sigma \sqrt{2\log(2/\alpha)}, \quad \text{and} \quad
\gamma_1^{(\mpeb)} = \sigma\sqrt{2\log(4/\alpha)}. %
\end{align}

These values succinctly characterize the relative strengths of these three CIs:

* Hoeffding CI achieves the order-optimal $1/\sqrt{n}$ dependence, but is not variance adaptive.

* Bernstein CI obtains a strictly smaller limiting width than Hoeffding CI for all values of $\sigma$ (since $\sigma$ can be at most $1/2$), but requires the additional information about the variance $\sigma^2$.

*  CI relaxes the requirement of knowing the variance, at the price of a larger $\alpha$-dependent term, which results from the EB-CI spending some of the $\alpha$ budget on estimating the variance.

Waudby-Smith and Ramdas, 2023 showed that the  CI has a limiting width equal to $\gamma_1^{(B)}$, thus closing the gap that exists between and Bernstein CI.
This improvement is also witnessed in practice, with being significantly tighter than in simulations across a wide range of examples.
In <Ref> of this paper, we prove that the limiting width of the betting CI is no larger than $\gamma_1^{(B)}$, suggesting the possibility that the betting CI might admit stronger performance guarantees than existing CIs. This motivates our subsequent investigation of the width of the betting CI (and CS) in the non-asymptotic regime, in which we characterize the fundamental limits of performance of any CI/CS, and then show that the betting CI/CS nearly matches this limit.

We end this section by noting that there also exist time-uniform analogs of the above confidence intervals (i.e., CSs), and while we refer the reader to Howard et al., 2021, Waudby-Smith and Ramdas, 2023 for the details, we will analyze the CS widths as well later in this paper.

§.§ The betting approach for CI construction

Waudby-Smith and Ramdas, 2023 proposed a general method for constructing CIs/CSs for the mean of bounded random variables, by inverting the following continuum of hypothesis testing problems:

\begin{align}
H_{0,m}: \mu = m, \quad \text{versus} \quad H_{1,m}: \mu \neq m, \quad \text{for all } m \in [0,1].
\end{align}

Then the CI (resp. CS) after $n$ observations is defined as those values of $m$ for which $H_{0,m}$ has not yet been rejected by the corresponding hypothesis test (resp. sequential hypothesis test). For simplicity, we discuss the construction of betting CIs here, and present the details of the betting CS at the beginning of <Ref>.

To design each  test required for the betting CI, Waudby-Smith and Ramdas, 2023 build upon the principle of testing-by-betting, recently popularized by Shafer, 2021. This principle states that the evidence against $H_{0,m}$ can be precisely quantified by the wealth of a fictitious gambler who sequentially bets against the null in a fair (under the null) repeated game of chance, starting with an initial wealth of $1$ and never betting more money than they have. Denoting the wealth after $n$ rounds as $W_n(m)$ (with $W_0(m)=1$), the the fairness of the game under the null implies that $\mathbb{E}[W_n(\mu)] \leq 1$.
Markov's inequality then implies that one can reject $H_{0,m}$ at level $\alpha$ if $W_n(m)$ exceeds $1/\alpha$. Inverting these tests defines the CI at time $n$ as

\begin{align}
C_n = \{m \in [0,1]: W_n(m) < 1/\alpha\}, \quad \text{with} \quad W_n(m) \defined \prod_{i=1}^n f_i(X_i, \lambda_i(m), m),  \label{eq:general-betting-CI}
\end{align}

where $f_i$ is a predictable (i.e., $\mc{F}_{i-1}$-measurable), nonnegative `payoff' function satisfying $\mathbb{E}[f_i(X, \lambda, \mu) \mid \mc{F}_{i-1}] \leq 1$ for all feasible values of  of $\lambda$, and $\lambda_i(m)$ is the  predictable `bet', denoting the fraction of the wealth, $W_{i-1}(m)$, that is put at stake by the bettor in round $i$.
This approach thus  transforms the task of constructing a CI/CS into that of designing wealth processes (or equivalently, payoff functions and betting strategies) that grow quickly for $H_{0,m}$ with $m \neq \mu$.

Note that the Hoeffding and Bernstein CIs, as well as , can be written as special cases of the general betting framework introduced above. For example, Hoeffding CI can be defined as the intersection of two level-$(1-\alpha/2)$ betting CIs, $C_n^0$ and $C_n^1$, that use the same bets ($i.e., \lambda_i(m)$, for all $i, m$), but different payoff functions $f_i^0$ and $f_i^1$ for $i \in [n]$, defined as

\begin{align}
f_i^j(x, \lambda, m) = \exp ( (-1)^j\lambda(x-m) - \lambda^2/8), \; \text{for } j \in \{0, 1\}, \quad \text{and} \quad \lambda_i(m) = \sqrt{\frac{8 \log(2/\alpha)}{n}},
\end{align}

for all $t \in [n]$ and $m \in [0,1]$.
Similarly, we can recover CI using

\begin{align}
f_i^j(x, \lambda, m) = \exp \lp (-1)^j \lambda (x-m) - \psi_E(\lambda)(x- \muhat_{i-1})^2\rp, \quad \text{and} \quad \lambda_i(m) = \lambda_{i,n} \defined \sqrt{\frac{2 \log(2/\alpha)}{n V_{i-1}}},
\end{align}

for all $m \in [0,1]$.
The bets $\{\lambda_i(m): i \in [n], \; m \in [0,1]\}$ in both examples are optimized for a fixed value of $n$, and hence we refer to them as CIs. We briefly discuss the constructing of betting CSs in <Ref>, at the beginning of <Ref>.

While the CI has the benefit of a closed form expression, it does not utilize the full power of the general framework, as it can be interpreted as playing a sub-fair betting game at the (unknown) true mean $\mu$. Mathematically, this means that the wealth process $\{W_n(\mu): n \geq 1\}$ is a nonnegative super-martingale. Waudby-Smith and Ramdas, 2023 also developed an alternative, and more powerful, approach that relies on nonnegative martingales, that results in a less conservative CI in practice. However, the drawback of the resulting CI that we refer to as betting CI is that the intervals do not have a closed-form expression, and have to be obtained numerically. We recall this construction next.

Given $X_1, X_2, \ldots, X_n$ drawn from a distribution $P^*$ supported on $[0,1]$ with mean $\mu$, consider an instance of the general CI of (<ref>), with

\begin{align}
f_i(x, \lambda, m) = 1 + \lambda(x-m), \quad
\text{and} \quad \lambda_{t}(m) \in \lb \frac{-1}{1-m}, \frac{1}{m} \rb, \quad \text{for all} \;m \in [0,1].
\end{align}

Then, we define the betting CI after $n$ observations as $C_n^{(bet)} = \{m \in [0, 1]: W_n(m) < 1/\alpha\}$.
Recall that, for all $m \in [0,1]$ and $t \in [n]$,  the bet $\lambda_t(m)$ is $\mc{F}_{t-1}$ measurable, but can use the knowledge of the horizon $n$.

The key component influencing the practical and theoretical performance of the betting CI is the strategy used for choosing the bets or the betting fractions,  $\{\lambda_t: t\geq 1, \; m \in[0,1]\}$.  Waudby-Smith and Ramdas, 2023 proposed and empirically compared various betting strategies that aim to optimize, either exactly or approximately, the growth rate of the wealth process for $m \neq \mu$. We formally describe this optimality criterion, and  recall a powerful betting strategy next.

§.§ Log-optimal betting and regret

The width of the CI (or, as we return to later, CS) constructed by the betting method depends strongly on the choice of the betting strategy. Good betting strategies ensure that the wealth for $m \neq \mu$ grows rapidly, which in turn leads to CIs or CSs whose width shrinks fast.
We begin by introducing the $\log$-optimal betting strategy [Kelly, 1956] that selects $\lambda_t(m) = \lambda^*(m)$ for all $t \geq 1$,  and $m \in [0,1]$, where $\lambda^*(m)$ is defined as

\begin{align}
\lambda^*(m) \in \argmax_{\lambda \in \lb - \frac{1}{1-m}, \frac{1}{m}\rb } \; \mathbb{E}_{X \sim P^*} \lb \log \lp 1 + \lambda(X-m) \rp \rb.  \label{eq:log-optimal}
\end{align}

The above constraints on $\lambda$ ensure that the quantity inside the logarithm is nonnegative.
Clearly this strategy cannot be employed in practice, as the distribution $P^*$ is unknown. Instead, practical betting CIs/CSs proceed by choosing a sequence of predictable bets, $\{\lambda_t(m): t \geq 1, m \in [0,1]\}$, which incrementally approximate the $\log$-optimal bets in a data-driven manner. The quality of a betting strategy can be measured by its  regret; that is, the cumulative suboptimality with respect to the optimal betting strategy:

\begin{align}
\mc{R}_n(m) =  \sum_{t=1}^n \log\lp 1 + \lambda^*(m)(X_t-m) \rp - \sum_{t=1}^n \log\lp 1 + \lambda_t(m)(X_t-m) \rp; \quad m \in [0,1].  \label{def:regret-1}
\end{align}

While the term $\mc{R}_n(m)$ is a random quantity (as a function of $X_1^n$), there exist strategies (called no-regret strategies) that can guarantee uniformly decaying average regret over all possible realizations of $X_1^n$.
Formally, we say a betting strategy is no-regret if for every $n \geq 1$ and $m \in [0,1]$, there exists a deterministic sequence, $\{r_{n}(m): n \geq 1\}$ with $r_n(m)/n \to 0$ for all $m \in [0,1]$, satisfying

\begin{align}
\mc{R}_n(m) \leq r_n(m) \quad \text{for all } n \in \mathbb{N}.
\end{align}

Many strategies, such as the mixture method or the online Newton step strategy [Hazan et al., 2007, Cutkosky and Orabona, 2018], admit a logarithmic regret bound for all $n$ and $m$. That is, for these strategies, we have $r_n(m) = c_m \log(n)$ for some constant $c_m$ depending on $m$. In this paper, we will present our results assuming that the bets are chosen via the following version of the mixture method <cit.>. Note that this method is also a special instance of the universal portfolio algorithm of Cover, 1991.

This betting strategy sets $\lambda_1(m)=0$, for all $m \in [0,1]$, and sets $\lambda_t(m)$ to be the weighted average of all possible $\lambda$ values, with the weight assigned to a candidate value $\lambda$ being proportional to the hypothetical wealth (denoted by $W_{t-1}^{\lambda}(m)$) if the bettor chose $\lambda_i(m) = \lambda$ for all $1 \leq i\leq t-1$. More formally, we have

\begin{align}
\lambda_t(m) = \frac{\int_{-1/(1-m)}^{1/m} \lambda\, W_{t-1}^{\lambda}(m) d\lambda }{\int_{-1/(1-m)}^{1/m} W_{t-1}^{\lambda}(m) d\lambda}, \quad \text{with} \quad
W_{t-1}^{\lambda}(m) \defined \prod_{i=1}^{t-1} \lp 1 + \lambda(X_i-m) \rp.
\end{align}

For this method, we have a  regret bound $\mc{R}_n(m) \leq \log(n) + 2$ for all $m \in [0,1]$, and this can be further upper bounded by $c \log(n)$, for a constant $c\approx 1.8$ for all values of $n \geq 13$.

We will analyze the performance of the betting CI and CS, constructed using the above betting strategy, in the finite sample regime in <Ref> and <Ref> respectively.

§ LIMITING WIDTH OF THE BETTING CI

We now present the first main result of this paper, which says that for the same choice of bets, the limiting width of the betting CI is upper bounded by that of the CI. The  limiting width of CI was shown by Waudby-Smith and Ramdas, 2023 to be equal to that of the Bernstein CI (we recall this in <Ref>). Thus our result shows that the betting CI is also at least as good as as the Bernstein CI in terms of the order induced by the first-order limiting width.

The  CI of (<ref>) is a valid level-$(1-\alpha)$ CI for the mean $\mu$ of $P^*$, and it has the following first-order limiting width:

\begin{align}
\gamma_1^{(\prpieb)} \eqas \sigma \sqrt{2 \log(2/\alpha)}.
\end{align}

Waudby-Smith and Ramdas, 2023 proved that for certain betting strategies, the width of the betting CI converges to $0$ at the order-optimal $1/\sqrt{n}$ rate. However, they did not establish whether or not the width of the betting CI is variance adaptive, and how it compares with their CI. Nevertheless, through extensive empirical evaluation, they showed that the betting CI is variance-adaptive, and is often much tighter than all the competitors in practice.
Our next result takes the first step to address this theory-practice gap, by showing that the limiting  width of the betting CI is upper bounded by that of the CI (and hence, also the usual Bernstein CI). This establishes that the width of the betting CI is variance-adaptive, and furthermore, it is also asymptotically tighter than (or at least, no worse than) the improved CI. This result also  motivates our exploration of the non-asymptotic behavior of betting CIs/CSs  in the subsequent sections of this paper.

The betting CI we analyze in this section is constructed  with the same bets used to define the CI. More specifically, we have the following, with $(\lambda_{t,n})$ as defined in (<ref>):

\begin{align}
&\CIbet = \{m \in [0,1]: W_n(m) < 1/\alpha\}, \\ \text{where} \quad  \label{eq:betting-ci-with-prpl-bets}
&W_n(m) =  \frac{1}{2} \lp W_n^+(m) + W_n^-(m) \rp, \quad
\text{and} \quad
W_n^{\pm}(m) = \prod_{t=1}^n \lp 1 \pm \lambda_{t,n}(X_t - m) \rp.
\end{align}

We now state the main result of this section.

Suppose the width  of the betting CI defined in (<ref>) after $n$ observations is denoted by $|\mc{C}_n| = 2w_n^{(bet)}$. Then, we have

\begin{align}
\limsup_{n \to \infty} \sqrt{n} \times w_n^{(bet)}
\;\stackrel{a.s.}{\leq}\;   \lim_{n \to \infty} \sqrt{n} \times w_n^{(\prpieb)}  \;\eqas\; \sigma \sqrt{2 \log(2/\alpha)}.
\end{align}

In other words, with the same choice of bets as used by the  CI defined in (<ref>), the limiting width achieved by the betting CI (<Ref>) is always no worse than the  CI.

Proof outline of <Ref>.  The first step in proving this result is to show that $\CIbet$,  the betting CI, is always contained inside a larger CI denoted by $\CIfan$, and furthermore, this larger CI has a finite limiting width $c_1<\infty$. Using the inclusion $\CIbet \subset \CIfan$, we can rewrite the betting CI as

\begin{align}
\CIbet = \{ m \in \CIfan: W_n(m) < 1/\alpha \}.
\end{align}

This simple modification, replacing “$m \in [0,1]$” to “$m \in \CIfan$” plays an important role in our analysis. This is because for  large values of $n$, we know that $|\CIfan| \leq 2c_1/\sqrt{n}$, which allows us to restrict our attention to values of  $m$ in a narrow band, instead of the whole unit interval. We exploit this to obtain the required approximation and concentration results, to bound width of betting CI with that of CI. In particular, we show that $w_n^{(bet)} \leq w_n^{(\prpieb)} + o(1/\sqrt{n})$, which leads to the required conclusion about the limiting widths. The details of the argument are presented in <Ref>.
<Ref> characterizes the performance of a betting CI  in the asymptotic regime. In the next section, we analyze its behavior in the non-asymptotic regime.

§ NON-ASYMPTOTIC ANALYSIS OF BETTING CI

To benchmark the performance of the betting CI in the non-asymptotic regime, we first   establish a fundamental, method-agnostic, lower bound on the width of any CI, in terms of certain inverse information projections (<Ref>) in <Ref>.
This result gives us a precise, problem-dependent measure of complexity (or hardness) of estimating the mean $\mu$ of a distribution $P^*$.
Then, in <Ref>, we show that the width of the betting CI nearly matches that lower bound, modulo a leading multiplicative constant and a logarithmic term in the argument of the information projection.

§.§ Lower bound on any CI width

Let $\mc{C}$ denote a method of constructing CIs for the mean of a univariate distribution; that is, given observations $X_1, \ldots, X_n$ drawn $\iid$ from a distribution $P^* \in \mc{P}_0 \subset \mc{P}(\mathbb{R})$, and a confidence level $\alpha \in (0,1)$, the method $\mc{C}$ gives us a CI, denoted by $C_n = \mc{C}(X^n, \alpha)$, which satisfies $\mathbb{P}\lp \mu \in C_n \rp \geq 1-\alpha$. Here $\mc{P}_0$ denotes some pre-specified class of probability distributions, such as all distributions supported on $[0,1]$. Furthermore, assume that the method $\mc{C}$ returns CIs whose width can be upper bounded by a deterministic quantity (as a function of $n$, $\alpha$, and the distribution $P^*$). Formally, assume there exists a function $w(n,P^*,\alpha)$ such that

\begin{align}
|\mc{C}(X^n, \alpha)| = |C_n| \defined \inf \{b-a: C_n \subset [a, b]\} \stackrel{a.s.}{\leq}  2w(n, P^*, \alpha).
\end{align}

For some CIs, such as Hoeffding and Bernstein CIs, the actual widths are deterministic

\begin{align}
w_H(n, P^*, \alpha) = \sqrt{ \frac{\log(2/\alpha)}{2 n}}, \quad \text{and} \quad
w_B(n, P^*, \alpha) = \sigma \sqrt{\frac{2 \log(2/\alpha)}{n}} + \frac{2 \log(1/\alpha)}{3n},
\end{align}

for distributions $P^* \in \mc{P}_0 =  \mc{P}\lp [0,1]\rp$.

Our main result of this section characterizes the achievable limit (i.e., minimum width) of CIs in terms of the minimum KL divergence (or relative entropy) between the distribution $P^*$, and a class of distributions whose means are either larger or smaller than some level $m$. We refer to these terms as information projections, and recall their formal definition below.

Let $P^*$ denote any distribution with mean $\mu$, lying in a class of distributions, $\mc{P}_0$, supported on $\mathbb{R}$. For any $m \in \mathbb{R}$, let  $\mc{P}_{0,m}^+$ (resp. $\mc{P}_{0,m}^-$) denote a subset of $\mc{P}_0$, containing distributions whose means are at least (resp. at most) $m \in \reals$; that is,  $\mc{P}^+_{0,m} = \{Q \in \mc{P}_0: \mu_Q \geq m\}$, and $\mc{P}_{0,m}^- = \{Q \in \mc{P}_0: \mu_Q \leq m\}$. Using these, we define the following two information projection terms:

\begin{align}
\klinf(P^*, m, \mc{P}_0) \defined \inf \{ \dkl(P^*, Q): Q \in \mc{P}^+_{0,m} \}, \quad \text{and} \quad
\klinfminus(P^*, m, \mc{P}_0) \defined \inf \{ \dkl(P^*, Q): Q \in \mc{P}^-_{0,m} \}.
\end{align}

For any $x \geq 0$, we define the inverse information projections as

\begin{align}
&\klinf(P^*, \cdot, \mc{P}_0)^{-1}(x) \defined \inf \lbr m \in \reals: \klinf(P^*, m, \mc{P}_0) \geq x \rbr,  \label{eq:inverse-klinf} \\
\text{and} \quad
&\klinfminus(P^*, \cdot, \mc{P}_0)^{-1}(x) \defined \sup \lbr m \in \reals: \klinfminus(P^*, m, \mc{P}_0) \geq x \rbr. \label{eq:inverse-klinf-minus}
\end{align}

Unlike the rest of this paper, the results in this section (as well as in <Ref>) are valid for arbitrary classes of distributions on the real line, and not necessarily restricted to distributions supported on $[0,1]$. When, dealing with arbitrary distribution classes, we will include $\mc{P}_0$ in the expression $\klinf(P, m, \mc{P}_0)$. However, for distributions supported on $[0,1]$, we will drop the $\mc{P}_0$ dependence, to simplify the notation.

We now show a lower bound on the width that can be achieved by any method ($\mc{C}$) of constructing level-$(1-\alpha)$ CIs for the mean  of real-valued random variables.

Suppose $\mc{C}$ denotes any method for constructing confidence intervals whose  width satisfies $|\mc{C}(X^n, \alpha)|\leq 2w(n, P, \alpha)$ almost surely, for all $P$ belonging to some class of distributions $\mc{P}_0 \subset \mc{P}(\mathbb{R})$.  Introduce the term $a(n, \alpha) =  \log\lp (1-\alpha)^{1-\alpha}\alpha^{2\alpha-1} \rp / n$, and  define

\begin{align}
w^*(n, P, \alpha)  = \frac{1}{{2}} \max \lbr \klinf(P, \cdot, \mc{P}_0)^{-1}\lp {a(n, \alpha)}\rp - \mu, \; \mu -  \klinfminus(P, \cdot, \mc{P}_0)^{-1}\lp {a(n, \alpha)}\rp \rbr.
\end{align}

Recall that $\klinf(P, \cdot, \mc{P}_0)^{-1}(x)$ and $\klinfminus(P, \cdot, \mc{P}_0)^{-1}$ were introduced in <Ref>. Then, the width of the CI must satisfy $w(n, P, \alpha) \geq w^*(n, P, \alpha)$.

The multiplicative factor of $(1/2)$ appearing in our width lower bound is likely an artifact of our proof technique, and we believe that it can be removed with a more careful analysis. However, the key conclusion of this result is that best achievable width (modulo a leading multiplicative constant) of any CI is characterized by the distribution dependent information projection terms. To the best of our knowledge, this is the first result providing an explicit characterization of the smallest achievable width of CI in terms of a distribution-dependent complexity term. As we see later in <Ref>, for some common distributions (namely, Bernoulli and Gaussian), the evolution of the above lower bound  with the sample size $n$ exactly matches that of the  widths of the optimal CIs (again, modulo a constant multiplicative term).

<Ref>, as stated, is not directly  applicable to CIs whose width after $n$ observations is a random quantity, such the the CI of Maurer and Pontil, 2009, or the CI, and betting CI of Waudby-Smith and Ramdas, 2023. However, this result can be used to obtain a lower bound on the width of the best deterministic envelope containing these CIs. Such an envelope can be constructed by using a part of the available $\alpha$ on replacing the random terms in the CIs, with their population counterparts, plus a deviation term. We obtain such a deterministic envelope for the betting CI in <Ref>.

Proof outline of <Ref>. The proof of this statement relies on the duality between confidence intervals (CIs) and (fixed sample-size) hypothesis tests. In other words, if we can construct tight level-$(1-\alpha)$ CIs around the mean of a distribution $P^*$, it means that we can also accurately test for the mean, and the detection boundary of such a test is determined by the width of the CI. In particular, we proceed in the following steps:

* Given $X_1, \ldots, X_n \simiid P^*$, we first consider a hypothesis testing problem with $H_0: P^* = P$ versus $H_1: P^* = Q$, where we assume that $\mu_Q$ (the mean of $Q$) is at least $\mu_P + 2w(n, P, \alpha)$ (here, we use $\mu_P$ and $\mu_Q$ to denote the means of $P$ and $Q$ respectively). For this problem, we define a test $\Psi$ that rejects the null if $\mu_Q \in \mc{C}(X^n, \alpha)$, and show that this test controls the type-I and type-II errors at level $\alpha$ for this hypothesis testing problem.

* Next, using the properties of the test $\Psi$, the chain rule of KL divergence, and the data processing inequality, we show that the KL divergence between $P$ and $Q$ must satisfy $\dkl(P, Q) \geq a(n,\alpha)$. Since the right side in this inequality is independent of $Q$, we conclude that $\klinf\big(P, \mu_P + 2w(n, P, \alpha) \big) \geq a(n, \alpha)\defined  \log\lp (1-\alpha)^{1-\alpha} \alpha^{2\alpha-1} \rp/n $, by taking an infimum over all possible distributions $Q$ in the set $\mc{P}_{0,\mu_P + 2w(n, P, \alpha)}^{+}$. Recall that $\mc{P}_{0,\mu_P + 2w(n, P, \alpha)}^{+}$ denotes the class of all distributions in $\mc{P}_0$, with mean at least $\mu_P + 2w(n, P, \alpha)$.

* Finally, we use the definition of $w^* \equiv w^*(n, P, \alpha)$, and the continuity of $\klinf(P, \cdot)$,  to observe that $\klinf\big(P, \mu_P + 2w(n, P, \alpha) \big) \geq \klinf\big(P, \mu_P + 2w^*(n, P, \alpha) \big)$. This implies one part of the required result due to the monotonicity of $\klinf(P, \cdot)$.

Repeating the same argument, but with $Q$ such that $\mu_Q$ is smaller than $\mu_P-2w(n, P, \alpha)$ gives us the other term depending on $\klinfminus$. The details of this proof are in <Ref>.

§.§ Width achieved by betting CI

Having established an unimprovable limit on the width of any level-$(1-\alpha)$ CI in <Ref>, we now analyze how close the betting CI comes to achieving this optimal performance.  Our main result shows the width of the betting CI nearly matches the lower bound derived in <Ref>, but with two minor differences: there is an extra leading multiplicative factor of $2$ (see <Ref>), and there is an extra $\mc{O}(\log n /n)$ term in the  argument of the inverse information projection terms. Despite these two sources of suboptimality, the main takeaway of this section is that the width of the betting CI has the `right' functional form, depending on the same inverse information projection based complexity measure that arise in the method-agnostic lower bound. To the best of our knowledge, none of the existing CIs are known to admit similar upper bounds on their widths.

Before proceeding to the statement of the result, we need to introduce some additional notation.
In particular, recall from Honda and Takemura, 2010 that for distributions supported on $[0,1]$, the two information projection terms (<Ref>) have the following dual representation for $a \in \{+, -\}$, that makes their connection to the betting CI/CS explicit:

\begin{align}
\text{KL}_{\inf}^a(P^*, m) = \sup_{\lambda \in S_a} \mathbb{E}[\log(1+\lambda(X-m))], \quad \text{where} \quad S_+ = \lb\frac{-1}{1-m}, 0\rb, \quad \text{and} \quad S_- = \lb0, \frac{1}{m}\rb. \label{eq:klinf-dual}
\end{align}

For any $m \in [0,1]$, we also introduce their corresponding optimal betting fractions

\begin{align}
&\lambda^*_a(m) \in \argmax_{\lambda \in S_a} \; \mathbb{E}_{X \sim P^*} \lb \log \lp 1 + \lambda(X-m) \rp \rb,\quad
\text{for} \; a \in \{+, -\}. \label{eq:lambda-def-dual}
\end{align}

We can now state the result characterizing the width of the betting CI.

Consider a betting CI constructed using the mixture betting strategy of <Ref>.  Then, the width of such a level-$(1-\alpha/3)$ CI, denoted by $w^{(bet)}(n, P^*, \alpha/3)$,  satisfies:

\begin{align}
w^{(bet)}(n, P^*, \alpha/3) \leq    \max \lbr \klinf(\Phat_n, \cdot)^{-1}\lp \log(3n^2/\alpha) \rp - \mu, \;  \mu - \klinfminus(\Phat_n, \cdot)^{-1}\lp \log(3n^2/\alpha) \rp \rbr, \label{eq:ci-random-upper-bound}
\end{align}

where $\Phat_n$ denotes the empirical distribution of $\{X_1, \ldots, X_n\}$.
Since the above upper bound on $w^{(bet)}(n, P^*, \alpha/3)$ is random, we next derive a deterministic bound on it, that holds with probability at least $1-\alpha$, for $n$ large enough (precise conditions in <Ref>):

\begin{align}
&w^{(bet)}(n, P^*, \alpha/3) \leq \max \lbr \klinf(P^*, \cdot)^{-1}\lp b(n, \alpha) \rp - \mu, \;  \mu - \klinfminus(P^*, \cdot)^{-1}\lp b(n, \alpha) \rp \rbr + \frac{1}{n^2}, \\
&\text{where} \quad b(n,\alpha) = \frac{\log(3n^2/\alpha)}{n} + \frac{9 \log(3n^2/\alpha)}{n\sigma^2} = \mc{O}\lp \frac{ \log(n/\alpha)}{n} \rp.  \label{eq:ci-deterministic-upper-bound}
\end{align}

Since the regret guarantee of the mixture method of <Ref> is valid for all $n$, the first part of <Ref>; that is, the bound in (<ref>), is simultaneously true for all values of $n$. Thus, (<ref>) is in fact a random upper bound on the width of the betting CS constructed using the mixture method. Interestingly,  the optimal complexity term characterizing the (random) width of the CS, again turns out to depend on  information projections, now computed for the empirical probability distribution, $\Phat_n$, instead of the true distribution $P^*$.
The second part of <Ref>, however, is valid only for a fixed value of $n$.

As mentioned in <Ref>, since the bound on the width of the betting CI obtained in (<ref>) is a random quantity, it is not subject to the fundamental limit obtained in <Ref>. To address this, we use one-third of the available $\alpha$ on constructing the CI, and the remaining two-thirds on obtaining a deterministic upper bound on the random width. The size of the resulting level-$(1-\alpha)$, deterministic CI  is then subject to the result of <Ref>, and it matches the dependence of the lower bound on the information projection term, with two differences. It is missing the leading multiplicative factor $1/2$ present in the lower bound of <Ref>, and it has an additional logarithmic in $n$ additive term in the argument of $\klinf(P^*, \cdot)^{-1}$. This $\mc{O}\lp \log n\rp$ term arises due to the regret incurred by the betting strategy, as well as a union bound over a uniform grid consisting of $m = \mc{O}(n^2)$ points, that we used to obtain the deterministic upper bound on the inverse empirical information projection.

It is easy to verify that the term $a(n, \alpha)$ used in the statement of the lower bound (<Ref>) is approximately equal to $\log(1/\alpha)/n$ in the limit of $\alpha \to 0$.
Thus, the main conclusion of <Ref> is that we can construct a deterministic envelope containing the betting CI, whose width has very nearly the same functional dependence on $n$, $P$, and $\alpha$, as the method-independent lower bound.  To the best of our knowledge, none of the other commonly used CIs (such as Hoeffding, Bernstein, , or ) are known to exhibit this near-optimal behavior.

Proof outline of <Ref>.
We begin by appealing to the logarithmic regret of the betting strategy, to show that for any $m \neq \mu$, the wealth after $n$ steps, $W_n(m)$, grows at an exponential rate (with $n$). Furthermore, the growth rate of the wealth is approximately equal to the maximum of two empirical information projection terms. Inverting this lower bound on the wealth gives us the bound on the width stated in (<ref>).

To obtain the deterministic upper bound on the width, we need a high probability bound for the concentration of the empirical information projection about its population value for (almost) all $m \in [0,1]$. Existing concentration inequalities, such as those derived by <cit.>, when applied directly are not sufficiently tight for our purposes. Instead, we take an alternative approach, by first obtaining a wider CI that contains $\CIbet$, and has a  width  of $2b_n(n, \alpha)$. By focusing on this narrow band, we show that the information projection can be well approximated by the first two terms of their Taylor's expansion. Hence by controlling the deviations of the first two empirical moments from their population terms, we get a sufficiently tight concentration result for the empirical information projection about its population value. The final step is to take a union bound for $m$ values over grid $\mc{M}_n$ of size $n^2+1$, consisting of equally spaced points inside the larger band of size $2b(n, \alpha)$.
This gives us a lower bound on the wealth, $W_n(m_i)$, for points $m_i \in \mc{M}_n$. We obtain the final bound (<ref>)  by taking the inverse of the information projection (i.e., $\klinf(P^*, \cdot)^{-1}$) over the points in the grid $\mc{M}_n$, and then adding the grid spacing term, $1/n^2$, to account for the possible discretization error.
The details of these steps are in <Ref>.

§ NON-ASYMPTOTIC ANALYSIS OF BETTING CS

We now turn our attention to the betting confidence sequences (CS) constructed by Waudby-Smith and Ramdas, 2023, and show that they can be also be shown to achieve a near-optimal performance, similar to the betting CI. The construction of betting CSs follows the same general steps introduced in <Ref> as we recall below.

Consider a stream of observations, $X_1, X_2, \ldots$, drawn from a distribution $P^*$ supported on $[0,1]$ with mean $\mu$. For all $m \in [0,1]$, set $W_0(m)=1$, and define the wealth process as

\begin{align}
W_n(m) = W_{n-1}(m) \times \lp 1 + \lambda_n(m)(X_n - m) \rp, \quad \text{for all } m \in [0, 1],
\end{align}

where $\{\lambda_n(m): n \geq 1, \, m \in [0,1]\}$ is any sequence of predictable bets. Then, the level-$(1-\alpha)$ betting CS is a collection of sets $\{C_n \subset [0,1]: n \geq 1\}$, defined as

\begin{align}
C_n = \{m \in [0,1]: W_n(m) < 1/\alpha \}, \label{eq:betting-cs-def}
\end{align}

satisfying the uniform coverage guarantee $\mathbb{P}\lp \forall n \geq 1: \mu \in C_n \rp \geq 1-\alpha$. As a consequence of the uniform coverage guarantee, we can also assume that the sets in the CS are nested; that is, $C_n \subset C_{n'}$ for all $n' \leq n$. In other words, for any $n \geq 1$, we can let $C_n$ be the running intersection of all $C_{n'}$ for $n'\leq n$ due to the time-uniform nature of CS.

The main difference between the betting CI of <Ref>, and the betting CS defined above, is that the bets $\{ \lambda_t(m): t \geq 1, \, m \in [0,1]\}$ are not optimized with a pre-specified horizon $n$. The uniform coverage guarantee of the betting CS is a simple consequence of Ville's inequality, a time-uniform variant of Markov's inequality, and we refer the reader to Waudby-Smith and Ramdas, 2023 for further details.

To analyze the behavior of betting CSs, with possibly random widths, we first introduce the notion of “effective width” in <Ref>. Then, in <Ref> we obtain a lower bound on the effective width of any CS, and show that the betting CS instantiated with the mixture method stated in <Ref>,  nearly matches this fundamental limit in <Ref>.

§.§ Lower Bound on any CS effective width

In this section, we establish fundamental limits on the performance of any valid level-$(1-\alpha)$ CS, with possibly random widths. We begin by introducing a notion of effective width, that we will use to characterize the performance of  CSs.

Let $\mc{C}$ denote a method for constructing confidence sequences. Given a stream of observations $X_1, X_2, \ldots \simiid P^*$,  define the random stopping times

\begin{align}
T_w \equiv T_w(P^*, \alpha) \defined \inf \lbr n \geq 1:  |\mc{C}(X^n, \alpha)| \leq 2w \rbr,
\quad \text{for } w \in (0, \infty).
\end{align}

Then, the effective width of the CS  after $n$ observations, is defined as:

\begin{align}
w_e(n, P^*, \alpha) \defined \inf \lbr w > 0: \mathbb{E}[T_w] \leq n  \rbr.
\end{align}

In words, the effective width of a CS after $n$ observations is the minimum $w>0$, for which the expected number of observations needed by the CS to reduce its width below $2w$, no larger  than $n$.

While this stopping time based definition of effective width turns out to be particularly well suited to analyzing confidence sequences, we note that the time-uniform coverage guarantee is not necessary for this definition to be valid. In particular, the same definition can also be applied to CIs with random or even deterministic widths.
In fact,  the definition of effective width reduces to that of the usual width for the case of CIs with deterministic widths. To see why this is true, suppose $\mc{C}$ constructs CIs with deterministic widths $w(n, P^*, \alpha)$, that are  non-increasing in $n$. Then, the term $T_w$ in this case is simply a constant. Hence, $w_e(n, P^*, \alpha)$ is equal to $\inf \{w \geq 0: T_w(P^*, \alpha) \leq n\}$. Now, note that for all $w \in [w(n, P^*, \alpha),  w(n-1, P^*, \alpha))$, we have $T_w = n$. This implies that

\begin{align}
w_e(n, P^*, \alpha ) = \inf \{ w: w \in [w(n, P^*, \alpha), w(n-1, P^*, \alpha)) \} = w(n, P^*, \alpha),
\end{align}

as claimed.
For example, in the case of Hoeffding CI, we have $T_w = \left \lceil \log(2/\alpha)/(2w^2) \right \rceil$, for all $w>0$, which implies that

\begin{align}
w_e^{H}(n, P^*, \alpha) = \inf \lbr w \geq 0:  \left\lceil \frac{\log(2/\alpha)}{2w^2} \right\rceil \leq n \rbr = \sqrt{\frac{\log(2/\alpha)}{2n}} = w_H(n, P^*, \alpha).
\end{align}

We now present the main result of this section, that  characterizes the minimum achievable effective width of a confidence sequence (CS).

Suppose $\mc{C}$ is a method for constructing confidence sequences that satisfies $\mathbb{E}[T_w(P, \alpha)] < \infty$ for all $w>0$, and for all $P \in \mc{P}_0 \subset \mc{P}(\reals)$. With  $a(n, \alpha) \defined \log\lp (1-\alpha)^{1-\alpha} \alpha^{2\alpha-1} \rp/n $, introduce

\begin{align}
w_e^*(n, P, \alpha)  = \frac{1}{{2}} \max \lbr \klinf(P, \cdot, \mc{P}_0)^{-1}\lp {a(n, \alpha)} - \mu \rp, \; \mu -  \klinfminus(P, \cdot, \mc{P}_0)^{-1}\lp {a(n, \alpha)}\rp \rbr,
\end{align}

where the inverse information projection terms, $\klinf(P, \cdot, \mc{P}_0)^{-1}(\cdot)$ and $\klinfminus(P, \cdot, \mc{P}_0)^{-1}(\cdot)$, were defined in (<ref>).
Then the effective width of the CS constructed by method $\mc{C}$ using observations from $P \in \mc{P}_0$ must satisfy $w_e(n, P, \alpha) \geq w_e^*(n, P, \alpha)$.

Proof outline of <Ref>.
The proof of this proposition uses a similar  high-level strategy outlined for proving <Ref>. The key difference is that we use now set up a sequential testing problem, for which we design a test using the method $\mc{C}$  for constructing CSs.  We present the details in <Ref>.

§.§ Effective width of betting CS

In the previous subsection, we obtained a lower bound on the effective width of any method, $\mc{C}$, for constructing confidence sequences. We now show that the betting CS proposed by Waudby-Smith and Ramdas, 2023 nearly matches this lower bound. We  first present a simplifying assumption about the data generating distribution $P^*$.

The distribution $P^*$ is supported over a  closed interval that is a strict subset of $[0,1]$. That is, $\text{supp}(P^*) = [A, B]$ with $A, B \in (0,1)$.

This assumption implies that for all values of $m$, the logarithmic increment of the wealth process, $\log(1+\lambda_t(m)(X_t-m))$, is a bounded random variable. While this assumption is not strictly necessary for obtaining the next result, it does simplify the final expression of the upper bound.

Suppose <Ref> is true, and consider a betting CS constructed using the mixture betting strategy (<Ref>) that incurs a logarithmic regret. Then, the effective width of this CS satisfies:

\begin{align}
&w_e^{(bet)}(n, P^*, \alpha) \leq \max \lbr \klinf(P^*, \cdot)^{-1}(b(n,\alpha)) - \mu, \; \mu - \klinfminus(P^*, \cdot)^{-1}(b(n,\alpha)) \rbr,\\
\text{where } &b(n,\alpha) = \frac{ 2\log(n^2/\alpha) + 2C }{n},
\end{align}

for a constant $C$ that depends on the distribution $P^*$ (<Ref>).

As in the case of <Ref>, this result implies that the effective width is of the same order as the method-agnostic lower bound established in <Ref>, modulo a constant multiplicative factor and an additive $2\log(n^2)+2C$ term in the argument to the inverse information projection.
The term $C$ arises due to the possible overshoot of the wealth process beyond the threshold $1/\alpha$, and it is generally unavoidable, without further assumptions.
Interestingly, the upper bound has much a smaller logarithmic penalty term, as compared to the upper bound on the betting CI width of <Ref>. This is because of the expectation in the definition of effective width, which causes the population information projection (instead of the empirical information projection) to naturally appear in the upper-bound expression,  and we don't need to apply a  concentration result over a uniform grid to get the required form matching the lower bound.

Proof outline of <Ref>. By appealing to the regret bound of the mixture betting strategy, we can reduce the problem into that of analyzing the `oracle' wealth process $\{W^*_t(m): t \geq 1, \; m \in [0,1]\}$, with $W^*_t(m) = \prod_{i=1}^t\lp 1 + \lambda^*(m)(X_i-m) \rp$. Due to the nature of the multiplicative factors, this process is significantly more tractable to analyze than the true wealth process.
In particular, we proceed as follows:

* In the first step, we show that for any $w$, we can upper bound the stopping time  $T_w$ in terms of the maximum of two stopping times, $\tau_w^+$ and $\tau_w^-$, associated with the oracle wealth process. In particular, $\tau_w^+$ (resp. $\tau_w^-$) is the first time, the $\log$ of the oracle wealth process at $m=\mu+w$ (resp. $m=\mu-w$) exceeds $\log(n^2/\alpha)$.  This implies the bound $\mathbb{E}[T_w] \leq 2 \max \{ \mathbb{E}[\tau_w^+], \, \mathbb{E}[\tau_w^-] \}$.

* The key benefit of working with the oracle process is that $\log(W_n^*(m))$ is the sum of terms, as the oracle bet is a fixed, non-random quantity. This is unlike the actual wealth process with predictable  bets. Hence, by applying appropriate optional stopping arguments, we show that $\mathbb{E}[\tau_w^+]$ (resp. $\mathbb{E}[\tau_w^-]$)  can be upper bounded in terms of $\klinf(P^*, \mu+w)$ (resp. $\klinfminus(P^*, \mu-w)$).

* The final step in concluding the proof involves inverting the two information projection terms that bound $\mathbb{E}[T_w]$, and some simplification to get the required bound.

The details are in <Ref>.

Orabona and Jun, 2021 proposed and analyzed a related confidence sequence for means of bounded random variables, that directly uses the regret of the betting strategy (denoted by $r_n(m)$) to define the CS. In particular, they define

\begin{align}
&C_n = \left\{m \in [0, 1]: \log \widetilde{W}_n(m)< \log(1/\alpha) \right\}, \label{eq:orabona-jun} \\
\text{where} \quad &\widetilde{W}_n(m) \defined \sup_{\lambda \in \lb \frac{-1}{1-m}, \frac{1}{m} \rb} \sum_{t=1}^n \log( 1+ \lambda(X_t - m)) - r_n(m).
\end{align}

Note that for many strategies, such as the mixture method, we know tight closed form expressions for $r_n(m)$, and furthermore, the optimization problem in the definition of $\widetilde{W}_n(m)$ can be solved efficiently using off-the-shelf solvers as its objective is concave. Thus, this CS is computationally feasible, and also satisfies several interesting properties.
In addition, we note that the results that we have stated in <Ref> and <Ref> for the betting CI/CS (constructed using the mixture method) are also applicable to the  CI/CS of Orabona and Jun, 2021. The reason for this is that the analysis of both these results implicitly proceeds by observing that the betting CI/CS is contained inside the CI/CS defined above in (<ref>), when constructed with the same betting strategy.

§ DISCUSSION, EXTENSIONS AND OPEN QUESTIONS

In <Ref>, we instantiate our general lower bound for CIs (<Ref>) for some univariate distributions, and compare them with the optimal CI width for those distributions. Next, in <Ref>, we show that the techniques we developed for obtaining the lower bounds on the widths of CIs and CSs can be easily generalized to the case of multivariate observations. In <Ref>, we extend our asymptotic analysis to the practically interesting case of estimating the mean of $M$ unknown values in the unit interval, by uniformly sampling them without replacement. We end  with some preliminary discussion about appropriate notions of second-order limiting widths of CIs  in <Ref>.

§.§ Instantiations of the lower bound

Since the non-asymptotic lower bounds in <Ref> and <Ref> are stated in terms of the abstract information projections, they might be difficult to interpret. For many distributions, such as members of one-parameter exponential family, the lower bounds admit closed-from expressions. In this section, we study the tightness of the CI lower bound (since the expressions for the CS lower bound are almost identical), by comparing its instantiations for two specific distributions with the width of an oracle CI constructed using the quantiles of the true distributions.

Bernoulli distribution. We begin with the simplest case, where the distribution $P^*$ is a Bernoulli with mean $\mu$. In this case, $\klinf$ and $\klinfminus$ can be explicitly calculated. In particular, both $\klinf(P^*, m)$ and $\klinfminus(P^*, m)$ are equal to  $\mu \log(\mu/m) + (1-\mu) \log( (1-\mu)/(1-m))$ for all $m \geq \mu$ and $m \leq \mu$ respectively. We can numerically invert these expressions to obtain a good approximation of the lower bounds derived in <Ref>.

To evaluate the tightness of the lower bound, we compare it to the width of the CI constructed with the knowledge of the distribution of the sample mean of $X_1, \ldots, X_n$. In particular, $\sum_{i=1}^n X_i$ is distributed according to the Binomial distribution with parameters $n$ and $\mu$. Hence, we can define an oracle CI as $C_n^* = [\mu \pm w^*]$, with $w^* = (z_{1-\alpha/2} - z_{\alpha/2})/2n$, where $z_{\beta}$ denotes the $\beta$-quantile of the Binomial distribution with parameters $n$ and $\mu$. We plot the variation of the lower bound, and the width of the oracle CI, with the sample size $n$ for $\mu = 0.9$ in <Ref>.

Gaussian distribution. Similarly, for the class of Gaussian distributions with variance $\sigma^2$,  $\klinf(P^*, m)$ and $\klinfminus(P^*, m)$ $ = (\mu - m)^2/2\sigma^2$, if $m \geq \mu$. Hence, the result of <Ref> implies that the width of any CI for this class must satisfy $w(n, P^*, \alpha) \geq \sigma\sqrt{ a(n, \alpha)/2}$, where $a(n,\alpha)$ is as defined in <Ref>.

As in the Bernoulli case, we will compare the lower bound with the width of the oracle CI, defined as $C_n^* = [\mu \pm w^*]$ with  $w^* = \sigma(z_{1-\alpha/2} - z_{\alpha})/2\sqrt{n}$, where $z_{\beta}$ denotes the $\beta$-quantile of the standard normal distribution. The variation of the predicted lower bound and the oracle upper bound with the sample size $n$, for $P^* = N(0, 4)$ is shown in <Ref>.

The figures plot the variation (with the sample size $n$) of the predicted lower bound (<Ref>) on the width of any CI (denoted by `lower'), and  the width of the oracle CI (denoted by `upper')  for the mean of Bernoulli (left) and Gaussian (right) distributions (with  $\alpha$  set to $0.01$). In both cases, the ratio of the upper and lower bounds is approximately $3.43$ for all values of $n \geq 1000$, indicating that the lower bound captures the `right' behavior of the optimal width with $n$, modulo a constant multiplicative factor.

§.§ Extending lower bounds to the multivariate case

While our focus in this paper is on the case of univariate observations, we note that the techniques used to obtain the lower bounds (<Ref> and <Ref>) can be easily extended to more general observation spaces.
To illustrate this, we state the generalizations of these two lower bounds for the case of observations lying in $\mathcal{X} = \mathbb{R}^d$, for some integer $d \geq 1$. In particular, suppose we are given observations $X_1, X_2, \ldots$, drawn from a distribution $P^* \in \mc{P}_0 \subset \mc{P}(\mc{X})$, with mean vector $\mu$.

Our first result considers a method ($\mc{C}$) for constructing confidence intervals for $P^*$ based on observations $X_1, \ldots, X_n$, which satisfies the condition that

\begin{align}
\sup_{x, x' \in \mc{C}(X_1^n, \alpha)} \; \|x-x'\|_2 \leq 2w(n, P^*, \alpha). \label{eq:mutltivariate-width-condition-1}
\end{align}

In other words, the confidence set constructed by the method $\mc{C}$ based on $n$ observations is contained in a ball of radius no larger than  a deterministic value $w(n, P^*, \alpha)$.  To state the lower bound, we need to introduce a notion of  information projection for multivariate case:

\begin{align}
&\klinfmulti(P, r, \mc{P}_0) = \inf_{Q \in \mc{P}_0: \|\mu_Q-\mu_P\|_2 \geq r} \dkl(P, Q),\label{eq:klinf-multi} \\
\text{and} \quad
&\klinfmulti(P, \cdot, \mc{P}_0)^{-1}(x) = \inf \{r \geq 0: \klinfmulti(P, r, \mc{P}_0) \geq x \}. \label{eq:klinf-multi-inv}
\end{align}

Suppose $\mc{C}$ denotes any strategy for constructing confidence sets for the mean vector $\mu$ satisfying (<ref>) for all $P \in \mc{P}_0 \subset \mc{P}(\mc{X})$ for $\mc{X} = \mathbb{R}^d$.   As before, we define $a(n, \alpha) = \frac{ \log\lp (1-\alpha)^{1-\alpha} \alpha^{2\alpha-1} \rp }{n}$, and

\begin{align}
w^*(n, P, \alpha)  = \frac{1}{{2}}  \klinfmulti(P, \cdot, \mc{P}_0)^{-1}\lp {a(n, \alpha)}\rp,
\end{align}

where $\klinfmulti(P, \cdot, \mc{P}_0)^{-1}$ was introduced in (<ref>).  Then, the radius of the confidence set must satisfy $w(n, P, \alpha) \geq w^*(n, P, \alpha)$.

The proof of this statement follows by adapting the arguments developed for proving <Ref>, and the details are in <Ref>.

Next, we introduce the notion of effective radius, that is a straightforward generalization of the effective width (<Ref>).
Let $\mc{C}$ denote a method for constructing confidence sequences for the mean $\mu$ of a distribution $P^* \in \mc{P}_0 \subset \mc{P}(\mc{X})$. Given a stream of observations $X_1, X_2, \ldots \simiid P^*$,  define the random stopping time

\begin{align}
T_w \equiv T_w(P^*, \alpha) \defined \inf \lbr n \geq 1:  \sup_{x, x' \in \mc{C}(X^n, \alpha)} \, \|x-x'\|_2 \leq 2w \rbr,  \quad \text{for } w \in (0, \infty).
\end{align}

Then, the effective radius of the CS  after $n$ observations, is defined as:

\begin{align}
w_e(n, P^*, \alpha) \defined \inf \lbr w \geq 0: \mathbb{E}[T_w(P^*, \alpha)] \leq n \rbr.
\end{align}

Our next result obtains a lower bound on the effective radius of any scheme for constructing a CS for the mean vector based on $\iid$ observations.

Suppose $\mc{C}$ is a method for constructing confidence sequences that satisfies $\mathbb{E}[T_w(P, \alpha)] < \infty$ for all $w>0$, and for all $P \in \mc{P}_0 \subset \mc{P}(\mc{X})$ for $\mc{X} = \mathbb{R}^d$. With  $a(n, \alpha) \defined  \log\lp (1-\alpha)^{1-\alpha} \alpha^{2\alpha-1} \rp /n$, introduce the following term:

\begin{align}
w^*(n, P, \alpha)  = \frac{1}{{2}}  \klinfmulti(P, \cdot, \mc{P}_0)^{-1}\lp {a(n, \alpha)} \rp.
\end{align}

Then the effective radius of the CS constructed by strategy $\mc{C}$ using observations from $P \in \mc{P}_0$ must satisfy $w_e(n, P, \alpha) \geq w^*(n, P, \alpha)$.

The proof of this result is also a simple generalization of the corresponding univariate result (<Ref>), and we present the details in <Ref>.

§.§ Sampling without replacement

Suppose $\Xsample_M$ denotes a collection of $M$ numbers, $\{x_1, \ldots, x_M\}$, each lying in the unit interval $[0,1]$. Define the mean and variance terms as

\begin{align}
\mu \equiv \mu_M = \frac{1}{M} \sum_{i=1}^M x_i, \quad \text{and} \quad \sigma^2 \equiv \sigma_M^2 = \frac{1}{M} \sum_{i=1}^M (x_i- \mu)^2.
\end{align}

Suppose $X_1, X_2, \ldots$ are drawn uniformly from this set without replacement (); that is $X_1 \sim \text{Uniform}(\Xsample_M)$, $X_2 \sim \text{Uniform}\lp \Xsample_M \setminus \{X_1\} \rp$, and so on. Our goal is to construct a high probability (i.e, with probability at least $1-\alpha$, for a given $\alpha$) estimate of the mean $\mu$, based on these observations drawn . We being be recalling some existing results on this topic most relevant to us.

As in the without replacement case, we can construct CIs based on standard exponential concentration inequalities. However, one key feature of the setting is that the uncertainty about the mean $\mu$ rapidly decays to zero (exactly) as the sample-size $n$ approaches $M$. This fact was captured by Serfling, 1974, who obtained an improved version of an earlier inequality by Hoeffding, 1963, with the term $n$ replaced by $\frac{n}{1 - (n-1)/M}$. Bardenet and Maillard, 2015 obtained a slight improvement of Serfling's result when $n \geq M/2$, and then used it to obtain variants of Hoeffding-Serfling, Bernstein-Serfling, and Empirical-Bernstein-Serfling inequalities. Finally, Waudby-Smith and Ramdas, 2023 showed that their techniques also extend easily to the case, and in particular, they proposed  variants of their CI and betting CI. We discuss the details about the construction of these CIs in <Ref>.

In this section, we introduce an analog of the first-order limiting width defined in (<ref>) for the case. First we state our main assumption.

Considering a sequence of problems $(\Xsample_M)_{M \geq 1}$, with $\mu_M \defined \frac{1}{M} \sum_{i=1}^M x_i$, assume that:

\begin{align}
\lim_{M \to \infty} \frac{1}{M} \sum_{i=1}^M (x_i - \mu_M)^2 = \lim_{M \to \infty} \sigma_M^2 = \sigma^2 >0.
\end{align}

A simpler version of the above condition is assuming that $\sigma_M^2=\sigma^2$ and $\mu_M=\mu$ for all $M \in \mathbb{N}$.

To define the limiting width of the CI in the case, we fix a $\rho \in (0,1]$, and consider the limiting value of the scaled width of the CI based on $n = \lceil \rho M \rceil$ observations, as $M \to \infty$. That is,

\begin{align}
\gamma_1(\rho) \defined \lim_{M \to \infty, n = \lceil \rho M \rceil} \, \sqrt{n} w_n.
\end{align}

The main result of this section is a analog of <Ref>. In particular, it says that for the same choice of the bets, the limiting width of the betting CI is never larger than that of the CI. Furthermore, both of these CIs capture the improvement in the width of the CI when $n$ approaches $M$, or equivalently when $\rho \to 1$.

Suppose <Ref> is true. Then, with $n = \lfloor \rho M \rfloor$ for some $\rho>0$, we have

\begin{align}
\gamma_1^{(bet)}(\rho) \leq \gamma_1^{(\prpieb)}(\rho) =  \sigma \sqrt{ 2\log (2/\alpha)} \lp  \frac{\rho}{-\log\lp1-\rho\rp} \rp.
\end{align}

The proof of this statement is in <Ref>.

Consider the case when $\rho=1/2$. Then, we have $\lim_{M \to \infty} \sqrt{n} w_n =  \frac{\sigma \sqrt{2 \log(2/\alpha)}}{2\, \log 2} \approx 0.72 \sigma \sqrt{2 \log(2/\alpha)}$. In comparison,  the Bernstein CI derived  by Bardenet and Maillard, 2015 with the knowledge of the variance, has a limiting value of $\sqrt{2 \log(2/\alpha)(1-1/2)} \approx 0.707 \sigma \sqrt{2 \log(2/\alpha)}$. While close, the Bernstein CI of Bardenet and Maillard, 2015 has a better limiting width. Investigating whether the limiting widths of betting and can be improved, as well as establishing the fundamental performance limits in the case (i.e., analogs of <Ref> and <Ref>) are interesting directions for future work.

§.§ Second-order limiting width

In (<ref>), we defined the notion of the first-order limiting (denoted by $\gamma_1$) widths to compare different CIs. Since the width of most practical CIs converges to zero at $\mc{O}(1/\sqrt{n})$ rate, their first-order limiting width is either a constant (for Hoeffding, Bernstein, , ), or upper bounded by a constant (betting CI)  almost surely. In this section, we explore the notion of second-order limiting widths for CIs.

Let $\mc{C}$ denote a method of constructing CIs: that is, for any $n \geq 1$, $\alpha \in (0,1)$, and $(X_1, \ldots, X_n) \simiid P^*$, the set $C_n = \mc{C}(X^n, \alpha)$ is a level-$(1-\alpha)$ CI for the mean $\mu$. Denote the width of $C_n$ with $2w_n$, and assume that its first-order limiting width, $\gamma_1$, is a constant almost surely. Then, we define the second-order limiting width as

\begin{align}
\gamma_2 = \lim_{n \to \infty} \,n \times \lp w_n - \frac{\gamma_1}{\sqrt{n}} \rp.
\end{align}

For  CIs with deterministic widths, such as Hoeffding or Bernstein, $\gamma_2$ is a constant. For example, $\gamma_2^{(H)} = 0$, and $\gamma_2^{(B)} = 2 \log(2/\alpha)/3$. For CIs with random widths, such as , due to the fluctuations in the estimated parameter being inflated by a factor of $n$, characterizing $\gamma_2$ in an almost sure sense is ruled out. Instead, we need to explore weaker forms of convergence for the second-order limiting widths of such CIs. For example, we can prove that $\gamma_2^{(\mpeb)}$ converges in distribution to a Gaussian random variable with mean $7\log(4/\alpha)/3$, as we show in our next result. In the statement of this result, we use $\mu_4$ to denote the fourth central moment of $X$; that is, $\mu_4 = \mathbb{E}[(X-\mu)^4]$.

With $2w_n^{(\mpeb)}$ denoting the  width of the CI, we have

\begin{align}
n \lp w_n^{(\mpeb)} - \frac{\gamma_1^{(\mpeb)}}{\sqrt{n}} \rp = \frac{7 \log(4/\alpha)}{3} + T^{(\mpeb)}_n + o_P(1),
\end{align}

where $o_P(1)$ is a term converging to $0$ in probability, and $T_n^{(\mpeb)}$ denotes a zero-mean statistic, that converges in distribution to $N(0, \log(4/\alpha)(\mu_4 - \sigma^4)/2)$. Similarly, the CI satisfies

\begin{align}
n \lp w_n^{(\prpieb)} - \frac{\gamma_1^{(\prpieb)}}{\sqrt{n}} \rp = \frac{2 \log(2/\alpha)}{3} + T^{(\prpieb)}_n + o_P(1),
\end{align}

where $T_n^{(\prpieb)}$ is again a zero-mean random variable.

The proof of this result is in <Ref>.
Unlike , the leading constant, $2\log(2/\alpha)/3$ in the above expression for the second-order width statistic of CI matches the second-order term of the Bernstein CI. However, we have not managed to prove the  convergence of $T_n^{(\prpieb)}$ in any suitable sense.
It is an interesting question for future work whether we can modify the CI (or modify the definition of second-order limiting width), to guarantee that it dominates $T_n^{(\mpeb)}$ in an appropriate sense.

§ CONCLUSION

In this paper, we provided theoretical justification for the superior empirical performance of the betting confidence intervals (CIs) and confidence sequences (CSs) reported by Waudby-Smith and Ramdas, 2023. In particular, we first showed that the first-order limiting width of the betting CI (i.e., scaled by $\sqrt{n}$) is strictly smaller than the empirical Bernstein CIs of Maurer and Pontil, 2009, and is at least as small as the limiting width of a Bernstein CI constructed with the knowledge of the true variance. Then, we established the near-optimality of the betting CI in the finite-$n$ regime, by showing that the width of the betting CI is of the same order as the fundamental, method-agnostic, limit. Finally, we showed that a similar near-optimality guarantee also holds for  betting CSs. Together these results provide strong theoretical arguments supporting the empirically observed superiority of betting CI/CS in both the asymptotic, and finite-sample regimes.

Our results open up several interesting directions for future work. For instance, our non-asymptotic analysis implies that there is a gap (inflation by a constant factor, and a $\mc{O}\lp \log(n)/n\rp$ additive term in the argument of inverse information projection) between the upper bound achieved by the betting CI/CS, and the corresponding method-agnostic lower bounds. Investigating whether this gap can be closed by using more refined analysis techniques is an important question for future work. Another important direction is to extend our results to the without-replacement () sampling setting. We presented a preliminary result on this topic in <Ref>, but developing the analogs of our non-asymptotic results for the case will require fundamentally new ideas. Finally, as we showed in <Ref>, our non-asymptotic lower bounds on the size of CIs can be easily extended to more general observation spaces, beyond the univariate case that was the main focus of this paper. Designing CIs/CSs that match these lower bounds for these general observation spaces using the betting framework is another interesting question for future work.

§.§ Acknowledgement

The authors acknowledge support from NSF grants IIS-2229881 and DMS-2310718.

[Audibert et al., 2009]
J.-Y. Audibert, R. Munos, and C. Szepesvári.
Exploration–exploitation tradeoff using variance estimates in
multi-armed bandits.
Theoretical Computer Science, 4100 (19):0
1876–1902, 2009.

[Bardenet and Maillard, 2015]
R. Bardenet and O.-A. Maillard.
Concentration inequalities for sampling without replacement.
Bernoulli, 210 (3):0 1361–1385, 2015.

[Bennett, 1962]
G. Bennett.
Probability inequalities for the sum of independent random variables.
Journal of the American Statistical Association, 570
(297):0 33–45, 1962.

[Bernstein, 1927]
S. Bernstein.
Theory of probability.
Gastehizdat Publishing House, 1927.

[Boucheron et al., 2013]
S. Boucheron, G. Lugosi, and P. Massart.
Concentration Inequalities: A Nonasymptotic Theory of
Oxford University Press, 02 2013.

[Cover, 1991]
T. M. Cover.
Universal portfolios.
Mathematical finance, 10 (1):0 1–29, 1991.

[Cutkosky and Orabona, 2018]
A. Cutkosky and F. Orabona.
Black-box reductions for parameter-free online learning in banach
In Conference On Learning Theory, pages 1493–1529. PMLR,

[Durrett, 2019]
R. Durrett.
Probability: Theory and Examples.
Cambridge Series in Statistical and Probabilistic Mathematics.
Cambridge University Press, 5th edition, 2019.

[Fan et al., 2015]
X. Fan, I. Grama, and Q. Liu.
Exponential inequalities for martingales with applications.
Electron. J. Probab, 200 (1):0 1–22, 2015.

[Hazan, 2016]
E. Hazan.
Introduction to online convex optimization.
Foundations and Trends in Optimization, 20
(3-4):0 157–325, 2016.

[Hazan et al., 2007]
E. Hazan, A. Agarwal, and S. Kale.
Logarithmic regret algorithms for online convex optimization.
Machine Learning, 69:0 169–192, 2007.

[Hoeffding, 1963]
W. Hoeffding.
Probability inequalities for sums of bounded random variables.
Journal of the American Statistical Association, 580
(301):0 13–30, 1963.

[Honda and Takemura, 2010]
J. Honda and A. Takemura.
An asymptotically optimal bandit algorithm for bounded support
In The Twenty Third Annual Conference on Learning Theory,
pages 67–79. PMLR, 2010.

[Honda and Takemura, 2015]
J. Honda and A. Takemura.
Non-asymptotic analysis of a new bandit algorithm for semi-bounded
Journal of Machine Learning Research, 160
(113):0 3721–3756, 2015.

[Howard et al., 2021]
S. R. Howard, A. Ramdas, J. McAuliffe, and J. Sekhon.
Time-uniform, nonparametric, nonasymptotic confidence sequences.
The Annals of Statistics, 490 (2), 2021.

[Kaufmann et al., 2016]
E. Kaufmann, O. Cappé, and A. Garivier.
On the complexity of best-arm identification in multi-armed bandit
Journal of Machine Learning Research, 170
(1):0 1–42, 2016.

[Kelly, 1956]
J. L. Kelly.
A new interpretation of information rate.
The Bell System Technical Journal, 350 (4):0
917–926, 1956.

[Lai and Robbins, 1985]
T. L. Lai and H. Robbins.
Asymptotically efficient adaptive allocation rules.
Advances in applied mathematics, 60 (1):0
4–22, 1985.

[Maurer and Pontil, 2009]
A. Maurer and M. Pontil.
Empirical Bernstein bounds and sample variance penalization.
In The Twenty Second Annual Conference on Learning Theory,

[Orabona and Jun, 2021]
F. Orabona and K.-S. Jun.
Tight concentrations and confidence sequences from the regret of
universal portfolio.
arXiv preprint arXiv:2110.14099, 2021.

[Serfling, 1974]
R. J. Serfling.
Probability inequalities for the sum in sampling without replacement.
The Annals of Statistics, pages 39–48, 1974.

[Shafer, 2021]
G. Shafer.
Testing by betting: A strategy for statistical and scientific
Journal of the Royal Statistical Society: Series A (Statistics
in Society), 1840 (2):0 407–431, 2021.

[van der Vaart, 1998]
A. van der Vaart.
Asymptotic Statistics.
Cambridge Series in Statistical and Probabilistic Mathematics.
Cambridge University Press, 1998.

[Waudby-Smith and Ramdas, 2020]
I. Waudby-Smith and A. Ramdas.
Confidence sequences for sampling without replacement.
Advances in Neural Information Processing Systems,
33:0 20204–20214, 2020.

[Waudby-Smith and Ramdas, 2023]
I. Waudby-Smith and A. Ramdas.
Estimating means of bounded random variables by betting.
Journal of the Royal Statistical Society Series B
Methodological, 2023.

§ ADDITIONAL BACKGROUND

In this section, we collect some of the results from prior work that we use often in proving our theoretical results. We begin by recalling the first Borel-Cantelli lemma <cit.>.
[Borel-Cantelli lemma]

Consider a probability space $(\Omega, \mc{F}, \mathbb{P})$, and let  $\{E_n \in \mc{F}: n \geq 1\}$ denote a sequence of events, satisfying $\sum_{n =1}^{\infty} \mathbb{P}\lp E_n \rp < \infty$. Then, we have

\begin{align}
\mathbb{P}\lp \limsup_{n \to \infty} E_n \rp = \mathbb{P}\lp  \cap_{N\geq 1} \cup_{n \geq N} E_n \rp = \mathbb{P}\lp E_n \, i.o.\rp =0.
\end{align}

The $i.o.$ above is an abbreviation for “infinitely often”.

We next recall Wald's equation <cit.>,  a standard result about the expected value of a sum of a random number of random variables.
[Wald's equation]

Suppose $Z_1, Z_2, \ldots$ are with $\mathbb{E}[Z_i] = b$, and let $S_n$ denote the sum $\sum_{i=1}^n Z_i$ for all $n \geq 1$. Then, if $T$ is any stopping time with $\mathbb{E}[T]<\infty$, we have $\mathbb{E}[S_T] = b \mathbb{E}[T]$.

Next, we recall a useful inequality derived by Fan et al., 2015 that we use in obtaining lower bounds on the wealth process used in the betting CI/CS.
[Fan's inequality]

For any $x \geq -1$, and $\lambda \in (0,1)$, we have the following

\begin{align}
\log(1+\lambda x) \geq \lambda x - 4 \psi_E(\lambda) x^2, \quad \text{where} \quad
\psi_E(\lambda) = \frac{-\lambda - \log(1-\lambda)}{4}.
\end{align}

This was first proved by Fan et al., 2015.

Finally, we state some results derived by Waudby-Smith and Ramdas, 2023 while analyzing their betting CIs/CSs, that will be used several times in our proofs.

Consider the bets $\{\lambda_{t,n}: 1 \leq t \leq n\}$ as used in the definition of in (<ref>). Then, we have the following:

\begin{align}
\lim_{n \to \infty} \frac{1}{\sqrt{n}} \sum_{t=1}^n \lambda_{t,n} = \sqrt{ \frac{2 \log(2/\alpha)}{\sigma^2}}, \quad \text{and} \quad
\lim_{n \to \infty} \sum_{t=1}^n 4\psi_E(\lambda_{t,n}) (X_t - \muhat_{t-1})^2 = \sqrt{ \log(2/\alpha)}.
\end{align}

§ PROOF OF THE LIMITING WIDTH OF BETTING CI (THEOREM <REF>)

Following the proof outline presented in <Ref>, we break down the proof into several smaller components.
First, we recall some notation:

\begin{align}
\lambda_{t,n} = \sqrt{\frac{2 \log(2/\alpha)}{n V_{t-1}}},\; \text{ for } t\geq 2,  \quad \text{where} \quad
V_{t-1} =  \frac{1}{t-1} \lp \frac{1}{4} +  \sum_{i=1}^{t-1}(X_i - \muhat_{t-1})^2 \rp, \quad \text{and} \quad
\muhat_{t-1} = \frac{1}{t-1} \sum_{i=1}^{t-1} X_i,
\end{align}

We begin by showing that the betting CI is contained in a larger CI whose width converges to $0$ at the order-optimal $\mc{O}(1/\sqrt{n})$ rate.

Suppose we construct a betting CI based on $n$ observations $X_1, \ldots, X_n$ drawn from $P^*$, with bets $\{\lambda_{t,n}: t \geq 1\}$ for all $m \in [0,1]$, where $\lambda_{1,n} = 0$, and $\lambda_{t,n}$ is as defined above for $t \geq 2$.
Then, the betting CI is contained inside a larger CI (that we denote by $\CIfan$), defined as

\begin{align}
\CIbet \subset \CIfan \defined \lb \frac{ \sum_{t=1}^n\lambda_{t,n} X_t}{\sum_{t=1}^n\lambda_{t,n}} \pm \frac{ \log(2/\alpha) + \sum_{t=1}^n \psi_E(\lambda_{t,n})}{\sum_{t=1}^n \lambda_{t,n}} \rb.
\end{align}

As a result, we have the following bound on the limiting width of the betting CI:

\begin{align}
\limsup_{n \to \infty} \,\sqrt{n} \times |C_n^{\text{bet}}|   \; \stackrel{a.s.}{\leq} \; c_1 \defined \sqrt{ \frac{ \log(2/\alpha)}{2}}\lp \sigma + \frac{1}{\sigma}\rp < \infty.
\end{align}

The proof of this statement is in <Ref>.
While this result implies that the width of the betting CI converges to zero at the correct (i.e., $1/\sqrt{n}$) rate, it does not explain the  fact that the width of the betting CI shrinks appropriately when the variance ($\sigma^2$) is small. Nevertheless, this result will play an important role in obtaining a more refined analysis of the betting CI width, as it allows us to concentrate our analysis in a narrow band of width $\approx 4c_1/\sqrt{n}$ for large enough $n$. First, we state a technical lemma about the concentration of the following mean and variance estimates:

\begin{align}
\muhat_n \defined \frac{1}{n} \sum_{i=1}^n X_i, \quad \mutilde_n \defined  \big(  \sum_{t=1}^n \lambda_{t,n} X_t\big) / \big( \sum_{t=1}^n \lambda_{t,n}\big), \quad \text{and} \quad \sigmatilde_n^2 = \frac{1}{n} \sum_{i=1}^n (X_i - \mu)^2.  \label{eq:empirical-estimates-1}
\end{align}

Let $E_t$ denote the intersection of the following three events:

\begin{align}
&E_{t,1} = \lbr |\muhat_t - \mu| \leq \sqrt{\log(t)/t} \rbr, \quad
E_{t,2} = \lbr |\sigmatilde_t^2 - \sigma^2_X| \leq \sqrt{\log(t)/t} \rbr, \\ \text{and} \quad
&E_{t,3} = \lbr |\mutilde_t - \muhat_t| \leq (11/\sigma^2)\sqrt{\log(t)/t} + \mc{O}\lp \log(t)/t  \rp\rbr.
\end{align}

Then we have $\mathbb{P}\lp E_t^c \rp \leq 8/t^2$.

We prove this result by showing that $\mathbb{P}\lp E_{t,i}^c \rp \leq 2/t^2$ for $i=1,2,$ and $\mathbb{P}(E_{t,3}^c) \leq 4/t^2$ by using some standard concentration techniques for bounded observations. Since our objective is to study the asymptotic behavior of the width, we have not attempted to optimize the $\sigma$-dependence of deviation in the definition of $E_{t,3}$. The details are in <Ref>.

The two results above set the stage for our main approximation result that will lead to the improved first-order limiting width bound.  To state this result, we  introduce the following new  CI, based on <Ref>:

\begin{align}
\widetilde{C}_n = [\mutilde_n - 2c_1/\sqrt{n}, \,\mutilde_n + 2c_1/\sqrt{n}],
\end{align}

where recall that $\mutilde_n$ is the empirical estimate introduced in (<ref>), and the constant $c_1$ was defined in the statement of <Ref>. Furthermore, introduce the random time

\begin{align}
N \defined \sup \lbr n \geq 1: |\CIfan| > \frac{4 c_1}{\sqrt{n}} \rbr,  \label{eq:def-N}
\end{align}

where $\CIfan$ was introduced in <Ref>.  We can now state our approximation result.

The random variable $N$ is finite almost surely, and for all $n \geq N$ we have $\CIbet \subset \CIfan \subset \CItilde$.
Furthermore, the following is true for all $m$ lying in $\CItilde$:

\begin{align}
\boldsymbol{1}_{n \geq N} \times \lp \sum_{t=1}^n \psi_E(\lambda_{t,n})(X_t-m)^2 \boldsymbol{1}_{E_{t-1}} \rp \; \stackrel{a.s.}{\leq} \; \sum_{t=1}^n \psi_E(\lambda_{t,n}) (X_t-\muhat_{t-1})^2 + o(1),
\end{align}

where $\boldsymbol{1}_{E_0} \eqas 1$, and  $E_t$ for $t \geq 1$ was introduced in <Ref>.

The proof of this statement is in <Ref>.

We now have all the components to show that the first-order limiting width is upper bounded by $\gamma_1^{(\prpieb)} \defined \sigma\sqrt{2 \log(2/\alpha)}$.  According to the definition of the random time $N$, we have

\begin{align}
\CIbet \subset \widetilde{C}_n, \quad \text{under the event} \{N \leq n\}.
\end{align}

Next, recall the definition of the wealth process used in the statement of <Ref>:

\begin{align}
W_n(m) = \frac{1}{2} \lp W_n^+(m) + W_n^-(m) \rp, \quad \text{where} \quad
W_n^{\pm}(m) = \prod_{t=1}^n \lp 1 \pm \lambda_{t,n} \lp X_t - m \rp \rp.
\end{align}

As a simple consequence of this choice of the wealth process, we note that  the betting CI  satisfies

\begin{align}
\CIbet \subset \cap_{a \in \{-, +\} } \lbr m \in [0,1]: \log(W_n^a(m)) < \log(2/\alpha) \rbr.
\end{align}

This immediately implies the following  under $\{N \geq n\}$:

\begin{align}
\CIbet & \subset \lbr m \in \CItilde: \log\lp W_n^+(m) \rp < \log(2/\alpha) \rbr \\
&\subset \bigg\{ m \in \widetilde{C}_n: \sum_{t=1}^n \lambda_{t,n}(X_t-m) - 4 \sum_{t=1}^n \psi_E(\lambda_{t,n})(X_t-m)^2 < \log(2/\alpha) \bigg\}. \label{eq:betting-ci-proof-4}
\end{align}

This inclusion is due to a direct application of Fan's inequality (<Ref>) in the definition of $W_n^+(m)$. On rearranging (<ref>), we obtain

\begin{align}
\CIbet \subset \bigg\{ m \in \widetilde{C}_n:  m \geq \mutilde_n  - \frac{ \log(2/\alpha) + 4\sum_{t=1}^n \psi_E(\lambda_{t,n})(X_t-m)^2}{\sum_{t=1}^n \lambda_{t,n}} \bigg\}, \label{eq:betting-ci-proof-5}
\end{align}

where recall that $\mutilde_n$ was introduced in (<ref>). Repeating the above argument with $W_n^-(m)$, we get (again, under the event $\{n \geq N\}$)

\begin{align}
\CIbet \subset \bigg\{ m \in \widetilde{C}_n:  m \leq \mutilde_n  + \frac{ \log(2/\alpha) + 4\sum_{t=1}^n \psi_E(\lambda_{t,n})(X_t-m)^2}{\sum_{t=1}^n \lambda_{t,n}} \bigg\}, \label{eq:betting-ci-proof-15}
\end{align}

Let $m_*$ and $m^*$ denote the (random) smallest and largest values respectively, that satisfy the condition in (<ref>) and (<ref>).  Then, we have the following:

\begin{align}
\boldsymbol{1}_{n \geq N} \times |\CIbet| \; \stackrel{a.s.}{\leq} \; m^* - m_* =  \frac{2 \log(2/\alpha) + 4 \sum_{t=1}^n \psi_E(\lambda_{t,n}) \lp (X_t-m^*)^2 + (X_t-m_*)^2 \rp }{\sum_{t=1}^n \lambda_{t,n}}
\end{align}

Next, note  that since $N$ is known to be finite almost surely from <Ref>, we have

\begin{align}
\gammabet \defined \limsup_{n \to \infty} \sqrt{n} \times \frac{|\CIbet|}{2} \eqas \limsup_{n \to \infty} \sqrt{n} \times \frac{|\CIbet|}{2} \times \boldsymbol{1}_{n \geq N}.
\end{align}

Thus, (<ref>) and (<ref>) imply the bound:

\begin{align}
\gammabet \leq \limsup_{n \to \infty}\; \sqrt{n} \times \frac{ \log(2/\alpha) + 2 \sum_{t=1}^n \psi_E(\lambda_{t,n}) \lp (X_t-m^*)^2 + (X_t-m_*)^2 \rp }{\sum_{t=1}^n \lambda_{t,n}} \times \boldsymbol{1}_{n \geq N}.
\end{align}

This limit appears similar to the width of the improved EB-CI of Waudby-Smith and Ramdas, 2023, with the only difference being the second term in the numerator. We first recall that

\begin{align}
\lim_{n \to \infty} \frac{1}{\sqrt{n}} \sum_{t=1}^n \lambda_{t,n}  \eqas \sqrt{2 \log(2/\alpha)/\sigma^2}.
\end{align}

Thus, to complete the proof, we need to show the following, with $U_t \defined (X_t-m^*)^2 + (X_t-m_*)^2$:

\begin{align}
\lim_{n \to \infty} \lp 2 \sum_{t=1}^n \psi_E(\lambda_{t,n}) \,U_t \rp \times \boldsymbol{1}_{n \geq N} \; \eqas \;  \sqrt{\log(2/\alpha)}.
\end{align}

Since we already know that $\lim_{n \to \infty} 4 \sum_{t=1}^n \psi_E(\lambda_{t,n})(X_t-\muhat_{t-1})^2 \eqas \sqrt{\log(2/\alpha)}$, it suffices to prove

\begin{align}
\limsup_{n \to \infty} \lp 2 \sum_{t=1}^n \psi_E(\lambda_{t,n}) \,U_t \rp \times \boldsymbol{1}_{n \geq N} \stackrel{a.s.}{\leq}
\lim_{n \to \infty} 4 \sum_{t=1}^n \psi_E(\lambda_{t,n})(X_t-\muhat_{t-1})^2.
\end{align}

We recall from <Ref> that $\mathbb{P}(E_t^c) \leq 8/t^2$, which means that $\sum_{t=1}^\infty \mathbb{P}(E_t^c) < \infty$. An application of Borel-Cantelli lemma then implies that

\begin{align}
\mathbb{P}\lp E_t^c \text{ infinitely often} \rp = 0 \; \Longleftrightarrow \;
\mathbb{P}\lp E_t \text{ all but finitely many times} \rp = 1.
\end{align}

As a consequence of this, we have

\begin{align}
\limsup_{n \to \infty} \lp 2 \sum_{t=1}^n \psi_E(\lambda_{t,n}) \,U_t {\boldsymbol{1}_{E_{t-1}}} \rp \times \boldsymbol{1}_{n \geq N} \eqas \limsup_{n \to \infty} \lp 2 \sum_{t=1}^n \psi_E(\lambda_{t,n}) \,U_t \rp \times \boldsymbol{1}_{n \geq N}
\end{align}

The final step is provided by <Ref>, which gives us

\begin{align}
\boldsymbol{1}_{n \geq N} \lp 2\sum_{t=1}^n \psi_E(\lambda_{t,n}) U_t \boldsymbol{1}_{E_{t-1}}\rp \stackrel{a.s.}{\leq}
\lp 4 \sum_{t=1}^n \psi_E(\lambda_{t,n})(X_t - \muhat_{t-1})^2 \rp + o(1).
\end{align}

Taking the limit, we obtain

\begin{align}
\limsup_{n \to \infty} \lp 2 \sum_{t=1}^n \psi_E(\lambda_{t,n}) \,U_t {\boldsymbol{1}_{E_{t-1}}} \rp \times \boldsymbol{1}_{n \geq N} &\stackrel{a.s.}{\leq} \lim_{n \to \infty} 4 \sum_{t=1}^n \psi_E(\lambda_{t,n})\lp (X_t - \muhat_{t-1})^2 \rp + o(1) \\
& = \sqrt{\log(2/\alpha)}.
\end{align}

The last equality follows from the fact that $\psi_E(\lambda_{t,n}) \approx \lambda_{t,n}^2/8 = \log(2/\alpha)/(4n \sigmahat_t^2) \approx \log(2/\alpha)/(4n\sigma^2)$, as recalled in <Ref>.   This completes the proof.

§.§ Proof of Lemma <ref>

To prove this statement, we recall the definition of the betting CI used in <Ref>:

\begin{align}
&\CIbet = \{m \in [0,1]: W_n(m) < 1/\alpha\}, \\ \text{where} \quad
&W_n(m) =  \frac{1}{2} \lp W_n^+(m) + W_n^-(m) \rp, \quad
\text{and} \quad
W_n^{\pm}(m) = \prod_{t=1}^n \lp 1 \pm \lambda_{t,n}(X_t - m) \rp.
\end{align}

Since both $W_n^{+}(m)$ and $W_n^{-}(m)$ are nonnegative by construction, it implies that

\begin{align}
\{m: W_n(m) < 1/\alpha \} \subset \{m: W_n^{+}(m) < 2/\alpha  \} \cap \{m: W_n^{-}(m) < 2/\alpha  \}.
\end{align}

We now consider the two events in the right side of the above display, and use Fan's inequality to obtain an interval containing them. In particular, Fan's inequality (<Ref>) implies the following lower bound

\begin{align}
\log(W_t^+(m)) = \sum_{t=1}^n \log(1 + \lambda_t(X_t-m)) \geq \sum_{t=1}^n \lambda_t (X_t-m) - 4\psi_E(\lambda_t) (X_t-m)^2.
\end{align}

Now, since $(X_t-m)^2 \leq 1$ for all $t \geq 1$ and $m \in [0,1]$, we can further lower bound $W_t^+(m)$ as follows:

\begin{align}
\log(W_t^+(m)) \geq \sum_{t=1}^n \lambda_t(X_t-m) - \psi_E(\lambda_t).
\end{align}

This leads us to the following inclusion:

\begin{align}
\{m: W_n^+(m) < 2/\alpha\} &\subset \lbr m \in [0,1]:  \sum_{t=1}^n \lambda_{t,n}(X_t-m) - \sum_{t=1}^n \psi_E(\lambda_{t,n}) \rbr,  \label{eq:betting-fan-1}\\
& \defined [L, 1], \quad \text{where} \quad
L = \frac{\sum_{t=1}^n \lambda_t X_t}{\sum_{t=1}^n\lambda_t}  - \frac{\log(2/\alpha) + \sum_{t=1}^n \psi_E(\lambda_t)}{\sum_{t=1}^n\lambda_t}.
\end{align}

To simplify the notation, we will use

\begin{align}
\mutilde_n = \frac{\sum_{t=1}^n \lambda_t X_t}{\sum_{t=1}^n\lambda_t}, \quad
w_n = \frac{\log(2/\alpha) + \sum_{t=1}^n \psi_E(\lambda_t)}{\sum_{t=1}^n\lambda_t}.  \label{eq:width-of-Fan-CI}
\end{align}

Next, we repeat the same argument for $W_n^-(m)$, to obtain

\begin{align}
\{m: W_n^-(m) < 2/\alpha\} &\subset \lbr m \in [0,1]:  \sum_{t=1}^n \lambda_{t,n}(m-X_t) - \sum_{t=1}^n \psi_E(\lambda_{t,n}) \rbr, \label{eq:betting-fan-2}  \\
& \defined [0, U], \quad \text{where} \quad
U = \mutilde_n + w_n.
\end{align}

Combining (<ref>) and (<ref>), we get

\begin{align}
\CIbet &\subset \{m: W_n^+(m) < 2/\alpha\} \cap \{m: W_n^-(m) < 2/\alpha\} \\
& \subset \CIfan \defined [L, U] = \lb \mutilde_n  \pm w_n\rb. \label{eq:CI-Fan-def}
\end{align}

To conclude the proof, we recall that (<Ref>):

\begin{align}
&\sum_{t=1}^n \lambda_t \eqas \sqrt{ \frac{ 2 \log(2/\alpha) n }{\sigma^2}}\lp 1 + o(1) \rp, \quad \text{and} \quad \sum_{t=1}^n \psi_E(\lambda_t) \eqas \frac{\log(2/\alpha)}{\sigma^2}\lp 1  + o(1) \rp.
\end{align}

This implies that the width of the CI satisfies:

\begin{align}
\limsup_{n \to \infty} \sqrt{n} \times \frac{|\CIbet|}{2} \leq   \sqrt{\log(2/\alpha)/2}\lp \sigma + 1/\sigma \rp = c_1.
\end{align}

This completes the proof.

§.§ Proof of Lemma <ref>

The proof of concentration of $\muhat_t$ and $\sigmatilde_t$ follows by a direct application of Hoeffding's inequality. For the concentration of $\mutilde_t$, we need a slightly more involved peeling argument, because it relies on a uniform concentration of $\sigmatilde_i$ for all $1 \leq i \leq t$.

Concentration of sample mean and variance. Recall the events

\begin{align}
E_{t,1} = \lbr |\muhat_t - \mu| \leq \sqrt{\log(t)/t} \rbr, \quad
E_{t,2} = \lbr \left\lvert \frac{1}{t} \sigmatilde_t^2 - \sigma^2 \right\rvert \leq \sqrt{\log(t)/t} \rbr,
\end{align}

where $\muhat_t = (1/t) \sum_{i=1}^t X_i$, and $\sigmatilde_t^2 = (1/t)\sum_{i=1}^t (X_i-\mu)^2$.
Since the observations are bounded, Hoeffding's inequality implies that

\begin{align}
\mathbb{P}\lp |\muhat_t - \mu| \leq \sqrt{ \log(2/\delta)/(2t)} \rp \leq \delta, \quad \text{and} \quad
\mathbb{P}\lp |\sigmatilde_t^2 - \sigma^2| \leq \sqrt{ \log(2/\delta)/(2t)} \rp \leq \delta.
\end{align}

Setting $\delta \leftarrow 2/t^2$ in the two inequalities above leads to the conclusion $\mathbb{P}\lp E_{i,t}^c \rp \leq 2/t^2$, for $i=1,2$.

Concentration of $\boldsymbol{\mutilde_t}$. We now look at the remaining event, $E_{t,3}$, defined as

\begin{align}
E_{t,3} = \lbr |\mutilde_t - \mu| \leq \sqrt{\log(t)/t} \rbr, \quad \text{where} \quad  \mutilde_t  \defined \big(  \sum_{t=1}^n \lambda_{t,n} X_t\big) / \big( \sum_{t=1}^n \lambda_{t,n}\big).
\end{align}

Since $\lambda_{t,n} = \sqrt{2 \log(2/\alpha) / (V_{t-1} n)}$, the estimate $\mutilde_t$ can we re-written as

\begin{align}
\mutilde_t = \frac{ \sum_{i=1}^t X_i/\sqrt{V_{i-1}} }{\sum_{i=1}^t 1/\sqrt{V_{i-1}}}, \quad \text{with } V_0 = 1/4, \text{ and } V_i = \frac{1}{i}\lp \frac{1}{4} +  \sum_{j=1}^{i}(X_j-\muhat_{j-1})^2 \rp, \quad \text{for } i \geq 2.
\end{align}

The above definition implies that to get a concentration result for $\mutilde_t$, we need to control the deviation of all $V_i$, for $i$ smaller than $t$.
By adding and subtracting $\mu$ in the definition of $V_i$, we can decompose $V_i$  into the following terms, for $i \geq 2$:

\begin{align}
V_i = \frac{1}{i} \sum_{j=1}^i (X_j-\mu)^2 + \frac{1}{i} \sum_{j=1}^i(\mu - \muhat_{j-1})^2 + \frac{2}{i} \sum_{j=1}^i(X_j-\mu)(\mu - \muhat_{j-1}).  \label{eq:mutilde-conc-1}
\end{align}

In the above display, we use the convention that $\muhat_{0}=0$. The expression stated in (<ref>) implies that in order to show the concentration of all $V_i$ around $\sigma^2$, it suffices to (i) show the uniform concentration of $\frac{1}{i}\sum_{j=1}^i (X_j-\mu)^2$ around $\sigma^2$, and (ii) a uniform concentration of $\muhat_i$ around $\mu$, for all $1 \leq i \leq t$. The concentration of the third term around $0$, then follows as a consequence of (ii). Thus, we will show that for the events, $G_{t,1} \defined \{\forall 1 \leq i \leq t: |\sigmatilde_i^2 - \sigma^2| \leq u_{i,t} \}$, and  $G_{t,2} \defined \{\forall 1 \leq i \leq t: |\muhat_i - \mu| \leq u_{i,t} \}$ with $u_{i,t} \defined \sqrt{3 \log(t)/i}$, the probabilities $\mathbb{P}\lp G_{t,1}^c \rp$ and $\mathbb{P}(G_{t, 2}^c)$ are both upper bounded by $2/t^2$.
Since the arguments are identical, we present the details only for $G_{t,1}$ below.

We begin by partitioning the set $[t] = \{1, 2, \ldots,  t\}$ into intervals of exponentially increasing lengths, $I_0, I_1, \ldots, I_{k_t}$, with $|I_j| = 2^j$. That is $I_0 = \{1\}$,  $I_1 = \{2, 3\}$, and $I_j = \{2^j, \ldots, 2^{j+1}-1\}$. The number of such intervals, is equal to $k_t= \lfloor \log_2(t) + 1\rfloor \leq \log_2t + 1$.  Since we want to control the probability of $G_{t,1}^c$ by $2/t^2$, we divide this `budget' equally among the $k_t$ intervals.  Let the elements of the $j^{th}$ interval be denoted by $\{i_j, i_{j+1}, \ldots, i_{j+1} -1 \}$, where we use the notation $i_j$ to denote the smallest element of the interval $I_j$, for all $1 \leq j \leq k_t$.
By using the time-uniform Hoeffding inequality in each interval, we get

\begin{align}
\mathbb{P}\lp \forall i \in I_j: |\sigmatilde_i^2 - \sigma^2| \leq \sqrt{\log(2/\delta_t)/(2 i_j)} \rp \leq \delta_t, \quad \text{where} \quad
\delta_t \defined \frac{2}{t^2 k_t} \geq \frac{2}{t^2 \lp \log_2 t + 1 \rp} \geq \frac{2}{t^3} .
\end{align}

Then, by taking a  union bound over the $k_t$ intervals, and using the fact that $2i_j \geq i$ for all $i \in I_j$, we get

\begin{align}
\mathbb{P}\lp G_{t,1} \rp = \mathbb{P}\lp \forall i \in [t]: |\sigmatilde_i^2-\sigma^2| \leq \sqrt{3\log(t)/i} \rp \geq 1-\frac{2}{t^2}.
\end{align}

An exactly analogous argument also implies that $\mathbb{P}(G_{t,2}) \geq 1-2/t^2$.

Going back to (<ref>), we see that under $E_{t,3} \defined G_{t,1} \cap G_{t,2}$, we have  for all $i \in \{2, \ldots, t\}$

\begin{align}
|V_i - \sigma^2| &\leq |\sigmatilde_i^2-\sigma|^2 + \frac{1}{i} \sum_{j=0}^{i-1}|\muhat_j-\mu|^2 + \frac{2}{i} \sum_{j=0}^i |\muhat_j - \mu|  \\
& \leq u_{i,t}^2 + \frac{1}{i} \sum_{j=0}^i u_{j,t}^2 + \frac{2}{i} \sum_{j=0}^{i-1} u_{j,t} = \frac{3 \log t}{i} + \frac{3 \log t}{i} \lp 1 + \sum_{j=1}^{i-1} \frac{1}{j} \rp + \frac{2\sqrt{3 \log t}}{i} \lp 1+ \sum_{j=1}^{i-1} \frac{1}{\sqrt{j}} \rp \\
& \leq \frac{3 \log t \log ei }{i} + \sqrt{\frac{12 \log t}{i}} \leq \sqrt{\frac{27 \log t}{i}} = u_i.
\end{align}

Plugging this deviation bound in the expression for $\mutilde_t$, we get  the following under $E_{t,3}$:

\begin{align}
\mutilde_t \leq \frac{ \sum_{i=1}^t X_i/\sqrt{1 - u_{i,t}/\sigma^2}}{\sum_{i=1}^t1/\sqrt{1 + u_{i,t}/\sigma^2}}, \quad \text{where} \quad
u_{i,t} = \sqrt{ \frac{3 \log t}{i}}.
\end{align}

A Taylor's expansion around $x=0$ for the functions $x \mapsto 1/\sqrt{1\pm x}$ implies

\begin{align}
\frac{1}{\sqrt{1-u_{i,t}/\sigma^2}} \leq 1 + \frac{u_{i,t}}{2\sigma^2} + \mc{O}\lp \frac{u_{i,t}^2}{\sigma^4} \rp, \quad \text{and} \quad
\frac{1}{\sqrt{1+u_{i,t}/\sigma^2}} \geq  1 - \frac{u_{i,t}}{2\sigma^2}.
\end{align}

Combining the above with the fact that $\sum_{i=1}^t u_{i,t} = \Theta \lp \sqrt{\log t/t} \rp$, we get

\begin{align}
\mutilde_t &\leq \lp \muhat_t +  \frac{1}{t} \sum_{i=1}^t X_i \frac{u_{i,t}}{\sigma^2} + \mc{O}(\log t/t) \rp \lp 1 + \frac{1}{t\sigma^2} \sum_{i=1}^t u_{i,t} + \mc{O}(\log t/t)\rp  \\
&= \muhat_t + \frac{1}{\sigma^2}\sqrt{ \frac{108 \log t}{t}}  + \frac{27 \log t}{\sigma^4 t} + \mc{O}\lp \frac{\log t}{t} \rp \\
& \leq \muhat_t + \frac{11}{\sigma^2}\sqrt{ \frac{\log t}{t}}  + \mc{O}\lp \frac{ \log t}{t} \rp.
\end{align}

Using same approximations, we can also obtain the required lower bound on $\mutilde_t$.

§.§ Proof of Lemma <ref>

$\boldsymbol{N}$ is finite almost surely. This is an easy consequence of <Ref>. In particular, recall that <Ref> shows that the width of $\CIfan$, denoted by $2w_n$, satisfies

\begin{align}
\lim_{n \to \infty} \sqrt{n} \times \frac{|\CIfan|}{2} = \lim_{n \to \infty} \sqrt{n} \times  w_n \eqas  c_1.
\end{align}

The exact expression of $w_n$ is in (<ref>).
Now, let $\Omega$ denote the probability $1$ event in which the limiting width of $\CIfan$ is $c_1$. Then, note that

\begin{align}
\Omega & \subset \cap_{a \in \mathbb{N}} \lbr w_n \leq \frac{c_1}{\sqrt{n}}\lp 1 + \frac{1}{a} \rp \text{ all but finitely many times} \rbr \\
&= \cap_{a \in \mathbb{N}}\lp  \cup_{m \in \mathbb{N}} \cap_{n \geq m} \lbr w_n \leq \frac{c_1}{\sqrt{n}}\lp 1 + \frac{1}{a} \rp \rbr \rp  \\
& \subset \cup_{m \in \mathbb{N}} \cap_{n \geq m} \lbr w_n \leq \frac{{2}c_1}{\sqrt{n}} \rbr = \{N < \infty \},
\end{align}

where the random variable $N$ was defined in (<ref>). Since $\mathbb{P}(\Omega)$ is $1$, the above inclusion implies that $N$ is finite almost surely. Also for all $n \geq N$, $w_n$ is smaller than $2c_1/\sqrt{n}$, which implies the required inclusion:

\begin{align}
\CIbet \subset \CIfan \subset \CItilde \quad \text{under } \{n \geq N\}.
\end{align}

The approximation result. For any $m \in [0,1]$, observe that

\begin{align}
(X_t - m)^2 &=  (X_t-\muhat_{t-1})^2 + (\muhat_{t-1} - m)^2 + 2 (\muhat_{t-1} - m)(X_t - \muhat_{t-1})  \\
& \stackrel{(i)}{\leq} (X_t-\muhat_{t-1})^2 + |\muhat_{t-1}-m| + 2|\muhat_{t-1}-m| \\
& = (X_t-\muhat_{t-1})^2 + 3|\muhat_{t-1} - \mu + \mu - \mutilde_n + \mutilde_n - m| \\
& \stackrel{(ii)}{\leq} (X_t-\muhat_{t-1})^2 + 3 \lp |\muhat_{t-1}-\mu| +  |\mu - \mutilde_n| + |\mutilde_n - m|\rp.
\end{align}

The inequality (i) uses the fact that $x^2 \leq |x|$ for $x \in (-1,1)$, and that $|X_t - \muhat_{t-1}|\leq 1$, while (ii) follows from two applications of the triangle inequality after adding and subtracting $\mu$, and $\mutilde_n$.

Since under the event $E_{t-1}$,  $|\muhat_{t-1} -  \mu|$ is $\mc{O}(\sqrt{\log t/t})$, we obtain

\begin{align}
(X_t - m)^2 \boldsymbol{1}_{E_{t-1}} \leq (X_t-\muhat_{t-1})^2 + 3 \lp  | \mutilde_n - m| + |\mutilde_n - \mu| \rp + \mc{O}(\sqrt{\log t/ t}).
\end{align}

Next, we will restrict our attention to a smaller subset of values of $m$ lying in $\CItilde$.
Under the event $\{n \geq N\}$, we know that $w_n \leq 2c_1/\sqrt{n}$, which implies that for all $m \in \widetilde{C}_n$, we have $|\mutilde_n - m|\boldsymbol{1}_{n \geq N} \leq 4c_1/\sqrt{n}$.

Thus, with $I_{t,n} \defined \boldsymbol{1}_{n \geq N} \times \boldsymbol{1}_{E_{t-1}}$, we have

\begin{align}
\sum_{t=1}^n\psi_{E}(\lambda_{t,n}) (X_t-m)^2\, I_{t,n} &\leq  \sum_{t=1}^n\psi_{E}(\lambda_{t,n}) (X_t-\muhat_{t-1})^2 +  \lp \frac{4c_1}{\sqrt{n}}+ |\mutilde_n - \mu|  \rp \sum_{t=1}^n\psi_{E}(\lambda_{t,n}) I_{t,n}  \\
& \quad + \mc{O}\lp \sum_{t=1}^n\psi_{E}(\lambda_{t,n})  \sqrt{ \frac{\log t}{t}} I_{t,n} \rp.
\end{align}

We will show that the last two terms converge to $0$ almost surely, to complete the proof. We do this, by observing the following three facts:

* $|\mutilde_n - \mu| \convas 0$. This is true because from the proof of <Ref>, we know that the probability  $\{ |\mutilde_n - \mu| > \mc{O}(\sqrt{\log n / n} ) \text{ infinitely often} \}$ is equal to $0$, which implies that the probability that $\{\mutilde_n \to \mu\}$ equals one, as required.

* The term $\sum_{t=1}^n \psi_E(\lambda_{t,n})$ converges almost surely to $\log(2/\alpha)/4 \sigma^2$. This was proved by Waudby-Smith and Ramdas, 2023.

* Finally, the term $\sum_{t=1}^n \psi_E(\lambda_{t,n}) \sqrt{\log t / t}$ converges almost surely to $0$. This is a simple consequence of the previous statement.

Together, these three facts imply the required result.

§ DETAILS OF THE NON-ASYMPTOTIC ANALYSIS OF BETTING CI (SECTION <REF>)

§.§ Proof of CI lower bound (Proposition <ref>)

The proof of this result proceeds in the following steps, as we outlined in <Ref>:

* First, using the method $\mc{C}$ for constructing valid CIs, we design a hypothesis test for distinguishing between two distributions with means separated by $2w(n, P, \alpha)$ (the width of the CI constructed by  the method $\mc{C}$ using $n$ observations from the distribution $P$). We show that this test controls both type-I and type-II errors at the level $\alpha$.

* Next, we show that the tight control over the type-I and type-II errors simultaneously implies a fundamental lower bound on the KL divergence between the two distributions. This follows essentially by an application of the data processing inequality for relative entropy.

* Finally, we translate this into a result about the information projections, and obtain the result by inverting this bound on $\klinf$ and $\klinfminus$.

Step 1: Design a hypothesis test using $\boldsymbol{\mc{C}}$.
Given observations $X_1, X_2, \ldots \simiid P^*$, we consider the hypothesis testing problem with $H_0: P^* = P$ and $H_1: P^* = Q$, with $\mu_Q > \mu_P + 2w(n, P, \alpha)$. For this problem, we can define a test $\Psi:\mc{X}^n \to \{0,1\}$, as follows:

\begin{align}
\Psi(X^n) = \begin{cases}
1, & \text{ if } \mu_Q \in C_n = \mc{C}(X^n, \alpha), \\
0, & \text{ otherwise}.
\end{cases}
\end{align}

Here $\Psi(X^n)=1$ indicates that the test rejects the null.
We now claim that under the stated assumption that $\mu_Q - \mu_P > 2 w(n, P, \alpha)$, the test $\Psi$ controls both, its type-I error and type-II error, at level $\alpha$. This is because, if $H_0$ is true, then $\mathbb{P}(\Psi = 1) = \mathbb{P}(\mu_Q \in C_n) \leq  \mathbb{P}(\mu_P \not \in C_n) \leq \alpha$.  Note that the inequality used the assumption that $\mu_Q - \mu_P > 2 w_n(n, P, \alpha)$, to infer that both $\mu_P$ and $\mu_Q$ cannot simultaneously lie in $C_n$.
Similarly, if $H_1$ is true, then $\mathbb{P}(\Psi=0) = \mathbb{P}\lp \mu_Q \not \in C_n \rp  \leq \alpha$, by definition of a level-$(1-\alpha)$ CI, and the separation assumption of $\mu_P$ and $\mu_Q$.

Step 2: Lower bound on $\boldsymbol{\dkl(P, Q)}$. Now, we observe the following:

\begin{align}
n \dkl\lp P, Q \rp = \dkl\lp P^{\otimes n}, Q^{\otimes n}  \rp \geq \dkl \lp \mathbb{E}_{P^{\otimes n}}[1-\Psi],\; \mathbb{E}_{Q^{\otimes n}}[1-\Psi] \rp. \label{eq:lower-bound-1-1}
\end{align}

The equality above is due to the standard chain rule for KL divergence, while the inequality follows from an application of the data processing inequality for KL divergence. Note that the last term in the display above denotes the KL divergence between two Bernoulli random variables.
Now, for any $p, q \in [0,1]$, we have

\begin{align}
\dkl(p, q) &= p \log(1/q) + (1-p)\log(1/(1-q)) + \lp p \log p + (1-p) \log (1-p) \rp \\
& \geq p \log(1/q) + 0 - h(p).
\end{align}

In the above display, $h(p)$ denotes the entropy (in nats) of the Bernoulli distribution with parameter $p$. Using the above inequality in (<ref>), and noting that $p \equiv \mathbb{E}_{Q^{\otimes n}}[\Psi] \geq 1-\alpha$, and $q \equiv \mathbb{E}_{P^{\otimes n}}[\Psi] \leq \alpha$, we obtain the following:

\begin{align}
\dkl(P, Q) \geq a(n, \alpha) \defined \frac{(1-\alpha) \log(1/\alpha) + \alpha \log(\alpha) + (1-\alpha) \log(1-\alpha)}{n} = \frac{\log\lp (1-\alpha)^{1-\alpha} \alpha^{2\alpha-1} \rp}{n}.  \label{eq:lower-bound-1-2}
\end{align}

To get the above inequality, we used the fact that for $\alpha < 0.5$, the binary entropy $h(p)$ is no larger than $ h(1-\alpha)$, since we have  $p \geq 1-\alpha$.

<Ref> says that the fact that we could construct a test to distinguish between $P$ and $Q$, with simultaneous control over the type-I and type-II errors, implies that the distributions $P$ and $Q$ must be sufficiently well-separated in terms of KL divergence.

Step 3: Connections to $\boldsymbol{\klinf}$.
Next, recall that for any $w \geq 0$, we can write

\begin{align}
\klinf(P, \mu_P+2w, \mc{P}_0) \defined \inf_{Q' \in \mc{P}^+_{0, \mu_P+2w}}\, \dkl(P, Q'),
\end{align}

where recall that $\mc{P}^+_{0, \mu_P + 2w}$ is used to represent the class of distributions $\{Q' \in \mc{P}_0: \mu_Q \geq \mu_P+2w\}$. Since it is known that $\klinf(P, \mu_P+2w, \mc{P}_0)$ is continuous in $w$,  we can also take the infimum over the set of all distributions $Q'$, whose mean is strictly greater than $\mu_P+2w$.
This observation, along with the inequality in (<ref>) leads us to the conclusion:

\begin{align}
\klinf\lp P, \mu_P + 2w(n, P, \alpha), \mc{P} \rp \geq a(n, \alpha). \label{eq:lower-bound-1-3}
\end{align}

To complete the proof,  we introduce the term

\begin{align}
w^{*, +} \equiv w^{*, +}(n, P, \alpha) & = \frac{1}{2} \lp \klinf(P, \cdot, \mc{P}_0)^{-1} \lp a(n, \alpha) \rp - \mu_P\rp. \label{eq:lower-bound-1-4}
\end{align}

Recall, that the inverse information projection is defined as

\begin{align}
\klinf(P, \cdot, \mc{P}_0)^{-1}(x) &\defined \inf \lbr m \geq \mu_P: \klinf(P, m, \mc{P}_0) \geq x \rbr.
\end{align}

Because of the continuity of $\klinf$, we note that the above infimum is achieved at some some $w^{*, +}$, which combined with (<ref>), gives us

\begin{align}
\klinf\big( P, \mu_P + 2 w(n, P, \alpha), \mc{P}_0 \big) \geq \klinf \lp P, \mu_P + 2w^{*, +}, \mc{P}_0 \rp.
\end{align}

Finally, the fact that $\klinf$ is monotonically increasing in the second argument implies the required $w(n, P, \alpha) \geq w^{*, +}(n, P, \alpha)$ completing the first part of the proof.

Repeating the exact same argument, now with $Q$ such that $\mu_Q < \mu_P - 2w(n, P, \alpha)$, we get the conclusion that $w(n, P, \alpha) \geq w^{*, -} \equiv w^{*, -}(n, P, \alpha)$, defined as

\begin{align}
w^{*, -} \equiv w^{*, -}(n, P, \alpha) & = \frac{1}{2} \lp \mu_P -  \klinfminus(P, \cdot, \mc{P}_0)^{-1} \lp a(n, \alpha) \rp\rp. \label{eq:lower-bound-1-5}
\end{align}

Combining these two results, we get that $w(n, P, \alpha) \geq \max\{w^{*, +}, w^{*, -} \}$, which completes the proof.

§.§ Proof of CI upper bound (Theorem <ref>)

We proceed in the following steps:

* First, we show that the wealth $W_n(m)$ after $n$ rounds for a betting strategy with logarithmic regret (such as the mixture method of <Ref>) grows exponentially, with the exponent approximately equal to the larger of the two terms: $\hatKplus(P^*, m)$, and $\hatKminus(P^*, m)$.

* Next, we obtain a lower bound on the wealth values in terms of the population analogs of the two information projection terms. This step is broken down into several smaller steps. In particular, we first obtain a more coarse CI with deterministic width that contains the betting CI (<Ref>). Then, in the next two lemmas (<Ref> and <Ref>), we obtain the required result about the concentration of the empirical information projection about its population value.

* The final expression for the deterministic envelope for the betting CI is obtained by inverting  the wealth process bound so obtained.

Step 1: Exponential growth of wealth. First we need to introduce the empirical versions of the two information projection terms, defined in (<ref>):

\begin{align}
\hatKplus(P^*, m) = \frac{1}{n} \sum_{t=1}^n \log \lp 1 + \lambda^*_+(m)(m-X_t) \rp, \quad \text{and}  \quad
\hatKminus(P^*, m) = \frac{1}{n} \sum_{t=1}^n \log \lp 1 + \lambda^*_-(m)(m-X_t) \rp. \label{eq:empirical-info-projection}
\end{align}

Here $\lambda_+^*$ and $\lambda_-^{*}$ denote the optimal betting fractions that define $\klinf$ and $\klinfminus$ respectively. Observe that for $X_1, \ldots, X_n$ drawn from $P^*$, the term $\widehat{K}_n^a(P^*, m)$ is an unbiased empirical estimate of $\text{KL}_{\inf}^a(P^*, m)$ for $a \in \{+, -\}$. Furthermore, we note here, that the two terms in the display above are different from $\klinf(\Phat_n, m)$ and $\klinfminus(\Phat_n, m)$.

Next, recall that the  regret incurred by the betting strategy (for all $m \in [0,1]$) is upper bounded by $c \log(n)$ for some fixed $c<2$. Then, we have the following for any $m \in [0,1]$:

\begin{align}
W_n(m) &= \prod_{t=1}^n \lp 1 + \lambda_t(m)(X_t-m) \rp = \exp \lp \sum_{t=1}^n \log\lp 1 + \lambda_t(m)(X_t-m) \rp \rp \\
& \geq \exp \lp \sup_{\lambda \in \lb \frac{-1}{1-m}, \frac{1}{m} \rb} \sum_{t=1}^n \log\lp 1 + \lambda(X_t-m) \rp - c\log(n) \rp \\
& \geq \exp \lp n \times \max \lbr \klinf(\Phat_n, m),\; \klinfminus(\Phat_n, m) \rbr - c \log(n) \rp \\
& \geq \exp \lp n \times \max \lbr \hatKplus(P^*, m),\; \hatKminus(P^*, m) \rbr - c \log(n) \rp.
\end{align}

The first inequality in the display above follows due to the logarithmic regret incurred by the mixture betting strategy, while the second inequality uses the definition of $\klinf$ and $\klinfminus$ for the empirical distribution $\Phat_n = (1/n) \sum_{i=1}^n \delta_{X_i}$ (with $\delta_x$ denoting the atomic distribution placing all the mass at $x$).
The third inequality uses the fact that the supremum is lower bounded by the value of the first term in the exponent at the  specific values $\lambda^*_+(m)$ and $\lambda^*_-(m)$. Thus, we have proved that the wealth process at any $m \in [0,1]$ grows exponentially, with the growth rate determined by the maximum of the two empirical information projection terms.

Step 2: A wider CS.  As in the proof of <Ref>, we will show that the betting CI at any time $n$ is also contained in a larger CI, that we denote by $\CItilde$, whose width is of the order $\mc{O}\lp \sqrt{\log n / n}\rp$. While this bound, by itself, is quite loose, it plays a crucial role in proving the stronger $\klinf$-dependent bound, by allowing us to focus our analysis on a small band of $m$ values.

The betting CI based on $n$ observations is contained inside a larger CI, denoted by $\CItilde$, whose width satisfies

\begin{align}
\frac{|\CItilde|}{2} = \sigmahat_n \sqrt{\frac{2\log(3n^c/\alpha)}{n}  }  \leq  \sqrt{\frac{2\log(3n^c/\alpha)}{n}}.
\end{align}

In the above expression,  $c$ is from the regret of the betting scheme, and $\sigmahat_n^2$ is the empirical variance based on the  $n$ observations.   In other words, the event $E_1 = \{\mu \in [\muhat_n \pm b_n]\}$, where $b_n = 2\sqrt{2\log(3n^c/\alpha)/n}$, occurs with probability at least $1-\alpha/3$.

The proof of this statement is in <Ref>.

Step 2: Concentration of information projection. In this step, we now replace the empirical information projections with their appropriate population counterparts. To do this we need a high probability concentration bound on the deviation of $\hatKplus$ and $\hatKminus$ from their expectations. We will show this in two steps, stated as <Ref> and <Ref>.

Fix a $\delta \in (0,0.1]$, and let $m>\mu$ be small enough to ensure that $|\lambda^*(m)| \leq \delta$. Then, we have

\begin{align}
\frac{ |\Delta_m|(1-\delta)^2}{\sigma^2 + \Delta_m^2} \leq |\lambda^*(m)| \leq \frac{ |\Delta_m|(1+\delta)^2}{\sigma^2 + \Delta_m^2}, \quad \text{where} \quad \Delta_m \defined \mu - m.
\end{align}

In other words, the above lemma (proved in <Ref>) tells us that in the neighborhood of $\mu$, the optimal betting fraction depends almost linearly on $\Delta_m$. This result plays a vital role in our next result, about the concentration of the empirical information projection around its population values.

Recall the term $b_n \defined 2 \sqrt{2 \log(3n^c/\alpha)/n}$ from <Ref>, and suppose $n$ is large enough to ensure that for all $m \leq \mu + b_n$, we have $|\lambda^*(m)| \leq \delta$. Then, for any $\beta \in (0,1)$ the following inequality holds for $d(n, \alpha, \beta) \defined \frac{6\sqrt{2\log(3n^c/\alpha) \log(4/\beta)}}{n\sigma^2}$:

\begin{align}
&\mathbb{P}\lp \hatKplus(P^*, m) \geq \klinf - d(n, \alpha, \beta)   \rp \geq \beta,  \text{ for any } m \in [\mu, \mu + b_n].
\end{align}

Similarly, we also have

\begin{align}
&\mathbb{P}\lp \hatKminus(P^*, m) \geq \klinfminus - d(n, \alpha, \beta)   \rp \geq \beta,  \text{ for any } m \in [\mu - b_n, \mu].
\end{align}

The proof of this statement  uses approximation arguments to show that both $\klinf$ and $\hatKplus$ can be written as their first two Taylor's series terms, plus a negligible remainder term. Hence, to show the concentration of the empirical information projection terms, it suffices to show the concentration of the empirical mean and second moment around their population values. This can be achieved via two applications of Hoeffding's inequality, since all the observations are bounded. The details are in <Ref>.

Introduce the term $B = \lceil 2b_n/(1/n^2)\rceil$, and consider the following two girds of equally spaced points:

\begin{align}
\mc{M}_n^+ = \{\mu, \mu + 1/n^2, \ldots, \mu + B/n^2\}, \quad \text{and} \quad
\mc{M}_n^- = \{\mu, \mu - 1/n^2, \ldots, \mu - B/n^2\}.
\end{align}

The cardinality of both $\mc{M}_n^+$ and $\mc{M}_n^-$ is equal to $B+1 = \Theta\lp n^{3/2} \sqrt{\log(n/\alpha)}\rp$, which we loosely upper bound by $n^2/8$.
Then, using <Ref>,  we can define a probability $1-2\alpha/3$ event $E_2$ as follows:

\begin{align}
&E_2 =  \bigcap_{a \in \{+, -\}}\;  \bigcap_{m_i \in \mc{M}_n} \;\lbr \widehat{K}_n^a(P^*, m_i) \geq  \text{KL}_{\inf}^a\lp P^*, m_i \rp - d(n, \alpha) \rbr, \label{eq:event-E2}\\
\text{where} \quad &d(n,\alpha) \equiv d\lp n, \alpha,\, \frac{2\alpha}{3}\times \frac{8}{2n^2}\rp \defined \frac{6 \sqrt{2 \log(3n^c/\alpha)\log(3n^2/\alpha)}}{n \sigma^2} \leq \frac{9\log(3n^2/\alpha)}{n\sigma^2}. \label{eq:d-n-alpha-def}
\end{align}

Step 3: Invert the wealth process.   Let $E$ denote the event $E_1 \cap E_2$, where $E_1$ was defined in the statement of <Ref>, and $E_2$ is defined in (<ref>) above.  Introduce the notation

\begin{align}
K^{\max}(P^*, m) = \max \lbr \klinf(P^*, m),\; \klinfminus(P^*, m) \rbr.
\end{align}

Then, under the event $E$, we can lower bound the wealth at any $m_i \in \mc{M}_n \defined \mc{M}_n^+ \cup \mc{M}_n^-$ as

\begin{align}
W_n(m_i) \geq \exp \lp n K^{\max}(P^*, m_i) - c \log(n) - 9\log(3n^2/\alpha)/\sigma^2 \rp. \label{eq:wealth-lower-bound-1}
\end{align}

Under the event $E$, the betting CI at time $n$ can be stated as

\begin{align}
\CIbet = \{m \in [\mu \pm 2b_n]: W_n(m) < 3/\alpha \}.
\end{align}

We have used $3/\alpha$ here, because we used the remaining $2\alpha/3$ on the event $E_2$.
Let $U$ and $L$ denote the end points in the intersection of this CI and the grid $\mc{M}_n $. That is,

\begin{align}
U = \max\{m_i: m_i \in \mc{C}_n \cap \mc{M}_n\}, \quad \text{and} \quad
L = \min\{m_i: m_i \in \mc{C}_n \cap \mc{M}_n\}.
\end{align}

Then, since the grid points are uniformly spaced at intervals of length $1/n^2$, it follows that the width of the CI, $2w(n, P^*, \alpha)$ is upper bounded by $U-L+2/n^2$. Using the lower bound on the wealth process stated in (<ref>), we obtain the following, with $b(n, \alpha) \defined \log(3n^2/\alpha)/n + d(n, \alpha)$ (recall that $d(n, \alpha)$ was defined in (<ref>)):

\begin{align}
U &= \max \{ m_i \in \mc{M}_n:  W_n(m_i) < \log(3/\alpha)\} \\
&\leq \max \lbr m_i \in \mc{M}_n: \exp \lp n K^{\max}(P^*, m_i) - 2 \log(n) - nd(n, \alpha) \rp < \log(3/\alpha)\rbr \\
& = \max \{m_i \in \mc{M}_n: \Kmax(P^*, m_i) < b(n, \alpha)\} \\
& \leq \sup \{m \in [0,1]: \Kmax(P^*, m) < b(n, \alpha)\} \\
& = \klinf(P^*, \cdot)^{-1}\lp b(n, \alpha)\rp.
\end{align}

The first inequality in the above display uses the lower bound on $W_n(m_i)$, as stated in (<ref>), while the second inequality uses the fact that the value of supremum increases by increasing the domain.
An analogous argument gives us the lower bound $L \geq \klinfminus(P^*, \cdot)^{-1}\lp b(n, \alpha)\rp$, and together, these two results imply the statement:

\begin{align}
2 w(n, P^*, \alpha) &\leq U - L + \frac{2}{n^2}
\leq \klinf(P^*, \cdot)^{-1}\lp b(n, \alpha) \rp - \mu,\; \mu - \klinfminus(P^*, \cdot)^{-1}\lp b(n, \alpha) \rp + \frac{2}{n^2},
\end{align}

which implies the required conclusion

\begin{align}
w(n, P^*, \alpha) \leq \max \lbr \klinf(P^*, \cdot)^{-1}\lp b(n, \alpha) \rp - \mu, \;  \mu - \klinfminus(P^*, \cdot)^{-1}\lp b(n, \alpha) \rp \rbr + \frac{1}{n^2}.
\end{align}

§.§.§ Proof of <Ref>

Consider any $m \in [0,1]$, and observe that the wealth, $W_n(m)$, satisfies the following, due to the $c\log n$ regret of the betting scheme:

\begin{align}
W_n(m) \geq \exp \lp n \sup_{\lambda \in [-1/(1-m), 1/m]} \frac{1}{n} \sum_{t=1}^n \log(1+\lambda(X_t-m))  \,- c\log n\rp.
\end{align}

Since we can lower bound $\log(1+x)$ with $x-x^2/2$ for all $x \geq 0$, we have

\begin{align}
W_n(m) &\geq \exp \lp n \sup_{\lambda \in [-1/(1-m), 1/m]}  \lambda \Deltahat_m - \frac{\lambda^2}{2} \lp \sigmahat_n^2 + \Deltahat_m^2\rp  \,- c\log n\rp \label{eq:coarse-betting-CI-proof-1} \\
&\geq \exp \lp n \sup_{\lambda \in [-1/(1-m), 1/m]}  \lambda \Deltahat_m - \frac{\lambda^2}{2}  \,- c\log n\rp, \label{eq:coarse-betting-CI-proof-2}
\end{align}

where we have used the notation

\begin{align}
\Deltahat_m \defined \frac{1}{n}\sum_{i=1}^n X_i - m \;=\; \muhat_n - m, \quad \text{and} \quad
\sigmahat_n^2 = \frac{1}{n} \sum_{i=1}^n (X_i - \muhat_n)^2.
\end{align}

On optimizing the RHS of (<ref>)  for $\lambda$, we get that

\begin{align}
W_n(m) \geq \exp \lp  \frac{n \Deltahat_m^2}{2} - c \log(n) \rp.
\end{align}

Using this lower bound, we can construct a larger CI that contains the usual betting CI, as follows:

\begin{align}
\{m \in [0,1]: \log(W_n(m)) < \log(3/\alpha)\} = \CIbet  \subset \CItilde \defined \lbr m \in [0,1]: \frac{n\Deltahat_m^2}{2} - c \log(n) < \log(3/\alpha) \rbr.
\end{align}

On simplification, we get

\begin{align}
\CItilde = \lbr m: |m - \muhat_n| \leq \sigmahat_n\sqrt{ \frac{2\log(3n^c/\alpha)}{n} } \rbr.
\end{align}

§.§.§ Proof of <Ref>

First, we recall that the mapping $m \mapsto \lambda^*(m)$ is continuous. Hence, we can define

\begin{align}
\epsilon \equiv \epsilon(\delta, P^*) = \sup \{ \epsilon' > 0: \lambda^*(m)\leq \delta \text{ for all } m \in [\mu, \mu + \epsilon'] \}. \label{eq:epsilon-def}
\end{align}

Thus for all $m \in [\mu, \mu + \epsilon]$, the optimal bet satisfies $|\lambda^*(m)| \leq \delta$. Thus, in this proof, we assume $m$ is small enough to lie in $[\mu, \mu + \epsilon]$.

Next, we know from <cit.> that for $P^*$ with $\sigma>0$, the optimal betting fraction $\lambda^*(m)$ satisfies the following:

\begin{align}
\mathbb{E}\lb \frac{1}{1 + \lambda^*(m)(X-m)} \rb = 1, \quad \text{for all } \mu \leq m \leq 1- \frac{1}{\mathbb{E}\lb 1/(1-X) \rb}.
\end{align}

The above condition is obtained by simply calculating the derivative of the objective function in the dual formulation of $\klinf$ by differentiating inside the expectation, and setting it to zero $\lambda = \lambda^*(m)$.

Since $|X-m|\leq 1$ almost surely, and $|\lambda^*(m)| \leq \delta$ by assumption, we will now approximate the above expectation by using a Taylor's expansion of the function $f(x) = 1/(1+x)$ around $0$. In particular, we obtain

\begin{align}
\frac{1}{1 + \lambda^*(m)(X-m)} = 1 - \lambda^*(m)(X-m) + \lambda^*(m)^2 (X-m)^2 \frac{1}{\big(1 + \delta U \big)^2},
\end{align}

for some $[-1,1]$ valued random variable $U$. Considering the two extreme values of $U$, we obtain the following:

\begin{align}
1 - \lambda^*(m)\Delta_m + \lambda^*(m)^2(\sigma^2 + \Delta_m^2) \frac{1}{(1-\delta)^2} \geq 1,
\end{align}

which on simplification implies

\begin{align}
|\lambda^*(m)| \geq \frac{(1-\delta)^2 |\Delta_m|}{\Delta_m^2 + \sigma^2}.
\end{align}

A similar argument with the other extreme value of $U=1+\delta$, gives us the upper bound

\begin{align}
|\lambda^*(m)| \leq \frac{(1+\delta)^2 |\Delta_m|}{\Delta_m^2 + \sigma^2}.
\end{align}

This completes the proof.

§.§.§ Proof of <Ref>

Recall that, by the dual form of the information projection, we know that

\begin{align}
\klinf(P^*, m) = \mathbb{E}\lb \log \lp 1 + \lambda^*(m)(X-m) \rp \rb.
\end{align}

We approximate the integrand above by its Taylor's expansion around $0$, and obtain

\begin{align}
\klinf(P^*, m) &= \mathbb{E}\lb \lambda^*(m)(X-m) - \frac{\lambda^*(m)^2(X-m)^2}{2} + \frac{\lambda^*(m)^3 U}{3} \rb,
\end{align}

for some random variable $U$ taking values in $[-1,1]$. On taking the expectation, we get

\begin{align}
\klinf(P^*, m) = \lambda^*(m) \Delta_m - \frac{\lambda^*(m)^2}{2} \lp \sigma^2 + \Delta_m^2 \rp + \frac{\lambda^*(m)^3}{3} \mathbb{E}[U]. \label{eq:klinf-conc-proof-1}
\end{align}

Now recall that the term $\hatKplus$ is simply the empirical version of $\klinf$, that is,

\begin{align}
\hatKplus(P^*, m) = \frac{1}{n} \sum_{i=1}^n \log \lp 1 + \lambda^*(m)(X_i - m) \rp.
\end{align}

Hence, by the same approximation argument used above for analyzing $\klinf(P^*, m)$, we obtain

\begin{align}
\hatKplus(P^*, m) = \lambda^*(m) \Deltahat_m - \frac{\lambda^*(m)^2}{2} \lp \sigmahat_n^2 + \Deltahat_m^2 \rp + \frac{\lambda^*(m)^3}{3} \lp \frac{1}{n} \sum_{i=1}^n U_i \rp, \label{eq:klinf-conc-proof-2}