Tight Gap-Dependent Memory-Regret Trade-Off for Single-Pass Streaming Stochastic Multi-Armed Bandits Zichun Ye, Chihao Zhang, Jiahao Zhao Abstract We study the problem of minimizing gap-dependent regret for single-pass streaming stochastic multi-armed bandits (MAB). In this problem, the n n arms are present in a stream, and at most m < n m 0 Δ i 1 − 2 ​ α ) O_{\alpha}\Big(\frac{(n-m)T^{\frac{1}{\alpha+1}}}{n^{1+{\frac{1}{\alpha+1}}}}\displaystyle\sum_{i:\Delta_{i}>0}\Delta_{i}^{1-2\alpha}\Big) 1 1 1 In this paper, the notations O α , Ω α , Θ α O_{\alpha},\Omega_{\alpha},\Theta_{\alpha} subsume a multiplicative factor depending only on α \alpha . This is fine since we usually take α \alpha to be a constant. and another applicable for m < 2 3 ​ n m<\frac{2}{3}n with regret at most O α ( T 1 α + 1 m 1 α + 1 ∑ i : Δ i > 0 Δ i 1 − 2 ​ α ) O_{\alpha}\Big(\frac{T^{\frac{1}{\alpha+1}}}{m^{\frac{1}{\alpha+1}}}\displaystyle\sum_{i:\Delta_{i}>0}\Delta_{i}^{1-2\alpha}\Big) . We also prove matching lower bounds for both cases by showing that for any constant α ≥ 1 \alpha\geq 1 and any m ≤ k < n m\leq k 0 Δ i 1 − 2 ​ α ) \Omega_{\alpha}\Big(\frac{(k-m+1)T^{\frac{1}{\alpha+1}}}{k^{1+\frac{1}{\alpha+1}}}\sum_{i:\Delta_{i}>0}\Delta_{i}^{1-2\alpha}\Big) . This is the first tight gap-dependent regret bound for streaming MAB. Prior to our work, an O ( ∑ i : Δ > 0 T ​ log ⁡ T Δ i ) O\Big(\sum_{i\colon\Delta>0}\frac{\sqrt{T}\log T}{\Delta_{i}}\Big) upper bound for the special case of α = 1 \alpha=1 and m = O ⁡ ( 1 ) m=O(1) was established by Agarwal, Khanna and Patil (COLT’22). In contrast, our results provide the correct order of regret as Θ ( 1 m ∑ i : Δ > 0 T Δ i ) \Theta\Big(\frac{1}{\sqrt{m}}\sum_{i\colon\Delta>0}\frac{\sqrt{T}}{\Delta_{i}}\Big) . 1 Introduction The stochastic multi-armed bandits (MAB) is a popular T -round game that has been widely studied in online learning. In the game, one player faces n arms. In each round t\in[T] , the player chooses an arm A_{t} among the n arms and gets a reward drawn from a predetermined reward distribution with mean \mu_{A_{t}}\in[0,1] . The arm with the largest reward mean \mu_{*} is called the best arm. The total expected regret is defined as \mathbf{E}\left[R(T)\right]=\mathbf{E}\left[\sum_{t=1}^{T}\mu_{*}-\mu_{A_{t}}\right], where the expectation is over the randomness from the player’s strategy, and the aim is to minimize \mathbf{E}\left[R(T)\right] . The classic MAB problem defined above has been thoroughly studied. It is known that the expected minimax regret, namely the regret of the best algorithm against the worst input, is \Theta\left(\sqrt{nT}\right) via the Upper Confidence Bounds (UCB) algorithm and its variants (see e.g. [ AB09 , Aue02 , GC11 ] ). As for the gap-dependent regret, the mean gap \Delta_{i}:=\mu_{*}-\mu_{i} for each i\in[n] is involved in such bound. The UCB algorithm provides an regret upper bound O\left(\sum_{i\in[n]\colon\Delta_{i}>0}\frac{\log T}{\Delta_{i}}\right) (see e.g. [ GC11 , KCG12 , LS20 ] ). A recent line of research modeled the MAB problem in the streaming setting to incorporate the situation where the number of arms is huge and cannot be stored in the memory at the same time. In this model, the n arm arrives one by one in a stream, and only m0}\frac{\sqrt{T}\log T}{\Delta_{i}}\right) , proved in [ AKP22 ] , which holds only for m=O(1) . This upper bound already suggests that the gap-dependent regret bound can be superior to the minimax regret bound ( \widetilde{O}(\sqrt{T}) v.s. O\left(T^{\frac{2}{3}}\right) ). However, as mentioned before, it is well known that when no memory constraint is considered, the dependency on T in the gap-dependent bound can be as low as \log T . Therefore, it is natural to ask what is the correct regret bound in the memory-constrained setting, and particularly how the memory affects the bound. On the other hand, since the mean gap \Delta_{i} ’s are part of the input instance and might depend on T , there might be a trade-off between the dependency on \frac{1}{\Delta_{i}} and T in the regret bound. To capture this trade-off, we introduce a new parameter \alpha\geq 1 and aim at establishing the regret bounds of the form f(\alpha,m,n,T)\cdot\sum_{i\colon\Delta_{i}>0}\Delta_{i}^{1-2\alpha} for some function f . Therefore previous gap-dependent bounds, either with or without memory constraint, correspond to the case \alpha=1 . 1.1 Our results In this work, we design new algorithms and prove matching regret lower bounds for the problem, confirming that the gap-dependent regret is \Theta_{\alpha}\left(\frac{(n-m)T^{\frac{1}{\alpha+1}}}{n^{1+{\frac{1}{\alpha+1}}}}\displaystyle\sum_{i:\Delta_{i}>0}\Delta_{i}^{1-2\alpha}\right) when m\geq\frac{2}{3}n and \Theta_{\alpha}\left(\frac{T^{\frac{1}{\alpha+1}}}{m^{{\frac{1}{\alpha+1}}}}\displaystyle\sum_{i:\Delta_{i}>0}\Delta_{i}^{1-2\alpha}\right) when 2\leq m<\frac{2}{3}n for any constant \alpha\geq 1 . Our results are summarized in Table 1 . Table 1: Summary of results for streaming MAB Regret Bounds Memory [ Wan23 ] O\left(n^{\frac{1}{3}}T^{\frac{2}{3}}\right) m=\Theta(\log^{*}n) \Omega\left(n^{\frac{1}{3}}T^{\frac{2}{3}}\right) m\leq\frac{n}{20} [ HYZ25 ] \Theta\left(\frac{n-m}{n^{\frac{2}{3}}}\cdot T^{\frac{2}{3}}\right) 2\leq m0}\frac{\sqrt{T}\log T}{\Delta_{i}}\right) m=O(1) [This work] \alpha=1,\;\Theta\left(\frac{(n-m)\sqrt{T}}{n^{\frac{3}{2}}}\displaystyle\sum_{i:\Delta_{i}>0}\frac{1}{\Delta_{i}}\right) m\geq\frac{2}{3}n \alpha=1,\;\Theta\left(\frac{\sqrt{T}}{m^{\frac{1}{2}}}\displaystyle\sum_{i:\Delta_{i}>0}\frac{1}{\Delta_{i}}\right) 2\leq m<\frac{2}{3}n [This work] \forall\alpha\geq 1,\;\Theta_{\alpha}\left(\frac{(n-m)T^{\frac{1}{\alpha+1}}}{n^{1+{\frac{1}{\alpha+1}}}}\displaystyle\sum_{i:\Delta_{i}>0}\Delta_{i}^{1-2\alpha}\right) m\geq\frac{2}{3}n \forall\alpha\geq 1,\;\Theta_{\alpha}\left(\frac{T^{\frac{1}{\alpha+1}}}{m^{{\frac{1}{\alpha+1}}}}\displaystyle\sum_{i:\Delta_{i}>0}\Delta_{i}^{1-2\alpha}\right) 2\leq m<\frac{2}{3}n Similar to the minimax regret case, the algorithm for the large memory case ( m\geq\frac{2}{3}n ) differs from that of the small memory case ( m<\frac{2}{3}n ). The reason is that the player continually faces the task of determining which arm to discard from the memory during the game. The task is called the best arm retention (BAR) problem and has been recently thoroughly studied [ HYZ25 , CHZ24 ] . It is known that the complexity of the problem is the same as that of the best arm identification (BAI) problem when the memory is small while a more efficient algorithm exists when the memory is large. Therefore, algorithms tailored for both small and large memory are necessary. Our bounds suggest many interesting behaviors of the model. Taking \alpha=1 , our results reveal that with m=n-1 , namely with only one unit less memory, the dependency on T significantly increases from \log T to \sqrt{T} . Another interesting phenomenon shown by our results is that the regret is not “smooth” in m , as shown in Figure 1 when \alpha=1 2 2 2 Since we only provide non-asymptotic bounds, the curve in Figure 1 demonstrates the regret bound qualitatively. In fact, the threshold m=\frac{2}{3}n can be replaced by any m=c\cdot n for constant c\in[\frac{2}{3},1) . . This is in sharp contrast with the minimax regret \Theta\left(\frac{n-m}{n^{\frac{2}{3}}}\cdot T^{\frac{2}{3}}\right) which is smooth with respect to m for all 2\leq m0}\Delta_{i}^{1-2\alpha}\right) . Therefore, the best lower bound is obtained by optimizing k . For m<\frac{2}{3}n , the best choice is k=\frac{3}{2}m while for m\geq\frac{2}{3}n , the best choice is k=n-1 . It is helpful to compare our results with the previous ones for \alpha=1 . In this case, our bound is \Theta\left(\frac{n-m}{n^{\frac{3}{2}}}\sum_{i\colon\Delta_{i}>0}\frac{\sqrt{T}}{\Delta_{i}}\right) when m\geq\frac{2}{3}n and \Theta\left(\frac{1}{\sqrt{m}}\sum_{i\colon\Delta_{i}>0}\frac{\sqrt{T}}{\Delta_{i}}\right) when 2\leq m<\frac{2}{3}n . It improves the previous best bound in [ AKP22 ] , which only holds for m=O(1) , and also fills the blank space in the large memory setting. \Theta\Big(\displaystyle\frac{1}{\sqrt{m}}\sum_{i:\Delta_{i}>0}\frac{\sqrt{T}}{\Delta_{i}}\Big) \Theta\Big(\displaystyle\frac{n-m}{n^{\frac{3}{2}}}\sum_{i:\Delta_{i}>0}\frac{\sqrt{T}}{\Delta_{i}}\Big) m=\frac{2}{3}n m=n-1 Memory ( m ) Regret Figure 1: Regret with respect to the memory size m . 1.2 Related work The MAB problem was first introduced in [ Rob52 ] . The work [ AB09 ] proved an optimal regret bound of \Theta(\sqrt{nT}) for both stochastic and adversarial cases. Then [ LSPY18 ] first took the streaming MAB problem into consideration and obtained an instance-dependent upper bound using O(\log T) passes and O(1) memory. The work of [ CK20 ] gave a generalized upper bound of O\left(\frac{n^{\frac{3}{2}}}{m}\sqrt{T\log\frac{T}{nm}}\right) for 2\leq m0}\frac{\sqrt{T}\log T}{\Delta_{i}}\right) when m=O(1) and P=1 . Very recently, [ HYZ25 ] studied the minimax regret bound in the multi-pass setting and obtained tight bounds in terms of m,n,T and P . In particular, they obtained a tight bound of \Theta\left(\frac{n-m}{n^{\frac{2}{3}}}\cdot T^{\frac{2}{3}}\right) in a single pass. 2 Preliminaries Multi-armed bandit (MAB) We defined the problem of MAB at the beginning of the introduction. Here we introduce some further notations and define the game in detail. We use a mean vector \nu=\left(\mu_{1},\mu_{2},\cdots,\mu_{n}\right) to denote an instance of MAB in which the i -th arm has a Bernoulli reward \mathtt{Ber}\left(\mu_{i}\right) . We use i^{*}=\arg\max_{i\in[n]}\mu_{i} to denote the index of the arm with maximum mean reward. We assume the choice of i^{*} is unique. We will sometimes call the i -th arm \mathtt{arm}_{i} and write \mathtt{arm}_{i^{*}} as \mathtt{arm}_{*} . We will also write \mu_{*} instead of \mu_{i^{*}} for convenience. For every i\in[n] , we use a random variable T_{i}:=\sum_{t=1}^{T}\mathbb{1}\left[A_{t}=i\right] to denote the number of times the i -th arm has been pulled during the game. We use \mathbb{P}_{\nu}\left[\cdot\right] and \mathbf{E}_{\nu}\left[\cdot\right] to denote the probability and expectation of the algorithm running on instance \nu . In the MAB game, the player is given a set of n arms, denoted as [n] . Each arm has a reward mean \mu_{i} from a fixed distribution \mathcal{D}_{i} . A T -round decision game starts as follows: in each round t\in[T] , the player first selects an arm A_{t}\in[n] to pull based on the information observed in previous rounds; then the player observes and gains reward of r_{t}(A_{t})\sim\mathcal{D}_{A_{t}} . The player’s objective is to minimize the difference between the cumulative reward of the best arm and the player’s own cumulative reward. That is, the player aims to design an algorithm \mathcal{A} to minimize the expected regret \mathbf{E}\left[R(T)\right]=\mathbf{E}\left[\sum_{t=1}^{T}r_{t}(i^{*})-r_{t}(A_{t})\right]=\mathbf{E}\left[\sum_{t=1}^{T}\mu_{*}-\mu_{A_{t}}\right]. Streaming stochastic MAB. The streaming MAB model was first formalized in [ LSPY18 ] . In this model, the n arm arrives sequentially in the stream and the number of arms that can be stored at the same time is substantially smaller than n . A single pass means every arm in the stream only comes once, that is, if an arm is not stored yet or has been discarded from the memory, it cannot be retrieved later. We consider the worst-case order of the stream. In each round t\in[T] , the player acts in two stages, which include manipulating arm storage (discard arms in the memory, read new arms in the stream) and pulling arm (choose an arm A_{t} in the memory to pull, observe and gain rewards) respectively. We emphasize that in one round, the player can discard and read any number of arms (including zero) but can only pull exactly once. Best arm retention. To obtain the lower bound, we observe that it is important for an algorithm to pull an arm enough times before discarding it. Otherwise, it can probably discard all good arms. The work of [ CHZ24 ] modeled and called it the best arm retention (BAR) problem. The BAR problem is to retain m arms out of all n arms after T rounds and make sure that the best arm is not discarded with high probability. In other words, the player has to discard n-m relatively bad arms during the game. A \left(\varepsilon,\delta\right) -PAC algorithm for BAR problem satisfies that for any fixed parameter \varepsilon,\delta\in(0,1) , it retains an \varepsilon -best arm in the m arms with probability at least 1-\delta . Gap-dependent bound. This paper focuses on gap-dependent regret bounds. Define the gap vector of a certain instance \nu as S(\nu)=(\Delta_{i}(\nu))_{i\in[n]} where \Delta_{i}(\nu) is the mean gap between the best arm and the i -th arm in the instance \nu . For an instance \nu of MAB, the gap-dependent regret ideally involves parameters m,n,T and the gap vector S(\nu) . In this work, we define the lower bound for the gap-dependent regret in the following sense. Definition 1 . Let m,n be fixed. Denote \Pi as the set of all possible algorithms with memory size m , and {I} as the set of all possible instances with n arms. We say R(m,n,T,S) is a non-asymptotic gap-dependent regret lower bound, if and only if for any algorithm \mathcal{A}\in\Pi , there exists \nu\in{I} such that R^{\mathcal{A},\nu}(T)\geq R(m,n,T,S(\nu)), for sufficiently large T , where R^{\mathcal{A},\nu}(T) represents the regret incurred by running \mathcal{A} on \nu after T rounds. The non-asymptotic bounud means that T is a part of the input and therefore \Delta_{i} might depend on T . Compared to the minimax lower bound, R(m,n,T,S) is a functional depending on the gap-vector S(\nu)=(\Delta_{i}(\nu))_{i\in[n]} where each \Delta_{i}(\cdot) is a function on the instance. Nevertheless, we will use R(T) as a shorthand for R(m,n,T,S) when no ambiguity arises. We will use the UCB algorithm as a black box and place the details of it in Section A.2 . We will use the following important property of the UCB algorithm in our analysis. Lemma 2 ( [ Aue02 ] ) . Giving n arms which have Bernoulli rewards in the memory and running UCB on them for T rounds, then for any \mathtt{arm}_{i} with \Delta_{i}>0 : \mathbf{E}\left[T_{i}\right]\leq\frac{8\log T}{\Delta_{i}^{2}}. We will also use the following technical lemma, which is a simple consequence of the Hoeffding’s inequality. Its proof is provided in Section A.1 . Lemma 3 . Let \mathtt{arm}_{1} and \mathtt{arm}_{2} be two different arms with reward means of \mu and \mu+\Delta,\Delta>0 respectively. Suppose we sample each arm L times and obtain empirical mean of \widehat{\mu}_{1} and \widehat{\mu}_{2} respectively, then \mathbb{P}\left[\widehat{\mu}_{1}\geq\widehat{\mu}_{2}\right]\leq e^{-\frac{L\Delta^{2}}{2}}. 3 Gap-Dependent Regret Upper Bounds In this section, we will propose two algorithms, which apply to large m and small m respectively. The philosophy behind the two algorithms is the same: one tries to retain the good arm in the memory and therefore solves a BAR problem in the streaming setting. However, when the memory is large, this can be done more efficiently. 3.1 Large memory case ( \frac{2}{3}n\leq m\leq n-1 ) When m\geq\frac{2}{3}n , we can simply read the first m arms into the memory and have enough room to replace parts of them by rest arms in one batch. We simply pick n-m pairs out of the m arms, compare them pairwise, and replace the n-m worst arms with the remaining n-m fresh arms in the stream. After the manipulation of the memory, we apply a standard UCB algorithm for arms in the memory in the remaining rounds. Algorithm 1 Single-pass algorithm for MAB when \frac{2}{3}n\leq m\leq n-1 Input: Time horizon T , memory size m , number of arms n and a constant \alpha\geq 1 . 1: Let L\leftarrow\left(\frac{2\alpha}{e}\right)^{\frac{\alpha}{\alpha+1}}\cdot\left(\frac{T}{n}\right)^{\frac{1}{\alpha+1}} , c\leftarrow n-m ; 2: Read in the first m arms; 3: Choose 2c arms from the memory u.a.r and denote them by S=\left\{s_{1},s_{2},\dots,s_{2c}\right\} ; 4: for i=1,2,\dots,c do 5: Pull s_{2i-1},s_{2i} each L times, calculate their empirical means respectively; 6: Discard the one with less empirical mean; 7: Read in the remaining c arms in the stream, denote all the m arms in memory as M ; 8: Run UCB on M until the game ends; \triangleright The Exploitation Phase The strategy for the analysis of the algorithm is as follows. If the best arm \mathtt{arm}_{*} does not show up in the first m arms, then it must belong to the last M , and thus the UCB algorithm will take care of everything. Otherwise, \mathtt{arm}_{*} has a probability of \frac{2c}{m} to be chosen into S . Then we carefully analyze its probability of being beaten by another sub-optimal arm in L rounds and deduce the bound for regret incurred by this bad event. We obtain the following theorem. Theorem 4 . Given any \alpha\geq 1 and any input instance, assuming T is sufficiently large, Algorithm 1 uses the memory of m arms with expected regret \mathbf{E}\left[R(T)\right]=O\left(\left(\frac{2\alpha}{e}\right)^{\frac{\alpha}{\alpha+1}}\frac{\left(n-m\right)T^{\frac{1}{\alpha+1}}}{n^{1+{\frac{1}{\alpha+1}}}}\displaystyle\sum_{i:\Delta_{i}>0}\Delta_{i}^{1-2\alpha}\right). Proof. We first define some events in the probability space induced by running our algorithm on a fixed instance. For every i\in[n]\cup\{*\} , • \mathcal{S}_{i}: the \mathtt{arm}_{i} is in the set S found in 3 of Algorithm 1 . • \mathcal{C}_{i}: the \mathtt{arm}_{i} and \mathtt{arm}_{*} are placed in the same group. • \mathcal{B}_{i}: the \mathtt{arm}_{i} beats \mathtt{arm}_{*} (the empirical mean of \mathtt{arm}_{i} is larger than \mathtt{arm}_{*} in 6 of Algorithm 1 ). • \mathcal{M}_{i}: the \mathtt{arm}_{i} is in the final collection of arms M . Note that when i=* , we mean the best arm. We use L_{1} to denote the number of rounds before the execution of 8 in Algorithm 1 and L_{2} be the remaining rounds consumed in 8 . For each i\in[n] , we denote by L_{1,i} and L_{2,i} the number of rounds playing the \mathtt{arm}_{i} during the first L_{1} and the last L_{2} rounds respectively. Clearly L_{1}+L_{2}=T and \sum_{i\in[n]}L_{c,i}=L_{c} for c=1,2 . We also use R_{1} and R_{2} to denote the regret incurred in the first L_{1} rounds and the last L_{2} rounds respectively. Then R(T)=R_{1}+R_{2} . According to the position of \mathtt{arm}_{*} in the stream, we classify the proof into two cases. Case 1: The \mathtt{arm}_{*} is in the last c=n-m arms. Therefore \mathbb{P}\left[\mathcal{M}_{*}\right]=1 , which means that we can bound the regret in the exploitation phase using Lemma 2 . That is, \displaystyle\mathbf{E}\left[R(T)\right] \displaystyle=\mathbf{E}\left[R_{1}\right]+\mathbf{E}\left[R_{2}\right]=\sum_{i:\Delta_{i}>0}\Delta_{i}\cdot\mathbf{E}\left[L_{1,i}\right]+\mathbf{E}\left[R_{2}\right] \displaystyle=\sum_{i:\Delta_{i}>0}\Delta_{i}\cdot\left(\mathbb{P}\left[\mathcal{S}_{i}\right]\mathbf{E}\left[L_{1,i}\;\middle|\;\mathcal{S}_{i}\right]+\mathbb{P}\left[\overline{\mathcal{S}}_{i}\right]\mathbf{E}\left[L_{1,i}\;\middle|\;\overline{\mathcal{S}}_{i}\right]\right)+\mathbf{E}\left[R_{2}\right] \displaystyle\leq\sum_{i:\Delta_{i}>0}\Delta_{i}\cdot\frac{2c}{m}\cdot\left(\frac{2\alpha}{e}\right)^{\frac{\alpha}{\alpha+1}}\cdot\left(\frac{T}{n}\right)^{\frac{1}{\alpha+1}}+\sum_{i:\Delta_{i}>0}\Delta_{i}\cdot\frac{8\log T}{\Delta_{i}^{2}} \displaystyle\overset{(\heartsuit)}{=}O\left(\left(\frac{2\alpha}{e}\right)^{\frac{\alpha}{\alpha+1}}\frac{(n-m)T^{\frac{1}{\alpha+1}}}{n^{1+{\frac{1}{\alpha+1}}}}\displaystyle\sum_{i:\Delta_{i}>0}\Delta_{i}^{1-2\alpha}\right), where (\heartsuit) is because T is sufficiently large and \forall 0<\Delta_{i}<1,\frac{1}{\Delta_{i}}\leq\Delta_{i}^{1-2\alpha} . Case 2: The best arm \mathtt{arm}_{*} is in the first m arms. In this case, it is possible that \mathtt{arm}_{*} does not belong to M and we denote the best arm in M as \mathtt{arm}_{\mathtt{king}} . We first bound \mathbf{E}\left[R_{1}\right]: \displaystyle\mathbf{E}\left[R_{1}\right] \displaystyle=\sum_{i:\Delta_{i}>0}\Delta_{i}\cdot\left(\mathbb{P}\left[\mathcal{S}_{i}\right]\mathbf{E}\left[L_{1,i}\;\middle|\;\mathcal{S}_{i}\right]+\mathbb{P}\left[\overline{\mathcal{S}}_{i}\right]\mathbf{E}\left[L_{1,i}\;\middle|\;\overline{\mathcal{S}}_{i}\right]\right) \displaystyle\leq\sum_{i:\Delta_{i}>0}\Delta_{i}\cdot\frac{2c}{m}\cdot\left(\frac{2\alpha}{e}\right)^{\frac{\alpha}{\alpha+1}}\cdot\left(\frac{T}{n}\right)^{\frac{1}{\alpha+1}}=O\left(\left(\frac{2\alpha}{e}\right)^{\frac{\alpha}{\alpha+1}}\frac{(n-m)T^{\frac{1}{\alpha+1}}}{n^{1+{\frac{1}{\alpha+1}}}}\displaystyle\sum_{i:\Delta_{i}>0}\Delta_{i}\right). Then we decompose \mathbf{E}\left[R_{2}\right] according to whether \mathtt{arm}_{*} belongs to M : \displaystyle\mathbf{E}\left[R_{2}\right] \displaystyle=\mathbb{P}\left[\mathcal{M}_{*}\right]\mathbf{E}\left[R_{2}\;\middle|\;\mathcal{M}_{*}\right]+\mathbb{P}\left[\overline{\mathcal{M}}_{*}\right]\mathbf{E}\left[R_{2}\;\middle|\;\overline{\mathcal{M}}_{*}\right] \displaystyle\leq\mathbf{E}\left[R_{2}\;\middle|\;\mathcal{M}_{*}\right]+\mathbb{P}\left[\overline{\mathcal{M}}_{*}\right]\mathbf{E}\left[R_{2}\;\middle|\;\overline{\mathcal{M}}_{*}\right] \displaystyle\overset{(\heartsuit)}{=}\mathbf{E}\left[R_{2}\;\middle|\;M_{*}\right]+\displaystyle\sum_{i\colon\mathtt{arm}_{i}\neq\mathtt{arm}_{*}}\mathbb{P}\left[\mathcal{B}_{i}\right]\mathbf{E}\left[R_{2}\;\middle|\;\mathcal{B}_{i}\right] \displaystyle\leq\sum_{i:\Delta_{i}>0}\frac{8\log T}{\Delta_{i}}+\displaystyle\sum_{i\colon\mathtt{arm}_{i}\neq\mathtt{arm}_{*}}\mathbb{P}\left[\mathcal{B}_{i}\right]\mathbf{E}\left[R_{2}\;\middle|\;\mathcal{B}_{i}\right], (1) where (\heartsuit) holds since \left\{\mathcal{B}_{i}\;\middle|\;\mathtt{arm}_{i}\neq\mathtt{arm}_{*}\right\} forms a partition of \overline{\mathcal{M}}_{*} . For the term \mathbb{P}\left[\mathcal{B}_{i}\right] , we have \displaystyle\mathbb{P}\left[\mathcal{B}_{i}\right] \displaystyle=\mathbb{P}\left[\mathcal{S}_{*}\cap\mathcal{S}_{i}\cap\mathcal{C}_{i}\cap\mathcal{B}_{i}\right]=\mathbb{P}\left[\mathcal{S}_{*}\cap\mathcal{S}_{i}\right]\mathbb{P}\left[\mathcal{C}_{i}\;\middle|\;\mathcal{S}_{*}\cap\mathcal{S}_{i}\right]\mathbb{P}\left[\mathcal{B}_{i}\;\middle|\;\mathcal{S}_{*}\cap\mathcal{S}_{i}\cap\mathcal{C}_{i}\right] \displaystyle\overset{(\spadesuit)}{\leq}\frac{{m-2\choose 2c-2}}{{m\choose 2c}}\cdot\frac{1}{2c-1}\cdot e^{-\frac{\Delta_{i}^{2}L}{2}}\leq\frac{4c}{m^{2}}\cdot e^{-\frac{\Delta_{i}^{2}L}{2}}, where (\spadesuit) applies Lemma 3 . Then we turn to bound \mathbf{E}\left[R_{2}\;\middle|\;\mathcal{B}_{i}\right] for every i such that \mathtt{arm}_{i}\neq\mathtt{arm}_{*} . Since conditioned on \mathcal{B}_{i} , \mathtt{arm}_{\mathtt{king}}\neq\mathtt{arm}_{*} , the regret \mathbf{E}\left[R_{2}\;\middle|\;\mathcal{B}_{i}\right] can be divided into three parts: those contributed by \mathtt{arm}_{\mathtt{king}} , those \mathtt{arm}_{j} with \Delta_{j} close to \Delta_{\mathtt{king}} and those \mathtt{arm}_{j} with \Delta_{j} much larger than \Delta_{\mathtt{king}} . We emphasize that the following inequalities involving conditional expectation \mathbf{E}\left[\cdot\;\middle|\;\mathcal{B}_{i}\right] holds for all outcomes \omega\in\mathcal{B}_{i} (in the underlying probability space). We have \displaystyle\mathbf{E}\left[R_{2}\;\middle|\;\mathcal{B}_{i}\right]\leq\Delta_{\mathtt{king}}\cdot T+\sum_{j\colon\Delta_{j}>0,\Delta_{j}\leq 2\Delta_{\mathtt{king}}}\Delta_{j}\cdot\mathbf{E}\left[L_{2,j}\;\middle|\;\mathcal{B}_{i}\right]+\sum_{j\colon\Delta_{j}>2\Delta_{\mathtt{king}}}\Delta_{j}\cdot\mathbf{E}\left[L_{2,j}\;\middle|\;\mathcal{B}_{i}\right]. (2) For those \mathtt{arm}_{j} with small \Delta_{j} , we have \displaystyle\sum_{j\colon\Delta_{j}>0,\Delta_{j}\leq 2\Delta_{\mathtt{king}}}\Delta_{j}\cdot\mathbf{E}\left[L_{2,j}\;\middle|\;\mathcal{B}_{i}\right]\leq 2\Delta_{\mathtt{king}}\cdot\sum_{j\colon\Delta_{j}\leq 2\Delta_{\mathtt{king}}}\mathbf{E}\left[L_{2,j}\;\middle|\;\mathcal{B}_{i}\right]\leq 2\Delta_{\mathtt{king}}\cdot T. (3) For those \mathtt{arm}_{j} with large \Delta_{j} , we use Lemma 2 and obtain \displaystyle\sum_{j\colon\Delta_{j}>2\Delta_{\mathtt{king}}}\Delta_{j}\cdot\mathbf{E}\left[L_{2,j}\;\middle|\;\mathcal{B}_{i}\right]\leq\sum_{j\colon\Delta_{j}>2\Delta_{\mathtt{king}}}\Delta_{j}\cdot\frac{8\log T}{(\Delta_{j}-\Delta_{\mathtt{king}})^{2}}\leq\sum_{j\colon\Delta_{j}>2\Delta_{\mathtt{king}}}\frac{32\log T}{\Delta_{j}}. (4) Note that at every outcome \omega\in\mathcal{B}_{i} , the random variable \Delta_{\mathtt{king}}(\omega)\leq\Delta_{i} since \mathtt{king} is the best arm in M . Combining ( 2 ), ( 3 ) and ( 4 ), we obtain \displaystyle\mathbf{E}\left[R_{2}\;\middle|\;\mathcal{B}_{i}\right]\leq 3\Delta_{\mathtt{king}}\cdot T+\sum_{j\colon\Delta_{j}>2\Delta_{\mathtt{king}}}\frac{32\log T}{\Delta_{j}}\leq 3\Delta_{i}\cdot T+\sum_{j:\Delta_{j}>0}\frac{32\log T}{\Delta_{j}}. (5) As a result, \displaystyle\sum_{i\colon\mathtt{arm}_{i}\neq\mathtt{arm}_{*}}\mathbb{P}\left[\mathcal{B}_{i}\right]\mathbf{E}\left[R_{2}\;\middle|\;\mathcal{B}_{i}\right] \displaystyle\leq\sum_{i\colon\mathtt{arm}_{i}\neq\mathtt{arm}_{*}}\frac{4c}{m^{2}}\cdot e^{-\frac{\Delta_{i}^{2}L}{2}}\left(3\Delta_{i}\cdot T+\sum_{j:\Delta_{j}>0}\frac{32\log T}{\Delta_{j}}\right) \displaystyle\overset{(\diamondsuit)}{\leq}\left(\frac{2\alpha}{e}\right)^{\frac{\alpha}{\alpha+1}}\cdot\frac{12cn^{\frac{\alpha}{\alpha+1}}}{m^{2}}\displaystyle\sum_{i\colon arm_{i}\neq arm_{*}}\frac{T^{\frac{1}{\alpha+1}}}{\Delta_{i}^{2\alpha-1}}+\frac{128cn}{m^{2}}\sum_{j\colon\Delta_{j}>0}\frac{\log T}{\Delta_{j}} \displaystyle=O\left(\left(\frac{2\alpha}{e}\right)^{\frac{\alpha}{\alpha+1}}\frac{(n-m)T^{\frac{1}{\alpha+1}}}{n^{1+{\frac{1}{\alpha+1}}}}\displaystyle\sum_{i:\Delta_{i}>0}\Delta_{i}^{1-2\alpha}+\sum_{i:\Delta_{i}>0}\frac{\log T}{\Delta_{i}}\right) \displaystyle\overset{(\heartsuit)}{=}O\left(\left(\frac{2\alpha}{e}\right)^{\frac{\alpha}{\alpha+1}}\frac{(n-m)T^{\frac{1}{\alpha+1}}}{n^{1+{\frac{1}{\alpha+1}}}}\displaystyle\sum_{i:\Delta_{i}>0}\Delta_{i}^{1-2\alpha}\right), where ( \diamondsuit ) uses the inequality e^{-x}\leq\frac{\alpha^{\alpha}e^{-\alpha}}{x^{\alpha}} for x>0 , ( \heartsuit ) is because T is sufficiently large and \forall 0<\Delta_{i}<1,\frac{1}{\Delta_{i}}\leq\Delta_{i}^{1-2\alpha} . In conclusion, we have \mathbf{E}\left[R(T)\right]=\mathbf{E}\left[R_{1}\right]+\mathbf{E}\left[R_{2}\right]=O\left(\left(\frac{2\alpha}{e}\right)^{\frac{\alpha}{\alpha+1}}\frac{(n-m)T^{\frac{1}{\alpha+1}}}{n^{1+{\frac{1}{\alpha+1}}}}\displaystyle\sum_{i:\Delta_{i}>0}\Delta_{i}^{1-2\alpha}\right) . ∎ 3.2 Small memory case ( 2\leq m<\frac{2}{3}n ) When m<\frac{2}{3}n , Algorithm 1 is not feasible since the rest n-m arms cannot be read into memory at once. We design Algorithm 2 to deal with this case. Algorithm 2 Single-pass algorithm for MAB when 2\leq m<\frac{2}{3}n Input: Time horizon T , memory size m , number of arms n and a constant \alpha\geq 1 . 1: Let L\leftarrow\left(\frac{2\alpha}{e}\right)^{\frac{\alpha}{\alpha+1}}\cdot\left(\frac{T}{m}\right)^{\frac{1}{\alpha+1}} ; 2: Read the first m-1 arms into memory; 3: Pull each of them L times and calculate their empirical means respectively; 4: for each arriving arm \mathtt{arm}_{i} do 5: Choose an arm \mathtt{arm}_{j} u.a.r. in the memory; 6: Read \mathtt{arm}_{i} into memory; 7: Pull \mathtt{arm}_{i} L times and calculate its empirical mean \widehat{\mu}_{i} ; 8: if \widehat{\mu}_{i}>\widehat{\mu}_{j} then 9: Discard \mathtt{arm}_{j} ; 10: else 11: Discard \mathtt{arm}_{i} ; 12: Run UCB on all arms in the memory until the game ends; \triangleright The Exploitation Phase Algorithm 2 will pull each arm L times before the exploitation phase. Every incoming arm will be compared with a uniformly and randomly chosen arm in the memory. The worse of the two will be discarded to incorporate future new arms. This operation lasts until the end of the stream. Finally, we apply a standard UCB algorithm for arms in the memory until the end. Theorem 5 . Given any \alpha\geq 1 and any input instance, assuming T is sufficiently large, Algorithm 2 uses the memory of m arms with expected regret \mathbf{E}\left[R(T)\right]=O\left(\left(\frac{2\alpha}{e}\right)^{\frac{\alpha}{\alpha+1}}\frac{T^{\frac{1}{\alpha+1}}}{m^{\frac{1}{\alpha+1}}}\displaystyle\sum_{i:\Delta_{i}>0}\Delta_{i}^{1-2\alpha}\right). Proof. We define notations L_{1},L_{2},L_{1,i},L_{2,i},R_{1},R_{2} similar to those in Section 3.1 with the only difference being that L_{1} now counts the number of rounds before the execution of 12 in Algorithm 2 . Denote \mathtt{arm}_{\mathtt{king}} as the best arm in the memory and \mathcal{M}_{i} as the event that \mathtt{arm}_{i} is in the memory during the exploitation phase. Conditioned on the event \overline{\mathcal{M}}_{*} (namely the event that the best arm is not in the memory during the exploitation phase), consider the maximal sequence of arms \ab\{\mathtt{arm}_{s_{i}}\}_{i\in[\ell]} satisfying \mathtt{arm}_{s_{1}}=\mathtt{arm}_{*} and \mathtt{arm}_{s_{i+1}} beats \mathtt{arm}_{s_{i}} for all 1\leq i\leq\ell-1 . By the maximality of the sequence, \mathbb{P}\left[\mathcal{M}_{s_{\ell}}\;\middle|\;\overline{\mathcal{M}}_{*}\right]=1 , which deduces \Delta_{\mathtt{king}}\leq\Delta_{\ell} conditioned on \overline{\mathcal{M}}_{*} . For each i\in[n] , denote by \mathcal{L}_{i} the event that \mathtt{arm}_{i}=\mathtt{arm}_{s_{\ell}} , or equivalently the event that \mathtt{arm}_{i} is the last one in the chain of elimination of \mathtt{arm}_{*} . Consider the time at which the \mathtt{arm}_{i} is about to join the chain of elimination of \mathtt{arm}_{*} . There are two cases: • the \mathtt{arm}_{*} is the incoming arm and at 5 , the algorithm picks \mathtt{arm}_{i} ; • or the \mathtt{arm}_{i} is the incoming arm and at 5 , the algorithm picks an arm already in the chain. Moreover, in both cases, we must have that \widehat{\mu}_{i}>\widehat{\mu}_{*} in order for \mathcal{L}_{i} to happen. As a result, we have \mathbb{P}\left[\mathcal{L}_{i}\right]\leq\frac{1}{m-1}\cdot e^{-\frac{\Delta_{i}^{2}L}{2}}. We first bound \mathbf{E}\left[R_{1}\right] , \displaystyle\mathbf{E}\left[R_{1}\right] \displaystyle=\sum_{i:\Delta_{i}>0}\Delta_{i}\cdot L=\sum_{i:\Delta_{i}>0}\Delta_{i}\cdot\left(\frac{2\alpha}{e}\right)^{\frac{\alpha}{\alpha+1}}\cdot\left(\frac{T}{m}\right)^{\frac{1}{\alpha+1}}=O\left(\left(\frac{2\alpha}{e}\right)^{\frac{\alpha}{\alpha+1}}\left(\frac{T}{m}\right)^{\frac{1}{\alpha+1}}\sum_{i:\Delta_{i}>0}\Delta_{i}\right). Then we also decompose \mathbf{E}\left[R_{2}\right] based on whether \mathcal{M}_{*} happens. \displaystyle\mathbf{E}\left[R_{2}\right] \displaystyle=\mathbb{P}\left[\mathcal{M}_{*}\right]\mathbf{E}\left[R_{2}\;\middle|\;\mathcal{M}_{*}\right]+\mathbb{P}\left[\overline{\mathcal{M}}_{*}\right]\mathbf{E}\left[R_{2}\;\middle|\;\overline{\mathcal{M}}_{*}\right] \displaystyle\leq\mathbf{E}\left[R_{2}\;\middle|\;\mathcal{M}_{*}\right]+\mathbb{P}\left[\overline{\mathcal{M}}_{*}\right]\mathbf{E}\left[R_{2}\;\middle|\;\overline{\mathcal{M}}_{*}\right] \displaystyle\overset{(\clubsuit)}{=}\mathbf{E}\left[R_{2}\;\middle|\;M_{*}\right]+\displaystyle\sum_{i\colon\mathtt{arm}_{i}\neq\mathtt{arm}_{*}}\mathbb{P}\left[\mathcal{L}_{i}\right]\mathbf{E}\left[R_{2}\;\middle|\;\mathcal{L}_{i}\right] \displaystyle\leq\sum_{i:\Delta_{i}>0}\frac{8\log T}{\Delta_{i}}+\frac{1}{m-1}\displaystyle\sum_{i\colon\mathtt{arm}_{i}\neq\mathtt{arm}_{*}}e^{-\frac{\Delta_{i}^{2}L}{2}}\mathbf{E}\left[R_{2}\;\middle|\;\mathcal{L}_{i}\right], (6) where (\clubsuit) holds since \left\{\mathcal{L}_{i}\;\middle|\;\mathtt{arm}_{i}\neq\mathtt{arm}_{*}\right\} forms a partition of \overline{\mathcal{M}}_{*} . Conditioned on \mathcal{L}_{i} , \Delta_{\mathtt{king}}\leq\Delta_{i} , thus we have following holds: \displaystyle\mathbf{E}\left[R_{2}\;\middle|\;\mathcal{L}_{i}\right] \displaystyle\leq\Delta_{\mathtt{king}}\cdot T+\sum_{j\colon\Delta_{j}>0,\Delta_{j}\leq 2\Delta_{\mathtt{king}}}\Delta_{j}\cdot\mathbf{E}\left[L_{2,j}\;\middle|\;\mathcal{L}_{i}\right]+\sum_{j\colon\Delta_{j}>2\Delta_{\mathtt{king}}}\Delta_{j}\cdot\mathbf{E}\left[L_{2,j}\;\middle|\;\mathcal{L}_{i}\right] \displaystyle\leq 3\Delta_{\mathtt{king}}\cdot T+\sum_{j\colon\Delta_{j}>2\Delta_{\mathtt{king}}}\Delta_{j}\cdot\frac{8\log T}{(\Delta_{j}-\Delta_{\mathtt{king}})^{2}} \displaystyle\leq 3\Delta_{i}\cdot T+\sum_{j:\Delta_{j}>0}\frac{32\log T}{\Delta_{j}}. Therefore, \displaystyle\mathbf{E}\left[R_{2}\right] \displaystyle\leq\sum_{i:\Delta_{i}>0}\frac{8\log T}{\Delta_{i}}+\frac{1}{m-1}\displaystyle\sum_{i\colon\mathtt{arm}_{i}\neq\mathtt{arm}_{*}}e^{-\frac{\Delta_{i}^{2}L}{2}}\cdot 3\Delta_{i}T+\frac{1}{m-1}\displaystyle\sum_{i\colon\mathtt{arm}_{i}\neq\mathtt{arm}_{*}}\sum_{j:\Delta_{j}>0}\frac{32\log T}{\Delta_{j}} \displaystyle\overset{(\diamondsuit)}{\leq}\sum_{i:\Delta_{i}>0}\frac{8\log T}{\Delta_{i}}+\left(\frac{2\alpha}{e}\right)^{\frac{\alpha}{\alpha+1}}\cdot\frac{3m^{\frac{\alpha}{\alpha+1}}T^{\frac{1}{\alpha+1}}}{m-1}\displaystyle\sum_{i\colon arm_{i}\neq arm_{*}}\Delta_{i}^{1-2\alpha}+\frac{32n}{m-1}\sum_{j\colon\Delta_{j}>0}\frac{\log T}{\Delta_{j}} \displaystyle=O\left(\left(\frac{2\alpha}{e}\right)^{\frac{\alpha}{\alpha+1}}\frac{T^{\frac{1}{\alpha+1}}}{m^{\frac{1}{\alpha+1}}}\displaystyle\sum_{i:\Delta_{i}>0}\Delta_{i}^{1-2\alpha}+\frac{n}{m}\sum_{i:\Delta_{i}>0}\frac{\log T}{\Delta_{i}}\right) \displaystyle\overset{(\spadesuit)}{=}O\left(\left(\frac{2\alpha}{e}\right)^{\frac{\alpha}{\alpha+1}}\frac{T^{\frac{1}{\alpha+1}}}{m^{{\frac{1}{\alpha+1}}}}\displaystyle\sum_{i:\Delta_{i}>0}\Delta_{i}^{1-2\alpha}\right), where ( \diamondsuit ) uses the inequality e^{-x}\leq\frac{\alpha^{\alpha}e^{-\alpha}}{x^{\alpha}} for x>0 and ( \spadesuit ) is because T is sufficiently large and \forall 0<\Delta_{i}<1,\frac{1}{\Delta_{i}}\leq\Delta_{i}^{1-2\alpha} . In conclusion, we have \mathbf{E}\left[R(T)\right]=\mathbf{E}\left[R_{1}\right]+\mathbf{E}\left[R_{2}\right]=O\left(\left(\frac{2\alpha}{e}\right)^{\frac{\alpha}{\alpha+1}}\frac{T^{\frac{1}{\alpha+1}}}{m^{\frac{1}{\alpha+1}}}\displaystyle\sum_{i:\Delta_{i}>0}\Delta_{i}^{1-2\alpha}\right) . ∎ 4 Gap-Dependent Regret Lower Bounds In this section, we will prove the regret lower bounds for every 2\leq m0}\Delta_{i}^{1-2\alpha}\right) . By picking k=\frac{3}{2}m when m<\frac{2}{3}n and k=n-1 otherwise, we obtain Corollary 7 . Given any \alpha\geq 1 , for any algorithm \mathcal{A} using 2\leq m0}\Delta_{i}^{1-2\alpha}\right) when m<\frac{2}{3}n and \Omega\left(16^{-\alpha}\cdot\frac{(n-m)T^{\frac{1}{\alpha+1}}}{k^{1+\frac{1}{\alpha+1}}}\sum_{i:\Delta_{i}>0}\Delta_{i}^{1-2\alpha}\right) when m\geq\frac{2}{3}n . 4.1 The construction of the hard instances In this section, we provide the family of hard instances and prove in the next section that any algorithm exhibits large regret on at least one of the instances in the family. Given a constant \alpha\geq 1 , let T be sufficiently large and \varepsilon=\frac{1}{4}\cdot\left(\frac{k}{T}\right)^{\frac{1}{2+2\alpha}} . For every m\leq k0}\Delta_{i}^{1-2\alpha} , since \alpha\geq 1 , then it holds that \displaystyle\mathbf{E}_{\nu_{1}}\left[R(T)\right] \displaystyle\leq\frac{2}{16^{\alpha+1}}\cdot\frac{(k-m+1)T^{\frac{1}{\alpha+1}}}{k^{1+\frac{1}{\alpha+1}}}\left((k-1)\varepsilon^{1-2\alpha}+(n-k)(n\varepsilon)^{1-2\alpha}\right) \displaystyle\leq\frac{2}{16^{\alpha+1}}\cdot\frac{(k-m+1)T^{\frac{1}{\alpha+1}}}{k^{1+\frac{1}{\alpha+1}}}\cdot k\varepsilon^{1-2\alpha}=f(k,m)\cdot T^{\frac{1}{\alpha+1}}\cdot\varepsilon^{1-2\alpha}, and for any 2\leq i\leq k , \displaystyle\mathbf{E}_{\nu_{i}}\left[R(T))\right] \displaystyle\leq\frac{2}{16^{\alpha+1}}\cdot\frac{(k-m+1)T^{\frac{1}{\alpha+1}}}{k^{1+\frac{1}{\alpha+1}}}\left(\varepsilon^{1-2\alpha}+(k-2)(2\varepsilon)^{1-2\alpha}+(n-k)((n+1)\varepsilon)^{1-2\alpha}\right) \displaystyle\leq\frac{2}{16^{\alpha+1}}\cdot\frac{(k-m+1)T^{\frac{1}{\alpha+1}}}{k^{1+\frac{1}{\alpha+1}}}\cdot k\varepsilon^{1-2\alpha}=f(k,m)\cdot T^{\frac{1}{\alpha+1}}\cdot\varepsilon^{1-2\alpha}, Similarly for any \nu^{\prime}\in{I}^{\prime} and sufficiently large T , \displaystyle\mathbf{E}_{\nu^{\prime}}\left[R(T)\right] \displaystyle\leq\frac{2}{16^{\alpha+1}}\cdot\frac{(k-m+1)T^{\frac{1}{\alpha+1}}}{k^{1+\frac{1}{\alpha+1}}}\cdot k\left(\frac{1}{2}-(n+1)\varepsilon\right)^{1-2\alpha} \displaystyle\leq\frac{2}{16^{\alpha+1}}\cdot\frac{(k-m+1)T^{\frac{1}{\alpha+1}}}{k^{\frac{1}{\alpha+1}}}\cdot\left(\frac{1}{4}\right)^{1-2\alpha}=\frac{1}{32}\cdot f(k,m)\cdot T^{\frac{1}{\alpha+1}}. The above discussions are summarized below. Lemma 9 . If there exists an algorithm \mathcal{A} with regret at most \frac{2}{16^{\alpha+1}}\cdot\frac{(k-m+1)T^{\frac{1}{\alpha+1}}}{k^{1+\frac{1}{\alpha+1}}}\sum_{i\colon\Delta_{i}>0}\Delta_{i}^{1-2\alpha} on each instance in {I}\cup{I}^{\prime} , then for every \nu\in{I} , \nu^{\prime}\in{I}^{\prime} , \mathbf{E}_{\nu}\left[R(T)\right]\leq f(k,m)T^{\frac{1}{\alpha+1}}\varepsilon^{1-2\alpha},\;\mathbf{E}_{\nu^{\prime}}\left[R(T)\right]\leq\frac{1}{32}\cdot f(k,m)\cdot T^{\frac{1}{\alpha+1}} (7) where the randomness in the expectation is from both the (possible) randomness of \mathcal{A} and the randomness of the instance. Provided the upper bound on the regret, we now show that L_{1} cannot be too large. Lemma 10 . If there exists an algorithm \mathcal{A} satisfying eq. 7 , then for every i\in[k] , \mathbf{E}_{\nu_{i}}\left[L_{1}\right]\leq\frac{1}{8}f(k,m)T^{\frac{1}{\alpha+1}}. Proof. Note that the random variable L_{1} only depends on the performance of the first k arms in the stream, and the first k arms of \nu_{i} are the same as that of \nu_{i}^{\prime} . Therefore \mathbf{E}_{\nu_{i}^{\prime}}\left[L_{1}\right]=\mathbf{E}_{\nu_{i}}\left[L_{1}\right] . Each pull of the first k arms in \nu_{i}^{\prime} incurs a regret at least \frac{1}{2}-(n+1)\varepsilon . So we have \mathbf{E}_{\nu_{i}^{\prime}}\left[L_{1}\right]\cdot\left(\frac{1}{2}-(n+1)\varepsilon\right)\leq\mathbf{E}_{\nu_{i}^{\prime}}\left[R\right]\leq\frac{1}{32}\cdot f(k,m)\cdot T^{\frac{1}{\alpha+1}}. This implies that \mathbf{E}_{\nu_{i}}\left[L_{1}\right]=\mathbf{E}_{\nu_{i}^{\prime}}\left[L_{1}\right]\leq\frac{\frac{1}{32}f(k,m)T^{\frac{1}{\alpha+1}}}{(1/2-(n+1)\varepsilon)}\leq\frac{1}{8}\cdot f(k,m)\cdot T^{\frac{1}{\alpha+1}}, for sufficiently large T . ∎ On the other hand, we prove the following lemma, justifying that for some \nu_{i} , \mathbf{E}_{\nu_{i}}\left[L_{1}\right] cannot be small provided the algorithm has small regret. Lemma 11 . If there exists an algorithm \mathcal{A} satisfying eq. 7 , then, \mathbf{E}_{\nu_{1}}\left[L_{1}\right]>8\cdot f(k,m)\cdot T^{\frac{1}{\alpha+1}}. Clearly Theorem 6 holds by combining Lemma 9 , Lemma 10 and Lemma 11 . The remaining part of the section devotes to a proof of Lemma 11 . For every i\in[k] , we let \tau_{i} be the event that “the arm i is not in the memory at the beginning of stage two”. We now show that for every \nu_{i}\in{I} , provided the algorithm \mathcal{A} has small regret, \mathbb{P}_{\nu_{i}}\left[\tau_{i}\right] is small. Lemma 12 . For every i\in[k] and sufficiently large T , it holds that \mathbb{P}_{\nu_{i}}\left[\tau_{i}\right]\leq\frac{1}{2}\cdot\frac{k-m+1}{k} . Proof. For every i\in[k] , it follows from Lemma 10 that \mathbf{E}_{\nu_{i}}\left[L_{2}\right]=T-\mathbf{E}_{\nu_{i}}\left[L_{1}\right]\geq T-\frac{1}{8}f(k,m)T^{\frac{1}{\alpha+1}}\geq\frac{T}{4}. Note that once \tau_{i} happens on \nu_{i} , each pull in stage two incurs a regret at least \varepsilon . Therefore, for every i\in[k] , \displaystyle\mathbf{E}_{\nu_{i}}\left[R\right] \displaystyle\geq\mathbb{P}_{\nu_{i}}\left[\tau_{i}\right]\mathbf{E}_{\nu_{i}}\left[R_{2}\;\middle|\;\tau_{i}\right]\geq\mathbb{P}_{\nu_{i}}\left[\tau_{i}\right]\cdot\frac{T}{4}\cdot\varepsilon. It then follows from eq. 7 that for sufficiently large T , \mathbb{P}_{\nu_{i}}\left[\tau_{i}\right]\leq 4f(k,m)T^{-\frac{\alpha}{\alpha+1}}\varepsilon^{-2\alpha}=\frac{1}{2}\cdot\frac{k-m+1}{k} . ∎ Now we claim that the algorithm \mathcal{A} can be used to solve the best arm retention problem with instances in {I}_{0} that retain m-1 arms out of k arms: Given an instance for BAR in {I}_{0} , we put them in a stream and call the algorithm \mathcal{A} . At the end of stage one, we output all the arms in the memory. Note that the memory is m-1 instead of m here since we do not count the one retaining the (k+1) -th arm in the stream. Clearly, the algorithm above is a (\delta,\varepsilon) -PAC algorithm with \delta=\mathbb{P}_{\nu_{i}}\left[\tau_{i}\right]\leq\frac{1}{2}\cdot\frac{(k-m+1)}{k} on these instances. On the other hand, by picking \beta=\frac{1}{2} , it follows from Lemma 8 that \displaystyle\mathbf{E}_{\nu_{1}}\left[L_{1}\right] \displaystyle\geq\frac{k-m+1-\delta}{64\varepsilon^{2}}\log\frac{k-m+1-\delta}{(k-1)\delta}\geq\frac{(k-m+1)-\frac{(k-m+1)}{2k}}{64\varepsilon^{2}}\log\frac{(k-m+1)-\frac{(k-m+1)}{2k}}{(k-1)\cdot\frac{(k-m+1)}{2k}} \displaystyle=\left(\frac{2k-1}{k}\log\frac{2k-1}{k-1}\cdot 16^{\alpha}\right)f(k,m)T^{\frac{1}{\alpha+1}}>8\cdot f(k,m)\cdot T^{\frac{1}{\alpha+1}}. Appendix A Omitted Proofs in Section 3 A.1 Technical preliminaries Lemma 13 (Hoeffding’s inequality, [ MU17 ] ) . Let X_{1},\cdots,X_{n} be n independent random variables defined on a common probability space and taking values in [a,b] . Define X:=\sum_{i=1}^{n}X_{i} , then for any s>0 , \mathbb{P}\left[X-\mathbf{E}\left[X\right]\geq s\right]\leq\exp\left(-\frac{2s^{2}}{n(b-a)^{2}}\right). Applying Hoeffding’s inequality, we could get the following lemma: Lemma 14 . Let \mathtt{arm}_{1} and \mathtt{arm}_{2} be two different arms with reward means of \mu and \mu+\Delta,\Delta>0 . Suppose we sample each arm L times and obtain empirical mean of \widehat{\mu}_{1} and \widehat{\mu}_{2} , then \mathbb{P}\left[\widehat{\mu}_{1}\geq\widehat{\mu}_{2}\right]\leq e^{-\frac{L\Delta^{2}}{2}}. Proof. Denote the reward of pulling \mathtt{arm}_{1} and \mathtt{arm}_{2} in the i -th round is X_{i} and Y_{i} , then \displaystyle\mathbb{P}\left[\widehat{\mu}_{1}\geq\widehat{\mu}_{2}\right] \displaystyle=\mathbb{P}\left[\frac{1}{L}\sum_{i=1}^{L}X_{i}\geq\frac{1}{L}\sum_{i=1}^{L}Y_{i}\right] \displaystyle=\mathbb{P}\left[\sum_{i=1}^{L}\left(X_{i}-Y_{i}\right)-(-L\Delta)\geq L\Delta\right] ( Lemma 13 ) \displaystyle\leq\exp\left(-\frac{2(L\Delta)^{2}}{4L}\right)=e^{-\frac{L\Delta^{2}}{2}}. ∎ A.2 The Upper Confidence Bound algorithm We provide the description of the UCB algorithm used in Algorithm 1 and Algorithm 2 here. For more detailed information, please refer to the work of [ LS20 ] . Given the parameter \delta , denote T_{i}(t-1) as the number of times pulling \mathtt{arm}_{i} before round t , and \widehat{\mu}_{i}(t-1) is the empirical mean of \mathtt{arm}_{i} before round t . We define the upper confidence bound for \mathtt{arm}_{i} in round t as \mathtt{UCB}_{i}(t-1,\delta)=\begin{cases}\infty,\quad&T_{i}(t-1)=0\\ \widehat{\mu}_{i}(t-1)+\sqrt{\frac{2\log\frac{1}{\delta}}{T_{i}(t-1)}},\quad&otherwise\\ \end{cases} Algorithm 3 UCB( \delta ) Input: Time horizon T , a set of n arms, probability \delta . 1: for t=1,\cdots,T do 2: Choose A_{t}=\mathop{\arg\max}_{i\in[n]}\mathtt{UCB}_{i}(t-1,\delta) and pull it once; 3: Observe its reward and update all arms’ upper confidence bounds; Appendix B Omitted Proofs in Section 4 B.1 Technique preliminaries The Kullback-Leibler (KL) divergence between \mathtt{Ber}\left(x\right) and \mathtt{Ber}\left(y\right) is defined as d(x,y):=x\log\left(\frac{x}{y}\right)+(1-x)\log\left(\frac{1-x}{1-y}\right), Here we give some propositions of the KL-divergence. Proposition 15 . Given \frac{1}{2}\leq\mu\leq\frac{5}{8} , 0<\zeta\leq\frac{1}{8} , then d(\mu,\mu+\zeta)\leq 4\zeta^{2} . Proof. Applying Taylor expansion, there exist \eta_{1}\in\left(0,\frac{\zeta}{\mu}\right),\eta_{2}\in\left(-\frac{\zeta}{1-\mu},0\right) such that \displaystyle d(\mu,\mu+\zeta) \displaystyle=\mu\cdot\log\frac{\mu}{\mu+\zeta}+(1-\mu)\cdot\log\frac{1-\mu}{1-\mu-\zeta} \displaystyle=-\mu\left(\frac{\zeta}{\mu}-\frac{1}{2}\cdot\frac{\zeta^{2}}{\mu^{2}}+\frac{1}{3(1+\eta_{1})^{3}}\cdot\frac{\zeta^{3}}{\mu^{3}}\right) \displaystyle-(1-\mu)(-\frac{\zeta}{1-\mu}-\frac{1}{2}\frac{\zeta^{2}}{(1-\mu)^{2}}-\frac{1}{3(1+\eta_{2})^{3}}\cdot\frac{\zeta^{3}}{(1-\mu)^{3}}) \displaystyle\leq\zeta^{2}\left(\frac{1}{2\mu}+\frac{1}{2(1-\mu)}\right)+\frac{\zeta^{3}}{3}\left(\frac{1-\mu}{(1-\mu-\zeta)^{3}}-\frac{\mu}{(\mu+\zeta)^{3}}\right) \displaystyle\leq\frac{7}{3}\zeta^{2}+\frac{\zeta^{2}}{24}\cdot\frac{832}{27}\leq 4\zeta^{2}. ∎ Proposition 16 . d(x,y) is convex for x (or y ) when y (or x ) is fixed. Proof. \frac{\mathinner{\partial}\mathchoice{\mskip-3.0mu}{\mskip-3.0mu}{}{}{}^{2}d(x,y)}{\mathinner{\partial}\mathchoice{\mskip-3.0mu}{\mskip-3.0mu}{}{}{}x^{2}}=\frac{\mathinner{\partial}\mathchoice{\mskip-3.0mu}{\mskip-3.0mu}{}{}{}\log\left(\frac{x(1-y)}{(1-x)y}\right)}{\mathinner{\partial}\mathchoice{\mskip-3.0mu}{\mskip-3.0mu}{}{}{}x}=\frac{1}{x}+\frac{1}{1-x}\geq 0. \frac{\mathinner{\partial}\mathchoice{\mskip-3.0mu}{\mskip-3.0mu}{}{}{}^{2}d(x,y)}{\mathinner{\partial}\mathchoice{\mskip-3.0mu}{\mskip-3.0mu}{}{}{}y^{2}}=\frac{\mathinner{\partial}\mathchoice{\mskip-3.0mu}{\mskip-3.0mu}{}{}{}\left(-\frac{x}{y}+\frac{1-x}{1-y}\right)}{\mathinner{\partial}\mathchoice{\mskip-3.0mu}{\mskip-3.0mu}{}{}{}y}=\frac{x}{y^{2}}+\frac{1-x}{(1-y)^{2}}\geq 0. ∎ Proposition 17 . \forall 0\leq p\leq x\leq y\leq q\leq 1 , d(p,q)\geq d(x,y). Proof. First we have \frac{\mathinner{\partial}\mathchoice{\mskip-3.0mu}{\mskip-3.0mu}{}{}{}d(x,y)}{\mathinner{\partial}\mathchoice{\mskip-3.0mu}{\mskip-3.0mu}{}{}{}x}\big|_{x=y}=0 . By Proposition 16 , d(\cdot,y) achieves the minimum when x=y . So d(p,y)\geq d(x,y) . Similarly d(x,\cdot) achieves the minimum when y=x . Therefore d(p,q)\geq d(p,y)\geq d(x,y) . ∎ Lemma 18 . \forall x_{1},x_{2},\cdots,x_{N}\in[0,1] with average a:=\frac{\sum_{i=1}^{N}x_{i}}{N}0. 2. \log\left(1+x\right)\geq\frac{x(2+x)}{2(1+x)},\forall-1\frac{\alpha}{1-\alpha} , then \displaystyle d\left(\frac{m-(1-\delta)}{k-1},1-\delta\right) \displaystyle=d\left(1-\frac{m-(1-\delta)}{k-1},\delta\right)=d\left(\frac{k-m-\delta}{k-1},\delta\right) \displaystyle=d\left(\frac{k-m}{k}(1+\frac{\alpha}{k-1}),\frac{k-m}{k}(1-\alpha)\right) ( Lemma 19 ) \displaystyle\geq\frac{r}{2+2r}\cdot\frac{k-m-\delta}{k-1}\log\frac{k-m-\delta}{(k-1)\delta} \displaystyle\geq\frac{\frac{\alpha}{1-\alpha}}{2+\frac{2\alpha}{1-\alpha}}\cdot\frac{k-m-\delta}{k-1}\log\frac{k-m-\delta}{(k-1)\delta} \displaystyle\geq\frac{\beta}{2}\cdot\frac{k-m-\delta}{k-1}\log\frac{k-m-\delta}{(k-1)\delta}, Bring this item back and we could get \mathbf{E}_{\rho_{1}}\left[T\right]\geq\frac{\beta}{32}\cdot\frac{k-m-\delta}{\varepsilon^{2}}\log{\frac{k-m-\delta}{(k-1)\delta}}.