# The DALPHI annotation framework & how its pre-annotations can improve
annotator efficiency

Robert Greinacher1,2 & Franziska Horn3
1Cognitive Psychology and Cognitive Ergonomics, Technische Universität Berlin,
Berlin, Germany
2Institute of Neuroscience & Psychology, University of Glasgow, Glasgow, UK
3Machine Learning Group, Technische Universität Berlin, Berlin, Germany
<EMAIL_ADDRESS>
###### Abstract

Producing the required amounts of training data for machine learning and NLP
tasks often involves human annotators doing very repetitive and monotonous
work. In this paper, we present and evaluate our novel annotation framework
DALPHI, which facilitates the annotation process by providing the annotator
with suggestions generated by an automated, active-learning based assistance
system. In a study with 66 participants, we demonstrate on the exemplary task
of annotating named entities in text documents that with this assistance
system the annotation processes can be improved with respect to the quality
and quantity of produced annotations, even if the pre-annotations provided by
the assistance system are at a recall level of only 50%.

##  1 Introduction

Machine learning (ML) applications often require huge amounts of training
data, especially when deep neural networks are involved. While for natural
language processing (NLP) tasks such as named entity recognition (NER), large
corpora of annotated text documents are usually available for the English
language, other languages or specific domains are lacking the required
resources to be tackled with advanced ML algorithms.

Generating large quantities of training data, e.g., by annotating named
entities in text documents, is essential, but at the same time also a very
monotonous and time consuming task. We therefore challenge how this annotation
process is implemented in currently available annotation tools and developed a
new general purpose and open source annotation framework called DALPHI to
accelerate and improve the annotation of documents. Our system is customizable
to fit any kind of data and desired user interface (UI). Most importantly, it
provides an annotation work cycle where the human annotators are supported by
a constantly improving active-learning (AL) based assistance system, which
supplies pre-annotations using a task specific ML unit.

Our main hypothesis was that overseeing suggestions and correcting them as
appropriate compared to manually annotating a complete document will lower the
workload and therefore improve and accelerate the annotation task. However, as
these pre-annotations are generated by an ML model trained on previously
annotated data, they are most likely far from perfect. Therefore, we conducted
a study with 66 participants to evaluate our annotation system on the
exemplary task of NER, specifically to determine the level of recall our
automated assistance system would have to achieve for the pre-annotations to
be helpful.

###  1.1 Related work

Biemann et al. (2017) provide a comprehensive list of web-based, collaborative
annotation tools, most of which focus on text annotation (highlighting spans
and relations between spans). Two frequently used tools are GATE Teamware
Bontcheva et al. (2013) and WebAnno Yimam et al. (2013, 2014), which already
support the annotator by providing pre-annotations. However, these tools only
provide limited support for custom ML models to generate pre-annotations with
or for active learning setups, i.e., to automatically prioritize those
documents for annotation that would be most informative for the ML model.
Additionally, their UIs can not be easily customized to fit novel annotation
tasks.

Previous studies already showed that annotator productivity can be enhanced by
an assistance system generating pre-annotations, but most of these studies
were conducted using only rule-based assistance systems Day et al. (1997);
Névéol et al. (2011); Lingren et al. (2013) or ML models operating at
uncontrolled levels of accuracy Komiya et al. (2016); Ganchev et al. (2007).
However, as ML models vary in their accuracy depending on the available
training data and task, it is important to determine what level of performance
such an assistance system needs to achieve for the generated pre-annotations
to accelerate and improve the annotation process. While this was previously
investigated for the task of part-of-speech (POS) tagging Ringger et al.
(2008); Fort and Sagot (2010), these studies were not performed using an
annotation tool but rather a synthetic testbed. Therefore it remains unclear
how these results translate to real annotation settings.

##  2 The DALPHI annotation framework

Figure 1: The DALPHI UI for text annotations.

Our novel open source web-based annotation framework is called _DALPHI Active
Learning Platform for Human Interaction_. It can be customized to fit
different data formats and to provide task specific UIs. An example setup for
the annotation of text documents with named entities is shown in Fig. 1.

Figure 2: The processing and data flow cycle of the DALPHI framework. Light
document symbols are annotated, dark are not.

The annotation workflow of DALPHI is structured as follows (Fig. 2): The
annotation of a whole corpus is split into several iterations. First, the
documents that should be annotated in the current annotation iteration are
retrieved and then presented one by one, together with the corresponding pre-
annotations, to the annotator in the UI. The human annotator then annotates
the documents by correcting the pre-annotations and completing misses. When
all documents of the current iteration are annotated, they are merged back
with the rest of the corpus. Before the next iteration, the task specific ML
unit can be retrained on these newly annotated documents to generate better
pre-annotations for the remaining unannotated documents. Furthermore, to
ensure that maximally informative training samples are annotated, the batch of
documents for the next iteration can be selected using active learning, i.e.,
based on how certain the ML model was when generating the pre-annotations.

While in the present study we focus on generating annotations for a NER task,
DALPHI can easily be used to generate training data for other tasks as well.
For this, specific components of the system, such as the UI, need to be
adapted, which should be straightforward given the open source collection of
examples we provide together with the DALPHI implementation. DALPHI, as well
as an example setup for NER with pre-annotations generated by a classifier
from NLTK NLTK Project (2017), is available on
GitHub.111https://github.com/Dalphi

##  3 Evaluation & Results

An automated assistance system can not be expected to provide perfect pre-
annotations. To systematically compare the impact of pre-annotations with
different levels of correctness (in terms of recall) on the human annotators,
we used three assistance systems that produced correct pre-annotations 10%,
50%, or 90% of the time. The 10% level represents the lower bound of what we
assumed might be a useful assistance and could, for example, correspond to the
performance achieved by an ML model at the beginning of the annotation process
when almost no training data is available. 50% recall can realistically be
achieved with an ML model trained on moderate amounts of data,22250% recall is
less than the median of the performance in the GermEval competition; the top
German NER systems perform below 80% recall Benikova et al. (2014). which
makes this scenario the most relevant in our comparison. The last system (90%)
is currently out of reach for many languages and domains. Nevertheless,
studying its impact on the perceived monotony and workload is important for
designing a novel, user-centred system.

To get pre-annotations at these controlled recall levels, we did not use an
actual ML model, but instead simulated the assistance system by using a
predefined lookup table with randomized chunk / label combinations.
Nevertheless, to get realistic performances, it is very important that the
_types of errors_ that are made by the simulated assistance system at a
specific recall level match those that would be made by a real ML model. We
therefore used a state of the art Conditional Random Field (CRF) NER model
Lample et al. (2016) to predict the labels for the corpus we used in our
study. We identified five possible types of annotation errors, ranging from
not annotated at all to wrongly annotated in terms of label and span (Table
1). The same distribution of errors made by the CRF classifier (Dist. column
in Table 1) was then used to generate the pre-annotations of the simulated
assistance system.

Table 1: Possible annotation errors. Green labels are person names, blue labels are company names. Label | Span | Description | Example | Dist.
---|---|---|---|---
✓ | ✓ | correct | CEO Lorene Duck raises wages. | 57.8%
✓ | ✗ | correct label, wrong span | CEO Lorene Duck raises wages. | 7.8%
✗ | ✓ | wrong label, correct span | CEO Lorene Duck raises wages. | 3.1%
✗ | ✗ | wrong label and span | CEO Lorene Duck raises wages. | 0.0%
✗ | ✗ | unnecessary annotation | CEO Lorene Duck raises wages. | 1.5%
- | - | missing annotation | CEO Lorene Duck raises wages. | 29.8%

For our study we chose 14 recent German news articles (approx. 6000 words in
total), selected by length and count of possible annotations. They were
presented one by one and split into their 73 paragraphs. We compiled the
collection to be as diverse as possible in order to mute performance
differences of the participants with different expertise and affinities.

Figure 3: The phases of the study for all groups.

The study was conducted in lab conditions on site with 66 participants who had
no prior annotation experience. After a short training phase, where the
subjects could get familiar with the task and the UI, they then annotated the
texts on their own in the main part of the experiment. This main part was
divided into four blocks, where the assistance was alternating present in two
out of four blocks (Fig. 3). According to our gold standard there were 310
named entities (persons or organizations) to annotate in the entire
texts.333We created this gold standard manually ourselves and it, together
with other data, is available online at https://gitlab.com/pasubda/dalphi-
study-data/. Annotations were distributed as equally as possible between the
four blocks. After each block, the participants were asked to fill in a
questionnaire about their perceived workload and monotony of the task. A post-
processing pipeline matched the 66 differently annotated corpora with the gold
standard to quantify the errors. For the statistical analysis, differences
between blocks with and without assistance were calculated to assess changes
using one sample t-tests.

As shown in Fig. 4, our lower-bound assistance system with 10% correct pre-
annotations did not significantly facilitate the process in any of the three
performance dimensions. However, the level 50% and level 90% assistance
systems yielded significant improvements compared to the baseline (no
assistance system). Regarding the perceived workload of the task, we found a
significant difference between the assistance with 90% recall and the
baseline, but none of the assistance systems significantly improved the
perception of monotony of the annotation task.

Figure 4: All three levels of the assistance (90%: green, 50%: blue, 10%: red)
regarding the three performance dimensions and the exploratory questionnaire
data analysis. The length of each bar is the mean value of the condition, the
whiskers depict the standard error of the mean in both directions.

##  4 Discussion

In this paper we introduced our novel annotation framework DALPHI and examined
if and how the task of manual data labelling can be improved by using pre-
annotations as generated by our system. In particular, we showed that it is
possible to increase the performance of the annotators in terms of producing
more correct and complete annotations in less time, provided that the
assistance system achieves a certain level of recall. Furthermore, we used
questionnaires in order to answer if the task itself can be improved: While a
very advanced assistance system can reduce the perceived workload, the
perceived monotony of the task remains unchanged.

An assistance system achieving 90% recall is not realistic for many tasks.
However, crafting a model that produces correct annotations in 50% of the
cases is feasible and already improves the annotation process by increasing
the quality of the produced annotations (yielding an average of 87.6% correct
annotations compared to the baseline performance of 83.9%) and reducing the
number of missed annotations by 36%.444This data describes the average
performance of a single annotator. To generate labelled datasets, the
annotations of several annotators are usually combined to yield better results
Brants (2000). Furthermore, an assistance system can save time, i.e. money: A
typical corpus for an NLP task contains tens of thousands of sentences and
annotations (e.g. GermEval 2014: 31,297 sentences and 37,926 named entity
annotations Biemann et al. (2014)). Without any assistance, our participants
needed an average of 8.2$\pm$2.3 seconds per correct named entity annotation.
Annotating the GermEval corpus at this pace would have taken more than two
weeks of full time work.555(8.2 seconds $\times$ 37,926 annotations); 3,600
seconds per hour; 8 hours per day $\to$ 10.8 days. By employing an assistance
system with only 50% recall, the average time per annotation was reduced by
about 1.7$\pm$3.6 seconds, which would have saved more than two work days in
the illustrated example.6666.5 seconds per annotation $\to$ 8.6 days.

In our evaluation we only examined three levels of recall for the automated
assistance system, which already required a large number of study participants
to get statistically meaningful results. In future work, it might be
interesting to explore recall levels in between the studied boundaries to
determine the sweet spot where a ML assistance model starts to facilitate the
annotation workflow. Furthermore, it should be examined to what extent our
results generalize to more complex tasks than NER, such as relationship
extraction or POS tagging Ringger et al. (2008); Fort and Sagot (2010).
Another important open question is how the different kinds of errors in the
annotation process (Table 1) influence the performance of the annotators. The
performance of ML models is subject to a trade-off between precision and
recall, therefore if certain errors in the pre-annotations are easier to
correct than other (e.g., it might be easier to remove a wrong annotation than
to identify a missing one), the assistance system could be adapted with this
in mind.

We hope that by improving the annotation process with our open source DALPHI
framework, we can facilitate the creation of larger training datasets for more
languages and specialized domains and therefore help bring (supervised) ML
technologies to more people.

## Acknowledgements

We would like to thank Dr. Nils Backhaus and the Chair of Cognitive Psychology
and Cognitive Ergonomics of the Technische Universität Berlin for their
support. DALPHI was developed by Hannes Korte, Arik Grahl, and Robert
Greinacher, who were at the time employed by Implisense GmbH. Franziska Horn
acknowledges funding from the Elsa-Neumann scholarship from the universities
of Berlin.

## References

  * Benikova et al. (2014) Darina Benikova, Chris Biemann, Max Kisselew, and Sebastian Pado. 2014.  Germeval 2014 named entity recognition: Companion paper.  _Proceedings of the KONVENS GermEval Shared Task on Named Entity Recognition, Hildesheim, Germany_ , pages 104–112.
  * Biemann et al. (2017) Chris Biemann, Kalina Bontcheva, Richard Eckart de Castilho, Iryna Gurevych, and Seid Muhie Yimam. 2017.  Collaborative Web-based Tools for Multi-layer Text Annotation.  _The Handbook of Linguistic Annotation’, Text, Speech, and Technology book series, Springer Netherlands_.
  * Biemann et al. (2014) Chris Biemann, Sebastian Pado, Darina Benikova, and Max Kisselew. 2014.  GermEval 2014 Named Entity Recognition Shared Task.
  * Bontcheva et al. (2013) Kalina Bontcheva, Hamish Cunningham, Ian Roberts, Angus Roberts, Valentin Tablan, Niraj Aswani, and Genevieve Gorrell. 2013.  GATE Teamware: a web-based, collaborative text annotation framework.  _Language Resources and Evaluation_ , 47(4):1007–1029.
  * Brants (2000) Thorsten Brants. 2000.  Inter-annotator Agreement for a German Newspaper Corpus.  In _LREC_.
  * Day et al. (1997) David Day, John Aberdeen, Lynette Hirschman, Robyn Kozierok, Patricia Robinson, and Marc Vilain. 1997.  Mixed-initiative development of language processing systems.  In _Proceedings of the Fifth Conference on Applied Natural Language Processing_ , pages 348–355. Association for Computational Linguistics.
  * Fort and Sagot (2010) Karën Fort and Benoît Sagot. 2010.  Influence of pre-annotation on pos-tagged corpus development.  In _Proceedings of the fourth linguistic annotation workshop_ , pages 56–63. Association for Computational Linguistics.
  * Ganchev et al. (2007) Kuzman Ganchev, Fernando Pereira, Mark Mandel, Steven Carroll, and Peter White. 2007\.  Semi-automated named entity annotation.  In _Proceedings of the linguistic annotation workshop_ , pages 53–56. Association for Computational Linguistics.
  * Komiya et al. (2016) Kanako Komiya, Masaya Suzuki, Tomoya Iwakura, Minoru Sasaki, and Hiroyuki Shinnou. 2016.  Comparison of annotating methods for named entity corpora.  In _Proceedings of the 10th Linguistic Annotation Workshop held in conjunction with ACL 2016 (LAW-X 2016)_ , pages 59–67.
  * Lample et al. (2016) Guillaume Lample, Miguel Ballesteros, Sandeep Subramanian, Kazuya Kawakami, and Chris Dyer. 2016.  Neural architectures for named entity recognition.  _arXiv preprint arXiv:1603.01360_.
  * Lingren et al. (2013) Todd Lingren, Louise Deleger, Katalin Molnar, Haijun Zhai, Jareen Meinzen-Derr, Megan Kaiser, Laura Stoutenborough, Qi Li, and Imre Solti. 2013.  Evaluating the impact of pre-annotation on annotation speed and potential bias: natural language processing gold standard development for clinical named entity recognition in clinical trial announcements.  _Journal of the American Medical Informatics Association_ , 21(3):406–413.
  * Névéol et al. (2011) Aurélie Névéol, Rezarta Islamaj Doğan, and Zhiyong Lu. 2011.  Semi-automatic semantic annotation of pubmed queries: a study on quality, efficiency, satisfaction.  _Journal of biomedical informatics_ , 44(2):310–318.
  * NLTK Project (2017) NLTK Project. 2017.  NLTK 3.2.4 documentation: nltk.chunk.named_entity.
  * Ringger et al. (2008) Eric K Ringger, Marc Carmen, Robbie Haertel, Kevin D Seppi, Deryle Lonsdale, Peter McClanahan, James L Carroll, and Noel Ellison. 2008.  Assessing the costs of machine-assisted corpus annotation through a user study.  In _LREC_ , volume 8, pages 3318–3324.
  * Yimam et al. (2014) Seid Muhie Yimam, Chris Biemann, Richard Eckart de Castilho, and Iryna Gurevych. 2014.  Automatic annotation suggestions and custom annotation layers in webanno.  In _Proceedings of 52nd Annual Meeting of the Association for Computational Linguistics: System Demonstrations_ , pages 91–96.
  * Yimam et al. (2013) Seid Muhie Yimam, Iryna Gurevych, Richard Eckart de Castilho, and Chris Biemann. 2013.  WebAnno: A Flexible, Web-based and Visually Supported System for Distributed Annotations.  In _ACL (Conference System Demonstrations)_ , pages 1–6.


\end{align}

where the terms $\Deltahat_m$ and $\sigmahat_n^2$ are defined as

\begin{align}
\Deltahat_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}

Subtracting (<ref>) from (<ref>), we get

\begin{align}
\hatKplus(P^*, m) - \klinf(P^*, m) \geq \lambda^*(m) \lp \muhat_n - \mu\rp - \frac{\lambda^*(m)^2}{2}\lp \frac{1}{n} \sum_{i=1}^n (X_i-m)^2 - \sigma^2 - \Delta_m^2\rp - \frac{2\lambda^*(m)^3}{3}.
\end{align}

Note that to get the above inequality, we have used the fact that $(1/n)\sum_{i=1}^n U_i - \mathbb{E}[U] \geq -2$.
Thus, the above inequality implies that to obtain a concentration result for the information projection, it suffices to show the concentration of the mean and second moment of the observations. In particular, for any $\beta>0$, we have the following two results by Hoeffding's inequality:

\begin{align}
&|\muhat_n - \mu| \leq \sqrt{\log(4/\beta)/2n}, \quad \text{w.p. } \geq 1-\beta/2,  \\
\text{and} \quad
&\left\lvert \frac{1}{n}\sum_{i=1}^n (X_i-m)^2 - \sigma^2 - \Delta_m^2 \right\rvert \leq \sqrt{\log(4/\beta)/2n}, \quad \text{w.p. } \geq 1-\beta/2.
\end{align}

This implies the statement:

\begin{align}
&\mathbb{P}\lp \hatKplus(P^*, m) \geq \klinf(P^*, m) - d(n, m, \beta) \rp \geq 1- \beta, \\
\text{where} \quad
&d(n, m, \beta) \defined |\lambda^*(m)| \sqrt{ \lp \log(4/\beta)\rp / 2n} \,+\, \frac{|\lambda^*(m)|^2}{2} \frac{\log(4/\beta)}{2n} + \frac{2 |\lambda^*(m)|^3}{3}.
\end{align}

Next, recall that <Ref> implies that$|\lambda^*(m)|  \leq \lp |\Delta_m|(1+\delta)^2\rp/\lp \Delta_m^2 + \sigma^2\rp$. If $\delta \leq 0.1$, then it is easy to check that $(1+\delta)^2 \leq (1+\delta)^4\leq (1+\delta)^6 \leq 2$. This implies that

\begin{align}
d(n, m, \beta) \leq \frac{2 |\Delta_m| \sqrt{\log(4/\beta)}}{\sigma^2\sqrt{2n}} + \frac{\Delta_m^2 \log(4/\beta)}{n \sigma^4} + \frac{8|\Delta_m|^3}{3 \sigma^6}.  \label{eq:klinf-conc-proof-3}
\end{align}

Finally, note that $|\Delta_m|\leq 2\sqrt{2 \log(3n^c/\alpha)/n}$, which implies that $d(n, m, \beta) = \mc{O}\lp \sqrt{\log(n/\alpha)\log(4/\beta)}/n \rp$. In particular, if $n$ is large enough to ensure that
the second and third terms in the RHS of (<ref>) are smaller than the first (see precise conditions in <Ref>), we can upper bound the RHS of (<ref>) with three times the first term:

\begin{align}
d(n, m, \beta) \leq \frac{6\sqrt{2\log(3n^c/\alpha) \log(4/\beta)}}{n\sigma^2}.
\end{align}

The proof for the concentration of $\hatKminus$ is obtained under the same, $1-\beta$ probability event, following an exactly analogous approximation argument as above. We omit the details to reduce repetition.

§.§.§ Meaning of “$\boldsymbol{n}$ large enough” in <Ref>

To simplify the final statement of <Ref>, we have assumed that $n$ is large enough at several points in the proof. We collect all those assumptions here.

* In <Ref>, we assumed that $n$ was large enough to ensure the following for a fixed $\delta \in (0,0.1]$:

\begin{align}
b_n = 2\sqrt{\frac{2 \log(3n^c/\alpha)}{n}} < \epsilon(\delta, P^*) \defined \sup \{ \epsilon'>0: |\lambda^*(m)| \leq \delta, \text{ for all } m \in [\mu, \epsilon']\}.
\end{align}

Thus, for a fixed $\delta$ (say $0.1$), we know that there exists a finite $\epsilon \equiv \epsilon(\delta, P^*)>0$, and the above condition requires $n$ to be $\Omega \lp \frac{\log(1/\epsilon)}{\epsilon^2} \rp$.

* Next, in <Ref>, we assumed that $n$ is large enough to satisfy

\begin{align}
\min \lbr \frac{n\sigma^2}{\sqrt{\log(3n^c/\alpha) \log(3n^2/4\alpha)}}, \;
\frac{3\sigma^4\sqrt{n \log(3n^2/4\alpha)}}{32\sqrt{2}\log(3n^c/\alpha)}
\rbr \geq 1,
\end{align}

The above assumption on $n$ is made purely to absorb the two higher order terms into the first  term in (<ref>), for the value of $\beta = 8\alpha/3n^2$.

* Then, we assumed that $n$ is large enough to ensure
$4b_nn^2 +2 = 8n^{3/2} \sqrt{2 \log(3n^c/\alpha)}  + 2\leq n^2/8$.

We emphasize that, other than the first bullet point, the other assumptions  on $n$ are made to simplify the expression of the final statement of <Ref>, by absorbing the higher order terms. Also note that the random upper bound on the width of the betting CI, in terms of the empirical information projections, is valid for all $n \geq 1$.

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

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

The starting point of the proof of this result is to use the duality between confidence sequences and sequential tests. In particular, given observations $X_1, X_2, \ldots \simiid P^*$, we consider the hypothesis testing problem with

\begin{align}
H_0: P^*=Q, \quad \text{versus} \quad H_1: P^*=P.
\end{align}

We assume that the means of the two distributions ($\mu_P$ and $\mu_Q$) satisfy the constraint $\mu_Q-\mu_P = 2w_0 > 2w_e(n, P, \alpha)$.  We now proceed to the main steps of the proof.

Step 1: Sequential test. Unlike the proof of <Ref>, where the sample-size $n$ was fixed beforehand, for the above testing problem, we propose a sequential test that stops and makes it decision at a random time. In particular,  this, we define a sequential test that stops at a random time $T$, and makes a decision $\Psi \in \{0, 1\}$, as follows:

\begin{align}
T = \inf \{n \geq 1: |C_n| < \mu_Q-\mu_P\}, \quad \text{and} \quad
\Psi = \boldsymbol{1}_{Q \not \in C_T}. \label{eq:T-psi-def}
\end{align}

We now show that this sequential test controls both the type-I and type-II errors at level $\alpha$.

Under the assumptions of <Ref>, the stopping time $T$ is finite almost surely, and the test $\Psi$ introduced above satisfies the following:

\begin{align}
\mathbb{E}_{H_0}[\Psi] \leq \alpha, \quad \text{and} \quad
\mathbb{E}_{H_1}[\Psi] \geq 1-\alpha. \label{eq:lower-bound-2-0}
\end{align}

The proof of this lemma is in <Ref>.

Step 2: Lower bound on KL divergence. In the next step, using the properties of the stopping time $T$ and the test $\Psi$, we show that the KL divergence between $P$ and $Q$ must be at least as large as a term depending on $E_{H_1}[T]$ and the binary KL divergence between the test outcome $\Psi$ under the $H_1$ and $H_0$.

The KL divergence between $P$ and $Q$, with $Q$ such that $\mu_Q > \mu_P + 2w_e(n, P, \alpha)$,  must satisfy

\begin{align}
\dkl(P, Q) \geq \frac{ \log\lp (1-\alpha)^{1-\alpha} \alpha^{2\alpha-1} \rp }{\mathbb{E}_{H_1}[T]}, \label{eq:lower-bound-2-2}
\end{align}

where $T$ was defined in (<ref>).

The above result is reminiscent of the corresponding fixed-sample size inequality (<ref>), used in proving <Ref> in <Ref>.
The main difference here is that the expected stopping time under the alternative plays the role of the fixed sample-size $n$  in (<ref>).

Step 3: Lower bound on width. Now, recall that $\mu_Q - \mu_P = 2w_0$, where $w_0>w_e(n, P, \alpha)$ by construction. Then, we have for any $w \in (w_e(n, P, \alpha), w_0]$:

\begin{align}
\mathbb{E}_{H_1}[T] \;\leq\; \mathbb{E}[T_{w}(P, \alpha)] \;\leq\;   n.  \label{eq:w-eff-lower-bound-proof-temp}
\end{align}

The two inequalities above use the following facts:

* Since $T$ is the first time the width of the CS falls below $2w_0 = \mu_Q-\mu_P$, it follows that we have $T \leq T_w$ almost surely for all $w \leq w_0$. The first inequality then follows from the monotonicity of the stopping time in the width $w$.

* Since $w>w_e(n, P, \alpha)$ by assumption, we can always choose a $w'$, such that $w_e(n, P, \alpha) < w' \leq w$.  This means that, by the same argument as in the first step, we also have $\mathbb{E}[T_w(P, \alpha)] \leq \mathbb{E}[T_{w'}] \leq n$.

* Finally,  recall that $w_e(n, P, \alpha)$ is defined as $\inf \{w' \geq 0: \mathbb{E}[T_{w'} \leq n\}$. Hence, the previous step implies that $\mathbb{E}[T_{w'} \leq n$ for that choice of $w'$, which implies the second inequality in (<ref>).

Plugging the inequality from the previous display into (<ref>), and taking the infimum over all $Q \in \mc{P}_0^+\lp \mu_P + 2w_0\rp = \{Q' \in \mc{P}_0: \mu_{Q'} \geq \mu_P + 2w_0\}$, we get

\begin{align}
\klinf(P, \mu_P + 2w_0) = \inf_{Q \in \mc{P}_0^+\lp \mu_P + 2w_0\rp} \; \dkl(P, Q) \geq \frac{\log\lp (1-\alpha)^{1-\alpha} \alpha^{2\alpha-1} \rp}{n} \defined a(n, \alpha).
\end{align}

Next, we introduce the term $w^*(n, P, \alpha) = \inf \{w \geq 0: \klinf(P, \mu_P + 2w ) \geq a(n,\alpha) \}$, and use the above inequality, and the monotonicity of the information projection for a fixed $P$, to conclude that

\begin{align}
w_0 \geq w^*(n, P, \alpha).
\end{align}

The final step is to note that $w_0$ is an arbitrary value larger than $w_e(n, P, \alpha)$, and thus we have

\begin{align}
w_e(n, P, \alpha) = \inf \{w_0: w_0> w_e(n, P, \alpha)\}     \geq w^*(n, P, \alpha).
\end{align}

This concludes the first part of the proof that gets the lower bound on $w_e(n, P, \alpha)$ in terms of $\klinf$. By repeating the exact same steps, but with the distribution $Q$ such that $\mu_Q = \mu_P - 2w_0$, for any $w_0> w_e(n, P, \alpha)$, we get the other term in terms of $\klinfminus$. We omit the details to avoid repetition.

§.§.§ Proof of <Ref>

This result is proved by following the definitions of the terms.

Type-I error probability. We proceed as follows:

\begin{align}
\mathbb{E}_{H_0}[\Psi] &= \mathbb{P}_{H_0} \lp \mu_Q \not \in C_T \rp
= \sum_{n \in \mathbb{N}} \mathbb{P}_{H_0}\lp T=n, \mu_Q \not \in C_n \rp
\end{align}

In the last equality, we used the fact that the sets $\{E_n: n \geq 1\}$ with $E_n \defined \{T=n\}$ form a disjoint partition of the sample space (since $T<\infty$ almost surely under the conditions of <Ref>). Furthermore, for any $n \geq 1$, we have $\{\mu_Q \not \in C_n\} \subset \mc{E} \defined \{ \exists i \in \mathbb{N}: \mu_Q \not \in C_i\}$. Hence, we have $\mathbb{P}_{H_0}\lp T=n, \mu_Q \not \in C_n\rp \leq \mathbb{P}_{H_0}\lp E_n \cap \mc{E}\rp$, which implies

\begin{align}
\mathbb{E}_{H_0}[\Psi] & \leq \sum_{n\in \mathbb{N}} \mathbb{P}_{H_0}\lp E_n \cap \mc{E} \rp = \mathbb{P}\lp \mc{E} \rp
= \mathbb{P}\lp \exists n \in \mathbb{N}: \mu_Q \not \in C_n \rp \leq \alpha.
\end{align}

True detection probability. To obtain the lower bound on the true detection rate, we proceed as follows:

\begin{align}
\mathbb{E}_{H_1}[\Psi] &= \mathbb{P}_{H_1}\lp \mu_Q \not\in C_T \rp  = \mathbb{P}_{H_1}\lp \mu_Q \not \in C_T, \mu_P \in C_T \rp + \mathbb{P}_{H_1}\lp \mu_Q \not \in C_T, \mu_P \not \in C_T \rp \\
&\geq 0 +  \mathbb{P}_{H_1}\lp \mu_Q\not \in C_T, \mu_P \in C_T \rp \\
& \stackrel{(i)}{=} \mathbb{P}_{H_1}\lp \mu_P \in C_T \rp   = 1 -\mathbb{P}_{H_1}\lp \mu_P \not \in C_T \rp
\end{align}

The equality (i) above simply uses the fact that since the width of the CS at $T$ is smaller than $\mu_Q - \mu_P = 2w_0$, if $\mu_P \in C_T$, it automatically means that $\mu_Q \not \in C_T$. Finally, we note that

\begin{align}
\mathbb{P}_{H_1}\lp \mu_P \not \in C_T \rp &= \sum_{n \in \mathbb{N}} \mathbb{P}_{H_1}\lp T=n, \mu_P \not \in C_n \rp \\
&\leq \mathbb{P}_{H_1}\lp \exists n \in \mathbb{N}: \mu_P \not \in C_n \rp \leq \alpha.
\end{align}

This completes the proof.

§.§.§ Proof of <Ref>

We start by noting that the KL divergence between the $T$-fold product of $P$ and $Q$ can be written as the product the $\mathbb{E}_{H_1}[T]$ and $\dkl(P, Q)$. In particular, note that

\begin{align}
\dkl\lp  P^{\otimes T}, Q^{\otimes T} \rp  = \mathbb{E}_{H_1} \lb \sum_{t=1}^T \log \lp \frac{dP}{dQ} \rp\rb =
\mathbb{E}_{H_1}[\Psi] \mathbb{E}_P\lb \lp \frac{dP}{dQ} \rp \rb
= \mathbb{E}_{H_1}[\Psi]\, \dkl(P, Q).
\end{align}

The second equality above follows from an application of Wald's identity (<Ref>), using the assumption that both $\mathbb{E}_{H_1}[T]$ and $\dkl(P, Q)$ are finite. Next, we use the above inequality to obtain the following:

\begin{align}
\mathbb{E}_{H_1}[T] \dkl(P, Q) =  \dkl\lp P^{\otimes T}, Q^{\otimes T} \rp  \geq \dkl\lp \mathbb{E}_{H_1}[\Psi], \mathbb{E}_{H_0}[\Psi] \rp \geq \log\lp (1-\alpha)^{1-\alpha} \alpha^{2\alpha-1} \rp. \label{eq:lower-bound-2-1}
\end{align}

The first inequality above uses the  data-processing inequality for relative entropy with random stopping times, proved by <cit.>. The second inequality simply uses the bounds on the two probabilities stated in <Ref>, to further lower bound the binary KL divergence.
On re-arranging (<ref>), we immediately obtain the required lower bound on the KL divergence between $P$ and $Q$:

\begin{align}
\dkl(P, Q) \geq \frac{\log\lp (1-\alpha)^{1-\alpha} \alpha^{2\alpha-1} \rp}{\mathbb{E}_{H_1}[T]}.
\end{align}

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

Step 1: Connection to optimal wealth process. By assumption, we know that the regret incurred by the mixture betting strategy satisfies

\begin{align}
\sup_{m \in \text{supp}(P^*)} \mc{R}_n(m) \leq  c \log(n),
\end{align}

for some $c<2$. This implies that for any $m$,

\begin{align}
\log\lp W_n(m) \rp   &\geq \sup_{\lambda \in \lb \frac{-1}{1-m}, \frac{1}{m} \rb}  \sum_{i=1}^n \log \lp 1 + \lambda \lp m - X_i \rp \rp - c \log n  \\
& \geq \max_{\lambda \in \{\lambda_+^*, \lambda_-^*\}} \sum_{i=1}^n \log \lp 1 + \lambda \lp m - X_i \rp \rp - c \log n,
\end{align}

where $\lambda_a^*$ for $a \in \{-, +\}$ were introduced in (<ref>), and denote the optimal betting fractions used to define $\klinf$ and $\klinfminus$. For any $m  \in [0, 1]$ and $a \in \{-, +\}$, introduce the notation $W_n^{*, a}$, to denote the oracle wealth process corresponding to a betting strategy that always plays the bet $\lambda_a^*$.
Next, we introduce the following stopping times, based on the above lower bound on the wealth process:

\begin{align}
&\tau_w^+ = \inf \{n \geq 1:  \log \lp W_n^{*,+}(\mu+w) \rp - c \log n \geq \log(1/\alpha)\}, \\
\text{and} \quad
&\tau_w^- = \inf \{n \geq 1:  \log \lp W_n^{*, -}(\mu-w) \rp - c \log n \geq \log(1/\alpha)\}.
\end{align}

Our first key observation is that $T_w$ can be bounded by the two `oracle' stopping times introduced above.

For any $w>0$, $T_w = \inf \{n \geq 1: |C_n| \leq 2w \}$,  used to define the effective width, satisfies

\begin{align}
T_w \leq \tau_w^+ \vee \tau_w^- \defined \max \{ \tau_w^+, \tau_w^-\}.
\end{align}

Hence, the expected value of $T_w$ satisfies

\begin{align}
\mathbb{E}[T_w] \leq \mathbb{E}[\tau_w^+ \vee \tau_w^-] \leq \mathbb{E}[\tau_w^+  + \tau_w^-] \leq 2 \max_{a \in \{+, -\} } \mathbb{E}[\tau_w^a].  \label{eq:Tw-upper-bound}
\end{align}

The proof of this statement is in <Ref>.

In the rest of this section, we  will focus on deriving an upper bound on the expected value of $\tau_w^+$, for any $w>0$. An exactly analogous argument also gives us an upper bound on the expected value of $\tau_w^-$. Together, these results give us an upper bound on $\mathbb{E}[T_w]$, that will eventually lead to a bound on the effective width.

Step 2: Upper bound on the oracle stopping time. Let $m = \mu + w$, and introduce  $Z_i = \log(1 + \lambda^*_+(m)(m-X_i))$, and $S_n = \sum_{i=1}^n Z_i$, with $Z_0 = 0$. Note that $\mathbb{E}[Z_i] = \klinf(P, \mu+w)$ for $i \geq 1$, by the definition of $\lambda^*_+(\cdot)$. We now proceed as follows, for an arbitrary $N<\infty$:

\begin{align}
\mathbb{E}\lb S_{\tau_w^+ \wedge N} \rb &= \mathbb{E}\lb \sum_{i=1}^{\tau_w^+ \wedge N} Z_i \rb = 0+ \sum_{i=1}^N \mathbb{E}\lb (S_i - S_{i-1}) \boldsymbol{1}_{\tau_w^+ \geq i} \rb  =
\sum_{i=1}^N \mathbb{E}\lb (S_i - S_{i-1}) \boldsymbol{1}_{\tau_w^+ \geq i} \rb \\
& \stackrel{(i)}{=} \sum_{i=1}^N \mathbb{E}\lb \boldsymbol{1}_{\tau_w^+ \geq i} \mathbb{E}[S_i - S_{i-1}|\mc{F}_{i-1}] \rb  \stackrel{(ii)}{=}\mathbb{E}[\tau_{w} \wedge N] \klinf(P, \mu+w),
\end{align}

where $(i)$ follows from  the fact that $\{\tau_w^+ \geq i\} = \{\tau_w^+ \leq i-1\}^c$ is $\mc{F}_{i-1}$-measurable, since $\tau_w^+$ is a stopping time adapted to $(\mc{F}_i)_{i \geq 0}$. The equality $(ii)$ uses the optional stopping theorem for bounded stopping times.
Next, by <Ref>, $Z_i \leq C$ almost surely for some constant $C<\infty$ (depending upon the support of $P^*$ in <Ref>),  and thus we can conclude that

\begin{align}
\mathbb{E}[\tau_w^+ \wedge N] &= \frac{\mathbb{E}\lb S_{\tau_w^+ \wedge N} \rb}{\klinf(P, \mu+w)}  \leq \frac{\mathbb{E}[S_{\tau_w^+ \wedge N -1} + C ]}{\klinf(P, \mu+w)}  \\
& \leq \frac{\mathbb{E}[\log(1/\alpha) + C + c \log(\tau_w^+ \wedge N)]}{\klinf(P, \mu+w)}   \\
& \leq \frac{\log(1/\alpha) + C + c \log( \mathbb{E}[\tau_w^+ \wedge N])}{\klinf(P, \mu+w)},
\end{align}

where the second inequality uses the fact that, by definition of $\tau_w^+$, the value $S_{\tau_w^+ \vee N - 1}$ must be smaller than $\log(1/\alpha) + c \log(\tau_w^+)$, and the third inequality uses the concavity of $\log(\cdot)$, along with Jensen's inequality.

Finally, note that $N$ is arbitrary, and $\tau_w^+ \wedge N \convas \tau_w^+$ as $N \to \infty$. Hence, we have $\lim_{N \to \infty} \mathbb{E}[\tau_w^+ \wedge N] = \mathbb{E}[\tau_w^+]$ due to the monotone convergence theorem (MCT), which implies the following:

\begin{align}
\mathbb{E}[\tau_w^+] \leq \frac{\log(1/\alpha) + C + c \log( \mathbb{E}[\tau_w^+ ])}{\klinf(P, \mu+w)}.  \label{eq:tau-w-plus-1}
\end{align}

Step 3: Bound the oracle effective width. Now, for any fixed $n \in \mathbb{N}$, let $w_n^+$ denote the smallest value of $w$ for which $\mathbb{E}[\tau_w^+]$ is no larger than $n/2$.  By (<ref>), it follows that

\begin{align}
w_n^+ \leq \inf \lbr w \geq 0: \frac{ \log(1/\alpha) + C + c\log(n)}{\klinf(P, \mu+w)} \leq \frac{n}{2} \rbr = \klinf(P, \cdot)^{-1}\lp \frac{ 2\log (n^c/\alpha) + 2C}{n} \rp - \mu.
\end{align}

By repeating this argument of $\tau_w^-$, we get an upper bound on $w_n^-$

\begin{align}
w_n^- \leq \inf \lbr w \geq 0: \frac{ \log(1/\alpha) + C + c\log(n)}{\klinfminus(P, \mu-w)} \leq \frac{n}{2} \rbr = \mu -  \klinfminus(P, \cdot)^{-1}\lp \frac{ 2\log (n^c/\alpha) + 2C}{n} \rp.
\end{align}

Combining these two results, we get the required upper bound on the effective width, $w_e(n, P, \alpha) \leq \max \{w_n^+, w_n-\}$. That is,

\begin{align}
&w_n(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,  \label{eq:eff-w-betting-cs-1} \\
\text{where } &b(n,\alpha) = \frac{ 2\log (n^c/\alpha) + 2C}{n},
\end{align}

and $C$  is a  constant that depends on the support of $P^*$ (<Ref>).

Notice that for the oracle CS, we can follow the exact same strategy as we used in proving <Ref>, with the modification that the term $c$ (obtained from the leading constant of the regret bound) can be set to $0$. In other words, we simply modify the bound stated in (<ref>), by changing $b(n,\alpha)$ to $\frac{\log(2/\alpha) + C}{n}$. The additive term $C$ seems to be necessary to deal with the possible overshoot of the random walk $(S_n)_{n \geq 1}$.

§.§.§ Proof of Lemma <ref>

To prove this result, we first introduce the notation

\begin{align}
N_w^+ = \inf \{n \geq 1: C_n \cap (\mu+w, 1] = \emptyset \}, \quad \text{and} \quad N_w^- = \inf \{n \geq 1: C_n \cap [0, \mu-w) = \emptyset \}.
\end{align}

Thus, $N_w^+$ (resp. $N_w^-$) denotes the first time at which the betting CS has rejected all $m$ values larger than $\mu+w$ (resp. smaller than $\mu-w$). Note that because of the nested nature of CSs, if a point $m$ has been discarded by the CS at some time $N$, then it remains discarded for all $n \geq N$. This means, that at $n=\max\{N_w^+, N_w^-\}$, all values of $m$ outside the band $\mu \pm w$ have been rejected by the CS; or equivalently, the width of the CS is smaller than $2w$. By definition, this means that $T_w \leq \max\{N_w^+, N_w^-\}$.

To complete the proof, we will show that $N_w^+ \leq \tau_w^+$. Recall that $\tau_w^+$ was introduced in (<ref>).  An exactly analogous argument implies that $N_w^- \leq \tau_w^-$, which gives us the required statement of the lemma.  The first step is to observe that

\begin{align}
N_w^+ \leq \sup_{w' \geq w} \tau_{w'}^+.
\end{align}

This inequality is due to the fact that $\tau_w^+$ is the first $n$ at which a lower bound on the wealth $W_n(\mu+w)$ crosses the threshold of rejection $1/\alpha$. Thus $\tau_w^+$ is an upper bound on the first time the betting CS rejects $\mu+w$. We will now show that $\tau_w' \leq \tau_w$ almost surely for all $w' \geq w$. This will imply the required $N_w^+ \leq \sup_{w' \geq w} \tau_{w'}^+ \leq \tau_w^+$.

For $w' \geq w$, observe the following (all the inequalities and equalities for the rest of this proof hold a.s.):

\begin{align}
\mu + w' - X_t \geq  \mu + w - X_t, \quad \text{for all } t \geq 1,
\end{align}

which implies the following for all fixed values of $\lambda \in [0, 1/(1-\mu-w)]$:

\begin{align}
\sum_{t=1}^n \log \lp 1 + \lambda \lp \mu + w' - X_t \rp \rp    \geq \sum_{t=1}^n \log \lp 1 + \lambda \lp \mu + w - X_t \rp \rp.  \label{eq:tau-proof-1}
\end{align}

Now, taking the supremum over appropriate ranges of $\lambda$ leads to the following:

\begin{align}
\log \lp W^{*, +}_n (\mu + w')  \rp &= \sup_{\lambda \in \lb 0, \frac{1}{1 - \mu - w'} \rb} \sum_{t=1}^n \log \lp 1 + \lambda \lp \mu + w' - X_t \rp \rp \\
& \geq \sup_{\lambda \in \lb 0, \frac{1}{1 - \blue{\mu - w}} \rb} \sum_{t=1}^n \log \lp 1 + \lambda \lp \mu + w' - X_t \rp \rp \\
& \geq \sup_{\lambda \in \lb 0, \frac{1}{1 - \mu - w} \rb} \sum_{t=1}^n \log \lp 1 + \lambda \lp \mu + w - X_t \rp \rp \\
& = \log \lp W_n^{*, +}(\mu + w) \rp.
\end{align}

The first inequality above is due to the smaller domain of the supremum, while the second inequality is simply due to (<ref>). Since $\tau_w^+$ is the first time $\log W_n^{*,+}(\mu + w)$ crosses the boundary $\log(n^2/\alpha)$, this implies that $\tau_{w'} \leq \tau_{w}$.  Thus, we have proved

\begin{align}
N_w^+ \leq \sup_{w' \geq w} \tau_{w'}^+ \leq \sup_{w' \geq w} \tau_w^+ = \tau_w^+.
\end{align}

§ PROOF OF LOWER BOUNDS FOR MULTIVARIATE OBSERVATIONS

§.§ Proof of Proposition <ref>

The proof of this statement is a simple generalization of the steps involved in proving <Ref> to deal with multivariate observations.

Step 1: Design a hypothesis test using $\boldsymbol{\mc{C}}$.
Given observations $X_1, X_2, \ldots \simiid P^*$ for $\mc{X} = \reals^d$, 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}

As the method $\mc{C}$ constructs level-$(1-\alpha)$ CIs, the test $\Psi$ controls both type-I and type-II errors at level $\alpha$.

Step 2: Lower bound on $\boldsymbol{\dkl(P, Q)}$. Now, by the chain rule for KL divergence along with the data processing inequality, we obtain the following, with $a(n, \alpha) = \log\lp (1-\alpha)^{1-\alpha} \alpha^{2\alpha-1} \rp/n$:

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

Step 3: Connections to $\boldsymbol{\klinf}$. Since the right-most term in (<ref>) is independent of $Q$, we can take an infimum over all $Q: \|\mu_Q - \mu_P\|_2 > w(n, P, \alpha)$, to get

\begin{align}
\klinfmulti\lp P, 2w(n, P, \alpha), \mc{P} \rp \geq   \log\lp (1-\alpha)^{1-\alpha} \alpha^{2\alpha-1} \rp/n. \label{eq:multi-lower-bound-1-2}
\end{align}

The monotonicity of $\klinf$ then implies the required

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

§.§ Proof of Proposition <ref>

The proof of this result follows by appropriately modifying the steps used in proving the analogous univariate result in <Ref>. We omit some of the details involved in proving this result, as they closely follow the proof of <Ref>.

Given a stream of observations $X_1, X_2, \ldots \simiid P^*$,   we  set up  the following  hypothesis testing problem:

\begin{align}
H_0: P^*=Q, \quad \text{versus} \quad H_1: P^*=P.
\end{align}

We assume that the means of the two distributions ($\mu_P$ and $\mu_Q$) satisfy the constraint $\|\mu_Q-\mu_P\|_2 = 2w_0 > 2w_e(n, P, \alpha)$.

Step 1: Sequential test. We define a sequential test for this problem, that stops at a random time $T$, and makes a decision $\Psi \in \{0, 1\}$, as follows:

\begin{align}
T = \inf \{n \geq 1: \sup_{x, x' \in C_n} \|x-x'\|_2 < 2w_0\}, \quad \text{and} \quad
\Psi = \boldsymbol{1}_{\mu_Q \not \in C_T}.
\end{align}

Following the exact argument used in <Ref>, we can show that this test controls both the type-I and type-II errors at level $\alpha$.

Step 2: Lower bound on KL divergence. Next, by an application of the optional stopping theorem, and the data-processing inequality, we  show that the KL divergence between $P$ and $Q$ must satisfy:

\begin{align}
\dkl(P, Q) \geq \frac{ \log \lp (1-\alpha)^{1-\alpha} \alpha^{2\alpha-1} \rp}{\mathbb{E}_{H_1}[T]}. \label{eq:multi-lower-bound-2-1}
\end{align}

The steps involved to obtain this follow the same argument as in the proof of <Ref>.

Step 3: Lower bound on width. Now, recall that $\|\mu_Q - \mu_P\|_2 = 2w_0$, where $w_0>w_e(n, P, \alpha)$ by construction. Then, we have for any $w \in (w_e(n, P, \alpha), w_0)$:

\begin{align}
\mathbb{E}_{H_1}[T] \;\leq\; \mathbb{E}[T_{w}(P, \alpha)] \;\leq\;   n,
\end{align}

where $T_w = \inf \{n \geq 1: \sup_{x, x' \in \mc{C}_n} \|x-x'\|_2  \leq 2w\}$. The first inequality then uses the fact that $w < w_0$, and the second inequality follows from the definition of $w_e(n, P, \alpha)$ and the fact that $w>w_e(n, P, \alpha)$
Plugging the inequality into (<ref>), and taking the infimum over all $Q \in \mc{P}_0: \|\mu_Q - \mu_P\| \geq 2w_0$, we get

\begin{align}
\klinfminus(P, 2w_0, \mc{P}_0) \geq a(n, \alpha).
\end{align}

The required result then follows by taking the inverse information projection.

§ DETAILS OF THE CASE

We recall some existing results about constructing CIs in the framework of uniform sampling without replacement in <Ref>, and then present the proof of <Ref> in <Ref>.

§.§ Background on CIs

Hoeffding, 1963 showed the following relation between the expected value of a convex function of random variables drawn with, and without replacement.

Let $Y_1, \ldots, Y_n$ denote $\text{Uniform}(\Xsample_M)$ random variables drawn with replacement, and $X_1,  \ldots, X_n$ denote their analogs.
Then, for any continuous and convex function $f: \reals \to \reals$, we have

\begin{align}
\mathbb{E}\lb f \lp \sum_{i=1}^n X_i \rp \rb  \leq \mathbb{E}\lb f \lp \sum_{i=1}^n Y_i \rp \rb.
\end{align}

Using the above relation, we can extend the usual Hoeffding's inequality to be valid for the case.

For a fixed sample size $n$, we have the following for any $\epsilon>0$.

\begin{align}
\mathbb{P}\lp \lv \frac{1}{n} \sum_{i=1}^n X_i - \mu\rv \geq \epsilon \rp \leq 2 \exp \lp -2n\epsilon^2 \rp.
\end{align}

However, the above result does not capture the fact that the uncertainty about the mean, $\mu = \frac{1}{M} \sum_{i=1}^M x_i$, rapidly decays as the sample size $n$ approaches $M$, the total number of items. This was addressed by Serfling, 1974, who obtained an improved version of Hoeffding's inequality, with the term $n$ replaced by $\frac{n}{1 - (n-1)/M}$.
Bardenet and Maillard, 2015 obtained a slight improvement of Serfling's result, replacing the $(n-1)$ with $n$, and then used it to obtain variants of Hoeffding-Serfling, Bernstein-Serfling, and Empirical-Bernstein-Serfling inequalities.

We now recall the Bernstein-Serfling confidence interval (CI) obtained by <cit.> for uniform sampling without replacement.
[Bardenet and Maillard, 2015]

Let $\Xsample_M$ denote numbers $\{x_1, \ldots, x_M\}$ lying in $[0,1]$. Suppose  $X_1, X_2, \ldots$ are drawn uniformly from $\Xsample_M$ without replacement. Introduce the terms $\mu = \frac{1}{M} \sum_{i=1}^n x_i$, and $\sigma^2 = \frac{1}{M} \sum_{i=1}^M (x_i-\mu)^2$. Then, we have the following with probability at least $1-\alpha$ for some $\alpha \in (0,1]$, for all $t \geq n$:

\begin{align}
&\mu \in \lb \frac{1}{n} \sum_{i=1}^n X_i - b_t,\,  \sum_{i=1}^n X_i + b_t \rb, \\
\quad \text{where} \quad &b_t = \sigma \sqrt{ \frac{2(1-n/M)(1+1/n) \log(2/\alpha)}{n} } + \lp \frac{4}{3} + \sqrt{\lp \frac{M}{n+1}-1 \rp \lp 1- \frac{n}{M} \rp} \rp\frac{  \log(2/\alpha)}{n}.
\end{align}

Note that the above expression involves the $\log(2/\alpha)$ term, instead of $\log(4/\alpha)$, because we have stated only the `second half' of the result, valid for $n>M/2$. This will be used in a direct comparison with the confidence sequences constructed by Waudby-Smith and Ramdas, 2020.

§.§.§ CIs proposed by Waudby-Smith and Ramdas, 2023

CI. To describe this CI, we need to introduce the following terms:

\begin{align}
\lambda_{t,n} = \sqrt{ \frac{2 \log(2/\alpha)}{n V_{t-1}}},
\quad V_t  = \frac{\frac{1}{4} + \sum_{i=1}^t (X_i - \muhat_i)^2}{t},
\quad \text{and} \quad
\muhat_t = \frac{1}{t} \sum_{i=1}^t X_i. \label{eq:wor-lambda-t-n}
\end{align}

For this predictable sequence $\{\lambda_t: t \in [M]\}$,  define the  mean estimate, $\mutilde_t$,  as

\begin{align}
\label{eq:weighted-mean}
\mutilde_t \defined \lp { \sum_{i=1}^t \lambda_{i,n}\lp X_i + \frac{1}{M-i+1}\sum_{j=1}^{i-1} X_j \rp}\rp\bigg/\lp { \sum_{i=1}^t \lambda_{i,n} \lp 1 + \frac{1}{M-i+1} \rp }\rp.
\end{align}

Note that we have assumed that all the values $x_i \in [0,1]$, and that $X_i$ are drawn uniformly without replacement from $\Xsample_M = \{x_1, \ldots, x_M\}$. With $\mu_M \defined \frac{1}{M} \sum_{i=1}^M x_i$, the CI is defined as:

\begin{align}
&C_n^{\prpieb} = [\mutilde_n \pm w_n^{\prpieb)}]
\quad \text{where} \quad
w_n^{(\prpieb)} = \frac{\log(2/\alpha)+ 4 \sum_{i=1}^t (X_i - \muhat_{i-1})^2\psi_E(\lambda_{i,n})}{\sum_{i=1}^t \lambda_{i,n} \lp 1 + \frac{i-1}{M-(i-1)} \rp}.
\end{align}

betting CI. The betting CI is constructed similar to the with-replacement case. The main difference is in the definition of the wealth process $\{W_t(m): t \geq 1\}$, which is centered with a time-varying conditional expectation. In particular, let $X_1, X_2, \ldots$ denote the sequence of observations, drawn uniformly from a set of numbers $\Xsample_M = \{x_1, \ldots, x_M\}$, and introduce the terms

\begin{align}
\mu_t = \frac{M\mu - \sum_{i=1}^{t-1} X_i}{M - t+1}, \quad \text{and} \quad
m_t = \frac{Mm - \sum_{i=1}^{t-1} X_i}{M - t+1}.
\end{align}

Define the wealth at time $n$,

\begin{align}
W_n(m) = \prod_{t=1}^n \big( 1 + \lambda_t(m) \lp X_t - m_t \rp \big),
\end{align}

with the bets $\{\lambda_t(m): t \geq 1\}$ selected according to any predictable betting strategy, such as the mixture method of <Ref>. The version of the betting CI analyzed in <Ref> is constructed by setting $\lambda_t(m) = \lambda_{t,n}$ for all $m \in [0,1]$, with $\lambda_{t,n}$ as defined in (<ref>).

§.§ Proof of betting CI limiting width (Proposition <ref>)

We prove this result in the following steps:

* We begin by obtaining a high probability concentration result for the empirical mean and variance about their true values in <Ref>, for a fixed value of $n$ and $M$.
As a consequence of the above, we show in <Ref> that $|V_n-\sigma_M^2| \convas 0$, and  $|\muhat_n-\mu_M| \convas 0$, under the assumption that $n = \lceil \rho M\rceil $, as $M \to \infty$

* Then, in <Ref>and <Ref>, we evaluate the numerator and denominator in the limiting width of the CI. Together these two results imply that
$\gamma_1^{\prpieb}(\rho)$ is  almost surely equal to $  \frac{1}{\rho}\log \lp \frac{1}{1 - \rho} \rp \frac{\sqrt{2 \log(2/\alpha)}}{\sigma}$.

Step 1: Concentration of empirical estimates.  In the next two lemmas, we show that the difference between empirical estimates of the mean, $\muhat_t = \frac{1}{t} \sum_{i=1}^t X_i$, and the variance $V_t = \frac{1}{t+1} \big(  1/4 + \sum_{i=1}^t (X_i - \muhat_{i-1})^2 \big)$ and their true values ($\mu_M$ and $\sigma^2_M$) converge to zero almost surely as $M\to \infty$.

For any fixed $1 \leq n \leq M$, the event $\mc{E}_n$ defined below, occurs with probability at least $1-2/n^2$.

\begin{align}
&\mc{E}_{n,1} = \lbr \forall t \in [n]: |\muhat_t - \mu_M| \leq \mc{O}\lp \sqrt{\log n/t}\rp \rbr, \quad
\mc{E}_{n,2} = \lbr \forall t \in [n]: |V_t - \sigma_M^2| \leq \mc{O}\lp \sqrt{\log n/ t}\rp \rbr,  \\
\quad \text{and} \quad &\mc{E}_n = \mc{E}_{n,1} \cap \mc{E}_{n,2}.
\end{align}

Recall that $\mu_M$ and $\sigma_M^2$ denote the mean and variance computed using all the $M$ values in $\Xsample_M$.

This result follows by applying the usual, fixed sample size, Hoeffding-Serfling inequality (e.g., <Ref>) for the mean and standard deviation estimates. Both of these results use the fact that the observations $(X_i)$ lie in the interval $[0,1]$. Since we are interested in the asymptotic limiting width, we use $\mc{O}(\cdot)$ in the definition of the events, instead of the exact constants, to simplify the notation.

As a consequence of the above result, we can easily conclude the following.

Suppose $\rho > 0$, and $n= \lceil \rho M \rceil$ for all $M \geq 1$. Then, we have $\mathbb{P}\lp \mc{E}_n^c \text{i.o.} \rp = 0$ as $M \to \infty$. This in turn implies that $\lim_{M \to \infty} | V_n - \sigma_M^2| \to 0$, and $|\muhat_n - \mu_M| \to 0$, almost surely.

The first statement follows by a standard application of the (first) Borel-Cantelli lemma. In particular, note that by <Ref>, we have $\mathbb{P}\lp \mc{E}_n^c \rp \leq \frac{1}{n^2}$, which implies that $\sum_{n = 1}^{\infty} \mathbb{P}\lp \mc{E}_n^c \rp<\infty$. Hence, we get that $\mathbb{P}\lp \mc{E}_n^c \text{i.o.} \rp = 0$, by the first Borel-Cantelli lemma.

Since $\lim_{n \to \infty} \sqrt{\log n / n} = 0$, we can thus conclude that $|\muhat_n - \mu_M| \stackrel{a.s.}{\rightarrow}  0$ and $|V_n-\sigma^2_M| \stackrel{a.s.}{\rightarrow}0$, due to the definition of the events $\mc{E}_{n,1}$ and $\mc{E}_{n,2}$ respectively.

Step 2: Limiting width of CI.
Our next two lemmas compute the limits of the $\lambda_{t,n}$ dependent terms in numerator and denominator respectively of the width of the CI of Waudby-Smith and Ramdas, 2023.

The following is true:

\begin{align}
\lim_{M \to \infty} 4 \sum_{i=1}^n (X_i - \muhat_{i-1})^2 \psi_E(\lambda_i) \stackrel{a.s.}{=} \sqrt{2 \log(2/\alpha)}.
\end{align}

The proof of this statement is in <Ref>. Next, we obtain the limiting value of the normalized denominator  of $w_n$.

Suppose $\lim_{M \to \infty} n/M = \rho$.  Then, we have the following

\begin{align}
\frac{1}{\sqrt{n}} \sum_{i=1}^n \lambda_i \lp 1 + \frac{i-1}{M-(i-1)} \rp \convas    \frac{1}{\rho}\log \lp \frac{1}{1 - \rho} \rp \frac{\sqrt{2 \log(2/\alpha)}}{\sigma}.
\end{align}

The proof of this statement is in <Ref>.
Combining these two results, we get the required limiting width of the CI.

Step 3: Obtain the bound on betting CI limiting width. Our final step is to show that the limiting width of the betting CI  is no larger than that of the CI. For this, we employ the general strategy we developed for proving <Ref> in <Ref>, with some modifications to deal with sampling. To avoid repetition, we omit some of the details in the steps that proceed almost exactly as the analogous steps in the proof of <Ref>.

Recall that, as in the with replacement case, the wealth $W_n(m)$ is the average of the two components:

\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_{i=1}^n \lp 1 \pm \lambda_{t,n}(m)(X_t - m_t) \rp.
\end{align}

This implies that the betting CI  satisfies the inclusion:

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

Next, we observe that the wealth $W^+_n(m)$ can be lower bounded by an application of Fan's inequality:

\begin{align}
\log(W^+_n(m)) &\geq  \sum_{t=1}^n \lambda_{t,n}(X_t-m_t) - 4\sum_{t=1}^t\psi_E(\lambda_{t,n}) (X_t-m_t)^2 \\
& \geq  \sum_{t=1}^n \lambda_{t,n}(X_t-m_t) - 4\sum_{t=1}^t\psi_E(\lambda_{t,n}).
\end{align}

Repeating this argument for $W_n^-(m)$,  we can define a larger CI that contains the betting CI:

\begin{align}
\CIbet \subset \CIfan \defined \lb \mutilde_n \pm \widetilde{w}_n^{(Fan)}\rb, \quad \text{with} \quad  \widetilde{w}_n^{(Fan)} \defined \frac{ \log(2/\alpha) + \sum_{t=1}^n \psi_E(\lambda_{t,n})}{\sum_{t=1}^n \lambda_{t,n}(1+ (t-1)/(M-t+1)}.
\end{align}

Then, following the exact argument as <Ref>, we can show that
\begin{align}
\limsup_{M \to \infty, n = \lceil \rho M \rceil} \sqrt{n} \times \widetilde{w}_n^{(Fan)} = c_2 = \lp \frac{\rho}{\log(1/(1-\rho))} \rp \sqrt{\frac{\log(2/\alpha)}{2}}\lp \sigma_M + \frac{1}{\sigma_M} \rp < \infty. \label{eq:wor-fan-limit}
\end{align}

Thus, as before, we can define a larger CI, denoted by $\CItilde$, that contains the betting CI. Furthermore, we can also define an  random time ($N$), after which the width of $\CIfan$ is smaller than $4c_2/\sqrt{n}$.

\begin{align}
\CItilde = \lb \mutilde_n \pm 2c_2/\sqrt{n} \rb, \quad \text{and} \quad
N = \sup\{M \geq 1: |\CIfan| > 4c_2/\sqrt{n} \}.
\label{eq:wor-CI-tilde}
\end{align}

To proceed with the proof, we need two technical results. The first result shows that under the high probability event $\mc{E}_n$, the modified mean estimate, $\mutilde_n$, is close to the true mean $\mu_M$.

Under the event $\mc{E}_n$ defined in <Ref>, we have the following:

\begin{align}
|\mutilde_n - \mu_M| = \mc{O}\lp \sqrt{\frac{\log n}{n}} \rp.
\end{align}

Recall that $\mutilde_n$ was defined in (<ref>), and $\mu_M = \frac{1}{M} \sum_{i=1}^M x_i$, is the true mean of the $M$ items.

The proof of this statement is in <Ref>. Using this result, we can then obtain the next technical result, that says that the term $(X_t - m_t)^2$ can be sufficiently well approximated with $(X_t - \muhat_{t-1})^2$ for all $m \in \CItilde$, and for all $M \geq N$.

The random variable $N$ defined above in (<ref>) is finite almost surely. Furthermore, with the high probability event $\mc{E}_n$ as defined in <Ref>, for any $m \in \CItilde$ and $2 \leq t \leq n$,   we have

\begin{align}
\boldsymbol{1}_{M \geq N} \boldsymbol{1}_{\mc{E}_n} (X_t-m_t)^2   \; \stackrel{a.s.}{\leq} \;  (X_t-\mu_M)^2 + \mc{O}\lp \sqrt{\frac{ \log n}{t} } \rp.  \label{eq:wor-betting-ci-proof-6}
\end{align}

The proof of this result is in <Ref>.

By the definition of $N$, under the event $\{N \leq M\}$, the confidence interval $\CItilde$ contains $\CIfan$, which by construction, contains $\CIbet$. Hence, we can write the following inclusion for $\CIbet$  under $\{N \leq M\}$:

\begin{align}
\CIbet & \subset \lbr m \in \CItilde: \log\lp W_n^+(m) \rp < \log(2/\alpha) \rbr \cap \lbr m \in \CItilde: \log\lp W_n^-(m) \rp < \log(2/\alpha) \rbr \label{eq:wor-proof-1}.
\end{align}

Let $l^*$ and $u^*$ denote the (random) smallest and largest values of $m$ respectively, that  satisfy the conditions in the right side of (<ref>) with equality.   Then, we have the following:

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

As for all $m \in [0,1]$, we define $l^*_t = \frac{Nl^* - \sum_{i=1}^{t-1} X_i}{N-t+1}$ and $u^*_t = \frac{Nu^* - \sum_{i=1}^{t-1} X_i}{N-t+1}$ above.

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

\begin{align}
\gammabet(\rho) \defined \limsup_{M \to \infty, n = \lceil \rho M\rceil} \sqrt{n} \times \frac{|\CIbet|}{2} \eqas \limsup_{M \to \infty} \sqrt{n} \times \frac{|\CIbet|}{2} \times \boldsymbol{1}_{M \geq N}.
\end{align}

Combining this observation with (<ref>), we get:

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

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

\begin{align}
\lim_{n \to \infty} \lp 2 \sum_{t=1}^n \psi_E(\lambda_{t,n}) \,U_t \rp \times \boldsymbol{1}_{M \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}
\lim_{n \to \infty} \lp 2 \sum_{t=1}^n \psi_E(\lambda_{t,n}) \,U_t \rp \times \boldsymbol{1}_{M \geq N} \eqas
\lim_{n \to \infty} 4 \sum_{t=1}^n \psi_E(\lambda_{t,n})(X_t-\muhat_{t-1})^2.
\end{align}

Since $\mathbb{P}\lp \{ \mc{E}_n\; i.o. \} \rp = 0$, we have

\begin{align}
\lim_{n \to \infty} \lp 2 \sum_{t=1}^n \psi_E(\lambda_{t,n}) \,U_t  \rp \times \boldsymbol{1}_{M \geq N} \boldsymbol{1}_{\mc{E}_n} \eqas \lim_{n \to \infty} \lp 2 \sum_{t=1}^n \psi_E(\lambda_{t,n}) \,U_t \rp \times \boldsymbol{1}_{M \geq N}.
\end{align}

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

\begin{align}
U_t \times \boldsymbol{1}_{\mc{E}_n} \times \boldsymbol{1}_{M \geq N} \stackrel{a.s.}{\leq} 2(X_t - \mu_M)^2 + \mc{O}\lp \sqrt{ \frac{\log n}{t}} \rp.
\end{align}

Plugging this into the previous equation, we obtain

\begin{align}
\lim_{n \to \infty} \lp 2 \sum_{t=1}^n \psi_E(\lambda_{t,n}) \,U_t  \rp \times \boldsymbol{1}_{M \geq N} \boldsymbol{1}_{\mc{E}_n}&\stackrel{a.s.}{\leq} \lim_{n \to \infty} 4 \sum_{t=1}^n \psi_E(\lambda_{t,n})\lp (X_t - \mu_M)^2 + \mc{O}\lp \sqrt{ \frac{\log n}{t}} \rp \rp \\
& \leq \sqrt{\log(2/\alpha)} + \mc{O}\lp \lim_{n \to \infty} \sum_{t=1}^n \psi_E(\lambda_{t,n})\sqrt{\frac{\log(n)}{t}}   \rp \\
& = \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 V_t) \approx \log(2/\alpha)/(4n\sigma_M^2)$, which implies that the term inside the $\mc{O}\lp \cdot \rp$ converges to $0$.  This completes the proof.

§.§.§ Proof of <Ref>

To simplify the presentation in this proof, we use $A \asymp B$ to indicate that $|A-B| \convas 0$ as $M \to \infty$.

We begin by noting that due to <Ref>, and <Ref>, we have $V_n \convas \sigma^2>0$. As a result, $\lambda_n = \sqrt{ 2\log(2/\alpha)/(V_n n)} \convas 0$, which implies that $|\psi_E(\lambda_n) - \psi_H(\lambda_n)| \convas 0$, where $\psi_H(\lambda) = \frac{\lambda^2}{8}$. Thus, we have :

\begin{align}
4 \sum_{i=1}^n \lp X_i - \muhat_{i-1} \rp^2 \psi_E(\lambda_i) &= 4 \sum_{i=1}^n \lp X_i - \muhat_{i-1} \rp^2  \lp \frac{\lambda_i^2}{8} + \lv\psi_E(\lambda_i) - \frac{\lambda^2_i}{8}\rv \rp \\
& \stackrel{(i)}{\asymp} 4 \sum_{i=1}^n \lp X_i - \muhat_{i-1} \rp^2 \frac{2 \log(2/\alpha)}{8 n V_i} \\
& \stackrel{(ii)}{\asymp} 4 \sum_{i=1}^n \lp X_i - \muhat_{i-1} \rp^2 \frac{2 \log(2/\alpha)}{8 n \sigma_M^2}
\stackrel{(iii)}{\asymp}  4 \sum_{i=1}^n \lp X_i - \muhat_{i-1} \rp^2 \frac{2 \log(2/\alpha)}{8 n \sigma^2}.
\end{align}

In the above display, $(i)$ uses the fact that $\lambda_i^2 = 2\log(2/\alpha)/n V_i$, and the fact that $\sum_{i=1}^n |\psi_E(\lambda_i) - \lambda_i^2/8| \convas 0$. Next, the equivalence $(ii)$ uses the fact that $|V_i - \sigma_M^2| = \mc{O}\lp \sqrt{ \log n / i} \rp$ all but finitely often( <Ref>), while $(iii)$ follows by <Ref>.

Next, we continue with the above chain of inequalities to obtain

\begin{align}
4 \sum_{i=1}^n \lp X_i - \muhat_{i-1} \rp^2 \psi_E(\lambda_i)
& \asymp \frac{\log(2/\alpha)}{ \sigma^2}  \frac{1}{n}\sum_{i=1}^n \lp X_i - \muhat_{i-1} \rp^2  \\
& \stackrel{(iv)}{\asymp} \frac{\log(2/\alpha)}{ \sigma^2}  V_n
\stackrel{(v)}{\asymp}  \frac{\log(2/\alpha)}{ \sigma^2}  \sigma_M^2 \\
& \stackrel{(vi)}{\asymp} \log(2/\alpha).
\end{align}

The equivalence $(iv)$ simply follows from the definition of $V_n = \frac{1}{n+1}\lp  \frac{1}{4}  + \sum_{i=1}^n (X_i - \muhat_{i-1})^2 \rp$, while $(v)$ uses <Ref> and $(vi)$ follows from <Ref>.

§.§.§ Proof of <Ref>

We proceed as follows:

\begin{align}
A_{M,n} \defined \frac{1}{\sqrt{n}} \sum_{i=1}^n \lambda_i \lp 1 + \frac{i-1}{M-(i-1)} \rp &=   \frac{1}{\sqrt{n}} \sum_{i=1}^n \lambda_i \lp  \frac{M}{M-(i-1)} \rp.
\end{align}

Next, note that we have

\begin{align}
\lambda_i = \sqrt{ \frac{2\log(2/\alpha)}{n V_{i-1}} }
= \sqrt{ \frac{2 \log(2/\alpha)}{n \sigma^2 \lp 1 - \frac{\sigma^2-V_{i-1}}{\sigma^2}\rp} }
\asymp \sqrt{ \frac{2\log(2/\alpha)}{n\sigma^2} \lp 1 + \frac{\sigma^2 - V_{i-1}}{\sigma^2} \rp }.
\end{align}

The last $\asymp$ follows by noting that the function $f(x) = 1/x$ is concave, hence, it can be bounded (over a bounded interval) from both above and below using linear approximations. That is, $f(1+x) \geq 1 - x$ for all $x \in (-1, \infty)$, and $f(1+x) \leq 1 - 2x$ for $x \in [-0.5, 0]$, and $f(1+x) \leq 1 - (2/3)x$, for $x \in [0, 0.5]$. Under the event $\mc{E}_{n,2}$, we know that the term $\sigma^2 - V_{i-1}$ is $\mc{O}\lp \sqrt{\log n/ i}\rp$. Hence, we have the following:

\begin{align}
\frac{1}{\sqrt{n}} \sum_{i=1}^n \lambda_i \frac{M}{M-(i-1)} &\lesssim
\frac{M}{\sqrt{n}} \sum_{i=1}^n \lambda^*_n \frac{1}{M-(i-1)} \lp 1 + \lp \frac{ \log n}{i} \rp^{1/4} \rp \nonumber \\
& \leq \frac{M}{\sqrt{n}} \lambda^*_n \lp S_M - S_{M-n} \rp + \frac{M \lambda^*_n}{\sqrt{n}} \lp \sum_{i=1}^n \frac{1}{(M-i+1)^2} \rp^{1/2} \lp \sqrt{\log n} \sum_{i=1}^n \frac{1}{\sqrt{i}} \rp^{1/2} \label{eq:eb-cs-proof-1}
\end{align}

where $S_k \defined \sum_{i=1}^k 1/i$. Now, since $S_k = \log k + 0.5772 + \frac{1}{2k} - \mc{O}(1/k^2)$, we can conclude that $S_M - S_{M-n} \asymp \log M - \log(M-n)$, under the assumption that $n = \rho M$ for some $\rho>0$.

Next, we note that $\sum_{i=1}^n 1/(M-i+1)^2 \asymp \frac{n}{M(M-n)}$, and $\sum_{i=1}^n 1/\sqrt{i} \asymp \sqrt{n}$.  Combining these facts, we observe that the second term in (<ref>) is $\mc{O}\lp (\log n/n)^{1/4} \rp$, which converges to $0$ with $M \to \infty$.
Hence, we get the following:

\begin{align}
A_{M,n} \asymp \frac{M}{\sqrt{n}} \log \lp \frac{M \lambda^*_n}{M-n} \rp = \frac{M \sqrt{2 \log(n/\alpha)}}{\sigma n} \log \lp \frac{1}{1 - n/M} \rp,
\end{align}

which implies that

\begin{align}
A_{M,n} \convas  \frac{1}{\rho}\log \lp \frac{1}{1 - \rho} \rp \frac{\sqrt{2 \log(2/\alpha)}}{\sigma}.
\end{align}

§.§.§ Proof of <Ref>

Under the event $\mc{E}_n$, we know that $\muhat_i$ and $V_i$ concentrate around the true mean ($\mu \equiv \mu_M$) and variance ($\sigma^2 \equiv \sigma_M^2$) respectively. As a result, we have

\begin{align}
&\lambda_i = \lambda^*_n\lp 1 + r_i \rp = \sqrt{\frac{2 \log(2/\alpha)}{n \sigma^2}}\lp 1 + r_i \rp, \quad \text{and} \quad \muhat_i = \mu + s_i, \quad \text{where} \quad r_i, s_i = \mc{O}\lp \sqrt{\log n/i} \rp.
\end{align}

Using this, we rewrite the weighted mean estimate as follows:

\begin{align}
\mutilde_n = \frac{\sum_{i=1}^n \lambda^*_n\lp X_i + \frac{\muhat_{i-1} (i-1)}{N-i+1} \rp\lp 1 + r_i\rp }{ \sum_{i=1}^n\lambda^*_n\lp 1 + \frac{i-1}{N-i+1} \rp \lp 1 + r_i \rp}
= \frac{\sum_{i=1}^n \lp X_i + \frac{\muhat_{i-1} (i-1)}{N-i+1} \rp\lp 1 + r_i\rp }{ \sum_{i=1}^n\lp 1 + \frac{i-1}{N-i+1} \rp \lp 1 + r_i \rp}
= \frac{\numerator}{\denominator}.
\end{align}

We now evaluate the and the separately. First, we introduce the terms

\begin{align}
q_i = 1 + \frac{i-1}{N-i+1}, \quad \text{and} \quad Q_n = \sum_{i=1}^n q_i,
\end{align}

and note that  $1 \leq q_i \leq 1/(1-\rho) = \Theta(1)$, which implies that $n \leq Q_n \leq n/(1-\rho)$. Using this, we obtain the following bound on the :

\begin{align}
\numerator &= \sum_{i=1}^n X_i + \sum_{i=1}^n \muhat_{i-1}\frac{i-1}{N-i+1} + \mc{O}\lp \sum_{i=1}^n \lp 1 + \frac{i-1}{N-i+1} r_i\rp \rp \\
& = n\mu  + \sum_{i=1}^n \frac{\mu (i-1)}{N-i+1} + \mc{O}\lp \sum_{i=1}^n q_i (r_i + s_i) \rp \\
& = Q_n\lp \mu +  \frac{1}{Q_n}\mc{O}\lp \sum_{i=1}^n (r_i + s_i) \rp \rp.
\end{align}

Similarly, the satisfies

\begin{align}
\denominator = Q_n + \sum_{i=1}^n q_i r_i  = Q_n \lp 1 + \frac{1}{Q_n} \lp \sum_{i=1}^n r_i \rp \rp
\end{align}

On combining these two observations, we get

\begin{align}
\mutilde_n &= \frac{ \mu +   \frac{1}{Q_n}\mc{O}\lp \sum_{i=1}^n (r_i + s_i) \rp}{1 + \frac{1}{Q_n} \lp \sum_{i=1}^n r_i \rp} = \lp \mu +  \frac{1}{Q_n}\mc{O}\lp \sum_{i=1}^n (r_i + s_i) \rp \rp \lp 1 + \mc{O}\lp\frac{1}{Q_n}  \sum_{i=1}^n r_i \rp \rp  \\
& = \mu +  \mc{O}\lp \frac{1}{Q_n}\sum_{i=1}^n (r_i + s_i) \rp = \mu + \mc{O}\lp \frac{1}{n} \sum_{i=1}^n \sqrt{\frac{\log n}{i}} \rp  = \mu + \mc{O}\lp \sqrt{\frac{\log n}{n}} \rp.
\end{align}

§.§.§ Proof of <Ref>

$\boldsymbol{N}$ is finite almost surely.
We know that $\lim_{M \to \infty} \sqrt{n} \,\widthfan = \lim_{M \to \infty} \frac{\sqrt{n}}{2} |\CIfan| = c_2$ almost surely. Or in other words, the set $\Omega = \{\omega: \lim_{M \to \infty} \sqrt{n} \widthfan(\omega) = c_2\}$ has probability $1$, which also implies that the set $\{\omega: \exists N(w) < \infty, \text{ s.t. } \sqrt{n} \widthfan(\omega) \leq 2c_2 \text{ for all } M \geq N(w)\}$ also has probability $1$. Since the latter is exactly the set on which $N$ is finite, this proves the first part of the lemma.

Bound on $\boldsymbol{(X_t - m_t)^2}$. Let $\mu \equiv \mu_M$ denote the true mean of the $M$ items, and define $\mu_t = (N\mu - \sum_{i=1}^{t-1}X_i)/(N-t+1)$. Then, we have the following:

\begin{align}
(X_t - m_t)^2 &= (X_t - \mu_t)^2 + (\mu_t - m_t)^2 + 2(X_t - \mu_t)(\mu_t - m_t) \\
&\leq (X_t - \mu_t)^2 + 3|\mu_t - m_t|  \\
& \leq (X_t - \mu_t)^2 + 3 \frac{1}{1-\rho}|\mu - m| \\
& \leq (X_t - \mu_t)^2 + 3 \frac{1}{1-\rho}\lp |\mu - \mutilde_n| + |\mutilde_n - m|\rp.  \label{eq:wor-proof-3}
\end{align}

The first inequality uses the fact that both $(\mu_t - m_t)^2$ and $(X_t - \mu_t)(\mu_t- m_t)$ are upper bounded by $|\mu_t - m_t|$.  The second inequality uses the fact that $|\mu_t - m_t| = N|\mu-m|/(N-t+1)$ and $t \leq n = \rho M + 1$, while the last inequality is a direct consequence of the triangle inequality for the absolute value function.

Next, we subtract and add a $\mu$ in $(X_t - \mu_t)^2$, to get an upper bound

\begin{align}
(X_t - \mu_t)^2 &\leq (X_t - \mu)^2 + 3|\mu_t - \mu| = (X_t - \mu)^2 + 3 \frac{t-1}{N-t+1}|\muhat_{t-1} - \mu| \\
& \leq (X_t - \mu)^2 +  \frac{3\rho}{1-\rho} |\muhat_{t-1} - \mu|. \label{eq:wor-proof-4}
\end{align}

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

\begin{align}
\boldsymbol{1}_{\mc{E}_n} \boldsymbol{1}_{M \geq N} (X_t - m_t)^2 &\leq \boldsymbol{1}_{\mc{E}_n} \boldsymbol{1}_{M \geq N}  \bigg( (X_t - \mu)^2 + \mc{O}\lp |\mu - \mutilde_n| + |\mutilde_n - m| + |\muhat_{t-1}-\mu| \rp \bigg)  \\
&\leq (X_t - \mu)^2 + \boldsymbol{1}_{\mc{E}_n} \boldsymbol{1}_{M \geq N}  \bigg( \mc{O}\lp |\mu - \mutilde_n| + |\mutilde_n - m| + |\muhat_{t-1}-\mu| \rp \bigg).
\end{align}

Finally, we observe that all the three terms inside $\mc{O}(\cdot)$ are small under the event $\mc{E}_n \cap \{M \geq N\}$:

* From <Ref>, we know that $|\mutilde_n - \mu| = \mc{O}\lp \sqrt{ \log n /n} \rp$ under the event $\mc{E}_n$.

* Since $m \in \CItilde = [\mutilde_n \pm 2c_2/\sqrt{n}]$, it follows that $|\mutilde_n - m| \leq 4c_2/\sqrt{n}$. The event $\{M \geq N\}$ implies that $\CIfan \subset \CItilde$, which in turn implies that $\CIbet \subset \CItilde$, since $\CIfan$ contains $\CIbet$ by construction.

* Finally, under the event $\mc{E}_n$, we know that $|\muhat_{t-1} - \mu| = \mc{O}\lp \sqrt{ \log n /t} \rp$, for all $t \leq n$.

Thus, these three observations imply that

\begin{align}
\boldsymbol{1}_{\mc{E}_n} \boldsymbol{1}_{M \geq N} (X_t - m_t)^2 &\leq (X_t - \mu)^2 + \mc{O}\lp \sqrt{ \frac{ \log n}{t} } \rp,
\end{align}

as required.

§ SECOND-ORDER LIMITING WIDTH ANALYSIS (PROPOSITION <REF>)

Second-order width of CI.
Let us denote the term $n \lp w_n^{(\mpeb)} - \gamma_1^{(\mpeb)}/\sqrt{n} \rp$ with $S_n$. Furthermore, to ease the notation , we will drop the from the superscripts for this proof. Then, observe that

\begin{align}
S_n &= \sqrt{n}\lp \sigmahat_n - \sigma \rp \sqrt{2 \log(4/\alpha)} + \frac{7 \log(4/\alpha)}{3}\lp 1 + \frac{1}{n-1} \rp  \\
& \defined c_1 \sqrt{n}\lp \sigmahat_n - \sigma \rp + c_2 \lp 1 + \frac{1}{n-1} \rp.
\end{align}

Since $c_2(1+1/(n-1))$ converges to $c_2$ as $n \to \infty$, we can focus on the first term above, and refer to it by $T_n$. By <cit.>, we know that

\begin{align}
\sqrt{n} \lp \sigmahat_n^2 - \sigma^2 \rp \convdist N\lp 0, \mu_4 - \sigma^4 \rp,
\end{align}

where $\mu_4 \defined \mathbb{E}[(X-\mathbb{E}[X])^4]$, is the fourth central moment of $X$. Then, by the delta-method <cit.>, we have

\begin{align}
\frac{T_n}{c_1} = \sqrt{n} \lp \sigmahat_n - \sigma \rp = \sqrt{n}\lp \sqrt{\sigmahat_n^2} - \sqrt{\sigma^2} \rp  \convdist N\lp 0, \frac{\mu_4 - \sigma^4}{4} \rp.
\end{align}

Thus, we have proved that the statistic $S_n$ satisfies

\begin{align}
S_n = T_n + c_2 + o_P(1), \quad \text{with} \quad T_n \convdist N\lp 0, \frac{\log(4/\alpha)(\mu_4 - \sigma^4)}{2} \rp, \quad \text{and} \quad c_2 = \frac{7 \log(4/\alpha)}{3}.
\end{align}

Second order width of CI. To analyze the statistic involved in the definition of the second-order limiting width, we introduce the following notation (dropping from the superscripts)

\begin{align}
w_n \equiv w_n^{(\prpieb)} = \frac{ \log(2/\alpha) + 4\sum_{t=1}^n \psi_E(\lambda_{t,n}) \lp X_t - \muhat_{t-1} \rp^2 }{ \sqrt{n} \,\times\, \frac{1}{\sqrt{n}} \sum_{t=1}^n \lambda_{t,n}  } = \frac{A_n}{\sqrt{n} B_n}.
\end{align}

From <Ref>, we know that $A_n \convas 2 \log(2/\alpha)$ and $B_n \convas b \defined \sqrt{2 \log(2/\alpha)}/\sigma$. Now, the second-order width statistic can be rewritten as  follows, with $\Delta_n = (B_n - b)/b$:

\begin{align}
S_n &= n \lp \frac{A_n}{\sqrt{n}b \lp 1 + \Delta_n  \rp} - \frac{\gamma_1}{\sqrt{n}} \rp = \frac{A_n \sqrt{n}}{b} \lp 1 - \Delta_n + \mc{O}\lp  \Delta_n^2   \rp \rp - \sqrt{n} \gamma_1  \\
& = \sqrt{n} \lp \frac{A_n - b \gamma_1}{b} \rp  - \sqrt{n} \frac{A_n \Delta_n}{b} + \mc{O}\lp \frac{A_n \sqrt{n} \Delta_n^2}{b} \rp \label{eq:prpl-second-order-proof-1}
\end{align}

An application of Borel-Cantelli Lemma implies that  $\{|\Delta_n| \leq \mc{O}\lp \sqrt{\log n / n} \rp \text{ i.o.}\}$ happens with probability one. Thus, the $\mc{O}\lp \sqrt{n} \Delta_n^2 \rp$ terms converges to $0$ almost surely, and hence also in probability.  We now expand the first term in (<ref>):

\begin{align}
\sqrt{n} \lp \frac{A_n - b \gamma_1}{b} \rp   &= \sqrt{n} \lp \frac{\log(2/\alpha) + 4 \sum_{t=1}^n \psi_E(\lambda_{t,n})(X_t-\muhat_{t-1})^2 - 2 \log(2/\alpha)}{b} \rp  \\
&= \sqrt{n} \lp \frac{4 \sum_{t=1}^n \psi_E(\lambda_{t,n})(X_t-\muhat_{t-1})^2 -  \log(2/\alpha)}{b} \rp  = \sqrt{n} \frac{C_n}{b}
\end{align}

Now, we note that $4 \psi_E(\lambda) = \frac{\lambda^2}{2} + \frac{\lambda^3}{3} + \mc{O}\lp \lambda^4 \rp$, which implies that

\begin{align}
4 \psi_E(\lambda_{t,n}) = \frac{\log(2/\alpha)}{n V_{t-1}} + \frac{1}{3}\lp \frac{2 \log(2/\alpha)}{n V_{t-1}}\rp^{3/2} +  \mc{O}\lp \frac{1}{n^2 V_{t-1}^2} \rp
\end{align}

This implies that

\begin{align}
\sqrt{n} C_n &= \frac{\log(2/\alpha)}{\sqrt{n}} \sum_{t=1}^n \lp \frac{(X_t - \muhat_{t-1})^2}{V_{t-1}} - 1 \rp + \frac{(2\log(/2\alpha))^{3/2}}{3n} \sum_{t=1}^n \frac{(X_t-\muhat_{t-1})^2}{V_{t-1}^{3/2}} + o_P(1) \\
& \defined G + H + o_P(1).  \label{eq:prpl-second-order-proof-2}
\end{align}

We now show that the term $H$ in (<ref>) is equal to $2b \log(2/\alpha)/3 + o_P(1)$.

\begin{align}
H &= \frac{(2\log(/2\alpha))^{3/2}}{3n \sigma^3} \sum_{t=1}^n (X_t-\muhat_{t-1})^2 \lp 1 - \frac{3(V_{t-1} - \sigma^2)}{2 \sigma^2} + \mc{O} \lp  \lp \frac{V_{t-1} - \sigma^2}{\sigma^2}\rp^2 \rp \rp \\
& \stackrel{(i)}{=} \frac{(2\log(/2\alpha))^{3/2}}{3\sigma} + \frac{(2\log(/2\alpha))^{3/2}}{3n \sigma^3} \sum_{t=1}^n \lp  (X_t- \muhat_{t-1})^2  - \sigma^2\rp + o_P(1) \\
& \stackrel{(ii)}{=} \frac{(2\log(/2\alpha))}{3} \times \frac{ \sqrt{2 \log(2/\alpha)}}{\sigma} + o_P(1) \\
& = \frac{(2\log(/2\alpha))}{3} \times b + o_P(1).
\end{align}

In this display, $(i)$ uses the fact that $V_t \convas \sigma^2$, and $(ii)$ uses the fact that $\frac{1}{n} \sum_{t=1}^n (X_t - \muhat_{t-1})^2 \convas \sigma^2$. Thus, we have proved that $H/b = 2 \log(2/\alpha) + o_P(1)$.

Next, we note that the term $G$ in (<ref>) can be expressed as

\begin{align}
\frac{G}{\log(2/\alpha)} &= \frac{1}{\sqrt{n}} \sum_{t=1}^n \lp \frac{(X_t - \muhat_{t-1})^2}{\sigma^2 (1+\rho_{t-1}) } - 1 \rp, \quad \text{where} \quad \rho_{t-1} = \frac{V_{t-1} - \sigma^2}{\sigma^2}. \label{eq:prpl-second-order-proof-3}
\end{align}

Now, observe that

\begin{align}
\frac{1}{\sqrt{n}}\sum_{t=1}^n \frac{(X_t - \muhat_{t-1})^2}{1 + \rho_{t-1}} &= \frac{1}{\sqrt{n}}\sum_{t=1}^n \lp X_t - \muhat_{t-1} \rp^2 \lp 1 - \rho_{t-1} + \mc{O}\lp \rho_{t-1}^2 \rp \rp \\
&= \frac{1}{\sqrt{n}}\sum_{t=1}^n (X_t - \muhat_{t-1})^2 ( 1 + \rho_{t-1})  + o_P(1),
\end{align}

where the second equality uses the fact that $(1/\sqrt{n})\sum_{t=1}^n \mathbb{E}[(X_t - \muhat_{t-1})^2 \rho_{t-1}^2] \leq (1/\sqrt{n})\sum_{t=1}^n \mathbb{E}[\rho_{t-1}^2] = \mc{O}(\log n / \sqrt{n}) \to 0$. Next, we add and subtract $\mu$ in $(X_t - \muhat_{t-1})^2$, to get

\begin{align}
\frac{1}{\sqrt{n}}\sum_{t=1}^n (X_t - \muhat_{t-1})^2(1 + \rho_{t-1}) &= \frac{1}{\sqrt{n}}\sum_{t=1}^n \lp (X_t - \mu)^2 + 2(X_t - \mu)(\mu - \muhat_{t-1}) + (\muhat_{t-1}-\mu)^2 \rp (1 + \rho_{t-1}) \\
& =  \frac{1}{\sqrt{n}}\sum_{t=1}^n \lp (X_t - \mu)^2 + 2(X_t - \mu)(\mu - \muhat_{t-1})  \rp (1 + \rho_{t-1}) + o_P(1).
\end{align}

The second equality uses the fact that $(1/\sqrt{n})\sum_{t=1}^n \mathbb{E}[(\muhat_{t-1}-\mu)^2] = \mc{O}(\log n/\sqrt{n}) \to 0$. Note that the mean of each term in the summation is equal to $\sigma^2$. Thus, plugging this back into (<ref>), we get that

\begin{align}
\frac{G}{b} &= \frac{\log(2/\alpha)}{\sigma^2 b \sqrt{n}} \sum_{t=1}^n \lp \frac{(X_t-\muhat_{t-1})^2}{1 + \rho_{t-1}} - \sigma^2 \rp \\
&= \frac{\log(2/\alpha)}{\sigma^2 b \sqrt{n}}\sum_{t=1}^n \lp \lp (X_t - \mu)^2 + 2(X_t - \mu)(\mu - \muhat_{t-1})  \rp (1 + \rho_{t-1}) - \sigma^2 \rp + o_P(1) \\
& \defined T_{n,1} + o_P(1),
\end{align}

where $T_{n,1}$ is a zero-mean random variable. Thus, the first term in (<ref>) satisfies

\begin{align}
\sqrt{n} \lp \frac{A_n - b \gamma_1}{b} \rp = \frac{2 \log(2/\alpha)}{3} +  T_{n,1} + o_P(1). \label{eq:prpl-second-order-proof-4}
\end{align}

It remains to characterize the second term in (<ref>) to complete the proof. In particular, following the same arguments as above, we can show that

\begin{align}
\sqrt{n}\frac{A_n}{b^2} \lp \frac{1}{\sqrt{n}} \sum_{t=1}^n \lambda_{t,n} - b\rp &=  \frac{2 \log(2/\alpha)}{b} \lp \frac{\sqrt{2 \log(2/\alpha)}}{b \sigma} \frac{1}{\sqrt{n}} \sum_{t=1}^n \rho_{t-1}   \rp  + o_P(1) \\
& = T_{n,2} + o_P(1),  \label{eq:prpl-second-order-proof-5}
\end{align}

where $T_{n,2}$ is also a zero-mean random variable. Thus, (<ref>) and (<ref>) together imply that the term $S_n$ introduced in in (<ref>) satisfies

\begin{align}
S_n = \frac{2\log(2/\alpha)}{3} + T_n + o_P(1),
\end{align}

where $T_n = T_{n,1} + T_{n,2}$ is a zero-mean random variable. This completes the proof.