Multi-Armed Bandits with Bounded Arm-Memory: Near-Optimal Guarantees for Best-Arm Identification and Regret Minimization
Authors: Arnab Maiti
Vishakha Patil
Arindam Khan
Venue: NeurIPS 2021 Poster (2021)
Keywords: Multi-Armed Bandits
Bounded Arm-Memory
Best-Arm Identification
Regret Minimization
KL-Divergence
Hoeffding's Inequality

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 $\Omega(T^{2/3})$ 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 $(\varepsilon, \delta)$-PAC algorithm with arm memory size of $O(\log^*n)$ and $O(\frac{n}{\varepsilon^2}\cdot \log(\frac{1}{\delta}))$ optimal sample complexity. 

Multi-Armed Bandits with Bounded Arm-Memory: Near-Optimal Guarantees for Best-Arm Identification and Regret Minimization
Arnab Maiti
Vishakha Patil Indian Institute of Science, Bangalore, India patilv0iisc.ac.
Arindam Khan
Indian Institute of Technology,
Indian Institute of Science, Bangalore, India
Kharagpur, India
arnabmaiti@iitkgp.o ac in
arindamkhan@0isc ac.
Abstract
We study the Stochastic Multi-armed Bandit problem under bounded mrmmme In this setting, the arms arrive in stream, and the number of arms that can be stored in the memory at any time, is bounded. The arms that are present in the memory. We address the problem from the perspective two standard objectives: I) regret minimization, and 2) best-arm identification. For regret minimization, we settle an important open question by showing an almost tight guarantee. We show Q(T2/3) 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 (c, 8)-PAC algorithm with arm-memory size a ()) optimal sample complexity.
can only pull
of (log" n) and (
Introduction
The Stochastic Multi-armed Bandit (MAB) problem is classical framework used capture decision- making 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 pulling 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 identifica- tion. See, e.g. [7] for 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 Herschkom 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 rescarch. Large number of arms may enforce a constraint that the
algorithm may not be able 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 the beginning.
The streaming model, first formalized in the pioneering work Alon et al. 3 has been developed to handle data streams where huge amount of data arrives online and an algorithm has access
A part of this work was done when the author undergraduate summer intern at IISc, Bangalore.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

to only a limited amount of memory. We refer the readers to 223 2 for a detailed survey of streaming algorithms. With the ever-increasing amount of data available to any machine learning (MI) algorithm, several salient areas of MI. are being studied under streaming constraints; e.g., active (see the
learning [3 29), lifelong learning [3]. and identifying correlations in multivariate data [1
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 227 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 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-m memory can not be pulled. Further, for any arm currently not in the mon-meorr, 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
[0 for regret minimization, and Median-Eliminatio Elimination [3] 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 f. the algorithm can only pull an arm that is currently in amm-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- am-mmmorr 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 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- one-pass pass SVMs when the data arrives in a stream, whereas Carvalho and Cohen 8 design single-pass algorithms for online learning.
1.1 Our Contribution
We study MAB under bounded arm-memory, where n arms arrive in stream and at most m 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-thhoretic machinery related to KL-divergence, we show that any single-pass algorithm in this model will incur an expected regret of 2(n T2/3 //3 Interestingly, this result holds for any m < n. which shows that even if the algorithm is allowed to store - 1 arms in the arm-memory at any time, we cannot hope to obtain better regret guarantee in terms of T. This lower bound almost matches with the Onn2/3/2// bound on the expected cumulative regret, obtained by the standard uniform-exploration algorithm where we store = 2 arms. We note here that the uniform- exploration algorithm with m = 2 can be trivially extended to an algorithm that stores m > arms in the memory and achieves regret guarantee that matches the lower bound by storing the 2 arms required by the uniform exploorttioooooiinn algorithm and filling the remaining m 2 sized arm arm-memory 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 1 arms in the memory. This shows an interesting dichotomy between m n and m n, as can obtain expected cumulative regret of Ó (V'T)) by standard UCB1 1 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: Section we propose an (e, -)C streaming algorithm that takes r as input and stores + 1 arms in the arm-memory at any time and has sample complexity 0
2

---

(ilog( + In( (2)) P In particular, when r r= log" n, our algorithm achieves the optimal worst- case sample complexity O (og())) 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 (s. 5...P 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 incorrect and their algorithm is nor (E, (c,6)-PAC. In Appendix E we construct family of input instances for which their algorithm will output a non-s-best arm with probability significantly larger than J. Section [ we show that the special case of our algorithm (when r = log" n) indeed provides the guarantee claimed in 4
1.2 Related Work
In one of the earliest works on MAB with bounded arm-memory, Herschkorn et al. [16 study the infinite-armed MAB problem where only 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 different variant of bounded memory where the algorithm 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.
remember the rewards
More recently, Kalvit and Zeevi [8] studied the infinite-armed bandit problem where each arm is associated with 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 (log 7") expected cumulative regret. Further, de Heide et al. [12 also study the infinite-an armed bandit problem where there could be multiple optimal arms. They propose an algorithm and prove that it achieves Oloo T' expected regret by sampling Oloo T) number of arms. In our work, we focus on the inite-armed MAB problem with bounded arm- arm-memory. Recently, the MAB problem where arms arrive in 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 (44 showed that when m = 1, 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-pas, algorithms. Liau et al. (21) propose an upper-confidence bound based algorithm with (1) arm-memory size, which achieves an expected cumulative regret log
bound of O Ei log( A A. A.)) which is within log( A factor of the UCBI regret bound (5). Here A is the gap parameter, i.e., the difference in the expected rewards of the best and the second-best arms, and A, is the difference in the expected rewards of the best arm and the i i'th arm. However, they do not provide a worst-case regret bound for their algorithm, and hence, depending
the instance the regret of this algorithm may be very high. More precisely, if say A, is 1/72/3 then the proven regret bound implies ( 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 UCBI, their algorithm achieves an expected regret of O(nm 3 m 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.
using 2(log T' passes. The recent work of Xu and Zhao [34]
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 (cquivalent to MAB with Bernoulli reward distributions), which keeps exactly extra coin in the memory any time and has optimal sample complexity. They further extend their algorithm to the top-k coins identification problem. which stores i coins in the memory and has optimal sample complexity. Crucially though, both algorithms assume that the gap parameter A is known. Throughout our work, we deal with the case when A is not known to the algorithm. Falahatgar et al. [4] also study the best-an arm identification
Here ilog (r) is iterated logarithm of order (see Section
1.3
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 uniformly random sequence. Note that unlike [14], the sample complexity of our algorithm is independent of the rewards observed during the sampling, and we not require the assumption that the arms need to arrive in uniformly random sequence. In a recent independent work, Jin et al. [17] proposed an e-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 settance-dependee 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 the same quantity.
1.3 Notation
Let [A]] (where & N) denote the set (1,2,...,k) Let log denote the binary logarithm. For integers 0, and 2 1, ilog() denotes the iterated logarithm of order r, i.e., (a) max (log((og0 (1) (a)), 1)
and ilog(") (a) Hence, ilog(log' (I(n 1. Let TP, E denote probability and expectation, respectively.
2 Model and Problem Definition
An instance of the MAB problem is defined as tuple (n. (D:) (15))e(x)) where is the number of arms. A pull of arm; gives a reward in [0, 1] drawn from a distribution D, with mean lt E [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-m mommmerry.
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- memooy. As we consider maggle-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 condition that at any time step the pulled arm can only be chosen from the set of m arms present in the umm-emory. We cannot pull an arm if the arm is not present in the arm-memonn oo-mmeory. 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 max μ4: Then arm,- is the best arm and let 1 = ft:- The cumulative regret (also called the pseudo-regret) of an algorithm over T time-steps is defined as follows:
Definition (Cumulative Regret). Given an instance (n,, (Di) (pS)sE(n)) of the MAB problem,
the cumulative regret of algorithm after T rounds is defined R(T) = n² T -t- Pio where arm; is the arm pulled by the algorithm at time E [T], and μ = max 14:
E[u;,,, where The expected cumulative regret of an algorithm is defined as E = = the expectation is over the randomness in the algorithm and the realization of rewards. 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 UCBI (5) and Thompson sampling (30] store all arms in memory, i.e., they require an arm-memory size equal to n.
For best-arm identification, the goal of a decision-maie is to output the best arm arm, using the minimum number of arm pulls. In practice, a relaxed goal is to find an arm which is close the best arm in terms of the expected reward. We formalize this notion below.
Definition 2 (c-best arm). Given parameter & E (0, 1), arm; with mean reward μrs is said be an e-best arm if (A: Z 1r" - E. Otherwise we call the arm arm; to be a non-e-best arm.
Definition 3 ((e, PPC Algorithm). Given an approximation parameter & E (0. and confidence parameter [0, 1 1/2,, an algorithm A is an (e, PPAC algorithm if it outputs an e-best arm with probability at least - 8.

---

Traditionally, the goal in the best-arm identification is to design an (s. 6)- algorithm minimizing the total number arm pulls. The goal under streaming setup is to find (e, 6)-PAC algorithm that minimizes the total number of arm pulls while storing at most m. arms in the arm-memory at any time.
3 Regret Minimization
In this section, we study limitations of bounded arm- memom for regret minimization. An adaptation of uniform-exploratinn
algorithm (see (28) achieves expected cumulative regret of Ö(n 2223333/33) with an arm-memon mmmmmmory of two The algorithm keeps the arm-memory one arm arm", called the king, with the best empirical mean Marn. among the arms seen so far. Whenever new arm arm; arrives, arm; is sampled (T (T/n)3/3O T)1/3 times to obtain its empirical mean 74, Then, T4 is compared with Parn". If Marn' < Pag then arm; 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 sample it for the rest of the time horizon.
An important question left open in (77 is to provide a lower bound on the expected cumulative regret of algorithm with bounded arm-mer mm-memory. We settle the question by showing that any single-pass algorithm for such setting incurs at least 52 (n2/3 T2233 /mm regret.
Now we state some fundamental properties of KL-divergence that will be needed in this section.
Theorem (Slivkins [28] ). KL-divergence satisfies the following properties:
Pinsker's inequality: For any event A we have 2p((A) {()))² KL(p, q).
Chain rule for product distributions: Let the sample space be a product
Q1 x22 Dr-
Let p, be two distributions on Q such that p P1 x P2 X x.. x Pt and q = q1 x 92 X x qr.
where Pjs Qj are distributions on Qj. for each j E [t]. Then KL(p, q) = Σ₁= KL(Pj, 93)
Random coins: Let Bg denote a Bernoulli distribution with mean (1 + s)/2. Then (0, 1/2).
(L By) S 2=² and (L B2) S E2, all
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 and the time horizon T. For any single- pass streaming MAB algorithm, if we are allowed to store at most m < n arms, then there exists a problem instance such that [[[(T)) 2 22T2/3 (rrr2/3/m²) /m²²
Proof. We consider 0-1 rewards and the following family of problem instances (I, : j E m.....,]]. each containing n arms, with parameter E >> 0 (where & = 1/T2/3):
μi =1/2, =1,
for + n; for = n.
To
Hi
pi e)/ for j; for i * j-
Vj E [m], I
= 1122
In the above instances, 14, denotes the expected reward of arm, the i-th to arrive in the stream.
Before delving into the formal proof, we present an intuitive idea behind the proof. Consider the first arms that are loaded in the arm-memory. If these arms not sampled for a sufficient number of times, then the probability discarding the best-arm from the arm-memory is large enough to lead to large regret in one of the instances in { {I,, ) }. Instead, if these arms sampled greater number of times, we accumulate a large regret in the problem instance Tg. 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.ogg we consider a deterministic algorithm A which directly stores the first m arms in the arm-memory.
where f(T)- Ö(((T)) S(T) O(g(1) log" * I') for some k.
5

---

We next set up the sample space. Let L = 1/m Further, let (r.(1) : E [m], E [L]) be table of mutually independent Bernuulii random variables where ri(() has expectation μı, We interpret (4) as the reward obtained when arm; is pulled for the s-th time and the table is called
the rewards table. The sample space is then expressed as {0, 1] mxx Then, any w can be
interpreted realization of the rewards table.
Each instance Zj, where j E {O,..., m., defines a distribution P3 on Q as follows:
(A) = P|A| Z,,, for each A C Q.
Given an instance Z, where E [0.....m} let pje be the distribution of (1) under this instance. Then, we have that P3 = 1l Ilig(m),e((1) p..
Let St S {arm1, arma............................ armm denote the subset of first m arms which are discarded from the arm-memory till (and including) time step by the algorithm A. If arm; is discarded before the algorithm begins pulling arms, call this time step O, then we include arm; in the set So where i [m]. As time horizon T is fixed and will eventually discard all arms at the end of time horizon, we can assume that Sr = farm1, army..... armm J. For all w E Ω let TV = arg minosiss( (1: : S, o 0j. i.e., Ty is the number of time steps since the beginning of the algorithm A when some arm in {armi, arm2,.... armm) } is discarded from the arm-memory for the first time. Let A₁ {w E Q: TV L) be the set of reward realizations for which T < L. Now, fix some arm i E {arm1, arm2, armm ). Define A = {w E Q arm; E STy } to be the event that the arm, belongs to Sry- Now, let A' = A1 n A3 be the set of reward realizations such that Vw E A T < L and arm; is discarded from the arm-memory at the time step Tw Also, for any event C Q, let = 2 A.
Now we have the following observation for instance To-
Observation 1. If E A1, then the algorithum A would incur regret of at least L/2 T2/3 /(8m²) on instance Io-
Proof. The event Aj is the set of all reward realizations such that TV the first time step at which some arm is discarded from the memory, is greater than L. Under instance Io, the first arms have mean 1/2 whereas the best arm has mean 1. Hence, the regret the first rounds is exactly (1-1/ 1. Substituting the value of L gives us the observation.
Let i' arg maxie|m] Po(A'). We get the next observation the best arm army is sampled at most times.
Observation For all w E A', the regret on instance Lş is at least - L)/2 12/3/4
Proof. The event A is the set of all outcomes such that TV, the first time step at which some arm discarded from the memory, is less than L and arm, one of the discarded arms. In instance Ie arm i' has mean (1 + e)/2 whereas other arms have mean 1/2. Hence, discarding it within rounds leads to some sub-optimal arm being pulled in the remaining L rounds. Thus, the regret in the last 7 - 7. rounds is exactly e(T T2)/2. Substituting the value of I. and e gives us the observation.
Now we will prove the following inequality, which will be useful in our analysis.
m (A + Po(A)) 2 1/4.
The above inequality intuitively shows that the probability "bad" events that incur large regret, is significant. This inequality is trivially true if (A 2 1/4. Therefore, let us assume (A < 1 1/4, i... Po(A 2 3/4. Then Po(A') 2 3/(4n 3/(4m). by averaging argument. Using Theorem for

---

distributions Po and p.v, we obtain:
2(Po(A') P. (. (L., Pa)
(L Pi)))
(by Pinsker's inequality and chain rule)
fE(m
Σ
KL (Pt' Pp))
> ELI(P'
Pf s 0 L. 2
In the last inequality, the first term of the summation is zero because all arms arm, where i E [m]]] [ have identical reward distributions under instances To and Iy. To bound the second term in the summation, we use the last property from Theorem | Thus, we have, Po(4") - (r(AA)) S EVI. Hence, Py: (A4' 2 Po - LV z (3/(4m)) - (1/(2m)) = 1/(4m). Here, we use Po > 3/(4m) and L = 1/ 1/) Hence, if Po1) S 1/4 then m (:(AA') 2 1/4. This proves
Inequality (I.
Now suppose that we choose an instance I in such a way that we have P|Z - I₁} = 1/(2m) for any j E [m]] and TP [ To] = 1/2. Then,
[[R(T)) 2 IP I = Iz] (AA) P Io] Po(AA) T/2 /2233//mm /(m²)
1. (m (AA))) (/213/(4m)) + - Po((A)) TT2 (8mm²)
2m
z m (A + Po(Ai) T2/3 /016/"/1mm))))) 2 2/3 /(64m²)
The first inequality follows from Observations andd] 2
In the last equality, we have used Inequality (T) Note that the expectation is taken over the choice of input instance and randomness in reward. D
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 for details):
Theorem 3. In the MAB setting. fix the number of arms n and the time horizon T. For any single- pass streaming MAB algorithm, if we allowed to store most < arms, then there exists problem instance such that [[[[(T)] 2 52( n3/33/2/3
m²73
In the above result, the arms can arrive in any order, known as adversarial-order arrival. Our hardness results can also be extended random-order arrival of arms, which we define next. Let (n, (D))se(n) (44))s(a)) be an instance of the MAB problem. Let, a : [m] + [n] be a permutation and let (() be the ordering of (arm:)ie(w) under a. Define S, = {a a a permutation of [m]]- Under the random-order arrival model, we assume that the arrival order Sn, which is drawn uniformly at random
of the arms in the stream is determined by permutation from the set Sn,. The arms arrive in the order in which they appear in the tuple (i))m i.c., the first arm to arrive in the stream is arm,(1). followed by arm,(2), and so on. Random-order arrival is 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 22(2233 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-par 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 B[R(T)) 2 20 22222/822 2//22/2
m37
4 Best-arm Identification
In this section, we design an (c, 8)- algorithm (Algorithm) D which minimizes the total number of arm pulls while storing at most m arms in the arm-memory. Let r := m 1.
7

---

Intuitively, our algorithm maintains r levels and in each level we maintain running best-arm candidate (denoted as arm; for the arm level in the arm-memory. Every new arm first arrives at the level 1. When an arm arm' arrives at level i, we sample arm' (8; number of times at level i) and compare its empirical mean with the empirical mean of arm;. it is better than arm; then arm' is stored in arm; by replacing the previous arm in it, otherwise we drop arm'. Once we see sufficient number (= C; for level i) of arms a level, we send arm; to the next level (i + 1). At each level i, only one out of every arms is sent to level + 1. As the level index increases, value of and 8; increases. Intuitively, for higher level indices, the number arms reaching that level decreases rapidly. Hence, in higher levels each arm can be sampled more number of times for more refined comparison without affecting the sample complexity. We perform a proccssngss 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 (s, 6)-PAC algorithm for Best-arm indentification
{ce]ē=1 :6 6 e/2 //Intermediate gap parameter level l.
2: {Be]=- : Br - 1/e2.
log( ( )) / /Samples per arm in level L. 4: Stored arms: arm', armj, arm arm... where arm; is a running best-arm candidate at the &-th
3: {se)e=1 5 (23g
level, initialized NULL.
5: Stored empirical means: 11, , initialized to O.
My, where μn is the highest empirical mean of (-th level,
6: {o : ce + [n]og(r-(n)]] //Number of arms that need to arrive in level & before we can promote arm; to level f+1.
7: Counters: C₁, C2...., Cy, initialized to 0.
/ /Modifiied Selective Promotion (Steps
18
8: while new arm arm; arrives in the stream do
9: arm' + arm, and +++ 0.
10:
while { = 0 or C₁ = C2 do
11:
If + 0, then C, + 0, μ + 0, arm' + arm;, and armž < NULL. f + 1. //Promtting arm' to next level
12:
Sample arm' for se times and compare empirical mean Marn with ptg- If Marn' < pt. drop arm' from the memory. Otherwise, arm; arm' and μ Parn'.
14:
15:
Ce C2 +
16: If ct and 1, return arm; 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 s, times. Let arm be the arm with the highest empirical mean fh among the arms which were sampled in this step, where E E [rr-]] 1]. If μæ, I The then arm, +- 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.
return arm,..
For log" n. our algorithm is related to the recent work by Assadi and Wang 4. They propose an (e, -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 which their algorithm will output non-s-best arm with probability much greater than for some input sequences. This implies that the (e, 8ACC guarantee in Lemma 6.2 of [4] does not hold. Here, intuitively describe the problem in their analysis and show how algorithm overcomes it.
The algorithm by [4] has a similar framework as that of our algorithm. It maintains log" n levels and each level they also maintain running best-arm candidate (denoted as arm; for level in the arm-memory number times whereas our algorithm only samples the arriving arm arm, 8ş 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 arm,, arm2, arm; with means
However, their algorithm samples both arm; and the arriving arm arm, sy

---

0.5, 0.45, 0.40, respectively. After sampling the first two arms, let us assume that army defeats armi. which can happen with sufficiently large probability as their means are close. Now, if we only sample arm; and use the previous empirical mean of arm2, then arm; can defeat armz if its empirical mean exceeds the empirical mean of arm; which in turn is greater than that of arm;- This is unlikely as the means of arm, and arm; are far apart. On other hand, arm; has a good chance of defeating arma if arma is resampled since the empirical mean of arma after resampling can be lower than the empirical mean of arm; 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 44] with high probability. For a detailed discussion this, we refer the reader to Appendix E
We now proceed towards the detailed analysis of Algorithm I For simplicity of presentation, we ignore the ceiling function in the expression of 8y and Cg.
Theorem 5. Algorithm|] 7is is an (e, 6)-AA algorithm with worst-case sample complexity O (ilog(r)(n) + log( ())) and r + arm-memory size, where S rrr (n).
Proof. We prove this theorem using the following lemmas. Lemma 7 shows that the sample com- plexity of our algorithm is O a (ilog(r) (n) + In( (n)))) Lemma 9 gives the proof of correctness that the algorithm is (s, 6)-PAC At any time step, store the arm currently being sampled and furthermore, at each of the levels we store a single arm, implying the r r arm-memory size of our algorithm.
Corollary 6. Algorithm is (e, 6PPAC algorithm with worst-case sample complexity O (lg({))) and O(log n) arm-memory size, when r = logg n.
The following lemma establishes the worst sample complexity of Algorithm I (sce Appendix for the detailed proof of the lemma).
Lemma 7. The worst case sample complexity of the algorithm is O (ilog(r)n) + (n) and does not depend on the arms' rewards or gap parameter or the order in which the arms arrive.
We 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 arm, and arm2 be two different arms with means μrl and μ2. Suppose μr - 122 2 and we sample each arm (/2
K times to obtain empirical means iu and Pzz. Then,
PM S P22) S 2 (K1/22)
We now proceed to show that our algorithm is an (s, P algorithm. Towards that, we introduce the notion of reward gap. We say that an arm with mean in has a reward gap of e' from arm with mean 22 (22 #1 = E'. 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 ---T, at leust one arm with reward gap at most Et. from arm' is sent to level + 1 or is sampled in Step T9
Proof. Let us consider some level and a set of arms arm,, arm arm which increases the counter C' from ct. Denote the best arm among them as arm; and let arm; be the empirically best arm seen so far since the arrival of arme, Our algorithm works as follows: once an arm arrives level f, it pulled 8ę 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 l. The arm with the greater empirical mean is maintained as arm; and its empirical mean stored for future comparisons. Once Ct ce, arm; is sent to level f + 1. Note that this is equivalent to simultaneously pulling each of the er arms sy number of times, and then sending the empirically best arm to level + 1. Also note that is not satisfied then we will sample arm; in the Step 19
if 100 < C2- < cz, and the condition in Step 8
Using Lemma g we can show that at any level f, if two arms have reward gap μ4 F3 2 Eg then PIñ. < p,y] 2 2 Since most Cg arms arrive level before the counter C₁ reaches og or the condition Step is not satisfied, taking union bound we have that the probability that least one arm with reward gap S E from arm is either sent to level e + 1 or is sampled in the Step 19 is
at least 1 2 Ct 1 à
ZET.. Note that while using the union bound, we comparing the

---

empirical mean of each of the arms with the empirical mean of the best arm. So the number of events most Cg.
Claim 2. Let arm', be the best arm among the arms which reached level including the arms which were sampled in Step119 Algorithm Then, with probability at least 2r+1 Algorithm returns an arm with reward gap most Er from arm..
Proof. Using Lemma we can show that among the arms that are being considered here, if two arms have reward gap 14 Hj 2 E, then P(P, < py) gr+t.e, As c, n, by taking union bound we get that with probability least FT Algorithm returns an arm with reward gap most er from arm,..
Lemma 9. With probability at least
5, the arm selected by the algorithm is an e-best arm.
Proof. Let the best arm be arm". By union bound and Claim | the probability that no arm with
reward gap at most Ei= E, from arm" reaches level r is upper bounded by Σi=1 8/24+1, Given this upper bound and Claim 2 the probability that Algorithm T doesn't return gap at most
with reward
Σi= E, from arm is upper bounded by: Σ 6/2 8/2++1 6 > 1/2
8/2
Thus with probability least 1 6, Algorithm returns
with reward gap at most: Σ E0
St=1e/2tt se/2 from arm". This concludes the proof.
5
Conclusion
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 (n 7723 /mm 7/3) on the expected cumulative regret for single-pass MAB algorithms with bounded arm-memory, Next we proposed (s, PPC streaming algorithm with + 1 arm-memory size (r E [log" nl) which has optimal sample complexity when 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 [T]. and the best-arm is the output the end of 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 [I.
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 (s, 8)- streaming algorithm with ((1) arm-memory size and optimal worst case sample complexity.
Acknowledgements
Vishakha Patil gratefully acknowledges the support of Google PhD Fellowship. Arindam Khan 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.
10

---

References
[1] Arpit Agarwal, Shivani Agarwal, Sepehr Assadi, and Sanjeev Khanna. Learning with limited rounds of adaptivity: Coin tossing, multi-armed bandits, and ranking from pairwise comparisons. In Conference on Learning Theory, pages 39-75. PMLR, 2017.
[2] Charu Aggarwal. Data streams: models and algorithms, volume 31. Springer Science & Business Media, 2007.
[3] Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approximating the frequency moments. In Proceedings of the twenty-eighth annual ACM symposium on Theory of Computing, pages 20-29, 1996.
[4] 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, pages 1237-1250, 2020.
[5] Peter Auer, Nicolò Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2-3):235-2555 2002.
[6] Donald A Berry, Robert W Chen, Alan Zame. David C Heath, and Larry A Shepp. Bandit problems with infinitely many arms. The Annals of Statistics, pages 2103-2116, 1997.
[7] Sébastien Bubeck and Nicolo Cesa-Bianchi. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends@ in Machine Learning, 5(1):1-122,
2012.
[8] Vitor R Carvalho and William W Cohen. Single-pass pass online learning: Performance, voting schemes and online feature selection. In Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 548-555 2006.
[9] Jhelum Chakravorty and Aditya Mahajan. Multi-armed bandits, gittins index, and its calculation. Methods and applications of statistics in clinical trials: Planning, analysis, and inferential methods, 2(416-435):455, 2014.
[10] Thomas M Cover. A note on the two-armed bandit problem with finite memory. Information and Control, (2(5):3713377 1968.
[1]] Yuval Dagan and Ohad Shamir. Detecting correlations with little memory and communication. In Conference On Learning Theory, pages 144--1198, 2018.
[12] Rianne de Heide, James Cheshire, Pierre Ménard, and Alexandra Carpentier. Bandits with many optimal arms. arXiv preprini arXiv:2103. /2452, 2021.
[13] Eyal Even-Dar, Shie Mannor, and Yishay Mansour. Pac bounds for multi-armed bandit and markov decision processes. In International Conference on Computationnl Learning Theory, pages 255-270. Springer, 2002.
[14] Moein Falahatgar, Alon Orlitsky, and Venkatadheerai Pichapati. Optimal sequential maxi- mization: One interview is enough! In International Conference on Machine Learning, pages 2975-2984. PMLR, 2020.
[15] Heitor Murilo Gomes, Jesse Read, Albert Bifet, Jean Paul Barddal, and João Gama. Machine learning for streaming data: state of the art, challenges, and opportumities. ACM SIGKDD Explorations Newsletter, 21(2):6-22, 2019.
[16] Stephen J Herschkorn, Erol Pekoez, and Sheldon M Ross. Policies without memory for the infinite-armed bernoulli bandit under the average-reward criterion. Probability in the Engineering and Informational Sciences, 10:21-28, 1996.
(17) Tianyuan Jin, Keke Huang, Jing Tang, and Xiaokui Xiao. Optimal streaming algorithms for multi-armed bandits. In Proceedings of the 38th International Conference on Machine Learning,
pages 5045-5054, 2021.
[18] Anand Kalvit and Assaf Zeevi. From finite to countable-armed bandits. arXiv preprint arXiv:2105.1072 2021.
[19] Anna Karlin and Eric Lei. On a competitive secretary problem. In Proceedings of the Twenty- Ninth AAAI Conference on Artificial Intelligence, pages 944-950, 2015.
[20] Robert Kleinberg, Aleksandrs Slivkins, and Eli Upfal. Bandits and experts in metric spaces. Journal of the ACM (JACM), 66(4):1-77, 2019.

---

[21] David Liau, Zhao Song, Eric Price, and Ger Yang. Stochastic multi armed bandits in constant space. International Conference on Artificial Intelligence and Statistics, pages 386-394, 2018.
[22] Chi-Jen Lu and Wei-Fu Lu. Making online decisions with bounded memory. In International Conference Algorithmic Learning Theory, pages 249-261. Springer, 2011.
[23] Shanmugavelayuthamm Muthukrishnan. Data streams: Algorithms and applications. Now
Publishers Inc, 2005.
[24] Erol Peköz. Some memoryless bandit policies. Journal of applied probability, pages 250-256, 2003.
[25] Piyush Rai, Hal Daumé, and Suresh Venkatasubramanian. Streamed learning: one-pass svms. In Proceedings of the s international jont conference on Artifical intelligence, pages 1211-1216. 2009.
[26] Herbert Robbins. Some aspects of the sequential design of experiments. Bulletin of the American Mathematical Society, 58(5):527-535, 1952.
[27] Arghya RoyChaudhuri and Shivaram Kalyanakrishnan. Regret minimisation in multi-armed bandits using bounded arm memory. In The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAA/ 2020, pages 10085-10092. AAAI Press, 2020.
[28] Alcksandrs Slivkins. Introduction to multi-armed bandits. Found. Trends Mach. Learn., 12 (1-2):1-286, 2019.
[29] Linqi Song, Jie Xu, and Congduan Li. Active learning for streaming data in a contextual bandit framework. In Proceedings of the 2019 5th International Conference on Computing and Data Engineering, pages 29-35, 2019.
[30] William R Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4))285-294 1933.
[31] Long Tran-Thanh, Lampros Stavrogiannis, Victor Naroditskiy, Valentin Robu, Nicholas R Jennings, and Peter Key. Efficient regret bounds for online bid optimisation in budget-limited sponsored search auctions. Uncertainty Artificial Intelligence, pages 809-818, 2014.
[32] Long Tran-Thanh, Sebastian Stein, Alex Rogers, and Nicholas R Jennings. Efficient crowd- sourcing of unknown experts using bounded multi-armed bandits. Artificial Intelligence, 214:
89-111, 2014.
[33] Zirui Wang, Sanket Vaibhav Mehta, Barnabas Poczos, and Jaime G Carbonell. Efficient meta lifelong-learning with limited memory. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 535-548, 2020.
[34] Xiao Xu and Qing Zhao. Montry-constrained no-regret learning in adversarial bandits. arXiv preprint arXiv:2002.1 1800, 2020.
[35] Indré Žliobaité, Albert Bifet, Bernhard Pfahringer, and Geoffrey Holmes. Active learning with drifting streaming data. IEEE transactions neural networks and learning systems, 25(1):
27-39, 2013.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [No] Our work is theoretical and all
the settings that we study have been clearly described in the paper.
(c) Did you discuss any potential negative societal impacts of your work? [No] Our work is theoretical and we do not see any potential negative societal impact.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you eite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you're you're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "r2pGBpNdjxW", "reviewer": "Reviewer_8qyp", "summary": "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.\nThe paper is focused on a single-pass model, in which after an arm being removed from the memory it can no longer be accessed.\n\nFor 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.\n\nFor 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$.\nThus showing that $log^*(n)$ memory is sufficient for asymptotically optimal sample complexity.\nThey also point out an error in [1] who previously claimed for showing such an algorithm. \n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The model is a very natural variant of the multi-armed bandit problem and is interesting both from the theoretical perspective and the possible practical uses.\nThe authors present two separate results that each is limited by its own and I’m not sure that tying them together is the right way to overcome this issue.\n\nQuestions and comments:\n\nIs there an upper bound for the regret minimization problem that does use additional memory for $m>2$?\nWhat is the known lower bound if we allow several passes?\n\nThe algorithm for the best arm identification problem seems close to the problem of MAB using a few rounds of sampling (where only a small number of arms are qualified for the next round). [2] studied the problem and showed lower bounds on the number of rounds needed for optimal sample complexity. On the other hand, under the assumption that $\\delta<1/n$, [3] show that the optimal sample complexity can be reached using a constant number of rounds. Those techniques may be useful for your model as well.\n\n[1] Sepehr Assadi and Chen Wang. Exploration with limited memory: streaming algorithms for\ncoin tossing, noisy comparisons, and multi-armed bandits. In Proceedings of the 52nd Annual\nACM SIGACT Symposium on Theory of Computing, pages 1237–1250, 2020.\n\n[2] Arpit Agarwal, Shivani Agarwal, Sepehr Assadi, Sanjeev Khanna. Learning with Limited Rounds of Adaptivity: Coin Tossing, Multi-Armed Bandits, and Ranking from Pairwise Comparisons. In Proceedings of the 2017 Conference on Learning Theory, PMLR 65:39-75, 2017.\n\n[3] Avinatan Hassidim, Ron Kupfer, Yaron Singer. An Optimal Elimination Algorithm for Learning a Best Arm. Advances in Neural Information Processing Systems 33 (2020): 10788-10798.‏\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Any societal impact depends on the application.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "qI1InzRDSQ4", "reviewer": "Reviewer_h7sF", "summary": "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. \n\nThe 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.\n\nLet $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.\n\nFor 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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The problem is natural and well-motivated, and the results are strong, so I recommend acceptance.\n\nOne surprising implication of this paper is that having limited memory significantly affects regret-minimization but doesn't affect best-arm identification very much.\n\nI have checked some of the proofs (those that appear in the body) and they seem correct. The inclusion of Theorem 2, which is a weaker version of the paper's lower bound was a good idea. One part of one proof should be adjusted, as I will explain below.\n\nThe paper claims to fix a bug from a STOC'20 paper. While I haven't read that paper and can't verify this claim, I think there is great value in fixing bugs of previous work.\n\nThe paper can be polished a lot more, and I will add some comments below. But it's acceptable as a conference paper.\n\nDetailed comments and suggestions:\n- Don't confuse arm-memory size and space complexity. It makes the paper confusing. Space complexity of an algorithm is a well-defined concept. Your result concern arm-memory size, which has connections with space complexity, but they're not the same. For example, in line 164 you say that UCB1 has space complexity $\\Omega(n)$. But that is irrelevant. What matters is that the arm-memory size is $n$ for UCB1. The constants are important here. Your result holds for arm-memory size smaller than $n$ regardless of the space complexity. That is, even if there is no limit on space complexity but the arm-memory size is smaller than $n$, your lower bound holds. I suggest that you stick to expressing your results in terms of arm-memory size, and don't use $O, \\Omega$ notation because the constants matter for your lower bound. You can have a remark explaining the connection with space complexity.\n\n- The union bound used in Claim 1 and Claim 2 should be changed. Here, you say you are using Lemma 8, which concerns pairs of arms. If you're gonna do a union bound over the pairs, that would give you $c_{\\ell}^2$ events to apply the union bound to. But this would shatter your calculations. What you want to do is to replace Lemma 8 with a lemma stating that each arm has been estimated within certain distance with certain probability, and then you can apply the union bound over the arms rather than pairs of arms.\n\n- The paper title is misleading as you don't give guarantees for regret minimization. A lower bound is not a guarantee.\n\n- Line 72: Your lower bound matches the upper bound *only when $m=2$.* This should be clarified.\n\n- Line 76: The actual dichotomy is between $m=n-1$ and $m=n$. This should be clarified.\n\n- Define the $\\widetilde{O}$ notation.\n\n- Line 110: \"They do not provide a regret bound for their algorithm, hence their regret can become very high.\" I don't understand the deduction here. If I can't prove that regret is small doesn't mean that regret is large.\n\n- Line 136: You say an MAB instance is specified by the arm means. But the distributions are also important, no?\n\n- Line 140: It seems you're restricting the algorithm to store only the mean and the number of pulls for each arm. But your proof doesn't require that; it seems your lower bound is general, regardless of what the algorithm stores. So why do you put such a restriction in your model?\n\n- Line 161: \"distribution\" should be \"randomization\" or \"realization\"\n\n- Line 187: \"We settle the question by showing ...\" You don't really settle the question. You prove a lower bound. Settling the question would mean proving matching lower and upper bounds for all $m$.\n\n- Line 212 to 219: This is not clearly explained. You can just say \"The algorithm doesn't lose anything by first loading the first $m$ arms into its memory.\" This is intuitive enough that all readers will believe you.\n\n- Line 221: Tuple is not a correct word here; use table or sequence.\n\n- Line 297: \"the algorithm returns the arm in the highest level.\" This is not true. The post-processing step is skipped here, which confuses the reader.\n\n- Algorithm 1: The values of $\\varepsilon_{\\ell}$ and $\\beta_{\\ell}$ are never used in the algorithm, so why define them in the pseudocode? Also, the comment of line 4 is very confusing; because the number of arms in level $\\ell$ is either 0 or 1.\n\n- Statement of Claim 1 is confusing. When you say \"an arm is sent,\" do you mean some arm, all arms, or there exists at least one arm? Similarly for Claim 2, and the proof of Lemma 9. The phrase \"an arm\" can mean at least one arm or all arms.\n\n- Statement of Claim 1, \"an arm with reward gap at most $\\varepsilon$ from arm'\" is understandable but can be made easier to understand.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not applicable.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "WbVYm2KGIY9", "reviewer": "Reviewer_EMgB", "summary": "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))$.", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The arrival of arms is poorly explained. Can the authors clarify how do arms arrive in detail? is there a delay between the arms' arrival? is there a probability distribution that governs the arms' arrival? Shouldn't that impact, for instance, the regret lower bound, if the best arm has a low probability of arrival? Furthermore, the authors present Theorem 1, 2, and 3 but all these theorems have the same statement! The authors should state their results in detail.\n\nExisting regret upper bounds have a worst-case regret upper bound of order $\\tilde{O}(\\sqrt{T}$, while the provided lower bound is of order $\\Omega(T^{3/2})$. It can be understood from the authors' result that this is because the class of algorithm over which the lower bound holds is restricted to a single-pass algorithm. Could the author confirm this and provide a discussion on this? Could they also explain how does the single-pass restriction appear in the proof? Furthermore, the algorithm would ensure regret only if the best arm is not played, discarding a suboptimal arm from the memory does not necessarily affect regret. Could the authors explain why observations 1 and 2 hold? for instance according to observation 1, if $\\bar{A_1}$ holds, then $T'> L$, and simply means that the first time algorithm ${\\cal A}$ discards an arm is larger than $L$. It could be a sub-optimal arm, in which case it wouldn't matter or maybe I am missing something. Furthermore, why was $\\epsilon$ chosen to be of order $1/T^{1/3}$, and $L$ chosen to be of order $1/\\epsilon^2$? These choices seem arbitrary, but they are behind the lower bound of order $T^{2/3}$.  Could the authors explain the intuition behind these choices?\n\n\nFor the pure exploration problem, the authors' algorithm is proven to be $(\\epsilon,\\delta)$-PAC and optimal in a mini-max sense (although they do not provide a lower bound) using only $O(\\log^\\star(n))$. It is not surprising that the memory requirement for best arm identification is going to be small, nonetheless, it is interesting to have an algorithm with such a guarantee. However, the minimax guarantee is rather disappointing and does not provide truly an insight into the trade-off of the sample complexity vs. memory complexity. Looking into algorithms that are instance-dependent optimal makes more sense. In fact, one can note that finding a minimax optimal algorithm that is $\\delta$-PAC is an ill-posed problem since one can easily show that the lower bound in the minimax sense is infinite. Perhaps the authors should look at the paper entitled \"Optimal Best Arm Identification with Fixed Confidence\" by Garivier and Kaufmann. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I do not see any potential negative impact of this work. The work is mainly theoretical. ", "review_text": "", "extra_scores": {"ethical_concerns": "I do not see any ethical issues with the current algorithm. The work is mainly theoretical. ", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "17 hours"}, "extra_text": {}}, {"review_id": "Bq3d4q1Fla7", "reviewer": "Reviewer_QqCn", "summary": "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.", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well-written overall with accessible proofs. I really enjoyed reading it. The $\\Omega\\left( T^{2/3} \\right)$ lower bound for single-pass algorithms applies also to a random-order arrival of arms (not just adversarial), which is interesting. I think the paper will certainly add value to the literature in this area.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Though I did not verify each and every step of the proofs very rigorously, the authors provide plenty of intuition and the proofs generally appear correct. The literature review seems to be comprehensive too, though there are a couple of papers I would like to suggest. I recently discovered these works on a related infinite-armed formulation of the stochastic bandits problem (https://arxiv.org/pdf/2105.10721.pdf and https://arxiv.org/pdf/2103.12452.pdf). Cited works show that it is possible to achieve a logarithmic instance-dependent regret if there exists a constant fraction of arms of the optimal \"type,\" and the best and second-best arm-types are \"well-separated\" in the mean-reward, despite an infinite population of arms. More interestingly and relevant to this submission, it is shown that the logarithmic bound can be achieved by algorithms that only store a finite number of arms at any time (as in https://arxiv.org/pdf/2105.10721.pdf), or at worst, logarithmic in the horizon (https://arxiv.org/pdf/2103.12452.pdf). I think these could enrich the discussion.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The committee was divided on this paper and the discussions have highlighted that the despite several writing issues, the paper presents novel and important contributions. We suggest the authors to revise their draft for clarity but we recommend to accept this work to Neurips 2021.
Decision: Accept (Poster)