In the experts problem, on each of $T$ days, an agent needs to follow the advice of one of $n$ “experts”. After each day, the loss associated with each expert's advice is revealed.
A fundamental result in learning theory says that the agent can achieve vanishing regret, i.e. their cumulative loss is within $o(T)$ of the cumulative loss of the best-in-hindsight expert.

Can the agent perform well without sufficient space to remember all the experts?
We extend a nascent line of research on this question in two directions:

* We give a new algorithm against the oblivious adversary, improving over the memory-regret tradeoff obtained by [PZ23], and nearly matching the lower bound of [SWXZ22].

* We also consider an adaptive adversary who can observe past experts chosen by the agent. In this setting we give both a new algorithm and a novel lower bound, proving that roughly $\sqrt{n}$ memory is both necessary and sufficient for obtaining $o(T)$ regret.

§ INTRODUCTION

Consider the online learning problem of an agent who has to make decisions in an unknown and dynamically changing environment. The standard discrete abstraction of this problem considers a sequence of $T$ days; every morning $n$  experts offer their “advice” to the agent, who chooses to follow one of them; every night the agent observes the loss incurred by her choice as well as all the other choices she could have made
[The model where the agent learns the loss-in-hindsight on actions she didn't take is called full feedback . In this work we do not study the alternative bandit model where the agent has to explore the different actions to learn their loss distribution.]
The benchmark for this problem is minimization of regret, aka

$$ (\text{Loss of agent's actions}) - (\text{Loss of single best-in-hindsight expert}).$$

Amazingly, simple algorithms like multiplicative weights update (MWU) achieve total regret that is asymptotically vanishing as a fraction of the total possible loss, even in the face of an adversarially chosen loss sequence.
This celebrated result has numerous applications in both theory and practice, including boosting [27], learning in games [28, 20], approximate algorithm for max flow [21] and etc.

Recently, Srinivas, Woodruff, Xu and Zhou [62] initiated the study of memory bounds for online learning. They gave a near-tight characterization of the memory-regret tradeoff in the case where each day the loss is drawn independently from the same distribution (alternatively, there is a fixed set of loss vectors that arrives in a random order). In particular, they gave an algorithm that obtains vanishing regret while only using $\polylog(nT)$ memory.
[62] posed as an open question what memory-regret tradeoff is possible without the i.i.d. or random order assumptions. The first progress on this problem was obtained by Peng and Zhang [54] who gave a low memory algorithm with vanishing regret.
Our first contribution is a new online learning algorithm in this setting, improving over [54]'s regret-memory tradeoff, and essentially matching [62]'s lower bound.[
Our space-efficient algorithms do not need to access the entire loss vector at once —  (single-pass) streaming access suffices.
Meanwhile, our lower bound continues to hold against stronger algorithms that have arbitrary internal memory on each day for processing the loss vector, and are only limited in how much information they store between days.]

[Algorithm, oblivious adversary]theoremOblivious

Let $n , T$ be sufficiently large integers and let $\polylog (nT) \leq S \leq n$.
There is an online learning algorithm that uses at most $S$ space and achieves $\widetilde{O}\left(\sqrt{\frac{nT}{S}}\right)$ regret against an oblivious adversary, with probability at least $1-1/(nT)^{\omega(1)}$.

Note that, up to polylogarithmic factors, this memory-regret tradeoff is tight, hence resolving the open question posed by [62].
It is also interesting to note that [62]'s lower bound holds for the special case of i.i.d. generated loss. Thus our algorithm implies that the much more general oblivious adversary is actually not strictly harder.

All the low memory algorithms discussed so far hold against an oblivious adversary who fixes the loss sequence in advance. But an even more amazing property of the classical MWU algorithm is that it achieves vanishing regret even in the face of an adaptive adversary that can update the current loss vector depending on the agent's past choices. This extension to adaptive adversary is crucial for analyzing settings where the agent interacts with the environment, as is the case in the most important applications to game theory (see e.g. <cit.>).

We give an online learning algorithm with sublinear memory against an adaptive adversary. Specifically, our algorithm can achieve $o(T)$ regret while using only $\tilde{O}(\sqrt{n})$ memory.

[Algorithm, adaptive adversary]theoremAdaptive

Let $n, T$ be sufficiently large integers. There is an online learning algorithm that uses up to $S$ space and achieves $\wt{O}\left(\max\left\{\sqrt{\frac{nT}{S}}, \frac{\sqrt{n}T}{S}\right\}\right)$ regret against an adaptive adversary, with probability at least $1-1/(nT)^{\omega(1)}$.

Finally, we give a novel lower bound for the adaptive adversary case, showing that $\tilde{\Omega}(\sqrt{n})$ memory is also necessary for guaranteeing vanishing regret.

Let $\eps \in (\frac{1}{\sqrt{n}}, 1)$, any online learning algorithm guaranteeing $o(\eps^2 T)$ regret against an adaptive adversary requires space $\tilde{\Omega}(\frac{\sqrt{n}}{\eps})$.

[Running time]
The focus of this paper is memory. We note that both algorithms (Theorem <ref> and Theorem <ref>) are computationally efficient —   the running time (per round) scales linearly with the memory.

§.§ Related work

Comparison with previous work [62, 54] The work of [62, 54] are closely related to us and we provide a detailed discussion.
Srinivas, Woodruff, Xu and Zhou [62] initiate the study of memory bounds for online learning and provide a regret lower bound of $\Omega(\sqrt{\frac{nT}{S}})$ that holds even for i.i.d. loss sequence.
Their lower bound reduces from the coin problem, and it is proved via a direct-sum argument and a strong data-processing inequality.
Both the construction and the proof technique are quite different in comparison with our lower bound for adaptive adversary. [62] also provide an algorithm with $O(\sqrt{\frac{nT}{S}})$ regret, when the loss sequence arrives in random order. It is not surprising that their analysis heavily relies on the random nature of loss sequence.

Peng and Zhang [54] provide the first sublinear space online learning algorithm for oblivious adversary.
Their algorithm obtains a total regret of $\wt{O}(n^2T^{\frac{2}{2+\delta}})$ using $n^{\delta}$ space (in concurrent work, [3] improved this regret bound to $\wt{O}(n^2T^{\frac{1}{1+\delta}})$). Our baseline algorithm shares some similarity with [54, 3], but as we shall discuss soon, the key component, i.e., the eviction rule is quite different. Our robustifying procedure, amortization technique, and low memory “monocarpic” experts
procedure are all new components that enable us to obtain near-optimal tradeoffs for the oblivious adversary.

Peng and Zhang [54] also provide a space lower bound of $\Omega(\min\{\eps^{-1}\log n, n\})$ for any algorithm with $O(\eps T)$ regret, against a strong adaptive adversary.
As noted in [54], the strong adversary could see the distribution/mixed strategy of the algorithm in the current round, which is stronger than the adaptive adversary usually considered in the literature.
Our lower bound is quantitatively stronger, and holds even against the weaker and more standard notion of adaptive adversary.
In terms of technique, [54] establish their lower bound via a counting argument and a connection to learning in games (which requires the strong adversary assumption). In contrast, our lower bound instance is constructed based on the standard notion of adaptive adversary who can attack the algorithm's recent actions;  the proof relies on direct-product theorems from communication complexity.
In fact, using our methodology, it is easy to derive an $\Omega(n)$ lower bound for any sub-linear regret algorithm $o(T)$, for the strong adaptive adversary (see Section <ref>).

Comparison with work of [64] on adaptive adversary
[64] also provide lower bounds and algorithms for an adaptive adversary, but both the set up and the technique are quite different from ours.
In particular: (1) They focus on the binary prediction task, while we study the general model where an adversary observes the specific experts chosen by algorithm in previous rounds. (2) They consider an additional parameter, $M$, the number of incorrect binary predictions made by the best expert.  In this setting they give a tight bound on the space-regret tradeoff for deterministic algorithms, and give a randomized algorithm that can improve over this tradeoff when $M = o(T/\log^2 n)$. Even though the settings are different, note that our algorithm for the adaptive adversary obtains sub-linear regret with sub-linear memory without any assumption on the loss of the best expert, and that our lower bound holds against randomized algorithms.

Online learning
The classic MWU algorithm has shown to achieve optimal regret [49, 52] for online learning with experts advice.
As a meta approach, it has found a wide range of applications in algorithm design and analysis, includes boosting [27], learning in games [28, 20], approximate algorithm for max flow [21] and etc [30, 45, 40].
See the survey [5] for a complete treatment.

The MWU algorithm falls into the broader framework of following the randomized/perturbed leader [46, 36], a general framework that subsumes almost all existing online learning algorithms (except [54]).
As observed in [62, 54], identifying even a (constant) approximately best expert requires $\Omega(n)$ memory, hence new ideas are required for a low memory online learning algorithm.
The online learning problem has also been studied in other context, examples including oracle efficient algorithm [38, 24], smooth adversary [42, 37, 11] and bandit feedback [1, 10].
Other extended regret notions have been considered, including second order regret [47], interval regret [43], sleeping expert [29, 15] and others [12, 22, 4, 63, 14].

Memory bounds for learningMemory bounds have been established in stochastic multi-arm bandit and pure exploration [48, 7, 50, 6]. They are not worst case or adversarial in nature.

The role of memory for learning has been extensively studied in the past decade, including time-space trade-off for parity learning [56, 57, 34, 35, 32], memory bounds for convex optimization [51, 19], continual learning [23], generalization [26, 8] and many others [61, 60, 33, 9, 25].

Communication complexity has been a useful approach for establishing memory lower bound. In particular, our lower bound proof critically utilizes the machinary of direct-product theorem [55, 41, 17, 16, 44] and the information cost of set disjointness [18, 59].

§ OVERVIEW OF TECHNIQUES

We provide a high level overview on our techniques.

§.§ Algorithm for oblivious adversary

We focus on the case of $S = \polylog(nT)$ and aim for a regret bound of $\wt{O}\left(\sqrt{nT}\right)$, the extension to a general dependence on $S$ is obtained via a grouping trick that is deferred to the end.

§.§.§ The baseline building block

We first present a baseline subroutine that obtains a total regret of $\wt{O}(nB + \frac{T}{\sqrt{B}})$.
The baseline algorithm proceeds epoch by epoch, with a total of $\frac{T}{B}$ epochs and  $B$ days in each epoch.
The algorithm maintains a pool $\mP$ of experts and runs MWU over them in each epoch; the pool is fixed within the epoch.
The pool is updated every epoch, it randomly samples and adds $O(1)$ experts at the beginning, and the algorithm prunes the pool at the end.
So far this is the same basic setup as [54]:  the algorithm is now competitive to the best experts in the pool and the task is to maintain a good set of experts.

Eviction rule – A first attempt
The first key step and the deviation from previous work of [54] is a new eviction rule.
Recall we have only polylogarithmic space and need to keep a small set of core experts.
For each expert $i \in \mP$ we compare its aggregate loss over its lifetime in the pool with the following very powerful benchmark:

The Covering Benchmark: Consider a hypothetical algorithm that in each epoch switches to the single best (in hindsight) expert in the pool for that epoch. Our benchmark is the total aggregate loss of this hypothetical algorithm[Contrast this benchmark with the standard notion of regret where the benchmark is a single expert for the entire stream.].

If the expert does not have a strictly better loss than this benchmark, we say that it is covered by the other experts in the pool and it is subject to eviction.
Intuitively, while this benchmark is strong, it suffices that an expert is covered by the pool to guarantee that running MWU over the pool would have low regret compared to that expert.

* Memory. The immediate advantage of this powerful benchmark is the saving of memory.
For a set of experts that survive the eviction, it is easy to see that the suffix spanned by the last $r$ experts has an overall advantage of at least $2^{r-1}$.
This indicates $|\mP|\leq O(\log T)$, otherwise the maximum loss exceeds $T$.
In other words, only $O(\log T)$ experts survive after the pruning step!
Finally, we note that to avoid recording the loss of each epoch, it actually suffices to record the pairwise loss and the memory scales quadratically with the size of the pool.

* Regret analysis (wishful)  Let $i^{*}$ be the best expert. For the regret analysis, we divide the entire epochs into two types. An epoch is “good”, if had we sampled  $i^{*}$ in this epoch, it will eventually be covered and evicted from the pool. Consider the interval from the current good epoch until $i^*$ is kicked out of the pool. We want to argue the algorithm's performance on the entire interval is comparable to $i^*$  even if $i^*$ is never sampled. An epoch is “bad”, if had we sampled  $i^{*}$ in this epoch, it will never be kicked out from the pool. We have no control over the regret in a bad epoch,
but intuitively we can only suffer a few bad epochs before we sample $i^{*}$ and keep it forever.

There is a fatal issue in formalizing the above outlined approach.
We want to analyse the regret by considering a hypothetical situation that $i^{*}$ is sampled into the pool at a given epoch, but the eviction time could depend on experts enter lately in the pool.
That is to say, we need to fix the entire sequence of selected experts when defining the good/bad epochs. However, once $i^{*}$ is really sampled into the pool, it interferes with the rest of pool, because adding $i^{*}$ into the pool might kick out other experts, the kicked out expert might allow the pool to keep other experts (that were supposed to be removed), etc. This issue seems subtle but fixing it turns out to be technically very challenging!

A robust algorithm We depict the high level intuition for fixing the above issue. The overall idea is to make the entire algorithm insensitive or “robust” to the addition of a single new expert in any epoch.
Instead of performing the pruning step in every epoch, we maintain $L +1 = O(\log T)$ disjoint sub-pools $\mP = \mP_0 \cup \cdots \cup \mP_{L}$, where the $\ell$-th sub-pool $\mP_{\ell}$ ($\ell \in [0:L]$) contains experts added in the most recent $2^{\ell}$ epochs, and it is merged into the higher sub-pool $\mP_{\ell+1}$ every $2^{\ell}$ epochs. This modification is critical for a robust algorithm as it ensures an expert can potentially participate in the eviction process at most $O(\log T)$ times (instead of every epoch).

Given two adjacent sub-pools $\mP_{\ell}, \mP_{\ell+1}$, the merging step needs to ensure (1) the output sub-pool has small size; and (2) the outcome should be insensitive to a single change[At this stage, it seems like we need a “differential private merging/pruning” procedure. Differential privacy techniques were indeed an inspiration, but they do not directly apply.

The memory analysis is very delicate and sensitive to even a small perturbation caused by a standard DP mechanism.
The final merging and pruning step is an iterative procedure.
At each iteration, we estimate the size of $\mP_{\ell} \cup \mP_{\ell+1}$ (in an insensitive way), and if it is too large, then we sample $\frac{1}{\polylog (nT)}$-fraction of experts and use them to filter the sub-pool. This is repeated for $O(\log(nT))$ times and we prove that it removes $\Omega(\frac{1}{\log (nT)})$-fraction of experts at each iteration w.h.p.

A more detailed description of the baseline algorithm In summary, the baseline algorithm maintains $L + 1$ sub-pools $\mP$, and for  $\ell \in [0:L]$ the $\ell$-th sub-pool $\mP_{\ell}$ is merged with $\mP_{\ell+1}$ every $2^{\ell}$ epochs.  The merge and pruning step proceeds in at most $K = O(\log (nT))$ iterations. At each iteration, it first estimates the size of $\mP_\ell\cup \mP_{\ell + 1}$ by sub-sampling and proceeds only if the size is large;
it then samples $\frac{1}{\polylog(nT)}$-fraction of the experts as the filter set $\mF$. An expert is removed if it is covered by $\mF$.

* Memory analysis.  The memory analysis now becomes involved and our goal is to prove $\Omega(\frac{1}{\log(nT)})$-fraction of experts are removed per iteration. To do so, we recursively identify (at most) $O(\log T)$ pivotal experts in $\mF$ such that the suffix of the last $r$ pivotal experts is at least $2^{r-1}$ better than a large fraction of remaining experts in the pool, unless $\Omega(\frac{1}{\log(nT)})$-fraction of experts has already been removed during the recursive procedure.

* Regret analysis.  An expert is passive if it never “participates” in the eviction process, i.e., it is never sampled in the filter set $\mF$ and the size estimation. It is active otherwise. The probability of being a passive expert is large, i.e., at least $(1 - \frac{1}{\polylog(nT)})^{2L\times 2K} \geq 1/2$.
In the analysis, we fix the set of sampled and active experts at each epoch and we divide the entire epochs into two types, defined similarly as before.
The set of sampled and passive experts are not fixed, but they do not influence the execution of the baseline algorithm (i.e., the estimate size, the filter set, the alive set of active experts).
The regret is controlled well for good epochs.
While for a bad epoch, if the expert $i^{*}$ is sampled and at the same time, being passive, then it would never be kicked out.
As the expert $i^{*}$ has probability $\Omega(\frac{1}{n})$ being sampled and passive, and we have proved the pool size rarely exceeds $\polylog(nT)$, the number of bad epoch is bounded by $\wt{O}(n)$.

In summary, the regret of baseline comes from three source (1) $\wt{O}(\sqrt{B})$ per epoch due to MWU; (2) $1$ for each interval containing good epochs; (3) $B$ for each bad epoch, hence the regret is upper bounded as
\wt{O}(\sqrt{B}\cdot (T/B) + (T/B) + B \cdot n) = \wt{O}(T/\sqrt{B} + nB).

A simple but sub-optimal bootstrapping  The baseline approach obtains $\wt{O}(n^{1/3}T^{2/3})$ regret after optimizing the epoch size.
A simple bootstrapping approach (similar and even simpler than the counterpart of [54]) can be used to decrease the regret and achieve optimal dependence on $T$.
Concretely, we have used a fairly crude regret bound of $B$ for bad epochs, this can be reduced by running a baseline (with sequence length $B$ instead of $T$) separately for each epoch, and the final decision is determined by running MWU over this epoch-wise baseline (sequence length $B$) and the entire baseline (sequence length $T$).

By doing so, the regret of a bad epoch is reduced to $\wt{O}(n^{1/3}B^{2/3})$ instead of $B$, and the regret of good epochs remains the same order.
The total regret becomes $\wt{O}(T/\sqrt{B} + n^{4/3}B^{2/3})$, and after balancing the epoch size, one obtains an improved regret of $\wt{O}(n^{4/7}T^{4/7})$.
The bootstrap method can be repeated for multiple times, attaining an algorithm of regret $\wt{O}(n\sqrt{T})$.
This already obtains the optimal dependence on $T$, but suboptimal by a factor of $\sqrt{n}$.

§.§.§ Optimal boosting against an oblivious adversary

The final oblivious adversary algorithm maintains multiple threads of the baseline with different parameters, and amortizes the regret carefully.
The new ideas (comparing with [54]) are (1) inheriting pools from a high frequency baseline to a low frequency baseline (instead of only the regret bound); (2) separating the pool maintenance and regret control.

Epoch assignment. Red segments are bad epochs of each thread, blue segments are intervals generated by the walk.

Detailed description of the walk in the figure: As the first epochs in threads 1 and 2 are bad, the walk moves to the first epoch of thread 3, where $i^*$ can be covered and evicted (interval $a_1$). In the next epoch, $i^*$ is not immediately covered so it moves down to thread 2 where it is covered (interval $a_2$). The walk moves to the next epoch (epoch 2 in thread 1), which is bad. The walk moves up to thread 2 where it finds a good epoch that immediately covers $i^*$ (interval $a_3$). The next thread-2 is epoch is bad, so the walk moves up to thread 3; there $i^*$ is covered immediately (interval $a_4$). After that, $i^*$ survives until it is finally covered in the last epoch (interval $a_5)$.

The full algorithm maintains $R = O(\log T)$ threads of baseline algorithms. The lowest thread has $n$ epochs and $B_1 = \frac{T}{n}$ days per epoch, the $r$-th ($r \in [2:R]$) thread has $2$ epochs only and each epoch contains $B_r = \frac{T}{2^{r-1} n}$ days – it restarts every $T_{r} = B_{r-1}$ days.

Every time we restart the $r$-th thread, we also start a new epoch of a lower thread (longer epochs); instead of discarding the experts in the $r$-th thread's pool, we move them to the lowest thread with a new epoch.
This is a key difference compared to the sub-optimal bootstrapping method.
It makes intuitive sense because one may hope the optimal expert has a better chance of being retained after a few rounds of sampling/pruning in the higher thread (though the final analysis turns out to be quite different). The memory bounds largely follow from the baseline and we outline the regret analysis.

Amortizing regret In the regret analysis, as before, we fix the set of active and sampled experts for each thread.
To account for all the regret incurred by the algorithm, our analysis splits the entire sequence into a collection of intervals, with different regret guarantees.
The splitting is defined by a walk over epochs at the different threads.
We note again that this walk is for analysis purposes only.

The walk starts from the first epoch of the bottom thread (longest epochs). We say that an epoch considered in the walk is bad if the set of alive active experts (union over all threads) would never cover $i^{*}$ until the end of the algorithm, had the expert $i^{*}$ entered the pool at the beginning of the epoch.

* Even if the current epoch is bad, we wouldn't want to pay maximal loss for the entirety of the epoch. Instead, the walk moves up to a higher thread with shorter epochs, in hope that we could at least cover $i^{*}$ for part of the epoch. (It continues moving up while the epoch is bad and while there are higher threads with shorter epochs, if the walk reached the maximum thread, we can afford a short bad epoch.)

* On good epochs, we can consider the interval from that epoch to the epoch where $i^{*}$ would be kicked out; it is guaranteed that the algorithm suffers a small regret over this interval (from the current epoch to the kicked-out epoch). By the definition of our tight boosting algorithm, if $i^{*}$ stays for sufficiently long, it will go down to lower threads (every time we restart $i^{*}$'s current thread, $i^{*}$  goes to the lowest thread with a new). Our walk follows $i^{*}$'s trajectory across epochs from different threads, until it is evicted.

* Once $i^{*}$ is evicted, we continue the walk moves to the next epoch that $i^{*}$ would have gone to if it were not evicted.
We see if that epoch is good or bad, and then continue with Steps 1 or 2 above.

In the analysis, we consider the intervals defined by Step 2 of the walk. On each interval $\mI$, the regret scales like $\sqrt{|\mI|}$, so we particularly want to bound the total time spent on short intervals. To do this, we show that every lower thread epoch that fully contains $\mI$ must be bad, and as we argued before there cannot be too many bad epochs.

Interval regret guarantee for monocarpic experts
One important detail is missing – the regret analysis goes through if we can guarantee an $O(\sqrt{|\mI|})$ regret (compared with the “epoch-wise” minimum of alive active experts) over any intervals $\mI$.
This is non-trivial and no longer guaranteed by “running MWU over each epoch”.
In particular, an interval could consist of epochs from different threads, and more importantly, the set of alive active experts need not come from the same thread (they could come from all threads).
We resolve the issue with a general procedure MonocarpicExpert, which obtains interval regret over any alive expert.

We consider a variant of the sleeping experts problem [29, 43] that we call monocarpic experts[The name is inspired by monocarpic plants, aka plants that only bloom once.]. In the monocarpic expert problem, the experts could enter and exit the pool at any time (but each expert only ever wakes up once) and we want an interval regret guarantee w.r.t. any alive expert.
That is, the algorithm is competitive with an expert at any time interval $\mI$ during its lifetime, with a regret of $O(\sqrt{|\mI|})$.
The monocarpic experts problem is closely related to the sleeping expert problem, but the difference is that a sleeping expert could re-enter the pool (i.e., its lifetime is not a consecutive period).
In this paper, we give a low memory algorithm for monocarpic experts with interval regret guarantees, whose memory scales linearly with the maximum number of alive experts.
This is obtained by binary division tricks and utilizes the recent advance of second-order regret guarantee (i.e., the Squint algorithm [47]).

Grouping trick Finally, to obtain $\wt{O}(\sqrt\frac{nT}{S})$ regret with $S$ space, we partition the experts into $\wt{O}(S)$ groups, and each group contains $\wt{O}(n/S)$ experts. We maintain a separate meta-thread of algorithm for each group and run the MWU on top of these $\wt{O}(S)$ threads  of algorithms.
This reduces the expert size from $n$ to $\wt{O}(n/S)$ and attains the  $\wt{O}(\sqrt{\frac{nT}{S}})$ regret.

§.§ Lower bound for adaptive adversary

We first delineate the high-level principle of constructing an adaptive adversary against a low memory (online learning) algorithm.
The adversary

* Attacks the most recent $S_r = \Omega(S)$ actions picked by the algorithm;

* Maintains a set of special experts $I$ ($ |I| = \Omega(S) \gg S_r$) that are good most of time.

Intuitively, the first principle demonstrates the memory advantage of an adaptive adversary.
While a low space online learning algorithm keeps only $S$ “good” experts in memory, an adaptive algorithm can make them bad once the algorithm releases them. The second principle ensures the existence of one good expert in $I$, this is because at any time, most experts in $I$ are not attacked (not played in the last $S_r$ rounds) and receive small loss.

For simplicity of exposition, we focus on the regime when the space $S = o(\sqrt{n})$ and we take the number of special experts $N = \sqrt{n}$.
The adversary first draws $(x_{A}, x_{B}) \in \{0,1\}^n\times \{0, 1\}^n \sim \mu^{N}$, where $\mu$ is some hard distribution for the set disjointness problem, with $\frac{n}{N} = \sqrt{n}$ coordinates.
The loss sequence is divided into $\frac{10T}{N}$ epochs and each epoch contains $\frac{N}{10}$ days.
The loss sequence of each epoch is constructed separately. During each epoch, the loss vector is set to $1 - x_{A}$ or $1- x_B$ with equal probability $1/2$, except for those coordinates that have been played by the algorithm during the current epoch – they are fixed to be $1/2$.
It is easy to see that the best expert receives at most $\frac{T}{20}$ loss over the entire sequence.
To obtain $o(T)$ regret, an online learning algorithm needs to commit at least $\Omega(N)$ different intersecting coordinates (of the $N$ set disjointness instance) at some epoch (otherwise the loss received is $\frac{T}{2} - o(T)$).

A natural three-party communication problem can be formulated as follow.
There is a prophet, Charlie, who knows all the $x_{A}$ and $x_B$, but it is only allowed to send $S$ bits of information at the beginning (this captures the initial memory state of an epoch).
Alice and Bob receive the input $x_A$ and $x_B$ separately, and they are allowed to communicate at most $\frac{N}{10}\cdot S$ bits.
The goal is to output $\Omega(N)$ intersecting coordinate at the end.

The challenging part is the $S$ bits advice from the prophet.
Our key observation is that one can get rid of the advice by seeking for a direct-product theorem.
In particular, a too-good-to-be-true three-party communication protocol would imply a two-party communication protocol that solves the $N$-copy set disjointness problem, with a total of $S\cdot \frac{N}{10} = o(n)$ bits communication, and success probability at least $\exp(-\wt{O}(S))$ (without advice!).
Roughly speaking, this holds from the fact that they can use the public randomness to guess the advice and it succeeds with probability $2^{-S}$ on average.
The set disjoint problem requires $\Omega(\sqrt{n})$ internal information cost per copy and
the direct-product theorem of [17] implies $\wt{\Omega}(n)$ bits of communication are necessary to resolve the problem with success probability at least $\exp(-\wt{O}(N)) \ll \exp(-\wt{O}(S))$.

§.§ Algorithm against adaptive adversary

Our algorithm for adaptive adversary completely differs from the one for oblivious adversary and it requires a set of new ideas.
Recall that we aim for an algorithm using $O(\sqrt{n}/\eps)$ space and obtaining $\eps T$ regret.
A natural idea is to observe (but not commit) an expert for some time before actually committing the action (or adding it to the pool).
However, the challenge is that an adaptive adversary can easily counter this type of algorithm by making an expert perform bad once it is released by the algorithm.
In other words, it seems that an expert becomes useless as soon as it is revealed, despite the enormous effort and difficulty of finding such a good expert.

Our solution is conceptually simple and it consists of two components.
We provide a sub-optimal version first.

* RandomExpert. The RandomExpert procedure sub-samples a new set of $\sqrt{n}/\eps$ experts per epoch, where each epoch contains $1/\eps^2$ days.
The goal of RandomExpert is to be $\eps$-competitive with the top $\sqrt{n}/\eps$-th expert within the epoch (i.e., to suffer at most $\eps$ more average loss than the $\sqrt{n}/\eps$-th expert of the epoch).
To handle the aforementioned challenge of adversary making the expert bad immediately after it is selected, we apply a common trick to make an algorithm work against adaptive adversary: The RandomExperts divides the set into $1/\eps^2$ groups, with $\eps \sqrt{n}$ experts per group.
It runs MWU separately for each group of experts, and at day $b$ ($b \in [1/\eps^2]$), it follows the decision from the $b$-th group.
The algorithm is guaranteed to be $\eps$-competitive with the top $\sqrt{n}/\eps$-th expert, because w.h.p. the RandomExpert samples one from the top $\sqrt{n}/\eps$ experts for each group.

* LongExpert. The LongExpert procedure maintains a pool $\mP$ of experts and runs MWU over $\mP$ during each epoch.
At each epoch, it samples a new random set of $\sqrt{n}/\eps$ experts and only observes their loss.
It compares their performance with the RandomExpert at the end of the epoch, and an expert is added to $\mP$, if its performance is $\Omega(\eps)$ better than the RandomExpert. The expert is kept for $\sqrt{n}$ epochs.

The final algorithm runs MWU over the RandomExpert and the LongExpert procedure.

The analysis is fairly intuitively

* Memory bounds. The LongExpert reserves $O(1/\eps^2)$ experts per epoch, since only the top $\sqrt{n}/\eps$ experts would be kept (due to the regret guarantee of RandomExpert), and it samples $\sqrt{n}/\eps$ experts per epoch.
An expert is kept in $\mP$ for $O(\sqrt{n})$ epochs, so the total memory used is $O(\sqrt{n}/\eps^2)$.

* Regret analysis.
For any expert $i\in [n]$, if it is not among the top $\sqrt{n}/\eps$ experts or it is not $\eps$ worse than the RandomExpert, then it causes at most $\eps$-regret in an epoch.
On the other hand (i.e., it is a top $\sqrt{n}/\eps$ expert and performs significantly better than the RandomExpert), with probability $\frac{1}{\eps\sqrt{n}}$, it is sampled and kept for $\sqrt{n}$ epochs (and afflicts $\eps$ average regret over these $\sqrt{n}$ epochs).
Intuitively speaking, this means, in order to make our algorithm perform bad on one epoch (and causes at most 1 average regret / epoch),
the adversary should punish this top expert for $\sqrt{n}$ epochs, worsening the loss of the average top expert by
$\frac{1}{\eps\sqrt{n}} \cdot \sqrt{n} = 1/\eps$ epochs in expectation, so an averaged of $\eps$ regret is obtained.

Optimizing the regret
The above algorithm obtains $O(\eps T)$ regret using $O(\sqrt{n}/\eps^2)$ space.
The sub-optimality comes from that experts that are $\alpha$-better than the RandomExpert are treated equally, for any $\alpha \in (\eps, 1]$.
To circumvent this inefficiency, we maintain $R = \log_2(1/\eps)$ threads of RandomExpert. The epoch size is still $1/\eps^2$ and let $\eps_r = 2^{r}\eps$ ($r\in [R]$).
The $r$-th thread RandomExpert samples $\eps_r^2\sqrt{n}/\eps$ experts, runs MWU for $1/\eps_r^2$ days and  repeats for $\eps_r^2/\eps^2$ times per epoch.
It is guarantee to be $\eps_r$-competitive with the top $\eps \sqrt{n}/\eps_r^2$-th expert (a worse regret guarantee, but comparable against top performance experts).
The LongExpert maintains $R$ sub-pools $\mP_1, \ldots, \mP_{R}$, the $r$-th pool samples $\sqrt{n}/\eps$ experts and observes their performance for $1/\eps_r^2$ days (it also restarts  for $\eps_r^2/\eps^2$ times per epoch). It only keeps experts that are $\eps_r$-better than the $r$-th thread RandomExpert, and an expert is kept for $\eps \sqrt{n}$ epochs (so $\sqrt{n}/\eps$ days in total).
A MonocarpicExpert procedure is executed on $\mP$.
We note an expected number of $O(1/\eps_r^2) \cdot (\eps_r^2/\eps^2) = O(1/\eps^2)$ experts are added to thread $r$ pool per epoch $\times$ they stay there for $\eps \sqrt{n}$ epochs, so the memory is bounded by $O(\sqrt{n}/\eps)$.
The regret analysis becomes a bit more complicated and we only sketch the intuition here.
If an expert is $\Theta(\eps_r)$ better than the $\eps \sqrt{n}/\eps_r^2$-th expert, then it incurs an average of $\eps_r$ loss over $1/\eps_r^2$ days. At the same time, with probability $1/\eps\sqrt{n}$, it is sampled and kept in the sub-pool $\mP_{r}$ for $\sqrt{n}/\eps$ days. Hence it has $(1/\eps_r) \cdot (\eps\sqrt{n}) / (\sqrt{n}/\eps) \leq \eps$ regret on average.
The complication  arises from the expert might not be $\Omega(\eps_r)$ worse in the first $1/\eps_r^2$ days, in that case, the RandomExpert procedure only guarantees $O(\eps_r)$ (instead of $O(\eps)$) regret and we need to carefully attribute the epoch in the analysis. We leave the technical details to Section <ref>.

One may tempt to obtain an algorithm against adaptive adversary using the recent developed technique of differential privacy (DP) [39, 13] on top of our oblivious algorithm.

This approach does not apply to our main setting because the algorithm is required to output the actual action, instead of a single binary prediction value which can be hidden via a DP median mechanism.
This seems to be an inherent limit of the DP approach and it is much more challenging to hide the actual action, which is critical for broader applications of the online learning algorithm.[For example, in the application of game theory, the opponent observes the actual action; in many applications of machine learning, the opponent observes the hypothesis outputs by the algorithm ]

Meanwhile, if we narrow down the online learning task and only require to output a binary prediction (e.g., the task is to predict whether it is going to rain or not, and the expert offers 0/1 advice), then the DP technique is indeed applicable, but only obtains a sub-optimal regret bound of $\wt{O}(\frac{n^{1/4}T}{\sqrt{S}})$.
We provide a short explanation here.

The typical setup of the DP approach is to maintain $K$ copies of the oblivious algorithm, each uses $S'$ space. The total space is $S = KS'$ and we need to balance $K$ and $S'$. The typical choice is to take $K = O(\sqrt{T})$ and apply a DP median mechanism each round. However, there is substantial difference between online learning and the typical streaming applications. In a typical streaming application, each copy is guaranteed to be correct with high probability so taking median is a good idea, while for online learning, there is no such guarantee and it is easy to construct an example showing the median approach suffers $\Omega(1)$ regret. Instead, we should apply a DP mean mechanism and choose $K = \sqrt{T}/ \eps$ to obtain $\eps$ regret on average. Balancing these terms, the total regret is of order $\wt{\Theta}(\frac{n^{1/4} T}{\sqrt{S}})$, which is worse than our Theorem <ref>.

§.§ Organization of the paper

Section <ref> provides formal definitions and introduces the background. We provide the algorithm for oblivious adversary in Section <ref>. Section <ref> and Section <ref> provide the upper and lower bound for adaptive adversary.

§ PRELIMINARY

We consider the standard model of online learning with expert advice.

In an online learning problem, there are $n$ experts and the algorithm is initiated with a memory state $M_0$. At the $t$-th day ($t\in [T]$),

* The algorithm picks an expert $i_t \in [n]$ bases on its internal state $M_{t-1}$;

* The nature reveals the loss vector $\ell_{t} \in [0,1]^n$;

* The algorithm receives loss $\ell_t(i_t)$, observes the loss vector $\ell_t$ and update its memory state from $M_{t-1}$ to $M_{t}$.

The loss vector is chosen adversarially:

* Oblivious adversary. An oblivious adversary (randomly) chooses the loss sequence $\ell_1, \ldots, \ell_T$ in advance.

* Adaptive adversary. An adaptive adversary chooses the loss $\ell_t$ at the beginning of day $t$ and it could depend on the past action $i_1, \ldots, i_{t-1}$.

An algorithm uses at most $S$ words of memory if $\max_{t\in [T]}|M_t| \leq S$.

The performance of the algorithm is measured as regret, which is defined as

\[
R(T) := \E\left[\sum_{t=1}^{T}\ell_t(i_t) - \min_{i^{*} \in [n]} \sum_{t=1}^{T}\ell_{t}(i^{*})\right]
\]

where the expectation is taken over the randomness of algorithm and the choice of $\ell_t$. The average regret is defined as $R(T)/T$.

Notation In an online learning problem, let $T$ be the total number of days, $n$ be the number of experts. Let $[n] = \{1,2, \ldots, n\}$ and $[n_1:n_2] = \{n_1,\ldots, n_2\}$. We sometimes use $\N$ to denote the set of experts. For any integer $t$, let $\mathsf{pw}(t)$ be the largest integer such that $t$ is a multiple of $2^{\mathsf{pw}(t)}$. Let $\Delta_n$ contain all probability distributions over $[n]$.

Regret guarantee of existing online learning algorithm

We make use of existing algorithms in online learning literature. The multiplicative weight update (see Algorithm <ref>) is the most fundamental algorithm.

MWU [5]

[1]
$t=1,2, \ldots, T$
Compute $p_t \in \Delta_n$ over experts such that $p_t(i) \propto \exp(-\eta \sum_{\tau=1}^{t-1}\ell_\tau(i))$ for $i\in [n]$
Sample an expert $i_t \sim p_t$ and observe the loss vector $\ell_t \in [0, 1]^n$

Let $n, T \geq 1$, $\eta > 0$ and the loss $\ell_t \in [0,1]^n$ ($t\in [T]$). The MWU algorithm guarantees

\begin{align*}
\sum_{t=1}^{T} \langle p_t, \ell_t\rangle - \min_{i^{*}\in [n]}\sum_{t=1}^{T}\ell_t(i^{*}) \leq \frac{\log n}{\eta} + \eta T,
\end{align*}

Taking $\eta = \sqrt{\log (n/\delta)/T}$, with probability at least $1-\delta$,

\begin{align*}
\sum_{t=1}^{T}  \ell_t(i_t) - \min_{i^{*}\in [n]}\sum_{t=1}^{T}\ell_t(i^{*}) \leq O\left(\sqrt{T \log (n/\delta)}\right).
\end{align*}

Define $v_{t}(i) = \langle p_t, l_t\rangle - \ell_t(i)$ be the loss difference between expert $i$ and the algorithm, the Squint algorithm (See Algorithm <ref>) provides second order guarantee.
Squint [47]

[1]
$t=1,2, \ldots, T$
Compute $p_t \in \Delta_n$ over experts such that

$p_t(i)  \sim \E_{\eta}\left[\eta \cdot \exp\left(\eta \sum_{\tau=1}^{t-1}v_{\tau}(i) - \eta^2 \sum_{\tau=1}^{t-1}v_{\tau}^2(i)\right)\right] $

Sample an expert $i_t \sim p_t$ and observe the loss vector $\ell_t \in [0, 1]^n$

Suppose the learning rate $\eta$ is sampled from the prior distribution of $\gamma$ over $[0, 1/2]$ such that $\gamma(\eta) \propto \frac{1}{\eta\log^2(\eta)}$. For any expert $i \in [n]$, the Squint guarantees that

\begin{align*}
\E\left[\sum_{t=1}^{T}\ell_t(i_t) - \sum_{t=1}^{T}\ell_{t}(i)\right] \leq O\left(\sqrt{V_T^i \log (nT)}\right).
\end{align*}

where $V_T^i = \sum_{t=1}^{T}(\E_{i_t}[\ell_t(i_t)] - \ell_t(i))^2$ is the loss variance of expert $i$.

Information theory We use standard notation from information. Let $X, Y$ be random variables, $H(X)$ be the entropy and $I(X; Y)$ be the mutual information. In a two-party communication problem, the internal information cost is defined as follows.

The internal information cost of a communication protocol $\Pi$ over inputs drawn from $\mu$ on $X\times Y$ is defined as

\[
\IC_{\mu}(\Pi) := I(X; \Pi |Y) + I(Y; \Pi |X).
\]

§ NEAR OPTIMAL BOUND FOR OBLIVIOUS ADVERSARY

We have the following regret guarantee for an oblivious adversary.

§.§ The baseline-subroutine building block

We first provide a baseline subroutine that achieves the following regret guarantee.

Let $n , T\geq 1$ be sufficiently large integers, for any $B \in [T]$, there is an online learning algorithm that uses at most $\polylog(nT)$ space and achieves $\widetilde{O}\left(nB + \frac{T}{\sqrt{B}}\right)$ regret against an oblivious adversary.

The pseudocode of the baseline subroutine is presented in Algorithms <ref>–<ref>.
The Baseline (i.e. Algorithm <ref>) proceeds epoch by epoch, and each epoch contains $B$ days.
It maintains a pool $\mP$ of experts and at the beginning of each epoch, it adds $O(1)$ random experts into the pool $\mP$ (Line <ref> of Algorithm <ref>).
It runs MWU over experts in $\mP$ within the epoch.
The pool size grows quickly and the algorithm prunes the pool at the end of each epoch.

The entire pool $\mP$ is divided into $L+1 =  \log_2(T)  + 1$ disjoint sub-pools $\mP = \mP_{0}\cup\cdots \cup \mP_{L}$. Roughly speaking, $\mP_{\ell}$ only contains experts sampled in the most recent $2^{\ell}$ epochs and it is merged into $\mP_{\ell+1}$ every $2^{\ell}$ epochs.

The Merge procedure (Algorithm <ref>) merges the sub-pool $\mP_{\ell}$ into $\mP_{\ell+1}$ and performs subsequent pruning step to control the pool size.
In particular, it proceeds in $K = 16  \log(nT) $ iterations, and at the $k$-th iteration, whenever the sub-pool size is greater than a threshold of (roughly) $\log^9 (nT)$, it samples $\frac{1}{\log^4 (nT)}$-fraction of experts $\mF_{k}$ and use them to filter $\mP_{\ell+1}$.
Looking ahead, we shall prove that each iteration removes at least $\Omega(\frac{1}{\log (nT)})$-fraction of experts in $\mP_{\ell+1}$, unless  $\mP_{\ell+1}$ is already small.
We note that both the size estimation and the sampling step (i.e. Algorithms <ref> and <ref>)  are performed in an insensitive way, which is critical to the memory analysis.

The core idea lies in the Filter procedure (Algorithm <ref>), it takes a set of experts $\mF$ and a pool $\mQ$, and an expert $i$ is removed from $\mQ$ if it is covered by experts in $\mF$ (see Definition <ref>).

Notation To formally introduce the concept of covering, we need some notations.
For any epoch $t\in [T/B]$, let $\mP_{\ell}^{(t)}$ ($\ell \in [0: L]$) be the sub-pool $\mP_{\ell}$ at the beginning of epoch $t$ (after Line <ref> of Algorithm <ref>) and
similarly let  $\mP^{(t)}$ denote the entire pool at the same time.
Our algorithm samples experts with replacement; even if it samples the same expert twice (in different epochs), we will treat it as two separate experts.

For expert $i \in \mP^{(t)}$, let $E_i \in [T/B]$ denote the time when expert $i$ was sampled and entered the pool.
For experts $i, j \in \mP^{(t)}$, we write $i \preceq j$ if $E_{i} \leq E_{j}$, i.e., the expert $i$ enters the pool no later than the expert $j$.
Let $\Gamma_{i, j}$ be the time interval $\{E_{i}, \ldots, E_{j} - 1\}$ ($\Gamma_{i, j} = \emptyset$ if $j$ enters the pool no later than $i$), and slightly abuse of notation, let $\Gamma_{i, t}$ be the time interval $\{E_i, \ldots,  t\}$.
For any interval $\mI \subseteq [T/B]$, the cumulative loss of expert $i$ over $\mI$ is defined as

\begin{align*}
\mL_{\mathcal{I}}(i) := \sum_{t\in \mathcal{I}}\sum_{b=1}^{B}\ell_{(t-1)B +b}(i).
\end{align*}

In particular, define

\begin{align*}
\mL_{\Gamma_{i, j}}(i) := \left\{
\begin{matrix}
\sum_{t\in \Gamma_{i, j}}\sum_{b=1}^{B}\ell_{(t-1)B +b}(i) & \Gamma_{i, j} \neq \emptyset \\
+\infty & \Gamma_{i, j} = \emptyset
\end{matrix}
\right.
\end{align*}

be the cumulative loss of expert $i$ during interval $\Gamma_{i, j}$. Slightly abusing notation, we set $\mL_{t}(i) = \sum_{b=1}^{B}\ell_{(t-1)B +b}(i)$ to be the total loss of expert $i$ during epoch $t$.

Now we can formally define the cover.

Given a set of experts $\mF = \{i_1, \ldots, i_{|\mF|}\}$ and an expert $j\in [n]$. Let $i_1 \preceq i_2 \cdots \preceq i_r \preceq j \preceq i_{r+1} \cdots \preceq i_{|\mF|}$ for some $r \in \{0, 1,2,, \ldots, |\mF|\}$.
At epoch $t$, we say expert $j$ is covered by $\mF$, if

\begin{align}
\mathcal{L}_{\Gamma_{j,t}}(j) \geq  \min_{i_{r}^{*} \in \mF}\mL_{\Gamma_{j, i_{r+1}}}(i_r^{*}) + \left(\sum_{s = r+1}^{|\mF|}\min_{i_{s}^{*} \in \mF}\mL_{\Gamma_{i_{s}, i_{s+1}}}(i_s^{*})\right)  - 1.
\end{align}

Here we slightly abuse notation and denote $\Gamma_{i_{|\mF|}, i_{|\mF|+1}} = \Gamma_{i_{|\mF|}, t}$.

Finally, it is worth noting that the Baseline only needs to record the loss $\mathcal{L}_{\Gamma_{i, j}}(i)$ for $i, j \in \mP$, which scales quadratically with the size of pool.

[1]
Initiate the pool $\mP \leftarrow \emptyset$ and sub-pools $\mP_{\ell} \leftarrow \emptyset$ ($\ell \in [0:L]$) $L = \log_2 (T)$
$t = 1,2, \ldots, T/B$ Epoch $t$
$\mP_0 \leftarrow \textsc{Sample}(\N, 1/n)$ Sample new experts into the pool
Run MWU over $\mP$ for the next $B$ days $\mP = \mP_0 \cup \cdots \cup \mP_{L}$
$\ell = 0,1, \ldots, \mathsf{pw}(t)$ $\mathsf{pw}(t)$ is the largest integer such that $(t/2^{\mathsf{pw}(t)}) \in \mathbb{N}$
$\mP_{\ell+1} \leftarrow \textsc{Merge}(\mP_{\ell+1}, \mP_{\ell})$
$\mP_{\ell} \leftarrow \emptyset$

Merge($\mQ_A, \mQ_B$)

[1]
$\mQ_C\leftarrow \mQ_A \cup \mQ_B$
$k=1,2, \ldots, K $ $K = 16  \log(nT) $
$s \leftarrow \textsc{EstimateSize}(\mQ_C, \frac{1}{\log^4 (nT)})$   Estimate the size of $\mQ_C$
$s \leq \log^5 (nT)$
Go to Line <ref>
$\mF_k \leftarrow \textsc{Sample}(\mQ_C, \frac{1}{\log^4 (nT)})$ Sample $\frac{1}{\log^4 (nT)}$-fraction of experts
$\mQ_C \leftarrow \textsc{Filter}(\mF_{k},\mQ_C) \cup \mF_{k}$
Return $\mQ_C$

EstimateSize($\mQ, p$)

[1]
$p_{i} \leftarrow \text{Bernoulli}(p)$ for every $i \in \mQ$
Return $\sum_{i \in \mQ}p_i$

Sample($\mQ, p$)

[1]
$p_{i} \leftarrow \text{Bernoulli}(p)$ for every $i \in \mQ$
Return $\{i\in \mQ: p_{i} = 1\}$

Filter($\mF, \mQ$)

[1]
each expert $i \in \mQ$
$\mF$ covers $i$ Definition <ref>
$\mQ \leftarrow \mQ \setminus \{i\}$
Return $\mQ$

§.§.§ Memory bound

We first provide the memory guarantee for Baseline.

With probability at least $1-1/(nT)^{\omega(1)}$, the total memory used by Algorithm <ref> is at most $O(\log^{20} (nT))$ words.

The key observation comes from the following guarantee of Merge procedure.

With probability at least $1-1/(nT)^{\omega(1)}$, the output $\mQ_{C}$ of Merge procedure satisfies
\begin{align*}
|\mQ_{C}| \leq \max\left\{2\log^9 (nT), \frac{1}{4}(|\mQ_A| + |\mQ_{B}|)\right\}.
\end{align*}

Suppose the Filter procedure has been called for $k_{\max} \in [0:K]$ times and let $\mQ_{C,k}$ be the status of pool $\mQ_{C}$ at the beginning of $k$-th loop.
Note that $|\mQ_{C,1}| = |\mQ_{A}| + |\mQ_{B}|$.
For any $k \in [k_{\max}]$, our goal is to prove, with probability at least $1-1/(nT)^{\omega(1)}$,

* Either $|\mQ_{C, k}| \leq 2 \log^9 (nT)$; or

* $|\mQ_{C, k+1}| \leq (1 - \frac{1}{6\log (nT)})|\mQ_{C,k}|$.

Suppose we have proved the claim, then taking a union bound over $k \in [k_{\max}]$, it guarantees that

\begin{align*}
|\mQ_{C,k_{\max}+1}| \leq &~ \max\left\{ 2\log^9 (nT), \left(1 - \frac{1}{6\log (nT)}\right)^{16\log(nT)} |\mQ_{C,1}|\right\}\\
\leq &~ \max\left\{ 2\log^9 (nT), \frac{1}{4}(|\mQ_A| + |\mQ_{B}|)\right\}.
\end{align*}

To prove the claim, fix an iteration $k \in [k_{\max}]$ and assume $|\mQ_{C,k}| > 2\log^9 (nT)$, it suffices to prove $|\mQ_{C, k+1}| \leq (1 - \frac{1}{6\log (nT)})|\mQ_{C, k}|$ holds with high probability.
First, it passes the threshold test (Line <ref> of Merge) with high probability, since

\begin{align*}
\Pr[s \leq \log^{5}(nT)] = \Pr\left[\sum_{i\in \mQ_{C,k}}p_i \leq \log^{5}(nT)\right] \leq \exp(-\log^4(nT)/4) = 1/(nT)^{\omega(1)}.
\end{align*}

The second step follows from the Chernoff bound and the fact that (1) $\{p_i\}_{i \in \mQ_{C,k}}$ are independent Bernoulli variables with mean $\frac{1}{\log^4(nT)}$; (2) $|\mQ_{C, k}| \geq 2\log^{9}(nT)$.

We next analyse the Filter procedure and prove with high probability (over the choice of $\mF_k$), at least $\frac{1}{6\log nT}$-fraction of experts would be removed.  We prove that this set of experts exists iteratively.

* At the $r$-th iteration of the analysis we identify a subset $R_r$ that are removed with high probability over the choice of $\mF_k$. If $R_r$ is not too small ($\Omega(1/\log(nT))$-fraction of the sub-pool), we are guaranteed to reduce the size of the sub-pool so we're done.

* Otherwise, we identify $r$ pivot experts of $\mF_k$ and a large ($1-O(r/\log(nT))$-fraction of the subset $\mW_{r+1}$ whose loss is quite large. Specifically, consider the suffix of the epochs spanned by the $r$ experts in $\mF_k$. Any expert in $\mW_{r+1}$ is covered by those $r$ experts over this suffix — and furthermore this continues to hold even if we give the experts in $\mW_{r+1}$ an additive $2^{r-1}$ loss reduction.  This cannot continue to hold if the loss reduction exceeds the total possible loss of $T$, hence the previous case of large $R_r$ must hold for some $r \le \log(nT)$.

Setting up notation for the analysis:
Let $S = |\mP^{(k)}_{C}|$ and $\mQ_1 = \mP^{(1)}_{C}$.
We start from the base case. For any expert $i \in \mQ_1$, let

\begin{align*}
D_1(i) := \{j \in \mQ_1 \setminus \{i\}, \mL_{\Gamma_{i, t}}(i) \geq \mL_{\Gamma_{i, t}}(j) - 1 \},
\end{align*}

that is, the set $D_1(i)$ contains experts that are comparable with expert $i$ over its life time.

\[
R_1 = \{i: i \in \mQ_1, |D_1(i)| \geq \log^6 (nT) \}.
\]

The set $R_1$ contains every expert $i$ that has a large size $D_1(i)$; i.e. these are the experts that are easily removed because they are could replaced by any single expert from $D_1$.

§.§.§ The first iteration of the analysis

We now consider two cases: in the first case, the set of easily removable experts $R_1$ is large, so we can just remove them!
In the second case while it is hard to cover the typical expert with a single expert, we will show by induction that the typical expert can be covered by pooling together several experts.

Case 1. If $|R_1| \geq \frac{1}{4\log (nT)}S$. We prove with high probability that experts in $R_1$ are removed by the Filter procedure.
For any expert $i \in R_1$, each expert $j \in D_1(i)$ is included into $\mF_k$ with (independent) probability $\frac{1}{\log^4(nT)}$, hence,

\begin{align*}
\Pr\left[j \notin \mF_{k}, \forall \, j \in D_1(i)\right] \leq \left(1 - \frac{1}{\log^4 (nT)}\right)^{\log^6 (nT)} \leq 1/(nT)^{\omega(1)}.
\end{align*}

The first step follows from $|D_1(i)| \geq \log^{6}(nT)$ holds for any $i \in R_1$.

Meanwhile, whenever an expert $j \in D_1(i)$ is included in $\mF_k$, expert $i$ would be evicted as it is covered by $j$, unless $i \in \mF_k$. That is, with probability at least $1 - 1/(nT)^{\omega(1)}$, the set of experts $R_1\setminus \mF_{k}$ are removed. Note that $|R_1| \geq \frac{1}{4\log (nT)}S$ and by Chernoff bound, the size of $\mF_k$ satisfies

\begin{align}
\Pr\left[|\mF_{k}| \geq \frac{2}{\log^4(nT)} S \right] \leq \exp(S/4\log^4(nT)) \leq 1/(nT)^{\omega(1)}.\label{eq:f-size}
\end{align}

Taking a union bound, we have $|R_1\setminus \mF_{k}| \geq \frac{1}{6\log (nT)}$ with high probability and we have already identified a large set to be removed.

Case 2. If $|R_1| < \frac{1}{4\log (nT)}S$.
Let $j_1 \in \mQ_1 \setminus R_1$ be the latest expert sampled into $\mF_{k}$.
With probability at least $1 - 1/(nT)^{\omega(1)}$, there are at most $\log^6 (nT)$ experts later than $j_1$ in set $\mQ_1 \setminus R_1$, since the experts are included in $\mF_k$ independently with probability $\frac{1}{\log^4(nT)}$.
Denote this set to be $O_1$ (hence $|O_1| \leq \log^6 (nT)$).
Set $\mQ_2 = \mQ_1 \setminus (R_1\cup O_1 \cup D_1(j_1))$.
The size of $\mQ_2$ satisfies

\begin{align}
|\mQ_2| \geq S - \frac{1}{4\log (nT)}S - \log^6 (nT) -  \log^6 (nT) \geq S - \frac{1}{2\log (nT)}S, \label{eq:ind-base1}
\end{align}

and every expert $i \in \mQ_2$ satisfies

\begin{align}
\mL_{\Gamma_{j_1, t}}(i) \geq \mL_{\Gamma_{j_{1}, t}}(j_1) + 1. \label{eq:ind-base2}
\end{align}

Setting up notation for the analysis: Let $M = |\mQ_{C, k}|$. For any $r \geq 1$, we iteratively define

\begin{align*}
\mW_{r+1} := \mW_{r} \backslash (R_{r} \cup O_{r} \cup D_{r}(j_{r})) \quad \text{and} \quad \mW_{1} = \mQ_{C,k}.
\end{align*}

The definitions of $j_r, R_{r}, O_{r}$ and $D_{r}(j_{r})$ are presented subsequently.

We first define the set $D_r(i)$ for every expert $i \in \mW_r$, let

\begin{align*}
D_r(i) := \{j \in \mW_r \setminus \{i\}, \mL_{\Gamma_{i, j_{r-1}}}(i) \geq \mL_{\Gamma_{i, j_{r-1}}}(j) - 2^{r-1} \}, \forall i \in \mW_{r}.
\end{align*}

Here we slightly abuse notation and take $\Gamma_{i, j_0} = \Gamma_{i,t}$.
In other words, the set $D_r(i)$ contains experts that are comparable with expert $i$ over the interval $\Gamma_{i, j_{r-1}}$.

We next define the set $R_r$, let

\begin{align*}
R_r = \{i: i \in \mW_r, |D_r(i)| \geq  \log^6(nT)\}.
\end{align*}

The set $R_r$ contains every expert $i \in \mW_r$ that has a large size $D_r(i)$; i.e. we shall argue these are the experts that are easily removed because they are covered by the combination of $j_1, \ldots, j_{r-1}$ and any single expert from $D_r$.

Now, define the expert $j_r$ as the latest expert in $\mW_{r}\backslash R_{r}$ that is also sampled into $\mF_{k}$, i.e.,

\begin{align*}
j_r := \argmax_{j\in (\mW_r\backslash R_r) \cap \mF_{k}} E_{j}.
\end{align*}

Note if no such expert exists, i.e. $(\mW_r\backslash R_r) \cap \mF_{k} = \emptyset$, then we leave it undefined.

The set $O_r$ includes experts enter the pool later than $j_r$, i.e.

\begin{align*}
O_r = \{i: i \in \mW_r\backslash R_r, E_{i} \geq E_{j_r} \}.
\end{align*}

Inductive hypothesis.
Let $r \geq 1$, our inductive hypothesis conditions on the event that $R_{m} \leq \frac{1}{4\log(nT)}M$ for all $m \in [r]$. Looking ahead, these are the easy cases because the set of experts $R_m$ are easily removed.
We inductively prove

* $|\mW_{r+1}| \geq (1 - \frac{r}{2\log (nT)})M$;

* The experts $j_{1}, \ldots, j_{r} \in \mF_{k}$ and follow the order of $j_{r} \preceq j_{r-1} \preceq \cdots \preceq j_1$ ;

* For any $m \in [r]$ and expert $i \in \mW_{r+1}$,

\begin{align}
\mL_{\Gamma_{j_{m}, j_{m-1}}}(i) \geq \mL_{\Gamma_{j_{m}, j_{m-1}}}(j_m) + 2^{m-1}.\label{eq:ind1}
\end{align}

We prove the claims by induction and we note the base case of $r=0$ holds trivially. Suppose the induction holds up to $r-1$.

The analysis of $r$-th iteration.
We now consider two cases: in the first case, the set of easily removable experts $R_r$ is large, so we can just remove them!
In the second case, while it is hard to cover the typical expert with a single expert, we could continue the induction and prove the typical expert can eventually be covered by pooling together several experts.

Case 1. If $|R_r| \geq \frac{1}{4\log (nT)}M$. We prove with high probability that experts in $R_r$ are removed by the Filter procedure.
For any expert $i \in R_r$, each expert $j \in D_r(i)$ is included into $\mF_k$ with (independent) probability $\frac{1}{\log^4(nT)}$, hence,

\begin{align*}
\Pr\left[j \notin \mF_{k}, \forall \, j \in D_r(i)\right] \leq \left(1 - \frac{1}{\log^4 (nT)}\right)^{\log^6 (nT)} \leq 1/(nT)^{\omega(1)}.
\end{align*}

The first step follows from $|D_r(i)| \geq \log^{6}(nT)$ holds for any $i \in R_r$.

Therefore, with probability at least $1 - 1/(nT)^{\omega(1)}$, there exists at least one expert $j \in D_r(i)\cap \mF_k$. We claim that the expert $i$ is covered by $j, j_{r-1}, j_{r-2}, \ldots, j_{1}$. In particular, we have

\begin{align*}
\mL_{\Gamma_{i,t}}(i) = &~  \sum_{m=1}^{r-1}\mL_{\Gamma_{j_m, j_{m-1}}}(i) + \mL_{\Gamma_{i, j_{r-1}}}(i)\\
\geq &~ \sum_{m=1}^{r-1}(\mL_{\Gamma_{j_m, j_{m-1}}}(j_{m}) + 2^{m-1}) + \mL_{\Gamma_{i, j_{r-1}}}(j) - 2^{r-1}\\
= &~ \sum_{m=1}^{r-1}\mL_{\Gamma_{j_m, j_{m-1}}}(j_{m}) + \mL_{\Gamma_{i, j_{r-1}}}(j) -1,
\end{align*}

where we split the loss of $i$ in the first step, the second step holds due to the inductive hypothesis (see Eq. (<ref>)) and $j \in \D_r(i)$.

Hence, with probability at least $1 - 1/(nT)^{\omega(1)}$, the set of experts $R_r\setminus \mF_{k}$ are removed. Note that $|R_r| \geq \frac{1}{4\log (nT)}M$ and the size of $\mF_k$ satisfies

\begin{align*}
\Pr\left[|\mF_{k}| \geq \frac{2}{\log^4(nT)} M \right] \leq \exp(-M/4\log^4(nT)) \leq 1/(nT)^{\omega(1)},
\end{align*}

where the first step holds due to Chernoff bound.

Taking a union bound, we have $|R_r\setminus \mF_{k}| \geq \frac{1}{6\log (nT)}M$ with probability at least $1 - 1/(nT)^{\omega(1)}$ and we have already identified a large set to be removed.

Case 2. If $|R_r| < \frac{1}{4\log (nT)}M$.
Recall $j_{r}$ is defined as the latest expert of $\mW_{r}\setminus R_{r}$ that is sampled into $\mF_{k}$.
With probability at least $1-1/(nT)^{\omega(1)}$, at most $\log^6 (nT)$ experts arrive later than $j_{r}$, i.e., $|O_r|\leq \log^6 (nT)$. Recall the set $\mW_{r+1}$ is recursively defined as $\mW_{r+1} = \mW_{r} \setminus (R_{r}\cup O_r \cup D_r(j_{r}))$. We prove our inductive hypothesis continues to hold.
First, the size of $\mW_{r+1}$ satisfies

\begin{align*}
|\mW_{r+1}| \geq &~ |\mW_{r}| - |R_r| - |O_r| - |D_r(j_r)| \\
\geq &~ \left(1 - \frac{r-1}{2\log (nT)}\right) M - \frac{1}{4\log (nT)}M - \log^6 (nT) - \log^6 (nT) \\
\geq &~ \left(1- \frac{r}{2\log (nT)}\right)M.
\end{align*}

Second, it is clear that $j_r \in \mF_k$ by definition and it comes earlier than $j_{r-1}, \ldots, j_1$.
The third claim holds since $D_{r}(j_r) \cap \mW_{r+1} = \emptyset$, we have proved the induction.

Finally, if the event $R_{r} < \frac{1}{4\log(nT)} M$ continues to hold to $r =\log(nT) + 1$, then one has $D_{r}(i) = \mW_r$ for every expert $i \in \mW_{r}$, since the loss is at most $T$. Consequently, one as $|R_r| = |\mW_{r}| \geq \frac{1}{2}M$.
We conclude the proof here.

Now we can bound the pool size.

For any epoch $t\in [T/B]$ and sub-pool $\ell \in [0: L]$, with probability at least $1-1/(nT)^{\omega(1)}$, one has $|\mP_{\ell}^{(t)}| \leq 2\log^9 (nT)$.

We prove by induction on $\ell$. For the base case, at any epoch $t$, the sub-pool $\mP_{0}^{(t)}$ consists of the experts sampled at the beginning of epoch $t$ and one has

\begin{align*}
\Pr[|\mP_{0}^{(t)}| \geq 2\log^9(nT)] \leq \exp(- \log^9(nT)/3) \leq 1/(nT)^{\omega(1)},
\end{align*}

this comes from Chernoff bound and the fact that each expert is sampled with probability $1/n$.

Suppose the induction holds up to $\ell-1$ ($\ell \geq 1$), the sub-pool $\mP_{\ell}$ is empty at beginning, and it is merged with $\mP_{\ell-1}$ every $2^{\ell-1}$ epochs. That is to say, the input sub-pools ($\mP_{\ell}$ and $\mP_{\ell-1}$) of Merge both have size no more than $2\log^9(nT)$, hence by Lemma <ref>, with probability at least $1-1/(nT)^{\omega(1)}$, the output sub-pool $|\mP_{\ell}^{(t)}| \leq 2\log^9 (nT)$.

Now we are ready to prove Lemma <ref>.

By Lemma <ref>, at epoch $t$, the size of the pool is bounded by:

\[
|\mP^{(t)}| \leq \sum_{\ell=0}^{L}|\mP_{\ell}^{(t)}| \leq 2\log^9 (nT) \cdot 2\log(nT) = O(\log^{10} (nT)).
\]

To execute the Filter procedure,  it suffices to record loss of expert $i \in \mP^{(t)}$ over interval $\Gamma_{i, j}$ for any $i, j \in \mP^{(t)}$, it takes $O(\log^{10} (nT))$ words per expert and up to $O(\log^{20} (nT))$ words of memory in total. We have finished the memory analysis of Baseline.

§.§.§ Regret analysis

Let $i^{*}$  denote the best expert.
At a high level, the regret analysis considers two types of epochs, which can be informally described as follows:

* An epoch is “good”, if had we sampled  $i^{*}$ in this epoch, it will eventually be covered and kicked out of the pool. Consider the interval from the current good epoch until $i^*$ is kicked out of the pool: We argue that the algorithm's performance on the entire interval  is comparable to $i^*$ even if $i^*$ is never sampled.

* The set of “bad” epochs, denoted by $\mH$, are ones where $i^*$ would survive until the end of the stream.

Our plan is to argue that number of bad epochs must be small — otherwise the pool would overflow with many copies of $i^*$; but we had already proved in Lemma <ref> that the pool size is polylogarithmic.  For each bad epoch we have no control over the regret, but the total regret from bad epochs is small because there aren't many of them. (And as we explained above, on good epochs the algorithm is guaranteed to have low regret.)

There is a subtle issue with the above approach
[The issue is subtle but fixing was perhaps the most difficult part in coming up with the algorithm and analyzing it.]:
We want to analyze the regret by considering a hypothetical situation that $i^*$ is sampled into the pool at a given epoch. However, sampling $i^*$ also interferes with the rest pool going forward because $i^*$ may kick out other experts; kicking out some experts may allow the pool to keep other experts that should have been kicked out, etc. This makes it very difficult to compare the pool the algorithm actually uses and the hypothetical pool with $i^*$.

To handle the above subtlety, we carefully designed the algorithm so that even conditioned on $i^*$ having been sampled into the pool, w.h.p. it is never considered in the Sample and EstimateSize subroutines. Hence it does not interfere with the rest of the pool.

Random bits
It is useful to understand the random bits used for pool selection first.

For each epoch $t \in [T/B]$, let $\xi_{t} = (\xi_{t, 1}, \ldots, \xi_{t, n})$, where $\xi_{t, i}$ is used for expert $i$ ($i \in [n]$).
The random bits $\xi_{t, i} = (\xi_{t, i,1}, \xi_{t, i,2})$ consists of two parts, where $\xi_{t, i, 1} \in \{0, 1\}$ is a Bernoulli variable with mean $1/n$, and it is used for sampling expert $i$ into the pool (i.e. Line <ref> of Algorithm <ref>). Baseline adds expert $i$ at epoch $t$ if and only if $\xi_{t, i,1} = 1$.
The second part of the random bits $\xi_{t, i,2} \in \{0, 1\}^{2L \times 2K}$ are used for EstimateSize and Sample when calling the Merge procedure. Each coordinate of $\xi_{t, i,2}$ is a Bernoulli random variable with mean $\frac{1}{\log^4 (nT)}$ and the expert $i$ gets sampled for Sample and EstimateSize if the corresponding random bit equals $1$.

We introduce the concept of passive/active expert.

At any epoch $t\in [T/B]$, an expert $i$ is said to be passive, if $\xi_{t, i, 2} = \vec{0}$. It is said to be an active expert otherwise.

Epoch assignment
Fix the loss sequence $\ell_1, \ldots, \ell_{T}$ and the set of sampled and active experts $Y_t \subseteq [n]$ of each epoch $t$ (note that the set of sampled and passive experts are still not determined yet).
The key observation is that the estimate size $s$, the filter set $\mF$ as well as the set of alive active experts are fixed at any time during the execution of Baseline. They are completely determined by the loss sequence $\{\ell_t\}_{t\in [T]}$ and the sampled while active experts $\{Y_t\}_{t\in [T/B]}$.

We would divide the entire epochs into two types.  Consider the following epoch assignment mechanism. We start with $\tau \leftarrow 1$, $a_{1} \leftarrow 1$ and $\mH \leftarrow \emptyset$. Here the set $\mH \subseteq [T/B]$ collects all bad epochs that the algorithm has no controls over the regret.
Let $t(a_\tau) \in [a_{\tau}: T/B] \cup \{+\infty\}$ be the first time such that $i^{*}$ (with entering time $a_{\tau}$) is covered by the set of alive active experts at epoch $t(a_{\tau})$.
We note that the notion of covering is well-defined regardless of $i^{*}$ being sampled or not. We divide into two cases.

* Expert $i^{*}$ is never covered (i.e., $t(a_\tau) =+\infty$). Then we augment the set of bad epochs $\mH \leftarrow \mH \cup\{a_{\tau}\}$, and update $a_{\tau+1} = a_{\tau} + 1$, $\tau \leftarrow \tau + 1$;

* Otherwise, update $a_{\tau + 1} \leftarrow t(a_{\tau}) + 1$ and $\tau \leftarrow \tau + 1$.

The assignment process terminates once $a_{\tau}$ reaches $\frac{T}{B}$ and let $\tau_{\max}$ be the total number of steps.

We decompose the regret of Baseline based on the above assignment process and bound it in terms of the size of bad epochs $\mH$.

Fixing the loss sequence as well as the set of sampled and active experts of each epoch, with probability at least $1 - 1/(nT)^{\omega(1)}$ over the choice of MWU, one has

\begin{align*}
\sum_{t=1}^{T/B} \sum_{b=1}^{B} \ell_{(t-1)B + b}(i_{(t-1)B + b}) - \sum_{t=1}^{T/B}\mL_t(i^{*}) \leq O\left(\frac{T}{\sqrt{B}}\log (nT)\right)+ B \cdot |\mH|.
\end{align*}

Let $i_{t}^{*}$ be the best expert in the pool $\mP^{(t)}$ during epoch $t$, then with probability at least $1 - 1/(nT)^{\omega(1)}$, we have

\begin{align*}
&~ \sum_{t=1}^{T/B} \sum_{b=1}^{B} \ell_{(t-1)B + b}(i_{(t-1)B + b}) - \sum_{t=1}^{T/B}\mL_t(i^{*})\\
= &~ \sum_{t=1}^{T/B} \sum_{b=1}^{B} \ell_{(t-1)B + b}(i_{(t-1)B + b}) - \sum_{t=1}^{T/B} \mL_t(i^{*}_t) + \sum_{t=1}^{T/B} \mL_t(i^{*}_t) - \sum_{t=1}^{T/B}\mL_t(i^{*}) \\
\leq &~ \sum_{t=1}^{T/B}\mL_{t}(i_t^{*}) - \sum_{t=1}^{T/B} \mL_t(i^{*}) + \frac{T}{B}\cdot O\left(\sqrt{B}\log (nT)\right) \\
= &~ \sum_{t \in \mH}\mL_{t}(i_t^{*}) - \mL_t(i^{*}) + \sum_{\tau=1}^{\tau_{\max}}\sum_{t\in [a_{\tau}:a_{\tau+1}-1]\backslash \mH} \mL_{t}(i_t^{*}) - \mL_t(i^{*}) + O\left(\frac{T}{\sqrt{B}}\log (nT)\right)\\
\leq &~ B \cdot |\mH| + \tau_{\max} + O\left(\frac{T}{\sqrt{B}}\log (nT)\right)\\
\leq &~ B \cdot |\mH| + O\left(\frac{T}{\sqrt{B}}\log (nT)\right).
\end{align*}

The second step follows from the regret guarantee of MWU. We decompose the regret according to the assignment in the third step. The fourth step follows from the naive bound of $\mL_t(i_t) \leq B$ and the definition of a cover. The last step follows from $\tau_{\max} \leq \frac{T}{B}$. This finishes the proof.

We next prove the size of $\mH$ is small with high probability.

With probability at least $1 - 1/(nT)^{\omega(1)}$, $|\mH| \leq O(n\log^{10}(nT))$.

We first fix the loss sequence $\ell_1, \ldots, \ell_{T}$ as well as the set of sampled and active experts $Y_t$ of each epoch $t$.
We prove the size of pool $\mP$ at the end satisfies

\[
\Pr\left[|\mP|\geq \frac{|\mH|}{4n} \mid Y_1, \ldots,Y_{T/B}, \ell_1, \ldots, \ell_T \right] \geq \frac{1}{2},
\]

whenever $|\mH| \geq \Omega(n)$. Here the probability is taken over the randomness of the remaining  sampled and passive experts.

Let $W_t$ be the set of sampled and passive experts of epoch $t$. For any epoch $t \in \mH$, by the epoch assignment mechanism, the expert $i^{*} \notin Y_{t}$ (otherwise it is covered by itself at epoch $t$).
Condition on $\{Y_t\}_{t\in [T/B]}$, the probability that $i^{*} \in W_t$ obeys

\begin{align*}
\Pr[i^{*}\in W_t | Y_1, \ldots, Y_{T/B}, \ell_1, \ldots, \ell_T] = &~  \Pr[i^{*}\in Y_t | i^{*}\notin Y_{t}] \\
\geq &~ \Pr[i^{*}\in W_t] = \frac{1}{n} \cdot \left(1 - \frac{1}{\log^4 (n)}\right)^{2L \times 2K} \geq \frac{1}{2n}.
\end{align*}

The key observation is that once $i^{*} \in W_{t}$, i.e., $i^{*}$ is sampled while passive at epoch $t$, it would survive till the end. This is because the filter set $\mF$ and the estimate size $s$ are fully determined by the sampled and active experts $\{Y_t\}_{t\in [T/B]}$ and the loss sequence, which has already been fixed.
Therefore, if a passive expert $i^{*}$ enters at epoch $t$, it survives till the end.

The event of $i^{*}\in W_t$ are independent for $t \in \mH$ (condition on the loss sequence and $\{Y_t\}_{t\in [T/B]}$), hence, by Chernoff bound, the pool $\mP$ at the end of epoch $T/B$ satisfies

\begin{align}
\Pr\left[|\mP|\leq \frac{|\mH|}{4n} \mid Y_1, \ldots, Y_{T/B}, \ell_1, \ldots, \ell_T \right]
\leq &~ \Pr\left[\sum_{t\in \mH}\mathsf{1}\{i^{*}\in W_t\}\leq \frac{|\mH|}{4n} \mid Y_1, \ldots, Y_{T/B}, \ell_1, \ldots, \ell_T \right] \notag \\
\leq &~ \exp(-|\mH|/16n). \label{eq:bad-size-baseline}
\end{align}

Note we have already proved in Lemma <ref> that $|\mP| \geq  \Omega(\log^{10}(nT))$ happens with probability at most $1/(nT)^{\omega(1)}$, by Eq. (<ref>), this implies

\[
\Pr[|\mH|\geq \Omega(n\log^{10}(nT))] \leq 1/(nT)^{\omega(1)}.
\]

We conclude the proof here.

For any $\xi \in \Omega$ and $a \in \mH_{\xi}$, $f(\xi, a)$ equals $\xi$, except that $\xi_{a, i^{*}}$ is replaced by $(1, \vec{0})$. Intuitively,  it means $i^{*}$ is added to the pool at the beginning of epoch $h$ but never interferes with the rest of the pool going forward.
Formally, define a mapping $f: \Omega \times [T/B] \rightarrow \Omega \cup \{\nil\}$,

\[
f(\xi, a) =
\left\{
\begin{matrix}
\xi', \xi' = \xi \text{ except }\xi'_{a, i^{*}} = (1, \vec{0}) & a \in \mH_{\xi}\\
\nil & a \notin \mH_{\xi}.
\end{matrix}
\right.
\]

That is to say,

Let $\Omega' \subseteq \Omega$ be the image of $f$. The key observation is that for any realization $\xi' \in \Omega'$, expert $i^{*}$ must stay in the pool till the end.

Let $\xi' = f(\xi, a) \in \Omega'$ for some $\xi \in \Omega$ and $a \in [T/B]$, then the expert $i^{*}$ enters at epoch $a$ and it stays in $\mP$ till the end.

Let $\ALG$ and $\ALG'$ be two executions of Baseline, using random bits $\xi$ and $\xi'$ respectively.
We aim to prove the only difference over $\mP_t$ and $\mP_t'$ is that $\mP'_{t}$ contains $i^{*}$ with entering time $h$.

Before epoch $a$, the execution of $\ALG$ and $\ALG'$ are the same.
At the beginning of epoch $a$, $\mP_{a}'$ contains $i^{*}$ while $\mP_{a}$ not.
This is because with random bits $\xi$, $i^{*}$ must not be added at epoch $a$, otherwise the eviction time is $t(a) = a$ but not $+\infty$ since $i^{*}$ is marginally dominated by itself.

From then on, since we set $\xi'_{a,i} = (1, \vec{0})$, $i^{*}$ is never sampled during Merge (in particular, Line <ref> and Line <ref>). While for the Filter step,
(1) $i^{*} \notin \mF_{k}$, as the marginal dominance is defined with respect to $\mF_k$ and the target expert $i$ only, $i^{*}$ does not affect the outcome;
(2) $i^{*}$ is never removed, otherwise $\mP_t$ marginal dominates $i^{*}$ for some $t \leq T/B$.
Combining the above argument, we have proved adding $i^{*}$ would not affect the execution of Line <ref>-<ref> and $i^{*}$ would survive till the end.

With Lemma <ref> in hands, we know that for any $\xi' \in \Omega'$, expert $i^{*}$ must stay till the end.
Let $\mP_{\xi'}$ be the pool at the end; for any expert $i \in \mP_{\xi'}$ surviving till the end, recall $E_{i}$ is the entering time of $i$.  Now we have

\begin{align*}
\E_{\xi}[|\mH_{\xi}|]  = &~ \sum_{\xi \in \Omega}\mu(\xi) |\mH_{\xi}| = \sum_{\xi \in \Omega}\sum_{a \in [T/B]}\sum_{\xi'\in \Omega'}\mu(\xi) \mathsf{1}\{f(\xi, a) = \xi'\} \\
\leq &~\sum_{\xi \in \Omega}\sum_{a \in [T/B]} \sum_{\xi' \in \Omega'} \sum_{i^{*} \in \mP_{\xi'}} \mu(\xi)\mathsf{1}\{f(\xi, a) = \xi'\}\mathsf{1}\{E_{i^{*}} = a\}\\
= &~ \sum_{\xi \in \Omega } \sum_{\xi' \in \Omega'} \sum_{i^{*} \in \mP_{\xi'}} \mu(\xi)\mathsf{1}\{f(\xi, E_{i^{*}}) = \xi'\}\\
= &~ \sum_{\xi' \in \Omega'} \sum_{i^{*} \in \mP_{\xi'}} \sum_{\xi \in \Omega } \mu(\xi)\mathsf{1}\{f(\xi, E_{i^{*}}) = \xi'\}\\
\lesssim &~ \sum_{\xi' \in \Omega'} \sum_{i^{*} \in \mP_{\xi'}} n\mu(\xi')\\
\leq &~ \sum_{\xi' \in \Omega'} n\mu(\xi') |\mP_{\xi'}|\\
\leq &~ \sum_{\xi \in \Omega} n\mu(\xi) |\mP_{\xi}|= n \E_{\xi}|\mP_{\xi}|
\end{align*}

The first two steps follow from the definition.
The third step holds since for any $\xi, \xi', a$ such that $f(\xi, a) = \xi'$, by Lemma <ref> it must be the case that $i^{*}$ enters at epoch $a$ and resides till the end pool $\mP_{\xi'}$.
We exchange summation in the fifth step.
For the sixth step, fix $\xi'$ and $i^{*} \in \mP_{\xi'}$, for any $\xi \in \Omega$ satisfies $f(\xi, E_{i^{*}}) = \xi'$, $\xi'$ and $\xi$ differs only on $\xi_{E_{i^{*}}, i^{*}}$, $\xi'_{E_{i^{*}}, i^{*}}$, and note that $\xi'_{E_{i^{*}}, i^{*}}$ takes value $(1, \vec{0})$ and $\xi_{E_{i^{*}}, i^{*}}$ could take any value as long as $\xi_{E_{i^{*}}, i^{*}, 1} = 0$ (otherwise the eviction time is $E_{i^{*}}$ but not $+\infty$). That is to say

\begin{align*}
\frac{\sum_{\xi \in \Omega}\mathsf{1}\{f(\xi, E_{i^{*}}) = \xi'\}\mu(\xi)}{\mu(\xi')} \leq &~ (n-1) \cdot \left(1 - \frac{1}{\log^3 (nT)}\right)^{-L\cdot 4K}\\
=&~ (n-1) \cdot \left(1 - \frac{1}{\log^3 (nT)}\right)^{-O(\log^2 (nT))} = O(n).
\end{align*}

The eighth step follows from $\Omega'$ is a subset of $\Omega$.

At the same time, by Lemma <ref>, with probability at least $1-\frac{1}{\poly(nT)}$, the pool size $\mP_{\xi}$ is at most $O(\log^{7}(nT))$ and note the pool size can be at most $nT$ in the worst case. Hence, we have

\[
\E_{\xi}[|\mH_{\xi}|]  \leq O(n)\cdot \E_{\xi}|\mP_{\xi}| = O(n\log^{7}(nT)).
\]

We have completed the proof here.

Combining Lemma <ref> and Lemma <ref>, we obtain the regret bound of Proposition <ref>. The memory guarantee of Proposition <ref> has already been established in Lemma <ref>.

§.§ Boosting

We achieve the optimal regret guarantee of Theorem <ref> by maintaining multiple threads of Baseline and amortizing the regret carefully.
The new algorithmic ingredient includes
(1) leveraging the pool selection from a high frequency run of Baseline for a lower frequency run of Baseline; and (2) a low memory monocarpic expert algorithm with interval regret guarantees.

We first obtain the optimal rate when the space $S$ is small.

Let $n , T\geq 1$ be sufficiently large, there is an online learning algorithm that uses at most $\polylog(nT)$ space and achieves $\widetilde{O}\left(\sqrt{nT}\right)$ regret against an oblivious adversary.

Full algorithm
The full algorithm is presented as Algorithm <ref>. WLOG, we assume $T/n$ is a tower of $2$.
Let $R = \log_2(T/n) $ be the total number of threads.
Let $B_{r} = \frac{T}{n 2^{r-1}}$ ($r \in [R]$), $T_1 = T$ and $T_{r} = B_{r-1}$ for $r\in [2:R]$.
The full algorithm maintains $R$ different threads of the $\textsc{Baseline}_{+}$ algorithm, where the $r$-th thread ($r \in [R]$) $\textsc{Baseline}_{+}(r)$ restarts every $T_{r}$ days, with epoch size $B_{r}$.
The $\textsc{Baseline}_{+}$ differs slightly from $\textsc{Baseline}$ by (1) at the beginning of each epoch, in addition to sampling $O(1)$ experts, it also inherits experts from pools of higher threads; (2) it only maintains its pool (running Merge procedure) but does not run MWU over the epoch.
In other words, $\textsc{Baseline}_{+}(r)$ ($r\in [R]$) determines the “alive” experts, while the regret is controlled by a separate procedure MonocarpicExpert.
Instead of the epoch-wise regret guarantee, the MonocarpicExpert procedure guarantees an $\wt{O}(\sqrt{|\mI|})$ regret over any interval $\mI$ of the life time of an expert.

Full algorithm

[1]
Initialize $\textsc{Baseline}_{+}(r)$ ($\forall\, r\in [R]$) $\textsc{Baseline}_{+}(r)$ maintains the pool $\mP_{r,\cdot}$
$\mP \leftarrow \mP_{1,\cdot}\cup \cdots \cup \mP_{R,\cdot}$ $\mP$ aggregates pools from all threads
$t = 1,2, \ldots, T$
Run $\textsc{Baseline}_{+}(r)$ ($r\in [R]$)
Run MonocarpicExpert over $\mP$

$\textsc{Baseline}_{+}(r)$ $r \in [R]$

[1]
$s = 1,2,\ldots, T/T_{r}$ $s$-th restart
Initiate the pool $\mP_{r,\cdot} \leftarrow \emptyset$ and sub-pools $\mP_{r, \ell} \leftarrow \emptyset$ ($i \in [0:L]$)
$t = 1,2, \ldots, T_r/B_r$ Epoch $t$

$r$ is the lowest thread with a new epoch
$r' = R, \ldots, r+1$
$\mP_{r,0} \leftarrow \textsc{Merge}(\mP_{r, 0} \cup \mP_{r', \cdot}$) Inherit from higher thread pools

$\mP_{r,0} \leftarrow \mP_{r,0} \cup \textsc{Sample}(\N, 1/n)$ Sample new experts into pool

$\ell = 0,1, \ldots, \mathsf{pw}(t)$
$\mP_{r,\ell+1} \leftarrow \textsc{Merge}(\mP_{r,\ell+1}, \mP_{r,\ell})$
$\mP_{r,\ell} \leftarrow \emptyset$

§.§.§ MonocarpicExpert

An important component of our full algorithm is the  MonocarpicExpert procedure. In the problem of monocarpic experts, instead of having all experts presented at the beginning, an expert could enter and exit at any time (but each expert only ever wakes up once). The MonocarpicExpert procedure achieves low regret with respect to every interval during the live period of an expert, while its memory scales with the maximum number of alive experts.

Let $T \geq 1$. For any expert $i$ that is alive over interval $\mathcal{I} \subseteq [T]$, the MonocarpicExpert procedure (Algorithm <ref>) guarantees that with probability at least $1-1/(nT)^{\omega(1)}$,

\begin{align*}
\sum_{t \in \mathcal{I}'}\ell_t(i_t) - \sum_{t \in \mathcal{I}'}\ell_t(i) \leq O\left(\sqrt{|\mathcal{I'}|\log (nT)}\right)
\end{align*}

holds for every interval $\mI'\subseteq  \mI$, against an adaptive adversary.
Furthermore, suppose the maximum number of alive experts at most $M$, then the MonocarpicExpert procedure uses up to $O(M\log^2(nT))$ words of memory.

It is worthy noting that the memory/regret guarantee of MonocarpicExpert works even against an adaptive adversary.
The pseudocode of MonocarpicExpert is presented as Algorithm <ref>.
The set of experts is divided into $L$ subsets $\mU_{1} \cup \cdots \cup \mU_{L}$ ($L = \log_2 (T)$), and $\mU_{\ell}$ contains experts that live for at most $2^{\ell}$ days.
The subset $\mU_{\ell}$ is updated every $2^{\ell-1}$ days (either receives experts from $\mU_{\ell-1}$ or gives away experts to $\mU_{\ell+1}$) and removes inactive expert. The membership of $\mU_{\ell}$ is fixed between two updates.
MonocarpicExpert relies heavily on the IntervalRegret subroutine. It runs IntervalRegret over $L$ experts $\textsc{Exp}_{\ell}$ ($\ell \in [L]$), where $\textsc{Exp}_{\ell}$ itself runs $\textsc{IntervalRegret}$ on $\mU_{\ell}$ every $2^{\ell-1}$ days (between two updates, where membership of $\mU_{\ell}$ is fixed).
If an expert in $\mU_{\ell}$ becomes inactive between two updates (i.e., it is alive at the beginning but exits in the middle), then we assign unit loss to it till the next update.

[1]
Initialize $\mU_\ell \leftarrow \emptyset$, $\textsc{Exp}_{\ell}$ ($\ell \in [L]$) $L = \log_2(T) $
$\textsc{Exp}\leftarrow \textsc{IntervalRegret}(\textsc{Exp}_1, \ldots, \textsc{Exp}_{L}, T)$
$t=1,2, \ldots, T$
Add newly activated experts to $\mU_1$
Follow the decision of $\textsc{Exp}$
$\ell = 1,2, \ldots, \mathsf{pw}(t)$ Update membership
$\mU_{\ell+1} \leftarrow \mU_{\ell+1} \cup \mU_{\ell}, \mU_{\ell} \leftarrow \emptyset$
Remove inactive experts in $\mU_{\ell+1}$

$\textsc{Exp}_{\ell}$ $\ell \in [L]$
$s=1,2,\ldots, T/2^{\ell-1}$$s$-th restart
$\textsc{IntervalRegret}(\mU_{\ell}, 2^{\ell-1})$
Add newly activated expert to $\mU_1$
$\ell = 1,2, \ldots, \mathsf{pw}(t)$
$\mU_{\ell+1} \leftarrow \mU_{\ell+1} \cup \mU_{\ell}, \mU_{\ell} \leftarrow \emptyset$
Remove inactive experts in $\mU_{\ell+1}$

The regret and memory guarantee largely follows from the IntervalRegret subroutine.

Let $T \geq 1$. For any expert $i \in \mU$ and time interval $\mI \subseteq [T]$, Algorithm IntervalRegret guarantees that with probability at least $1 - 1/(nT)^{\omega(1)}$,

\begin{align*}
\sum_{t \in \mathcal{I}}\ell_t(i_t) - \sum_{t \in \mathcal{I}}\ell_t(i) \leq O\left(\sqrt{|\mathcal{I}|\log (nT)}\right)
\end{align*}

holds against an adaptive adversary.
Moreover, IntervalRegret uses up to $O(|\mU|\log(nT))$ words of memory.

The IntervalRegret maintains a set of meta experts $\textsc{SingleInterval}_{a, b}$ ($a \in [L], b \in [T/2^a]$).
The $\textsc{SingleInterval}_{a, b}$ is effective over the time interval $[2^a(b-1)+1: 2^a b]$.
It runs MWU over $\mU$ in $[2^a(b-1)+1: 2^a b]$ (initiates with uniform weight) and does nothing outside of the interval.
Let $h(t, a, b)$ denote the effectiveness of $\textsc{SingleInterval}_{a, b}$, that is, it $h(t, a, b) = 1$ when $t\in [2^a(b-1)+1: 2^a b]$ and $h(t, a,b) = 0$ otherwise.

We use $i_{t, a, b}$ to denote the action of $\textsc{SingleInterval}_{a, b}$ at day $t$.

IntervalRegret maintains a set of weights $\{w_{a, b}\}_{a \in [L], b \in [T/2^a]}$ over $\textsc{SingleInterval}_{a, b}$.
At day $t$, there are $L$ effective meta experts and the algorithm follows the advice from one of them, by sampling proportional to $\{w_{a, b}\}_{h(t, a, b) =1}$.
The loss vector is constructed as follow: For an effective meta expert $\textsc{SingleInterval}_{a, b}$ (i.e., $h(t, a, b) = 1$), it simply equals $\ell_{t}(i_{t, a, b})$, while for non-effective expert (i.e., $h(t, a, b)=0$), it is set to $\bar{\ell}_t$, where $\bar{\ell}_t$ is the “expected” loss computed by Eq. (<ref>). It equals the expected loss received by IntervalRegret at day $t$.
The weight $w_{a, b}$ is updated by the Squint algorithm [47].

IntervalRegret($\mU, T$)

[1]
Initialize $w_{a, b} \leftarrow 1$ over $\textsc{SingleInterval}_{a,b}$ ($a \in [L], b \in [T/2^a]$)
$t=1,2, \ldots, T$
Sample action $i_{t, a,b}$ from $\{w_{a, b}\}_{h(t, a, b) =1}$  $h(t, a, b) = 1$ if $t \in [2^a(b-1)+1: 2^a b]$
Compute the expected loss

\begin{align}
%\sum_{a, b: h(t, a, b) = 1}w_{a, b}\ell_{t}(i_{t, a, b}) + \sum_{a, b: h(t, a, b) = 0}w_{a, b}\bar{\ell}_{t} = \sum_{a, b}w_{a, b}\bar{\ell}_t
\bar{\ell}_t \leftarrow \sum_{a, b: h(t, a, b) = 1}\frac{w_{a, b}}{\sum_{a, b: h(t, a, b) = 1} w_{a, b} } \cdot \ell_{t}(i_{t, a, b})
\label{eq:loss-construct}
\end{align}

Assign loss

\[
\hat{\ell}_{t}( a, b ) = \left\{
\begin{matrix}
\ell_{t}(i_{t, a, b}) &  h(t, a, b) =1\\
\bar{\ell}_t & h(t, a, b) =0
\end{matrix}
\right.
\]

Update the weight distribution using Squint

\begin{align}
w_{a, b}  \leftarrow \E_{\eta}\left[\eta \cdot \exp\left(\eta \sum_{\tau=1}^{t-1}v_{\tau}(a, b) - \eta^2 \sum_{\tau=1}^{t-1}v_{\tau}^2(a, b)\right)\right] \label{eq:squint}
\end{align}

where $v_{\tau}(a, b) = \bar{\ell}_{\tau} - \hat{\ell}_{\tau}(a, b)$

$\textsc{SingleInterval}_{a, b}$
$t = 2^{a}(b-1) +1, \ldots, 2^{a}b$
Run MWU over $\mU$.

For any $a \in [L], b \in [T/2^{a}]$ and expert $i \in \mU$, due to the regret guarantee of MWU, one has, with probability at least $1- 1/(nT)^{\omega(1)}$,

\begin{align}
\sum_{t=2^a(b-1)+1}^{2^a b}\ell_{t}(i_{t, a, b}) -\sum_{t=2^a(b-1)+1}^{2^a b}\ell_{t}(i) \leq O\left(\sqrt{2^a \log (nT)}\right) \label{eq:interval1}.
\end{align}

Recall $\bar{\ell}_t$ is the solution of Eq. (<ref>) at day $t$, it equals the expected loss received by IntervalRegret, since

\begin{align*}
\bar{\ell}_t  = \sum_{a,b: h(t,a, b) = 1}\frac{w_{t, a, b}}{\sum_{a, b: h(t, a, b) = 1}w_{t, a, b}}\ell(i_{t, a, b}) = \sum_{a,b: h(t,a, b) = 1}p_{t,a, b}\ell(i_{t, a, b})
\end{align*}

where $p_{t,a, b} = \frac{w_{t, a, b}}{\sum_{a, b: h(t, a, b) = 1}w_{t, a, b}}$ is the probability of following $i_{t, a, b}$.

By the regret guarantee of Squint (see Lemma <ref>), one has

\begin{align}
&~\E\left[\sum_{t\in [2^a (b-1) + 1: 2^a b]}\ell_t(i_t) -  \sum_{t\in [2^a (b-1) + 1: 2^a b]}\ell_t(i_{t,a, b})\right]\notag \\
= &~ \E\left[\sum_{t=1}^{T}\ell_t(i_t) - \sum_{t=1}^{T}\hat{\ell}_t(a, b)\right]\notag \\
\leq &~  O\left(\sqrt{\left(\sum_{t\in [T]}(\E[\ell_t(i_t)] - \hat{\ell}_t(a, b))^2\right)\cdot \log (nT)}\right) =  O\left(\sqrt{2^a\log (nT)}\right) \label{eq:interval2}.
\end{align}

The first and third steps hold since $\hat{\ell}_t(a, b) = \ell_t(i_{t, a, b})$ for $t \in [2^a (b-1) + 1: 2^a b]$ and loss $\hat{\ell}_t(a, b) = \bar{\ell}_t = \E[\ell_t(i_t)]$ for any $t \notin [2^a (b-1) + 1: 2^a b]$, the second step follows from the regret guarantee of Squint.

Applying the Azuma-Hoeffding inequality to Eq. (<ref>) and note $|\E[\ell_t(i_t)] - \ell_t(i_t)| \leq 2$, one obtains

\begin{align}
\sum_{t\in [2^a (b-1) + 1: 2^a b]}\ell_t(i_t) -  \sum_{t\in [2^a (b-1) + 1: 2^a b]}\ell_t(i_{t,a, b}) \leq O\left(\sqrt{2^a \log (nT)}\right) \label{eq:interval3}
\end{align}

holds with probability at least $1-1/(nT)^{\omega(1)}$.

Combining Eq. (<ref>) and Eq. (<ref>), we have that with probability at least $1-1/(nT)^{\omega(1)}$,

\begin{align*}
\sum_{t\in [2^a (b-1) + 1: 2^a b]}\ell_t(i_t) - \sum_{t\in [2^a (b-1) + 1: 2^a b]}\ell_{t}(i)\leq O\left(\sqrt{2^a \log (nT)}\right).
\end{align*}

To conclude the regret analysis, we note for any interval $\mI = [t_1: t_2]\subseteq T$, one can split $\mI$ into $X \leq 2\log_2(|\mI|)$ disjoint intervals $\mI = \mI_1 \cup \mI_{2}\cup \cdots \cup \mI_X$, such that  (1) $\mI_{x}$ ($x \in [X]$) exactly spans the lifetime of some meta expert $\textsc{SingleInterval}_{a_x, b_x}$ and (2) there are at most two length-$2^{x}$ intervals. Then we conclude

\begin{align*}
\sum_{t\in \mI}\ell_t(i_t) - \sum_{t\in \mI}\ell_{t}(i) = &~ \sum_{x=1}^{X}\sum_{t\in \mI_x}(\ell_t(i_t) - \ell_{t}(i)) \leq  \sum_{x=1}^{X} O\left(\sqrt{|\mI_x|\log(nT)}\right)\\
\leq &~ \sum_{x=1}^{\log (|\mI|)}O\left(\sqrt{2^{x}\log (nT)}\right) = O\left(\sqrt{|\mI|\log(nT)}\right).
\end{align*}

Memory usage of IntervalRegret
A naive implementation takes $O(T|\mU|\log(nT))$ as one needs to maintain $O(T\log T)$ $\textsc{SingleInterval}_{a, b}$ procedures.
However, note that at day $t$, the algorithm only needs to know the weights $\{w_{a, b}\}_{h(t, a, b)=1}$ to determine its action and compute the average loss $\bar{\ell}_t$.
That is, it suffices to know the weight $w_{a, b}$ of effective experts.
There are $L = \log_2 (T)$ effective meta experts at any time, and $\textsc{SingleInterval}_{a, b}$ is effective for a consecutive period with weight $w_{a, b}$ starting from $\E_{\eta}[\eta]$.
Hence IntervalRegret requires $O(|\mU|\log (nT))$ words of memory in total. We conclude the proof here.

We can now conclude the analysis of MonocarpicExpert.

We first provide the regret analysis.
For any expert $i$ that is alive over interval $\mI$. Let $\mI' = [t_1: t_2] \subseteq \mI$ be any sub-interval. One can split the interval $\mI'$ into $X \leq \log(|\mI'|)$ consecutive intervals $\mI' = \mI'_1 \cup \mI'_2 \cup \ldots \cup \mI'_X$, such that expert $i$ resides in $\mU_{\ell_x}$ during the interval of $\mI'_x$ ($\ell_1 < \ell_2 < \cdots < \ell_{X}$).
Moreover, the size of $\mI'_x$ is exponentially increasing, except for $\mI'_1$ and $\mI'_X$
($i$ may not stay for an entire update at $\mU_{\ell_1}$ and $\mU_{\ell_X}$).
Let $i_{t,\ell}$ be the action of $\textsc{Exp}_{\ell}$ at day $t$, Then due to the IntervalRegret guarantee, with probability at least $1-1/(nT)^{\omega(1)}$, one has

\begin{align*}
\sum_{t \in \mI'}\ell_{t}(i_t) - \sum_{t \in \mI'}\ell_t(i) =  &~ \sum_{x=1}^{X}\sum_{t \in \mI'_{x}}\ell_{t}(i_t) - \ell_t(i) \\
= &~ \sum_{x=1}^{X}\sum_{t \in \mI'_{x}}\ell_{t}(i_{t}) - \ell_t(i_{t, \ell_x}) +  \sum_{x=1}^{X}\sum_{t \in \mI'_{x}}\ell_{t}(i_{t, \ell_x}) - \ell_t(i)\\
\leq &~ \sum_{x=1}^{X} O(\sqrt{|\mI_{x}'|\log (nT)}) \leq O(\sqrt{|\mI'|\log (nT)}).
\end{align*}

Here the third step follows from the interval guarantee (see Lemma <ref>) of $\textsc{Exp}_{\ell_x}$, the interval regret guarantee of $\textsc{Exp}_{\ell_x}$ on $\mU_{\ell_{x}}$,  and the fact that $\textsc{Exp}_{\ell_x}$ restarts at most twice when $i$ resides in $\mU_{\ell_x}$.
The last step follows from the increasing size of $\mI_{x}'$.

Finally, for the memory usage, there are $L = \log_2(T)$ procedures $\textsc{Exp}_{\ell}$ ($\ell \in [L]$), and $\textsc{Exp}_{\ell}$ runs on $\mU_{\ell}$.
It suffices to bound the size of $\mU_{\ell}$.
Note that $\mU_{\ell}$ is updated every $2^{\ell-1}$ days, and at the time of update, all experts in $\mU_{\ell}$ are alive and the set remains the same during the next $2^{\ell-1}$ days. Hence $|\mU_{\ell}| \leq M$ and the memory usage of $\textsc{Exp}_{\ell}$ is at most $O(M\log (nT))$.
The total memory is at most $O(M\log^2(nT))$.

§.§.§ Analysis of full algorithm

We next analyse the memory and regret guarantee of the full algorithm.

§.§.§ Memory bound

The memory bound is largely inherited from Baseline.

With probability at least $1 - 1/(nT)^{\omega(1)}$, for any $r \in [R]$, the pool $\mP_{r, \cdot}$ never exceeds $O(\log^{10}(nT))$.

We prove with probability at least $1- 1/(nT)^{\omega(1)}$, at any time, the size of $\mP_{r, \ell}$ is at most $2\log^9 (nT)$ ($r \in [R]$, $\ell \in [L]$) and $\mP_{r, 0}$ is at most $3\log^9 (nT)$.
The case of $r = R$ holds trivially and suppose the induction holds for thread $r+1$.

For the $r$-th thread, $\mP_{r, 0}$ is initiated as $\textsc{Sample}(\mN, 1/n)$, or the union of $\textsc{Sample}(\mN, 1/n)$ and the result of merging $\mP_{r+1, \cdot}, \ldots, \mP_{R, \cdot}$ (Line <ref> – <ref> of Algorithm <ref>).
We have by induction $|\mP_{r', \cdot}| = |\mP_{r', 2}| \leq 2\log^9 (nT)$ for any $r' > r$ (there are only two epochs of  $\textsc{Baseline}_{+}(r')$ per restart). Hence by Lemma <ref>, the pool obtained from merging  $\mP_{r+1, \cdot}, \ldots, \mP_{R, \cdot}$ has size at most $2\log^9(nT)$, and by Chernoff bound, the sample set $\textsc{Sample}(\mN, 1/n)$ is at most $\log^9(nT)$ with high probability.

While for $\ell \geq 1$, by Lemma <ref>, the Merge procedure guarantees that the sub-pool $\mP_{r, \ell}$ satisfies

\begin{align*}
|\mP_{r, \ell}| \leq &~ \max\left\{2\log^9(nT), \frac{1}{4}(|\mP_{r, \ell}| + |\mP_{r, \ell-1}|)\right\}\\
\leq &~ \max\left\{2\log^9(nT), \frac{1}{4}(2\log^9(nT) + 3\log^9(nT))\right\} = 2\log^9(nT).
\end{align*}

Consequently, the memory usage of the full algorithm is not large.

With probability at least $1 - 1/(nT)^{\omega(1)}$, the pool size of $\mP$ never exceeds $O(\log^{11}(nT))$.
Furthermore, the memory usage of Algorithm <ref> is bounded by $O(\log^{22}(nT))$ words.

By Lemma <ref>, we know that the size of pool $\mP$ satisfies $|\mP| = |\mP_{1, \cdot} \cup \cdots \cup \mP_{R, \cdot}| \leq O(\log^{11}(nT))$.
The Merge procedure needs to know the loss on each interval $\Gamma_{i, j}$ of $i, j\in \mP$, this takes $O(\log^{22}(nT))$ words of memory.
By Theorem <ref>, the MonocarpicExpert requires memory $O(|\mP|\log^2(nT)) = O(\log^{13}(nT))$ . In summary, the total memory is bounded by $O(\log^{22}(nT))$.

We conclude the proof here.

§.§.§ Regret analysis

The main departure (and complication) comes from the regret analysis.

Let $i^{*} \in [n]$ be the best expert and let

\[
K_1 = [0:n-1], \quad K_2 = [0:n-1]\times \{0,1\}  \quad \ldots  \quad K_R=  [0:n-1] \times \underbrace{\{0,1\}\times \cdots \times \{0,1\}}_{R-1}
\]

and $K$ be the union of $K_1, \ldots, K_R$, i.e.,

\[
K = K_1 \cup \cdots \cup K_{R}.
\]

Given any timestep $a = (a_{1}, \ldots, a_{r(a)}) \in K$ (where $r(a)$ is defined such that $a \in K_{r(a)}$), the timestep $a$ uniquely identifies an epoch of $\textsc{Baseline}_{+}(r(a))$, i.e., it refers to the $a_{r(a)}$-th epoch of the $(\sum_{r =1}^{r(a)-1}a_r 2^{r(a)-r-1})$-th restart.

For any timestep $a\in K$, we write

\[
a'  = (a_1', a_2', \ldots a_{r(a')}') = a\oplus 1 \in K
\]

as the unique timestep that satisfies

\[
\sum_{i=1}^{r(a')} a_i'B_i = \sum_{i=1}^{r(a)} a_i B_i + B_{r(a)} \quad \text{and} \quad a'_{r(a')} \neq 0.
\]

That is to say, $a' = a \oplus 1$ is the next number under $2$-base with $0$ truncated at the end  (except the first coordinate, which belongs to $[0:n-1]$).

Intuitively, $a\oplus 1$ is the next complete epoch after epoch $a$, if there are multiple epochs of different threads, it refers to the one at the lowest thread.

Let $K(a)$ contain all timesteps that succeed $a$ under the $\oplus$ operation, i.e.,

\[
K(a) := \{a\} \cup \{a \oplus 1\} \cup \{(a \oplus 1) \oplus 1\} \cup \cdots  \subseteq K
\]

Roughly speaking, $K(a)$ includes all timesteps/epochs that an expert enters at $a$ would reside.

Random bits
Again, it is useful to understand the random bits used for pool selection before defining an active/passive expert.
For any timestep $a \in K$, let the random bits $\xi_{a} = (\xi_{a, 1}, \ldots, \xi_{a, n})$, where $\xi_{a, i} = (\xi_{a,i, 1}, \xi_{a, i,2})$ is used for expert $i$ ($i \in [n]$).
The first coordinate $\xi_{a, i, 1} \in \{0, 1\}$ is a Bernoulli variable with mean $1/n$. It is used for sampling new expert into the pool at the beginning of epoch $a$ (i.e. Line <ref> of Algorithm <ref>).
The second part of random bits $\xi_{a, i, 2} \in \{0, 1\}^{R \times 2L \times 2K}$ are used for estimating size and filtering in the Merge procedure of each sub-pool, they are of mean $\frac{1}{\log^4 (nT)}$.

Recall the concept of passive/active expert.

At any timestep $a \in K$, an expert $i\in [n]$ is said to be passive, if $\xi_{a, i, 2} = \vec{0}$. It is said to be an active expert otherwise.

Epoch Assignment  Our accounting argument will split the entire sequence of epochs into a  collection of disjoint subsequences, and assign each subsequence to a different set of experts in the pool.

Fix the loss sequence $\ell_1, \ldots, \ell_{T}$ and the set of sampled and active experts $Y_a \subseteq [n]$ for each timestep $a \in K$.

Our key observation is

Suppose the loss sequence $\{\ell_t\}_{t\in [T]}$ and the set of sampled and active experts $\{Y_a\}_{a \in K}$ are fixed, then at any time during the execution of Algorithm <ref>, the estimate size $s$, the filter set $\mF$ and the set of alive active experts are also fixed, regardless of the set of sampled and passive experts.

For any timestep $a \in K$, consider the expert $i^{*}$ with entering time $a$, the eviction time $t(a) \in K(a)\cup \{+\infty\}$ is defined as the first timestep of $K(a)$, such that $i^{*}$ is covered by the set of alive active experts at the end of $t(a)$.
If $i^{*}$ would not be covered, then set $t(a) = +\infty$.

Epoch assignment (Note: only used in analysis)

[1]
Initialize $\mH_{r} \leftarrow \emptyset$ ($r\in [R]$), $\tau \leftarrow 1$, $a_{1} \leftarrow 0$
$\cup_{\tau'\leq \tau}\mI_{\tau'}  \neq [T]$
$t(a_{\tau}) = +\infty$$i^{*}$ survives till the end
$\mH_{r(a_{\tau})} \leftarrow \mH_{r(a_{\tau})} \cup a_{\tau}$ $a_\tau$ is a bad epoch at thread $r(a_\tau)$
$r(a_{\tau}) = R$ Stop at the top thread
$\mI_{\tau} \leftarrow a_\tau$, $a_{\tau + 1} \leftarrow a_{\tau} \oplus 1$, $\tau \leftarrow \tau + 1$,
$a_{\tau} \leftarrow (a_{\tau}, 0)$ Move to next thread
$a_{\tau + 1} \leftarrow t(a_{\tau}) \oplus 1$, $I_{\tau} \leftarrow [a_{\tau}: t(a_{\tau})]$, $\tau \leftarrow \tau + 1$

The key ingredient in our analysis is the epoch assignment mechanism, whose pseudocode is presented as Algorithm <ref> (note again that this algorithm is only for analysis). Algorithm <ref> splits the entire sequence and determines the bad epochs $\mH_{r}$ of each thread $r$ ($r\in [R]$) through a bottom-up walk.
It starts from the bottom thread $r=1$.
At each step $\tau$, if the expert $i^{*}$ could survive till the end with entering time $a_{\tau}$, then it is a bad epoch at thread $r(a_{\tau})$ and the algorithm augments the collection of bad epochs $\mH_{r(a_{\tau})}$ of thread $r(a_{\tau})$ (Line <ref>).
Instead of moving to the next epoch of the same thread, Algorithm <ref> walks to the next thread, unless it is already at the top thread $R$.
If the expert $i^{*}$ would be covered until timestep $t(a_{\tau}) \in K(a)$,
then Algorithm <ref> sets the $\tau$-th interval as $\mI_{\tau} = [a_{\tau}:t(a_{\tau})]$ and moves to the next epoch $a_{\tau+1} = t(a_{\tau})\oplus 1$.
Here $a_{\tau}$ and $t(a_{\tau})$ do not need to be at the same thread, and we write $\mI_{\tau} = [a_{\tau}:t(a_{\tau})]$ to denote the time interval between the beginning of $a_\tau$ and the end of $t(a_{\tau})$.
See Figure <ref> for an illustration.

Let $\tau_{\max}$ be the total number of intervals in the partition generated by Algorithm <ref>.
We first make a few simple observations about the intervals $\{\mI_{\tau}\}_{\tau \in [\tau_{\max}]}$.

We have

* The intervals $\{\mI_{\tau}\}_{\tau \in [\tau_{\max}]}$ are disjoint and $\bigcup_{\tau \in [\tau_{\max}]}\mI_{\tau} = [T]$.

* Let $L_1 = \{\mI_{\tau}\}_{\tau \in [\tau_{\max}] }$ and let $L_{r}:= \{\mI_{\tau}:  |\mI_{\tau}| < B_{r-1}\}$ ($r \in [2:R]$) contain intervals of length less than $B_{r-1}$, then

\begin{align*}
\sum_{\mI\in L_{r}} |\mI| \leq |\mH_{r-1}| \cdot B_{r-1}.
\end{align*}

The first claim follows directly from the assignment process and we focus on the second claim.
For any thread $r \in [2:R]$ and any interval $\mI_{\tau}\in L_{r}$, we prove $\mI_{\tau}$ is contained in a bad epoch of thread $r-1$.

Recall $\mI_{\tau}$ starts from the beginning of epoch $a_\tau$ and terminates at the end of epoch $t(a_{\tau})$ ($a_{\tau}, t(a_{\tau})$ are not necessarily at the same thread).
We first observe $t(a_\tau)$ is of thread at least $r$, otherwise $\mI$ spans at least an epoch of thread $r-1$.
Suppose the timestep $t(a_\tau)$ is contained in epoch $a'$ of thread $r-1$ (i.e., $r(a') = r-1$), it suffices to prove (1) $\mI$ starts within $a'$ and (2) $a'$ is a bad epoch of thread $r-1$ (i.e., $a' \in \mH_{r-1}$).

The first claim follows from the epoch assignment procedure.
For the second claim, suppose $a'$ is not a bad epoch of thread $r-1$, then let $a_1'$ be the closest thread $r-1$ bad epoch before $a'$ and $a_2'$ be the closest thread $(r-1)$ bad epoch after $a'$. The “walk”  defined by Algorithm <ref> would not go above thread $r-1$ between $a_1'$ and $a_2'$, which contradicts our assumption of $\mI\in L_{r}$.
We conclude the proof here.

We next prove the size of bad epochs $\mH_{r}$ is at most $O(n\log^{11} (nT))$ with high probability.

With probability at least $1 - 1/(nT)^{\omega(1)}$, $|\mH_r| \leq O(n\log^{11}(nT))$ holds for any $r\in [R]$.

Recall we first fixed the loss sequence $\ell_1, \ldots, \ell_{T}$ as well as the set of sampled and active experts $\{Y_a\}_{a\in K}$.
For any $r\in [R]$, we prove the size of pool $\mP$ at the end satisfies

\[
\Pr\left[|\mP|\geq \frac{|\mH_r|}{4n} \mid \{Y_a\}_{a\in K}, \{\ell_t\}_{t\in[T]} \right] \geq \frac{1}{2},
\]

whenever $|\mH_r| \geq \Omega(n)$. Here the probability is taken over the randomness of the remaining  sampled and passive experts.

The proof is similar to Lemma <ref>.
Let $W_a$ be the set of sampled and passive experts of timestep $a$. For any timestep $a \in \mH_r$, by our assignment mechanism (Algorithm <ref>), the expert $i^{*} \notin Y_{a}$ (otherwise $i^{*}$ is covered by itself.)
The probability that $i^{*} \in W_a$ obeys

\begin{align*}
\Pr\left[i^{*}\in W_a | \{Y_a\}_{a\in K}, \{\ell_t\}_{t\in[T]} \right] = &~  \Pr[i^{*}\in W_a | i^{*}\notin Y_{a}] \\
\geq &~ \Pr[i^{*}\in W_a] = \frac{1}{n} \cdot \left(1 - \frac{1}{\log^4 (n)}\right)^{R\times 2L \times 2K} \geq \frac{1}{2n}.
\end{align*}

The key observation is that once $i^{*} \in W_{a}$, i.e., $i^{*}$ is sampled while passive at timestep $t$, it would survive till the end. This is because the filter set $\mF$, the estimate size $s$ and the set of alive active experts are all fully determined by the sampled and active experts $\{Y_a\}_{a\in K}$ and the loss sequence $\{\ell_t\}_{t\in [T]}$, which has already been fixed when defining the eviction time $t(a)$.
Therefore, if a passive expert $i^{*}$ enters at timestep $a$, it survives till the end.

The event of $i^{*}\in W_a$ are independent for $a \in \mH_r$ (condition on the loss sequence and $\{Y_a\}_{a\in [K]}$), hence, by Chernoff bound, one has

\begin{align*}
\Pr\left[|\mP|\leq \frac{|\mH_r|}{4n} \mid \{Y_a\}_{a\in K}, \{\ell_t\}_{t\in[T]}\right] \leq &~ \Pr\left[\sum_{a\in \mH_r}\mathsf{1}\{i^{*}\in W_{a}\} \leq \frac{|\mH_r|}{4n} \mid \{Y_a\}_{a\in K}, \{\ell_t\}_{t\in[T]}\right]\\
\leq &~ \exp(-|\mH_r|/16n).
\end{align*}

Note we have already proved in Lemma <ref> that $|\mP| \geq  \Omega(\log^{11}(nT))$ happens with probability at most $1/(nT)^{\omega(1)}$, this implies

\[
\Pr[|\mH_r|\geq \Omega(n\log^{11}(nT))] \leq 1/(nT)^{\omega(1)}.
\]

We conclude the proof here.

Now we apply the regret guarantee of MonocarpicExpert and prove that Algorithm <ref> achieves low regret over each interval $\mI_{\tau}$.

With probability at least $1-1/(nT)^{\omega(1)}$, for any $\tau \in [\tau_{\max}]$ and $a_{\tau} \notin \mH_{R}$,

\begin{align*}
\sum_{t \in \mI_{\tau}}\ell_{t}(i_t) - \sum_{t \in \mI_{\tau}}\ell_{t}(i^{*}) \leq O\left(\sqrt{|\mI_{\tau}|} \cdot \log^6(nT)\right).
\end{align*}

We condition on the event of Lemma <ref>.
Given any interval $I_{\tau}$ starting with $a_\tau$, ending with $t(a_{\tau})$ and $a_{\tau} \notin \mH_{R}$, the expert $i^{*}$ with entering time $a_\tau$ is covered by $\mP$ the end of $t(a_{\tau})$. Let $i_1^{*}, \ldots, i_{s}^{*}$ be the set of experts that cover $i^{*}$.
By Definition <ref>, we can partition the interval $\mI_{\tau} = \mI_{\tau, 1} \cup \cdots \cup \mI_{\tau, s}$ and obtain

\begin{align}
\label{eq:mg1}
\sum_{t \in \mI_{\tau}}\ell_{t}(i^{*}) \geq \sum_{j=1}^{s}\sum_{t\in \mI_{\tau, j}}\ell_t(i_{j}^{*}) - 1
\end{align}

By the regret guarantee of MonocarpicExpert, with probability at least $1 - 1/(nT)^{\omega(1)}$, one has

\begin{align}
\sum_{t \in \mI_{\tau}}\ell_{t}(i_t) - \sum_{t \in \mI_{\tau}}\ell_{t}(i^{*}) = &~ \sum_{t \in \mI_{\tau}} \ell_{t}(i_t) - \sum_{j=1}^{s}\sum_{t\in \mI_{\tau, j}}\ell_t(i_{j}^{*}) +  \sum_{j=1}^{s}\sum_{t\in \mI_{\tau, j}}\ell_t(i_{j}^{*}) - \sum_{t \in \mI_{\tau}}\ell_{t}(i^{*})\notag\\
\leq &~ \sum_{j=1}^{s}O\left(\sqrt{|\mI_{\tau, j}|\log(nT)}\right) + \sum_{j=1}^{s}\sum_{t\in \mI_{\tau, j}}\ell_t(i_{j}^{*})  - \sum_{t \in \mI_{\tau}}\ell_{t}(i^{*}) \notag  \\
\leq &~ \sum_{j=1}^{s}O\left(\sqrt{|\mI_{\tau, j}|\log(nT)}\right) + 1\notag \\
\leq &~ \sqrt{|\mI_{\tau}|} \cdot \log^{6}(nT).\notag%\label{eq:mg2}
\end{align}

The second step follows from Theorem <ref>, the third step follows from Eq. (<ref>) and the last step follows from $s \leq \log^{11}(nT)$ (Lemma <ref>), $\mI_{\tau} = \mI_{\tau, 1} \cup \cdots \cup \mI_{\tau, s}$ and Cauchy-Schwarz. We conclude the proof here.

Now we can bound the regret of full algorithm.

With probability at least $1- 1/(nT)^{\omega(1)}$, one has

\[
\sum_{t \in [T]}\ell_{t}(i_t) - \sum_{t \in [T]}\ell_{t}(i^{*}) \leq \wt{O}\left(\sqrt{nT}\right).
\]

In the proof, we first fix the loss sequence $\{\ell_t\}_{t\in [T]}$ and the set of sampled and active experts $\{Y_a\}_{a\in K}$.
Now we can use the epoch assignment mechanism (Algorithm <ref>) and split the entire sequence $[T]$ into a collection of intervals $\{I_{\tau}\}_{\tau \in [\tau_{\max}]}$.

We first categorize the intervals based on their length. With probability at least $1-1/(nT)^{\omega(1)}$, we have

\begin{align}
\sum_{t \in [T]}\ell_{t}(i_t) -\sum_{t \in [T]}\ell_{t}(i^{*}) = &~ \sum_{r=1}^{R-1}\sum_{\mI \in L_{r}\setminus L_{r+1}}\sum_{t\in \mI}(\ell_{t}(i_t) -  \ell_{t}(i^{*})) + \sum_{\mI \in L_R}\sum_{t\in \mI}(\ell_{t}(i_t) -  \ell_{t}(i^{*}))\notag \\
\leq &~ \sum_{r=1}^{R-1}\sum_{\mI \in L_{r}\setminus L_{r+1}}\sum_{t\in \mI}(\ell_{t}(i_t) -  \ell_{t}(i^{*})) + O(|\mH_{R-1}|)\notag \\
\leq &~ \sum_{r=1}^{R-1}\sum_{\mI \in L_{r}\setminus L_{r+1}}O\left(\sqrt{|\mI|}\log^6 (nT)\right) + O(|\mH_{R-1}|).\label{eq:regret-last1}
\end{align}

The first step holds from $[T] = \cup_{\mI\in L_1} \mI$, the second step uses the naive bound of

\[
\sum_{\mI \in L_R}\sum_{t\in \mI}(\ell_{t}(i_t) -  \ell_{t}(i^{*})) \leq \sum_{\mI\in L_{R}}|\mI| \leq |\mH_{R-1}|\cdot B_{R-1} = O(|\mH_{R-1}|),
\]

and the last step follows from the interval regret bound of Lemma <ref>.

We bound the regret of each group separately.

Note for any $r\in [R-1]$, one has

\begin{align}
\sum_{\mI \in L_{r}\setminus L_{r+1}}\sqrt{|\mI|} \leq &~ \sqrt{| L_{r}\setminus L_{r+1}| \cdot \sum_{\mI \in L_{r} \backslash L_{r+1}}|\mI|}\notag \\
\leq &~ |\mH_{r-1}| B_{r-1} \cdot  \sqrt{\frac{1}{B_{r}}} \notag \\
\leq &~ \left\{
\begin{matrix}
|\mH_{r-1}| \cdot \sqrt{2T/n}  & r\geq 2\\
\sqrt{nT}& r = 1
\end{matrix}
\right..\label{eq:regret-last2}
\end{align}

The first step follows from Cauchy-Schwarz, the second step follows from (1) the length of an interval $\mI \in L_{r} \backslash L_{r+1}$ satisfies $|\mI| \in [B_{r}: B_{r-1})$ and (2) $\sum_{\mI \in L_{r} \backslash L_{r+1}}|\mI| \leq |\mH_{r-1}| \cdot B_{r-1}$ (see Lemma <ref>).
The last step follows from the choice of $\{B_r\}_{r\in [R]}$. Note we slightly abuse notation and set $|\mH_{0}| = 1$ and $B_{0} = T$.

We can bound the RHS of Eq. (<ref>) using Eq. (<ref>). With probability at least $1-1/(nT)^{\omega(1)}$, one has

\begin{align}
&~ \sum_{r=1}^{R-1}\sum_{\mI \in L_{r}\setminus L_{r+1}}O\left(\sqrt{|\mI|}\log^6 (nT)\right) + O(|\mH_{R-1}|)\notag\\
\leq &~ O\left( \sqrt{n T}\log^6(nT) + \sum_{r=2}^{R-1} |\mH_{r-1}|\cdot \sqrt{T/n}\log^6(nT)  + |\mH_{R-1}|\right)\notag\\
\leq &~ \wt{O}\left(\sqrt{T/n}\right),
\label{eq:regret-last3}
\end{align}

where the second step follows from Lemma <ref>, i.e., $|\mH_{r}| \leq \wt{O}(n)$ holds with high probability for any $r \in [R]$.

Combining Eq. (<ref>) and Eq. (<ref>), we conclude

\begin{align*}
\sum_{t \in [T]}\ell_{t}(i_t) -\sum_{t \in [T]}\ell_{t}(i^{*})  \leq \wt{O}\left(\sqrt{nT}\right)
\end{align*}

holds with probability at least $1-1/(nT)^{\omega(1)}$.
We complete the proof here.

Combining the regret analysis (Lemma <ref>) and the memory bounds (Lemma <ref>), we conclude the proof of Proposition <ref>. We complete the proof of Theorem <ref> by a grouping trick.

We partition the experts $[n]$ into $G = \wt{O}(S)$ groups, with $n' = \wt{O}(n/S)$ experts per group.
We instantiate a meta-thread
[here we use meta-thread to distinguish from the $R$ threads internal to Algorithm <ref>.] of Algorithm <ref> over each group $j \in [G]$, and each meta-thread is viewed as an individual meta expert.
The final decision comes from running the MWU over the set of meta experts $[G]$.
Let the optimal expert $i^{*} \in [n]$ be contained in the $j^{*}$-th group ($j^{*} \in [G]$), the regret guarantee follows from

\begin{align*}
\sum_{t=1}^{T}\ell_t(i_t) - \sum_{t=1}^{T}\ell_t(i^{*}) = &~ \sum_{t=1}^{T}\ell_t(i_t) - \sum_{t=1}^{T}\ell_t(j^{*}) + \sum_{t=1}^{T}\ell_t(j^{*}) - \sum_{t=1}^{T}\ell_t(i^{*})\\
\leq &~ \wt{O}(\sqrt{T}) + \wt{O}(\sqrt{n' T}) =  \wt{O}\left(\sqrt{\frac{nT}{S}}\right),
\end{align*}

where the second step follows from the regret guarantee of MWU and Proposition <ref>.
To bound the memory, note the algorithm maintains $G$ threads of Algorithm <ref> , each takes $\polylog(nT)$ space, so the total space used is at most $G \cdot \polylog(nT) \leq S$. We conclude the proof here.

[1]
Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire.
The nonstochastic multiarmed bandit problem.
SIAM journal on computing, 32(1):48–77, 2002.

[2]
Sepehr Assadi, Yu Chen, and Sanjeev Khanna.
Polynomial pass lower bounds for graph streaming algorithms.
In Proceedings of the 51st Annual ACM SIGACT Symposium on theory
of computing, pages 265–276, 2019.

[3]
Anders Aamand, Justin Chen, Huy Le Nguyen, and Sandeep Silwal.
Improved space bounds for learning with experts.
https://arxiv.org/abs/2303.01453, 2023.

[4]
Ioannis Anagnostides, Constantinos Daskalakis, Gabriele Farina, Maxwell
Fishelson, Noah Golowich, and Tuomas Sandholm.
Near-optimal no-regret learning for correlated equilibria in
multi-player general-sum games.
In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory
of Computing, pages 736–749, 2022.

[5]
Sanjeev Arora, Elad Hazan, and Satyen Kale.
The multiplicative weights update method: a meta-algorithm and
Theory of Computing, 8(1):121–164, 2012.

[6]
Arpit Agarwal, Sanjeev Khanna, and Prathamesh Patil.
A sharp memory-regret trade-off for multi-pass streaming bandits.
Conference on Learning Theory (COLT), 2022.

[7]
Sepehr Assadi and Chen Wang.
Exploration with limited memory: streaming algorithms for coin
tossing, noisy comparisons, and multi-armed bandits.
In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory
of Computing (STOC), 2020.

[8]
Gavin Brown, Mark Bun, Vitaly Feldman, Adam Smith, and Kunal Talwar.
When is memorization of irrelevant training data necessary for
high-accuracy learning?
In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory
of Computing, pages 123–132, 2021.

[9]
Gavin Brown, Mark Bun, and Adam Smith.
Strong memory lower bounds for learning natural models.
Conference on Learning Theory (COLT), 2022.

[10]
Sébastien Bubeck, Nicolo Cesa-Bianchi, et al.
Regret analysis of stochastic and nonstochastic multi-armed bandit
Foundations and Trends® in Machine Learning,
5(1):1–122, 2012.

[11]
Adam Block, Yuval Dagan, Noah Golowich, and Alexander Rakhlin.
Smoothed online learning is as easy as statistical learning.
In Conference on Learning Theory (COLT), 2022.

[12]
Omar Besbes, Yonatan Gur, and Assaf Zeevi.
Non-stationary stochastic optimization.
Operations research, 63(5):1227–1244, 2015.

[13]
Amos Beimel, Haim Kaplan, Yishay Mansour, Kobbi Nissim, Thatchaphol Saranurak,
and Uri Stemmer.
Dynamic algorithms against an adaptive adversary: Generic
constructions and lower bounds.
In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory
of Computing, pages 1671–1684, 2022.

[14]
Sébastien Bubeck, Yuanzhi Li, Haipeng Luo, and Chen-Yu Wei.
Improved path-length regret bounds for bandits.
In Conference On Learning Theory, pages 508–528. PMLR, 2019.

[15]
Avrim Blum and Yishay Mansour.
From external to internal regret.
Journal of Machine Learning Research, 8(6), 2007.

[16]
Mark Braverman, Anup Rao, Omri Weinstein, and Amir Yehudayoff.
Direct products in communication complexity.
In 2013 IEEE 54th Annual Symposium on Foundations of Computer
Science, pages 746–755. IEEE, 2013.

[17]
Mark Braverman and Omri Weinstein.
An interactive information odometer and applications.
In Proceedings of the forty-seventh annual ACM symposium on
Theory of Computing, pages 341–350, 2015.

[18]
Ziv Bar-Yossef, Thathachar S Jayram, Ravi Kumar, and D Sivakumar.
An information statistics approach to data stream and communication
Journal of Computer and System Sciences, 68(4):702–732, 2004.

[19]
Moïse Blanchard, Junhui Zhang, and Patrick Jaillet.
Quadratic memory is necessary for optimal query complexity in convex
optimization: Center-of-mass is pareto-optimal.
arXiv preprint arXiv:2302.04963, 2023.

[20]
Nicolo Cesa-Bianchi and Gábor Lugosi.
Prediction, learning, and games.
Cambridge university press, 2006.

[21]
Paul Christiano, Jonathan A Kelner, Aleksander Madry, Daniel A Spielman, and
Shang-Hua Teng.
Electrical flows, laplacian systems, and faster approximation of
maximum flow in undirected graphs.
In Proceedings of the Forty-third Annual ACM Symposium on Theory
of Computing (STOC), pages 273–282, 2011.

[22]
Xi Chen and Binghui Peng.
Hedging in games: Faster convergence of external and swap regrets.
Advances in Neural Information Processing Systems,
33:18990–18999, 2020.

[23]
Xi Chen, Christos Papadimitriou, and Binghui Peng.
Memory bounds for continual learning.
In 2022 IEEE 63th Annual Symposium on Foundations of Computer
Science (FOCS), 2022.

[24]
Miroslav Dudík, Nika Haghtalab, Haipeng Luo, Robert E Schapire, Vasilis
Syrgkanis, and Jennifer Wortman Vaughan.
Oracle-efficient online learning and auction design.
Journal of the ACM (JACM), 67(5):1–57, 2020.

[25]
Yuval Dagan and Ohad Shamir.
Detecting correlations with little memory and communication.
In Conference On Learning Theory (COLT), 2018.

[26]
Vitaly Feldman.
Does learning require memorization? a short tale about a long tail.
In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory
of Computing, pages 954–959, 2020.

[27]
Yoav Freund and Robert E Schapire.
A decision-theoretic generalization of on-line learning and an
application to boosting.
Journal of computer and system sciences, 55(1):119–139, 1997.

[28]
Yoav Freund and Robert E Schapire.
Adaptive game playing using multiplicative weights.
Games and Economic Behavior, 29(1-2):79–103, 1999.

[29]
Yoav Freund, Robert E Schapire, Yoram Singer, and Manfred K Warmuth.
Using and combining predictors that specialize.
In Proceedings of the twenty-ninth annual ACM symposium on
Theory of computing, pages 334–343, 1997.

[30]
Dan Garber and Elad Hazan.
Sublinear time algorithms for approximate semidefinite programming.
Mathematical Programming, 158(1):329–361, 2016.

[31]
Alon Gonen, Elad Hazan, and Shay Moran.
Private learning implies online learning: An efficient reduction.
Advances in Neural Information Processing Systems, 32, 2019.

[32]
Sumegha Garg, Pravesh Kumar Kothari, Pengda Liu, and Ran Raz.
Memory-sample lower bounds for learning parity with noise.
In 24th International Conference on Approximation Algorithms for
Combinatorial Optimization Problems (APPROX 2021) and 25th International
Conference on Randomization and Computation (RANDOM 2021), 2021.

[33]
Alon Gonen, Shachar Lovett, and Michal Moshkovitz.
Towards a combinatorial characterization of bounded-memory learning.
Advances in Neural Information Processing Systems (NeurIPS),

[34]
Sumegha Garg, Ran Raz, and Avishay Tal.
Extractor-based time-space lower bounds for learning.
In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory
of Computing (STOC), 2018.

[35]
Sumegha Garg, Ran Raz, and Avishay Tal.
Time-space lower bounds for two-pass learning.
In 34th Computational Complexity Conference (CCC), 2019.

[36]
Elad Hazan.
Introduction to online convex optimization.
Foundations and Trends® in Optimization,
2(3-4):157–325, 2016.

[37]
Nika Haghtalab, Yanjun Han, Abhishek Shetty, and Kunhe Yang.
Oracle-efficient online learning for beyond worst-case adversaries.
Advances in Neural Information Processing Systems (NeurIPS),

[38]
Elad Hazan and Tomer Koren.
The computational power of optimization in online learning.
In Proceedings of the Forty-eighth Annual ACM Symposium on
Theory of Computing (STOC), pages 128–141, 2016.

[39]
Avinatan Hasidim, Haim Kaplan, Yishay Mansour, Yossi Matias, and Uri Stemmer.
Adversarially robust streaming algorithms via differential privacy.
Advances in Neural Information Processing Systems, 33:147–158,

[40]
Sam Hopkins, Jerry Li, and Fred Zhang.
Robust and heavy-tailed mean estimation made simple, via regret
Advances in Neural Information Processing Systems (NeurIPS),

[41]
Thomas Holenstein.
Parallel repetition: simplifications and the no-signaling case.
In Proceedings of the thirty-ninth annual ACM symposium on
Theory of computing, pages 411–419, 2007.

[42]
Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty.
Smoothed analysis with adaptive adversaries.
In 2021 IEEE 62nd Annual Symposium on Foundations of Computer
Science (FOCS), 2022.

[43]
Elad Hazan and Comandur Seshadhri.
Adaptive algorithms for online decision problems.
In Electronic colloquium on computational complexity (ECCC),

[44]
Hartmut Klauck.
A strong direct product theorem for disjointness.
In Proceedings of the forty-second ACM symposium on Theory of
computing, pages 77–86, 2010.

[45]
Adam Klivans and Raghu Meka.
Learning graphical models using multiplicative weights.
In 2017 IEEE 58th Annual Symposium on Foundations of Computer
Science (FOCS), pages 343–354. IEEE, 2017.

[46]
Adam Kalai and Santosh Vempala.
Efficient algorithms for online decision problems.
Journal of Computer and System Sciences, 71(3):291–307, 2005.

[47]
Wouter M Koolen and Tim Van Erven.
Second-order quantile methods for experts and combinatorial games.
In Conference on Learning Theory, pages 1155–1175. PMLR, 2015.

[48]
David Liau, Zhao Song, Eric Price, and Ger Yang.
Stochastic multi-armed bandits in constant space.
In International Conference on Artificial Intelligence and
Statistics (AISTATS), 2018.

[49]
N Littlestone and MK Warmuth.
The weighted majority algorithm.
In 30th Annual Symposium on Foundations of Computer Science
(FOCS), 1989.

[50]
Arnab Maiti, Vishakha Patil, and Arindam Khan.
Multi-armed bandits with bounded arm-memory: Near-optimal guarantees
for best-arm identification and regret minimization.
Advances in Neural Information Processing Systems (NeurIPS),

[51]
Annie Marsden, Vatsal Sharan, Aaron Sidford, and Gregory Valiant.
Efficient convex optimization requires superlinear memory.
In Conference on Learning Theory (COLT), 2022.

[52]
Erik Ordentlich and Thomas M Cover.
The cost of achieving the best portfolio in hindsight.
Mathematics of Operations Research, 23(4):960–982, 1998.

[53]
Serge A Plotkin, David B Shmoys, and Éva Tardos.
Fast approximation algorithms for fractional packing and covering
Mathematics of Operations Research, 20(2):257–301, 1995.

[54]
Binghui Peng and Fred Zhang.
Online prediction in sub-linear space.
In Proceedings of the Thirty Fourth Annual ACM-SIAM Symposium on
Discrete Algorithms, 2023.

[55]
Ran Raz.
A parallel repetition theorem.
In Proceedings of the twenty-seventh annual ACM symposium on
Theory of computing, pages 447–456, 1995.

[56]
Ran Raz.
A time-space lower bound for a large class of learning problems.
In 2017 IEEE 58th Annual Symposium on Foundations of Computer
Science (FOCS), 2017.

[57]
Ran Raz.
Fast learning requires good memory: A time-space lower bound for
parity learning.
Journal of the ACM (JACM), 66(1):1–18, 2018.

[58]
Tim Roughgarden.
Cs364a: Algorithmic game theory. lecture 17: No-regret dynamics,
November 2013.

[59]
Alexander A Sherstov.
Communication complexity theory: Thirty-five years of set
In International Symposium on Mathematical Foundations of
Computer Science (MFCS), pages 24–43. Springer, 2014.

[60]
Vatsal Sharan, Aaron Sidford, and Gregory Valiant.
Memory-sample tradeoffs for linear regression with small error.
In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory
of Computing (STOC), 2019.

[61]
Jacob Steinhardt, Gregory Valiant, and Stefan Wager.
Memory, communication, and statistical queries.
In Conference on Learning Theory (COLT), 2016.

[62]
Vaidehi Srinivas, David P. Woodruff, Ziyu Xu, and Samson Zhou.
Memory bounds for the experts problem.
In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory
of Computing (STOC), 2022.

[63]
Chen-Yu Wei and Haipeng Luo.
More adaptive algorithms for adversarial bandits.
In Conference On Learning Theory, pages 1263–1291. PMLR, 2018.

[64]
David Woodruff, Fred Zhang, and Samson Zhou.
Streaming algorithms for learning with experts: Deterministic versus

§ PROBABILISTIC TOOL

We state the version of Chernoff bound and Azuma-Hoeffding bound used in this paper.

Let $X = \sum_{i=1}^n X_i$, where $X_i=1$ with probability $p_i$ and $X_i = 0$ with probability $1-p_i$, and all $X_i$ are independent. Let $\mu = \E[X] = \sum_{i=1}^n p_i$. Then

1. $ \Pr[ X \geq (1+\delta) \mu ] \leq \exp ( - \delta \mu / 3 ) $, $\forall\, \delta > 1$ ;

2. $ \Pr[ X \leq (1-\delta) \mu ] \leq \exp ( - \delta^2 \mu / 2 ) $, $\forall\, 0 < \delta < 1$.

Let $X_0, \ldots, X_n$ be a martingale sequence with respect to the filter $F_0 \subseteq F_1 \cdots \subseteq F_n$ such that for $Y_i = X_i - X_{i-1}$, $i \in [n]$, we have that $|Y_i| = |X_i - X_{i-1}| \leq c_i$. Then

\begin{align*}
\Pr[|X_t - X_0 | \geq t ] \leq 2\exp\left(-\frac{t^2}{2\sum_{i=1}^{n}c_i^2}\right).
\end{align*}

§ MISSING PROOF FROM SECTION <REF>

Consider the following distribution $\mu'$ defined over $\{0, 1\}^{2M}$

* Sample an index $i^{*} \in [M]$ uniformly at random and set $(x_{A, i}, x_{B, i}) = (1,1)$

* For the rest of coordinates, set $(x_{A, i}, x_{B, i})$ to be $(0,1), (1, 0), (0,0)$ with equal probability.

The only (minor) difference between $\mu$ and $\mu'$ is that $(x_{A}, x_{B})$ contains exactly $\frac{M-1}{3}$ pairs of $(0,0), (0,1), (1,1)$ under $\mu$.

An internal information cost lower bound of $\mu'$ is known, in particular, we have

The internal information cost of any communication protocol for Disjointness (with success probability at least $2/3$) under distribution $\mu'$ is at least $\Omega(M)$.

Given an instance of Setdisjointness $(x_A', x_{B}')$ under distribution $\mu'$, we turn it into an input from $\mu$ by augmenting a few coordinates.

Alice and Bob augment their input to $x_{A}, x_{B}$ ($x_A, x_B \in \{0, 1\}^{3M+1}$ such that there are exact $M$ pairs of $(0,1), (1,0), (0,1)$. This can be done by (1) Alice appends $M - |x_A'| + 1$ coordinates of $1$ and (2) Bob appends $M - |x_B'| +1$ (different) coordinates of $1$. They then use public randomness to shuffle the coordinates and then run the protocol $\Pi$ (designed for input from $\mu$) on $x_{A}, x_{B}$. Let $\gamma$ be the public randomness used for shuffling.

It is clearly that Alice and Bob would success with probability at least $2/3$, to bound the internal information cost, we note

\begin{align*}
\IC_{\mu'}(\Pi') = &~ I(X_A'; \Pi'|X_B') + I(X_B'; \Pi'|X_A') \\
= &~ I(X_A'; \Pi, \gamma |X_B') + I(X_B'; \Pi, \gamma|X_A') \\
= &~ I(X_A'; \Pi |X_B', \gamma) + I(X_B'; \Pi|X_A', \gamma) \\
= &~ I(X_A; \Pi |X_B, \gamma) + I(X_B; \Pi |X_A, \gamma)\\
\leq &~ I(X_A; \Pi |X_B) + I(X_B; \Pi |X_A)\\
= &~ \IC_{\mu}(\Pi).
\end{align*}

The third step follows from the chain rule of mutual information and $I(X_A'; \gamma| X_{B}') = 0$.
The fourth step holds since $(X_B, \gamma)$ are one to one $(X_B', \gamma)$, and  $(X_A, \gamma)$ are one to one $(X_A', \gamma)$.
The fifth step holds since $I(\gamma; \Pi | X_{A}, X_{B}) = 0$, i.e., the transcript $\Pi$ is independent of the  permutation function given $X_A$ and $X_B$. We finish the proof here.