Lipschitz Bandits in Optimal Space
Authors: Xiaoyi Zhu
Zengfeng Huang
Venue: ICLR 2025 Poster (2025)
Keywords: Space complexity
Lipschitz bandits
Primary area: learning theory

Abstract: This paper considers the Lipschitz bandit problem, where the set of arms is continuous and the expected reward is a Lipschitz function over the arm space. This problem has been extensively studied. Prior algorithms need to store the reward information of all visited arms, leading to significant memory consumption. We address this issue by introducing an algorithm named Log-space Lipschitz bandits (Log-Li), which achieves an optimal (up to logarithmic factors) regret of $\widetilde{O}\left(T^{\frac{d_z+1}{d_z+2}}\right)$ while only uses $O\left(\log T\right)$ bits of memory. Additionally, we provide a complexity analysis for this problem, demonstrating that $\Omega\left(\log T\right)$ bits of space are necessary for any algorithm to achieve the optimal regret. We also conduct numerical simulations, and the results show that our new algorithm achieves regret comparable to the state-of-the-art while reducing memory usage by orders of magnitude.

Published as a conference paper at ICLR 2025
LIPSCHITZ BANDITS IN OPTIMAL SPACE
Xiaoyi Zhu School of Data Science
Zengfeng Huang
School of Data Science
Fudan University Shanghai, China
Fudan University
Shanghai, China huangz E fudan. edu. en
zhuxy22 @m fudan. edu. cn
ABSTRACT
This paper considers the Lipschitz bandit problem, where the set of arms is con- tinuous and the expected reward is Lipschitz function the space. This problem has been extensively studied. Prior algorithms need to store the reward information of all visited arms, leading significant memory consumption. We address this issue by introducing an algorithm named Log-space Lipschitz ban- dits (Log-Li), which achieves an optimal (up logarithmic factors) regret of dett while only uses O (") bits of memory. Additionally,
δ (T
pro- vide a complexity analysis for this problem, demonstrating that Ω (log T") bits of space are necessary for any algorithm achieve the optimal regret. We also con- duct numerical simulations, and the results show that our new algorithm achieves regret comparable to the state-of-the-art while reducing memory usage by orders of magnitude.
INTRODUCTION
In multi-armed bandit (MAB) problem, online algorithm must select from set of strategies over a sequence of n trials, with the objective of maximizing the cumulative payoff of the chosen strategies. These problems form the fundamental theoretical framework for analyzing the trade-offs between exploration and exploitation that are intrinsic to sequential decision- making under condi- tions of uncertainty. Algorithms and methodologies for these problems find successful applications in areas such as online auctions, adaptive routing, and the theory of learning in games (Silver et al., 2016 Schneider & Zimmert 2024).
decision-making
In this paper, we study the Lipschitz bandit problem a specific type of MAB problem where the expected reward is Lipschitz rithms heavily rely on storing the reward statistics (e.g. the number of pulls and the mean reward of an arm observed so far) for the visited arms in the memory. Due the intrinsic assumption in Lipschitz bandit problems that arms belong to a large set, these algorithms need to store information for poly(T) arms, leading to significant space consumption. For instance, the Zooming algorithm Kleinberg et al.] 2008) and Hierarchical Optimistic Optimization (HOO) algorithm (Bubeck et al.) 2011) require OTT) space, while the state-of-the-an A-BLiN (Feng al., 2022) has a space com-
(aatinnouu(Kleinberrg
al. 2008). Existing Lipschitz bandit algo-
plexity of O ( (TogT) 3.47
(d= is the zooming dimension). These space requirements are impractical in many real-world scenarios with high time horizons T, leading to natural question:
What is the memory cost of achieving optimal regret for the Lipschitz bandit problem?
Recently, learning with constrained memory has garnered significant attention due to its myriad practical applications. Extensive research has been conducted in various fields, including kernel Seeger] 2000). convex optinization(Marsdde
et al.) 2022] Blanchard et al. (initthnmMMMiiiakaa al.] (2013). Memory constraints have also been explored in the context of multi-armed bandit (MAB) settings, though most studies have
meehods/Willlanns
2023), and general machine learning
focused on stochastic MAB
streaming setting (Maiti et al. 2021 Jin et al., [021]] Assadi &
Wang 2024). These approaches, however, do not apply to the Lipschitz bandit problem, which
involves an infinite set of arms without a stream.
"Corresponding Author; also affiliated with STI.

---

Published as a conference paper at ICLR 2025
To solve the problem, present novel algorithm, named Log- space Lipschitz(Log Li) that only uses memory of O (log 2') bits space while achieving an optimal regret rate of Ô T Log- Li maintains the empirically best arm and strategically narrows the arm set learn regions of high reward. This suggests the main finding in this paper that, surprisingly. there is almost no tradeoff between regret and space efficiency for the Lipschitz bandit problem. We further complement this result with a lower-bound complexity analysis and show that ! (log 7') is necessary for achieving optimal regret rate. This means that Log-Li is optimal for both space complexity and regret rate.
1.1 PROBLEM DEFINITIONS AND PRELIMINARIES
consider a compact doubling metric space (A, d.a) of arms. Each arm associated a sub- Gaussian distribution where the expected reward f A E satisfies the I-Lipschitz condition that Ip (z1) - μ (x2) I dA (I1, x2) for any 21, 22 E A. For simplicity, we assume the parameter for the subgaussian distribution be extending other value is straightforward.
Let /r = max ((x)) denote the maximal expected payoff. The objective of the algorithm is to minimize regret, defined R(T) Σd= 1= (n" 1 (x,)). For convenience, we define the optimal gap of as A, = μ p(x) for all E
Consistent with other works, restrict our consideration the metric space (10, 1J (H+loo) for simplicity, since we can always embed a doubling space into a Euclidean space with some distor- tion of metric by the Assouad's embedding theorem (Assouad 1983). The ideas underlying our algorithms can be generalized to other doubling metric spaces.
In accordance with previous work, we define the zooming dimension as follows.
Definition 1. For a problem instance with arm A, metric A and expected payoff μ.. Let X, {a E A: A. μ³ μ(x) S <r}. We define the r-zooming number as N,- N (X1er, E), which is the & -packknng number of X The zooming dimension is then defined as
d₂ == min {d 2 0 3a N, or ,,
Moreover, we define the zooming constant C₂
C min {a 0: N, S or VO <r <<<<<
The zooming dimension d, can be significantly smaller if the set of near-optimal arms is "small" in terms of the packing number.
1.2
MAIN RESULTS
This paper investigates the space complexity for the Lipschitz bandit problem and offers both upper and lower bounds.
Space upper bounds. Our main contribution is the introduction of the Log-Li algorithm, which solves Lipschitz bandits using logarithmic space. With the Doubling Edge-length Sequence I'm
d.+1
2-m+1 Log-Li achieves the optimal regret rate of Ô (
using O(log T') bits.
With probability exceeding 1 25, the T-step total regret R(T) of Log-Li with Doubling Edge-length Sequence I'm = m+1 satisfies
Theorem 1.
R(T) < (512C. 16) T
where de is the zooming dimension of the problem instance. Moreover, the space complexity of Log-Li is O(log T) bits.
The details of the algorithm can be found in Algorithm 2 and Algorithm | The proof of Theorem [ can be found in Section 3 The core of bandit algorithms lies in balancing exploration and exploita- tion. Prior research addressed this balance by storing the results of all explored arms. This approach allowed their algorithms to deactivate undesirable regions, thereby limiting the number pulls in these areas and enabling continued exploration in promising directions.
2

---

Published as a conference paper at ICLR 2025
Log-Li, however, adopts a different strategy to reduce space consumption. Instead of deactivating suboptimal regions entirely, it allows revisits to less favorable areas. The frequency of these revisits is controlled based each area's contribution to regret. With careful analysis, the regret rate of dat1
Log-Li Li is shown to be Ö T
+2
In contrast, seminal studies (Kleinberg al., 2008 Bubeck et al. 2011 Feng et al. 2022) demon- strate that the optimal regret bound for Lipschitz bandits without space limitations is R(T) X T (log 7) म. Consequently, Log-Li attains the optimal regret rate for Lipschitz bandits while utilizing minimal space.
Space lower bounds. Our next contribution is the space lower bounds for the Lipschitz bandit.
Theorem 2. Consider Lipschitz bundit problems with time horizon T larger than a large enough constant and zooming dimension d2 I d. Then for any algorithm, the regret bound B[R(T)) S we must have that the space complexity of the algorithm is at least 2 log T bits.
12
Consequently, Log-Li algorithm is optimal in terms of both regret and space. We also conduct numerical simulations in Section [ and the results show that our Log-I.i achieves regret comparable to the state-of-the the-trr- while reducing memory usage by orders of magnitude.
1.3 OTHER RELATED WORK
Prior work MAB. The history of the Multi-Armed Bandit (MAB) problem dates back to Thompson 1933), with sigmificant surge of activity in recent decades. Several notable algorithms, such as UCB (Agrawal 1995). the arm elimination strategy (Even-Dar et al.) 2006 Perchet & Rigol- strategyyEven- let 2013), the greedy method(Auer 2002). the exponential weights and mirror descent frame- Auer al. 2002). have been shown achieve order-optimal cumulative regret. The Lipschitz bandit problem was first introduced Kleinbbbg et al. (2008) and holds significant importance on its own The Zooming algorithm (Kleinberg et al. 2008) and the Hierarchical Optimistic Optimization (HOO) algorithm (Bubeck et al.) 2011) were developed for general doubling metric space.
Learning under limited space. Recently, there has been a surge of work on understanding learning under information constraints such as limited memory communication constraints. One line of research follows the breakthrough paper of Raz (2017), which shows that any learning algorithm for parity problem requires either a memory of quadratic size an exponential number of samples. Subsequent works have extended these techniques to other learning problems, such as linear regres- sion (Sharan et al. 2019) and noisy version of the parity problem (Garg al., (02T). There is also significant work on memory lower bounds for random-order streaming models, addressing problems such entropy estimation (Acharya al. 2019) and the needle problem (Lovett & Zhang 2023).
MAB under limited space. Most works focus on the (stochastic) multi-arm bandit problem in the streaming setting where both regret minimization and pure exploration are studied. The streaming pure exploration MAB was first introduced by Assadi & Wang (2020), and algorithms are proposed to find e-best arms with (11) memory and O pulls. These algorithms were further developed by Assadi & Wang (2022) to achieve eestance-opting sample complexity. For the regret minimization problem, building on earlier algorithms by Liau et al. (2018); Chaudhuri Kalyanakrishnan (2020), Agarwal et al. (202)) provided upper and lower regret bounds that are tight in 7. The lower bound was further improved by Li et al. (2023). Additionally, there is another line of work focusing on the closely related expert learning problem (Srinivas et al., 2022 Peng & Zhang 2023).
2 ALGORITHM
With space constraints, the agent only has knowledge about constant number of arms in the envi- ronment. To fully learn the landscape of the reward, the agent must keep exploring different regions of the arm set. Since the agent forgets information about most regions, it may revisit areas that have previously been eliminated, leading to sub-optimal regrets. To overcome this problem, we gradually partition the regions of the arm set and perform exploration in iterative deepening manner.
Log-Li operates based on finite partitions of the arm space. To keep exploring while avoiding con- sistent visits suboptimal areas, control the maximum depth the algorithm search in each
3

---

Published as a conference paper at ICLR 2025
round. The algorithm must start from depth I each round, as it has already forgotten which areas were previously eliminated. This process may cause redundant visits to undesirable regions. To mitigate this problem, the algorithm maintains the empirically best arm in the last round and uses to perform arm elimination. This strategy prevents us from searching too deeply in suboptimal areas. By carefully designing partitions and determining the number of pulls for each round, effectively control the overall regret. The learning process is summarized in Algorithm | and
Algorithm 1: Logarithmic Space Lipschitz for Each round (RoundFune)
Input: Time horizon 7' current time I; maximum depth vn; current depth h; current cube C: comparison arm reward fim-1; current round max reward f7"
if + > T then
L return Play arm "C,
th C.r. from C. Collect the rewards of these pulls VC, M. and -imh VC.
compute the average payoft iy (C)
h equals to m then L Compute jtnh max {ū (.T
else
pmm po (C)- 4ry then
Equally partition current cube into (FR/rR41)) subcubes and define as the collection of these subcubes.
foreach subcube B E do RoundFunc ni: m, B. ".
else Eliminate the cube C implicitly by ending the recursion.
Algorithm 2: Logarithmic Space Lipschitz(Log-
Input: Arm set = [0, 1]5; time horizon T. Initialize:
Error probability Number of rounds B; Edge-length sequence {rm] B+1, current time /. = 0: comparison arm reward ji0 = 0
Compute 7ym 16 (Tg6))))
for m 1,2,
for m 1,2, ... B do
Equally partition A
1 17
subcubes and define B as the collection of these subcubes.
Set p=m= for each subcube B E B do RoundFunc(T, t, m, 1, B, pm )m).
Cleanup: play the arm corresponding p=n until all T steps are used.
running example of Log-Li can be found in figure T In each round, Log-Li starts from depth 1 and re-examines the rewards of the cubes. By leveraging the empirically best reward from the last round, we can eliminate suboptimal areas (dark cubes) at the same depth as the previous round without significantly impacting our regret. Simultaneously, we collect rewards from the promising regions (white cubes) for further exploration.
It is worth mentioning that the partition process in the algorithm is detailed explicitly for clarity and comprchension. In practice, the algorithm only requires iterating over the newly partitioned subcubes sequentially, without the need explicitly store information for each individual subcube.
Moreover, The overhead running time the algorithm is O(T) since at each time stamp we simply collect reward and compare it with T In comparison, the time complexity of the Zooming Algo- rithm (Kleinberg et al. 2008) is ( while the time complexity of the HOO algorithm
Bagritth/Bubbckk Bubeck
al. 2011) is O(7 |og
4

---

Published as a conference paper at ICLR 2025
Figure 1: Runing example of Log-L.. The ith subfigure reflects the results after the ith round. The dark cubes are the eliminated areas and the white cubes are regions with decent rewards the maximum depth of the current round.
3 SPACE AND REGRET ANALYSIS
In this section, we provide space regret analysis for Log-Li. The highlight of the finding is that Ollog 7') bits are sufficient to achieve optimal regret rate of Ô (T T
d.+1
summarized Theorem
3.1 SPACE ANALYSIS
We would start with the space analysis which is more straightforward.
Lemma 1. Algorithm Sa and consumes Ollog T) bits.
Proof. Note that at each timestamp, Algorithm and Sonly needs to store:
The id and the empirical mean of the best arm in the last round j²""!
The id and the empirical mean of the best arm in the current round ftm
The id and the empirical mean of the current running arm P. (C.)
Since the number of subcubes we may run bound by T, we can use log bits to encode the id of each subcube. For the empirical mean, need store the number of pulls and the sum of the rewards, which are both bound by T since reward of each pull less than 1. Therefore, we can encode the empirical mean in log bits. The total bits consumed by Algorithm and is bound by 3 x (log T + 2 log 7) = O(log 7') bits.
3.2 REGRET ANALYSIS
In this subsection, we would prove the regret upper bound of Log-Li with Doubling Edge-length Sequence Y' = 2 m+1 Compared to previous research, Log-Li permits revisits less favorable directions, which may result in additional regret. However, we will manage the number of these revisits by controlling the number of rounds to ensure that the overall regret remains bounded.
Consistent with other studies, first show that the estimator ğu is concentrated to the true expected reward i (Lemma 2). In the following analysis, we let Bsoo be the total number of rounds and Ar, be the set of cubes we visit when the depth is h in round
Lemma 2. Define
3 = (m(o)) [n(0)-AA(( (C) S +
16 (Tg(T//)
V1 < h < m S B Bunp - 1,VC E A Vx EC
holds that IP(E)= 2 25.
5

---

Published as a conference paper at ICLR 2025
Proof.
Fix any cube C' E Ag,, have
E VO. E(AN(()
Eis
Di=l
(ar.a)
P% (C)
nh
Since (,,(C)) (C) E [07, (C)] obeys subgaussian distribution with parameter inequality
_, ni
Applying Hoeffding
16log(T/6)
20
P (C)
P (C))I 2
S
7
By the Lipschitz condition of y that [ [2 (C) p(x)) Th. Vx C, have
16 1hh
28 7
IP
sup (u(x) #EC
13 (C) S +
2 1
Any cube C' E An is played for not less than time, and thus [A4]) I T. On the other hand, there most B Bstop T rounds. Taking union bound over C' E A and I h S m S Bsuo would have that holds with probability at least 25.
We then show that the optimal arm survives all eliminations with high probability (Lemma 3
Lemma 3. Under event & (defined in Lemma 2), the optimal arm x² = arg max p(x) is not elimi- nated in any round.
Proof. Fix any round m [B]. We (CT")* to denote the cube containing xt in Ag We will show that (CT))* is not eliminated in depth h for 1 h 1. Under event E, for any cube
C E A== and C, we have
16 log (T/0))
16 16log(T/8) nh
" 1 (C) - pxx ((CK)") S m(x)
+ rm-1 (x-))++++++++++
+ th
Mm-1
I 2r 2- + 2rm $ 4rh-
where the second inequality holds for n'm
16 (T/8) and the last inequality holds for decreasing
r2.
property of Doubling Edge-length Sequence. By the elimination rule, (CTr)" not eliminated.
Based on lemma 2 and
control the loss of cubes in each depth.
Lemma 4. Under event & (defined in Lemma 2 for any < h S m S Bste any C E AD and
any C, Ar satisfies
A < 8TA-1
Proof. We again fix any round m E [B). For h 1, this is straightforward from the Lipschitz condition of μ.. For h > 1, let (Cm=l) be the cube in Am=l such that x² E (Cm=l)² This cube (Cm=1)" is well-defined under & by Lemma For any cube C E ATT and x E C, it is obvious that x is also in the parent of C (the cube in the previous depth that contains C)), denoted as Cpar For any x C, have
16 (Tg(
16 logg(()))) +Tk-1-
A - ---x(((xx)) -==1
((m==1)))
11 - (Cper J+/
7m
n1
Due to our choice of nm
16log(T/8)
we have
r
pm ((mm=1)")
1//11 (Cpar) 2r + 2r
((mm=l)")
1 (Cpar) 4rh-1;

---

Published as a conference paper at ICLR 2025
where the last inequality holds from the decreasing property of Doubling Edge-length Sequence. It is obvious that #1=1 (C==)))" - p²-- Since the cube Cpar is not eliminated, we can easily
derive the following from the elimination rule
A I 4r + 4r S 8r
We are now ready to prove Theorem
Proof of Theorem ! Let R. denote regret of the m-th round. Fixing any positive number B, the total regret R(T) can be divided into two parts: R(T) = Em B Rm + + Rm- In the following, we bound two parts separately and then determine B to obtain the upper bound the total regret.
We firstly fix any round Recall that AN," is set of the survived cubes in depth h. According to Lemma for any x E Uceeg C, we have A₂ I 8ra-1 = 16rr. Each cube in Ar, is a || -bbll with radius 2, and is a subset of S (16r)). Therefore, AW, forms ("2) -packing of S (16rx), and the definition of zooming dimension yields that
A S Nr. C2rn S C,2
where the last inequality holds since = 2 h+1 The total regret of the m-th round is
16 log(T/o)
Rm
A
167
h= CEAM 1=1
h=1
m
256 log (T/6)
m
2.2th-1)ds
C.2 256 log(T
Th
Therefore, we have
m
Σ Rm = Σ
C.2 (,2(h-1((d,+)) (1) .10o4+)))266...g... (56log(T/6)
MSB
mSB h=1
Σ (B- 1B- mSB
256log( (1)))
By standard calculation, we should have that for any real number a,
Σ B m + 1)a"
MSB
Σ (B 1)aa
Σ
ma (B+1)
Σ an
B
a
B+1
1
m
a
0 B
MSB
mSB
m
1
B
B+1
B
1+++
Σ m
B+1 <
B+++
B+ 1+
B+1
a-1
0
a
a
a B+1
1
20 B
a-1
which gives that
Σ Rm = 256C' log(T/8) (d+++1
Σ m m 1) (2id.tu))
MBB
mSB
< 512C' log (T)() 2 (
On the other hand, Lemma implies that the arm corresponding to B must satisfy that A S 16 2 B Therefore, we finally have
8r 16r
R(T)
Σ Rm + Σ Rm < 512C. log(T/8) 2 (B11)(+++)) 16 2--22-B-1 B+1T.
m
m>

---

Published as a conference paper at ICLR 2025
This inequality holds for any positive B. By choosing 8* log Ionl
we have
d.
R(T) & (512C, + 16) T T (log(T/6)) -..2.
SPACE LOWER BOUND
In this section, we present space lower bounds for Lipschitz bandit problem as summarized in The- orem 2 Essentially, Theorem 2 says that if we want to achieve the optimal regret bound, we must consume at least 22log 7' bits. Similar to most works, we would first construct problem instances that are difficult to differentiate and then prove lower bounds on these instances.
4.1
HARD CASE
and K C2 T_ Here C₂ is small enough constant satisfying by the definition of zooming dimension, we can find set of arms U = {uI,'" ... _x. such that d (u;, Uz) 2 for any # j. Then we consider a set of problem instances
We would construct a set of problem instances that are difficult to distinguish. Let
7'
(-1.-.. Lx }. The expected reward for 4, is
= {
1 + r, if Wér
(x(x)=
max (2:)) d(æ,, uz)) otherwise.
Note that here we would have that log dr e, log O(log
4.2 PROOF OF THEOREM 2
We consider the "best-cube identification" problem that after t rounds, the algorithm outputs a cube Ye prediction for which cube is optimal (has the highest mean reward). For this problem, may find that if our space is small, the prediction quality will be very poor.
Lemma 5. Consider "best-cube identification" " problem with K 2 10 and space complexity less than _ log(K), (. Then there exists at least K cubes that, for problem instances in Section 4.1
3
Pr 1y, i I,
Proof. We consider that summing up all the instance cases and use M to denote the memory state.
Pr ly: = i
Pr ly, = il M m, m. I, Pr M m I+]
i=1
K
Pr [yt = m] Pr[M = m I
Pr [yt = M mm]
K
Σ
M
Pr(ye- = M = m]] Σ 1 1 log(K)
K²_
X 1=1
T7
where the second equation holds since the prediction determined by the memory state, and the last inequation is due our bound of space complexity. To prove the lemma, assume for contradiction that we have more than 2K cubes with Pr [ye 3
I
Z 3. We would have that I.
2K
3 1 K> K
Σ Priy -
2
where the last inequation holds for K 2 10 and leads to the contradiction.
8

---

Published as a conference paper at ICLR 2025
Lemma jimeediaell implies this corollary.
Corollary 1. Consider a "best-cube identification" problem with K 2 10 and space complexity less than 2 l. Choose a cube uniformly at random, and run the algorithm on instance Ii.
Then Pr [ye + 2 1. where the probability over the choice of cube i, the randomness in rewards and the algorithm.
12'
Proof. By Lemma
5, we can find a set A such that
3 V A. 2
K
Pr I
4
Since we choose the cube uniformly at random, we would have that
K Pr [y #
K
1 2
Pr Pr(ye + 1) Z
Σ iEA
Pr lye +
I
K
3
4
12
Finally, we use Corollary D to finish our proof of space complexity.
Proof of Theorem
2 For T larger than large enough constant, we would have that K
c,T 2 10. Assume for contradiction that we have space complexity less than log(K). ()). Fix round I, Let us interpret the algorithm as a "best-cube identification" algorithm, where the predic- tion is the closest u, to the arm that the algorithm chooses. Note that here choosing the closet us will only decrease the regret by our hard instance setting. We can apply Corollary to have that Pr [y, * i| 12. words, the algorithm chooses non-optimal cube with probability least and choosing a non-optimal cube will incur A(y:) = μ 14(2 = regret. Therefore,
T B[R(T)) 2 Σ (
= Σ Pr [v + 1 1=1
T
r
T
1
2
T
d
12 T
12
which leads to contradiction.
EXPERIMENTS
20
39
14
10
19
16
08 15
T1
(0.3, 0.1)
Ø1 (0.8, 0.7)
T1 = (0.45, 0.55) 22 00.1,
12 (0.9.
22 (0.7, 0.3)
Figure 2: the landscape of μ.
In this section, we evaluate the Log-Li algorithm. the experiment, the time horizon T 100, 000. the arm space is [0, 1]2 and the expect reward function is μ(xz)
| -1112 0.5 || x ll for different values of xı and T2. The landscape of μ can be found in figure where the optimal arm is always at x² ø1 We select A (een et al. (022) and Z Kleinberg et al., 2008) for comparison. Zooming algorithm achieves an optimal regret rate but with relatively high time complexity of ( and space complexity of O(T); A-BLiN delivers performance comparable
to the Zooming algorithm while utilizing space proportional to O (r dat1
(T (log T) 2: and op-
erating in (T)) time. We will compare the regret rate and space complexity of three algorithms to illustrate the sublinear trend of regret and space efficiency of algorithm.

---

Published as a conference paper at ICLR 2025
(0.3, 0.1) 42 = (0.9, 0.9)
(0.8, 0.7) 22 = (0.7, 0.3)
(0.45, 0.55)
22 = 0.9)
Figure 3: The cumulative regret v.s. time horizon t.
words
Logel ASLM Zooming
Figure 4: Number of words Saved by Log-Li, A-BLiN and Zooming for Different
Figure 3 iillsstrates the performance of the three algorithms under different expect reward μ.. When t small, all of the three algorithms are in their initial exploration phases, leading to similar perfor- mance. As increases, the performance of Log-Li tends to be relatively worse compared to the other two algorithms because restarts the search from depth each time save space consumption. This could also be reason why Log-Li experiences increases in regret during the latter stages and exhibits more instability during the exploration process. However, we should also notice that as the search progresses further, Log-Li Li ultimately achieves sublinear regret curve, with growth trend similar to that A-BLiN. This indicates that the regret rate Log-Li is asymptotically optimal with limited space, which is consistent with analysis in section
We also report the space usage the three algorithms in figure is clear that Log-Li significantly reduces the number of arms needed save and thus consumes much less space. It is noteworthy that this gap will further widen as the time horizon T increases because Log-L_i needs to save information about only 3 arms regardless of T, whereas the other algorithms require saving statistics of an increasing number of arms as T grows.
CONCLUSIONS
In this study, we explore the space complexity for the Lipschitz bandit problem, presenting both upper and lower bounds. Our algorithm, Log-Li, is proven to achieve the optimal regret rate using only Ollog T) bits, whereas prior algorithms require poly(T) bits. This significant improvement in space efficiency greatly reduces memory costs and suggests that there is almost tradeoff between regret and space efficiency for the Lipschitz bandit problem. Furthermore, the space lower bounds for the Lipschitz bandit indicate that achieving the optimal regret bound necessitates consuming at least (log T) bits. Hence, Log-Li is optimal terms of both regret and space. We also conduct experiments to visualize the performance of our algorithm Log-Li. Our work provides novel insights into designing memory- memory-llmitee bandit algorithms. would be valuable to apply the principles of Log-Li other related bandit problems.
10

---

Published as a conference paper at ICLR 2025
7
ACKNOWLEDGEMENTS
This work supported by National Natural Science Foundation China No. 62276066, No.
U2241212.
REFERENCES
Jayadev Acharya, Sourbh Bhadane, Piotr Indyk, and Ziteng Sun. Estimating entropy of distributions in constant space. Advances in Neural Information Processing Systems, 32, 2019.
Arpit Agarwal, Sanjeev Khanna, and Prathamesh Patil, A sharp memory-regret trade-off for multi- pass streaming bandits. In Conference Learning Theory, pp. 1423-1462. PMLR, 2022.
Rajeev Agrawal. Sample mean based index policies by (log n) regret for the multi-armed bandit problem. Advances in applied probability. 27(4):105--1078, 1995.
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, pp. 1237-1250, 2020.
Sepehr Assadi and Chen Wang. Single-pass streaming lower bounds for multi-armed bandits ex- ploration with sestacc-sensiiive sample complexity. Advances Neural Information Processing Systems, 35:33066-33079, 2022.
Sepehr Assadi and Chen Wang. The best arm evades: Near-optimal multi-pass streaming lower bounds for pure exploration in multi-armed bandits. The Thirty Seventh Annual Conference on Learning Theory, pp. 311-358. PMLR, 2024.
Patrice Assouad. Plongements lipschitziens dans R". Bulletin de la Société Mathématique de France, 111::229 1983.
Auer. Finite-time analysis of the multiarmed bandit problem, 2002.
Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire. The nonstochastic multi- armed bandit problem. SIAM journal on computing, (2(1):48-71 2002.
Moise Blanchard, Junhui Zhang, and Patrick Jaillet. Memory-constrained algorithms for convex optimization via recursive cutting-planes. arXiv preprint arXiv:2306. 10096, 2023.
Sébastien Bubeck, Rémi Munos, Gilles Stoltz, and Csaba Szepesvári. X-armed bandits. Journal of Machine Learning Research, 12(5), 2011.
Arghya Roy Chaudhuri and Shivaram Kalyanakrishnan. Regret minimisation in multi-armed bandits using bounded arm memory. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp- 10085-10092. 2020.
Eyal Even-Dar, Shie Mannor, Yishay Mansour, and Sridhar Mahadevan. Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. Journal of machine learning research, 7(6), 2006.
Yasong Feng, Tianyu Wang, et Lipschitz bandits with batched feedback. Advances in Neural Information Processing Systems, 15819686-19848 2022.
Sumegha Garg, Pravesh K Kothari, Pengda Liu, and Ran Raz. Memory-sample lower bounds for learning parity with noise. arXiv preprint arXiv:2107.02320, 2021.
Tianyuan Jin, Keke Huang, Jing Tang, and Xiaokui Xiao. Optimal streaming algorithms for multi- armed bandits. In International Conference on Machine Learning, pp. 5045-5054, PMLR, 2021.
Robert Kleinberg, Aleksandrs Slivkins, and Eli Upfal. Multi-armed bandits in metric spaces. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pp. 681-690, 2008.
Shaoang Li. Lan Zhang, Junhao Wang, and Xiang- Yang Li. Tight memory-regret lower bounds for streaming bandits. arXiv preprint arXiv:2306.0rr 306000000.7, 2023.

---

Published as a conference paper at ICLR 2025
David Liau, Zhao Song, Eric Price, and Ger Yang. Stochastic multi-armed bandits in constant space. In International Conference on Artificial Intelligence and Staristics, pp. 386-394. PMLR, 2018.
Shachar Lovett and Jiapeng Zhang. Streaming lower bounds and asymmetric set-disjointness. In 2023 IEEE 64th Annual Symposium Foundations of Computer Science (FOCS), pp. 871-882. IEEE, 2023.
Arnab Maiti, Vishakha Patil, and Arindam Khan. Multi-armed bandits with bounded arm-memon arm-memory: Near-optimal guarantees for best-arm identification and regret minimization. Advances Neural Information Processing Systems, 34:19553-19565 2021.
Annie Marsden, Vatsal Sharan, Aaron Sidford, and Gregory Valiant. Efficient convex optimization requires superlinear memory. In Conference on Learning Theory, pp. 2390-2430. PMLR, 2022.
Ioannis Mitliagkas, Constantine Caramanis, and Prateek Jain. Memory limited, streaming pea.
Advances in neural information processing systems, 26, 2013.
Binghui Peng and Fred Zhang. Online prediction in sub-linear space. Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrele Algorithms (SODA), pp. 1611-1634, SIAM, 2023.
Vianney Perchet and Philippe Rigollet. The multi-armed bandit problem with covariates. The Annals of Statistics, 4 41(2):693-721, 2013.
Ran Raz. A time-space lower bound for a large class of learning problems. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pp. 732-742. IEEE, 2017.
Jon Schneider and Julian Zimmert. Optimal cross-learning for contextual bandits with unknown context distributions. Advances in Neural Information Processing Systems, 36, 2024.
Vatsal Sharan, Aaron Sidford, and Gregory Valiant. Memory-samplee tradcoffss for linear regression with small error. Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pp. 890-901, 2019.
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Mare Lanctot, et al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):844488, 2016.
Vaidehi Srinivas, David P Woodruff, Ziyu Xu, and Samson Zhou. Memory bounds for the experts problem. In Proceedings of the 54th Annual ACM SIGACT Symposium Theory of Computing. pp. 1158-1171, 2022.
William R Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika,
1933.
Christopher Williams and Matthias Seeger. Using the nyström method speed up kernel machines. Advances in neural information processing systems, 13, 2000.
12


Reviews:
[{"review_id": "HK3vw9SOuk", "reviewer": "Reviewer_KiQN", "summary": "This paper introduces the Log-space Lipschitz bandits (Log-Li) algorithm to address high memory usage in the Lipschitz bandit problem by achieving optimal regret with only O($\\log T$) bits of memory. Next the paper provides a space lower bound for the Lipschitz bandit\nproblem showing that the algorithm is optimal in terms of both regret and space.", "questions": "- This is regarding the novelty of the analysis. The authors say \"Similar to prior research, Log-Li identifies and removes the undesirable region of the arm set while exploring and partitioning the remaining area\". Could the authors provide references for these prior research. Further could the authors also provide more details on the novelty of the analysis, how it differs from existing analysis and where, if any have they used modifications of existing results.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is well written - provides adequate motivation and highlights the technical challenges involved.\n- To the best of my knowledge, the proofs in the main paper seem fine.\n- The space complexity improvement is significant and makes the solution practical.", "weaknesses": "No major weakness.", "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": "", "extra_scores": {}}, {"review_id": "vNauH9wHPK", "reviewer": "Reviewer_VDg4", "summary": "This paper introduces a new algorithm for the Lipshitz bandit problem which uses only $O(\\log T)$ bits of memory while achieving an optimal regret of $O(T^{\\frac{d_{z} + 1}{d_{z} + 2}})$. It also showed that $\\Omega(\\log T)$ bits of space are necessary for any algorithm to achieve optimal regret. Finally, it numerically showed that the proposed algorithm is superior to an existing method in terms of regret while reducing memory usage sifnificantly.", "questions": "- Related to the second weakness above, it seems Log-Li uses a large memory space when we partition the arm set (Line 176). How much memory does the algorithm consume in this procedure? Does it exceed memories than that used to store information of each arm?\n- Isn't the \"for loop\" in Line 194 computationally heavy? In my understanding, the size of $\\mathcal{B}$ is exponentially large in $d$, and therefore hurts the computational complexity of the Algorithm.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The proposed algorithm named Log-Li (Log-space Lipschitz) algorithm achieves an optimal regret rate in the Lipschitz bandit problem while using a memory of $O(\\log T)$ bits space. This is a significant improvement compared to other existing methods, which have to store information of $poly (T)$ arms. They also showed that using $O(\\log T)$ bits is unavoidable if we want to achieve an optimal regret rate. From above, the Log-Li algorithm is optimal in terms of regret and space, which is the contribution of this paper.", "weaknesses": "- The only algorithm that is compared to the Log-Li algorithm is the A-BLiN algorithm. Even though other existing methods use poly(T) bits of memory space, I believe it is still necessary to empirically compare cumulative regret with them. \n- In line 176, Log-Li algorithm generates $(\\frac{r_{h}}{r_{h + 1}})^{d}$ subcubes, which possibly consume large amount of memory.\n- The log-Li algorithm has a larger cumulative regret than an existing method empirically.\n\n[Missing citation]\n- Stefan Magureanu, Richard Combes, and Alexandre Proutiere. Lipschitz Bandits: Regret Lower Bound and Optimal Algorithms. COLT2014.\n\n\n[Minor comments]\n- The authors should refer to the definition of $d_{z}$ in the abstract.\n- Periods are missing, and upper and lower case letters are mixed inappropriately.\n  - P9 Figure 2-> \"The landscape of $\\mu$.\" \n  - P10: Figure 4 \"Logarithm of number of words saved by Log-Li and A-BLiN for different $\\mu$.\"\n  - Line 178:  Space between \"for\" and \"each\"\n  - Lines 99, 208, 380: \"theorem\"-> \"Theorem \"", "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": "", "extra_scores": {}}, {"review_id": "slTA0Mr2fl", "reviewer": "Reviewer_pV8P", "summary": "This paper proposed a novel algorithm, “Log-space Lipschitz bandits” (Log-Li), which reduces space complexity to $O(\\log T)$ from $O(T)$ while achieving near-optimal regret, for the the Lipschitz bandit problem.", "questions": "My detailed questions are as follows:\n\n1. My first question is about the claimed \"optimal regret\" in this paper. As indicated in Weakness 3, the regret bound is almost linear with a large zoom dimension $d_z$. If this is the optimal upper bound, does it mean that no algorithm can achieve sublinear regret for Lipschitz bandit in high-dimensional spaces?\n\n2. What is Doubling Edge-Length Sequence  $r_m$? And why do we need to set it as  $2^{-m+1}$? \n\n3. Corollary 1 implies that with  $K \\geq 10$ , the probability of non-optimal cube selection exceeds  $\\frac{1}{12} $. How would this probability scale as  $T$  grows large? Would the required cube size in terms of $K$ or arm space expand as  $T$ increases, potentially impacting the algorithm’s ability to achieve optimal regret in very high-dimensional spaces? \n\n4. In Lemma 2, you define the event  $E$  to bound the difference between the estimated and true expected reward. However, the analysis assumes that each cube in  $A_h^m$  has been played sufficiently to approximate rewards accurately. Could you clarify how this holds in scenarios with very large or complex arm spaces where  |$A_h^m| $  is substantial? Would the regret increase under limited play-per-cube situations, and if so, how could this impact your regret bound?\n\n5. The paper states that Log-Li’s arm elimination rule requires revisiting previously eliminated areas. In practical terms, this leads to redundant exploration of suboptimal regions, increasing regret. Is there an analytical way to quantify the regret incurred from this repeated exploration? Could adding memory to store limited past elimination history potentially reduce these redundancies?", "limitations": "", "rating": 3, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "1. This paper proposed a novel algorithm (Log-Li), which reduces space complexity to $O(\\log T)$ from $O(T)$ while achieving near-optimal regret. \n\n2. It shows that the regret achievable with this minimal memory is near optimal. \n\n3. The paper includes theoretical proofs for the space and regret bounds of the algorithm, complemented by experimental results demonstrating that Log-Li maintains regret close to other state-of-the-art algorithms but with significantly lower memory usage.", "weaknesses": "There are several weaknesses in the current manuscript. \n\n1. The authors acknowledge that Log-Li’s regret is higher and more variable than the benchmark algorithm A-BLiN (as shown in Fig .3) due to memory limitations, requiring repeated exploration of suboptimal regions.  This means that Log-Li cannot guarantee the regret performance if the required memory decreases.\n\n2.  The evaluation is too weak to support the claim made in this paper. It only compares with one benchmark algorithm and the performance of the proposed Log-Li is even worse than that of the benchmark algorithm. \n\n3. The regret bound is highly dependent on the zooming dimension  $d_z$ . If  d_z  is large, the regret bound  $O(T^{\\frac{d_z + 1}{d_z + 2}})$  grows close to linear in $ T$ , suggesting that the Log-Li algorithm may struggle with higher-dimensional spaces. The analysis would benefit from a more in-depth exploration of how the zooming dimension affects both regret and space efficiency in high-dimensional spaces.\n\n4. The presentation of the current manuscript is extremely poor and unfriendly to readers. Though this reviewer may misunderstand the main technique and theoretical results, the poor presentation is an outstanding issue. From this reviewer's point of view, it is way below the standard.", "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": "", "extra_scores": {}}, {"review_id": "Fncdv9v1d4", "reviewer": "Reviewer_6qq4", "summary": "The paper considers the problem of continuous armed bandit for a reward function which is Lipschitz over the action space. This setting is already well studied in the literature, and optimal regret guarantees are already well-known. The novelty of this work stays in proposing al algorithm which is also efficient on the point of view of the space complexity. \nIn fact, the authors show both that their algorithm enjoys order $\\log(T)$ space complexity (in number of bits) and that this is the lower bound for the setting.", "questions": "1. Indeed, to achieve a regret bound of order $T^\\alpha$ for any bandit setting, one has to be able to allocate numbers with a precision of at least $T^{\\alpha-1}$, as a larger misspecification would compromise the regret bound. This already takes $O(\\log(T))$ bits. Does it make the lower bound for the space complexity trivial?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "The topic of the paper is very interesting. The setting is very interesting, and the space complexity is indeed a limitation of previous approaches for this setting.\n\nThe contribution is valuable, and the idea of the paper could bring an impact also outside of the bandit literature.", "weaknesses": "Despite I have really appriciated this work, which I think brings a valuable contribution to the bandit community, I am also convinced that this is a little bit immature for a publication at this conference.\n\nI have reached this conlusion after reading many passages of the paper which, in my opinion, need to be deepened.\nFor example,\n 1. In Theorem 1, the result seems to hold with a probability of $1-T^{-5}$. I was rather surprised about this, as most of the other regret bounds in this field fix a given $\\delta>0$ and show that the regret is bounded by some function of $T$ multiplied by $\\sqrt{\\log(1/\\delta)}$. At first, I tought this was because the authors were using some given technique which goes outside from usual concentration bounds used in the bandit literature. But in fact, looking at the proof of the result, it seems to me that the proof could be adapted to hold with high probability, as usual. Even if the result is correct, putting the statement in this form could affect the possibility of using this result for future work, and create confusion.\n 2. The paper assumes that all arms distribution are Gaussian, even if this assumption is never used except at line 263, where in fact only _subgaussianity_ is used. Again, introducing this (very restrictive) assumption without a reason creates unnecessary confusion in anybody needing to use the results of this paper.\n 3. Line 277 \"By similar argument to Lemma F.1 in Sinclair et al. (2020) and Lemma 1 in Lu et al. (2019), taking a union bound over C ∈ Amh\nand 1 ≤ h ≤ m ≤ Bstop finishes the proof\" is not sufficiently precise to be used in a proof\n 4. The proof of the space complexity bound seems to ignore the fact that the algorithm has also (according to line 192) to allocate the subcubes and to remember which of theme have already been visitied. By the way the pseudocode is written this seems to take order $2^d$ bits, and it is not clear if it can be done in less space.\n\nIn the end, I am not against the acceptance of this work, but I'm wondering if it is in the interest of the author to publish it like this or if it is better to clarify and improve the mentioned passages.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)