Efficient Algorithms for Lipschitz Bandits

Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 15:14:08

Abstract: Lipschitz bandits is a fundamental framework used to model sequential decision-making problems with large, structured action spaces. This framework has been applied in various areas. Previous algorithms, such as the Zooming algorithm, achieve near-optimal regret with $O(T^2)$ time complexity and $O(T)$ arms stored in memory, where $T$ denotes the size of the time horizons. However, in practical scenarios, learners may face limitations regarding the storage of a large number of arms in memory. In this paper, we explore the bounded memory stochastic Lipschitz bandits problem, where the algorithm is limited to storing only a limited number of arms at any given time horizon. We propose algorithms that achieve near-optimal regret with $O(T)$ time complexity and $O(1)$ arms stored, both of which are almost optimal and state-of-the-art. Moreover, our numerical results demonstrate the efficiency of these algorithms.

Main paper: 
 our contributions: 
 Our primary insight revolves around two key aspects: metric embedding and pairwise comparisons.Metric embedding involves mapping elements from one metric space to another while preserving distance relationships as closely as possible. Our algorithm effectively maps the metric space to a tree, where each node represents a cube. Traversing this tree is analogous to navigating the entire metric space. Pairwise comparisons of arms reduce memory complexity. Instead of constantly covering the entire space, our approach considers all subcubes as a stream. From this stream, we continuously select cubes for pairwise comparisons, gradually converging to the optimal region.Overall, our contribution lies in pioneering memory-efficient algorithms for large structured action spaces, particularly within Lipschitz metric spaces. We introduce the MBUD and MBAD algorithms, which achieve near-optimal regret while requiring storage for only the best-estimate arm for exploitation and one additional arm for exploration. This means only two arms need to be stored in memory, regardless of the problem's scale. Furthermore, each algorithm exhibits O(T ) time complexity, indicating that their execution time scales linearly with the number of rounds.Lipschitz bandits. Multi-armed bandits is one of the most classical frameworks to model the trade-off between exploration and exploitation in online decision problems. The Lipschitz bandits framework considers the large, structured action space in which the algorithm has information on similarities between arms. The model was first introduced by Agrawal (1995) with interval [0, 1].The near-optimal upper and lower bounds for the worst case were provided in Kleinberg (2004) via the uniform discretization strategy. Subsequent work (Kleinberg et al., 2019) proposed the zooming algorithm, achieving near-optimal instance-dependent regret for the problem and studying the extension for the general metric action space. Several other works have established regret bounds for the stochastic reward feedback setting (Bubeck et al., 2011a; Magureanu et al., 2014; Lazaric et al., 2014) . Other works have also extended the results to the adversarial version (Podimata & Slivkins, 2021; Kang et al., 2023) , contextual setting (Slivkins, 2014; Krishnamurthy et al., 2019; Lee et al., 2022) , ranked setting (Slivkins et al., 2013) , contract design (Ho et al., 2014) , federated X-armed bandit (Li et al., 2024a,b) , and other settings (Bubeck et al., 2011b; Lu et al., 2019; Wang et al., 2020; Grant & Leslie, 2020; Feng et al., 2022; Xue et al., 2024) .Memory-efficient learning. Another line relevant to this paper is online learning with memory constraints. Liau et al. (2018) considered stochastic bandits with constant arm memory and proposed an algorithm achieving an O(log 1/∆) factor of optimal instance-dependent regret, where ∆ is the gap between the best arm and the second-best arm. Chaudhuri & Kalyanakrishnan (2020) studied stochastic bandits with M stored arms and showed there is an algorithm with regret Õ(KM + (K 3/2 √ T )/M ). Subsequent work (Agarwal et al., 2022) provided an algorithm achieving regretO( √ KT log T log log T ).In addition to the bandits problem, there are also many works about other online learning problems. Srinivas et al. (2022) ; Peng & Zhang (2022) showed the trade-off between regret and memory for the expert problem. More pure exploration models with memory constraints were considered in Assadi & Wang (2020) , including the coin tossing problem, noisy comparisons problem, and Top-K arms identification. Previous works on bandits with limited memory have not considered structured action spaces and could not deal with infinite actions. There are some other works on memory-efficient online learning (Peng & Rubinstein, 2023; Assadi & Wang, 2023b) . Beyond the online learning setting, the memory-efficient learning problem was solved in different situations, including statistical learning (Steinhardt et al., 2016; Garg et al., 2017; Raz, 2017; Garg et al., 2019; Sharan et al., 2019; Lyu et al., 2023) , convex optimization (Marsden et al., 2022; Blanchard et al., 2023a,b; Chen & Peng, 2023) , estimation problems (Acharya et al., 2019; Diakonikolas et al., 2022; Berg et al., 2022) , parity learning (Raz, 2019; Kol et al., 2017) , and other learning problems (Hopkins et al., 2021; Brown et al., 2022; Chen et al., 2022) . 
problem setup and preliminaries: 
 Notations. In this paper, we use bold fonts to represent vectors and matrices. For a positive integer T , we use [T ] to denote the set {1, 2, . . . , T }. For a set X , we use |X | to denote its cardinality. For a random variable Z, we use E[Z] to denote its expectation. For an event E, we use P[E] to denote its probability.We formally define the Lipschitz bandits problem below. Given T rounds, dimension d, and arm space We use regret to measure the performance of the algorithm compared with the expected total reward of the best-fixed arm in action space X : R XX = [0, 1] d , each(T ) = T • sup x∈X µ(x) -E t∈[T ] r t .Then we present the memory model employed in the paper. The algorithm operates by selecting arms from the memory and pulling them. When the memory reaches the capacity and the algorithm attempts to choose a new arm, it becomes necessary to discard at least one arm from the memory.Consequently, any statistical information associated with the discarded arm, including its index, mean reward, and number of pulls, is forgotten and will not be retained thereafter. We measure the space complexity of the algorithm by the hard constraint for the number of arms stored in the memory. This constraint aligns with the assumption of having oracle access to the input arm, as commonly defined in streaming problems.Then we provide some technical tools that are used in this paper and introduce the covering dimension and zooming dimension for one action space X . We use the definitions in (Slivkins, 2019) and provide them below. Notice that the Lipschitz bandits problem is defined in an infinite-action space. We select a fixed, finite discretization actions space S ⊂ X . Let {X 1 , . . . , X N }[X i ⊂ X ] be an cover of the action space X . Let ϵ denote the maximum diameter of X i for all i ∈ [N ]. Then the arm setS = {x i |x i ∈ X i , i ∈ [N ]} is an ϵ-mesh.The covering dimension d of the action space X is definedas d = inf α≥0 {|S| ≤ ϵ -α , ∀ϵ > 0}. Let µ * X := sup x∈X µ(x)denote the expected per-round reward of the optimal arm in space X and ∆(x) := µ * X -µ(x) denote the gap between arm x and the optimal arm. Define Y j = {x ∈ X : 2 -j ≤ ∆(x) < 2 1-j , j ∈ N}, then set Y j contains all arms whose gap is between 2 -j and 2 1-j . Consider the ϵ-mesh S j for space Y j . Then the zooming dimension d z for the action space X isd z = inf β≥0 |S j | ≤ ϵ β , ϵ = 2 -j , ∀j ∈ N .Covering dimension is a property of the action space while the zooming dimension is a property of the instance. Notice that we always have d z ≤ d. This is because the covering dimension considers the ϵ-mesh of the entire action space X , whereas the zooming dimension focuses only on the set Y j .The covering dimension is closely related to other notions of dimensionality in a metric space, such as the Hausdorff dimension, capacity dimension, and box-counting dimension, all of which characterize the covering properties in fractal geometry. Similarly, the zooming dimension is another measure used to evaluate the structure of a metric space. Both of these dimensions are widely utilized in the field of Lipschitz bandits. For further details and alternative formulations regarding the covering dimension and zooming dimension, refer to (Kleinberg et al., 2019) .Question: Does the paper discuss the limitations of the work performed by the authors? Justification: Yes, the paper provides all the necessary details for anyone to reproduce the main experimental results, ensuring transparency and allowing others to validate the claims and conclusions independently.Guidelines:• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.• If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.• Depending on the contribution, reproducibility can be accomplished in various ways.For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.• While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility.In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 
warm up: uniform discretization algorithm: 
 This section provides the intuition, specification, and theoretical analysis of the Memory Bounded Uniform Discretization (MBUD) algorithm (shown in Algorithm 1) for the stochastic Lipschitz bandits problem.Algorithm overview. To facilitate our discussion, we begin by outlining the core idea behind the algorithm. This algorithm employs a uniform discretization strategy and adopts an Explore-First methodology, which endeavors to identify a near-optimal arm following the exploration phase and dedicates the remaining rounds to exploitation. Throughout the exploration stage, the algorithm allocates two units of memory space: one for storing the best-estimated arm and another for temporarily holding a newly read arm. Note that the best-estimated arm serves a dual purpose: it is not only crucial for the exploitation phase but also enables the swift identification of sub-optimal arms.The exploration phase in Algorithm 1 is divided into ⌈log log T ⌉ phases, further structured into two main segments: the 'cross exploration phases' and the 'summarize phase'. During the initial ⌈log log T ⌉ -1 phases, the algorithm iterates over the arms within the discretized action space to minimize regret. Exploration is limited to a subset of cubes at a time, allowing the algorithm to gather information about the optimal arm while minimizing regret. In the final phase, termed the 'summarize phase', the algorithm revisits all arms within the uniform discretization space. Overall, each arm is read into memory twice to ensure thorough evaluation. Furthermore, we implement a budgeting strategy for each phase, wherein the total number of pulls across all arms is constrained by a predefined budget. The goal is to select the optimal arm with high probability after accumulating sufficient information during the previous phases. This structured approach balances exploration and Algorithm 1 Memory Bounded Uniform Discretization (MBUD)Input: arm space X = [0, 1] d , time horizon T , parameter c.1: y ← 0, ry ← 0, n y ← 0, B -1 ← 1, ϵ = log T T 1/(d+2), ϕ ← ⌈log log T ⌉ -1.2: for p = 0, • • • , ϕ -1 do 3: B p ← T B p-1 . 4: for q = 1, • • • , ⌊ϕϵ -d ⌋ do 5:Generate a new cube C ← CROSSCUBE(ϕ, ϵ, p, q), and select a arm x from C.(y, ry , n y ) ← COMPARE(c, x, y, ry , n y , ϵB p ).end for 8: end for 9:for q = 1, • • • , ⌊ϵ -d ⌋ do 10:Generate a new cube C ← GENERATECUBE(ϵ, q), and select a arm x from C.(y, ry , n y ) ← COMPARE(c, x, y, ry , n y , ϵB ϕ-1 ). 12: end for 13: Play arm y until the end of the game.Algorithm 2 CROSSCUBE Input: number of phases ϕ, edge-length ϵ, parameters q.1:κ 1 ← max k∈N {k d ≤ ϕ}, κ 2 ← max k∈N {k d ≤ ⌊ϕϵ -d ⌋}. 2: Let node ← ϵG d (p, κ 1 ) + ϵϕ √ d G d (q, κ 2 ), then the cube could be determined by node and ϵ.exploitation under memory constraints, aiming to quickly identify the optimal arm while minimizing the sampling of suboptimal arms. The specifics of this approach will be detailed subsequently.Exploration strategies. For the cross exploration phases, the gap between neighboring arms is ϵϕ (ϕ defined in Algorithm 1). There are O(ϵ -d ) cubes (arms) in the discretization action set, which is an ϵ-mesh of X . Each cross exploration phase will only explore O For the summarize phase, the gap is ϵ and all cubes in the discretization set are explored.The CROSSCUBE function generates cubes for the cross exploration phases by calculating parameters based on the number of phases and the edge-length of the cubes. Specifically, CROSSCUBE generates a new cube using a combination of two geometric sequences. It first calculates the parameters κ 1 and κ 2 as the maximum integers such that k d ≤ ϕ and k d ≤ ⌊ϕϵ -d ⌋, respectively. The function then determines the cube's position using these parameters and the edge-length ϵ. The cube is defined by a node position generated by ϵG d (p, κ 1 ) and ϵϕ √ d G d (q, κ 2 ), where G d is a geometric sequence generator that converts an integer to a d-dimensional vector. The GENERATECUBE function is similar to CROSSCUBE but is used during the summarize phase to generate cubes without considering the phases. It calculates the parameter κ as the maximum integer such that k d ≤ ⌊ϵ -d ⌋. The cube is then determined by the edge-length ϵ and a node position generated by ϵG d (q, κ).Compare strategy. Then we introduce the compare strategy, which is also useful for the MBAD algorithm described in the following section. The algorithm always selects the arm with the fewest pulls in the memory. After sufficient samples, it will eliminate one sub-optimal arm based on its upper confidence bound and then generate a new arm (i.e., read a new arm into the memory). Notice that the algorithm may prioritize two sub-optimal arms with a small gap. Therefore, there is a cap on the number of pulls each phase for any arm. It helps the algorithm in striking a balance between exploration (read a new arm) and exploitation (play arms in memory).The algorithm maintains three statistics for one arm in memory: the index x, the mean reward estimator rx , and the number of pulls n x . The constant c is an exploration and exploitation balancing parameter. In the exploration part, there are ⌈log log T ⌉ phases. Let B p be the budget of samples for the p-th phase. We use y and x to denote the best-estimated arm and the new arm in the algorithm, Algorithm 3 GENERATECUBE Input: edge-length ϵ, parameters q.1: κ ← max k∈N {k d ≤ ⌊ϵ -d ⌋}.2: Let node ← ϵG d (q, κ), then the cube could be determined by node and ϵ.Algorithm 4 COMPARE Input: constant c, arm x and y, ry , n y , b.1: rx ← 0, n x ← 0. 2: while n x ≤ b or n y ≤ b do 3:Pull the least played arm between x and y. If there is no single least played arm, select a random arm.Update rx , n x , ry , n y .5:if min{r x + (c log T )/n x , 1} < max{r y -(c log T )/n y , 0} then 6:Break and return (y, ry , n y ).7:else if max{r x -(c log T )/n x , 0} > max{r y -(c log T )/n y , 0} then 8:Break and return (x, rx , n x ).end if 10: end while 11: Return (y, ry , n y ).respectively. If the upper confidence bound (UCB) of arm x is less than the lower confidence bound (LCB) of arm y, then x is suboptimal with high probability. If the LCB of y is less than the LCB of arm x, then x is not too bad with high probability. For the remaining cases, we could choose either x or y, and we choose arm y at the end of the algorithm.Flowchart. In Appendix A.1, we include a flowchart that illustrates the operation of the algorithm.Theoretical result. The computational workload of the MBUD algorithm is characterized by a constant per-round operation, leading to a total time complexity of O(T ), where T represents the number of rounds. Regarding space complexity, the MBUD algorithm necessitates the storage of merely two arms in memory at any given time. Additionally, the space requirements for the GENERATECUBE and CROSSCUBE subroutines are minimal, each consuming O(1) units of space in terms of arm storage. Consequently, the overall space complexity of the algorithm is O(1).We provide the theoretical result below and provide the details of the theoretical analysis in Appendix B. The result recovers the worst case regret in previous work and recovers the lower bound up to a logarithmic factor (Kleinberg, 2004) .Theorem 1. For the stochastic Lipschitz bandits problem with metric (X , D) and time horizon T , where X = [0, 1] d and D is a known metric function. Algorithm 1 uses O(1) stored arms and achieves regretR X (T ) ≤ Õ(T d+1 d+2 ),where d is the covering dimension of space X .The theoretical analysis is mainly based on the 'clean event', which holds that the observed mean average is a good estimator for the expectation with high probability. At a high level, the analysis shows that the deviation between the mean estimator of the best-estimated arm y and the optimal expected reward µ * X is small enough when p ≥ 1. Then the sub-optimal arms could be discarded quickly, which helps us to bound the incurred regret of sub-optimal arms and the exploitation phase.We bound the expected regret during all time horizons by considering the discretization error, the incurred regret of all sub-optimal arms during the exploration, and the sub-optimality of the selected arm before the exploitation together. 
adaptive discretization algorithm: 
 This section provides the main idea, specification, and theoretical analysis of the Memory Bounded Adaptive Discretization (MBAD) algorithm (shown in Algorithm 5).Input: time horizon T , constant c.1: y ← 0, ry ← 0, n y ← 0, B 1 ← √ T . 2: for p = 1, 2, . . . do 3: x ← 0, rx ← 0, n x ← 0, b p ← B p • log T T 1/(d+2) . 4: ADAPTIVECUBE(4, 1). 5: B p+1 ← B p log T . 6: end for Algorithm 6 ADAPTIVECUBE Input: parameters m, q, edge-length ϵ = 2 -m . 1: κ ← max k∈N {k d ≤ ⌊ϵ -d ⌋}.2: node ← ϵG d (q, κ), then the cube C could be determined by node and ϵ.3: Select a arm x from C. 4: if q + 1 ≤ 2 m and the output of COMPARE(c, x, y, ry , n y , 20ϵ -2 ) is arm y then 5:check the next cube with parameters m and q + 1.6: else if 20ϵ -2 ≤ b p then 7:(y, ry , n y ) ← COMPARE(c, x, y, ry , n y , 20ϵ -2 ).Equally partition the cube C into 2 d subcubes and check the first subcube. 9: end if Algorithm overview. We begin with some intuitions. The MBUD algorithm achieves near-optimal regret in the worst case but fails to leverage the beneficial structure of 'nice' problem instances.To address this, we present the MBAD algorithm, which is based on adaptive discretization, and establish a near-optimal instance-dependent upper bound. The idea behind adaptive discretization is straightforward: the algorithm should focus more on promising regions. For instance, the zooming algorithm approximates the expected rewards over the action space and explores more in regions with a high probability of yielding high rewards. However, due to memory constraints, the algorithm cannot obtain a comprehensive picture of the action space over time. To overcome this obstacle, the MBAD algorithm employs a "round robin" strategy, storing the best-estimated arm as the next read arm in memory. Unlike the MBUD method, which chooses predetermined steps, the MBAD algorithm selects the next read arm based on the confidence radius of the arms in memory. Consequently, steps are smaller and probes (newly picked arms) are more numerous in promising regions.Exploration strategies. The ADAPTIVECUBE subroutine is the cornerstone of the MBAD algorithm, functioning as a recursive mechanism to navigate and leverage a cubic region within the decision space. This procedure dynamically adjusts the exploration granularity based on observed rewards and predetermined sampling constraints. Initially, the algorithm selects a cube C for exploration. If this cube is deemed sub-optimal compared to the optimal estimated arm stored in memory (denoted as arm y), the algorithm discards this cube in favor of exploring a subsequent cube, following the generation rules outlined in the GENERATECUBE subroutine described in the MBUD algorithm (Section 3). Conversely, if the cube shows promise, the algorithm proceeds to explore within it, subdividing it into smaller subcubes for more detailed exploration. Each exploration phase is governed by a specific sample budget, which regulates the granularity of exploration to prevent excessive sampling of sub-optimal arms in the early stages. This adaptive exploration process continues until the entire action space has been thoroughly explored. The decision-making process is inherently dynamic, constantly evolving based on past actions to enhance the efficiency of future exploration and exploitation efforts.To prevent the MBAD algorithm from "over-zooming", we implement two stop conditions. The first condition discards the current cube in favor of a new one once we are highly confident that the current cube is inferior to the best cube we've explored (see lines 4-5 of Algorithm 6). The second condition sets a lower bound on the edge length of the cube to be explored in each round, which gradually decreases as exploration progresses (see line 6 of Algorithm 6). These conditions together ensure the algorithm avoids over-zooming. In the initial learning phase, our knowledge of the optimal cube is limited, making it challenging to effectively distinguish suboptimal cubes using only the first stop condition. However, the second condition, with a larger initial lower bound on cube edge length, prevents over-zooming. As the learning process advances, the algorithm can more reliably eliminate suboptimal cubes, thus avoiding over-zooming on them.Flowchart and algorithm description. Due to page limitations, Appendix A.2 contains a flowchart illustrating the operation of the algorithm along with its description.Theoretical result. Analyzing the space complexity of the MBAD algorithm and its ADAPTIVE-CUBE subroutine requires careful consideration due to the subroutine's recursive nature. Specifically, the conditional logic that triggers further recursion or partitioning into 2 d subcubes adds layers of complexity. Within the ADAPTIVECUBE subroutine, each recursive invocation contributes to the call stack, with space consumption directly proportional to the recursion depth. The space required to sustain the state of each cube, alongside the recursive call stack within ADAPTIVECUBE, implies a complexity that scales linearly with recursion depth, complemented by constant overheads for variables preserved at each recursion level. Nonetheless, the algorithm's design allows for the direct computation of all parent and neighboring cube information from the current cube's coordinates and edge length, obviating the need for multiple cube storage in memory. Consequently, only a single cube needs to be maintained at any time during the ADAPTIVECUBE process, affirming a space complexity of O(1) for the MBAD algorithm. This space complexity analysis directly informs the algorithm's time complexity. Similar to the MBUD algorithm, the overall time complexity of the MBAD algorithm remains linear with respect to the total number of rounds.As a by-product of the MBAD algorithm, we introduce a simpler, more practical algorithm for scenarios where d z ≤ 1. Detailed descriptions and theoretical analyses of this algorithm can be found in Appendix D. We provide the theoretical result below and elaborate on the details of the theoretical analysis in Appendix C. The result establishes the optimal instance-dependent upper bound, up to a logarithmic factor, for the stochastic Lipschitz bandits problem. Previous works (Slivkins, 2014; Kleinberg et al., 2019) have already established related lower bounds, indicating that our work achieves near-optimal regret. While there are other forms of results, such as those presented in work (Magureanu et al., 2014) , we believe that adopting one form is sufficient to demonstrate the near-optimal performance of our algorithm.Theorem 2. For Lipschitz bandits with time horizon T and Lipschitz constant L, Algorithm 5 withc ≥ 5 achieves regret R X (T ) ≤ Õ(T dz +1 dz +2 ),using O(1) stored arms, where d z is the zooming dimension of space X .We also mainly consider the clean event. The algorithm plays in a 'round-robin' manner. There are at most O(log T ) phases because of the delicate design of the budget for each phase. For each phase, we show that the deviation between the mean reward of the best-estimated arm and optimal expected per-round reward µ * X is small. Then the algorithm could approximately adjust the sub-optimality of arms and set more probes in more promising regions. Then we prove that the incurred regret could be bounded by O(Tz+1 z+2 (log T ) 2 z+2) by bounding the pulls of bad arms according to the definition of zooming dimension. 
numerical evaluations: 
 In this section, we show the efficiency of our algorithms through a series of numerical simulations.The baseline consists of three algorithms: the uniform discretization with UCB1 algorithm (UD) and the zooming algorithm. For the uniform discretization, we pick a fixed ϵ-mesh of the action space and run the UCB1 algorithm only considering the finite uniform discretization action space. The UCB1 algorithm is a popular algorithm for achieving near-optimal regret with finite action space. Kleinberg (2004) prove that the uniform achieves optimal worst-case regret up to logarithm factors.The zooming algorithm (Kleinberg et al., 2019) is an implementation of the adaptive discretization strategy, which deploys more probes in regions deemed more 'promising'. Theoretical analysis shows that the zooming algorithm both achieves optimal worst-case regret and instance-dependent regret up to logarithm factors. We set X = [0, 1] and choose the reward function f (x) = 0.5 -|x -0.5|. In each round t, the algorithm plays one arm x t and receives a stochastic reward y satisfyingy =    f (x) + ξ, 0 ≤ f (x) + ξ ≤ 1 1, f (x) + ξ > 1 0, f (x) + ξ < 0 .Specifically, ξ ∼ N (0, 0.1 2 ) is the Gaussian noise. The MBAD algorithm are only allowed to store two arms in memory, while there is no memory constraint for the UD+UCB1 algorithm and the zooming algorithm. All results are averages over 50 runs. Figure 1 Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [No] Justification: We plan to release this information after the paper's publication. 
conclusion and discussion: 
 We consider the Lipschitz bandits with limited memory problem. We introduce two novel algorithms:the Memory Bounded Uniform Discretization (MBUD) algorithm and the Memory Bounded Adaptive Discretization (MBAD) algorithm, which are predicated on the principles of uniform and adaptive discretization, respectively. Theoretical analyses reveal that the MBAD algorithm achieves nearoptimal performance with O(1) stored arms and O(T ) time complexity, highlighting its efficiency and practical applicability. Moreover, numerical results show the efficiency of our algorithms.The Lipschitz bandit problem in higher dimensions is often perceived as a 'needle in a haystack' problem. Intuitively, finding the optimal solution in such high-dimensional spaces seems extremely challenging, but this perception does not always hold in practice. Many scenarios reveal beneficial structures within Lipschitz bandits, which is why our research emphasizes not only worst-case regret but also instance-dependent regret. Our proposed algorithm achieves nearly optimal time and space complexity for both worst-case and instance-dependent regrets.In practical applications, Lipschitz bandit problems are found in areas such as non-parametric estimation, model selection in machine learning tasks, and decision-making processes in robotics and games. Furthermore, research on Lipschitz bandits has inspired algorithmic advancements in other domains, such as decision trees and tree-based methods, where the principles from Lipschitz bandit algorithms guide the splitting and growth of trees. Despite these advancements, certain limitations remain. High-dimensional Lipschitz bandits can still pose significant computational challenges, especially in cases where the underlying structure is less apparent or more complex. Additionally, the requirement for sufficient exploration to accurately estimate the optimal arm can lead to increased computational overhead in large action spaces.Our algorithm introduces a novel framework that efficiently addresses online decision-making and balances exploration and exploitation in Lipschitz action spaces. This framework leverages beneficial structures in the problem space to enhance performance while maintaining computational efficiency.We hope our approach could make a substantial contribution to the community, especially in areas that require efficient and effective decision-making under uncertainty. C by calculating parameters κ 1 and κ 2 and determining the cube's position using the edge-length ϵ.An arm x is then selected from the cube C. The COMPARE function evaluates the selected arm against the current best-estimated arm y, updating y if necessary based on the comparison of their upper and lower confidence bounds. In the final phase, known as the summarize phase, the algorithm revisits all arms within the uniform discretization space. For each q from 1 to ⌊ϵ -d ⌋, the GENERATECUBE function generates a new cube C without considering the phases, using a parameter κ to determine the cube's position. An arm x is selected from this cube and compared against the current best-estimated arm y using the COMPARE function, ensuring thorough evaluation. The algorithm culminates by selecting the best-estimated arm y and playing it for the remaining rounds until the end of the time horizon.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes] Justification: The paper clearly outlines essential information needed to understand the results.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.• The full details can be provided either with the code, in appendix, or as supplemental material. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). 
experiment statistical significance: 
 • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)• The assumptions made should be given (e.g., Normally distributed errors).• It should be clear whether the error bar is the standard deviation or the standard error of the mean.• It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.• For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).• If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes] Justification: The paper gives clear details on the computer resources needed for each experiment.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.• The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.• The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.• The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.• If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).• At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
crowdsourcing and research with human subjects: 
 Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?Answer: [NA] Justification: The paper does not involve crowdsourcing nor research with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.• Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.• For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
: 
 One general approach to solving Lipschitz bandits is through discretizing the structured action space.Algorithms based on uniform discretization have been shown to achieve optimal worst-case regret up to a logarithmic factor (Kleinberg, 2004) . Another strategy, adaptive discretization, progressively 'zooms in' on more promising regions of the action space, yielding near-optimal problem-dependent regret (Kleinberg et al., 2019) . However, existing algorithms like the Zooming algorithm necessitate O(T ) stored arms in memory and O(T 2 ) time complexity for stochastic Lipschitz bandits (Kleinberg et al., 2019; Feng et al., 2022) , which may be impractical for many real-world applications. In this paper, we consider a typical scenario where the learner operates within the stochastic bandits framework over a Lipschitz action space while facing constraints on the number of arms that can be stored in memory.The limited memory constraint and large structured action space present several challenges, necessitating a nuanced approach to effectively balance exploration and exploitation under uncertainty. One key challenge is the propensity to over-exploit suboptimal arms retained in memory, leading to high regret. Conversely, reading new arms into memory risks discarding potentially valuable arms. In scenarios with infinite actions, the vast search space requires numerous samples to ensure adequate exploration. The structured nature of the action space demands that algorithms focus on zooming in on more promising regions, but space constraints limit the learner's capacity to acquire comprehensive knowledge about the metric space. Traditional full-memory algorithms start by dividing the action space into many small subcubes, a process known as discretization. Each cube is treated as an arm, and in each round, the algorithm updates the average estimate of the selected cube's reward based on feedback. It then compares this estimate against all other cubes in the storage space through various computational methods. 
 
 Appendix: The MBAD algorithm dynamically adapts its discretization of the action space, focusing more on promising regions to identify the optimal arm with high probability. The flowchart effectively demonstrates how the algorithm narrows down the search space through adaptive discretization.Initially, the algorithm sets up the necessary parameters and variables. During the cross-exploration phases, the ADAPTIVECUBE function generates and selects arms from cubes. Arrows indicate the process of moving to the next cube if y remains the best arm, and the selection and evaluation of subcubes when the comparison budget condition is met. Let S denote the ϵ-mesh of the action space where ϵ = log T T 1/(d+2). Similarly, the discretization error is the gap of the best fixed arm benchmarks between two spaces:D X (S) = T • sup x∈X µ(x) -T • sup x∈S µ(x).Then the regret could be rewrote asR X (T ) = R X (T ) + D X (S).We call D X (S) the discretization error and it could be bounded byD X (S) ≤ T ϵ ≤ T d+1 d+2 (log T ) 1 d+2 .In the rest of this subsection, we shall proveR S (T ) ≤ Õ T d+1 d+2.For any fixed arm x ∈ S, with probability 1 -T -c :EQUATIONBy a union bound for all arms and all rounds, (1) holds for all arm x t ∈ S, t ∈ [T ] with probability at least 1 -T 4-c . To ease the reading, we assume c = 5. We call this 'clean event' and let E denote it. Then we analyze the regret based on the clean event. Let R p S denote the regret for the p-th phase.Consider R 0 S , because the number of pulls of all arms in phase 0 is bounded by ϵB 0 , we haveR 0 S ≤ 2 √ T / log log T.Then we consider R p S , p ∈ [ϕ -1]. Let µ * S := sup x∈S µ(x) denote the expected per-round reward of the optimal arm in space S. Let x * p and µ * p denote the optimal selected arm during phase p and its expected per-round reward, respectively. From the definition of uniform discretization and Lipschitz condition, we haveµ * S -µ * p ≤ log T T 1/(d+2)log log T.(2) for all phase p ∈ [ϕ -1]. To ease the reading, defineΦ := log T T 1/(d+2) log log T.For phase p, we consider the best estimate arm y at the start of the p-th phase. If x * p-1 is discarded in phase p -1, according to the stop condition of compare strategy, we haveEQUATION)For arbitrary discarded arm x, let R p x and N p x denote the accumulated reward and total number of pulls during phase p, respectively. Notice that the value of ry -(5 log T )/n y is non-decreasing, so we haveR p x N p x -1 + 5 log T N p x -1 ≥ µ * p-1 -2 5 log T ϵB p-1 .Combine ( 2) and ( 3) together, we getR p x ≥ 2N p x µ * p-1 - 5 log T N p x -1 - 5 log T ϵB p-1 .Let R p x denote the cumulative regret of playing arm x during phase p, we haveR p x ≤ 2N p x 5 log T N p x -1 + 5 log T ϵB p-1 + Φ ≤ 2 6N p x log T + N p x 5 log T ϵB p-1 + N p x Φ .The first term from the gap between the expected reward of best estimated arm and the selected sub-optimal arm. The second term from the deviation between the best estimated arm and optimal expected per-round reward of the (p -1)-th phase. And the last is the discretization error during phase p -1. Let S p denote the set of arms in phase p. According to Jensen's inequality1 |S p | x∈Sp N p x ≤ 1 |S p | x∈Sp N p x ≤ ϵB p .Then we obtainx∈Sp N p x ≤ |S p | ϵB p ≤ B p ϵ log log T .Consider all selected arms during phase p and the stop condition of the compare strategy, we haveR p S ≤ 2 x∈Sp 6N p x log T + N p x 5 log T ϵB p-1 + N p x Φ ≤ 3B p log log T 5 log T ϵB p-1 + Φ + 2 6 log T x∈Sp N p x ≤ 3B p log log T 5 log T ϵB p-1 + Φ + 3 6B p log T ϵ log log T .For the incurred regret by the deviation between the expected reward of best estimated arm and the selected sub-optimal arm, we haveϕ-1 p=1 3 6B p log T ϵ log log T ≤ 6 6B ϕ-1 log T ϵ log log T ≤ 6 6T log T ϵ log log T ≤ Õ T d+1 d+2.For the incurred regret the deviation between the best estimated arm and optimal expected per-round reward, we haveϕ-1 p=1 3B p log log T 5 log T ϵB p-1 ≤ 6B ϕ-1 5 log T ϵB ϕ-2 ≤ 6 √ T 5 log T ϵ .For the incurred regret of the discretization error during one phase, we obtainϕ-1 p=1 3B p Φ log log T ≤ 6B ϕ-1 Φ log log T ≤ Õ T d+1 d+2.Combine them together, we getϕ-1 p=1 R p S ≤ Õ T d+1 d+2.Then we consider the total cumulative regret during the exploration part. Let R ϕ S denote the regret incurred in the last part. According to that the value of ry -(5 log T )/n y is non-decreasing and the relationship between B ϕ and B ϕ-1 , we haveR ϕ S ≤ R ϕ-1 S .Then the regret incurred by the exploration isϕ p=0 R p S ≤ 2 ϕ-1 p=0 R p S ≤ Õ T d+1 d+2.Consider the selected arm y after the exploration and let R y S denote the regret due to selecting it.According to the stop condition of compare strategy, we havery ≥ µ * S -2 5 log T ϵB ϕ-1 .Then for the regretR y S ≤ 2T 5 log T ϵB ϕ-1 ≤ Õ T d+1 d+2.Based on the clean event, we haveE[R S (T )|E] = R y S + ϕ p=0 R p S ≤ Õ T d+1 d+2.Then the regret isR S (T ) = E[R S (T )|E] • P(E) + E[R S (T )|¬E] • P(¬E) ≤ [ Õ T d+1 d+2 ](1 -1/T ) + 1 ≤ Õ T d+1 d+2.Combine it with the discretization error, then we complete the proof.To ease the reading, let c = 5. For all arms x t ∈ X and all rounds t ∈ [T ], the gap between the mean reward and the expectation could be bounded with probability 1 -T -1 :|µ(x t ) -rxt | ≤ 5 log T n xt , ∀t ∈ [T ].We call this 'clean event' E and mainly analyze the regret based on E. Assume the MBAD algorithm consume all time horizons during the ϕ-th phase. For the stochastic Lipschitz instance, we always have ϕ ≤ O log T log log T . Let R p S denote the regret for the p-th phase. For the first phase, we haveR 1 X ≤ N 1 ≤ B 1 ≤ √ T . Then we consider R p S , 1 < p ≤ ϕ.For phase p, we consider the best estimate arm y at the start of the p-th phase. If x * p-1 is discarded in phase p -1, according to the stop condition of compare strategy, we havery ≥ µ * p-1 - 5 log T n y - 5 log T n x * p-1 ≥ µ * p-1 -2 5 log T b p-1 .For arbitrary discarded arm x, let R p x and N p x denote the accumulated reward and total number of pulls during phase p, respectively. Notice that the value of ry -(5 log T )/n y is non-decreasing, so we haveR p x N p x -1 + 5 log T N p x -1 ≥ µ * p-1 -2 5 log T b p-1 .Then we getR p x ≥ 2N p x µ * p-1 - 5 log T N p x -1 - 5 log T b p-1 .Let R p x denote the cumulative regret of playing arm x during phase p, we haveR p x ≤ 2N p x 5 log T N p x -1 + 5 log T b p-1 .Similarly, the first term from the gap between the expected reward of best estimated arm and the selected sub-optimal arm. The second term from the deviation between the best estimated arm and optimal expected per-round reward of the (p -1)-th phase. Recall the setY i = {x ∈ X : 2 -i ≤ ∆(x) < 2 1-i , i ∈ N},and the definition of zooming dimensiond z = inf β≥0 |S j | ≤ O(ϵ β ), ϵ = O(2 -j ), ∀j ∈ N . Pick δ = log 2 T T 1 dz +2 , if 5 log T N p x -1 + 5 log T bp-1 ≤ O(δ), then R p x ≤ O(δN p x ). If 5 log T bp-1 > Ω(δ), then b p-1 = O(log T )∆ -2 (x). If 5 log T N p x -1 > Ω(δ), then N p x = O(log T )∆ -2 (x).According the stop condition of the compare strategy and the definition of zooming dimension, we haveR p X ≤ δN p + i:2 -i >δ x∈Yi R p x ≤ δN p + O((log T ) 2 )δ dz+1 ≤ δT + O((log T ) 2 )δ dz+1 ≤ O(T dz +1 dz +2 (log T ) 2 dz +2 ).Then we haveϕ p=1 R p X ≤ ϕ p=1 O(T dz +1 dz +2 (log T ) 2 dz +2 ) ≤ Õ(T dz +1 dz +2 ).Based on the clean event, we haveE[R X (T )|E] ≤ ϕ p=1 R p X ≤ Õ(T dz +1 dz +2 ).The regret isR X (T ) ≤ Õ(T dz +1 dz +2 )(1 -1/T ) + 1 ≤ Õ(T dz +1 dz +2 ).Then we complete the proof.We present the pseudocode. The algorithm also maintains the index x, the mean reward estimator rx , and the number of pulls n x for one arm in memory. The constants c and η are two parameters to balance the exploration and exploitation. For each phase p, the algorithm determines the budget b p of samples for each probe, the number of total pulls N p during the phase, and the usage factor λ p obtained after the phase. Once the arm x is discarded, the algorithm chooses the next probe by adding η (c log T )/(n x L 2 ), which is the step size and has the same order as the confidence radius of arm x.We have the following theoretical result.Theorem 3. For Lipschitz bandits with time horizon T and Lipschitz constant L, Algorithm 7 with c ≥ 5 and η = 1/3 achieves regretR X (T ) ≤ Õ(T dz +1 dz +2 ),using O(1) stored arms, where d z ≤ 1 is the zooming dimension of space X .Algorithm 7 A Simple Algorithm Input: rounds T , Lipschitz constant L, constant c and η1: y ← 0, ry ← 0, n y ← 0, B 1 ← √ T . 2: for p = 1, 2, • • • do 3: x ← 0, N p ← 0. 4: while x ≤ 1 do 5: rx ← 0, n x ← 0, b p ← (B p /3) 2/3 (c log T ) 1/3 L -2/3 . 6: while n x ≤ b p or n y ≤ b p do 7: N p ← N p + 1. 8:Pull the least played arm between x and y, and select a random arm if there not exists a least played arm.Update rx , n x , ry , n y . 10:if min{r x + (c log T )/n x , 1} < max{r y -(c log T )/n y , 0} then 11:Break.12: x ← x + η (c log T )/(n x L 2 ). The proof closely mirrors that of Theorem 2. To ease the reading, let c = 5 and η = 1/3. For all arms x t ∈ X and all rounds t ∈ [T ], the gap between the mean reward and the expectation could be bounded with probability 1 -T -1 :else if max{r x -(c log T )/n x , 0} > max{r y -(c log T )/n y ,|µ(x t ) -rxt | ≤ 5 log T n xt , ∀t ∈ [T ].We call this 'clean event' E and mainly analyze the regret based on E. For the number of phases ϕ, we always have ϕ ≤ O log T log log T . Notice that the number of total pulls during the phase p,N p ≤ 3b p L b p 5 log T ≤ 3(B p /3) 2/3 (5 log T ) 1/3 (B p /3) 2/3 (5 log T ) 1/3 5 log T = B p .Let R p S denote the regret for the p-th phase. For the first phase, we haveR 1 X ≤ N 1 ≤ B 1 ≤ √ T .Then we consider R p S , 1 < p ≤ ϕ. For phase p, we consider the best estimate arm y at the start of the p-th phase. If x * p-1 is discarded in phase p -1, according to the stop condition of compare strategy, we havery ≥ µ * p-1 - 5 log T n y - 5 log T n x * p-1 ≥ µ * p-1 -2 5 log T b p-1 .For arbitrary discarded arm x, let R p x and N p x denote the accumulated reward and total number of pulls during phase p, respectively. Notice that the value of ry -(5 log T )/n y is non-decreasing, so we haveR p x N p x -1 + 5 log T N p x -1 ≥ µ * p-1 -2 5 log T b p-1 .Then we getR p x ≥ 2N p x µ * p-1 - 5 log T N p x -1 - 5 log T b p-1 .Let R p x denote the cumulative regret of playing arm x during phase p, we haveR p x ≤ 2N p x 5 log T N p x -1 + 5 log T b p-1 .Similarly, the first term from the gap between the expected reward of best estimated arm and the selected sub-optimal arm. The second term from the deviation between the best estimated arm and optimal expected per-round reward of the (p -1)-th phase. Recall the setY i = {x ∈ X : 2 -i ≤ ∆(x) < 2 1-i , i ∈ N},and the definition of zooming dimensiond z = inf β≥0 |S j | ≤ O(ϵ β ), ϵ = O(2 -j ), ∀j ∈ N . Pick δ = log 2 T T 1 dz +2 , if 5 log T N p x -1 + 5 log T bp-1 ≤ O(δ), then R p x ≤ O(δN p x ). If 5 log T bp-1 > Ω(δ), then b p-1 = O(log T )∆ -2 (x). If 5 log T N p x -1 > Ω(δ), then N p x = O(log T )∆ -2 (x).According the stop condition of the compare strategy and the definition of zooming dimension, we haveR p X ≤ δN p + i:2 -i >δ x∈Yi R p x ≤ δN p + O((log T ) 2 )δ dz+1 ≤ δT + O((log T ) 2 )δ dz+1 ≤ O(T dz +1 dz +2 (log T ) 2 dz +2 ).Then we haveϕ p=1 R p X ≤ ϕ p=1 O(T dz +1 dz +2 (log T ) 2 dz +2 ) ≤ Õ(T dz +1 dz +2 ).Based on the clean event, we haveE[R X (T )|E] ≤ ϕ p=1 R p X ≤ Õ(T dz +1 dz +2 ).The regret isR X (T ) ≤ Õ(T dz +1 dz +2 )(1 -1/T ) + 1 ≤ Õ(T dz +1 dz +2). Then we complete the proof.Different variances. Keeping other setting of Figure 1 Justification: The main claims in the abstract and introduction accurately reflect the paper's contributions and scope as they succinctly outline the problem addressed, the approach taken, and the novel insights or advancements achieved within the specified research domain.• The answer NA means that the abstract and introduction do not include the claims made in the paper.• The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.• The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.• It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.• The answer NA means that paper does not include experiments requiring code.• Please see the NeurIPS code and data submission guidelines (https://nips.cc/ public/guides/CodeSubmissionPolicy) for more details.• While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).• The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: //nips.cc/public/guides/CodeSubmissionPolicy) for more details.• The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.• The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones are omitted from the script and why.• At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).• Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 


Decision: This paper considers Lipschitz bandits, a version of multi-armed bandit problem where the arms are on $[0,1]^d$ and the mean reward function is $L=1$ Lipchitz on that. The authors proposed MBAD algorithm that improves time and space complexity over existing algorithms. 

The problem setting is known, and the contribution would be great if it were presented appropriately. For us, the largest concern is its solidness. Rev Bcg5 considers the mathematical presentation unclear and the claimed results hard to verify. I hope the authors revise the paper based on the reviews.

Reviews: review: paper_summary: paper_summary: This paper studies the Lipschitz bandit problem with a memory constraint. There are two algorithms proposed by the authors. The Memory Bounded Uniform Discretization (MBUD) algorithm uses a fixed discretization over the metric space and implements a strategy which explores first and then commits to an exploitation phase. The second algorithm, called Memory Bounded Adaptive Discretization (MBAD) , swaps arms in and out of the memory while creating a mesh over the metric space adaptively (ala zooming). The authors prove upper bounds which match lower bounds from previous work for Lipschitz bandits without memory constraints while maintaining linear time complexity and constant space complexity. Finally, the authors perform experimental validation of the theoretical results on small 1-dimensional datasets.
strength_weakness: strength_weakness: I am unclear about the novelty and contributions of the paper. The problem formulation (limited memory) is new in the Lipschitz bandit setting but it has been studied in several papers in bandits with finite arms (as the authors point out in the related works). Moreover, the proof techniques used in the paper appear standard - MBAD is based on zooming introduced by kleinberg et al., the clean event analysis is from the recent textbook of Slivkins (and their papers), MBUD is based on an explore first strategy resembling the naive Explore-then-Commit algorithm (which trivially satisfies the O(1) memory constraint). In all, I’m not sure what specific parts of the paper are being claimed as novel vs that from prior work.

The experiments in this paper are very limited - only a 1 dimensional interval with an L1 metric. To show real world applicability, it would be nice to have results in higher dimensions and also on real world datasets (since that was the original motivation).

Minor/Typo:
I think the caption for Fig 1 should clarify what is on the X and Y axes. It is obvious from context but it would be nice to have from a readability perspective.
questions: questions: 1. From what I recall, the Kleinberg survey paper proves bounds for all metric spaces, whereas in this paper only the L1 metric on [0, 1]^d is considered. Is there any reason why similar techniques from that paper would not translate to the bounded memory setting for all metric spaces? 
2. On line 229, the authors state “computational workload of the MBUD algorithm is characterized by a constant per-round operation,” but don’t the subroutines (like CROSSCUBE, GENERATECUBE etc) have time complexity depending on T? Is this statement meant to ignore sublunar factors?
3. Do we need to know the zooming dimension beforehand for MBAD? If so, it should be mentioned in the paper as it it was not clear to me.
limitations: limitations: The Lipschitz constant needs to be known beforehand to apply these algorithms.
paper_summary: paper_summary: The paper investigates a multi-armed bandit problem where the action space is a metric space a stochastic Lipschitz rewards. The authors present algorithms that use a constant amount of memory and achieve a near-optimal regret. This improves on previous results that had heavy memory usage.
strength_weakness: strength_weakness: While the result is great, the ideas presented in the paper are modifications of existing methods
questions: questions: * Line 136: Should be norm rather than absolute value, right?
* Line 156: Definition of the mesh seems like it contains ALL elements of a cover set. Should be only one per set?
* Line 196: The use of $O$ notation for the fraction is nonstandard and confusing (as is it looks like $O(1)$)
limitations: limitations: I did not find the limitations presented as sufficient and I would like to see more discussion on the downsides of the presented algorithm and future directions of research.
paper_summary: paper_summary: The paper considers regret minimization for Lipschitz bandits with time horizont $T$ and proposes an algorithm that provably achieves nearly optimal regret while having strictly smaller (by a factor of $T$) time (of order $O(T)$) and memory complexity (of order $O(1)$). This is achieved by considering a tree-like embedding of the state space and pairwise comparison between elements of the tree. A suboptimal method with uniform discretization called MBUD has dependence on the covering dimension of the state space, while MBAD, a method with adaptive discretization, instead has dependence only on the zooming dimension.
strength_weakness: strength_weakness: 1) It is not simple to parse algorithms in their current form in a short amount of time. Although you give comprehensive descriptions in text, I believe adding illustrations or additional explanations will significantly improve clarity of your algorithms. 

2) I would appreciate a more explicit comparison with previous work - what parts of the algorithms were already reported in the literature?
questions: questions: 1) Could you provide intuition behind your node exploration process i.e. line 2 in Algorithm 2?

2) (196) Should each cross exploration phase explore instead $O(\\log \\log T)$ cubes?

3) Could you please refer to previous works that worked on reducing time and memory complexity for bandits, and, more specifically, whether it is a common thing to achieve the same regret bounds for settings with restricted time and memory?

4) Could you please comment what part of the proposed algorithms has already been used before in literature? I am especially interested whether cube generation i.e. the way you do tree search has been used before in this context.
limitations: limitations: The authors have addressed limitations adequately.
paper_summary: paper_summary: The paper proposes two algorithms for Lipschitz bandit problems, with improved time complexity and memory requirements.
strength_weakness: strength_weakness: The paper is sloppy to the extent that it is difficult to understand the authors' algorithm or verify their claims. To be specific, consider the following sentences, all taken from a single two-paragraph subsection (section 2.2):
1. "Let $\\{\mathcal{X}_1, \dotsc, \mathcal{X}_N\\}[\mathcal{X}_i \subset \mathcal{X}]$ be an cover of the action space $\mathcal{X}$" --- okay, what is the $\\{\dotsc\\}[\dotsc]$ notation?  
2. "Let $\epsilon$ denote the maximum diameter of $\mathcal{X}_i$ for all $i \in [N]$." --- okay, but what is a diameter? Are we in a metric space? This hasn't been specified. 
3. "Then the arm set $S = \\{ x_i \mid x_i \in \mathcal{X}_i, i \in [N]\\}$ is an $\epsilon$-mesh."  --- what set is this? Now, I presume that the authors mean to say that they want $S$ to be any set that contains a single element chosen arbitrarily from each of the $\mathcal{X}_i$, but that's not written, instead the authors said its __the__ set, but the right hand side does not specify any unique set. Also, the concept of an $\epsilon$-mesh has not been defined, and when its defined, it needs to be with respect to some metric. And if this description was meant to be the definition of an $\epsilon$-mesh... then that's not clear either (and the definition given by the work the authors state these definitions are from, i.e. Slivkins 2019, is _very_ clear---all the authors needed to do was copy it).
4. "The covering dimension $d$ of the action space $\mathcal{X}$ is defined as $d=\inf_{\alpha \geq 0}\\{|\mathcal{S}| \leq \epsilon^{-\alpha}, \forall \epsilon > 0\\}$." But the set $\mathcal{S}$ does not depend on $\epsilon$ (not even implicitly)... (the correct definition, I presume, would be to ask that $\mathcal{S}\_{\epsilon}$ is a minimal $\epsilon$-cover of $\mathcal{X}$ in some metric $D$, and then have that infimum include $\mathcal{S}_\epsilon$ and not $\mathcal{S}$.)
5. "Define $\mathcal{Y}\_j = \\{x \in \mathcal{X} \colon 2^{-j} \leq \Delta(x) \leq 2^{1-j}, j \in \mathbb{N}\\}$, then the set $\mathcal{Y}_j$ contains all arms whose gap is between $2^{-j}$ and $2^{1-j}$." --- but $j \in \mathbb{N}$ is within the constructions of the set on the RHS, which could be read as asking that the condition holds for all such $j$, or for some $j$, but it breaks the dependence of the right hand side on the subscript $j$ of $\mathcal{Y}_j$. Of course, the definition shouldn't have the $j \in \mathbb{N}$ inside the $\\{ \dotsc \\}$ on the right hand side of the definition. 
6. "Consider the $\epsilon$-mesh $\mathcal{S}_j$ for space $\mathcal{Y}_j$." --- __the__ $\epsilon$-mesh? Also, $\mathcal{S}_j$ hasn't been defined. This should say instead 'fix some $\epsilon > 0$ and let $\mathcal{S}_j$ be an $\epsilon$-mesh of $\mathcal{Y}_j$', or something like that.
7. "[...] the zooming dimension focuses only on the set $\mathcal{Y}_j$" --- no, the zooming dimension depends on all the sets $\mathcal{Y}_1, \mathcal{Y}_2, \dotsc$, not only a single one of those sets.

While each individual mistake or ambiguity can be resolved easily enough, verifying the authors claims would require me to rewrite everything myself, and this goes beyond what I'm willing to do (and should do...).  The whole paper is like this, and it's just not acceptable.

I would urge the authors to, in the future, have someone _not intimately familiar with the work_ proof-read the work.

Note, I put down confidence as "5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully." --- I am indeed very familiar with the related work, but I have not checked the math/other details carefully. It's too much work to read it. I am absolutely certain, however, that this level falls short of any level of clarity that might be expected in published work.
questions: questions: .
limitations: limitations: .

Comments: title: Response
comment: I appreciate the authors response.

Since the paper's contribution is mainly theoretical, I'm not too worried about the state of the experiments currently (although more is always better). However, the technical significance of the paper seems limited to me from the authors responses to me and other reviewers.

For instance, the tree based exploration of a metric space has been done in prior work in lipschitz bandits. See section 8 in [1].

Thus, I maintain my score.

[1] Kleinberg et al. Bandits and experts in metric spaces
Dear reviewers,

Please respond to the author's response if you have not done it yet. Thank you for your attention and efforts.

Best,
AC
Thank you for your response. I was aware of the flowcharts in Appendix A at the time of writing the review, but I did not find them particularly intuitive or explanatory. Considering the concerns raised by Reviewer Bcg5, I agree that the paper could have been written more clearly. I will maintain my score for now and closely follow the discussion surrounding the issues raised by Reviewer Bcg5.
Thank you very much for your feedback. We will amend the notation to clarify this point explicitly in the revised manuscript. We greatly appreciate your attention to detail, and we are committed to improving the precision and clarity of the definition based on your valuable feedback.
Thank you for the detailed response. I still don't find the insights enough to increase my score, I will keep it as-is for now and wait for further discussion with the other reviewers.

I still don't think Line 156 is correct. I understand the definition, but the notation is wrong - from the current notation it seems you take all $x_i\in X_i$, not a single element.
Thank you very much for your prompt response and valuable feedback. We appreciate the opportunity to improve our paper through your insights. Below is our reply:

1. **Acknowledgment:** We sincerely appreciate the constructive feedback from each reviewer, which has helped identify aspects of our paper that were unclear. We would like to express our gratitude once again to all the reviewers for their thoughtful comments. In our rebuttal, we have provided further explanations and worked diligently to improve the paper's quality, which we believe is one of the key values and purposes of the rebuttal period.

2. **Presentation Feedback:** While reviewers q7Fp and svqm pointed out specific aspects where the algorithm's presentation could be improved, it is also worth noting that the other three reviewers, including q7Fp and svqm, rated the presentation as "**3 - good**". This suggests that the presentation is generally well-received, though we acknowledge there is always room for refinement to enhance clarity and understanding.

3. **Implementation Variability:** You mentioned that "if I gave the algorithm blocks in this paper to 5 strong master's students to implement, they would each return with a different algorithm". This variability is quite common, as many algorithms can be implemented in multiple ways. For instance, in the Lipschitz bandits area, the well-known Zooming algorithm, when only considering the original paper's description, can be implemented in several different ways.

4. **Section 2.2:** As mentioned in our rebuttal, we introduced the concepts of Covering Dimension and Zooming Dimension primarily to provide background for readers who may be unfamiliar with them. While this section enhances understanding, many papers in the field do not include such introductions. Of course, we will continue to refine this section to make it more accurate and clear, but its presence or absence does not affect the paper's overall framework and contributions.
To clarify, the issue isn't section 2.2. That is just an example. This level of "messiness" is present throughout.

This isn't a matter of the definitions being hard to understand due to a lack of space: clear definitions would not take more space at all. 

And, on that point, if, as you claim, you could remove section 2.2 from the paper, and still fully understand the contribution... why is that section in your paper? 

__To area chair:__ I fully stand by my recommendation to reject this work. I'd like to point out that the other reviewer's comments were:
1. Reviewer q7Fp:  "I did have a little trouble reading the parts about the crosscut and generating cubes but it might just be me not being familiar with prior work in the area."
2. Reviewer svqm: "It is not simple to parse algorithms in their current form in a short amount of time. Although you give comprehensive descriptions in text, I believe adding illustrations or additional explanations will significantly improve clarity of your algorithms. "

It's not a matter of Reviewer q7Fp being unfamiliar with prior work---I am familiar with it, and those parts require deciphering, not reading. And its not a matter of Reviewer svqm struggling to parse the algorithms in a short time---the algorithms are not parsable. Additional illustrations are nice, but should not be necessary for a skilled researcher to parse an algorithm. I am certain that if I gave the algorithm blocks in this paper to 5 strong master's students to implement, they would each return with a different algorithm. Reviewer mKhe states that "The paper has good presentation"---I find this wild; I can only presume that the reviewer did not try to understand the details of how the algorithm works, or study the proofs in any depth; then yes, at a high level, the paper might seem reasonable---but this is a theory paper, high level does not suffice.