Lipschitz Bandits in Optimal Space

Thank you for communicating these questions to us. We will clarify them in the following and improve our presentation in the camera-ready version.

Response to W1

Thank you for pointing this out. We will adapt the results and proof to hold with high probability in our future versions.

Response to W2

Thank you for pointing this out. We do not require the Gaussian assumption; sub-Gaussian conditions are sufficient to meet our requirements. The confusion was caused by a writing error, which we will correct in future versions.

Response to W3

Thank you for pointing this out. We will add more explanations of this point in future versions to make the proof clearer.

Response to W4

The way we wrote our pseudocode is intended to help readers clearly understand how we partition our set. In practice, our algorithm doesn't need to pre-allocate the subcubes but only needs to traverse them one by one. Since the maximum number of subcubes we will access is T, we only need to maintain the IDs for these T subcubes.

Response to Q1

To achieve the desired regret bound, it is indeed necessary to estimate the expected reward with a specified additive error. However, this requirement does not directly imply a space lower bound. Consider the coin problem: for difference as small as $n^{-0.306}$, there are functions that can amplify this value to a constant using only $O(\log \log n)$ bits [1]. Similarly, in our problem, while precision is important, proving the non-existence of such functions is essential. Our proof take a different aspect by connecting the lower bound with the number of hard instances, which provides a more intuitive understanding and complements our limited-space algorithm.

[1] Braverman M, Garg S, Zamir O. Tight space complexity of the coin problem[C]//2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2022: 1068-1079.

I thank the authors for their rebuttal.

The consideration about the coin problem is interesting, but I did not found in the paper the result mentioned by the authors, so I would like to ask them which is it and how does it apply.

Still, about the lower bound if this paper, I try to clarify my reasoning. Let us say that we have just the easier problem of best arm identification, so that it is sufficient to output $x_T$ such that $|x_T-x_*|$ is small.

If we consider the set of reward functions

$f_a(x)=-|a-x|\qquad x\in (0,1),$

where the optimal arm of $f_a(\cdot)$ is $a$. We can see that to guarantee $|x_T-x_*|<T^{\alpha-1}$ in every case (this must hold for $\alpha \in (0,1)$, and, being a one-dimensional Lipschitz class precisely with $\alpha=2/3$ to match the lower bound), we need to distinguish at least $T^{1-\alpha}$ instances. This requires at least $\log(T^{1-\alpha})=(1-\alpha)\log(T)$ bits.

Thank you for communicating these questions to us. We will clarify them in the following and improve our presentation in the camera-ready version.

Response to W1 & W2

The core of our paper is theoretical analysis. We first prove that the regret of our algorithm, Log-Li, is asymptotically optimal. Based on this, the primary purpose of our experiments is to verify the correctness of our theoretical conclusions, so we focus more on the trend of regret for our algorithm. From our experimental results, it is evident that the regret of our algorithm is indeed asymptotically optimal, which aligns with our expectations. Moreover, our algorithm only uses a constant number of words.

According to our theoretical results, there might be constant differences compared to other algorithms; however, the differences are not significant. Empirically, since we are only concerned with the trend, we have not fine-tuned the parameters of our algorithm. It is possible that by adjusting the parameters, we could achieve better experimental results, but this is not our main focus.

Response to Q1

The regret lower bound is proved to be $R(T) = \Omega(T^{\frac{d_z+1}{d_z+2}})$[1]. This lower bound indicates that any algorithm for the Lipschitz bandit problem will incur at least this amount of regret. Therefore, according to our theoretical analysis, the regret of Log-Li is already asymptotically optimal.

[1] A. Slivkins, “Contextual bandits with similarity information,” J. Mach. Learn. Res., vol. 15, pp. 2533–2568, Jan. 2014.

Response to Q2

We denote $r_m$ as the edge length because it corresponds to the side length of each subcube in our partition. We describe it as doubling since it decays at a rate of 1/2. We chose this particular edge-length sequence to achieve the desired optimal regret rate in our regret analysis. Due to space constraints, our algorithm inevitably re-explores incorrect directions; using this sequence helps us control the additional regret from these erroneous explorations.

Response to Q3

Your first point of view is incorrect and this probability will not scale as T grows large. Our proof for the lower bound of space complexity does not depend on the size of T. As demonstrated in our proof, regardless of the size of T, as long as K>10 and space complexity less than $\frac{1}{2}\log K$, our Corollary 1 holds.

As T increases, our cube size decreases and the number of K increases. You can see this specifically in the construction of our hard instance (line 394). This is because as T increases, the allowed error decreases, requiring us to more precisely characterize the landscape of reward and thus increase the space requirement(increase by $\log(T)$).

Response to Q4

Your point is incorrect; we do not need each cube to be played sufficiently. In Lemma 2, our estimation range for the true reward is related to the number of times we play each arm, denoted as $n_h$. If the number of plays for a particular cube is small, the estimation range is wider; if the number of plays is large, the range is narrower. Regardless of the number of subcubes, the total number of arm plays is T. Therefore, using the union bound, our Lemma 2 always holds. Consequently, the regret bound we obtain under event E is always valid with high probability.

Response to Q5

In the theoretical analysis section, we carefully analyzed all the components of regret caused by Log-Li in each round (line 338). Under our carefully chosen edge sequence, the extra regret incurred is also within the $O(T^{\frac{d_z+1}{d_z+2}})$bound.

Adding memory is definitely helpful because it allows us to retain information about previously explored subcubes, reducing exploration in incorrect directions. However, the main focus of our work is on theoretical analysis, and experimental results are not our primary concern.

We would like to thank the reviewer for communicating these questions to us. We will clarify them in the following and correct the citation and grammar issues in the camera-ready version.

Response to missing citation & minor comments

Thank you for pointing that out. We will further refine and edit the text.

Response to W1 & W3

The primary focus of our paper is on theoretical analysis. We begin by demonstrating that our algorithm, Log-Li, achieves asymptotically optimal regret. Consequently, the main aim of our experiments is to validate the accuracy of our theoretical findings, which is why we concentrate on observing the trend of regret in our algorithm. Our experimental results clearly show that the regret of our algorithm is asymptotically optimal, confirming our expectations. Furthermore, our algorithm operates using only a constant number of words.

While our theoretical results suggest there may be differences when compared to other algorithms, these differences are not large. Since our empirical focus is on the overall trend, we did not fine-tune the parameters of our algorithm. Although parameter adjustments might yield improved experimental outcomes, this is not our primary concern.

Response to Q1

We still present our partitioning in the algorithm this way to make it easier for readers to understand how we perform the partition operation on the set. In the actual algorithm, our algorithm only needs to iterate through the newly partitioned subcubes one by one, without needing to explicitly store information for each of them. Our algorithm only needs to store information about 3 arms, therefore it only requires $O(\log T)$ space.

Response to Q2

The "for loop" in Line 194 does not incur significant computational overhead. We explicitly include "for loop" over all subcubes in our algorithm just to help readers understand our partitioning method. Considering what we do at each time step from 1 to T, we simply collect a reward and occasionally update $\tilde{\mu}^{m}$. These actions do not result in substantial computational overhead.

Thank you for communicating these questions to us. We will clarify them in the following and improve our presentation in the camera-ready version.

Response to Questions

Since arms belong to a very large set in our problem, it is a classic approach to gradually partition the set to learn the landscape of the reward function, such as in [1,2]. Our algorithm also employs this design, resulting in similarities to past algorithms. In the analysis of previous algorithms, to control the regret caused by exploring in the wrong directions, they managed this by saving all explored arms and promptly eliminating and marking them. This strategy helped limit the number of explorations in unpromising directions. However, this strategy fails in our setting because we can only store information for a constant number of arms and will experience some inevitable repeated exploration in incorrect directions. The novelty of our analysis lies in the control of these extra regrets which is not typically seen in analyses of previous algorithms. By improving our search strategy and making the proper choice of the edge sequence of partitions, we show that even with this additional regret, we can still achieve the desired optimal regret bound.

[1] 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.

[2] Yasong Feng, Tianyu Wang, et al. Lipschitz bandits with batched feedback. Advances in Neural Information Processing Systems, 35:19836–19848, 2022.