Multi-Armed Bandits with Bounded Arm-Memory: Near-Optimal Guarantees for Best-Arm Identification and Regret Minimization

Abstract:
We study the Stochastic Multi-armed Bandit problem under bounded arm-memory. In this setting, the arms arrive in a stream, and the number of arms that can be stored in the memory at any time, is bounded. The decision-maker can only pull arms that are present in the memory. We address the problem from the perspective of two standard objectives: 1) regret minimization, and 2) best-arm identification. For regret minimization, we settle an important open question by showing an almost tight guarantee. We show Ω(T ) cumulative regret in expectation for single-pass algorithms for arm-memory size of (n− 1), where n is the number of arms. For best-arm identification, we provide an (ε, δ)-PAC algorithm with arm-memory size of O(log∗ n) and O( n ε2 · log( 1 δ )) optimal sample complexity.

text: 1 δ )) optimal sample complexity.

heading: 1 Introduction
text: The Stochastic Multi-armed Bandit (MAB) problem is a classical framework used to capture decisionmaking in uncertain environments. In this model, a decision-maker is faced with n choices (called arms) and has to sequentially choose one of the n arms (referred to as pulling an arm). Based on the pulled arm, the decision-maker gets a reward drawn from a corresponding reward distribution unknown to the decision-maker. Starting with the seminal work of Robbins [26], MAB has been extensively studied with one of the following two goals: regret minimization and best-arm identification. See, e.g. [7] for a textbook treatment of the area. In addition to being theoretically interesting, MAB also finds numerous practical applications in diverse areas, including online advertising [31], crowd-sourcing [32], and clinical trials [9]. Hence, the study of MAB and its variants is of paramount interest in multiple fields, including online learning and reinforcement learning.
In many applications of the MAB problem, the number of arms (set of advertisements, crowd-workers, etc.) could be huge. Thus, the MAB problem with a large set of arms has received significant attention in recent years. Starting with the formative work of Berry et al. [6] and Herschkorn et al. [16] which studied the MAB problem with infinitely many arms, to the more recent work of Kleinberg et al. [20] which studies the MAB problem where the set of arms form a metric space, this variant has remained an active and prominent area of research. Large number of arms may enforce a constraint that the algorithm may not be able to store all the arms in the memory simultaneously. Additionally, as is common in these applications, the arms could arrive online, i.e., the algorithm may not have access to the entire set of arms at the beginning.
The streaming model, first formalized in the pioneering work of Alon et al. [3], has been developed to handle data streams where a huge amount of data arrives online and an algorithm has access
∗A part of this work was done when the author was an undergraduate summer intern at IISc, Bangalore.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
to only a limited amount of memory. We refer the readers to [23, 2] for a detailed survey of streaming algorithms. With the ever-increasing amount of data available to any machine learning (ML) algorithm, several salient areas of ML are being studied under streaming constraints; e.g., active learning [35, 29], lifelong learning [33], and identifying correlations in multivariate data [11] (see the recent survey by Gomes et al. [15] for further discussions).
In this work, we study the classical stochastic MAB problem under streaming constraints. This model has recently been studied in [27, 21, 4]. In particular, we study a setting where we are given a set of n arms arriving one-by-one, and an algorithm can store only a fixed number of arms m < n in the memory. The set of arms stored in the memory is known as arm-memory and m denotes the upper bound on the number of arms that can be stored in the memory at any time step. In this model, at any time step an arm not in the current arm-memory can not be pulled. Further, for any arm currently not in the arm-memory, we assume we do not know anything about the reward statistics corresponding to that arm until that arm is read into arm-memory and subsequently pulled. Note that the classical MAB algorithms such as UCB1 [5] and Thompson Sampling [30] for regret minimization, and Median-Elimination [13] for best-arm identification are not suited for this streaming setting as they require all arms to be present in the arm-memory at the start of the algorithm. Our goal is to study the interplay between arm-memory size vs. expected regret and arm-memory size vs. sample complexity, respectively.
An algorithm for our setting works as follows: at any time step t, the algorithm can only pull an arm that is currently in arm-memory and update its reward statistics. Then, the algorithm may choose to discard some of the arms that are currently in the arm-memory and read new arms into the arm-memory before proceeding to the next time-step to pull an arm from the arm-memory. In streaming terminology, algorithms that can not read back an arm into the arm-memory that was previously discarded from the arm-memory, are called single-pass or one-pass algorithms. On the other hand, algorithms that are allowed to read back an arm into the arm-memory that was previously discarded from the arm-memory, are called multi-pass algorithms. We note that our algorithms are designed for the more challenging single-pass setting, which has also been the focus of other prominent areas in machine learning, for example, Rai et al. [25] focus on designing one-pass SVMs when the data arrives in a stream, whereas Carvalho and Cohen [8] design single-pass algorithms for online learning.

heading: 1.1 Our Contribution
text: We study MAB under bounded arm-memory, where n arms arrive in a stream and at most m < n arms can be stored in the arm-memory at any time. We study the trade-off between arm-memory size vs. expected regret, and arm-memory size vs. sample complexity.
Regret minimization: Our first result, in Section 3, settles an open question stated in both [21] and [27] pertaining to the lower bound on the expected cumulative regret in this model. Using information-theoretic machinery related to KL-divergence, we show that any single-pass algorithm in this model will incur an expected regret of Ω ( n1/3 · T 2/3/m7/3 ) . Interestingly, this result holds for any m < n, which shows that even if the algorithm is allowed to store n− 1 arms in the arm-memory at any time, we cannot hope to obtain a better regret guarantee in terms of T . This lower bound almost matches with the Õ(n1/3T 2/3) bound on the expected cumulative regret, obtained by the standard uniform-exploration algorithm where we store m = 2 arms. We note here that the uniformexploration algorithm with m = 2 can be trivially extended to an algorithm that stores m > 2 arms in the memory and achieves a regret guarantee that matches the lower bound by storing the 2 arms required by the uniform-exploration algorithm and filling the remaining m− 2 sized arm-memory with arbitrary arms that would have otherwise been discarded. Since this is already optimal for the single-pass setting, we cannot hope to get a better regret guarantee in terms of T , even if we store n− 1 arms in the memory. This shows an interesting dichotomy between m = n− 1 and m = n, as one can obtain expected cumulative regret of Õ (√ nT ) by standard UCB1 algorithm [5], where we are allowed to store n arms. Our lower bound holds even when the arms arrive in a uniformly random sequence.
Best-arm identification: In Section 4, we propose an (ε, δ)-PAC streaming algorithm that takes r as input and stores r + 1 arms in the arm-memory at any time and has sample complexity O( nε2 ·
(ilog(r)(n) + ln( 1δ ))) 2. In particular, when r = log∗ n, our algorithm achieves the optimal worstcase sample complexity O ( n ε2 log( 1 δ ) ) for any best-arm identification algorithm [13].
This problem was also studied in recent STOC’20 paper by Assadi and Wang [4] where they proposed an (ε, δ)-PAC algorithm with optimal sample complexity and O(log∗ n) arm-memory size. However, we show that due to an error in their analysis, their claim is incorrect and their algorithm is not (ε, δ)-PAC. In Appendix E, we construct a family of input instances for which their algorithm will output a non-ε-best arm with probability significantly larger than δ. In Section 4, we show that the special case of our algorithm (when r = log∗ n) indeed provides the guarantee claimed in [4].

heading: 1.2 Related Work
text: In one of the earliest works on MAB with bounded arm-memory, Herschkorn et al. [16] study the infinite-armed MAB problem where only a single arm is stored in the arm-memory at any time step and an arm that is once discarded from the arm-memory cannot be recalled. On the other hand, Cover [10] studied a different variant of bounded memory where the algorithm can remember the rewards of only a finite number of samples for each arm in a two-armed bandit model. The work of Lu and Lu [22] also studies this variant of bounded memory in the learning from experts setting, where the constraint is on the number of time steps for which the rewards can be stored by the algorithm and not on the number of arms.
More recently, Kalvit and Zeevi [18] studied the infinite-armed bandit problem where each arm is associated with a type, and the number of types is finite. An algorithm knows the set of types but not the exact type of each arm. For this problem, they propose an algorithm that samples a finite number of arms and has O(log T ) expected cumulative regret. Further, de Heide et al. [12] also study the infinite-armed bandit problem where there could be multiple optimal arms. They propose an algorithm and prove that it achieves O(log T ) expected regret by sampling O(log T ) number of arms. In our work, we focus on the finite-armed MAB problem with bounded arm-memory. Recently, the MAB problem where arms arrive in a stream and arm-memory is bounded, has been studied in both regret minimization and best-arm identification frameworks.
For the regret minimization problem in the stochastic MAB setting, Peköz [24] showed that when m = 1, a single-pass algorithm can have linear regret unless the reward distributions of arms satisfy some additional conditions. Liau et al. [21] and RoyChaudhuri and Kalyanakrishnan [27] study the stochastic MAB problem with bounded arm-memory with the goal of minimizing the expected cumulative regret over T time steps. The algorithms in both these works are multi-pass algorithms whereas our work focusses on single-pass algorithms. Liau et al. [21] propose an upper-confidence bound based algorithm with O(1) arm-memory size, which achieves an expected cumulative regret bound of O (∑ i 6=i∗ log( ∆i ∆ ) log T ∆i ) , which is within log(∆i∆ ) factor of the UCB1 regret bound [5]. Here ∆ is the gap parameter, i.e., the difference in the expected rewards of the best and the second-best arms, and ∆i is the difference in the expected rewards of the best arm and the i’th arm. However, they do not provide a worst-case regret bound for their algorithm, and hence, depending on the instance the regret of this algorithm may be very high. More precisely, if say ∆i is 1/T 2/3, then the proven regret bound implies O(T 2/3) expected cumulative regret. RoyChaudhuri and Kalyanakrishnan [27] propose an algorithmic framework, which is given m as input and uses a MAB algorithm as a black-box. When the MAB algorithm used is UCB1, their algorithm achieves an expected regret of O(nm+ n3/2m √ T log(T/nm)) using Ω(log T ) passes. The recent work of Xu and Zhao [34] also studies the regret minimization problem with bounded arm-memory constraints. However, they consider the setting with adversarial rewards and is different from the stochastic MAB setting studied in our paper.
Recently, Assadi and Wang [4] studied the best-arm identification variant of this problem. First, they propose an algorithm for the best-coin identification problem (equivalent to MAB with Bernoulli reward distributions), which keeps exactly one extra coin in the memory at any time and has optimal sample complexity. They further extend their algorithm to the top-k coins identification problem, which stores k coins in the memory and has optimal sample complexity. Crucially though, both algorithms assume that the gap parameter ∆ is known. Throughout our work, we deal with the case when ∆ is not known to the algorithm. Falahatgar et al. [14] also study the best-arm identification
2Here ilog(r) is iterated logarithm of order r (see Section 1.3).
problem with bounded arm-memory and provide an algorithm with O(1) arm-memory size. However, they only provide a high probability guarantee on the sample complexity while additionally assuming that the arms arrive in a uniformly random sequence. Note that unlike [14], the sample complexity of our algorithm is independent of the rewards observed during the sampling, and we do not require the assumption that the arms need to arrive in a uniformly random sequence. In a recent independent work, Jin et al. [17] proposed an ε-top-k arms identification algorithm with optimal sample complexity and arm-memory size of one. They also propose an algorithm that identifies the best-arm with high probability using arm-memory size equal to one, having optimal instance-dependent sample complexity, and using instance-dependent constant number of passes. We would like to note that their work provides high probability bounds on the sample complexity, whereas our work provides worst-case bounds on the same quantity.

heading: 1.3 Notation
text: Let [k] (where k ∈ N) denote the set {1, 2, . . . , k}. Let log denote the binary logarithm. For integers r ≥ 0, and a ≥ 1, ilog(r)(·) denotes the iterated logarithm of order r, i.e., ilog(r)(a) = max{log(ilog(r−1)(a)), 1} and ilog(0)(a) = a. Hence, ilog(log∗ n)(n) = 1. Let P, E denote probability and expectation, respectively.

heading: 2 Model and Problem Definition
text: An instance of the MAB problem is defined as a tuple 〈n, (Di)i∈[n], (µi)i∈[n]〉 where n is the number of arms. A pull of armi gives a reward in [0, 1] drawn from a distribution Di with mean µi ∈ [0, 1] that is unknown to the decision-maker beforehand. We study MAB under bounded arm-memory setting where the arms arrive in a stream, and at any time-step, the algorithm can store only m < n arms in the arm-memory.
In a single-pass algorithm, every arm arrives only once and it can’t be read back into the arm-memory after it is discarded from the arm-memory. When an arm is read into the arm-memory, its reward statistics get initialized to zero and are updated whenever the arm is pulled until it is discarded from the arm-memory. As we consider single-pass algorithms, our results hold even for a more general model where we do not enforce any restriction on the number of arms for which we can store the arm-statistics. We only impose a condition that at any time step the pulled arm can only be chosen from the set of m arms present in the arm-memory. We cannot pull an arm if the arm is not present in the arm-memory. Next, we formalize the notions of regret minimization and best-arm identification.
The regret of a MAB algorithm can be thought of as the loss suffered by it due to not knowing the reward distributions of the arms beforehand. Let i∗ = arg maxi∈[n] µi. Then armi∗ is the best arm and let µ∗ = µi∗ . The cumulative regret (also called the pseudo-regret) of an algorithm over T time-steps is defined as follows: Definition 1 (Cumulative Regret). Given an instance 〈n, (Di)i∈[n], (µi)i∈[n]〉 of the MAB problem, the cumulative regret of an algorithm after T rounds is defined as R(T ) = µ∗ · T − ∑T t=1 µit , where armit is the arm pulled by the algorithm at time t ∈ [T ], and µ∗ = maxi∈[n] µi.
The expected cumulative regret of an algorithm is defined as E[R(T )] = µ∗ ·T − ∑T t=1 E[µit ], where the expectation is over the randomness in the algorithm and the realization of rewards. In the model with bounded arm-memory, the goal is to minimize expected cumulative regret while storing at most m (< n) arms in arm-memory at any time-step. Note that, popular algorithms such as UCB1 [5] and Thompson sampling [30] store all n arms in memory, i.e., they require an arm-memory size equal to n.
For best-arm identification, the goal of a decision-maker is to output the best arm armi∗ using the minimum number of arm pulls. In practice, a relaxed goal is to find an arm which is close to the best arm in terms of the expected reward. We formalize this notion below. Definition 2 (ε-best arm). Given a parameter ε ∈ (0, 1), armi with mean reward µi is said to be an ε-best arm if µi ≥ µ∗ − ε. Otherwise we call the arm armi to be a non-ε-best arm. Definition 3 ((ε, δ)-PAC Algorithm). Given an approximation parameter ε ∈ [0, 1) and a confidence parameter δ ∈ [0, 1/2), an algorithm A is an (ε, δ)-PAC algorithm if it outputs an ε-best arm with probability at least 1− δ.
Traditionally, the goal in the best-arm identification is to design an (ε, δ)-PAC algorithm minimizing the total number of arm pulls. The goal under streaming setup is to find an (ε, δ)-PAC algorithm that minimizes the total number of arm pulls while storing at most m arms in the arm-memory at any time.

heading: 3 Regret Minimization
text: In this section, we study limitations of bounded arm-memory for regret minimization. An adaptation of uniform-exploration algorithm (see [28]) achieves expected cumulative regret of Õ(n1/3T 2/3) with an arm-memory of two.3 The algorithm keeps in the arm-memory one arm arm∗, called the king, with the best empirical mean µ̂arm∗ among the arms seen so far. Whenever a new arm armi arrives, armi is sampled (T/n)2/3O(log T )1/3 times to obtain its empirical mean µ̂i. Then, µ̂i is compared with µ̂arm∗ . If µ̂arm∗ < µ̂i, then armi becomes the new king, replacing arm∗. Otherwise, arm∗ continues to be the king. After the algorithm tries out all the arms, it returns the king as the best-arm and continues to sample it for the rest of the time horizon.
An important question left open in [27] is to provide a lower bound on the expected cumulative regret of an algorithm with bounded arm-memory. We settle the question by showing that any single-pass algorithm for such a setting incurs at least Ω ( n1/3 · T 2/3/m7/3 ) regret.
Now we state some fundamental properties of KL-divergence that will be needed in this section. Theorem 1 (Slivkins [28]). KL-divergence satisfies the following properties:
• Pinsker’s inequality: For any event A ⊂ Ω, we have 2(p(A)− q(A))2 ≤ KL(p, q).
• Chain rule for product distributions: Let the sample space be a product Ω = Ω1×Ω2×. . .×Ωt. Let p, q be two distributions on Ω such that p = p1×p2×· · ·×pt and q = q1×q2×· · ·×qt, where pj , qj are distributions on Ωj , for each j ∈ [t]. Then KL(p, q) = ∑t j=1 KL(pj , qj).
• Random coins: Let Bε denote a Bernoulli distribution with mean (1 + ε)/2. Then KL(Bε, B0) ≤ 2ε2 and KL(B0, Bε) ≤ ε2, for all ε ∈ (0, 1/2).
For simplicity of presentation, we first discuss a weaker version of our main result in the following theorem. Theorem 2. In the MAB setting, fix the number of arms n and the time horizon T . For any singlepass streaming MAB algorithm, if we are allowed to store at most m < n arms, then there exists a problem instance such that E[R(T )] ≥ Ω(T 2/3/m2)
Proof. We consider 0-1 rewards and the following family of problem instances {Ij : j ∈ {0, . . . ,m}} each containing n arms, with parameter ε > 0 (where ε = 1/T 1/3):
I0 = { µi = 1/2, for i 6= n; µi = 1, for i = n.
∀j ∈ [m], Ij = { µi = (1 + ε)/2, for i = j; µi = 1/2, for i 6= j.
In the above instances, µi denotes the expected reward of armi, the i-th arm to arrive in the stream.
Before delving into the formal proof, we present an intuitive idea behind the proof. Consider the first m arms that are loaded in the arm-memory. If these arms are not sampled for a sufficient number of times, then the probability of discarding the best-arm from the arm-memory is large enough to lead to a large regret in one of the instances in {(Ij)j∈[m]}. Instead, if these arms are sampled a greater number of times, we accumulate a large regret in the problem instance I0. Appropriately choosing the number of samplings to be done and balancing the regrets in these different cases leads to the lower bound on the regret.
Note that a deterministic algorithm does not lose anything by first loading the first m arms into its memory. Thus, w.l.o.g. we consider a deterministic algorithm A which directly stores the first m arms in the arm-memory.
3where f(T ) = Õ(g(T )) =⇒ f(T ) = O(g(T ) logk T ) for some k.
We next set up the sample space. Let L = 1/(4m2ε2). Further, let (rs(i) : i ∈ [m], s ∈ [L]) be a table of mutually independent Bernoulli random variables where rs(i) has expectation µi. We interpret rs(i) as the reward obtained when armi is pulled for the s-th time and the table is called the rewards table. The sample space is then expressed as Ω = {0, 1}m×L. Then, any ω ∈ Ω can be interpreted as a realization of the rewards table.
Each instance Ij , where j ∈ {0, . . . ,m}, defines a distribution Pj on Ω as follows:
Pj(A) = P[A | Ij ], for each A ⊆ Ω.
Given an instance Ij where j ∈ {0, . . . ,m}, let P i,sj be the distribution of rs(i) under this instance. Then, we have that Pj = ∏ i∈[m],s∈[L] P i,s j .
Let St ⊆ {arm1, arm2, . . . , armm} denote the subset of first m arms which are discarded from the arm-memory till (and including) time step t by the algorithm A. If armi is discarded before the algorithm begins pulling arms, call this time step 0, then we include armi in the set S0 where i ∈ [m]. As time horizon T is fixed , and we will eventually discard all arms at the end of time horizon, we can assume that ST = {arm1, arm2, . . . , armm}. For all ω ∈ Ω, let T ′ω = arg min0≤t≤T {t : St 6= ∅}, i.e., T ′ω is the number of time steps since the beginning of the algorithm A when some arm in {arm1, arm2, . . . , armm} is discarded from the arm-memory for the first time. Let A1 = {ω ∈ Ω : T ′ω ≤ L} be the set of reward realizations for which T ′ω ≤ L. Now, fix some arm i ∈ {arm1, arm2, . . . , armm}. Define Ai2 = {ω ∈ Ω : armi ∈ ST ′ω} to be the event that the armi belongs to ST ′ω . Now, let A
i = A1 ∩Ai2 be the set of reward realizations such that ∀ω ∈ Ai, T ′ω ≤ L and armi is discarded from the arm-memory at the time step T ′ω. Also, for any event A ⊆ Ω, let A = Ω \A. Now we have the following observation for instance I0.
Observation 1. If ω ∈ A1, then the algorithm A would incur regret of at least L/2 = T 2/3/(8m2) on instance I0.
Proof. The event A1 is the set of all reward realizations such that T ′ω, the first time step at which some arm is discarded from the memory, is greater than L. Under instance I0, the first m arms have mean 1/2 whereas the best arm has mean 1. Hence, the regret in the first L rounds is exactly (1− 1/2)L. Substituting the value of L gives us the observation.
Let i′ = arg maxi∈[m] P0(Ai). We get the next observation as the best arm armi′ is sampled at most L times.
Observation 2. For all ω ∈ Ai′ , the regret on instance Ii′ is at least ε(T − L)/2 ≥ T 2/3/4.
Proof. The event Ai ′ is the set of all outcomes such that T ′ω , the first time step at which some arm is discarded from the memory, is less than L and armi′ is one of the discarded arms. In instance Ii′ , arm i′ has mean (1 + ε)/2 whereas other arms have mean 1/2. Hence, discarding it within L rounds leads to some sub-optimal arm being pulled in the remaining T − L rounds. Thus, the regret in the last T − L rounds is exactly ε(T − L)/2. Substituting the value of L and ε gives us the observation.
Now we will prove the following inequality, which will be useful in our analysis.
m · Pi′(Ai ′ ) + P0(A1) ≥ 1/4. (1)
The above inequality intuitively shows that the probability of “bad" events that incur large regret, is significant. This inequality is trivially true if P0(A1) ≥ 1/4. Therefore, let us assume P0(A1) ≤ 1/4, i.e., P0(A1) ≥ 3/4. Then P0(Ai ′ ) ≥ 3/(4m), by averaging argument. Using Theorem 1 for
distributions P0 and Pi′ , we obtain:
2(P0(A i′)− Pi′(Ai ′ ))2
≤ KL(P0, Pi′) = ∑ i∈[m] L∑ t=1 KL(P i,t0 , P i,t i′ ) (by Pinsker’s inequality and chain rule) = ∑
i∈[m]\{i′} L∑ t=1 KL(P i,t0 , P i,t i′ ) + L∑ t=1 KL(P i ′,t 0 , P i′,t i′ ) ≤ 0 + L · 2ε 2.
In the last inequality, the first term of the summation is zero because all arms armi, where i ∈ [m]\{i′}, have identical reward distributions under instances I0 and Ii′ . To bound the second term in the summation, we use the last property from Theorem 1. Thus, we have, P0(Ai ′ )− Pi′(Ai ′ ) ≤ ε √ L. Hence, Pi′(Ai ′ ) ≥ P0(Ai ′ )− ε √ L ≥ (3/(4m))− (1/(2m)) = 1/(4m). Here, we use P0(Ai ′ ) ≥ 3/(4m) and L = 1/(4m2ε2). Hence, if P0(A1) ≤ 1/4 then m · Pi′(Ai ′ ) ≥ 1/4. This proves Inequality (1).
Now suppose that we choose an instance I in such a way that we have P [ I = Ij ] = 1/(2m) for any
j ∈ [m] and P [ I = I0 ] = 1/2. Then,
E[R(T )] ≥ P [ I = Ii′ ] · Pi′(Ai ′ ) · T 2/3/4 + P [ I = I0 ] · P0(A1) · T 2/3/(8m2)
≥ 1 2m · (m · Pi′(Ai ′ )) · T 2/3/(4m) + 1 2 · P0(A1) · T 2/3/(8m2)
≥ ( m · Pi′(Ai ′ ) + P0(A1) ) · T 2/3/(16m2) ≥ T 2/3/(64m2)
The first inequality follows from Observations 1 and 2. In the last equality, we have used Inequality (1). Note that the expectation is taken over the choice of input instance and randomness in reward.
Since a randomized algorithm is a distribution over deterministic algorithms, the above result also holds for any randomized algorithm. Now, by slight modification to the above family of instances and using more sophisticated techniques and involved analysis, we can improve the lower bound on the expected cumulative regret and obtain the following main result (see Appendix A for details): Theorem 3. In the MAB setting, fix the number of arms n and the time horizon T . For any singlepass streaming MAB algorithm, if we are allowed to store at most m < n arms, then there exists a problem instance such that E[R(T )] ≥ Ω(n 1/3T 2/3
m7/3 ).
In the above result, the arms can arrive in any order, known as adversarial-order arrival. Our hardness results can also be extended to random-order arrival of arms, which we define next. Let 〈n, (Di)i∈[n], (µi)i∈[n]〉 be an instance of the MAB problem. Let, σ : [n] → [n] be a permutation and let (armσ(i))i∈[n] be the ordering of (armi)i∈[n] under σ. Define Sn = {σ : σ is a permutation of [n]}. Under the random-order arrival model, we assume that the arrival order of the arms in the stream is determined by a permutation σ ∈ Sn, which is drawn uniformly at random from the set Sn. The arms arrive in the order in which they appear in the tuple (armσ(i))i∈[n], i.e., the first arm to arrive in the stream is armσ(1), followed by armσ(2), and so on. Random-order arrival is a well-studied model in optimization under uncertainty due to its connection with the secretary problem and optimal stopping theory [19]. The algorithm of RoyChaudhuri and Kalyanakrishnan [27] also uses an analogous random shuffling of arms. We show that even such random shuffling of arms does not beat Ω(T 2/3) for the single-pass case. For random-order arrival, we obtain the following result (see Appendix B for details): Theorem 4. In the MAB setting, fix the number of arms n and the time horizon T . For any single-pass streaming MAB algorithm, if we are allowed to store at most m < n arms, then in the setting of random order arrival there exists an input instance such that E[R(T )] ≥ Ω(n 1/3T 2/3
m7/3 ).

heading: 4 Best-arm Identification
text: In this section, we design an (ε, δ)-PAC algorithm (Algorithm 1) which minimizes the total number of arm pulls while storing at most m < n arms in the arm-memory. Let r := m− 1.
Intuitively, our algorithm maintains r levels and in each level we maintain a running best-arm candidate (denoted as arm∗i for the arm in level i) in the arm-memory. Every new arm first arrives at the level 1. When an arm arm′ arrives at level i, we sample arm′ (si number of times at level i) and compare its empirical mean with the empirical mean of arm∗i . If it is better than arm ∗ i then arm
′ is stored in arm∗i by replacing the previous arm in it, otherwise we drop arm
′. Once we see a sufficient number (= ci for level i) of arms in a level, we send arm∗i to the next level (i+ 1). At each level i, only one out of every ci arms is sent to level i + 1. As the level index i increases, value of ci and si increases. Intuitively, for higher level indices, the number of arms reaching that level decreases rapidly. Hence, in higher levels each arm can be sampled more number of times for a more refined comparison without affecting the sample complexity. We perform a post-processing step at the end of the stream to send any arm present in intermediate levels to the final level for sampling. After the post-processing step, the algorithm returns the arm left in the highest level.
Algorithm 1 (ε, δ)-PAC algorithm for Best-arm indentification
1: {ε`}r`=1 : ε` ← ε/2`+1. //Intermediate gap parameter in level `. 2: {β`}r`=1 : β` ← 1/ε2` . 3: {s`}r`=1 : s` ← d2β` ( ilog(r+1−`)(n) + log( 2 `+2 δ ) ) e. //Samples per arm in level `. 4: Stored arms: arm′, arm∗1, arm ∗ 2, . . . , arm ∗ r , where arm ∗ ` is a running best-arm candidate at the `-th
level, initialized to NULL. 5: Stored empirical means: µ∗1, µ ∗ 2, . . . , µ ∗ r , where µ ∗ ` is the highest empirical mean of `-th level,
initialized to 0. 6: {c`}r`=1 : c` ← dilog(r−`)(n)e. //Number of arms that need to arrive in level `
before we can promote arm∗` to level `+ 1. 7: Counters: C1, C2, . . . , Cr, initialized to 0.
//Modified Selective Promotion (Steps 8-18). 8: while a new arm armi arrives in the stream do 9: arm′ ← armi and `← 0.
10: while ` = 0 or C` = c` do 11: If ` 6= 0, then C` ← 0, µ∗` ← 0, arm′ ← arm∗` , and arm∗` ← NULL. 12: `← `+ 1. //Promoting arm′ to next level 13: Sample arm′ for s` times and compare its empirical mean µ̂arm′ with µ∗` . 14: If µ̂arm′ < µ∗` , drop arm
′ from the memory. Otherwise, arm∗` ← arm′ and µ∗` ← µ̂arm′ . 15: C` ← C` + 1. 16: If C` = c` and r = 1, return arm∗1 as the selected arm and terminate the Algorithm. 17: end while 18: end while 19: If there is any arm which is stored in a level below r, then promote it to level r and sample it for
sr times. Let arm∗`′ be the arm with the highest empirical mean µ̂`′ among the arms which were sampled in this step, where `′ ∈ [r − 1]. If µ∗r ≤ µ̂`′ then arm∗r ← arm∗`′ . //Post-processing step done at the end of the stream to send any arm present in intermediate levels to the final level for sampling.
20: return arm∗r .
For r = log∗ n, our algorithm is related to the recent work by Assadi and Wang [4]. They propose an (ε, δ)-PAC algorithm (Algorithm 3 in [4]) for the above setting, which has optimal sample complexity and stores at most log∗ n arms in the arm-memory at any time step. However, their analysis is erroneous, due to which their algorithm will output a non-ε-best arm with probability much greater than δ for some input sequences. This implies that the (ε, δ)-PAC guarantee in Lemma 6.2 of [4] does not hold. Here, we intuitively describe the problem in their analysis and show how our algorithm overcomes it.
The algorithm by [4] has a similar framework as that of our algorithm. It maintains log∗ n levels and in each level they also maintain a running best-arm candidate (denoted as arm∗i for level i) in the arm-memory. However, their algorithm samples both arm∗` and the arriving arm armi s` number of times whereas our algorithm only samples the arriving arm armi s` number of times and reuses the stored empirical mean of arm∗` for the comparison. This seemingly simple but critical difference renders their claim erroneous. We briefly explain the intuition behind this with the help of an example. Let the first three arms to arrive in the stream be arm1, arm2, arm3 with means
0.5, 0.45, 0.40, respectively. After sampling the first two arms, let us assume that arm2 defeats arm1, which can happen with sufficiently large probability as their means are close. Now, if we only sample arm3 and use the previous empirical mean of arm2, then arm3 can defeat arm2 if its empirical mean exceeds the empirical mean of arm2 which in turn is greater than that of arm1. This is unlikely as the means of arm3 and arm1 are far apart. On other hand, arm3 has a good chance of defeating arm2 if arm2 is resampled since the empirical mean of arm2 after resampling can be lower than the empirical mean of arm3 with sufficiently large probability. Extending this example to a stream of n arms would imply that an arm with significantly low mean can get selected by the Algorithm in [4] with high probability. For a detailed discussion on this, we refer the reader to Appendix E.
We now proceed towards the detailed analysis of Algorithm 1. For simplicity of presentation, we ignore the ceiling function in the expression of s` and c`.
Theorem 5. Algorithm 1 is an (ε, δ)-PAC algorithm with worst-case sample complexity O( nε2 · (ilog (r)(n) + log( 1δ ))) and r + 1 arm-memory size, where 1 ≤ r ≤ log ∗(n).
Proof. We prove this theorem using the following lemmas. Lemma 7 shows that the sample complexity of our algorithm is O( nε2 · (ilog
(r)(n) + ln( 1δ ))). Lemma 9 gives the proof of correctness that the algorithm is (ε, δ)-PAC. At any time step, we store the arm currently being sampled and furthermore, at each of the r levels we store a single arm, implying the r+ 1 arm-memory size of our algorithm.
Corollary 6. Algorithm 1 is an (ε, δ)-PAC algorithm with worst-case sample complexity O( nε2 · log( 1 δ )) and O(log ∗ n) arm-memory size, when r = log∗ n.
The following lemma establishes the worst sample complexity of Algorithm 1 (see Appendix D for the detailed proof of the lemma).
Lemma 7. The worst case sample complexity of the algorithm is O( nε2 · (ilog (r)(n) + ln( 1δ ))) and it does not depend on the arms’ rewards or gap parameter or the order in which the arms arrive.
We use the following lemma which follows from the Hoeffding’s inequality, to prove the correctness of our algorithm (see Appendix D for the detailed proof).
Lemma 8. Let arm1 and arm2 be two different arms with means µ1 and µ2. Suppose µ1 − µ2 ≥ θ and we sample each arm Kθ2 times to obtain empirical means µ̂1 and µ̂2. Then,
P(µ̂1 ≤ µ̂2) ≤ 2 · e(−K/2)
We now proceed to show that our algorithm is an (ε, δ)-PAC algorithm. Towards that, we introduce the notion of reward gap. We say that an arm with mean µ1 has a reward gap of ε′ from an arm with mean µ2 if µ2 − µ1 = ε′. Now we prove the following claim. Claim 1. For any level ` < r, let arm′` be the best arm to ever reach this level. Then, with probability at least 1− δ
2`+1 , at least one arm with reward gap at most ε` from arm′` is sent to level `+ 1 or is
sampled in Step 19.
Proof. Let us consider some level ` and a set of arms arm`1 , arm`2 , . . . , arm`c` , which increases the counter C` from 0 to c`. Denote the best arm among them as arm′` and let arm ∗ ` be the empirically best arm seen so far since the arrival of arm`1 . Our algorithm works as follows: once an arm arrives at level `, it is pulled s` number of times. Next, we compare its empirical mean with that of arm∗` , which was computed when the arm corresponding to arm∗` arrived at level `. The arm with the greater empirical mean is maintained as arm∗` and its empirical mean is stored for future comparisons. Once C` = c`, arm∗` is sent to level `+ 1. Note that this is equivalent to simultaneously pulling each of the c` arms s` number of times, and then sending the empirically best arm to level `+ 1. Also note that if 0 < C` < c`, and the condition in Step 8 is not satisfied then we will sample arm∗` in the Step 19.
Using Lemma 8, we can show that at any level `, if two arms have reward gap µi − µj ≥ ε` then P[µ̂i < µ̂j ] ≤ δ2`+1·c` . Since at most c` arms arrive at level ` before the counter C` reaches c` or the condition in Step 8 is not satisfied, taking union bound we have that the probability that at least one arm with reward gap ≤ ε` from arm′` is either sent to level `+ 1 or is sampled in the Step 19 is at least 1− δ
2`+1·c` · c` = 1− δ 2`+1 . Note that while using the union bound, we are comparing the
empirical mean of each of the arms with the empirical mean of the best arm. So the number of events is at most c`.
Claim 2. Let arm′r be the best arm among the arms which reached level r including the arms which were sampled in Step 19 of Algorithm 1. Then, with probability at least 1− δ2r+1 , Algorithm 1 returns an arm with reward gap at most εr from arm′r.
Proof. Using Lemma 8, we can show that among the arms that are being considered here, if two arms have reward gap µi − µj ≥ εr then P[µ̂i < µ̂j ] ≤ δ2r+1·cr . As cr = n, by taking union bound we get that with probability at least 1− δ2r+1 , Algorithm 1 returns an arm with reward gap at most εr from arm′r.
Lemma 9. With probability at least 1− δ, the arm selected by the algorithm is an ε-best arm.
Proof. Let the best arm be arm∗. By union bound and Claim 1, the probability that no arm with reward gap at most ∑r−1 i=1 εi from arm ∗ reaches level r is upper bounded by ∑r−1 `=1 δ/2
`+1. Given this upper bound and Claim 2, the probability that Algorithm 1 doesn’t return an arm with reward gap at most ∑r i=1 εi from arm ∗ is upper bounded by: ∑r `=1 δ/2 `+1 ≤ δ · ∑∞ `=1 1/2 `+1 = δ/2 < δ.
Thus with probability at least 1− δ, Algorithm 1 returns an arm with reward gap at most: ∑r `=1 ε` =∑r
`=1 ε/2 `+1 ≤ ε/2 < ε from arm∗. This concludes the proof.

heading: 5 Conclusion
text: In this paper, we studied the stochastic MAB problem with bounded arm-memory under regret minimization and best-arm identification. First we showed a lower bound of Ω ( n1/3 · T 2/3/m7/3 ) on the expected cumulative regret for single-pass MAB algorithms with bounded arm-memory. Next we proposed (ε, δ)-PAC streaming algorithm with r + 1 arm-memory size (r ∈ [log∗ n]) which has optimal sample complexity when r = log∗ n. Our best-arm identification algorithm is a streaming version of the r-round adaptive algorithm where the arm pulls in each round are decided based on the observed outcomes in the earlier rounds [1], and the best-arm is the output at the end of r rounds. The upper bound on the sample complexity of our algorithm almost matches with the lower bound for any r-round adaptive algorithm that is mentioned in [1].
A future research direction is to obtain lower bounds and upper bounds on the expected cumulative regret for k-pass stochastic MAB algorithms with bounded arm-memory where k > 1. Another direction would be to obtain instance-dependent lower bound and upper bound on the expected cumulative regret for single-pass stochastic MAB algorithms with bounded arm-memory. Another interesting question is to obtain an (ε, δ)-PAC streaming algorithm with O(1) arm-memory size and optimal worst case sample complexity.

heading: Acknowledgements
text: Vishakha Patil gratefully acknowledges the support of a Google PhD Fellowship. Arindam Khan is thankful to be supported by a Pratiksha Trust Young Investigator Award. The authors would like to thank Santanu Rathod for useful discussions surrounding interesting problems in this area. The authors are also grateful to the anonymous reviewers for their detailed comments that helped us to improve the presentation of this work.

Review summaries:
The authors consider the problem of multi-armed bandits with the additional constraint that the learner can only pull arms that belong to the so-called arm-memory. First, the authors look at the regret minimization setting, and provide a worst-case regret lower bound of order $\Omega(T^{3/2})$ that any single-pass algorithm must satisfy, given that arm-memory size is strictly smaller than the number of arms. Single-pass algorithms can only add an arm or remove it from the arm-memory once. Second, the authors investigate the pure exploration problem and propose an algorithm that is $(\epsilon,\delta)$-PAC, only uses $O(\log^\star(n))$ space complexity, and has a sample complexity of order $O(\frac{n}{\epsilon^2} \log(1/\delta))$.

The paper studied the multi-armed bandit problem with bounded arm-memory. In this model, at each time at most $m<n$ arms (and their statistics) may be stored in memory. The paper is focused on a single-pass model, in which after an arm being removed from the memory it can no longer be accessed.  For the regret minimization problem, the authors prove a $\Omega(n^{1/3}T^{2/3}/m^{7/3})$ lower bound, and show a simple $\tilde{O}(n^{1/3}T^{2/3})$ upper bound.  For the best arm identification problem, they show an algorithm with sample complexity of $O(\frac{n}{\epsilon^2}(\log(1/\delta)+ilog^{(m-1)}(n)))$ where $ilog^{(r)}$ is the iterated logarithm of order $r$. Thus showing that $log^*(n)$ memory is sufficient for asymptotically optimal sample complexity. They also point out an error in [1] who previously claimed for showing such an algorithm.  

This paper studies a variant of stochastic multi-armed bandits in which the learner doesn't have access to all the arms. The learner has a memory of size $m$, which means it can store and access only $m$ arms. The learner can discard some arms to free up space for new arms, which come in a stream. When an arm is discarded, it can never be accessed again.   The standard problems of regret minimization and best-arm identification are studied here; a regret lower bound for the former and an algorithm for the latter are given.  Let $T, n,$ and $m$ denote the time horizon, the number of arms, and the memory size, respectively. When $m=2$, a regret upper bound of $\widetilde{O}(n^{1/3}T^{2/3})$ was shown in previous work. This paper gives a matching lower bound up to logarithmic factors, and gives a lower bound of ${\Omega}(n^{1/3}T^{2/3}/m^{7/3})$ for all $m=1,2,\dots,n-1$. This is in sharp contrast with the $m=n$ case, which achieves $O(\sqrt{nT})$ regret.  For best-arm identification, the paper provides an algorithm with memory size $1 + \log^* (n)$ that pulls $O(n\log(1/\delta)/\varepsilon^2)$ arms and outputs an $\varepsilon$-optimal arm with probability $1-\delta$. This sample complexity is optimal even with memory size $n$. A similar result was shown in a previous work, but this paper claims that that proof had a bug.

This paper studies the classical $T$-period $n$-armed stochastic bandit problem under "memory" constraints: the decision maker can only store reward statistics for a certain maximum number $m < n \ll T$ of arms at any time $t\in[T]$. The authors establish an $\Omega\left( T^{2/3} \right)$ fundamental hardness result (modulo dependence on $m,n$) for the cumulative regret minimization problem under "single-pass" policies (arms discarded from memory cannot be recalled) with memory sizes up to $n-1$. This is optimal in $T$ since an algorithm with a matching upper bound in $T$ (up to log factors) already exists in literature. The result is also particularly interesting since it is known that the "holy grail" of $\Theta\left( \sqrt{T} \right)$ regret (modulo $n$) is achievable with memory size $n$. The authors also study the memory-limited best arm identification problem under the fixed confidence setting, and propose an $\left( \epsilon,\delta\right)$-PAC algorithm (where the parameters are the approximation and confidence factors respectively) with a space complexity of $m = \mathcal{O}\left( \log^\ast n \right)$ and an optimal sample complexity. Notably, a different algorithm that was claimed to have these very properties, already appeared in a STOC'20 paper. The authors show that the claims made in said paper are, in fact, erroneous, by constructing a family of instances on which aforementioned properties are provably violated.